25.5.12

1636.- Teoría algorítmica de juegos (2)

(viene de Teoría algorítmica de juegos 1)

Ineficiencia


Consideren un juego, sus reglas, y los pagos y costos por participar. El problema principal que esta gente quiso resolver es el de analizar la ineficiencia asociada con la libertad que tienen los jugadores para elegir qué hacer. Claramente, si no hay restricciones, cada jugador actúa por su propio interés, pero el resultado al que se llega puede ser malo desde el punto de vista social o colectivo.

En Una mente brillante se dice que Nash refutó a Adam Smith, mostrando cómo todos podían beneficiarse, etcétera. Ni ahí. Hay equilibrios de Nash donde la mano invisible que elige las estrategias producen resultados desastrosos (de los cuales nadie quiere salir, porque empeora su situación), y hay ejemplos que lo muestran claramente.

* * *


Primer Ejemplo

El primer ejemplo NO es el dilema del prisionero. Ahí no hay opción: el juego tiene un solo equilibrio, así que no tienen chances de hacer nada. En cualquier situación, confesar es mejor que quedarse callado, y si bien se llega a un resultado no deseado, es clarísimo que no hay alternativas.


El primer ejemplo es una red con dos caminos A y B para ir de s a t. Pero A cuesta K y B cuesta 1+E, con E muy pequeño. Tenemos también K jugadores, que deben elegir ruta, y compartirán el costo de una ruta aquellos jugadores que la elijan.

Observemos que si todos van por el camino B, cada uno paga (1+E)/K, muy poco, y a nadie le conviene desviarse porque pagaría K, muchísimo.

Pero resulta que hay otro equilibrio de Nash, muy ineficiente, y es que todos elijan la ruta A: cada uno paga 1, y si un jugador se desvía, pagaría 1+E. Resultado: se quedan todos en la ruta A, pagando en total K.

Bienvenidos a la ineficiencia de la mano invisible de Nash.

* * *


Antes de otro ejemplo, veamos que buscaron resolver los seis ganadores del Godel de este año. Para analizar la ineficiencia de un juego hay que contestar las siguientes preguntas:

  • 1.- ¿Cuáles son los pagos?




  • El problema se simplifica si hay un valor monetario (se paga o cobra cierta cantidad según qué hacen todos), pero también se puede considerar el tiempo que lleva una tarea (si bien time = money, hay situaciones donde el presupuesto no importa con tal de minimizar el tiempo).


  • 2.- ¿Cómo comparar los distintos resultados del juego?




  • Si bien 1.- sugiere minimizar costos ó tiempos, o maximizar ganancias, hay que distinguir entre dos enfoques:

    -Utilitario: buscamos minimizar el costo (o tiempo) general, tal vez a costa de matar a algún jugador, que corre con todo el costo.

    -Igualitario: se quiere reducir el costo máximo de los jugadores.

    Según el contexto, habrá que ver cuál conviene, definir la función correspondiente, y se busca el valor óptimo.

  • 3.- ¿Qué quiere decir 'casi óptimo'?



  • La solución que eligieron es dividir el valor óptimo y el valor de la función en un equlibrio. Si esa razón está cerca de uno, podemos pensar que el equilibrio es casi óptimo. Y es fácil comparar, diciendo que es un tanto por ciento peor, o que cuesta el triple, etc. Además, como dicen en el libro: casi todos usan ese parámetro...

    En la elección de cómo comparar, se llegó a un equilibrio ¿será cercano a un óptimo? :-)


  • 4.- ¿Qué equilibrios se considerarán?




  • Acá no hay mucha vuelta: son los equlibrios de Nash, preferentemente los equilibrios en estrategias puras, y se mira cuánto valen para la función del punto 2.-


  • 5.- ¿Qué pasa si hay más de un equilibrio?




  • Ahí vienen las dos definiciones importantes:

    Precio de la Anarquía: es la razón (definida en 3.-) entre el peor valor de la función evaluada en los equilibrios (4.-) y el valor óptimo (2.-).

    Precio de la Estabilidad: es la razón (definida en 3.-) entre el mejor valor de la función evaluada en los equilibrios (4.-) y el valor óptimo (2.-).

    En el ejemplo de la red de dos caminos, el óptimo (utilitario e igualitario) es que todos vayan por B, que era un equilibrio de Nash. Como ese equilibrio coincide con el óptimo, el precio de la estabilidad es 1. Pero hay un equilibrio cuyo costo es K, con lo cual el precio de la anarquía es

    (valor del equilibrio)/óptimo = K / (1+E) ~ K.


    * * *


    Precio de la estabilidad

    Recordemos que en un equilibrio de Nash nadie tiene motivos para desviarse, lo cual estabiliza una situación: si todos estamos haciendo algo, y nadie gana más por desviarse unilateralmente, entonces seguiremos haciendo todos lo mismo.

    En cualquier elección de estrategias que no sea un Nash, habrá un jugador que tiene incentivos por desviarse, con lo cual es difícil lograr que todos se coordinen en una situación (por ejemplo, la que da el valor óptimo) si esta no es un Nash. El precio de la estabilidad es lo mínimo que tenemos que sacrificar para tener un Nash.

    * * *


    Precio de la anarquía

    El precio de la anarquía, en cambio, es el peor caso que puede darse. Nos alejamos del óptimo, y nadie tiene incentivos para cambiarse. Cuando hay un único equilibrio, mala suerte, coincide con el precio de la estabilidad y no hay mucho más para decir.

    El problema más grave es cuando hay varios equilibrios y justo ese es fácil de descubrir, o es el que se implementa fácil o rápido por razones dinámicas. Veamos el ejemplo inicial con otra óptica.

    Vivir en el centro de Buenos Aires es una locura, y si bien muchísima gente trabaja en el centro, prefiere vivir en Pilar, o Tigre, zonas alejadas desde las que sólo se llega en auto. Si K personas viven en Pilar, salen a las 8hs y vuelven a las 18hs, cada una pagando el costo de un auto, unas 8-10 podrían pagar mucho menos y mantener una combi que los lleve/traigo más o menos en el mismo tiempo. El tema es que cuando un country comienza a formarse, como los habitantes son pocos, la única solución es que cada uno resuelva su problema de transporte con su propio auto.

    La formación de una villa sigue una dinámica similar: cada familia ocupa parcelas de un terreno, hasta cubrir por completo el área disponible. Abrir luego caminos internos (para circular con más comodidad o seguridad, llevar luz o agua, etc) termina siendo imposible, porque es necesario desplazar algunas familias, y en ocasiones ya no hay donde ubicarlas a menos que sea en otra parte.

    El problema se ve también en las partes más viejas de las ciudades, donde la estructura antigua tiene calles intransitables para la modernidá, e invitan a carnicerías históricas, tales como en el centro de Buenos Aires, cuando se demolió parte del Cabildo para facilitar el tránsito. Bueno, también a Vieytes se le ocurre instalar su jabonería justo donde hoy (25 de Mayo, pero 202 años después) tenía que pasar la Avenida 9 de Julio...

    * * *


    Continuará.

    (y esta vez, el Carnaval está en Gaussianos.)