One-Sided Matching Markets with Endowments: Equilibria and Algorithms

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, and we give the following results.

(1) Existence of equilibrium under linear utility functions. 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.

Next, we define a one-sided matching market, with endowments, using a Nash-bargaining-based approach. For the case of dichotomous utilities, we show that the model admits a rational convex program as well as a combinatorial, strongly polynomial time algorithm.

Joint work with Jugal Garg and Vijay Vazirani.