[{"doi":"10.4230/LIPICS.STACS.2010.2463","language":[{"iso":"eng"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_processing_charge":"No","date_updated":"2023-02-21T16:30:02Z","type":"conference","oa_version":"Published Version","day":"09","alternative_title":["LIPIcs"],"publication_identifier":{"issn":["1868-8969"],"isbn":["978-3-939897-16-3"]},"scopus_import":"1","arxiv":1,"date_published":"2010-03-09T00:00:00Z","external_id":{"arxiv":["0912.1934"]},"page":"287-298","title":"Sponsored search, market equilibria, and the Hungarian Method","publication":"27th International Symposium on Theoretical Aspects of Computer Science","oa":1,"related_material":{"record":[{"relation":"earlier_version","status":"public","id":"11838"}]},"_id":"11838","publication_status":"published","abstract":[{"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.","lang":"eng"}],"citation":{"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>","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.","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>.","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.","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>","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."},"main_file_link":[{"open_access":"1","url":"https://doi.org/10.4230/LIPIcs.STACS.2010.2463"}],"quality_controlled":"1","author":[{"first_name":"Paul","last_name":"Dütting","full_name":"Dütting, Paul"},{"first_name":"Monika H","last_name":"Henzinger","full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"},{"last_name":"Weber","first_name":"Ingmar","full_name":"Weber, Ingmar"}],"extern":"1","year":"2010","intvolume":"         5","date_created":"2022-08-12T11:45:49Z","conference":{"name":"STACS: Symposium on Theoretical Aspects of Computer Science","end_date":"2010-03-06","location":"Nancy, France","start_date":"2010-03-04"},"month":"03","status":"public","volume":5,"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik"},{"volume":3,"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","intvolume":"         3","status":"public","month":"02","conference":{"start_date":"2009-02-26","location":"Freiburg, Germany","name":"STACS: Symposium on Theoretical Aspects of Computer Science","end_date":"2009-02-28"},"date_created":"2022-08-18T06:57:25Z","quality_controlled":"1","extern":"1","author":[{"full_name":"Baykan,  Eda","last_name":"Baykan","first_name":" Eda"},{"orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","last_name":"Henzinger","first_name":"Monika H"},{"first_name":"Stefan F.","last_name":"Keller","full_name":"Keller, Stefan F."},{"full_name":"de Castelberg, Sebastian","first_name":"Sebastian","last_name":"de Castelberg"},{"first_name":"Markus","last_name":"Kinzler","full_name":"Kinzler, Markus"}],"citation":{"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>.","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>","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.","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>","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.","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>.","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."},"main_file_link":[{"url":"https://doi.org/10.4230/LIPIcs.STACS.2009.1809","open_access":"1"}],"year":"2009","_id":"11912","oa":1,"publication":"26th International Symposium on Theoretical Aspects of Computer Science","title":"A comparison of techniques for sampling web pages","abstract":[{"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.","lang":"eng"}],"publication_status":"published","page":"13-30","external_id":{"arxiv":["0902.1604"]},"date_published":"2009-02-01T00:00:00Z","scopus_import":"1","publication_identifier":{"issn":["1868-8969"],"isbn":["978-3-939897-09-5"]},"alternative_title":["LIPIcs"],"arxiv":1,"article_processing_charge":"No","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","day":"01","oa_version":"Published Version","date_updated":"2023-02-17T08:57:16Z","type":"conference","language":[{"iso":"eng"}],"doi":"10.4230/LIPICS.STACS.2009.1809"}]