<p>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. </p>

<p>One of the texts that I know of that is most accessible to auction theorists with an economics background is Jason Hartline's "<a href="http://users.eecs.northwestern.edu/~hartline/amd.pdf">Approximation in Economic Design</a>". Chapter 1 in particular tries to make the case for approximation algorithms, if not specifically for the importance of computational complexity. </p>

CC BY-SA 3.0
2013-05-09T01:27:56.500Z
2013-05-09T01:27:56.500Z
Aaron Roth
<p>heres another angle based on some more search. a principle historical/emerging nexus/intersection between economics and computer science/complexity theory is computing <a href="http://en.wikipedia.org/wiki/Nash_equilibrium" rel="nofollow">Nash equilibria</a> which are central to various economics models, where Daskalakis (collaborating with Papadimitriou) is a leading figure.[1][2][5]</p>

<p>this overlap generally occurs through the field of <a href="http://en.wikipedia.org/wiki/Game_theory" rel="nofollow">game theory</a> 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."</p>

<p>[1] <a href="http://people.csail.mit.edu/costis/journal_ver10.pdf" rel="nofollow">The Complexity of Computing a Nash Equilibrium</a> Constantinos Daskalakis, Paul W. Goldberg, Christos H. Papadimitriou</p>

<p>[2] <a href="http://web.mit.edu/newsoffice/2009/game-theory.html" rel="nofollow">What computer science
can teach economics</a> MIT News</p>

<p>[3] <a href="http://robotics.stanford.edu/~shoham/www%20papers/CSGT-CACM080417.pdf" rel="nofollow">Computer
Science
and
Game
Theory</a> Shoham</p>

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

<p>[5] <a href="http://people.csail.mit.edu/costis/reconstruct.pdf" rel="nofollow">Nash Equilibria: Complexity,
Symmetries, and Approximation</a> Daskalakis</p>

CC BY-SA 3.0
2013-05-09T18:10:24.110Z
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
CC BY-SA 3.0
2013-05-09T18:05:36.197Z
2013-05-09T18:29:39.677Z
2013-05-09T18:29:39.677Z
vzn
<p>Beware that is not only econometrists but even mathematicians whose education still seems quite unfirm with the NPC=PET definition:</p>

<p>As of 2011 thru half of 2013 <a href="http://www.proofwiki.org/wiki/Definition:NP-Complete" rel="nofollow">http://www.proofwiki.org/wiki/Definition:NP-Complete</a> 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.</p>

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

CC BY-SA 3.0
2013-05-24T01:09:53.130Z
2013-05-24T01:09:53.130Z
DerComputer
<p>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 <em>auctions</em> 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. </p>

<p>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.</p>

<p>[1] <a href="http://www.sci.brooklyn.cuny.edu/~parsons/projects/mech-design/publications/bluffers-final.pdf" rel="nofollow">Auctions and bidding: A guide for computer
scientists</a> by Parsons</p>

<p>[2] <a href="http://web.mit.edu/newsoffice/2012/comp-sci-econ-0625.html" rel="nofollow">Computer science tackles 30-year-old economics problem</a> - 
MIT researchers generalize Nobel winner’s work on single-item auctions to auctions involving multiple items.</p>

<p>[3] <a href="http://arxiv.org/abs/1304.6116" rel="nofollow">Menu size complexity of auctions</a> Sergiu Hart, Noam Nisan</p>

CC BY-SA 3.0
2013-05-08T17:15:53.640Z
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
CC BY-SA 3.0
2013-05-08T17:42:57.130Z
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
CC BY-SA 3.0
2013-05-08T15:56:07.750Z
2013-05-08T15:56:07.750Z
vzn
<p>I see two separate directions to take your question. One is <strong>How has a computer science philosophy and computational thinking impacted the field of economics, and why should economists care about the computer science approach</strong>? This is a really cool but really broad question that I'll avoid attempting to address.</p>

