Sponsored search, market equilibria, and the Hungarian Method

Dütting P, Henzinger MH, Weber I. 2013. Sponsored search, market equilibria, and the Hungarian Method. Information Processing Letters. 113(3), 67–73.

Download (ext.)

Journal Article | Published | English

Scopus indexed
Author
Dütting, Paul; Henzinger, MonikaISTA ; Weber, Ingmar
Abstract
Matching markets play a prominent role in economic theory. A prime example of such a market is the sponsored search market. Here, as in other markets of that kind, market equilibria correspond to feasible, envy free, and bidder optimal outcomes. For settings without budgets such an outcome always exists and can be computed in polynomial-time by the so-called Hungarian Method. Moreover, every mechanism that computes such an outcome is incentive compatible. We show that the Hungarian Method can be modified so that it finds a feasible, envy free, and bidder optimal outcome for settings with budgets. We also show that in settings with budgets no mechanism that computes such an outcome can be incentive compatible for all inputs. For inputs in general position, however, the presented mechanism—as any other mechanism that computes such an outcome for settings with budgets—is incentive compatible.
Publishing Year
Date Published
2013-02-15
Journal Title
Information Processing Letters
Publisher
Elsevier
Volume
113
Issue
3
Page
67-73
ISSN
IST-REx-ID

Cite this

Dütting P, Henzinger MH, Weber I. Sponsored search, market equilibria, and the Hungarian Method. Information Processing Letters. 2013;113(3):67-73. doi:10.1016/j.ipl.2012.11.006
Dütting, P., Henzinger, M. H., & Weber, I. (2013). Sponsored search, market equilibria, and the Hungarian Method. Information Processing Letters. Elsevier. https://doi.org/10.1016/j.ipl.2012.11.006
Dütting, Paul, Monika H Henzinger, and Ingmar Weber. “Sponsored Search, Market Equilibria, and the Hungarian Method.” Information Processing Letters. Elsevier, 2013. https://doi.org/10.1016/j.ipl.2012.11.006.
P. Dütting, M. H. Henzinger, and I. Weber, “Sponsored search, market equilibria, and the Hungarian Method,” Information Processing Letters, vol. 113, no. 3. Elsevier, pp. 67–73, 2013.
Dütting P, Henzinger MH, Weber I. 2013. Sponsored search, market equilibria, and the Hungarian Method. Information Processing Letters. 113(3), 67–73.
Dütting, Paul, et al. “Sponsored Search, Market Equilibria, and the Hungarian Method.” Information Processing Letters, vol. 113, no. 3, Elsevier, 2013, pp. 67–73, doi:10.1016/j.ipl.2012.11.006.
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
OA Open Access

Export

Marked Publications

Open Data ISTA Research Explorer

Sources

arXiv 0912.1934

Search this title in

Google Scholar