Document Open Access Logo

Online Bipartite Matching and Adwords (Invited Talk)

Author Vijay V. Vazirani

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2022.5.pdf
  • Filesize: 0.66 MB
  • 11 pages

Document Identifiers

Author Details

Vijay V. Vazirani
  • University of California, Irvine, CA, USA

Funding

NSF Grant CCF-2230414

Cite As Get BibTex

Vijay V. Vazirani. Online Bipartite Matching and Adwords (Invited Talk). In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 5:1-5:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.MFCS.2022.5

Abstract

The purpose of this paper is to give a "textbook quality" proof of the optimal algorithm, called Ranking, for the online bipartite matching problem (OBM) and to highlight its role in matching-based market design. In particular, we discuss a generalization of OBM, called the adwords problem, which has had a significant impact in the ad auctions marketplace.

Subject Classification

ACM Subject Classification
  • Theory of computation → Algorithmic game theory and mechanism design
Keywords
  • matching-based market design
  • online algorithms
  • ad auctions
  • competitive analysis

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Gagan Aggarwal, Ashwinkumar Badanidiyuru, and Aranyak Mehta. Autobidding with constraints. In International Conference on Web and Internet Economics, pages 17-30. Springer, 2019. Google Scholar
  2. Gagan Aggarwal, Gagan Goel, Chinmay Karande, and Aranyak Mehta. Online vertex-weighted bipartite matching and single-bid budgeted allocations. In Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms, pages 1253-1264, 2011. Google Scholar
  3. Susanne Albers and Sebastian Schubert. Optimal algorithms for online b-matching with variable vertex capacities. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2021. Google Scholar
  4. Benjamin Birnbaum and Claire Mathieu. On-line bipartite matching made simple. ACM Sigact News, 39(1):80-87, 2008. Google Scholar
  5. Niv Buchbinder, Kamal Jain, and Joseph Seffi Naor. Online primal-dual algorithms for maximizing ad-auctions revenue. In European Symposium on Algorithms, pages 253-264, 2007. Google Scholar
  6. Nikhil Devanur and Aranyak Mehta. Online matching in advertisement auctions. In Federico Echenique, Nicole Immorlica, and Vijay V. Vazirani, editors, Online and Matching-Based Market Design. Cambridge University Press, 2022. [To appear] URL: https://www.ics.uci.edu/~vazirani/AdAuctions.pdf.
  7. Nikhil R Devanur, Kamal Jain, and Robert D Kleinberg. Randomized primal-dual analysis of ranking for online bipartite matching. In Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms, pages 101-107. SIAM, 2013. Google Scholar
  8. Federico Echenique, Nicole Immorlica, and Vijay V. Vazirani. One-sided matching markets. In Federico Echenique, Nicole Immorlica, and Vijay V. Vazirani, editors, Online and Matching-Based Market Design. Cambridge University Press, 2022. [To appear] URL: https://www.ics.uci.edu/~vazirani/Chapter2.pdf.
  9. Alon Eden, Michal Feldman, Amos Fiat, and Kineret Segal. An economic-based analysis of ranking for online bipartite matching. In SIAM Symposium on Simplicity in Algorithms, 2021. Google Scholar
  10. David Gale and Lloyd S Shapley. College admissions and the stability of marriage. The American Mathematical Monthly, 69(1):9-15, 1962. Google Scholar
  11. Gagan Goel and Aranyak Mehta. Online budgeted matching in random input models with applications to adwords. In SODA, volume 8, pages 982-991, 2008. Google Scholar
  12. Zhiyi Huang and Thorben Trobst. Online matching. In Federico Echenique, Nicole Immorlica, and Vijay V. Vazirani, editors, Online and Matching-Based Market Design. Cambridge University Press, 2022. [To appear] URL: https://www.ics.uci.edu/~vazirani/Ch4.pdf.
  13. Zhiyi Huang, Qiankun Zhang, and Yuhao Zhang. Adwords in a panorama. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 1416-1426. IEEE, 2020. Google Scholar
  14. Simons Institute. Online and matching-based market design, 2019. URL: https://simons.berkeley.edu/programs/market2019.
  15. Kamal Jain, Mohammad Mahdian, Evangelos Markakis, Amin Saberi, and Vijay V Vazirani. Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP. Journal of the ACM (JACM), 50(6):795-824, 2003. Google Scholar
  16. Bala Kalyanasundaram and Kirk R Pruhs. An optimal deterministic algorithm for online b-matching. Theoretical Computer Science, 233(1-2):319-325, 2000. Google Scholar
  17. Richard M Karp, Umesh V Vazirani, and Vijay V Vazirani. An optimal algorithm for on-line bipartite matching. In Proceedings of the twenty-second annual ACM symposium on Theory of computing, pages 352-358, 1990. Google Scholar
  18. Aranyak Mehta. Online matching and ad allocation, volume 8(4). Now Publishers, Inc., 2013. Google Scholar
  19. Aranyak Mehta, Amin Saberi, Umesh Vazirani, and Vijay Vazirani. Adwords and generalized online matching. Journal of the ACM (JACM), 54(5), 2007. Google Scholar
  20. Rajan Udwani. Adwords with unknown budgets. arXiv preprint, 2021. URL: http://arxiv.org/abs/2110.00504.
  21. Vijay V Vazirani. Online bipartite matching and adwords. arXiv preprint, 2021. URL: http://arxiv.org/abs/2107.10777.
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 About DROPS Imprint Privacy Contact