Trade Lane Megacities & Algorítmica y complejidad computacional. Modelos económicos, su utilidad práctica y su complejidad.

Nota. Hemos cambiado el título en un par de ocasiones para añadir y modificar algunas palabras. Uno no sabe nunca cual es el nombre más adecuado…. Fin de nota.

0. Introducción.

En Ciencias Sociales el punto de vista desde el que se estudia un determinado problema es clave.

Y hay al menos cuatro puntos de vista posibles (los cuatro perfectamente válidos): el del actor pragmático (en economía digamos es el punto del vista del empresario o emprendedor: dada una realidad que no quiero, no puedo y no voy a intentar cambiar, como me puedo beneficiar de ella de la mejor manera posible); el del regulador (en economía sería el punto de vista del Gobierno: dada una realidad como puedo hacer que las acciones de actores pragmáticos se hagan en un marco en igualdad de condiciones); el del activista (es un actor que no toma la realidad como dato, sino que quiere cambiarla; sería por ejemplo el punto de vista de  una ONG activista en algún aspecto social) y, finalmente el punto de vista del observador teórico (es el punto de vista del Académico).

En un corto pero muy interesante y enriquecedor (no me  refiero en sentido material sino espiritual) proyecto profesional en el que he tenido que adoptar el punto de vista del regulador he tenido un contacto muy tangencial (he tenido que leer algo al respecto pero sin tiempo para profundizar) con este tipo de modelos: modelos de equilibrio general y modelos de gravedad o gravitacionales.

Últimamente alterno profesionalmente entre puntos de vista (pragmático, activista, regulador y el del observador, que es el que adoptamos en este blog, que no es profesional) y en breve me implico en otro nuevo proyecto completamente diferente y también muy interesante, en en el que tendré que adoptar el punto de vista pragmático (no es  nuestro proyecto personal que tendrá otro retraso: la realidad no nos da un respiro…) y antes de cambiar de tercio quiero hacer, antes de que se me olvide, una entrada sobre este tema.

Nota. Creo que un activista, un académico, un político o regulador, deberían de conocer bien el punto de vista pragmático antes de empezar estas otras actividades, y cada vez es más frecuente que un profesional tenga que cambiar de punto de vista a lo largo de su carrera. Fin de nota.

Ahora (es decir desde el incremento en la capacidad computacional de los últimos quinquenios) no son conceptos o modelos puramente abstractos como podían serlo en tiempos de Walras, por poner un ejemplo, sino herramientas prácticas tan útiles para el científico social como pueda serlo un martillo para el carpintero.

Por eso interesa que funcionen de manera eficaz y eficiente. No vamos a entrar en esta entrada a juzgar el tema de la eficacia (sirven las herramientas para contestar de manera adecuada las preguntas que se plantea el científico social ?), que a veces es debatido. Mi posición al respecto es no ser dogmático y no obsesionarse con la exactitud, dado que las bases teóricas son débiles.

Y sólo muy brevemente vamos a comentar el tema de su eficiencia. Son herramientas computacionales y por lo tanto es de aplicación a este tema la teoría de la complejidad computacional.

En aplicaciones macroeconómicas, aplicable hasta cierto punto pues los problemas reales tienen el tamaño que tienen y son estos tamaños aquellos sobre los que interesa conocer su eficiencia.  Es decir, en este caso la eficiencia asintótica, que es de lo que trataría la teoría de complejidad computacional, tiene un interés muy relativo. Pero en otras aplicaciones muy prácticas (mercados de internet y otro tipo de plataformas relacionadas con internet) que pueden escalar a diferentes y grandes tamaños el análisis asintótico sí tiene un interés incluso práctico.

En esta entrada nos vamos a centrar casi exclusivamente en este tema de la complejidad computacional de estos problemas, que hemos visto muy por encima en el pasado y ahora nos han llamado la atención. Además por su relación con los temas que estudiamos ahora mismo en nuestro proyecto personal nos interesa conocerlos un poco mejor. Como siempre la entrada es sobre todo para aprender algo sobre este tema. Poco, ya que por falta de tiempo, no vamos a poder profundizar en ello. Va a ser más bien una recopilación de enlaces.

No es habitual que tratemos en una misma entrada temas de dos series de entradas del blog cuyo contenido suele ser completamente independiente (Trade Lane Megacities y Algorítmica y Complejidad Computacional). Nos complace que ahora lo hayamos realizado de manera natural.

2. Primero algunos enlaces para que el lector vea de que estamos hablando:

Equilibrio General Computado: Descripción de la Metodología

Martín Cicowiez y Luciano Di Gresia Trabajo Docente No. 7 Abril 2004

Manual sobre Modelos de Equilibrio General Computado para Economías de LAC con Énfasis en el Análisis Económico del Cambio Climático

Omar O. Chisari Javier A. Maquieyra Sebastián J. Miller. 2012.

