2020/04/02 by Vijay V. Vazirani, Mihalis Yannakakis, Vazirani, Vijay V. +1
Decision Sciences · Economics, Econometrics and Finance · #Auction Theory and Applications #Combinatorics (math.CO) #Computational Complexity (cs.CC) #Computer Science and Game Theory (cs.GT) #F.2.2 #FOS: Computer and information sciences #FOS: Economics and business #FOS: Mathematics #Game Theory and Applications #Game Theory and Voting Systems #Theoretical Economics (econ.TH)
paper · pdf · doi:10.48550/arxiv.2004.01348
openalex publication_date 2020/04/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In 1979, Hylland and Zeckhauser citehylland gave a simple and general\nscheme for implementing a one-sided matching market using the power of a\npricing mechanism. Their method has nice properties -- it is incentive\ncompatible in the large and produces an allocation that is Pareto optimal --\nand hence it provides an attractive, off-the-shelf method for running an\napplication involving such a market. With matching markets becoming ever more\nprevalant and impactful, it is imperative to finally settle the computational\ncomplexity of this scheme.\n We present the following partial resolution:\n 1. A combinatorial, strongly polynomial time algorithm for the special case\nof 0/1 utilities.\n 2. An example that has only irrational equilibria, hence proving that this\nproblem is not in PPAD. Furthermore, its equilibria are disconnected, hence\nshowing that the problem does not admit a convex programming formulation.\n 3. A proof of membership of the problem in the class FIXP.\n We leave open the (difficult) question of determining if the problem is\nFIXP-hard. Settling the status of the special case when utilities are in the\nset 0, frac 1 2, 1 appears to be even more difficult.\n