• 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
 
 
Thèse de Doctorat
DOI
https://doi.org/10.11606/T.45.2014.tde-25022014-112039
Document
Auteur
Nom complet
Rafael Crivellari Saliba Schouery
Adresse Mail
Unité de l'USP
Domain de Connaissance
Date de Soutenance
Editeur
São Paulo, 2014
Directeur
Jury
Fernandes, Cristina Gomes (Président)
Bornstein, Claudson Ferreira
Laber, Eduardo Sany
Mascarenhas, Walter Figueiredo
Miyazawa, Flávio Keidi
Titre en portugais
Problemas de alocação e precificação de itens
Mots-clés en portugais
Algoritmo de Aproximação
Leilão
Otimização Combinatória
Precificação
Programação Inteira
Teoria dos Jogos Algorítmica
Resumé en portugais
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.
Titre en anglais
Allocation and pricing problems
Mots-clés en anglais
Algorithmic Game Theory
Approximation Algorithm
Auction
Combinatorial Optimization
Integer Programming
Pricing
Resumé en anglais
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.
 
AVERTISSEMENT - Regarde ce document est soumise à votre acceptation des conditions d'utilisation suivantes:
Ce document est uniquement à des fins privées pour la recherche et l'enseignement. Reproduction à des fins commerciales est interdite. Cette droits couvrent l'ensemble des données sur ce document ainsi que son contenu. Toute utilisation ou de copie de ce document, en totalité ou en partie, doit inclure le nom de l'auteur.
tese.pdf (1.01 Mbytes)
Date de Publication
2014-03-17
 
AVERTISSEMENT: Le matériau se réfère à des documents provenant de cette thèse ou mémoire. Le contenu de ces documents est la responsabilité de l'auteur de la thèse ou mémoire.
  • 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/
Tous droits de la thèse/dissertation appartiennent aux auteurs
CeTI-SC/STI
Bibliothèque Numérique de Thèses et Mémoires de l'USP. Copyright © 2001-2024. Tous droits réservés.