Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR05-055 | 19th May 2005 00:00

Leontief Economies Encode Nonzero Sum Two-Player Games



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.

ISSN 1433-8092 | Imprint