18

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

Community
  • 1
Artem Kaznatcheev
  • 10,251
  • 12
  • 74
  • 174
  • 7
    Two recent papers: "A revealed preference approach to computational complexity in economics", "The Computational Complexity of Games and Markets: An Introduction for Economists" – Marzio De Biasi May 08 '13 at 07:17
  • 2
    Try this, Markets are efficient if and only if P=NP; http://arxiv.org/pdf/1002.2284.pdf – Mohammad Al-Turkistany May 08 '13 at 08:25
  • 2
    @MohammadAl-Turkistany: I gave a quick look at it and the decision problem "Does there exist a strategy that statistically significantly (after accounting for possible data mining) makes money (after accounting for transactions costs)?" is poorly defined (in particular the definition of "strategy" and "statistically significant") and the proof is far from being "mathematical" (a standard reduction from an NP-complete problem) – Marzio De Biasi May 08 '13 at 10:16
  • one emerging area where there is a lot of overlap between CS & econ is auctions – vzn May 08 '13 at 15:43
  • @MarzioDeBiasi your second link is exactly the sort of thing I am looking for, sections 2, 3, and 4 seem spot on! Would you want to expand your comment into an answer with some comments on that paper? Otherwise I can do that once I finish reading through it more carefully. – Artem Kaznatcheev May 08 '13 at 17:17
  • @MohammadAl-Turkistany and vzn, please read the question carefully. I am not asking about specific results or intersections of TCS and Econ, there are other questions that do that. I am asking about how to justify and motivate TCS to economists in a language and style they are more comfortable with (instead of algorithmic game theory or algorithmic economics results presented to other other scientists). Thus, a technical result cannot answer this question, only a survey or historic overview can. Finally, the EMH and P = NP result has been discussed elsewhere on this site and found lacking. – Artem Kaznatcheev May 08 '13 at 17:21
  • @ArtemKaznatcheev: I found it searching on internet and I only gave a quick look at it for curiosity. So ... if you find it useful ... you can surely explain why better than me :-D :-D – Marzio De Biasi May 08 '13 at 18:04
  • possibly the best that is available might be to compile a list of papers written by complexity theorists on economic topics/problems. it would be an interesting list and closely supporting your question, but your comments indicate you are not really open to such an approach to an answer. – vzn May 09 '13 at 15:43
  • 2
    @vzn that would be too long of a list, since AGT is now a standard part of computer science. For more restricted lists there are already questions (that I mentioned in the body of this post) like for ones about quantitative finance and CS results that made direct impact and altered existing theories/paradigms in the social sciences. Although I appreciate your enthusiasm, I prefer asking focused questions and appreciate focused answers like the ones given Marzio De Biasi, usul, and Aaron Roth. – Artem Kaznatcheev May 09 '13 at 17:24
  • @Artem: note that Roughgarden's survey is published in the journal Economic Theory, which is an out-and-out Economics venue. – Rahul Savani May 10 '13 at 06:10

5 Answers5

13

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.

usul
  • 7,615
  • 1
  • 26
  • 45
  • 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. – Artem Kaznatcheev May 09 '13 at 01:27
8

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.

Aaron Roth
  • 9,870
  • 1
  • 43
  • 68
-1

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

vzn
  • 11,014
  • 2
  • 31
  • 64
  • 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. – vzn May 09 '13 at 18:10
-2

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.

DerComputer
  • 1
-4

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

vzn
  • 11,014
  • 2
  • 31
  • 64
  • 3
    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. – Artem Kaznatcheev May 08 '13 at 17:15
  • 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. – vzn May 08 '13 at 17:42