betaFeedback

WorksComputer Science

Exploring the Tractability Frontier of Hylland-Zeckhauser Models

Abstract

The Hylland-Zeckhauser (HZ) mechanism provides a market-based approach to one-sided matching, making efficient equilibrium computation central to its implementation. Under bi-valued utilities, it admits 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 slopes. For every fixed rational a∈(0,1)a\in(0,1), we prove that computing a normalized additive ε∗(a)/N\varepsilon_{*}(a)/N-equilibrium in an NN-buyer HZ market is PPAD-complete for some constant ε∗(a)>0\varepsilon_{*}(a)>0, even when all utilities belong to the same prescribed set {0,a,1}\{0,a,1\}. This resolves the main question left open by [VY, CCPY]: whether three utility values already suffice for PPAD-hardness. Assuming the PCP-for-PPAD conjecture, we strengthen the above-stated result to constant additive-error hardness. For the concave extension, we compute an exact equilibrium in strongly polynomial time with two marginal utility slopes common across goods for each buyer and arbitrary rational buyer-good breakpoints. 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.

Introduction

Allocating indivisible goods without monetary transfers is a basic problem in matching markets, such as assigning students to dormitory rooms. The Hylland–Zeckhauser (HZ) mechanism [12] addresses this problem through a market for probability shares of goods. There are NN buyers with cardinal utilities and NN indivisible goods, each available in one copy. Each buyer receives one unit of artificial money and chooses an affordable bundle of probability shares of total quantity one to maximize her expected utility. Equilibrium prices make these demands clear the market. The resulting doubly stochastic allocation can be implemented as a lottery over assignments in which each buyer receives exactly one good. No monetary transfers are made. For linear utilities over probability shares, the allocation is ex ante envy-free and, with minimum-expenditure tie-breaking among optimal bundles, ex ante Pareto-efficient [12].

At fixed prices, a buyer’s demand in the linear model is a linear program with a budget constraint and a unit-quantity constraint. Finding prices that clear the market is the computational difficulty. An optimal bundle may mix an expensive preferred good with a cheaper less preferred good to satisfy both constraints. Vazirani and Yannakakis [17] gave a strongly polynomial exact algorithm for bivalued utilities, where each buyer has at most two values, which may differ across buyers, and asked whether {0,1/2,1}\{0,1/2,1\} already suffices for intractability. Chen, Chen, Peng, and Yannakakis [4] proved PPAD-hardness of inverse polynomial approximation with four values per buyer. Yan and Liu [18] subsequently gave a polynomial-time additive 1/e1/e approximation for utilities in [0,1][0,1] and a 5×55 \times5 market over {0,1/2,1}\{0,1/2,1\} whose exact equilibria all have an irrational price. Irrationality does not, however, establish hardness of approximation; the three-value case remained open.

We study two extensions of the tractable bi-valued domain. The first keeps utilities linear and adds a third value. The second allows separable concave utilities over fractional allocations, with two marginal slopes common across goods for each buyer and a separate breakpoint for every buyer–good pair. Taking all breakpoints in {0,1}\{0,1\} recovers bi-valued linear utilities, so both extensions contain the tractable case. We can therefore distinguish the effect of an additional utility value from that of diminishing returns.

Our results

Three common utility values. We use the additive approximation notion of [4]. A normalized additive ε\varepsilon-equilibrium consists of nonnegative prices with minimum zero and an allocation that clears every good and gives every buyer total quantity one. Each buyer ii spends at most 1+ε1+\varepsilon and receives utility at least Vi(p)−εV_i(p)-\varepsilon, where Vi(p)V_i(p) is her maximum utility over unit bundles costing at most one at prices pp. This notion allows expenditure on zero-utility goods and does not impose minimum-expenditure tie-breaking; see Definition 2.2.

