# CMI Seminar

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

**Speaker:**Ruta Mehta, College of Computing, Georgia Institute of Technology

**Location:**Annenberg 213

We show FIXP-hardness of computing equilibria in Arrow-Debreu exchange markets under Leontief utility functions, and Arrow-DebreuÂ markets under linear utility functions and Leontief production, thereby settling open questions of Vazirani and Yannakakis (2009). In both cases, as required under FIXP, the set of instances mapped onto will admit equilibria, i.e., will be "yes'' instances. If all instances are under consideration, then in both cases we prove that the problem of deciding if a given instance admits an equilibrium is ETR-complete, where ETR is the class Existential Theory of Reals.

The main technical part of our result is the following reduction:

Given a set 'F' 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 market 'M' which has one good corresponding to each variable in 'F'. 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. (Joint work with J. Garg, V. V. Vazirani, S. Yazdanbod)

**Series**Center for the Mathematics of Information Seminar Series

**Contact:** Linda Taddeo at 626-395-6704 ltaddeo@caltech.edu

For more information visit: http://www.cmi.caltech.edu/events.shtml