Sponsored search, market equilibria, and the Hungarian Method
Dütting P, Henzinger MH, Weber I. 2010. Sponsored search, market equilibria, and the Hungarian Method. 27th International Symposium on Theoretical Aspects of Computer Science. STACS: Symposium on Theoretical Aspects of Computer Science, LIPIcs, vol. 5, 287–298.
Download (ext.)
https://doi.org/10.4230/LIPIcs.STACS.2010.2463
[Published Version]
Conference Paper
| Published
| English
Scopus indexed
Author
Dütting, Paul;
Henzinger, MonikaISTA ;
Weber, Ingmar
Series Title
LIPIcs
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.
Publishing Year
Date Published
2010-03-09
Proceedings Title
27th International Symposium on Theoretical Aspects of Computer Science
Publisher
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Volume
5
Page
287-298
Conference
STACS: Symposium on Theoretical Aspects of Computer Science
Conference Location
Nancy, France
Conference Date
2010-03-04 – 2010-03-06
ISBN
ISSN
IST-REx-ID
Cite this
Dütting P, Henzinger MH, Weber I. Sponsored search, market equilibria, and the Hungarian Method. In: 27th International Symposium on Theoretical Aspects of Computer Science. Vol 5. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2010:287-298. doi:10.4230/LIPICS.STACS.2010.2463
Dütting, P., Henzinger, M. H., & Weber, I. (2010). Sponsored search, market equilibria, and the Hungarian Method. In 27th International Symposium on Theoretical Aspects of Computer Science (Vol. 5, pp. 287–298). Nancy, France: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.STACS.2010.2463
Dütting, Paul, Monika H Henzinger, and Ingmar Weber. “Sponsored Search, Market Equilibria, and the Hungarian Method.” In 27th International Symposium on Theoretical Aspects of Computer Science, 5:287–98. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2010. https://doi.org/10.4230/LIPICS.STACS.2010.2463.
P. Dütting, M. H. Henzinger, and I. Weber, “Sponsored search, market equilibria, and the Hungarian Method,” in 27th International Symposium on Theoretical Aspects of Computer Science, Nancy, France, 2010, vol. 5, pp. 287–298.
Dütting P, Henzinger MH, Weber I. 2010. Sponsored search, market equilibria, and the Hungarian Method. 27th International Symposium on Theoretical Aspects of Computer Science. STACS: Symposium on Theoretical Aspects of Computer Science, LIPIcs, vol. 5, 287–298.
Dütting, Paul, et al. “Sponsored Search, Market Equilibria, and the Hungarian Method.” 27th International Symposium on Theoretical Aspects of Computer Science, vol. 5, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2010, pp. 287–98, doi:10.4230/LIPICS.STACS.2010.2463.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Link(s) to Main File(s)
Access Level
Open Access
Export
Marked PublicationsOpen Data ISTA Research Explorer
Sources
arXiv 0912.1934