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.

Seguir lendo

Advertisements

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

Seguir lendo

Teoría de xogos (XIV): Dilema do prisioneiro

[Esta é unha tradución autorizada de Ciención de Breogán, adaptada do artigo orixinal de 29 de novembro de 2010 Teoría de juegos XIV – Dilema del prisionero, 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 (XIII): Xogo do ditador.]

Bóla

Ao longo da serie xa vimos xogos finitos e xogos infinitos.

Xa vimos que un xeito de atopar unha estratexia óptima para os xogos finitos era facer o camiño inverso desde as follas, subindo pola árbore de decisión, ata a decisión inicial (ou empregando a indución, se era posible). Aquí empregamos «unha» e non «a» intencionalmente, porque xa vimos que, cando dicimos «óptima», hai que dicir con relación a que. Tamén vimos, durante a discusión do xogo do cempés, que a estratexia que propuñamos non acababa de encaixar cos resultados empíricos. E ademais os empíricos eran mellores!

No futuro, dedicaremos máis artigos a enumerar e formalizar eses procedementos para atopar os óptimos, pero antes queremos dedicar un par de artigos (ou seica algún máis) a introducir algunha cousa máis e, de camiño, atopar estratexias para os xogos infinitos.

Para isto partiremos dun xogo que, por pouco que escoitases falar de teoría de xogos, seguro que oíches algunha vez: o dilema do prisioneiro.

Seguir lendo

Teoría de xogos (IV): Pedra, papel ou tesoiras

[Esta é unha tradución autorizada de Ciención de Breogán, adaptada do artigo orixinal de 13 de setembro de 2010 Teoría de juegos IV – Piedra, papel, tijera, 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 (III): A poxa do dólar (II).]

No artigo de hoxe desta serie dedicada á teoría de xogos, imos presentar un xogo moi sinxelo para irmos introducindo algúns conceptos.

Supoño que todos xogamos algunha vez a pedra, papel ou tesoiras. Polo si ou polo non, imos resumir as regras:

  • Xogan dous xogadores. Poden xogar máis, pero iso pode dar lugar a círculos de vitoria e é máis difícil decidir o que facer en caso de empates parciais.
  • Ambos os xogadores sacan a man asemade, cun dos símbolos seguintes:
    • Pedra: o puño cerrado.
    • Papel: a palma estendida.
    • Tesoiras: os dedos índice e maior estendidos e separados (coma unhas tesoiras abertas) e o resto dos dedos cerrados.
  • A vitoria decídese do xeito seguinte:
    • A pedra gana (machuca) ás tesoiras.
    • As tesoiras ganan (cortan) ao papel.
    • O papel gana (envolve) á pedra.
  • Se dous xogadores sacan o mesmo, empatan. Dependendo do obxectivo do xogo, poden volver xogar ou simplemente empataron e xa está (segundo o que queira conseguirse co xogo).

Pedra-Papel-Tesoiras
Esquema de «pedra, papel ou tesoiras». [Tradución. Fonte orixinal: Enzoklop, CC BY-SA 3.0]
Seguir lendo