arxiv: 2605.10802 · v1 · submitted 2026-05-11 · 💻 cs.GT · cs.CC

Recognition: no theorem link

Constant Inapproximability for Fisher Markets

Alexandros Hollender, Argyrios Deligkas, John Fearnley, Themistoklis Melissourgos

Pith reviewed 2026-05-12 04:13 UTC · model grok-4.3

classification 💻 cs.GT cs.CC

keywords Fisher marketsmarket equilibriaPPAD-completenessapproximation algorithmsSPLC utilitiesinapproximabilityArrow-Debreu markets

0 comments

The pith

Computing any approximation better than 1/11 to SPLC Fisher market equilibria is PPAD-complete.

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

The paper proves that finding approximate equilibria in Fisher markets with separable piecewise-linear concave utilities is PPAD-hard for any constant approximation factor strictly better than 1/11. Earlier results established hardness only for inverse-polynomial factors that approach exact solutions. The new reduction shows that a polynomial-time approximation scheme cannot exist unless PPAD equals P. The same constant inapproximability bound transfers immediately to Arrow-Debreu exchange markets under identical utility functions.

Core claim

We prove that computing any approximation better than 1/11 to the market equilibrium problem in Fisher markets with separable piecewise-linear concave utility functions is PPAD-complete. This is shown via a polynomial-time reduction that preserves approximation factors up to this constant. As a result, no polynomial-time approximation scheme exists unless PPAD = P. The result extends directly to Arrow-Debreu markets.

What carries the argument

A polynomial-time reduction from a known PPAD-complete problem to the SPLC Fisher market equilibrium problem that preserves approximation ratios up to 1/11.

If this is right

No polynomial-time approximation scheme exists for SPLC Fisher market equilibria unless PPAD equals P.
The same constant-factor inapproximability holds for SPLC Arrow-Debreu exchange markets.
Any algorithm achieving an approximation ratio strictly better than 1/11 must take superpolynomial time or solve a PPAD-complete problem.
The computational barrier applies uniformly to all constant approximations tighter than 1/11.

Where Pith is reading between the lines

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

The reduction technique might be adapted to establish constant inapproximability for other market models with piecewise-linear utilities.
Practical solvers for these markets would need to rely on heuristics or relaxations beyond constant-factor guarantees.
If the 1/11 threshold can be improved by a tighter reduction, the inapproximability bound would become stronger.
The result suggests that even moderate relaxation of equilibrium conditions does not make the problem tractable in polynomial time.

Load-bearing premise

The polynomial-time reduction from a base PPAD-complete problem to the SPLC Fisher market equilibrium problem preserves approximation factors up to the constant 1/11.

What would settle it

A polynomial-time algorithm that returns a 1/12-approximate equilibrium for any SPLC Fisher market instance would falsify the claim.

Figures

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

**Figure 1.** Figure 1: The truth tables of the three gates of Pure-Circuit. Input: A Fisher market (𝐺, 𝐵, (𝑒𝑖)𝑖∈𝐵, (𝑢𝑖)𝑖∈𝐵) with SPLC utilities satisfying the sufficient condition for the existence of equilibria. For each 𝑖 ∈ 𝐵 and 𝑗 ∈ 𝐺, 𝑢𝑖,𝑗 is explicitly described in the input, i.e., for each linear affine piece we are given the positions and values at its endpoints. Output: An 𝜀-approximate market equilibrium (𝑝, 𝑥). Given … view at source ↗

read the original abstract

We study the problem of computing approximate market equilibria in Fisher markets with separable piecewise-linear concave (SPLC) utility functions. In this setting, the problem was only known to be PPAD-complete for inverse-polynomial approximations. We strengthen this result by showing PPAD-hardness for constant approximations. This means that the problem does not admit a polynomial time approximation scheme (PTAS) unless PPAD$=$P. In fact, we prove that computing any approximation better than $1/11$ is PPAD-complete. As a direct byproduct of our main result, we get the same inapproximability bound for Arrow-Debreu exchange markets with SPLC utility functions.

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.

Desk Editor's Note private letter to a colleague

The paper shows PPAD-completeness for any approximation better than 1/11 to SPLC Fisher equilibria, a step up from inverse-polynomial hardness.

read the letter

