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.

Por unha banda, cada un dos equilibrios de Nash é «inxusto»: un dos xogadores gana máis ca o outro. Se Ana tiver a mala sorte de caer no equilibrio (Tenis, Tenis), ela sempre ganará 2. Alberte estará contentísimo, pero Ana… Sempre lle quedará a espiña de non saír ganando tanto como ela querería.

Pola outra banda, son… como chamalo?… «equilibrios inestables»: se un dos xogadores, mesmo contra o seu propio interese, cambia, o outro está «obrigado» a cambiar tamén.

Exemplo: están en (Tenis, Tenis), cobrando (3, 2). Ana decide «facer un farol» e pasar a (Tenis, Discoteca), cobrando (1, 1), incluso contra o seu interese. Se Ana sostén o seu farol, a mellor solución para Alberte é pasar a (Discoteca, Discoteca), pasando a cobrar (2, 3). Pero claro, entón pode ser Alberte quen «faga un farol» pasando a (Discoteca, Tenis). Que fará Ana?

Logo cal é o risco? Que ambos «fagan un farol» e sosteñan o estado (Tenis, Discoteca), cobrando (1, 1).

Equilibrio de Nash en estratexias mixtas

Como xa avanzamos moito na serie, sabemos que unha alternativa é empregar estratexias mixtas. Se tentamos un método do gradiente como fixemos no xogo dos tenistas, veremos que non se acada unha solución. Isto é algo que poderiamos deducir nós, pois que tanto (Tenis, Discoteca) como (Discoteca, Tenis) son dous pozos da curva, e ambos son igual de profundos.1 Se tentarmos aplicar un método de gradiente nunha curva que ten dous pozos, e ambos iguais… ás veces caeremos nun, outras noutro, outras veces iremos saltando… Se lembrades o artigo dos tenistas, engadiamos «ruído» para provocar saltos na bóla que, nalgún momento, nos sacasen dun mínimo local e nos levasen a un mínimo global. Pois ben, podemos comparar este ruído cos «farois» que fan o un e a outra para obrigar a cambiar. Pero aquí non existe un mínimo local e outro global: ambos os mínimos son igual de importantes. Resumindo: que este procedemento non nos leva a ningures.

Isto non debería sorprendernos, xa que as estratexias puras non son máis ca un caso particular das mixtas.

Así que, como descubrimos o outro equilibrio de estratexias mixtas? Mellor dito, existe algún outro equilibrio en estratexias mixtas? Pois si, existe.

Neste punto vou facer un pouquiño de trampa. Primeiro vouche presentar resultados numéricos, para que vexas de xeito obvio que ese equilibrio existe, e logo imos empregar ese coñecemento para resolvelo de forma analítica.

Fixemos unhas follas de cálculo coa esperanza de pagamento dependendo da probabilidade de cada un de escolleren o que lles Gusta. Observa que son dúas follas: unha para o pagamento que recibe Alberte e outra para o pagamento que recibe Ana.

Pagamento Alberte

Pagamento Ana

Hai unha columna do pagamento de Alberte que nos é curiosa, é por iso que a resaltamos en azul. Resulta que hai unha estratexia de Ana para a cal Alberte recibe o mesmo pagamento (1,50) independentemente da probabilidade coa que el escolla. Curioso, non si? Evidentemente, dado que o xogo é simétrico, ocorre o mesmo cunha das filas do pagamento de Ana.

Pagamentos lecturaToma un minuto para volver mirar eses cadros, porque é doado non decatarse do seguinte detalle: cando está decidindo Alberte, o cadro que debemos mirar é o de Alberte, e cando está a decidir Ana, o de Ana. Polo tanto, no primeiro cadro (o de Alberte) moverémonos sempre en vertical, cara arriba ou cara abaixo. Consecuentemente, no segundo cadro (o de Ana) moverémonos sempre en horizontal.

