pith. sign in

arxiv: 2606.00951 · v2 · pith:JEQG3SRUnew · submitted 2026-05-31 · 💻 cs.GT · cs.CC

Hardness of Approximate Hylland-Zeckhauser Equilibria

Mark Braverman , Jingyi Liu , Eric Xue , Chenghan Zhou This is my paper

Pith reviewed 2026-06-28 16:49 UTC · model grok-4.3

classification 💻 cs.GT cs.CC
keywords Hylland-Zeckhauser equilibriumPPAD-hardnessapproximate equilibriaCEEIgeneralized circuitscomputational complexityfair divisionmarket equilibria
0
0 comments X

The pith

Finding an approximate Hylland-Zeckhauser equilibrium is PPAD-hard assuming the PCP-for-PPAD conjecture, and unconditionally for a restricted version.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper sets out to establish that computing approximate competitive equilibria from equal incomes for unit-demand players is computationally intractable in the PPAD sense. It proves conditional hardness by reducing from the (ε,δ)-Generalized Circuits problem under the PCP-for-PPAD conjecture, and proves unconditional hardness for equilibria where players cannot include positive-price items of zero utility in their bundles. A sympathetic reader would care because these equilibria are a standard tool for fair allocation, so the hardness indicates that even allowing small response errors does not make the problem tractable.

Core claim

Assuming the (ε,δ)-Generalized Circuits problem is PPAD-hard, finding an approximate HZ equilibrium is also PPAD-hard. Further, there exists a constant ε such that finding a restricted ε-HZ equilibrium is PPAD-hard, where the restriction requires that players' bundles contain no positive-price items for which the player has zero utility.

What carries the argument

A reduction from the (ε,δ)-Generalized Circuits problem to the problem of finding approximate HZ equilibria.

If this is right

  • Approximate HZ equilibria cannot be computed in polynomial time unless PPAD is in P, under the stated conjecture.
  • The restricted version of approximate HZ equilibria remains PPAD-hard even without assuming the conjecture.
  • Market mechanisms relying on HZ equilibria for unit-demand players inherit this intractability even when small approximation is permitted.
  • The result supplies additional motivation for proving the PCP-for-PPAD conjecture to obtain robust hardness statements for other market problems.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Similar hardness may apply to other equilibrium concepts that allow approximate best-response behavior.
  • Practical fair-division systems using HZ allocations may need to adopt further relaxations beyond the restricted form studied here.
  • The modeling restriction on zero-utility purchases could be tested empirically to see whether it aligns with observed buyer behavior in real markets.

Load-bearing premise

The PCP-for-PPAD conjecture that (ε,δ)-Generalized Circuits is PPAD-hard, together with the modeling choice that the restricted equilibrium forbids positive-price zero-utility items.

What would settle it

A polynomial-time algorithm that outputs a restricted ε-HZ equilibrium for some constant ε would directly refute the unconditional hardness result.

read the original abstract

In this paper, we investigate the computational hardness of finding fractional allocations to unit-demand players using competitive equilibria from equal incomes (CEEI), where we allow a small constant error in players' response to market prices (also known as an approximate Hylland-Zeckhauser equilibrium). We show that assuming the $\mathbf{(\varepsilon,\delta)}$-Generalized Circuits problem is PPAD-hard (the "PCP-for-PPAD" conjecture), finding an approximate HZ equilibrium is also PPAD-hard. This result provides additional motivation for trying to prove the PCP-for-PPAD conjecture as a tool for obtaining robust computational hardness results about markets. Further, we introduce a natural restriction on approximate HZ equilibria, where players' bundles may still only be approximately optimal given the prices, but may not contain positive-price items for which the player has zero utility. We show unconditionally that there exists a constant $\epsilon$ such that finding a restricted $\epsilon$-HZ equilibrium is PPAD-hard.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 1 minor

Summary. The manuscript proves two hardness results for approximate Hylland-Zeckhauser (HZ) equilibria in unit-demand markets with equal incomes. Assuming the (ε,δ)-Generalized Circuits problem is PPAD-hard (the PCP-for-PPAD conjecture), it shows that finding an approximate HZ equilibrium is PPAD-hard. Unconditionally, it shows that there exists a constant ε such that finding a restricted ε-HZ equilibrium—where bundles may not contain positive-price items yielding zero utility—is PPAD-hard.

