Lente algorítmica nas ciências sociais

32

Examinar perguntas através da lente algorítmica (isto é, do ponto de vista algorítmico ou da complexidade) tornou-se útil em disciplinas fora do 'domínio padrão' da ciência da computação. Em particular, o CS causou impacto na biologia através da biologia computacional, na física através do processamento quântico de informações, e a IA e a teoria da complexidade parecem interagir regularmente com a neurociência. As ciências naturais parecem relativamente confortáveis ​​com o TCS.

Assim, minha pergunta é em relação ao impacto do TCS nas ciências sociais .

Que novas e importantes idéias sobre as ciências sociais a TCS forneceu?

Estou vagamente ciente do impacto do pensamento algorítmico na economia (através da teoria dos jogos). De fato, a teoria algorítmica dos jogos agora faz parte do "domínio padrão" do TCS, então vamos excluir as respostas da AGT, a menos que elas tenham alterado especificamente as teorias existentes nas ciências sociais.

Outro exemplo que recordo é da lingüística no debate da aprendizagem vs. inatilidade do gramático (isto é, pobreza do estímulo ). O teorema de Gold sobre a impossibilidade de aprender gramáticas livres de contexto forneceu um forte argumento para a inatilidade e ajudou a convencer alguns céticos (não tenho certeza se isso ainda é válido, pois o SCFG parece ser aprendível). Estou mais interessado em exemplos desse tipo, nos quais o pensamento do TCS ajudou a mudar ou moldar as teorias existentes nas ciências sociais.

Referências a livros / pesquisas são apreciadas.

Artem Kaznatcheev
fonte
CW? Não tenho certeza ... - é uma ótima pergunta.
Suresh Venkat
6
O termo "ciências sociais" não é um nome impróprio?
Tegiri Nenashi

Respostas:

16

Redes, multidões e mercados: raciocínio sobre um mundo altamente conectado , de Easley e Kleinberg, provavelmente deve ser mencionado aqui. É bastante elementar, mas fornece uma ampla seleção de tópicos de ciências sociais que foram considerados do ponto de vista do CS e fornece muitas referências. Alguém com mais experiência no campo talvez possa nos dizer o quão perto o livro está do atual estado da arte no campo?

Como resposta mais específica, com a proliferação de vários sites de redes sociais, a ciência da computação se tornou bastante relevante na análise dos enormes conjuntos de dados de redes sociais desses sites.

Janne H. Korhonen
fonte
11
obrigado! Parece um livro divertido, você conhece livros ou pesquisas semelhantes que estão no nível de pós-graduação ou de pesquisa? Uma pesquisa sobre Easley e Kleinberg sugere que ele é direcionado como uma introdução para os estudantes de graduação.
Artem Kaznatcheev
Infelizmente não, não. Na verdade, eu adoraria ver esse livro ou me fazer uma pesquisa.
Janne H. Korhonen
Não tenho certeza se alguém ainda segue o tópico, mas os outros excelentes livros incluem Social and Economic Network, de Matthew O. Jackson e 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 exemplo é da teoria da escolha social, e das eleições em particular. Sabemos que o teorema de Arrow (e o teorema de Gibbard-Satterthwaite em geral) exclui a possibilidade de eleições justas, não manipuláveis ​​e sem outras conseqüências bizarras. Mas um artigo seminal de Bartholdi, Tovey e Trick mostrou que encontrar o 'hack' desejado para quebrar um esquema de votação era difícil para o NP, e houve um grande corpo de trabalho de muitos pesquisadores sobre a complexidade dos problemas no campo do design de eleições. . Há uma boa pesquisa de Faliszewski, Hemaspaandra e Hemaspaandra sobre esse tópico.

Suresh Venkat
fonte
obrigado! Um pouco mais sobre o estado atual da escolha social está nesta pergunta: cstheory.stackexchange.com/questions/2711/…
Artem Kaznatcheev
Ah obrigada. Eu tinha esquecido a minha própria resposta de lá :)
Suresh Venkat
5

A psicologia cognitiva de hoje é realmente baseada no ponto de vista do "cérebro como computador". (Embora isso possa ser considerado parte da "neurociência" mencionada na pergunta.)

