http://www.cnr.it/ontology/cnr/individuo/prodotto/ID29993

The complexity of equilibria: Hardness results for economies via a correspondence with games (Articolo in rivista)

Type

Prodotto della ricerca (Classe)
Articolo in rivista (Classe)

Label

The complexity of equilibria: Hardness results for economies via a correspondence with games (Articolo in rivista) (literal)

Anno

2008-01-01T00:00:00+01:00 (literal)

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#doi

10.1016/j.tcs.2008.08.007 (literal)

Alternative label

[1] Codenotti B., [2] Saberi A., [2] Ye Y., [3]Varadarajan K. (2008)
The complexity of equilibria: Hardness results for economies via a correspondence with games
in Theoretical computer science; Elsevier Sequoia, Lausanne (Svizzera)
(literal)

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#autori

[1] Codenotti B., [2] Saberi A., [2] Ye Y., [3]Varadarajan K. (literal)

Pagina inizio

188 (literal)

Pagina fine

198 (literal)

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#altreInformazioni

Codice Puma: cnr.iit/2008-A0-023 (literal)

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#numeroVolume

408 (literal)

Rivista

Theoretical computer science (Rivista)

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#pagineTotali

11 (literal)

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#numeroFascicolo

2-3 (literal)

Note

Scopu (literal)
ISI Web of Science (WOS) (literal)

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#affiliazioni

[1] IIT-CNR, Pisa, Italy; [2] Department of Management Science and Engineering, Stanford University, CA, United States; [3] Department of Computer Science, The University of Iowa, Iowa City, United States (literal)

Titolo

The complexity of equilibria: Hardness results for economies via a correspondence with games (literal)

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 PPAD-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 NP-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 NP-hard to decide whether a Leontief exchange economy has an equilibrium. This fact should be contrasted against the known PPAD-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. (literal)

Editore