Significance. If correct, the conditional result supplies additional motivation for establishing the PCP-for-PPAD conjecture as a route to robust market hardness statements. The unconditional result is a direct contribution via a self-contained reduction, though it applies only to the authors' restricted equilibrium variant. No machine-checked proofs or parameter-free derivations are present, but the separation into conditional and unconditional arguments is a clear organizational strength.

major comments (2)
  1. [§2] §2 (definition of restricted HZ equilibrium): the restriction forbidding positive-price zero-utility items is introduced by the authors and deviates from the standard approximate HZ definition used in the conditional result and prior literature; the reduction must therefore enforce this restriction while preserving PPAD-hardness, yet the manuscript provides no explicit argument that the restricted problem remains equivalent in computational difficulty to the unrestricted version.
  2. [§4] §4 (unconditional hardness statement): the claim that a constant ε exists is load-bearing for the unconditional result, but the manuscript does not exhibit an explicit numerical value for ε or verify that the reduction's approximation parameters remain constant (independent of instance size) after the restriction is imposed.
minor comments (1)
  1. The abstract and introduction should explicitly state the numerical range of ε and δ used in the (ε,δ)-Generalized Circuits conjecture to allow readers to compare approximation parameters across the two results.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their thoughtful review and for highlighting these points of clarification. We respond to each major comment below and indicate the revisions we will make to strengthen the manuscript.

read point-by-point responses

  1. Referee: §2 (definition of restricted HZ equilibrium): the restriction forbidding positive-price zero-utility items is introduced by the authors and deviates from the standard approximate HZ definition used in the conditional result and prior literature; the reduction must therefore enforce this restriction while preserving PPAD-hardness, yet the manuscript provides no explicit argument that the restricted problem remains equivalent in computational difficulty to the unrestricted version.

    Authors: We do not claim computational equivalence between the restricted and unrestricted variants. Our unconditional result proves PPAD-hardness directly for the restricted ε-HZ equilibrium via a self-contained reduction from a PPAD-complete problem. The reduction is designed so that the equilibria it produces satisfy the restriction (i.e., no positive-price zero-utility items appear in the bundles), and any restricted approximate equilibrium can be mapped back to a solution of the source instance. We will add a dedicated paragraph in §2 that explicitly describes how the gadgets enforce the restriction without weakening the hardness, thereby making the argument self-contained. revision: yes

  2. Referee: §4 (unconditional hardness statement): the claim that a constant ε exists is load-bearing for the unconditional result, but the manuscript does not exhibit an explicit numerical value for ε or verify that the reduction's approximation parameters remain constant (independent of instance size) after the restriction is imposed.

    Authors: The reduction parameters (including those arising from the restriction) are fixed constants taken from the underlying generalized-circuit construction and do not grow with instance size; this is already implicit in the gadget analysis but not stated explicitly. We agree that exhibiting a concrete numerical bound on ε and a short verification paragraph would improve clarity. We will revise §4 to state an explicit constant (derived from the maximum approximation error across all gadgets) and confirm that all parameters remain independent of n. revision: yes

Circularity Check

0 steps flagged

No circularity: hardness results from external conjecture and direct reduction

full rationale

The paper's main claims consist of a conditional PPAD-hardness result that explicitly assumes the external PCP-for-PPAD conjecture on (ε,δ)-Generalized Circuits, plus an unconditional direct hardness proof for an explicitly defined restricted variant of approximate HZ equilibria. Neither claim reduces by construction to a self-definition, a fitted input renamed as prediction, or a load-bearing self-citation chain; the modeling restriction is introduced transparently and the reductions are presented as independent of the paper's own outputs. The derivation is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The conditional claim rests on the PCP-for-PPAD conjecture; the unconditional claim rests on the modeling restriction that buyers do not purchase positive-price zero-utility items. No free parameters or invented entities are introduced.

