Regístrate | Conectar
El Tamiz Libros Recursos Series Únete 5 Users Online
Skip to content

Teoría de juegos XV – Dilema del prisionero iterado (I)




En el último artículo de la serie vimos el dilema al que se enfrentaban dos (presuntos… a ver si me van a enchironar a mí por prejuzgarlos) criminales muy peligrosos llamados Anny y Albert. Uno de los aspectos más importantes de aquel juego era que solo se jugaba una vez. Pues hoy vamos a jugarlo repetitivamente, a ver si el resultado cambia (¡pues claro que cambia! Si no, no le dedicaríamos un artículo).

Aprovecharemos para aprender un concepto nuevo importantísimo, el equilibrio de Nash, y relacionaremos aún más la serie con la evolución y la genética. Dividiremos este artículo en dos partes, porque si no, salía muy largo.

Como partiremos del dilema del prisionero, vamos a recordar su matriz de pagos, para que no tengas que estar continuamente yendo y viniendo de aquel artículo.

Albert
Delata Calla
Anny Delata -6,-6 0,-10
Calla -10,0 -1,-1

Equilibrio de Nash

Como decíamos, uno de los aspectos más importantes de dilema del prisionero es que se juega una sola vez: no hay lugar a cambiar de estrategia, ni castigar en el siguiente turno ni nada: decides una vez y se acabó.

Pues ahora vamos a dejar que los jugadores jueguen a este juego un número muy grande de veces (si son infinitas, el juego no cambia sustancialmente, pero se me hace más difícil explicarlo, así que vamos a dejarlo en “muchas”). En cada una de esas muchas (infinitas) veces, cada jugador puede decidir Delatar o Callar. Al final del juego se suman los años de condena, y obviamente otra vez el objetivo es cumplir el mínimo tiempo de condena total posible.

He estado tentado de ofreceros la posibilidad de que jugarais los lectores, pero la única forma que se me ha ocurrido es pediros que me enviarais un programita en C o algo así, para luego haceros jugar por parejas un montón de veces en algún tipo de liga. Como eso me ha parecido que eran demasiados deberes para obligaros a hacer en casa, al final he preferido contar directamente la conclusión.

Equilibrio de Nash: es un array de decisiones de los jugadores (es decir, una casilla de la matriz de pagos) tal que ninguno de los jugadores mejora si cambia su estrategia (manteniendo las de los demás invariantes). Nótese que según la definición no es necesario que empeore, basta con que no mejore.

El dilema del prisionero iterado tiene un equilibrio de Nash: ambos Delatan. Veámoslo despacio. Vamos a representar como AnnyC el hecho de que Anny elija Callar, y del mismo modo tendremos AnnyD, AlbertC y AlbertD.

  • Si estamos en AnnyC,AlbertC (recompensa -1,-1), y ambos dicen eso una y otra vez (recordemos que es un juego iterado, juegan muchas veces, una detrás de otra), Anny puede darse cuenta de que si ella decide D, su pago pasa a ser 0 (es decir, mejora). Así que Anny, ante una situación AnnyC,AlbertC cambiará a AnnyD,AlbertC. Por supuesto, Albert puede hacer la misma reflexión, así que Albert, ante una situación AnnyC,AlbertC cambiará a AnnyC,AlbertD, porque él pasa de -1 a 0. Por lo tanto AnnyC,AlbertC no es un equilibrio de Nash: aunque el oponente no cambie de estrategia, cualquiera de ellos gana si cambia.
  • Si estamos en AnnyC,AlbertD (recompensa -10,0), Anny se dará cuenta de que si ella también Delata (pasando a AnnyD,AlbertD) su recompensa mejora desde -10 a -6. Por lo tanto AnnyC,AlbertD no es un equilibrio de Nash.
  • Similar análisis podemos hacer para AnnyD,AlbertC, que tampoco es un equilibrio de Nash.
  • Si estamos en AnnyD,AlbertD (recompensa -6,-6), Anny no querrá cambiar a AnnyC,AlbertD porque su recompensa empeoraría de -6 a -10. Lo mismo le ocurrirá a Albert, que tampoco querrá pasar a AnnyD,AlbertC. Por lo tanto AnnyD,AlbertD sí es un equilibrio de Nash.

Todos los puntos que no sean equilibrios de Nash son inestables: al menos un jugador está tentado de cambiar y volver al equilibrio de Nash.

Algunos juegos tienen más de un equilibrio de Nash (veremos alguno más adelante, pero de momento imaginad por ejemplo una matriz de recompensas en que decisiones distintas tengan el mismo pago), pero no todos los juegos tienen por qué tener un equilibrio de Nash[1].

El equilibrio de Nash y la estrategia dominante que vimos en el anterior capítulo son dos de las herramientas más utilizadas para analizar juegos infinitos (existe un tercer concepto utilizado para esto, pero aún no hemos llegado a él), en que no podemos hacer el backtrack desde las recompensas hasta las decisiones.

