1 Search Results for "Weber, Ingmar"

Document
DOI: 10.4230/LIPIcs.STACS.2010.2463
Sponsored Search, Market Equilibria, and the Hungarian Method

Authors: Paul Dütting, Monika Henzinger, and Ingmar Weber

Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)

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.
Cite as

Paul Dütting, Monika Henzinger, and Ingmar Weber. Sponsored Search, Market Equilibria, and the Hungarian Method. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 287-298, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{dutting_et_al:LIPIcs.STACS.2010.2463,
  author =	{D\"{u}tting, Paul and Henzinger, Monika and Weber, Ingmar},
  title =	{{Sponsored Search, Market Equilibria, and the Hungarian Method}},
  booktitle =	{27th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{287--298},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-16-3},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{5},
  editor =	{Marion, Jean-Yves and Schwentick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2463},
  URN =		{urn:nbn:de:0030-drops-24636},
  doi =		{10.4230/LIPIcs.STACS.2010.2463},
  annote =	{Keywords: Stable matching, truthful matching mechanism, general position}
}
  • Refine by Author
  • 1 Dütting, Paul
  • 1 Henzinger, Monika
  • 1 Weber, Ingmar

  • Refine by Classification

  • Refine by Keyword
  • 1 Stable matching
  • 1 general position
  • 1 truthful matching mechanism

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2010

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact