Soluciones para juegos en contextos formales

Universidad de Sevilla Máster Universitario en Matemáticas Soluciones para juegos en contextos formales Autor Juan Carlos Rodríguez Gómez Tutores Don Andrés Jiménez Losada Don Manuel Ordóñez Sánchez Dpto. de Matemática Aplicada II Escuela Superior de Ingeniería Universidad de Sevilla Sevilla 2021 Agradecimientos Transmitir mi más sincero agradecimiento a todos aquellos que me han ayudado a lo largo de esta etapa y han colaborado en esta investigación. En primer lugar, a mis tutores, Andrés Jiménez y Manuel Ordóñez, por su ayuda en la planificación, información y organización en este Trabajo de Fin de Máster. En segundo lugar, a mi familia, que han estado a lo largo de toda mi carrera apoyándome en todo momento y animándome a seguir adelante. También, expresar mi más sentido agradecimiento a la Universidad de Sevilla y a la Facultad de Matemáticas, por acogerme dentro de sus aulas y hacerme sentir como en casa. Después de este período de investigación escribo este apartado de agradecimientos para finalizar mi TFM. Sin duda, ha sido un período de aprendizaje científico y personal. Desarrollar este estudio ha tenido un gran impacto en mi persona y es por eso que me gustaría agradecer a todas aquellas personas que me han apoyado durante este proceso. A todos ellos, mil gracias. Índice general IntroducciónGeneral.......................... 6 1. Juegos cooperativos 10 1.1. Juegos de utilidad transferible . . . . . . . . . . . . . . . . . . 10 1.2. El Core y conceptos relacionados . . . . . . . . . . . . . . . . 13 1.3. El valor de Shapley . . . . . . . . . . . . . . . . . . . . . . . . 25 1.4. Juegosconvexos.......................... 30 1.5. Algunas Aplicaciones de los Juegos TU . . . . . . . . . . . . . 32 2. Juegos cooperativos en contextos formales 40 2.1. Contextos formales . . . . . . . . . . . . . . . . . . . . . . . . 40 2.2. Juegos en contextos formales . . . . . . . . . . . . . . . . . . . 44 2.3. El valor de Shapley para juegos sobre contextos formales . . . 48 2.4. El core de un juego de conceptos . . . . . . . . . . . . . . . . 60 3. Valores de compromiso en contextos formales 72 3.1. Valores de compromisos clásicos . . . . . . . . . . . . . . . . . 73 3.2. Contextos regulares . . . . . . . . . . . . . . . . . . . . . . . . 77 3.3. τ-Valores.............................. 82 3.4. χ-Valores ............................. 88 3.5. Comparativa de los valores de compromiso . . . . . . . . . . . 98 3.6. Axiomatizaciones y el Core . . . . . . . . . . . . . . . . . . . . 99 0.0. INTRODUCCIÓN GENERAL 6 Introducción General En la teoría de juegos cooperativos, asumimos que los jugadores se comportan de tal forma que ya no solo sus estrategias están orientadas a conseguir sus propios objetivos de manera unilateral, maximizando sus beneficios (o minimizando sus costes). Por el contrario, están dispuestos a cooperar entre ellos para poder así conseguir más de lo que pueden conseguir de manera individual. La principal cuestión es, una vez que han cooperado, ¿cómo se pueden repartir los beneficios entre ellos de manera racional y justa?. Este estudio se centra en esa cuestión, donde los jugadores van a formar distintos subgrupos, a los que llamaremos coaliciones, con unos beneficios que cada coalición puede conseguir, sin tener en cuenta lo que otros jugadores hagan fuera de ella. El conjunto de jugadores se denota por N:= {1, ..., n}. Para cada S⊂N, nos referimos a Scomo una coalición, siendo |S|el número de jugadores en S. A la coalición Nse le llama la gran coalición. Centraremos el estudio en los juegos de utilidad transferible y en los conceptos de soluciones. Siendo un concepto solución aquél en el que el reparto que se asigna a cada jugador es eficiente, es decir, la suma de las asignaciones que se dan a cada jugador es igual a la asignación que obtiene la gran coalición. Además tiene que ser racionalmente individual; cada jugador no puede obtener menos de lo que pueden obtener por sí mismo. Estos dos axiomas dan lugar al conjunto de soluciones llamado conjunto de imputación. A este último concepto de solución se le añade el concepto de racionalidad coalicional, que consiste en que al conjunto de imputación se le exige que cada coalición que se forma en el juego también debe cumplir la racionalidad individual. Llegando al concepto de solución llamado core. En este estudio se demostraran los conceptos de solución anteriormente mencionados así como sus axiomas de caracterización. Introduciremos el concepto de juegos coope- 0.0. INTRODUCCIÓN GENERAL 7 rativos en contextos formales y retículo de conceptos. De esta clase de juegos, nace un nuevo concepto de solución, el cual se denomina, valores de compromisos. Presentaremos el estudio del τ-Valor y el χ-Valor, tanto en los juegos clásicos como su aplicación en los juegos en contextos formales. Se estudiaran distintas formulaciones dependiendo del punto de vista de la estructura del retículo que forma el juego, así como su axiomática. Un contexto formal de un juego cooperativo es aquel al que a cada jugador se le asigna un handicap, es decir, un atributo o varios, que le hace menos atractivo a la hora de unirse a una coalición. Un contexto formal se representa con la tabla de asignaciones, una tabla donde están representados todos los jugadores y todos los handicap posibles. En esta tabla se le asigna un 1si el jugador iposee el handicap o un 0en caso contrario. De la tabla de incidencia obtenemos el retículo de conceptos, que simplemente es una representación gráfica en forma de retículo, donde se representan las distintas coaliciones que se van formando, desde el bottom, que es la parte más inferior del retículo (aquí se encuentran los jugadores que poseen todos los handicaps) hasta el top , en la parte superior, que es donde está representada la gran coalición (la cual no posee ningún handicap). Este tipo de juegos en contextos formales se presenta por primera vez en el articulo Games on concept lattices: Shapley value and core (2014 [21]) En el primer capitulo se introduce los juegos cooperativos de utilidad transferible, así como el concepto solución dado por Shapley y el core. En esta sección estudiaremos problemas de negociación coalicional. En uno de tales problemas, un conjunto de jugadores, que dispone de mecanismos para tomar acuerdos vinculantes, debe decidir cómo repartirse los beneficios de su cooperación. A diferencia de lo que ocurría en los problemas de negociación simple, ahora no es necesaria la unanimidad para que un reparto sea adoptado, sino que puede haber algunos grupos de jugadores capaces de forzar determinados repartos. También supondremos que los beneficios generados por los grupos de jugadores (a los que denominamos coaliciones) pueden repartirse libremente entre ellos. Por eso, en realidad, trataremos con pro- 0.0. INTRODUCCIÓN GENERAL 8 blemas de negociación coalicional con utilidad transferible. Para caracterizar uno de tales problemas usaremos los llamados juego cooperativos con utilidad transferible (abreviadamente juegos TU). Las diferentes coaliciones que se pueden formar entre los jugadores en Npueden exigir ciertas asignaciones. El problema es decidir como los beneficios generados por la cooperación de los jugadores pueden ser repartidos entre ellos. Dada una coalición Sdenotamos por v(S)las posibles asignaciones x∈RSde utilidad para los jugadores si la coalición se forma. Si x∈v(S)entonces que la utilidad sea transferible significa que todas las posibles asignaciones que se pueden obtener de xpor transferencia de utilidades entre los jugadores en Stambién pertenecen a v(S). Por lo tanto, v(S)puede ser caracterizado por un único número, dado por m´axx∈v(S)Pi∈Sxi, es decir, la suma del máximo que cada jugador puede conseguir. A este número v(S)se le llama valor de la coalición S, como el beneficio que puede generar. Sea GNla clase de juegos TU con njugadores. Estudiaremos dos aplicaciones de gran utilidad en este tipo de juegos. En el segundo capítulo se introduce los juegos en contextos formales y el retículo de conceptos. Para este tipo de juegos también estudiaremos el valor de Shapley y el core. En el tercer capítulo se hace una breve introducción de los valores de compromiso en juegos cooperativos de utilidad transferible. Se define que es un contexto regular y un algoritmo para la regularización de contextos. La aportación de este estudio recae en una nueva visión en el campo de los juegos de utilidad transferible en contextos formales, en especial, sus valores de compromiso (τ-Valor y χ-Valor) así como su axiomática. 1.2. EL CORE Y CONCEPTOS RELACIONADOS 15 X i∈S xi≥v(S) El conjunto constituido por todos los vectores de pago eficientes que satisfacen estas desigualdades da lugar al concepto solución denominado core del juego v. Definición 1.2.2. Sea v∈GN. El core de v, C(v), se define como: C(v) := (x∈I(v) : para cada S⊂N, X i∈S xi≥v(S)) El core fue introducido por Gillies [2] en 1953 y se considera un concepto muy natural de solución, aunque tiene el inconveniente de que, en muchos casos, es vacío. Para la clase de juegos convexos se puede afirmar que éste es no vacío; no obstante, aún cuando el core sea no vacío, podría ser pequeño para conseguir dar soluciones razonables a ciertos juegos. Esto conduce a la consideración de otros conceptos solución. Desde el inicio de la teoría de juegos, se han propuestos muchos conceptos de solución. En 1944, von Neumann y Morgenstern [3] introdujeron el concepto de conjunto estable. Los conjuntos estables son descritos en términos de una relación entre imputaciones llamada dominación, y por tanto, requieren que el conjunto de imputaciones sea no vacío. Definición 1.2.3. Sea v∈GNun juego TU y sean S∈2N\ ∅ yx, y ∈I(v). Se dice que xdomina a ya través de Ssi se cumple: 1. xi> yi, para todo i∈S. 2. P i∈S xi≤v(S). Se dice que xdomina a aysi existe una coalición T∈2N\∅ tal que xdomina aya través de T. Se dice que xes no dominada si no existe z∈I(v)tal que 1.2. EL CORE Y CONCEPTOS RELACIONADOS 16 zdomina a x. Obsérvese que xdomina a ya través de Scuando todos los jugadores de Sprefieren xay, además, xes alcanzable para S, en el sentido de que la cantidad total propuesta por xpara los jugadores de Sno es superior a la cantidad que los jugadores de Spueden garantizarse por sí mismos. Por tanto, si xdomina a y, existe alguna coalición con interés y capacidad de vetar y. En definitiva, para que una imputación sea realmente estable debe ser no dominada. Esto es lo que le ocurre a las imputaciones del core, tal como se muestra en el resultado siguiente. Proposición 1.2.1. Sea v∈GNun juego TU. 1. Si x∈C(v), entonces xes no dominada. 2. Si, además, v∈SGN, entonces se tiene que C(v) = {x∈I(v) : xes no dominada}. Demostración. Probemos la primera afirmación. Supongamos que x∈C(v) y existe y∈I(v)y una coalición no vacía S⊂Ntales que ydomina a xa través de S. Entonces v(S)≥X i∈S yi>X i∈S xi≥v(S), lo cual es una contradicción. Veamos ahora 2). Sea xuna imputación no dominada de vy supongamos que no pertenece a C(v). En tal caso existe S⊂Ntal que Pi∈Sxi< v(S). Definamos y∈RNdel siguiente modo: yi=             xi+v(S)−Pj∈Sxj |S|si i∈S, v(i) + v(N)−v(S)−Pj∈N\Sv(j) |N\S|si i∈N\S. 1.2. EL CORE Y CONCEPTOS RELACIONADOS 17 Como ves superaditivo, y∈I(v). Además, ydomina a xa través de S, lo cual es una contradicción.  A continuación veremos varios ejemplos para ilustrar el concepto del core. El primero muestra un juego TU que no es superaditivo y que tiene una imputación no dominada que, sin embargo, no pertenece a su core. Los demás estudian los cores de los ejemplos tratados en la sección anterior. Ejemplo 1.2.1.- Sea el juego (N, v)tal que N={1,2,3},v(1) = v(2) = 0, v(3) = 1,v(12) = 2,v(13) = v(23) = 1,v(N) = 2. Obsérvese que v(N)< v(12) + v(3) y que por tanto, vno es superaditivo. Por otro lado, C(v) = ∅ y(1,0,1) es una imputación no dominada. En este caso, la coalición Sprefiere la distribución xsobre la yporque cada miembro de Sobtiene más, y Sno sobrepasa su valor con esta imputación. Ejemplo 1.2.2.- Es fácil ver que el core del juego del reparto del millón es vacío, a pesar de que es un juego superaditivo. Esto quiere decir que la situación de negociación descrita por este juego es fuertemente inestable. Ejemplo 1.2.3.- El core del juego del guante es el conjunto unitario {(1,0,0)}. Puede parecer extraño que el único elemento del core de este juego asigne todos los beneficios al poseedor del guante singular. Sin embargo, (1,0,0) es la única imputación del juego no dominada, es decir, estable. La interpretación que se puede hacer de este resultado es que el precio de los guantes derechos en el mercado se hace cero ya que hay un exceso de oferta de tales guantes. Ejemplo 1.2.4.- Está claro que el core del juego de ahorro vasociado al problema de la profesora visitante está dado por C(v) = {x∈I(v) : x1+x2≥1500, x1+x3≥500, x2+x3≥500}, 1.2. EL CORE Y CONCEPTOS RELACIONADOS 18 que es un conjunto no vacío. En la Figura 1.1 representamos los hiperplanos que delimitan I(v)yC(v). A la vista de esto es fácil comprobar que C(v) = conv{(1500,0,500),(1500,500,0),(500,1500,0),(0,1500,500)}. En la Figura 1.2 representamos C(v)y sus puntos extremos. De hecho, lo que está representando en los dos dibujos de la Figura son I(v)yC(v)como subconjuntos del hiperplano eficiente, que está dado por {x∈RN:Pi∈Nxi= v(N)}. Figura 1.1: El core del juego de la profesora visitante. Hiperplano asociados aI(v)yC(v) 1.2. EL CORE Y CONCEPTOS RELACIONADOS 19 Figura 1.2: El core del juego de la profesora visitante. El conjunto C(v)y sus puntos extremos Antes de analizar el juego asociado al Parlamento de Aragón vamos a introducir algunos conceptos y resultados. Definición 1.2.4. Un juego v∈GNse denomina simple si: 1. Para toda S⊂N, v(S)=0, o v(S) = 1. 2. v(N)=1 3. ves un juego monótono, esto es, v(S)≤v(T)para cualquiera S, T ⊂N con S⊆T. Se denotará por S(N)el conjunto de los juegos simples con conjunto de jugadores N. Para un juego simple (N, v)y una coalición S⊂N, se dice que Ses ganadora si v(S) = 1; en caso contrario, se dice que Ses perdedora. Se denotará por Wel conjunto de todas las coaliciones ganadoras, es decir, W={S⊂N:v(S)=1}. Es evidente que Nes un elemento de Wy que si S∈WyS⊂T, entonces T∈W. Una coalición ganadora es minimal si no contiene a ninguna otra coalición ganadora. Se denotará por Wmel conjunto de todas las coaliciones ganadoras minimales, es decir, 1.2. EL CORE Y CONCEPTOS RELACIONADOS 20 Wm={S∈W:v(T) = 0,∀T⊂Scon T6=S} Nótese que un juego simple puede caracterizarse dando el conjunto de coaliciones ganadoras, o también, dando el conjunto de coaliciones ganadoras minimales. Definición 1.2.5. Sea v∈SNun juego simple. Se dice que i∈Nes un jugador veto de v(N\i)=0. Proposición 1.2.2. Sea v∈SNun juego simple. Entonces C(v)6=∅si y solo si el conjunto V de jugadores veto es no vacío. Además, si C(v)6=∅ entonces C(v) = {x∈I(v) : xi= 0 ∀i∈N\V}. Demostración. Supongamos que C(v)6=∅y que V=∅. Tomemos x∈C(v). Entonces, para todo i∈N, xi= 0 puesto que 0 = v(N)−v(N\ {i})≥X j∈N xj−X j∈N\{i} xj=xi≥0. Esto es obviamente imposible. Recíprocamente, supongamos que Ves un conjunto no vacío y consideremos el conjunto no vacío {x∈I(v) : xi= 0 ∀i∈N\V}. Es inmediato comprobar que este conjunto es C(v).  1.2. EL CORE Y CONCEPTOS RELACIONADOS 21 Ejemplo 1.2.5.- En virtud de los resultados anteriores y teniendo en cuenta que el juego asociado al Parlamento de Aragón es un juego simple con un conjunto vacío de jugadores veto, está claro que su core es vacío. Hemos visto que hay situaciones de negociación coalicional que son altamente inestables y, por ello, tienen un core vacío. A continuación proporcionamos una condición necesaria y suficiente para el carácter no vacío del core de un juego. El correspondiente resultado fue probado independientemente por Bondareva (1963) y Shapley (1967), por lo que es conocido por el teorema de Bondareva-Shapley. Definición 1.2.6. Una familia de coaliciones F⊂2N\ {∅} se denomina equilibrada si existe una familia asociada de números reales positivos (denominados coeficientes equilibrantes){yS:S∈F}tal que, para todo i∈N, X S∈F,i∈S yS= 1 Definición 1.2.7. Un juego v∈GNse denomina equilibrado si, para cualquier familia de coaliciones equilibrada Fcon coeficientes equilibrantes {ys: S∈F}, se tiene que X S∈F ySv(S)≤v(N). El hecho de que (N, v)sea equilibrado viene a significar que las coaliciones “intermedias” no tienen demasiado poder. Por ello, el carácter equilibrado de un juego parece estar relacionado con la estabilidad de la situación de negociación coalicional descrito por dicho juego. Esto es precisamente lo que afirma el teorema de Bondareva-Shapley. Teorema 1.2.1 (Teorema de Bondareva-Shapley).Sea v∈GNun juego TU. Entonces C(v)6=∅si y solo si ves equilibrado. 1.2. EL CORE Y CONCEPTOS RELACIONADOS 22 Demostración. La demostración del resultado anterior hace uso de nociones básicas de dualidad en programación lineal. Supongamos que C(v)6=∅. Sean x∈C(v)yFuna familia de coaliciones equilibradas con coeficientes equilibrantes {yS:S∈F}. Entonces, X S∈F ySv(S)≤X S∈FX i∈S ySxi=X i∈N (xiX S∈F,i∈S yS) = X i∈N xi=v(N). Recíprocamente, supongamos que ves equilibrado y consideremos el siguiente problema de programación lineal (P): minimizar P i∈N xi sujeto a P i∈S xi≥v(S)∀S∈2N\ {∅}. Nótese que C(v)6=∅si y solo si existe xuna solución óptima de (P) con Pi∈Nxi=v(N). El dual (P) es el siguiente problema de programación lineal (D): maximizar P S∈2T\{∅} ySv(S) sujeto a P S∈2T\{∅},i∈S yS= 1 ∀i∈N, yS≥0∀S∈2N\ {∅}. Claramente, (D) tiene, al menos, una solución óptima y, ya que el conjunto de soluciones factibles es no vacío y compacto, y su función objetivo es continua. Definamos ahora F={S⊂N:yS>0}. 1.2. EL CORE Y CONCEPTOS RELACIONADOS 23 Obviamente Fes una familia equilibrada con coeficientes equilibrantes {yS: S∈F}. Como (D) tiene una solución óptima entonces, por el teorema de dualidad,(P) tiene también una solución óptima xy, además, X i∈N xi=X S∈2T\{∅} ySv(S). Como ves equilibrado y xes una solución óptima de (P) v(N)≤X i∈N xi=X S∈2T\{∅} ySv(S)≤v(N) por lo que v(N) = Pi∈Nxi.  Otro concepto de solución es el llamado conjunto de negociación, propuesto por Aumann y Maschler [5]. Este conjunto es una extensión del core y está unido a los procesos de negociación ya que, en ellos se tiene en cuenta las posibles acciones y respuestas hechas por las coaliciones. Actualmente hay varias versiones del conjunto de negociación, pero aquí se considera la más clásica. Si xes una imputación para un juego v, una objeción de un jugador i∈N contra otro jugador j∈Ncon respecto a la imputación xes un par (y, S) donde S⊂Nes una coalición que contiene al jugador ipero no al j, y el vector y∈R|S|satisface y(S) = V(S)y además yk> xkpara cada k∈S. Una contraobjeción a la objeción (y, S)es un par (z, T)donde T⊂Nes una coalición conteniendo al jugador jpero no al jugador i, y el vector z∈R|T| 1.2. EL CORE Y CONCEPTOS RELACIONADOS 24 verifica que z(T) = v(T)y, además,    zk≥xkpara k∈T\S, zk≥ykpara k∈T∩S. Una objeción esta justificada si no existe contraobjeción. El conjunto de negociación de Aumann y Maschler es el conjunto de todas las imputaciones x para las cuales no existen objeciones justificadas respecto de x. En 1978, Weber [6] propuso como concepto de solución un conjunto que contiene al core, y es más fácil de computar. Además, este conjunto es siempre no vacío. La definición de conjunto de Weber se basa en los vectores de contribución marginal. Se suponen ordenados los jugadores en un juego (N, v)y se tienen en cuenta todos los posibles órdenes del conjunto de jugadores; es decir, se considera el conjunto Πnde todas las permutaciones de N. Para cada orden π∈Πnse define el vector de contribución marginal aπ(v)∈Rncomo la preimputación cuyas coordenadas satisfacen aπ i(v) = v(πi∪ {i})−v(πi)∀i∈N, donde πies el conjunto de los predecesores del jugador ien el orden π. El vector aπ(v)asigna a cada jugador su contribución marginal en el orden π. El conjunto de Weber del juego ves la envoltura convexa de los vectores de contribución marginal; esto es Weber(v) = conv{aπ(v) : π∈Πn}. En la mayoría de los casos, los conceptos de solución citados no asignan al juego una única distribución, sino un conjunto de distribuciones. También se 1.4. JUEGOS CONVEXOS 31 mπ i(v) := v(Pπ(i)∪ {i})−v(Pπ(i)) La envoltura convexa de los vectores de contribución marginal es comúnmente conocido como conjunto de Weber, formalmente introducido como concepto de solución por Weber ([6]). Es fácil de ver que el valor de Shapley es equivalente a Φi(v) := 1 n!X π∈Π(N) mπ i(v) . A continuación presentamos el resultado más importante para los juegos convexos. Este relaciona juegos convexos, vectores marginales y el core. Teorema 1.4.1. Sea v∈GN. Los siguientes resultados son equivalentes: i) El juego ves convexo. ii) Para cada π∈Π(N), mπ(v)∈core(v). iii) core(v) = conv{mπ(v) : π∈Π(N)}, i.e., el core y el conjunto de Weber coinciden. Corolario 1.4.1. Sea v∈GNun juego convexo. Entonces Φ(v)∈C(v) Ejemplo 1.4.1.- En el juego asociado al Parlamento de Aragón, IU es un jugador nulo y los demás partidos son jugadores simétricos. Por tanto, su valor de Shapley es (1/3,1/3,1/3,0). Ejemplo 1.4.2.- Las dos tablas siguientes recogen los cálculos para la obtención del valor de Shapley del juego de ahorro y del juego de coste asociados al problema de la profesora visitante. El valor de Shapley del primero de estos juegos, el de ahorro, viene dado por 1.5. ALGUNAS APLICACIONES DE LOS JUEGOS TU 32 π123 123 0 1500 500 132 0 1500 500 213 1500 0 500 231 1500 0 500 312 500 1500 0 321 1500 500 0 Φ 5000/6 5000/6 2000/6 π123 123 1500 100 1400 132 1500 100 1400 213 0 1600 1400 231 0 1600 1400 312 1000 100 1900 321 0 1100 1900 Φ 4000/6 4600/6 9400/6 Φ(v) = (5000/6,5000/6,2000/6). De acuerdo con esta asignación de ahorros, los jugadores deben pagar (4000/6,4600/6,9400/6). Este último vector es precisamente Φ(c). Para explicar este resltado, notemos que Φi(v) = P S⊂N\{i} s!(n−s−1)! n!(v(S∪ {i})−v(S)) =P S⊂N\{i} s!(n−s−1)! n!(c(S)−c(S∪ {i}) + c(i)) =c(i)−Φi(c). Finalmente, es claro que Φ(v)∈C(v). De hecho, ves un juego convexo. 1.5. Algunas Aplicaciones de los Juegos TU En esta sección presentamos dos aplicaciones de los juegos TU, una en el contexto de los problemas de asignación de costes y la otra en el de los modelos de la investigación operativa. Tales aplicaciones dan lugar a dos clases relevantes de juegos TU: los juegos del aeropuerto y los juegos de producción lineal. Juegos del Aeropuerto Littlechild y Owen (1973 [13]) propusieron este modelo como un ejemplo donde el valor de Shapley es fácil de calcular y tiene una interpretación 1.5. APLICACIONES 33 sencilla. Su idea surgió de los trabajos de Baker (1965 [14]) y Thompson (1971 [15]) sobre el precio que tienen que pagar las operaciones de distintos tipos de aviones, donde por operación se entiende un despegue o un aterrizaje. A continuación formalizamos el modelo. Supongamos que hay mtipos diferentes de aviones. Para cada tipo l, conocemos el número de operaciones, nl, y los costes totales de construcción de una pista, cl, asociados a ese tipo de aviones. Dado que queremos conocer lo que tiene que pagar cada operación, consideramos que cada una de ellas es un jugador; por lo tanto, Nles el conjunto de jugadores asociados con operaciones de aviones del tipo l. Supongamos que los tipos de aviones están ordenados con respecto a los costes, es decir, 0< c1< c2<· · · < cm. Sea N=∪m l=1Nlel conjunto de todas las operaciones. El juego del aeropuerto asociado a este problema de reparto de costes está definido por el conjunto de jugadores Ny la función característica vdada por v(S) = −m´ax{cl:S∩Nl6=∅} para cada S⊂N, S 6=∅. Esta definición se basa en la consideración de que los aviones más grandes necesitan pistas más largas. El coste imputables a una coalición Ses el coste de una pista adecuada para que puedan realizarse todas las operaciones de S. Dicho coste es claramente m´ax{cl:S∩Nl6=∅}, es decir, el coste de una pista adecuada para que puedan operar en ella los aviones más grandes asociados a operaciones de S. Finalmente, cambiamos el signo para mantener la interpretación de la función característica en términos de beneficios y no de costes. En los trabajos de Baker (1965 [14]) y Thompson (1971 [15]) aparece una asignación de costes que se define secuencialmente del siguiente modo. En primer lugar, el coste de construcción de una pista para operaciones de los aviones más pequeños (tipo 1) se divide igualitariamente entre el número total de operaciones correspondientes a todos los tipos de aviones. La idea que subyace en esta asignación es que todas las operaciones utilizan esta parte de la pista. A continuación, se divide igualitariamente el incremento 1.5. APLICACIONES 34 que supone construir la pista para las operaciones del segundo tipo de aviones más pequeños entre el número total de operaciones correspondientes a aviones de tipo mayor o igual que 2. El procedimiento continúa de este modo hasta que alcanzamos el incremento que supone construir una pista adecuada para las operaciones del tipo de avión más grande. En esta caso, este incremento se divide igualitariamente entre este número de operaciones. Ejemplo 1.5.1.- Consideramos que m= 3, N1={1,2}, N2={3,4}, N3= {5}y los costes están dados por c1= 10, c2= 25 yc3= 35, para las operaciones de aviones de tipo 1, para las operaciones de aviones de tipo 2, y para las operaciones de aviones del tipo 3, respectivamente. Entonces, la función característica del juego del aeropuerto asociado está dada por v(S) =                        −10 si S⊂ {1,2}, S 6=∅ −25 si S∩N26=∅,5/∈S −35 si 5∈S En la Figura 1.3, aparece representado el esquema secuencial de asignación. Littlechild y Owen (1973 [13]) prueban que el esquema secuencial de asignación descrito anteriormente coincide con el valor de Shapley del juego del aeropuerto asociado. Teorema 1.5.1. Sea (N, v)un juego del aeropuerto. Si denotamos por c0= 0 y para cada i∈N, el tipo de avión de la operación ies li, entonces el valor de Shapley del juego (N, v)puede obtenerse como Φi(v) = li X l=1 −(cl−cl−1) rl , siendo rlel número total de operaciones correspondientes a tipos de avión 1.5. APLICACIONES 35 Figura 1.3: Esquema de asignación secuencial con tamaño igual o superior a l, es decir, rl=m P j=l |Nj|. Juegos de producción lineal Los juegos de producción lineal fueron introducidos en Owen (1975 [16]). Denotemos por Nun conjunto de fabricantes. Cada fabricante i∈Ndispone de cierta cantidad de lmaterias primas, representada por el vector con componentes no negativas ci= (ci 1, ..., ci l)∈Rl. A partir de estas materias primas, se pueden obtener mproductos diferentes mediante un proceso de producción lineal dado por una matriz Ade dimensión l×m, con elementos no negativos y al menos un elemento no nulo en cada fila; el elemento ajk indica el número de unidades de la materia prima j-ésima que son necesarias para producir una unidad del producto k-ésimo. Cada materia prima carece de valor por sí misma. El beneficio de cada fabricante se consigue mediante la venta de los productos finales. El precio de mercado de cada producto está dado por el vector con componentes no negativas b= (b1, ..., bm)∈Rm. El objetivo de cada fabricante es maximizar su beneficio. Así pues, cada fabricante i∈Nse enfrenta a un problema de optimización que puede formularse mediante el problema de programación lineal 1.5. APLICACIONES 36 maximizar byt sujeto a Ayt≤(ci)t, y≥0. El proceso conjunto de producción puede caracterizarse por la cuaterna (N, A, b, c). Supongamos que un grupo de fabricantes deciden cooperar uniendo sus materias primas y fabricando los productos en un único centro de producción. En ese caso la cantidad total de materias primas disponibles para los fabricantes de S⊂Nestá dado por cS∈Rl, donde para cada materia prima j,cS j=Pi∈Sci j. En consecuencia, el beneficio que la coalición S puede conseguir está dado por el valor óptimo del problema de programación lineal PSdefinido como maximizar byt sujeto a Ayt≤(cS)t, y≥0. Esta aproximación sugiere un modo natural de asociar un juego TU a cada proceso de producción (N, A, b, c). En este juego el conjunto de ugadores es Ny la función característica asigna, a cada coalición S⊂N, la ganancia v(S)dada por el valor optimo del problema de programación lineal PS. Nos referimos a este juego con el nombre de juego de producción lineal. Claramente, los juegos de producción lineal son superaditivos. Además, tienen cores no vacío tal como se prueba a continuación. Teorema 1.5.2. Para cualquier proceso de producción lineal (N, A, b, c), el juego de producción lineal asociado tiene core no vacío. Demostración. Sea (N, A, b, c)un proceso de producción lineal y sea (N, v)el juego de producción lineal asociado. Vamos a encontrar un elemento de C(v). Para ello utilizaremos las soluciones óptimas del problema de programación lineal dual de PN, denotado por DN, que está dado por 1.5. APLICACIONES 37 maximizar cNzt sujeto a zA ≥b, z≥0. Por el teorema de dualidad, el conjunto de soluciones óptimas es no vacío y el valor óptimo es v(N). Sea zuna solución óptima de DN. Para cada i∈N, sea xi=cizt. Vamos a probar que x∈C(v). Sea S⊂Ny sea DSel problema de programación lineal dual de PS. Utilizando de nuevo el teorema de dualidad, tenemos que el valor óptimo de DSes v(S). Como z es factible en el problema DS, se cumple que Pi∈Sxi=Pi∈Scizt≥v(S), y Pi∈Nxi=Pi∈Ncizt=v(N). Por tanto, x∈C(v).  El conjunto de asignaciones del core obtenidas del modo descrito anteriormente se denomina conjunto de Owen del juego de producción lineal. Este conjunto ha sido caracterizado en van Gellekom y otros (2000 [17]). En general, es un subconjunto propio del núcleo tal como vemos en el siguiente ejemplo. Ejemplo 1.5.2.- Consideremos el proceso de producción lineal (N, A, b, c) donde A= 1 0 2 1 1 3  , b = (3,1,8), c1= (1,0), c2= (2,2),yc3= (0,2). El problema de programación lineal DNestá dado por 1.5. APLICACIONES 38 minimizar 3z1+ 4z2 sujeto a z1+z2≥3, z2≥1, 2z1+ 3z2≥8, z1, z2≥0. El valor óptimo de este problema es 11 y el conjunto de soluciones óptimas está dado por {(1,2)}. Por tanto, v(N) = 11. La función característica completa de este proceso de producción lineal está dada por v(1) = 0, v(2) = 6, v(3) = 2, v(12) = 6, v(13) = 9/2, v(23) = 9, v(N) = 11. El conjunto de Owen tiene x= (x1, x2, x3)como único elemento, donde x1= (1,0)(1,2)t= 1, x2= (2,2)(1,2)t= 6, x3= (0,2)(1,2)t= 4. Sin embargo, el core del juego de producción lineal está dado por C(v) = conv{(2,6,3),(0,6,5),(0,13/2,9/2),(5/2,13/2,2),(2,7,2)}. Este juego no es convexo. Por ejemplo, considerando S={3}, T ={2,3}e i= 1 tenemos que v(T∪{1})−v(T)=2< v(S∪{1})−v(S) = 5/2.El valor de Shapley está dado por Φ(v) = (13/12,19/3,43/12) y está en el core. Capítulo 2 Juegos cooperativos en contextos formales 2.1. Contextos formales Un retículo es un conjunto parcialmente ordenado (poset) (L, ), donde  es reflexiva, antisimétrica y transitiva, tal que para cualquiera dos elementos x, y ∈L, existe un supremo x∨y, donde la unión disjunta se encuentra en un nivel superior y un ínfimo x∧y, donde la intersección seencuentra en un nivel inferior en el retículo. Si no se produce ninguna ambigüedad, el retículo se denota simplemente por L. El orden dual parcial ∂se define como x∂y si y solo si yx. El dual del retículo (L, )es el poset (L, ∂), denotado como L∂. En la parte superior del retículo se encuentra el top, en el cual se encuentra todas las uniones disjuntas de los elementos y en la parte inferior del retículo está el bottom, que es la intersección de los elementos. Una cadena maximal es un camino que va desde el bottom al top de un retículo. Definición 2.1.1. Un contexto es una tripleta C= (N, M, I), donde Nes un conjunto finito no vacío de objetos, Mes un conjunto finito de atributos, eI:N×M→ {0,1}es una relación binaria definida por I(i, a) = 1 si 2.2. JUEGOS EN CONTEXTOS FORMALES 47 v(1, M)=6, v(13, αβ) = 16, v(12, αγ) = 20 v(123, α) = 32, v(135, β) = 28, v(1246, γ) = 30, v(N, ∅) = 60 El valor v(1, M)representa el pago obtenido por el dueño de la patente si el producto es vendido. Observamos en el ejemplo que las lineas 4 y 6 están duplicadas, linea 7 esta completa, y linea 3 es la intersección de las lineas 1 y 2. Sobre el retículo de conceptos, esto se corresponde respectivamente con el hecho de que 4 y 6 están siempre juntos en un concepto, 7 está siempre presente, y 3 está presente siempre y cuando 1 y 2 lo están. Estas situaciones están recogidas en las nociones de macro-jugador y jugador acompañante. Definición 2.2.2. Sea C= (N, M, I)un contexto para el conjunto de jugadores N. Una coalición K⊆N, |K|>1, es un macro-jugador en Csi K⊆S oK∩S=∅para cada coalición no vacía S∈LN C. Esto es, una coalición que no se puede separar por ninguna factible. Definición 2.2.3. Sea C= (N, M, I)un contexto para el conjunto de jugadores N. Un jugador i∈Nes un acompañante de S, S ⊆N\i, si S∪i∈LN C y para todo T∈LN C, T3isi y solo si S⊆T De la definición tenemos que un macro-jugador se representa como lineas idénticas en la tabla, mientras que un acompañante ide Sse corresponde con la situación donde la linea ies la intersección de las lineas en S. Las siguientes propiedades son importantes: 2.2. VALOR DE SHAPLEY SOBRE CONTEXTOS 48 Nota 2.2.1. (i) Si K, K0 Cson macro-jugadores maximales, entonces K∩K0 C=∅. (ii) Si M0 C(bottom de F) es no vacío, entonces M0 Ces un macro-jugador cuando |M0 C|>1, y un acompañante cuando |M0 C|= 1 (iii) Cuando M0 C=∅, los átomos los cuales no son singleton son macrojugadores, pero al contrario es falso. Precisamente, un macro-jugador Kes un átomo si y solo si K∈ F. (iv) Si ies un acompañante de {j}, entonces {i, j}es un macro-jugador. (v) Si iyjson acompañante de la misma coalición S, entonces {i, j}es un macro-jugador. 2.3. El valor de Shapley para juegos sobre contextos formales Sea C= (N, M, I)un contexto y LN Csu retículo de conceptos por jugadores. Consideramos el conjunto CH(C)de todas las cadenas maximales, y denotamos su cardinalidad por ch(C). Considera una cadena maximal de LN Ccon C∈CH(C), siendo C=M0=⊂S1⊂ · · · ⊂ Sk=N, y un jugador i∈N. Denotamos por Ti CySi Crespectivamente, al último conjunto en la secuencia Cque no contiene a iy el primer conjunto que contiene a i. Figura 2.2: Ejemplo de cadena donde se aprecian los conjuntos Ti CySi C. 2.3. VALOR DE SHAPLEY SOBRE CONTEXTOS 49 Definición 2.3.1. El valor de Shapley de (C, v), denotado por φ(C, v), se define, para cada i∈N, como φi(C, v) =          1 ch(C)P C∈CH(C) 1 |Si C\Ti C|(vN(Si C)−vN(Ti C)) si i6∈ M0 C vN(M0 C) |M0 C|cc. Esta definición es una generalización de los valores introducidos por Faigle y Kern [18], y Bilbao y Edelman [19]. Formulamos propiedades para axiomatizar el valor de Shapley. Sea Fcualquier valor sobre el conjunto de juegos conceptos. Entendemos un valor para juegos de conceptos como una aplicación que obtiene un vector de RNpor cada juego definido en un contexto formal con un conjunto de objetos N. Teniendo en cuenta a v(M0, M)como un pago separable para jugadores en M0, introducimos los siguientes axiomas para un valor F: Axioma 2.3.1 (Axioma de pago separable (SP)).Si (C, v)∈CCG con C= (N, M, I)entonces se tiene: X i∈M0 C Fi(C, v) = v(M0 C, M) Como para el valor de Shapley clásico, nos centramos en los vectores de pagos eficientes. Axioma 2.3.2 (Axioma de eficiencia (E)).Para todo (C, v)∈CCG tenemos X i∈N Fi(C, v) = v(N, N0 C) 2.3. VALOR DE SHAPLEY SOBRE CONTEXTOS 50 Todos los agentes en un macro-jugador de un contexto son equivalentes para el retículo de conceptos, así que su valor debería ser el mismo. Equivalentes en el sentido de que si uno participa en una contribución, el otro participa en la misma y viceversa. Axioma 2.3.3 (Axioma macro-jugador (MP)).Si (C, v)∈CCG con C= (N, M, I)yKes un macro-jugador en LN C, entonces Fi(C, v) = Fj(C, v)∀i, j ∈K Definición 2.3.2. Un contexto C2= (N2, M2, I2)es concatenable a otro contexto C1= (N1, M1, I1)si N1= (M2)0 C2yM1∩M2=∅. El resultado de la concatenación de los dos contextos concatenables es un nuevo contexto C2∗ C1= (N, M, I), donde N=N2, M =M1∪M2y I(i, a) =                I1(i, a)si i∈N1, a ∈M1 I2(i, a)si i∈N2\N1, a ∈M2 1si i∈N1, a ∈M2 0si i∈N2\N1, a ∈M1 Es fácil ver que la concatenación equivale a la concatenación de sus tablas de incidencia y que LC1∗C2es isomorfo a la concatenación de los retículos, concretamente es {(S, A ∪M2)∈LC1} ∪ LC2\ {((M2)0 C2, M2)} Ejemplo 2.3.1.- Consideramos N1={1,2}, N2={1,2,3,4,5}, M1={α, β} yM2={a, b, c, d}. Las dos tablas de incidencias y los conceptos retículos LC1, LC2vienen dado en la Figura 2.4. El resultado de la concatenación C1∗ C2se muestra en la Figura 2.5. 2.3. VALOR DE SHAPLEY SOBRE CONTEXTOS 51 Figura 2.4: Dos contextos C1,C2representados por sus tablas y retículos de conceptos Figura 2.5: La concatenación C1∗ C2de los dos contextos de la Figura 2.4 La concatenación de dos contextos no debería cambiar el pago de los jugadores. Axioma 2.3.4 (Axioma de concatenación (C)).Para todo (C1, v1),(C2, v2)∈ CCG tal que C2es concatenable con C1, y v1(N1, N0 C) = v2((M2)0 C2, M2), tenemos Fi(C2∗ C1, v2∗v1) =    Fi(C2, v2)si i∈N2\N1 Fi(C1, v1)si i∈N1 2.3. VALOR DE SHAPLEY SOBRE CONTEXTOS 52 donde v2∗v1es un juego concepto sobre C=C2∗ C1, definido por: (v2∗v1)(S, A) =    v2(S, A)si N1⊆S v1(S, A \M2)cc Sea C= (N, M, I)un contexto, y consideramos el conjunto de cadenas maximales CH(C) = {C1, ..., Cch(C)}de su retículo de conceptos por jugadores LC. La descomposición en cadenas maximales de Ces una colección de contextos C1, ..., Cch(C)uno por cada cadena, la cual s en particular un sistema de clausura, construido siguiendo el método descrito ene punto (iii) de la Nota 2.1.1. En el siguiente ejemplo mostramos como funciona. Ejemplo 2.3.2.- Continuamos con el Ejemplo 2.1.3 y la Figura 2.2. Descomponemos el contexto Cen tres cadenas maximales C1,C2,C3como se observa en la Figura 2.6. Los contextos C1,C2yC3, correspondientes a dichas cadenas son: C1a b c d 1 x x x 2 x x 3 x x 4 5 x 6 7 x x x x C2a b c d 1 x x 2 x x 3 x x x 4 5 x 6 7 x x x x C3a b c d 1 2 x x x 3 4 x 5 6 x 7 x x x x Axioma 2.3.5 (Axioma de descomposición (D)).Sea (C, v)un juego de conceptos, se verifica que F(C, v) = 1 ch(C) ch(C) X p=1 F(Cp, vp) 2.3. VALOR DE SHAPLEY SOBRE CONTEXTOS 53 Figura 2.6: Descomposición en cadenas maximales donde {C1, ..., Cch(C)es la descomposición por cadenas maximales y con vp(S, A) = v(S, A)para todo (S, A)∈LCpyp= 1, ..., ch(C). Demostramos ahora que el valor de Shapley satisface todos estos axiomas. Teorema 2.3.1. El valor de Shapley satisface (SP), (E), (MP),(C) y (D). Demostración. - Pagos separables: esto se satisface obviamente. - Eficiencia: Sea (C, v)∈CCG con C= (N, M, I). X i∈N φi(C, v) = X i∈M0 φi(C, v) + X i∈N\M0 φi(C, v) =v(M0 C, M) + 1 ch(C)X C∈CH(C) (v(N, N0 C)−v(M0 C, M)) =v(N, N0 C). - Macro-jugadores: Sea (C, v)∈CCG yKun macro-jugador en LC. Si 2.3. VALOR DE SHAPLEY SOBRE CONTEXTOS 54 K=M0 C, por definición, cada jugador en Krecibe el mismo pago con φ. Suponemos ahora K6=M0 C, i.e., K⊆N\M0 C. En este caso, para cualquier i, j ∈Ky para cada C∈CH(C), Si C=Sj CyTi C=Tj C. Por lo tanto, φi(C, v) = φj(C, v)para cada i, j ∈K - Concatenación: Consideramos dos contextos concatenables C1= (N1, M1, I1), C2= (N2, M2, I2)con N1= (M2)0 C2. Observamos que ch(C2∗ C1) = ch(C2)ch(C1). Si i∈(M1)0 C1entonces φi(C2∗ C1, v2∗v1) = (v2∗v1)((M1)0 C1, M1∪M2) |(M1)0 C1|=φi(C1, v1) Si i∈N1\(M1)0 C1, entonces para cualquier cadena maximal Cen C2∗C1 la transición de Ti CaSi Cocurre ch(C1)veces como la misma transición en Crestringido a C1. Por lo tanto, tenemos φi(C2∗ C1, v2∗v1) =1 ch(C2∗ C1)X C∈CH(C2∗C1) 1 |Si C\Ti C|[(v1∗v2)(Si C,(Si C)0 C2∗C1)−(v1∗v2)(Ti C,(Ti C)0 C2∗C1)] =1 ch(C1)X C∈CH(C1) 1 |Si C\Ti C|[v1(Si C,(Si C)0 C1)−v1(Ti C,(Ti C)0 C1)] = φi(C1, v1) Si i∈N2\N1, entonces para cadena maximal Cen C2∗ C1la transición de Ti CaSi Cocurre ch(C2)veces como la misma transición en C restringida a C2. Por lo tanto: 2.3. VALOR DE SHAPLEY SOBRE CONTEXTOS 55 φi(C2∗ C1, v2∗v1) =1 ch(C2∗ C1)X C∈CH(C2∗C1) 1 |Si C\Ti C|[(v1∗v2)(Si C,(Si C)0 C2∗C1)−(v1∗v2)(Ti C,(Ti C)0 C2∗C1)] =1 ch(C2)X C∈CH(C2) 1 |Si C\Ti C|[v2(Si C,(Si C)0 C2)−v2(Ti C,(Ti C)0 C2)] = φi(C2, v2) - Descomposición: Consideramos la descomposición (C1, ..., Cq)en cadenas maximales del contexto C, para el juego (C, v). Por la definición de vp, p = 1, ..., q, tenemos para cada jugador i. φi(C, v) = 1 ch(C)X C∈CH(C 1 |Si C\Ti C|[vN(Si C)−vN(Ti C)] =1 ch(C) ch(C) X p=1 1 |Si C\Ti C|[vN p(Si C)−vN p(Ti C)] =1 ch(C) ch(C) X p=1 φi(Cp, vp) Finalmente, probamos que el valor de Shapley es el único valor para juegos sobre contextos formales que satisfacen los axiomas anteriores.  Teorema 2.3.2. El valor de Shapley es el único valor sobre juegos conceptos que satisface (SP), (E), (MP), (C) y (D). Demostración. Ya hemos probado en el Teorema 2.3.1 que el valor de Shapley satisface todos los axiomas. Solo queda demostrar la unicidad. Sea (C, v)∈CCG un juego concepto con C= (N, M, I)con M={a} (contexto simple). Se tiene que M0 C={i∈N|I(i, a) = 1}, por lo tanto el 2.3. VALOR DE SHAPLEY SOBRE CONTEXTOS 56 retículo de conceptos se reduce a {(M0 C,{a}),(N, ∅)}. En la primera opción, |M0 C|>1, M0 Ces un macro-jugador, y de manera similar N\M0 Ces un macrojugador también. Suponemos primero que M0 C=∅. El axioma (MP) impone que Fi(C, v) = Fj(C, v)para todo i, j ∈N, por tanto por el axioma (E), se sigue que Fi(C, v) = 1 |N|v(N, ∅),∀i∈N por lo que Festé determinado de forma única por ese tipo de juego. Suponemos ahora que M0 Cse reduce a un jugador, llamado {i}. El axioma (SP) impone que Fi(C, v) = v(M0 C, M). Si |M0 C|>1, M0 Ces un macro-jugador, y por el axioma de (MP), se tiene que para cada i, j ∈M0 C, Fi(C, v) = Fj(C, v). Ahora, el axioma (SP) implica que X j∈M0 C Fj(C, v) = v(M0 C, M) luego finalmente Fi(C, v) = v(M0 C, M) |M0 C|, para todo i∈M0 C. Podemos proceder de manera similar con el resto de jugadores en N\M0: aplicando (MP) y (E) finalmente llegamos a Fi(C, v) = 1 |N\M0 C|(v(N, ∅)−v(M0 C, M)),∀i∈N\M0 C En el segundo caso el axioma (SP) garantiza la unidad. Como conclusión, Festá determinada de manera única para cualquier juego (C, v)con C= (N, {a}, I). Consideramos ahora cualquier juego concepto (C, v)y su descomposición en cadenas maximales C1, ..., Cch(C)de C. El axioma de descomposición implica que si Festá determinada de manera única sobre cada C1, ..., Cch(C), entonces 2.4. EL CORE DE UN JUEGO DE CONCEPTOS 63 no tiene vértices). La condición general para ser puntado es que le sistema de ecuaciones x(S)=0,∀S∈ F tenga al 0 como única solución (en ese caso decimos que, siguiendo a Derk y Reijnierse [8], Fes no degenerada). Es fácil de ver que Fes degenerada si existe un macro-jugador Ken F, porque Fcontiene al hiperplano x(K)=0. Un resultado notable en los sistemas cerrados es que el contrario también es cierto. Teorema 2.4.1. Un sistema de clausura es nodegenerado si y solo si no contiene ningún macro-jugador. Demostración. La parte solo si es obvia ya que la presencia de macro-jugador implica degeneración. Suponemos que Fes un sistema de clausura sobre Ncon bottom M0 C, el cual no tiene macro-jugador. Probamos por inducción sobre n=|N|que es no degenerada. Para n= 1, tenemos dos opciones {∅,{1}} y{{1}}. Suponemos que es verdad hasta algún valor n−1y lo probamos para n. Afirmación: existe un i∈Ntal que {i}∈F. Demostración de la afirmación: Como Fno tiene macro-jugadores, sabemos que su bottom M0 Cno es ni ∅ni algún singleton. En el último caso, la afirmación está probada. Suponemos entonces que M0 C=∅. Entonces necesariamente, cada átomo es un singleton. De hecho, supongamos que Ses un átomo, con |S|>1. Desde que Sno es un macro-jugador, existe un T∈ F que separa a S, i.e., j∈T63 kpara algún j, k ∈S. Desde que Fes cerrado bajo intersección, se sigue que S∩T∈ F y∅ 6=S∩T(S, una contradicción 2.4. EL CORE DE UN JUEGO DE CONCEPTOS 64 con el hecho de que Ses un átomo. Consideramos entonces (F \ i) = {S⊆N\i|SoS∪i∈ F} sobre N\i, la colección de conjuntos que se obtienen de Feliminando ien cada conjunto. Notese que ∅ ∈ (F \ i). Probamos que (F \ i)es un sistema de clausura sin macro-jugadores. -F 3 N\i: por la definición anterior. -(F \ i)es cerrado bajo intersección: tomamos S, S0∈(F \ i). Entonces tenemos tres casos. Si S, S0 C∈ F, entonces S∩S0 C∈ F yi /∈S∩S0 C, por tanto S∩S0 C∈(F \ i). Si S∈ F yS0 C∪i∈ F, entonces i /∈ S∩(S0 C∪i)∈ F, y además S∩(S0 C∪i) = S∩S0 C∈(F \ i). Por último, si S∪i, S0 C∪i∈ F, entonces i∈(S∪i)∩(S0 C∪i)∈ F, además ((S∪i)∩(S0 C∪i)) \i=S∩S0 C∈(F \ i) -(F \ i)no tiene macro-jugadores: suponemos que K⊆N\ies un F−i.Tomamos S∈ F−i. Entonces o S∩K=∅oS∪i⊇Kes verdad porque K63 i. Por tanto Kes un macro-jugador en F, lo que es una contradicción. Luego (F \ i)es un sistema cerrado sin macro-jugadores sobre N\i, y por la hipótesis de inducción, (F \i)es no degenerada, i.e., el sistema de ecuaciones x(S)=0, S ∈ F tiene como única solución x= 0. Finalmente, observamos que el sistema x(S)=0, S ∈ F difiere de la anterior solamente por la adición de xien algunas lineas. Como {i}∈F, la linea xi= 0 ambos sistemas son equivalentes restringidos a otras variables. Además, Fes no degenerada. El siguiente ejemplo muestra que este resultado no se extiende a colecciones de conjuntos arbitrarios. Ejemplo 2.4.3.- Tomamos n= 5 y la colección Fen la Figura 2.8. Fno es cerrada bajo intersección pero no tiene macro-jugador. Sin embargo es degenerada (el rango es 4 y (1,-1,0,1,-1) es un vector del espacio nulo). 2.4. EL CORE DE UN JUEGO DE CONCEPTOS 65 Figura 2.8: Familia Fdel ejemplo. Volvamos a la cuestión de si el core es no acotado. El siguiente resultado nos es útil.  Teorema 2.4.2. El cono de recesión de un juego sobre una colección de conjuntos Fes un subespacio linear si y solo si F \ {∅, N}es una colección equilibrada. Corolario 2.4.1. El core esta acotado (equivalentemente, el cono de recesión se reduce a {0}) si y solo si Fes no degenerada y F \ {∅, N}es equilibrada. Esta situación se resume en la tabla. M0 C=∅ |M0 C|= 1 |M0 C|= 1 puntuado si Fno tiene macro-jugador si Fno tiene macro-jugador no acotado si Fequilibrado y no macro-jugador no no Tabla 1: Cuando el core de los alcances es acotado y puntuado Para cualquier colección B ⊆ 2N\{∅}, su clausura por intersección denotada por Bestá formada por todos los conjuntos de B, más la intersección de cualquier familia de conjuntos de B, siempre que la intersección sea no vacía1. Nótese que (·)es un operador de cierre, en el sentido que B=B,B ⊆ B, y B ⊆ B0implica que B ⊆ B0. 1Hay que tener cuidado ya que esto no significa que Bes cerrada bajo intersección, desde que Bno contiene al conjunto vacío, a pesar que debe contener conjuntos disjuntos. 2.4. EL CORE DE UN JUEGO DE CONCEPTOS 66 Teorema 2.4.3. Suponemos Bes una colección equilibrada sobre N. Entonces B, su clausura por intersección, es equilibrada. Demostración. Probamos el resultado por inducción sobre |N|. El resultado es trivialmente verdadero cuando |N|= 1. Suponemos que la propiedad es verdadera para todo Nde tamaño al menos n, y lo probamos para |N|=n+1. Suponemos que existe un macro-jugador K, y sea [k]un (nuevo) jugador que reemplaza a K. Entonces considerando N0 C= (N\K)∪{[k]}, podemos definir una colección equilibrada desde Bsobre N0 C, y desde que |N0 C|< n, el resultado se demuestra por hipótesis de inducción. Podemos además considerar en el resto de la demostración que no existes macro-jugadores. Esto implica en particular que |B| >1y que ningún conjunto S∈ B,|S|>1el cual es disjunto con otro conjunto. Suponemos primero que B 3 Stal que S∩T=∅para todo T∈ B, T 6=S, con |S|= 1. Entonces observamos que B \ {S}es una colección equilibrada sobre N\S. Por hipótesis de inducción, B \ {S}es equilibrado, como B= B \ {S}∪{S}, el resultado está probado en este caso. Suponemos por el contrario que para cada S∈ B, S intersecta algún T∈ B. Afirmamos que la colección B∩={S∩T|S, T ∈ B, S 6=T}es equilibrada. Como la unión de colecciones equilibradas es equilibrada, (ver , e.g., Owen [17]), se tiene que B ∪ B∩es equilibrada sobre N. Aplicando el mismo procedimiento sobre B ∪ B∩se llega a otra colección equilibrada, y continuando de la misma forma, como es un proceso finito, se llega a B, probando que es equilibrada. Demostración de la afirmación: Tomamos (λS)S∈B cualquier sistema de pesos para B. Para cada i∈N, consideramos la subcolección Bi={S1, ..., Sk}de B de conjuntos que contienen a i. Observese que Bi6=∅ya que Bes equilibrado, yk > 1. De hecho, k= 1 da como resultado λS1= 1. Por hipótesis, existe T∈ B cortando a S1, además existe j6=i, j ∈T∩S1, y PT03jλT0= 1 lo cual implica que λT= 0, lo que es imposible. 2.4. EL CORE DE UN JUEGO DE CONCEPTOS 67 Para cada Biconstruimos la colección de parejas de intersecciones Bi ∩= {Sj∩Sl|Sj, Sl∈ Bi, Sj6=Sl}, con los siguientes pesos λi S=X Sj,Sl∈Bi Sj6=Sl Sj∩Sl=S λSj+λSl k−1,para cada S∈ Bi ∩ Por construcción, cada λi Ses positivo, y tenemos X S∈Bi ∩ λi S=1 k−1 k X j=1 k X l=j+1 (λSj+λSl) = k X j=1 λSj= 1 Claramente, B∩=Si∈NBi ∩, sin embargo algunos conjuntos deben estar presentes en dos diferentes Bi ∩, posiblemente con dos ponderaciones diferentes. El ultimo paso es definir una única ponderación para cada S∈ B∩, manteniendo la condición de normalización. Observe que si Saparece en Bi ∩y Bj ∩, Entonces S⊇ {i, j}. Como no existen macro-jugadores, {i}∈Bi ∩, y {j}∈Bj ∩. Se define λ0 S=min(λi S, λj S) , y asumiendo que λi S< λj S, se define λ0 {j}=λj {j}+ (λj S−λi S) Observe que λ0 S>0, λ0 {j}>0. Reiterando este razonamiento para otros conjuntos λ0 T=λi Tpara algún i, el sistema de ponderaciones (λ0 S)S∈B∩satisface P T3i λ0 T= 1 para todo i∈N.  2.4. EL CORE DE UN JUEGO DE CONCEPTOS 68 Lema 2.4.1. Suponemos que Bes una colección equilibrada sobre N. Entonces Bcontiene todos los singletons en Nsi y solo si Bno tiene macro-jugador. Demostración. ⇒) Claro. ⇐) Suponemos que Bno tiene macro-jugadores y para algún i∈N, {i}/∈B. Entonces TB∈B,B3iB=S3S, con |S|>1. Desde que Sno es un macro-jugador, debe existir un T∈ B tal que T63 i yT∩S6=∅. Tomamos j∈T∩S, y consideramos un sistema balanceado (λB)B∈B para B. Entonces 1 = X B∈B,B3i λB<X B∈B,B3i λB+λT≤X B∈B,B3j λB= 1 que es una contradicción.  Notese que ⇒) se verifica también si Bno es equilibrado. Una consecuencia inmediata es: Corolario 2.4.2. Si Bes una colección equilibrada sobre N, entonces B contiene a todos los macro-jugadores en By todos los singletons en Nno contenidos en ningún macro-jugador. Demostración. Si no hay macro-jugadores, se aplica el Lema 2.4.1. En otro caso, reemplazar cada macro-jugador por un solo jugador y aplicar el Lema 2.4.1.  Nota 2.4.1. (i) Si Bes mínima equilibrada y no contiene macro-jugadores, entonces B 6=B. Esto está claro por el Lema 2.4.1 y al hecho de que una colección equilibrada minimal tiene al menos nconjuntos. (ii) Nos podríamos preguntar si una versión dual del Teorema 2.4.2 existe, i.e.: Si Bis equilibrado y B=B, entonces su abierto B0(i.e., eliminando todos los conjuntos que son intersección de otros) es equilibrado. 2.4. EL CORE DE UN JUEGO DE CONCEPTOS 69 Esto no es cierto como se demuestra en el siguiente ejemplo: tomamos N={1,2,3,4}y la colección equilibrada B={12,23,2,134,14,34} (λS=1 3puede ser tomado por cualquier S∈ B). Su clausura es B={12,23,2,134,14,34,1,3,14,4} y es equilibrado por el Teorema 2.4.2. Ahora su abierto es B0={12,23,134,14,34} pero no es una colección equilibrada, como se puede ver. (iii) Observar que en general B1∪ B2⊆ B1∪ B2posiblemente con inclusión estricta (e.g., toma B1={1,23}yB2={12,3}). Esto no es seguro porque se puede obtener cualquier colección cerrada equilibrada como unión de las colecciones equilibradas de clausura minimal. Llegamos al resultado final. Teorema 2.4.4. Asumimos M0 C=∅. Entonces el core de cualquier juego balanceado es acotado si y solo si Fno tiene macro-jugadores y F \{∅, N}se obtiene como la clausura bajo intersección de la unión de algunas colecciones equilibradas minimales sobre N, i.e., F \ {∅, N}=SBi. Demostración. ⇐) Sabemos que la unión de colecciones equilibradas es equilibrada, por el Teorema 6, F \ {∅, N}es equilibrada. Como no existe macrojugadores, por el Lema 1, Fcontiene a todos los singletons, y es además no degenerada. Por lo tanto el core(0) = {0}por el Corolario 1. ⇒)core(0) = {0}si y solo si Fes no degenerada y F \{∅, N}es equilibrada. Como Fes cerrada bajo intersección, se tiene que F \ {∅, N}es la clausura de alguna colección equilibrada B, con F \ {∅, N} ⊇ B ⊆ (F \ {∅, N}. Como Bes la unión de algunas colecciones equilibradas minimales, F \{∅, N}tiene la forma que buscamos. Finalmente, como Fes no degenerada, implica que 2.4. EL CORE DE UN JUEGO DE CONCEPTOS 70 Fno contiene ningún macro-jugador.  Tanto el teorema como la observación (iii), nos da una idea para derivar cualquier sistema Fcerrado bajo intersección tal que F \{∅, N}es equilibrado. Es suficiente para generar todas las colecciones minimales equilibradas, excepto para N(ver [9] para la descripción de un algoritmo para generar colecciones minimales equilibradas), y construye todas las posibles uniones de ellos, luego toma sus clausuras bajo intersección. Esto da F \ {∅, N}. Capítulo 3 Valores de compromiso en contextos formales El problema más estudiado en la teoría de juegos cooperativos es como dividir la ganancia total de la gran coalición si todos los jugadores cooperan. Algunos conceptos de solución han sido propuestos para resolver este problema, como los ya estudiados en la sección anterior, que son el valor de Shapley, el core y el nucleolo en juegos de utilidad transferibles (TU-games). El objetivo de este capítulo es estudiar un tipo particular de conceptos de solución, los valores de compromiso. Un valor de compromiso es un concepto de solución que pertenece a la combinación convexa de dos vectores, llamados vector superior e inferior. Los ejemplos mas notables de valores de compromiso son el τ-valor para TU-games y la solución de Raiffa-Kalai-Smorodinsky para problemas de negociación. Vamos a centrar nuestra atención en el valor de compromiso τ-valor. Estudiaremos estos valores de compromiso en la literatura clásica así como para los juegos en contextos formales. Centramos el estudio para el caso de contextos regulares y por la regularización de contextos, se extiende al caso general. Se demostrarán ciertas propiedades de los valores de compromiso 3.2. CONTEXTOS REGULARES 79 Para el caso que en Ctengamos M6=∅se añade a la formula anterior el atributo nuevo a c M=h(M\N0)\h[ L (L\aL)ii∪a La relación viene dada por la matriz de incidencia que no cambia. b I(i, b) = I(i, b)∀b6=a Cuando M06=∅la relación para el nuevo atributo es b I(i, a)=0 ∀i Al tener el nuevo contexto b Cregularizado, el juego se ve modificado. Por ello se define un nuevo juego para el contexto regular. (C, v)→(b C,b v) Definición 3.2.2. Sea (S, A)∈ Lb C, entonces se define el nuevo juego como b v(S, A) =                      v S∪"S K∩S6=∅ K\iK#,(A∪N0)∪"S L∩A6=∅ L\aL#∪a! b v(∅, Mb C)=0 solo si M0 C6=∅ 3.2. CONTEXTOS REGULARES 80 donde Kes un macro-jugador, Les un macro-atributo y aes el nuevo atributo creado en el caso que M0 C6=∅. En la siguiente sección presentamos cuatro valores de compromiso. Dos de ellos basados en la idea de τ-valor y los otros dos basados en la idea de χvalor. Para ello, introducimos el concepto solución sobre juegos en contextos formales. Ejemplo 3.2.1.- Regularización de un contexto. El siguiente contexto no es regular ya que M0 Cno es vacío y N0 Cno es vacío. Comenzamos introduciendo un nuevo atributo. a b c d 1 x x 2 x x x 3 x x x 4 x x 5 x x x x 6 x x x 7 x x x 8 x x Existen dos macro-jugadores K1={2,3,6}yK2={4,8}estos se pueden ver en la tabla ya que la intersección de sus filas es el vacío. Tratamos a los macro-jugadores como a un solo jugador quedando el nuevo contexto como sigue 3.2. CONTEXTOS REGULARES 81 a c d e 1 x 2 x x 4 x 5 x x x 7 x x Definición 3.2.3. Sea (C, v)un contexto no regular y sea Kun macrojugador. Sea funa solución sobre juegos en contextos regulares y sea iKel representante del macro-jugador. Se tiene que fi(C, v) =    fi(b C,b v)i6∈ K fiK(b C,b v)/|K|i∈K La definición anterior es una extensión de fque verifica la condición de igual tratamiento en macro-jugadores, es decir, si Kes un macro-jugador entonces todos sus jugadores reciben el mismo pago. Teniendo en cuenta como se extiende una solución para contextos generales, nos centraremos en el resto del capítulo en contextos que son regulares. 3.3. τ-VALORES 82 3.3. τ-Valores Los dos primeros valores de compromiso que presentamos se basan en la idea del τ-valor. Donde tenemos dos vectores uno superior y otro inferior. El vector superior mantiene el mismo significado, i.e., el mayor pago que el jugador ipuede esperar. En esta y en las secciones restantes representamos al vector superior como Qi(C, v)para diferenciarlo del vector superior presentado anteriormente. De la misma forma representamos el valor inferior como qi(C, v). Veremos que existen varias opciones para generalizar la idea de τ-valor, en particular nosotros vamos a tratar con dos de ellas. τ-Valor basado en coaliciones maximales El primer τ-valor centra su atención en las coaliciones factibles, (S, A)∈ LC, que son maximales y que no contienen al jugador i, para el cálculo de su vector superior. Como en el caso clásico el τ-valor, para juegos quasi-equilibrados en contextos, es un compromiso entre el vector superior e inferior para un juego. Definición 3.3.1. Sea (C, v)∈CCG. Se define el vector superior Q1(C, v)∈ RNcon coordenadas Q1 i(C, v) = m´ax {S∈Mi}(1 |N\S|[v(N, ∅)−v(S, S0 C)]) Dado el vector superior, introducimos el vector inferior como q1(C, v)con coordenadas q1 i(C, v) = m´ax {S,S0 C)∈LC} {i∈S}(v(S, S0 C)−X {j∈S\i} Q1 j(C, v)) 3.3. τ-VALORES 83 donde Mi(C)={S⊆N\ {i}: (S, S0 C)∈ LC,S maximal }(maximal en el sentido de la contención) es el conjunto de las coaliciones maximales que no contienen a i, esto es, cualquier otro concepto (T, T0 C)tal que Sesté contenido en T, ocurre que iestá en T. La interpretación del vector superior en este caso es la siguiente. Dado un jugador ien el tau-valor el jugador buscaba la única contribución marginal en una coalición maximal en la estructura 2N. Ahora el jugador iselecciona la mejor entre todas las opciones que tiene pero teniendo en cuenta que ese beneficio no es sólo para él sino que tiene que compartirlo con los jugadores de N−S. La definición de quasi-equilibrado para este caso sería, siguiendo el modelo general q1(v)≤ Q1(v)yX i∈N q1 i(v)≤v(N)≤X i∈N Q1(v) Definición 3.3.2. Para un juego v∈ QBN, el τ1-valor de v, denotado por τ1(v), es el único vector sobre la recta-segmento en RNcuyos puntos extremos son q1(v)yQ1(v). Así que tenemos: τ1(v) := q1(v) + α Q1(v)−q1(v)! donde αes tal que Pi∈Nτ1 i(v) = v(N) Ejemplo 3.3.1.- Continuación. Recordamos la tabla de valores asociada al retículo de conceptos: 3.3. τ-VALORES 84 (S, S0) (1, abc) (4, bde) (5, cde) (12, bc) (35, ce) (45, de) (124, b) (1235, c) (345, e) (N, ∅) v(S, S0)10 20 20 50 30 40 40 50 40 100 a b c d e 1 x x x 2 x x 3 x x 4 x x x 5 x x x Calculamos q1(v)yQ1del juego: M1={(345)} Q1 1= m´ax s∈M1 {1 2[100 −40]}= 30 M2={(345)} Q1 2= m´ax s∈M2 {1 2[100 −40]}= 30 M3={(124)} Q1 3= m´ax s∈M3 {1 2[100 −40]}= 30 M4={(1235)} Q1 4= m´ax s∈M4 {[100 −50]}= 50 M5={(124)} Q1 5= m´ax s∈M5 {1 2[100 −40]}= 30 3.3. τ-VALORES 85 q1 1= m´ax{10,50 −30,40 −80,50 −90,100 −140}= 20 q1 2= m´ax{50 −30,40 −80,50 −90,100 −140}= 20 q1 3= m´ax{30 −30,50 −90,40 −80,100 −140}= 0 q1 4= m´ax{20,40 −30,40 −60,40 −60,40 −60,100 −120}= 20 q1 5= m´ax{20,30 −30,40 −50,50 −90,40 −80,100 −140}= 20 Tenemos el vector superior e inferior Q1= (30,30,30,50,30) q1= (20,20,0,20,20) Puede comprobarse que el juego es quasi-equilibrado y su tau-valor es: τ1(v) = (22.22,22.22,6.66,26.66,22.22) τ-Valor basado en particiones conceptuales maximales En esta sección definimos que es una partición conceptual para un contexto (C, v). Definición 3.3.3. Sea Cun contexto. Una partición conceptual de S⊆N es P={S1, ..., Sr}de forma que Sl∩Sp=∅ ∀l, p = 1, ..., r l 6=p r S p=1 Sp⊆S; (Sp)00 C=S ∀i∈S\r S p=1 Sp→i00 C∩ r S p=1 Sp∪N\S!6=∅ Una partición conceptual de una coalición es una partición de dicha coalición 3.3. τ-VALORES 86 en coaliciones que estén definidas el retículo de contextos, aunque no cubra la coalición completa, es decir, algunos jugadores de la coalición original pueden no estar presentes en la partición, debido a la estructura del retículo. Definición 3.3.4. Si P, b Pson particiones conceptuales de Sen Centonces Pb Psi ∀T∈P⇒ ∃ b T∈b Pcon T⊆b T Sea PC(S)la familia de particiones conceptuales maximales de Sen C. Con esta partición ya podemos definir los vectores superior e inferior de (C, v). Definición 3.3.5. Sea (C, v)∈CCG, se define el vector superior Q2 i(C, v)∈ RN, con coordenadas Q2 i(C, v) = m´ax {P∈PC(N\i)}(v(N, ∅)−X T∈P v(T, T0 C)) Dado el vector superior, introducimos el vector inferior comoq2 i(C, v)con coordenadas q2 i(C, v) = m´ax {(S,S0 C)∈LC} {i∈S}(v(S, S0 C)−X j∈S\i Q2 j(C, v)) donde PCson las particiones conceptuales maximales de N\i. Un juego (C, v)∈CCG es quasi-equilibrado si y solo si: q2(v)≤ Q2(v)yX i∈N q2 i(v)≤v(N)≤X i∈N Q2(v) 3.3. τ-VALORES 87 Igual que para el caso clásico definimos el siguiente valor de compromiso. Definición 3.3.6. Para un juego v∈ QBN, el τ2-valor de v, denotado por τ2(v), es el único vector eficiente sobre la recta-segmento en RNcuyos extremos son q2(v)yQ2(v). Así que tenemos: τ2(v) := q2(v) + α Q2(v)−q2(v)! donde αes tal que Pi∈Nτ2 i(v) = v(N) Ejemplo 3.3.2.-. Continuación del Ejemplo 3.3.1. P(N\1) = {(345)} Q2 1=v(N)−v(345) = 100 −40 = 60 P(N\2) = {(1)(345)} Q2 2=v(N)−v(1) −v(345) = 100 −40 −10 = 50 P(N\3) = {{(5),(124)},{(12),(45)}} Q2 3= m´ax{v(N)−v(5) −v(124), v(N)−v(12) −v(45)}= 40 P(N\4) = {(1235)} Q2 4=v(N)−v(1235) = 100 −50 = 50 P(N\5) = {(124)} Q2 5=v(N)−v(124) = 100 −40 = 60 3.4. χ-VALORES 88 q2 1= m´ax{10,50 −50,40 −50 −50,50 −50 −40 −60, 100 −50 −40 −50 −60}= 10 q2 2= m´ax{50 −60,40 −110,50 −160,100 −210}=−10 q2 3= m´ax{30 −60,50 −170,40 −110,100 −220}=−30 q2 4= m´ax{20,40 −60,40 −110,40 −100,100 −210}= 20 q2 5= m´ax{20,30 −40,40 −50,50 −150,40 −90,100 −150}= 20 Tenemos el vector superior e inferior Q2= (60,50,40,50,60) q2= (10,−10,−30,20,20) Puede comprobarse que el juego es quasi-equilibrado y su τ2-valor es: τ2(v) = (28,11.6,−4.8,30.8,34.4) 3.4. χ-Valores En esta sección definimos el χ-valor para un juego sobre contextos formales. La única diferencia radica en que el vector superior de un jugador ies la máxima de las contribuciones marginales. χ-Valor basado en coaliciones maximales Definición 3.4.1. Sea C= (N, M, I)un contexto. Un activo simple de un jugador i∈Nen Ces un par de coaliciones (S;T)que satisfacen las siguientes condiciones. 1. (S, S0 C),(T, T0 C)∈LC, y 3.4. χ-VALORES 95 Demostración. Recordamos que q3 i(C, v) = m´ax (S,S0 C)∈LC i∈S(v(S, S0 C)−P j∈S\i Q3 j(C, v)), por lo que, como (i00 C, i0 C)∈ LC⇒q3 i≥v(i00 C, i0 C)−P j∈i00\i Q3 j(C, v). Vamos a probar que ∀(S, S0 C)∈ LCcon i∈Socurre que v(S, S0 C)−X {j∈S\i} Q3 j≤v(i00 C, i0 C)−X {j∈i00\i} Q3 j(C, v) Definimos para cada (S, S0 C)con i∈S,hScomo la mínima longitud de una cadena de (S, S0 C)a(i00, i0 C). Ejemplo de hS= 2 Demostramos la desigualdad anterior por inducción en hS. Si hS= 0 ⇒S= i00 Cy está probado. Si hS= 1 entonces existe una cadena (i00, i0 C)<(S, S0 C) Se verifica que v(S, S0 C)−X j∈S\i Q3 j(C, v) =(1) v(S, S0 C)−X j∈S\i00 C Q3 j(C, v)−X j∈i00 C\i Q3 j(C, v) Se tiene que (S, i00 C)∈ Bj(C)∀j∈S\i00 C, luego 3.4. χ-VALORES 96 S\i00 C⊆S\i Q3 j≥1 |S\i00 C|[v(S, S0 C)−v(i00 C, i0 C)] Por lo tanto −X j∈S\i00 C Q3 j≤v(i00 C, i0 C)−v(S, S0 C) y la igualdad (1) queda como v(S, S0 C)−X j∈S\i Q3 j≤v(i00 C, i0 C)−X j∈i00 C\i Q3 j Supongamos cierta la desigualdad anterior con hS≤p−1. Vamos a demostrarlo para hS=p. 3.4. χ-VALORES 97 Para cada j∈S\Sp−1ocurre que (S;Sp−1)∈ Bj(C)⇒ Q3 j(C, v)≥[v(S, S0 C)−v(Sp−1,(Sp−1)0 C)] 1 |S\Sp−1| por lo que −X j∈S\Sp−1 Q3 j(C, v)≤v(Sp−1,(Sp−1)0 C)−v(S, S0 C) Por lo tanto, 3.5. COMPARATIVA DE LOS VALORES DE COMPROMISO 98 v(S, S0 C)−X j∈S\i Q3 j(C, v) = v(S, S0 C)−X j∈S\Sp−1 Q3 j(C, v)−X j∈Sp−1\i Q3 j(C, v) ≤v(Sp−1,(Sp−1)0 C)−X j∈Sp−1\i Q3 j(C, v) ≤v(i00 C, i0 C)−X j∈i00 C\i Q3 j(C, v) La última desigualdad es cierta por inducción, ya que hSp−1≤p−1. Observa que al menos existe una cadena de (Sp−1,(Sp−1)0 C)a(i00 C, i0 C)de tamaño p−1.  3.5. Comparativa de los valores de compromiso En la siguiente tabla se compara los distintos valores de compromiso calculados anteriormente, x1x2x3x4x5 τ1(v)22.22 22.22 6.66 26.66 22.22 τ2(v)28 11.6 -4.8 30.8 34.4 χ3(v)15.45 25.45 8.18 28.18 22.72 χ4(v)26.67 10 0 30 33.33 Para tener una visión más global de la asignación que le correspondería a cada agente, calculamos la media aritmética de los valores de compromisos anteriormente calculados, la cual conserva las propiedades de eficiencia y racionalidad individual. La media aritmética por jugador es la siguiente: (23.085,17.3175,2.51,28.91,28.1675) 3.6. AXIOMATIZACIONES Y EL CORE 99 Se aprecia que los agentes 4 y 5 obtiene aproximadamente la misma cantidad. El agente numero 1 y 2 obtiene un poco menos que los anteriores. Y el agente 3 es el que obtiene menos de todos. En diferencia con el valor de Shapley (18.57,27.14,11.42,22.85,20), este último hace un reparto más equitativo. A los agentes 4 y 5 le asigna menos que los valores de compromiso, así como al agente 1. Los agentes 2 y 3 reciben más con el valor de Shapley. 3.6. Axiomatizaciones y el Core Definición 3.6.1. Se dice que un contexto C= (N, M, I)es de partición si para todo i∈Nocurre que i00 C={i}. Como consecuencia todo elemento de la forma (i, i0)∈Cpara i∈N. También se tiene que para todo S∈Nexiste una partición conceptual de Sde forma que cubre la coalición completa. En particular S=S {i∈S} ies una partición conceptual, cumpliendo ese hecho. Centraremos esta sección en contextos regulares de partición, y en particular en los valores τ3(v)yχ4(v). Sea C= (N, M, I)un contexto de partición y sea (C, v)un juego sobre dicho contexto. Definimos el vector superior asociado a este juego como Qi(C, v) = m´ax {Pm(N\i)}[v(N, N0)−X {Sp∈Pm(N\i)} v(Sp, S0 p)]. Aquí lo que hacemos es reescribir Q3yQ4sin tener que dividir entre varios. Observación 3.6.1. Observar que como en nuestro caso tenemos la desigualdad Qi(C, v)≥xi≥qi(C, v)para todo i∈N, donde x∈Core(C, v) podemos asegurar la existencia del τ-valor. A continuación damos una axiomatización del τ-valor. Introduciremos antes 3.6. AXIOMATIZACIONES Y EL CORE 100 los axiomas y veremos que nuestro valor los verifica. El primer axioma es el de eficiencia que verifica trivialmente al ser una imputación. Introducimos a continuación la noción de covarianza. Definición 3.6.2. Sea C= (N, M, I)un contexto de partición y sean (C, v) y(C, w)dos juegos sobre dicho contexto. Diremos que estos juegos son covariantes si existe d, juego aditivo y un número real a, tal que w(S, S0) = av(S, S0) + Pi∈Sdi,para todo S∈C. Introducimos los siguientes axiomas para un valor sobre juegos de conceptos. Axioma 3.6.1. Axioma de covarianza en contextos de partición. Sea Ψ:Γ(C,P,N,M)→Rnun valor sobre dicho espacio, donde Ces el contexto, Pla partición, Nel número de agentes y Mlos handicaps. Diremos que Ψ verifica covarianza si para todo par de juegos covariantes (C, v)y(C, w)se tiene que Ψi(C, w) = aΨi(C, v) + di, i ∈N. Introducimos ahora el tercer axioma llamado de proporcionalidad. Axioma 3.6.2. Axioma de proporcionalidad para Q3(Q4): Sea C= (N, M, I)un contexto de partición y sea (C, v)un juego sobre conceptos. Supongamos que el vector inferior es nulo, es decir, q3(C, v) = 0 (q4(C, v) = 0). Diremos entonces que un valor Ψsobre (C, v)verifica pro- 3.6. AXIOMATIZACIONES Y EL CORE 101 porcionalidad si existe una constante ctal que Ψi(C, v) = cQ4 i(C, v)para todo i∈N. Para ver que nuestro valor verifica covarianza introducimos la función gap. Definición 3.6.3. . Sea (C, v)un juego sobre conceptos. Dado un vector superior Q(C, v), definimos la función gap para contextos de partición como g(S, S0) = X i∈S Qi(C, v)−v(S, S0) y el vector de concesión λi= m´ın (S,S0 C∈LC)g(S, S0) Proposición 3.6.1. Sea (C, v)un juego sobre conceptos y Qun vector superior. Entonces qi(C, v) = Qi(C, v)−λi(C, v) Demostración. Observar que qi(C, v) = m´ax {S∈C, i∈S}[v(S, S0)−Q(C, v)(S\i)] = m´ax {S∈C, i∈S}[Qi(C, v)+(v(S, S0)−Q(C, v)(S)] = Qi(C, v)+ m´ax {S∈C, i∈S}[v(S, S0)−Q(C, v)(S)] = Qi(C, v)−m´ın {S∈C, i∈S}[Q(C, v)(S)−v(S, S0)] = Qi(C, v)−λi(C, v).  Proposición 3.6.2. Sean (C, w)y(C, v)dos juegos covariantes en contextos de partición de manera que w=v+d, donde des un juego aditivo. Entonces 3.6. AXIOMATIZACIONES Y EL CORE 102 1. Qi(C, w) = Q(C, v) + di. 2. λi(C, w) = λi(C, v). 3. qi(C, w) = qi(C, v) + di. Demostración. Se prueban los puntos anteriores. 1. Q2 i(C, w) = m´ax {Pm(N\i)}[w(N, N0)−X Sp∈Pm(N\i) w(Sp, S0 p)] Observar que como (i, i0)es factible para todo i∈Nentonces P0= Si∈N\ii=N\{i}es una partición de factibles que cubre a todo N\{i}. Observar también que a su vez si una partición maximal no cubriese a N\ {i}se le podría añadir los jugadores que no contuviese de N\ {i} y así cubriría a todo el conjunto, es decir, de toda partición maximal Pde N\ {i}se pude afirmar que verifica que P0 P.Luego cualquier partición maximal de N\ {i}cubre a N\ {i}. Como wyvson covariantes se tiene que τi(C, w) = m´ax {Pm(N\i)}[w(N, N0)−X Sp∈Pm(N\i) w(Sp, S0 p)] = m´ax {Pm(N\i)}[v(N, N0) + d(N)−X Sp∈Pm(N\i) v(Sp, S0 p)−d(Sp)] = m´ax {Pm(N\i)}[v(N, N0)−X Sp∈Pm(N\i) v(Sp, S0 p)+(d(N)−X Sp∈Pm(N\i)) d(Sp)] = m´ax {Pm(N\i)}[v(N, N0)−X Sp∈Pm(N\i) v(Sp, S0 p)] + di=τi(C, v) + di. Esto último es debido a que des aditivo y la partición maximal cubre aN\i. 3.6. AXIOMATIZACIONES Y EL CORE 103 2. λi(C, w) = m´ın {S∈C,i∈S}g(S, S0) = m´ın {S∈C, i∈S}Q(C, w)(S, S0)−w(S, S0) = m´ın {S∈C, i∈S}Q(C, v)(S, S0)−v(S, S0) + d(S)−d(S) = λi(C, v). Observar que hemos usado el apartado 1 de esta proposición y la aditividad de d. 3. Es consecuencia directa de la proposición 2 y de los dos primeros items de esta.  Teorema 3.6.1. El valor τ2(χ4)es el único valor que verifica sobre los contextos de partición eficiencia, covarianza y Q2(Q4)-proporcionalidad. Demostración. La prueba de que verifica los axiomas es inmediara por definición y la proposición 3.  En el siguiente teorema se muestra la relación de los valores τ2yχ4con los vectores del core del juego de contextos. Teorema 3.6.2 (Acotación del Core).Si x∈Core(C, v)con Cregular y de partición, entonces q2≤x≤Q2yq4≤x≤Q4 3.6. AXIOMATIZACIONES Y EL CORE 104 Demostración. Recordemos que Q2 i(C, v) = m´ax P∈PC(N\i)([v(N)−PT∈Pv(T)]) Si el x∈Core(C, v)yP∈ PC(N\i)⇒x(N) = v(N, N0 C)yx(T)≥ v(T, T0 C)∀T∈P Por lo tanto −x(T)≤ −v(T, T0 C)∀T∈P Así, para cualquier P∈ PC(N\i) Q2 i≥v(N, N0 C)−X T∈P v(T, T0 C)≥x(N)−X T∈P x(T) Pero como P∈ PC(N\i)yCes de partición, tenemos que P T∈P x(T) = x(N\i). Luego Q2 i≥x(N)−x(N\i) = xi Recordamos que Q4 i(C, v) = m´ax S∈LC m´ax P∈PC(S\i)([v(S)−X T∈P v(T)]) Pero se observa que podemos tomar (S, S0 C)=(N, N0 C), luego Q4 i≥Q2 i≥xi Por otro lado,