Lente algorítmica en las ciencias sociales.

32

Mirar las preguntas a través de la lente algorítmica (es decir, desde un punto de vista algorítmico o de complejidad) se ha vuelto útil en disciplinas fuera del "dominio estándar" de la informática. En particular, CS ha tenido un impacto en la biología a través de la biología computacional, en la física a través del procesamiento de información cuántica, y la IA y la teoría de la complejidad parecen interactuar regularmente con la neurociencia. Las ciencias naturales parecen relativamente cómodas con TCS.

Por lo tanto, mi pregunta es sobre el impacto de TCS en las ciencias sociales .

¿Qué ideas nuevas e importantes sobre las ciencias sociales ha proporcionado TCS?

Soy vagamente consciente del impacto del pensamiento algorítmico en la economía (a través de la teoría de juegos). De hecho, la teoría algorítmica de juegos ahora es parte del 'dominio estándar' de TCS, por lo que excluiremos las respuestas AGT a menos que alteren específicamente las teorías existentes en las ciencias sociales.

Otro ejemplo que recuerdo es el de la lingüística en el debate sobre la capacidad de aprendizaje versus lo innato de la gramática (es decir, la pobreza del estímulo ). El teorema de Gold sobre la imposibilidad de aprender de las gramáticas libres de contexto proporcionó un fuerte argumento a favor de lo innato y ayudó a convencer a algunos escépticos (no estoy seguro de si esto todavía es válido, ya que SCFG parece ser aprendible). Estoy más interesado en ejemplos de este tipo, donde el pensamiento TCS ayudó a cambiar o dar forma a las teorías existentes en las ciencias sociales.

Se agradecen las referencias a libros / encuestas.

Artem Kaznatcheev
fuente
CW? No estoy seguro ... es una gran pregunta.
Suresh Venkat
66
¿No es el término "ciencias sociales" un nombre inapropiado?
Tegiri Nenashi

Respuestas:

16

Redes, multitudes y mercados: razonamiento sobre un mundo altamente conectado , por Easley y Kleinberg, probablemente debería mencionarse aquí. Es bastante elemental, pero ofrece una amplia selección de temas de ciencias sociales que se han considerado desde un punto de vista de CS y proporciona muchas referencias. ¿Alguien con más experiencia en el campo quizás pueda decirnos qué tan cerca está el libro del estado actual del arte en el campo?

Como respuesta más particular, con la proliferación de varios sitios de redes sociales, la informática se ha vuelto bastante relevante en el análisis de los enormes conjuntos de datos de redes sociales de dichos sitios.

Janne H. Korhonen
fuente
1
¡Gracias! Parece un libro divertido, ¿conoce algún libro o encuesta similar que tenga un nivel de posgrado o de investigación? Un vistazo a Easley y Kleinberg sugiere que está dirigido como una introducción para estudiantes de pregrado.
Artem Kaznatcheev
Lamentablemente, no, no lo hago. De hecho, me encantaría ver un libro o una encuesta de este tipo.
Janne H. Korhonen
No estoy seguro de si alguien todavía sigue el tema, pero los otros libros excelentes incluyen Social and Economic Network de Matthew O. Jackson y 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

Este ejemplo es de la teoría de la elección social, y de las elecciones en particular. Sabemos que el teorema de Arrow (y el teorema de Gibbard-Satterthwaite en general) descartan la posibilidad de elecciones que sean justas, no manipulables y sin otras consecuencias extrañas. Pero un documento seminal de Bartholdi, Tovey y Trick mostró que encontrar el 'truco' deseado para romper un esquema de votación fue NP-difícil, y muchos investigadores han trabajado mucho sobre la complejidad de los problemas en el ámbito del diseño electoral. . Hay una buena encuesta de Faliszewski, Hemaspaandra y Hemaspaandra sobre este tema.

Suresh Venkat
fuente
¡Gracias! Un poco más sobre el estado actual de elección social se encuentra en esta pregunta: cstheory.stackexchange.com/questions/2711/…
Artem Kaznatcheev
Ah gracias. Había olvidado mi propia respuesta desde allí :)
Suresh Venkat
5

La psicología cognitiva actual se basa realmente en el punto de vista del "cerebro como computadora". (Aunque, esto puede considerarse como parte de la "neurociencia" mencionada en la pregunta).

Noam
fuente
Es un área realmente fascinante. Esperaba leer más sobre esto en su blog por algún tiempo, y ahora que lo ha convertido en un blog grupal aún más. :)
Kaveh
1

