CoMeT | <%=title %>
Collaborative Management of Talks Hello! sign in or register
Bookmark Talks, Share with Friends, and We Recommend More!
Advanced Search
Home
Calendar
Series
Speaker
Groups
Connections
 
 
 
 
Talk Detail
Posted: comet.paws on  Jan 15 10:40:53 AM
Title: A Complementary Pivot Algorithm for Market Equilibrium under Separable, Piecewise-Linear Concave Utilities  
Speaker:
Vijay V. Vazirani
Sponsor: Carnegie Mellon University  >  School of Computer Science  >  Computer Science Department
Series: Theory Lunch Seminar
Date: Jan 20, 2012 3:30 PM - 4:30 PM
URL: http://calendar.cs.cmu.edu/scsEvents/demo/7444.html
Location: 8102 Gates and Hillman Centers
Detail:

Using the powerful machinery of the linear complementarity problem and Lemke's algorithm, we give a practical algorithm for computing an equilibrium for Fisher and Arrow-Debreu markets under separable, piecewise-linear concave (SPLC) utilities, despite the PPAD- completeness of this case.

In 1975, Eaves had given such an algorithm for the case of linear utilities and had asked for an extension to the piecewise-linear, concave utilities. Our result settles the relevant subcase of his problem as well as the problem of Vazirani and Yannakakis of obtaining a path following algorithm for SPLC markets, thereby giving a direct proof of membership of this case in PPAD.

We also prove that SPLC markets have an odd number of equilibria (up to scaling), hence matching the classical result of Shapley (1974), which was based on the Lemke-Howson algorithm and shows a similar fact about Nash equilibria of a 2-person bimatrix game.

For the linear case, Eaves had asked for a combinatorial interpretation of his algorithm. We provide this and use it to get a particularly simple proof of the fact that the set of equilibrium prices is convex.

This is joint work with Jugal Garg, Ruta Mehta and Milind Sohoni.

Additional information on the Speaker

Poster

 
 
People Who Viewed This Talk, Also Viewed
 
 
Export
RSS Feed: RSS 2.0
ATOM Feed: Atom
iCalendar: iCal
Share: Bookmark and Share
 
Google Calendar:
 
 
 
 
CoMeT Blog
©2009-2019 CoMeT - Supported by Google Grant
School of Information Sciences, University of Pittsburgh, 135 North Bellefield Avenue, Pittsburgh, PA 15260
Real Time Web Analytics