ECCC-Report TR05-055https://eccc.weizmann.ac.il/report/2005/055Comments and Revisions published for TR05-055en-usFri, 20 May 2005 20:11:27 +0300
Paper TR05-055
| Leontief Economies Encode Nonzero Sum Two-Player Games |
Bruno Codenotti,
Amin Saberi,
Kasturi Varadarajan,
Yinyu Ye
https://eccc.weizmann.ac.il/report/2005/055We 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 potential 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.
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. 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, which holds when the problem satisfies some standard
sufficient conditions that make it equivalent to the computational
version of Brouwer's Fixed Point Theorem.
Fri, 20 May 2005 20:11:27 +0300https://eccc.weizmann.ac.il/report/2005/055