Pactos y Documentos

Parece que la pactologia de la semana que viene va a pivotar sobre el documento de acuerdo PSOE-Ciudadanos, que afortunadamente gracias a Echenique ya es el mismo en las webs de ambos partidos (un pdf de 67 folios, uno mas que en los docs anteriores). Seria interesante poder comparar su compatibilidad con:

(No se ha filtrado cual era el documento exacto de partida de la negociacion a cuatro PSOE-Podemos-Compromis-IU ¿no? Existe un documendo del PSOE de partida del dia 8, titulado “programa para un gobierno progresista y reformista”)

Aparte de los discursos oficiales, una vez acabado el alboroto tenemos el tiroteo “8 razones” (u 8 incompatibilidades) y “8 sinrazones” (PDF) en el tiroteo entre PSOE y Podemos. Aqui el problema es que no existe online el documento original al que supuestamente contesta el PSOE, tan solo una nota de prensa de Europa Press.

El sabado 27 el PSOE redacta un documento en cinco partes, que distribuye el lunes bajo el titulo “Medidas programáticas compartidas con…”

Otra referencia interesante, quizas incluso más que el programa electoral de Podemos, es su lista de ICPs, en el sentido de que es el programa “de las bases”. Por supuesto puestos a bucer podriamos ir hasta la 15m-pedia y sus listas de propuestas, pero la cosa ahora va sobre la negociacion actual -o su imposibilidad-.

Politicos y Equilibrios de Negociación

Al hilo de la eleccion de presidente del gobierno, han salido dos articulos sobre teoria de juegos en la prensa: “Sanchez y la teoria de juegos“, de Fernando Garea, y “¿Por qué la teoria de juegos predice que Sanchez será presidente?”, de Daniel Sarasa. Sin entrar en el fondo ni en los objetivos de cada articulo -no son inocentes, pues estan todavia las negociaciones en marcha-, queria apuntar lo complejo que resulta la nomenclatura en este area.

Un primer problema es la definicion de “equilibrio de Nash”, sobre todo porque depende de si se parte de literatura evolutiva moderna, donde buscan el equilibrio de poblaciones o de literatura matematica clasica, donde buscan la solucion de juego no iterado. Y la propia definicion de estrategia cambia cuando el juego se itera.

En general, hay un punto de equilibrio de Nash cuando cada jugador individual no gana nada modificando su estrategia mientras los otros mantengan las suyas. Esta es la definicion que da Sarasa (“nada que ganar si cambia”) y es sutilmente diferente de la definicion de Garea (“cualquiera empeora su posicion”) pero es una sutilidad necesaria para que funcionen algunos teoremas de existencia. Y desde luego no coincide con el remark que añade Jose Carlos Diez al final del articulo de Garea, y que seguramente corresponde a un caso concreto de un juego determinado.

Conviene recordar que la existencia de equilibrio depende del  tipo de juego. Con dos jugadores, asumiendo pagos simetricos -que no tiene por qué ser el caso- hay 14 juegos, como ya expliqué dos posts más atras.

image (1)

En aquel post estaba preocupado de calcular el equilibrio simetrico de Nash en los juegos con T>R y S>P, porque es el mas complicado al estar asociado a una estrategia mixta, asi que me olvide repasar los otros cuadrantes. Veamos que pasa:

Juegos con T>R, S<P: Dilema del Prisionero.

Este es el caso mas analizado. La situacion en la que ambos jugadores colaboran (jugada C, en la notacion tradicional) les permitiria cobrar R, pero si un jugador opta por jugar C el otro puede jugar D cobrando asi una cantidad T>R. Asi que la situacion en la que ambos colaboran no es un equilibrio de Nash. En cambio sí lo es la situacion en la que ambos juegan D, porque si uno esta ya en defeccion el otro no gana nada colaborando.

(Un problemilla con la nomenclatura en Dilema del Prisionero es que la jugada “colaborar con la policia” es la jugada D. Hay veces que el que lo explica se lia por utilizar “colaborar” tanto para la operacion de colaborar con el otro jugador como con la de traicionarlo.)

Juegos con T<R, S>P

Aquí la jugada C en ambos, colaborar para cobrar R, sí que es un equilibrio de Nash, porque nadie va a mejor cambiando a D; el pago de Traicion es menor que la Recompensa. Y por  el contrario, la jugada (D,D), con pago P para ambos, no es equilibrio, porque cualquiera de los dos sale ganando en pasar a C: el pago de (D,C) para el que Colabora es S, que es mayor que P.

