  Unlike ordinal-utility matching markets, which are well-developed from the
viewpoint of both theory and practice, recent insights from a computer science
perspective have left cardinal-utility matching markets in a state of flux. The
celebrated pricing-based mechanism for one-sided cardinal-utility matching
markets due to Hylland and Zeckhauser, which had long eluded efficient
algorithms, was finally shown to be intractable; the problem of computing an
approximate equilibrium is PPAD-complete.
  This led us to ask the question: is there an alternative, polynomial time,
mechanism for one-sided cardinal-utility matching markets which achieves the
desirable properties of HZ, i.e.\ (ex-ante) envy-freeness (EF) and
Pareto-optimality (PO)? In this paper we show:
  1. The problem of finding an EF+PO lottery in a one-sided cardinal-utility
matching market is PPAD-complete.
  2. A $(2 + \epsilon)$-approximately envy-free and (exactly) Pareto-optimal
lottery can be found in polynomial time using Nash bargaining. Moreover, the
resulting mechanism is $(2 + \epsilon)$-approximately incentive compatible.
  We also present several results on two-sided cardinal-utility matching
markets, including non-existence of EF+PO lotteries as well as existence of
justified-envy-free and weak Pareto-optimal lotteries.
