[Colloquium] REMINDER: TTIC Colloquium: Ruta Mehta, Georgia Institute of Technology

[Dawn Ellis]

                                             TTIC Colloquium
                                         **Note Special Date**

When:     Thursday, October 16, at 11:30am

Where:    TTIC, 6045 S Kenwood Avenue, 5th Floor, Room #526

Who:       Ruta Mehta, Georgia Institute of Technology

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

Abstract:

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.

Based on a joint work with Jugal Garg, Vijay V. Vazirani and Sadra Yazdanbod

Host:  Julia Chuzhoy,  cjulia at ttic.edu



-- 
*Dawn Ellis*
Administrative Coordinator,
Bookkeeper
773-834-1757
dellis at ttic.edu

TTIC
6045 S. Kenwood Ave.
Chicago, IL. 60637
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20141015/f3c94f5e/attachment.htm