Conference 2014
Top image

 
Home
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: New (Practical) Complementary Pivot Algorithms for Market Equilibria

Abstract:
Complementary pivot algorithms, in the style of the simplex algorithm, tend to work well in practice despite having an exponential worst case behavior -- a case in point being the classic Lemke-Howson algorithm (1964) for 2-player Nash equilibrium. This algorithm also gives a direct proof of membership of the problem in the class PPAD and yields deep structural insights, such as oddness of the number of equilibria.
Our first result accomplishes all of the above for the problem of finding an equilibrium for an Arrow-Debreu market under separable, piecewise linear concave utilities. Our second result extends this to markets with production.

Based on the following paper, and a recent joint work with Jugal Garg: http://www.cc.gatech.edu/~vazirani/SPLC.pdf