<p>This example is from social choice theory, and elections in particular. We know that <a href="http://en.wikipedia.org/wiki/Arrow%27s_impossibility_theorem">Arrow's theorem</a> (and the <a href="http://en.wikipedia.org/wiki/Gibbard%E2%80%93Satterthwaite_theorem">Gibbard-Satterthwaite theorem</a> in general) rule out the possibility of elections that are fair, non-manipulatable and without other bizarre consequences. But a seminal paper by <a href="http://www.cs.huji.ac.il/~arielpro/mfai_papers/BTT89.pdf">Bartholdi, Tovey and Trick</a> showed that finding the desired 'hack' to break a voting scheme was NP-hard, and there's been a large body of work by many researchers on the complexity of problems in the realm of election design. There's a nice survey by <a href="http://cacm.acm.org/magazines/2010/11/100640-using-complexity-to-protect-elections/fulltext">Faliszewski, Hemaspaandra, and Hemaspaandra</a> on this topic.  </p>

CC BY-SA 3.0
2011-05-05T04:51:13.957Z
thanks! A bit more about the current state of social choice  is in this question: http://cstheory.stackexchange.com/questions/2711/social-choice-arrows-theorem-and-open-problems
Artem Kaznatcheev
CC BY-SA 3.0
2011-05-05T04:53:11.537Z
Ah thanks. I had forgotten my own answer from there :)
Suresh Venkat
CC BY-SA 3.0
2011-05-04T06:42:41.130Z
2011-05-04T06:42:41.130Z
Suresh Venkat
<p>Today's cognitive psychology is really based on the "brain as computer" viewpoint.  (Although, this may be considered as part of "neuroscience" mentioned in the question.)</p>

CC BY-SA 3.0
2012-01-16T07:26:44.353Z
It is a really fascinating area. I have been hoping to read more about this on your blog for sometime, and now that you have turned it into a groups blog even more so. :)
Kaveh
CC BY-SA 3.0
2012-01-14T06:17:36.860Z
2012-01-14T06:17:36.860Z
Noam
<p><a href="http://en.wikipedia.org/wiki/Noam_Chomsky_bibliography">Chomsky</a>? </p>

<p>For more modern examples <a href="http://computationallegalstudies.com/">Computational Legal Studies Blog</a> has some great work. They predicted the nomination of U.S. Supreme Court Justice Sotmayor by <a href="http://computationallegalstudies.com/2009/05/04/judge-sonia-sotomayor-justice-sotomayor/">using graph theory</a>.</p>

CC BY-SA 3.0
2011-05-06T21:22:14.450Z
2011-05-06T21:22:14.450Z
Chad Brewbaker
<p>Some additional references:</p>

<p>In Macgill S M, 1985, "Structural analysis of social data: a guide to Ho's Galois lattice approach and a partial respecification of Q-analysis" Environment and Planning A 17(8) 1089 – 1109.</p>

<p>MacGill highlights how those in the social sciences who might benefit from using Q-analysis are (usually) least well placed to understand the maths and hence the potential of such tools in the humanities. Which must be the case even with increased computerization - algorithmic formulations. (Maths is a fascinating mist to this nurse.) </p>

<p>www.envplan.com/abstract.cgi?id=a171089</p>

<p>A great many issues of ERCIM news have considered the social applications of maths - inc. algorithmic:</p>

<p><a href="http://ercim-news.ercim.eu/back-issues-online" rel="nofollow">http://ercim-news.ercim.eu/back-issues-online</a></p>

<p>Another possible avenue to pursue is visualization in the social sciences. There was a major initiative in England in the 1990s:</p>

<p>www.agocg.ac.uk/train/review/toc.htm</p>

<p>The combination of the semantic web, conceptual spaces Gärdenfors (2000) may provide new, hybrid avenues:</p>

<p>Gärdenfors, P. (2000). Conceptual Spaces: The Geometry of Thought, Cambridge.</p>

<p>Conference May - 'Conceptual Spaces at Work'</p>

<p>www.fil.lu.se/conferences/conference.asp?id=46&amp;lang=se</p>

