Time-Efficient Algorithms for Nash-Bargaining-Based Matching Market Models

Ioannis Panageas, Thorben Tr\"obst and Vijay V. Vazirani

Papers from arXiv.org

Abstract: In the area of matching-based market design, existing models using cardinal utilities suffer from two deficiencies: First, the Hylland-Zeckhauser (HZ) mechanism, which has remained a classic in economics for one-sided matching markets, is intractable; computation of even an approximate equilibrium is PPAD-complete. Second, there is an extreme paucity of such models. This led Hosseini and Vazirani (2022) to define a rich collection of Nash-bargaining-based models for one-sided and two-sided matching markets, in both Fisher and Arrow-Debreu settings, together with very fast implementations using available solvers and very encouraging experimental results. In this paper, we give fast algorithms with proven running times for the models introduced by Hosseini and Vazirani, using the techniques of multiplicative weights update (MWU) and conditional gradient descent (CGD). Additionally, we make the following contributions: (1) By Tr\"obst and Vazirani (2024), a linear one-sided Nash-bargaining-based matching market satisfies envy-freeness within factor two. We show that the other models satisfy approximate equal-share fairness, where the exact factor depends on the utility function being used in the particular model. (2) We define a Nash-bargaining-based model for non-bipartite matching markets and give fast algorithms for it using conditional gradient descent.

Date: 2021-06, Revised 2024-11
New Economics Papers: this item is included in nep-des, nep-gth and nep-ore
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://arxiv.org/pdf/2106.02024 Latest version (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:arx:papers:2106.02024

Access Statistics for this paper

More papers in Papers from arXiv.org
Bibliographic data for series maintained by arXiv administrators ().