Talks & Seminars
Title: Leontief Exchange Markets Can Solve Polynomial Equations, Yielding FIXP and ETR Hardness
Dr. Jugal Garg,
Date & Time: December 12, 2014 16:30
Venue: Conference Room, C Block, 01st Floor, Department of Computer Science and Engineering, Kanwal Rekhi (KReSIT) Building
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 sets, thereby settling open questions of Vazirani and Yannakakis (2009). As corollaries, we obtain FIXP-hardness for piecewise-linear concave (PLC) utilities and for Arrow-Debreu markets under linear utility functions and polyhedral production sets. In all 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 all 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. 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 joint work with Ruta Mehta, Vijay V. Vazirani and Sadra Yazdanbod)
Speaker Profile:
List of Talks


Faculty CSE IT
Forgot Password
    [+] Sitemap     Feedback