The Computation of Economic equilibria

  • Nikhil Devanur | Toyota Technological Institute at Chicago

When and how can computers ?nd market equilibrium? There are many reasons why this question is interesting, stemming from the fact that computers are better at such a task than people. Natural cases of interest are when a computer can be substituted for a human, such as when using models to evaluate economic policies, or in markets specially designed to take advantage of computational resources. Or an algorithm to compute equilibrium could be considered as an indication that actual markets do reach equilibrium.

The question is studied in two settings, a centralized, full information and static setting, and a distributed, limited information and dynamic setting. In the former setting, most of the algorithms known were for simple families of “utility functions”, and they essentially solved a convex program. These have their limitations, since the set of equilibria could in general be disconnected. We show how to ?nd exact equilibria for a very general class of utility functions, when the number of goods is bounded. We use tools from computational algebraic geometry to overcome the di?culties mentioned above.

In the latter setting, we show that the “tatonnement process”, a simple and distributed price-updating rule that has been widely studied by economists, converges fast to equilibrium for many markets. A new feature of this analysis is that it works even for dynamic markets, all earlier analysis considered static markets. The analysis involves showing that the tatonnement process is equivalent to running the gradient descent algorithm, a surprisingly simple observation that is of interest in itself. This approach has many applications, one of which is bid-optimization strategies in sponsored search auctions.

The first part of the talk is based on joint work with Ravi Kannan.

Speaker Details

Dr. Nikhil Devanur recieved his B.Tech from the Computer Science Department at IIT Bombay, and his PhD in Algorithms, Combinatorics and Optimization from the College of Computing at Georgia Tech.Nikhil’s research interests lie in the intersection of computer science, economics and game theory, such as computing market equilibrium, designing auctions and computational theories of decision making. He is also interested in fundamental problems in combinatorial optimization, such as matching, graph partitioning and network design.

Watch Next