TCS Journal 2008 Journal Article
The complexity of equilibria: Hardness results for economies via a correspondence with games
- Bruno Codenotti
- Amin Saberi
- Kasturi Varadarajan
- Yinyu Ye
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.