Title: A Strongly Polynomial Algorithm for Linear Exchange Markets

Description: Speaker: Prof. Jugal Garg

Time: Tuesday, 14 January 2020, 2:0pm
Venue: Department of Computer Science and Engineering, Room No. 109, 01st Floor, New CSE/CC Building

Abstract:
In this talk, I will present the first strongly polynomial algorithm for computing equilibrium in exchange markets with linear utilities. The exchange market model has been extensively studied since its introduction by Walras in 1874. This problem has a non-separable convex flow formulation and the property that we can find an equilibrium in strongly polynomial time given its support, i.e., the flow variables which are non-zero. Using a variant of the Duan and Mehlhorn (DM) algorithm, we gradually reveal new variables that are in the support of equilibrium. We show that a new variable can be revealed in strongly polynomial time if we start the DM algorithm with the best possible solution corresponding to the current revealed set. Finding the best solution can be reduced to solving a linear program (LP). Even though we are unable to solve this LP in strongly polynomial time, we show that it can be approximated by a simpler LP with two variables per inequality that is solvable in strongly polynomial time and it turns out to be good enough to make the overall algorithm run in strongly polynomial time.

This is based on joint work with Laszlo Vegh.

Speaker's Profile:
Jugal Garg is an Assistant Professor in Industrial and Enterprise Systems Engineering and an Affiliate Assistant Professor in the Department of Computer Science at the University of Illinois at Urbana-Champaign. Prior to that, he was a postdoctoral fellow at Max-Planck-Institute for Informatics, Germany, and Georgia Tech, USA. He received his Ph.D. from IIT-Bombay in 2012. Jugal is broadly interested in computational aspects of economics and game theory, design and analysis of algorithms, and mathematical programming. Currently, he is working on designing fast algorithms for computing competitive equilibria and their applications to fair division problems.

Organization:
University of Illinois at Urbana-Champaign



Host:
Prof. Sundar Vishwanathan

Date: Tuesday, 14 January, 2020
Time: 2:00pm IST
Access: Public
Category: Talk*
Created by: Department Calendar
Updated: Sunday, 15 November, 2020 3:13am IST
Send Reminder: Yes  -  354 hours 57 minutes before start
Participants: Department Calendar
<all@cse.iitb.ac.in> (External User)
_NUC_department <office@cse.iitb.ac.in> (External User)