Teoría de xogos (XV): Dilema do prisioneiro iterativo (I)

[Esta é unha tradución autorizada de Ciención de Breogán, adaptada do artigo orixinal de 13 de decembro de 2010 Teoría 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, dispoñible aquí.]

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

Cárcere

No último artigo da serie vimos o dilema ao que se enfrontaban dous (presuntos… a ver se vou acabar eu no caldeiro por prexulgalos) criminais moi perigosos chamados Anny e Albert. Un dos aspectos máis importantes daquel xogo era que soamente se xogaba unha vez. Ben, pois hoxe ímolo xogar de xeito repetitivo, a ver se o resultado cambia. (Pois claro que cambia! Se non, non lle dedicariamos un artigo…)

Aproveitaremos para aprender un concepto novo importantísimo, o equilibrio de Nash, e relacionaremos a serie aínda máis coa evolución e coa xenética. Dividiremos este artigo en dúas partes porque, se non, quedaría moi longo.

Como imos partir do dilema do prisioneiro, vamos lembrar a súa matriz de pagamentos para que non teñas de andar decote indo e volvendo daquel artigo.

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

Equilibrio de Nash

Como diciamos, un dos aspectos máis importantes do dilema do prisioneiro é que se xoga só unha vez. Non hai posibilidade de cambiar de estratexia, nin de castigar na quenda seguinte, nin nada: decides unha vez e acabouse.

Pois agora imos deixar que os xogadores xoguen a este xogo un número moi grande de veces (se son infinitas, o xogo non cambia substancialmente pero é máis difícil explicalo, así que imos deixalo en «moitas»). En cada unha destas moitas (infinitas) veces, cada xogador pode decidir Delatar ou Calar. Á fin do xogo súmanse os anos de condena e, obviamente outra vez, o obxectivo é cumprir o mínimo tempo de condena total posible.

Estiven tentado de ofrecer a posibilidade de que xogásedes os lectores, pero o único xeito que se me ocorría era pedirvos que me enviásedes un programiña en C ou algo así, para despois facervos xogar en parellas unha morea de veces nalgún tipo de liga. Como pensei que eran demasiados deberes para obrigarvos a facelos na casa, finalmente preferín contarvos directamente a conclusión.

Equilibrio de Nash: é un array de decisións dos xogadores (é dicir, unha casa da matriz de pagamentos) tal que ningún dos xogadores mellora se cambia a súa estratexia (mantendo invariables as dos demais participantes). Nótese que, consonte a definición, non é preciso que empeore; é abondo con que non mellore.

 

O dilema do prisioneiro iterativo ten un equilibrio de Nash: ambos os dous Delatan. Vexámolo paseniño. Imos representar como AnnyC o feito de que Anny escolla Calar, e do mesmo xeito teremos AnnyD, AlbertC e AlbertD.

  • Se estamos en (AnnyC, AlbertC), con recompensa (−1, −1), e ambos a dous fan o mesmo unha e outra vez (lembremos que é un xogo iterativo: xogan moitas veces, unha detrás de outra), Anny pode decatarse de que, se ela decide D, o seu pagamento vai ser cero (é dicir, mellora). Así que Anny, ante unha situación (AnnyC, AlbertC), cambiará a (AnnyD, AlbertC). Por suposto, Albert pode facer a mesma reflexión: ante unha situación (AnnyC, AlbertC) cambiará a (AnnyC, AlbertD), porque el pasa de −1 a 0. Polo tanto, (AnnyC, AlbertC) non é un equilibrio de Nash: aínda que o opoñente non mude de estratexia, calquera deles gana se cambia.
  • Se estamos en (AnnyC, AlbertD), con recompensa (−10, 0), Anny decatarase de que, se ela tamén Delata, pasando a (AnnyD, AlbertD), a súa recompensa mellora desde −10 a −6. Polo tanto, (AnnyC, AlbertD) non é un equilibrio de Nash.
  • Podemos facer unha análise semellante para (AnnyD, AlbertC), que tampouco é un equilibrio de Nash.
  • Se estamos en (AnnyD, AlbertD), con recompensa (−6, −6), Anny non quererá cambiar a (AnnyC, AlbertD) porque a súa recompensa empeoraría de −6 a −10. Ocorreralle o mesmo a Albert, que tampouco quererá pasar a (AnnyD, AlbertC). Polo tanto, (AnnyD, AlbertD) si é un equilibrio de Nash.

Todos os puntos que non sexan equilibrios de Nash son inestables: ao menos un xogador estará tentado de cambiar e volver ao equilibrio de Nash.

Algúns xogos teñen máis dun equilibrio de Nash; máis adiante veremos algún, pero polo de pronto imaxinade unha matriz de recompensas na cal decisións diferentes teñan o mesmo pagamento. Porén, non todos os xogos teñen de ter un equilibrio de Nash.1

O equilibrio de Nash e a estratexia dominante que vimos no capítulo anterior son dúas das ferramentas máis empregadas para analizar xogos infinitos, nos cales non podemos percorrer o camiño inverso desde as recompensas ata as decisións (existe un tercer concepto para isto, pero aínda non chegamos a el).

De calquera xeito, é o equilibrio de Nash o máximo ao que podemos aspirar? Na segunda parte, máis.

[O seguinte artigo da serie é Teoría de xogos (XVI): Dilema do prisioneiro iterativo (II).]


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


1. Isto soamente é certo se consideramos unicamente estratexias puras. John Nash demostrou que, se consideramos estratexias mixtas, cousa que aínda non vimos, si pode demostrarse que todos os xogos teñen un equilibrio de Nash. Porén, como polo de pronto estamos supondo implicitamente estratexias puras e aínda non chegamos a ver as estratexias mixtas, ímolo deixar así.

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 )

Conectando a %s