2026-07-21T23:35:11Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:2463 2024-03-06T10:33:23Z ddc:004 open_access

Sponsored Search, Market Equilibria, and the Hungarian Method Dütting, Paul Henzinger, Monika Weber, Ingmar Stable matching truthful matching mechanism general position 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Paul Dütting and Monika Henzinger and Ingmar Weber 2010 Is Part Of LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2010.2463 urn:nbn:de:0030-drops-24636 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2463 eng https://creativecommons.org/licenses/by-nd/3.0/legalcode