axioms (1)
  • domain assumption (ε,δ)-Generalized Circuits problem is PPAD-hard (PCP-for-PPAD conjecture)
    Directly invoked to obtain the conditional PPAD-hardness of approximate HZ equilibria.

pith-pipeline@v0.9.1-grok · 5701 in / 1134 out tokens · 27111 ms · 2026-06-28T16:49:25.939529+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

31 extracted references · 12 canonical work pages

  1. [1]

    Végh , keywords =

    Jugal Garg and Yixin Tao and László A. Végh , keywords =. Approximating competitive equilibrium by Nash welfare , journal =. 2026 , issn =. doi:https://doi.org/10.1016/j.geb.2026.03.004 , url =

    work page doi:10.1016/j.geb.2026.03.004 2026

  2. [2]

    Proceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems , pages =

    Caragiannis, Ioannis and Hansen, Kristoffer Arnsfelt and Rathi, Nidhi , title =. Proceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems , pages =. 2024 , isbn =

    2024

  3. [3]

    12th Innovations in Theoretical Computer Science Conference , year=

    Computational Complexity of the Hylland-Zeckhauser Scheme for One-Sided Matching Markets , author=. 12th Innovations in Theoretical Computer Science Conference , year=

  4. [4]

    2026 , eprint=

    Fisher Markets with Approximately Optimal Bundles and the Need for a PCP Theorem for PPAD , author=. 2026 , eprint=

    2026

  5. [5]

    2024 , isbn =

    Deligkas, Argyrios and Fearnley, John and Hollender, Alexandros and Melissourgos, Themistoklis , title =. 2024 , isbn =. doi:10.1145/3670865.3673533 , booktitle =

    work page doi:10.1145/3670865.3673533 2024

  6. [6]

    2026 , eprint=

    Constant Approximation for Hylland--Zeckhauser Equilibria , author=. 2026 , eprint=

    2026

  7. [7]

    Shapley, L. S. and Shubik, M. , title =. 1971 , issue_date =. doi:10.1007/BF01753437 , journal =

    work page doi:10.1007/bf01753437 1971

  8. [8]

    , title =

    Leonard, Herman B. , title =. Journal of Political Economy , volume =. 1983 , doi =

    1983

  9. [9]

    Random Serial Dictatorship and the Core from Random Endowments in House Allocation Problems , urldate =

    Atila Abdulkad. Random Serial Dictatorship and the Core from Random Endowments in House Allocation Problems , urldate =. Econometrica , number =

  10. [10]

    On cores and indivisibility , journal =

    Lloyd Shapley and Herbert Scarf , abstract =. On cores and indivisibility , journal =. 1974 , issn =. doi:https://doi.org/10.1016/0304-4068(74)90033-0 , url =

    work page doi:10.1016/0304-4068(74)90033-0 1974

  11. [11]

    A New Solution to the Random Assignment Problem , journal =

    Anna Bogomolnaia and Hervé Moulin , keywords =. A New Solution to the Random Assignment Problem , journal =. 2001 , issn =. doi:https://doi.org/10.1006/jeth.2000.2710 , url =

    work page doi:10.1006/jeth.2000.2710 2001

  12. [12]

    and Markakis, Evangelos and Mehta, Aranyak , title =

    Lipton, Richard J. and Markakis, Evangelos and Mehta, Aranyak , title =. 2003 , isbn =. doi:10.1145/779928.779933 , pages =

    work page doi:10.1145/779928.779933 2003

  13. [13]

    Vazirani , year=

    Thorben Tröbst and Vijay V. Vazirani , year=. Cardinal-Utility Matching Markets: The Quest for Envy-Freeness,. 2402.08851 , archivePrefix=

    arXiv

  14. [14]

    1974 , issn =

    Equity, envy, and efficiency , journal =. 1974 , issn =. doi:https://doi.org/10.1016/0022-0531(74)90075-1 , url =

    work page doi:10.1016/0022-0531(74)90075-1 1974

  15. [15]

    SIAM Journal on Computing , volume =

    Rubinstein, Aviad , title =. SIAM Journal on Computing , volume =. 2018 , doi =

    2018

  16. [16]

    Settling the Complexity of Computing Approximate Two-Player

    Rubinstein, Aviad , booktitle=. Settling the Complexity of Computing Approximate Two-Player. 2016 , volume=

    2016

  17. [17]

    2009 , issue_date =

    Chen, Xi and Deng, Xiaotie and Teng, Shang-Hua , title =. 2009 , issue_date =. doi:10.1145/1516512.1516516 , journal =

    work page doi:10.1145/1516512.1516516 2009

  18. [18]

    Journal of political economy , volume=

    Multi-item auctions , author=. Journal of political economy , volume=. 1986 , publisher=

    1986

  19. [19]

    2022 , organization=

    Deligkas, Argyrios and Fearnley, John and Hollender, Alexandros and Melissourgos, Themistoklis , booktitle=. 2022 , organization=

    2022

  20. [20]

    Can Almost Everybody be Almost Happy?

    Yakov Babichenko and Christos Papadimitriou and Aviad Rubinstein , year=. Can Almost Everybody be Almost Happy?. 1504.02411 , archivePrefix=

    arXiv

  21. [21]

    The Combinatorial Assignment Problem: Approximate Competitive Equilibrium from Equal Incomes , urldate =

    Eric Budish , journal =. The Combinatorial Assignment Problem: Approximate Competitive Equilibrium from Equal Incomes , urldate =

  22. [22]

    Finding clearing payments in financial networks with credit default swaps is

    Schuldenzucker, Steffen and Seuken, Sven and Battiston, Stefano , booktitle=. Finding clearing payments in financial networks with credit default swaps is. 2017 , organization=

    2017

  23. [23]

    43rd International Symposium on Mathematical Foundations of Computer Science , year=

    Hardness Results for Consensus-Halving , author=. 43rd International Symposium on Mathematical Foundations of Computer Science , year=

  24. [24]

    Proceedings of the 22nd ACM Conference on Economics and Computation , pages=

    On the complexity of equilibrium computation in first-price auctions , author=. Proceedings of the 22nd ACM Conference on Economics and Computation , pages=

  25. [25]

    Proceedings of the 17th International Conference on Web and Internet Economics (WINE) , year =

    Chen, Xi and Kroer, Christian and Kumar, Rachitesh , title =. Proceedings of the 17th International Conference on Web and Internet Economics (WINE) , year =

  26. [26]

    and Hollender, Alexandros and Igarashi, Ayumi and Manurangsi, Pasin and Suksompong, Warut , year=

    Goldberg, Paul W. and Hollender, Alexandros and Igarashi, Ayumi and Manurangsi, Pasin and Suksompong, Warut , year=. Consensus Halving for Sets of Items , volume=. Mathematics of Operations Research , publisher=. doi:10.1287/moor.2021.1249 , number=

    work page doi:10.1287/moor.2021.1249 2021

  27. [27]

    The Efficient Allocation of Individuals to Positions , urldate =

    Aanund Hylland and Richard Zeckhauser , journal =. The Efficient Allocation of Individuals to Positions , urldate =

  28. [28]

    Optimization-friendly generic mechanisms without money , publisher =

    Braverman, Mark , keywords =. Optimization-friendly generic mechanisms without money , publisher =. 2021 , copyright =. doi:10.48550/ARXIV.2106.07752 , url =

    work page doi:10.48550/arxiv.2106.07752 2021

  29. [29]

    Public Goods Games in Directed Networks , url=

    Papadimitriou, Christos and Peng, Binghui , year=. Public Goods Games in Directed Networks , url=. doi:10.1145/3465456.3467616 , booktitle=

    work page doi:10.1145/3465456.3467616

  30. [30]

    CoRR , volume =

    Thomas Chen and Xi Chen and Binghui Peng and Mihalis Yannakakis , title =. CoRR , volume =. 2021 , url =. 2107.05746 , timestamp =

    arXiv 2021

  31. [31]

    2005 , isbn =

    Blum, Avrim and Mansour, Yishay , title =. 2005 , isbn =. doi:10.1007/11503415_42 , booktitle =

    work page doi:10.1007/11503415_42 2005