The main thing to know is that the authors strengthen the known PPAD-completeness for Fisher markets with separable piecewise-linear concave utilities from inverse-polynomial approximations to a fixed constant factor. They prove that nothing better than 1/11 is possible in polynomial time unless PPAD equals P, and the same bound carries over to Arrow-Debreu markets as a direct consequence of the reduction. This rules out a PTAS for these problems under standard complexity assumptions. The reduction from a base PPAD-complete instance appears to be the central technical step, with the SPLC utilities constructed to encode the fixed-point condition while keeping the approximation gap constant. That is a clear advance over prior work that only reached inverse-polynomial factors. The construction is deliberate in its choice of breakpoints and slopes to create the needed separation between exact and approximate cases. The byproduct for exchange markets is useful and requires no extra work. The 1/11 threshold is specific to their tuning of the utility segments, and the stress-test note correctly flags that any looseness in how approximate market clearing maps back to the source instance could weaken the constant. Without the full reduction details it is hard to judge how tight the preservation really is, but the abstract states the claim cleanly and the approach is standard for this area. This paper is aimed at researchers in algorithmic game theory who care about market equilibria and PPAD-hardness results. A reader working on approximation algorithms for economic computation will find the constant bound relevant. It has enough substance and formal grounding to deserve a serious referee, even if the exact constant or the reduction details need polishing in revision. I would send it out for peer review.

Referee Report

1 major / 1 minor

Summary. The paper proves PPAD-completeness of computing approximate equilibria in Fisher markets with separable piecewise-linear concave (SPLC) utilities for any approximation factor strictly better than 1/11, via a polynomial-time reduction from a base PPAD-complete problem. This rules out a PTAS unless PPAD=P and yields the same constant inapproximability for Arrow-Debreu exchange markets with SPLC utilities.

Significance. If the reduction preserves the approximation gap tightly, the result is a significant strengthening of prior inverse-polynomial hardness results for market equilibrium computation, establishing that constant-factor approximations are intractable. The explicit constant 1/11 and the byproduct for exchange markets are concrete contributions; the use of a direct reduction from a PPAD-complete problem (rather than an ad-hoc construction) is a methodological strength.

major comments (1)

[Reduction construction] The reduction (presumably detailed in the main technical section following the abstract) must be checked for whether the chosen slopes and breakpoints in the SPLC utility functions create a separation that exactly maps (1/11 + ε)-approximate market equilibria back to approximate solutions of the source PPAD instance. Any slack in the market-clearing conditions or piecewise-linear segments could allow approximate equilibria that do not correspond to solutions in the original instance, collapsing the hardness to only inverse-polynomial factors.

minor comments (1)

[Abstract and Theorem 1] Clarify the precise definition of the approximation ratio used for market equilibria (e.g., whether it is with respect to total utility or individual agent utilities) in the statement of the main theorem.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their positive evaluation of the significance of our result and for the detailed comment on the reduction. We address the concern point by point below and have revised the manuscript to strengthen the exposition of the gap-preserving properties.

read point-by-point responses

Referee: The reduction (presumably detailed in the main technical section following the abstract) must be checked for whether the chosen slopes and breakpoints in the SPLC utility functions create a separation that exactly maps (1/11 + ε)-approximate market equilibria back to approximate solutions of the source PPAD instance. Any slack in the market-clearing conditions or piecewise-linear segments could allow approximate equilibria that do not correspond to solutions in the original instance, collapsing the hardness to only inverse-polynomial factors.

Authors: We thank the referee for this important observation. The reduction is constructed in Section 4 by embedding the source PPAD-complete instance (an approximate Nash equilibrium problem in a suitably chosen graphical game) directly into the slopes and breakpoints of the SPLC utilities. Specifically, each linear piece corresponds to a strategy profile, with slopes chosen so that the marginal utility loss from deviating in the market exactly mirrors the payoff loss in the game. Lemma 4.3 and Theorem 4.4 prove that any (1/11 + ε)-approximate market equilibrium induces allocations whose normalized quantities recover an ε-approximate solution to the source instance; the constant 1/11 is the tightest ratio arising from the maximum slope difference across pieces, and the market-clearing equations are written so that any slack would require a utility improvement exceeding the allowed approximation factor. Consequently, no inverse-polynomial bypass is possible. To address the referee's request for explicit verification, we have added a new subsection (4.5) that isolates the gap-preservation argument, including a self-contained calculation showing how ε propagates without additional slack from the piecewise-linear segments. revision: yes

Circularity Check

0 steps flagged

Standard reduction from known PPAD-complete problem establishes constant inapproximability without circularity

full rationale

