TITLE: Polynomial time algorithms to compute market equilibria.

SPEAKER: Kamal Jain,  Microsoft Research


Abstract: I will present some of the recent developments in the area of
computing market equilibria with an emphasis on my latest work titled,
"A polynomial time algorithm for computing the Arrow-Debreu Market
Equilibrium for Linear Utilities". Existence of market equilibria was
first conjectured in 1874 and formally proven in 1954 by two Nobel
laureates, Arrow and Debreu. Their existence theorem holds for any
concave utility function. The case of linear utilities provides a lot of
simplification and a real opportunity to understand computational
issues. For this reason, this case of linear utilities was heavily
studied (at least for quarter century), which is recently settled in
last December.