László Végh: A Strongly Polynomial Algorithm for Linear Exchange Markets

Abstract: 
In this talk, I will present the first strongly polynomial algorithm for computing an equilibrium in exchange markets with linear utilities. The exchange market model has been extensively studied since its introduction by Walras in 1874. Our starting point is the previous weakly polynomial combinatorial algorithm by Duan and Mehlhorn. We use a variant of this algorithm to gradually reveal new variables that are in the support of every equilibrium. 
A key subroutine used for re-initializing this algorithm reduces 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. This turns out to be good enough to make the overall algorithm run in strongly polynomial time.

This is based on joint work with Jugal Garg.