Thorben Tröbst (UC Irvine)
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.