Hay cinco juegos de este tipo, y de ellos dos casos son un poco paradojicos: cuando S>R le resultaria posible a un jugador obtener mayor beneficio… ¡si convenciera al otro para que le traicionara! Naturalmente el otro jugador no lo va a hacer porque el pago de la traicion, T, es menor que el de la colaboracion, R.

Juegos con T<R, S<P

En este caso hay dos equilibrios de Nash: o bien ambos juegan C, o bien ambos juegan D.  Si ambos estan jugando C no hay beneficio para un jugador en cambiar a D, porque pasaria a cobrar T que es menor que R. Y si ambos estan jugando  D no hay beneficio para un jugador en pasar a C, porque el pago S es menor que P.

Asi que la paradoja en este cuadrante es que si los dos jugadores estan por algun motivo jugando ambos D, estan cobrando menos que si ambos jugaran C pero no pueden cambiar su situacion si no se ponen de acuerdo para hacerlo ambos a la vez.  En un juego de una sola tirada seguramente ambos escogerian el equilibrio de recompensa dominante, pero durante una negociacion se pueden quedar atascados en el equilibrio de Nash que menos les conviene. Tambien es tipico encontrarse en este atasco evolutivamente, en juegos iterados.

Queda un cuadrante…

¿Y no hay algun juego donde el equilibrio de Nash sea (C,D) o su reciproco? Para que el jugador que esta jugando D no tenga nada que ganar, habria que pedir T > R. Y Para que el jugador que esta jugando C no tenga nada que ganar, habria que pedir S > P. Ese es el cuadrante para el que, hace dos posts, estuvimos calculando las estrategias mixtas y por su asimetricidad ignoramos la existencia de estas estrategias puras. En situacion de negociacion si que seria posible que los negociadores evolucionaran hacia un equilibrio de Nash con jugada asimetrica.

En este ultimo cuadrante si los negociadores llegan a estos equilibrios de Nash asimetricos la situacion es mas de envidietas que de paradojas. A no ser que el juego este en la linea T=S, obviamente uno de los dos cobrara mas que el otro, aunque ninguno tenga nada a ganar cambiando de estrategia.  Me pregunto si es posible negociar para converger al equilbrio con estrategia mixta, que sí que es simetrico. Parece que las negociaciones deberian converger siempre a estrategias puras.

Nomenclaturas

La cuestion de la nomenclatura de los juegos puede ser especialmente importante en articulos como el de Sarasa donde parecia considerar la posibilidad de que durante una negociación cambie la matriz de pagos.  Asi, no es apropiado decir que el juego es un chicken o un dilema del prisionero si precisamente la idea es ir alterando los cebos, palos y zanahorias hacia una matriz donde la solucion de equilibrio sea la que garantice consiga el objetivo lateral buscado (no convocar elecciones, o nombrar determinado presidente). El problema es que no hay mucho acuerdo acerca de los nombres mas alla del cuadrante de Dilema del Prisionero. Tambien hay que tener en cuenta que muchos articulos estudian solo el cuadrado R=1, S=0, -1<S<1, 0<T<2, que solo contiene cinco juegos distintos, pero en algunos casos sus conclusiones valen para todo el cuadrante. Para colmo, si es posible iterar el juego, la situacion se subdivide, porque entonces hay coordinaciones imprevistas, turnismos a lo Canovas y Sagasta; por ejemplo el caso donde S+T > 2R crearia nuevas paradojas.

Por ultimo hay que considerar que los teoremas de existencia aflojan enseguida cuando la matriz de pagos no es simetrica.

 

Muerte y Soledad

Sigo con la cuestion del post anterior, la de optimizar el cosechado de recursos en un juego simetrico de dos jugadores. Esta optimización se podria hacer a partir de considerar efectos finitos, distintas update rules y demas casuistica de los juegos de evolución, dado que la “evolutionary game dynamics” es más rica que el caso estatico, por más que este aparezca como límite si se dan las condiciones adecuadas. Muy recomendable el review de Roca, Cuesta y Sánchez de 2009.

Si no mencionamos otra cosa, asumimos que se esta jugando en el cuadrante superior derecho: Snowdrift, etc. Esto es S >0, T>1, R=1, P=0



 

 

Habiamos visto que para un juego (1,S,T,0) la solucion mas conveniente es el equilibrio del juego que optendriamos al proyectar el punto T,S en la diagonal S=T.  Esto es obviamente el juego (1, (S+T)/2,(S+T)/2,0). Dicho de otra manera, tenemos que desplazar el juego una distancia Delta

