Theory Matters Wiki

Summary | Rationale | Images | Credits | Powerpoint | Comments | All Nuggets

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, Jason, Anna, Claire, Tim

Image Ideas

a magnifying glass on a dollar bill. Outside the glass is a dollar, inside the glass is a 0,1 pattern that resembles the image of on the dollar. (or a circuit board that resembles the image on the dollar)

Comments

• to give feedback on this nugget, just add another bullet to this list.
• I think the summary would be better if it were more concise, got to the role of TCS sooner, and devoted a larger fraction of the text to this. - Salil
• Low-level suggestions: "country"->"national", "Game-theory"->"Game theory", "impossibly"->"something a bit less absolute (maybe unreasonably?)","their respective problems" - not sure that the reader will understand what this is referring to, "laws of computational tractability" - I wonder if this will be cryptic (maybe because too small a percentage of summary is devoted to TCS role), "play make" -> "make", "paradigm changing" -> "paradigm-changing", fix grammar in sentences about Nobel Laureate John Nash. - Salil
• Nice image idea! - Salil
• I concur with Salil's comments -- it would be better if the summary motivated TCS's role earlier, perhaps with some simple examples. Also, right now the phrase "computational lens" comes up in the last sentence without much explanation... It would be nice (though as we all know, hard to do concisely with words) if we could somehow point out that the computational lens has given us tools for attacking economic problems aside from "just" worrying about computational intractability. --Amit
• Indeed, the nugget feels long, although that is in part due to the overlap between the summary and the first para of the rationale. Is it intentional ? - Piotr
• Low level comment: I would put a new line before ".Unfortunately" in the summary, to emphasize the sentence that follows. - Piotr
• Minor points: the first paragraph copies the abstract, better to drop the repetition. The royal tributes to Nash sound un-academic and better be avoided. His equilibrium (based on the assumption of absolute absence of hidden coordination between participants) did not become any more realistic just because Nobel Memorial Prize sounds like Nobel Prize :-). I would also separate the issue of uninformed agents (informational or stochastic veil, well understood by economists) from the issue of computational intractability.
• Major point: I would refocus the Nugget somewhat from specific issues (like equilibriums) to more general ones, using specific points only as examples. The intractability is indeed a crucial issue ignored in economic literature. Its computational nature is not always apparent, but everybody knows that making best decisions in complex environment is a ridiculously unrealistic goal. Thus, classical game theory (which assumes perfectly rational behavior of all agents) has limited applicability. A focus on methods that do not always rely on such assumptions could change paradigms in economics and make it more relevant. (The economists are often puzzled why their logically convincing recommendations are ignored by politicians and, when not ignored, bring unexpected results.) Computer science acquired a great wealth of results exposing intractability and finding ways around it. -Leonid Levin.
• In the summary, I would omit the second sentence "They self-optimize subject to the laws of the system" since it is stated as fact here and later questioned. The para also flows much better without this sentence. - Rajmohan
• The sentence "If no computer can optimally solve the problem, how could anyone else?" is quite a strong assertion -- while this is what guides much of the work in this area, to outsiders it may seem like we are claiming humans can only do things that computers can do (of course, this is an age-old question....). - Rajmohan
• Is the last para of the summary (and the rationale) necessary? Reads a little strange- Rajmohan
• Minor suggestions: Last sentence of first para of rationale "Answers to these questions are". In the second last para, maybe "The Computer Science approach to addressing information-theoretic limitations ..." - Rajmohan
• Maybe Discovering or Uncovering or Revealing or Unveiling... Because "exposing" has a negative connotation. One exposes bad things (fraud, theft, vacuity, etc). - Bernard
• Note from designer Elaine Park on first design: Though the initial image suggestion is a great illustration of the thought, I was worried that a picture of cash might not do the bigness of the idea true justice. Most of the world's money exists as abstract numbers as it is, and I thought that stock charts might not only provide an indication of the broader impact of this idea, but given the state of things these days, maybe pull at a few heart strings too.
• Comments from organizers: Tagline does not add anything to title; perhaps a more effective one can be found in the form of a question. Text of summary is very good in terms of accessibility, but still needs a lot of work - shortening and emphasizing the role of TCS more prominently. Need to tell reader what the "computational lens" means.
• The tagline does not give any hint on what we plan to do and why it is important. Maybe "Goal: Study economic mechanisms through lens of efficient computation". - Sanjeev
• I think the tagline should be a question similar to the ones found on the Massive Data Sets and other. In this way it appears that there is something to solve. - Richard
• Uploaded revised design. - Salil
• Note from designer Elaine Park on second design: Here's the initial suggestion brought to life. I think it looks great. But let me know if the reference to the magazine is too overt – that'd just be a simple change to the headline.
• Would be improved with a reference to some concrete open questions. e.g. "What kind of equilibria do computationally limited agents arrive at?" ---Sanjeev
• Edited summary and rationale to reflect comments. Further edits to the rationale & a new punchline are forthcoming. Thank you all for your input! -Shuchi
• I have a preference for the last tagline Revealing the computational building blocks of economics. Actually I prefer the others, because they don't work. That's because computation and resources are de facto limited. So there is no other kind of economics and the tagline might as well say "How do economic systems work?" Or to be more concise "Economics," which makes no sense. I think we want to convey the idea of the lens. The point is not that economics operates in a bounded-resource world but that it is that very fact that will guide our investigations. (Resource limited world suggests peak oil theory and that kind of thing. Not sure that's what we want.) - bernard
• I see Bernard's point. The taglines make sense if one interprets "economic systems" to refer to standard (non-computational) economic theory as opposed to those in the real world (which are de facto computationally limited as Bernard says). I guess we want something more like "How should computational limitations affect economic theory?" or "Revising economic theory for a computationally limited world." - Salil
• I edited the summary. it is a mistake to introduce the term algorithmic game theory to the folks who will be reading this. i propose we use a tagline that is a combination of salil's second suggestion and the last sentence of the summary. i think it is important not to sell ourselves short by forgetting the informational aspects of the work we do. --Jason
• Removed old alternate taglines: "How do economic systems behave in a computationally limited world?", "How do economic systems behave in a resource-limited world?", "Revealing the computational building blocks of economics" - Salil
• Uploaded ppt with final tagline. - Salil