Sponsored Search, Market Equilibria, and the Hungarian Method

Abstract : 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.
Document type :
Conference papers
Jean-Yves Marion and Thomas Schwentick. 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Mar 2010, Nancy, France. pp.287-298, 2010, Proceedings of the 27th Annual Symposium on the Theoretical Aspects of Computer Science
Liste complète des métadonnées


https://hal.inria.fr/inria-00455288
Contributor : Publications Loria <>
Submitted on : Monday, February 15, 2010 - 10:56:51 AM
Last modification on : Monday, February 15, 2010 - 4:10:14 PM
Document(s) archivé(s) le : Thursday, September 23, 2010 - 11:22:59 AM

File

duetting_v2.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00455288, version 2

Collections

Citation

Paul Dütting, Monika Henzinger, Ingmar Weber. Sponsored Search, Market Equilibria, and the Hungarian Method. Jean-Yves Marion and Thomas Schwentick. 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Mar 2010, Nancy, France. pp.287-298, 2010, Proceedings of the 27th Annual Symposium on the Theoretical Aspects of Computer Science. <inria-00455288v2>

Share

Metrics

Record views

152

Document downloads

122