<p>The second is more specific: <strong>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?</strong> 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).</p>

<p>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 <em>a priori</em> 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.</p>

<p>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.</p>

<p>Third, I think many economists to whom these issues <em>are</em> relevant <em>have</em> 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 <em>her</em> interests, she might be right; but there are others who do take notice.</p>

<p>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.</p>

CC BY-SA 3.0
2013-05-09T01:27:40.123Z
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
CC BY-SA 3.0
2013-05-09T00:21:23.940Z
2013-05-09T00:21:23.940Z
usul
<p><strong>When trying to convince economists of the relevance of complexity theory in print, is there a standard reference to cite?</strong> I am familiar with <a href="http://agtb.wordpress.com/2009/11/27/economists-and-complexity/" rel="noreferrer">Noam Nisan's blog post</a>, <a href="http://theory.stanford.edu/%7Etim/papers/et.pdf" rel="noreferrer">Tim Roughgarden's survey</a>, and chapter 11 of <a href="http://arxiv.org/pdf/1108.1791.pdf" rel="noreferrer">Scott Aaronson's essay</a>. 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? <strong>Is there a good historic overview of how economists have responded to pressure from computer scientists?</strong></p>
<p>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 <a href="http://egtheory.wordpress.com/2013/05/03/evolutionary-economics-and-game-theory/" rel="noreferrer">evolutionary economics</a> and <a href="http://en.wikipedia.org/wiki/Complexity_economics" rel="noreferrer">complexity (in the SFI sense) economics</a> 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.</p>
<hr />
<h3>Related questions</h3>
<ul>
<li><p><a href="https://cstheory.stackexchange.com/q/6387/1037">Algorithmic lens in the social sciences</a></p>
</li>
<li><p><a href="https://cstheory.stackexchange.com/q/7951/1037">Computational complexity in quantitative finance</a></p>
</li>
</ul>

