pith. machine review for the scientific record. sign in

arxiv: 2604.27276 · v1 · submitted 2026-04-30 · 💻 cs.GT · cs.CC

Recognition: unknown

Fisher Markets with Approximately Optimal Bundles and the Need for a PCP Theorem for PPAD

Argyrios Deligkas , John Fearnley , Alexandros Hollender , Themistoklis Melissourgos
Authors on Pith no claims yet

Pith reviewed 2026-05-07 08:50 UTC · model grok-4.3

classification 💻 cs.GT cs.CC
keywords Fisher marketscompetitive equilibriumapproximate bundlesPPAD-hardnessPCP-for-PPAD conjectureSPLC utilitiesmarket clearinglinear capped utilities
0
0 comments X

The pith

Computing competitive equilibria where buyers get nearly optimal bundles is PPAD-hard for constant factors, but only under the PCP-for-PPAD conjecture.

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

The paper examines the task of finding competitive equilibria in Fisher markets with separable piecewise-linear concave utilities when buyers are permitted to receive bundles that are only a constant factor away from being optimal for them. It proves that this approximate problem is PPAD-hard even when all buyers have identical budgets, utilities are linear capped functions, and the market is allowed to clear only approximately. The authors further establish that any demonstration of PPAD-hardness for this problem in a wide class of markets would itself prove the PCP-for-PPAD conjecture, making the conjecture necessary rather than optional for the hardness result.

Core claim

Finding a competitive equilibrium in which every buyer receives a (1-δ)-optimal bundle for some fixed δ > 0 is PPAD-hard assuming the PCP-for-PPAD conjecture. The hardness continues to hold when all buyers share the same budget, when utilities are linear capped, and when the market clears only to within ε < 1/9 of exact balance. Any proof that the problem is PPAD-hard for a broad family of markets that includes the constructed instances would establish the PCP-for-PPAD conjecture.

What carries the argument

A reduction from PPAD instances to Fisher market instances with SPLC utilities that produces constant-factor approximate equilibria only when the PCP-for-PPAD conjecture is used to amplify the approximation gap.

If this is right

  • The problem stays PPAD-hard even after restricting to identical budgets and linear capped utilities.
  • Approximate clearing to within any constant less than 1/9 does not make the problem easier.
  • The same hardness applies when buyers need only constant-factor near-optimal bundles rather than exact ones.
  • The result identifies the first natural problem whose constant-δ intractability is equivalent to the PCP-for-PPAD conjecture.

Where Pith is reading between the lines

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

  • Similar constant-factor approximation versions of other PPAD-complete economic problems may turn out to be equivalent to the same conjecture.
  • Algorithms that work for exponentially small δ might still exist even if the conjecture holds.
  • The construction could be adapted to test whether other market models inherit the same dependence on the conjecture.

Load-bearing premise

The PCP-for-PPAD conjecture is true.

What would settle it

A polynomial-time algorithm that returns a competitive equilibrium with (1-δ)-optimal bundles for some constant δ > 0 in Fisher markets with linear capped utilities, equal budgets, and ε-approximate clearing for ε < 1/9 would imply that the PCP-for-PPAD conjecture is false.

Figures

Figures reproduced from arXiv: 2604.27276 by Alexandros Hollender, Argyrios Deligkas, John Fearnley, Themistoklis Melissourgos.

