PaperlayerView exact revision on arXiv

Source-linked AI summary

Settling the Complexity of Arrow-Debreu Equilibria in Markets with Additively Separable Utilities

Xi Chen, Decheng Dai, Ye Du, Shang-Hua Teng

arXiv:0904.0644v1cs.CCcs.GT

TL;DR

Whether equilibria with additively separable PLC utilities are polynomial-time computable or PPAD-hard had remained open. The paper reduces sparse bimatrix games to exchange markets using price-regulating markets. It proves PPAD-completeness already for 2-linear markets, while 1-linear markets admit polynomial-time algorithms.

  • Problem

    Whether market equilibria with additively separable PLC utilities can be computed in polynomial time or are PPAD-hard remained an open question.

    Source: §1 · p. 2

  • Method

    The reduction uses price-regulating markets to encode game strategies in prices and adds traders whose behavior enforces Nash-equilibrium constraints.

    Source: §1.1 · p. 3

  • Results

    2-linear markets are PPAD-complete, whereas 1-linear markets admit polynomial-time equilibrium algorithms [18, 30, 12, 14, 25].

    Source: §1.1 · p. 3

  • Takeaways & Limitations

    The tractable 1-linear case does not extend to 2-linear markets under the stated complexity classification.

    Source: §1.1 · p. 3

    The sparse-market formulation assumes each trader owns and is interested in at most t goods.

    Source: §2.3 · p. 8

Abstract

from arXiv · show

We prove that the problem of computing an Arrow-Debreu market equilibrium is PPAD-complete even when all traders use additively separable, piecewise-linear and concave utility functions. In fact, our proof shows that this market-equilibrium problem does not have a fully polynomial-time approximation scheme unless every problem in PPAD is solvable in polynomial time.

1 Introduction

The introduction frames computing exchange-market equilibria with additively separable PLC utilities as an open complexity question and states that this paper proves PPAD-completeness.

1 Introduction

  • Arrow-Debreu’s existence proof is nonconstructive for polynomial-time computation, while fundamental complexity questions about market equilibria remained unsettled.Source: §1 · p. 2
  • Vazirani asked whether equilibria with additively separable PLC utilities are polynomial-time computable or PPAD-hard, a question echoed in subsequent work.The paper states that it settles this complexity question.Source: §1 · p. 2, §1.1 · p. 3

1.1 Our Contribution

  • Even 2-linear markets are PPAD-complete, whereas equilibria in 1-linear markets can be found in polynomial time.A t-linear market uses additively separable utilities that are piecewise linear with t segments.Source: §1.1 · p. 3
  • Normalized approximate-equilibrium prices in the price-regulating markets lie in [1, 2], allowing variables to be encoded as pk − 1.The construction uses this price-regulation property to encode free variables between 0 and 1.Source: §1.1 · p. 3
  • Adding small-endowment traders to a price-regulating market encodes two probability vectors in prices and maps every approximate market equilibrium to an approximate Nash equilibrium.For sparse games, the resulting market also has a sparse trader-good relation.Source: §1.1 · p. 3

1.2 Related Work

  • The paper follows Scarf in defining approximate market equilibrium through approximate supply-demand and/or individual-optimality conditions, rather than geometric distance from an exact equilibrium.Source: §1.2 · p. 4

1.2.1 Algorithms for Market Equilibria

  • Polynomial-time algorithms cover linear utilities and some restricted nonconvex markets, including PLC markets with a constant number of goods and CES markets with substitution elasticity s ≥ 1/2.The cited PLC and CES results are due to Devanur and Kannan and Codenotti et al., respectively.Source: §1.2.1 · pp. 4–5

1.2.2 The Complexity of Equilibrium Problems

  • Earlier reductions established PPAD-completeness for two-player Nash equilibria and linked that result to Leontief market hardness; approximation hardness also reached Leontief and low-elasticity CES markets.Source: §1.2.2 · p. 5

2 Preliminaries

The preliminaries define the sparse game and market-equilibrium problems, then establish PPAD-completeness for a restricted market class. Strong connectivity also guarantees equilibrium existence, with rational prices of polynomial bit length when market parameters are rational.

2.1 Complexity of Nash Equilibria in Sparse Two-Player Games

  • Sparse Bimatrix is PPAD-complete for finding an n^-6-well-supported Nash equilibrium in a sparse normalized two-player game.The games have entries in [-1, 1], with at most 10 nonzero entries per row and column.Source: §2.1 · p. 6

2.2 Markets with Additively Separable PLC Utilities

  • A market is strongly connected when its trader graph links traders through goods they own and other traders want; this condition guarantees equilibrium existence.For rational market parameters, an equilibrium price is rational and has polynomial bit length.Source: §2.2 · p. 7

2.3 Definition of the Sparse Market Equilibrium Problem

  • The sparse-market problem searches for an n^-13-approximate equilibrium in a strongly connected, rational market with additively separable PLC utilities.The restricted version further imposes boundedness, at most two utility segments, and limits on each trader’s endowment support and interests.Source: §2.3 · pp. 7–8

2.2 Markets with Additively Separable PLC Utilities

  • The paper uses t-linear markets for additively separable utilities whose per-good functions have at most t piecewise-linear segments.A 2-linear market therefore allows at most two segments per trader-good utility function.Source: §2.2 · p. 6, §2.3 · p. 8

