---
_id: '11838'
abstract:
- lang: eng
  text: 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.
alternative_title:
- LIPIcs
article_processing_charge: No
arxiv: 1
author:
- first_name: Paul
  full_name: Dütting, Paul
  last_name: Dütting
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
- first_name: Ingmar
  full_name: Weber, Ingmar
  last_name: Weber
citation:
  ama: 'Dütting P, Henzinger MH, Weber I. Sponsored search, market equilibria, and
    the Hungarian Method. In: <i>27th International Symposium on Theoretical Aspects
    of Computer Science</i>. Vol 5. Schloss Dagstuhl - Leibniz-Zentrum für Informatik;
    2010:287-298. doi:<a href="https://doi.org/10.4230/LIPICS.STACS.2010.2463">10.4230/LIPICS.STACS.2010.2463</a>'
  apa: 'Dütting, P., Henzinger, M. H., &#38; Weber, I. (2010). Sponsored search, market
    equilibria, and the Hungarian Method. In <i>27th International Symposium on Theoretical
    Aspects of Computer Science</i> (Vol. 5, pp. 287–298). Nancy, France: Schloss
    Dagstuhl - Leibniz-Zentrum für Informatik. <a href="https://doi.org/10.4230/LIPICS.STACS.2010.2463">https://doi.org/10.4230/LIPICS.STACS.2010.2463</a>'
  chicago: Dütting, Paul, Monika H Henzinger, and Ingmar Weber. “Sponsored Search,
    Market Equilibria, and the Hungarian Method.” In <i>27th International Symposium
    on Theoretical Aspects of Computer Science</i>, 5:287–98. Schloss Dagstuhl - Leibniz-Zentrum
    für Informatik, 2010. <a href="https://doi.org/10.4230/LIPICS.STACS.2010.2463">https://doi.org/10.4230/LIPICS.STACS.2010.2463</a>.
  ieee: P. Dütting, M. H. Henzinger, and I. Weber, “Sponsored search, market equilibria,
    and the Hungarian Method,” in <i>27th International Symposium on Theoretical Aspects
    of Computer Science</i>, Nancy, France, 2010, vol. 5, pp. 287–298.
  ista: '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.'
  mla: Dütting, Paul, et al. “Sponsored Search, Market Equilibria, and the Hungarian
    Method.” <i>27th International Symposium on Theoretical Aspects of Computer Science</i>,
    vol. 5, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2010, pp. 287–98, doi:<a
    href="https://doi.org/10.4230/LIPICS.STACS.2010.2463">10.4230/LIPICS.STACS.2010.2463</a>.
  short: P. Dütting, M.H. Henzinger, I. Weber, in:, 27th International Symposium on
    Theoretical Aspects of Computer Science, Schloss Dagstuhl - Leibniz-Zentrum für
    Informatik, 2010, pp. 287–298.
conference:
  end_date: 2010-03-06
  location: Nancy, France
  name: 'STACS: Symposium on Theoretical Aspects of Computer Science'
  start_date: 2010-03-04
date_created: 2022-08-12T11:45:49Z
date_published: 2010-03-09T00:00:00Z
date_updated: 2023-02-21T16:30:02Z
day: '09'
doi: 10.4230/LIPICS.STACS.2010.2463
extern: '1'
external_id:
  arxiv:
  - '0912.1934'
intvolume: '         5'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.4230/LIPIcs.STACS.2010.2463
month: '03'
oa: 1
oa_version: Published Version
page: 287-298
publication: 27th International Symposium on Theoretical Aspects of Computer Science
publication_identifier:
  isbn:
  - 978-3-939897-16-3
  issn:
  - 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
related_material:
  record:
  - id: '11838'
    relation: earlier_version
    status: public
scopus_import: '1'
status: public
title: Sponsored search, market equilibria, and the Hungarian Method
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 5
year: '2010'
...