<p>I wish I could get to grips with these subjects - post-grad studies possibly. My spare time efforts include plans to attend the above conference and writing about a specific form of big picture (conceptual framework) Hodges model here:
<a href="http://hodges-model.blogspot.co.uk/" rel="nofollow">http://hodges-model.blogspot.co.uk/</a></p>

CC BY-SA 3.0
2012-04-08T21:45:00.637Z
2012-04-08T21:45:00.637Z
Peter Jones
<p><a href="https://en.wikipedia.org/wiki/Fair_division" rel="nofollow">cake cutting algorithms</a> which are important for fair division. I am sure they play a large part in social science.</p>

CC BY-SA 3.0
2012-04-09T21:32:00.943Z
can you cite a reference where cake cutting algorithms were important to social scientists? or somehow changes some theory in social science?
Artem Kaznatcheev
CC BY-SA 3.0
2012-04-10T03:57:38.380Z
Cake cutting algorithm deals with fair division of resources among n parties which is a long standing problem in social science. Wiki link which I gave cites a lot of references about how it pertains to social science. In particular I like this http://3quarksdaily.blogs.com/3quarksdaily/2005/04/3qd_monday_musi.html
Sai Venkat
CC BY-SA 3.0
2012-04-18T04:01:27.513Z
I think a better reference is the paper "Cake cutting really is not a piece of cake" by Edmonds and Pruhs.
Sai Venkat
CC BY-SA 3.0
2012-04-09T05:56:47.697Z
2012-04-09T05:56:47.697Z
Sai Venkat
<p>re applications of complexity theory in social science-- scott aaronson has a daring &amp; amusing-at-times essay tying complexity theory to deep century-old questions in philosophy that I ran across recently reading his blog.</p>

<p>Why Philosophers Should Care About Computational Complexity
<a href="http://arxiv.org/abs/1108.1791" rel="nofollow">http://arxiv.org/abs/1108.1791</a></p>

<p><a href="http://www.scottaaronson.com/blog/" rel="nofollow">http://www.scottaaronson.com/blog/</a></p>

<p><hr>
another interesting area of the application of algorithmic theory to social sciences happens in economics such as studying markets or other "complex systems". the idea is that the market is composed of separate actors or "agents" that each attempt to develop algorithms to make money. a darwinian process of selection ensues. similar to genetic algorithms. (and probably now actually quite close to reality of HST, high speed trading, where there are estimates that up to 70% of market trading is due to program trading.) a leading investigator in this area is j doyne farmer</p>

<p><a href="http://tuvalu.santafe.edu/~jdf/SFI%20Template/About%20Me.html" rel="nofollow">http://tuvalu.santafe.edu/~jdf/SFI%20Template/About%20Me.html</a></p>

<p><hr>
I see you mention biology on your course page. an excellent application of complexity and algorithmic theory and one under intense development is in the cutting edge problem of determining protein folding configurations. for example an early paper proved that a formalized version of the protein folding problem is NP complete.</p>

<p><a href="http://en.wikipedia.org/wiki/Protein_folding" rel="nofollow">http://en.wikipedia.org/wiki/Protein_folding</a></p>

<p>protein folding problem is NP complete by berger/leighton
<a href="http://www.brown.edu/Research/Istrail_Lab/papers/1998/p30-berger.pdf" rel="nofollow">http://www.brown.edu/Research/Istrail_Lab/papers/1998/p30-berger.pdf</a></p>

CC BY-SA 3.0
2012-01-13T16:52:25.630Z
Thank you for mentioning Scott's article, but the other two answers  you give (AGT/E and Biology) I specifically exclude in the question.
Artem Kaznatcheev
CC BY-SA 3.0
2012-01-13T17:22:58.337Z
do you think all computational approaches to finance are subsumed in AGT? AGT/E==algorithm game theory + economics? not sure I would agree with that or that Farmers work is in that category. you excluded AGT but did not seem to explicitly exclude Economics.
vzn
CC BY-SA 3.0
2012-01-13T16:34:14.987Z
2012-01-13T16:46:00.123Z
2012-01-13T16:46:00.123Z
vzn
<p><a href="http://www.cs.cornell.edu/home/kleinber/networks-book/">Networks, Crowds, and Markets: Reasoning About a Highly Connected World</a>, by Easley and Kleinberg probably should be mentioned here. It is rather elementary, but gives a wide selection of social sciences topics that have been considered from a CS point of view and provides a lot of references. Someone with more experience in the field can perhaps tell us how close the book is to the current state of the art in the field?</p>

