En la primera parte del artículo veíamos el concepto de equilibrio de Nash y parece que llegábamos a la conclusión de que los únicos puntos estables de la matriz de recompensas eran dichos equilibrios de Nash.

Hoy, como adelantábamos, vamos a utilizar la profunda relación que hay entre la evolución y los juegos para buscar una mejor solución al dilema del prisionero iterado.

Recordemos la matriz de pagos que utilizábamos:

Algoritmo genético

Y para demostrar esa relación, ¿qué mejor que un algoritmo genético? Como probablemente muchos lectores no conocerán el concepto de algoritmo genético, vamos a introducirlo brevemente a la vez que lo utilizamos en nuestro particular problema.

Para definir un algoritmo genético, debemos definir primero los genes de nuestro procedimiento. Dichos genes serán las unidades mínimas que manejaremos. Si nuestro procedimiento es una red neuronal, los genes serán los parámetros de cada neurona de la red; si lo que estamos colocando son antenas en un campo, los genes serán las posiciones y potencias de cada antena; si estamos haciendo una máscara XOR, los genes serán los bits de la máscara… lo que sea.

Supongamos que de alguna manera podemos reducir el procedimiento de decisión de nuestro dilema del prisionero iterado a un conjunto de 10 bits. Así por ejemplo 1011100010 define completamente nuestro comportamiento. Un individuo que tenga el código genético 1011100010 y otro individuo que también tenga 1011100010 tomarán la misma decisión ante la misma situación.^[1]

Ahora definimos una población inicial suficientemente grande y les asignamos genes al azar. Por ejemplo 1 millón de jugadores, cada uno con sus bits aleatorios.

Luego les ponemos a competir entre ellos en una liga de “dilema del prisionero iterado”, de modo que todos luchen con todos. No olvidemos que cada una de esas “partidas” de dilema del prisionero iterado se compone de muchas iteraciones, de modo que esta liga puede tardar bastante en resolverse.

Al acabar la “liga”, habrá una clasificación. Bien, pues cogemos los 500.000 inferiores y los matamos. ¿Suena cruel? Pues sí, pero eso precisamente es lo que hace la evolución: eliminar a los débiles. Y los 500.000 que quedan los hacemos reproducirse entre sí. Tenemos que definir, claro está, un mecanismo de reproducción razonable. Por ejemplo, podemos emparejarlos aleatoriamente (de modo que tendremos 250.000 parejas), y para cada pareja sacamos 4 hijos (para que la población en la siguiente generación sea también de 1 millón). Eso implica definir, obviamente, cómo nacen esos hijos. Por ejemplo podemos decir: para cada uno de los genes del hijo cogemos el gen correspondiente de uno de sus padres al azar.

Y finalmente, producimos, con una probabilidad dada (pequeña) una mutación en uno de los genes, cambiando un 0 por un 1 o viceversa.

Y volvemos a empezar el ciclo, haciendo a esta nueva generación competir entre sí en una nueva liga.

¿Hasta cuándo? Hasta que nos cansemos, o hasta que el resultado nos parezca lo bastante bueno, si es que somos capaces de medir lo bueno que es (no en todos los problemas se puede, pero en la mayoría es suficiente con encontrar algo lo bastante bueno, aunque no sea lo mejor).

Dilema del prisionero iterado, revisitado

Si aplicamos un algoritmo genético como este al dilema del prisionero iterado, al cabo de un montón de generaciones nos encontramos con que la mayoría de nuestros individuos tienen un conjunto de genes que, leídos en roman paladino significan: repite lo mismo que haya hecho el oponente en turno anterior^[2]. En inglés se suele conocer esa estrategia como “tit-for-tat”, que se suele traducir por “donde las dan las toman” o “toma y daca”.

Veamos lo que implica esto en nuestro juego:

• Empezar Callando.
• Si el otro se Calló en el turno anterior, sigue Callado. De este modo, ambos obtenemos -1,-1 si él mantiene su estrategia.
• Si el otro Delató el turno anterior, castígale Delatándole tú. De este modo, si él persiste en su Delación, ambos obtenemos -6,-6, demostrándole que si él traiciona estamos dispuestos a vengarnos.
• Si el otro pasó de Delatar a Callar, acepta la disculpa y Calla tú también, volviendo a -1,-1 si él sostiene la disculpa.

Lo cual no parece muy alejado del comportamiento aceptable en nuestra sociedad, ¿verdad?

El lector puede enlazar él mismo estas conclusiones con las que hemos visto en el pasado sobre el comportamiento social, y cómo los genes egoístas producen individuos sociales. Nosotros hemos hecho competir egoístamente a nuestros genes y hemos llegado a un algoritmo en el que, si ambos usan esta estrategia tit-for-tat, se quedan en el estado Callar/Callar. Es decir, cooperan entre sí. Son sociales precisamente porque eso es lo más egoísta para sus genes.

Las sociedades secretas

Si leéis el artículo correspondiente en la Wikipedia, veréis una cosa curiosa. La Universidad de Southampton participó una vez en una competición sobre el dilema del prisionero iterado, donde cada participante debía proporcionar un algoritmo, como lo que yo estuve a punto de pediros en el artículo anterior. Pues bien, la Universidad de Southampton no presentó 1 participante, como era de esperar, sino 60. La gracia es que esos 60 participantes se detectaban entre sí, de modo que cuando uno de ellos detectaba que su oponente era uno de sus “amigos”, se “suicidaba”, ofreciendo siempre Callar (y supongo que cuando detectaba que era uno de los “no amigos” siempre Delataba, aunque eso no lo confirma), de modo que el “amigo” podía siempre Delatar. Así, este participante se suicidaba, pero su “amigo” conseguía una puntuación altísima.

Aunque esta “sociedad secreta” no seguía el espíritu de la competición, lo cierto es que se ajustaba a las reglas, de modo que se aceptó. De ese modo, la mayoría de sus participantes quedaron en puestos bajísimos en la competición, pero unos pocos de ellos coparon el podium, muy por delante de los algoritmos basados en tit-for-tat.^[3]

1. En favor de quienes no conocen las máscaras y los XOR y cosas así, estamos simplificando mucho la explicación. La versión más simple que conozco de este procedimiento de decisión utiliza ese conjunto de bits como una máscara AND que se aplica sobre la memoria de las 10 últimas decisiones del oponente, y luego se hace XOR de todos los bits. Se mapea Callar=1 y Delatar=0. Y lo que salga es la decisión que debo tomar. Versiones más sofisticadas utilizan redes neuronales y cosas así. Si no has entendido la mayor parte de esta nota, no te preocupes, no hace falta para entender el resto del artículo. Simplemente tendrás que hacer un pequeño acto de fe en este asunto. [↩]
2. Para quienes entendieron la nota al pie anterior: la mayoría de los individuos acaban teniendo máscaras como 1000000000 [↩]
3. No obstante, como nota marginal, la estrategia tit-for-tat sigue siendo evolutivamente estable. Cuando dentro de diez o doce capítulos veamos las estrategias evolutivamente estables, vuelve aquí e intenta aplicar lo aprendido a esta situación. [↩]

The Teoría de juegos XVI – Dilema del prisionero iterado (y II) by , unless otherwise expressly stated, is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 2.5 Spain License.