\begin{pmatrix} 1 & S+\Delta \\ T-\Delta & 0 \end{pmatrix}

que sería \Delta= (T-S)/2 Una primera pista sobre tales desplazamientos la tenemos en el analisis de Ohtsuki y Nowak con juegos en grafos aleatorios. Si la diferencia S-T es bastante mayor que la recompensa R y el grafo tiende a tener muy poquitas interacciones de forma que su grado medio se aproxime a cero, entonces la estrategia optima se aproxima a la de acercar el juego a la diagonal. Eso ocurre para las tres “update rules” que estudian los autores: Pairwise Comparison, Imitation y Death-Birth

 


 

Una update rule que se limita a permitir a un solo competidor cada vez compararse con otro y modificar su posicion va a terminar generando una solucion mixed con p=1/2. Esto se ve facil. Hay :

  • una probabilidad p p de jugar C contra un C y por tanto preferir cambiar a D, porque T > 1
  • una probabilidad p (1-p) de jugar C contra un D y preferir quedarse, porque S >0
  • una probabilidad (1-p) p de jugar D contra un C y preferir quedarse, porque T > 1
  • una probabilidad (1-p) (1-p) de jugar D contra D y preferir cambiar a C, porque S > 0

asi que el equilibrio de la poblacion ocurre cuando p p = (1-p) (1-p), esto es cuando p=1/2.

Por otro lado, sabemos que esta solucion p=1/2 es la mas ventajosa cuando T+S es muy grande. Asi que hay cierta conexion, en el sentido de una ventaja evolutiva global, entre T o S grande en el cuadrante S>0, T>0  y utilizar reglas de update de grado de conectividad muy bajo, que fomenten p=1/2



(continuara en este mismo post)

Juegos simetricos: halcones,palomas y estrategias mixtas.

Siguiendo con el tema de la semana he pedido un par de reviews y me he metido un poco  más a fondo en teoria de juegos. Lo primero para no perderme ha sido el clasificar todos los juegos simetricos, de dos jugadores con dos posibles movimientos (C y D, Colaborar o Desertar) y cuatro posibles resultados: cobramos R si ambos colaboramos, S si Colaboramos pero el contrario Deserta, T en el caso reciproco, y P si ambos desertamos. En principio hay 24 posibles formas de ordenar los cuatro valores, y con el convenio R>P se reducirian a 12. La clasificación, incluyendo tambien juegos asimetricos, la hicieron en los sesenta Rapoport and Guyer (“A taxonomy of 2×2 games” , aunque es mas facil encontrar en la red una mas reciente de Robinson and Goforth del año 2005.

Podemos ver los distintos juegos sobre el plano T-S: Dado que tanto T como S pueden ser estar en tres posiciones respecto a P<R, tenemos nueve juegos:

                  |         ||
       Mixed      | Pure    ||
       Delight    | Delight ||       Hero
                  |         ||
------------------+---------++------------------S=R
  Mixed Harmony   | Harmony ||     Chicken
==================+=========++==================S=P
                  |         ||
     Coordination |  Stag   || Prisoner Dilemma
                  |  Hunt   ||
                 T=P       T=R

Además en los casos Coordination, Harmony y Hero puede que T sea mayor que S o lo contrario, lo que nos define, cortando esos sectores en diagonal tres juegos mas, y ya tenemos el total de 12. En el caso especial de R=P=0 es posible intercambiar T y S, y solo quedarian Hero, Coordination y Prisoner Dilema (o MD).

En la práctica se suele normalizar con P=0 y R=1, y estudiar un cuadrado con S en [-1 .. 1] y T en [0 .. 2], lo que captura esencialmente cinco juegos: Chicken, PD, SH, y los dos triangulos en los que se ha divido Harmony (a veces al triangulo inferior se le llama “No Conflict”). Esto se hace asi porque realmente las propiedades de equilibrio del juego pivotan sobre si S es mejor o peor resultado que P y si T es mejor o peor resultado que R. Esto es, alrededor del punto (T=1,S=0) en la normalizacion habitual.

El juego del “bote de una loteria de un solo numero” que hemos jugado en los dos post anteriores esta un poco fuera de la normalizacion: vemos que tiene la propiedad de que S=R=0,  llamando “Colaborar” al hecho de no comprar el billete (sí, suena raro, pero se trata de mantener el convenio R > P), P=bote/2 – ticket < 0, y T =Bote – Ticket > 0. Se trata pues de un caso limite de Chicken: cuando los dos jugadores compran billete, ambos pierden, al igual que cuando ninguno de los dos conductores del chicken gira para apartarse. La unica complicacion es que en esta normalizacion no podriamos estudiar bien el caso en el que el bote crece tanto que se hace mayor que dos veces el ticket, pero la verdad es que tampoco vamos a hacerlo; ya fue suficiente con dos posts sobre la loteria dichosa.

Lo que si que me interesa por encima de esta clasificacion es una circunstancia que puede marcar diferencias cuando el juego se plantea repetidas veces: los casos en los que a los dos jugadores les mereceria mas la pena pactar para ir llevandose alternativamente S + T en vez de R + R.  Esta linea S+T > 2R, o simplemente S+T > 2 en la normalizacion habitual, deberia tener algun efecto en la clasificacion, pero al no afectar para la construccion de los equilibrios de Nash tampoco afecta a las simulaciones con modelos evolutivos, al menos no en los casos mas comunes. Se podria decir que el juego no es capaz de explotar adecuadamente los “recursos naturales”.

En el caso concreto de Chicken (Snowdrift, Hawks and Doves), calculemos el equilibrio mixto. Si el primer jugador tiene una probabilidad p de jugar “C”, y el segundo una probabilidad q de lo mismo, el cobro del primer jugador sera a la larga:

p q  R + p (1-q) S + (1-p) q T + (1-p) (1-q) P

o, ya con R=1, P=0, y separando terminos

p ( q (1-S-T) + S) ) + q T