<p>As a more particular answer, with the proliferation of various social networking sites, computer science has become quite relevant in analysing the huge social network data sets from such sites.</p>

CC BY-SA 3.0
2011-05-05T04:48:32.790Z
thanks! That looks like a fun book, do you know of any similar books or surveys that are at a graduate or research level? A skim on Easley and Kleinberg suggests that it is targeted as an intro for undergrads.
Artem Kaznatcheev
CC BY-SA 3.0
2011-05-05T06:36:23.030Z
Unfortunately, no, I don't. In fact, I'd love to see such a book or survey myself.
Janne H. Korhonen
CC BY-SA 3.0
2013-09-24T03:06:05.323Z
Not sure if anyone still follows the topic, but the other excellent books include Social and Economic Network by Matthew O. Jackson and Network: An Introduction by Mark Newman.  

[1]: http://www.amazon.com/Social-Economic-Networks-Matthew-Jackson/dp/0691148201/ref=tmm_pap_title_0#  
[2]: http://www.amazon.com/Networks-An-Introduction-Mark-Newman/dp/0199206651
Thang Dinh
CC BY-SA 3.0
2011-05-04T11:12:39.000Z
2011-05-04T18:49:38.820Z
2011-05-04T18:49:38.820Z
Janne H. Korhonen
<p>Looking at questions through the <a href="http://egtheory.wordpress.com/2013/09/15/algorithmic-lens/" rel="nofollow">algorithmic lens</a> (i.e. from an algorithmic or complexity point of view) has become useful in disciplines outside of the 'standard domain' of computer science. In particular CS has made an impact on biology through computational biology, on physics through quantum information processing, and AI and complexity theory seem to regularly interact with neuroscience. The natural sciences seem relatively comfortable with TCS.</p>

<p>Thus, my question is in regard to the impact of TCS on the <a href="http://en.wikipedia.org/wiki/Social_sciences" rel="nofollow">social sciences</a>.</p>

<blockquote>
  <p>What novel and important insights into the social sciences has TCS provided?</p>
</blockquote>

<p>I am vaguely aware of the impact of algorithmic thinking on economics (through game theory). In fact algorithmic game theory is now a part of the 'standard domain' of TCS, so lets exclude AGT answers unless they specifically altered existing theories in the social sciences. </p>

<p>Another example I recall is from linguistics in the learnability vs. innateness of grammar (i.e. <a href="http://en.wikipedia.org/wiki/Poverty_of_stimulus" rel="nofollow">poverty of the stimulus</a>) debate. Gold's theorem about the unlearnability of context free grammars provided a strong argument for innate-ness and helped convince some skeptics (I am not sure if this is still valid, since SCFG seem to be learnable). I am more interested in examples of this type, where TCS thinking helped change or shape existing theories in the social sciences.</p>

<p>References to books/surveys are appreciated.</p>

CC BY-SA 3.0
2011-05-04T06:35:32.780Z
CW ? I'm not sure ... - it's a great question.
Suresh Venkat
CC BY-SA 3.0
2011-05-04T21:22:44.880Z
Isn't the term "social sciences" a misnomer?
Tegiri Nenashi
<reference-request><soft-question><big-picture><social-sciences><algorithmic-lens>
Algorithmic lens in the social sciences
Artem Kaznatcheev
# Algorithmic lens in the social sciences

(Asked by: username_0 on 2011-05-04)