CC BY-SA 3.0
2013-05-08T07:17:18.710Z
Two recent papers: "[A revealed preference approach to computational complexity in economics](http://users.cms.caltech.edu/~adamw/papers/revealedpref.pdf)", "[The Computational Complexity of Games and Markets: An Introduction for Economists](http://cupid.economics.uq.edu.au/mclennan/Papers/complexity_survey.pdf)"
Marzio De Biasi
CC BY-SA 3.0
2013-05-08T08:25:56.557Z
Try this, Markets are efficient if and only if P=NP;  http://arxiv.org/pdf/1002.2284.pdf
Mohammad Al-Turkistany
CC BY-SA 3.0
2013-05-08T10:16:38.320Z
@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
CC BY-SA 3.0
2013-05-08T15:43:08.107Z
one emerging area where there is a lot of overlap between CS & econ is _auctions_
vzn
CC BY-SA 3.0
2013-05-08T17:17:40.113Z
@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
CC BY-SA 3.0
2013-05-08T17:21:12.410Z
@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
CC BY-SA 3.0
2013-05-08T18:04:31.280Z
@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
CC BY-SA 3.0
2013-05-09T15:43:05.040Z
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
CC BY-SA 3.0
2013-05-09T17:24:35.453Z
@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](http://cstheory.stackexchange.com/q/7951/1037) and [CS results that made direct impact and altered existing theories/paradigms in the social sciences](http://cstheory.stackexchange.com/q/6387/1037). 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
CC BY-SA 3.0
2013-05-10T06:10:23.587Z
@Artem: note that Roughgarden's survey is published in the journal Economic Theory, which is an out-and-out Economics venue.
Rahul Savani
<cc.complexity-theory><reference-request><application-of-theory><ho.history-overview><ce.computational-finance>
Why economists should care about computational complexity
Artem Kaznatcheev
# Why economists should care about computational complexity

(Asked by: username_0 on 2013-05-08)

**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](http://agtb.wordpress.com/2009/11/27/economists-and-complexity/), [Tim Roughgarden's survey](http://theory.stanford.edu/%7Etim/papers/et.pdf), and chapter 11 of [Scott Aaronson's essay](http://arxiv.org/pdf/1108.1791.pdf). 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](http://egtheory.wordpress.com/2013/05/03/evolutionary-economics-and-game-theory/) and [complexity (in the SFI sense) economics](http://en.wikipedia.org/wiki/Complexity_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

* [Algorithmic lens in the social sciences](https://cstheory.stackexchange.com/q/6387/1037)
* [Computational complexity in quantitative finance](https://cstheory.stackexchange.com/q/7951/1037)

**Tags:** cc.complexity-theory, reference-request, application-of-theory, ho.history-overview, ce.computational-finance

> **Comments:**
> **username_1**: Two recent papers: "[A revealed preference approach to computational complexity in economics](http://users.cms.caltech.edu/~adamw/papers/revealedpref.pdf)", "[The Computational Complexity of Games and Markets: An Introduction for Economists](http://cupid.economics.uq.edu.au/mclennan/Papers/complexity_survey.pdf)"  
> **username_2**: Try this, Markets are efficient if and only if P=NP;  http://arxiv.org/pdf/1002.2284.pdf  
> **username_1**: @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)  
> **username_3**: one emerging area where there is a lot of overlap between CS & econ is _auctions_  
> **username_0**: @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.  
> **username_0**: @MohammadAl-Turkistany and username_3, 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.  
> **username_1**: @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  
> **username_3**: 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.  
> **username_0**: @username_3 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](http://cstheory.stackexchange.com/q/7951/1037) and [CS results that made direct impact and altered existing theories/paradigms in the social sciences](http://cstheory.stackexchange.com/q/6387/1037). Although I appreciate your enthusiasm, I prefer asking focused questions and appreciate focused answers like the ones given username_1, username_7, and username_5.  
> **username_4**: @Artem: note that Roughgarden's survey is published in the journal Economic Theory, which is an out-and-out Economics venue.  

---

## 5 answers

### Answer by username_7 on 2013-05-09. Score: 13 | Accepted answer

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.

> **Comments:**
> **username_0**: 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.  

---

### Answer by username_5 on 2013-05-09. Score: 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](http://users.eecs.northwestern.edu/~hartline/amd.pdf)". Chapter 1 in particular tries to make the case for approximation algorithms, if not specifically for the importance of computational complexity.


---

### Answer by username_3 on 2013-05-09. Score: -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](http://en.wikipedia.org/wiki/Nash_equilibrium) 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](http://en.wikipedia.org/wiki/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](http://people.csail.mit.edu/costis/journal_ver10.pdf) Constantinos Daskalakis, Paul W. Goldberg, Christos H. Papadimitriou

[2] [What computer science
can teach economics](http://web.mit.edu/newsoffice/2009/game-theory.html) MIT News

[3] [Computer
Science
and
Game
Theory](http://robotics.stanford.edu/~shoham/www%20papers/CSGT-CACM080417.pdf) Shoham

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

[5] [Nash Equilibria: Complexity,
Symmetries, and Approximation](http://people.csail.mit.edu/costis/reconstruct.pdf) Daskalakis

> **Comments:**
> **username_3**: 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.  

---

### Answer by username_6 on 2013-05-24. Score: -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.


---

### Answer by username_3 on 2013-05-08. Score: -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](http://www.sci.brooklyn.cuny.edu/~parsons/projects/mech-design/publications/bluffers-final.pdf) by Parsons

[2] [Computer science tackles 30-year-old economics problem](http://web.mit.edu/newsoffice/2012/comp-sci-econ-0625.html) -
MIT researchers generalize Nobel winner’s work on single-item auctions to auctions involving multiple items.

[3] [Menu size complexity of auctions](http://arxiv.org/abs/1304.6116) Sergiu Hart, Noam Nisan

> **Comments:**
> **username_0**: 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.  
> **username_3**: 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.  

---