la condicion de equilibrio es que el termino multiplicando p sea nulo, esto es

q= S / (S+T-1)

Y cuando toda la poblacion ha evolucionado hacia el punto de equilibrio q el valor extraido por cualquier jugador es a la larga el dado por la primera ecuacion poniento tambien p=q, esto es

S T / (S+T-1)

Incidentalmente, notad que la condicion de equilibrio es una recta que pasa por S=0, T=1. En cierto modo esta familia de rectas, para q entre cero y uno, va interpolando desde el dilema del prisionero hasta Harmony. La recta para q=1/2 es paralela a la diagonal S=T.

Otra pregunta seria, sabiendo que en el equilibrio el valor extraido por jugador va a ser este p ( p (1-S-T) + S) ) + p T, ¿cual seria la estrategia mixta que maximiza la extraccion de valor?. Derivando la funcion, tendriamos la condicion

0 =  2 p (1-S-T) + (S+T)

con solucion

p = (S + T) / 2(S+T-1)

que extraeria un valor por jugador de

[(S + T) / 2(S+T-1)]  ( [(S + T) / 2(S+T-1)]  (1-S-T)  + (S+T) ) = [(S + T) / 2(S+T-1)] (  (S+T) /2)) =
= (S+T)^2 /  4(S+T-1)

Si  (S+T)/2 = S, entonces el equilibrio de Nash es tambien la mejor estrategia mixta a la hora de extraer valor. Esto es la diagonal S=T, que en realidad ni siquiera es dominio de Chicken.

Lejos de esta diagonal,  el equilibrio de Nash es una estrategia ineficaz, la diferencia seria:

(S+T)^2 /  4(S+T-1) – S T / (S+T-1)  =   (S-T)^2 /  4(S+T-1)

Es interesante que las soluciones de mayor eficacia dependen solo de S+T, esto es, forman rectas antidiagonales, perpendiculares a la S=T. Una forma grafica de visualizar por tanto la “solucion eficaz” para un juego (1,S,T,0) es proyectar, o trasladar, perpendicularmente la coordenada (S,T) a la diagonal y tomar la solucion de Nash para el juego resultante, llamemosle (2, S+T, S+T, 0).

Otra cosa que podemos observar mirando la forma de p en funcion de S+T, esto es (S + T) / 2(S+T-1), es que p < 1 solo si (S+T) > 2 ó si (S+T)<0.  La primera de estas condiciones es tambien, como emos mencionado más arriba, la condicion para que empieze a merecer la pena ponerse de acuerdo para jugar CD o DC alternativamente en vez de jugar por el Reward. A medida que va aumentando (S+T), el valor de p va descendiendo hacia 1/2, confirmando el metodo “gráfico” que hemos sugerido en el parrafo anterior.

Por otra parte, si (S+T)/2 es pues el maximo valor extraible por jugada si los jugadores pudieran adoptar algun metodo para ponerse de acuerdo, otra forma de leer las ecuaciones es que el valor optimo (S+T)/2 recibe de partida una correccion (S+T)/ 2(S+T-1) por el hecho de quedarnos limitados a usar soluciones de estrategia mixta, sin memoria ni contexto de las jugadas anteriores.