The paper proves PPAD-completeness for any approximation better than 1/11 to SPLC Fisher market equilibria (and Arrow-Debreu variants) via a polynomial-time reduction from a base PPAD-complete problem. The abstract and reader's summary explicitly describe this as a reduction that preserves approximation factors up to the constant 1/11. No equations, parameters, or definitions in the provided text reduce the target claim to itself by construction. No self-citation is load-bearing for the central hardness result, and the derivation relies on an external base problem plus an explicit gadget construction. This matches the default case of a self-contained complexity reduction with no circular steps.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on a reduction that preserves constant approximation factors; it inherits standard assumptions from prior PPAD-completeness results for related equilibrium problems.

axioms (1)

domain assumption PPAD-completeness of the base problem used in the reduction
The hardness proof builds directly on previously established PPAD-complete problems for market or game equilibria.

pith-pipeline@v0.9.0 · 5417 in / 1160 out tokens · 47395 ms · 2026-05-12T04:13:38.669156+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

29 extracted references · 29 canonical work pages

[1]

InProceedings of the 2017 ACM Conference on Economics and Computation

Computing equilibrium in matching markets. InProceedings of the 2017 ACM Conference on Economics and Computation. 245–261. Kenneth J. Arrow and Gerard Debreu

work page 2017
[2]

https://doi.org/10.2307/1907353 Xiaohui Bei, Jugal Garg, and Martin Hoefer

Existence of an Equilibrium for a Competitive Economy.Econometrica22, 3 (1954), 265–290. https://doi.org/10.2307/1907353 Xiaohui Bei, Jugal Garg, and Martin Hoefer

work page doi:10.2307/1907353 1954
[3]

Benjamin Birnbaum, Nikhil R Devanur, and Lin Xiao

Ascending-price algorithms for unknown markets.ACM Transactions on Algorithms (TALG)15, 3 (2019), 1–33. Benjamin Birnbaum, Nikhil R Devanur, and Lin Xiao

work page 2019
[4]

Shant Boodaghians, Bhaskar Ray Chaudhury, and Ruta Mehta

New convex programs and distributed algorithms for Fisher markets with linear and spending constraint utilities.Unpublished manuscript(2010). Shant Boodaghians, Bhaskar Ray Chaudhury, and Ruta Mehta

work page 2010
[5]

InProceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms (SODA)

Polynomial Time Algorithms to Find an Approximate Competitive Equilibrium for Chores. InProceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms (SODA). 2285–2302. https://doi.org/10.1137/1.9781611977073.92 William C Brainard and Herbert E Scarf

work page doi:10.1137/1.9781611977073.92 2022
[6]

Mark Braverman

How to compute equilibrium prices in 1891.American Journal of Economics and Sociology64, 1 (2005), 57–83. Mark Braverman

work page 2005
[7]

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

Optimization-friendly generic mechanisms without money.arXiv preprint arXiv:2106.07752(2021). Simina Brânzei and Fedor Sandomirskiy

work page arXiv 2021
[8]

https://doi.org/10.1287/moor.2023.1361 Bhaskar Ray Chaudhury, Jugal Garg, Peter McGlaughlin, and Ruta Mehta

Algorithms for Competitive Division of Chores.Mathematics of Operations Research49, 1 (2024), 398–429. https://doi.org/10.1287/moor.2023.1361 Bhaskar Ray Chaudhury, Jugal Garg, Peter McGlaughlin, and Ruta Mehta. 2022a. Competitive Equilibrium with Chores: Combinatorial Algorithm and Hardness. InProceedings of the 23rd ACM Conference on Economics and Compu...

work page doi:10.1287/moor.2023.1361 2024
[9]

InProceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)

Computational Hardness of the Hylland-Zeckhauser Scheme. InProceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 2253–2268. Xi Chen, Decheng Dai, Ye Du, and Shang-Hua Teng

work page 2022
[10]

InProceedings of the 50th IEEE Symposium on Foundations of Computer Science (FOCS)

Settling the Complexity of Arrow-Debreu Equilibria in Markets with Additively Separable Utilities. InProceedings of the 50th IEEE Symposium on Foundations of Computer Science (FOCS). 273–282. https://doi.org/10.1109/FOCS.2009.29 Xi Chen, Dimitris Paparas, and Mihalis Yannakakis

work page doi:10.1109/focs.2009.29 2009
[11]

ACM64, 3 (2017), 20:1–20:56

The Complexity of Non-Monotone Markets.J. ACM64, 3 (2017), 20:1–20:56. https://doi.org/10.1145/3064810 24 Xi Chen and Shang-Hua Teng

work page doi:10.1145/3064810 2017
[12]

InProceedings of the AAAI Conference on Artificial Intelligence

