### ACO/Theory Seminar - Dichotomies in Equilibrium Computation - Markets Provide a Surprise

- Series
- Other Talks
- Time
- Wednesday, August 21, 2013 - 16:30 for 1 hour (actually 50 minutes)
- Location
- Klaus 1116W
- Speaker
- Vijay V. Vazirani – School of Computer Science, Georgia Tech

**Please Note:** Hosted by School of Computer Science.

Equilibrium computation is among the most significant
additions to the theory of algorithms and computational complexity in
the last decade - it has its own character, quite distinct from the
computability of optimization problems.
Our contribution to this evolving theory can be summarized in the
following sentence: Natural equilibrium computation problems tend to
exhibit striking dichotomies. The dichotomy for Nash equilibrium,
showing a qualitative difference between 2-Nash and k- Nash for k > 2,
has been known for some time. We establish a dichotomy for market
equilibrium.
For this purpose. we need to define the notion of Leontief-free
functions which help capture the joint utility of a bundle of goods that
are substitutes, e.g., bread and bagels. We note that when goods are
complements, e.g., bread and butter, the classical Leontief function
does a splendid job. Surprisingly enough, for the former case, utility
functions had been defined only for special cases in economics, e.g.,
CES utility function.
We were led to our notion from the high vantage point provided by an
algorithmic approach to market equilibria.
Note: Joint work with Jugal Garg and Ruta Mehta.