Teoría de xogos (XVI): Dilema do prisioneiro iterativo (II)

[Esta é unha tradución autorizada de Ciención de Breogán, adaptada do artigo orixinal de 20 de decembro de 2010 Teoría de juegos XVI – Dilema del prisionero iterado (y II), de Javier “J” Sedano, que pode lerse en El Cedazo. Toda a serie Teoría de juegos está publicada en forma de libro, dispoñible aquí.]

[O artigo previo da serie é Teoría de xogos (XV): Dilema do prisioneiro iterativo (I).]

Prisioneiro

Na primeira parte do artigo viamos o concepto de equilibrio de Nash, e semella que chegabamos á conclusión de que os únicos puntos estables da matriz de recompensas eran os ditos equilibrios de Nash.

Hoxe, tal e como adiantabamos, imos empregar a fonda relación que hai entre a evolución e os xogos para procurarmos unha mellor solución ao dilema do prisioneiro iterativo.

Lembremos a matriz de pagamentos que empregabamos:

Albert
Delata Cala
Anny Delata −6, −6 0, −10
Cala −10, 0 −1, −1

Algoritmo xenético

E, para demostrar esa relación, que hai mellor ca un algoritmo xenético? Como, probablemente, moitos lectores non coñecerán o concepto de «algoritmo xenético», ímolo introducir brevemente á vez que o empregamos no noso problema particular.

Para definir un algoritmo xenético, debemos definir primeiro os xenes do noso procedemento. Tales xenes serán as unidades mínimas que manexaremos. Se o noso procedemento é unha rede neural, os xenes serán os parámetros de cada neurona da rede; se o que estamos colocando son antenas nun campo, os xenes serán as posicións e potencias de cada antena; se estamos a facer unha máscara xor, os xenes serán os bits da máscara… o que sexa.

Supoñamos que, dalgún xeito, podemos reducir o procedemento de decisión do noso dilema do prisioneiro iterativo a un conxunto de 10 bits. Así, por exemplo, 1011100010 define completamente o noso comportamento. Un individuo que teña o código xenético 1011100010 e outro individuo que tamén teña 1011100010 tomarán a mesma decisión perante a mesma situación.1

Agora definimos unha poboación inicial suficientemente grande e asignámoslle xenes á toa. Por exemplo, un millón de xogadores, cada un cos seus bits aleatorios.

Logo pomos os individuos a competir entre eles nunha liga de «dilema do prisioneiro iterativo», de xeito que todos loiten con todos. Non esquezamos que cada unha desas «partidas» do dilema do prisioneiro iterativo se compón de moitas iteracións, de xeito que esta liga pode tardar bastante en resolverse.

Ao rematar a «liga», haberá unha clasificación. Pois ben, collemos os 500 000 inferiores e matámolos. Soa cruel? Pois si, pero iso é precisamente o que fai a evolución: eliminar os débiles. E, os 500 000 que quedan, facémolos reproducirse entre si. Temos de definir, por suposto, un mecanismo de reprodución razoable. Por exemplo, podemos emparellalos á toa (de xeito que teremos 250 000 parellas) e, para cada parella, obtemos 4 fillos (para que a poboación na seguinte xeración tamén sexa de un millón). Iso implica definir, obviamente, como nacen eses fillos. Por exemplo podemos dicir: para cada un dos xenes do fillo collemos o xene correspondente dun dos seus pais aleatoriamente.

E, finalmente, producimos, cunha (pequena) probabilidade determinada, unha mutación nun dos xenes, cambiando un 0 por un 1 ou ao revés.

E volvemos comezar o ciclo, facendo que os membros desta nova xeración compitan entre si nunha nova liga.

Ata cando? Ata que cansemos, ou ata que o resultado nos pareza bo dabondo, se é que somos quen a medir o bo que é (non en todos os problemas se pode, pero na maioría abonda con atopar algo suficientemente bo aínda que non sexa o mellor).

O dilema do prisioneiro iterativo, revisado

