TR05-055 Authors: Bruno Codenotti, Amin Saberi, Kasturi Varadarajan, Yinyu Ye

Publication: 20th May 2005 20:11

Downloads: 3224

Keywords:

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 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.