License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2022.86
URN: urn:nbn:de:0030-drops-156821
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/15682/
Hosseini, Mojtaba ;
Vazirani, Vijay V.
Nash-Bargaining-Based Models for Matching Markets: One-Sided and Two-Sided; Fisher and Arrow-Debreu
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.
BibTeX - Entry
@InProceedings{hosseini_et_al:LIPIcs.ITCS.2022.86,
author = {Hosseini, Mojtaba and Vazirani, Vijay V.},
title = {{Nash-Bargaining-Based Models for Matching Markets: One-Sided and Two-Sided; Fisher and Arrow-Debreu}},
booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
pages = {86:1--86:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-217-4},
ISSN = {1868-8969},
year = {2022},
volume = {215},
editor = {Braverman, Mark},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/15682},
URN = {urn:nbn:de:0030-drops-156821},
doi = {10.4230/LIPIcs.ITCS.2022.86},
annote = {Keywords: Matching-based market design, Nash bargaining, convex optimization, Frank-Wolfe algorithm, cutting planes, general equilibrium theory, one-sided markets, two-sided markets}
}
|
Keywords: |
|
Matching-based market design, Nash bargaining, convex optimization, Frank-Wolfe algorithm, cutting planes, general equilibrium theory, one-sided markets, two-sided markets |
|
Collection: |
|
13th Innovations in Theoretical Computer Science Conference (ITCS 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
25.01.2022 |