Theorem 1.1. For every fixed rational a∈(0,1)a \in(0,1), there is a positive rational constant ε∗(a)\varepsilon_*(a) such that computing a normalized additive ε∗(a)/N\varepsilon_*(a)/N-equilibrium of an NN-buyer HZ market is PPAD-complete when all utilities belong to {0,a,1}\{0,a,1\}.

Membership in PPAD follows from [17 Section 7]. Their approximation notion imposes all the conditions in Definition 2.2, together with an approximate minimum-expenditure condition. Dropping that additional condition gives a solution of our problem at the same error parameter. Their upper bound applies to rational utilities in [0,1][0,1] and positive rational accuracy, including ε∗(a)/N\varepsilon_*(a)/N.

The theorem answers the question of [17] for {0,1/2,1}\{0,1/2,1\} and, more generally, for every prescribed middle value aa. The same three values are used by all buyers; this is stronger than allowing each buyer her own three values. In contrast, the hardness of [4] does not assume four common values for all buyers. Furthermore, every row and column of our constructed utility matrix has only a bounded number of positive entries, with the bound depending on aa. Since 1/ε=N/ε∗(a)1/\varepsilon= N/\varepsilon_*(a) is polynomial in the market size, Theorem 1.1 rules out a fully polynomial-time approximation scheme unless PPAD⊆P\mathrm{PPAD} \subseteq\mathrm{P}.

Constant approximation and PCP for PPAD. The PCP-for-PPAD conjecture of Babichenko, Papadimitriou, and Rubinstein [2] concerns generalized circuits in which a small constant fraction of gates may fail. We use the formulation of [6]: for some positive constant gate accuracy and failure fraction, finding such an assignment is PPAD-hard. The original conjecture asks for a quasilinear reduction. OpenAI has announced a proof of that stronger formulation [13]; we state our constant-approximation result conditionally on PCP for PPAD.

Theorem 1.2 (Constant-error hardness under PCP for PPAD). Assuming the PCP-for-PPAD conjecture, for every fixed rational a∈(0,1)a \in(0,1) there is a positive rational constant ε0=ε0(a)\varepsilon_0 = \varepsilon_0(a) such that computing a normalized additive ε0\varepsilon_0-equilibrium of an HZ market with utilities in {0,a,1}\{0,a,1\} is PPAD-hard.

Two common marginal slopes. For the concave extension, buyer ii has separable utility Ui(xi)=∑jfij(xij)U_i(x_i) = \sum_j f_{ij}(x_{ij}), where

fij(t)=ci(2)t+(ci(1)−ci(2))min⁡{t,τij},0≤t≤1.(1)f_{ij}(t) = c_i^{(2)}t + \left(c_i^{(1)} - c_i^{(2)}\right)\min\{t,\tau_{ij}\}, \qquad0 \le t \le1. \tag*{(1)}

The slopes ci(1)≥ci(2)≥0c_i^{(1)} \ge c_i^{(2)} \ge0 are common across goods for buyer ii, while τij∈[0,1]\tau_{ij} \in[0,1] is the breakpoint for good jj. Budgets, supplies, and required bundle quantities are still one.

Theorem 1.3 (Two marginal slopes). For rational input in (1), an exact normalized HZ equilibrium can be computed in strongly polynomial time. Each buyer receives a minimum-expenditure bundle among her utility-maximizing affordable bundles.

With three common slopes, zero-length segments can represent each of the linear utilities 00, atat, and tt. Thus the linear hardness theorem immediately gives the corresponding concave hardness result.

Corollary 1.4 (Three common marginal slopes). For every fixed rational a∈(0,1)a \in(0,1), computing a normalized additive ε∗(a)/N\varepsilon_*(a)/N-equilibrium is PPAD-hard for separable concave utilities with the same ordered marginal slopes 11, aa, 00 for every buyer–good pair, allowing segments of zero length.

Table 1 summarizes these results.

