# Computational Complexity of the Hylland-Zeckhauser Scheme for One-Sided Matching Markets

arXiv: https://arxiv.org/abs/2004.01348 · HTML: https://mlsanity.com/paper/2004.01348/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Apr 2020.

## Built on by (most cited first, 1 of 1)

- [Optimization-friendly generic mechanisms without money](https://mlsanity.com/paper/2106.07752/) (2021)

## Abstract (arXiv)

In 1979, Hylland and Zeckhauser citehylland gave a simple and general scheme for implementing a one-sided matching market using the power of a pricing mechanism. Their method has nice properties -- it is incentive compatible in the large and produces an allocation that is Pareto optimal -- and hence it provides an attractive, off-the-shelf method for running an application involving such a market. With matching markets becoming ever more prevalant and impactful, it is imperative to finally settle the computational complexity of this scheme. We present the following partial resolution: 1. A combinatorial, strongly polynomial time algorithm for the special case of 0/1 utilities. 2. An example that has only irrational equilibria, hence proving that this problem is not in PPAD. Furthermore, its equilibria are disconnected, hence showing that the problem does not admit a convex programming formulation. 3. A proof of membership of the problem in the class FIXP. We leave open the (difficult) question of determining if the problem is FIXP-hard. Settling the status of the special case when utilities are in the set 0, frac 1 2, 1  appears to be even more difficult.