Teoría de Juegos: el penalty de Nash

TEOR´ IA DE JUEGOS: EL PENALTY DE NASH Guillermo Bautista Baquero c 2018 TEORÍA DE JUEGOS: EL PENALTY DE NASH Por Guillermo Bautista Baquero TRABAJO FIN DE GRADO PRESENTADO PARA OPTAR AL GRADO EN MATEMÁTICAS POR LA UNIVERSIDAD DE SEVILLA Guillermo Bautista Baquero UNIVERSIDAD DE SEVILLA DEPARTAMENTO DE ESTADÍSTICA E INVESTIGACIÓN OPERATIVA El abajo rmante ha leído este trabajo y recomienda a la Facultad de Matemáticas la aceptación del trabajo  Teoía de Juegos: el penalty de Nash  realizado por Guillermo Bautista Baquero como Trabajo Fin de Grado para obtener el Grado en Matemáticas a conforme a lo dispuesto en la Ley. Con fecha de: Junio 2018 Tutor: Prof. Dr. José María Fernández Ponce UNIVERSIDAD DE SEVILLA Fecha: Junio 2018 Autor: Guillermo Bautista Baquero Título: Teoría de Juegos: el penalty de Nash Dpto: Estadística e Investigación Operativa Firma del autor SE PROHIBE LA REPRODUCCIÓN TOTAL O PARCIAL DE ESTE TRABAJO SIN EL PERMISO EXPRESO DEL AUTOR O DE LA UNIVERSIDAD DE SEVILLA. INDICE Resumen i Abstract iii 1. Introducción 1 1.1. Conceptos fundamentales: equilibrio . . . . . . . . . . . . . . . . . . . . 1 1.2. Teorema del Punto Fijo . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3. Estructura del trabajo . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2. Juegos de Suma Nula 9 2.1. Denición de un juego en forma normal . . . . . . . . . . . . . . . . . . 9 2.2. Estrategias MIN-MAX . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.3. Extensión mixta de un juego . . . . . . . . . . . . . . . . . . . . . . . . 13 2.4. Solución en juegos matriciales . . . . . . . . . . . . . . . . . . . . . . . 16 2.5. Estrategias óptimas y valor del juego . . . . . . . . . . . . . . . . . . . 20 2.6. Juegos completamente mixtos y simétricos . . . . . . . . . . . . . . . . 21 3. Juegos de Suma No Nula 25 3.1. Juego no cooperativo en f.n. . . . . . . . . . . . . . . . . . . . . . . . . 25 3.2. Principios de Optimidad . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.3. Estrategiasmixtas ............................. 32 3.4. Existencia equilibrios de Nash . . . . . . . . . . . . . . . . . . . . . . . 36 3.5. Equilibrios en estrategias mixtas conjuntas . . . . . . . . . . . . . . . . 38 4. Aplicación: El Penalty de Nash 41 4.1. Introducción................................. 41 4.2. Estrategias mixtas en lanzamientos de penalties . . . . . . . . . . . . . 43 4.3. Datos .................................... 47 4.4. Análisisempírico .............................. 49 4.4.1. Pruebas individuales . . . . . . . . . . . . . . . . . . . . . . . . 51 4.4.2. Pruebas conjuntas . . . . . . . . . . . . . . . . . . . . . . . . . 52 4.4.3. Interpretación y discusión . . . . . . . . . . . . . . . . . . . . . 55 4.5. Debate y pruebas adicionales . . . . . . . . . . . . . . . . . . . . . . . . 57 4.6. Conclusión.................................. 57 .1. Apéndice. Identidades de lanzadores y porteros . . . . . . . . . . . . . 59 1 Introducción Youngeun (2016). Denición 1.2.1. Una envolvente convexa de un conjunto de puntos en el espacio Euclídeo E , es el menor conjunto convexo que contiene a E . Denición 1.2.2. Un politopo es un objeto geométrico con lados planos y que puede existir en cualquier dimensión n, siendo así un politopo n-dimensional. Denición 1.2.3. Un símplex es un politopo k-dimensional cuya envolvente convexa tiene k+ 1 vértices. Suponiendo que los k+ 1 puntos son u0, u1, . . . , uk∈Rk son afínmente independientes, i.e., u1−u0, u2−u0, . . . , uk−u0 son linealmente independientes, entonces el símplex determinado por estos puntos es de la forma: C={θ0u0+θ1u1+· · · +θkuk| k X i=0 θi= 1, θi≥0}. Denición 1.2.4. Una función continua g es aquella que transforma sucesiones convergentes en sucesiones convergentes: si xn→x , entonces g(xn)→g(x) . Denición 1.2.5. Un subespacio B⊂A es un retracto si existe una función continua r:A→B , llamada retracción, tal que r◦i=idA donde i representa la inclusión de B en A e idA reprenta la función identidad de A . Teorema 1.2.6 (Punto Fijo de Brouwer) . Si x→ϕ(x) es una función continua punto a punto de un símplex r-dimensional S en sí mismo, entonces existe x0∈S tal que ϕ(x0) = x0 . Demostración. La prueba está basada en el hecho de la no existencia de retracciones del disco unidad en su frontera. Se puede encontrar en Youngeun (2016). El teorema del punto jo de Kakutani generaliza el de Brouwer en dos aspectos: la función continua no es punto a punto sino que se da de punto a conjunto y la continuidad de funciones se generaliza como funciones semicontinuas superiormente. 3 Introducción 1 Notation 1. Denotamos por Ω(A) al conjunto partes de A : Ω(A) = {B:B⊂A}. (1.2.1) Denición 1.2.7. Sean X,Y dos conjuntos no vacíos. Una correspondencia de X en Y es una función Φ : X→Ω(Y) , que a cada punto x de X , le asigna un subconjunto no vacío Φ(x) de Y . Denición 1.2.8. Una correspondencia x→Φ(x)∈Ω(Y) de X en Ω(Y) se dice que es semicontinua superiormente si xn→x0 , yn∈Φ(xn) e yn→y0 implican que y0 ∈Φ(x0) . Denición 1.2.9. Una subdivisión baricéntrica simplicial es un algoritmo que divide un politopo convexo arbitrario en simpliciales de la misma dimensión conectando los baricentros de sus caras. Lema 1.2.10. Cualquier sucesión de números reales acotada tiene una subsucesión convergente. Demostración. Véase Youngeun (2016). Lema 1.2.11 (Bolzano-Weierstrass) . Cualquier sucesión acotada de Rn tiene una subsucesión convergente. Demostración. Véase Youngeun (2016). Corolario 1.2.12. Toda sucesión en un conjunto S cerrado y acotado de Rn tiene una subsucesión que converge a un punto en S . Demostración. Toda sucesión en un cerrado y acotado es acotada, luego por el Lema 1.2.11, tiene una subsucesión convergente. Como el conjunto S es cerrado, dicha subsucesión converge a un punto en S . Teorema 1.2.13 (Teorema del Punto Fijo de Kakutani) . Si x→Φ(x) es una correspondencia semicontinua superiormente de un símplex r-dimensional S en Ω(S) , entonces existe un x0∈S tal que x0∈Φ(x0) . 4 1 Introducción Demostración. Sea Sn la n -ésima subdivisión baricéntrica simplicial de S. El número n∈N denota cuántas divisiones de este tipo se han hecho previamente. Los ejemplos de S0 , S1 y S2 están en la gura (1.1). Obsérvese que sólo se necesita el símplex S para ser dividido en simpliciales más pequeños, no necesariamente mediante subdivisión baricéntrica. Dicha subdivisión es una entre muchas posibles. Como S es un símplex Figura 1.1 cerrado r -dimensional, existen muchos simpliciales r -dimensionales cerrados más pequeños en Sn . Se toma uno de ellos, que tendrá r+ 1 vértices, y lo denotamos por Sx . Sean x0, . . . , xr los vértices. Así, todos los puntos de Sx pueden ser representados por la ecuación θ0x0+θ1x1+· · · +θrxr , con Pr i=0 θi= 1, θi≥0 por denición de símplex. Para cada vértice xi , Φ(xi) será un conjunto de números ya que Φ(xi) es una correspondencia. Sean yi un punto arbitrario en Φ(xi) y Sy el símplex formado por y0, y1, . . . , yr . Entonces, todos los puntos de Sy también pueden ser representados por θ0y0+θ1y1+· · · +θryr,Pr i=0 θi= 1, θi≥0 donde θi son exactamente los mismos que se necesitan para representar los puntos en Sx . Por tanto, existe una correspondencia entre los puntos de Sx y los de Sy . Figura 1.2 Si se repite el proceso para todos los simpliciales r -dimensionales en Sn , entonces todos los puntos en Sn tendrían su correspondiente punto en S . Luego, dicha función es punto a punto de S en sí mismo. Esa función se denotará por x→ϕn(x) . Como es una función 5 Introducción 1 continua punto a punto de un símplex cerrado r -dimensional en sí mismo, por el Teorema 1.2.6 existe un punto xn∈S tal que xn=ϕn(x) . Repitiendo de nuevo todo este proceso para S0, S1, S2, . . . , existirían los correspondientes x0, x1, x2, . . . . Como la subdivisión baricéntrica puede hacerse tantas veces como se desee, la sucesión x0, x1, x2, . . . es innita. Además, como S es un cerrado y acotado en Rn , por el Corolario 1.2.12, esta sucesión tiene una subsucesión convergente a un punto x∗∈S . Dicho punto es el punto x∗∈S tal que x0∈Φ(x0) . Obsérvese que puede haber más de un x∗ si existe más de una subsucesión convergente de x0, x1, x2, . . . . Para probar esta característica de x∗ , sea ∆n un símplex r -dimensional de Sn que contiene al punto x∗ . El punto x∗ puede ser parte de más de un símplex r -dimensional si está en algún vértice o eje de los simpliciales. En ese caso, se toma cualquiera de esos simpliciales. Sean v0, v1, . . . , vr los r+1 vértices de ∆n . Entonces, como ∆n es un símplex y xn∈∆n , xn=Pr i=0 θivi, para θ0, θ1, . . . , θr tal que Pr i=0 θi= 1, θi≥0 . Ahora, sean qi=ϕ(vi),(i= 0,1,2, . . . , r) . Entonces, qi∈Φ(vi) ya que ϕ(x∗) = Pr i=0 θiqi para los θi usados para representar xn=Pr i=0 θivi . Se puede repetir el proceso obteniendo: x∗=ϕn(x∗) = r X i=0 θn ivn i. Ahora tomando una nueva subsucesión (n0 v) de (nv) tal que (θn0 v i) y (vn0 v i) converge para i= 0,1, . . . , r y se toma l´ımv→∞ θn0 v i=θ0 i y l´ımv→∞ vn0 v i=v0 i . Entonces por la semicontinuidad superior de Φ(x) , y0 i∈Φ(x0) para i= 0,1, . . . , r y esto implica, por la convexidad de Φ(x0) , que x0=Pr i=0 θ0 iv0 i∈Φ(x0) . Ésto completa la prueba. 1.3. Estructura del trabajo Como se ha mencionado anteriormente, el trabajo se centrará en juegos no cooperativos con un conjunto, tanto de jugadores como de estrategias, nito. A continuación se presenta un breve resumen de los contenidos de cada uno de los capítulos restantes que conforman el trabajo. En el segundo capítulo se abordan los juegos donde hay dos partes en conicto con intereses enfrentados y el total de las recompensas permanece constante a lo largo 6 1 Introducción de todo el juego (cero). Son los llamados juegos de suma nula donde los pagos son opuestos. Primero se introducirán los conceptos necesarios para analizar esta clase de juegos, sirviendo estos conceptos para capítulos posteriores. Seguidamente se presenta el teorema principal del capítulo, el Teorema Minimax de John Von Neumann. Por último, se tratarán un subtipo especial de juegos dentro de los de suma nula. A lo largo de esta parte, se expondrán ejemplos para una mejor comprensión de la teoría. Se explicará cómo se puede modelar una situación de suma nula y ver las posibles soluciones (que no siempre podrán ser las mejores) de cualquier juego de este tipo. El principal objetivo del capítulo 3 es presentar el concepto de equilibrios de Nash. Basándose en deniciones anteriores, se trata de comprender cómo se formalizan los juegos cuando la recompensa total no es constante. Comienza con la denición de un juego no cooperativo en forma normal para seguir introduciendo conceptos con el objetivo nal de demostrar la existencia de equilibrios de Nash en juegos de suma no nula. De nuevo, a través de ejemplos simples se visualizará cómo se formulan y resuelven dichos juegos. Finalmente se trata de ver qué ocurre cuando las estrategias son llevadas a cabo conjuntamente. El cuarto capítulo trata sobre una aplicación empírica al teorema principal del capítulo 2, el Teorema del Minimax. Tras numerosas observaciones realizadas el matemático Ignacio Palacios-Huerta pretende aportar una situación real de la teoría de equilibrios. Para ello, analiza más de 1400 penalties, un juego en el que las estrategias están perfectamente denidas y donde las recompensas son inmediatas, generando una situación totalmente controlada. 7 2 Juegos de Suma Nula Desde pequeño, todos conocemos juegos tradicionales como piedra/papel/tijera o el ajedrez, pero lo que (seguramente) no sabíamos es que estábamos divirtiéndonos con juegos de suma nula. Estos juegos clásicos son estrictamente competitivos ya que, lo que es benecio para un jugador se transforma en pérdida para el otro. Como curiosidad decir que deportes donde no se contempla el empate, como el baloncesto o el tenis, son juegos de este tipo. No es el caso del fútbol, aunque sí existen situaciones durante un partido que se dan esta clase de juegos, pero eso es una cuestión que se abordará más adelante. Se empezará deniendo los juegos en forma normal y se continuará explicando un tipo de estrategia, probablemente el más famoso. A contnuación se procederá a relacionar la teoría de probabilidades con las estrategias para después ver tanto el concepto de solución de un juego como las estrategias más favorables para los jugadores. Se concluirá haciendo una descripción de una clase particular de juego de suma nula. 2.1. Denición de un juego en forma normal Establecidos los conceptos de juego, jugadores y estrategias, veamos uno de los casos más importantes dentro de los juegos. Un juego, según si los jugadores pueden comunicarse entre ellos y negociar resultados o no, se puede clasicar como cooperativo o no cooperativo. Los juegos de suma nula están dentro de la segunda clase. Denición 2.1.1. Un juego bipersonal de suma nula (jbsn) es aquel en el que se enfrentan dos jugadores con una serie de estrategias y cuyos pagos son opuestos; lo que un jugador gana el otro lo pierde. 9 Juegos de Suma Nula 2 Denición 2.1.2. La función de pagos es aquella función real que proporciona explícitamente el pago que recibe un jugador para cada una de sus estrategias. Un juego puede describirse, principalmente, mediante dos formas: forma extensiva (a través un árbol de decisión) y forma normal. La segunda, nos resultará mucho más útil para analizar los juegos, así que se utilizará a la hora de representarlos. Denición 2.1.3. Se llama representación formal de un juego bipersonal a una especicación de las estrategias de cada jugador, S y T , y de las funciones de pago, p1 y p2 , denidas como: p1:S×T→Rp2:S×T→R El juego es nito cuando los conjuntos de estrategias S y T son nitos, S={s1, ..., sm} T={t1, ..., tn} . Así pues un juego es de suma nula si, y sólo si, p1(s, t) + p2(s, t)=0 ∀(s, t)∈S×T. Además, cuando el juego es nito, toda la información está contenida en la llamada matriz de ganancias , denida por: A=       a11 · · · a1n . . ..... . . am1· · · amn       , donde aij =p1(si, tj) = −p2(si, tj) . Esta matriz muestra la ganancia para el jugador 1 ( J1 ) o la pérdida para jugador 2 ( J2 ) Por tanto, la estrategia si de ( J1 ) es la i -ésima la de A y la estrategia tj de ( J2 ) es la j -ésima columna de la matriz anterior. Luego se supondrá que J1 elige una la y J2 10 2 Juegos de Suma Nula elige una columna simultáneamente, ignorando cada uno la elección del otro jugador. Una vez conocidas sus estrategias, J1 gana el valor de la entrada aij , que es pagado por J2 . Si ésta es un número negativo, J1 pagará el valor absoluto de esa cantidad a J2 . Así pues, J1 buscará una estrategia que maximice la función p1 sin importar qué estrategia escoge el otro jugador, y J2 buscará minimizar dicha función independientemente de la elección del primer jugador. Problema J1 : m´ax s∈Sp1(s, t)∀t∈T Problema J2 : m´ın t∈Tp1(s, t)∀s∈S 2.2. Estrategias MIN-MAX En los juegos de suma nula, cuando un jugador intenta maximizar sus ganancias, a la vez está intentando minimizar las de su oponente. Las estrategias de seguridad se denen en Bilbao y Fernández (1999) como aquellas en las que cada jugador presume que va a obtener el peor resultado y escoge la estrategia que proporciona el mejor de los peores resultados. De esta forma se garantiza que, en el caso más desfavorable, se obrendrá la mejor solución posible. Desde el punto de vista de J1 , se tienen dos posibles estrategias de seguridad a seguir. Se puede buscar maximizar el mínimo de ganancias a obtener, o bien, minimizar la ganancia máxima de J2 , minimizando así la pérdida máxima. Denición 2.2.1. Para cada estrategia si∈S , se dene el nivel de seguridad de 11 Juegos de Suma Nula 2 J1 como el pago que puede asegurarse con esa estrategia prescindiendo de las acciones de J2 : v1(si) = m´ın jaij. Análogamente, para cada estrategia, tj∈T el nivel de seguridad de J2 es el pago que puede asegurarse con esa estrategia prescindiendo de las acciones de J1 : v2(tj) = m´ax iaij. Denición 2.2.2. El valor maximin viene dado por: v1= m´ax iv1(si) = m´ax im´ın jaij. Así, una estrategia maximin es aquella que proporciona al jugador su valor maximin. Denición 2.2.3. El valor minimax viene dado por: v2= m´ın jv2(tj) = m´ın jm´ax iaij Una estrategia minimax es aquella que proporciona al jugador su valor maximin. Se cumple siempre que v1≤v2. La estrategia maximin, o criterio de Wald (matemático que estableció por primera vez este método en su libro Wald (1950)), y la estrategia minimax, o criterio de Savage (Shafer (1986)), se dice que son pesimistas ya que el jugador quiere asegurarse la mejor elección en caso que se dé la situación más desfavorable. Suelen ser útiles en situaciones 12 2 Juegos de Suma Nula Como Λ(x) y Λ(y) son funciones continuas y están denidas en X e Y , que son compactos, entonces ∃x∗∈X e y∗∈Y, tal que: Λ(x∗) = m´ax xm´ın yxaj=λ (2.4.2) Λ(y∗) = m´ın ym´ax xaiyT=λ. (2.4.3) Así para cada j , con 1≤j≤n : x∗aj≥m´ın 1≤j≤nx∗aj= Λ(x∗) = m´ax xm´ın yxaj, y para cada i , con 1≤i≤m : aiy∗T≤m´ax 1≤i≤maiy∗T= Λ(y∗) = m´ın ym´ax xaiyT. Hay 3 posibles casos: 1. Para cada j , x∗aj=λ , y para cada i , aiy∗T=λ . 2. ∃k , 1≤k≤n , tal que x∗ak> λ . 3. ∃h , 1≤h≤m , tal que ahy∗T< λ . En el caso 1 el juego tiene valor claramente. Veamos qué ocurre en el caso 2 (el caso 3 es completamente análogo). Al existir, k se sigue que n > 1 . Se denota como A−k la matriz resultante de eliminar la k -ésima la de A . Así, el conjunto de estrategias mixtas de J2 en A−k se identica como: Y−k={y∈Y|yk= 0}. Sean λ−k y λ−k el valor minimax y maximin del juego de matriz A−k . La hipótesis de inducción, es que este juego tiene valor, i.e., λ−k=λ−k . Por otra parte: λ−k= m´ax x∈Xm´ın j∈{1,...k−1,k+1,...,n}xaj≥m´ax x∈Xm´ın j∈{1,...,n}xaj=λ λ−k= m´ın y∈Y−km´ax 1≤i≤maiyT≥m´ın y∈Ym´ax 1≤i≤maiyT=λ. Se probará que λ−k=λ y, por tanto, λ=λ−k=λ−k≥λ≥λ, 19 Juegos de Suma Nula 2 quedando demostrado el teorema. Así pues, se supone que λ−k> λ (reducción al absurdo). Sea x0 tal que λ−k= m´ın j∈{1,...k−1,k+1,...,n}x0aj. Entonces para cada j∈ {1, ...k −1, k + 1, ..., n} , se cumple que: x0aj≥λ−k> λ. Por último utilizando 2.4.2, se tiene que, para cada ∈(0,1) y cada j∈ {1, ...k −1, k + 1, ..., n} , (x0+ (1 −)x∗)aj> λ. Además, como x∗ak> λ existe un ∈(0,1) sucientemente pequeño, tal que (x0+ (1 −)x∗)ak> λ. Por tanto, λ= m´ax x∈Xm´ın jxaj≥m´ın j(x0+ (1 −)x∗)aj> λ Lo cual es una contradicción. 2.5. Estrategias óptimas y valor del juego Esta sección tratará de relacionar dos conceptos fundamentales en la teoría de juegos: las estrategias óptimas y el valor del juego. Se supone que el jugador 1 utiliza la estrategia mixta x= (x1, ..., xm) y el jugador 2 utiliza la estrategia j -ésima de la matriz del juego A= (aij) . Entonces, el valor esperado para J1 es: xAej= m X i=1 xiaij, donde ej denota la columna j -ésima de la matriz identidad. Denición 2.5.1. Sea v el valor de un juego. Una estrategia óptima x para J1 es aquella que garantiza que el pago medio para J1 sea, al menos, v sin importar la columna 20 2 Juegos de Suma Nula j -ésima que elija J2 , es decir, tiene que cumplir: m X i=1 xiaij ≥v∀j∈ {1, ..., n}. Análogamente, una estrategia y= (y1, ..., yn) es óptima para J2 si cumple: n X j=1 aijyj≤v∀i∈ {1, ..., m}. Cuando ambos jugadores escogen sus estrategias óptimas, el pago esperado es exactamente v : v= n X j=1 vyj≤ n X j=1 ( m X i=1 xiaij)yj= m X i=1 ( n X j=1 xiaij)yj= m X i=1 xi( n X j=1 aijyj)≤ m X i=1 xiv=v, lo cual implica que las estrategias de J1 y J2 deben cumplir, respectivamente, que: m X i=1 xiaij =v n X j=1 aijyj=v. (2.5.1) Por tanto, J1 ( respec. J2 ) busca una estrategia originando que el J2 ( respec. J1 ) sea indiferente en cuanto a qué estrategias puras usa.( Principio De Indiferencia . Se puede encontrar en Ferguson (2005)). 2.6. Juegos completamente mixtos y simétricos Un amplio conocimiento de las estrategias óptimas simplica la resolución de juegos, es decir, permite encontrar el valor del juego más fácilmente. Denición 2.6.1. Se dice que J1 (respec. J2 ) utiliza una estrategia completamente mixta si asigna una probabilidad estrictamente positiva a cada estrategia pura. Es decir, x= (x1, ..., xm) es una estrategia completamente mixta para J1 si xi>0 y Pm i=1 xi= 1 .(Análogo para J2 cambiando y por x y n por m). 21 Juegos de Suma Nula 2 Denición 2.6.2. Se dirá que un punto de silla (x∗,y∗) es completamente mixto (c.m.) si las estrategias x∗ e y∗ son completamente mixtas y si, en un juego cada punto de silla es c.m., entonces éste es completamente mixto. Estos juegos son interesantes ya que tienen una única solución: Teorema 2.6.3. Un juego ΓA c.m. con matriz A de dimensión m×n tiene una única solución (x∗,y∗) y una matriz cuadrada (m=n). Además, si el valor del juego v es no nulo entonces A es una matriz regular y se tiene: x∗=uA−1 uA−1uy∗=A−1u uA−1uv=1 uA−1u, donde u= (1,...,1) ∈Rm . Nota 2. Una matriz regular es aquella que tiene inversa ( A tal que |A| 6= 0 ). Demostración. Sean x∗= (x∗ 1, ..., x∗ m)∈X∗ e y∗= (y∗ 1, ..., y∗ n)∈Y∗ las estrategias arbitrarias óptimas para J1 y J2 respectivamente y sea vA el valor del juego ΓA . Al ser c.m., x∗ y y∗ son estrategias completamente mixtas y (sólo ellas) son soluciones de las ecuaciones 2.5.1: xaj=vAxi>0,xuT= 1, i = 1, . . . , m;j= 1, . . . , n (2.6.1) aiyT=vAyj>0,ywT= 1, i = 1, . . . , m;j= 1, . . . , n, (2.6.2) donde ai es el vector la i -ésimo de la matriz A , aj el vector columna j -ésimo y u= (1,...,1) ∈Rm , v= (1,...,1) ∈Rn . Hay que probar que la solución (x∗, y∗) del juego c.m. ΓA es única. Los conjuntos X∗, Y ∗ que denen las ecuaciones 2.6.1 y 2.6.2 son poliedros convexos no vacíos y, por tanto, se alcanzan los valores extremos. Además se puede comprobar que: m≤rg(a1, . . . , an, u) = rg(A|u)≤m n≤rg(a1, . . . , am, w) = rg(A|w)≤n, donde rg denota la rango de la matriz y (A|u),(A|w) son las matrices que se obtienen al añadir u y w a la matriz A . Ésto implica que los conjuntos X∗ e Y∗ tienen un punto extremo cada uno y, por tanto, consiste solo en esos puntos. Así se tiene la unicidad de (x∗, y∗) . Sea vA= 0 . 22 2 Juegos de Suma Nula Entonces el sistema homogéneo: xaj=vA, j = 1, . . . , n, tiene una solución no nula; por tanto rg(A)< m . Como rg(A|u) = m , se tiene: rg(A) = m−1 . Análogamente se obtiene del otro sistema que rg(A) = n−1 . Por tanto m=n . Sea vA6= 0 . Entonces rg(A) = rg(A|vAu) = rg(A|u) = m, rg(A) = rg(A|vAw) = rg(A|u) = n. Por tanto m=n=rg(A) , i.e., A es una matriz regular. El sistema de ecuaciones x∗A=vAu tiene una solución: x∗=vAuA−1. Escribiendo la solución del sistema Ay∗T=vAu se obtiene que: y∗=vAA−1u, Por tanto vA=1 uA−1u. Ésto completa la prueba. Ahora se estudiará un tipo de juego con una matriz especial. Denición 2.6.4. Un juego, con una matriz cuadrada A , es simétrico si A es antisimétrica, i.e., si aij =−aji para todo i y j . En este caso, todos los elementos de la diagonal son ceros, aii = 0 para todo i . Al ser la matriz cuadrada, se sigue que las estrategias mixtas de cada jugador son las mismas. Además estas matrices cumplen que AT=−A . Los juegos simétricos tienen unas características especiales: Teorema 2.6.5. Sea ΓA un juego simétrico. Entonces vA= 0, 23 Juegos de Suma Nula 2 y los conjuntos de estrategias óptimas de cada jugador coinciden, i.e. X∗=Y∗. Demostración. Sea A la matriz del juego y x∈X una estrategia arbitraria. Entonces, xAx=xATx=−xAx . Y, por tanto, xAx= 0 . Sea (x∗,y∗) un punto de silla y vA el valor del juego. Entonces: vA=x∗Ay∗≤x∗Ay, vA=x∗Ay∗≥xAy, para todo x∈X, y ∈Y . Consecuentemente: vA≤x∗Ax∗= 0, vA≥y∗Ay∗= 0. Por tanto vA = 0. Sea x∗ la estrategia óptima en el juego. Entonces: x∗A≥0. Se sigue, sin embargo que x∗(−AT)≥0 , por tanto x∗AT≤0 . Por tanto, se tiene Ax∗≤0. Por la caracterización de estrategias óptimas, se sigue que x∗ es la estrategia óptima para J2 . Así pues, se ha probado que X∗⊂Y∗ . La conclusión inversa se prueba de manera totalmente análoga. 24 3 Juegos de Suma No Nula Una vez estudiados los juegos donde la ganancia de un jugador es exactamente la pérdida del otro, toca ver qué ocurre cuando hay más de dos jugadores y los pagos no tienen por qué ser opuestos. En este capítulo se supondrá que los jugadores son inteligentes en el sentido que cada uno será capaz de realizar los mismos cálculos y determinar un plan coherente antes de que empiece el juego. Además, se supone que son racionales al buscar maximizar su benecio. Por tanto, no se perderá generalidad si se asume que todos los jugadores formulan su plan de estrategias simultáneamente al principio del juego. Así, un juego consiste solo en un proceso mecánico donde se implementan dichas estrategias y se determinan los resultados acorde a las reglas del juego. Esta situación en la que todos los jugadores toman sus decisiones a la vez y de manera independiente (con respecto a los demás) está exactamente descrita por la forma normal (f.n.) de un juego. 3.1. Juego no cooperativo en f.n. La teoría de este capítulo está basada en Petrosyan y Zenkevich (1996). En Neumann y Morgenstern (1944) argumentaron, a groso modo, que la representación de un juego en forma normal es todo lo que se necesita para poder analizar un juego. Luego, aún existiendo la forma extensiva a la hora de representar un juego, la forma normal ofrece una descripción más compacta ya que se pueden relacionar estrategias y recompensas mediante la matriz de pagos. A pesar de que el objetivo de cada jugador es elegir una estrategia que maximice su ganancia, en algunos casos puede que esta elección ayude a los demás jugadores y en otros que los perjudique, al contrario que pasaba con los juegos de suma nula. Es por ello que se pueden dar situaciones donde haya un benecio mutuo. Luego, a veces, la 25 Juegos de Suma No Nula 3 llegada a un acuerdo por parte de los jugadores (cooperación) produce un incremento en el benecio para ellos. Por esta razón, en los juegos de suma no nula se distingue el caso de comportamiento no cooperativo, donde las reglas no permiten ningún tipo de colaboración, ni de comportamiento cooperativo. Cabe destacar que, como las posibilidades de cooperación son muchas y muy complejas, resulta difícil modelarlas explícitamente. Así pues, se considerará el primer caso. Denición 3.1.1. La terna Γ = (N, {Xi}i∈N,{ui}i∈N), se llama juego no cooperativo en forma normal donde N={1,2, ..., n} es el conjunto de jugadores, Xi es el conjunto de estrategias del jugador i-ésimo y ui es la función de pagos para el jugador i, denida sobre el producto cartesiano de los conjuntos de estrategias X=Qn i=1 Xi . Como se ha dicho antes, los jugadores escogen sus estrategias xi de forma independiente y simultánea de los conjuntos de estrategias Xi , i= 1, ..., n , generando una combinación de estrategias x= (x1, ..., xn) , xi∈Xi . A este vector se le llamará situación. Al contrario que pasa con los jbsn, ahora no basta con dar una matriz de pagos ya que éstos no son opuestos. Así se podrá formar matrices donde las entradas están formadas por un vector la con dos componentes (bimatrices): la primera es el pago que recibe un jugador si elige la i -ésima estrategia (la) y la segunda el pago que recibe otro jugador si escoge la j -ésima estrategia (columna). Además, al no tratarse de un juego bipersonal, habría que implementar N 2 matrices, cuestión que diculta el análisis. Por ello habrá veces que se simplicará el caso a dos jugadores, para la mejor comprensión. Ejemplo 3.1.2 (Dilema del prisionero.) . García (2016) La policía acaba de arrestar a dos sospechosos de un crimen. No se han encontrado pruebas sucientes para condenarlos y, tras haberlos separado, un ocial de policía visita a cada uno y les ofrece el 26 3 Juegos de Suma No Nula mismo trato. Si uno conesa y el otro no, el que conesa no será condenado al haber colaborado con la justicia mientras que al otro le condenarán a diez años de prisión. Pero si ambos conesan el crimen, cada uno recibirá una condena menor, de seis años. Si ninguno conesa, ante la falta de pruebas, pasarán un año en la cárcel acusados de un cargo menor. Si la primera estrategia para ambos es confesar, α1 y β1 y la segunda negar, α2 y β2 , entonces la bimatriz sería: (A, B) =  β1β2 α1(6,6) (0,10) α2(10,0) (1,1) , Por último apuntar que van Damme y Furth (2002) dieron otro punto de vista sobre los juegos no cooperativos. Proponían que, en muchas ocasiones, los jugadores no cooperaban al carecer de mecanismos que les permitan llegar a acuerdos vinculantes; no es que no quieran colaborar, es que no pueden. 3.2. Principios de Optimidad Cuando se habla de optimizar se referirá a buscar alguna de las mejores soluciones entre muchas alternativas posibles. Este proceso puede ser visto como una secuencia de decisiones que nos proporciona la solución correcta. Si dada una secuencia de decisiones siempre se conoce cuál es la decisión que debe tomarse a continuación para obtener la estrategia óptima, el problema es elemental y se resuelve trivialmente tomando una decisión detrás de otra, lo que se conoce como estrategia voraz . Pero ésto solamente ocurre en una minoría de juegos. En los casos donde no se puedan aplicar, se cumple el principio de Bellman (1958) que dicta: " Dada una secuencia óptima de decisiones, toda subsecuencia de ella es, a su vez, óptima ". 27 Juegos de Suma No Nula 3 Hemos visto que para los juegos de suma nula los principios de minimax, maximin y equilibrio coinciden en el sentido que si son factibles, entonces existe un equilibrio (punto de silla) mientras haya maximin y minimax y además coinciden. En tal caso denen una única noción de optimalidad y soluciones del juego. Aunque en la teoría de los juegos de suma no nula no existe una única aproximación a los principios óptimos, existen algunos, basados en hipótesis adicionales sobre el comportamiento de los jugadores y la estructura del juego, que permiten el cálculo de valores óptimos y solución del juego. Parece natural que cada jugador procure alcanzar una situación x en el juego Γ tal que su pago sea máximo. La función valor ui , sin embargo, no solo depende de las estrategias del jugador i , sino que también depende de las escogidas por los oponentes. Por ello, las situaciones que determinan un pago máximo para un cierto jugador pueden no ser las mismas que para los demás. Así, como en el caso de los jbsn, la búsqueda del pago máximo involucra un conicto e incluso la formulación de un comportamiento óptimo, se vuelve problemática. Hay muchos enfoques a esta cuestión. Uno de ellos es el equilibrio de Nash (eq. N.) con sus extensiones y renamientos. En el caso de suma nula, el eq N. coincide con la idea del punto de silla, que es el principio básico de este tipo de juegos. En lo que queda de este capítulo se estudiará la noción de equilibrios de Nash en los juegos no cooperativos de suma no nula. Se supone una situacón arbitraria del juego x= (x1, ..., xi, ..., xn) con xi la i -ésima estrategia del jugador i . Se construye una situación diferente reemplazando xi por x0 i obteniendo x= (x1, ..., x0 i, ..., xn) la que se escribirá como (x||x0 i) . Nótese que si xi=x0 i ⇒(x||x0 i) = x . Denición 3.2.1. La situación x∗= (x∗ 1, ..., x∗ i, ..., x∗ n) es un equilibrio de Nash si 28 3 Juegos de Suma No Nula 1−q . Así el pago esperado para J1 sería: K1= 2pq + 0p(1 −q) + 1(1 −p)q+ 3(1 −p)(1 −q) = p(4q−3) + (3 −2q). (3.3.3) Existen varios casos: Si q= 3/4 , es decir, J2 opta por la estrategia β1 las tres cuartas partes de las veces y por β2 una cuarta parte, J1 obtendrá el mismo pago si utiliza α1 o α2 . Si q > 3/4 , el paréntesis de la segunda igualdad en 3.3.3 será positivo, luego como J1 busca maximizar su pago esperado K1 , entonces le interesa que p se haga lo mayor posible (se recuerda que 0≤p≤1 ). Si q < 3/4 , el paréntesis de la segunda igualdad en 3.3.3 será negativo, entonces le interesa que p sea lo menor posible. El pago esperado para J2 viene dado por: K2=pq + 2p(1 −q) + 2(1 −p)q+ 0(1 −p)(1 −q) = q(2 −3p)+2p Siguiendo el mismo procedimiento, si p= 2/3 , J2 será indiferente a las elecciones de J1 . Si p < 2/3 , a J2 le interesa que q sea lo más grande posible (se recuerda que 0≤q≤1 )., porque lo que va multiplicando por q sería positivo. Análogamente, si p > 2/3 , J2 busca que q sea lo más pequeño que se pueda. En este caso el equilibrio de Nash en estrategias mixtas (ENEM) es aquel que J1 utiliza la estrategia α1 con probabilidad 2/3 y la α2 con 1/3 y el J2 utiliza la estrategia β1 con probabilidad 3/4 y la α2 con 1/4 . Se representa de la siguiente forma: ENEM = ((2/3)α1+ (1/3)α2,(3/4)β1+ (1/4)β2). Sea K(µ∗) = {Ki(µ∗)} un vector de pago en algún equilibrio de Nash. Se denota por vi=Ki(µ∗) y v={vi} . Mientras que en los j.s.n el valor v de una función de recompensas es el mismo para todos los equilibrios y, por tanto, está univocamente determinado, en los juegos de suma nula hay un conjunto completo de vectores v . Por tanto, todo vector v está relacionado con un determinado equilibrio µ∗ , vi=Ki(µ∗) , µ∗ ∈X , X=Qn i=1 Xi . Para nalizar, puntualizar que si los conjuntos de estrategias son no nitos, X1∈ Rm , X2∈Rn , entonces las estrategias mixtas de los jugadores están identicadas con 35 Juegos de Suma No Nula 3 las medidas de probabilidad dadas por el σ -álgebra de Borel sobre los conjuntos de estrategias. Si µ y ν son las estrategias mixtas de J1 y J2 respectivamente, entonces el pago al jugador i , en la situación (µ, ν) , es la esperanza matemática del pago: Ki(µ, ν) = ZX1ZX2 Hi(x, y)dµ(x)dν(y)i= 1,2, donde las integrales que se toman son de Lebesgue. 3.4. Existencia equilibrios de Nash En el capítulo previo se ha visto que la continuidad de la función de pagos y la compacidad de los conjuntos de estrategias eran sucientes para la existencia de un equilibrio en estrategias mixtas para los juegos de suma nula. Se verá que también bastan estas condiciones en el caso que nos incumbe. Primero se prueba la existencia de un equilibrio en estrategias mixtas para un juego bipersonal. Esta demostración está basada en el teorema del punto jo de Kakutani, estudiado en el primer capítulo. Teorema 3.4.1. Sea Γ(A, B) un juego bimatricial m×n . Entonces existen las estrategias mixtas x∗∈X1 e y∗∈X2 para J1 y J2 respectivamente tal que el par (x∗,y∗) es un equilibrio de Nash. Demostración. Los conjuntos de estrategias mixtas X1 y X2 son poliedros (politopos tridimensionales) convexos . Luego el conjunto de situaciones X1×X2 es un convexo compacto. Sea ψ la función: ψ:X1×X2→X1×X2, dada por ψ(x0,y0) = {(x0,y0)|K1(x0,y0) = m´ax X1 K1(x,y0), K2(x0,y0) = m´ax X2 K2(x0,y0)}. 36 3 Juegos de Suma No Nula Así la imagen de ψ consiste en los pares de las mejores estrategias para reaccionar a las estrategias x0 y y0 respectivamente. Se recuerda que las funciones K1 y K2 son las esperanzas matemáticas de los pagos en la combinación de estrategias (x,y) . Dichas funciones son bilineales y, por tanto, la imagen ψ(x0,y0) representa un subconjunto convexo compacto de X1×X2 . Además, si la sucesión de pares {(xn 0,yn 0)},(xn 0,yn 0)∈X1×X2 y {(x0 n,y0 n)},(x0 n,y0 n)∈ψ(xn 0,yn 0) tiene puntos límites l´ım n→∞ (xn 0,yn 0)=(x0,y0),l´ım n→∞ (x0 n,y0 n) = (x0,y0), entonces, por la bilinearidad de las funciones K1 y K2 y por la compacidad de los conjuntos X1 y X2 , se tiene que (x0,y0)∈ψ(x0,y0) . Así, por el teorema de Kakutani existe una situación (x∗,y∗)∈X1×X2 para la cual (x∗,y∗)∈ψ(x∗,y∗) , i.e. K1(x∗,y∗)≥K1(x,y∗)K2(x∗,y∗)≥K2(x∗,y), para todo x∈X1 e y∈X2 , completándose la demostración del teorema Nota 3. El teorema anterior puede ser extendido al caso en que los conjuntos de estrategias sean innitos e inducen unas funciones continuas de pago. Finalmente remarcar que el de equilibrio de Nash es probablemente, el concepto de solución más importante. Dado un equilibrio de Nash, la desviación hacia otra elección de estrategias, provoca una alteración en los benecios de varios jugadores, pudiendo ser éstos negativos. Cuando algún jugador se pregunta por qué usar un equilibrio de Nash, la respuesta debe ser: ¾por qué no? y dejar que piense lo que cree que el resto de jugadores deben hacer. En general, el concepto solución es cualquier regla para especicar predicciones sobre cómo los jugadores podrían comportarse dado un juego. 37 Juegos de Suma No Nula 3 3.5. Equilibrios en estrategias mixtas conjuntas En esta sección se considera un juego bipersonal para mejor la comprensión de la misma. Como se ha explicado en la sección 3.2, habrá equilibrios que serán más bene- ciosos para un jugador que para el otro. Ésto conlleva ciertos problemas a la hora de encontrar una solución mutuamente propicia en un conicto no antagónico. Por ello, se puede examinar cómo se formaliza un conicto donde los intereses no están enfrentados, permitiendo a los jugadores tomar una decisión conjunta. Denición 3.5.1. Una estrategia mixta conjunta es una distribución de probabilidad sobre el conjunto de pares de estrategias puras (i, j) , que no está necesariamente generada por elecciones aleatorias independientes de las estrategias puras. Una estrategia mixta en el juego bimatricial Γ(A, B) será denotada por M . Así si se juega esta estrategia por ambos jugadores, sus pagos esperados K1(M) y K2(M) serán: K1(M) = X i,j αijµij K2(M) = X i,j βijµij, donde A= (αij) y B= (βij) son las matrices de pago y M= (µij) tal que uMw = 1 con u= (1,...,1) ∈Rm y w= (1,...,1) ∈Rn . Geométricamente el conjunto de todos los posibles vectores de pago correspondientes a las estrategias mixtas es la envolvente convexa del conjunto de todos los posibles vectores de pago correspondientes a las estrategias puras. Denición 3.5.2. Para el juego bimatricial Γ(A, B) , sea M= (µij) la probabilidad conjunta sobre los pares (i, j) con i= 1, . . . , m, j = 1, . . . , n . Se denota por µi(j) a la probabilidad condicionada de que J2 realice la estrategia j -ésima si J1 ha realizado la estrategia i -ésima. Análogamente, se denota por νj(i) a la probabilidad condicionada de 38 3 Juegos de Suma No Nula que J1 realice la estrategia i -ésima si J2 ha realizado la estrategia j -ésima. Entonces: µi(j) =    µij Pn j=1 µij , si Pn j=1 µij 6= 0, 0, si µij = 0, j = 1, . . . , n νj(i) =    µij Pm i=1 µij , si Pm i=1 µij 6= 0, 0, si µij = 0, i = 1, . . . , m. Entonces se dice que M∗= (µ∗ ij) es un equilibrio en estrategias mixtas conjuntas si se cumplen las siguientes desigualdades: n X j=1 αijν∗ i(j)≥ n X j=1 αi0jν∗ i(j) m X i=1 αijµ∗ j(i)≥ m X i=1 αij0µ∗ j(i) (3.5.1) para todo i, i0∈ {1, . . . , m} y para todo j, j0∈ {1, . . . , n} . El juego Γ(A, B) en estrategias mixtas conjuntas puede ser interpretado de la siguiente forma: Se supone que los jugadores han alcanzado un acuerdo en estrategias conjuntas M∗= (µ∗ ij) y el J1(J2) elige la estrategia i ( j respectivamente); se ha producido la situación (i, j) . Remarcar que cada jugador sólo conoce su plan de acción. En general, el jugador 1(2) puede no estar de acuerdo en escoger i ( j respec.) de la estrategia conjunta y escoge i0 ( j0 ). Si M∗ es un equilibrio, se sigue de 3.5.1 que es desfavorable para cada jugador desviarse de la realización propuesta i ( j ), donde los lados izquierdos de las desigualdades coinciden con los pagos esperados de J1(J2) suponiendo que se acuerda la realización de i ( j ). Si se supone que J1 elige la estrategia i tal que µij = 0 , con j= 1, . . . , n , entonces la primera desigualdad de 3.5.1 se satisface. De la misma forma, suponiendo que J2 elige la estrategia j tal que µij = 0 , con i= 1, . . . , m , entonces la segunda desigualdad de 39 Juegos de Suma No Nula 3 3.5.1 se satisface. Ahora sustituyendo las expresiones de µi(j) y νj(i) en términos de µij en 3.5.1, se sigue que es condición necesaria y suciente de equilibrio que se cumplan: n X j=1 αijν∗ i(j)≥ n X j=1 αi0jν∗ i(j) m X i=1 αijµ∗ j(i)≥ m X i=1 αij0µ∗ j(i) m X i=1 n X j=1 µ∗ ij = 1 µ∗ ij ≥0 para todo i, i0∈ {1, . . . , m} y para todo j, j0∈1, . . . , n . 40 4 Aplicación: El Penalty de Nash Los deportes profesionales, como el fútbol, son un laboratorio excelente para observar las interacciones estratégicas humanas; son situaciones reales en un ambiente perfectamente controlado. El estudio se centra en analizar cómo dos jugadores se comportan en un lanzamiento de penalty. Tiene cierta relevancia ya que los intentos para dar ejemplos empíricos de jbsn daban resultados que no se correspondían con la teoría, porque muchas dependen de numerosas propiedades de la función de pagos. Luego los teóricos que examinan este tipo de situaciones se enfrentaban a algo tan abstracto como un juego en una hoja de papel. Así se decidió empezar un análisis donde realmente había jugadores tomando decisiones. 4.1. Introducción Este capítulo está basado en un estudio realizado en Palacios-Huerta (2002a). Al encontrarse problemas para probar empíricamente estudios teóricos, muchos autores se han visto obligados a probar las predicciones en un entorno experimental. Pero, a pesar de la controlada estructura de los experimentos, a menudo los resultados rechazaban la hipótesis de que los sujetos están jugando de acuerdo a las implicaciones teóricas de un juego de equilibrio. Por ejemplo, muchos experimentos han evaluado la utilidad empírica del Teorema de Minimax de Neumann (1928) para juegos bipersonales de suma nula, generando resultados contradictorios y, frecuentemente, negativos. Así, en entornos experimentales los jugadores se enfrentan a situaciones no conocidas y ésto, a pesar de su simpleza, hace que no se conviertan en expertos a lo largo del tiempo, contribuyendo, a su vez, a generar numerosos estudios sobre el juego sin tener 41 Aplicaciones 4 en cuenta el equilibrio. Consecuentemente, la mayoría de pronósticos relacionados con equilibrios no han recibido apoyo real. Este capítulo ofrece una prueba empírica donde es aplicable el concepto de equilibrio en situaciones de interacciones estratégicas. Tanto en el Teorema del Minimax como en el concepto de equilibrio de Nash, es fundamental el hecho de que un jugador debe ser imprevisible a su oponente. Se usarán datos de un juego estratégico que se da en el deporte profesional para ofrecer una prueba empírica del teorema del Minimax. Es más, las características especícas del juego y su entorno, permiten sobreponerse a las habituales inconveniencias de la aplicación real de dicho teorema. En los deportes profesionales los jugadores son expertos en los juegos, lo que hace que sea una ventaja con respecto a otros experimentos ya que son los más capaces de controlar la situación del juego. Sin embargo, la gran cantidad de estrategias a escoger y las múltiples consecuencias que se obtienen al aplicarlas hacen que no sea factible llegar a resultados precisos a la hora de usar empíricamente las hipótesis del teorema del Minimax. Pero, todas estas dicultades e inconvenientes se superan en la situación que se analizará en esta sección, que es un jbsn que requiere impredecibilidad y que ambos jugadores busquen el mejor resultado. Como en las condiciones habituales, el juego tiene perfectamente denido un conjunto de reglas, (pocas) estrategias disponibles, los resultados se dan inmediatamente después de que se decidan las estrategias y toda la información relevante es visible. El análisis trata uno de los juegos más famosos del mundo: lanzamientos de penalties en fútbol. Para probar las implicaciones del teorema del Minimax, se analizan más de 1400 lanzamientos de partidos profesionales que incluyen información muy detallada de todos los aspectos relevantes del juego, especialmente acciones y resultados. 42 4 Aplicaciones Como breve adelanto de los resultados principales, se encuentra que, como predice la TJ en estrategias mixtas: Las probabilidades de éxito son estadísticamente idénticas usando cualquier estrategia. Las elecciones son temporalmente independientes. A continuación se describe cómo está organizado lo que resta del capítulo. La siguiente sección describe la estructura y escenario del juego, evaluándose también la hipótesis empírica. En la sección 3 se describen los datos recogidos y en la 4 se analizan. La quinta sección contiene una evaluación de las pruebas realizadas frente a un criterio diferente al del Minimax. Por último, en la sección 6 se concluye y se estudia la relevancia que ha tenido este análisis en posteriores aplicaciones. Nota 4. A partir de ahora, se omitirá teorema del Minimax de Von Neumann, re- riéndose a este simplemente como el teorema. En caso de utilización de otro, se pondrá explícitamente. 4.2. Estrategias mixtas en lanzamientos de penalties Aunque es mundialmente conocido, se describen las características de un penalty. Para empezar diremos que el árbitro señala penalty cuando un equipo comete una de las diez infracciones existentes en el fútbol dentro de su área mientras el balón está en juego. El penalty tiene las siguientes particularidades: La pelota se coloca en el punto de penalty. Éste está colocado dentro del área a 11 metros de la línea de gol. 43 Aplicaciones 4 El jugador que va a realizar el lanzamiento está perfectamente identicado. El portero permanece en la línea de gol, equidistante a los postes y enfrente del lanzador, hasta que éste tire. El resto de jugadores se colocan fuera del área de penalty, detrás del punto de penalty y, como mínimo, a 9.15 metros del punto fatídico. El lanzador golpea el balón hacia delante. No puede tocar otra vez el esférico hasta que no lo haya tocado otro jugador. Figura 4.1 El balón suele tardar 0.3 segundos en recorrer la distancia del punto de penalty hasta la portería. Portero y lanzador deben moverse simultáneamente. Tiene solo dos posibles 44 4 Aplicaciones Antes de comenzar cualquier prueba formal, vale la pena examinar hasta qué punto los datos de la muestra coinciden con las predicciones de equilibrio de Nash. Para todos los jugadores de la muestra, las probabilidades de anotar son las siguientes: pI1−pI lI 58.3 94.97 1−lI 92.91 69.92 (4.4.1) donde, como se ha indicado previamente, lI y pI denotan que lanzador y portero escogen el lado no natural. La estrategia mixta del equilibrio de Nash predijo las frecuencias con la que los jugadores eligen una estrategia y otra. A continuación se compara los datos reales con las predicciones realizadas: pI (%) 1−pI (%) lI (%) 1−lI (%) Frecuencias pronosticadas por eq.N 41.99 58.01 38.54 61.46 Frecuencias reales 42.31 57.69 39.98 60.02 (4.4.2) Se observa que las predicciones teóricas son prácticamente idénticas que los datos observados. Las frecuencias pronosticadas por equilibrio de Nash se obtienen de las ecuaciones 4.2.1 y 4.2.2. Nota 5. Los datos mostrados a lo largo de la sección, como los que dan las tablas 4.4.1 y 4.4.2 , se pueden encontrar en Palacios-Huerta (2002b). Se pasa a probar las implicaciones del teorema. 51 Aplicaciones 4 4.4.1. Pruebas individuales Sean pi j la probabilidad de que el jugador i triunfe cuando elige la estrategia j∈ {I, D} , ni j el número de veces que i escoge j y Ni jE y Ni jF el número de veces que el lanzador (portero) i obtiene éxito ( E ) o fracaso ( F ) anotando (fallando) el penalty cuando elige la estrategia j . Por tanto, la hipótesis nula será: pi D=pi I=pi Cuando pi es sustituido por su estimador de máxima verosimilitud Ni IE +Ni DE ni I+ni D , entonces el estadístico de Pearson para el jugador i será: Pi=X j∈{I,D}(Ni jE −ni jpi)2 ni jpi+(Ni jF −ni j(1 −pi))2 ni j(1 −pi), está distribuido asintóticamente como una χ2 con 1 grado de libertad. Los resultados de las pruebas están reejados en la Tabla 3. Los datos demuestran que la hipótesis nula no se rechaza para la mayoría de jugadores. De los 42 jugadores de la muestra, la hipótesis se rechaza para 3 jugadores (2 lanzadores y 1 portero) al nivel de signicancia del 5% y para 5 jugadores (3 lanzadores y 2 porteros) al del 10%. Nótese, que con 42 datos, el número esperado de rechazos a un nivel del 5% es 2.1 y para uno del 10% es 4.2. Estas estimaciones sugieren que, a nivel individual, la hipótesis de que la probabilidad de anotar es idéntica sea cual sea la estrategia escogida no se puede rechazar para la mayoría de jugadores. 52 4 Aplicaciones Estrategia Porcentaje acierto Estadístico Jugador Obs I D I D Pearson p− valor Lanzador 1 34 0.32 0.68 0.91 0.91 0.000 0.970 Lanzador 2 31 0.35 0.65 0.82 0.80 0.020 0.902 Lanzador 3 40 0.48 0.52 0.74 0.76 0.030 0.855 Lanzador 4 38 0.42 0.58 0.88 0.91 0.114 0.735 Lanzador 5 38 0.50 0.50 0.79 0.84 0.175 0.676 Lanzador 6 46 0.28 0.72 0.70 0.77 0.185 0.667 Lanzador 7 41 0.20 0.80 0.75 0.82 0.191 0.662 Lanzador 8 35 0.31 0.69 0.82 0.75 0.199 0.656 Lanzador 9 31 0.19 0.81 0.83 0.92 0.416 0.519 Lanzador 10 35 0.37 0.63 0.86 0.77 0.476 0.490 Lanzador 11 32 0.48 0.52 0.87 0.94 0.521 0.471 Lanzador 12 32 0.48 0.52 0.87 0.94 0.521 0.471 Lanzador 13 38 0.55 0.45 0.76 0.88 0.907 0.341 Lanzador 14 30 0.33 0.67 0.90 0.75 0.938 0.333 Lanzador 15 30 0.50 0.50 0.80 0.93 1.154 0.283 Lanzador 16 42 0.43 0.57 0.89 0.75 1.287 0.257 Lanzador 17 40 0.42 0.58 0.58 0.85 1.637 0.201 Lanzador 18 36 0.44 0.56 0.90 0.77 1.665 0.197 Lanzador 19 49 0.48 0.52 0.74 0.90 1.761 0.184 Lanzador 20 40 0.35 0.65 0.93 0.69 2.913 0.088* Lanzador 21 40 0.42 0.58 0.65 0.91 4.322 0.038** Lanzador 22 40 0.40 0.60 1.00 0.75 4.706 0.030** Todos los lanzadores 808 0.3998 0.6002 0.8111 0.8268 Portero 1 37 0.38 0.62 0.21 0.22 0.000 0.982 Portero 2 38 0.39 0.61 0.20 0.22 0.017 0.898 Portero 3 30 0.60 0.40 0.28 0.25 0.028 0.866 Portero 4 50 0.46 0.54 0.17 0.15 0.061 0.804 Portero 5 36 0.33 0.67 0.25 0.21 0.080 0.777 Portero 6 34 0.44 0.56 0.27 0.21 0.147 0.702 Portero 7 37 0.19 0.81 0.14 0.10 0.221 0.638 Portero 8 37 0.54 0.46 0.25 0.18 0.294 0.588 Portero 9 32 0.56 0.44 0.22 0.14 0.326 0.568 Portero 10 40 0.45 0.55 0.11 0.18 0.388 0.533 Portero 11 33 0.18 0.82 0.17 0.30 0.416 0.519 Portero 12 30 0.27 0.73 0.25 0.14 0.545 0.460 Portero 13 34 0.41 0.59 0.14 0.25 0.578 0.447 Portero 14 40 0.50 0.50 0.15 0.25 0.625 0.429 Portero 15 44 0.45 0.55 0.10 0.21 0.957 0.328 Portero 16 36 0.31 0.69 0.09 0.24 1.804 0.298 Portero 17 42 0.55 0.45 0.30 0.11 2.449 0.118 Portero 18 42 0.38 0.62 0.13 0.35 2.506 0.113 Portero 19 42 0.40 0.60 0.35 0.12 3.261 0.071* Portero 20 40 0.50 0.50 0.08 0.37 5.104 0.024** Todos los porteros 754 0.4231 0.5769 0.1943 0.2068 TABLA 3 Pruebas de igualdades en las probabilidades de acierto Nota: *Indica hipótesis nula rechazada al nivel 10%, y ** indica al 5%. 53 Aplicaciones 4 Cuadro A: Tests de Pearson Tests de las hipótesis conjunta de que los datos para todos las pruebas fueron generados por el juego de equilibrio: pi I = pi D para cada jugador i Estadístico de Pearson Grados de libertad p− valor Todos los jugadores 43.944 42 0.389 Todos los lanzadores 24.138 22 0.340 Todos los porteros 19.806 20 0.470 Cuadro B: Tests de Kolmogorov-Smirnov Tests de las hipótesis nula de que las distribuciones de los p-valores en los tests individuales de Pearson están generados por una toma decisión aleatoria sobre distribución uniforme U(0,1). Estadístico de KS p− valor Todos los jugadores 0.527 0.883 Todos los lanzadores 0.396 0.891 Todos los porteros 0.373 0.832 TABLA 4 Pruebas de igualdades en las probabilidades de acierto para una distribución conjunta 4.4.2. Pruebas conjuntas Ahora se analizará si en el comportamiento grupal puede considerarse en equilibrios, probando la hipótesis de que cada uno de los experimentos están simultáneamente generado por un juego de equilibrio. En este caso, el estadístico para el test de Pearson es la suma de los estadísticos individuales Pi . Bajo la hipótesis nula, el test sigue la distribución χ2 con 42 grados de libertad. Remarcar que este test conjunto permite diferencias en las probabilidades pi de los jugadores. Los resultados se muestran en la Tabla 4. El primer cuadro muestra que el estadístico de Pearson es 43.94 y el p− valor asociado 0.389, lo que indica que la hipótesis nula de que los datos para todos los jugadores están generados por un juego de equilibrio no puede ser rechazada para los convencionales niveles de signicancia. Si los lanzadores y porteros son considerados como grupos separados, entonces, bajo la hipótesis nula, el estadístico está distribuido como una χ2 con 22 y 20 grados de libertad respectivamente. Mientras que el estadístico de Pearson para los lanzadores es 24.138 con un p− valor asociado de 0.340, el estadístico para los portero vale 19.806 con un p− valor de 0.470. La hipótesis de la igualdad de probabilidades de 54 4 Aplicaciones ganar tampoco puede ser rechazada para ninguno de los subgrupos. Se sabe que el test de Pearson conjunto presenta el problema de que tiene poco poder frente a la hipótesis alternativa en cuanto a cómo se han generado los datos. El cuadro B muestra un test más potente que reeja que los resultados son consistentes coon la teoría. Bajo la hipótesis nula, todas las observaciones fueron generadas por juegos de equilibrios con los p− valores asociados al estadístico Pi deben ser 42 sorteos de una distribución estándar uniforme U(0,1) . Los valores 0 y 1 representan los extremos del intervalo donde la variable toma valores no nulos. Se recuerda que la función densidad de una variable aleatoria que sigue una distribución uniforme estándar viene dada por: f(x) = χ[0,1](x) donde χ[a,b] es la función indicador en el intervalo [a, b] . Con una simple comparación con la distribución de los p− valores de la Tabla 3 se puede comprobar que los resultados son consistentes con la teoría ya que los p− valores están distribuidos uniformemente a través de deciles. Una evaluación formal puede hacerse comparando la distribución de los p− valores con la distribución uniforme usando el test de Kolmogorov-Smirnov (KS). El valor del estadístico KS para todos los jugadores considerados simultáneamente es 0.527 con un p− valor de 0.883. Cuando se consideran solo los lanzadores simultáneamente el estadístico KS es 0.396 con un p− valor de 0.891; para los porteros es 0.373 con un p− valor asociado de 0.832. Nota 6. El autor realizó un test de Kolmogorov-Smirnov aunque la muestra es menor de 50 individuos, pudiéndose usar el test de Smirnov-Wilk. En todos los casos, el p− valor ni siquiera se ha acercado para rechazar la hipótesis de que las probabilidades de ganar son las mismas sea cual sea la estrategia. Además, como se verá en la siguiente sección, los tests tienen tal poder que permiten distinguir estrategias de equilibrio y estrategias de no equilibrio. 55 Aplicaciones 4 4.4.3. Interpretación y discusión Como en todo juego estrictamente competitivo, los intereses de los jugadores en los lanzamientos de penalties son totalmente opuestos. Los resultados de la muestra indican que las acciones tanto de los porteros como de los lanzadores pueden ser interpretadas como un maxminimizador para cada jugador en el sentido que sus acciones maximizan las recompensas que se pueden garantizar. Se sabe que un jugador utiliza la estrategia maximin si elige una estrategia que es la mejor para él suponiendo que el oponente va a elegir una para perjudicarle. Por tanto, en este sentido, las pruebas empíricas de los lanzamientos de penalties son consistentes con la teoría de equilibrios de Nash. Nótese las dos características especiales de este juego. Primero, no todos los penalties son lanzados al mismo tiempo. Por ello, los jugadores pueden tener información previa del oponente, hecho que contradice las hipótesis del teorema. Sin embargo, los resultados sugieren que no; se observa que los jugadores actúan instintivamente e intuitivamente. Segundo, los rivales van cambiando. Los equilibrios en estrategias mixtas proporcionan una buena descripción de estado estable en el comportamiento de los jugadores que compiten repetidas veces contra oponentes seleccionados al azar. Los jugadores, sin embargo, podrían servirse de enfrentamientos previos como ayuda. No obstante, se observa que sus decisiones son secuencialmente independientes; no siguen ningún patrón. Por tanto, no eligen las estrategias basándose en elecciones anteriores propias o de los rivales. Además existen más análisis realizables para conrmar la idea que los equilibrios en estrategias mixtas describen el comportamiento estable de un jugador dado que se 56 4 Aplicaciones enfrenta a oponentes al azar. Por ejemplo, consideramos el lanzador número 2 (Alan Shearer) de la Tabla 3. Al no rechazarse la hipótesis nula, es indiferente que elija D o I , i.e., las probabilidades de que anote son las mismas si escoge su lado natural o no. Se supone ahora que, en vez de tener 31 observaciones, se tienen el doble. Se toma un subconjunto de 30 observaciones de las 62. Entonces, en teoría, se rechazará la hipótesis nula o, al menos, habría una variación signicativa de los p− valores de la prueba. Implementando esta idea para muchas otras submuestras, se demuestra que la media de los p− valores son muy similares a los obtenidos en la Tabla 3 para cada lanzador y portero. Además, la desviación estándar de los p− valores es muy pequeña, siempre por debajo de 0.187. Estos resultados ratican la idea que, dado un jugador, su oponente ha sido elegido al azar. 4.5. Debate y pruebas adicionales Las pruebas empíricas del comportamiento de futbolistas profesionales en lanzamientos de penalties proporcionan un apoyo considerable a las dos implicaciones que se derivan de la hipótesis de que los participantes juegan siguiendo la teoría de equilibrio. Los resultados útiles obtenidos en las pruebas son, en gran parte, gracias a que los participantes son profesionales, ya que son capaces de generar secuencias al azar y aprender a considerar la forma correcta de enfrentarse en un jbsn. La motivación y los incentivos son altos y, tanto las elecciones estratégicas como todos los rasgos relevantes del entorno, son visibles. La experiencia de los jugadores hace que se necesiten pocos elementos en la muestra para aplicar el teorema en comparación con la cantidad de datos producidos en escenarios experimentales. Otra característa muy útil en este ejemplo de juego es que se pueden calcular los 57 Aplicaciones 4 equilibrios para ambos jugadores. En el caso del servicio en tenis, por ejemplo, sólo es posible calcularlo para quien saca. Se puede encontrar un estudio sobre la aplicación del teorema en el tenis en Walker y Wooders (2001). Además la independencia secuencial que se da en los lanzamientos de penalties no suele ser común en juegos con condiciones naturales o experimentales. 4.6. Conclusión Durante las últimas décadas, la teoría de juegos no cooperativos se ha convertido en una herramienta muy útil en economía y otras ciencias sociales. A pesar de los numerosos avances, sigue siendo un reto importante enfrentarse al problema de refutar con pruebas empíricas las predicciones realizadas por la teoría de juegos. El análisis realizado aprovecha la experiencia de los jugadores, bajo condiciones naturales, para proporcionar pruebas consistentes relativas al concepto de equilibrio en todos los aspectos: (i) las probabilidades de ganar son estadísticamente idénticas para todas las estrategias (ii) los jugadores generan secuencias independientes e ignoran cualquier posible vínculo estratégico entre las jugadas. Estos resultados representan la primera vez que las dos implicaciones del Teorema del Minimax de Neumann (1928) son respaldadas bajo condiciones naturales. Este análisis fue utilizado para aconsejar cómo tirar la tanda de penalties a varios clubes de fútbol. Por ejemplo, en la competición más famosa de clubes, la UEFA Champions League, se realizó un informe basado en estos datos para la nal de la temporada 2007-2008 que enfrentaban a los equipos ingleses de Manchester United frente al Chelsea. En el informe realizado por Palacios-Huerta para el Chelsea, se mostraba que el 58 Aplicaciones portero del rival, Edwin Van der Saar, se tiraba demasiado al lado natural del lanzador (80% de las ocasiones), que paraba más penalties a media altura que los que iban rasos o altos, y que muchos jugadores eran predecibles: Cristiano Ronaldo lanzaba el 85% de las veces a la derecha del portero, dato que sirvió para que el guardameta del Chelsea adivinara el lanzamiento de la estrella portuguesa. Fue también contratado por Holanda para una hipotética tanda en la nal del mundial de 2010, pero Iniesta tenía otros planes. Otra aplicación se recoge en la revista económica American Economic Review (AER). Palacios-Huerta y Apesteguia (2009) muestra que el primero que tira en la tanda de penalties tiene un 60% de probabilidades de ganar. Ésto reeja que el azar importa demasiado en este tipo de juegos. Por ello, Palacios-Huerta propone invertir el orden de lanzamiento cada 2 penalties, para igualar las fuerzas, haciendo que el azar tenga la menor cabida posible. Esta propuesta fue remitida al máximo organismo del fútbol profesional, la FIFA, pero hasta ahora, no han llevado a cabo cambio alguno en las tandas de penalties. Del estudio realizado por el autor, sacamos que a la hora de aplicar las conclusiones realizadas a un penalty, como las probabilidades de acertar tanto para el lanzador como para el portero son las mismas si eligen lado natural o no. Por lo tanto, hay un equilibrio en estrategias mixtas de: (I, D) = (1/2,1/2) reriéndose I que el jugador elige el lado no natural y D elige el centro o lado natural. 59 Aplicaciones .1. Apéndice. Identidades de lanzadores y porteros A continuación se muestran los jugadores que se han analizado en los penalties; están agrupados por países. Entre corchetes la identicación de cada uno en la Tabla 3 y entre paréntesis los equipos donde jugaban. Lanzadores Italia : [9] Batistuta(Roma), [13] Baggio(Brescia), [11] Del Piero(Juventus), [5] Mihajlovic(Lazio), [15] Chiesa(Fiorentina), [6] Signori(Bologna), [7] Rui Costa(Milán), [8] Amoroso(Udinese), [1] Mendieta(Lazio). España : [22] Penev(Atlético de Madrid), [17] Hierro(Real Madrid), [16] Larrazábal(Athletic de Bilbao), [14] Garitano(Zaragoza), [19] Catanha(Celta), [20] Donosti(Eibar), [12] Juninho(Atlético de Madrid), [10] Rivaldo(Barcelona), [3] Zidane(Real Madrid). Inglaterra : [2] Shearer(Newcastle), [4] Bergkamp(Arsenal), [21] Finidi(Ipswich Town), [18] Suker(West Ham). Porteros Italia : [7] Toldo(Inter Milán), [9] Mazzantani(Perugia), [10] Peruzzi(Lazio), [14] Pagliuca(Bologna), [11] Taivi(Atalanta), [3] Brivio(Venezia), [12] Buon(Juventus). España : [2] César(Real Madrid), [1] Alberto(Real Sociedad), [13] Cañizares(Valencia), [4] Ceballos(Racing de Santander), [17] Stelea(Salamanca), [18] Etxeberria(Rayo Vallecano), [8] Molina(Deportivo Coruña), [19] Juanmi(Real Zaragoza), [20] Dutruel(Barcelona), [16] Esteban(Real Oviedo), [5] Toni Prats(Real Betis). 60