Search for: All records

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 [1979](HZ), which had long eluded efficient algorithms, was finally shown to be intractable; the problem of computing an approximate equilibrium is PPAD-complete (Vazirani and Yannakakis [2021], Chen et al. [2022]). 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) envyfreeness (EF) and Pareto-optimality (PO)? We show that the problem of finding an EF+PO lottery in a one-sided cardinal-utility matching market is by itself already PPAD-complete. However, a (2 + ǫ)-approximately envy-free and (exactly) Pareto-optimal lottery can be found in polynomial time using the Nash-bargaining-based mechanism of Hosseini and Vazirani [2022]. Moreover, the mechanism is also (2+ǫ)-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.