Journal article
The complexity of equilibria: Hardness results for economies via a correspondence with games
Theoretical computer science, Vol.408(2), pp.188-198
2008
DOI: 10.1016/j.tcs.2008.08.007
Abstract
We give a reduction from any two-player game to a special case of the Leontief exchange economy, with the property that the Nash equilibria of the game and the equilibria of the market are in one-to-one correspondence.
Our reduction exposes a computational hurdle inherent in solving certain families of market equilibrium problems: finding an equilibrium for Leontief economies is at least as hard as finding a Nash equilibrium for two-player nonzero sum games, a problem recently proven to be
P
P
A
D
-complete.
As a corollary of the one-to-one correspondence, we obtain a number of hardness results for questions related to the computation of market equilibria, using results already established for games [I. Gilboa, E. Zemel, Nash and correlated equilibria: Some complexity considerations, Games and Economic Behavior 1 (1989) 80–93]. In particular, among other results, we show that it is
N
P
-hard to say whether a particular family of Leontief exchange economies, that is guaranteed to have at least one equilibrium, has more than one equilibrium.
Perhaps more importantly, we also prove that it is
N
P
-hard to decide whether a Leontief exchange economy has an equilibrium. This fact should be contrasted against the known
P
P
A
D
-completeness result of [C.H. Papadimitriou, On the complexity of the parity argument and other inefficient proofs of existence, Journal of Computer and System Sciences 48 (1994) 498–532], which holds when the problem satisfies some standard sufficient conditions that make it equivalent to the computational version of Brouwer’s Fixed Point Theorem.
Details
- Title: Subtitle
- The complexity of equilibria: Hardness results for economies via a correspondence with games
- Creators
- Bruno Codenotti - IIT-CNR, Pisa, ItalyAmin Saberi - Stanford UniversityKasturi Varadarajan - University of IowaYinyu Ye - Stanford University
- Resource Type
- Journal article
- Publication Details
- Theoretical computer science, Vol.408(2), pp.188-198
- DOI
- 10.1016/j.tcs.2008.08.007
- ISSN
- 0304-3975
- eISSN
- 1879-2294
- Publisher
- Elsevier B.V
- Language
- English
- Date published
- 2008
- Academic Unit
- Computer Science
- Record Identifier
- 9984259492702771
Metrics
4 Record Views