Making Economic Theory Tractable

 

 

Making Economic Theory Tractable

If your laptop can’t find it, neither can the market.

Summary

Our understanding of the world depends on our ability to predict it. When it comes to the economy, there is no shortage of predictive theories: supply will equal demand, prices will reach equilibrium values, trade will be balanced between nations, and players in an arbitrary game will play a Nash equilibrium, to mention a few examples. Such theories are crucial to our belief in the efficient and stable operation of the economy.

These predictive theories raise a fundamental question: what is the computational complexity of reaching these equilibia? The question is important for a simple reason: If computational processes (which can simulate the behavior of buyers, sellers, consumers, producers, and governments) cannot efficiently reach the predicted equilibrium, what makes us believe the market will? And if the market cannot, then of what use is the equilibrium as a predictive model? Thus, a grand challenge is to develop economic theories that are both predictive and tractable.

Rationale

The most fundamental incongruity between algorithmic thinking on the one hand and economics and game theory on the other is that the latter predicts outcomes and equilibrium behavior with little regard to the ways in which such a state will be reached — a consideration that is a computer scientist’s foremost concern. A fundamental challenge is to merge these two ways of thinking — to develop economic theories that are both predictive and tractable, in the sense that there are reasonably efficient processes by which these outcomes can be reached.

Already in recent years, computer scientists have focused their attention on fundamental questions related to algorithms for computing equilibria, including Nash and correlated equilibia in games, and price equilibria for markets.

For example, a central tenet is that prices are such that demand equals supply; that is, the economy should operate at equilibrium. It is not surprising therefore that perhaps the most celebrated theorem within general equilibrium theory, the Arrow-Debreu Theorem, establishes precisely the existence of such prices under a very general model of the economy. The First Welfare Theorem, which shows Pareto optimality of allocations obtained at equilibrium prices, provides important social justification for this theory. Although general equilibrium theory enjoys crown jewel status within mathematical economics, it suffers from a serious shortcoming. Other than a small number of beautiful results, it is essentially a nonalgorithmic theory. With the emergence of new markets on the Internet, which already form an important part of today’s economy and are projected to grow considerably in the future, and the availability of massive computational power for running these markets, the need for developing an algorithmic theory of markets and market equilibria is only growing. A good beginning has been made within the theoretical computer science community over the last 5 years in developing algorithms for computing various market equilibria. However, it is fair to say that we have only just scratched the surface of what should be a very rich theory.

When it comes to algorithms for computing Nash equilibria, we have also made important progress within the last 5 years, but here the progress is mostly negative. The results obtained give substantial new evidence that there is no efficient method for finding such equilibria, thereby raising the importance of finding alternative solution concepts. In this sense, the intractability results we know so far are most usefully seen as the opening move in an interesting game.

In summary, we believe that this matter of computational complexity is one of central importance and that the algorithmic point of view has much to contribute to the debate of economists about solution concepts. If an equilibrium concept is not efficiently computable, much of its credibility as a prediction of the behavior of rational agents is lost — as there is no clear reason why a group of agents cannot be simulated by a machine.

Efficient computability and predictive power are equally important modeling prerequisites for economic theories.

Contributors and Credits

Major portions of text taken from chapters by Christos Papdimitriou and Vijay Vazirani in the new algorithmic game theory book; tagline due to Kamal Jain; contributions from Shuchi Chawla, Jason Hartline, Anna Karlin, Claire Mathieu, and Tim Roughgarden.