Optimización lineal aplicada a teoría de juegos

FACULTAD DE MATEM´ ATICAS DEPARTAMENTO DE AN´ ALISIS MATEM´ ATICO Trabajo Fin de Grado OPTIMIZACI ´ ON LINEAL APLICADA A TEOR´ IA DE JUEGOS Alejandro Serrano Gallardo Dirigido por: Victoria Mart´ın M´arquez Sevilla, Junio 2017. ´ Indice general Breve introducci´on hist´orica 1 1. Preliminares 9 1.1. Conceptos b´asicos de la Teor´ıa de Juegos . . . . . . . . . . . . 9 1.2. Conceptos b´asicos de la Programaci´on Lineal . . . . . . . . . . 11 2. Juegos no cooperativos 15 2.1. Introducci´on a los Juegos en Forma Estrat´egica . . . . . . . . 15 2.2. El Equilibrio de Nash en Juegos en Forma Estrat´egica . . . . . 18 2.3. Juegos Bipersonales de Suma Nula . . . . . . . . . . . . . . . 21 2.4. Estrategias Mixtas en Juegos Finitos . . . . . . . . . . . . . . 26 2.5. Juegos Matriciales y Algoritmos . . . . . . . . . . . . . . . . . 30 2.6. Juegos Matriciales y Programaci´on Lineal . . . . . . . . . . . 40 3. Juegos Cooperativos 47 3.1. Introducci´on............................ 47 3.2. El Core y Conceptos Relacionados . . . . . . . . . . . . . . . . 49 3.3. Juegos de producci´on lineal . . . . . . . . . . . . . . . . . . . 54 3.4. ElNucleolus............................ 60 Bibliograf´ıa 68 i ii Optimizaci´on Lineal aplicada a Teor´ıa de Juego ABSTRACT In the following TFG we deal with the Game Theory and with the application that the Linear Programming has on it. We start defining some key concepts that will serve us as a base. Within the Game Theory there are manly two theories: the cooperative one and the non-cooperative one. We consider that the non-cooperative approach is the most appropriate to analyse our problem, that is: every single player might find its own strategies considering that the others will use their best strategies as well. To this effect, we will use the Linear Programming to obtain the most accurate solution. On the other side, the cooperative approach deals with the assumption that the hypothetical players are going to cooperate and, to this respect, they will act according to the most suitable social way, focusing on how the players should divide out the benefits of its cooperation. Due to those reasons, we will use the Core and the Nucleolus and revise the Linear Production Games, in which the Linear Programming furnishes on how to spread the benefits within extensive coalitions. iii iv Optimizaci´on Lineal aplicada a Teor´ıa de Juego Breve introducci´on hist´orica La Programaci´on Lineal estudia el problema de minimizar o maximizar una funci´on lineal en presencia de desigualdades lineales. Desde que George B. Dantzig desarroll´o el m´etodo simplex en 1947, la programaci´on lineal se ha utilizado extensamente en el ´area militar, industrial, gubernamental y de planificaci´on urbana, entre otras. Su popularidad se puede atribuir a muchos factores, incluyendo su potencial para modelar problemas grandes y complejos, y la habilidad de los usuarios para resolver problemas a gran escala en un intervalo de tiempo razonable mediante el uso del m´etodo simplex y de computadoras. A partir de la Segunda Guerra Mundial se hizo evidente que era esencial la planificaci´on y coordinaci´on entre varios proyectos, as´ı como el uso eficaz de los recursos disponibles. En junio de 1947 se inici´o un trabajo intensivo del equipo de la Fuerza A´erea de los EE.UU. conocido como SCOOP (Scientific Computation of Optimum Programs). Como resultado, George B. Dantzig desarroll´o el m´etodo simplex a finales del verano de 1947. El inter´es de la programaci´on lineal se difundi´o r´apidamente entre economistas, matem´aticos, estad´ısticos e instituciones gubernamentales. Desde la creaci´on del m´etodo simplex mucha gente ha contribuido al crecimiento de la programaci´on lineal, ya sea desarrollando su teor´ıa matem´atica, dise˜nando c´odigos y m´etodos computacionales eficientes, experimentando nuevas aplicaciones, y tambi´en utilizando la programaci´on lineal como una herramienta auxiliar para resolver problemas m´as complejos como son pro- 1 2 Optimizaci´on Lineal aplicada a Teor´ıa de Juego gramas enteros, programas discretos, programas no lineales, problemas combinatorios, problemas de programaci´on estoc´astica y problemas de control ´optimo. La Teor´ıa de Juegos como tal fue creada por el matem´atico h´ungaro John von Neumann (1903-1957) y por Oskar Morgenstern (1902-1976) en 1944 gracias a la publicaci´on de su libro ”The Theory of Games Behavior”. Anteriormente los economistas Cournot y Edgeworth hab´ıan anticipado ya ciertas ideas, a las que se sumaron otras posteriores de los matem´aticos Borel y Zermelo que en uno de sus trabajos (1913) muestra que juegos como el ajedrez son resolubles. Sin embargo, no fue hasta la aparici´on del libro de von Neumann y Morgenstern cuando se comprendi´o la importancia de la Teor´ıa de Juegos para estudiar las relaciones humanas. Von Neumann y Morgenstern investigaron dos planteamientos distintos de la Teor´ıa de Juegos. El primero de ellos es el planteamiento estrat´egico o no cooperativo. Este planteamiento requiere especificar detalladamente lo que los jugadores pueden y no pueden hacer durante el juego, y despu´es cada jugador buscar´a una estrategia ´optima. En la segunda parte de su libro, von Neumann y Morgenstern desarrollaron el planteamiento coalicional o cooperativo, en el que buscaron describir la conducta ´optima en juegos con muchos jugadores. Puesto que ´este es un problema mucho m´as dif´ıcil, sus resultados fueran mucho menos precisos que los alcanzados para el caso de suma cero y dos jugadores, ambos juegos no cooperativos. En los a˜nos 50 hubo un desarrollo importante de estas ideas en Princeton, con Luce and Raiffa (1957), difundiendo los resultados en su libro introductorio, Kuhn (1953) que permiti´o establecer una forma de atacar los juegos cooperativos, y por fin Nash (1950) quien defini´o el equilibrio que lleva su nombre, lo que permiti´o extender la Teor´ıa de Juegos no-cooperativos m´as BREVE INTRODUCCI ´ ON HIST ´ ORICA 3 generales que los de suma cero. Durante esa ´epoca, el Departamento de Defensa de los EE.UU. fue el que financi´o las investigaciones en el tema, debido a que la mayor parte de las aplicaciones de los juegos de tipo suma-cero se concentraban en temas de estrategia militar. John Forbes Nash (1928-2015) es el nombre m´as destacado relacionado con la Teor´ıa de Juegos. A los 21 a˜nos escribi´o una tesina de menos de treinta p´aginas en la que expuso por primera vez su soluci´on para juegos estrat´egicos no cooperativos, lo que desde entonces se llam´o “el equilibrio de Nash”, que tuvo un inmediato reconocimiento entre todos los especialistas. El punto de equilibrio de Nash es una situaci´on en la que ninguno de los jugadores siente la tentaci´on de cambiar de estrategia ya que cualquier cambio implicar´ıa una disminuci´on en sus pagos. Von Neumann y Oskar Morgenstern hab´ıan ya ofrecido una soluci´on similar pero s´olo para los juegos de suma cero. Para la soluci´on formal del problema, Nash utiliz´o funciones de mejor respuesta y el teorema del punto fijo de los matem´aticos Brouwer y Kakutani. En los a˜nos siguientes public´o nuevos escritos con originales soluciones para algunos problemas matem´aticos y de la Teor´ıa de Juegos, destacando la “soluci´on de regateo de Nash” para juegos bipersonales cooperativos. Propuso tambi´en lo que se ha dado en llamar “el programa de Nash” para la reducci´on de todos los juegos cooperativos a un marco no cooperativo. A los veintinueve a˜nos se le diagnostic´o una esquizofrenia paranoica que lo dej´o pr´acticamente marginado de la sociedad e in´util para el trabajo cient´ıfico durante dos d´ecadas. Pasado ese lapsus, en los a˜nos setenta, recuper´o su salud mental y pudo volver a la docencia y la investigaci´on con nuevas geniales aportaciones, consiguiendo en 1994 el Premio N´obel de Econom´ıa compartido con John C. Harsanyi y Reinhart Selten por sus pioneros an´alisis del equilibrio en la Teor´ıa de los Juegos no cooperativos. 10 Optimizaci´on Lineal aplicada a Teor´ıa de Juego cada uno, mientras que en el enfoque no cooperativo se analiza que decisiones tomar´ıa cada jugador en ausencia de acuerdo previo. Entre los juegos no cooperativos cabe hacer dos distinciones b´asicas, juegos est´aticos o din´amicos, y juegos con o sin informaci´on completa. Aunque se explicar´a con m´as detalle cada uno de los t´erminos, se incluye a continuaci´on una primera definici´on de la terminolog´ıa b´asica que se utiliza habitualmente en la Teor´ıa de Juegos. •Jugadores: Participantes que toman decisiones con el fin de maximizar su utilidad. •Acciones de cada jugador: Decisiones que puede tomar cada jugador. El conjunto de acciones de un jugador puede ser finito o infinito. •Resultados del juego: Distintos modos en que puede concluir un juego. Cada resultado conlleva unas consecuencias para cada jugador. •Pagos: Valoraci´on que para cada jugador tienen las consecuencias de alcanzar un determinado resultado. Cada jugador recibe un pago al acabar el juego. •Estrategias: Plan completo de acciones con las que cada jugador participa en el juego. •Forma normal y forma extensiva: Son formas de describir un juego. Ambas especifican los jugadores, las acciones y los pagos. La forma normal o forma estrat´egica organiza la descripci´on centrando su ´enfasis en las estrategias de los jugadores. La forma extensiva lo hace en forma de ´arbol, resaltando la secuencia del juego. En este trabajo nos centraremos en juegos cooperativos y juegos no cooperativos. Veamos ahora un ejemplo: PRELIMINARES 11 Ejemplo 1.1.1. Piedra, papel o tijera. Dos individuos, a los que denominaremos Jugador I y Jugador II, escogen simult´aneamente una de las tres opciones (piedra, papel o tijera). Si uno escoge la piedra y el otro papel, gana quien escoge papel. Si uno escoge la piedra y el otro la tijera, gana el que escoge piedra. Si uno escoge el papel y el otro la tijera, gana quien escoge tijera. Si los dos jugadores eligen la misma opci´on se empata. La informaci´on relevante la podemos resumir en la tabla siguiente: Piedra Papel Tijer Piedra 0 -1 1 Papel 1 0 -1 Tijera -1 1 0 1.2. Conceptos b´asicos de la Programaci´on Lineal En este apartado veremos los conceptos b´asicos que necesitaremos de ahora en adelante de la programaci´on lineal. Definici´on 1.2.1. Un problema de programaci´on lineal es un problema de optimizaci´on con restricciones en el que tanto la funci´on a optimizar, tambi´en llamada funci´on objetivo, como las restricciones son lineales. Todo problema de programaci´on lineal se puede expresar como: minimizar cxt sujeto a xA ≥b, x≥0, (P) donde A es una matriz m×n,ces un vector 1×mybes un vector 1×n. Queremos encontrar una soluci´on factible para el problema (es decir, un vector x∈Rmque satisfaga las desigualdades) de modo que minimice la 12 Optimizaci´on Lineal aplicada a Teor´ıa de Juego funci´on objetivo cxtdentro del conjunto de soluciones factibles; de tal soluci´on decimos que es ´optima para este problema. Definici´on 1.2.2. El dual del problema de la definici´on anterior es el siguiente problema de programaci´on: maximizar byt sujeto a Ayt≤ct, y≥0. (D) Ahora queremos encontrar una soluci´on factible para el problema (es decir, un vector y∈Rnque satisfaga las desigualdades) de modo que maximice la funci´on objetivo bytdentro del conjunto de soluciones factibles; de tal soluci´on decimos que es ´optima para este problema. Si tenemos un par de problemas como los de las dos definiciones anteriores, nos referimos al primero como el problema primal (P) y al segundo como el problema dual (D). A continuaci´on enunciamos un importante resultado que relaciona ambos problemas. Teorema 1.2.3. [Teorema de dualidad ]. Sean (P) y (D) un par de problemas de programaci´on lineal duales. Entonces, 1. (P) tiene una soluci´on ´optima si y solo si (D) tiene una soluci´on ´optima. 2. Supongamos que x e y son soluciones factibles de los problemas (P) y (D), respectivamente. Entonces, x es una soluci´on ´optima de (P) e y es una soluci´on ´optima de (D) si y solo si cxt=byt. Para llegar a la soluci´on de un problema de Programaci´on Lineal se utilizan diferentes m´etodos de soluci´on. Los m´as difundidos son: el m´etodo gr´afico y el M´etodo Simplex. La soluci´on de un problema de Programaci´on Lineal utilizando un procedimiento gr´afico es posible si se tienen no m´as de dos PRELIMINARES 13 variables. El M´etodo Simplex fue el primer m´etodo surgido para solucionar problemas de Programaci´on Lineal, por lo que se le considera el m´etodo de soluci´on cl´asico por excelencia. Teniendo en cuenta la filosof´ıa de este m´etodo han surgido otros m´etodos cuyas ventajas fundamentales se concentran en las posibilidades de los mismos para ser programados por computadoras. El procedimiento gr´afico comienza elaborando una gr´afica que muestre las soluciones posibles (valores x1yx2). La gr´afica tendr´a valores los valores x1en el eje horizontal y los valores x2en el eje vertical. El procedimiento para hallar la soluci´on gr´afica consiste en lo siguiente: 1. Para cada inecuaci´on del sistema de restricciones (medio espacio cerrado) se toma la recta correspondiente y se determinan los interceptos con la gr´afica. Si la recta pasa por el origen del eje de coordenadas, el t´ermino independiente es cero, entonces se traza la recta tomando el origen y otro punto determinado dando un valor arbitrario a una de las variables. 2. Para determinar los puntos que satisfacen cada inecuaci´on se sustituye un punto cualquiera del espacio (se recomienda el origen cuyas coordenadas son (0,0)), y de esta forma se determina si los puntos que satisfacen la misma est´an hacia el lado que est´a el origen o hacia el lado contrario, se˜nalando con una flecha ese lado. Cuando la recta pasa por el origen entonces se toma otro punto cualquiera pero que sean sencillos los valores de sus coordenadas, por ejemplo, (0,1) , (1,0), (1,1), etc. 3. Luego se determina la regi´on soluci´on que es la regi´on del plano que satisface todas las restricciones al mismo tiempo y que debe estar en el primer cuadrante. La figura formada es un poliedro convexo que tiene un conjunto de puntos extremos. 4. Se busca el punto ´optimo entre el conjunto de puntos extremos. Para 14 Optimizaci´on Lineal aplicada a Teor´ıa de Juego eso se sustituye cada par de puntos (x1, x2) de los puntos extremos en la funci´on objetivo y se calcula el valor de Z. Si se est´a maximizando el valor de la misma, el punto ´optimo ser´a aquel que proporcione el valor mayor para Z y si el criterio de optimizaci´on es de minimizar, entonces el punto ´optimo ser´a aquel que proporcione el valor m´ınimo de Z. Este m´etodo gr´afico tiene la desventaja que s´olo permite la soluci´on de problemas que tengan dos variables de aqu´ı que la mayor´ıa de los problemas de programaci´on lineal se resuelvan utilizando como base el m´etodo simplex. El m´etodo del Simplex constituye un procedimiento iterativo algebraico que resuelve cualquier problema en un n´umero finito de pasos. La concepci´on de este m´etodo ha facilitados que otros especialistas del tema desarrollen otros m´etodos de soluci´on con la misma filosof´ıa, pero m´as adecuados para la programaci´on por computadoras. Para explicar el m´etodo simplex es necesario definir un conjunto de conceptos b´asicos necesarios para la comprensi´on del mismo. Los pasos a tener en cuenta son los siguientes: Paso 1. Poner el problema en forma estandar: La funci´on objetivo se minimiza y las restricciones son de igualdad. Paso 2. Encontrar una soluci´on b´asica factible. Paso 3. Testar la optimalidad. Paso 4. Elegir una variable de entrada. Paso 5. Elegir una variable de salida. Paso 6.Actualizar la base y la soluci´on b´asica factible. Paso 7. Ahora tenemos una soluci´on b´asica factible mejor que la inicial. Necesitamos saber si ´esta es la ´optima. Para ello necesitamos aplicar el test de optimalidad, el paso 3. Para los que quieran entrar en m´as detalle pueden hacer uso de Paul R. Thie y Gerard E. Keough [9]. Cap´ıtulo 2 Juegos no cooperativos 2.1. Introducci´on a los Juegos en Forma Estrat´egica Un juego en forma estrat´egica es un modelo est´atico que describe problemas de decisi´on en los que interaccionan varios jugadores. De acuerdo a este modelo, los jugadores toman sus decisiones simult´anea e independientemente y, aunque los jugadores podr´ıan comunicarse y tomar acuerdos informales antes de que el juego comience, se supone que no disponen de mecanisms que les permitan tomar acuerdos vinculantes. De ahora en adelante asumiremos que todos los jugadores son racionales en el sentido de que intentan maximizar su propia utilidad. Daremos ahora la definici´on formal de juego en forma estrat´egica. Definici´on 2.1.1. Un juego en forma estrat´egica G con conjunto de jugadores N= 1, ..., n es una 2n-tupla G= (X1, ..., Xn,H1, ..., Hn) donde, para todo i∈N,Xies el conjunto de estrategias del jugador iyHi:X= Qn i=1 Xi→Res su funci´on de pago, que asigna a cada perfil de estrategias x∈Xel pago que iobtiene si se juega de acuerdo a tal perfil. 15 16 Optimizaci´on Lineal aplicada a Teor´ıa de Juego En realidad, en un problema de decisi´on en el que interaccionan los jugadores de N est´an involucrados los siguientes elementos: • {Xi}i∈N, los conjuntos de estrategias de los jugadores. •R, el conjunto de posibles resultados. •Una aplicaci´on f:X=Qn i=nXi−→ Rque asigna a cada perfil de estrategias xsu correspondiente resultado f(x). • {i}i∈N, las preferencias de los jugadores sobre R (relaciones binarias completas y transitivas). La definici´on de juego en forma estrat´egica asume que las preferencias de los jugadores pueden representarse a trav´es de funciones de utilidad. Si para cada i∈Ndenotamos por hisu funci´on de utilidad, la correspondiente funci´on de pago Hiviene dada, para todo perfil de estrategias x∈X, por Hi(x) = hi(f(x)). Veamos ahora un ejemplo muy conocido en la Teor´ıa de Juegos. Ejemplo 2.1.2. Dilema del prisionero. Dos sospechosos de un delito grave y de un peque˜no hurto son ubicados en celdas diferentes. Se sabe que son culpables de ambos hechos, pero no hay pruebas de que hayan cometido el delito. A ambos se les da la oportunidad de confesar. Si ambos confiesan el delito, cada uno de ellos pasar´a 10 a˜nos en la c´arcel. Si s´olo uno confiesa, actuar´a como testigo contra el otro (que pasar´a 15 a˜nos en la c´arcel) y no recibir´a ning´un castigo. Finalmente, si ninguno confiesa, ser´an juzgados por el hur- to y cada uno de ellos pasar´a en la c´arcel 1 a˜no. Siguiendo la terminolog´ıa com´un para este juego, nos vamos a referir a la confesi´on como “delatar” (D) y a la no confesi´on como “no delatar” (ND). En tal caso, el juego del dilema del prisionero se puede representar como el juego en forma estrat´egica (X1, X2, H1, H2)dado por: JUEGOS NO COOPERATIVOS 17 •X1=X2={ND, D}; •H1(ND, ND) = -1, H1(ND, D) = -15, H1(D, ND) = 0, H1(D, D) = -10; •H2(ND, ND) = -1, H2(ND, D) = 0, H2(D, ND) = -15, H2(D, D) = -10. La siguiente tabla muestra una representaci´on m´as conveniente de este juego, que es la forma habitual de representar juegos en forma estrat´egica bipersonales con conjuntos finitos de estrategias. ND D ND -1, -1 -15,0 D 0, -15 -10, -10 El dilema del prisionero es un cl´asico en Teor´ıa de Juegos. Ha sido ampliamente utilizado en ´ambitos te´oricos, aunque tambi´en para prop´ositos m´as aplicados en sociolog´ıa o econom´ıa. El resultado “cooperativo”, (-1,-1), es bastante bueno para ambos jugadores; es “casi” todo lo que pueden obtener en el juego. Ahora bien, para cada jugador, la estrategia D conduce a un pago estrictamente m´as alto que ND, independientemente de la estrategia elegida por el otro jugador. De esta forma, un decisor racional deber´ıa jugar siempre D. As´ı, si ambos jugadores se comportan racionalmente, obtienen pagos (-10,-10), que son muchos peores que los pagos en el resultado “cooperativo”. Muchas situaciones de la vida real pueden ser vistas como un juego del dilema del prisionero. Por ejemplo, en la carrera nuclear entre los EEUU y la URSS durante la denominada Guerra Fr´ıa, ambos pa´ıses deb´ıan decidir si producir o no armas nucleares; en esta situaci´on, los pagos tendr´ıan una estructura similar a la tabla vista antes.  18 Optimizaci´on Lineal aplicada a Teor´ıa de Juego 2.2. El Equilibrio de Nash en Juegos en Forma Estrat´egica El concepto de soluci´on m´as importante para juegos en forma estrat´egica es el equilibrio de Nash. Por su impacto en la teor´ıa econ´omica, John Nash recibi´o el Premio Nobel de Econom´ıa en 1994. En Kohlberg [16] se dice que la idea principal del equilibrio de Nash es hacer una importante simplificaci´on y, en vez de preocuparse de c´omo se desarrollar´a la interacci´on entre los jugadores, preguntarse cu´ales ser´an los resultados estables de tal interacci´on. De hecho, un equilibrio de Nash de un juego en forma estrat´egica no es m´as que un perfil de estrategias tal que ning´un jugador gana desvi´andose unilateralmente de ´el; en este sentido puede decirse que el concepto de equilibrio de Nash busca resultados estables de la situaci´on interactiva descrita por el juego en forma estrat´egica. Definici´on 2.2.1. Sea G = (X1, ..., Xn, H1, ..., Hn)un juego en forma estrat´egica. Un equilibrio de Nash de G es un perfil de estrategias x∈X que cumple que Hi(x)≥Hi(x−i, x0 i), para todo x0 i∈Xi, y todo i∈N, donde el perfil (x−i, x0 i)es: (x1, ..., xi−1, x0 i, xi+1, ..., xn). Vemos ahora un par de ejemplos. Ejemplo 2.2.2. El ´unico equilibrio de Nash del dilema del prisionero es (D, D). De hecho, como ya hemos argumentado, (D, D) es el ´unico comportamiento racional en un contexto no cooperativo. Ejemplo 2.2.3. Pares o nones. Los jugadores 1 y 2 tienen que escoger simult´anea e independientemente un n´umero natural. Si la suma de los n´umeros escogidos es par, entonces gana el jugador 1 y si la suma es impar entonces JUEGOS NO COOPERATIVOS 19 gana el jugador 2. Esencialmente, todo lo que importa para este juego es si el n´umero escogido es par (P) o impar (I) y, por tanto, el juego en forma estrat´egica que describe esta situaci´on es el que se recoge en la siguiente tabla; claramente, este juego no tiene equilibrios de Nash. P I P 1,-1 -1,1 I -1,1 1,-1 A continuaci´on vamos a presentar el teorema de Nash, que da una condici´on suficiente para la existencia de equilibrios de Nash en un juego en forma estrat´egica. Para enunciar y demostrar el teorema de Nash debemos introducir algunos conceptos y resultados de an´alisis de correspondencias. Definici´on 2.2.4. Sea X ⊂Rne Y ⊂Rm. 1) Una correspondencia F de X en Y es una aplicaci´on de X en 2Y(la clase de todos los subconjuntos de Y). 2) Se dice que una correspondencia F es semicontinua superiormente si para toda sucesi´on {xk} ⊂ Xque converge a x ∈Xy todo abierto G de Y que contiene a F(x), existe k0∈Ntal que F(xk)⊂Gpara todo k≥k0. 3) Se dice que una correspondencia F es no vac´ıa, cerrada o convexa si, para todo x∈X, F(x) es un subconjunto de Y no vac´ıo, cerrado o convexo, respectivamente. 4) Una aplicaci´on f →Res cuasi-c´oncava si para todo r∈R, el conjunto {x∈X:f(x)≥r}es convexo o, equivalentemente si para cualesquiera x, ˆx∈Xy para todo α∈[0,1], f(αx + (1−α) ˆx)≥m´ın{f(x), f(ˆx)}. Claramente la concavidad implica cuasi-concavidad ya que la concavidad requiere que f(αx + (1 −α)ˆx)≥αf(x) + (1 −α)f(ˆx) y αf(x) + (1 −α)f(ˆx)≥min{f(x), f(ˆx)}. 26 Optimizaci´on Lineal aplicada a Teor´ıa de Juego Nota 2.3.8. Por las proposiciones anteriores, si (x, y)y(x0, y0)son equilibrios de Nash del juego bipersonal de suma nula G, entonces (x, y0)y(x0, y) son tambi´en equilibrios de Nash de G, y adem´as, H(x, y) = H(x0, y0) = H(x, y0) = H(x0, y). Sin embargo, esto no es cierto para cualquier juego bipersonal como veremos, por ejemplo, al estudiar los juegos bimatriciales. Nota 2.3.9. Un juego bipersonal de suma constante es un juego en forma estrat´egica G= (X, Y, H1, H2)tal que, para todo perfil de estrategias (x, y)∈X×Y, H1(x, y) + H2(x, y) = k, siendo k una constante real. Obviamente, un juego de suma nula es un juego de suma constante con k = 0. Sin embargo, desde el punto de vista estrat´egico, analizar el juego G es lo mismo que analizar el juego de suma nula G1= (X, Y, H1)ya que (x, y)∈X×Y es un equilibrio de Nash de G si y s´olo si es un equilibrio de Nash de G1. 2.4. Estrategias Mixtas en Juegos Finitos A partir de ahora nos centraremos en la clase de los juegos finitos, que definimos a continuaci´on. Definici´on 2.4.1. Un juego finito es un juego en forma estrat´egica G= (X1, ..., Xn, H1, ..., Hn) cuyos jugadores tienen conjuntos de estrategias finitos, es decir, tal que |Xi|= mipara todo i∈N(siendo cada miun n´umero natural). El teorema de Nash visto anteriormente no se puede aplicar a los juegos finitos, ya que los conjuntos de estrategias no son convexos. Por otro lado, ya hemos visto un juego finito sin equilibrios de Nash: el juego de pares o nones. JUEGOS NO COOPERATIVOS 27 Sin embargo, hay un “ingenio te´orico” que nos permite extender el juego y garantizar la existencia de equilibrios de Nash en la revisi´on extendida de todo juego finito: tal ingenio consiste en aumentar las posibilidades estrat´egicas de los jugadores y considerar que no s´olo tienen sus estrategias iniciales (que pasaremos a denominar estrategias puras), sino que tambi´en pueden escoger loter´ıas sobre sus conjuntos finitos de estrategias puras. Esta extensi´on del juego original se llama extensi´on mixta y las estrategias de los jugadores en la extensi´on mixta se llaman estrategias mixtas. Aunque nos hemos referido a la extensi´on mixta de un juego como un “ingenio te´orico”, las estrategias mixtas surgen de modo natural en muchas situaciones en la pr´actica. Vamos a discutir brevemente esta cuesti´on en el ejemplo siguiente, en el que introducimos informalmente la extensi´on mixta de un juego en forma estrat´egica. Despu´es del ejemplo daremos una definici´on formal. Ejemplo 2.4.2. Consideremos de nuevo el juego de pares y nones y supongamos ahora que los jugadores, adem´as de escoger P o I, pueden escoger tambi´en una loteria L que selecciona P con probabilidad 1/2 e I con probabilidad 1/2. Supongamos tambi´en que los jugadores tienen funciones de utilidad de von Neumann y Morgenstern y, por tanto, sus funciones de pago se pueden extender al conjunto de perfiles de estrategias mixtas calculando sus correspondientes esperanzas matem´aticas. El juego resultante viene dado por la tabla siguiente: P I L P 1,-1 -1,1 0,0 I -1,1 1,-1 0,0 L 0,0 0,0 0,0 Para calcular las funciones de pago del juego extendido hemos tenido en cuenta que, dado que estamos en un juego en forma estrat´egica, los jugadores 28 Optimizaci´on Lineal aplicada a Teor´ıa de Juego eligen sus loter´ıas independientemente. As´ı, por ejemplo: H1(L, L) = 1 4H1(P, P) + 1 4H1(P, I) + 1 4H1(I, P) + 1 4H1(I, I) = 0 Observamos que este juego tiene un equilibrio de Nash: (L, L). La exten- si´on mixta del juego de partida es un nuevo juego en forma estrat´egica en el que los jugadores pueden escoger cualquier loter´ıa sobre {P, I}. Es f´acil comprobrar que el ´unico equilibrio de Nash de este juego es (L, L). Una posible interpretaci´on de esto es la siguiente. En el juego de pares o nones es muy importante para cada uno de los jugadores que el otro no tenga ninguna informaci´on sobre si elegir´a finalmente P o I. Para ello, lo mejor es que ni ´el mismo lo sepa, lo cual puede llevarse a efecto seleccionando la estrategia de L.  Definici´on 2.4.3. Sea G= (X1, ..., Xn, H1, ..., Hn)un juego finito. La extensi´on mixta de G es el juego en forma estrat´egica E(G) = (S1, ...Sn, H1, ..., Hn) donde, para cada jugador i∈N, 1. Si={si∈RXi:si(xi)≥0∀xi∈Xi,Pxi∈Xisi(xi)=1} 2. Hi(s) = Px∈XHi(x)s(x),para todo s∈S, donde S=Qi∈NSiy s(x) denota el producto s1(x1)×... ×sn(xn). Nota 2.4.4. La extensi´on mixta de un juego finito s´olo tiene sentido cuando los jugadores tienen preferencias sobre el conjunto de loter´ıas definidas sobre el conjunto de posibles resultados y sus funciones de utilidad son funciones de utilidad de von Neumann y Morgenstern. Nota 2.4.5. E(G) es una extensi´on de G en el sentido de que, para todo jugador i, cada elemento de Xi, o estrategia pura, puede ser identificado con JUEGOS NO COOPERATIVOS 29 un elemento de Si, o estrategia mixta, por lo que podemos escribir Xi⊂Si. Por otro lado, las funciones de pago de los jugadores en E(G) son extensiones de las funciones de pago de los jugadores en G. Nota 2.4.6. El conjunto de estrategias del jugador ilo vamos a identificar en ocasiones con el s´ımplex de Rmidado por: {si∈Rmi:sk i≥0∀k∈ {1, ..., mi}, mi X k=1 sk i= 1}. Nota 2.4.7. La extensi´on mixta de un juego finito cumple las hip´otesis del teorema de Nash y, por lo tanto, un corolario de tal teorema es que la exten- si´on mixta de un juego finito tiene siempre, al menos, un equilibrio de Nash. De hecho, ´este fue el resultado probado por John Nash en su art´ıculo original. Para terminar con esta secci´on daremos algunas definiciones y resultados b´asicos en relaci´on con los juegos finitos. Definici´on 2.4.8. Sea E(G) la extensi´on mixta de un juego finito y sean si∈Si, una estrategia del jugador i, y s∈Sun perfil de estrategias. 1. El soporte de sies el conjunto C(si)dado por: {xi∈Xi:si(xi)>0}, 2. El soporte de ses el conjunto C(s)dado por: Y i∈N C(si) = {x∈X:s(x)>0}. 3. Se dice que sies completamente mixta si C(si) = Xi. Se dice que s es completamente mixta si C(s) = Xo, equivalentemente, si sies completamente mixta para todo i∈N. 30 Optimizaci´on Lineal aplicada a Teor´ıa de Juego 4. El conjunto de mejores respuestas puras del jugador ias−ies el conjunto PBi(s−i) = {xi∈Xi:Hi(s−i, xi)≥Hi(s−i, x0 i)∀x0 i∈Xi}. Usaremos la notaci´on PB(s) = Qi∈NPBi(s−i). Proposici´on 2.4.9. En la extensi´on mixta de un juego finito, para todo i∈N, si∈Siys∈S, se cumple: 1. si∈Bi(s−i)si y s´olo si C(si)⊂PBi(s−i). 2. s es un equilibrio de Nash de E(G) si y solo si C(s)⊂PB(s). 3. s es un equilibrio de Nash de E(G) si y solo si Hi(s)≥Hi(s−i, xi)para todo xi∈Xiy todo i∈N. Demostraci´on. Es f´acil ver que Hi(s) = Pxi∈XiHi(s−i, xi)si(xi), con lo que la proposici´on se sigue inmediatamente. Obs´ervese que el apartado 3) de la proposici´on anterior implica que si un perfil de estrategias es un equilibrio de Nash de un juego finito Gtambi´en lo es de E(G). 2.5. Juegos Matriciales y Algoritmos En esta secci´on comprobaremos que resolver un juego matricial es, en cierto modo, equivalente a resolver un par de problemas de programaci´on lineal duales y obtendremos un algoritmo para resolver juegos matriciales. Definici´on 2.5.1. Un juego bimatricial es la extensi´on mixta de un juego bipersonal finito (M, N, H1, H2), donde M={1, .., m}yN={1, .., n}. Por tanto, un juego bimatricial es una 4-tupla (Sm, Sn, H1, H2)tal que: JUEGOS NO COOPERATIVOS 31 1. Sm={x∈Rm:xi≥0∀i∈M, Pi∈Mxi= 1}. 2. Sn={y∈Rn:yj≥0∀j∈N, Pj∈Nyj= 1}. 3. Para todo (x, y)∈Sm×Sn, H1(x, y) = X i∈MX j∈N H1(i, j)xiyj=xAyt, donde A= (H1(i, j))i∈M,j∈Nes una matriz m×n. 4. Para todo (x, y)∈Sm×Sn, H2(x, y) = X i∈MX j∈N H2(i, j)xiyj=xByt, donde B= (H2(i, j))i∈M,j∈Nes una matriz m×n. N´otese que para caracterizar un juego bimatricial es suficiente conocer el par de matrices (A, B). Definici´on 2.5.2. Un juego matricial es la extensi´on mixta de un juego bipersonal de suma nula finito (M, N, H), donde M={1, ..., m}yN= {1, ..., n}. Por tanto, un juego matricial es una terna (Sm, Sn, H)tal que: 1. Sm={x∈Rm:xi≥0∀i∈M, Pi∈Mxi= 1}. 2. Sn={y∈Rn:yi≥0∀j∈N, Pj∈Nyj= 1}. 3. Para todo (x, y)∈Sm×Sn, H(x, y) = X i∈MX j∈N H(i, j)xiyj=xAyt, donde A= (H(i, j))i∈M,j∈Nes la matriz m×nque contiene los pagos del jugador 1. 32 Optimizaci´on Lineal aplicada a Teor´ıa de Juego V´ease que para caracterizar un juego matricial es suficiente dar la matriz A. Obviamente todo juego matricial puede verse como un juego bimatricial, aunque el rec´ıproco no es cierto. Por tanto, el teorema de Nash implica que todo juego matricial tiene un equilibrio de Nash. Por la Proposici´on 2.3.7, se tiene entonces que todo juego matricial est´a estrictamente determinado. ´ Este es el resultado conocido como teorema minimax, probado por John von Neumann en 1928. Teorema 2.5.3. [Teorema minimax de von Neumann ]. Todo juego matricial tiene un valor (en estrategias mixtas), es decir, m´ax x∈Xm´ın y∈YxtAy = m´ın y∈Ym´ax x∈XxtAy. El lector interesado en la demostraci´on del Teorema 2.5.3 puede encontrarla en Isabel Fern´andez [6]. Existen diferentes pruebas directas del teorema minimax, algunas de ellas muy elegantes: una basada en un lema de alternativas para matrices, una basada en un teorema de punto fijo de Brower; incluso hay una que utiliza ´unicamente el principio de inducci´on. El lector interesado puede encontrar algunas de estas demostraciones en Owen [8] y Gonz´alez-D´ıaz y otros [11]. Vamos a ver a continuaci´on dos m´etodos para resolver juegos matriciales (por “resolver un juego matricial” entendemos encontrar su valor y los conjuntos de estrategias ´optimas de los jugadores). Comenzamos por un m´etodo geom´etrico para juegos matriciales 2 ×n. Para describirlo necesitamos el siguiente resultado. Proposici´on 2.5.4. Consideremos un juego matricial m×ndado por la matriz A. Entonces, para todo x∈Smy todo y∈Sn, Λ(x) = m´ın j∈NxPj, Γ(y) = m´ax i∈MQiyt, JUEGOS NO COOPERATIVOS 33 donde PjyQidenotan la columna j-´esima y la fila i-´esima de A, respectivamente. Demostraci´on. S´olo vamos a probar la primera de las igualdades (la segunda se probar´ıa analogamente). Sea x∈Sm, Claramente, Λ(x) = ´ınf y∈Sn xAyt≤m´ın j∈NxPj. Por otro lado, dado y∈Sn. xAyt=X k∈N (xPk)yk≥X k∈N (m´ın j∈NxPj)yk= m´ın j∈NxPj. Por tanto, Λ(x) = ´ınfy∈SnxAyt≥m´ınj∈NxPj,con lo que se tiene el resultado. Consideramos ahora un juego matricial 2×ndado por la siguiente matriz:   a11 ... a1j... a1n a21 ... a2j... a2n  Podemos identificar una estrategia del jugagador 1, x∈S2, con su primera componente, y utilizando la proposici´on anterior se tiene que: V= m´ax x∈[0,1] Λ(x) = m´ax x∈[0,1] m´ın j∈N[(x, 1−x)a1j a2j] = m´ax x∈[0,1] m´ın j∈N[a2j+ (a1j−a2j)x]. Por lo tanto, para calcular el valor del juego y el conjunto de estrategias ´optimas del jugador 1, ser´a suficiente representar, para cada j∈N, los segmentos {(x, a2j+ (aij −a2j)x) : x∈[0,1]}, obtener su envoltura inferior y buscar el conjunto de puntos ¯x∈Smque maximiza esa envoltura. Ahora, para calcular el conjunto de estrategias ´optimas del jugador 2, debemos tener en cuenta que y∈Snes una de tales estrategias si y s´olo si: 34 Optimizaci´on Lineal aplicada a Teor´ıa de Juego V= Γ(y) = m´ax x∈[0,1] H(x, y) = m´ax x∈[0,1] xAyt= m´ax x∈[0,1][X j∈N [a2j+ (a1j−a2j)x]yj]. En consecuencia, una estrategia ´optima del jugador 2 vendr´a dada por un elemento de Snque proporciona una combinaci´on convexa de los segmentos {(x, a2j+(aij −a2j)x) : x∈[0,1]}que se encuentra bajo el segmento {(x, V ) : x∈[0,1]}. A continuaci´on lo vemos con un ejemplo. Ejemplo 2.5.5. Resolvamos el juego matricial dado por la matriz A=  2 2 3 1 4 3   Los segmentos correspondientes a las columnas de A son, {(x, 1 + x) : x∈[0,1]},{(x, 4−2x) : x∈[0,1]},{(x, 3) : x∈[0,1]}. Claramente, el valor de este juego es V= 2, el conjunto de estrategias del jugador 1 es O1(A) = {(1,0)}y el conjunto de estrategias ´optimas del jugador 2 es la envoltura convexa de (1,0,0) y(2/3,1/3,0), esto es O2(A) = conv({(1,0,0),(2/3,1/3,0)}). Para obtener O2(A), la forma m´as sencilla ser´a combinar una recta creciente y otra decreciente de entre las que cortan a la recta y=V(y= 2) y conseguir que la pendiente de esa combinaci´on sea nula. La recta ser´a paralela al eje de abcisas y pasa por los puntos (0, V ) y(1, V ). Si ahora tomamos una combinaci´on convexa de las expresiones 1+x y4−2xde la forma α(1 + x) + (1 −α)(4 −2x) = (3α−2)x+ 4 −3α, con α∈[0,1], entonces por la condici´on de pendiente nula, α= 2/3. A continuaci´on vamos a describir el denominado m´etodo de las submatrices, que es un algoritmo para resolver cualquier juego matricial m×n. Se basa en la caracterizaci´on de los puntos extremos de los conjuntos de estrategias ´optimas de los jugadores. JUEGOS NO COOPERATIVOS 35 Proposici´on 2.5.6. Sea A un juego matricial m×ny tomemos x∈Sme y∈Sn. Entonces: 1. x∈O1(A)si y s´olo si xPj≥V, para todo j∈N. 2. y∈O2(A)si y s´olo si Qiyt≤V, para todo i∈M. Demostraci´on. Probamos s´olo la primera equivalencia (la segunda se probar´ıa an´alogamente). “⇒” Supongamos que x∈O1(A). Entonces, por la Proposici´on 2.5.4, V= Λ(x) = m´ınj∈NxPj. Consecuentemente, V≤xPjpara todo j∈N. “⇐” Supongamos que xPj≥Vpara todo j∈N. Aplicamos nuevamente la Proposici´on 2.5.4: V= m´ax x0∈Sm Λ(x0)≥Λ(x) = m´ın j∈NxPj≥V con lo que concluye la demostraci´on. Proposici´on 2.5.7. Sea A un juego matricial m×n. Entonces, los conjuntos de estrategias ´optimas de los jugadores, O1(A)yO2(A), son conjuntos convexos y compactos. Demostraci´on. En virtud de la Proposici´on 2.5.6, los conjuntos son claramente convexos. Tambi´en est´a claro que son acotados. Son cerrados ya que las funciones Λ y Γ son continuas y O1(A) = Λ−1({V}) y O2(A)=Λ−1({V}). Proposici´on 2.5.8. Sea A un juego matricial m×n, y tomemos x∈Sm, y∈Sn. Entonces, x∈O1(A)ey∈O2(A)si y s´olo si xPj≥Qiytpara todo i∈My todo j∈N. Demostraci´on. “⇒” Esta implicaci´on es una consecuencia de la Proposici´on 2.5.6. “⇐” Si xPj≥Qiytpara todo i∈My todo j∈N, entonces V=γ≤Γ(y) = m´ax i∈MQiyt≤m´ın j∈NxPj= Λ(x)≤λ=V. 42 Optimizaci´on Lineal aplicada a Teor´ıa de Juego b) Si u es una soluci´on ´optima del problema (2.2), entonces (x, Λ) es una soluci´on ´optima del problema (2.1) donde, para todo i∈M, xi=1 uJt m ui,yΛ = 1 uJt m . Ahora podemos proceder de modo an´alogo desde el punto de vista del jugador 2. Para encontrar el valor del juego y el conjunto de estrategias ´optimas del jugador 2 basta resolver el siguiente problema de programaci´on lineal: minimizar Γ sujeto a Qiyt≤Γ,∀i∈M, yJt n= 1, y≥0. Claramente este problema es equivalente al siguiente: maximizar 1 Γ sujeto a Ayt≤ΓJt m,(2.3) yJt n= 1, y≥0. Consideremos ahora el problema que describimos a continuaci´on (que es el dual del problema (2.2): maximizar wJt n sujeto a Awt≤Jt m,(2.4) w≥0. JUEGOS NO COOPERATIVOS 43 De nuevo, es un ejercicio sencillo probar el siguiente resultado. Proposici´on 2.6.2. a) Si el par (y, Γ) es una soluci´on ´optima del problema (2.3), entonces wes una soluci´on ´optima del problema (2.4) donde, para todo j∈N, wj=1 Γyj. b) Si wes una soluci´on ´optima del problema (2.4), entonces (y, Γ) es una soluci´on ´optima del problema 2.3 donde, para todo j∈N, yj=1 wJt n wj,yΓ = 1 wJt n . Como conclusi´on podemos decir que, para resolver un juego matricial, es suficiente resolver los problemas (2.2) y (2.4) que son un par de problemas de programaci´on lineal duales. N´otese que este resultado implica que el algoritmo del s´ımplex puede ser usado para resolver un juego matricial. Vamos a ver ahora que, para resolver un par de problemas de programaci´on lineal, es suficiente resolver un cierto juego matricial. Para ello precisamos de unas definiciones y resultados b´asicos. Definici´on 2.6.3. Un juego matricial n×ncaracterizado por la matriz A se dice sim´etrico si los jugadores son intercambiables, esto es, si A=−At. Proposici´on 2.6.4. Sea A un juego matricial n×nsim´etrico. Entonces, su valor V es cero y, adem´as, O1(A) = O2(A). Definici´on 2.6.5. Sea A un juego matricial m×n. Una fila Qise denomina relevante si existe x∈O1(A)tal que xi>0. Una columna Pjse denomina relevante si existe y∈O2(A)tal que yj>0. Proposici´on 2.6.6. Sea A un juego matricial m×n. 1. Si Pjes una columna relevante, entonces se tiene que xPj=Vpara todo x∈O1(A). 44 Optimizaci´on Lineal aplicada a Teor´ıa de Juego 2. Si Qies una fila relevante, entonces se tiene que Qiyt=Vpara todo y∈O2(A). Consideremos ahora un par de problemas de programaci´on lineal duales (P)y(D) seg´un las definiciones . Consideremos el siguiente juego matricial B: B=    0A−ct −At0bt c−b0     Obs´ervese que se trata de un juego matricial sim´etrico, por lo que su valor es cero y adem´as O1(B) = O2(B).A partir de ahora en juegos matriciales sim´etricos, al referirnos a una estrategia ´optima de los jugadores diremos sencillamente una estrategia ´optima del juego. Teorema 2.6.7. Los problemas (P) y (D) tienen soluciones ´optimas si y s´olo si el juego matricial B tiene una estrategia ´optima cuya ´ultima componente es positiva. Ejemplo 2.6.8. La matriz de pagos del jugador 1 es   2 4 3 7 2 5   Es claro que no hay estrategias puras en equilibrio. Formulamos uno de los problemas de programaci´on lineal, o el del jugador 1 m´ax v sujeto a 2p1+ 7p2≥v 4p1+ 2p2≥v 3p1+ 5p2≥v p1 + p2= 1 p1, p2≥0 JUEGOS NO COOPERATIVOS 45 o bien, el del jugador 2 m´ın w sujeto a 2q1+ 4q2+ 3q3≤w 7q1+ 2q2+ 5q3≤w q1+q2+q3= 1 q1, q2, q3≥0 Si por ejemplo resolvemos este ´ultimo problema, la soluci´on ´optima es q1= 2/7, q2= 5/7, q3= 0, siendo w=v= 24/7, y las variables duales son (−5/7,−2/7), de donde se deduce que la estrategia ´optima del jugador 1 es p1= 5/7, p2= 2/7. 46 Optimizaci´on Lineal aplicada a Teor´ıa de Juego Cap´ıtulo 3 Juegos Cooperativos En este cap´ıtulo tratamos de estudiar c´omo pueden actuar grupos de jugadores, sin detenernos en las acciones individuales de los mismos. El problema fundamental que vamos a estudiar es el de c´omo puede hacerse una distribuci´on de pagos entre los jugadores que forman una coalici´on y han obtenido una ganancia actuando coordinalmente, de manera cooperativa y c´omo la programaci´on lineal facilita el c´alculo. Para resolver dicho problema, y al igual que en el caso de los juegos no cooperativos, se han propuesto diversos conceptos de soluci´on. En este cap´ıtulo se estudian dos de ellos: el core y el nucleolus. 3.1. Introducci´on En los juegos cooperativos se parte de que es posible que algunos jugadores puedan llegar a acuerdos vinculantes (a los que quedar´ıan obligados de manera ineludible), por lo que se trata es de estudiar los resultados que puede obtener cada una de las coaliciones de jugadores que se pueden formar. Se trata, por tanto de estudiar c´omo pueden actuar grupos de jugadores, interes´andonos los comportamientos colectivos y sin que haga falta detenerse 47 48 Optimizaci´on Lineal aplicada a Teor´ıa de Juego en las acciones individuales de cada uno de los miembros de una coalici´on. A continuaci´on, tras recordar la definici´on de juego en forma coalicional (o juego en forma de funci´on caracter´ıstica), se introducen otras definiciones que se van a utilizar a lo largo del cap´ıtulo. Definici´on 3.1.1. Un juego en forma coalicional o en forma funci´on caracter´ıstica con utilidades transferibles consiste en: 1. Un conjunto finito de jugadores N={1,2, ..., n}. 2. Una funci´on caracter´ıstica, que asocia a cada subconjunto S de N un n´umero real v(S)(valor de coalici´on), siendo v(∅)=0. Por tanto, G= (N, v)es un juego en forma coalicional con utilidades transferibles si Nyvest´an especificados. Si al crecer el n´umero de jugadores que forman una coalici´on se cumple que el beneficio o ganancia que obtiene la coalici´on no disminuye, estamos ante un juego cooperativo mon´otono, tal como se define formalmente a continuaci´on. Definici´on 3.1.2. Se dice que un juego G= (N, v)es mon´otono si ∀S, T ⊂ N, con S⊂T, se verifica que v(S)≤v(T). A continuaci´on se define el concepto de juego superaditivo, en el cual cuando dos coaliciones con intersecci´on vac´ıa se unen el beneficio o ganancia de la nueva coalici´on es al menos igual a la suma de los beneficios de las coaliciones que se unen. Definici´on 3.1.3. Se dice que un juego G= (N, v)es superaditivo si ∀S, T ⊂N, con S∩T=∅, se verifica que v(S) + v(T)≤v(S∪T) JUEGOS COOPERATIVOS 49 Si la desigualdad de la definici´on anterior se da en sentido opuesto se dice que el juego es subaditivo. Ahora se introduce una propiedad m´as fuerte que la anterior. Si dos coaliciones (con intersecci´on no necesariamente vac´ıa) se unen, entonces la suma de los beneficios de la uni´on e intersecci´on es al menos igual a la suma de beneficios de las coaliciones que se unen. Definici´on 3.1.4. Se dice que un juego G= (N, v)es convexo si ∀S, T ⊂ N, se verifica que v(S) + v(T)≤v(S∪T) + v(S∩T) Si la desigualdad anterior se da en sentido opuesto se dice que el juego es c´oncavo. Definici´on 3.1.5. Sean (N, v)y(N, w)dos juegos cooperativos, con N= {1,2, ..., N}. Sea λ∈R. Se define: (v+w)(S) = v(S) + w(S),∀S⊂N; (λv)(S) = λ[v(S)],∀S⊂N; (vw)(S) = v(s)w(S),∀S⊂N. Se comprueba facilmente que el conjunto de juegos cooperativos con n jugadores, sobre el cuerpo de los n´umeros reales, con las operaciones definidas de suma y de producto por un escalar, tiene estructura de espacio vectorial de dimensi´on 2n−1. 3.2. El Core y Conceptos Relacionados Sea G= (N, v) un juego en su forma coalicional, en donde N={1, ..., n} es el conjunto de jugadores y ves la funci´on caracter´ıstica. Si en un juego los 50 Optimizaci´on Lineal aplicada a Teor´ıa de Juego jugadores deciden trabajar conjuntamente, es decir, cooperan, el problema que se presenta consiste en c´omo repartir el valor v(N) entre los njugadores. Sea x= (x1, x2, ..., xn)∈Rnun vector de distribuci´on de pagos, en donde para cada i= 1,2, .., n,xirepresenta el pago que recibe el jugador i. Para cualquier coalici´on S⊂N, se utilizar´a la siguiente notaci´on: x(S) = X i∈S xi. Por tanto, x(N) = n X i=1 xi. Definici´on 3.2.1. El conjunto de preimputaciones de un juego G= (N, v) es el siguiente conjunto de vectores de distribuci´on de pagos: PI(N, v) = {x= (x1, x2, .., xn)∈Rn:x(J) = v(J)}. Cabe pensar que ning´un jugador aceptar´a un pago inferior al que obtendr´ıa por s´ı mismo sin participar en ninguna coalici´on. Surge entonces el concepto que se define a continuaci´on. Definici´on 3.2.2. El conjunto de imputaciones de un juego G= (N, v) es el siguiente conjunto de vectores de pagos: I(N, v) = {x= (x1, x2, ..., xn)∈Rn:x(N) = v(n), xi≥v({i}),para i= 1,2, .., n} La condici´on de que para cada jugador itiene que cumplirse que xi≥ v({i}) recibe el nombre de principio de racionalidad individual. La siguiente proposici´on nos da una condici´on necesaria y suficiente para que el conjunto de imputaciones de un juego sea no vac´ıo. Proposici´on 3.2.3. Sea G= (N, v)un juego en su forma funci´on caracter´ıstica. I(N, v)6=∅ ⇔ n X i=1 v({i})≤v(N) JUEGOS COOPERATIVOS 51 Definici´on 3.2.4. Se dice que el juego G= (N, v)es esencial si verifica que I(N, v)6=∅. El principio de racionalidad individual que se recoge en el conjunto de imputaciones puede extenderse a todas las coaliciones mediante el principio de racionalidad coalicional. Llegamos entonces al concepto de core de un juego cooperativo. Definici´on 3.2.5. El core de un juego G= (N, v)es el siguiente conjunto de vectores de pagos: C(N, v) = {x= (x1, x2, .., xn)∈Rn:x(N) = v(N), x(S)≥v(S),∀S∈P(N)} A partir de la definici´on se ve que el core es un subconjunto del conjunto de imputaciones. Se trata de las asignaciones que podr´ıan constituir acuerdos de distribuci´on estables, en el sentido de que ning´un grupo de jugadores podr´ıa impugnar unilateralmente ninguno de esos acuerdos. En efecto, ning´un grupo conseguir´ıa por s´ı mismo m´as de lo que cualquiera de esos acuerdos le permite obtener. Proposici´on 3.2.6. Sea G= (N, v)un juego cooperativo. El conjunto C(N, v) es cerrado, acotado y convexo. Ejemplo 3.2.7. Una finca est´a valorada por su actual propietario en 350.000 euros. Un empresario le ofrece acondicionarla para su utilizaci´on como pol´ıgono industrial, con lo que su valor de mercado alcanzar´ıa los 700.000 euros. Una empresa constructora le ofrece urbanizar la finca para su posible subdivisi´on en parcelas destinadas a viviendas unifamiliares. Con esta urbanizaci´on el valor de la finca ser´ıa de 775.000 euros. Representamos el juego en forma coalicional. Sea N={1,2,3} 58 Optimizaci´on Lineal aplicada a Teor´ıa de Juego sombra a los que se valoran los recursos, es decir a los agentes se les valoran sus recursos de acuerdo al vector de precios sombra, que produce un vector Owen, siendo dicho vector un reparto del n´ucleo del juego. La soluci´on que proporcionan los Conjuntos de Owen no tiene porque ser ´unica. Si (DN) tiene soluci´on m´ultiple, todas las valoraciones duales que dichas soluciones representan son v´alidas para obtener elementos del conjunto de Owen. A´un en el caso en que (DN) tenga soluci´on ´unica, si hay holgura positiva en alguno de los recursos, eliminando el recurso sobrante obtenemos una soluci´on m´ultiple dual y algunas de las valoraciones duales que dichas soluciones representan nos permiten obtener elementos en el conjunto de Owen del juego original. Ejemplo 3.3.4. Consideremos tres agentes o jugadores que aportan al proceso productivo tres recursos necesarios, seg´un se muestra a continuaci´on: B=    139 181 110 140 87 183 130 225 215     Se producen tres bienes que se venden en el mercado obteni´endose unos beneficios unitarios p= (2,5,5,4)t. La matriz tecnol´ogica del problema es: A=    2 9 3,5 6 4 9 8 9 7     Veamos el juego. Si se forma la gran coalici´on, el problema a resolver es: JUEGOS COOPERATIVOS 59 m´ax 2,5x1+ 5x2+ 4x3 sujeto a: 2x1+ 9x2+ 3,5x3≤430 6x1+ 4x2+ 9x3≤410 8x1+ 9x2+ 7x3≤570 x1, x2, x3≥0 Si resolvemos el problema, utilizando el software LINDO obtenemos que el esquema ´optimo de producci´on consiste en producir exclusivamente de los bienes segundo y tercero, es decir, x∗(N) = (0,36,343,29,403). La soluci´on ´optima del problema dual (DN), es: u∗(N) = (0,4328,0,2761,0). Resolviendo el problema (PN)hemos obtenido el valor de la funci´on caracter´ıstica para la gran coalici´on en el juego de la producci´on (N, v), siendo dicho valor de v(N) = 299,328. Resolviendo los problemas (PS)para cada coalici´on, S, obtenemos todos los valores de la funci´on caracter´ıstica del juego: S{1} {2} {3} {1,2} {1,3} {2,3}N v(S) 73,774 102,336 98,142 198,528 194,868 200,507 299,328 Obtengamos el reparto de Owen, valorando los recursos aportados por cada jugador a los precios duales, u∗(N). Se obtiene el siguiente reparto: Ow(N, v)=(u∗(N)bi) = = ((0,4328,0,2761,0)(139,140,130)t,(0,4328,0,2761,0)(181,87,225)t, (0,4328,0,2761,0)(110,183,215)t) = = (98,821,102,366,98,142). A continuaci´on se presenta una tabla que contiene los valores de la funci´on caracter´ıstica con las asignaciones del reparto de Owen, pudi´endose comprobar que dicho reparto es del n´ucleo del juego. Ow(S) = Pi∈SOw(i), represen- 60 Optimizaci´on Lineal aplicada a Teor´ıa de Juego ta la asignaci´on que conjuntamente obtiene la coalici´on Scon el reparto de Owen. S{1} {2} {3} {1,2} {1,3} {2,3}N v(S) 73,774 102,336 98,142 198,528 194,868 200,507 299,328 Ow(S)98,821 102,366 98,142 201,19 196,96 200,507 299,328 En ´este ejemplo la m´axima utilidad que se obtiene de la cooperaci´on de los tres agentes que participan en el proceso de producci´on es v(N) = 299,3283. Pero ahora en ´este caso sobran recursos. En concreto sobran 37,0895 unidades del tercer recurso. En este caso los agentes pueden considerar la posibilidad de aportar al proceso de producci´on los recursos justos, eliminando el recurso sobrante. 3.4. El Nucleolus Hemos visto en la secci´on anterior que el core es un concepto de soluci´on que tiene una dificultad importante: en algunas ocasiones es un conjunto muy grande y en otras es un conjunto vac´ıo. El concepto de nucleolus propone una soluci´on que, siempre que el conjunto de imputaciones sea no vac´ıo, supera la dificultad anterior, pues es no vac´ıo y ´unico. Adem´as, pertenece al core si ´este es no vac´ıo. Se considera un juego cooperativo (N, v). Sea una distribuci´on de pagos x= (x1, x2, .., xn)∈Rneficiente entre los jugadores, es decir, tal que n X i=1 xi=v(N) Definici´on 3.4.1. El exceso oqueja de una coalici´on Scon respecto a una distribuci´on de pagos xes la diferencia entre el valor de la coalici´on Sy lo JUEGOS COOPERATIVOS 61 que recibe dicha coalici´on por la distribuci´on x. Es decir, e(S, x) = v(S)−x(S) = v(S)−X i∈S xi Se trata de una medida del grado de insatisfacci´on de la coalici´on Scon la distribuci´on x. Cuanto mayor es e(S, x) mayor es la insatisfacci´on. Definici´on 3.4.2. Para cada x∈I(N, v), se define el vector de excesos como el siguiente vector θ(x), con 2ncomponentes: θ(x) = (e(S, x))S∈P(N)= (θ1(x), θ2(x), .., θ2n(x)) en donde θk(x)≥θk+1(x),∀k= 1,2, .., 2n−1. Se considera el orden lexicogr´afico que definimos formalmente a continuaci´on. Definici´on 3.4.3. Sean x, x0∈I(N, x). a) θ(x)≤Lθ(x0)⇔θ1(x)< θ1(x0), o bien, para j > 1, θj(x)< θj(x0)yθi(x) = θi(x0), i = 1, ..., j −1. b) θ(x) =Lθ(x0)⇔θj(x) = θj(x0),∀j. c) θ(x)≤Lθ(x)<Lθ(x0)o bien θ(x) =Lθ(x0). Por tanto, dados dos vectores de excesos, para compararlos seg´un el orden lexicogr´afico, se observan s´olo las primeras componentes; si la primera componente de un vector es menor que la primera componente del otro vector, el 62 Optimizaci´on Lineal aplicada a Teor´ıa de Juego primer vector es menor que el segundo seg´un el orden lexicogr´afico definido. Si los dos vectores tienen iguales sus primeras componentes se comparan sus segundas componentes, siendo menor seg´un el orden lexicogr´afico aquel vector cuya segunda componente sea menor. Si sus segundas componentes son iguales, se comparan con sus terceras componentes y as´ı sucesivamente. Definici´on 3.4.4. El nucleolus de un juego (N, v) es el conjunto N(N, v) definido de la siguiente forma: N(N, v) = {x∈I(N, v) : θ(x)≥Lθ(y),∀y∈I(N, v)} Por tanto, se puede decir que el nucleolus contiene aquellas distribuciones de pagos que son imputaciones, y para las cuales se minimiza el mayor de los grados de insatisfacci´on. El siguiente teorema, del que vamos a dar el enunciado sin la demostraci´on, se debe a Schemeidler [15]. Teorema 3.4.1. Sea (N, v)un juego esencial (lo cual quiere decir que su conjunto de imputaciones es no vac´ıo). Entonces se verifica que el nucleolus existe y es ´unico. Proposici´on 3.4.5. Una condici´on suficiente para que el nucleolus exista y sea ´unico es que n X i=1 v({i})≤v(N). Demostraci´on. Supongamos que Pn i=1 v({i})≤v(N). Entonces por la Proposici´on 3.2.3 se tiene que I(N, v)6=∅de donde se deduce la existencia y unicidad del nucleolus por el Teorema 3.4.1 A continuaci´on, se dan dos definiciones que se utilizar´an posteriormente en una proposici´on en que se presentar´an algunas propiedades importantes del nucleolus, que nos permitir´an calcularlo en algunos casos. JUEGOS COOPERATIVOS 63 Definici´on 3.4.6. Se dice que dos jugadores i,json sim´etricos en un juego (N, v)si realizan aportaciones equivalentes para cada coalici´on. Es decir, si se cumple que v(S∪ {i}) = v(S∪ {j}),∀S∈P(N), i, j /∈S Definici´on 3.4.7. Se dice que el jugador ies un jugador pasivo en el juego (N, v) si no aporta ning´un beneficio adicional al resto de los jugadores. Es decir, si se cumple que v(S) = v(S− {i}) + v({i}),para toda coalicion Scon i∈S Proposici´on 3.4.8. Se considera el juego (N, v). El nucleolus N(N, v)verifica las siguientes propiedades: 1. Si el core del juego es no vac´ıo, entonces el ´unico elemento del nucleolus pertenece al core. 2. Si el core del juego es unitario, entonces el core coincide con el nucleolus. 3. Sea N(N, v) = (N1,N2, ..., Nn)el nucleolus. Si i, j son jugadores sim´etricos, entonces Ni=Nj. 4. Sea N(N, v)=(N1,N2, ..., Nn)el nucleolus. Si i∈Nes un jugador pasivo, entonces Ni=v({i}). El lector interesado puede ver la demostraci´on en Joaqu´ın P´erez y otros [1] M´etodo para calcular el nucleolus utilizando programaci´on lineal Para calcular el nucleolus x = (x1, x2, ..., xn) del juego (N, v), se resuelve 64 Optimizaci´on Lineal aplicada a Teor´ıa de Juego el siguiente programa lineal: m´ın α1 v(S)−X i∈S xi≤αi,para S ∈P(N), S 6=∅, S 6=N x∈I(N, v) Sea α∗ 1el m´ınimo de ese problema. Si tal m´ınimo se alcanza en un ´unico punto ˆx, entonces ˆxes el nucleolus y el c´alculo est´a completo. Normalmente dicho m´ınimo no se alcanzar´a en un ´unico punto xsino en un conjunto X1. En tal caso normalmente habr´a una familia =1de coaliciones, tal que para todo S∈ =1yx∈X1es e(S, x) = α1. Entonces se resueve el programa lineal m´ın α2 v(S)−X i∈S xi≤α2,para S ∈P(N)− =1, S 6=∅, S 6=N x∈X1. Si el m´ınimo se alcanza en un ´unico xse termina, si no es as´ı se sigue como anteriormente. Ejemplo 3.4.9. En un departamento universitario hay tres investigadores consolidados que trabajan en la misma linea de investigaci´on. Se disponen a presentar solicitudes para optar a financiaci´on de proyectos de investigaci´on. Han preguntado a una persona de confianza que tiene toda la informaci´on sobre los criterios y candidatos y les ha comentado lo que es previsible que ocurra con la resoluci´on acerca de las posibles solicitudes, a la vista del historial y m´eritos de los candidatos. Si el doctor D´ıaz presenta de manera individual la solicitud, lo previsible es que le concedan treinta mil euros, el doctor Garc´ıa no conseguir´a nada si JUEGOS COOPERATIVOS 65 va solo, mientras que la doctora L´opez conseguir´ıa individualmente cincuenta mil euros. Si los doctores D´ıaz y Garc´ıa presentan un proyecto conjunto obtendr´an una financiaci´on de 50, D´ıaz y L´opez obtendr´ıan 80 y Garc´ıa y L´opez obtendr´ıan tambien 80 (siempre en miles de euros). Si los tres investigadores solicitan el proyecto de manera conjunta, previsiblemente obtendr´ıan 100(en miles de euros). Cada investigador s´olo puede figurar en una solicitud. La representaci´on del juego en forma coalicional es inmediata en este caso: N={1,2,3} en donde el jugador 1 es el doctor D´ıaz, el jugador 2 es el doctor Garc´ıa y la jugadora 3 es la doctora L´opez. La funci´on caracter´ıstica es la funci´on v:P(N)→R, con v(∅)=0, v({1}) = 30, v({2}) = 0, v({3}) = 50, v({1,2}) = 50, v({1,3}) = 80, v({2,3}) = 80, v({1,2,3}) = 100 Calculemos el nucleolus. Para este juego se verifica que v({1}) + v({2}) + v({3}) = 80 < v({1,2,3}) = 100, por lo que el conjunto de imputaciones es no vac´ıo y el nucleolus existe y es ´unico. Sea x= (x1, x2, x3)el nucleolus. Por pertenecer el nucleolus, por definici´on, al conjunto de imputaciones se tienen que cumplir las siguientes condiciones: x1≥30, x2≥0, x3≥50, x1+x2+x3= 100 Los valores de e(S, x)para S∈P(N), con S6=∅yS6=N, y x= (x1, x2, x3) son los siguientes: 66 Optimizaci´on Lineal aplicada a Teor´ıa de Juego S{1} {2} {3} {1,2} {1,3} {2,3} e(S, x) 30 −x1−x250 −x350 −x1−x280 −x1−x380 −x2−x3 Para calcular el nucleolus hay que resolver el siguiente problema: m´ın x1,x2,x3 {m´ax{30 −x1,−x2,50 −x3,50 −x1−x2,80 −x1−x3,80 −x2−x3}}, sujeto a: x1≥30, x2≥0, x3≥50, x1+x2+x3= 100 Para resolver el anterior problema minimax se procede de la siguiente forma, se define: m´ax{30 −x1,−x2,50 −x3,50 −x1−x2,80 −x1−x3,80 −x2−x3}=α1 Cada una de las funciones a las que afecta la maximizaci´on anterior debe ser menor o igual a α1. El problema minimax formulado es equivalente al siguiente programa lineal: m´ın x1,x2,x3,α1 α1 30 −x1≤α1 −x2≤α1 50 −x3≤α1 50 −x1−x2≤α1 80 −x1−x3≤α1 80 −x2−x3≤α1 x1≥30 x2≥0 x3≥50 x1+x2+x3= 100. JUEGOS COOPERATIVOS 67 Resolvemos el problema anterior con alg´un programa inform´atico para programas lineales, y obtenemos que el programa tiene soluci´on ´optima que no es ´unica. Dicha soluci´on ´optima se alcanza para α1= 10, x1= 30 yx2, x3tales que x2≥0, x3≥50 yx2+x3= 70. (En la soluci´on ´optima del programa lineal no se satura ninguna de las 5 primeras restricciones y s´ı se satura la sexta restricci´on.) Podemos asegurar que la primera componente del nucleolus es x1= 30 pero a´un no podemos concretar su segunda y tercera componente. Para ello hay que resolver el siguiente programa: m´ın x1,x2,x3,α1 α2 −x2≤α2 50 −x3≤α2 20 −x2≤α2 50 −x3≤α2 x2≥0 x3≥50 x2+x3= 70 El problema tiene soluci´on ´unica, que es x2= 20, x3= 50, α2= 0. Por tanto, el nucleolus del juego es N= (30,20,50).