Talks & Seminars
Equilibrium in Markets: Algorithms and Complexity
Dr. Jugal Garg, Max Planck Institute for Informatics, Germany
Date & Time: March 23, 2015 10:30
Venue: Lecture Hall (SIB 201), 03rd Floor, B Block, Department of Computer Science and Engineering, Kanwal Rekhi (KReSIT) Building
Market equilibrium is a central concept in Economics. A market comprises of buyers, each with a budget, and sellers, each with a bundle of goods. Given prices, each buyer buys the most preferred bundle. It is clear that if the prices are set too low then demand will outweigh supply and vice-versa. A key question studied extensively by Economists is whether prices can always be set so that the demand matches supply. In such a case the market is said to be in equilibrium. Some notable early work on this question was by Adam Smith (1776) and Leon Walras (1874). In a celebrated result, which won them the Nobel prize, Arrow and Debreu (1954) showed the existence of such prices using the Kakutani fixed point theorem. Their proof was non-constructive, meaning, it does not yield an algorithm. The algorithmic problem of finding such equilibrium prices attracted a large body of research and many algorithms were proposed. Among these those especially worth mentioning are algorithms by Scarf (1967) and Smale (1976) which find approximate fixed points. Considerable progress on this problem happened in the 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. The work that we present touches on many aspects of this problem from computational issues 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. We present the first "practical" algorithms for a very general class of markets settling long standing open questions. These algorithms are based on the machinery of linear complementarity problems, a generalization of linear programs. The worst case complexity is still exponential but the algorithms have qualities much like the Simplex algorithm for LPs. Simplex-type algorithms are known to work well in practice. These results also help bring out a clear dichotomy among equilibrium computation problems and these will be touched upon in the talk.
Speaker Profile:
Jugal Garg is currently a research fellow at the Max-Planck-Institute for Informatics, Germany. Prior to that, he was a postdoctoral fellow at Georgia Tech. 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 the design and analysis of algorithms, optimization and mathematical programming.
List of Talks


Faculty CSE IT
Forgot Password
    [+] Sitemap     Feedback