Conference 2014
Top image

Program LNMB Conference
Invited Speakers LNMB conference
Program PhD presentations
Abstracts PhD presentations
Registration LNMB Conference
Announcement NGB/LNMB Seminar
Abstracts/Bios NGB/LNMB Seminar
Registration NGB/LNMB Seminar
Registered Participants
Conference Office
How to get there
Return to LNMB Site

Vijay Vazirani: Dichotomies in Equilibrium Computation: Markets Provide a Surprise

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.