Por que os economistas devem se preocupar com a complexidade computacional

17

Ao tentar convencer economistas da relevância da teoria da complexidade impressa, existe uma referência padrão a ser citada? Estou familiarizado com o post de Noam Nisan , a pesquisa de Tim Roughgarden e o capítulo 11 do ensaio de Scott Aaronson . Essas postagens são acessíveis aos cientistas da computação, mas não usam a linguagem dos economistas e não são publicadas em locais normalmente lidos por eles. Existem bons argumentos para a importância da complexidade dos equilíbrios etc. direcionados aos economistas? Existe uma boa visão histórica de como os economistas reagiram à pressão dos cientistas da computação?

Pode-se argumentar que a economia neoclássica é simplesmente fechada e, portanto, esses papéis não podem existir, mas existem campos ligeiramente heterodoxos, como a economia evolucionária e a economia da complexidade (no sentido do SFI) que se justificam em linguagem familiar aos economistas. Esses campos também fazem críticas semelhantes à abordagem da complexidade computacional (como afastar-se de suposições de equilíbrios), mas não as justificam tão rigorosamente quanto a CS.


Perguntas relacionadas

Artem Kaznatcheev
fonte
2
Tente isso, os mercados são eficientes se e somente se P = NP; arxiv.org/pdf/1002.2284.pdf
Mohammad Al-Turkistany
2
@ MohammadAl-Turkistany: dei uma rápida olhada no problema e decidi: "Existe uma estratégia que estatisticamente significativamente (após contabilizar uma possível mineração de dados) ganha dinheiro (após contabilizar os custos de transação)?" está mal definido (em particular a definição de "estratégia" e "estatisticamente significante") e a prova está longe de ser "matemática" (uma redução padrão de um problema de NP-completo)
Marzio De Biasi
uma área emergente onde há muita sobreposição entre CS e econ é leilões
vzn
2
@vzn que seria uma lista muito longa, já que a AGT agora é uma parte padrão da ciência da computação. Para listas mais restritas, já existem perguntas (que eu mencionei no corpo deste post), como aquelas sobre finanças quantitativas e resultados de CS que causaram impacto direto e alteraram as teorias / paradigmas existentes nas ciências sociais . Embora aprecie seu entusiasmo, prefiro fazer perguntas focadas e apreciar respostas focadas, como as que foram dadas a Marzio De Biasi, usul e Aaron Roth.
Artem Kaznatcheev

Respostas:

13

Vejo duas direções separadas para responder à sua pergunta. Uma é: Como a filosofia da ciência da computação e o pensamento computacional impactaram o campo da economia, e por que os economistas deveriam se preocupar com a abordagem da ciência da computação ? Essa é uma pergunta muito legal, mas muito ampla, que evitarei tentar resolver.

A segunda é mais específica: agora que os cientistas da computação sabem que muitos problemas na teoria dos jogos são difíceis, como convencemos os economistas de que essas são questões importantes ou objeções ao seu trabalho? Pode não ser o que você tinha em mente, mas parece ser uma interpretação do que você escreveu, por isso quero abordá-lo porque acho um pouco problemático e acho que há razões para não escrever um ensaio discutindo esse ponto ( o que pode explicar qualquer falta de respostas).

Primeiro, os microeconomistas são frequentemente teóricos e podem estar mais interessados ​​em entender o problema em seu modelo do que no nosso. Não há uma razão a priori de uma abordagem ser melhor que a outra. Como analogia, muitos cientistas da computação teóricos estão felizes em projetar algoritmos que funcionam com números reais, mesmo que isso exija operações indecidíveis. Da mesma forma, para um economista, a complexidade pode ser um detalhe que obscurece a compreensão do que é importante em seu modelo, em vez de uma consideração importante. Isso parece mais uma questão de preferência ou filosofia do que certo ou errado.

Segundo, não está claro que a ciência da computação ainda esteja em posição de argumentar convincentemente que nossos modelos se encaixam no mundo real melhor que o deles, até termos dados experimentais para respaldar isso. (Afinal, pode ser, por exemplo, que os mercados geralmente encontrem equilíbrios rapidamente na prática, de modo que a dureza da computação é irrelevante para aplicativos do mundo real.) Sem dados, o desacordo é filosófico e é difícil afirmar que existe um lado certo ou errado . Não sei se ainda temos dados suficientes para fazer reivindicações específicas.

Terceiro, acho que muitos economistas para quem essas questões são relevantes têm notado. Em áreas como a correspondência, por exemplo (assunto do Nobel do ano passado!), Uma complexidade computacional e uma abordagem algorítmica são importantes, pois eles tentam implementar soluções em larga escala. Portanto, se um economista afirma que a complexidade não é relevante para seus interesses, ela pode estar certa; mas há outros que prestam atenção.

Então, em suma, embora pareça um objetivo que vale a pena ajudar a conscientizar os economistas dos resultados relativos à complexidade da economia (especialmente porque alguns se interessam), não tenho certeza se estamos em posição de argumentar que eles devem prestar muita atenção ou mudar sua abordagem; e acho que um forte argumento científico exigiria mais dados do que apenas filosofia.