Modelo de gravedad aplicado al comercio intraeuropeo.

Modelos Gravitacionales para el Análisis del Comercio Exterior para el Análisis del Comercio Exterior.

Relacionado.  Una entrada en NeG sobre métodos cuantitativos en Economía. No he visto que traten sobre los temas sobre los que hablamos en la entrada.

3. Complejidad Computacional. 

En abstracto, una solución al modelo de equilibrio general competitivo es equivalente a encontrar un equilibrio de Nash en un juego finito.

Y más en abstracto todavía ambos son equivalentes a encontrar un punto fijo en una función algebraica de R^n–>R^n.

El teorema de Brouwer, que tuvo una motivación puramente matemática, es de aplicación. Es una demostración de existencia, lo cual no es poco.

Para esta clase de problemas para los que se dispone de una demostración de existencia, lo cual no significa que la búsqueda de la solución sea sencilla existe la clase de complejidad PPAD.

Las clases de complejidad funcionales (FP, TFNP, FNP etc…), entre las que está PPAD, son un mundo nuevo para mi. El lector puede encontrar información adicional aquí.

FP⊆TFNP⊆FNP

Para más detalles sobre la relación de las clases funcionales con las de búsqueda, que son aquellas en las que se incluyen los problemas que estudiamos, se puede ver esta presentación (accesible en una búsqueda web):

On the Complexity of Search Problems 

George Pierrakos

También las correspondientes entradas de wikipedia.

Decíamos que una demostración de existencia  no es poco, pero es claramente insuficiente a efectos prácticos. En la práctica queremos conocer  la solución. El algoritmo, por lo poco que he visto bastante sofisticado, para encontrar una especie de solución a este problema lo desarrolló Scarf en 1967.

En esta muy interesante presentación nos ponen al día.

The computational complexity of Games, Equilibria and Fixed Points.

Kousha Etessami. Sin fecha. ¿ 2010 ?. El lector podrá encontrarla en Internet en una búsqueda.

Nos habla sobre los mismo pero con más detalle y en forma de paper el merecidamente célebre Yannakakis.

EQUILIBRIA, FIXED POINTS, AND COMPLEXITY CLASSES

MIHALIS YANNAKAKIS

Department of Computer Science, Columbia University, New York City, NY, USA E-mail address : mihalis@cs.columbia.edu

Abstract. Many models from a variety of areas involve the computation of an equilibrium or fixed point of some kind. Examples include Nash equilibria in games; market equilibria; computing optimal strategies and the values of competitive games (stochastic and other games); stable configurations of neural networks; analysing basic stochastic models for evolution like branching processes and for language like stochastic context-free grammars; and models that incorporate the basic primitives of probability and recursion like recursive Markov chains. It is not known whether these problems can be solved in polynomial time. There are certain common computational principles underlying different types of equilibria, which are captured by the complexity classes PLS, PPAD, and FIXP. Representative complete problems for these classes are respectively, pure Nash equilibria in games where they are guaranteed to exist, (mixed) Nash equilibria in 2-player normal form games, and (mixed) Nash equilibria in normal form games with 3 (or more) players. This paper reviews the underlying computational principles and the corresponding classes.

Extracto.

In this paper we will discuss a variety of equilibria and fixed point problems, and the complexity classes which capture the essential aspects of several types of such problems. We discuss three classes, PLS, PPAD, and FIXP, which capture different types of equilibria. Some representative complete problems for these classes are: for PLS pure Nash equilibria in games where they are guaranteed to exist, for PPAD (mixed) Nash equilibria in 2-player normal form games, and for FIXP (mixed) Nash equilibria in normal form games with 3 (or more) players.

Many problems, from a broad, diverse range of areas, involve the computation of an equilibrium or fixed point of some kind. There is a long line of research (both mathematical and algorithmic) in each of these areas, but for many of these basic problems we still do not have polynomial time algorithms, nor do we have hard evidence of intractability (such as NP-hardness). We reviewed a number of such problems here, and we discussed three complexity classes, PLS, PPAD and FIXP, that capture essential aspects of several types of such problems. The classes PLS and PPAD lie somewhere between P and TFNP (total search problems in NP), and FIXP (more precisely, the associated discrete problems) lie between P and PSPACE. These, and the obvious containment PPAD ⊆ FIXP, are the only relationships we currently know between these classes and the other standard complexity classes. It would be very interesting and important to improve on this state of knowledge. Furthermore, there are several important problems that are in these classes, but are not (known to be) complete, so it is possible that one can make progress on them, without resolving the relation of the classes themselves.

Anuncios

Terms and conditions: 1. Any commenter of this blog agrees to transfer the copy right of his comments to the blogger. 2. RSS readers and / or aggregators that captures the content of this blog (posts or comments) are forbidden. These actions will be subject to the DMCA notice-and-takedown rules and will be legally pursued by the proprietor of the blog.

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s


A %d blogueros les gusta esto: