Sponsored Search, Market Equilibria, and the Hungarian Method - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2010

Sponsored Search, Market Equilibria, and the Hungarian Method

Résumé

Two-sided matching markets play a prominent role in economic theory. A prime example of such a market is the sponsored search market where n advertisers compete for the assignment of one of k sponsored search results, also known as "slots", for certain keywords they are interested in. Here, as in other markets of that kind, market equilibria correspond to stable matchings. In this paper, we show how to modify Kuhn's Hungarian Method (Kuhn, 1955) so that it finds an optimal stable matching between advertisers and advertising slots in settings with generalized linear utilities, per-bidder-item reserve prices, and per-bidder-item maximum prices. The only algorithm for this problem presented so far (Aggarwal et al., 2009) requires the market to be in "general position". We do not make this assumption.
Fichier principal
Vignette du fichier
duetting_v2.pdf (217.44 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00455288 , version 1 (10-02-2010)
inria-00455288 , version 2 (15-02-2010)

Identifiants

  • HAL Id : inria-00455288 , version 2

Citer

Paul Dütting, Monika Henzinger, Ingmar Weber. Sponsored Search, Market Equilibria, and the Hungarian Method. 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Inria Nancy Grand Est & Loria, Mar 2010, Nancy, France. pp.287-298. ⟨inria-00455288v2⟩

Collections

STACS2010
96 Consultations
232 Téléchargements

Partager

Gmail Facebook X LinkedIn More