Así que se, polo motivo que fose, Alberte escollese unha estratexia 0,75 e Ana escollese unha estratexia 0,75, estariamos na posición (0,75, 0,75) e o pagamento sería 1,50 para cada un. Se Alberte se movese en vertical, modificando a súa estratexia mixta… melloraría o seu pagamento? Non, seguiría a ser 1,50. E se Ana se movese en horizontal no seu cadro? O mesmo, seguiría cobrando 1,50. Xustamente esa é a definición dun equilibrio de Nash!2 (0,75, 0,75) é un equilibrio de Nash!

E… Que casualidade… Ambos os valores coinciden, son o mesmo número, 0,75… Será casualidade? Pois non, non tal. Isto é o que se chama equilibrio simétrico e está demostrado que calquera xogo simétrico ten un equilibrio simétrico en estratexias mixtas.3

Como atopamos ese punto de xeito analítico? Cando xa vimos os cadros, é doado. Soamente temos de decatarnos de que, por exemplo para Ana, cando estamos por riba da liña azul, os seus pagamentos medran cando se move cara á dereita, e cando estamos por baixo da liña azul, os seus pagamentos medran ao nos movermos cara á esquerda. Unha vez máis, o concepto de derivada, que xa empregamos antes.

Se existen filas onde a derivada é positiva e filas onde a derivada é negativa, existe necesariamente unha fila onde a derivada é nula (que é xusto o que andamos a procurar).

Así que podemos chamar pAnaG á probabilidade de que Ana escolla o que lle Gusta (e do mesmo xeito definimos pAlbG). Logo calculamos a esperanza do pagamento para Ana da forma seguinte:

eAna(pAnaG, pAlbG) = 1 · pAlbG · pAnaG + 2 · pAlbG(1 − pAnaG) + 3(1 − pAlbG) · pAnaG

Podemos calcular a súa derivada con relación a pAnaG:

eAna′(pAnaG, pAlbG) = 1 · pAlbG − 2 · pAlbG + 3 − 3 · pAlbG

Sabemos que, na liña azul, esa derivada é cero, así que igualamos a derivada a cero, resolvemos a ecuación e sáenos:

pAlbG = 0,75

Podemos facer un procedemento análogo con eAlb(pAlbGpAnaG) para obter a columna azul do primeiro cadro.

No caso xeral, no que os pagamentos sexan

Ana
Gusta Odia
Alberte Gusta C, C A, D
Odia D, A B, B

a fórmula do punto de equilibrio é \frac{A-B}{A+D-B-C}.

É un bo equilibrio? Pois non, non moito. Podemos fixarnos nos outros dous equilibrios, os de estratexias puras, que semella que non nos gustaban porque un ganaba menos ca o outro. Vemos que, naqueles, incluso quen menos gana dos dous, gana 2 (e o outro gana 3). E, neste outro equilibrio, ambos os dous ganan 1,5…

E iso como é posible? É posible porque, nos outros casos, tanto (Gusta, Odia) como (Odia, Gusta), sempre escollían o mesmo. É verdade que un deles non ganará tanto como podía, pero aínda así… Pola contra, neste caso, ambos escollen ao chou, cun 75 % de probabilidades de elixiren o que a eles lles gusta. Iso implica que, ás veces (cunha probabilidade nada desdeñable) escollerán (Gusta, Gusta) ou incluso (Odia, Odia), o que fai que baixe moito a media. É o que se chama un equilibrio ineficiente. Nin sequera é que un gane máis ca antes e o outro menos, é que os dous ganan menos ca antes.

Pero é que, ademais, se os outros equilibrios nos semellaban inestables, porque alguén podería tentar facer un farol… aquí é aínda máis inestable. Abonda con que un deles se afaste minimamente do 0,75 para que a tendencia natural sexa incrementar aínda máis esa desviación, acabando novamente en (Gusta, Odia) ou en (Odia, Gusta), dependendo de cara a onde fose a desviación inicial. Un exemplo: se no canto de (0,75, 0,75) están en (0,80, 0,75), o pagamento é (1,50, 1,45). Pero agora Ana xa sae ganando se reduce a súa pAnaG, así que a reducirá ata chegar a pAnaG = 0 (que é onde máis gana ela, concretamente 1,60), e entón Alberte aumentará a súa pAlbG ata chegar a 1. É dicir, a estratexia pura (Gusta, Odia).