Utility restrictionComplexity and accuracyReference
Linear, two values per buyerStrongly polynomial, exact[17]
Linear, common values {0, aa, 1}PPAD-complete, error ε∗(a)/N\varepsilon_*(a)/NTheorem 1.1
Linear, common values {0, aa, 1}PPAD-hard, constant error under PCP for PPADTheorem 1.2
Linear, four values per buyerPPAD-hard, inverse polynomial error[4]
Concave, two common slopesStrongly polynomial, exactTheorem 1.3
Concave, three common slopesPPAD-hard, error ε∗(a)/N\varepsilon_*(a)/NCorollary 1.4

Table 1. Complexity under restrictions on linear utility values and common marginal slopes, for fixed rational a∈(0,1)a \in(0,1). In the concave model, slopes are common across goods for each buyer; the three-slope hardness uses the same slopes for all buyers. Zero-length segments are permitted.

Technical overview

We reduce from the bounded-degree threshold game [15, 5], with a fixed small tolerance κ>0\kappa> 0. Each vertex has a value zv∈[0,1]z_v \in[0,1], which must be at most κ\kappa when the incoming sum exceeds 1/2+κ1/2 + \kappa, and at least 1−κ1 - \kappa when that sum is below 1/2−κ1/2 - \kappa. Inside this tolerance interval, any value is allowed. Both indegree and outdegree are at most two, and every vertex has at least one outgoing edge. For fixed rational a∈(0,1)a \in(0,1), we choose a small constant τ\tau and a large admissible integer KK before receiving the graph. All vertex and wire gadgets then have constant size, with vertex sizes depending only on the bounded degree pair.

Chen, Chen, Peng, and Yannakakis [4 Section 3, full version] also reduce from threshold games, using at most four utility values per buyer, which may differ across buyers. Their edge gadgets use this freedom to cancel unwanted price dependencies. With the same prescribed set {0,a,1}\{0, a, 1\} for every buyer, we cannot tune these comparisons separately. Our construction uses two successive comparisons to obtain a price ratio a2a^2. Its separation from the utility ratio aa lets wire buyers transmit an approximately affine signal. Their spending also changes at the source; degree-dependent supplies cancel that second change. We first explain the reduction at an exact equilibrium.

Encoding values in prices. Each vertex vv has three target groups of goods LvL_v, MvM_v, HvH_v, with prices qvq_v, mvm_v, pvp_v. Goods within a group have identical utility vectors, allowing price equalization (Lemma 2.3). Lower-link buyers compare utilities aa and one on LvL_v, MvM_v; upper buyers make the same comparison on MvM_v, HvH_v. Two reference groups of goods, supported by their own anchor buyers, bound the target prices. Floor buyers can buy the low and middle targets or their reference; upper buyers can buy the middle and high targets or a second reference.

Suitable group sizes force

qv=amv=a2pv,qv<1<mv<pv.q_v = a m_v = a^2 p_v,\qquad q_v < 1 < m_v < p_v.

Thus the two comparisons produce the ratio a2a^2, while a unit of the low target is affordable and a unit of either other target is not. The reference groups confine every high price to the same interval [L,U+η][L, U + \eta], of width Oa(1/K)O_a(1/K), just below a−2a^{-2}. Writing w=U−Lw = U - L and η=τw\eta= \tau w, we decode zv=clip⁡(tv)z_v = \operatorname{clip}(t_v), where tv=(pv−L)/wt_v = (p_v - L)/w and clip truncates to [0,1][0,1]. Then 0≤tv≤1+τ0 \le t_v \le1 + \tau and ∣tv−zv∣≤τ|t_v - z_v| \le\tau. Figure 1 shows the gadget; § 3 and § 4 give the group sizes and prove the price relations.

The vertex gadget at $v$

Figure 1. The vertex gadget at vv. Solid blue ellipses denote groups of goods; dashed orange ellipses denote buyer populations. Each edge label gives every buyer’s utility for each good in the adjacent group. The balancing group Z\mathcal{Z} is shared by the whole market and has no positive-utility connections.

