One-sided matching markets with endowments: equilibria and algorithms

The Arrow–Debreu extension of the classic Hylland–Zeckhauser scheme (Hylland and Zeckhauser in J Polit Econ 87(2):293–314, 1979) 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 give the following results. 1. Existence of equilibrium under linear utility functions. We prove that the equilibrium allocation 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 Vazirani and Yannakakis (in: Innovations in theoretical computer science, pp 59–15919, 2021). The ϵ-approximate ADHZ model fills a void in the space of general mechanisms for one-sided matching markets; see details in the paper.