Cardinal-Utility Matching Markets: The Quest for Envy-Freeness, Pareto-Optimality, and Efficient Computability

• 成果类型: Article; Early Access
• 署名作者: Trobst, Thorben; Vazirani, Vijay V.
• 署名单位: University of California System; University of California Irvine
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2024.0770
• 发表日期: 2025
• 关键词: approximate competitive-equilibrium; allocation; complexity

摘要

Recent insights have left cardinal-utility matching markets in a state of flux: the celebrated pricing-based mechanism for one-sided cardinal-utility matching markets due to Hylland and Zeckhauser (HZ) [Hylland A, Zeckhauser R (1979) The efficient allocation of individuals to positions. J. Polit. Econom. 87(2):293-314.], which had long eluded efficient algorithms, was finally shown to be polynomial parity argument in digraphs (PPAD)-complete (Chen et al. [Chen T, Chen X, Peng B, Yannakakis M (2022) Computational hardness of the Hylland-Zeckhauser scheme. Proc. 2022 Annual ACMSIAM Sympos. Discrete Algorithms SODA (SIAM, Philadelphia), 2253-2268.], Vazirani and Yannakakis [Vazirani VV, Yannakakis M (2025) Computational complexity of the Hylland-Zeckhauser mechanism for onesided matching markets. SIAM J. Comput. 54(2):193-232.]). This raises the question: is there a polynomial time mechanism for one-sided cardinal-utility matching markets which achieves the desirable properties of HZ-that is, envy-freeness (EF) and Pareto-optimality (PO)? We show that the problem of finding an EF + PO lottery in a one-sided cardinalutility matching market is by itself PPAD-complete. However, a (2 + e)-approximately envy-free and Pareto-optimal lottery can be found in polynomial time using the Nashbargaining-based mechanism of Hosseini and Vazirani [Hosseini M, Vazirani VV (2022) Nash-bargaining-based models for matching markets: One-sided and two-sided; Fisher and Arrow-Debreu. Braverman M, ed. 13th Innovations Theoretical Comput. Sci. Conf. ITCS 2022, LIPIcs, Leibniz International Proceedings in Informatics (LIPIcs), vol. 215 (Schloss Dagstuhl-Leibniz-Zentrum fur Informatik, Wadern, Germany), 86:1-86:20.]. This mechanism is also (2 + e)-approximately incentive compatible. We next turn to two-sided cardinal-utility matching markets, for which Bogomolnaia and Moulin [9] had shown that for a symmetric, bipartite two-sided matching market with {0, 1} utilities, rational EF + PO allocations exist. We prove that both these conditions are essential by giving negative results for an asymmetric {0,1} utilities market and a symmetric {0,1, 2} utilities market. We also prove existence of justified-envy-free and weak Pareto-optimal lotteries.