usul
fonte
Resposta incrível! Gosto da sua segunda interpretação, acho que está de acordo com o que eu tinha em mente. Eu também gosto da sua primeira interpretação, é uma pena que você tenha decidido não abordá-la. Vou manter a pergunta em aberto por mais tempo, porque acho que existem tais pesquisas, há pelo menos uma boa nos comentários que é minha hora de dormir lendo esta noite.
Artem Kaznatcheev
8

Penso que os principais teóricos dos jogos em fluxo estão se tornando muito mais abertos ao trabalho contemporâneo na comunidade da ciência da computação, por isso pode ser menos necessário "defender o caso" da teoria algorítmica dos jogos do que no passado.

Um dos textos que conheço mais acessível aos teóricos de leilão com formação em economia é " Approximation in Economic Design ", de Jason Hartline . O capítulo 1, em particular, tenta defender os algoritmos de aproximação, se não especificamente a importância da complexidade computacional.

Aaron Roth
fonte
-1

aqui está outro ângulo baseado em mais algumas pesquisas. um princípio histórico / emergente nexo / interseção entre economia e ciência da computação / teoria da complexidade está computando os equilíbrios de Nash, que são centrais para vários modelos econômicos, nos quais Daskalakis (colaborando com Papadimitriou) é uma figura de destaque. [1] [2] [5]

essa sobreposição geralmente ocorre através do campo da teoria dos jogos, onde [3] é uma pesquisa publicada no ACM e que serve como outra ponte importante entre os campos. Shoham também cita [4] como uma pesquisa focada nos equilíbrios de Nash e "Voltada principalmente para economistas, inclui amplo material de base sobre conceitos relevantes da teoria da complexidade".

[1] A complexidade da computação em um equilíbrio de Nash Constantinos Daskalakis, Paul W. Goldberg, Christos H. Papadimitriou

[2] O que a ciência da computação pode ensinar economia MIT News

[3] Ciência da computação e teoria dos jogos Shoham

[4] T. Roughgarden. Equilíbrio computacional: uma perspectiva de complexidade computacional. Teoria Econômica, 2008

[5] Equilíbrios de Nash: complexidade, simetrias e aproximações Daskalakis.

vzn
fonte
opa, segundo olhar, a referência de Roughgarden é a mesma citada por AK, exceto a versão publicada do diário. mas mostra / sublinha que a interface é principalmente através dos equilíbrios de Nash não apontados na pergunta.
Vzn
-2

Cuidado para não apenas os econometristas, mas também os matemáticos cuja educação ainda parece bastante incompleta com a definição NPC = PET:

Desde 2011 até a metade de 2013, o http://www.proofwiki.org/wiki/Definition:NP-Complete ainda confunde o significado de um problema NP-completo com o de um problema NP-difícil que pode estar em Co-NP ou mesmo além e por não-determinismo com steprate constante polinomialmente delimitado.

É provável que os economistas possam se motivar melhor ao serem apontados para a prova de completude do NP do mercado livre por P Maymin em http://arxiv.org/pdf/1002.2284 e ser questionados sobre suas habilidades para projetar algoritmos sócio-evolutivos-informativos.

DerComputer
fonte
-4

essa é claramente uma área muito emergente, portanto seria difícil encontrar pesquisas e literatura estabelecida. também a teoria da complexidade pode ser um pouco mais abstrata para isso. no entanto, uma área atraente / natural em ascensão / interseção entre a CS / econ: tente pesquisas recentes em leilões que são especialmente importantes, uma vez que a publicidade do Google Adsense financia em grande parte o crescimento da empresa na última década e também seu IPO único baseado em leilão. observe também que as flutuações dos preços econômicos em larga escala e a dinâmica do comprador / vendedor podem ser modeladas como um sistema de leilão.

outra área um tanto semelhante em que um CS muito avançado / substancial é aplicado é o comércio em alta velocidade, uma ciência complexa / avançada, mas infelizmente não é uma pesquisa publicamente publicada devido ao seu sigilo pesado.

[1] Leilões e lances: um guia para cientistas da computação por Parsons

[2] A ciência da computação resolve o problema econômico de 30 anos - os pesquisadores do MIT generalizam o trabalho do vencedor do Nobel em leilões de item único para leilões que envolvem vários itens.

[3] Complexidade do tamanho do menu dos leilões Sergiu Hart, Noam Nisan

vzn
fonte
3
Esta não é uma resposta para a pergunta. Não perguntei o que são interseções do CS / Econ, já estou ciente disso e há outras questões (na seção de perguntas relacionadas) que já lidam com isso. Minha pergunta não é sobre resultados de complexidade, mas sobre como explicar a complexidade computacional para economistas.
Artem Kaznatcheev
tanto faz! boa sorte! é uma resposta para "por que os economistas devem se preocupar com a complexidade computacional" ... talvez a falta de referências fortes seja um indicador de que talvez não devam! às vezes, suas perguntas são muito estreitas para exigir a resposta surpreendente.
vzn