Por se alguén estaba a preguntalo: este é o motivo polo que o método do gradiente non atopa este equilibrio. Agás que esteamos exactamente en (0,75, 0,75), o gradiente tenderá a afastarse, non a achegarse. Isto sucede porque este equilibrio non está nun máximo, senón nun punto arbitrario.

Ao longo da serie algún lector puido confundir, probablemente polo xeito no que fomos explicando as cousas, a idea de que un punto sexa un equilibrio de Nash co feito de que sexa a mellor estratexia. A miúdo é verdade que os equilibrios son a mellor estratexia (ao menos para algunha das definicións de «mellor»), por exemplo en «pedra, papel ou tesoiras»… pero non sempre. Como demostración, neste caso temos 3 equilibrios posibles e non poden ser todos a mellor estratexia asemade; logo non pode ser certo que ser un equilibrio de Nash equivalla a ser a mellor estratexia.

Estratexia mixta máxima

Aínda podemos mellorar. Ana e Alberte poden saber moito de teoría de xogos e saber que, como vimos máis arriba, todo xogo simétrico ten un equilibrio simétrico en estratexias mixtas. Así que poderían autolimitarse a procuraren estratexias simétricas. É dicir: estratexias nas que pAlbG = pAnaG. Chamaremos a isto p para abreviar.

Isto significa que nos estariamos movendo pola diagonal dos dous cadros que viamos antes e, pois que o xogo é simétrico, esa diagonal é a mesma para ambos os cadros. Ou dito doutro xeito: podemos reducir esas funcións, que eran de dúas dimensións e cun resultado composto por dous valores,4 a unha función dunha soa dimensión e cun único resultado que se lles aplica aos dous, Alberte e mais Ana:

e(p) = p · p · 1 + p · (1 − p) · 3 + (1 − p) · p · 2 + (1 − p) · (1 − p) · 0 = −4p2 + 5p

Podemos debuxar esta curva, que ten a seguinte forma:

Se queremos atopar de xeito analítico o máximo, podemos simplemente derivar e igualar a cero, como faciamos cando estabamos na escola, e atoparemos que o máximo é para p = 5/8 = 0,625, o que nos dá unha esperanza de 1,56.

Non esquezamos que o xogo é simétrico e estamos movéndonos pola diagonal, así que ambos deben escoller o que lles gusta cunha probabilidade 0,625 e obterán un pagamento esperado de 1,56.

Fíxate nisto: se un dos dous cedese e sempre fixese o que quere o outro, obtería un pagamento de 2 (e ademáis a súa parella obtería un pagamento de 3). Pero, se ambos aplican a máxima estratexia mixta simétrica, ambos a dous cobran 1,56 de media. Algo ganamos con relación ao equilibrio do (0,75, 0,75) de antes, pero non moito. E ademais, se aquel era un equilibrio inestable e iso nos amolaba… é que este nin sequera é un equilibrio.

Cooperación

Aínda che estraña que levemos tentando resolver esta guerra de sexos desde que aprendimos a camiñar ergueitos?

Menos mal que a reprodución é un incentivo forte para chegar a un entendemento, porque se non…

Malia que inicialmente dixésemos que o xogo non permite a coordinación previa á decisión, non che sorprenderá se dicimos que a única solución satisfactoria é romper as regras e negociar, indo a metade das veces a cada sitio de xeito coordinado.5

A isto chámaselle xenericamente xogo de coordinación. O xogo de coordinación clásico e paradigmático é a escolla do sentido da circulación (por exemplo, en España estamos afeitos a conducir pola dereita, mentres no Reino Unido conducen pola esquerda). Dous condutores poden decidir ir cada un deles pola dereita ou pola esquerda:

Condutor B
Esquerda Dereita
Condutor A Esquerda 0, 0 −100, −100
Dereita −100, −100 0, 0

Se ambos coinciden na escolla, todo perfecto. Se non coinciden, acaban chocando.

Existen tres equilibrios neste xogo: os dous de estratexias puras (Esquerda, Esquerda) e (Dereita, Dereita) e outro de estratexia mixta no que os condutores elixen cun 50 %. Este último é obviamente peor ca os outros dous, pero en realidade non hai, desde este punto de vista, nada que diga que (Esquerda, Esquerda) ou (Dereita, Dereita) sexa mellor un ca o outro, así que a lei determina unha forma de xeito arbitrario e fóra.

Cal sería o equivalente á lei no noso exemplo da guerra de sexos? Pois a propia evolución. Xa o dixemos ao estudarmos os algoritmos xenéticos no dilema do prisioneiro iterativo: se non cooperamos, dificilmente sobreviviremos como especie. Ou, dito doutro xeito: «a reprodución é un incentivo forte para chegar a un entendemento» (iso xa o dixen, non si?)… Ou hai algunha solución máis?

Xan

Como dicía un amigo, parafraseando un refrán sobre motoristas: «só hai dous tipos de homes: os que saben que son uns xans e os que non o saben».

Ídesme permitir este toque de humor sexista para explicar a modificación máis habitual do xogo: un dos xogadores rompe a simetría. Se un deles en realidade prefire a súa actividade máis ca a compaña do outro, a matriz pode semellarse a estoutra:

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

É dicir, Ana si que quere ir con Alberte… pero Gústalle máis ir á Discoteca, aínda que sexa soa, que ir ao Tenis, aínda que sexa con Alberte.

Agora o xogo xa non é simétrico e o único equilibrio en estratexias puras é (Discoteca, Discoteca).

Se estivesen en (Tenis, Tenis), Ana cambiaría a Discoteca, pero non para «facer un farol» como viamos antes, senón porque realmente ela sae ganando, así que non ten incentivo ningún para tornar ao Tenis, e Alberte acabará cedendo e cambiando tamén a Discoteca. E a Alberte non lle vale para nada «facer un farol» porque, se volver a (Tenis, Discoteca), Ana xamais cambiará a (Tenis, Tenis).

Coidado: que sexa o único equilibrio en estratexias puras non quere dicir que sexa o único equilibrio.

Pode existir outro equilibrio en estratexias mixtas, porque non todos os posibles valores da asimetría levan a que (Discoteca, Discoteca) sexa o único equilibrio. Non imos demostralo, pero si o imos indicar por completude. Nun xogo de coordinación, se a matriz ten a forma xenérica

Ana
Gusta Odia
Alberte Gusta C, c A, a
Discoteca D, d B, b

entón existe un equilibrio de Nash en estratexias mixtas no punto definido por:6

pAlbG=\frac{d-b}{a+d-b-c}pAnaG=\frac{A-B}{A+D-B-C}

Estes foron un par de artigos duros, e ademais semella que a concusión nos deixa un sabor agridoce: por máis que analizamos, non acabamos de atopar unha solución satisfactoria… Pois si… real coma a vida mesma. Ás veces non podemos atopar unha solución boa e temos de nos conformar cunha solución non demasiado mala.

[O seguinte artigo da serie é Teoría de xogos (XXV): Os piratas democráticos.]


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


1. En realidade son máximos e o que buscamos é maximizar, pero éme máis sinxelo seguir empregando a comparación da bóla que está buscando o fondo do cunco.

2. Lembremos que non cómpre empeorar, abonda con non mellorar.

3. Ou poida que máis dun, por exemplo se a matriz de pagamentos non ten só dúas decisións coma a nosa.

4. O que se chama un resultado vectorial.

5. Ollo: isto non é o mesmo ca dicir p = 0,5 no caso da decisión simétrica do epígrafe anterior.

6. Se comparas coa fórmula que vimos antes, verás que aquela é unha particularización desta cando hai simetría.

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