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.