Computing Equilibrium Prices: Does Theory Meet Practice?

The best known algorithms for the computation of market equilibria, in a general setting, are not guaranteed to run in polynomial time. On the other hand, simple poly-time algorithms are available for various restricted - yet important - markets. In this paper, we experimentally explore the gray zone between the general problem and the poly-time solvable special cases. More precisely, we analyze the performance of some simple algorithms, for inputs which are relevant in practice, and where the theory does not provide poly-time guarantees.