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 Formula: see text-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 Formula: see text-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 Formula: see text utilities, rational EF + PO allocations exist. We prove that both these conditions are essential by giving negative results for an asymmetric Formula: see text utilities market and a symmetric Formula: see text 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.
Tröbst et al. (Fri,) studied this question.