• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Tese de Doutorado
DOI
10.11606/T.45.2014.tde-25022014-112039
Documento
Autor
Nome completo
Rafael Crivellari Saliba Schouery
E-mail
Unidade da USP
Área do Conhecimento
Data de Defesa
Imprenta
São Paulo, 2014
Orientador
Banca examinadora
Fernandes, Cristina Gomes (Presidente)
Bornstein, Claudson Ferreira
Laber, Eduardo Sany
Mascarenhas, Walter Figueiredo
Miyazawa, Flávio Keidi
Título em português
Problemas de alocação e precificação de itens
Palavras-chave em português
Algoritmo de Aproximação
Leilão
Otimização Combinatória
Precificação
Programação Inteira
Teoria dos Jogos Algorítmica
Resumo em português
Nessa tese consideramos problemas de alocação e precificação de itens, onde temos um conjunto de itens e um conjunto de compradores interessados em tais itens. Nosso objetivo é escolher uma alocação de itens a compradores juntamente com uma precificação para tais itens para maximizar o lucro obtido, considerando o valor máximo que um comprador está disposto a pagar por um determinado item. Em particular, focamos em três problemas: o Problema da Compra Máxima, o Problema da Precificação Livre de Inveja e o Leilão de Anúncios de Segundo Preço. O Problema da Compra Máxima e o Problema da Precificação Livre de Inveja modelam o problema que empresas que vendem produtos ou serviços enfrentam na realidade, onde é necessário escolher corretamente os preços dos produtos ou serviços disponíveis para os clientes para obter um lucro interessante. Já o Leilão de Anúncios de Segundo Preço modela o problema enfrentado por empresas donas de ferramentas de busca que desejam vender espaço para anunciantes nos resultados das buscas dos usuários. Ambas as questões, tanto a precificação de produtos e serviços quanto a alocação de anunciantes em resultados de buscas, são de grande relevância econômica e, portanto, são interessantes de serem atacadas dos pontos de vista teórico e prático. Nosso foco nesse trabalho é considerar algoritmos de aproximação e algoritmos de programação inteira mista para os problemas mencionados, apresentando novos resultados superiores àqueles conhecidos previamente na literatura, bem como determinar a complexidade computacional destes problemas ou de alguns de seus casos particulares de interesse.
Título em inglês
Allocation and pricing problems
Palavras-chave em inglês
Algorithmic Game Theory
Approximation Algorithm
Auction
Combinatorial Optimization
Integer Programming
Pricing
Resumo em inglês
In this thesis we consider allocation and pricing problems, where we have a set of items and a set of consumers interested in such items. Our objective is to choose an allocation of items to consumers, considering the maximum value a consumer is willing to pay in a specific item. In particular, we focus in three problems: the Max-Buying Problem, the Envy-Free Pricing Problem and the Second-Price Ad Auction. The Max-Buying Problem and the Envy-Free Pricing Problem model a problem faced in reality by companies that sell products or services, where it is necessary to correctly choose the price of the products or services available to clients in order to obtain an interesting profit. The Second-Price Ad Auction models the problem faced by companies that own search engines and desire to sell space for advertisers in the search results of the users. Both questions, the pricing of items and services and the allocation of advertisers in search results are of great economical relevance and, for this, are interesting to be attacked from a theoretical and a practical perspective. Our focus in this work is to consider approximation algorithms and mixed integer programming algorithms for the aforementioned problems, presenting new results superior than the previously known in the literature, as well as to determine the computational complexity of such problems or some of their interesting particular cases.
 
AVISO - A consulta a este documento fica condicionada na aceitação das seguintes condições de uso:
Este trabalho é somente para uso privado de atividades de pesquisa e ensino. Não é autorizada sua reprodução para quaisquer fins lucrativos. Esta reserva de direitos abrange a todos os dados do documento bem como seu conteúdo. Na utilização ou citação de partes do documento é obrigatório mencionar nome da pessoa autora do trabalho.
tese.pdf (1.01 Mbytes)
Data de Publicação
2014-03-17
 
AVISO: O material descrito abaixo refere-se a trabalhos decorrentes desta tese ou dissertação. O conteúdo desses trabalhos é de inteira responsabilidade do autor da tese ou dissertação.
  • Fernandes, Cristina G., and R.C.S. Schouery. Second-Price Ad Auctions with Binary Bids and markets with good competition [doi:10.1016/j.tcs.2013.08.022]. Theoretical Computer Science [online], 2014, vol. 540-541, p. 103-114.
  • Fernandes, Cristina G., e Schouery, Rafael C. S. Approximation Algorithms for the Max-Buying Problem with Limited Supply [doi:10.1007/978-3-642-54423-1_61]. In 3rd International Symposium on Combinatorial Optimization (ISCO). Lecture Notes in Computer Science [online]. Organizador. Springer Berlin Heidelberg, 2014{Volume}, p. 707-718.http://www.teses.usp.br/teses/disponiveis/45/45134/tde-25022014-112039/
  • Fernandes, Cristina G., et al. The Envy-Free Pricing Problem and Unit-Demand Markets [doi:10.1007/978-3-319-09174-7_20]. In 11th Latin American Theoretical INformatics Symposium (LATIN). Lecture Notes in Computer Science [online]. Organizador. Springer International Publishing, 2014{Volume}, p. 230-241.http://www.teses.usp.br/teses/disponiveis/45/45134/tde-25022014-112039/
  • Fernandes, Cristina G., e Schouery, Rafael C. S. Second-Price Ad Auctions with Binary Bids and Markets with Good Competition [doi:10.1007/978-3-642-32147-4_39]. In 2nd International Symposium on Combinatorial Optimization (ISCO). Lecture Notes in Computer Science [online]. Organizador. Springer Berlin Heidelberg, 2012{Volume}, p. 439-450.http://www.teses.usp.br/teses/disponiveis/45/45134/tde-25022014-112039/
Todos os direitos da tese/dissertação são de seus autores
Centro de Informática de São Carlos
Biblioteca Digital de Teses e Dissertações da USP. Copyright © 2001-2019. Todos os direitos reservados.