{"72405":{"#nid":"72405","#data":{"type":"event","title":"ARC Colloquium: Ruta Mehta, IIT, Bombay","body":[{"value":"\u003Cp\u003E\u003Cstrong\u003EAbstract:\u003C\/strong\u003E Using 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 under\u0026nbsp;separable, piecewise-linear concave (SPLC) utilities, despite the PPAD-completeness of\u0026nbsp;this case.\u003C\/p\u003E\u003Cp\u003EIn 1975, Eaves had given such an algorithm for the case of linear utilities and had asked for an extension to the piecewise-linear, concave case. Our result settles 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.\u003C\/p\u003E\u003Cp\u003EWe also prove that SPLC markets have an odd number of equilibria (up to scaling),\u0026nbsp;hence matching\u0026nbsp;the classical result of Shapley (1974), which was based on the Lemke-Howson algorithm and shows\u0026nbsp;a similar fact about Nash\u0026nbsp;equilibria of a 2-person bimatrix game.\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;(This is joint work with Jugal Garg, Milind Sohoni and Vijay V. Vazirani.)\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"A Lemke-Type Algorithm for Market Equilibrium Under Separable, Piecewise-Linear Concave Utilities"}],"uid":"27263","created_gmt":"2011-11-04 10:49:16","changed_gmt":"2016-10-08 01:56:32","author":"Elizabeth Ndongi","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2011-12-01T15:30:00-05:00","event_time_end":"2011-12-01T15:30:00-05:00","event_time_end_last":"2011-12-01T15:30:00-05:00","gmt_time_start":"2011-12-01 20:30:00","gmt_time_end":"2011-12-01 20:30:00","gmt_time_end_last":"2011-12-01 20:30:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"47223","name":"College of Computing"},{"id":"70263","name":"ARC"}],"categories":[],"keywords":[],"core_research_areas":[],"news_room_topics":[],"event_categories":[],"invited_audience":[],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[{"value":"\u003Cp\u003EElizabeth Ndongi\u003C\/p\u003E","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}}}