Directed signals and cancellation. For each edge u→vu \to v, introduce KK wire buyers valuing LuL_u at aa and HvH_v at one. Since both high prices lie in the same narrow interval, qu/pv=a2+Oa(1/K)<aq_u/p_v = a^2 + O_a(1/K) < a. The low good offers better utility per dollar, whereas the high good offers better utility per unit. Each wire buyer therefore mixes the two, exhausting both budget and quantity. With our calibration of the price interval, their total spending on HvH_v is

Iuv=Kpv(1−a2pu)pv−a2pu=3−2tu+Oa(1/K).I_{uv} = \frac{Kp_v(1-a^2p_u)}{p_v-a^2p_u} = 3-2t_u+O_a(1/K).

The error is proportional to pu−pvp_u-p_v, with a factor bounded in terms of aa alone, so the bound holds for every edge; see Lemma 2.5 and (14). Spending on HvH_v therefore records the value encoded at uu.

The same buyers spend their remaining budget K−Iuv=K−3+2tu+Oa(1/K)K-I_{uv}=K-3+2t_u+O_a(1/K) on LuL_u. Thus outgoing wires contribute a term 2ovtv2o_vt_v to revenue at vv, where ovo_v is its outdegree. We choose the target supplies so that the revenue required to clear them contains exactly the same term. Subtracting wire spending cancels this extra dependence on tvt_v. The numbers of link buyers adjust the constant terms according to the indegree and outdegree, placing the threshold at 1/21/2. The remaining market-clearing identity is

Φv=2∑u→vtu−1+Oa(1/K).\Phi_v = 2\sum_{u\to v} t_u - 1 + O_a(1/K).

where Φv\Phi_v is floor spending on the targets minus upper spending on the upper reference goods. If Φv>0\Phi_v>0, floor buyers must spend on targets. This is optimal only near the low endpoint, forcing zv≤τz_v\le\tau. If Φv<0\Phi_v<0, upper buyers must spend on their reference, forcing the high price to be at least UU and hence zv=1z_v=1. Small τ\tau and large KK therefore turn a large incoming sum into a small output, and a small incoming sum into a large output, whenever the sum lies outside the tolerance interval. Proposition 4.8 formalizes this decoding argument.

Robustness and inverse-linear accuracy. Approximate buyers may spend on goods they value at zero, supplying revenue absent from the exact argument. Even a small quantity can matter if its price is high, so we must control expenditure. We do this before assuming approximate price relations. Our demand estimates bound purchases from inferior options while accounting for both the budget and the unit-bundle constraint. The construction also keeps each buyer’s optimal utility a fixed amount below one. Together with revenue bounds, these estimates give total unapproved expenditure W=Oa(Nε)W=O_a(N\varepsilon) for sufficiently small KεK\varepsilon.

When WW and K2εK^2\varepsilon are small, approximate price relations follow, and the additional error in the revenue identity is Oa(K2ε+W)O_a(K^2\varepsilon+W). Away from the required endpoint, nearly optimal floor or upper buyers cannot supply the spending needed to explain the residual. This preserves the threshold response. At ε=ε∗(a)/N\varepsilon=\varepsilon_*(a)/N, both error terms are small for sufficiently small ε∗(a)\varepsilon_*(a), since N=Ωa(K2)N=\Omega_a(K^2). Appendix § 9 gives the quantitative estimates.

Constant error and local decoding. At constant accuracy, total unapproved expenditure can grow with the graph. We instead bound the amount received by each vertex gadget. A vertex decodes correctly whenever this expenditure is small throughout its radius-two neighborhood: price comparisons use incoming neighbors, and wire accounting uses both endpoints. Bounded degree limits the number of vertices affected by any one gadget receiving too much expenditure. For errors below a suitable constant multiple of 1/K21/K^2, at most Oa(Nε)O_a(N\varepsilon) constraints fail. For an nn-vertex source graph, N=Θa(K2n)N=\Theta_a(K^2n), so choosing a sufficiently small constant accuracy makes the failure fraction arbitrarily small. Under PCP for PPAD, the required weak threshold problem is hard: start from weak Pure-Circuit instances in which every node is used as an input exactly once [6], then apply the threshold gadgets of [5]. This preserves bounded degree and transfers failures with only a constant loss.

