---
_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'
...
---
_id: '11912'
abstract:
- lang: eng
  text: As the World Wide Web is growing rapidly, it is getting increasingly challenging
    to gather representative information about it. Instead of crawling the web exhaustively
    one has to resort to other techniques like sampling to determine the properties
    of the web. A uniform random sample of the web would be useful to determine the
    percentage of web pages in a specific language, on a topic or in a top level domain.
    Unfortunately, no approach has been shown to sample the web pages in an unbiased
    way. Three promising web sampling algorithms are based on random walks. They each
    have been evaluated individually, but making a comparison on different data sets
    is not possible. We directly compare these algorithms in this paper. We performed
    three random walks on the web under the same conditions and analyzed their outcomes
    in detail. We discuss the strengths and the weaknesses of each algorithm and propose
    improvements based on experimental results.
alternative_title:
- LIPIcs
article_processing_charge: No
arxiv: 1
author:
- first_name: ' Eda'
  full_name: Baykan,  Eda
  last_name: Baykan
- 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: Stefan F.
  full_name: Keller, Stefan F.
  last_name: Keller
- first_name: Sebastian
  full_name: de Castelberg, Sebastian
  last_name: de Castelberg
- first_name: Markus
  full_name: Kinzler, Markus
  last_name: Kinzler
citation:
  ama: 'Baykan  Eda, Henzinger MH, Keller SF, de Castelberg S, Kinzler M. A comparison
    of techniques for sampling web pages. In: <i>26th International Symposium on Theoretical
    Aspects of Computer Science</i>. Vol 3. Schloss Dagstuhl - Leibniz-Zentrum für
    Informatik; 2009:13-30. doi:<a href="https://doi.org/10.4230/LIPICS.STACS.2009.1809">10.4230/LIPICS.STACS.2009.1809</a>'
  apa: 'Baykan,  Eda, Henzinger, M. H., Keller, S. F., de Castelberg, S., &#38; Kinzler,
    M. (2009). A comparison of techniques for sampling web pages. In <i>26th International
    Symposium on Theoretical Aspects of Computer Science</i> (Vol. 3, pp. 13–30).
    Freiburg, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href="https://doi.org/10.4230/LIPICS.STACS.2009.1809">https://doi.org/10.4230/LIPICS.STACS.2009.1809</a>'
  chicago: Baykan,  Eda, Monika H Henzinger, Stefan F. Keller, Sebastian de Castelberg,
    and Markus Kinzler. “A Comparison of Techniques for Sampling Web Pages.” In <i>26th
    International Symposium on Theoretical Aspects of Computer Science</i>, 3:13–30.
    Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2009. <a href="https://doi.org/10.4230/LIPICS.STACS.2009.1809">https://doi.org/10.4230/LIPICS.STACS.2009.1809</a>.
  ieee: Eda Baykan, M. H. Henzinger, S. F. Keller, S. de Castelberg, and M. Kinzler,
    “A comparison of techniques for sampling web pages,” in <i>26th International
    Symposium on Theoretical Aspects of Computer Science</i>, Freiburg, Germany, 2009,
    vol. 3, pp. 13–30.
  ista: 'Baykan  Eda, Henzinger MH, Keller SF, de Castelberg S, Kinzler M. 2009. A
    comparison of techniques for sampling web pages. 26th International Symposium
    on Theoretical Aspects of Computer Science. STACS: Symposium on Theoretical Aspects
    of Computer Science, LIPIcs, vol. 3, 13–30.'
  mla: Baykan,  Eda, et al. “A Comparison of Techniques for Sampling Web Pages.” <i>26th
    International Symposium on Theoretical Aspects of Computer Science</i>, vol. 3,
    Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2009, pp. 13–30, doi:<a href="https://doi.org/10.4230/LIPICS.STACS.2009.1809">10.4230/LIPICS.STACS.2009.1809</a>.
  short: Eda Baykan, M.H. Henzinger, S.F. Keller, S. de Castelberg, M. Kinzler, in:,
    26th International Symposium on Theoretical Aspects of Computer Science, Schloss
    Dagstuhl - Leibniz-Zentrum für Informatik, 2009, pp. 13–30.
conference:
  end_date: 2009-02-28
  location: Freiburg, Germany
  name: 'STACS: Symposium on Theoretical Aspects of Computer Science'
  start_date: 2009-02-26
date_created: 2022-08-18T06:57:25Z
date_published: 2009-02-01T00:00:00Z
date_updated: 2023-02-17T08:57:16Z
day: '01'
doi: 10.4230/LIPICS.STACS.2009.1809
extern: '1'
external_id:
  arxiv:
  - '0902.1604'
intvolume: '         3'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.4230/LIPIcs.STACS.2009.1809
month: '02'
oa: 1
oa_version: Published Version
page: 13-30
publication: 26th International Symposium on Theoretical Aspects of Computer Science
publication_identifier:
  isbn:
  - 978-3-939897-09-5
  issn:
  - 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: A comparison of techniques for sampling web pages
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 3
year: '2009'
...