Por qué los economistas deberían preocuparse por la complejidad computacional

17

Al tratar de convencer a los economistas de la relevancia de la teoría de la complejidad en forma impresa, ¿hay alguna referencia estándar para citar? Estoy familiarizado con la publicación del blog de Noam Nisan , la encuesta de Tim Roughgarden y el capítulo 11 del ensayo de Scott Aaronson . Estas publicaciones son accesibles para los informáticos, pero no utilizan el lenguaje de los economistas y no se publican en lugares que normalmente leen. ¿Existen buenos argumentos para la importancia de la complejidad del equilibrio, etc. dirigida a los economistas? ¿Existe una buena descripción histórica de cómo los economistas han respondido a la presión de los informáticos?

Se podría argumentar que la economía neoclásica simplemente está cerrada y, por lo tanto, tales documentos no pueden existir, pero hay campos ligeramente heterodoxos como la economía evolutiva y la economía de la complejidad (en el sentido SFI) que se justifican en un lenguaje familiar para los economistas. Estos campos también hacen críticas similares al enfoque de complejidad computacional (como alejarse de los supuestos de equilibrio), pero no los justifica tan rigurosamente como lo hace CS.


Preguntas relacionadas

Artem Kaznatcheev
fuente
2
Pruebe esto, los mercados son eficientes si y solo si P = NP; arxiv.org/pdf/1002.2284.pdf
Mohammad Al-Turkistany
2
@ MohammadAl-Turkistany: Le eché un vistazo rápido y el problema de decisión "¿Existe una estrategia que estadísticamente significativa (después de tener en cuenta la posible minería de datos) genera dinero (después de tener en cuenta los costos de las transacciones)?" está mal definido (en particular, la definición de "estrategia" y "estadísticamente significativo") y la prueba está lejos de ser "matemática" (una reducción estándar de un problema NP-completo)
Marzio De Biasi
un área emergente donde hay mucha superposición entre CS y econ son las subastas
vzn
2
@vzn sería una lista demasiado larga, ya que AGT ahora es una parte estándar de la informática. Para listas más restringidas ya hay preguntas (que mencioné en el cuerpo de esta publicación), como las relacionadas con las finanzas cuantitativas y los resultados de CS que tuvieron un impacto directo y alteraron las teorías / paradigmas existentes en las ciencias sociales . Aunque aprecio su entusiasmo, prefiero hacer preguntas enfocadas y agradezco las respuestas enfocadas como las que se les dan a Marzio De Biasi, usul y Aaron Roth.
Artem Kaznatcheev

Respuestas:

13

Veo dos direcciones separadas para responder su pregunta. Una es ¿Cómo ha afectado la filosofía de la informática y el pensamiento computacional al campo de la economía, y por qué los economistas deberían preocuparse por el enfoque de la informática ? Esta es una pregunta realmente genial pero muy amplia que evitaré intentar abordar.

El segundo es más específico: ahora que los informáticos saben que muchos problemas en la teoría de juegos son difíciles, ¿cómo podemos convencer a los economistas de que estos son problemas importantes u objeciones a su trabajo? Puede que esto no sea lo que tenía en mente, pero parece ser una interpretación de lo que escribió, por lo que quiero abordarlo porque creo que es un poco problemático y creo que hay razones para no escribir un ensayo argumentando este punto ( lo que podría explicar cualquier falta de respuestas).

Primero, los microeconomistas son a menudo teóricos y pueden estar más interesados ​​en comprender el problema en su modelo que en el nuestro. No hay una razón a priori que un enfoque sea mejor que el otro. Como analogía, muchos científicos teóricos en computación están contentos de diseñar algoritmos que funcionan sobre números reales a pesar de que esto puede requerir operaciones indecidibles. De manera similar, para un economista, la complejidad puede ser un detalle que nubla la comprensión de lo que es importante en su modelo, en lugar de una consideración clave. Esto parece más una cuestión de preferencia o filosofía que correcta o incorrecta.

En segundo lugar, no está claro que la informática todavía esté en condiciones de argumentar de manera convincente que nuestros modelos se ajustan mejor al mundo real que el de ellos, hasta que tengamos datos experimentales que respalden esto. (Después de todo, podría ser, por ejemplo, que los mercados a menudo encuentran equilibrios rápidamente en la práctica, por lo que la dureza de la informática es irrelevante para las aplicaciones del mundo real). Sin datos, el desacuerdo es filosófico y es difícil afirmar que hay un lado correcto o incorrecto . No sé si todavía tenemos suficientes datos para realizar reclamos específicos.

En tercer lugar, creo que muchos economistas para quienes estas cuestiones son relevantes se han dado cuenta. En áreas como el emparejamiento, por ejemplo (¡tema del Nobel del año pasado!), La complejidad computacional y el enfoque algorítmico son importantes, ya que intentan implementar soluciones a gran escala. Entonces, si un economista afirma que la complejidad no es relevante para sus intereses, podría tener razón; pero hay otros que se dan cuenta.

En resumen, aunque parece un objetivo valioso ayudar a que los economistas sean conscientes de los resultados con respecto a la complejidad de la economía (especialmente porque algunos se interesan), no estoy seguro de que podamos argumentar que deberían prestar mucha atención. o cambiar su enfoque; y creo que un fuerte argumento científico requeriría más datos en lugar de solo filosofía.