The two-slope algorithm. On unit bundles, the lower-slope contribution is constant. Subtracting it and scaling reduces each nonindifferent buyer’s utility to Ui(xi)=∑jmin⁡{xij,τij}U_i(x_i)=\sum_j \min\{x_{ij},\tau_{ij}\}, preserving demand and minimum-expenditure tie-breaking; indifferent buyers have zero thresholds. All quantities below a threshold now have the same marginal value. Fractional thresholds introduce a difficulty absent from the bi-valued case: a buyer can exhaust a cheap good’s useful quantity while retaining both money and room in her bundle.

We extend the increasing-price method of [17], tracking each buyer’s remaining budget and quantity separately. An initial quantity flow identifies goods that can be assigned price zero. On these goods, each buyer receives either a full bundle of useful quantities or her entire threshold quantity of every identified good, so any unused supply can later fill bundle deficits without changing utility or expenditure. At each subsequent stage, we use reciprocal price as a parameter and apply the Gallo–Grigoriadis–Tarjan parametric maximum-flow algorithm [8] to find the largest feasible common price for the remaining goods. A residual-network certificate in the expenditure network identifies which goods can be committed at that price and establishes the key invariant: every continuing buyer has filled every threshold at earlier prices. This ensures that buyers receive cheaper useful quantities first. Buyers stop when their budget or unit-quantity constraint binds, or when all their useful quantities have been allocated. Unused free goods complete their bundles without changing utility or expenditure. These properties establish demand optimality and minimum expenditure. Each stage commits at least one good, giving at most NN stages; together with polynomial bounds on intermediate encoding lengths, the parametric-flow implementation yields a strongly polynomial algorithm. § 6 gives the implementation and proof. With three common slopes, linear utilities 00, atat, and tt are already representable by allowing zero-length segments, so the hardness result follows directly.

Related work

Exact HZ equilibria need not be rational. Vazirani and Yannakakis [17] established this fact and placed their computation in FIXP. Alaei, Jalaly Khalilabadi, and Tardos [1] gave exact polynomial-time algorithms, using algebraic representations, when the number of buyer preference types or good types is fixed. Garg, Tao, and Végh [9] studied constrained piecewise linear concave utilities, including matching markets, and obtained approximation schemes when the number of buyers or goods is fixed. Their existence theorem also provides normalized equilibria with minimum-expenditure tie-breaking.

