Lentille algorithmique en sciences sociales

32

L'examen des questions à travers la lentille algorithmique (c'est-à-dire d'un point de vue algorithmique ou complexe) est devenu utile dans des disciplines en dehors du «domaine standard» de l'informatique. En particulier, CS a eu un impact sur la biologie grâce à la biologie computationnelle, sur la physique grâce au traitement de l'information quantique, et l'IA et la théorie de la complexité semblent interagir régulièrement avec les neurosciences. Les sciences naturelles semblent relativement à l'aise avec le TCS.

Ainsi, ma question concerne l'impact du TCS sur les sciences sociales .

Quelles idées nouvelles et importantes sur les sciences sociales le TCS a-t-il apporté?

Je suis vaguement conscient de l'impact de la pensée algorithmique sur l'économie (à travers la théorie des jeux). En fait, la théorie des jeux algorithmiques fait maintenant partie du «domaine standard» du TCS, donc permet d'exclure les réponses AGT à moins qu'elles ne modifient spécifiquement les théories existantes dans les sciences sociales.

Un autre exemple dont je me souviens est celui de la linguistique dans le débat sur la capacité d'apprentissage par rapport à l'innéité de la grammaire (c'est-à-dire la pauvreté du stimulus ). Le théorème de Gold sur l'ignorabilité des grammaires sans contexte a fourni un argument solide pour l'innéité et a aidé à convaincre certains sceptiques (je ne suis pas sûr que cela soit toujours valable, car SCFG semble être apprenable). Je suis plus intéressé par des exemples de ce type, où la pensée TCS a aidé à changer ou à façonner les théories existantes dans les sciences sociales.

Les références aux livres / sondages sont appréciées.

Artem Kaznatcheev
la source
CW? Je ne suis pas sûr ... - c'est une excellente question.
Suresh Venkat
6
Le terme "sciences sociales" n'est-il pas impropre?
Tegiri Nenashi

Réponses:

16

Networks, Crowds, and Markets: Reasoning About a Highly Connected World , par Easley et Kleinberg devraient probablement être mentionnés ici. Il est plutôt élémentaire, mais donne une large sélection de sujets en sciences sociales qui ont été considérés d'un point de vue CS et fournit de nombreuses références. Quelqu'un avec plus d'expérience dans le domaine peut peut-être nous dire à quel point le livre est proche de l'état actuel de la technique dans le domaine?

Comme réponse plus particulière, avec la prolifération de divers sites de réseaux sociaux, l'informatique est devenue tout à fait pertinente pour analyser les énormes ensembles de données de réseaux sociaux de ces sites.

Janne H. Korhonen
la source
1
Merci! Cela ressemble à un livre amusant, connaissez-vous des livres ou des sondages similaires qui sont à un niveau supérieur ou de recherche? Un survol d'Easley et Kleinberg suggère qu'il est ciblé comme une introduction pour les étudiants de premier cycle.
Artem Kaznatcheev
Malheureusement non. En fait, j'adorerais voir un tel livre ou un sondage moi-même.
Janne H. Korhonen
Je ne sais pas si quelqu'un suit toujours le sujet, mais les autres excellents livres incluent Social and Economic Network de Matthew O. Jackson et Network: An Introduction de Mark Newman. [1]: amazon.com/Social-Economic-Networks-Matthew-Jackson/dp/… [2]: amazon.com/Networks-An-Introduction-Mark-Newman/dp/0199206651
Thang Dinh
18

Cet exemple est tiré de la théorie du choix social, et des élections en particulier. Nous savons que le théorème d'Arrow (et le théorème de Gibbard-Satterthwaite en général) exclut la possibilité d'élections justes, non manipulables et sans autres conséquences bizarres. Mais un article fondateur de Bartholdi, Tovey et Trick a montré que trouver le `` hack '' souhaité pour briser un schéma de vote était difficile à NP, et de nombreux chercheurs ont étudié de manière complexe la complexité des problèmes dans le domaine de la conception des élections. . Il y a une belle enquête de Faliszewski, Hemaspaandra et Hemaspaandra sur ce sujet.

Suresh Venkat
la source
Merci! Un peu plus sur l'état actuel du choix social se trouve dans cette question: cstheory.stackexchange.com/questions/2711/…
Artem Kaznatcheev
Ah merci. J'avais oublié ma propre réponse à partir de là :)
Suresh Venkat
5

La psychologie cognitive d'aujourd'hui est vraiment basée sur le point de vue du "cerveau comme ordinateur". (Bien que cela puisse être considéré comme faisant partie des "neurosciences" mentionnées dans la question.)

Noam
la source
C'est un domaine vraiment fascinant. J'espère en savoir plus sur votre blog depuis un certain temps, et maintenant que vous l'avez transformé en blog de groupe encore plus. :)
Kaveh
1

Quelques références supplémentaires:

Dans Macgill SM, 1985, "Analyse structurelle des données sociales: un guide de l'approche du réseau Galois de Ho et une respécification partielle de l'analyse Q" Environment and Planning A 17 (8) 1089 - 1109.

MacGill souligne comment ceux des sciences sociales qui pourraient bénéficier de l'utilisation de l'analyse Q sont (généralement) les moins bien placés pour comprendre les mathématiques et donc le potentiel de ces outils dans les sciences humaines. Ce qui doit être le cas même avec une informatisation accrue - des formulations algorithmiques. (Les mathématiques sont une brume fascinante pour cette infirmière.)

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

Un grand nombre de numéros de nouvelles ERCIM ont considéré les applications sociales des mathématiques - inc. algorithmique:

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

Une autre voie possible à suivre est la visualisation dans les sciences sociales. Il y a eu une initiative majeure en Angleterre dans les années 1990:

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

La combinaison du web sémantique et des espaces conceptuels Gärdenfors (2000) peut fournir de nouvelles voies hybrides:

Gärdenfors, P. (2000). Espaces conceptuels: la géométrie de la pensée, Cambridge.

Conférence mai - «Espaces conceptuels au travail»

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

J'aimerais pouvoir m'attaquer à ces sujets - des études post-universitaires peut-être. Mes efforts de temps libre incluent des plans pour assister à la conférence ci-dessus et écrire sur une forme spécifique de modèle Hodges à vue d'ensemble (cadre conceptuel) ici: http://hodges-model.blogspot.co.uk/

Peter Jones
la source
0

des algorithmes de découpe de gâteaux qui sont importants pour une division équitable. Je suis sûr qu'ils jouent un grand rôle dans les sciences sociales.

Sai Venkat
la source
pouvez-vous citer une référence où les algorithmes de découpe de gâteaux étaient importants pour les spécialistes des sciences sociales? ou change en quelque sorte une théorie en sciences sociales?
Artem Kaznatcheev
L'algorithme de découpe de gâteaux traite de la répartition équitable des ressources entre n parties, ce qui est un problème de longue date en sciences sociales. Le lien Wiki que j'ai donné cite de nombreuses références sur la façon dont il se rapporte aux sciences sociales. En particulier, j'aime ce 3quarksdaily.blogs.com/3quarksdaily/2005/04/…
Sai Venkat
Je pense qu'une meilleure référence est le papier "La découpe de gâteaux n'est vraiment pas un morceau de gâteau" par Edmonds et Pruhs.
Sai Venkat
-1

concernant les applications de la théorie de la complexité dans les sciences sociales - scott aaronson a un essai audacieux et parfois amusant liant la théorie de la complexité à des questions philosophiques profondes d'un siècle que j'ai rencontrées récemment en lisant son blog.

Pourquoi les philosophes devraient se soucier de la complexité informatique http://arxiv.org/abs/1108.1791

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


un autre domaine intéressant de l'application de la théorie algorithmique aux sciences sociales se situe en économie, comme l'étude des marchés ou d'autres "systèmes complexes". l'idée est que le marché est composé d'acteurs ou «agents» distincts qui tentent chacun de développer des algorithmes pour gagner de l'argent. un processus darwinien de sélection s'ensuit. similaire aux algorithmes génétiques. (et probablement maintenant en fait assez proche de la réalité de la TVH, le trading à grande vitesse, où l'on estime que jusqu'à 70% du trading sur le marché est dû au trading de programmes.) un chercheur de premier plan dans ce domaine est j doyne farmer

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


Je vois que vous mentionnez la biologie sur votre page de cours. une excellente application de la complexité et de la théorie algorithmique et une en cours de développement intense est dans le problème de pointe de la détermination des configurations de repliement des protéines. par exemple, un premier article a prouvé qu'une version formalisée du problème de repliement des protéines est NP complète.

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

le problème de repliement des protéines est NP complet par berger / leighton http://www.brown.edu/Research/Istrail_Lab/papers/1998/p30-berger.pdf

vzn
la source
1
Merci d'avoir mentionné l'article de Scott, mais les deux autres réponses que vous donnez (AGT / E et biologie) j'exclus spécifiquement dans la question.
Artem Kaznatcheev
Pensez-vous que toutes les approches informatiques du financement sont incluses dans l'AGT? AGT / E == théorie des jeux d'algorithmes + économie? Je ne suis pas sûr d'être d'accord avec cela ou si les agriculteurs travaillent dans cette catégorie. vous avez exclu AGT mais ne semble pas exclure explicitement l'économie.
vzn