Nuevos valores para juegos con cooperación restringida

Nuevos valores para juegos con cooperación restringida ANTONIO CARLOS ALARCÓN CARRERO Nuevos valores para juegos con cooperación restringida Agradecimientos y dedicatoria Este trabajo no habría sido posible sin el apoyo incondicional, la guía y generosidad por parte de mis directores, D. Andrés Jiménez Losada y D. José Manuel Gallardo Morilla. Por su tiempo y conocimiento, y por la libertad con la que he podido trabajar y reflexionar junto a ellos. Gracias. Agradecer también el trato y acogida por parte del grupo de investigación de Juegos con estructuras combinatorias y de orden (FQM237), sus ánimos, humor, calor y apoyo. Agradecer también a mis padres, pareja y amigos cercanos, por ser mi pilar y mi fuente de ánimo; por su apoyo incondicional, su paciencia y su amor que han sido mi mayor fuente de motivación a lo largo de todo este proceso. Quiero expresar mi sincero agradecimiento a mis compañeros del Departamento de Matemáticas Aplicada de la Universidad de Huelva, por sus consejos, colaboración y ayuda y, de forma muy especial, a mi compañera y amiga, Dª. María de la Cinta Domínguez Moreno. A todos los que han estado cerca e interesados, por acompañarme en cada paso de este largo camino y por ser mi refugio en los momentos de agotamiento y frustración; por estar siempre a mi lado y por hacer de este logro algo que pueda compartir con cada uno de ustedes. Muchas gracias. vlkpeewkc ldfpowerkwoek kfpwe9tuefj A mi abuela Dolores, por su amor y gran sentido de la justicia. Gracias por estar siempre a mi lado. Introducción La teoría de juegos es una rama de las matemáticas que estudia las interacciones estratégicas entre agentes. Tiene amplias aplicaciones en economía [ 54 ], biología [ 46 ], sociología [ 20 ], política [ 24 ] e inteligencia artificial [ 53 ] y [ 62 ]. En la teoría de juegos, los agentes pueden ser individuos, empresas, gobiernos o cualquier entidad que toma decisiones. Los juegos pueden ser competitivos, cooperativos o una mezcla de ambos, y se representan mediante modelos matemáticos que analizan los posibles resultados y las mejores estrategias a seguir. Desde un punto de vista lúdico, Zermelo [ 70 ] en 1913 publicó el primer teorema matemático relacionado con la teoría de juegos, que ofrecía una comprensión sobre la naturaleza del ajedrez al establecer que el ajedrez es un juego determinista con información completa, lo que significa que, existe una estrategia óptima para uno de los jugadores. Por otra parte, los primeros trabajos sobre juegos probabilísticos fueron realizados por Borel [ 10 ] en 1921. Se considera que la teoría de juegos nació con la publicación por parte de John von Neumann en 1928 del artículo Zur Theorie der Gesellschaftsspiele [ 65 ] donde se introdujeron los conceptos de juegos de suma cero y el equilibrio de estrategias mixtas, demostrándose el teorema minimax que establece que en un juego de suma cero con dos jugadores, en el que cada jugador busca maximizar su propia ganancia y minimizar la del otro jugador, existe siempre una estrategia óptima para cada jugador. Algunos años más tarde, en 1944, las bases de esta teoría se consolidaron con la publicación de Theory of Games and Economic Behavior escrito por Oskar Morgenstern y John von Neumann [ 66 ]. En este libro se demostró que muchas situaciones sociales y económicas pueden ser descritas a través de juegos estratégicos. En la década de 1950, el matemático John Nash [ 52 ] amplió la teoría de juegos al introducir el concepto de equilibrio de Nash. Un equilibrio de Nash es una situación en la cual ningún agente tiene incentivos para cambiar su estrategia. De manera general, se puede decir que la teoría de juegos se dedica al estudio de situaciones de cooperación y conflicto, utilizando métodos matemáticos. Usualmente, la teoría de juegos se divide en dos grandes categorías: juegos no cooperativos y juegos cooperativos, que describen diferentes tipos de interacción entre los agentes en función de su capacidad para formar alianzas y coordinar estrategias. A los agentes implicados se les suele llamar jugadores. En los juegos no cooperativos, los jugadores actúan de forma independiente y no se permite la formación de alianzas vinculantes. Cada jugador busca maximizar su propio beneficio, tomando en cuenta las decisiones de los demás. Por contra, los juegos cooperativos pueden verse como una herramienta matemática para modelar situaciones de colaboración entre agentes. En un juego cooperativo las alianzas de jugadores dan lugar a la formación de grupos denomina- xii 5.4 Aplicación: Riesgos compartidos en tráfico en línea ................78 6Conclusiones y trabajos futuros ..............................81 1. Juegos cooperativos 1.1 Conjuntos parcialmente ordenados Comenzamos exponiendo algunos conceptos y resultados básicos sobre relaciones binarias de orden (ver para más detalles [45]). Consideramos en esta sección un conjunto finito P y una relación binaria R sobre P . La relación binaria Rse denomina pre-orden si verifica las siguientes propiedades: •Reflexiva: para todo a∈P,aRa. •Transitiva: para a,b,c∈Ptal que aRbybRc, entonces: aRc. Por otro lado, el pre-orden R se denomina relación de equivalencia si también satisface la propiedad: •Simétrica: para a,b∈Ptal que aRbse tiene que bRa. Sea R una relación de equivalencia sobre P . Si a∈P , la clase de equivalencia asociada al elemento a viene dada por [a] = {b∈P:aRb} . Al conjunto de todas las clases de equivalencia respecto a R , se le denomina conjunto cociente. El conjunto cociente de P con respecto a R es una partición de P , esto es una familia de subconjuntos {B1,...,Bk} de P disjuntos dos a dos y tal que Sk i=1Bi=P . Es más, toda partición es el conjunto cociente de una relación de equivalencia. El pre-orden Rsobre Pse denomina relación de orden parcial si verifica la propiedad: •Antisimétrica: para a,b∈Ptal que aRbybRa, entonces: a=b. Dada una relación binaria R se define su clausura transitiva ˆ R como la relación binaria transitiva más pequeña que contiene a R . Es decir, la intersección de las relaciones binarias transitivas que contienen a R. En este apartado nos centraremos en las relaciones de orden, que son denotadas habitualmente como R=≤ . Si a,b∈P se denota por a<b si a≤b y a=b . La relación de orden ≤ se dice de orden total si todo par de elementos de P está relacionado, es decir, para todo a,b∈P , a≤b ob≤a. 1.2 Nociones de juegos cooperativos 2 Definición 1.1 Un conjunto parcialmente ordenado (finito) es un par (P,≤) donde P es un conjunto finito no vacío y ≤ es una relación de orden sobre P . Si ≤ es de orden total, se dice que (P,≤)está totalmente ordenado. Sea (P,≤) un conjunto parcialmente ordenado. Si A⊆P entonces (A,≤) representa al conjunto parcialmente ordenado generado al restringir la relación ≤ a los elementos de A . Una cadena en (P,≤) es un subconjunto Q⊆P tal que (Q,≤) es un conjunto totalmente ordenado. Definición 1.2 Sea (P,≤) un conjunto parcialmente ordenado y a,b∈P . Si a<b de manera que no existe un c∈P tal que a<c<b , entonces diremos que b cubre a a y lo denotamos por a◁b. El diagrama de Hasse de un conjunto parcialmente ordenado (P,≤) es una representación gráfica de la relación ≤ basada en el concepto de cobertura. Cada elemento de P se representa por un punto en el plano de forma que si para a,b∈P se tiene que a◁b entonces el punto que representa al elemento a se pinta por debajo del de b y se dibuja el segmento entre ellos. Fijado un conjunto finito N , un ejemplo de conjunto parcialmente ordenado es el álgebra de Boole de la familia de partes de N, 2N:={E:E⊆N}, junto con la relación binaria de inclusión de conjuntos, esto es (2N,⊆). Ejemplo 1.1 En la siguiente Figura 1.1 se puede ver el deagrama de Hasse correspondiente al álgebra de Boole correspondiente al conjunto N={1,2,3}. ■ Figura 1.1: Álgebra de Boole de tres elementos. 1.2 Nociones de juegos cooperativos Los juegos cooperativos son una herramienta fundamental para analizar situaciones en las que un grupo de agentes colaboran para lograr una ganancia común. Pretenden formalizar repartos "equitativos" y "justos" en situación de cooperación. Considera además que los agentes son "racionales", en el sentido de que harán lo mejor en la toma de decisiones, y que están "bien informados". Para más detalles sobre aspectos históricos en los juegos cooperativos remito a [41] y para profundizar en aspectos analíticos a [56] y [30]. 1.2 Nociones de juegos cooperativos 3 Definición 1.3 Un juego cooperativo (de utilidad transferible) consiste en un par (N,v) donde N es un conjunto finito no vacío y v: 2N→R una aplicación sobre las partes de N que satisface v(/0) = 0 . Los elementos de N son llamados jugadores, los subconjuntos de N coaliciones y la aplicación vfunción característica. Sea (N,v) un juego cooperativo. Dada una coalición E⊆N , v(E) es el valor de E , y se interpreta como el pago colectivo que los jugadores de E podrían obtener si cooperaran. Si tratamos con juegos cooperativos para los cuales el conjunto de jugadores N es fijo, cada juego (N,v) puede identificarse con su función característica v . El conjunto de juegos cooperativos con N fijo se denota por GN, por lo que v∈GNsignifica que el par (N,v)es un juego cooperativo. Ejemplo 1.2 Sea N={1,2,3} . Supongamos que el valor que genera cada coalición es el doble del número de integrantes de la coalición. Esto es, v(E) = 2|E| para todo E⊆N . Así tendríamos E⊆N v(E) {1}2 {2}2 {3}2 {1,2}4 {1,3}4 {2,3}4 {1,2,3}6 Tabla 1. Juego dependiente del tamaño de coalición. ■ Ejemplo 1.3 Supongamos que tenemos tres vecinos que conviven en una misma comunidad y necesitan un sistema de vídeo-vigilancia para proteger las zonas comunes. El conjunto de costes, individuales y colectivos entre los propietarios 1, 2 y 3 viene recogido en la siguiente tabla: E⊆N c(E) {1}100 {2}100 {3}150 {1,2}200 {1,3}210 {2,3}250 {1,2,3}299 Tabla 2. Juego del sistema de vigilancia. ■ Ejemplo 1.4 El órgano de gobierno de una institución está formada por 10 personas con derecho a toma de decisión. La elección de una propuesta solo puede ser aprobada por la institución si goza de la mayoría absoluta por parte de sus miembros. Esta situación puede modelarse del siguiente modo: el conjunto de jugadores es N={1,2,...,10} y la función característica v: 2N→Rviene dada para cada coalición E⊆Npor v(E) = 1 si |E|≥6 0 en otro caso. 1.2 Nociones de juegos cooperativos 4 ■ Describimos a continuación diferentes tipos de juegos cooperativos según las propiedades de la función característica. Definición 1.4 Sea v∈GN . El juego v es de beneficios si v(E) representa un beneficio cuantitativo para la coalición E , es decir, cuanto mayor sea el valor de v(E) mejor para los jugadores de E . El juego v es de costos si v(E) representa un costo de un proyecto común para los jugadores de E, es decir, cuanto menor sea el valor de v(E), mejor. El Ejemplo 1.2 es un juego de beneficios mientras que el Ejemplo 1.3 es un juego de costos. Normalmente se utiliza la letra c en vez de v para indicar que es de costos. A todo juego de costos c∈GN se le puede asignar un juego de beneficios mediante el juego de ahorros vc∈GN definido por vc(E) = ∑ i∈E c({i})−c(E).(1.1) En el Ejemplo 1.3, el juego de ahorros correspondiente a ces vc({1}) = vc({2}) = vc({3}) = 0 vc({1,2}) = 0,vc({1,3}) = 40 , vc({2,3}) = 0,vc({1,2,3}) = 51. Definición 1.5 Se dice que un juego cooperativo v∈GN es monótono si v(E)≤v(F) , para cualesquiera E,F∈2Ntales que E⊆F. Gran parte de los juegos cooperativos que se utilizan en la literatura son monótonos, como ocurre con los juegos de los ejemplos anteriores. Definición 1.6 Un juego cooperativo v∈GN se dice aditivo o inesencial si para E,F∈2N tales que E∩F=/0 se satisface que v(E∪F) = v(E)+v(F). Los juegos aditivos están determinados por los valores de las coaliciones individuales (aquellas formadas por un solo jugador). Por lo tanto son identificados con los vectores de RN . Si b∈RN , entonces, suponemos que representa al juego con los valores v({i}) = bi para cada i∈N . De hecho, usaremos la notación b(E) = ∑ i∈E b(i) para cada coalición E∈2N. Definición 1.7 Sea v∈GN . El juego v es superaditivo si para E,F∈2N tales que E∩F=/0 , se tiene v(E∪F)≥v(E)+v(F). Análogamente, el juego ves subaditivo si para E,F∈2Ntales que E∩F=/0, se tiene v(E∪F)≤v(E)+v(F). 1.2 Nociones de juegos cooperativos 5 En el contexto de juegos de beneficios, los juegos superaditivos son aquellos en los cuales los jugadores tienen un incentivo para cooperar. Análoga interpretación tiene la condición de subaditivo para los juegos de costos; de hecho, muchos autores incluyen la condición de superaditivo (subaditivo) en la definición de juego de beneficios (de costos). Si el juego de costos es subaditivo entonces el de ahorros asociado es superaditivo. Definición 1.8 Un juego v∈GNes convexo si para todo S,T∈2Nse verifica v(S∩T)+v(S∪T)≥v(S)+v(T). Análogamente, v∈GNes cóncavo si para todo S,T∈2Nse verifica v(S∩T)+v(S∪T)≤v(S)+v(T). En un juego convexo los incentivos para cooperar son mayores cuanto más grande sea la coalición; es decir, los incentivos marginales para unirse a coaliciones más grandes son crecientes. En los juegos cóncavos pasa lo opuesto, esto es que, los incentivos marginales de un jugador para unirse a una coalición disminuyen a medida que la coalición se agranda. Definición 1.9 El juego v∈GNse denomina 0-normalizado si v({i}) = 0,para todo i∈N. Los juegos 0 -normalizados representan situaciones donde se evalúa con 0 a la acción individual. Los valores de las coaliciones individuales por lo tanto no interesan. La 0-normalización de un juego cooperativo cualquiera v∈GNes el juego v0∈GNtal que para cada coalición S⊆N, v0(S) = v(S)−∑ i∈S v({i}).(1.2) Definición 1.10 Sea v∈GN . Se dice que v es un juego simple si v(E)∈ {0,1} para todo E⊆Ny es un juego monótono. En un juego simple los valores de la función característica no tienen un significado cuantitativo sino cualitativo. Permiten diferenciar las coaliciones entre dos opciones ordenadas (la opción 1 se supone mejor que la 0 ). A las coaliciones que toman el valor 1 se les llama coaliciones ganadoras, mientras que las que obtienen el 0 son coaliciones perdedoras. Denotaremos por W(v) al conjunto de coaliciones ganadoras en el juego simple; es decir, W(v):={E⊆N:v(E) = 1} . Se verifica que: • La gran coalición siempre es ganadora, N∈W(v) , salvo que el juego sea idénticamente cero. •La coalición vacía siempre es perdedora, /0 /∈W(v). •Si E⊆F⊆Ntal que E∈W(v), entonces F∈W(v). El Ejemplo 1.4 es un caso particular de juego simple denominado juego de votación donde W(v) = {E⊆N:|E|≥6}. 1.2 Nociones de juegos cooperativos 6 Definición 1.11 Un juego v∈GN es simétrico si existe una función real f:R→R monótona creciente con f(0) = 0 tal que v(E) = f(|E|)para toda coalición E. Esto es, el juego es simétrico si su función característica solo depende del tamaño de la coalición. Definimos las siguientes operaciones de suma y producto por un escalar en el conjunto GN para determinar su estructura como espacio vectorial. •Suma de juegos: +:GN×GN−→ GN (v,w)−→ v+w definida por (v+w)(E) = v(E)+ w(E),E⊆N. •Producto por un escalar: ·:R×GN−→ GN (α,v)−→ α·v definida por (α·v)(E) = α·v(E),E⊆Nyα∈R. Teorema 1.1 El conjunto de juegos cooperativos GN junto con las operaciones definidas anteriormente, (GN,+,·), forman un espacio vectorial real de dimensión 2|N|−1. Al elemento neutro 0∈GN respecto a la suma de juegos se le denomina juego nulo y queda definido por 0(E) = 0 para todo E⊆N . Para el juego v∈GN existe su juego opuesto, −v∈GN tal que v+(−v) = 0. Una base de GN es el conjunto uE:E∈2N\{/0} donde para una coalición no vacía E , el juego de unanimidad uEviene definido por uE(F) = 1 si E⊆F, 0 en caso contrario.(1.3) Por lo tanto, todo juego v∈GNpuede ser escrito como v=∑ {E∈2N:E=/0} △v(E)uE.(1.4) Al coeficiente △v(E) se le denomina dividendo de Harsanyi de E en el juego v y se calcula como △v(E) = ∑ F⊆E (−1)|E|−|F|v(F),(1.5) para cada E∈2N\{/0}. Definición 1.12 Dos juegos v,w∈GN son estratégicamente equivalentes si existen α>0 y b∈RNtales que w=αv+b. 1.3 Valores. El valor de Shapley 7 Con la anterior definición, se establece en GN una relación de equivalencia entre los juegos definidos para un determinado conjunto de jugadores N . Dos juegos son equivalentes si son iguales salvo por un escalamiento de los pagos o por ciertos pagos fijos individuales que no son resultado de la cooperación. Antes de finalizar la sección exponemos algunos conceptos relacionados con la solución de un juego. Suponemos un conjunto finito N fijo. Una solución de un juego cooperativo v∈GN es lo que se denomina un vector de pagos x= (xi)i∈N∈RN donde cada coordenada xi con i∈N es interpretada como el pago final que recibe el jugador i por su cooperación en el juego. Dado un vector de pagos x∈RNy una coalición E⊆N, se usará la notación x(E) = ∑i∈Exi. Obviamente, cualquier vector de RN es un vector de pagos de v en potencia, pero parece razonable buscar vectores de pago con ciertas relaciones con v . Para este fin, es usual suponer que v es un juego de beneficios y que los jugadores deciden cooperar entre ellos formando la gran coalición N . En ese caso, el vector de pagos debe ser un reparto de v(N) y además, como los jugadores son racionales, sólo aceptarán la cooperación si reciben más de lo que pueden obtener de forma individual. Definición 1.13 Un vector de pagos x∈RN se denomina imputación de un juego cooperativo v∈GNsi verifica las siguientes dos condiciones: 1) Eficiencia. x(N) = v(N), y 2) Racionalidad individual. xi≥v({i})para todo i∈N. El conjunto de imputaciones es, en la mayoría de los casos, no vacío pero muy amplio. Con la idea de restringir este conjunto, debido a que los requisitos de las imputaciones son muy débiles propondremos condiciones adicionales. Gillies [ 33 ] propuso en 1953 una extensión de la racionalidad individual a la coalicional, es decir, se dice que el vector de pagos x cumple con la racionalidad coalicional si para toda E⊆Nse verifica que x(E)≥v(E). Definición 1.14 Sea v∈GN . El conjunto constituido por todos los vectores de pagos eficientes que satisfacen la racionalidad coalicional constituyen el core del juego v. Formalmente, Core(v) = {x∈RN:x(N) = v(N),x(E)≥v(E),para todo E⊆N}. 1.3 Valores. El valor de Shapley Cuando añadimos requisitos adicionales, los subconjuntos del conjunto de imputaciones que obtenemos en muchas ocasiones contendrán más de una imputación. Sin embargo, a veces queremos dar un único vector de pagos como solución, y por tanto, cabe preguntarse cuál de todas esas soluciones posibles se toma como solución final. Shapley [ 59 ] en 1953 propuso para resolver ese problema establecer una regla que asigne a cada juego cooperativo un solo vector de pagos. Definición 1.15 Un valor en GN es una aplicación ψ:GN→RN que asigna a cada juego v∈GNun vector de pagos ψ(v). El interés de un valor para juegos cooperativos viene dado por las propiedades razonables 1.3 Valores. El valor de Shapley 8 que verifique. A continuación veremos varias de estas propiedades, aunque primeramente es necesario introducir un concepto básico que permite describir la aportación individual de un jugador a una coalición. Definición 1.16 Sea v∈GN , i∈N un jugador y E⊆N\{i} una coalición que no contenga a i. La contribución marginal de iaEes el valor v(E∪{i})−v(E). La contribución marginal de un jugador a una coalición es el incremento de beneficio que se produce con su incorporación a dicha coalición. Según sean sus contribuciones marginales definimos tres tipos particulares de jugadores Definición 1.17 Sea v∈GNun juego cooperativo. Se tiene que: 1) un jugador i∈Nes dummy si v(E∪{i}) = v(E) +v({i}), para todo E⊆N\ {i} 2) un jugador i∈Nes nulo si es dummy y además v({i}) = 0 3) dos jugadores i,j∈N son simétricos si v(E∪{i}) = v(E∪{ j}), para toda coalición E⊆ Ncon i,j/∈E. Un jugador es dummy si aporta a la coalición lo mismo que genera actuando por su propia cuenta y nulo si no aporta ningún beneficio. Los jugadores son simétricos si para cada coalición la contribución marginal de uno es igual a la contribución marginal del otro. Para un valor ψ:GN→RN, enunciamos aquí algunas propiedades: (S1) Eficiencia.∑i∈Nψi(v) = v(N)para todo v∈GN. Esto significa que, un valor es eficiente si reparte completamente el valor de la gran coalición, v(N), entre los jugadores. (S2) Aditividad.ψ(v1+v2) = ψ(v1)+ψ(v2)para todo v1,v2∈GN. La aditividad establece que el pago del juego suma es igual a la suma de los pagos de los juegos originales. (S3) Covarianza bajo equivalencia estratégica. Para cada v∈GN , α∈R y b∈RN se tiene que ψ(αv+b) = αψ (v)+b. Para dos juegos estratégicamente equivalentes los pagos son los mismos, teniendo en cuenta la escala que los relaciona, salvo por los pagos individuales que los diferencian. Si π es una permutación del conjunto N , entonces, denotamos por πE:={π(i):i∈E} con E⊆Ny por πx:= (xπ(i))i=1,...,Ncon x= (x1,...,xN)∈RN. (S4) Anonimato. Para todo v∈GN y π una permutación del conjunto N , πψ (v) = ψ(πv) , siendo πv∈GNel juego definido para cada coalición Ecomo πv(E) = v(πE). 1.3 Valores. El valor de Shapley 9 La propiedad de anonimato establece que la cantidad que recibe un jugador no depende de la etiqueta usada para identificarlo. (S5) Igual tratamiento. Si v∈GN , e i,j∈N dos jugadores simétricos en el juego v , entonces, ψi(v) = ψj(v). Un hecho importante a resaltar es que el anonimato implica igual tratamiento mientras que lo contrario no es cierto en general. (S6) Jugador dummy. Sea i∈N un jugador dummy en el juego v∈GN , entonces, ψi(v) = v({i}). La propiedad del jugador dummy establece que un jugador cuya contribución marginal en cualquier coalición coincide siempre con el valor que puede obtener por su cuenta, v({i}) , ha de recibir exactamente dicha cantidad. (S7) Jugador nulo. Si i∈Nes un jugador nulo en el juego v∈GN, entonces, ψi(v) = 0. (S8) Positividad. Si ves monótono, entonces, ψi(v)≥0, para todo i∈N. (S9) Monotonía fuerte. Si v,w∈GN , i∈N y v(E∪ {i})−v(E)⩾w(E∪ {i})−w(E) para cada E⊆N\{i}, entonces, ψi(v)⩾ψi(w). Según la monotonía fuerte, cuanto más contribuya un jugador a las coaliciones mayor pago debe recibir. (S10) Contribuciones marginales. Para cualquiera v,w∈GN de tal forma que las contribuciones marginales, para cada jugador, coincidan (esto es, para todo i∈N,v(S∪{i})−v(S) = w(S∪{i})−w(S), para todo S⊆N{i}), entonces, ψi(v) = ψi(w). Si un jugador tiene las mismas contribuciones marginales para todas las coaliciones en dos juegos diferentes, entonces sus pagos para ambos juegos deben ser iguales. Sea un jugador i∈N, definimos el juego v−i: 2N→R, dado por v−i(E) = v(E\{i}).(1.6) Se observa que el jugador ies nulo en el juego v−i. (S11) Contribuciones equilibradas. Para todo v∈GN y par de jugadores i,j∈N , entonces ψi(v)−ψi(v−j) = ψj(v)−ψj(v−i). Originalmente, esta propiedad viene formulada cambiando el conjunto de jugadores N . Definimos en primer lugar el concepto de subjuego. Sea (N,v) un juego sobre N . El subjuego sobre R⊂N es (R,vR) , donde vR: 2R→R , definida por vR(E) = v(E) para todo E⊆R . Entonces, el axioma de contribuciones equilibradas para todo v∈GN y par de 1.4 Juegos multichoice 16 tacto directo con secreciones de una persona infectada o por contacto con superficies u objetos contaminados, como un vaso de beber o un teléfono, podemos simplificar razonablemente las opciones de los agentes de la siguiente manera: σ0= "no hacer nada", σ1= "tomar la temperatura de cualquier persona que quiera entrar en el pueblo, y no dejarle entrar si tiene fiebre", y σ2= "limpiar el pueblo con productos específicos cada dos horas y no permitir la entrada a nadie con fiebre". Ahora podemos modelar el juego de control de enfermedades de la siguiente forma. Sea N={1,2,3} el conjunto de los tres agentes y β={0,1,2} . La función característica que define al juego multichoice es V:βN→R , donde V( x ) representa el beneficio generado por la coalición x∈βN. ■ En los juegos multichoice existen unos juegos que realizan el mismo papel que los juegos de unanimidad y se denominan juegos de esfuerzo mínimo: Uy(x) = 1 si xi≥yi,∀i∈N 0 en otro caso La colección {Uy: y ∈βN, y = 0 } constituye una base del espacio real de los juegos multichoice. Por tanto, todo juego V∈M G βN puede expresarse como combinación lineal de juegos de dicha base, esto es, V=∑ 0≤y≤m ∆V(y)Uy, donde ∆V( y ) es el dividendo de Harsanyi multichoice y queda definido por la siguiente relación en recurrencia: ∆V(0):=0, ∆V(y) = V(y)−∑x<y∆V(x). Definición 1.21 Un valor para juegos multichoice es una aplicación Ψ:M G βN→R{1,...,m}×N . Si V∈M G βN , k∈β\ {0} e i∈N , el número Ψk,i(V) se interpreta como el pago que se asigna al jugador ipor realizar la acción k∈β\{0}. Se considera que Ψ0,i(V) = 0. Para obtener un valor para juegos mutichoice, Hsiao y Raghavan [ 37 ] consideraron pesos 0= w(0)⩽w(1)⩽... ⩽w(m) para las diferentes acciones que pueden realizar los jugadores. Estos pesos determinan los ratios que se consideran justos a la hora de asignar el pago obtenido por un grupo de jugadores que realizan diferentes acciones dentro de una coalición. Una vez fijados estos pesos, Hsiao y Raghavan introducen un valor extendiendo el valor de Shapley. Definición 1.22 El valor de Hsiao para el juego multichoice V con pesos 0=w(0)⩽w(1)⩽ ... ⩽w(m), viene dado por Φw k,i(V) = k ∑ l=1 w(l)>0 ∑ x∈βN xi=l ∑ F⊆N\(Nm(x)∪{i}) (−1)|F|w(l) ∥x∥w+∑j∈F(w(xj+1)−w(xj))(V(x)−V(x−ei)), donde se ha utilizado la siguiente notación: si x ∈βN y l∈β , entonces Nl( x ) = {j∈N:xj=l} , 1.4 Juegos multichoice 17 ∥x∥w=∑j∈Nw(xj)yei∈ {0,1}Nestá dado por ei i=1 y eij=0 para cada j∈N\ {i}. Hsiao y Raghavan en [ 37 ] demostraron que éste es el único valor en M G βN que satisface las siguientes propiedades. Sea Ψun valor para juegos multichoice. (H1) Carrier. Si y ∈βN y V∈M G βN satisface V( x ) = V( x ∧ y ) para cada x ∈βN (donde la coordenada i -ésima del vector x ∧ yviene dada por min{xi,yi} ); entonces ∑i∈NΨyi,i(V) = V(m,...,m), (H2) Linealidad.Ψ(V1+V2) = Ψ(V1)+Ψ(V2)para cada V1,V2∈M G βN, (H3) Mínimo esfuerzo. Si y ∈βN y V∈M G βN satisface V( x ) = 0 para cada x  y, entonces Ψk,i(V) = 0 para cada i∈Nyk<yi, y (H4) Pesos proporcionales. Si y∈βN,c>0 y V∈M G βNse define por V(x) = csi x≥y 0 en caso contrario , entonces (Ψyi,i(V))i∈Nes proporcional a (w(yi))i∈N. Derks y Peters [ 23 ] dieron en 1993 otro valor tipo Shapley para juegos multichoice, que fue más tarde caracterizado en [ 22 ], distribuyéndose los dividendos entre los jugadores que los obtienen teniendo en cuenta las acciones realizadas por cada uno. El valor DP de un juego V∈M G βN para cada jugador i∈Nes DPi(V) = ∑ {x∈βN:i∈car(x)} ∆V(x) ||x||β . En [ 23 ] se mostró que DP =Φβ ; es decir, tomando como pesos en el valor de Hsiao los niveles. Aparte existen otros conceptos de valor en la literatura que tratan de extender el valor de Shapley a los juegos multichoice como son [19], [69], [13] y [14]. 2. Cooperación restringida En un juego cooperativo de utilidad transferible, no hay restricciones en las posibilidades de cooperación de los jugadores, es decir, cada coalición es factible y puede generar un valor. Este modelo general en ocasiones no es aplicable puesto que no todas las cooperaciones son viables, sino que aparecen restricciones y limitaciones en la cooperación. Estas restricciones deben tenerse en cuenta a la hora de asignar el beneficio porque si los jugadores de una coalición no pueden cooperar no generarán el valor de la coalición dado por la función característica. Nos centraremos en las restricciones en la comunicación y en las relaciones de dependencia. En las restricciones de comunicación [ 49 ] los jugadores no pueden formar coaliciones libremente, sino que su capacidad de cooperación depende de una estructura de comunicación, representada por un grafo, que establece quiénes pueden interactuar directamente entre sí. En las restricciones por permisos [ 31 ], [ 15 ], se introduce una jerarquía donde se determina quién puede cooperar con quién, poniendo de manifiesto relaciones de subordinación o dependencia. 2.1 Teoría de grafos En muchos entornos sociales o económicos, la comunicación entre los participantes es importante para la difusión de información y el trabajo cooperativo. Gran parte de esta comunicación se realiza a través de redes, sistemas de relaciones bilaterales entre los participantes. Estas redes y conexiones vienen definidas a través de grafos. Si V es un conjunto finito, definimos LV:={{i,j}:i,j∈V,i=j} . De aquí en adelante escribiremos {i,j}por i j. Definición 2.1 Se define un grafo (no dirigido y sin loops) como un par G= (V,L) donde V es un conjunto finito de elementos llamados nodos o vértices y L⊆LV es una familia de pares llamados aristas. Sea G= (V,L) un grafo. Dada la arista e=i j , los vértices i y j se denominan extremos de e . En un grafo diremos que i y j son adyacentes si existe la arista i j , y en ese caso, la arista e=i j es incidente a los vértices iyj. Definición 2.2 Un grafo dirigido o digrafo es un par G= (V,L) donde V es un conjunto finito de vértices y L es un conjunto de pares ordenados de vértices distintos denominados aristas dirigidas. 2.1 Teoría de grafos 20 Cada arista dirigida e∈L en un digrafo G= (V,L) la representamos como e= (i,j) si tiene a i como vértice inicial y a jcomo vértice final. Figura 2.1: Grafo no dirigido y digrafo. A continuación recordaremos algunos conceptos básicos de grafos. Definición 2.3 Sea G= (V,L) un grafo. Un camino (simple) entre dos vértices i,j∈V (donde i es el vértice inicial y j el final) es una secuencia no vacía de vértices diferentes (i1,...,ip)⊆V\ {i,j} de forma que ii1,ipj,ikik+1∈L para k=1,..., p−1 . Un ciclo es un camino entre un vértice y sí mismo con p≥1. Observemos que si, en un grafo, existen dos caminos diferentes entre dos vértices eso garantiza que existe un ciclo en el grafo. El concepto más importante que usaremos de grafos es el de grafo conexo. Definición 2.4 Un grafo es conexo si existe un camino entre cada par de vértices diferentes. Para un digrafo el concepto de camino es válido tomando las aristas dirigidas en el sentido de la secuencia y por lo tanto se denomina camino dirigido. Para digrafos existen varios conceptos de conexión pero no los utilizaremos. Definición 2.5 Sea G= (V,L) un grafo. Un subgrafo de G es otro grafo G0= (V0,L0) , donde V0⊆V y L0⊆L . El subgrafo inducido por S⊆V es el subgrafo G[S]=(S,LS) donde LS={i j ∈L:i,j∈S}. Figura 2.2: Grafo y subgrafo inducido. Sea G= (V,L) un grafo. Podemos definir una relación de equivalencia R en V de la siguiente forma: iRj si existe un camino entre i y j en G ; es decir, i y j están conectados en G . Dicha relación genera una partición de V en clases de equivalencia. Estas clases de equivalencia, que llamaremos componentes conexas, coinciden con los conjuntos de vértices más grandes que podemos formar de manera que sus subgrafos inducidos sean conexos. Diremos, además, que una coalición es conexa si el grafo inducido por la coalición es conexo. 2.2 Juegos con estructura de comunicación 21 Definición 2.6 Sea G= (V,L) un grafo. Las componentes conexas de G son las coaliciones conexas maximales. El conjunto de componentes conexas de G es denotado por V/G y forman una partición de V. Ejemplo 2.1 Consideremos el grafo de la Figura 2.3 . El conjunto de nodos viene dado por N={1,2,3,4,5,6} y el de aristas, L={13,14,23,35,36,45} . Dicho grafo es conexo, por lo que tiene una única componente. Un ejemplo de camino para comunicar los nodos 1 y 6 sería el definido por la secuencia 136 . Éste no es único, aunque sí el más corto. Podríamos optar también por 14536. Un ejemplo de ciclo sería el dado por 14531. ■ Figura 2.3: Componentes en un grafo. Sea G= (V,L) un grafo. Dada una arista e∈L se denota por G−e= (V,L−e) el subgrafo obtenido al eliminar la arista e , es decir, (V,L\{e}) . De forma análoga, el subgrafo formado al eliminar un vértice o nodo i∈V se define por G−i= (V\{i},L\Li) , con Li={e∈L:i∈e} . Observemos que, G−i=G[V\{i}]. Finalmente introducimos el concepto de árbol. Definición 2.7 Un árbol es un grafo conexo que no contiene ciclos. Un bosque es un grafo en el que cada una de sus componentes conexas genera un subgrafo inducido que es árbol. 2.2 Juegos con estructura de comunicación Sea N un conjunto finito fijado. Supongamos un juego cooperativo v∈GN . Myerson [ 49 ] en 1977 describió los canales factibles de comunicación entre los jugadores mediante un grafo. En ese grafo los vértices son los jugadores de N y las aristas L⊆LN representan las comunicaciones bilaterales que existen entre ellos. Cada grafo G= (N,L) es denominado estructura de comunicación sobre N ; y como N está fijo, podemos identificar G con su conjunto de aristas L . La familia de estructuras de comunicación se identifica entonces con 2LN . Usaremos las nociones desarrolladas sobre grafos en la sección anterior denotando los grafos por su conjunto de aristas. De esta forma, si L∈2LN , entonces N/L=N/(N,L) es la familia de componentes conexas de (N,L) . Myerson supuso que la asignación de pagos justa de un juego dependía de la estructura de comunicación que se tuviese entre los jugadores, por lo que definió el siguiente concepto modificado de juego cooperativo. 2.2 Juegos con estructura de comunicación 22 Definición 2.8 Un juego con estructura de comunicación sobre N es un par (v,L) donde v∈GN y L∈2LN , es decir, un juego cooperativo y una estructura de comunicación dada por un grafo. El conjunto de juegos con estructura de comunicación sobre N se denota por CSGN . Se extiende el concepto de valor para esta familia de juegos, siguiendo la misma idea clásica dada para juegos cooperativos. Definición 2.9 Un valor sobre CSGN es una función ψ:CSGN→RN que asigna a cada juego con estructura de comunicación (v,L)un vector de pagos ψ(v,L)∈RN. Myerson [ 49 ] introdujo también un método para analizar juegos con estructura de comunicación y encontrar valores para estos juegos. Consiste en generar un nuevo juego cooperativo que incorpore en la función característica la información del grafo. Para coordinar acciones dentro de una coalición E de jugadores es necesario que el subgrafo inducido LE sea conexo (esto es, G[E] sea conexo). Si una coalición E no es conexa en L entonces las componentes conexas de su subgrafo inducido E/L=E/LE generan una partición de E en coaliciones conexas. Un jugador i∈N se dice aislado en L si Li=/0 . Puede ocurrir que todos los jugadores estén aislados, es decir, L=/0 . En este caso no existe comunicación entre los jugadores para coordinar la cooperación. Como caso opuesto, diremos que la estructura de comunicación Les completa si L=LN. Definición 2.10 Sea (v,L)∈CSGN un juego con estructura de comunicación sobre N . El juego restringido asociado es vL∈GNde forma que para cada coalición E⊆Nse tiene que vL(E) = ∑ R∈E/L v(R). Las coaliciones E conexas en L verifican que vL(E) = v(E) . Si la coalición no es conexa esta se divide en coaliciones conexas maximales, de forma que los jugadores de cada una de estas coaliciones pueden actuar conjuntamente. Es decir, el beneficio es la suma de los valores de las componentes conexas. Si L es vacío, el juego restringido se convierte en el juego aditivo definido por los valores de las coaliciones individuales, y si L es completa entonces vL=v . Una vez construido el juego restringido se le aplican los distintos conceptos de solución de juegos cooperativos. El valor por excelencia para juegos con estructura de comunicación es el valor de Myerson [ 49 ] que consiste en, siguiendo el modelo descrito, aplicar el valor de Shapley al juego restringido. Definición 2.11 El valor de Myerson asigna a cada situación de comunicación (v,L) el valor de Shapley del juego restringido por la estructura, es decir Y(v,L) = Sh(vL). Ejemplo 2.2 Sea N={1,2,3} el conjunto de jugadores comunicados por L={12,23} . Consideramos el juego definido por: v(E) = 1 si E∈{{1,3},{2,3},N} 0 en otro caso . Entonces, tenemos que: 2.2 Juegos con estructura de comunicación 23 Figura 2.4: Estructura de comunicación. E⊆N E/L vL(E) /0 /0 0 {1} {{1}} v({1}) = 0 {2} {{2}} v({2}) = 0 {3} {{3}} v({3}) = 0 {1,2} {{1,2}} v({1,2}) = 0 {1,3} {{1},{3}} v({1})+v({3}) = 0 {2,3} {{2,3}} v({2,3}) = 1 {1,2,3} {{1,2,3}} v({1,2,3}) = 1 Por tanto: vL(E) = 1 si E∈{{2,3},N} 0 en otro caso. El valor de Myerson asociado a este juego es Y(v,L) = Sh(vL). Por tanto: Y(v,L) = 0,1 2,1 2 ■ Introducimos ahora algunas propiedades aplicables a un valor para juegos con estructura de cooperación. Sea ψun valor sobre CSGN. (M1) Descomposición por componentes. Para cualquier juego con estructura de comunicación (v,L)∈CSGNy cualquier jugador i∈N, se verifica que el pago a este jugador ies ψi(v,L) = ψi(v,L{i}), donde L{i}es el conjunto de aristas que están en la componente conexa de i. Es decir, el pago a un jugador no depende de las aristas del grafo que no pertenecen a la componente conexa que contiene al jugador. (M2) Eficiencia por componentes. Si (v,L)∈CSGN , entonces para cualquier componente conexa R∈N/Lse verifica que ∑ i∈R ψi(v,L) = v(R). Las ganancias de cada componente conexa se distribuyen de forma separada. 2.2 Juegos con estructura de comunicación 24 (M3) Jugador aislado. Si i es un jugador aislado para la estructura de comunicación L en (v,L)∈CSGN, entonces ψi(v,L) = v({i}). Si un jugador es aislado, su pago debería ser su valor individual; esto es, el valor es eficiente para las componentes individuales. (M4) Contribuciones equilibradas. Para cada juego con estructura de comunicación (v,L)∈ CSGNy cualquier arista i j ∈L, se verifica ψi(v,L)−ψi(v,L−j) = ψj(v,L)−ψj(v,L−i), donde L−jhace referencia al conjunto de aristas L\Ljcon Lj={l∈L:j∈l}. Por tanto, una regla de asignación satisface la propiedad de contribuciones equilibradas si para dos jugadores i y j se tiene que la pérdida que el jugador i puede provocar al jugador j por quedarse aislado es la misma que la pérdida que puede provocar el jugador j al jugador ial realizar la misma acción. (M5) Justicia. Si (v,L)∈CSGNei j ∈L, entonces se verifica ψi(v,L)−ψi(v,L−i j) = ψj(v,L)−ψj(v,L−i j), donde L−i j es el grafo resultante de eliminar la arista i j en L. La eliminación de una arista de comunicación entre dos vértices implica la misma pérdida para ambos jugadores implicados. (M6) Estabilidad. Para (v,L)∈CSGNy cualquier arista i j ∈L, se verifica ψi(v,L)≥ψi(v,L−i j). La reducción de comunicación de un jugador produce una pérdida de ganancia a ese jugador. Proposición 2.1 El valor de Myerson satisface los axiomas de descomposición por componentes, eficiencia por componentes, jugador aislado, contribuciones equilibradas y justicia. Además verifica el axioma de estabilidad cuando (v,L)∈CSGNsatisface que ves superaditivo. Con estas propiedades podemos enunciar las siguientes axiomatizaciones que definen al valor de Myerson de forma unívoca, ambas dadas por Myerson en [49] y [50]. Teorema 2.1 El valor de Myerson es la única regla de asignación en CSG que satisface: 1) Eficiencia por componentes y justicia (axiomática de Myerson (1977).) 2) Eficiencia por componentes y la propiedad de contribuciones equilibradas (axiomática de Myerson (1980).) 2.3 Estructuras de permiso 25 2.3 Estructuras de permiso Otro tipo de restricción en la cooperación puede venir dada por una estructura de permiso que describa una organización jerárquica respecto a los jugadores. Definición 2.12 Una estructura de permiso en N viene dada por una aplicación S:N→2N verificando que, i/∈S(i) . A los jugadores de S(i) son les denomina sucesores del jugador i∈N . Denotaremos por SNal conjunto de todas las estructuras de permisos definidas sobre N. Podemos ver al conjunto S(i) como el subconjunto de N que contiene a todos los jugadores que están dominados directamente por el jugador i . Si se considera un digrafo D donde haya una arista de i a j si y solo si j sea sucesor de i , entonces podemos identificar la estructura de permiso con el digrafo. Así, para i∈N , S(i) = {j∈N:(i,j)∈D} por la identificación descrita antes, son los sucesores de i. Sea la estructura de permiso S∈SN . Podemos definir la relación binaria R de tal manera que, para dos jugadores i,j∈N , jRi si y solo si j∈S(i) . Usando la clausura transitiva de R , ˆ R , podemos definir ˆ S(i) = {j∈N:jˆ Ri} . Por tanto, j∈ˆ S(i) si y solo si existe una secuencia de jugadores en N , ipq p=0 , tal que, i0=i,iq=j e ip∈Sip−1 para 1≤p≤q . Definimos, en base a este concepto, los siguientes subconjuntos de jugadores: •El conjunto de jugadores subordinados de icorresponde con el conjunto ˆ S(i). • El conjunto de predecesores del jugador i con la estructura de permiso S , es el conjunto de jugadores PS(i) = {j∈N:i∈S(j)}. • El conjunto de superiores de i en la estructura de permiso S viene dado por ˆ PS(i) = j∈N:i∈ˆ S(j). Definición 2.13 Una estructura de permiso S:N→2N es estricta si es acíclica, es decir, ningún jugador es subordinado de sí mismo. En una estructura de permiso estricta hay jugadores que no tienen superiores y hay jugadores que no tienen subordinados. A una estructura de permiso estricta en la que existe un único jugador sin predecesor y todos los demás jugadores son sus subordinados indirectos de él se denomina jerarquía [30]. Ejemplo 2.3 Consideremos el conjunto de jugadores dados por N={1,2,3,4,5} , donde existe la estructura de permiso definida por el digrafo D={(1,2),(1,3),(2,4),(3,4),(4,5)} , tal y como se aprecia en la Figura 2.5 . Recopilamos en la Tabla 1 toda la información de la estructura de permiso. N S(i)PS(i)ˆ S(i)ˆ PS(i) 1{2,3}/0 {2,3,4,5}/0 2{4} {1} {4,5} {1} 3{4} {1} {4,5} {1} 4{5} {2,3} {5} {1,2,3} 5 /0 {4}/0 {1,2,3,4} 3.1 Un valor para juegos restringidos con middlemen sobre las aristas 32 Ejemplo 3.1 Consideramos el conjunto de tres jugadores N={1,2,3} con la estructura de comunicación L={12,23}. Figura 3.1: Estructura de comunicación (N,L). Sobre (N,L) podemos definir el juego (v,L)∈CSGN definido por v(E) = |E|2,E⊆N . Este es el juego cuyos jugadores son los integrantes de NyLmuestra las comunicaciones entre ellos. E⊆N v(E) /0 0 {1}1 {2}1 {3}1 {1,2}4 {1,3}4 {2,3}4 {1,2,3}9 Obtenemos el siguiente valor de Shapley, Sh(v) = (3,3,3). Para obtener el valor de Myerson, tenemos E⊆N E/L vL(E) /0 /0 0 {1} {{1}} v({1}) = 1 {2} {{2}} v({2}) = 1 {3} {{3}} v({3}) = 1 {1,2} {{1,2}} v({1,2}) = 4 {1,3} {{1},{3}} v({1})+v({3}) = 2 {2,3} {{2,3}} v({2,3}) = 4 {1,2,3} {{1,2,3}} v({1,2,3}) = 9 Obteniéndose, Y(v,L) = 8 3,11 3,8 3. Volvemos a considerar la estructura de comunicación anterior ampliando al conjunto de jugadores de N a N∪L={1,2,3,12,23} . El juego con intermediarios en las aristas viene dado por la siguiente tabla 3.1 Un valor para juegos restringidos con middlemen sobre las aristas 33 E∪F E/F vL(E∪F) /0∪/0 /0 0 {1}∪ /0 {{1}} v({1}) = 1 {2}∪ /0 {{2}} v({2}) = 1 {3}∪ /0 {{3}} v({3}) = 1 {1,2}∪ /0 {{1},{2}} v({1})+v({2}) = 2 {1,3}∪ /0 {{1},{3}} v({1})+v({3}) = 2 {2,3}∪ /0 {{2},{3}} v({2})+v({3}) = 2 {1,2,3}∪ /0 {{1},{2},{3}} v({1})+v({2})+v({3}) = 3 /0∪{12}/0 0 /0∪{23}/0 0 /0∪L/0 0 {1}∪{12} {{1}} v({1}) = 1 {1}∪{23} {{1}} v({1}) = 1 {1}∪L{{1}} v({1}) = 1 {2}∪{12} {{2}} v({2}) = 1 {2}∪{23} {{2}} v({2}) = 1 {2}∪L{{2}} v({2}) = 1 {3}∪{12} {{3}} v({3}) = 1 {3}∪{23} {{3}} v({3}) = 1 {3}∪L{{3}} v({3}) = 1 {1,2}∪{12} {{1,2}} v({1,2}) = 4 {1,2}∪{23} {{1},{2}} v({1})+v({2}) = 2 {1,2}∪L{{1,2}} v({1,2}) = 4 {1,3}∪{12} {{1},{3}} v({1})+v({3}) = 2 {1,3}∪{23} {{1},{3}} v({1})+v({3}) = 2 {1,3}∪L{{1,3}} v({1,3}) = 4 {2,3}∪{12} {{2},{3}} v({2})+v({3}) = 2 {2,3}∪{23} {{2,3}} v({2,3}) = 4 {2,3}∪L{{2,3}} v({2,3}) = 4 {1,2,3}∪{12} {{1,2},{3}} v({1,2})+v({3}) = 5 {1,2,3}∪{23} {{1},{2,3}} v({1})+v({2,3}) = 5 {1,2,3}∪L{{1,2,3}} v({1,2,3}) = 9 Obtenemos el valor de Shapley, Sh(vL) = 2167 1000,2333 1000,2167 1000,1167 1000,1167 1000. ■ Definición 3.2 Sea N un conjunto finito. Un valor para juegos con intermediarios en las aristas para juegos con estructura de comunicación se define como una aplicación Ψ que asigna a cada (v,L)∈CSGNun vector de pagos Ψ(v,L)∈RN∪L. Definimos un valor para los juegos con intermediarios en las aristas con estructura de comunicación usando vL. 3.1 Un valor para juegos restringidos con middlemen sobre las aristas 34 Definición 3.3 El valor de Myerson para juegos con intermediarios en las aristas es el valor Φ dado por Φ(v,L) = Sh(vL)∈RN∪L, para todo (v,L)∈CSGN. Este valor está relacionado con el valor original de Myerson. De hecho, probamos el siguiente resultado que nos permite determinar Φ a través del valor de Myerson cambiando el juego y el grafo asociado, por otros en los que los intermediarios son jugadores (situados, por tanto, en los nodos). Proposición 3.1 El valor de Myerson para juegos con intermediarios en las aristas Φ satisface que Φ(v,L) = Y(ˆv,ˆ L)para todo (v,L)∈CSGN, donde 1) el juego ˆv∈GN∪Lviene definido por ˆv(E∪F):=v(E), para E⊆NyF⊆L, 2) y el grafo con intermediarios (N∪L,ˆ L) es el grafo determinado por el conjunto de nodos ampliados N∪L y ˆ L={ie :i∈N,e∈L,i∈e} que denota al nuevo conjunto de aristas constituido por las aristas no dirigidas que conectan cada nodo con cada intermediario incidente en él. Demostración. Consideramos (v,L)∈CSGN . Sea E∪F con E⊆N y F⊆L una coalición en N∪L . Para cada T⊆E , definimos el conjunto de aristas de F con extremos adyacentes en T , como HT F={i j ∈F:{i,j}∩T=/0}. Se verifica, entonces que (E∪F)/ˆ L={T∪HT F:T∈E/F}, ya que la coalición T está en E/F si y solo si T está conectada en (E,FE) y no hay i j ∈HT F con j∈E\T. Ahora obtenemos ˆvˆ L(E∪F) = ∑ T∪H∈(E∪F)/ˆ L ˆv(T∪H) = ∑ T∪H∈(E∪F)/ˆ L v(T) =∑ T∈E/F v(T) = vL(E∪F). Si ambos juegos son iguales, entonces, Y(ˆv,ˆ L) = Sh(ˆvˆ L) = Sh(vL) = Φ(v,L). ■ Ejemplo 3.2 Tomando el Ejemplo 3.1 , podemos considerar unos jugadores intermediarios denotados e1 (jugador localizado en la arista 12 ) y e2 (equivalente al jugador intermedio en la arista 23), tal y como viene ilustrado en la Figura 3.2. Aquí, ˆ L={1e1,2e1,2e2,3e2}. 3.1 Un valor para juegos restringidos con middlemen sobre las aristas 35 Figura 3.2: Grafo (N,L)y grafo con intermediarios (N∪L,ˆ L) ■ Nuestro objetivo en el resto de esta sección será caracterizar Φ . Para ello, consideraremos las siguientes propiedades: (I1) Eficiencia por componentes. Un valor Ψ para juegos con intermediarios en las aristas satisface eficiencia por componentes si ∑ i∈T Ψi(v,L)+ ∑ jk∈LT Ψjk (v,L) = v(T), para cada (v,L)∈CSGNyT∈N/L. La propiedad de eficiencia por componentes establece que si T es una componente conexa del grafo de la estructura de comunicación, entonces los jugadores de T y los intermediarios que los comunican reciben la ganancia que los jugadores de T pueden generar cuando cooperan. (I2) Justicia. Un valor Ψpara juegos con intermediarios en las aristas satisface justicia si Ψi(v,L)−Ψi(v,L−i j) = Ψi j(v,L), para cada (v,L)∈CSGNy cada i j ∈L. La propiedad de justicia afirma que si un intermediario establece una comunicación directa entre dos jugadores, los tres se beneficiarán por igual. Este axioma de justicia (I2) implica, en particular, la justicia de Myerson (M5): si i j ∈L , Ψi(v,L)−Ψi(v,L−i j) = Ψj(v,L)−Ψj(v,L−i j). Los siguientes teoremas establecen que Φse caracteriza por las dos propiedades anteriores. Teorema 3.1 El valor Φ satisface las dos anteriores propiedades de eficiencia por componentes (I1) y justicia (I2). Demostración. Mostraremos que Φsatisface las propiedades anteriormente mencionadas. EFICIENCIA POR COMPONENTES. 3.1 Un valor para juegos restringidos con middlemen sobre las aristas 36 Sean (v,L)∈CSGN y T∈N/L . Se tiene que: T∪LT∈(N∪L)/ˆ L . De la Proposición 3.1 anterior, tenemos la igualdad ∑ i∈T Φi(v,L)+ ∑ i j∈LT Φi j(v,L) = ∑ i∈T Yi(ˆv,ˆ L)+ ∑ i j∈LT Yi j(ˆv,ˆ L), y como el valor de Myerson satisface la eficiencia por componentes ∑ i∈T Yi(ˆv,ˆ L)+ ∑ i j∈LT Yi j(ˆv,ˆ L) = ˆv(T∪LT) = v(T), por lo que concatenando ambas igualdades obtenemos la propiedad I1. JUSTICIA. Sea (v,L)∈CSGN y sea e=i j ∈L . Consideramos la arista ie ∈ˆ L , y aplicamos la propiedad de justicia del valor de Myerson al juego (ˆv,ˆ L), obteniéndose la siguiente relación Ye(ˆv,ˆ L)−Ye(ˆv,ˆ L−ie) = Yi(ˆv,ˆ L)−Yi(ˆv,ˆ L−ie).(3.1) De la Proposición 3.1 , seguimos que, Φe(v,L) = Ye(ˆv,ˆ L) y Φi(v,L) = Yi(ˆv,ˆ L) . Además, la definición del valor de Myerson implica que Y(ˆv,ˆ L−ie) = Shˆvˆ L−ie , donde ˆvˆ L−ie ∈GN∪L. Primero, probaremos que e es un jugador nulo en ˆvˆ L−ie . Se observa que e , como un vértice en (N∪L,ˆ L−ie) , solo está conectado a j . Sea E∪F con E⊆N y F⊆L−e . Tenemos la intención de probar que ˆvˆ L−ie ((E∪F)∪{e}) = ˆvˆ L−ie (E∪F).(3.2) De hecho, si j/∈E , entonces {e} es una componente conexa en (E∪(F∪{e}),(ˆ L−ie)E∪(F∪{e})) y como ˆv({e}) = 0 , la igualdad se verifica. Supongamos que j∈E . Si T∪H∈(E∪F)/(ˆ L−ie) es la componente conexa que contiene a j en el grafo sin e , entonces T∪(H∪{e})∈((E∪F)∪ {e}))/(ˆ L−ie)es la componente conexa que contiene a jen el grafo con e. Ahora, podemos ver que [(E∪F)/(ˆ L−ie)]\{T∪H}= [((E∪F)∪{e}))/(ˆ L−ie)]\{T∪(H∪{e})}. De la definición del juego ˆv , obtenemos la igualdad (3.2) . Dado que e es un jugador nulo en ˆvˆ L−ie y el valor de Shapley satisface la propiedad del jugador nulo, se tiene, Ye(ˆv,ˆ L−ie) = Sheˆvˆ L−ie =0.(3.3) Consideremos los juegos ˆvˆ L−ie e=ˆvˆ L−ie |N∪L−e y ˆvˆ L−ie i=ˆvˆ L−ie |N∪L−i . El jugador arista e es nulo también para ˆvˆ L−ie i , por lo que por la propiedad (S11) de contribuciones equilibradas que satisface el valor de Shapley con la fórmula (1.7), implica que Shi(ˆvˆ L−ie e) = Shi(ˆvˆ L−ie ). 3.1 Un valor para juegos restringidos con middlemen sobre las aristas 37 Tomamos, entonces, E∪F con E⊆N y F⊆L−e . Si volvemos a no considerar al jugador e , entonces: ˆvˆ L−ie e(E∪F) = ˆvd L−e(E∪F). En segundo lugar, obtenemos que Yi(ˆv,ˆ L−ie) = Shiˆvˆ L−ie e=Shiˆvd L−e=Yi(ˆv,d L−e).(3.4) Finalmente, de las ecuaciones (3.1), (3.3) y (3.4) concluimos que Φi j(v,L) = Ye(ˆv,ˆ L) = Yi(ˆv,ˆ L)−Yi(ˆv,d L−e) = Φi(v,L)−Φi(v,L−i j). ■ Ahora probaremos que nuestro valor está determinado unívocamente por las propiedades de eficiencia por componentes (I1) y la justicia (I2). Teorema 3.2 El valor Φ es el único valor para juegos restringidos por grafo con intermediarios en las aristas que satisface I1 e I2. Demostración. Sean Ψ,Φ:CSGN→RN∪L valores que satisfacen I1 e I2. Nuestro objetivo es demostrar que Φ(v,L) = Ψ(v,L)para cada (v,L)∈CSGN. Probaremos la igualdad anterior por inducción sobre |L|. •Caso base: |L|=0. Por la propiedad de la eficiencia por componentes (I1), se deduce que Ψi(v,/0) = Φi(v,/0) = v({i}), para cada i∈N. •Paso inductivo: Sea (v,L)∈CSGN tal que |L|>0 . Para probar que Ψ(v,L) = Φ(v,L) , mostraremos que para cada T∈N/L, se cumplen las siguientes igualdades Ψi(v,L) = Φi(v,L)para todo i∈T,(3.5) Ψjk(v,L) = Φjk(v,L)para todo jk ∈LT.(3.6) Tomamos T∈N/L . Si |T|=1 , entonces LT=/0 , y por la propiedad de eficiencia por componentes, la ecuación (3.5) se verifica. Suponemos ahora que |T|>1 . Sea i,j∈T con i j ∈L. Por la propiedad I2, es claro que Ψi(v,L)−Ψi(v,L−i j) = Ψj(v,L)−Ψj(v,L−i j),(3.7) Φi(v,L)−Φi(v,L−i j) = Φj(v,L)−Φj(v,L−i j).(3.8) 3.1 Un valor para juegos restringidos con middlemen sobre las aristas 38 Además, por hipótesis de inducción, tenemos que, Ψi(v,L−i j) = Φi(v,L−i j),(3.9) Ψj(v,L−i j) = Φj(v,L−i j).(3.10) De las ecuaciones (3.7),(3.8),(3.9)y(3.10), concluimos que Ψi(v,L)−Φi(v,L) = Ψj(v,L)−Φj(v,L). Teniendo en cuenta que i y j han sido elegidos arbitrariamente en T con la condición i j ∈L y que T es una componente conexa de (N,L) , entonces se tiene que existe b∈R tal que Ψi(v,L)−Φi(v,L) = b,para todo i∈T.(3.11) Sea jk ∈LT. Por la propiedad de la justicia (I2), sabemos que Ψjk(v,L) = Ψj(v,L)−Ψj(v,L−jk), Φjk(v,L) = Φj(v,L)−Φj(v,L−jk). De este modo, se verifica Ψjk(v,L)−Φjk(v,L) = Ψj(v,L)−Φj(v,L)−Ψj(v,L−jk) +Φj(v,L−jk) = b, donde hemos usado (3.11)y la hipótesis de inducción. Por lo tanto, hemos probado Ψjk(v,L)−Φjk(v,L) = bpara todo jk ∈LT.(3.12) De 3.11 y 3.12 y del hecho de que tanto Ψ y Φ satisfacen la eficiencia por componentes (I1), podemos deducir fácilmente que b=0, lo que conduce a 3.5y3.6. ■ Nótese que la caracterización que hemos obtenido para el valor Φ es similar a la obtenida por Myerson [ 49 ] para el valor Y (ver Definición 2.11 ). En términos generales, hemos adaptado las propiedades de eficiencia por componentes (M2) y justicia (M5) a nuestro marco. En su artículo seminal, Myerson introdujo una tercera propiedad interesante de los valores para juegos con restricción por grafos, la estabilidad (M6). En este contexto, la estabilidad significa que si el juego subyacente (es decir, el juego antes de considerar las restricciones de comunicación) es superaditivo (ver Definición 1.7 ), dos jugadores siempre se beneficiarán al establecer comunicación entre ellos. Después de demostrar que el valor Y se caracteriza por las propiedades de justicia y eficiencia por componentes (ver Teorema 2.1 apartado 1), Myerson concluye su artículo con la prueba de que Y es estable. Para mantener el paralelismo entre nuestro valor expuesto y el de Myerson, probaremos que Φtambién satisface esta propiedad. 3.1 Un valor para juegos restringidos con middlemen sobre las aristas 39 Proposición 3.2 El valor Φ es estable para juegos superaditivos. Es decir, si (v,L)∈CSGN y v es superaditivo, entonces, Φi(v,L)⩾Φi(v,L−i j) por cada i j ∈L. Demostración. Sea (v,L)∈CSGN tal que v es superaditivo. Sea i j ∈L . Nuestro objetivo es probar que Φi(v,L)⩾Φi(v,L−i j) . Por la propiedad de justicia, esto es equivalente a Φi j(v,L)⩾0 . Tenemos ahora que Φi j(v,L) = ∑ E⊆N F⊆L−i j qN∪L E∪F(vL(E∪F∪{i j})−vL(E∪F)). Por lo tanto, basta probar que vL(E∪F∪{i j})⩾vL(E∪F) para cada E⊆N y todo F⊆L−i j . Para ello, tomamos E⊆NyF⊆L−i j y distinguimos tres casos: (i) {i,j}⊈E. En este caso, es evidente que (F∪{i j})E=FE. Tenemos que vL(E∪F∪{i j}) = ∑ R∈E/(F∪{i j})E v(R) = ∑ R∈E/FE v(R) = vL(E∪F). (ii) i,j∈E y están conectados en (E,FE) . En este caso, es fácil comprobar que E/(F∪ {i j})E=E/FE. Esto lleva a que vL(E∪F∪{i j}) = vL(E∪F). (iii) i,j∈E y no están conectados en (E,FE) . Podemos escribir E/FE={R1,...,Rm} , donde m⩾2 , i∈R1 y j∈R2 . Es claro que E/(F∪ {i j})E={R1∪R2,R3...,Rm} . Tenemos que vL(E∪F∪{i j})−vL(E∪F) = ∑ R∈E/(F∪{i j})E v(R)−∑ R∈E/FE v(R) =v(R1∪R2)−v(R1)−v(R2), que es no negativo por la superaditividad de v. Por eso, vL(E∪F∪ {i j})⩾vL(E∪F). ■ La siguiente propiedad será interesante en la siguiente sección. Proposición 3.3 Si (v,L)∈CSGN satisface que v es superaditivo y positivo, entonces se cumple Φ(v,L)≥0. Demostración. Sea (v,L)∈CSGN tal que v sea superaditivo y positivo. Probaremos que vL es monótono. Sean T⊆E⊆NyS⊆F⊆L. Vemos que vL(T∪S)≤vL(E∪F). En la prueba de la Proposición 3.2, mostramos que si v es superaditivo, entonces vL(E∪S)≤vL(E∪F) . Observe que si R′∈T/LT , entonces existe solo un R∈E/LE con 3.2 Aplicación: un KRI para redes internas 40 R′⊆R . Como se expuso, dado que v es superaditivo y positivo, entonces v es monótono. Para cada R∈E/LEestablecemos M(R) = {R′∈T/LT:R′⊆R}. Como los elementos de M(R)son disjuntos y ves superaditivo y monótono, obtenemos vL(T∪S) = ∑ {R∈E/LE:M(R)=/0} ∑ R′∈M(R) v(R′)≤∑ {R∈E/LE:M(R)=/0} v [ R′∈M(R) R′  ≤∑ {R∈E/LE:M(R)=/0} v [ R′∈M(R) R′ +v R\[ R′∈M(R) R′   ≤∑ {R∈E/LE:M(R)=/0} v(R)≤∑ R∈E/LE v(R) = vL(E∪S). Por lo tanto, obtenemos el siguiente resultado: vL(T∪S)≤vL(E∪S)≤vL(E∪F). Sabemos que el valor de Shapley satisface la positividad (S8) como puede verse en [ 68 ]. Como vLes monótono y Φ(v,L) = Sh(vL), entonces Φ(v,L)≥0. ■ 3.2 Aplicación: un KRI para redes internas Consideremos una red interna de dispositivos conectados identificando cada conexión bilateral con una arista. Se puede intercambiar información, protegida por protocolos, entre dispositivos a través de la conexión respetando la arquitectura de capas del modelo OSI (Open Systems Interconnections) [ 67 ]. Las diferentes capas del modelo OSI garantizan que la información se transmita con disponibilidad, integridad y confidencialidad [ 42 ]. Sin embargo, el canal de comunicación (arista) puede ser intervenido por especialistas capaces de vulnerar sistemas de seguridad débiles. Este ataque de conexión se denomina man in the middle (generalmente conocido por las siglas MiTM). Este ataque permite que un agente malicioso manipule la conexión, ya sea escuchando la comunicación (sniffing) o suplantando la identidad (spoofing) de cualquiera de las partes. Pretendemos usar la teoría de juegos cooperativos para definir un indicador de riesgo potencial KRI (Key Risk Indicator) [ 7 , 58 ], que transformaremos en una métrica para reflejar los riesgos en un mapa de riesgo (tal y como aconseja la norma ISO/ Norma IEC 27001). El mapa de riesgos es una simplificación de la información técnica, donde la gravedad de las vulnerabilidades se puede mostrar por colores [5]. Para nuestra aplicación consideramos una red interna de computadoras conectadas según la topología representada en un grafo (N,L) y suponemos que la información se almacena en las computadoras de forma independiente. La red tiene un sistema para saber cuando ha habido un robo o alteración de información, pero no puede determinar con exactitud si la vulnerabilidad proviene de la computadora o de la comunicación. Utilizamos lo desarrollado anteriormente como una especie de indicador de riesgo que establece la probabilidad de sufrir una vulnerabilidad en las computadoras y/o comunicaciones, y en vista de estas probabilidades hacer una distribución de la inversión. Supongamos un cierto punto de control en el tiempo de la red. Sea E⊆N un 3.2 Aplicación: un KRI para redes internas 41 subconjunto de computadoras. Podemos definir un juego (N,v)de la siguiente manera: v(E) = cantidad de datos atacados almacenados solo en computadoras de E cantidad total de datos atacados (3.13) Hay que tener en cuenta que los datos en las computadoras de E pueden ser robados en las computadoras mismas o en los enlaces entre ellas. Por la construcción del juego, v es positivo, monótono y superaditivo, por lo que proponemos el valor Φ(v,L) como el KRI para la red en ese determinado punto de control, que distribuye el riesgo entre los diferentes elementos de la red, nodos y enlaces. En realidad, dado que hay eficiencia por componentes, obtenemos un KRI en cada componente conectada de la red. La Proposición 3.2 garantiza que el índice no sea negativo. La justicia dice que el riesgo en una arista es la diferencia entre el riesgo de uno de sus vértices con el enlace en la estructura y sin él. En primer lugar, se propone obtener un KRI estructural para la red o cualquiera de sus subredes inducida por un subconjunto de computadores T⊂N por el valor Φ(uT,L) , donde uT es el juego de unanimidad. Este índice inicial mide el riesgo estructural de cada elemento, es decir, la incidencia de cada uno de ellos (nodos y enlaces) en el robo de un dato de T . A continuación, proponemos calcular un KRI en un punto de control de tiempo en la red usando Φ(v,L) y construyendo v como en (3.13) con la información de los datos de robo en ese momento. Para demostrar esta idea, tomamos la red en la Figura 3.3 con N={1,2,3,4} y L={12,13,14,23,34}. Figura 3.3: Red y estructura interna. (1) Nuestro objetivo es calcular el KRI estructural de la red, es decir, calcular el valor Φ(uN,L) . Recordamos que Φ(uN,L) = Sh((uN)L). Para determinar Sh((uN)L) , aplicaremos la caracterización del valor de Shapley a través del cómputo de los dividendos de Harsanyi (ver Proposición 1.1 apartado 3). En primer lugar, calculamos (uN)L(E∪F) para cada E⊆N y cada F⊆L . Ahora, usamos la forma recursiva para calcular los dividendos de Harsanyi de vL . La Tabla 1 muestra los resultados obtenidos. Así, obtenemos Sh1((uN)L) = 1 7+1 7+1 7+1 7+1 7+1 7+1 7+1 7−2 8−2 8−2 8−2 8−3 8+4 9=0.211. Está claro que el cálculo de los pagos a los jugadores 2,3,4 sería el mismo que el anterior. Por lo tanto, Sh1((uN)L) = Sh2((uN)L) = Sh3((uN)L) = Sh4((uN)L) = 0.211. 4.2 Una familia de valores para juegos con estructura de autorización 48 Como ∑ R⊆N1(x)\{i} (−1)|R|=0 si N1(x)\{i} =/0 1 de otra manera Entonces, ξ1 i(v,A) = ∑ x∈3N N1(x)={i} ∑ F⊆N0(x)\{i} (−1)|F| ∥x∥w+|F|(MA v(x+ei)−MA v(x−ei)). Como cada vector x + e i∈3N con N1( x ) = {i} se puede identificar con la coalición E= N2( x )∪{i} , tenemos que MA v( x + e i) = v(A(N2( x )∪{i})) = v(A(E)), y también: MA v( x − e i) = v(A(N2(x))) = v(A(E\{i})).Por tanto, el valor se describe ahora como: ξ1 i(v,A) = ∑ E⊆N:i∈E ∑ F⊆N\E (−1)|F| |E|+|F|[v(A(E)))−v(A(E\{i}))] (4.4) =∑ E⊆N:i∈E ∑ F⊆N\E (−1)|F| |E|+|F|hvA(E)−vA(E\{i})i.(4.5) Ahora, haciendo uso de la siguiente igualdad para la función beta: para todo a,b∈N , se verifica que (a−1)!(b−1)! (a+b−1)!=β(a,b) = b−1 ∑ r=0 (−1)r a+rb−1 r; tenemos que si r=|F|,a=|E|yb=n−|E|+1, obtenemos que ∑ F⊆N\E (−1)|F| |E|+|F|= n−|E| ∑ r=0n−|E| r(−1)r |E|+r=(|E|− 1)!(n−|E|)! n!.(4.6) Entonces, substituyendo lo anterior en (4.5), obtenemos ξ1=φ. ■ Proposición 4.2 El valor de 0 -autorización, para v∈GN y A∈AN , satisface que ξ0(v,A) = Sh(v|A(N)) , donde el juego v|A(N)∈GN viene dado por v|A(N)(E) = v(E∩A(N)) . En particular, se tiene que si la estructura de autorización es normal, A(N) = N, entonces ξ0(v,A) = Sh(v). Demostración. Sea r=0. La fórmula (4.1) tiene solo un sumatorio ξ0 i(v,A) = ∑ x∈3N xi=2 ∑ F⊆(N0(x)∪N1(x)) (−1)|F| ∥x∥w+|F1(x)|(MA v(x)−MA v(x−ei)). Como en el caso definido en la demostración de la proposición anterior, de (4.3) obtenemos que P0 x(i) = ∑ F⊆(N0(x)∪N1(x)) (−1)|F| ∥x∥w+|F1(x)|=0, 4.2 Una familia de valores para juegos con estructura de autorización 49 para x∈3Ncon xi=2 y N0(x)=/0. Entonces, ξ0 i(v,A) = ∑ x∈3N N0(x)=/0 xi=2 ∑ F⊆N1(x) (−1)|F| ∥x∥w+|F|(MA v(x)−MA v(x−ei)). Cada x ∈3N con N0( x ) = /0 y xi=2 se identifica con la coalición E⊆N por xj=2 si j∈E . Obtenemos de este modo que, MA v( x ) = v(E∩A(N)) y MA v( x − e i) = v((E\ {i})∩A(N)) . La fórmula anterior se escribe como ξ0 i(v,A) = ∑ E⊆N:i∈E ∑ F⊆N\E (−1)|F| |E|+|F|[v(E∩A(N)))−v((E\{i})∩A(N))] =∑ E⊆N:i∈E ∑ F⊆N\E (−1)|F| |E|+|F|v|A(N)(E)−v|A(N)(E\{i}). y usando de nuevo la igualdad anterior (4.6) y substituyendo en la expresión anterior obtenemos el resultado ξ0(v,A) = Sh(v|A(N)). ■ Definición 4.3 Sea A∈AN e i∈N , decimos que el jugador i no tiene poder posicional respecto a A si A(E)\A(E\{i})⊆{i} para cada E⊆N . Es decir, i no tiene poder posicional si su ausencia o ausencia en cualquier coalición no afecta a los jugadores autorizados a cooperar en dicha coalición. Aprovechando la definición anterior, podemos presentar la siguiente proposición. Proposición 4.3 Sea (v,A)∈GN×ANy los jugadores i,j∈Ntal que 1) el jugador jno tiene poder posicional, 2) el jugador ies un jugador nulo (ver Definición 1.17 apartado 2), 3) el jugador itiene poder de veto sobre j(ver Definición 2.17), 4) ningún jugador aparte de iyjdepende parcialmente de i(ver Definición 2.17). Entonces, se verifica que ξr i(v,A) = rξr j(v,A). Demostración. Sea v∈GN , A∈AN y i,j∈N tales que se cumplan las condiciones establecidas en la Proposición 4.3. Sea r∈[0,1]. Dado que jno tiene poder posicional, es claro que ξr j(v,A) = ∑ x∈3N xj=2 Pr x(j)(MA v(x)−MA v(x−ej)) lo cual, teniendo en cuenta que itiene poder de veto sobre j, es igual a ξr j(v,A) = ∑ x∈3N xj=2,xi=1 Pr x(j)(MA v(x)−MA v(x−ej)) 4.2 Una familia de valores para juegos con estructura de autorización 50 +∑ y∈3N yj=yi=2 Pr y(j)(MA v(y)−MA v(y−ej)) Para cada x∈βNcon xj=2 y xi=1 obtenemos Pr x(j) = ∑ F⊆(N0(x)∪N1(x)) i/∈F (−1)|F| ∥x∥w+r|F0(x)|+(1−r)|F1(x)| +∑ H⊆N0(x)∪N1(x) i/∈H (−1)|H∪{i}| ∥x∥w+r|H0(x)|+(1−r)|H1(x)∪{i}| =Pr x(i)−∑ H⊆N0(x)∪N1(x) i/∈H (−1)|H| ∥x∥w+1−r+r|H0(x)|+(1−r)|H1(x)| =Pr x(i)−∑ H⊆N0(x)∪N1(x) i/∈H (−1)|H| ∥x+ei∥w+r|H0(x+ei)|+(1−r)|H1(x+ei)| Sea y∈βNcon yj=yi=2, Pr y(j) = ∑ F⊆N0(y)∪N1(y) (−1)|F| ∥y∥w+r|F0(y)|+(1−r)|F1(y)|. Si identificamos ycon x = y − e i con xi=1 , entonces Pr y(i) coincide con el segundo término de la última diferencia en la expresión de Pr x(j). Como ies un jugador nulo, tenemos MA v(x)−MA v(x−ej) = MA v(x+ei)−MA v(x+ei−ej) = MA v(y)−MA v(y−ej). Así reducimos ξr j(v,A)a ξr j(v,A) = ∑ x∈3N xj=2,xi=1 Pr x(i)(MA v(x)−MA v(x−ej)).(4.7) Además, dado que i es un jugador nulo y ningún otro jugador aparte de i y j depende parcialmente de i, es claro que ξr i(v,A) = ∑ x∈3N xj=2,xi=1 rPr x(i)(MA v(x)−MA v(x−ei)) (4.8) Sea x∈3Ntal que xj=2,xi=1. Nótese que MA v(x−ei) = v(N2(x−ei)∩A(N1(x−ei)∪N2(x−ei))) =v(N2(x)∩A((N1(x)∪N2(x))\{i})) lo cual, teniendo en cuenta que itiene poder de veto sobre j, es igual a v((N2(x)\{j})∩A((N1(x)∪N2(x))\{i})) 4.3 Aplicación 51 lo cual, dado que ningún otro jugador aparte de iyjdepende parcialmente de i, es igual a v((N2(x)\{j})∩A(N1(x)∪N2(x))) =v(N2(x−ej)∩A(N1(x−ej)∪N2(x−ej))) =MA v(x−ej). Hemos probado que si x∈3N,xj=2 y xi=1, entonces MA v(x−ei) = MA v(x−ej).(4.9) De (4.7), (4.8) y (4.9), se sigue fácilmente que ξr i(v,A) = rξr j(v,A). ■ Por tanto, el coeficiente r se puede interpretar como la proporción entre el pago generado por el poder de veto y el generado únicamente por la cooperación activa. 4.3 Aplicación Mostramos aquí un escenario donde es necesario ajustar la ganancia derivada del poder de veto para modela situaciones de forma más justas. El primero de ellos se basa en la capacidad de explotación de un producto bajo patente. Así, consideramos dos empresas 1 y 2 . Cada una de ellas puede producir, digamos, un millón de unidades de un cierto componente, que se puede vender con una ganancia de una unidad monetaria cada uno. La empresa 1 está especializada en la producción de ampollas de vidrio, y la empresa 2 crea filamentos incandescentes. Ambas empresas pueden decidir ensamblar sus componentes (una unidad por una unidad) y producir una bombilla de alta duración que se puede vender con una ganancia de tres unidades cada una. Además, hay una tercera empresa que no produce ningún componente. Esta situación se puede modelar mediante un juego cooperativo clásico v (ver Definición 1.3 ), donde v(E)es la ganancia (en millones de unidades monetarias) que las empresas en Epueden generar cuando cooperan. Mostramos en la Tabla 4 los valores que toma la función característica. E{1} {2} {3} {1,2} {1,3} {2,3} {1,2,3} v(E)1 1 0 3 1 1 3 Tabla 4. Juego cooperativo. Con lo anterior, observamos que la empresa 3 es un jugador nulo en v . Ahora consideramos el siguiente escenario. La empresa 3 es titular de la patente sobre el componente que produce la empresa 2 ; y por tanto, la empresa 2 solo puede producir bajo autorización de la empresa 3 . Esta situación se puede modelar mediante la estructura de autorización A (ver Definición 2.16 ) definida en la tabla siguiente. E{1} {2} {3} {1,2} {1,3} {2,3} {1,2,3} A(E){1}/0 {3} {1} {1,3} {2,3} {1,2,3} Tabla 5. Estructura de autorización. 4.3 Aplicación 52 Figura 4.1: Digrafo de autorización. Esta estructura de autorización puede representarse por el digrafo expresado en la Figura 4.1. Se observa que la empresa 3 tiene poder de veto sobre la empresa 2 . Si calculamos el valor de autorización de (v,A)para esta situación (ver Definición 2.20), obtenemos φ(v,A) = 1 6(8,5,5). Esto implica que la empresa 3 aun siendo un jugador nulo en v consigue mediante el vector φ(v,A) el mismo pago que la empresa 2 . Esto puede verse como injusto o poco realista. En la práctica, la empresa 2 terminaría dando a la empresa 3 un porcentaje de las ganancias. La regla del 25% [ 34 ] establece que el 25% de la ganancia de la venta de un bien infractor es una tasa de regalía razonable. Proponemos exactamente 25% como porcentaje, dado que el jugador 3 es nulo y el jugador 2 solo depende del 3 , la proporción entre sus pagos debería ser 1/3 , es decir, si ψ(v,A)es el vector de pagos, entonces ψ3(v,A) = 1 3ψ2(v,A). Usando lo desarrollado en este capítulo, calculamos primeramente el juego multichoice MA v , obteniéndose para los vectores x∈3N, tales que MA v(x)=0, la Tabla: xMA v(x)xMA v(x) (0,2,1)1(2,1,0)1 (0,2,2)1(2,1,1)1 (1,2,1)1(2,1,2)1 (1,2,2)1(2,2,0)1 (2,0,0)1(2,2,1)3 (2,0,1)1(2,2,2)3 (2,0,2)1− − En consecuencia, como nuestro parámetro r indica la proporción entre lo que se lleva el propietario de los derechos y lo que se lleva el fabricante, aplicando la regla del 25% , r=1 3 . Por tanto, ξ1 3(v,A) = 40 28,33 28,11 28. Otra opción para obtener repartos en situaciones con estructuras de autorización sería, por ejemplo, tomar combinaciones convexas entre el valor de Shapley clásico (ver Definición 1.19 ) y el valor de autorización (ver Definición 2.20 ). En nuestro ejemplo, vale la pena señalar que nuestro vector de pagos obtenido no es combinación convexa de los vectores ξ0(v,A) = Sh(v) = 3 2,3 2,0 yξ1(v,A) = φ(v,A) = 8 6,5 6,5 6. 4.3 Aplicación 53 Podríamos plantearnos si definiendo un valor como combinación convexa del valor de Shapley y el valor de autorización podríamos obtener un valor que permitiera resolver el problema tratado. Para ello, definimos para α∈[0,1]el valor τα:GN×AN→RN, dado por τα(v,A) = (1−α)Sh(v)+αφ(v,A) para todo (v,A)∈GN×AN. Observamos que si α=0 obtenemos el valor de Shapley, y si α=1 , obtenemos el valor de autorización. Mostramos los valores de la familia aplicados a un juego en particular en los siguientes ejemplos. Ejemplo 4.1 Supongamos la situación descrita en el Ejemplo 2.4 . Para cualquier α∈[0,1] , calculamos τα(v,A) = (1−α)1 2(0,0,0,3,1)+α1 20(1,1,6,6,6) = 1 20 (α,α,6α,30−24α,10−4α). Por ejemplo, si α=0.5 entonces obtenemos τ0.5(v,A) = 1 40(1,1,6,36,16). Basta observar que A(N) = {1,2,3,4} y que v(A(N)) = 1 , por lo que v(N) = 2 . Entonces, si α=0.5, se tiene que 5 ∑ i=1 τ0.5 i(v,A) = 3 2=v(A(N)). ■ En este ejemplo se muestra un primer problema de esta familia de valores. No son en general eficientes salvo que la estructura de autorización sea normal. Además, veremos en el siguiente ejemplo que no verifica la propiedad de proporcionalidad expuesta en la Proposición 4.3. Ejemplo 4.2 Consideramos el conjunto de jugadores N={1,2,3,4} con la estructura de permiso disyuntiva S(ver Sección 2.3) descrita en la Figura 4.2. Figura 4.2: Estructura de permiso sobre N={1,2,3,4} En esta situación, consideramos u{4} como juego y AS d el operador de autorización dado por el enfoque disyuntivo de la estructura de permiso S (ver Definición 2.15 ). Tenemos que AS d(E) = A(E), donde Aviene representada en la siguiente Tabla 2. 4.4 Caracterización del valor de r-autorización 54 E A(E)E A(E)E A(E)E A(E) /0 /0 {1} {1} {2} {2} {3}/0 {4}/0 {1,2} {1,2} {1,3} {1,3} {1,4} {1} {2,3} {2,3} {2,4} {2} {3,4}/0 {1,2,3} {1,2,3} {1,2,4} {1,2} {1,3,4} {1,3,4} {2,3,4} {2,3,4}N{1,2,3,4} Tabla 2. Operador de autorización. El valor de Shapley viene dado por Sh(u{4})=(0,0,0,1) y el valor de autorización es φ(u{4},AS d) = 1 12(1,1,5,5). Si volvemos a tomar α=0.5, entonces obtenemos la solución τ0.5(u{4},AS d) = 1 24(1,1,5,17). Como el jugador 3 es nulo en u{4} y tiene poder de veto sobre el jugador necesario 4 en u{4} , ese número αdebería ser τ0.5 3(u{4},AS d) τ0.5 4(u{4},AS d)=5 17. Tomemos ahora el mismo juego, u{4} , pero con el operador de autorización B definido para todo E⊆Npor B(E) = Esi 3,4∈E E\{4}en otro caso. Obtenemos el valor τ0.5(u{4},B) = 1 2Sh(u{4})+ 1 2φ(u{4},B) = 1 2(0,0,0,1)+ 1 4(0,0,1,1) = 1 4(0,0,1,3). Observamos que el jugador 3 mantiene el poder de veto sobre 4 en B, pero τ0.5 3(u{4},B)=5 17τ0.5 4(u{4},B). ■ 4.4 Caracterización del valor de r-autorización Sea ψ un valor para juegos con estructura de autorización (ver Definición 2.19 ). Para caracterizar el valor de r-autorización consideramos los siguientes axiomas: (A1) Eficiencia sobre el conjunto autorizado. Para todo (v,A)∈GN×AN se verifica: ∑i∈Nψi(v,A) = v(A(N)). El valor reparte completamente la ganancia obtenida por parte del conjunto de jugadores autorizados. (A2) Aditividad. Si v,w∈GNyA∈AN, entonces: ψ(v+w,A) = ψ(v,A)+ψ(w,A). La ganancia obtenida por la suma de dos juegos con la misma estructura de autorización es igual a la suma de las ganancias que produce cada uno de los juegos por separados. 4.4 Caracterización del valor de r-autorización 55 (A3) Jugador irrelevante. Si i∈Nes irrelevante para (v,A), entonces: ψi(v,A) = 0. El jugador irrelevante obtiene una ganancia nula en el reparto. (A4*) Igualdad de trato para los jugadores necesarios. Sean v∈GN e i,j∈N jugadores necesarios para v. Para todo A∈ANse tiene ψi(v,A) = ψj(v,A). La igualdad de trato para los jugadores necesarios establece que todos los jugadores necesarios obtienen el mismo pago. (A5*) Justicia proporcional. Sea r∈[0,1] . Supongamos que v∈GN , A∈AN , T⊆N , i,j∈T eies un jugador nulo en v. Recordemos que el operador AT,j∈ANviene definido por AT,j(E):=A(E)if T⊈E, A(E)∪ { j}if T⊆E. para todo E⊆N. Entonces, ψiv,AT,j−ψi(v,A) = rψjv,AT,j−ψj(v,A). Nótese que si j∈A(T) , entonces AT,j=A . Por lo tanto, la expresión anterior no es trivial solo si j∈ A(T). La justicia proporcional tiene la siguiente interpretación. Supongamos, en primer lugar que tenemos v∈GN , A∈AN , T⊆N , i∈T un jugador nulo en v y j∈T tal que en caso de que se formara una coalición T , j no podría cooperar, es decir, j/∈A(T) . Impongamos ahora, que de alguna manera, la coalición T adquiere el poder de autorizar a j para cooperar. Observamos que la ganancia adicional que obtendría i provendría exclusivamente de dar permiso a j para cooperar dentro de T , mientras que la ganancia adicional obtenida por j provendría exclusivamente de cooperar activamente dentro de T . Teniendo en cuenta los pesos ( r y 1 ) que previamente se han considerado justos para, respectivamente, autorizar y cooperar activamente, la propiedad A5∗ podría interpretarse diciendo que: la ganancia del jugador que autoriza es proporcional a la ganancia del jugador que participa con constante de proporcionalidad r. En el siguiente teorema mostraremos que las cinco propiedades vistas anteriormente determinan de forma única al valor de r-autorización. Teorema 4.1 Sea r∈[0,1] . Un valor para juegos con estructura de autorización en N es igual al valor de r -autorización si y solo si satisface las propiedades de eficiencia sobre el conjunto de autorización (A1), aditividad (A2), propiedad del jugador irrelevante (A3 ), igualdad de trato para los jugadores necesarios (A4*) y justicia proporcional (A5*). Demostración. En primer lugar, vamos a demostrar que ξr , el valor de r -autorización, satisface las cinco propiedades mencionadas. EFICIENCIA SOBRE EL CONJUNTO DE AUTORIZACIÓN. 4.4 Caracterización del valor de r-autorización 56 Sean v∈GN y A∈AN . Está claro que, para cada x ∈3N ,x ∧ 2 = x. Usando el axioma (H1) de la caracterización de Φw, y la definición de vA, obtenemos ∑ i∈N ξr i(v,A) = ∑ i∈N Φw 2,iMA v=MA v(2) = v(A(N)). ADITIVIDAD. Sean v,w∈GN , A∈AN e i∈N . Por aditividad, tenemos que MA v+w=MA v+MA w . Si además utilizamos la aditividad (H2) de Φw, obtenemos ξr i(v+w,A) = Φw 2,iMA v+w=Φw 2,i(MA v+MA w) =Φw 2,i(MA v)+Φw 2,i(MA w) = ξr i(v,A)+ξr i(w,A). PROPIEDAD DEL JUGADOR IRRELEVANTE . Sea v∈GN , A∈AN e i∈N ser tal que i sea un jugador irrelevante en (v,A) . Debemos demostrar que ξr i(v,A) = 0 . Teniendo en cuenta la definición de ξr i(v,A) , basta demostrar que para cada x∈3Ncon xi∈ {1,2}, MA v(x) = MA v(x−ei).(4.10) Sea x ∈3N . Si xi=2 , la igualdad (4.10) se deriva del hecho de que i es un jugador nulo en V ya que N2(x−ei)∩A(N2(x−ei)∪N1(x−ei)) = [N2(x)∩A(N2(x)∪N2(x))]\{i}. Suponemos ahora que xi=1. Por tanto, tenemos MA v(x) = v(N2(x)∩A(N1(x)∪N2(x))) (4.11) Observamos que vA(x−ei) = v(N2(x)∩A((N1(x)∪N2(x))\{i})).(4.12) Tenga en cuenta que los jugadores en A(N1( x )∪N2( x ))\A((N1( x )∪N2( x ))\{i}) son jugadores nulos en V, ya que dependen parcialmente de isegún Aeies irrelevante en (v,A). Por lo tanto, v(N2(x)∩A(N1(x)∪N2(x))) = v(N2(x)∩A((N1(x)∪N2(x))\{i})), de donde, junto con (4.11) y (4.12), concluimos (4.10). IGUALDAD DE TRATO PARA LOS JUGADORES NECESARIOS. Sean v∈GN,A∈ANei,j∈Ntales que i,json jugadores necesarios en v. Tenemos que ξr i(v,A) = ∑ x∈3N xi=2 ∑ F⊆(N0(x)∪N1(x)) (−1)|F| ∥x∥w+r|F0(x)|+(1−r)|F1(x)|MA v(x) =∑ x∈3N xi=2 xj=2 ∑ F⊆(N0(x)∪N1(x)) (−1)|F| ∥x∥w+r|F0(x)|+(1−r)|F1(x)|MA v(x).(4.13) 4.4 Caracterización del valor de r-autorización 57 De forma análoga podemos obtener la misma expresión para ξr j(v,A). JUSTICIA PROPORCIONAL. Suponemos que v∈GN , A∈AN , T⊆N , i,j∈T e i es un jugador nulo en v . Vamos a probar que ξr iv,AT,j−ξr i(v,A) = r(ξr jv,AT,j−ξr j(v,A)).(4.14) Por un lado tenemos que ξr iv,AT,j−ξr i(v,A) = =∑ x∈3N xi=1 ∑ F⊆(N0(x)∪N1(x))\{i} (−1)|F|r ∥x∥w+r|F0(x)|+(1−r)|F1(x)|MAT,j v(x)−MAT,j v(x−ei) +∑ x∈3N xi=2 ∑ F⊆(N0(x)∪N1(x)) (−1)|F| ∥x∥w+r|F0(x)|+(1−r)|F1(x)|MAT,j v(x)−MAT,j v(x−ei) −∑ x∈3N xi=1 ∑ F⊆(N0(x)∪N1(x))\{i} (−1)|F|r ∥x∥w+r|F0(x)|+(1−r)|F1(x)|MA v(x)−MA v(x−ei) −∑ x∈3N xi=2 ∑ F⊆(N0(x)∪N1(x)) (−1)|F| ∥x∥w+r|F0(x)|+(1−r)|F1(x)|MA v(x)−MA v(x−ei) Y dado que ies un jugador nulo en v, obtenemos =∑ x∈3N xi=1 ∑ F⊆(N0(x)∪N1(x))\{i} (−1)|F|r ∥x∥w+r|F0(x)|+(1−r)|F1(x)|MAT,j v(x)−MAT,j v(x−ei) −∑ x∈3N xi=1 ∑ F⊆(N0(x)∪N1(x))\{i} (−1)|F|r ∥x∥w+r|F0(x)|+(1−r)|F1(x)|MA v(x)−MA v(x−ei) Teniendo en cuenta que AT,j(E) = A(E) para todo E⊆N\ {i} , entonces la igualdad anterior sigue como =∑ x∈3N xi=1 ∑ F⊆(N0(x)∪N1(x))\{i} (−1)|F|r ∥x∥w+r|F0(x)|+(1−r)|F1(x)|MAT,j v(x)−MA v(x) Si ahora tenemos en cuenta que AT,j(E)\A(E)⊆ { j} para todo E⊆N , entonces la igualdad anterior se escribe como =∑ x∈3N xi=1 xj=2 ∑ F⊆(N0(x)∪N1(x))\{i} (−1)|F|r ∥x∥w+r|F0(x)|+(1−r)|F1(x)|MAT,j v(x)−MA v(x).(4.15) 5.1 Valor de comunicación r-justo 64 separa. Figura 5.1: Estructura de comunicación de (u{1,3},L). Tomando u{1,3} como el juego que modela nuestra situación, obtenemos que el valor de Myerson es Y(u{1,3},L) = 1 3,1 3,1 3. Observamos que el aeropuerto 2 es un jugador nulo (ver Definición 1.17 apartado 2) en el juego u{1,3} . Sin embargo, recibe la misma cantidad como recompensa que el resto de aeropuertos, que han sido jugadores necesarios. En otras palabras, un aeropuerto con el rol pasivo de permitir la comunicación obtiene el mismo pago con el valor de Myerson que los aeropuertos que generan activamente todas las ganancias. ■ En casi cualquier contexto realista, la distribución de beneficios que se muestra en el ejemplo anterior estaría fuera de lugar. Nuestro objetivo es presentar una solución para juegos restringidos por grafos (ver Definición 2.9 ) que permita ponderar el valor del poder posicional. A lo largo del capítulo, definiremos un nuevo valor para los juegos restringidos por grafos que pondera de una forma distinta el poder posicional y la cooperación activa. Para ello, seguiremos un procedimiento ampliamente utilizado en la literatura para obtener valores de juegos cooperativos con estructura combinatoria, que consiste en, a partir de la función característica del juego y su estructura combinatoria, obtener una nueva función característica (denominada juego restringido). Luego, se aplica un concepto de solución al juego restringido. En nuestro caso, el punto clave es que el juego restringido no será un juego cooperativo en forma de coalición, sino un juego multichoice tal y como detallamos en el capítulo anterior. Sea el juego (v,L)∈CSGN restringido por grafos (ver Definición 2.8 ). Definimos un juego multichoice ML v (ver Sección 1.4 ), en el cual, cuando se forma una coalición, los jugadores de N pueden realizar tres acciones diferentes. La acción σ0 consiste en no hacer nada, es decir, no cooperar activamente ni permitir la comunicación entre otros jugadores. La acción σ1 consiste en no cooperar activamente pero sí permitir la comunicación; y la acción σ2 consiste tanto en cooperar activamente como en permitir la comunicación. Por lo tanto, el espacio de acción será 3N, donde identificamos 3 ={0,1,2}. Tal y como se comentó en la Sección 2.2 , donde la cooperación estaba sujeta a la comunicación entre los jugadores, si una coalición E⊆N está internamente conectada en el grafo L , es decir, si todos los jugadores de E pueden comunicarse entre sí directa e indirectamente, sin la ayuda de jugadores ajenos a E , entonces los integrantes de la coalición pueden coordinar completamente sus acciones y obtener el valor v(E) respecto del juego original. Si por contra, la coalición E no está conectada internamente, entonces no todos los jugadores que conforman la coalición E pueden comunicarse entre sí sin la ayuda de jugadores externos a la coalición, por lo que, se considera la partición E/L que divide a E en componentes conexas de comunicación. Así, en este caso, el mayor beneficio que pueden lograr los jugadores de E teniendo en cuenta las 5.2 Valor de comunicación r-justo para r=0yr=165 restricciones impuestas por L , después de coordinar sus acciones dentro de cada una de las componentes conexas, será la suma de los beneficios de cada componente conexa. Razonando de forma análoga en nuestro modelo, tenemos que el pago que obtendrá la coalición multichoice x ∈3N sujeta a las restricciones de comunicación dadas por L será igual al pago alcanzable en el juego original v por los jugadores que estén dispuestos a cooperar activamente en cada una de las componentes conexas formadas por todos aquellos jugadores que permiten la comunicación. Por tanto, dicho pago será igual a ML v(x) = ∑ E∈(N1(x)∪N2(x))/L v(E∩N2(x)); (5.1) para cada x∈3N, donde Nl(x):={j∈N:xj=l}con l∈ {0,1,2}es el conjunto de jugadores que actúan a nivel l. Ahora, aplicaremos el valor definido para juegos multichoice Φw (ver Definición 1.22 ) al juego ML v . Para este fin, usaremos los pesos w(0) = 0,w(1) = r∈[0,1] y w(2) = 1 . Nos interesan los beneficios que recibirán los jugadores cuando decidan cooperar activamente. De esta forma, obtenemos el vector de pagos Φw 2,i(ML v)dado por Φw 2,i(ML v) = =∑ x∈3N xi=1 ∑ F⊆(N0(x)∪N1(x))\{i} (−1)|F|r ∥x∥w+r|F0(x)|+(1−r)|F1(x)|(ML v(x)−ML v(x−ei)) +∑ x∈3N xi=2 ∑ F⊆(N0(x)∪N1(x)) (−1)|F| ∥x∥w+r|F0(x)|+(1−r)|F1(x)|(ML v(x)−ML v(x−ei)) donde se ha utilizado la siguiente notación: si x ∈3N , l∈ {0,1,2} y F⊆N , entonces Fl( x ) = {j∈F:xj=l} , ∥ x ∥w=∑j∈Nw(xj) ye i∈ {0,1}N viene dado por ei i=1 y eij=0 para cada j∈N\{i}. Definición 5.1 El valor de comunicación r -justo es el valor Λr para juegos restringidos por grafos definido como Λr i(v,L) = Φw 2,iML v para cada (v,L)∈CSGNy cada i∈N. 5.2 Valor de comunicación r-justo para r=0yr=1 Una vez definido Λr , surge la pregunta de qué valores se obtienen para r=0 y r=1 . Las dos proposiciones siguientes responden a esto. Proposición 5.1 El valor de comunicación 1 -justo es igual al valor de Myerson, es decir, Λ1=Y . Demostración. Sean (v,L)∈CSGNei∈N. Tenemos que Λ1 i(v,L) = ∑ x∈3N xi=1 ∑ F⊆(N0(x)∪N1(x))\{i} (−1)|F| ∥x∥w+|F0(x)|(ML v(x+ei)−ML v(x−ei)). 5.2 Valor de comunicación r-justo para r=0yr=166 Dado x ∈3N con xi=1 , si escribimos cada F⊆(N0( x )∪N1( x )) \ {i} como F=H∪R con H⊆N0(x)\{i}yR⊆N1(x)\{i}, obtenemos ∑ F⊆(N0(x)∪N1(x))\{i} (−1)|F| ∥x∥w+|F0(x)|=∑ H⊆N0(x)\{i} (−1)|H| ∥x∥w+|H|∑ R⊆N1(x)\{i} (−1)|R|. Obsérvese que si N1(x)\{i} =/0, entonces ∑R⊆N1(x)\{i}(−1)|R|=0. Por lo tanto, Λ1 i(v,L) = ∑ x∈3N N1(x)={i} ∑ F⊆N0(x)\{i} (−1)|F| ∥x∥w+|F|(ML v(x+ei)−ML v(x−ei)) =∑ {E⊆N:i∈E} ∑ F⊆N\E (−1)|F| |E|+|F| ∑ E∈E/L v(E)−∑ T∈(E\{i})/L v(T)! =∑ {E⊆N:i∈E} ∑ F⊆N\E (−1)|F| |E|+|F|(vL(E)−vL(E\{i})).(5.2) Teniendo en cuenta que para todo a,b∈N, la función beta verifica (a−1)!(b−1)! (a+b−1)!=β(a,b) = b−1 ∑ r=0 (−1)r a+rb−1 r. Tenemos que la siguiente igualdad se desprende de la expresión anterior de la función beta, ∑ F⊆N\E (−1)|F| |E|+|F|= n−|E| ∑ r=0n−|E| r(−1)r |E|+r=(|E|− 1)!(n−|E|)! n!.(5.3) Sustituyendo en (5.2) la expresión anterior, obtenemos Λ1 i(v,L) = Yi(v,L).■ Proposición 5.2 Si (v,L)∈CSGN, entonces Λ0(v,L) = ∑ T∈N/L Sh(v|T), donde v|T∈GN se define como v|T(E) = v(E∩T) para cada T∈N/L . En particular, si L es conexo, entonces Λ0(v,L) = Sh(v). Demostración. Sean (v,L)∈CSGNei∈N. Tenemos Λ0 i(v,L) = ∑ x∈3N xi=2 ∑ F⊆(N0(x)∪N1(x)) (−1)|F| ∥x∥w+|F1(x)|(ML v(x)−ML v(x−ei)). Siguiendo un razonamiento similar al usado en la Proposición 5.1, podemos obtener que si x∈3N,xi=2 y N0(x)=/0, entonces ∑ F⊆(N0(x)∪N1(x)) (−1)|F| ∥x∥w+|F1(x)|=0. 5.3 Caracterización del valor de comunicación r-justo 67 Por lo tanto, Λ0 i(v,L) = ∑ x∈3N N0(x)=/0 xi=2 ∑ F⊆N1(x) (−1)|F| ∥x∥w+|F|(ML v(x)−ML v(x−ei)) =∑ {E⊆N:i∈E} ∑ F⊆N\E (−1)|F| |E|+|F| ∑ T∈N/L v(T∩E)−∑ T∈N/L v(T∩(E\{i}))! =∑ T∈N/L ∑ {E⊆N:i∈E} ∑ F⊆N\E (−1)|F| |E|+|F|(v|T(E)−v|T(E\{i})) que, por (5.3), es igual a ∑ T∈N/L ∑ {E⊆N:i∈E} (|E|−1)!(n−|E|)! n!(v|T(E)−v|T(E\{i})) = ∑ T∈N/L Shi(v|T) ■ Ejemplo 5.2 Considerando de nuevo al Ejemplo 5.1 , podemos considerar r=1 10 , obteniéndose Λ1 10 (u{1,3},L) = 10 21,1 21,10 21. Este valor de r establece una ponderación del poder posicional más adecuada, en algunos contextos, que el valor 1 (correspondiente al valor de Myerson, según la proposición anterior), teniéndose en cuenta que el pago recibido por el jugador 2 debería ser, en ciertas situaciones significativamente menor que el pago recibido por los jugadores que generan activamente las ganancias. ■ Uno podría preguntarse si Λr es alguna combinación convexa de Λ0 y Λ1 . En la Aplicación dada en la última sección mostraremos que la respuesta es negativa en general. 5.3 Caracterización del valor de comunicación r-justo Ahora veremos una caracterización de Λr . Para caracterizar el valor de comunicación r -justo consideraremos las siguientes propiedades sobre un valor genérico para juegos restringidos por grafos Ψ. (C1) Eficiencia por componentes. Si (v,L)∈CSGN , entonces ∑{T∈N/L:i∈T}Ψi(v,L) = v(T) . Esto significa que el valor reparte completamente la ganancia de cada componente conexa entre los jugadores que participan en la misma. (C2) Aditividad. Si (v,L),(w,L)∈CSGN, entonces Ψ(v+w,L) = Ψ(v,L)+Ψ(w,L). La aditividad establece que el pago del juego constituido por la suma de dos juegos es igual a la suma de los pagos de dichos dos juegos originales. 5.3 Caracterización del valor de comunicación r-justo 68 (C3) Justicia para jugadores nulos. Sean (v,L)∈CSGN e i j ∈L tales que i,j sean jugadores nulos en v(ver Definición 1.17 apartado 2). Entonces, Ψi(v,L)−Ψi(v,L−i j) = Ψj(v,L)−Ψj(v,L−i j). La eliminación de una arista de comunicación entre dos jugadores nulos implica la misma pérdida de ganancia para ambos jugadores implicados. (C4) Justicia para jugadores necesarios. Sean (v,L)∈CSGN e i j ∈L tales que i,j sean jugadores necesarios en v(ver Sección 2.4 propiedad A4). Entonces, Ψi(v,L)−Ψi(v,L−i j) = Ψj(v,L)−Ψj(v,L−i j). La eliminación de una arista de comunicación entre dos jugadores necesarios implica la misma pérdida de ganancia para ambos jugadores implicados. (C5) r -Justicia. Consideramos r∈[0,1] . Sean (v,L)∈CSGN e i j ∈L tales que i es un jugador nulo en vyjes un jugador necesario en v. Entonces, Ψi(v,L)−Ψi(v,L−i j) = rΨj(v,L)−Ψj(v,L−i j). La ganancia que el jugador nulo obtiene tras perder la comunicación con un jugador necesario es una proporción de la ganancia del jugador necesario (ver Sección 2.4 ) tras perder la comunicación con el jugador nulo. En el siguiente teorema mostramos una caracterización del valor de comunicación r-justo. Teorema 5.1 Sea r∈[0,1] . El valor Λr satisface las cinco propiedades mencionadas anteriormente. Demostración. Vamos a probar que el valor satisface cada una de las anteriores propiedades. EFICIENCIA POR COMPONENTES. Sea (v,L)∈CSGNyT∈N/L. Sean VT,VN\T∈M G 3Ndefinidos como VT(x):=∑ {E∈(N1(x)∪N2(x))/L:E⊆T} v(E∩N2(x)) VN\T(x):=∑ {E∈(N1(x)∪N2(x))/L:E⊆N\T} v(E∩N2(x)) para cada x∈3N. Del hecho de que T∈N/Lse obtiene que ML v=VT+VN\T.(5.4) Además, podemos ver que Φw 2,i(VT) = 0 para todo i∈N\T(5.5) y Φw 2,i(VN\T) = 0 para todo i∈T.(5.6) 5.3 Caracterización del valor de comunicación r-justo 69 Por (5.4) y la linealidad de Φw 2,i(H2), tenemos que ∑ i∈T Λr i(v,L) = ∑ i∈T Φw 2,i(ML v) = ∑ i∈T Φw 2,i(VT) + ∑ i∈T Φw 2,i(VN\T), el cual, por (5.5), (5.6) y la propiedad H1 de Φwvista en la Sección 1.4, es igual a ∑ i∈N Φw 2,i(VT) = VT(2) = v(T). ADITIVIDAD. Sean v,w∈GN , L∈2LN e i∈N . Está claro que ML v+w=ML v+ML w . Si además utilizamos la linealidad de Φw(H2), obtenemos Λr i(v+w,L) = Φw 2,iML v+w=Φw 2,i(ML v+ML w) =Φw 2,i(ML v)+Φw 2,i(ML w) = Λr i(v,L)+Λr i(w,L). JUSTICIA PARA JUGADORES NULOS. Sean v∈GN , L∈2LN e i j ∈L tales que i,j sean jugadores nulos en v (ver Definición 1.17 apartado 2), tenemos que Λr i(v,L)−Λr i(v,L−i j) = =∑ x∈3N xi=1 ∑ F⊆(N0(x)∪N1(x))\{i} (−1)|F|r ∥x∥w+r|F0(x)|+(1−r)|F1(x)|ML v(x)−ML v(x−ei) +∑ x∈3N xi=2 ∑ F⊆(N0(x)∪N1(x)) (−1)|F| ∥x∥w+r|F0(x)|+(1−r)|F1(x)|ML v(x)−ML v(x−ei) −∑ x∈3N\{0,1}N xi=1 ∑ F⊆(N0(x)∪N1(x))\{i} (−1)|F|r ∥x∥w+r|F0(x)|+(1−r)|F1(x)|ML−i j v(x)−ML−i j v(x−ei) −∑ x∈3N xi=2 ∑ F⊆(N0(x)∪N1(x)) (−1)|F| ∥x∥w+r|F0(x)|+(1−r)|F1(x)|ML−i j v(x)−ML−i j v(x−ei) por lo que, teniendo en cuenta que ies un jugador nulo en v, es igual a =∑ x∈3N xi=1 ∑ F⊆(N0(x)∪N1(x))\{i} (−1)|F|r ∥x∥w+r|F0(x)|+(1−r)|F1(x)|ML v(x)−ML v(x−ei) −∑ x∈3N\{0,1}N xi=1 ∑ F⊆(N0(x)∪N1(x))\{i} (−1)|F|r ∥x∥w+r|F0(x)|+(1−r)|F1(x)|ML−i j v(x)−ML−i j v(x−ei) 5.3 Caracterización del valor de comunicación r-justo 70 por lo que, del hecho de que ML v(x) = ML−i j v(x)para cada x∈3Ntales que xi=0, es igual a =∑ x∈3N xi=1 ∑ F⊆(N0(x)∪N1(x))\{i} (−1)|F|r ∥x∥w+r|F0(x)|+(1−r)|F1(x)|ML v(x)−ML−i j v(x) lo cual, del hecho de que ML v(x) = ML−i j v(x)para cada x∈3Ntales que xj=0, es igual a =∑ x∈3N xi=1 xj=1 ∑ F⊆(N0(x)∪N1(x))\{i} (−1)|F|r ∥x∥w+r|F0(x)|+(1−r)|F1(x)|ML v(x)−ML−i j v(x) +∑ x∈3N xi=1 xj=2 ∑ F⊆(N0(x)∪N1(x))\{i} (−1)|F|r ∥x∥w+r|F0(x)|+(1−r)|F1(x)|ML v(x)−ML−i j v(x) =∑ x∈3N xi=1 xj=1 ∑ F⊆(N0(x)∪N1(x))\{i,j} (−1)|F|r ∥x∥w+r|F0(x)|+(1−r)|F1(x)|ML v(x)−ML−i j v(x) +∑ x∈3N xi=1 xj=1 ∑ F⊆(N0(x)∪N1(x))\{i,j} (−1)|F∪{ j}|r ∥x∥w+r|(F∪{ j})0(x)|+(1−r)|(F∪{ j})1(x)|ML v(x)−ML−i j v(x) +∑ x∈3N xi=1 xj=2 ∑ F⊆(N0(x)∪N1(x))\{i} (−1)|F|r ∥x∥w+r|F0(x)|+(1−r)|F1(x)|ML v(x)−ML−i j v(x) =∑ x∈3N xi=1 xj=1 ∑ F⊆(N0(x)∪N1(x))\{i,j} (−1)|F|r ∥x∥w+r|F0(x)|+(1−r)|F1(x)|ML v(x)−ML−i j v(x) +∑ x∈3N xi=1 xj=1 ∑ F⊆(N0(x)∪N1(x))\{i,j} (−1)|F|+1r ∥x∥w+r|F0(x)|+(1−r)(|F1(x)|+1)ML v(x)−ML−i j v(x) +∑ x∈3N xi=1 xj=2 ∑ F⊆(N0(x)∪N1(x))\{i} (−1)|F|r ∥x∥w+r|F0(x)|+(1−r)|F1(x)|ML v(x)−ML−i j v(x) lo cual, teniendo en cuenta que jes un jugador nulo en v, es igual a =∑ x∈3N xi=1 xj=1 ∑ F⊆(N0(x)∪N1(x))\{i,j} (−1)|F|r ∥x∥w+r|F0(x)|+(1−r)|F1(x)|ML v(x)−ML−i j v(x) +∑ x∈3N xi=1 xj=1 ∑ F⊆(N0(x)∪N1(x))\{i,j} (−1)|F|+1r ∥x∥w+r|F0(x)|+(1−r)(|F1(x)|+1)ML v(x)−ML−i j v(x) 5.3 Caracterización del valor de comunicación r-justo 71 +∑ x∈3N xi=1 xj=2 ∑ F⊆(N0(x)∪N1(x))\{i} (−1)|F|r ∥x∥w+r|F0(x)|+(1−r)|F1(x)|ML v(x−ej)−ML−i j v(x−ej) =∑ x∈3N xi=1 xj=1 ∑ F⊆(N0(x)∪N1(x))\{i,j} (−1)|F|r ∥x∥w+r|F0(x)|+(1−r)|F1(x)|ML v(x)−ML−i j v(x) +∑ x∈3N xi=1 xj=1 ∑ F⊆(N0(x)∪N1(x))\{i,j} (−1)|F|+1r ∥x∥w+r|F0(x)|+(1−r)(|F1(x)|+1)ML v(x)−ML−i j v(x) +∑ x∈3N xi=1 xj=1 ∑ F⊆(N0(x+ej)∪N1(x+ej))\{i} (−1)|F|r ∥x+ej∥w+r|F0(x+ej)|+(1−r)|F1(x+ej)|ML v(x)−ML−i j v(x) =∑ x∈3N xi=1 xj=1 ∑ F⊆(N0(x)∪N1(x))\{i,j} (−1)|F|r ∥x∥w+r|F0(x)|+(1−r)|F1(x)|ML v(x)−ML−i j v(x) +∑ x∈3N xi=1 xj=1 ∑ F⊆(N0(x)∪N1(x))\{i,j} (−1)|F|+1r ∥x∥w+r|F0(x)|+(1−r)(|F1(x)|+1)ML v(x)−ML−i j v(x) +∑ x∈3N xi=1 xj=1 ∑ F⊆(N0(x)∪N1(x))\{i,j} (−1)|F|r ∥x∥w+1−r+r|F0(x)|+(1−r)|F1(x)|ML v(x)−ML−i j v(x) =∑ x∈3N xi=1 xj=1 ∑ F⊆(N0(x)∪N1(x))\{i,j} (−1)|F|r ∥x∥w+r|F0(x)|+(1−r)|F1(x)|ML v(x)−ML−i j v(x). Basta notar que en la última expresión iyjson intercambiables. JUSTICIA PARA JUGADORES NECESARIOS. Sean v∈GN , G= (N,L)∈2LN e i j ∈L tales que i,j sean jugadores necesarios en v (ver Sección 2.4 propiedad A4). Tenemos que Λr i(v,L)−Λr i(v,L−i j) = =∑ x∈3N xi=1 ∑ F⊆(N0(x)∪N1(x))\{i} (−1)|F|r ∥x∥w+r|F0(x)|+(1−r)|F1(x)|ML v(x)−ML v(x−ei) +∑ x∈3N xi=2 ∑ F⊆(N0(x)∪N1(x)) (−1)|F| ∥x∥w+r|F0(x)|+(1−r)|F1(x)|ML v(x)−ML v(x−ei) 5.3 Caracterización del valor de comunicación r-justo 72 −∑ x∈3N\{0,1}N xi=1 ∑ F⊆(N0(x)∪N1(x))\{i} (−1)|F|r ∥x∥w+r|F0(x)|+(1−r)|F1(x)|ML−i j v(x)−ML−i j v(x−ei) −∑ x∈3N xi=2 ∑ F⊆(N0(x)∪N1(x)) (−1)|F| ∥x∥w+r|F0(x)|+(1−r)|F1(x)|ML−i j v(x)−ML−i j v(x−ei) lo cual, teniendo en cuenta que ies un jugador necesario en v, es igual a =∑ x∈3N xi=2 ∑ F⊆(N0(x)∪N1(x)) (−1)|F| ∥x∥w+r|F0(x)|+(1−r)|F1(x)|ML v(x)−ML−i j v(x) que, dado que jes un jugador necesario en v, es igual a =∑ x∈3N xi=2 xj=2 ∑ F⊆(N0(x)∪N1(x)) (−1)|F| ∥x∥w+r|F0(x)|+(1−r)|F1(x)|ML v(x)−ML−i j v(x), donde podemos intercambiar iyj. r-JUSTICIA. Sean v∈GN , G= (N,L)∈2LN e i j ∈L tales que i es un jugador nulo en v y j es un jugador necesario en v. Nuestro objetivo es demostrar que Λi(v,L)−Λi(v,L−i j) = rΛj(v,L)−Λj(v,L−i j). Por un lado tenemos Λr i(v,L)−Λr i(v,L−i j) = =∑ x∈3N xi=1 ∑ F⊆(N0(x)∪N1(x))\{i} (−1)|F|r ∥x∥w+r|F0(x)|+(1−r)|F1(x)|ML v(x)−ML v(x−ei) +∑ x∈3N xi=2 ∑ F⊆(N0(x)∪N1(x)) (−1)|F| ∥x∥w+r|F0(x)|+(1−r)|F1(x)|ML v(x)−ML v(x−ei) −∑ x∈3N\{0,1}N xi=1 ∑ F⊆(N0(x)∪N1(x))\{i} (−1)|F|r ∥x∥w+r|F0(x)|+(1−r)|F1(x)|ML−i j v(x)−ML−i j v(x−ei) −∑ x∈3N xi=2 ∑ F⊆(N0(x)∪N1(x)) (−1)|F| ∥x∥w+r|F0(x)|+(1−r)|F1(x)|ML−i j v(x)−ML−i j v(x−ei) lo cual, teniendo en cuenta que ies un jugador nulo en v, es igual a =∑ x∈3N xi=1 ∑ F⊆(N0(x)∪N1(x))\{i} (−1)|F|r ∥x∥w+r|F0(x)|+(1−r)|F1(x)|ML v(x)−ML v(x−ei) 5.3 Caracterización del valor de comunicación r-justo 73 −∑ x∈3N\{0,1}N xi=1 ∑ F⊆(N0(x)∪N1(x))\{i} (−1)|F|r ∥x∥w+r|F0(x)|+(1−r)|F1(x)|ML−i j v(x)−ML−i j v(x−ei) lo cual, del hecho de que ML v(x) = ML−i j v(x)para cada x∈3Ntales que xi=0, es igual a =∑ x∈3N xi=1 ∑ F⊆(N0(x)∪N1(x))\{i} (−1)|F|r ∥x∥w+r|F0(x)|+(1−r)|F1(x)|ML v(x)−ML−i j v(x) que, dado que jes un jugador necesario en v, es igual a =∑ x∈3N xi=1 xj=2 ∑ F⊆(N0(x)∪N1(x))\{i} (−1)|F|r ∥x∥w+r|F0(x)|+(1−r)|F1(x)|ML v(x)−ML−i j v(x). Por otro lado tenemos que Λr j(v,L)−Λr j(v,L−i j) = =∑ x∈3N xj=1 ∑ F⊆(N0(x)∪N1(x))\{j} (−1)|F|r ∥x∥w+r|F0(x)|+(1−r)|F1(x)|ML v(x)−ML v(x−ej) +∑ x∈3N xj=2 ∑ F⊆(N0(x)∪N1(x)) (−1)|F| ∥x∥w+r|F0(x)|+(1−r)|F1(x)|ML v(x)−ML v(x−ej) −∑ x∈3N\{0,1}N xj=1 ∑ F⊆(N0(x)∪N1(x))\{j} (−1)|F|r ∥x∥w+r|F0(x)|+(1−r)|F1(x)|ML−i j v(x)−ML−i j v(x−ej) −∑ x∈3N xj=2 ∑ F⊆(N0(x)∪N1(x)) (−1)|F| ∥x∥w+r|F0(x)|+(1−r)|F1(x)|ML−i j v(x)−ML−i j v(x−ej) por lo que, teniendo en cuenta que jes un jugador necesario en v, es igual a =∑ x∈3N xj=2 ∑ F⊆(N0(x)∪N1(x)) (−1)|F| ∥x∥w+r|F0(x)|+(1−r)|F1(x)|ML v(x)−ML−i j v(x) =∑ x∈3N xi=0 xj=2 ∑ F⊆(N0(x)∪N1(x)) (−1)|F| ∥x∥w+r|F0(x)|+(1−r)|F1(x)|ML v(x)−ML−i j v(x) +∑ x∈3N xi=1 xj=2 ∑ F⊆(N0(x)∪N1(x)) (−1)|F| ∥x∥w+r|F0(x)|+(1−r)|F1(x)|ML v(x)−ML−i j v(x) +∑ x∈3N xi=2 xj=2 ∑ F⊆(N0(x)∪N1(x)) (−1)|F| ∥x∥w+r|F0(x)|+(1−r)|F1(x)|ML v(x)−ML−i j v(x) 5.4 Aplicación: Riesgos compartidos en tráfico en línea 80 Podemos ver que el valor Λ1 (el valor de Myerson) recompensa el poder posicional tanto como la generación activa de ganancias, el valor Λ0 no recompensa el rol de verificador que tiene la empresa 2 y el valor Λ1 10 pondera el poder posicional y la capacidad de generar ganancias en cierta proporción. Además, vemos con los valores obtenidos que Λ1 10 no se puede expresar como combinación convexa de Λ0yΛ1. Esta situación de intermediario logístico es muy habitual en grandes centros de conexiones aéreas (hub) con escala. Éstos nodos masivos ayudan a centralizar la comunicación dentro de la red aérea entre vuelos, ya que entre los nodos periféricos hay pocas conexiones, mientras que los centrales acaparan la mayoría de la actividad para permitir enlaces de forma indirecta. Estos hubs necesitan percibir un pago por el trabajo que realizan como intermediarios y en las labores de eficiencia en la gestión del tráfico. Lo justo en este caso es que el hub reciba una fracción del coste total del vuelo que realiza escala en sus instalaciones, y que éste obtenga beneficios mayores si es capaz de ofrecer soporte a una gran cantidad de vuelos. Esta situación es general en telecomunicaciones y conexiones. toda comunicación que un usuario efectúa con Internet se hace a través de unos servidores específicos llamados proxy. Cuando un usuario envía una solicitud para acceder a un sitio web, el proxy recibe dicha solicitud y la reenvía al sitio web en lugar del usuario, ocultando así la dirección IP real del usuario y añadiendo una capa de anonimato o seguridad. 6. Conclusiones y trabajos futuros El principal tema de la tesis ha sido en el estudio de la intermediación, del poder posicional y el poder de veto en diferentes juegos con restricciones en la cooperación. Hemos introducido modelos para estudiar la influencia que ciertos jugadores pueden ejercer en situaciones cooperativas, especialmente cuando tienen una posición estratégica clave o poseen la capacidad de bloquear acciones de otros cooperantes. En el Capítulo 3, consideramos la participación de un agente intermediario localizado en las aristas. Esta consideración nos permitió definir un nuevo modelo para juegos restringidos por grafos en el que tanto los nodos como los enlaces del grafo representan agentes en el juego, y obteniéndose un nuevo valor, el valor para juegos con intermediarios en las aristas. Se ha demostrado que este valor se caracteriza por las propiedades de eficiencia por componentes y justicia, que son análogas a las propiedades homónimas que definen al valor de Myerson para juegos restringidos por grafos. Además, se ha probado que el valor obtenido es estable y positivo siempre que el juego subyacente sea superaditivo y positivo. Propusimos el uso de dicho valor como una herramienta para monitorizar la seguridad de los nodos y enlaces en una red informática, creando un indicador clave de riesgo (KRI) para redes internas, es decir, un índice que informa sobre el riesgo de sufrir un ataque en cada elemento de una red. Este índice puede valorar las vulnerabilidades de la red y la susceptibilidad de un ataque Man-in-the-Middle. El uso de valores alternativos, como el valor de Banzhaf o el valor de posición, no han sido considerados y queda como una posible línea de investigación futura. En el Capítulo 4 , nos replanteamos la recompensa que se ha asignado al poder de veto en los valores anteriormente introducidos en la literatura. Para lograr este objetivo, el uso de juegos multichoice ha sido fundamental, ya que nos ha permitido ponderar los pagos asignados a cada posible acción de los jugadores (no hacer nada, otorgar permiso sin colaborar activamente y cooperar en todos los aspectos). Aplicando el operador de autorización y el valor de Hsiao hemos introducido y caracterizado una familia de valores, dependientes de un parámetro r , donde el parámetro se puede interpretar como la proporción entre el beneficio derivado del poder de veto y el que se obtiene únicamente de la cooperación activa. Este valor nos permite ponderar el peso de la intermediación, ya que en muchas situaciones ni es justo ni realista que cooperar activamente y dar permiso para cooperar tengan el mismo valor. Como investigación futura, proponemos aplicar esta metodología a otros modelos de teoría de juegos con cooperación restringida en los que puede no ser factible reunir adecuadamente toda 82 la información de la situación cooperativa en un juego clásico de utilidad transferible (TU). Se dejan abiertos posibles estudios en modelos de cohesión y perfeccionar los algoritmos de cálculo del valor usando la expresión por dividendos. Finalmente, en el Capítulo 5 se ha propuesto un nuevo valor para juegos cooperativos restringidos por grafos para poder ponderar de manera más justa la recompensa que obtiene el intermediario ya que, en la literatura, si un jugador es un intermediario indispensable para comunicar a los demás jugadores dentro de la coalición, este jugador recibirá, al menos, la misma parte del beneficio generado que los demás miembros de la coalición. Para ello, primero obtenemos una nueva función característica tras recopilar la información de la función característica y estructura combinatoria del juego original. En nuestro caso, el punto clave es que este juego no será un juego cooperativo en forma coalicional, sino un juego multichoice. Seguidamente, aplicamos un concepto de solución a este nuevo juego, el valor de Hsiao. Bibliografía [1] Alarcón, A.C.; Gallardo, J.M.; Jiménez-Losada, A. A Value for Graph-Restricted Games with Middlemen on Edges. Mathematics (2022), 10, 1856. https://doi.org/10.3390/math10111856. [2] Alarcón, A.C.; Gallardo, J.M.; Jiménez-Losada, A. Weighing hierarchical power and active contribution in cooperative games with authorization structure. OR Spectrum (2024). https://doi.org/10.1007/s00291-024-00779-7. [3] Algaba, E.; Bilbao, J.M.; Brink, R.; Jiménez-Losada, A. Cooperative games on antimatroids. Discrete Mathematics (2004), 282, 1–15. https://doi.org/10.1016/j.disc.2003.10.019. [4] Algaba, E.; Fragnelli, V.; Sánchez-Soriano, J. Handbook of the Shapley Value. Chapman and Hall/CRC, Taylor and Francis Group: Boca Raton, FL, USA (2020), ISBN: 978-0-81537468-8. [5] Amutio, M.A.; Candau, J. MAGERIT v.3, Methodology for Information Systems Risk Analysis and Management; Ministry of Finance and Public Administrations: Madrid, Spain (2006). Available online: https://administracionelectronica.gob.es/pae_Home/pae_ Documentacion/pae_Metodolog/pae_Magerit.html?idioma=en#.YpEnjS8lOhw (accessed on May 5, 2022). [6] Aumann, R.J.; Drèze, J. Cooperative Games with Coalition Structures. International Journal of Game Theory (1974), 3(4), 217-237. https://doi.org/10.1007/BF01766876. [7] Avrachenkov, K.E.; Kondratev, A.Y.; Mazalov, V.V. Cooperative Game Theory Approaches for Network Partitioning. In: Cao, Y.; Chen, J. (eds) Computing and Combinatorics. Lecture Notes in Computer Science, vol 10392. Springer, Cham (2017). https://doi.org/10.1007/9783-319-62389-4-49. [8] Banzhaf, J.F. Weighted voting doesn’t work: A mathematical analysis. Rutgers Law Review (1964), 19, 317-343. [9] Bessey, D. Hierarchies and decision-making groups: experimental evidence. Humanities and Social Sciences (2023), 10, 198. https://doi.org/10.1057/s41599-023-01714-x. [10] Borel, É. La théorie du jeu et les équations intégrales à noyau symétrique. Comptes Rendus de l’Académie des Sciences (1921), 173, 1304–1308. [11] Borm, P.; Owen, G.; Tijs, S. On the position value for communication situations. SIAM Journal on Discrete Mathematics (1992), 5, 305-320. https://doi.org/10.1137/0405023. BIBLIOGRAFÍA 84 [12] Branzei, R.; Dimitrov, D.; Tijs, S. Models in Cooperative Game Theory: Crisp, Fuzzy and Multichoice Games. Springer (2005). ISBN-13: 978-3540260820. [13] Branzei, R.; Tijs, S.; Zarzuelo, J. Convex multi-choice games: Characterizations and monotonic allocation schemes. European Journal of Operational Research (2009), 198(2), 571-575. [14] Branzei, R.; Llorca, N.; Sánchez Soriano, J.; Tijs, S. A constraint egalitarian solution for convex multi-choice games. TOP (2014), 22(3), 860-874. https://doi.org/10.1007/s11750013-0302-z. [15] Brink, R. van den. An axiomatization of the disjunctive permission value for games with a permission structure. International Journal of Game Theory (1997), 26(1), 27-43. https://doi.org/10.1007/s001820050034. [16] Brink, R. van den. An axiomatization of the Shapley value using a fairness property. International Journal of Game Theory (2002), 30(3), 309–319. https://doi.org/10.1007/s001820100079. [17] Brink, R. van den, & Dietz, C. Games with local permission structure: Separation of authority and value generation. Theory and Decision (2014), 76, 343–361. [18] Brink, R. van den. Games with a permission structure: A survey on generalizations and applications. TOP (2017), 25(1), 1–33. https://doi.org/10.1007/s11750-017-0440-9. [19] Calvo, J.; Santos, J.C. A value for multichoice games. Mathematical Social Sciences (2000), 40(3), 341-354. https://doi.org/10.1016/S0165-4896(99)00054-2. [20] Camerer, C.F. Behavioral Game Theory: Experiments in Strategic Interaction. Princeton University Press (2003). https://doi.org/10.1515/9780691090399. [21] Chiou, W.L.; Hsiao, C.R. A characterization of the multi-choice Shapley value with partially consistent property. Taiwanese Journal of Mathematics (2010), 14(1), 287-318. https://doi.org/10.11650/twjm/1500402878. [22] Derks, J.; Hsiao, C.R.; Peters, H. Shapley-like values for multichoice games. Mathematical Methods of Operations Research (2000), 51(3), 479-492. https://doi.org/10.1007/s001860000047. [23] Derks, J.; Peters, H. A Shapley value for games with restricted coalitions. International Journal of Game Theory (1993), 21, 351-366. https://doi.org/10.1007/BF01240135. [24] Dixit, A.K.; Nalebuff, B.J. The Art of Strategy: A Game Theorist’s Guide to Success in Business and Life. W.W. Norton & Company (2008). [25] Dubey, P.; Neyman, A.; Weber, R.J. Value theory without efficiency. Mathematics of Operations Research (1981), 6, 122-128. https://doi.org/10.1287/moor.6.1.122. [26] Edgeworth, F. Y. Mathematical Psychics: An Essay on the Application of Mathematics to the Moral Sciences. C. Kegan Paul & Co (1881). BIBLIOGRAFÍA 85 [27] Faigle, U., & Kern, W. The Shapley value for cooperative games under precedence constraints. International Journal of Game Theory (1992), 21, 249–266. https://doi.org/10.1007/BF01240130. [28] Grabisch, M., & Lange, F. Games on lattices, multichoice games and the Shapley value: A new approach. Mathematical Methods of Operations Research (2007), 65(1), 153–167. https://doi.org/10.1007/s00186-006-0144-7. [29] Gallardo, J. M., Jiménez, N., & Jiménez-Losada, A. A Shapley value for games with authorization structure. In D. Mueller & R. Trost (Eds.), Game Theory in Management Accounting (pp. 1–18). Springer, Cham (2018). Contributions to Management Science. [30] Gilles, R. P. The Cooperative Game Theory of Networks and Hierarchies. Springer, Heidelberg Dordrecht London New York (2010). ISBN: 978-3-642-05281-1. https://doi.org/10.1007/978-3-642-05282-8. [31] Gilles, R. P., Owen, G., & Brink, R. van den. Games with permission structures: The conjunctive approach. International Journal of Game Theory (1992), 20, 277–293. [32] Gilles, R. P. The Cooperative Economy: Theory, Structure, and Organization. Springer (1996). ISBN-13: 978-0792397869. [33] Gillies, D. B. Some theorems on n-person games. PhD thesis, Princeton University (1953), New Jersey. [34] Goldscheider, R., Jarosz, J., & Mulhern, C. Use of the 25% rule in valuing intellectual property. In R. Goldscheider (Ed.), Intellectual Property: Valuation, Exploitation, and Infringement Damages (pp. 272–290). John Wiley and Sons (2018). [35] González-Díaz, J., & Sánchez-Rodríguez, E. A natural selection from the core of a TU game: The core-center. International Journal of Game Theory (2007), 36, 27–46. https://doi.org/10.1007/s00182-007-0074-5. [36] Hsiao, C.-R., & Raghavan, T. E. S. . Monotonicity and dummy-free property for multichoice cooperative games. International Journal of Game Theory (1993a), 21, 301–312. [37] Hsiao, C.-R., & Raghavan, T. E. S. Shapley value for multichoice cooperative games. Games and Economic Behavior (1993), 5, 240–256. https://doi.org/10.1006/game.1993.1014. [38] Jackson, M. O. Social and Economic Networks. Princeton University Press (2008). ISBN: 9780691148205. [39] Jackson, M. O., & Wolinsky, A. A strategic model of social and economic networks. Journal of Economic Theory (1996), 71(1), 44–74. https://doi.org/10.1006/jeth.1996.0041 [40] Kalai, E., & Samet, D. On weighted Shapley values. International Journal of Game Theory (1987), 16(3), 205–222. https://doi.org/10.1007/BF01756292. [41] Kiselev, V. Y. Cooperative games: Historical problems, modern theory. The Mathematical Intelligencer (2005), 27, 33–40. https://doi.org/10.1007/BF02985836. [42] Krutz, R. L., & Vines, R. D. The CISSP Prep Guide: Gold Edition. John Wiley & Sons Inc (2002). ISBN: 978-0471268024. BIBLIOGRAFÍA 86 [43] Lehrer, E. An axiomatization of the Banzhaf value. International Journal of Game Theory (1988), 17, 89–99. https://doi.org/10.1007/BF01254541. [44] Lowing, D. Allocation rules for multi-choice games with a permission tree structure. Working Papers 2106, Groupe d’Analyse et de Théorie Économique Lyon St-Étienne (GATE)(2021), Université de Lyon. https://doi.org/10.1007/s10479-022-04953-4. [45] Martin, J. L. Lecture Notes on Algebraic Combinatorics. University of Kansas. Licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License. Last updated August 23, (2023). [46] Maynard Smith, J. Evolution and the Theory of Games. Cambridge University Press (1982). [47] Mazalov, V.V., & Trukhina, L.I. Generating functions and the Myerson vector in communication networks. Discrete Mathematics and Applications (2014), 24(5), 295–303. [48] Meesen, R. Communication Games (Doctoral dissertation). University of Nijmegen (1988), The Netherlands. [49] Myerson, R. B. Graphs and cooperation in games. International Journal of Game Theory (1977), 7(3), 253-263. [50] Myerson, R. B. Conference structures and fair allocation rules. International Journal of Game Theory (1980), 9(3), 169-182. [51] Myerson, R. B. Graphs and cooperation in games. Mathematics of Operations Research (1988), 2(3), 225-229. https://doi.org/10.1287/moor.2.3.225 [52] Nash, J. F. Jr. Equilibrium points in n-person games. Proceedings of the National Academy of Sciences of the United States of America (PNAS) (1950), 36(1), 48–49. https://doi.org/10.1073/pnas.36.1.48. [53] Nisan, N., Roughgarden, T., Tardos, É., & Vazirani, V. V. Algorithmic Game Theory. Cambridge University Press (2007). ISBN-13: 978-0521872829. [54] Osborne, M. J., & Rubinstein, A. A Course in Game Theory. MIT Press (1994). [55] Owen, G. Values of games with a priori unions. In Essays in Mathematical Economics in Honor of Oskar Morgenstern (pp. 76-88). Princeton University Press (1977). [56] Peleg, B., & Sudhölter, P. . Introduction to the Theory of Cooperative Games (2nd ed.). Springer (2003). ISBN-13: 978-3-642-18938-1. [57] Roth, A. E. (Ed.). The Shapley Value: Essays in Honor of Lloyd S. Shapley. Cambridge University Press (1988). [58] Saaty, T. L., & Vargas, L. G. Decision Making with the Analytic Network Process. Springer (2002). https://doi.org/10.1007/0-387-33987-6. [59] Shapley, L. S. A value for n-person games. Annals of Mathematical Studies (1953), 28, 307–317. https://doi.org/10.1515/9781400881970-018. BIBLIOGRAFÍA 87 [60] Shapley, L. S., & Shubik, M. A method for evaluating the distribution of power in a committee system. American Political Science Review (1954), 48(3), 787–792. https://doi.org/10.2307/1951053. [61] Schmeidler, D. The nucleolus of a characteristic function game. SIAM Journal of Applied Mathematics (1969), 17(6), 1163–1170. https://doi.org/10.1137/0117107. [62] Shoham, Y., & Leyton-Brown, K. Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations. Cambridge University Press (2008). ISBN-13: 978-0521429787. [63] Thomson, W. How to Divide When There Isn’t Enough (Vol. 62). Cambridge University Press (2019). ISBN-13: 978-1108483520. [64] Tijs, S. H. Bounds for the core and the τ -value. In O. Moeschlin & D. Pallaschke (Eds.), Game Theory and Mathematical Economics (1981) (pp. 123-132). North-Holland. [65] von Neumann, J. Zur Theorie der Gesellschaftsspiele. Mathematische Annalen (1928), 100, 295–320. https://doi.org/10.1007/BF01448847. [66] von Neumann, J., & Morgenstern, O. Theory of Games and Economic Behavior. Princeton University Press (1944). [67] Warsinke, J., Graff, M., Henry, K., Hoover, C., Malisow, B., Murphy, S., Oakes, C. P., Pajari, G., Parker, J. T., Seidl, D., & Vasquez, M. Domains 2 and 4. In Official (ISC)2 Guide to the CISSP CBK (pp. 618–630). John Wiley & Sons Inc (2019). [68] Young, H. P. Monotonic solutions of cooperative games. International Journal of Game Theory (1985), 14(2), 65–72. https://doi.org/10.1007/BF01766022. [69] Peters, H., & Zank, H. The egalitarian solution for multichoice games. Annals of Operations Research (2005), 137(1), 399–409. https://doi.org/10.1007/s10462-005-6985-7. [70] Zermelo, E. Über eine Anwendung der Mengenlehre auf die Theorie des Schachspiels. Proceedings of the Fifth International Congress of Mathematicians (1913).