{"78211":{"#nid":"78211","#data":{"type":"event","title":"ARC Colloquium: Vijay V. Vazirani, Georgia Tech","body":[{"value":"\u003Cp\u003E\u0026nbsp;\u003Cstrong\u003EAbstract: \u003C\/strong\u003EUsing the powerful machinery of the linear complementarity problem and Lemke\u0027s algorithm, we give a practical algorithm for computing an equilibrium for Fisher and Arrow-Debreu markets\u0026nbsp;under separable, piecewise-linear concave (SPLC) utilities, despite the PPAD-completeness of\u0026nbsp;this case.\u0026nbsp;\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;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\u0026nbsp;problem as well as the problem of Vazirani and Yannakakis of obtaining a path following algorithm\u0026nbsp;for SPLC markets, thereby giving a direct proof of membership of this case in PPAD.\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;We also prove that SPLC markets have an odd number of equilibria (up to scaling), hence matching\u0026nbsp;the classical result of Shapley (1974), which was based on the Lemke-Howson algorithm and\u0026nbsp;shows a similar fact about Nash equilibria of a 2-person bimatrix game.\u0026nbsp;\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;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\u0026nbsp;of the fact that the set of equilibrium\u0026nbsp;prices is convex.\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;(This is joint work with Jugal Garg, Ruta Mehta and Milind Sohoni.)\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"A Complementary Pivot Algorithm for Market Equilibrium under Separable, Piecewise-Linear Concave Utilities"}],"uid":"27263","created_gmt":"2012-01-13 15:23:32","changed_gmt":"2016-10-08 01:57:02","author":"Elizabeth Ndongi","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2012-01-18T14:00:00-05:00","event_time_end":"2012-01-18T14:00:00-05:00","event_time_end_last":"2012-01-18T14:00:00-05:00","gmt_time_start":"2012-01-18 19:00:00","gmt_time_end":"2012-01-18 19:00:00","gmt_time_end_last":"2012-01-18 19:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"50875","name":"School of Computer Science"},{"id":"70263","name":"ARC"}],"categories":[],"keywords":[],"core_research_areas":[],"news_room_topics":[],"event_categories":[{"id":"1795","name":"Seminar\/Lecture\/Colloquium"}],"invited_audience":[],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[{"value":"\u003Cp\u003E\u003Ca href=\u0022mailto:ndongi@cc.gatech.edu\u0022\u003Endongi@cc.gatech.edu\u003C\/a\u003E\u003C\/p\u003E","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}}}