References

  1. [1][AJT17] Saeed Alaei, Pooya Jalaly Khalilabadi, and Éva Tardos. Computing equilibrium in matching markets. In Proceedings of the 2017 ACM Conference on Economics and Computation (EC), pages 245–261, 2017. https://doi.org/10.1145/3033274.3085150. Full version: https://arxiv.org/abs/1703.10689.
  2. [2][BPR16] Yakov Babichenko, Christos H. Papadimitriou, and Aviad Rubinstein. Can almost everybody be almost happy? In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science (ITCS), pages 1–9, 2016. https://doi.org/10.1145/2840728.2840731. Full version: https://arxiv.org/abs/1504.02411.
  3. [3][BLXZ26] Mark Braverman, Jingyi Liu, Eric Xue, and Chenghan Zhou. Hardness of approximate Hylland–Zeckhauser equilibria. Preprint, arXiv:2606.00951v2, June 9, 2026. https://arxiv.org/abs/2606.00951v2.
  4. [4][CCPY22] Thomas Chen, Xi Chen, Binghui Peng, and Mihalis Yannakakis. Computational hardness of the Hylland–Zeckhauser scheme. In Proceedings of the 2022 Annual ACM–SIAM Symposium on Discrete Algorithms (SODA), pages 2253–2268, 2022. https://doi.org/10.1137/1.9781611977073.90. Full version: https://arxiv.org/abs/2107.05746.
  5. [5]Argyrios Deligkas, John Fearnley, Alexandros Hollender, and Themistoklis Melissourgos. Pure-Circuit: Tight inapproximability for PPAD. Journal of the ACM, 71(5), Article 31, 2024. https://doi.org/10.1145/3678166. Theorem 4.23 in the author version: author-version PDF.
  6. [6]Argyrios Deligkas, John Fearnley, Alexandros Hollender, and Themistoklis Melissourgos. Fisher markets with approximately optimal bundles and the need for a PCP theorem for PPAD. In Proceedings of the 58th Annual ACM Symposium on Theory of Computing (STOC), pages 1049–1060, 2026. https://doi.org/10.1145/3798129.3800817. Full version: https://arxiv.org/abs/2604.27276v3.
  7. [7]Federico Echenique, Antonio Miralles, and Jun Zhang. Constrained pseudo-market equilibrium. American Economic Review, 111(11):3699–3732, 2021. https://doi.org/10.1257/aer.20201769.
  8. [8]Giorgio Gallo, Michael D. Grigoriadis, and Robert E. Tarjan. A fast parametric maximum flow algorithm and applications. SIAM Journal on Computing, 18(1):30–55, 1989. https://doi.org/10.1137/0218003.
  9. [9]Jugal Garg, Yixin Tao, and László A. Végh. Approximating equilibrium under constrained piecewise linear concave utilities with applications to matching markets. In Proceedings of the 2022 Annual ACM–SIAM Symposium on Discrete Algorithms (SODA), pages 2269–2284, 2022. https://doi.org/10.1137/1.9781611977073.91. Conference version: https://www.laszlovegh.eu/papers/Garg-Tao-Vegh-SODA.pdf.
  10. [10]Yinghua He, Antonio Miralles, Marek Pycia, and Jianye Yan. A pseudo-market approach to allocation with priorities. American Economic Journal: Microeconomics, 10(3):272–314, 2018. https://doi.org/10.1257/mic.20150259.
  11. [12]Aanund Hylland and Richard Zeckhauser. The efficient allocation of individuals to positions. Journal of Political Economy, 87(2):293–314, 1979. https://doi.org/10.1086/260757.
  12. [13]OpenAI. The PCP-for-PPAD conjecture: a quasilinear reduction. Preprint, September 25, 2026. Preprint PDF.hub.valency.io/works/W_4sppw2e4
  13. [14]Ioannis Panageas, Thorben Tröbst, and Vijay V. Vazirani. Time-efficient algorithms for Nash-bargaining-based matching market models. In Web and Internet Economics (WINE 2024), volume 15534 of Lecture Notes in Computer Science, pages 119–136, Springer, 2026. https://doi.org/10.1007/978-3-032-08560-3_7. Full version: https://arxiv.org/abs/2106.02024v6.
  14. [15]Christos H. Papadimitriou and Binghui Peng. Public goods games in directed networks. In Proceedings of the 22nd ACM Conference on Economics and Computation (EC), pages 745–762, 2021. https://doi.org/10.1145/3465456.3467616. Full version: https://arxiv.org/abs/2106.00718.
  15. [17]Vijay V. Vazirani and Mihalis Yannakakis. Computational complexity of the Hylland–Zeckhauser mechanism for one-sided matching markets. SIAM Journal on Computing, 54(2):193–232, 2025. https://doi.org/10.1137/23M157586X. Author manuscript: https://ics.uci.edu/~vazirani/VY.pdf.
  16. [18]Yonglei Yan and Zhengyang Liu. Approximation and irrationality in Hylland–Zeckhauser equilibria. Preprint, arXiv:2606.06317v2, June 17, 2026. https://arxiv.org/abs/2606.06317v2.

Paper details

vlnc:W_k2hjtadf
Version
v2 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 17

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

GPT-6 Astra

View statement
Looking for related papers…
Contents