Equilibrium in Markets: Algorithms and Complexity

Market equilibrium is a central solution concept in economics, where prices are set such that the demand and supply are balanced. It has been under study ever since the inception of the field starting with the pioneering work of Adam Smith (1776) and Leon Walras (1874). In a celebrated result, Arrow and Debreu (1954) showed the existence of equilibrium using the Kakutani fixed point theorem, which is highly non-constructive. Since then many algorithms have been proposed, especially worth mentioning are algorithms of Scarf (1967) and Smale (1976) to find approximate fixed points. While much progress has been made in the last century, computationally large part of progress happened in last fifteen years using tools from complexity theory, optimization and mathematical programming. This has led to a remarkable theory of computability of equilibria in markets. My work touches many aspects of this problem from computation to strategic analysis to learning. While the problem has turned out to be intractable for most of the important cases, designing even a non-enumerative algorithm for these cases remained elusive. I will show the first "practical" algorithms for a very general class of markets settling long standing open questions. These algorithms are based on the powerful machinery of linear complementarity problem (LCP) and complementary pivot (Simplex-like) algorithms. I will also show how these results help bring out a clear dichotomy among equilibrium computation problems.

Bio: Jugal Garg is currently a research fellow at Max-Planck-Institute for Informatics, Germany. Prior to that, he was a Algorithms and Randomness Center (ARC) postdoctoral fellow at Georgia Tech for two years. He received his PhD from IIT-Bombay in 2012. Jugal's research explores computational and strategic aspects of equilibria in game theory and economics, and their connections with dynamical systems and learning. He is interested broadly in design and analysis of algorithms, optimization and mathematical programming.