2026-07-23T21:51:31Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15682 2024-03-06T10:55:56Z ddc:004 open_access

Nash-Bargaining-Based Models for Matching Markets: One-Sided and Two-Sided; Fisher and Arrow-Debreu Hosseini, Mojtaba Vazirani, Vijay V. Matching-based market design Nash bargaining convex optimization Frank-Wolfe algorithm cutting planes general equilibrium theory one-sided markets two-sided markets 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mojtaba Hosseini and Vijay V. Vazirani 2022 Is Part Of LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2022.86 urn:nbn:de:0030-drops-156821 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.86 eng https://creativecommons.org/licenses/by/4.0/legalcode