One-Sided Matching Markets with Endowments: Equilibria and Algorithms

Jugal Garg (University of Illinois at Urbana-Champaign), Thorben Trรถbst (University of California, Irvine), Vijay V. Vazirani (University of California, Irvine)

Abstract

The Arrow-Debreu extension of the classic Hylland-Zeckhauser scheme [27] for a one-sided matching market-called ADHZ in this paper-has natural applications but has instances which do not admit equilibria. By introducing approximation, we define the ๐œ–-approximate ADHZ model, and we give the following results. (1) Existence of equilibrium under linear utility functions. We prove that the equilibrium satisfies Pareto optimality, approximate envy-freeness, and approximate weak core stability. (2) A combinatorial polynomial time algorithm for an ๐œ–-approximate ADHZ equilibrium for the case of dichotomous, and more generally bi-valued, utilities. (3) An instance of ADHZ, with dichotomous utilities and a strongly connected demand graph, which does not admit an equilibrium. (4) A rational convex program for HZ under dichotomous utilities; a combinatorial polynomial time algorithm for this case was given in [35]. The ๐œ–-approximate ADHZ model fills a void in the space of general mechanisms for one-sided matching markets; see details in the paper.