Figure 1
Figure 1. Figure 1: The truth tables of the two gates of Pure-Circuit. PCP-for-PPAD Conjecture (Pure-Circuit version). There exists a constant δ > 0 such that δ-Pure-Circuit is PPAD-hard, even when every node is the input to exactly one gate. Furthermore, as we show in Theorem 2.2, removing the restriction on every node being the input to exactly one gate does not change the conjecture, i.e., the versions with and without tha… view at source ↗
Figure 2
Figure 2. Figure 2: The construction of the flow graph. good g1 with length 1, and is currently buying 0.6 units of that segment, and another in-window segment to good g2, of which 0.2 of the maximum 0.4 units are currently bought. Note that buyer b1 can shift up to εc money from g1 and burn it instead, and doing so reduces the over-clearing at g1, since fewer units of g1 would now be bought. Buyer b1 can also shift εc money … view at source ↗
Figure 3
Figure 3. Figure 3: An inverter buyer with parameter t. Proposition 4.4. Fix any constant εm < 1/9. For any constant δc > 0, there exists a constant δm > 0 such that δc-Pure-Circuit reduces in polynomial time to the problem of finding an (εm, δm)-approximate market equilibrium in a family of simple Fisher markets. The rest of this section is devoted to the proof of this proposition. At the end of the proof, we explain the min… view at source ↗
Figure 4
Figure 4. Figure 4: NAND gate gadget. All inverter buyers have t = 2/9. u aux v w inv1 uaux inv2 uaux inv3 uaux inv4 uaux inv1 auxv inv2 auxv invauxw t = 4/9 view at source ↗
Figure 5
Figure 5. Figure 5: PURIFY gate gadget. All inverter buyers, except invauxw, have t = 2/9. PURIFY gates. For every gate g = (PURIFY, u, v, w), i.e., every PURIFY gate with input u and outputs v and w, we introduce a new good auxg, as well as the following inverter buyers: • Four inverter buyers inv1 uaux, inv2 uaux, inv3 uaux, inv4 uaux, each with input good in = u, output good out = auxg, and parameter t = 2/9. • Two inverte… view at source ↗
Figure 6
Figure 6. Figure 6: The truth tables of additional Pure-Circuit gates. nodes u1, . . . , uM, called unary vector, and we will think of them as encoding in unary the value of u. Given an assignment x ′ ∈ {0, ⊥, 1} |VP | of Pure-Circuit, for any node u ∈ VG and b ∈ {0, ⊥, 1}, we denote Ub = |{i ∈ [M] : x ′ [ui ] = b}|. We extract an assignment x ∈ [0, 1]|VG| of ε-GCircuit by computing for each u ∈ VG, x[u] = U1/M. For ease of p… view at source ↗
read the original abstract

We study the problem of computing a competitive equilibrium with approximately optimal bundles in Fisher markets with separable piecewise-linear concave (SPLC) utility functions, meaning that every buyer receives a $(1-\delta)$-optimal bundle, instead of a perfectly optimal one. We establish the first intractability result for the problem by showing that it is PPAD-hard for some constant $\delta > 0$, assuming the PCP-for-PPAD conjecture. This hardness result holds even if all buyers have identical budgets (competitive equilibrium with equal incomes), linear capped utilities, and even if we also allow $\varepsilon$-approximate clearing instead of perfect clearing, for any constant $\varepsilon < 1/9$. Importantly, we show that the PCP-for-PPAD conjecture is in fact required to show hardness for constant $\delta$: showing PPAD-hardness for finding such approximate market equilibria in a broad class of markets encompassing those generated by our hardness result would prove the conjecture. This is the first natural problem where the conjecture is provably required to establish hardness for it.

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

0 major / 2 minor

Summary. The manuscript claims to provide the first intractability result for computing competitive equilibria with (1-δ)-approximately optimal bundles (rather than exactly optimal) in Fisher markets with separable piecewise-linear concave utilities. It shows that the problem is PPAD-hard for some constant δ > 0 assuming the PCP-for-PPAD conjecture. The hardness holds even under equal buyer budgets, linear capped utilities, and ε-approximate market clearing for any constant ε < 1/9. The paper also proves a necessity result: that establishing PPAD-hardness for constant δ in a broad class of markets (including those arising from the reduction) would itself prove the PCP-for-PPAD conjecture.

Significance. If the conditional reduction and necessity argument hold, the result is significant for algorithmic game theory and computational complexity of equilibria. It supplies the first hardness for approximate bundle optimality in Fisher markets, extends prior work on exact equilibria to constant-factor approximations, and identifies a natural problem where the PCP-for-PPAD conjecture is provably required for constant-δ hardness. The necessity direction is a particular strength, as it explains barriers to unconditional results and links market computation directly to open questions in PPAD.