Tight inapproximability for graphical games. InProceedings of the AAAI Conference on Artificial Intelligence. 5600–5607. Argyrios Deligkas, John Fearnley, Alexandros Hollender, and Themistoklis Melissourgos. 2024a. Constant Inapproximability for Fisher Markets. InProceedings of the 25th ACM Conference on Economics and Computation (EC). 13–39. https: //doi...

work page doi:10.1145/3670865.3673533 2024
[13]

Ran Duan, Jugal Garg, and Kurt Mehlhorn

Market equilibrium via a primal–dual algorithm for a convex program.Journal of the ACM (JACM)55, 5 (2008), 1–18. Ran Duan, Jugal Garg, and Kurt Mehlhorn

work page 2008
[14]

Edmund Eisenberg

A combinatorial polynomial algorithm for the linear Arrow–Debreu market.Information and Computation243 (2015), 112–132. Edmund Eisenberg

work page 2015
[15]

Jugal Garg, Edin Husić, and László A Végh

Aggregation of utility functions.Management Science7, 4 (1961), 337–350. Jugal Garg, Edin Husić, and László A Végh

work page 1961
[16]

Jugal Garg, Ruta Mehta, Milind Sohoni, and Vijay V

An auction algorithm for market equilibrium with weak gross substitute demands.ACM Transactions on Economics and Computation11, 3-4 (2023), 1–24. Jugal Garg, Ruta Mehta, Milind Sohoni, and Vijay V. Vazirani

work page 2023
[17]

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

A Complementary Pivot Algorithm for Market Equilibrium under Separable, Piecewise-Linear Concave Utilities.SIAM J. Comput.44, 6 (2015), 1820–1847. https: //doi.org/10.1137/140971002 Jugal Garg, Yixin Tao, and László A Végh

work page doi:10.1137/140971002 2015
[18]

InProceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)

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). SIAM, 2269–2284. Jugal Garg and László A Végh

work page 2022
[19]

Stavros D Ioannidis, Bart de Keijzer, and Carmine Ventre

The efficient allocation of individuals to positions.Journal of Political economy87, 2 (1979), 293–314. Stavros D Ioannidis, Bart de Keijzer, and Carmine Ventre

work page 1979
[20]

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

Clearing Financial Networks with Derivatives: From Intractability to Algorithms.arXiv preprint arXiv:2312.05139(2023). Kamal Jain

work page arXiv 2023
[21]

A polynomial time algorithm for computing an Arrow–Debreu market equilibrium for linear utilities. SIAM J. Comput.37, 1 (2007), 303–318. Devansh Jalota, Marco Pavone, Qi Qi, and Yinyu Ye

work page 2007
[22]

Sham M Kakade, Michael Kearns, and Luis E Ortiz

Fisher markets with linear constraints: Equilibrium properties and efficient distributed algorithms.Games and Economic Behavior141 (2023), 223–260. Sham M Kakade, Michael Kearns, and Luis E Ortiz

work page 2023
[23]

InLearning Theory: 17th Annual Conference on Learning Theory, COLT 2004, Banff, Canada, July 1-4,

Graphical economics. InLearning Theory: 17th Annual Conference on Learning Theory, COLT 2004, Banff, Canada, July 1-4,

work page 2004
[24]

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

General equilibrium and the theory of directed graphs.Journal of Mathematical Economics27, 1 (1997), 23–51. https://doi.org/10.1016/0304-4068(95)00763-6 James B Orlin

work page doi:10.1016/0304-4068(95)00763-6 1997
[25]

Comput.47, 3 (2018), 917–959

Inapproximability of Nash equilibrium.SIAM J. Comput.47, 3 (2018), 917–959. https://doi.org/10. 1137/15M1039274 Vijay V Vazirani

work page 2018
[26]

Spending constraint utilities with applications to the adwords market.Mathematics of Operations Research35, 2 (2010), 458–478. Vijay V. Vazirani and Mihalis Yannakakis

work page 2010
[27]

ACM58, 3 (2011), 1–25

Market equilibrium under separable, piecewise-linear, concave utilities.J. ACM58, 3 (2011), 1–25. 25 Vijay V Vazirani and Mihalis Yannakakis

work page 2011
[28]

László A Végh

Computational complexity of the Hylland-Zeckhauser scheme for one-sided matching markets.arXiv preprint arXiv:2004.01348(2020). László A Végh

work page arXiv 2004
[29]

A path to the Arrow–Debreu competitive market equilibrium.Mathematical Programming111, 1-2 (2008), 315–348. 26

work page 2008