  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 $\epsilon$-approximate ADHZ model, and we give the
following results.
  * Existence of equilibrium under linear utility functions. We prove that the
equilibrium satisfies Pareto optimality, approximate envy-freeness, and
approximate weak core stability.
  * A combinatorial polynomial-time algorithm for an $\epsilon$-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.
  Since computing an equilibrium for HZ is likely to be highly intractable and
because of the difficulty of extending HZ to more general utility functions,
Hosseini and Vazirani proposed (a rich collection of) Nash-bargaining-based
matching market models. For the dichotomous-utilities case of their model
linear Arrow-Debreu Nash bargaining one-sided matching market (1LAD), we give a
combinatorial, strongly polynomial-time algorithm and show that it admits a
rational convex program.