Algunas referencias adicionales:

En Macgill SM, 1985, "Análisis estructural de datos sociales: una guía para el enfoque de celosía de Ho Galois y una respecificación parcial del análisis Q" Medio ambiente y planificación A 17 (8) 1089 - 1109.

MacGill destaca cómo aquellos en las ciencias sociales que podrían beneficiarse del uso del análisis Q están (generalmente) en una posición menos adecuada para comprender las matemáticas y, por lo tanto, el potencial de tales herramientas en las humanidades. Cuál debe ser el caso incluso con una mayor informatización: formulaciones algorítmicas. (Matemáticas es una niebla fascinante para esta enfermera).

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

Un gran número de noticias de ERCIM han considerado las aplicaciones sociales de las matemáticas - inc. algorítmico:

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

Otra posible vía a seguir es la visualización en las ciencias sociales. Hubo una iniciativa importante en Inglaterra en la década de 1990:

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

La combinación de la web semántica, espacios conceptuales Gärdenfors (2000) puede proporcionar nuevas vías híbridas:

Gärdenfors, P. (2000). Espacios conceptuales: La geometría del pensamiento, Cambridge.

Conferencia de mayo - 'Espacios conceptuales en el trabajo'

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

Desearía poder familiarizarme con estas materias, posiblemente estudios de posgrado. Mis esfuerzos de tiempo libre incluyen planes para asistir a la conferencia anterior y escribir sobre una forma específica de panorama general (marco conceptual) modelo de Hodges aquí: http://hodges-model.blogspot.co.uk/

Peter Jones
fuente
0

Algoritmos de corte de torta que son importantes para una división equitativa. Estoy seguro de que juegan un papel importante en las ciencias sociales.

Sai Venkat
fuente
¿Puedes citar una referencia donde los algoritmos de corte de pastel eran importantes para los científicos sociales? o de alguna manera cambia alguna teoría en las ciencias sociales?
Artem Kaznatcheev
El algoritmo de corte de torta se ocupa de la división equitativa de los recursos entre n partes, que es un problema de larga data en las ciencias sociales. El enlace Wiki que le di cita cita muchas referencias sobre cómo se relaciona con las ciencias sociales. En particular, me gusta esto 3quarksdaily.blogs.com/3quarksdaily/2005/04/…
Sai Venkat
Creo que una mejor referencia es el artículo "El corte de pasteles realmente no es pan comido" por Edmonds y Pruhs.
Sai Venkat
-1

Aplicaciones de la teoría de la complejidad en las ciencias sociales: Scott Aaronson tiene un ensayo audaz y divertido en ocasiones que vincula la teoría de la complejidad con preguntas profundas de filosofía que encontré recientemente leyendo su blog.

Por qué los filósofos deberían preocuparse por la complejidad computacional http://arxiv.org/abs/1108.1791

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


Otra área interesante de la aplicación de la teoría algorítmica a las ciencias sociales ocurre en la economía, como estudiar mercados u otros "sistemas complejos". La idea es que el mercado está compuesto por actores o "agentes" separados que intentan desarrollar algoritmos para ganar dinero. se produce un proceso de selección darwiniano. similar a los algoritmos genéticos. (y probablemente ahora bastante cerca de la realidad del HST, comercio de alta velocidad, donde hay estimaciones de que hasta el 70% del comercio de mercado se debe al comercio de programas). Un investigador líder en esta área es J Doyne Farmer

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


Veo que mencionas biología en la página de tu curso. Una excelente aplicación de la complejidad y la teoría algorítmica y una en desarrollo intenso es el problema de vanguardia de determinar las configuraciones de plegamiento de proteínas. Por ejemplo, un artículo anterior demostró que una versión formalizada del problema de plegamiento de proteínas es NP completa.

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

problema de plegamiento de proteínas es NP completo por berger / leighton http://www.brown.edu/Research/Istrail_Lab/papers/1998/p30-berger.pdf

vzn
fuente
1
Gracias por mencionar el artículo de Scott, pero las otras dos respuestas que da (AGT / E y Biología) excluyo específicamente en la pregunta.
Artem Kaznatcheev
¿Crees que todos los enfoques computacionales de las finanzas están incluidos en AGT? AGT / E == algoritmo teoría del juego + economía? No estoy seguro de que estaría de acuerdo con eso o que el trabajo de los agricultores está en esa categoría. excluyó AGT pero no pareció excluir explícitamente la economía.
vzn