When trying to convince economists of the relevance of complexity theory in print, is there a standard reference to cite? I am familiar with Noam Nisan's blog post, Tim Roughgarden's survey, and chapter 11 of Scott Aaronson's essay. These posts are accessible for computer scientists, but do not use the language of economists and are not published in venues typically read by them. Are there good arguments for the importance of the complexity of equilibiria, etc. targeted at economists? Is there a good historic overview of how economists have responded to pressure from computer scientists?

It could be argued that neoclassical economics is simply closed off and hence such papers can't exist, but there are slightly heterodox fields such as evolutionary economics and complexity (in the SFI sense) economics that justify themselves in language familiar to economists. These fields also make similar critiques as the computational complexity approach (such as moving away from assumptions of equilibria), but don't justify them as rigorously as CS does.

Related questions


5 Answers 5


I see two separate directions to take your question. One is How has a computer science philosophy and computational thinking impacted the field of economics, and why should economists care about the computer science approach? This is a really cool but really broad question that I'll avoid attempting to address.

The second is more specific: Now that computer scientists know that many problems in game theory are hard, how do we convince economists that these are important issues with or objections to their work? This may not be what you had in mind, but it seems to be an interpretation of what you wrote, so I want to address it because I think it's a bit problematic and I think there are reasons not to write an essay arguing this point (which might explain any lack of answers).

First, micro-economists are often theorists and they may be more interested in understanding the problem in their model than in ours. There is no a priori reason one approach is better than the other. As an analogy, many theoretical computer scientists are happy to design algorithms that work over real numbers even though this may require undecidable operations. Similarly, to an economist, complexity may be a detail that clouds one's understanding of what's important in their model rather than a key consideration. This seems more a matter of preference or philosophy than right or wrong.

Second, it's not clear that computer science is yet in a position to argue convincingly that our models fit the real world better than theirs, until we have experimental data to back this up. (After all, it might be for example that markets often find equilibria quickly in practice, so hardness of computing is irrelevant to real-world applications.) Without data, the disagreement is philosophical and it's hard to claim there is a right or wrong side. I don't know that we have enough data yet to make any specific claims.

Third, I think many economists to whom these issues are relevant have been taking notice. In areas like matching, for example (subject of last year's Nobel!), a computational complexity and algorithmic approach is important as they attempt to implement solutions at large scale. So if an economist claims that complexity isn't relevant to her interests, she might be right; but there are others who do take notice.

So in sum, while it seems like a worthwhile goal to help make economists aware of the results regarding complexity in economics (especially as some do take interest), I am not sure that we are in a position to argue that they should take much notice or change their approach; and I think a strong scientific argument would require more data rather than just philosophy.

  • $\begingroup$ Awesome answer! I like your second interpretation, I think it is in line with what I had in mind. I also like your first interpretation, it is a shame that you decided not to address it. I will keep the question open for longer, because I think there are such surveys, there is at least one good one provided in the comments which is my bedtime reading tonight. $\endgroup$ May 9, 2013 at 1:27

Main stream game theorists are, I think, becoming much more open to contemporary work in the computer science community, so it may be less necessary to "make the case'' for algorithmic game theory than it has been in the past.

One of the texts that I know of that is most accessible to auction theorists with an economics background is Jason Hartline's "Approximation in Economic Design". Chapter 1 in particular tries to make the case for approximation algorithms, if not specifically for the importance of computational complexity.


heres another angle based on some more search. a principle historical/emerging nexus/intersection between economics and computer science/complexity theory is computing Nash equilibria which are central to various economics models, where Daskalakis (collaborating with Papadimitriou) is a leading figure.[1][2][5]

this overlap generally occurs through the field of game theory where [3] is a survey published in ACM and which serves as another key bridge between the fields. also Shoham cites [4] as a survey focusing on Nash equilibria and "Geared mostly towards economists, it includes ample background material on relevant concepts from complexity theory."

[1] The Complexity of Computing a Nash Equilibrium Constantinos Daskalakis, Paul W. Goldberg, Christos H. Papadimitriou

[2] What computer science can teach economics MIT News

[3] Computer Science and Game Theory Shoham

[4] T. Roughgarden. Computing equilibria: A computational complexity perspective. Economic Theory, 2008

[5] Nash Equilibria: Complexity, Symmetries, and Approximation Daskalakis

  • $\begingroup$ oops, 2nd look, the Roughgarden ref is the same cited by AK except the published journal version. but it shows/underlines the interface is mainly through Nash equilibria not pointed out in the question. $\endgroup$
    – vzn
    May 9, 2013 at 18:10

Beware that is not only econometrists but even mathematicians whose education still seems quite unfirm with the NPC=PET definition:

As of 2011 thru half of 2013 http://www.proofwiki.org/wiki/Definition:NP-Complete still confuses the meaning of NP-complete problem with that of a NP-hard problem which may possibly be in Co-NP or even beyond and by no nondeterminism with constant steprate polynomially bounded.

Economists can likely best be motivated by being pointed to the free markets' NP-completeness proof by P Maymin in http://arxiv.org/pdf/1002.2284‎ and be queried about their wisdoms for engineering social-evolutionary-informatory algorithms.


this is clearly a very emerging area so surveys and established literature would be difficult to come by. also complexity theory may be a little more abstract for this. however a compelling/natural area on the rise/intersection between CS/econ: try recent research into auctions which is especially significant given google Adsense advertising largely funding the rise of the company over the last decade and also their singular auction-based IPO. also note the large-scale economy price fluctuations and buyer/seller dynamics can be modelled somewhat as an auction-like system.

another somewhat similar area where some very advanced/substantial CS is applied is high-speed trading, a complex/advancing science but unfortunately it is not openly published research due to its heavy secrecy.

[1] Auctions and bidding: A guide for computer scientists by Parsons

[2] Computer science tackles 30-year-old economics problem - MIT researchers generalize Nobel winner’s work on single-item auctions to auctions involving multiple items.

[3] Menu size complexity of auctions Sergiu Hart, Noam Nisan

  • 3
    $\begingroup$ This is not an answer to the question. I did not ask what are intersections of CS/Econ, I am already aware of these and there are other questions (in the related questions section) that already deal with this. My question is not about complexity results but about how to explain computational complexity to economists. $\endgroup$ May 8, 2013 at 17:15
  • $\begingroup$ whatever! good luck! its an answer to "why economists should care about computational complexity" ... maybe the lack of strong refs is an indicator that maybe they shouldnt! your questions are sometimes far too narrow to have the hairsplitting answer demanded. $\endgroup$
    – vzn
    May 8, 2013 at 17:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.