Se lle aplicamos un algoritmo xenético coma este ao dilema do prisioneiro iterativo, ao cabo dunha morea de xeracións atopámonos con que a meirande parte dos nosos individuos teñen un conxunto de xenes que, interpretados, significan: repite o mesmo que fixese o opoñente na quenda anterior.2 En inglés adóitase coñecer esta estratexia como «tit-for-tat», que se traduce como «ollo por ollo» ou «man por man».

Vexamos o que implica isto no noso xogo:

  • Comezar Calando.
  • Se o outro Calou na quenda anterior, segue Calado. Deste xeito, ambos obteremos (−1, −1) se el mantén a súa estratexia.
  • Se o outro Delatou na quenda anterior, castígao Delatándoo ti. Deste xeito, se el persiste na súa Delación, ambos os dous obtemos (−6, −6), demostrándolle que, se el traizoa, nós estamos dispostos a nos vingar.
  • Se o outro pasou de Delatar a Calar, acepta a desculpa e Cala ti tamén, volvendo a (−1, −1) se el sostén a desculpa.

Isto non semella moi afastado do comportamento aceptable na nosa sociedade, non si?

O lector mesmo pode ligar estas conclusións coas que vimos no pasado verbo do comportamento social e como os xenes egoístas producen individuos sociais. Nós fixemos competir egoistamente os nosos xenes e acadamos un algoritmo no cal, se ambos empregan esta estratexia tit-for-tat, quedan no estado (Calar, Calar). É dicir, cooperan entre si. Son sociais precisamente porque iso é o máis egoísta para os seus xenes.

Sociedades secretas

Se ledes o artigo correspondente na Wikipedia (en castelán), veredes unha cousa curiosa. A Universidade de Southampton (University of Southampton) participou unha vez nunha competición sobre o dilema do prisioneiro iterativo onde cada participante debía achegar un algoritmo. Pois ben, a Universidade de Southampton non presentou un participante, como era esperable, senón 60. A graza é que eses 60 participantes se detectaban entre si, de xeito que, cando un deles detectaba que o seu opoñente era un dos seus «amigos», «suicidábase» ofrecendo sempre Calar (e supoño que, cando detectaba un «non amigo», sempre Delataba, se ben iso non o confirma), de maneira que o «amigo» podía sempre Delatar. Así, este participante suicidábase, pero o seu «amigo» conseguía unha puntuación altísima.

Aínda que esta «sociedade secreta» non seguía o espírito da competición, o certo é que se axustaba ás regras, polo que se aceptou. Dese xeito, a maioría dos seus participantes quedaron en postos baixísimos na competición, pero uns poucos deles coparon o podio, moi por diante dos algoritmos baseados en tit-for-tat.3


Este artigo e mais a súa tradución están publicados baixo licenza CC BY-NC-ND 2.5 ES.


1. En favor daqueles que non coñecen as máscaras e os xor e cousas tales, estamos simplificando moito a explicación. A versión máis simple que coñezo deste procedemento de decisión emprega este conxunto de bits como unha máscara and que se aplica sobre a memoria das 10 últimas decisións do opoñente e despois faise xor de todos os bits. «Mapéase» Calar = 1 e Delatar = 0. E o que saia é a decisión que debo tomar. Versións máis sofisticadas empregan redes neurais e cousas así. Se non entendiches a meirande parte desta nota, non te preocupes, non cómpre para comprender o resto do artigo. Simplemente terás de te fiar de min neste asunto.

2. Para os que entenderon a nota anterior: os máis dos individuos acaban tendo máscaras como 1000000000.

3. Porén, como nota marxinal, a estratexia tit-for-tat segue sendo evolutivamente estable. Cando, dentro de dez ou doce capítulos, vexamos as estratexias evolutivamente estables, volve aquí e tenta aplicar o aprendido a esta situación.

Advertisements

Deixar unha resposta

introduce os teu datos ou preme nunha das iconas:

Logotipo de WordPress.com

Estás a comentar desde a túa conta de WordPress.com. Sair /  Cambiar )

Google+ photo

Estás a comentar desde a túa conta de Google+. Sair /  Cambiar )

Twitter picture

Estás a comentar desde a túa conta de Twitter. Sair /  Cambiar )

Facebook photo

Estás a comentar desde a túa conta de Facebook. Sair /  Cambiar )

w

Conectando a %s