minor comments (2)
  1. The abstract and introduction would benefit from an explicit (even if small) numerical example of the constructed market instance to illustrate how the PCP-for-PPAD reduction produces linear capped utilities and equal incomes.
  2. Section 4 (or the reduction section) should include a brief remark on why the ε < 1/9 bound is tight enough to preserve the (1-δ) bundle approximation without collapsing to exact clearing.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of the manuscript, recognition of its significance in algorithmic game theory, and recommendation for minor revision. We are particularly pleased that the necessity result linking constant-δ hardness to the PCP-for-PPAD conjecture is highlighted as a strength. As the report contains no specific major comments, we interpret the minor revision recommendation as pertaining to any editorial or presentational improvements that may be suggested during the process.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper's central result is an explicit conditional PPAD-hardness statement for constant-δ approximate bundle equilibria in Fisher markets (even under equal incomes, linear capped utilities, and ε-approximate clearing), derived by reduction under the external PCP-for-PPAD conjecture. The paper further proves a necessity direction showing that unconditional hardness for the broad class would itself establish the conjecture. No load-bearing step reduces by definition, by fitted-parameter renaming, or by a self-citation chain whose cited result is itself unverified; the conjecture is treated as an independent assumption whose necessity is demonstrated rather than assumed. The derivation chain therefore remains self-contained against external benchmarks and does not exhibit any of the enumerated circularity patterns.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the unproven PCP-for-PPAD conjecture as the sole non-standard assumption needed to obtain PPAD-hardness for constant δ. No numerical parameters are fitted to data and no new entities are postulated; the result is a conditional complexity statement.

axioms (1)
  • ad hoc to paper PCP-for-PPAD conjecture
    Assumed without proof to establish PPAD-hardness for constant δ; the paper proves that this assumption is necessary because hardness in a broad class would imply the conjecture.

pith-pipeline@v0.9.0 · 5498 in / 1482 out tokens · 67259 ms · 2026-05-07T08:50:32.445339+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

