Tractability boundaries identified for hylland-zeckhauser matching models
Exploring the Tractability Frontier of Hylland-Zeckhauser Models
Computer Science and Game Theory
Summary
The paper studies a particular market-based method for matching buyers and goods efficiently. It shows that when buyers have three different utility values, finding an approximate equilibrium is computationally very hard, confirming a long-standing open question. The authors also identify a case with special concave utilities where equilibrium can still be found efficiently. Their work thus pinpoints exactly when this matching problem transitions from easy to hard, based on the complexity of utility preferences.
What this means in practice
- •For market designers: Understand when efficient algorithms exist for computing allocations in markets with simple buyer preferences and when they do not.
- •For algorithm engineers: Recognize classes of utility functions in matching problems that admit polynomial-time equilibrium computation and those that are computationally intractable.
A theory result. No direct application yet.
Authors
Ioannis Panageas, Avi Shein, Shayan Taherijam, Vijay V. Vazirani
Abstract
The Hylland-Zeckhauser (HZ) mechanism provides a market-based approach to one-sided matching, making efficient equilibrium computation central to its implementation. Bi-valued utilities admit a strongly polynomial-time algorithm [VY], whereas with four values per buyer, the problem is PPAD-hard under inverse polynomial approximation [CCPY]. To understand the tractability boundary, we study two extensions of the bi-valued case: a third linear utility value and separable concave utilities with two common marginal slopes. For every fixed rational $a\in(0,1)$, we prove that computing a normalized additive $\varepsilon_{*}(a)/N$-equilibrium in an $N$-buyer HZ market is PPAD-hard for some constant $\varepsilon_{*}(a)>0$, even when all utilities belong to the same prescribed set $\{0,a,1\}$. This resolves the main question left open by [VY, CCPY]: whether three utility values already suffice for PPAD-hardness. Using the same market gadgets, we show that hardness at a specified constant accuracy on the recognizable family generated by our construction is equivalent to the PCP-for-PPAD conjecture. Consequently, assuming that conjecture, general markets over $\{0,a,1\}$ admit no PTAS unless $\mathrm{PPAD}\subseteq\mathrm{P}$. For the concave extension, we compute an exact equilibrium in polynomial time with two marginal slopes common across goods for each buyer and arbitrary rational buyer--good breakpoints. The algorithm selects a cheapest utility-maximizing bundle for each buyer. With three common marginal slopes, suitable breakpoints encode the three valued linear case, yielding PPAD-hardness. Thus, our paper identifies two thresholds separating tractable and intractable cases of HZ models with utility functions specified by utility values or marginal slopes. In both cases, the tractability threshold lies between two and three.