2026-07-22T13:29:33Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13598 2024-03-06T10:52:24Z ddc:004 open_access

Computational Complexity of the Hylland-Zeckhauser Scheme for One-Sided Matching Markets Vazirani, Vijay V. Yannakakis, Mihalis Hyland-Zeckhauser scheme one-sided matching markets mechanism design dichotomous utilities PPAD FIXP In 1979, Hylland and Zeckhauser [Hylland and Zeckhauser, 1979] gave a simple and general scheme for implementing a one-sided matching market using the power of a pricing mechanism. Their method has nice properties - it is incentive compatible in the large and produces an allocation that is Pareto optimal - and hence it provides an attractive, off-the-shelf method for running an application involving such a market. With matching markets becoming ever more prevalent and impactful, it is imperative to finally settle the computational complexity of this scheme. We present the following partial resolution: 1) A combinatorial, strongly polynomial time algorithm for the dichotomous case, i.e., 0/1 utilities, and more generally, when each agent’s utilities come from a bi-valued set. 2) An example that has only irrational equilibria, hence proving that this problem is not in PPAD. 3) A proof of membership of the problem in the class FIXP. 4) A proof of membership of the problem of computing an approximate HZ equilibrium in the class PPAD. We leave open the (difficult) questions of determining if computing an exact HZ equilibrium is FIXP-hard and an approximate HZ equilibrium is PPAD-hard. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Vijay V. Vazirani and Mihalis Yannakakis 2021 Is Part Of LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2021.59 urn:nbn:de:0030-drops-135987 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.59 eng https://creativecommons.org/licenses/by/3.0/legalcode