2.3 Definition of the Sparse Market Equilibrium Problem

  • Sparse Market is PPAD-complete for strongly connected, 2-linear, 27-bounded, 23-sparse markets, with an n^-13-approximate equilibrium as the search target.The market has additively separable PLC utilities.Source: §2.3 · pp. 8–9
  • The authors state that the sparse-market restrictions retain PPAD-completeness, while the problem is in PPAD.Their membership argument reduces approximate market equilibrium to finding an approximate fixed point of a Lipschitz continuous map.Source: §2.3 · pp. 8–9

3 A Price-Regulating Market

The authors construct a price-regulating market whose approximate equilibrium prices are confined to a fixed interval. Those prices can then encode variables for the subsequent reduction.

3 A Price-Regulating Market

  • A normalized n^-1-approximate equilibrium price vector of M_n has every price p_k between 1 and 2.Conversely, prices in that interval form a market-clearing allocation with optimal bundles.Source: §3 · p. 9
  • The constructed market M_n is strongly connected, 2-bounded, and 2-sparse.Its price-regulation property supplies the bounded price coordinates used in the reduction.Source: §3 · p. 9
  • Setting x_k = p_k − 1 encodes each of n free variables in the interval [0, 1].The later reduction uses the first 2n prices of M_{2n+2} to encode a pair of distributions.Source: §3 · p. 10

4 Reduction from Sparse Bimatrix to Sparse Market

The reduction augments a price-regulating market with traders whose endowments and utilities encode payoff comparisons from a sparse two-player game. Approximate market equilibria can then be decoded into well-supported approximate Nash equilibria.

4 Reduction from Sparse Bimatrix to Sparse Market

  • A polynomial-time reduction maps an n × n sparse two-player game (A, B), with A, B in [−1, 1]^(n×n), to Sparse Market by adding traders to price-regulating market M2n+2.Source: §4 · p. 10

4.1.1 Traders T_s, where s ∈ S

  • The traders T_s retain the price-regulating market’s basic endowment and linear-utility pattern, with slight parameter changes.Each T_s initially owns 1/n of good G_i and values G_i and G_j at slopes 2 and 1, respectively.Source: §4.1.1 · p. 11

4.1.2 Traders T_u, where u ∈ U

  • For each row comparison in A, traders T_u encode the payoff difference as nonnegative vectors C and D with C − D = A_i − A_j.Each such trader has at most 23 goods with nonzero utility functions.Source: §4.1.2 · pp. 11–12

4.1.3 Traders T_v, where v ∈ V

  • Traders T_v analogously encode column-payoff differences in B as nonnegative vectors C and D with C − D = B_i − B_j.Their endowments and nonzero utility functions each have at most 22 and 23 entries, respectively.Source: §4.1.3 · pp. 12–13

4.1.4 Traders T_i, where i ∈ [2n]

  • Each trader T_i owns 1/n^12 of good G_{2n+1} and has positive utility only for good G_i.The other goods have zero utility for T_i.Source: §4.1.4 · p. 13

4.2 From Approximate Market Equilibria to Approximate Nash Equilibria

  • The vectors x′ and y′ are normalized into distributions (x, y); if p is an n−13-approximate market equilibrium of M, the constructed pair is an n−6-well-supported Nash equilibrium of (A, B).Source: §4.2 · pp. 13–14
  • Any n^-13-approximate market equilibrium of the constructed market yields an n^-6-well-supported Nash equilibrium of the input game.The market has 2n+2 goods, and the reduction is polynomial-time.Source: §4 · p. 10, §4.2 · pp. 13–14

5 Correctness of the Reduction

Section 5 verifies the reduction by constraining prices in any normalized n^-13-approximate market equilibrium and showing how its allocation yields an ε-well-supported Nash equilibrium.

5.1 The Price-Regulation Property

  • Every price in the normalized approximate equilibrium lies between 1 and 2, inclusive.Source: §5.1 · p. 14

5.2 Relations between pk and wk[T2] −ak[T2]

  • For a normalized n^-13-approximate market equilibrium p and an optimal allocation X that clears the market approximately, if w_k[T2]−a_k[T2] > 3/n^13 for some k ∈ [2n+2], then p_k=1; if it is < −3/n^13, then p_k=2.Source: §5.2 · p. 15
  • For paired traders in U and V, initial holdings cover final allocations of goods k≤2n+1, and the resulting inequalities imply p2n+1=1.Source: §5.2 · pp. 16–17

5.3 Proof of Theorem 4

  • The proof establishes properties of x′ and y′ that, after normalization, make them an ε-well-supported Nash equilibrium.Here ε=n^-6.Source: §5.3 · p. 18

A Proof of Theorem 2

The proof establishes equilibrium existence for strongly connected additively separable PLC markets by first obtaining a quasi-equilibrium, then showing it is a market equilibrium and has a polynomial-size rational representation.

A Proof of Theorem 2

  • A quasi-equilibrium need not enforce optimal allocations for zero-income traders, but positive income for every trader makes it a market equilibrium.Source: A Proof of Theorem 2 · p. 23
  • Strong connectivity and additively separable PLC utilities meet the stated conditions for a quasi-equilibrium, with non-satiability following from a strictly monotone utility on an incident good.Source: A Proof of Theorem 2 · p. 23
  • Strong connectivity rules out zero-income traders in a quasi-equilibrium, making it a market equilibrium.A zero-income trader would lead along a directed path to a positive-income trader wanting an unbounded amount of a zero-priced good.Source: A Proof of Theorem 2 · pp. 23–24
  • A rational linear program for the cell containing an equilibrium has a polynomial-size rational solution, which is also an equilibrium.The cited algorithm divides the price space into cells and characterizes equilibria in each by a rational linear program.Source: A Proof of Theorem 2 · p. 24
Loading 0904.0644v1…