La cuestion que quiero enfocar en el siguiente post es. ¿hay alguna modificacion del juego, en terminos de reglas de evolucion, que permita equilibrios sobre estrategias mixtas mas eficaces que el equilibrio de Nash? Esto puede ser factible porque las reglas de update en una simulacion tienen en realidad influencia sobre el punto de equilbrio. La cuestion es si se puede aprovechar esa influencia para  ajustarse al optimo de extraccion de una manera razonable, o si simplemente nos desplazamos hacia otro equilibrio sin poder relacionarlo con el óptimo. Pero eso ya sera para el fin de semana.

2016183238bis

jackpot lotteries: some extra analysis

First of all, congratulations to the winners. Lets try to collect here the final data of the  jackpot run:  Reminder, the jackpot prize comes from an extraction of 5 numbers from 69 plus another of 1 number between 26. This was chosen purposefully last year, to produce this kind of big prizes once in the yer. (69 5) times 26 is 292 201338, ticket price is $2 and you can expect a return from minor prizes setting the price to a lower $1.58. The number of players was unknown, but  from the increase of the jackpot it can be napkin-guessed to be around 635M, (no idea why the estimation of wired is a lot lower, say 170M, and on the other hand (1500-947.9)/0.34/2 is even greater, 800M. Perhaps it should be estimated from the cash-payout, which is a 62% of the jackpot?).  There has been, or it is claimed so, three winners that will share the big prize. The number of players increases faster than linear with the size of the jackpot, fitting well with quadratic (!) or exponential function.

Now, back to the game-theoretical considerations of yesterday.

We assume a god-given jackpot, a “resource” to be harvested, having always the same value, and players having no memory of previous winners, so that they only can choose between buying or not the offered tickets. They can do it by having a internal preference q1,q2,… between 0 and 1 and drawing a random number to decide.

One point of the lottery is that our result if we do not play is simply zero, not losses -except moral ones if some friend wins, of course-. In the general formula for the expected win, with p our own mixed strategy,

p f(q1,q2,q3,…) + (1-p) g( q1,q2,q3,…)

the function g is zero. This means that whatever mixed strategy the other players choose, the total expected win will always be proportional to our own probability p of playing. This also means that if f(…) were non zero, we should always counter by moving to a pure strategy, either p=1 or p=0. So this kind equilibrium happens only when p is cancelled out because  f(…) itself is equal to g(…) ; in  this case g() is zero, and then the expected benefit in the long run for all the players will be zero. Generically the benefit will be exactly the same as the pure strategy of not playing at all.

Another argument for not to play is to minimize your expected loss if you are completely unsure of the other partners strategy: if g(…) is zero but f(q1,q2,q3…) can be less than zero, then p=0 is your escape option.

Of course all of this is a tragedy because a god-given jackpot could be harvested. Ideal goal is to coordinate all players to buy only exactly the 292 201338 combinations, and share the prize.  The question is, can it be done, or approximated, without a fully forceful central coordination?  I leave it open.

What about populating the lotto world with hawks and doves? This is, the players can be either fanatic, always play for this amount of jackpot, or pessimistic, never playing. A initial population of doves could gradually mutate to hawks in order to extract some benefit for the resource, but at some point the probability of fighting hawk vs hawk should stop the mutation and keep a fixed level of players against no players. Is this point also given by the same equilibrium that above? If so, is the total resource extraction again zero? I have run some simulations and it seems that the proportion of hawks evolves to be slightly smaller that the expected point of zero benefit, but still near enough to attribute the discrepancy to finite size effects, and finite number of trials. Of course, that implies another philosophical question, given the fact that real games have a finite number of trials, should we recalculate for only a few trials?

There is, to me, some lack of intuition here. One could think that the idea in a lottery is to keep adding players until the probability of benefit becomes zero again, and that in hawks and doves we keep turning doves into hawks also in the same way, until the benefit extracted from the game becomes zero. This seems consistent with setting to zero the above equation, for the case g(q) =0, f(q)= q (P/2-T) + (1-q) (P-T), is

p (P-T) + p q (-P/2)

and then f(…) =0, exhausting but if there is some small prize or penalisation K when we do not play, the intuition fails, as then we need the partial respect to p of

p f(q1,q2,q3,…) + (1-p) K

and we get f(…) = K and the total expected benefit equal to K, not zero. So in principle if K is still positive there is room to turn doves to hawks even beyond the equilibrium point. The general solution  q (P/2-T) + (1-q) (P-T) = K is   q=   2 (1-T/P) –  2K/P