Looking at questions through the [algorithmic lens](http://egtheory.wordpress.com/2013/09/15/algorithmic-lens/) (i.e. from an algorithmic or complexity point of view) has become useful in disciplines outside of the 'standard domain' of computer science. In particular CS has made an impact on biology through computational biology, on physics through quantum information processing, and AI and complexity theory seem to regularly interact with neuroscience. The natural sciences seem relatively comfortable with TCS.

Thus, my question is in regard to the impact of TCS on the [social sciences](http://en.wikipedia.org/wiki/Social_sciences).

> What novel and important insights into the social sciences has TCS provided?

I am vaguely aware of the impact of algorithmic thinking on economics (through game theory). In fact algorithmic game theory is now a part of the 'standard domain' of TCS, so lets exclude AGT answers unless they specifically altered existing theories in the social sciences.

Another example I recall is from linguistics in the learnability vs. innateness of grammar (i.e. [poverty of the stimulus](http://en.wikipedia.org/wiki/Poverty_of_stimulus)) debate. Gold's theorem about the unlearnability of context free grammars provided a strong argument for innate-ness and helped convince some skeptics (I am not sure if this is still valid, since SCFG seem to be learnable). I am more interested in examples of this type, where TCS thinking helped change or shape existing theories in the social sciences.

References to books/surveys are appreciated.

**Tags:** reference-request, soft-question, big-picture, social-sciences, algorithmic-lens

> **Comments:**
> **username_1**: CW ? I'm not sure ... - it's a great question.  
> **username_2**: Isn't the term "social sciences" a misnomer?  

---

## 7 answers

### Answer by username_9 on 2011-05-04. Score: 16 | Accepted answer

[Networks, Crowds, and Markets: Reasoning About a Highly Connected World](http://www.cs.cornell.edu/home/kleinber/networks-book/), by Easley and Kleinberg probably should be mentioned here. It is rather elementary, but gives a wide selection of social sciences topics that have been considered from a CS point of view and provides a lot of references. Someone with more experience in the field can perhaps tell us how close the book is to the current state of the art in the field?

As a more particular answer, with the proliferation of various social networking sites, computer science has become quite relevant in analysing the huge social network data sets from such sites.

> **Comments:**
> **username_0**: thanks! That looks like a fun book, do you know of any similar books or surveys that are at a graduate or research level? A skim on Easley and Kleinberg suggests that it is targeted as an intro for undergrads.  
> **username_9**: Unfortunately, no, I don't. In fact, I'd love to see such a book or survey myself.  
> **username_10**: Not sure if anyone still follows the topic, but the other excellent books include Social and Economic Network by Matthew O. Jackson and Network: An Introduction by Mark Newman.    [1]: http://www.amazon.com/Social-Economic-Networks-Matthew-Jackson/dp/0691148201/ref=tmm_pap_title_0#   [2]: http://www.amazon.com/Networks-An-Introduction-Mark-Newman/dp/0199206651  

---

### Answer by username_1 on 2011-05-04. Score: 18

This example is from social choice theory, and elections in particular. We know that [Arrow's theorem](http://en.wikipedia.org/wiki/Arrow%27s_impossibility_theorem) (and the [Gibbard-Satterthwaite theorem](http://en.wikipedia.org/wiki/Gibbard%E2%80%93Satterthwaite_theorem) in general) rule out the possibility of elections that are fair, non-manipulatable and without other bizarre consequences. But a seminal paper by [Bartholdi, Tovey and Trick](http://www.cs.huji.ac.il/~arielpro/mfai_papers/BTT89.pdf) showed that finding the desired 'hack' to break a voting scheme was NP-hard, and there's been a large body of work by many researchers on the complexity of problems in the realm of election design. There's a nice survey by [Faliszewski, Hemaspaandra, and Hemaspaandra](http://cacm.acm.org/magazines/2010/11/100640-using-complexity-to-protect-elections/fulltext) on this topic.

> **Comments:**
> **username_0**: thanks! A bit more about the current state of social choice  is in this question: http://cstheory.stackexchange.com/questions/2711/social-choice-arrows-theorem-and-open-problems  
> **username_1**: Ah thanks. I had forgotten my own answer from there :)  

---

### Answer by username_3 on 2012-01-14. Score: 5

Today's cognitive psychology is really based on the "brain as computer" viewpoint. (Although, this may be considered as part of "neuroscience" mentioned in the question.)

> **Comments:**
> **username_4**: It is a really fascinating area. I have been hoping to read more about this on your blog for sometime, and now that you have turned it into a groups blog even more so. :)  

---

### Answer by username_5 on 2011-05-06. Score: 5

[Chomsky](http://en.wikipedia.org/wiki/username_3_Chomsky_bibliography)?

For more modern examples [Computational Legal Studies Blog](http://computationallegalstudies.com/) has some great work. They predicted the nomination of U.S. Supreme Court Justice Sotmayor by [using graph theory](http://computationallegalstudies.com/2009/05/04/judge-sonia-sotomayor-justice-sotomayor/).


---

### Answer by username_6 on 2012-04-08. Score: 1

Some additional references:

In Macgill S M, 1985, "Structural analysis of social data: a guide to Ho's Galois lattice approach and a partial respecification of Q-analysis" Environment and Planning A 17(8) 1089 – 1109.

MacGill highlights how those in the social sciences who might benefit from using Q-analysis are (usually) least well placed to understand the maths and hence the potential of such tools in the humanities. Which must be the case even with increased computerization - algorithmic formulations. (Maths is a fascinating mist to this nurse.)

www.envplan.com/abstract.cgi?id=a171089

A great many issues of ERCIM news have considered the social applications of maths - inc. algorithmic:

<http://ercim-news.ercim.eu/back-issues-online>

Another possible avenue to pursue is visualization in the social sciences. There was a major initiative in England in the 1990s:

www.agocg.ac.uk/train/review/toc.htm

The combination of the semantic web, conceptual spaces Gärdenfors (2000) may provide new, hybrid avenues:

Gärdenfors, P. (2000). Conceptual Spaces: The Geometry of Thought, Cambridge.

Conference May - 'Conceptual Spaces at Work'

www.fil.lu.se/conferences/conference.asp?id=46⟨=se

I wish I could get to grips with these subjects - post-grad studies possibly. My spare time efforts include plans to attend the above conference and writing about a specific form of big picture (conceptual framework) Hodges model here:
<http://hodges-model.blogspot.co.uk/>


---

### Answer by username_7 on 2012-04-09. Score: 0

[cake cutting algorithms](https://en.wikipedia.org/wiki/Fair_division) which are important for fair division. I am sure they play a large part in social science.

> **Comments:**
> **username_0**: can you cite a reference where cake cutting algorithms were important to social scientists? or somehow changes some theory in social science?  
> **username_7**: Cake cutting algorithm deals with fair division of resources among n parties which is a long standing problem in social science. Wiki link which I gave cites a lot of references about how it pertains to social science. In particular I like this http://3quarksdaily.blogs.com/3quarksdaily/2005/04/3qd_monday_musi.html  
> **username_7**: I think a better reference is the paper "Cake cutting really is not a piece of cake" by Edmonds and Pruhs.  

---

### Answer by username_8 on 2012-01-13. Score: 0

re applications of complexity theory in social science-- scott aaronson has a daring & amusing-at-times essay tying complexity theory to deep century-old questions in philosophy that I ran across recently reading his blog.

Why Philosophers Should Care About Computational Complexity
<http://arxiv.org/abs/1108.1791>

<http://www.scottaaronson.com/blog/>

---

another interesting area of the application of algorithmic theory to social sciences happens in economics such as studying markets or other "complex systems". the idea is that the market is composed of separate actors or "agents" that each attempt to develop algorithms to make money. a darwinian process of selection ensues. similar to genetic algorithms. (and probably now actually quite close to reality of HST, high speed trading, where there are estimates that up to 70% of market trading is due to program trading.) a leading investigator in this area is j doyne farmer

<http://tuvalu.santafe.edu/~jdf/SFI%20Template/About%20Me.html>

---

I see you mention biology on your course page. an excellent application of complexity and algorithmic theory and one under intense development is in the cutting edge problem of determining protein folding configurations. for example an early paper proved that a formalized version of the protein folding problem is NP complete.

<http://en.wikipedia.org/wiki/Protein_folding>

protein folding problem is NP complete by berger/leighton
<http://www.brown.edu/Research/Istrail_Lab/papers/1998/p30-berger.pdf>

> **Comments:**
> **username_0**: Thank you for mentioning Scott's article, but the other two answers  you give (AGT/E and Biology) I specifically exclude in the question.  
> **username_8**: do you think all computational approaches to finance are subsumed in AGT? AGT/E==algorithm game theory + economics? not sure I would agree with that or that Farmers work is in that category. you excluded AGT but did not seem to explicitly exclude Economics.  

---

