An Arrow-Debreu Extension of the Hylland-Zeckhauser Scheme: Equilibrium Existence and Algorithms
share
The Arrow-Debreu extension of the classic Hylland-Zeckhauser scheme 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. We give the following results. * Existence of equilibrium for the ϵ-approximate ADHZ model under linear utility functions. The equilibrium satisfies Pareto optimality, approximate envy-freeness and incentive compatibility in the large. * A combinatorial polynomial time algorithm for an ϵ-approximate ADHZ equilibrium for the case of dichotomous, and more generally bi-valued, utilities. * An instance of ADHZ, with dichotomous utilities and a strongly connected demand graph, which does not admit an equilibrium. * A rational convex program for HZ under dichotomous utilities; a combinatorial polynomial time algorithm for this case was given by Vazirani and Yannakakis (2020). The ϵ-approximate ADHZ model fills a void, described in the paper, in the space of general mechanisms for one-sided matching markets.
READ FULL TEXT