Teoría de xogos (XXIV): A guerra de sexos (II)

[Esta é unha tradución autorizada de Ciención de Breogán, adaptada do artigo orixinal de 25 de abril de 2011 Teoría de juegos XXIV – La guerra de sexos (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 (XXIII): A guerra de sexos (I).]

No último artigo quedamos coa gana de ver como se solucionaba a guerra de sexos entre Ana e Alberte… pois ben, vamos alá.

ParellaComezamos lembrando a matriz de pagamentos que propuxeramos:

Ana
Gusta Odia
Alberte Gusta 1, 1 3, 2
Odia 2, 3 0, 0

Se non tes fresco aquel primeiro artigo, convén que o refresques.

Solución Maximin

Se ambos os xogadores aplicaren unha estratexia Maximin, Alberte escollerá Tenis e Ana escollerá Discoteca. Non imos contar como chegamos a esa conclusión porque a estratexia Maximin xa a contamos antes. Se alguén quere resolvelo como exercicio nos comentarios, será benvido; se non, que o resolva cada un na cabeza.

O caso é que ambos os dous cobran 1, polo que non semella unha solución moi boa, non si? Ben, xa dixemos que Maximin era unha estratexia conservadora… Ademáis, é unha situación inestable: calquera dos dous mellora se cambia a súa decisión.

Equilibrio de Nash en estratexias puras

Neste xogo existen dous equilibrios de Nash en estratexias puras: (Tenis, Tenis) e mais (Discoteca, Discoteca). Novamente, se non tes claro por que eses son equilibrios de Nash, revisa o artigo correspondente e resólveo como exercicio nos comentarios se queres.

Seguir lendo

Advertisements

Teoría de xogos (XXIII): A guerra de sexos (I)

[Esta é unha tradución autorizada de Ciención de Breogán, adaptada do artigo orixinal de 18 de marzo de 2011 Teoría de juegos XXIII – La guerra de sexos (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 (XXII): «Stock options».]

O concepto que imos introducir hoxe xa apareceu moitas veces ao longo da serie, pero nunca lle puxemos nome explicitamente. Coma sempre, imos aproveitar para propor un xogo, analizalo empregando moitos dos conceptos que xa vimos e, polo camiño, explicar un novo: a asimetría.

O xogo que imos analizar hoxe é o da guerra de sexos.

A guerra de sexos existe desde sempre. [Fonte: Flickr de tnarik]
Ana e mais Alberte, que andan a facerse as beiras mutuamente, quererían coincidir na actividade desta tarde. Pero ao mesmo tempo cada un ten gustos diferentes, así que lles gustaría coincidir… pero na actividade que lle gusta a cada un. Por se máis adiante caes na tentación: non, non poden coordinarse previamente.

Vexamos cal é a matriz de recompensas.

Ana
Tenis Discoteca
Alberte Tenis 3, 2 1, 1
Discoteca 0, 0 2, 3

Cada un deles pode decidir ir ao Tenis ou á Discoteca. En cada cela da matriz pomos primeiro o pagamento de Alberte e logo o de Ana. Como diciamos, ambos a dous están a cortexarse mutuamente, así que o seu maior pagamento é cando coinciden na escolla (isto é, a diagonal da matriz). Pero claro, se coinciden facendo o que quere Alberte, el gana un pouquiño máis (3), mentres Ana gana moito pero non o máximo (2). Temos unha situación semellante se coinciden na discoteca.

Seguir lendo

Teoría de xogos (XX): Os tenistas (II)

[Esta é unha tradución autorizada de Ciención de Breogán, adaptada do artigo orixinal de 7 de febreiro de 2011 Teoría de juegos XX – Los tenistas (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 (XIX): Os tenistas (I).]

Cuncos
Vamos buscar o fondo…

No artigo anterior puxemos a Ana e a Alberte a xogar ao tenis e acabamos descubrindo que non tiñan unha estratexia pura que fose dominante, así que propuxemos unha estratexia mixta. Deste xeito, no canto de decidir sistematicamente unha das opcións, facíano cunha probabilidade p.

Contamos que John Nash demostrara que todos os xogos teñen, ao menos, un equilibrio de Nash en estratexias mixtas, pero que empregou unha demostración non construtiva, de maneira que non proporcionaba un método para achar ese equilibrio. Neste artigo veremos unha aproximación para atopar unha estratexia empregando o método do gradiente e veremos como interpretar ese método desde o punto de vista da teoría de xogos.

Método do gradiente

Se ben probablemente algúns dos nosos lectores coñecerán o método do gradiente, imos dedicarlle unhas alíneas polo ben daqueles que non o coñezan.

Seguir lendo

Teoría de xogos (XIX): Os tenistas (I)

[Esta é unha tradución autorizada de Ciención de Breogán, adaptada do artigo orixinal de 24 de xaneiro de 2011 Teoría de juegos XIX – Los tenistas (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 (XVIII): Escándalo de corrupción.]

Tenis

Case desde o comezo desta serie fomos propondo xogos, introducindo conceptos sinxelos sobre a teoría de xogos e aplicándollelos a eses xogos, e fomos perfeccionando o noso coñecemento dos xogos que estudabamos.

Hoxe imos introducir o concepto de estratexias mixtas e para isto imos convidar a Ana e mais Alberte a xogar ao tenis.

Sempre que lin algunha cousa verbo deste xogo ou algunha variación, foi con xogadores de béisbol que teñen de decidir se guindan unha bóla rápida ou unha lenta. Pero, como en España case non hai tradición beisboleira e nin sequera sei o que diferencia unha bóla rápida dunha lenta (supoño que unha irá a máis velocidade ca a outra, pero non sei como afecta iso), nós imos facer o xogo con tenistas.

Por suposto, non imos escribir un tratado sobre tenis (entre outras cousas porque, ademais, son bastante malo xogando), pero si imos empregar a súa terminoloxía para darlle cor ao artigo. Se ben espero que poidas seguir o texto sen problema ningún malia non coñeceres o argot tenístico, podes botarlle unha ollada á Galipedia ou ir ver algún partido e logo volver aquí.

Seguir lendo

Teoría de xogos (XVIII): Escándalo de corrupción

[Esta é unha tradución autorizada de Ciención de Breogán, adaptada do artigo orixinal de 10 de xaneiro de 2011 Teoría de juegos XVIII – Escándalo de corrupción, 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 (XVII): A caza do cervo.]

Hoxe empregaremos novas de actualidade para seguir avanzando na nosa serie de Teoría de xogos: un escándalo de corrupción.1 Veremos como se enfrontan a un escándalo de corrupción dous partidos políticos e como escollen a súa mellor acción utilizando a teoría de xogos.

Concello de Hamburgo

Aproveitaremos o xogo para presentar un par de conceptos novos, Maximin e Minimax, e veremos como estivemos empregándoos de xeito implícito ao longo da serie.

A situación é a seguinte: sorprendentemente, a un alcalde electo collérono aceptando subornos dun contratista (non sei se o sorprendente é que os aceptase ou que o collesen; que cada quen escolla). O asunto aínda non se fixo público, pero tanto o partido no poder (o Partido Laranxa ou PL) como a oposición (o Partido Amarelo ou PA) xa o coñecen e poden escoller entre tres opcións:

  • Condenar o asunto enerxicamente.
  • Ficar Calados, nin confirman nin desmenten.
  • Defender a actuación do alcalde.

Ademais, as eleccións están moi cerquiña, así que a posición que tome cada partido ante este asunto pode ser determinante. Nós tomaremos a posición do Partido Laranxa.

Seguir lendo

Teoría de xogos (XVII): A caza do cervo

[Esta é unha tradución autorizada de Ciención de Breogán, adaptada do artigo orixinal de 3 de xaneiro de 2011 Teoría de juegos XVII – La caza del ciervo, 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 (XVI): Dilema do prisioneiro iterativo (II).]

Antes de avanzarmos máis, imos presentar un xogo novo, intimamente relacionado co dilema do prisioneiro que viamos antes e que moitos consideran a mellor forma de modelar a cooperación social. O xogo chámase a caza do cervo.

Cervo
De verdade queres cazalo? [Fonte: Pixabay, dominio público]
Serviranos para afianzar os conceptos de equilibrio de Nash e estratexia dominante, e tamén para introducirmos un concepto novo: a suma cero.

O xogo di algo así: temos dous lobos, Rómulo e mais Remo, que poden decidir ir cazar un Coello ou cooperaren para cazar un Cervo.

Se un deles decide cazar un Coello, come. Non é festín ningún, pero vaia, come. Se ambos a dous deciden ir xuntos cazar un Cervo, aquilo é unha lupanda. Non soamente comen, senón que ademais obteñen enerxías sobrantes que poden dedicar a, por exemplo, a reprodución.

Pero, se un deles decide ir polo Cervo e o outro vai polo Coello, quen decidiu ir polo Cervo queda sen nada, porque el só non é quen a cazalo (porén, o seu «amigo», que foi polo Coello, si come).

Seguir lendo

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

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