19 extracted references · 15 canonical work pages

  1. [1]

    Computing equilibrium in matching markets

    Saeed Alaei, Pooya Jalaly Khalilabadi, and Eva Tardos. Computing equilibrium in matching markets. InProceedings of the 2017 ACM Conference on Economics and Computation, pages 245–261,

    2017

  2. [2]

    Papadimitriou, and Aviad Rubinstein

    59 Yakov Babichenko, Christos H. Papadimitriou, and Aviad Rubinstein. Can almost everybody be almost happy? InProceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, pages 1–9. ACM,

    2016

  3. [3]

    Benjamin Birnbaum, Nikhil R Devanur, and Lin Xiao

    doi:10.1145/2840728.2840731. Benjamin Birnbaum, Nikhil R Devanur, and Lin Xiao. New convex programs and distributed algorithms for Fisher markets with linear and spending constraint utilities.Unpublished manuscript,

    work page doi:10.1145/2840728.2840731

  4. [4]

    Optimization-friendly generic mechanisms without money.arXiv preprint arXiv:2106.07752,

    Mark Braverman. Optimization-friendly generic mechanisms without money.arXiv preprint arXiv:2106.07752,

    work page arXiv

  5. [5]

    Thomas Chen, Xi Chen, Binghui Peng, and Mihalis Yannakakis

    doi:10.1007/978-3-642-17572-5_43. Thomas Chen, Xi Chen, Binghui Peng, and Mihalis Yannakakis. Computational hardness of the Hylland-Zeckhauser scheme. InProceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2253–2268. SIAM,

    work page doi:10.1007/978-3-642-17572-5_43 2022

  6. [6]

    Bruno Codenotti and Kasturi Varadarajan

    doi:10.1145/1516512.1516516. Bruno Codenotti and Kasturi Varadarajan. Computation of market equilibria by convex programming.Algorithmic Game Theory, pages 135–158,

    work page doi:10.1145/1516512.1516516

  7. [7]

    Pure-circuit: Tight inapproximability for PPAD.JACM, 71(5):31:1–31:48, 2024a

    Argyrios Deligkas, John Fearnley, Alexandros Hollender, and Themistoklis Melissour- gos. Pure-circuit: Tight inapproximability for PPAD.JACM, 71(5):31:1–31:48, 2024a. doi:10.1145/3678166. URLhttps://doi.org/10.1145/3678166. Argyrios Deligkas, John Fearnley, Alexandros Hollender, and Themistoklis Melissourgos. Con- stant inapproximability for fisher market...

    work page doi:10.1145/3678166 2024

  8. [8]

    Numerical experiments in revisited brittle fracture

    doi:10.1016/s0022- 0000(03)00011-4. Nikhil R Devanur. The spending constraint model for market equilibrium: Algorithmic, existence and uniqueness results. InProceedings of the thirty-sixth annual ACM symposium on Theory of computing, pages 519–528,

    work page doi:10.1016/s0022-

  9. [9]

    Comput.44, 6 (2015), 1820–1847

    doi:10.1137/140971002. Jugal Garg, Yixin Tao, and László A Végh. Approximating equilibrium under constrained piecewise linear concave utilities with applications to matching markets. InProceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2269–2284. SIAM,

    work page doi:10.1137/140971002 2022

  10. [10]

    Jugal Garg, Yixin Tao, and László A

    doi:10.1287/moor.2019.0129. Jugal Garg, Yixin Tao, and László A. Végh. Approximating competitive equilibrium by Nash welfare.Games and Economic Behavior, 158:142–166,

    work page doi:10.1287/moor.2019.0129 2019

  11. [11]

    Kristoffer Arnsfelt Hansen and Xinhao Nie

    doi:10.1016/j.geb.2026.03.004. Kristoffer Arnsfelt Hansen and Xinhao Nie. On the complexity of stationary Nash equilibria in discounted perfect information stochastic games.arXiv preprint arXiv:2510.11550,

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

  12. [12]

    Clearing financial networks with derivatives: From intractability to algorithms.arXiv preprint arXiv:2312.05139,

    Stavros D Ioannidis, Bart de Keijzer, and Carmine Ventre. Clearing financial networks with derivatives: From intractability to algorithms.arXiv preprint arXiv:2312.05139,

    work page arXiv

  13. [13]

    Devansh Jalota, Marco Pavone, Qi Qi, and Yinyu Ye

    doi:10.1007/978-3-540-45198-3_9. Devansh Jalota, Marco Pavone, Qi Qi, and Yinyu Ye. Fisher markets with linear constraints: Equilibrium properties and efficient distributed algorithms.Games and Economic Behavior, 141:223–260,

    work page doi:10.1007/978-3-540-45198-3_9

  14. [14]

    Graphical economics

    61 Sham M Kakade, Michael Kearns, and Luis E Ortiz. Graphical economics. InLearning Theory: 17th Annual Conference on Learning Theory, COLT 2004, Banff, Canada, July 1-4,

    2004

  15. [15]

    Donald E

    doi:10.1007/978-3-540-77105-0_40. Donald E. Knuth.The Art of Computer Programming, Volume 3: Sorting and Searching. Addison-Wesley Professional,

    work page doi:10.1007/978-3-540-77105-0_40

  16. [16]

    https://doi.org/10.1016/0304-4068(95)00763-6 James B Orlin

    doi:10.1016/0304-4068(95)00763-6. James B Orlin. Improved algorithms for computing Fisher’s market clearing prices: Computing Fisher’s market clearing prices. InProceedings of the forty-second ACM symposium on Theory of computing, pages 291–300,

    work page doi:10.1016/0304-4068(95)00763-6

  17. [17]

    Aviad Rubinstein

    doi:10.1109/focs.2016.35. Aviad Rubinstein. Inapproximability of Nash equilibrium.SIAM Journal on Computing, 47(3): 917–959,

    work page doi:10.1109/focs.2016.35 2016

  18. [18]

    Vijay V Vazirani

    doi:10.1137/15M1039274. Vijay V Vazirani. Spending constraint utilities with applications to the adwords market. Mathematics of Operations Research, 35(2):458–478,

    work page doi:10.1137/15m1039274

  19. [19]

    4230/LIPIcs.ITCS.2021.59

    URLhttps://doi.org/10. 4230/LIPIcs.ITCS.2021.59. László A Végh. Strongly polynomial algorithm for a class of minimum-cost flow problems with separable convex objectives. InProceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 27–40,

    2021