Noam
fonte
É uma área realmente fascinante. Eu espero ler mais sobre isso no seu blog há algum tempo e agora que você o transformou em um blog de grupos ainda mais. :)
Kaveh 16/01
1

Algumas referências adicionais:

Em Macgill SM, 1985, "Análise estrutural de dados sociais: um guia para a abordagem da estrutura de Ho Ho Galois e uma respecificação parcial da Q-análise" Environment and Planning A 17 (8) 1089 - 1109.

MacGill destaca como aqueles em ciências sociais que podem se beneficiar do uso da análise Q são (geralmente) menos bem posicionados para entender a matemática e, portanto, o potencial de tais ferramentas nas ciências humanas. O que deve ser o caso mesmo com o aumento da informatização - formulações algorítmicas. (Matemática é uma névoa fascinante para esta enfermeira.)

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

Muitas questões de notícias do ERCIM consideraram as aplicações sociais da matemática - inc. algorítmico:

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

Outra via possível a seguir é a visualização nas ciências sociais. Houve uma grande iniciativa na Inglaterra nos anos 90:

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

A combinação da web semântica, espaços conceituais de Gärdenfors (2000) pode fornecer novos caminhos híbridos:

Gärdenfors, P. (2000). Espaços conceituais: A geometria do pensamento, Cambridge.

Conferência de maio - 'Espaços conceituais no trabalho'

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

Eu gostaria de poder lidar com esses assuntos - possivelmente estudos de pós-graduação. Meus esforços no tempo livre incluem planos para participar da conferência acima e escrever sobre uma forma específica de modelo geral (modelo conceitual) de Hodges aqui: http://hodges-model.blogspot.co.uk/

Peter Jones
fonte
0

algoritmos de corte de bolos que são importantes para a divisão justa. Tenho certeza de que eles desempenham um papel importante nas ciências sociais.

Sai Venkat
fonte
você pode citar uma referência em que os algoritmos de corte de bolos eram importantes para os cientistas sociais? ou de alguma forma muda alguma teoria nas ciências sociais?
Artem Kaznatcheev
O algoritmo de corte de bolos lida com uma justa divisão de recursos entre n partes, o que é um problema antigo nas ciências sociais. O link do Wiki que eu citei muitas referências sobre como se refere à ciência social. Em particular, eu gosto disso #: 3quarksdaily.blogs.com/3quarksdaily/2005/04/…
Sai Venkat
Eu acho que uma referência melhor é o artigo "Cortar bolo realmente não é um pedaço de bolo" de Edmonds e Pruhs.
Sai Venkat
-1

re aplicações da teoria da complexidade nas ciências sociais - scott aaronson tem um ensaio ousado e divertido às vezes vinculando a teoria da complexidade a questões profundas de um século na filosofia que encontrei recentemente lendo seu blog.

Por que os filósofos devem se preocupar com a complexidade computacional http://arxiv.org/abs/1108.1791

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


outra área interessante da aplicação da teoria algorítmica às ciências sociais ocorre na economia, como o estudo de mercados ou outros "sistemas complexos". a idéia é que o mercado seja composto de atores ou "agentes" separados, que cada um tenta desenvolver algoritmos para ganhar dinheiro. segue-se um processo darwiniano de seleção. semelhante a algoritmos genéticos. (e provavelmente agora, na verdade, bem próximo da realidade do HST, negociação de alta velocidade, onde há estimativas de que até 70% do comércio de mercado é devido ao comércio de programas.) um investigador líder nessa área é um fazendeiro

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


Vejo você mencionar biologia na página do seu curso. uma excelente aplicação de complexidade e teoria algorítmica e outra sob intenso desenvolvimento está no problema de ponta da determinação de configurações de dobragem de proteínas. por exemplo, um artigo anterior provou que uma versão formalizada do problema da dobragem de proteínas é NP completa.

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

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

vzn
fonte
11
Obrigado por mencionar o artigo de Scott, mas as outras duas respostas que você dá (AGT / E e Biologia) excluí especificamente na pergunta.
Artem Kaznatcheev
você acha que todas as abordagens computacionais para financiamento estão incluídas no AGT? AGT / E == teoria dos jogos do algoritmo + economia? não tenho certeza se eu concordaria com isso ou se o trabalho dos agricultores está nessa categoria. você excluiu a AGT, mas não pareceu excluir explicitamente a Economia.
vzn