En cualquier caso, ¿es el equilibrio de Nash lo máximo a lo que podemos ambicionar? En la segunda parte, más.

  1. Esto solo es cierto si consideramos únicamente estrategias puras. John Nash demostró que si se consideran estrategias mixtas, cosa que aún no hemos visto, sí que se puede demostrar que todos los juegos tienen un equilibrio de Nash. Pero como hasta ahora estamos suponiendo implícitamente estrategias puras y aún no hemos llegado a ver las estrategias mixtas, dejémoslo así. []

Sobre el autor:

J ( )

 

{ 9 } Comentarios

  1. Gravatar Argus | 13/12/2010 at 06:46 | Permalink

    Yo jugué a algo similar en un curso de la empresa. Competían entre sí tres grupos y la banca (el organizador) y con matriz positiva de recompensas no de castigos.

    Votábamos en secreto C (colaborar) o T (traicionar) y nos habríamos forrado si turno tras turno hubiéramos colaborado todos, lo que suponía ganar 1000 pesetas por grupo cada vez (pagaba la banca). Parecía tan fácil. Resultaba incomprensible que el organizador insistiese en jugar con dinero de verdad. No quisimos jugar con dinero, más que nada por la pena que nos daba el organizador, al que íbamos a desplumar con una facilidad insultante.

    Sin embargo, uno de los grupos tenía prisa por ganar más y turno tras turno traicionaba. Si un solo grupo traicionaba, los demás perdían 3000 pesetas cada uno y el traidor ganaba 6000.

    Acabamos traicionando todos, lo que suponía que cada grupo pagaba a la banca 1000 pesetas cada vez. El grupo traidor disfrutó unas partidas de beneficios para finalmente entrar en pérdidas, como todos.

    Bendita la hora que decidimos no jugar con dinero.

    Por cierto, me gustaría saber hacer programas en C, como el que querías plantear. Yo me quedé anclado en el basic, que ya tengo mis años. ¿Dónde puedo encontrar algo sencillo para empezar en C, o cualquier lenguaje que permita hacer pequeños programas como el basic? ¿Para cuándo una serie sobre ello? ;)

  2. Gravatar Brigo | 13/12/2010 at 10:43 | Permalink

    Mi programa se llamaría “Donde las dan las toman” :-D

  3. Gravatar Pedro | 14/12/2010 at 07:16 | Permalink

    Argus, otros que saben más que yo te recomendarán cosas más elevadas seguro, pero yo lo haría en python. En la página web tienen un tutorial bastante bueno, y hay documentación por ahí. No tiene la rapidez del C, pero tampoco las pesadillas del C y es mucho más divertido, al menos para mí, programar en él. http://python.org

    Pero alguien que sepa debería hablar aquí de estas cosas en una pequeña serie :)

  4. Gravatar J | 14/12/2010 at 07:56 | Permalink

    Argus,

    el texto clásico para aprender C es:

    Brian W. Kernighan, Dennis M. Ritchie. The C programming language. Segunda Edición, Prentice Hall, 1989. ISBN: 0-13-110362-8. (Biblioteca: L/D 004.438 C KER 1988)

    Te cuento una anécdota para que veas hasta que punto es importante ese libro. Kernighan y Ritchie explican una versión de C que no es exactamente la misma que estandarizó ANSI. Son diferencias muy pequeñas y muy sutiles, que no vas a detectar, no te preocupes. Pues bien, muchos compiladores pueden comportarse “según ANSI” o “según K&R”. Hasta ese punto es importante el libro de K. y R.

    En Intener, no obstante, hay miles de tutoriales:

    http://www2.its.strath.ac.uk/courses/c/

    http://www.tti.unipa.it/~ricrizzo/KS/Data/PBurden/default.htm

    El lenguaje… hay decenas (o cientos). Depende de lo que quieras hacer te será mejor uno u otro (seguro que Macluskey te recomendaría COBOL), o puede que incluso te valga con una simple macro para Excel.

  5. Gravatar Eagle | 14/12/2010 at 09:36 | Permalink

    Uy Argus, lo que acabas de pedir, ahora saltamos todos a darte consejos… jeje.

    Yo, como pragmático que soy, directamente no te recomiendo C, ni siquiera Python (pese a lo “sencillo” que parece, muestra propiedades y conceptos muy complejos, aunque para hacer cosillas sencillas, como todos, no es complicado). Lo mío es Visual Basic 6, pero como eso está “obsoleto” (nótese la ironía), de aprender algo nuevo y sencillo, pero también visual (porque en C no vas a ver un textbox ni un combobox de serie donde el usuario pueda escribir o elegir de una lista) me iría a Visual Basic.NET

    Vale, no es multiplataforma, es propietario de Microsoft… pero pides algo fácil de comprender y aprender… sin preocuparte de poner ; al final de cada línea y con un entorno amigable de trabajo… Pues eso.

    Respecto al artículo, como siempre muy interesante ese equilibrio de Nash. Y lo que le pasó a Argus es lo de siempre: no todos los jugadores siguen la lógica, o incluso pueden ser “amigos” de la banca e ir a romper el juego para crear caos. Y así acabásteis.

  6. Gravatar Argus | 14/12/2010 at 04:05 | Permalink

    Muchísimas gracias por vuestros consejos! Voy a probar los links que enviáis y seguro me ayudarán mucho. De verdad se agradecería una serie amena sobre estos lenguajes. A mí me estresa sólo pensar que el tiempo que dedicaré a aprender uno cualquiera es muy superior al tiempo que tardará en quedar obsoleto.

    Volviendo a los juegos, el grupo que siempre traicionaba no estaba compinchado con la banca. Éramos compañeros de trabajo y formamos los grupos al azar. La diferencia es que esos tres que formaron el grupo traicionero eran más listos. Bueno, no sé si listos: Eran más “Nash”. Repetían continuamente: “ganar es fácil, ganar es fácil”. En cierto modo ganaron, es decir, perdieron mucho menos que los demás.

    Sin embargo, en una situación real no creo que les hubiese valido la técnica. La vida da muchas vueltas y se pueden producir otros posibles emparejamientos. Se pueden crear grupos que confíen entre sí. De esta forma, el grupo traicionero estaría condenado a perder poco en cada enfrentamiento, pues nadie colaboraría estando ellos presentes, mientras los otros grupos podrían recuperar dinero, en ausencia del traicionero, gracias a la confianza ganada.

  7. Gravatar Macluskey | 14/12/2010 at 04:37 | Permalink

    Mmmm ¿pretendéis que en 2010 aconseje COBOL a alguien??

    No. Una cosa es que siga siendo (de momento) el lenguaje que mueve el mundo, y otra es que lo vaya a ser en el futuro. Lo que yo no haría ni harto de vino es empezar por el C. Es un lenguaje que es un poco de alto nivel y un bastante de bajísimo nivel, casi como un ensamblador.

    Yo haría caso a la experiencia: o Visual Basic.Net o si no, un Visual algo, incluso un Python. Pero fácil, fácil… no vas a encontrar nada. Ni siquiera hacer una macro en Excel es fácil.

    Siento el jarro de agua fría, pero es que la informática se ha vuelto muy complicada en los últimos tiempos… tanto, que un amigo mío dice que “esto de la informática es muy complicado para dejárselo a los informáticos”.

    Y sobre la anécdota de Argus… Yo también hice cursos de dirección de empresa y se hacían “experimentos” de diversos tipos. Y salían cosas tan tan curiosas e impensables que yo (hablo por mí) llegué a la conclusión de que:

    a) O había una cantidad realmente elevada de descerebrados e inanes mentales.

    b) O había una cantidad bastante alta de auténticos “machos cabríos de gran tamaño” que debían disfrutar fastidiando sistemáticamente el experimento.

    c) O ambas cosas.

    Claro que luego me pregunté a mí mismo: Y tú, Mac… ¿en cuál de las tres categorías estás encuadrado? Y me deprimí, claro.

    Y es que convivir en la empresa es muuuuu difícil….

    Qué buen artículo, como todos, J!!!

  8. Gravatar Scarbrow | 15/12/2010 at 02:11 | Permalink

    Argus, como informático de oficio y programador de afición, me permito afirmar que un lenguaje no se queda “obsoleto” (como podrá jurar Macluskey). Como mucho, “pasa de moda”. Yo, personalmente, me he especializado en VBA sobre Excel. Y permite hacer pequeñas maravillas, si no te importa tener que reajustar un poquito los módulos sobre la marcha cuando cambias entre diferentes versiones de Excel y un par de cabr— esto…. chuminadas más por el estilo :)

    Elige un lenguaje, apréndelo bien, y será tu fiel compañero por años y años… y además, para cuando hayas terminado con él, aprender otro cualquiera te resultará facilísimo…

  9. Gravatar Juan Carlos Giler | 15/12/2010 at 03:50 | Permalink

    Yo tambien soy informático, y este comentario “esto de la informática es muy complicado para dejárselo a los informáticos” le ha sacado muchas risas a todo mi grupo :D :D :D

    Nosotros trabajamos, en nuestros aplicativos, en Visual Basic 6 (70%) y Visual .Net con C# (el otro 30%) y personalmente, creo que un lenguaje SI se queda obsoleto, porque no te premite hacer cosas nuevas y mejores (a pesar que las que si realiza, las hace perfectamente bien)

    Desde mi punto de vista, mejor aprende Visual .Net (y C#).

    Saludos.

{ 1 } Trackback

  1. [...] de juegos XV – Dilema del prisionero iterado (I), de Javier “J” Sedano, que pode lerse en El Cedazo. Toda a serie Teoría de juegos está publicada en forma de libro, [...]

Escribe un comentario

Tu dirección de correo no es mostrada. Los campos requeridos están marcados *

Al escribir un comentario aquí nos otorgas el permiso irrevocable de reproducir tus palabras y tu nombre/sitio web como atribución.