Document Open Access Logo

Nash-Bargaining-Based Models for Matching Markets: One-Sided and Two-Sided; Fisher and Arrow-Debreu

Authors Mojtaba Hosseini , Vijay V. Vazirani

PDF

File

Thumbnail PDF
PDF
LIPIcs.ITCS.2022.86.pdf
  • Filesize: 0.88 MB
  • 20 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Theory of computation → Algorithmic game theory
  • Theory of computation → Algorithmic mechanism design
  • Mathematics of computing → Convex optimization
Keywords
  • Matching-based market design
  • Nash bargaining
  • convex optimization
  • Frank-Wolfe algorithm
  • cutting planes
  • general equilibrium theory
  • one-sided markets
  • two-sided markets

Metrics

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

Abstract

This paper addresses two deficiencies of models in the area of matching-based market design. The first arises from the recent realization that the most prominent solution that uses cardinal utilities, namely the Hylland-Zeckhauser (HZ) mechanism [Hylland and Zeckhauser, 1979], is intractable; computation of even an approximate equilibrium is PPAD-complete [Vazirani and Yannakakis, 2021; Chen et al., 2021]. The second is the extreme paucity of models that use cardinal utilities, in sharp contrast with general equilibrium theory.
Our paper addresses both these issues by proposing Nash-bargaining-based matching market models. Since the Nash bargaining solution is captured by a convex program, efficiency follow; in addition, it possesses a number of desirable game-theoretic properties. Our approach yields a rich collection of models: for one-sided as well as two-sided markets, for Fisher as well as Arrow-Debreu settings, and for a wide range of utility functions, all the way from linear to Leontief. 
We also give very fast implementations for these models which solve large instances, with n = 2000, in one hour on a PC, even for a two-sided matching market. A number of new ideas were needed, beyond the standard methods, to obtain these implementations.

Cite As Get BibTex

Mojtaba Hosseini and Vijay V. Vazirani. Nash-Bargaining-Based Models for Matching Markets: One-Sided and Two-Sided; Fisher and Arrow-Debreu. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 86:1-86:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.ITCS.2022.86

Author Details

Mojtaba Hosseini
  • The Paul Merage School of Business, University of California, Irvine, CA, USA
Vijay V. Vazirani
  • Computer Science Department, University of California, Irvine, CA, USA

Funding

  • Vazirani, Vijay V.: Supported in part by NSF grant CCF-1815901.

Acknowledgements

The second author would like to thank Richard Zeckhauser for a very enlightening discussion on his "wish list" of models for matching markets. Several of the models considered in this paper have their origins in that discussion.

