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

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 one-sided 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 cardinal-utility matching market is by itself PPAD-complete. However, a $(2+ϵ)$-approximately envy-free and Pareto-optimal lottery can be found in polynomial time using the Nash-bargaining-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 für Informatik, Wadern, Germany), 86:1–86:20.]. This mechanism is also $(2+ϵ)$-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.

Funding: Financial support from the National Science Foundation [Grant CCF-2230414] is gratefully acknowledged.