A Faster and Simpler Algorithm for Computing Market Equilibrium

Jim Orlin
M.I.T.

Wednesday, November 11, 2009
3:00 - 4:00 PM
Terman 453

Abstract:

Devanur, Papadimitriou, Saberi, and Vazirani recently published the first polynomial time algorithm for computing an equilibrium for the linear utilities case of the market model defined by Fisher. Here we provide a much faster and simpler algorithm. In addition, we provide the first strongly polynomial time algorithm for computing the equilibrium. (This latter algorithm is not as simple.) We describe our algorithms from an economic perspective in a way that is accessible to a general audience.

---

Operations Research Colloquia: http://or.stanford.edu/oras_seminars.html