References

  1. Atila Abdulkadiroğlu, Yeon-Koo Che, and Yosuke Yasuda. Expanding" choice" in school choice. American Economic Journal: Microeconomics, 7(1):1-42, 2015. Google Scholar
  2. Rediet Abebe, Richard Cole, Vasilis Gkatzelis, and Jason D Hartline. A truthful cardinal mechanism for one-sided matching. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2096-2113. SIAM, 2020. Google Scholar
  3. Saeed Alaei, Pooya Jalaly Khalilabadi, and Eva Tardos. Computing equilibrium in matching markets. In Proceedings of the 2017 ACM Conference on Economics and Computation, pages 245-261, 2017. Google Scholar
  4. Saugata Basu, Richard Pollack, and MF Roy. A new algorithm to find a point in every cell defined by a family of polynomials. Quantifier Elimination and Cylindrical Algebraic Decomposition, B. Caviness and J. Johnson eds., Springer-Verlag, to appear, 1995. Google Scholar
  5. Garrett Birkhoff. Tres observaciones sobre el algebra lineal. Univ. Nac. Tucuman, Ser. A, 5:147-154, 1946. Google Scholar
  6. Eric Budish. The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes. Journal of Political Economy, 119(6):1061-1103, 2011. Google Scholar
  7. Ioannis Caragiannis, David Kurokawa, Herve Moulin, Ariel D Procaccia, Nisarg Shah, and Junxing Wang. The unreasonable fairness of maximum Nash welfare. ACM Transactions on Economics and Computation (TEAC), 7(3):1-32, 2019. Google Scholar
  8. Thomas Chen, Xi Chen, Binghui Peng, and Mihalis Yannakakis. Computational hardness of the hylland-zeckhauser scheme. arXiv preprint arXiv:2107.05746, 2021. Google Scholar
  9. Richard Cole, Nikhil Devanur, Vasilis Gkatzelis, Kamal Jain, Tung Mai, Vijay V Vazirani, and Sadra Yazdanbod. Convex program duality, Fisher markets, and Nash social welfare. In Proceedings of the 2017 ACM Conference on Economics and Computation, pages 459-460, 2017. Google Scholar
  10. Richard Cole and Vasilis Gkatzelis. Approximating the Nash social welfare with indivisible items. SIAM Journal on Computing, 47(3):1211-1236, 2018. Google Scholar
  11. Nikhil R Devanur, Christos H Papadimitriou, Amin Saberi, and Vijay V Vazirani. Market equilibrium via a primal-dual algorithm for a convex program. Journal of the ACM (JACM), 55(5):22, 2008. Google Scholar
  12. Federico Echenique, Antonio Miralles, and Jun Zhang. Constrained pseudo-market equilibrium. arXiv preprint arXiv:1909.05986, 2019. Google Scholar
  13. Federico Echenique, Antonio Miralles, and Jun Zhang. Fairness and efficiency for probabilistic allocations with endowments. arXiv preprint arXiv:1908.04336, 2019. Google Scholar
  14. E. Eisenberg and D. Gale. Consensus of subjective probabilities: the Pari-Mutuel method. The Annals of Mathematical Statistics, 30:165-168, 1959. Google Scholar
  15. Jack Elzinga and Thomas G Moore. A central cutting plane algorithm for the convex programming problem. Mathematical Programming, 8(1):134-145, 1975. Google Scholar
  16. Simons Institute for the Theory of Computing. Online and matching-based market design, 2019. URL: https://simons.berkeley.edu/programs/market2019.
  17. Marguerite Frank and Philip Wolfe. An algorithm for quadratic programming. Naval Res. Logis. Quart., 3(1-2):95-110, 1956. Google Scholar
  18. David Gale and Lloyd S Shapley. College admissions and the stability of marriage. The American Mathematical Monthly, 69(1):9-15, 1962. Google Scholar
  19. Jugal Garg, Thorben Tröbst, and Vijay V Vazirani. An Arrow-Debreu extension of the hylland-zeckhauser scheme: Equilibrium existence and algorithms. arXiv preprint arXiv:2009.10320, 2020. Google Scholar
  20. Martin Grötschel, László Lovász, and Alexander Schrijver. Geometric algorithms and combinatorial optimization, volume 2. Springer Science & Business Media, 2012. Google Scholar
  21. Yinghua He, Antonio Miralles, Marek Pycia, and Jianye Yan. A pseudo-market approach to allocation with priorities. American Economic Journal: Microeconomics, 10(3):272-314, 2018. Google Scholar
  22. Aanund Hylland and Richard Zeckhauser. The efficient allocation of individuals to positions. Journal of Political economy, 87(2):293-314, 1979. Google Scholar
  23. Martin Jaggi. Revisiting Frank-Wolfe: Projection-free sparse convex optimization. In International Conference on Machine Learning, pages 427-435. PMLR, 2013. Google Scholar
  24. James E Kelley, Jr. The cutting-plane method for solving convex programs. SIAM Journal on Applied Mathematics, 8(4):703-712, 1960. Google Scholar
  25. Phuong Le. Competitive equilibrium in the random assignment problem. International Journal of Economic Theory, 13(4):369-385, 2017. Google Scholar
  26. Andy McLennan. Efficient disposal equilibria of pseudomarkets. In Workshop on Game Theory, volume 4, page 8, 2018. Google Scholar
  27. Hervé Moulin. Fair division in the age of internet. Annual Review of Economics, 2018. Google Scholar
  28. John Nash. Two-person cooperative games. Econometrica: Journal of the Econometric Society, pages 128-140, 1953. Google Scholar
  29. George L Nemhauser and WB Widhelm. A modified linear program for columnar methods in mathematical programming. Operations Research, 19(4):1051-1060, 1971. Google Scholar
  30. Ioannis Panageas, Thorben Tröbst, and Vijay V Vazirani. Combinatorial algorithms for matching markets via nash bargaining: One-sided, two-sided and non-bipartite. arXiv preprint arXiv:2106.02024, 2021. Google Scholar
  31. V. V. Vazirani. The notion of a rational convex program, and an algorithm for the Arrow-Debreu Nash bargaining game. Journal of the ACM, 59(2), 2012. Google Scholar
  32. Vijay V Vazirani and Mihalis Yannakakis. Computational complexity of the hylland-zeckhauser mechanism for one-sided matching markets. In Innovations in Theoretical Computer Science, 2021. Google Scholar
  33. Nisheeth Vishnoi. Algorithms for Convex Optimization. Cambridge University Press, 2021. To appear. Google Scholar
  34. John Von Neumann. A certain zero-sum two-person game equivalent to the optimal assignment problem. Contributions to the Theory of Games, 2(0):5-12, 1953. Google Scholar
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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact