El problema de la asignación de costes en problemas de optimización

Trabajo Fin de Grado El problema de la asignaci´on de costes en problemas de optimizaci´on. Autor: Jos´e Ram´on S´anchez Leo Tutor: Justo Puerto Albandoz Universidad de Sevilla Facultad de Matem´aticas Junio 2017 Abstract The problem of cost allocation in optimization problems can be solved by game theory, in particular with cooperative games. Actually, in this work we will try to give conditions so that the core of a cooperative games is nonempty, since if it is nonempty we will have a solution. ´ Indice general 1. Introducci´on 7 2. Juegos Cooperativos 11 2.1. Conceptos Introducctorios . . . . . . . . . . . . . . . . . . . . . . 12 2.2. Core.................................. 17 2.3. Colecciones equilabradas . . . . . . . . . . . . . . . . . . . . . . . 20 3. Juego de Asignaci´on 29 3.1. MatchingMarkets .......................... 33 4. Juego de Producci´on Lineal 37 4.1. Aplicaci´on con CPLEX . . . . . . . . . . . . . . . . . . . . . . . 41 5. Juegos de Localizaci´on 47 5.1. Problema Continuo de Localizaci´on . . . . . . . . . . . . . . . . . 48 5.2. Juego de localizaci´on minimax . . . . . . . . . . . . . . . . . . . 54 5.3. Juego de localizaci´on de Weber, con coste fijo . . . . . . . . . . . 57 5.4. Juego de localizaci´on de Weber, con coste fijo variable . . . . . . 59 6. Juegos de Radio y Di´ametro 65 6.1. Espacios m´etricos de red . . . . . . . . . . . . . . . . . . . . . . . 70 6.1.1. Grafos medianos . . . . . . . . . . . . . . . . . . . . . . . 74 6.1.2. MSTGyMRLG ....................... 75 6.2. Espacios m´etricos discretos . . . . . . . . . . . . . . . . . . . . . 76 6.3. lpespacio m´etrico sobe Rd...................... 77 6.3.1. Espacios eucl´ıdeos . . . . . . . . . . . . . . . . . . . . . . 82 5 ´ Indice general 7. Conclusiones 85 A. Aplicaci´on del Juego de Producci´on Lineal 89 6 Cap´ıtulo 1 Introducci´on Vamos a analizar el problema de asignaci´on de costes mediante la teor´ıa de juegos. Es necesario observar que dicha teor´ıa tiene dos enfoques b´asicos en el an´alisis, de lo que denominaremos, un juego: cooperativo y no cooperativo. Antes de analizar las diferencias entre ambos tipos de juegos, contextualicemos hist´oricamente la teor´ıa de juegos. Los postulados b´asicos de la teor´ıa de juegos aparecen durante las d´ecadas de los 40 y 50 de la mano de Johan Von Neumann, Oskar Morgenstern y John Nash. Esta teor´ıa aparece con idea de resolver conflictos meramente econ´omicos, cuando los principales economistas la conocieron cambiaron su forma de tomar sus decisiones. Esto se debe a que Nash, Neumann y Morgenstern concluyen que: el inter´es individual, el ego´ısmo y la racionalidad a la hora de tomar decisiones, conducen a los seres humanos a una situaci´on no ´optima; y, esto va en contra de lo que planteaba la econom´ıa cl´asica, dada por Adam Smith. Los textos m´as importantes que aparecieron entonces fueron [23] y [19]. La diferencia principal entre un juego cooperativo y uno no cooperativo es que en el cooperativo los jugadores deciden enfrentarse a una situaci´on de forma conjunta y, si es posible, tomar una postura ante esta para as´ı minimizar costes, o maximizar beneficios; luego comparten informaci´on y las preferencias de cada uno con el resto. Sin embargo, en los juegos no cooperativos cada jugador trata de solucionar una situaci´on por su cuenta, sin compartir necesariamente informaci´on con el resto. 7 Introducci´on En los juegos no cooperativos es necesario hacer dos distinciones b´asicas entre juegos est´aticos y juegos din´amicos. En los juegos est´aticos los jugadores toman sus decisiones de forma simult´anea (es decir, cada jugador toma su decisi´on sin conocer la decisi´on del resto), mientras que en los din´amicos puede darse el caso de que un jugador conozca ya las decisiones de otro antes de decidir. En los juegos cooperativos se analizan las posibilidades de que algunos o todos los agentes, jugadores, lleguen a un acuerdo sobre que decisiones va a tomar cada uno. Dentro de la teor´ıa de juegos, los juegos cooperativos son la herramienta m´as conveniente para solucionar problemas de asignaci´on de costes, ya que su objetivo es repartir costes o beneficios, dependiendo de la situaci´on, entre varios agentes. Ya que nos vamos a centrar en los juegos cooperativos, vamos a analizar su contexto hist´orico. Ya en [23], en 1944, aparece el concepto de juego cooperativo. En cuatro art´ıculos entre 1950 y 1953 John Nash hizo contribuciones importantes tanto a la teor´ıa de juegos no cooperativa. Nash demostr´o la existencia de un equilibrio estrat´egico para los juegos no cooperativos -el equilibrio de Nash- y propuso el ”programa de Nash”, en el que sugiri´o acercarse al estudio de los juegos cooperativos a trav´es de su reducci´on a forma no cooperativa. En 1963, O. N. Bondareva estableci´o que para un juego TU su core es no vac´ıo si es equilibrado, veas´e [1]. As´ı se obtuvo una condici´on necesaria para que el core, de un juego cooperativo, fuera no vac´ıo. Esto es el conocido como Teorema de Bondareva-Shapley que enunciaremos y demostraremos en el Cap´ıtulo 2. En los juegos cooperativos se parte de que es posible que algunos jugadores puedan llegar a acuerdos vinculantes, por lo que se trata de estudiar los resultados que puede obtener cada una de las coaliciones de jugadores que se puedan formar. Se trata, por tanto de estudiar c´omo pueden actuar las distintas posibles coaliciones de jugadores, interes´andonos los comportamientos colectivos y sin que haga falta detenerse en las acciones individuales de cada uno de los miembros de una coalici´on. En el Cap´ıtulo 2, de este trabajo fin de grado, introducimos las primeras ideas y conceptos necesarios para tratar juegos cooperativos, dichos conceptos son necesarios para el resto de cap´ıtulos. El objetivo principal es introducir el 8 Introducci´on concepto de core, como soluci´on de un juego cooperativo, y dar una condici´on necesaria y suficiente para que sea no vac´ıo. Durante el Cap´ıtulo 3, analizamos uno de los tipos de juegos m´as importantes para la teor´ıa de juegos: el Juego de Asignaci´on. En pocas palabras podr´ıamos decir que se trata de una situaci´on de reparto, por ejemplo de bienes o tareas, entre usuarios que demandan dichos servicios. El resultado principal de este cap´ıtulo es que el core de este juego es no vac´ıo. Adem´as trataremos situaciones reales que fueron resueltas mediante el estudio de ”Matching Markets”, que esta muy relacionado con el Juego de Asignaci´on. Esto ´ultimo dio lugar a un premio Nobel. Seguidamente en el Cap´ıtulo 4, desarrollamos el Juego de Producci´on Lineal. Se trata de un juego en el que diversos agentes tratan de usar de forma conjunta sus bienes para producir determinados productos que se puedan vender a un precio de mercado fijo. De nuevo, el resultado principal es el teorema que prueba que el core de este juego es no vac´ıo. Tambi´en, hemos resuelto una situaci´on de producci´on lineal usando CPLEX mediante NEOS-SERVER, el c´odigo se puede consultar en el Ap´endice A. A continuaci´on, en el Cap´ıtulo 5, tratamos los Juegos de Localizaci´on. Al comienzo damos las ideas principales de estos juegos, introduciendo el concep- to de situaci´on de localizaci´on. Despu´es, tratamos distintos casos concretos de juegos de localizaci´on: el minimax, el de Weber con coste fijo y el de Weber con coste fijo variable. Como antes, los resultados m´as importantes son aquellos que dan condiciones suficientes para que el core de estos juegos sea no vac´ıo. Aqu´ı encontraremos una variedad de ejemplos de cada situaci´on. Tras esto, en el Cap´ıtulo 6, estudiamos un caso similar a los del cap´ıtulo anterior pero que se definen de una forma ligeramente distinta, veremos los Juegos de Radio y Di´ametro. En este cap´ıtulo estudiaremos la existencia de puntos en el core y la existencia de representaciones polinomiales de este, centr´andonos en redes. El juego que estudiaremos, principalmente, ser´a el juego de localizaci´on de radio m´ınimo. De nuevo, hemos a˜nadido una gran variedad de ejemplos de las distintas situaciones. Para terminar, en el ´ultimo cap´ıtulo se incluyen las conclusiones de este Trabajo Fin de Grado. 9 Cap´ıtulo 2. Juegos Cooperativos n−2. Si el juego es de suma constante, tenemos una condici´on adicional. (v)v(n−S) = v(N)−v(S),∀S⊆N. (2.10) Con esta nueva condici´on nuestro conjunto tiene dimensi´on 2n−1−n−1. Por lo tanto, es claro que la dimensi´on del conjunto de juegos de npersonas en suma constante es la misma que la del conjunto de juegos de (n−1) personas. De hecho son conjuntos congruentes. En particular, si ues un juego de (n−1) personas normalizado (0,1), puede ser ampliado a un juego de suma constante de npersonas mediante la adicci´on de un nuevo jugador n, definimos: v(S) =    u(S) si n6∈ S 1−u(N−S) si x∈S. Es f´acil comprobar que es un juego de suma constante. Definamos ahora dos tipos de juegos especiales que son de nuestro inter´es: Definici´on 2.11. Un juego vse dice sim´etrico si v(S) depende solo del n´umero de elementos de S. Definici´on 2.12. Un juego normalizado en norma (0,1) se dice simple si, para cada S⊆N, se tiene que, o bien, v(S) = 0, o bien, v(S) = 1. Un juego es simple si su normalizaci´on en (0,1) es simple. Esencialmente, un juego simple es aquel en el que cualquier coalici´on o bien gana (valor 1) o pierde (valor 0), sin posibilidad de tomar valores intermedios. Como tales, los juegos simples son aplicables a ciencias pol´ıticas, como juegos de votaciones en elecciones. Entre los juegos simples, distinguimos un clase especial: los juegos de mayor peso: Definici´on 2.13. Sea (p1, p2, . . . , pn) un vector no negativo, y sea qsatisfaciendo: 0< q ≤ n X i=1 pi. 16 Cap´ıtulo 2. Juegos Cooperativos Entonces, el juego de mayor peso [q;p1, p2, . . . , pn] es el juego simple vdefinido por v(S) =    0 si Pi∈Spi< q 1 si Pi∈Spi≥q. 2.2. Core Ahora vamos a proceder al an´alisis de juegos en t´erminos de relaci´on de dominio. Comenzamos, obviamente, estudiando las imputaciones no dominadas. Definici´on 2.14. El conjunto de todas las imputaciones no dominadas para un juego ves llamado Core. Lo denotaremos como C(v). Teorema 2.3. El core del juego ves el conjunto de todos los vectores x satisfaciendo: (a)X i∈S xi≥v(S),∀S⊆N (b)X i∈N xi=v(N). (2.11) Lo podemos escribir en forma de conjunto: Core(v) = C(v) = {x∈RN +:x(N) = v(N); x(S)≥v(S),∀S⊆N}(2.12) Demostraci´on. Si S={i}, la primera condici´on se reduce a xi≥v{i}. Supongamos que xsatisface ambas condiciones, y que yi> xi,∀i∈S. Pero esto, junto con (a) , significa que X i∈S yi> v(S), luego no es posible que xSy. Por lo tanto, x∈C(v). Por el contrario, supongamos que yno satisface las condiciones. Si no satisface la segunda ni siquiera es una imputaci´on y por lo tanto no esta en C(v). Supongamos, entonces que hay alg´un S⊆Nno vac´ıo tal que: X i∈S yi=v(S)−ε, 17 Cap´ıtulo 2. Juegos Cooperativos con ε > 0. Sea: α=v(N)−v(S)−X i∈N−S xi=v({i}) Es f´acil ver, por superaditividad, que α≥0. Finalmente, sea s el cardinal de S. Ahora definimos z como: zi=   yi+ε s, i ∈S v({i}) + α n−s, i 6∈ S. Se ve f´acilmente que zes una imputaci´on y, adem´as zSy. Por lo tanto, y6∈ C(v).  Observaci´on 2.1. M´as adelante, en el Juego de Localizaci´on el core ser´a el de un juego de coste (N, c) que es el siguiente: Core(v) = C(v) = {x∈RN +:x(N) = v(N); x(S)≤v(S),∀S⊆N}(2.13) El Teorema 2.3 muestra que C(v) es un conjunto convexo cerrado (ya que se define con desigualdades no estrictas). Esto es muy interesante, ya que la teor´ıa econ´omica cl´asica suele dar el core como ”soluci´on” a la mayor´ıa de los problemas de teor´ıa de juegos. Generalmente, por supuesto, el Core puede tener m´as de un punto. Esto no es una gran desventaja; simplemente significa que m´as de un resultado es estable. La gran dificultad con el core es que puede ser vac´ıo. Teorema 2.4. Si ves un juego esencial de suma constante, entonces C(v) = ∅. Demostraci´on. Supongamos x∈C(v). Para cualquier i∈N, sabemos que X j∈N−{i} xj≥v(N−{i}) pero, al ser un juego de suma constante: v(N−{i}) = v(N)−v({i}) y, ya que x es una imputaci´on, tenemos xi≤v({i}). Dado que ves esencial, 18 Cap´ıtulo 2. Juegos Cooperativos tenemos Xxi≤Xv({i})< v(N). Pero esto significa que x6∈ E(v). La contradicci´on implica que C(v) = ∅. Ejemplo 2.1. Ahora analizamos el caso particular de los llamados Juegos Simples. Vamos a comprobar que el core de estos juegos normalizados (0,1) es no vac´ıo en ciertas condiciones. Sea vun juego simple normalizado (0,1). Decimos que el jugador ies un jugador vetado si v(N−{i}) = 0 donde, como hemos observado antes, Nes el conjunto de todos los jugadores. Supongamos que vno tiene jugadores vetados. Entonces, para cada i∈N, tenemos v(N− {i}) = 1. Para que la imputaci´on xeste en el core, tiene que verificar: X j∈N xj=v(N)=1, X j6=i xj≥v(N−{i}) = 1 Por lo tanto, xi= 0,∀i, y entonces xno puede ser una imputaci´on. Esta contradicci´on prueba que Core(v) = C(v) = ∅. Supongamos ahora que vtiene uno o m´as jugadores vetados; sea Sel conjunto de todos ellos. Sea x tal que X i∈S xi= 1, xi≥0 para todo i∈S, xi= 0 para i6∈ S. Ahora, si Tes una coalici´on ganadora, tenemos que S⊂T, entonces X i∈T xi≥X i∈S xi=1=v(T), y podemos comprobar que x∈C(v) = Core(v). Por lo tanto, C(v)6=∅, y concluimos que, para un juego simple v, el core es no vac´ıo si y s´olo si hay al menos un jugador vetado. 19 Cap´ıtulo 2. Juegos Cooperativos 2.3. Colecciones equilabradas El Teorema 2.4 nos proporciona un caso en el que el core es vac´ıo. Esto parece de inter´es para determinar, de forma m´as general, aquellos juegos que tienen core no vac´ıo. Es f´acil comprobar que, para cualquier n, el conjunto de juegos de npersonas con core no vac´ıo (pensado como un subconjunto del espacio eucl´ıdeo de dimensi´on 2n−1) es un cono convexo. Supongamos que tenemos dos juegos vywcon core no vac´ıo, con x∈C(v), y ∈C(w). Es f´acil comprobar que, para dos escalares no negativos rys, rx +sy ∈C(rv +sw). Con el fin de caracterizar este cono convexo, observemos que C(v) = ∅si y s´olo si el problema de programaci´on lineal (P) m´ın n X i=1 xi=z s.a.: X i∈S xi≥v(S) para toda S⊂N. (2.14) tiene un m´ınimo z∗≤v(N). Para, en tal caso, cualquier x∗m´ınimo esta en el core. A la inversa, si x∈C(v), entonces xsatisface la condici´on de (2.14) y, adem´as, X i∈N xi=v(N). Por lo tanto, el minimo debe ser z∗≤v(N). Ahora consideremos el dual del problema (P): (P∗) m´ax X S⊂N ySv(S) = q s.a.: X i∈S⊂N yS= 1 para todo i∈N, yS≥0 para toda S⊂N. (2.15) Ambos problemas de programaci´on lineal (P) y (P∗) son factibles, y entonces el m´ınimo, z∗, tiene que ser igual al m´aximo, q∗. Por lo tanto, C(v)6=∅si y s´olo si el m´aximo q∗≤v(N). Esto lo podemos escribir con las siguientes palabras, Teorema 2.5. Una condici´on necesaria y suficiente para que un juego vtenga core no vac´ıo, C(v)6=∅, es que, para cada vector no negativo (yS)S⊂Nque 20 Cap´ıtulo 2. Juegos Cooperativos verifique la primera condici´on de (2.15), tengamos X S⊂N ySv(S)≤v(N).(2.16) En este formato, el Teorema 2.5 no es una herramienta muy eficiente. Ya que necesita resolver el programa lineal (P), que no es m´as simple que su dual. Sin embargo, resulta que podemos caracterizar los puntos extremos del programa dual (P∗) con un concepto bastante fino: que son las colecciones equilibradas. Definici´on 2.15. Sea C={S1, S2, . . . , Sm}colecci´on no vac´ıa de subconjuntos de N={1,2, . . . , n}. Diremos que Ces N-equilibrado (o simplemente, equilibrado cuando no haya confusi´on respecto a N) si existen n´umeros positivos y1, y2, . . . , ymtales que, para cada i∈N, X j;i∈Sj yj= 1. Entonces y= (y1, y2, . . . , ym) es el vector de equilibrio para C; los yjson llamados coeficientes de equilibrio. Ejemplo 2.2. La colecci´on {N}es claramente equilibrada y, de hecho, cualquier partici´on de N(cualquier colecci´on de conjuntos no vac´ıos disjuntos cuya uni´on es N) es equilibrada. Los coeficientes de equilibrio aqu´ı son todos 1. Ejemplo 2.3. Sea N={1,2,3}. Entonces la colecci´on C={{1,2},{1,3},{2,3}} es equilibrada con coeficientes de equilibrio {1 2,1 2,1 2}. De forma general, para cualquier N, la colecci´on de todos los conjuntos n scon selementos es equilibrada, con todos los coeficientes de equilibrio igual a n−1 s−1−1. Ejemplo 2.4. Sea N={1,2,3,4}. Entonces C={{1,2},{1,3},{1,4},{2,3,4}} es equilibrada, con vector de equilibrio y= (1 3,1 3,1 3,2 3). 21 Cap´ıtulo 2. Juegos Cooperativos Esencialmente, una colecci´on equilibrada es una partici´on generalizada (como hemos visto en el Ejemplo 2.2). Hay, por supuesto, muchas mas colecciones N-equilibradas que particiones de N. La siguiente propiedad de las colecciones equilibradas es de inter´es. Teorema 2.6. La uni´on de colecciones equilibradas es equilibrada. Demostraci´on. Sean C={S1, . . . , Sm}yD{T1, . . . , Tk}colecciones equilibradas, con vectores de equilibrio respectivos (y1, . . . , ym)y(z1, . . . , zk). Entonces, C∪D={R1, . . . , Rq} donde q≤m+k. Para cada t, 0 <t<1, definimos: wj=         tylsi Rj=Sl∈C−D (1 −t)zpsi Rj=Tp∈D−C tyl+ (1 −t)zpsi Rj=Sl=Tp∈C∪D Es f´acil comprobar que (w1, . . . , wq) es un vector de equilibrio para C∪D. Por lo tanto, la uni´on de dos colecciones equilibradas es equilibrada, y, por inducci´on, la uni´on de colecciones equilibradas es equilibrada.  Lema 2.1. Sean CyDcolecciones equilibradas tales que: C⊂Dcon C6=D. Entonces existe una colecci´on equilibrada Btal que: B∪C=D, con B6=D. Adem´as, el vector de equilibrio Dno es ´unico. Demostraci´on. Sean: C={S1, S2, . . . , Sk}, D={S1, S2, . . . , Sk, . . . , Sm}, m > k, (2.17) que tienen como vectores de equilibrio (y1, . . . , yk) y (z1, . . . , zm), respectivamente. Para t > 0, definimos: wj= (1 + t)zj−tyj,j= 1, . . . , k, wj= (1 + t)zj,j=k+ 1, . . . , m. (2.18) 22 Cap´ıtulo 2. Juegos Cooperativos Para t > 0 peque˜no, vemos que todos wj>0. Adem´as, para i∈N, X j;i∈Sj∈D wj= (1 + t)X j;i∈Sj∈D zj−tX j;i∈Sj∈C yj= 1, y entonces wes un vector equilibrado para D. Puesto que wj> zjpara k+ 1 ≤ j≤m, vemos que zno es ´unico. Ahora, debe haber alg´un j, 1 ≤j≤k, tal que yj> zj, cuando no sea as´ı, para cualquier i∈Sk+1, tendr´ıamos 1 = X i∈Sj∈C yj≤X i∈Sj∈C zj<X i∈Sj∈D zj= 1, lo cual es una contradicci´on. Establecemos, entonces, t= m´ın zj yj−zj :yj> zj. Sea C0={Sj|Sj∈C,(1 + t)zj=tyj},y el conjunto: B=D−C0.Claramente, C0es una subcolecci´on no vac´ıa de C, y entonces tenemos: B6=D,B∪C=D. Adem´as, wj>0,∀Sj∈B, y esto es f´acil de comprobar (para este valor de t)w es un vector de equilibrio de la colecci´on B. Por lo tanto, Bes como deseamos.  A continuaci´on, definimos el concepto de colecci´on m´ınima equilibrada como una colecci´on equilibrada que no tiene subcolecciones propias equilibradas. Teorema 2.7. Cualquier colecci´on equilibrada es uni´on de colecciones m´ınimas equilibradas. Demostraci´on. Por inducci´on sobre m(el n´umero de conjuntos en la colecci´on). El teorema se verifica claramente cuando m= 1, la ´unica colecci´on equilibrada con un conjunto es {N}, que evidentemente es cierto. Supongamos, entonces, que esto es cierto para todas las colecciones con m−1 o menos elementos. Sea Duna colecci´on equilibrada con melementos. 23 Cap´ıtulo 2. Juegos Cooperativos Si Des en s´ı misma m´ınima, entonces es claramente uni´on de colecciones m´ınimas equilibradas. Si Dno es m´ınima, entonces tenemos que probar que tiene una subcolecci´on propia equilibrada, C, y, por el lema anterior, existir´a otra subcolecci´on propia equilibrada, B, tal que B∪C=D. Como ByCson subcolecciones propias, cada uno tendr´a m−1 o menos elementos, y por lo tanto cada uno se puede expresar como uni´on de colecciones m´ınimas equilibradas. Pero entonces Des tambi´en union de colecciones m´ınimas equilibradas.  Ahora, vamos a demostrar un resultado t´ecnico relativo a la suma de los coeficientes de equilibrio de la familia de coaliciones equilibradas. Recordemos que una colecci´on de coaliciones, B⊂2N, es equilibrada si y s´olo si existe un conjunto de coeficientes reales positivos {γS/S ∈B}(coeficientes de equilibrio) satisfaciendo que PS:ai∈SγS= 1 para cada ai∈N. El conjunto de los coeficientes de equilibrio asociados a una colecci´on equilibrada no tiene porque ser ´unico. Sin embargo, cada colecci´on equilibrada m´ınima de coaliciones (en el sentido de que no contiene otra recolecci´on equilibrada) tiene un ´unico conjunto de coeficientes de equilibrio (como ya hemos probado en el Teorema 2.8). Tambi´en hemos probado anteriormente que un juego (N,c) tiene core no vac´ıo si y s´olo si para cada coalici´on m´ınima equilibrada B, con coeficientes de equilibrio {γ/S ∈B}, se verifica que PS∈BγSc(S)≥c(N) (Teorema de Bondareva- Shapley, observemos que la desigualdad es la contraria al ser un juego de coste). Observemos que solo la colecci´on equilibrada con coeficientes de equilibrio que suman 1 es B= 1. En efecto, para cada colecci´on equilibrada By cada ai∈N, PS:ai∈SγS= 1; si, adem´as, PS∈BγS= 1 entonces, para cada S∈B y cada ai∈N, ai∈S. Por lo tanto, S=N, y por lo tanto B={N}. Diremos que B={N}es la colecci´on trivial. El siguiente resultado acota la suma de los coeficientes de equilibrio para cualquier colecci´on no trivial equilibrada. Lema 2.2. Sea Buna colecci´on no trivial equilibrada con coeficientes de equilibrio {yS:S∈B}.Entonces, n n−1≤X S∈B ys≤n. 24 Cap´ıtulo 2. Juegos Cooperativos Demostraci´on. Consideremos el siguiente problema de programaci´on lineal (1): m´ın X S∈2N\{N} yS s. a.: X S∈2N\{N}:ai∈S yS= 1, ys≥0,∀S∈2n\{N}. La soluci´on de este problema es un conjunto de coeficientes equilibrados de un una colecci´on no trivial con suma m´ınima (B={S∈2N:yS>0}). Denotemos la coalici´on N\{aj}={a1, . . . , aj−1, aj+1, . . . , an}por −j. Consideremos la base Bdel problema (1) cuyas columnas corresponden a y−1, y−2, . . . , y−n. En este problema la matriz de B, su inversa B−1y la transformaci´on por el lado derecho B−1bson: B=         −(n−2) 1 . . . 1 1−(n−2) . . . 1 . . .. . ..... . . 1 1 . . . −(n−2)         , B−1=1 n−1         −(n−2) 1 . . . 1 1−(n−2) . . . 1 . . .. . ..... . . 1 1 . . . −(n−2)         , B−1b=1 n−1,..., 1 n−1t . Los costes reducidos para cualquier coalici´on Scon 1 ≤k≤n−1 jugadores son: cbB−1aS−cS=k n−1−1<0 sii k < n −1, cbB−1aS−cS=n−1 n−1−1 = 0 sii k=n−1. Entonces B es una base asociada con una soluci´on ´optima de (1), que prueba el l´ımite inferior. La prueba para el l´ımite superior es directa y se sigue tomando la colecci´on cuyos elementos son todos los conjuntos de tama˜no uno con coeficientes iguales a 1.  Teorema 2.8. Una colecci´on equilibrada tiene un ´unico vector de equilibrio si 25 Cap´ıtulo 3. Juego de Asignaci´on y entonces todo z0 j≥0. Por lo tanto, (y0, z0) es una imputaci´on del juego v. Veamos que pertenece a C(v). Para cualquier S, tenemos: v(S) = ci1j1+... +ciqjq, donde i1, ..., iq, j1, ..., jqson distintos miembros de S. Entonces X i∈S y0 i+X m+j∈S z0 j≥y0 i1+... +y0 iq+z0 i1+... +z0 iq≥ ≥ci1j1+... +ciqjq=v(S). y concluimos que (y0;z0)∈C(v). En algunos casos, (y0;z0) ser´a la ´unica imputaci´on del core. M´as habitualmente la imputaci´on no ser´a ´unica. De hecho, cualquier vector m´ınimo (y∗;z∗) con componentes no negativas estar´a situado en el core. Lo usual es que la asignaci´on ´optima de vendedores a compradores, dada por el problema principal, es ´unica; sin embargo, el precio de mercado, dado por el dual, no es ´unico. Ejemplo 3.1. Un ejemplo de un juego de asignaci´on. Un vendedor (Juan, j1) tiene un coche sin valor para ´el, a menos que pueda venderlo. Dos compradoras (Roc´ıo, j2, y Mar´ıa, j3) valoran el objeto en 90e y en 100erespectivamente. Si Juan vende el coche a Roc´ıo al precio de x, ´el obtendr´a un beneficio de x, mientras que el beneficio de Roc´ıo ser´a de 90−x. El beneficio total de la coalici´on {j1, j2}es entonces 90e. Para lo coalici´on {j1, j3} es similar con un beneficio de 100e. Por lo tanto, v({j1, j2}) = 90, v({j1, j3}) = 100. (3.2) Por otro lado, un jugador solo, o los dos compradores, no obtiene ning´un beneficio. Por lo tanto, v({j1}) = v({j2, j3})=0. Por ´ultimo, la coalici´on de los tres jugadores puede no hacer nada mejor que 32 Cap´ıtulo 3. Juego de Asignaci´on asignar el coche a Mar´ıa, j3. Por lo tanto, v({j1, j2, j3}) = 100. Por todo esto el core est´a formado por todos los vectores (x1, x2, x3) que verifican: x1+x2≥90, x1+x3≥100, x1+x2+x3= 100, xi≥0. Esto implica que x1≥90, x2= 0, x1+x3= 100, x3≥0.Por lo tanto, Core(v) = C(v) = {(t, 0,100 −t)|90 ≤t≤100}.(3.3) Esto quiere decir que Mar´ıa, j3, comprar´a el coche al precio de al menos 90e. Roc´ıo, j2, tiene un precio fuera de mercado - a partir que la ”puja” supere el precio de 90e. Podemos concluir que los Juegos de Asignaci´on tienen siempre core no vac´ıo, luego podremos dar alguna soluci´on al problema. Aunque en muchas situaciones tendremos m´as de una imputaci´on en el core, luego tendremos m´as de una posible soluci´on. 3.1. Matching Markets Encontramos una situaci´on muy similar a la anterior en ”Matching Markets”, la gran diferencia consiste en que ahora el coste no puede ajustarse para asignar recursos, ya que en muchos casos reales el coste se descarta por motivos ´eticos. Algunos de estos casos son asignar estudiantes a colegios o institutos, asignar ´organos a pacientes enfermos, m´edicos a hosptiales y otros muchos casos. Como curiosidad debemos se˜nalar que Alvin E. Roth obtuvo su premio Nobel de econom´ıa en 2012 por sus contribuciones a ”Matching Markets”. El algoritmo de Shapley-Gale, descrito en 1962, para asignar parejas entre hombres y mujeres, es la primera vez en la que aparecen este tipo de problemas. Analizaron, desde un punto de vista abstracto, como deber´ıan asignarse 33 Cap´ıtulo 3. Juego de Asignaci´on diez hombres y diez mujeres, respetando sus preferencias. Con el algoritmo de ”aceptaci´on en diferido” (”deferred acceptance”) dieron con una correspondencia estable. El algoritmo puede configurarse de dos maneras alternativas: o los hombres proponen a las mujeres, o las mujeres proponen a los hombres. Si son las mujeres las que proponen a los hombres, el proceso comienza con cada mujer proponi´endose al hombre que m´as le gusta. A continuaci´on, cada hombre mira las diferentes propuestas que ha recibido (si existen), retiene la que considera como la mejor propuesta y rechaza el resto. Las mujeres que fueron rechazadas en la primera ronda se proponen entonces a sus segundas mejores elecciones, mientras que los hombres vuelven a mantener su mujer propuesta. Esto continua hasta que ninguna mujer quiera hacer m´as propuestas. Cuando cada uno de los hombres acepta la propuesta que tiene el proceso finaliza. Gale y Shapley demostraron que este algoritmo siempre conduce a una situaci´on estable. Es importante conocer la estructura distributiva del algoritmo, ya que si el derecho a proponer se le da a las mujeres, como hemos descrito antes, el resultado es mejor para los hombres y, al contrario, si el derecho a proponer es de los hombres. Alvin E. Roth estudi´o el problema de asignar de m´edicos reci´en graduados a hospitales. En Estado Unidos cuando un estudiante de medicina finaliza sus estudios, en gran parte, pasa a trabajar de residente en un Hospital. Se percat´o de que el algoritmo usado por ”National Resident Matching Program (NRMP)”, para asignar reci´en licenciados a hospitales, estaba muy relacionado con el algoritmo de Shapley-Gale. A pesar de funcionar correctamente, y ser usado m´as all´a de Estados Unidos, el NRMP no funcionaba a la perfecci´on. Uno de los problemas fue que el n´umero de mujeres estudiantes creci´o y, as´ı, el n´umero de parejas reci´en graduadas que quer´ıan hacer la residencia de forma conjunta. Como ya hemos comentado anteriormente, el lado que propone (en este caso los hospitales) es sistem´aticamente favorecido, esto provoco muchas cr´ıticas. En 1995, se le pidi´o a Roth que ayudara a dise˜nar un algoritmo mejorado que eliminar´a estos problemas. El nuevo algoritmo, implementado desde 1997, ha funcionado bastante bien. Parec´ıa que los solicitantes pod´ıan manipular el algoritmo al rechazar ofertas que realmente prefer´ıan y mantener las que eran peores, para as´ı lograr un mejor resultado. En varios trabajos te´oricos Roth mostr´o que esto pod´ıa suceder, por ello el algoritmo fue revisado y dise˜nado para ser inmune a 34 Cap´ıtulo 3. Juego de Asignaci´on manipulaci´on. El algoritmo de Gale-Shapley tambi´en se puede usar, por ejemplo, en la elecci´on de institutos o colegios. En 2003, Roth y sus colaboradores ayudaron a redise˜nar el proceso de admisi´on que hab´ıa hasta entonces, basado en un algoritmo del tipo de Gale-Shapley. El algoritmo resulto ser exitoso. Hoy, un n´umero creciente de ´areas metropolitanas de Estados Unidos usa alguna variante de ´este. Todo esto est´a claramente relacionado con el Juego de Asignaci´on. La caracter´ıstica m´as sorprendente de estos algoritmos es que los precios no forman parte del proceso. 35 Cap´ıtulo 3. Juego de Asignaci´on 36 Cap´ıtulo 4 Juego de Producci´on Lineal Analicemos ahora el Juego de Producci´on Lineal. Este problema fue analizado por primera ver por G. Owen, en [14]. Se trata de un juego en el que los jugadores combinan recursos para producir productos terminados que puedan venderse a un precio de mercado determinado. El proceso de producci´on es lineal, de modo que la funci´on caracter´ıstica puede obtenerse resolviendo programas lineales. La teor´ıa de la dualidad de la programaci´on lineal se utiliza para obtener vectores de equilibrios de precios y para probar que el core es no vac´ıo. Consideremos entonces el juego de producci´on con N={1,2, . . . , n}conjun- to de jugadores, cada jugador tiene un paquete de tama˜no qde productos. M´as espec´ıficamente, el jugador itiene bi1unidades del producto C1,bi2unidades de C2,..., ybiq unidades de Cq. Los productos carecen de valor por si mismos, excepto que pueden ser usados para producir bienes B1, . . . , Bm, que puedan venderse a precios fijos de mercado. Asumimos un proceso de producci´on lineal, en el que una unidad de Blrequiere a1lunidades de C1,a2lunidades de C2,..., yaql unidades de Cq, y puede ser vendido por un precio pl. Cuando se forma una coalici´on S, sus miembros pondr´an en com´un sus recursos (materia prima) para maximizar el valor de venta en el mercado de sus productos. As´ı, la funci´on caracter´ıstica viene dada por los problemas de pro- 37 Cap´ıtulo 4. Juego de Producci´on Lineal gramaci´on lineal v(S) = m´ax m X l=1 plxl s.a.: m X l=1 aklxl≤bk(S), k = 1,2, . . . , q, xl≥0, l = 1,2, . . . , m (4.1) donde: bk(S) = X i∈S bik es la cantidad total de Ckque tiene la coalici´on S. Teorema 4.1. En este juego, vtiene core no vac´ıo. Demostraci´on. Sea C={S1, S2, . . . , Sr}una colecci´on equilibrada, con vector de equilibrio (y1, y2, . . . , yr). Para cada Sj∈C, sea xj= (xj 1, . . . , xj m) vector de optimizaci´on del programa anterior definido para Sj, y sea x∗= r X j=1 yjxj≥0. Para cada k, tenemos: m X l=1 aklx∗ l= r X j=! yj m X l=1 aklxj l ≤ r X j=1 yjX i∈Sj bik =X i∈N bik X j;i∈Sj yj =X i∈N bik =bk(N). Por lo tanto, x∗satisface las condiciones del programa definido para v(N), luego m X l=1 plx∗ l≤v(N). Ahora, r X j=1 yjv(Sj) = r X j=1 yj m X l=1 plxj l= m X l=1 plx∗ l≤v(N). Como esto es cierto para toda colecci´on equilibrada C, concluimos que el juego tiene core no vac´ıo.  Hemos demostrado que v tiene core no vac´ıo. Sin embargo, es importante encontrar puntos en el core. Para ello, consideramos el programa dual de (4.1): 38 Cap´ıtulo 4. Juego de Producci´on Lineal m´ın q X k=1 bk(S)zk s.a.: q X l=1 alkzl≥pk, k = 1,2, . . . , m, zl≥0, l = 1,2, . . . , q, (4.2) v(S) ser´a igual al m´ınimo del programa (4.2). Observemos, ahora que las restricciones del programa (4.2) son independientes de S; sin embargo, el vector soluci´on (z1, . . . , zq) depender´a de S. En particular, sea (z∗ 1, . . . , z∗ q) el vector soluci´on de (4.2) cuando S=N. Entonces, v(N) = b1(N)z∗ 1+. . . +bq(N)z∗ q(4.3) mientras que, para cualquier S, v(S)≤b1(S)z∗ 1+. . . +bq(S)z∗ q(4.4) ya que v(S) es el m´ınimo para todos los vectores factibles z. Ahora, consideremos el vector de pago u= (u1, . . . , un) definido como sigue: ui=bi1z∗ 1+bi2z∗ 2+. . . +biqz∗ q= q X k=1 bikzk(4.5) Para cualquier S, tenemos X i∈S ui=X i∈S q X k=1 bikz∗ k= m X k=1 X i∈S bikz∗ k= =b1(S)z∗ 1+. . . +bq(S)z∗ q y entonces, por (4.3), X i∈N zi=v(N) y, por (4.4), X i∈S zi≥v(S), para cualquier S⊂N. Por lo tanto, zes una imputaci´on del core. Entonces, tenemos un m´etodo para obtener un punto del core: calculamos el vector z∗ 39 Cap´ıtulo 4. Juego de Producci´on Lineal resolviendo un programa lineal de tama˜no razonable (qvariables y mrestricciones). Esto entonces nos da una imputaci´on upor (4.5) Heur´ıstcamente, las componentes z∗ 1, . . . , z∗ mpueden considerarse precios de equilibrio de los recursos. A cada uno de los jugadores se les paga por sus recursos seg´un el vector de equilibrio z∗; los pagos resultantes siempre dar´an un vector en el core. Vemos que cualquier vector de equilibrio de precio z∗dar´a lugar a un punto en el core. (Puede haber m´as de un vector de equilibrio y, por lo tanto, el core puede contener m´as de un punto). La pregunta es si el inverso es verdadero, es decir, si todos los puntos en el core se pueden obtener por este procedimiento. En [20], Shapley y Shubik consideran un tipo especial de programa lineal - un problema de asignaci´on - en el cual los ”bienes”producidos son oficios. En ese caso, todos los puntos centrales se pueden obtener resolviendo el programa dual; de hecho, las limitaciones del programa dual reducen a las desigualdades b´asicas, pero esto se debe puramente al hecho de que es un tipo de programa tan especial. Para nuestros juegos m´as generales, esta conjetura no es verdad. Ejemplo 4.1. Veamos un contraejemplo trivial, consideremos un juego de dos personas con paquetes de recursos: b1= (1,0), b2= (0,2) y un ´unico producto final, una unidad requiere una unidad de cada recurso, y se vende por 100e. Entonces, el programa lineal (4.1) toma la siguiente forma: v(S) = m´ax x s.a.: x≤b1(S), x ≤b2(S), x ≥0, que nos da v(1) = v(2) = 0, v({1,2}) = 1. El core aqu´ı esta formado por todos los puntos (u1, u2) con 0 ≤u1≤1, u1+u2= 1. Siendo S=N, tenemos b(N) = (1,2). Entonces el problema dual (4.2) es el siguiente: m´ın z1+ 2z2, s.a.: z1+z2≥1, z1, z2≥0, Este tiene una ´unica soluci´on z∗ 1= 1, z∗ 2= 0. Por lo tanto, el precio de equilibrio 40 Cap´ıtulo 4. Juego de Producci´on Lineal no usa nada para el segundo recurso; ya que el jugador 2 comienza solo con este recurso, no puede recibir nada por este esquema. As´ı, s´olo se puede obtener de este manera u= (1,0), mientras que el core contiene otros muchos puntos. Concluimos entonces que el core del Juego de Producci´on Lineal es no vac´ıo. Aunque, el core puede tener m´as de un punto por lo que podr´a haber m´as de un vector de equilibrio. 4.1. Aplicaci´on con CPLEX Ahora vamos a hacer una aplicaci´on del Juego de Producci´on Lineal mediante CPLEX usando la p´agina web www.neos-server.org. NEOS-SERVER es un servicio gratuito de Internet para resolver problemas de optimizaci´on num´erica. Organizado por el Wisconsin Institute for Discovery de la Universidad de Wisconsin, NEOS-SERVER proporciona acceso a m´as de 60 m´etodos para resolver organizados en m´as de una docena de categor´ıas. Vamos a resolver una situaci´on en la que tres empresas, E1, E2, E3, E4, quieren generar tres bienes, B1, B2, B3, que necesitan distintos productos, en este caso son necesarios siete productos para generar los tres bienes, p1, . . . , p7. Las empresas poseen la siguiente cantidad de productos, las mostramos mediante el Cuadro 4.1. La cantidad de producto necesario para generar cada bien se dan en el Cuadro 4.2. E1E2E3E4 p1100 0 50 150 p240 40 0 0 p30 40 0 80 p40 90 100 200 p560 100 0 40 p640 0 30 30 p710 70 50 0 Cuadro 4.1: Cantidad de producto que tienen las empresas Ej. Los bienes que producen se venden a un precio fijo de mercado: p1= 1 p2= 2 p3= 3. 41 Cap´ıtulo 5. Juegos de Localizaci´on f´acil de probar, para que la soluci´on proporcionalmente igualitaria este en ´el. Para finalizar el cap´ıtulo tratamos el juego de localizaci´on de Weber con coste fijo no variable y con coste variable. Veremos una condici´on necesaria para que la soluci´on igualitaria est´e en el core y, tambi´en, daremos varios ejemplos de ambas situaciones analizando las diferencias entre ambos juegos. Para este cap´ıtulo hemos usado las fuentes [18] y [9]. 5.1. Problema Continuo de Localizaci´on En primer lugar, describimos que es un problema continuo de localizaci´on de instalaciones individuales. El problema consiste en encontrar una ubicaci´on para la instalaci´on que minimice el coste de transporte (que depende de la distancia de los usuarios a la instalaci´on). Formalmente, un problema continuo de localizaci´on de instalaciones individuales es una tripleta: (N, Φ, d) donde: N={a1, . . . , an}conjunto de npuntos distintos en Rm(con n≥2). Φ : Rn→Res una funci´on de globalizaci´on semicontinua inferior que verifica: 1. Φ es definida, i.e., Φ(x) = 0 si y solo si x= 0; 2. Φ es mon´otona, i.e., Φ(x)≤Φ(y) para x≤y. d:Rm×Rm→Res una medida de distancia, satisfaciendo que, para cada r, s ∈Rm, d(r, s) = f(||r−s||),donde fes una aplicaci´on semicontinua inferior, no decreciente y no negativa de Ren Rcon f(0) = 0, y ||·|| es una norma sobre Rm. Resolver el problema de localizaci´on continuo con una ´unica instalaci´on (N, Φ, d), para S⊂N, consiste en encontrar un punto x∈Rmque minimice Φ(dS(x)), donde dS(x) es el vector en Rncuya i-´esima componente es igual a d(x, ai) si ai∈Se igual a 0 en otro caso. Denotaremos L(S) = m´ınx∈RmΦ(dS(x)). Observemos que este problema siempre tiene soluci´on para cada S⊂N(ver [16]). Esta es la versi´on cl´asica del problema de localizaci´on continuo con una ´unica instalaci´on. Vamos a considerar una variante, natural, de este problema en el que 48 Cap´ıtulo 5. Juegos de Localizaci´on los usuarios en Nest´an interesados no s´olo en encontrar una ubicaci´on ´optima de la instalaci´on, sino tambi´en en compartir los costes totales correspondientes. Por coste total entendemos la suma de los costes variables (dependiendo de los usuarios y de la ubicaci´on de la instalaci´on, en su mayor parte ser´an costes de transporte), m´as los costes fijos (independiente de lo anterior, principalmente los costes de la instalaci´on). Formalmente, una situaci´on de localizaci´on continua de una sola instalaci´on es una 4-tupla (N, Φ, d, K) donde (N, Φ, d) es un problema de localizaci´on continuo con ´unica instalaci´on y K∈R, K ≥0, es el coste fijo de instalaci´on de la instalaci´on. Tengamos en cuenta que podemos asociar (N, Φ, d, K) con un juego (N, c) cuya funci´on caracter´ıstica cse define, para cada S⊂N={a1, . . . , an}, por: c(S) =    K+L(S) si S6=∅ 0 si S=∅. Denotaremos por L(N) a la clase de juegos de localizaci´on con el conjunto de jugadores N(identificaremos cada jugador con su posici´on en el plano). Como de costumbre, tambi´en identificaremos el juego (N, c) con la funci´on caracter´ıstica c. El objetivo de los jugadores, de un problema de localizaci´on, es encontrar una ubicaci´on para la instalaci´on que minimice el coste total y asignar el coste total m´ınimo correspondiente. Veamos un par de situaciones de localizaci´on: Ejemplo 5.1. Supongamos que los alcaldes de nciudades cercanas (ciudad i localizada en el punto ai∈R2), desean hacer un acuerdo para construir un aeropuerto conjuntamente. El coste de construcci´on del aeropuerto es, aproximadamente, Ke. El acuerdo incluye el compromiso de invertir en cada ciudad una cantidad de euros igual a Aveces su distancia al cuadrado al aeropuerto (con Aun n´umero real positivo) para crear buenas carreteras e infraestructura ferroviaria comunicando las ciudades y el aeropuerto. Los ayuntamientos quieren encontrar una ubicaci´on ´optima para el aeropuerto (minimizar el coste total) y compartir los costes totales correspondientes. Observemos que se trata de una situaci´on de localizaci´on (N, Φ, d, K) con Φ(dS(x)) = APai∈Skx−aik2 2 para todo x∈R2, y toda S⊂N. Observemos que Φ(x) = APn i=1 xi,∀x∈ 49 Cap´ıtulo 5. Juegos de Localizaci´on Rn, f(y) = y2,∀y∈R, y d=kk2la norma eucl´ıdea. (Aqu´ı hemos tomado kk2, pero otras normas podr´ıan ser m´as naturales en otras circunstancias). Ejemplo 5.2. Supongamos que los ayuntamientos de nciudades cercanas (ciudad ilocalizada en el punto ai∈R2), desean hacer un acuerdo para crear una televisi´on local. Esto tiene un coste fijo de Keuros (construcci´on del edificio de oficinas y el estudio) y un coste variable. Se ha estimado que el coste variable (el coste del propio canal) es Aveces el cuadrado del radio de cobertura del canal de televisi´on (el radio de cobertura de un canal es la distancia m´axima a la ubicaci´on del canal desde la cual la se˜nal de televisi´on puede ser recibida correctamente, Aes un n´umero real positivo). Los ayuntamientos quieren encontrar una ubicaci´on ´optima para la estaci´on de televisi´on (de tal manera que todas las ciudades reciban correctamente la se˜nal y a un coste m´ınimo) y compartir los costes totales correspondientes. Observemos que esto es una situaci´on de localizaci´on (N, Φ, d, K) con Φ(dS(x)) = Am´axai∈Skx−aik2 2,∀x∈Rn, f(y) = y2,∀y∈R,yd=kk2la norma eucl´ıdea. (De nuevo hemos tomado kk2, pero otras normas podr´ıan ser m´as naturales en otras circunstancias). Un problema interesante que se plantea ahora es estudiar bajo que condiciones el core del juego de localizaci´on correspondiente es no vac´ıo. Porque los usuarios no s´olo quieren encontrar una ubicaci´on ´optima para la instalaci´on, sino tambi´en asignar los costes totales. Si esto no sucediera probablemente estos usuarios no podr´ıan llegar a un acuerdo y no construir´ıan la instalaci´on juntos. Daremos condiciones suficientes para que el core sea no vac´ıo. M´as tarde veremos algunas clases importantes de juegos de localizaci´on y veremos que condiciones son necesarias para usar la regla de asignaci´on igualitaria (que normalmente se usa en la pr´actica) que proporciona asignaciones. Veamos ahora algunas propiedades preliminares de los juegos de localizaci´on. Proposici´on 5.1. Tomemos c∈L(N)el juego de localizaci´on correspondiente a (N, Φ, d, K). Entonces ces mon´otono, es decir, c(s)≤c(T),∀S, T ⊂ Ncon S⊂T). Demostraci´on. Sean S⊆Tdos coaliciones. Por definici´on dS i(x)≤dT i(x) para todo iex. Entonces, dado que Φ es mon´otona, Φ(dS(x)) ≤Φ(dT(x)). Por lo tanto, se tiene el resultado.  50 Cap´ıtulo 5. Juegos de Localizaci´on Proposici´on 5.2. Tomemos c∈L(N)juego de localizaci´on correspondiente a(N, Φ, d, K). Si L(N)≤Kentonces ces subaditivio, es decir, c(s∪T)≤ c(S) + c(T)∀S, T ⊂Ncon S∩T=∅. Demostraci´on. Sean S, T dos coaliciones. Entonces, por la monoton´ıa de L(ver la prueba anterior) y las propiedades de Φ, L(S∪T)−(L(S)−L(T)) ≤L(S∪T)≤L(N). Ahora, dado que L(N)≤K, se tiene que L(S∪T)≤K+L(S) + L(T) y c(S∪T) = K+L(S∪T)≤K+L(S) + K+L(T) = c(S) + c(T). Obs´ervese que en el resultado anterior probamos que, si L(N)≤K, entonces c(S∪T)≤c(S) + c(T) para cualquier par de coaliciones SyTdisjuntas o no. El siguiente ejemplo muestra un juego de localizaci´on subaditivo con core vac´ıo. Esto motiva los resultados posteriores donde buscamos condiciones suficientes para que el core del juego de localizaci´on sea no vac´ıo. Ejemplo 5.3. Sea N={a1, a2, a3}el conjunto de los jugadores, localizados en los vertices de un tri´angulo equil´atero de lado l. Consideremos que la funci´on de globalizaci´on es la suma y que des la distancia eucl´ıdea elevada a la potencia b, (b≥2). Entonces, Φ(dS(x)) X ai∈Skx−aikb 2, para cada S⊂Ny cada x∈Rm. Es f´acil comprobar que el juego de localizaci´on asociado con (N, Φ, d, K) esta dado por: c(a1) = c(a2) = c(a3) = K, c(a1a2) = c(a1a3) = c(a2a3) = K+ 2(l/2)b, c(a1a2a3) = K+ 3√3 3lb. Se puede comprobar que el juego es subaditivo si y s´olo si K≥(lb/√3b−2)− (lb/2b−1). Sin embargo, tomando por ejemplo K= (lb/√3b−2)−(lb/2b−1), se puede ver que el juego de localizaci´on resultante tiene core vac´ıo. Es decir, dado que todos sus actores son sim´etricos, una condici´on necesaria y suficiente para 51 Cap´ıtulo 5. Juegos de Localizaci´on tener core no vac´ıo es que la asignaci´on igualitaria (c(N)/3, c(N)/3, c(N)/3) pertenezca al core. Se puede comprobar que no es el caso cuando b > 2. Los siguientes resultados tienen la motivaci´on de proporcionar una condici´on suficiente para que el core del juego de localizaci´on sea no vac´ıo. En la Observaci´on 2.1 describimos el core de un juego de localizaci´on (N, c), lo recordamos: Core(v) = C(v) = {x∈RN +:x(N) = v(N); x(S)≤v(S),∀S⊆N}.(5.1) Utilizando el Lema 2.2 vamos a probar el teorema m´as importante de esta secci´on. Teorema 5.1. Sea (N, Φ, d, K)una situaci´on de localizaci´on y sea (N, c)el correspondiente juego de localizaci´on. Denotamos l2= m´ınS⊂N:|S|=2 L(S). (a)Supongamos que 2≤n≤2 + l2 K. Si K(n−1) ≥L(N), entonces ctiene core no vac´ıo. (b)Supongamos que 2 + l2 K≤n. Si K≥(n−1)L(N)−nl2, entonces ctiene core no vac´ıo. Demostraci´on. En un juego de localizaci´on tenemos para cualquier colecci´on equilibrada B con coeficientes de equilibrio {ys:S∈B}: X S∈B ySc(S) = KX S∈B yS+X S∈B ySL(S). Teniendo en cuenta la monoton´ıa de Ly el hecho de que L(S) = 0 para cualquier coalici´on de tama˜no uno, tenemos que X S∈B ySc(S) = KX S∈B yS+X S∈B:|S|≥2 ySL(S) ≥KX S∈B yS+X S∈B:|S|≥2 ySl2. Para cualquier colecci´on equilibrada m´ınima Bdenotamos: m(B) = KX S∈B yS+l2X S∈B:|S|≥2 yS. 52 Cap´ıtulo 5. Juegos de Localizaci´on (Observamos que, si Bes m´ınima, los coeficientes de equilibrio est´an determinados de forma ´unica). Entonces, una condici´on suficiente para que el core sea no vac´ıo es: m´ın {B:Bno trivial y m´ınima equilibrada}m(B)≥c(N).(5.2) Supongamos que este m´ınimo se alcanza en ˆ B. Si {ai} 6∈ ˆ Bpara cada ai∈N, entonces ˆ B={−i:ai∈N}(ver lema anterior) y m(ˆ B)=(K+l2)n n−1. Si ˆ B={{ai}:ai∈N}, entonces m(ˆ B) = Kn. En otro caso ˆ Bsolo puede ser una familia {{ai}, N \ai}(para un ai∈A) y, entonces, m(ˆ B)=2K+l2. Ahora, dado que m(ˆ B) = m´ın{(K+l2n n−1, Kn, 2K+l2}, es f´acil comprobar que: m(ˆ B) =    Kn, si 2 ≤n≤2 + l2 K, (K+l2)n n−1,si l2 K< n. Esto junto con (5.2) completa la prueba.  Los siguientes ejemplos demuestran que los l´ımites en el teorema son ajustados, en el sentido de que no se puede mejorar para todo n. En particular, estos ejemplos muestran que se consiguen para n= 2 y n= 3. Ejemplo 5.4. Sea N={a1, a2}un conjunto de jugadores, localizados en los extremos de un segmento de longitud 2. Considere que la funci´on de globalizaci´on es la suma y que des la distancia euclidiana cuadrada. Es f´acil comprobar que, el juego de localizaci´on (N, c) asociado a (N, Φ, d, K) esta dado por: c(a1) = c(a2) = K, c(a1, a2) = K+ 2. Claramente, este juego tiene core no vac´ıo si y s´olo si K≥2. Observemos que, en este caso, bajo la condici´on (a) del teorema anterior y K(n−1) ≥L(N) es equivalente a K≥2, entonces la cota es ajustada para este juego. Ejemplo 5.5. Tomemos la misma situaci´on de localizaci´on y el mismo juego de localizaci´on del Ejemplo 5.3 con b= 2. Por lo tanto, N={a1, a2, a3}y la funci´on caracter´ıstica del juego es: c(a1) = c(a2) = c(a3) = K, c(a1a2) = c(a1a3) = c(a2a3) = K+l2/2, c(a1a2a3) = K+l2. Ya que los jugadores son sim´etricos en c,core(c)6=∅si y s´olo si la asignaci´on 53 Cap´ıtulo 5. Juegos de Localizaci´on igualitaria c(N) 3,c(N) 3,c(N) 3pertenece a core(c). Es f´acil comprobar que esta asignaci´on pertenece core(c) si y s´olo si K≥l2 2. Observemos que, en este caso, si K > l2 2estamos bajo la condici´on (b); si K≤l2 2estamos bajo la condici´on (a). En ambos casos, la cota dada por el Teorema es K≥l2 2. Entonces, de nuevo la cota es ajustada para este ejemplo. Con el teorema anterior tenemos una condici´on suficiente para que el core de cualquier juego de localizaci´on sea no vac´ıo. Esta condici´on es buena porque: a) no puede mejorarse en general, y b) puede ser comprobada de una manera razonablemente f´acil (s´olo hay que calcular l2yL(N)). Otra condici´on suficiente m´as sencilla que la del Teorema 5.1 es la siguiente. Proposici´on 5.3. Sea (N, Φ, d, K)una situaci´on de localizaci´on y sea (N, c) su correspondiente juego de localizaci´on. Si K≥(n−1)L(N), entonces ctiene core no vac´ıo. Demostraci´on. Comprobemos que la asignaci´on igualitaria K+L(N) n,...,K+L(N) n pertenece a core(c). Espec´ıficamente, para cada S⊂Ncon |S| ≤ n−1, |S|K+L(N) n≤(n−1)K+L(N) n≤K≤c(S). De donde se deduce lo que quer´ıamos probar.  Obs´ervese que, aunque la condici´on en la Proposici´on 5.3 es m´as simple que la condici´on en el Teorema 5.1, tambi´en es m´as d´ebil. S´olo en el caso de que l2 sea muy peque˜na (es decir, en caso de que haya dos usuarios situados en dos puntos muy cercanos), la condici´on en el Teorema 5.1 tiende a ser la misma que la de la Proposici´on 5.3. Pero, en tal caso, tal vez ser´ıa m´as conveniente considerar a estos dos jugadores cercanos como un solo jugador. 5.2. Juego de localizaci´on minimax Consideremos ahora la clase de Juegos de Localizaci´on Minimax en Rm. Para empezar observemos que en esta clase, des la distancia eucl´ıdea y la funci´on de 54 Cap´ıtulo 5. Juegos de Localizaci´on globalizaci´on es m´ın m´ax, adem´as: cM(S) = m´ın x∈Rmm´ax a∈Skx−ak2 2+K. (5.3) Luego: l2= m´ın a,b∈N,a6=bka−bk2 2 4. Por lo tanto, l2se puede calcular de una manera razonablemente f´acil y las condiciones del Teorema 5.1 se pueden comprobar f´acilmente. Ahora denotemos lk=minS⊂N:|S|=kL(S), para k∈ {2, . . . , n}.En teor´ıa de localizaci´on, es una caracter´ıstica bien conocida que, para cada S⊂Ncon |S| ≥ m+1, L(S) es igual a L(S) para un S⊂Scon |S|=m+1 (ya que, en un problema de localizaci´on minimax con un conjunto de puntos S, la soluci´on es el centro de la esfera m´as peque˜na que contemga S, y esta esfera esta completamente determinada por a lo m´as m+ 1 puntos de S, s´olo tres puntos para un c´ırculo en R2). Por lo tanto, puesto que Les mon´otona, lk=lk+1,∀k≥m+ 1. A continuaci´on vamos a dar una condici´on suficiente y f´acil de probar para que la soluci´on proporcionalmente igualitaria pertenezca al core en un juego de localizaci´on minimax. Primero vamos a decir lo que entendemos por soluci´on proporcionalmente igualitaria en este contexto. Como diremos en los juegos de localizaci´on de Weber, supongamos que aqu´ı hay un vector de coeficientes de proporcionalidad real positivo (α1, . . . , αn).Supongamos, sin p´erdida de generalidad, que α1≤α2≤ ··· ≤ αn. Denotemos α=Pai∈Nαi. Observemos que, en los juegos de localizaci´on minimax, un usuario en particular no produce costes de transporte una vez que se decide la ubicaci´on de la instalaci´on, en el sentido de que los costes de transporte ser´ıan iguales si se abandonar´a el juego. (Pensemos en el Ejemplo 5.2: la ubicaci´on y el radio de cobertura del canal se ha decidido, un usuario particular no produce costes de transporte. Este no es el caso del juego de localizaci´on de Weber, como en el Ejemplo 5.1. Por lo tanto, la forma correcta de definir aqu´ı la soluci´on proporcionalmente igualitaria E es la siguiente. Si (N, cM) es el juego de localizaci´on minimax asociado con la situaci´on de localizaci´on minimax (N, Φ, d, K), entonces Ei(cM)=(K+L(N))αi/α, ∀ai∈N. El siguiente teorema establece una condici´on suficiente para que Eproporcione asignaciones al core. 55 Cap´ıtulo 5. Juegos de Localizaci´on Teorema 5.2. Sea (N, cM)el correspondiente juego de localizaci´on minimax a la situaci´on de localizaci´on minimax (N, Φ, d, K). Entonces, E(cM)pertenece al core(cM)si L(N)Pn j=n−k+1 αj α−r(k)≤K 1−Pn j=n−k+1 αj α!,(5.4) para cada k∈ {1, . . . , n}, donde r(1) = 0, r(k) = lkpara cada 2≤k≤m+ 1 y r(k) = lm+1,∀k≥m+ 1. Demostraci´on. E(cM)∈core(cM) si y s´olo si, para todo S⊂N, X ai∈S (K+L(N))αi α≤K+L(S).(5.5) Teniendo en cuenta α1≤α2≤ ··· ≤ αny que lk=lm+1 para todo k≥m+ 1, es claro que, para cada k∈ {1, . . . , n}(5.4) implica (5.5) para cada S⊂Ncon |S|=k. Podemos interpretar la condici´on (5.4) de la siguiente manera. La mitad izquierda de la desigualdad es la parte del coste de cobertura que los jugadores en {a1, . . . , ak}ahorran, menos el coste de cobertura m´as peque˜no que debe ser pagado por una coalici´on de kjugadores si s´olo ellos cooperan. El lado derecho es la parte del coste fijo pagado por los jugadores en {a1, . . . , an}. Por lo tanto, E(cM) pertenece a core(cM) si y s´olo si los jugadores con coeficientes de proporcionalidad peque˜no pagan una parte suficientemente grande del coste de cobertura. Una vez m´as, la condici´on (5.4) se cumple, para cada problema de localizaci´on minimax y cada vector de proporcionalidad α, si Kes suficientemente grande. Obs´ervese que se podr´ıa encontrar f´acilmente una condici´on suficiente m´as d´ebil. Sin embargo, la del Teorema 3.8. anterior es especialmente f´acil de comprobar. S´olo hay que considerar n desigualdades, y calcular l2, . . . , lm+1 que en el caso del plano (R2) se reduce a l2yl3. Anteriormente hemos visto un ejemplo de este juego en el Ejemplo 5.2. 56 Cap´ıtulo 5. Juegos de Localizaci´on 5.3. Juego de localizaci´on de Weber, con coste fijo Ahora consideremos el Juego de Localizaci´on de Weber, conste fijo no variable. En el problema de localizaci´on de Weber la funci´on de globalizaci´on es la suma. El juego de localizaci´on correspondientes viene dado por: cW(S) = m´ın x∈RnX a∈Skx−ak2 2+K, (5.6) para toda S⊂N. Siendo (N, Φ, d, K) situaci´on de localizaci´on, con ddistancia eucl´ıdea al cuadrado. Observemos que el Ejemplo 5.1 es una situaci´on de localizaci´on de Weber. Esta clase de problemas de localizaci´on es muy conocida. Es f´acil deducir que la soluci´on ´optima del problema (3) es: x∗(S) = 1 |S|X a∈S a. Obviamente, todos los resultados anteriores siguen siendo aplicables a estos juegos. En muchas situaciones pr´acticas, cuando varios usuarios deciden construir una instalaci´on conjuntamente, acuerdan usar alg´un tipo de soluci´on proporcionalmente igualitaria para la asignaci´on de los costes. Para las situaciones de localizaci´on de Weber, una regla proporcionalmente igualitaria consiste en lo siguiente: (a) La instalaci´on se construir´a en la ubicaci´on x∗(P), (b) Los coste fijos K se dividen proporcionalmente entre los usuarios, de acuerdo con un vector de coeficientes de proporcionalidad (α1, . . . , αn), (c) Cada usuario paga los costes de transporte que produce. Esto significa que, si (N, cW) es el juego de localizaci´on asociado con la situaci´on de localizaci´on de Weber (N, Φ, d, K), de acuerdo con esta regla (la 57 Cap´ıtulo 5. Juegos de Localizaci´on tenemos una l´ınea de ferrocarril y el problema es decidir d´onde construir una estaci´on de ferrocarril para mejorar el servicio a los habitantes de la regi´on. Para simplificar consideremos Ω = [0, L], (L > 0), y el conjunto de instalaciones N={a1, . . . , an}ubicadas en Ω con coordenadas xa1, . . . , xan. Supongamos tambi´en que el coste fijo definido en Ω es: K(x) =    k1x≤¯x, k2en otro caso, (5.14) con 0 < k1< k2y la soluci´on correspondiente al problema de Weber es x∗(N) = ¯x. Centremos el an´alisis en dos instalaciones consecutivas ai, aj,(xai < xaj ). Como en la siguiente figura: Fig. 1: el problema de localizaci´on sobre una recta. ai¯xaj En este caso si k1+ (xaj −¯x)< k2, tenemos que c({ai}) = k1, c({aj}) = k1+ (xaj −¯x), c({ai, aj}) = k1+ (xaj −xai). Si el valor proporcional xP i= kx∗(N)−aik2+αik1pertenece al core, por la inecuaci´on (5.13) para S={ai} tenemos la cota αi≤1−kx∗(N)−aik2 k1y para S={aj}la inecuaci´on trivial αj≤ 1. Por otro lado, si el jugador aiy el jugador ajdeciden localizar su instalaci´on en x∗({ai, aj}) = ai, la inecuaci´on (5.12) dice αi+αj≤1−2kx∗(N)−aik2 k1, que no se satisface con αi>1−2kx∗(N)−aik2 k1.Si este es el caso, no tenemos el efecto de compensaci´on dado por la condici´on (5.11). Tengamos en cuenta que para el jugador aiy el jugador ajes indiferente ubicar x∗({ai, aj}) en cualquier punto del intervalo [xai,¯x]. Finalmente, observemos que en caso del coste fijo constante la condici´on (5.11) es similar a la condici´on (5.7), que hemos dado en el problema anterior. 64 Cap´ıtulo 6 Juegos de Radio y Di´ametro Durante este cap´ıtulo continuamos analizando los juegos de localizaci´on, aunque ahora nos centramos en un tipo espec´ıfico que se tratan de forma ligeramente distinta. Aqu´ı hemos usado la referencia [17]. De nuevo los jugadores son los clientes (puntos de demanda) en el problema de localizaci´on y el valor caracter´ıstico de una coalici´on es el coste de servir a sus miembros. Espec´ıficamente, el coste en estos juegos es el radio de servicio de la coalici´on. A estos juegos se les conoce como Juegos de Localizaci´on de Radio M´ınimo. Estudiaremos la existencia de puntos en el core y la existencia de representaciones polinomiales de los cores de estos juegos, centr´andonos en espacios de red, es decir, espacios m´etricos finitos inducidos por grafos no dirigidos y longitudes de aristas positivo y en los espacios m´etricos definidos sobre Rd. Adem´as, analizaremos la relaci´on entre los Juegos de Localizaci´on de Radio M´ınimo y los Juegos de Localizaci´on de Di´ametro M´ınimo. Por esto comenzamos el cap´ıtulo con unos conceptos introductorios sobre el radio y el di´ametro de un conjunto finito de un espacio m´etrico. Demostraremos un teorema que proporciona una situaci´on en el que el core de ambos juegos es igual y no vac´ıo. Durante el cap´ıtulo veremos distintos ejemplos de este tipo de juegos, en alguno de ellos comprobaremos distintas situaciones en las que el core puede ser vac´ıo o no vac´ıo. Sea Xun espacio m´etrico y sea N0={v0, v1, . . . , vk}un conjunto finito de puntos de X. El subconjunto N={v1, . . . , vk}se identifica con el conjunto 65 Cap´ıtulo 6. Juegos de Radio y Di´ametro de kjugadores, nos referimos a estos puntos como instalaciones existentes, o puntos de demanda. Tambi´en hay un punto v0, que representa la ubicaci´on de un servidor que proporciona servicios a los jugadores, que puede ser visto como un elemento especial en el sistema, por ejemplo, cada punto de demanda debe tener acceso a v0. Observemos que v0no es un jugador. Por ejemplo, supongamos que los puntos de demanda representan a los pacientes y v0es la ubicaci´on de un m´edico que presta servicios sanitarios. Este estudio est´a motivado por modelos de localizaci´on, donde el tiempo transcurrido hasta que se proporciona el servicio (tiempo de respuesta) es cr´ıtico. Continuando con el ejemplo anterior, el servicio m´edico no se proporciona en su origen. Por otra parte, la coalici´on de pacientes Spuede seleccionar de forma ´optima la ubicaci´on del centro (por ejemplo, cl´ınica u hospital), donde se proporcionar´a el servicio. Cuando hay una llamada de servicio, tanto el paciente como el m´edico viajar´an a la cl´ınica. El coste del servicio se supone como el radio de servicio, definido como la distancia m´axima recorrida por un paciente o el m´edico al centro de servicio (centro). Utilizando la terminolog´ıa de la teor´ıa de localizaci´on, el coste de una coalici´on Ses el valor de soluci´on del problema 1-centro para el conjunto S∪{v0}. Definamos algunos conceptos necesarios: Definici´on 6.1. Dado un subconjunto finito de puntos Y⊆X, su di´ametro D(Y) se define como: D(Y) = m´ax y1,y2∈Yd(y1, y2). Un par de puntos y1, y2∈Y, que verifiquen: D(Y) = d(y1, y2) se denominan diametrales. Definici´on 6.2. Dado un subconjunto finito de puntos Y⊆X, se define el radio de Ycomo: R(Y) = ´ınf x∈Xm´ax y∈Yd(x, y). Un punto x∈Xsatisfaciendo R(Y) = m´axy∈Yd(x, y) se llama 1-centro de Y. Observemos que por la desigualdad triangular: R(Y)≤D(Y)≤2R(Y).(6.1) 66 Cap´ıtulo 6. Juegos de Radio y Di´ametro Observemos que el core de (N, v), en el caso de un juego de coste, como ya hemos visto en secciones anteriores, es el conjunto: C(N, v) = {x∈Rk:x(N) = v(N), x(S)≤v(S),∀S⊆N}.(6.2) El Juego de Localizaci´on de Di´ametro M´ınimo (MDLG), (N, vI), respecto al espacio m´etrico Xy el conjunto de puntos N0, tiene como funci´on caracter´ıstica: vI(S) = D(S∪{v0}). Ahora definimos formalmente la clase de juegos de costes cooperativos basados en los problemas de localizaci´on de instalaciones anteriores que estudiamos a continuaci´on: el Juego de Localizaci´on de Radios M´ınimo (MRLG). Su funci´on caracter´ıstica se define como: vII(S) = 2R(S∪{v0}). Consideremos el espacio m´etrico de red inducido por un grafo conectado no dirigido. Supongamos G= (V, E) un grafo conectado no dirigido con longitudes de aristas positivas {le}, e ∈E, donde V={v0, v1, . . . , vn}.Donde e= (vi, vj), usaremos la notaci´on l(vi, vj) = le. Suponemos que cada arista en Ees rectificable. Nos referimos a los puntos interiores de una arista por su distancia (a lo largo de la arista) de los dos nodos de la arista. A(G) es el conjunto continuo de puntos en las aristas de G. Para cualquier par de puntos x, y ∈A(G), denotaremos por d(x, y) el camino m´as corto en A(G) conectando xey. Nos referimos aA(G) como el espacio m´etrico inducido por Gy las distancias m´ınimas. Por definici´on la funci´on caracter´ıstica vII es mon´otona. Sin embargo, cuando el espacio m´etrico X es discreto, es decir, |X|es finito, el juego de localizaci´on de radios, (N, vII) no tiene porque verificar la propiedad de superaditividad. Como resultado los jugadores pueden no tener ning´un incentivo para cooperar y el core puede estar vac´ıo, como se ve en el siguiente ejemplo: Ejemplo 6.1. Consideremos una ruta con 5 nodos con el siguiente conjunto de aristas: E={(v1, v2),(v2, v0),(v0, v3),(v3, v4)}. Las respectivas longitudes son 67 Cap´ıtulo 6. Juegos de Radio y Di´ametro 1,1,2 y 2. El espacio finito (discreto) X esta compuesto de 5 nodos (puntos) con funci´on de distancia inducida por la longitud de las aristas. Tambi´en podemos ver Xcomo un conjunto de 5 puntos en la l´ınea real. Consideremos primero el juego de 2 jugadores sobre Xdefinido por N={v1, v4}. No es subaditivo ya que: vII({v1, v4})> vII ({v1})+vII({v4}).Se tiene tambi´en que para el juego discreto completo sobre el conjunto Xy el conjunto N=X\ {v0}={v1, v2, v3, v4} tampoco verifica la subaditividad pues: vII ({v1, v2, v3, v4})=8, vII ({v1, v2}) = 2, vII({v3, v4}) = 4, luego: vII({v1, v2, v3, v4})> vII ({v1, v2}) + vII ({v3, v4}) Ejemplo 6.2. Veamos ahora un ejemplo que verifica subaditividad pero tiene core vac´ıo. Consideremos el espacio m´etrico discreto definido por X={v0, v1, v2, v3}, d(v0, v1) = d(v2, v3) = 2 y d(v0, v2) = d(v0, v3) = d(v1, v2) = d(v1, v3) = 1. Sea N={v1, v2, v3}, y consideremos el juego radial (discreto) (N, vII) Tenemos vII(N) = 4 y vII (S) = 2 para cualquier coalici´on S, con |S| ≤ 2. Es f´acil comprobar que no hay un vector xque verifique x1+x2+x3= 4 x1+x2≤2 x2+x3≤2 x1+x3≤2 Luego este juego tiene core vac´ıo. Cuando el espacio m´etrico Xconsiste en un conjunto continuo de puntos, C(N, vII) tambi´en puede ser vac´ıo para un juego de 3 jugadores, como se ilustra en el siguiente ejemplo de un espacio m´etrico de red A(G). Este ejemplo corresponde a una red de carretera plana geom´etrica muy simple, donde las aristas son segmentos de l´ınea y sus longitudes son las distancias euclidianas respectivas. Ejemplo 6.3. Consideremos el grafo G= (V, E) donde V={v0, v1, . . . , v6}y E={(v0, v4),(v0, v5),(v0, v6),(v1, v4),(v1, v6),(v2, v4),(v2, v5),(v3, v5),(v3, v6)}. Todas las aristas de longitud 1. Como en la siguiente figura: 68 Cap´ıtulo 6. Juegos de Radio y Di´ametro v6 v1 v3 v0 v4 v5 v2 Sea X=A(G). Consideremos el juego (N, vII ), definido sobre X, con N0= {v0, v1, v2, v3}yN={v1, v2, v3}. Es f´acil comprobar que para cada coalici´on S⊆Ncon |S| ≤ 2 tenemos vII (S) = 2, y vII (N) = 4. Por simetr´ıa, si el core es no vac´ıo la asignaci´on sim´etrica x= (4/3,4/3,4/3) estar´ıa en el core contradiciendo la restricci´on x1+x2≤vII({v1, v2}) = 2. Para cualquier espacio m´etrico X, la definici´on de vII asegura la monoton´ıa del juego (N, vII ), mientras que la subaditividad se demuestra en la proposici´on siguiente, antes veamos una definici´on necesaria para poder asegurarla: Definici´on 6.3. Sea Xun espacio m´etrico tal que para cada par de puntos x, y ∈X, y un real 0 ≤α≤1, hay un punto z∈Xtal que d(x, z) + d(z, y) = d(x, y) y d(x, z) = αd(x, y).Entonces Xse llama espacio m´etrico geod´esico (ver [15]). Proposici´on 6.1. Si Xes un espacio m´etrico geod´esico, entonces el juego de radio (N, vII )sobre Xes subaditivo. Demostraci´on. Consideremos un par de coaliciones S1yS2. Tenemos que probar que vII(S1∪S2)≤vII (S1) + vII (S2). Para j= 1,2, sean cjyrjel centro y el radio de la bola m´as peque˜na que encierra los puntos Sj∪{v0}, respectivamente. Sea P(c1, c2) el camino mas corto en X, conectando c1yc2. Denotemos d(c1, c2) como la distancia de P(c1, c2). Entonces, d(c1, c2)≤d(c1, v0)+d(v0, c2)≤ r1+r2. Supongamos sin p´erdida de generalidad que r2≥r1. Si r2≥r1+d(c1, c2), 69 Cap´ıtulo 6. Juegos de Radio y Di´ametro entonces un centro establecido en c2garantizar´a un radio de cobertura r2para todos los nodos en S1∪S2∪{v0}. Por lo tanto, vII(S1∪S2)≤r2=vII (S2). Si r1≤r2≤r1+d(c1, c2), entonces consideremos un centro establecido en el punto c∗, tal que d(c1, c∗)=(d(c1, c2)+r2−r1)/2, y d(c2, c∗)=(d(c1, c2)−r2+ r1)/2. Es f´acil comprobar que este centro garantizar´a un radio de cobertura de d(c1, c2)+r1+r2)/2≤r1+r2para todos los nodos de S1∪S2∪{v0}. (Observemos que v0est´a en la intersecci´on de las bolas m´as peque˜nas que encierran S1∪{v0} yS2∪{v0}). Por lo tanto, vII(S1∪S2)≤vII (S1) + vII (S2). 6.1. Espacios m´etricos de red Ahora vamos a considerar espacios m´etricos espec´ıficos que se estudian con frecuencia en el an´alisis de localizaci´on y muestran que en estos casos el core puede ser representado por un n´umero polin´omico de desigualdades lineales. En general, necesitaremos un n´umero exponencial de desigualdades lineales para representar el core de un juego, (6.2). En primer lugar, vamos a considerar el caso donde X=A(G), es espacio m´etrico inducido por un grafo conectado no dirigido G= (V, E), V = {v0, v1, . . . , vn}, y sus longitudes de arista positivas. Supongamos que el conjunto de jugadores Nsatisface que N⊆V\ {v0}. Adem´as, consideremos sin p´erdida de generalidad que N={v1, v2, . . . , vk}, donde k=|N|. Proposici´on 6.2. Consideremos el juego de radio (N, vII ), definido sobre un espacio m´etrico de red A(G), inducido por el grafo G= (V, E)con longitud de arista positiva. Entonces, hay una colecci´on de subconjuntos de N, Si,j p,q,(vi, vj)∈ E, vp, vq∈N∪{v0},(i, j, p, q)∈I, tal que |I|=O(m|N|2)y C(N, vII) = nx∈RN +:x(N) = vII (N), x(Si,j p,q ≤vII(Si,j p,q),∀(i, j, p, q)∈Io. Como resultado, la pertenencia al core, adem´as de ver que el core es no vac´ıo, puede ser comprobada en tiempo fuertemente polinomial. Demostraci´on. Primero observemos que, si N={v1, . . . , vn}, vII (N) es igual al di´ametro de un ´arbol de expansi´on de di´ametro m´ınimo de V. Este ´arbol de expansi´on, digamos T∗, resuelve el problema continuo (o absoluto) de 1-centro 70 Cap´ıtulo 6. Juegos de Radio y Di´ametro sobre G, y puede encontrarse en tiempo O(mn +n2logn), (ver [8]). M´as generalmente, cuando N⊆V\{v0}, vII(S) se define como la longitud del di´ametro de un ´arbol spanning de di´ametro m´ınimo de S∪{v0},∀S⊆N. Tal ´arbol, digamos T∗(S), resuelve el problema de un centro continuo para el subconjunto de los nodos S∪{v0}, y se puede encontrar en tiempo O(mn +n2logn). Recordemos que el problema continuo de 1-centro para algunos subconjuntos V0⊆V, define la vecindad de radio m´as peque˜na es el espacio m´etrico A(G), que recubre V0. Adem´as, T∗(S) tiene la siguiente propiedad. Hay una arista de G, digamos (vi, vj), tal que el 1-centro de T∗(S) est´a sobre esta arista, de nuevo ver [8], y vII(S) = d(vp, vi) + l(vi, vj) + d(vj, vq), para algunos nodos vp, vq∈S∪{v0}. En total hay a lo m´as O(|N|2) centros de ´arboles de di´ametro m´ınimo sobre la arista (vi, vj). Cada uno de estos centros Ci,j p,q est´a asociado con un radio de la forma: ri,j p,q = (d(vp, vi) + l(vi, vj) + d(vj, vq))/2. Despu´es, para cada centro ci,j p,q tal que d(v0, ci,j p,q)≤ri,j p,q, definamos la coalici´on m´axima: Si,j p,q ={u∈N:d(u, ci,j p,q)≤ri,j p,q}. Sea I={(i, j, p, q):(vi, vj)∈E, vp, vq∈N∪{v0}, d(vo, ci,j p,q)≤ri,j p,q} Ahora consideremos la coalici´on S⊆N. Entonces, a partir de lo anterior se deduce que hay un cierto centro ci,j p,q y radio ri,j p,q, tal que vII (S) = 2ri,j p,q, yS⊆Si,j p,q. Por lo tanto, la monoton´ıa del juego implica que la restricci´on del core x(S)≤vII(S) que se deduce por la restricci´on xSi,j p,q≤vII Si,j p,q. Esto valida la representaci´on eficiente del n´ucleo indicada en la proposici´on. Finalmente, observemos que utilizando los algoritmos anteriores para resolver problemas de un centro, se necesita tiempo polinomial para construir toda la colecci´on nSi,j p,qo,(vi, vj)∈E, vp, vq∈N∪{v0},(i, j, p, q)∈I. En particular, la 71 Cap´ıtulo 6. Juegos de Radio y Di´ametro propiedad de pertenencia al core, como ser no vac´ıo puede ser comprobada en tiempo fuertemente polinomial por el algoritmo que encontramos en [22]. Esto completa la prueba.  Observaci´on 6.1. Relativo al MRLG definido sobre un espacio m´etrico de red podemos suponer sin p´erdida de generalidad que el grafo subyacente G= (V, E) es un grafo completo, y sus longitudes de aristas satisfacen la desigualdad triangular. En otro caso, siempre podremos introducir una arista entre cualquier par de nodos y establecer su longitud igual a la distancia en A(G) entre el par. Consideremos una coalici´on S. Observemos que en este caso cada ruta simple de T∗(S) tiene a lo m´as 3 aristas. Sin embargo, incluso en este caso T∗(S) no es necesariamente un sub´arbol de Gv0(S), el subgrafo de Ginducido por el conjunto de nodos S∪{v0}. Como ejemplo consideremos el grafo completo con conjunto de nodos V={v0, v1, v2, v3}.Con longitudes de las aristas (v3, v0),(v3, v1),(v3, v2) igual a 1, y la longitud del resto igual a 2. Cuando S={v1, v2}, T∗(S) es la estrella centrada en v3, que no est´a en Gv0(S). Corolario 6.1. Si Ges un ´arbol, hay una colecci´on de subconjuntos de N, {Sp,q}, vp, vq∈N∪{v0}, p, q ∈I0, tal que |I0|=O(|N|2), y el core del juego (N, vII ) esta defino por: C(N, vII) = {x∈Rn +:x(N) = vII (N).x(Sp,q)≤vII(Sp,q),∀p, q ∈I0} Demostraci´on. Si Ges un ´arbol, el n´umero total de centros de los sub´arboles de exppansi´on de di´ametro m´ınimo es solo O(|N|2). En este caso, cada par de nodos, vp, vqaporta un centro candidato, denotado por cp,q, el punto medio de la ruta simple ´unica que conecta vpcon vq. Si d(v0, cp,q)≤d(vp, vq)/2, la coalici´on m´aximal respectiva se define entonces por Sp,q ={u∈N:d(u, cp,q)≤d(vp, vq)/2} Sea I0={(p, q) : d(v0, cp,q)≤d(vp, vq)/2}.Entonces el resultado general en la proposici´on anterior conduce a la descripici´on m´as sencilla de C(N, vII ) dada en el corolario.  Observaci´on 6.2. Dado un grafo conectado no dirigido G= (V, E), con 72 Cap´ıtulo 6. Juegos de Radio y Di´ametro V={v0, v1, . . . , vn}, observamos que el espacio m´etrico respectivo X=A(G), inducido por Gy sus longitudes de aristas positivos, es geod´esico. El Ejemplo 6.3 ilustra que cuando el conjunto de jugadores Nes el subconjunto propio V\{v0}, el core del juego de locaci´on radial puede ser vac´ıo. Sin embargo, todav´ıa no sabemos si el core del juego (N, vII ) definido sobre el espacio X=A(G) es siempre no vac´ıo en el caso donde G= (V, E) es un grafo no dirigido conectado general y N={v1, . . . , vn}. Nos referimos a este caso como el juego de localizaci´on completo de radio m´ınimo (CMRLG) sobre redes. Ahora nos centramos en algunas observaciones y casos especiales del juego de radio completo, CMRLG. Primero observamos que la funci´on vII no puede ser submodular si la gr´afica Gcontiene un ciclo. Ejemplo 6.4. Consideremos el 4-ciclo con longitud de arista 1, y V={v0, v1, v2, v3}. Como en la figura: v1 v0 v3 v2 1 1 1 1 Sea S1={v1, v2}yS2={v3, v2}. Entonces, vII (S1) = vII(S2)=2, vII (S1∪ S2)=3, vII(S1∩S2) = 2, y por lo tanto vII(S1∪S2) +vII (S1∩S2)> vII(S1) + vII(S2). Hemos observado en la introducci´on que hay una asignaci´on del core para el juego de di´ametro (N, vI) que divide vI(N) entre un par de jugadores que corresponden al di´ametro de V. Por el contrario, el n´ucleo del juego completo de localizaci´on de radio (N, vII ) no puede contener en general una asignaci´on en la que s´olo 2 jugadores paguen un coste positivo. Por ejemplo, en el Ejemplo 6.4, d(v0, v2) = 2, y d(v0, v1) = d(v0, v3) = 1. Sin embargo, la asignaci´on del core ´unica es el vector (1,1,1). 73 Cap´ıtulo 6. Juegos de Radio y Di´ametro Como antes, observamos que para cada subconjunto S⊆N, hay un subconjunto Sj, j ∈Jyk= 1, . . . , c1 j(n, d), tal que la restricci´on x(S)≤vII (S), es dominada por la restricci´on xS1 j(k)≤vII(Sj). Esto completa la prueba.  Con la excepci´on del caso p=∞, todav´ıa no se conoce si C(N, vII ) es no vac´ıo para todo espacio m´etrico lpsobre Rd. Asumimos sin p´erdida de generalidad que vi6=v0,∀i= 1, . . . , n. Teorema 6.4. El core del juego (N, vII ), definido en el espacio m´etrico l∞ sobre Rd, es no vac´ıo. Espec´ıficamente, C(N, vI) = C(N, vII ). Adem´as, si D(N0) = d(v0, vj), para alg´un vj∈N, la dimensi´on de C(N, vII ) es n−1, y hay un x∗∈C(N, vII )tal que x∗ t>0, para cualquier vt∈N. Tambi´en, si D(N0) = d(vi, vj), para alg´un vi, vj∈Nyd(vi, vj)< d(vi, v0) + d(vj, v0), entonces la dimensi´on de C(N, vII )es n−1,y hay un x∗∈C(N, vII) tal que x∗ t>0, para cualquier vt∈N. Demostraci´on. Cuando p=∞, es f´acil ver que para cualquier conjunto Stenemos vI(S) = D(S∪{v0})=2R(S∪{v0}) = vII (S). Por lo tanto, C(N, vI) = C(N, vII), y la propiedad de core no vac´ıo se sigue de la Observaci´on 6.3. Supongamos sin p´erdida de generalidad que D(N0) = d(v0, v1). Sea α= (α1, α2, . . . , αn) un vector real arbitrario que verifica 0 ≤α0≤m´ınt=1,...,n d(v0, vt), α1=Pn j=2 αjyαj≥0, j = 2, . . . , n. Consideremos ahora una coalici´on S⊆N. Si v1∈S, entonces xα(S)≤α1≤m´ınt=1,...,n d(v0, vt)≤vII (S). Para ver que la dimensi´on af´ın de C(N, vII ) en este caso es n−1, vamos a probar que el core contiene nvectores independientes. Uno de ellos es el vector x1= (x1 1, . . . , x1 n), definido por x1 1=d(v0, v1) y x1 j= 0,para j= 2,3, . . . , n. Los otros n−1 vectores se definen como sigue: Sea εun real positivo suficientemente peque˜no, y consideremos las n−1 asignaciones independientes del core {xα(q)}, q = 2, . . . , n, donde α(q) es el vector definido por α1(q) = ε, αq(q) = εyαt(q) = 0, para cualquier t= 2, . . . , n;t6=q. La asignaci´on x∗=Pn q=2 xα(q)/(n−1) esta en el core y tiene componentes estrictamente positivas. Ahora, supongamos sin p´erdida de generalidad que D(N0) = d(v1, v2) y d(v1, v2)< d(v0, v1) + d(v0, v2). Sean δ1, δ2reales positivos que verifican 0 < δ1< d(v0, v1),0< δ2< d(v0, v2), y δ1+δ2=d(v1, v0) + d(v2, v0)−d(v1, v2). 80 Cap´ıtulo 6. Juegos de Radio y Di´ametro Sea α= (α1, α2, . . . , αn) un vector real arbitrario verifcando α1≤d(v1, v0)− δ1, α2≤d(v2, v0)−δ2,0≤α1+α2≤m´ınt=1,...,n d(v0,t),0≤α1+α2≤ m´ın δ1, δ2, α1+α2=Pn j=3 αjyαj≥0, j = 1, . . . , n. Demostraremos que la asignaci´on: xα= (d(v0, v1)−δ1−α1, d(v0, v2)−δ2−α2, α3, . . . , αn) esta en C(N, vII). Primero, por definici´on xα(N) = d(v1, v2) = D(N0) = vII(N). Ahora consideremos la coalici´on S⊆N. Si v1, v2∈S, entonces xα(S)≤ d(v1, v2) = vII(S). Si v1∈S, v26=S, entonces xα(S)≤d(v1, v0)−δ1, α1+ Pn q=3 αq≤d(v1, v0)−α2−α1+Pn q=3 αq≤d(v1, v0)≤vII(S). Similarmente, si v16=S, v2∈S, obtenemos xα(S)≤d(v2, v0)≤vII (S). Finalmente, supongamos que v1, v26=S. Entonces xα(S)≤α1+α2≤m´ınt=1,...,n d(v0, vt)≤vII (S). Para ver que la dimensi´on af´ın de C(N, vII ) en este caso es n−1, demostremos que el core contiene nvectores independientes. Dos de ellos son los vectores x1= (x1 1, . . . , x1 n) y x2= (x2 1, . . . , x2 n), definidos por x1 1=d(v1, v0), x1 2= d(v1, v2)−d(v1, v0), x1 j= 0 para j= 3,4, . . . , n, x2 1=d(v1, v2)−d(v2, v0), x2 2= d(v2, v0) y x2 j= 0 para j= 3,4, . . . , n. Los otros n−2 vectores se definen como sigue: Sea εun real positivo suficientemente peque˜no, y consideremos la colecci´on de n−2 asignaciones independientes del core {xα(q)}, q = 3, . . . , n, donde α(q) es un vector definido por α1(q) = ε, αq(q) = ε, y αt(q) = 0, para cualquier t= 2, . . . , n;t6=q. La asignaci´on x∗= (x1+x2+Pn q=3 xα(q))/n esta en el core y sus componentes son estrictamete positivas. Esto completa la prueba.  Aumentando el resultado del teorema anterior, el siguiente ejemplo ilustra que cuando no se satisfacen las condiciones del teorema, la dimensi´on del core puede incluso ser cero. Espec´ıficamente, para cualquier n´umero de jugadores, incluso en el caso plano l∞, el core puede ser un ´unico punto donde solo dos jugadores compartan el coste total, a pesar de que la distancia de cada jugador al servidor v0sea positiva. Ejemplo 6.10. Consideremos el conjunto de puntos N0={v0, v1, . . . , vk}donde v0= (0,0), v1= (0,1), v2= (0,−1), v3= (1,0) y vi= (ai,0),0< ai< 1,para i= 4,5, . . . , k. Dado que vI(S) = 2, si v1, v2⊆N, y vI(S)≤1, en otro 81 Cap´ıtulo 6. Juegos de Radio y Di´ametro caso, es f´acil probar que C(N, vI) = C(N, vII) = {(1,1,0,...,0)}. Corolario 6.2. El core del juego (N, vII )definido en el espacio m´etrico l1es no vac´ıo. Espec´ıficamente, C(N, vI) = C(N, vII ). Demostraci´on. Dado que la norma rectilineal l1, es equivalente a la norma l∞ sobre el plano, para cualquier subconjunto S, D(S∪{v0})=2R(S∪{v0}) para el caso del plano. Por lo tanto, el core del respectivo juego de radio m´ınimo en el plano es no vac´ıo.  6.3.1. Espacios eucl´ıdeos Volviendo al caso eucl´ıdeo, en general, la igualdad vI(N) = vII (N) no se verifica incluso en el caso plano. De la Proposici´on 6.1 se deduce que la funci´on caracter´ıstica vII(S) es subadditiva tambi´en para el modelo eucl´ıdeo. Sin embargo, no se sigue del an´alisis general en secciones anteriores que el n´ucleo del juego plano eucl´ıdeo sea no vac´ıo. A pesar de ello, vamos a probar que C(N, vII ) es no vac´ıo para el caso del plano eucl´ıdeo. M´as espec´ıficamente, hay una asignaci´on b´asica donde al menos 3 jugadores (puntos) pagan cantidades positivas. Estos son puntos que definen C(V), el c´ırculo m´ınimo en el plano que encierra el conjunto V. Teorema 6.5. El core C(N, vII )del juego de localizaci´on de radio m´ınimo (N, vII)en el caso del plano eucl´ıdeo es no vac´ıo. Demostraci´on. Ver ap´endice de [17]. Observaci´on 6.4. En el juego de localizaci´on de radio m´ınimo (N, vII), para cada coalici´on S, vII se define como el doble del valor de la soluci´on para el problema de un centro para el conjunto de nodos S∪{v0}. Del mismo modo, podemos considerar los juegos de localizaci´on definidos por otros criterios de optimizaci´on comunes que se usan con frecuencia en los modelos de localizaci´on de instalaciones. Por ejemplo, consideremos el juego de localizaci´on de mediana m´ınima, (N, vIII), donde para cada coalici´on S, vIII se define como el valor de la soluci´on al problema 1-mediana para conjunto de los nodos S∪{v0}. Observamos que desde del punto de vista cooperativo la definici´on anterior ni siquiera induce la propiedad deseable de la subaditividad. Por lo tanto, los 82 Cap´ıtulo 6. Juegos de Radio y Di´ametro jugadores pueden no tener incentivos para cooperar, como se muestra en el siguiente ejemplo. Ejemplo 6.11. Consideremos una ruta de 4 nodos con el siguiente conjunto de aristas: E={(v1, v0),(v0, v2),(v2, v3)}. Aristas de longitud 1. Es f´acil ver que vIII (N) = 4, vIII ({v1}) = 1 y vIII({v2, v3}) = 2. Por lo tanto, vIII ({v1}) + vIII ({v2, v3})=3<4 = vIII (N). El core es vac´ıo en este ejemplo, ya que el conjunto de restricciones, x1≤1, x2+x3≤2 y x1+x2+x3= 4 es inconsistente. 83 Cap´ıtulo 6. Juegos de Radio y Di´ametro 84 Cap´ıtulo 7 Conclusiones Para realizar este Trabajo Fin de Grado he necesitado los conocimientos adquiridos, principalmente, en dos asignaturas del Grado en Matem´aticas: Programaci´on Matem´atica y M´etodos de Investigaci´on Operativa. Donde conoc´ı como resolver un programa lineal de optimizaci´on y la utilidad del respectivo programa dual. Como conclusi´on general del Trabajo Fin de Grado, podemos decir que una forma efectiva de resolver problemas de asignaci´on de costes es usar la teor´ıa de juegos cooperativos. El Teorema de Bondareva-Shapley nos proporciona una condici´on necesaria y suficiente para que un juego cooperativo tenga core no vac´ıo. Podemos entender el core como soluci´on de un juego cooperativo, aunque en algunos casos el core es vac´ıo, si verifica las condiciones del Teorema de Bondareva-Shapley, en otros casos puede haber m´as de un punto en el core, lo que nos proporcionar´a m´as de una soluci´on. Ahora veamos las conclusiones espec´ıficas de cada cap´ıtulo. Respecto al Juego de Asignaci´on podemos concluir que tiene core no vac´ıo, luego siempre podremos obtener al menos una soluci´on, aunque en muchas ocasiones el core no proporcionar´a una soluci´on ´unica. De los Juegos de Producci´on Lineal, como en los de Asignaci´on, hemos probado que su core es no vac´ıo. Adem´as hemos encontrado un punto del core, a trav´es del respectivo programa dual. Aqu´ı hemos a˜nadido una aplicaci´on de una situaci´on de producci´on lineal usando CPLEX, la cual hemos resuelto mediante 85 Cap´ıtulo 7. Conclusiones NEOS-SERVER, donde hemos comprobado como lo que hemos desarrollado de forma te´orica se verifica en un ejemplo. Adem´as, al trabajar con CPLEX y NEOS-SERVER he aprendido a resolver programas lineales de optimizaci´on de forma computacional. Despu´es hemos introducido lo que es una situaci´on de localizaci´on y los juegos de localizaci´on para estas. Podemos afirmar que existen condiciones necesarias y suficientes para que el core de estos juegos sea no vac´ıo, y as´ı tener soluciones para dichas situaciones. Hemos descrito tres tipos de juegos de localizaci´on, donde en cada caso hemos visto ejemplos y hemos probado que el core de cada juego es no vac´ıo. Las situaciones de localizaci´on son un caso muy pr´actico sobre el que hay una gran variedad de casos estudiados. En el caso de Juegos de Radio y Di´ametro hemos trabajado en diferentes espacios m´etricos, hemos visto ejemplos de distintas situaciones con core vac´ıo o no vac´ıo, y distintas propiedades para los juegos de radio. Hemos definido el core para el caso de estos juegos dependiendo del espacio donde trabaj´asemos y las diferencias entre los distintos juegos (MSTG vs MRLG). Tambi´en hemos trabajado sobre Rddonde hemos extendido, la definici´on del core y que este es no vac´ıo en el caso eucl´ıdeo, en el caso del juego de localizaci´on de radio m´ınimo. Por lo tanto, los juegos cooperativos, en muchos casos, proporcionan una soluci´on para estas situaciones mediante el core. Finalmente, podemos concluir que el core es una buena herramienta para solucionar problemas de asignaci´on de costes, aunque no siempre exista, o posea m´as de una imputaci´on. Como conclusi´on personal de este Trabajo Fin de Grado, se han descrito situaciones reales, de la vida cotidiana, donde las matem´aticas, de la mano de la Teor´ıa de Juegos, pueden resolver conflictos interpersonales. Definitivamente las matem´aticas viven entre nosotros y, como hemos desarrollado, nos ayudan a solucionar una gran variedad de situaciones cotidianas de forma efectiva. En concreto en este trabajo hemos mostrado situaciones tan cotidianas como: asignar alumnos a un colegio; organizar distintos ayuntamientos para construir un aeropuerto, con sus respectivas infraestructuras; o, que beneficio podr´an 86 Cap´ıtulo 7. Conclusiones obtener varias empresas al poner en com´un sus productos para generar determinados bienes, que se pueden vender en el mercado a un precio fijo, pueden ser analizados cuantitativamente con t´ecnicas matem´aticas. Los cient´ıficos, en nuestro caso matem´aticos, tenemos el deber de transmitir todo lo anterior y mostrar al mundo de una forma amena y atractiva la importancia de la ciencia y su gran variedad de aplicaciones. 87 Cap´ıtulo 7. Conclusiones 88 Ap´endice A Aplicaci´on del Juego de Producci´on Lineal Hoy en d´ıa disponemos de bastantes software para resolver programas lineales de optimizaci´on como el XPress, Gurobi o CPLEX. Nosotros hemos elegido CPLEX, para implementarlo hemos usado la p´agina web www.neos-server.org, donde podemos trabajar con NEOS-SERVER, aqu´ı encontramos un servicio gratuito ofrecido por la Universidad de Wisconsin. En NEOS-SERVER encontraremos m´as de 60 m´etodos para resolver distintos programas de optimizaci´on entre ellos los nombrados anteriormente. Para resolver un programa, como los que nosotros tenemos que resolver, hay que enviar a NEOS-SERVER tres archivos. El primero de ellos tiene que ser un archivo con extensi´on ”.mod”, aqu´ı debemos reflejar nuestro modelo, este es el c´odigo de nuestro modelo para el programa primal: 1param n ; 2param m; 3set J := {1 . . n }; #conjunto de v a r i a b l e s de d e c i s i´o n 4set I := {1 . .m}; #conjunto de r e s t r i c c i o n e s 5 6param C {J}>= 0 ; #c o e f i c i e n t e s de l a fu nci´on o b j et i vo 7param A {I , J}>= 0 ; #matriz de l o s c o e f i c i e n t e s de l a s restricciones 8param B {I}>= 0 ; #vect o r d e l lado derecho de l a s r e s t r i c c i o n e s 89