usul
fuente
Respuesta impresionante! Me gusta su segunda interpretación, creo que está en línea con lo que tenía en mente. También me gusta su primera interpretación, es una pena que haya decidido no abordarla. Mantendré la pregunta abierta por más tiempo, porque creo que hay encuestas de este tipo, hay al menos una buena en los comentarios, que es mi lectura antes de dormir esta noche.
Artem Kaznatcheev
8

Creo que los principales teóricos de los juegos se están volviendo mucho más abiertos al trabajo contemporáneo en la comunidad de la informática, por lo que puede ser menos necesario "defender" la teoría algorítmica de juegos que en el pasado.

Uno de los textos que conozco que es más accesible para los teóricos de las subastas con experiencia en economía es la " Aproximación en el diseño económico " de Jason Hartline . El Capítulo 1, en particular, trata de defender los algoritmos de aproximación, si no es específicamente por la importancia de la complejidad computacional.

Aaron Roth
fuente
-1

Aquí hay otro ángulo basado en alguna búsqueda más. Un principio histórico / emergente nexo / intersección entre economía y ciencias de la computación / teoría de la complejidad es calcular los equilibrios de Nash que son fundamentales para varios modelos económicos, donde Daskalakis (colaborando con Papadimitriou) es una figura destacada. [1] [2] [5]

Esta superposición generalmente ocurre a través del campo de la teoría de juegos donde [3] es una encuesta publicada en ACM y que sirve como otro puente clave entre los campos. También Shoham cita [4] como una encuesta centrada en los equilibrios de Nash y "Dirigida principalmente a los economistas, incluye abundante material de antecedentes sobre conceptos relevantes de la teoría de la complejidad".

[1] La complejidad de calcular un equilibrio de Nash Constantinos Daskalakis, Paul W. Goldberg, Christos H. Papadimitriou

[2] Lo que la ciencia de la computación puede enseñar economía MIT News

[3] Informática y teoría de juegos Shoham

[4] T. Roughgarden. Equilibrios computacionales: una perspectiva de complejidad computacional. Teoría económica, 2008

[5] Equilibrios de Nash: complejidad, simetrías y aproximación Daskalakis

vzn
fuente
Vaya, segunda mirada, el árbitro Roughgarden es el mismo citado por AK, excepto la versión publicada de la revista. pero muestra / subraya que la interfaz es principalmente a través de equilibrios de Nash no señalados en la pregunta.
vzn
-2

Tenga en cuenta que no solo los economometristas, sino incluso los matemáticos cuya educación todavía parece poco firme con la definición NPC = PET:

Desde 2011 hasta la mitad de 2013 http://www.proofwiki.org/wiki/Definition:NP-Complete todavía confunde el significado del problema NP-completo con el de un problema NP-hard que posiblemente pueda estar en Co-NP o incluso más allá y por ningún no determinismo con una constante tasa estelar polinomialmente limitada.

Es probable que los economistas se sientan mejor motivados por P Maymin en la prueba de integridad de NP de los mercados libres en http://arxiv.org/pdf/1002.2284 y que se les pregunte acerca de sus conocimientos para diseñar algoritmos informativos de evolución social.

DerComputer
fuente
-4

esta es claramente un área muy emergente, por lo que sería difícil encontrar encuestas y literatura establecida. También la teoría de la complejidad puede ser un poco más abstracta para esto. Sin embargo, un área convincente / natural en el ascenso / intersección entre CS / econ: intente una investigación reciente sobre las subastas que es especialmente importante dado que la publicidad de Google Adsense financia en gran medida el crecimiento de la compañía en la última década y también su IPO singular basada en subastas. También tenga en cuenta que las fluctuaciones de precios de la economía a gran escala y la dinámica del comprador / vendedor pueden modelarse de alguna manera como un sistema similar a una subasta.

Otra área algo similar en la que se aplica un CS muy avanzado / sustancial es el comercio de alta velocidad, una ciencia compleja / avanzada, pero desafortunadamente no es una investigación publicada abiertamente debido a su gran secreto.

[1] Subastas y licitaciones: una guía para informáticos de Parsons

[2] La informática aborda el problema económico de 30 años : los investigadores del MIT generalizan el trabajo del ganador del Nobel en subastas de artículos individuales a subastas que involucran artículos múltiples.

[3] Complejidad del tamaño del menú de las subastas Sergiu Hart, Noam Nisan

vzn
fuente
3
Esta no es una respuesta a la pregunta. No pregunté qué son las intersecciones de CS / Econ, ya estoy al tanto de estas y hay otras preguntas (en la sección de preguntas relacionadas) que ya se ocupan de esto. Mi pregunta no se trata de resultados de complejidad, sino de cómo explicar la complejidad computacional a los economistas.
Artem Kaznatcheev
¡lo que sea! ¡buena suerte! es una respuesta a "por qué los economistas deberían preocuparse por la complejidad computacional" ... ¡tal vez la falta de referencias fuertes es un indicador de que tal vez no deberían! sus preguntas a veces son demasiado limitadas para exigir la respuesta cortante.
vzn