Leontief Exchange Markets Can Solve Multivariate Polynomial Equations, Yielding FIXP and ETR Hardness

As a consequence of the results stated above, the entire computational difficulty of Arrow-Debreu markets under PLC utility functions lies in the Leontief utility subcase. This is perhaps the most unexpected aspect of our result, since Leontief utilities are meant for the case that goods are perfect complements, whereas PLC utilities are very general, capturing not only the cases when goods are complements and substitutes, but also arbitrary combinations of these and much more.

The main technical part of our result is the following reduction: Given a set 'S' of simultaneous multivariate polynomial equations
in which the variables are constrained to be in a closed bounded region in the positive orthant, we construct a Leontief exchange market 'M' which has one good corresponding to each variable in 'S'. We prove that the equilibria of 'M', when projected onto prices of these latter goods, are in one-to-one correspondence with the set of solutions of the polynomials. This reduction is related to a classic result of Sonnenschein (1972).

(Based on a joint work with Ruta Mehta, Vijay V. Vazirani and Sadra Yazdanbod)