**The Computational Lens on Economics**

*Revising economic theory for a computationally and informationally limited world.*

**Summary**

How do computers, people, organizations, companies, countries, interact in systems together? They self-optimize as best as they can subject to the laws of the system. Computers follow network protocols, people follow moral, state, and national laws, organizations and companies follow corporate law, and countries follow international laws. Of course, within each of these systems there is still much room for individuals to make their own choices. Economics studies the performance of these systems. Game theory provides economists with the mathematical tools to rigorously analyze and understand how economics governs interaction of rational but selfish participants.

Unfortunately, classical economic and game-theoretic models make an unreasonably strong assumption: participants *can* follow strategies that are rationally optimal. They assume that participants know the precise informational structure of the economic system and are able to act in a manner that is optimally in their best interest. This assumption overlooks key issues that severely limit the applicability of classical economic theory. What if the participants do not have the full information necessary to solve the optimization problems they face? What if these optimization problems are computationally intractable? How do they and how should they act in such situations? Computer Science theory tells us that computationally intractable problems do arise in the context of economic systems. Fortunately it also provides tools for getting around the issues of tractability and lack of information: approximation! The computational lens provides the theory for design and analysis of economic systems in a computationally and informationally limited world.

**Rationale**

Since the inception of computer science as a field of study, techniques for understanding optimization in settings with computational or informational restrictions have been developed to directly address challenges like the ones outlined above. Computer science has precise quantifications of computational power, and therefore, of computational limitations. Actions of participants in an economic system are in practice subject to such computational and informational constraints. For instance, central to economic and game theoretic analysis is the notion that participants play in “equilibrium”. What if participants cannot compute their equilibrium strategies? Computer Science provides definitions and techniques for determining precisely when participants can compute their equilibrium actions and when they cannot. This gives a paradigm-changing view point on the classic work of Nobel Laureate John Nash that showed that equilibrium always exist — not so when there are computational limitations! What good is an equilibrium that exists if no one, not even a computer, can find it? Notions of rational play must address the case where participants can only make “approximately good” actions, and not their optimal ones. Several issues arise: what systems admit computationally efficient equilibria? What are the properties of approximate equilibria?

What about the laws of the system themselves? Suppose that we wish to design a system so that when participants self-optimize the system is optimal on the whole. What rules should we impose on the participants? This question forms the basis of a sub-area of game theory known as mechanism design. Consider the paradigmatic mechanism design problem faced by the FCC when selling radio frequency spectrum rights to cell phone companies. The companies have diverse preferences over combinations of which rights they get, both across frequencies and across geographic regions. The FCC’s aim is to assign the spectrum to the companies that can best use them; however, this optimization problem is computationally intractable. The problem is compounded by the fact that the cell phone companies’ preferences are private to the company. Thus, the FCC must design a protocol (a.k.a., mechanism) for eliciting preferences and assigning rights. Mechanism design theory, prior to recent work in computer science on the subject, failed to account for the fact that running the auction and computing its outcome must be computationally tractable in order to be practically relevant. A joint economic and computer science theory of mechanism design is developing to give crisp answers to these and related questions. This “theory of approximation mechanisms” gives the principles for designing and analyzing mechanisms that are approximately optimal.

In many mechanism design settings no single mechanism is optimal. Indeed, the prevailing framework for mechanism design in economics is to assume that the designer had some knowledge of the preferences of the other participants in the system. This designer then would like to design the mechanism that is optimal given this knowledge. The result, of course, is a design problem only half solved. Where shall the designer acquire this information? Furthermore, it may not be possible for the designer to give a different mechanism for each different setting. What if the designer must deploy a single mechanism to be used everywhere? Indeed most real world mechanisms are simple and standardized. If this is a design goal, how should a designer design a mechanism that is good in every setting? The computer science approach to information theoretic limitations (i.e., lack of information on the part of the designer) is to approximate. Instead of designing many mechanisms, each optimal for its own specific setting, we design one mechanism that simultaneously approximates the performance of each of the individual mechanisms in their respective settings. This approach of approximation gives answers where there were none in classical economic theory.

Economic systems function because of selfish optimization. When optimization is intractable because of computational or informational constraints, the computational lens can be applied.

**Contributors and Credits**

Shuchi Chawla, Jason Hartline, Anna Karlin, Claire Mathieu, Tim Roughgarden

## Leave a Reply