El valor de Shapley
Full text
Traballo Fin de Grao El valor de Shapley David Bamio Martínez 2019/2020 UNIVERSIDADE DE SANTIAGO DE COMPOSTELA
GRAO DE MATEMÁTICAS Traballo Fin de Grao El valor de Shapley David Bamio Martínez Xullo 2020 UNIVERSIDADE DE SANTIAGO DE COMPOSTELA
Trabajo propuesto Área de coñecemento: Estatística e Investigación Operativa Título: El valor de Shapley Breve descrición do contido Tras una introducción a la teoría de juegos, se estudiarán las propiedades más importantes del valor de Shapley, algunos procedimientos de cálculo (como las extensiones multilineares), variaciones (como el índice de Banzhaf-Coleman o el valor de Owen) y campos de aplicación como el diseño de tarifas o la medida del poder en una organización.
Índice general Resumen vii Introducción ix 1. El valor de Shapley: denición y algunos resultados 1 1.1. Introducción a los juegos de utilidad transferible . . . . . . . . . . . . . . . 1 1.2. Construcción axiomática del valor de Shapley . . . . . . . . . . . . . . . . . 5 2. Extensiones multilineales 15 2.1. Denición y relación con el valor de Shapley . . . . . . . . . . . . . . . . . . 15 2.2. Interpretación probabilística y aplicaciones . . . . . . . . . . . . . . . . . . . 18 2.3. Extensiones multilineales de juegos compuestos . . . . . . . . . . . . . . . . 22 3. Otros valores relacionados con el valor de Shapley 27 3.1. El índice de poder de Banzhaf-Coleman . . . . . . . . . . . . . . . . . . . . 27 3.2. El valor coalicional de Owen . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.3. El valor de Myerson y otros valores relacionados . . . . . . . . . . . . . . . . 35 4. Aplicaciones 41 4.1. El juego del aeropuerto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 4.2. El juego del pase a museos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 4.3. El problema de bancarrota . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 5. Conclusiones 49 Bibliografía 51 v
Resumen El valor de Shapley busca obtener un procedimiento justo para distribuir los benecios (o costes) generados por un proyecto conjunto. Esta propuesta está basada en las contribuciones marginales de los agentes a dicho proyecto. En el presente trabajo mostramos que el valor de Shapley queda caracterizado de forma única por una serie de propiedades deseables y hallamos su fórmula explícita. Estudiamos algunas formas alternativas de cálculo del valor mediante extensiones multilineales de juegos, ya que su computación directa puede requerir la suma de un número elevado de términos. Estudiamos también otros valores relacionados, como son el índice de poder de Banzhaf-Coleman, el valor de Owen y el valor de Myerson. Finalmente, se muestran algunas aplicaciones del valor a problemas reales como el diseño de tarifas, repartición de ganancias o el pago a acreedores tras una quiebra. Abstract The Shapley value seeks to obtain a fair procedure to distribute the benets (or costs) generated by a joint project. This proposal is based on the agents' marginal contributions to said project. In this work we show that the Shapley value is uniquely determined by a series of desirable properties and we nd its explicit formula. We study some alternative ways of calculating the value using multilinear extensions of games, since computing it directly can require the sum of a very large number of terms. We also study other related values, such as the Banzhaf-Coleman power index, the Owen value and the Myerson value. Finally, we show some applications of the value to real problems such as designing a schedule of fees, sharing prots or paying creditors after a bankruptcy. vii
1.1. INTRODUCCIÓN A LOS JUEGOS DE UTILIDAD TRANSFERIBLE cada posición nal posible en el mismo. En el caso de los juegos TU, se pueden formar grupos de jugadores (que denominaremos coaliciones ) que fuercen determinados repartos. Así pues, un juego TU puede ser denido mediante una función que asigna a cada coalición posible un número real que indica el pago asociado a dicha coalición. Denición 1.1. Un juego TU es un par (N, v) donde N es el conjunto nito de jugadores y v: 2N−→ R es una función que cumple que v(∅)=0 . La función v se denomina función característica del juego. Su dominio es el conjunto de todos los subconjuntos de N , que denotamos por 2N . Dada una coalición S⊂N , v(S) representa el pago asegurado por los jugadores de S , independientemente de las estrategias del resto de jugadores. Se denotará por G(N) el conjunto de todos los juegos TU con conjunto de jugadores N , y por n la cardinalidad de N . Por simplicidad, en general identicaremos (N, v) con su función característica v . Ejemplo 1.2. ( Juego del guante ). Tres jugadores están dispuestos a repartirse los bene- cios derivados de la venta de un par de guantes. El jugador 1 tiene un guante izquierdo, mientras que los jugadores 2 y 3 tienen un guante derecho cada uno. Supongamos que un par de guantes se puede vender por una unidad monetaria. Identicando dinero con utilidad, esta situación se puede modelizar como el juego (N, v) con N={1,2,3} , v(1) = v(2) = v(3) = v(23) = 0 y v(12) = v(13) = v(N)=1 . 1 / Veamos ahora una clase de juegos TU especialmente relevante. Denición 1.3. Sea un juego v∈G(N) . Diremos que v es superaditivo si, para cualquier par de coaliciones disjuntas S, T ⊂N , se tiene que v(S∪T)≥v(S) + v(T) . Se denotará por SG(N) el conjunto de los juegos TU de G(N) que son superaditivos. Nótese que en un juego superaditivo se generan verdaderos incentivos para la cooperación entre jugadores, ya que la unión de dos grupos disjuntos cualesquiera nunca provoca una disminución de los benecios obtenidos por separado. Consideremos ahora las siguientes deniciones: Denición 1.4. Se dice que un juego v∈G(N) es de suma constante si, para todo S⊂N , v(S) + v(N\S) = v(N). 1 Por simplicidad, usaremos v(1) para referirnos a v({1}) , v(12) para v({1,2}) , etc. 2
CAPÍTULO 1. EL VALOR DE SHAPLEY: DEFINICIÓN Y ALGUNOS RESULTADOS Denición 1.5. Se dice que un juego v∈G(N) está en normalización (0,1) si 1. v({i})=0 , para todo i∈N , 2. v(N)=1 . Denición 1.6. Se dice que un juego v∈G(N) en normalización (0,1) es simple si, para cada S⊂N , tenemos que v(S)=0 o v(S) = 1 . Esencialmente, un juego simple es aquel en el que cada coalición es, o bien ganadora (pago 1), o bien perdedora (pago 0), sin ningún término intermedio. Dentro de estos juegos, distinguimos los juegos de mayoría ponderada: Denición 1.7. Sea ( p1, p2, ..., pn ) un vector no negativo, y sea q un número real que satisface 0< q ≤ n X i=1 pi. El juego de mayoría ponderada [ q;p1, p2, ..., pn ] es el juego simple v∈G(N) denido por v(S) = 0 si Pi∈Spi< q, 1 si Pi∈Spi≥q. Ejemplo 1.8. Consideremos el Parlamento de Galicia formado tras las elecciones de septiembre de 2016, cuya composición, de un total de 75 diputados, fue la siguiente: PPdeG (Partido Popular de Galicia) con 41 diputados, PSdeG (Partido dos Socialistas de Galicia) con 14 diputados, EM (En Marea) con 14 diputados y BNG (Bloque Nacionalista Galego) con 6 diputados. Las mayoría de las decisiones del Parlamento, entre ellas la elección del Presidente de la Xunta, se toman por regla de mayoría simple. Así pues, el Parlamento de Galicia puede entenderse como un juego de mayoría ponderada [ q;p1, p2, p3, p4 ] donde q= 38 y los pi representan el número de escaños de cada partido político (1=PPdeG, 2=PSdeG, 3=EM, 4=BNG). En este juego, p1= 41 ≥q= 38 , por lo que v(S)=1 para toda coalición S que contenga al jugador 1 y v(S)=0 en otro caso. En particular, v(1) = 1 , por lo que el jugador 1 ostenta todo el poder (se dice que el jugador 1 es un dictador para este juego) mientras que los demás no tienen ningún poder de decisión (son jugadores nulos , tal y como se denirán más adelante). / Denición 1.9. Sean M1, M2, ..., Mnn conjuntos disjuntos y no vacíos; sean w1, w2, ..., wn juegos simples en normalización (0,1) , con conjuntos de jugadores M1, M2, ..., Mn , respectivamente; sea v∈G(N) un juego no negativo. Entonces, la composición de w1, w2, ..., wn con v , denotada por u=v[w1, w2, ..., wn], 3
1.1. INTRODUCCIÓN A LOS JUEGOS DE UTILIDAD TRANSFERIBLE es el juego con conjunto de jugadores M∗= n [ j=1 Mj y función característica u(S) = v({j|wj(S∩Mj)=1}), para S⊂M∗ . Heurísticamente, el juego compuesto u representa una división entre comités Mj . Los miembros de Mj eligen un representante mediante el juego wj ; luego, los n representantes juegan el juego v entre ellos. Ejemplo 1.10. Consideremos en este caso el Colegio Electoral de los Estados Unidos. Cada uno de los 50 estados, además del Distrito de Columbia, tiene asignado un número de compromisarios que depende de la población del estado, siendo 3 el número mínimo. Tras la celebración de las elecciones, los candidatos presidencial y vicepresidencial que reciban la mayoría del voto popular en un estado obtienen la totalidad de los votos por parte de los compromisarios de dicho estado. 2 El número total de compromisarios en el Colegio Electoral es de 538, siendo necesaria una mayoría absoluta de 270 votos electorales para ser presidente. Sea entonces v el juego de mayoría ponderada de 51 jugadores [ 270; 55,38, ..., 3,3 ], cuyos jugadores son los estados de los EE. UU. Para cada j , Mj representaría el conjunto de votantes del estado j ; wj sería un juego de mayoría simple (i. e., un juego donde gana la coalición con más miembros) con conjunto de jugadores Mj . Así pues, las elecciones presidenciales se pueden entender como un juego simple u=v[w1, w2, ..., w51] con conjunto de jugadores M∗= 51 [ j=1 Mj que consiste en el número total de votantes en los EE. UU. En denitiva, cada wj es el juego entre los Mj votantes del estado j , v es el juego del Colegio Electoral entre los 51 estados, y u es el juego entre todos los votantes de los EE. UU. Un conjunto S⊂M∗ es ganador (i. e., u(S) = 1 ) si contiene un subconjunto de la forma S0=[ j∈T Sj, donde wj(Sj)=1 para todo j∈T y v(T)=1 , siendo T un subconjunto de los 51 estados y cada Sj un subconjunto de Mj . Esto es, un candidato gana si recibe la mayoría del 2 En los estados de Maine y Nebraska se pueden repartir los votos electorales entre varios candidatos. Obviaremos esta particularidad para no distraer del foco del ejemplo. 4
CAPÍTULO 1. EL VALOR DE SHAPLEY: DEFINICIÓN Y ALGUNOS RESULTADOS voto popular ( wj(Sj)=1 ) en estados que sumen un total de, como mínimo, 270 votos electorales ( v(T) = 1 ). / El objetivo principal de la teoría de juegos TU es proponer, para cada juego TU, una asignación o conjunto de asignaciones que pueda ser aceptado por todos los jugadores involucrados en el problema. Uno de los enfoques para alcanzar este objetivo está basado en la idea de estabilidad : se trata de buscar un conjunto de soluciones estable en el sentido de que los acuerdos que cabe esperar que un grupo de jugadores racionales realicen sea un elemento de dicho conjunto. Relacionado con esta idea, se dene el siguiente concepto: Denición 1.11. Sea v∈G(N) . Una imputación de v es un vector x ∈Rn que satisface las dos condiciones siguientes: 1. xi≥v({i}) , para todo i∈N . 2. Pi∈Nxi=v(N) . Se denotará por I(v) el conjunto de imputaciones de v . Así pues, una imputación es una división de v(N) entre todos los jugadores de forma que ningún jugador reciba menos de lo que obtendría por sí mismo. Nótese que, si v∈SG(N) , entonces I(v)6=∅ . Será deseable que la solución alcanzada sea una imputación, ya que sería una solución estable, en el sentido de que no deja insatisfecho a ningún jugador. Un segundo enfoque para alcanzar soluciones aceptables por los jugadores está basado en la idea de ecuanimidad : se trata de proponer un reparto justo, en el sentido de que se asigne a cada jugador un pago que tenga en cuenta, de alguna manera, su contribución a las ganancias de cada coalición posible. El valor de Shapley surge en el contexto de la búsqueda de un reparto ecuánime. 1.2. Construcción axiomática del valor de Shapley La aproximación de Shapley [20] es axiomática: su valor está caracterizado de forma única por una serie de propiedades que un reparto ecuánime debería cumplir. Antes de presentar tales propiedades, es necesario dar varias deniciones. Denición 1.12. Llamamos valor a cualquier aplicación f:G(N)−→ Rn . Denición 1.13. Sea v∈G(N) un juego TU. 1. Decimos que i∈N es un jugador nulo de v si, para cada S⊂N , v(S∪ {i}) = v(S) . 5
1.2. CONSTRUCCIÓN AXIOMÁTICA DEL VALOR DE SHAPLEY 2. Dos jugadores i, j ∈N se denominan simétricos si, para cada coalición S⊂N\{i, j} , se tiene que v(S∪ {i}) = v(S∪ {j}) . Denición 1.14. ( Propiedades de Shapley ). Sea f un valor y consideremos las siguientes propiedades: 1. Eciencia: f satisface la propiedad de eciencia si, para todo v∈G(N) , se tiene que X i∈N fi(v) = v(N). Es decir, f debe repartir v(N) entre todos los jugadores. 2. Jugador nulo: f satisface la propiedad de jugador nulo si, para todo v∈G(N) y para todo i∈N jugador nulo de v , se tiene que fi(v) = 0 . Esto quiere decir que los jugadores nulos, ya que no generan benecios para ninguna coalición, no deben recibir nada. 3. Simetría: f satisface la propiedad de simetría si, para todo v∈G(N) y para todo par de jugadores i, j ∈N simétricos en v , se tiene que fi(v) = fj(v) . Es decir, dos jugadores que aportan los mismos benecios deben recibir lo mismo. 4. Aditividad: f satisface la propiedad de aditividad si, para todo par de juegos u, v ∈G(N) , se tiene que f(u+v) = f(u) + f(v) . Cabe recordar que un juego es esencialmente una función de valor real, por lo que es posible hablar de la suma de dos o más juegos. La aditividad es básicamente un requerimiento técnico necesario para caracterizar el valor de Shapley de cualquier juego. Estas son las propiedades de Shapley. Resulta un hecho notable que estas cuatro propiedades básicas sean sucientes para caracterizar un valor único para todos los juegos. Para demostrarlo, es necesario enunciar una serie de lemas previos. Lema 1.15. Sea Φ un valor que cumple las propiedades de Shapley. Para cada coalición no vacía S⊂N , denimos el juego wS∈G(N) por wS(T) = 1 si S⊂T, 0 si S6⊂ T. Entonces, si s es el número de jugadores en S , Φi(wS) = 1/s si i∈S, 0 si i /∈S. 6
CAPÍTULO 1. EL VALOR DE SHAPLEY: DEFINICIÓN Y ALGUNOS RESULTADOS Demostración. Es fácil ver que todos los jugadores que no forman parte de S son jugadores nulos, por lo que Φi(wS) = 0 para todo i /∈S . Análogamente, todos los jugadores que forman parte de S son simétricos entre sí, y por lo tanto Φi(wS)=Φj(wS) para todo i, j ∈S . Como hay s jugadores en S y, por eciencia, la suma de sus asignaciones es wS(N)=1 , se sigue que Φi(wS)=1/s para todo i∈S . Lema 1.16. Sea v∈G(N) . Existen 2n−1 números reales cS , con S⊂N , S6=∅ , tales que v=X S⊂N cSwS, donde wS se dene como en el Lema 1.15. Demostración. Tengamos en cuenta que cada juego v∈G(N) se puede ver como un vector real: (v(S))S∈2N\{∅} ∈R2n−1 . Así pues, podemos pensar en G(N) como un espacio vectorial ( 2n−1 )-dimensional, con lo que la demostración del lema se reduce a probar que W(N) = {wS:S∈2N\ {∅}} es una base de dicho espacio vectorial. Hay 2n−1 elementos en W(N) , por lo que es suciente con ver que son vectores linealmente independientes. En efecto, sean αS∈R para todo S∈2N\ {∅} y consideremos X S∈2N\{∅} αSwS= 0. Supongamos ahora que existe T∈2N\ {∅} con αT6= 0 y asumamos, sin pérdida de generalidad, que no existe e T(T tal que αe T6= 0 . Tenemos ahora que X S∈2N\{∅} αSwS(T) = αT, lo cual es una contradicción. Por tanto, αS= 0 para todo S∈2N\ {∅} , con lo que queda probado que W(N) es una base de G(N) . Teorema 1.17. Existe un único valor Φ: G(N)−→ Rn que satisface las propiedades de eciencia, jugador nulo, simetría y aditividad. Demostración. Por el Lema 1.15, la función Φ , que verica las propiedades de Shapley, está denida de forma única para cada wS . El Lema 1.16 nos dice que cualquier juego puede ser escrito como una combinación lineal de juegos wS . Así pues, aplicando la propiedad de aditividad se prueba que Φ está denida de forma única para todo v∈G(N) . Pasaremos ahora a construir la forma explícita de la función Φ para luego comprobar que efectivamente satisface las propiedades de Shapley. Sabemos por el Lema 1.16 que, 7
1.2. CONSTRUCCIÓN AXIOMÁTICA DEL VALOR DE SHAPLEY para S6=∅ , v=X S⊂N cSwS y por tanto, dado i∈N , Φi(v) = X S⊂N cSΦi(wS) =X S⊂N i∈S cS·1 s. (1.1) Sea cS=X T⊂S (−1)s−tv(T), (1.2) donde t es el número de elementos en T , y probemos que los coecientes cS así denidos satisfacen el Lema 1.16. Si U es una coalición cualquiera y S6=∅ , tenemos que X S⊂N cSwS(U) = X S⊂U cS =X S⊂U X T⊂S (−1)s−tv(T)! =X T⊂U X S⊂U S⊃T (−1)s−t v(T). Ahora bien, para cada valor de s entre t y u , habrá u−t u−s conjuntos S con s elementos tales que T⊂S⊂U . Por tanto, la suma comprendida entre paréntesis en la última expresión puede sustituirse por u X s=tu−t u−s(−1)s−t. Esta expresión es, de hecho, la expansión binomial de (1 −1)u−t . Por tanto, será cero de forma trivial para todo t<u , y de la expansión se deduce que será 1 para t=u . Así pues, obtenemos que X S⊂N S6=∅ cSwS(U) = v(U) para todo U⊂N , satisfaciendo así el Lema 1.16. Sustituyendo la expresión (1.2) en (1.1), 8
CAPÍTULO 1. EL VALOR DE SHAPLEY: DEFINICIÓN Y ALGUNOS RESULTADOS tenemos que Φi(v) = X S⊂N i∈S 1 s X T⊂S (−1)s−tv(T)! =X T⊂N X S⊂N T∪{i}⊂S (−1)s−t1 s·v(T) . Denotemos γi(T) = X S⊂N T∪{i}⊂S (−1)s−t1 s. Es fácil ver que, si i /∈T0 y T=T0∪ {i} , entonces γi(T0) = −γi(T) ; todos los términos de la expresión permanecen iguales salvo que t=t0+ 1 , por lo que se produce un cambio de signo. Esto signica que podemos expresar Φi de la siguiente forma: Φi(v) = X T⊂N i∈T γi(T) [v(T)−v(T\{i})] . Ahora bien, si i∈T , hay exactamente n−t s−t coaliciones S con s elementos tales que T⊂S . Así pues, γi(T) = n X s=t (−1)s−tn−t s−t1 s = n X s=t (−1)s−tn−t s−tZ1 0 xs−1dx =Z1 0 n X s=t (−1)s−tn−t s−txs−1dx =Z1 0 xt−1 n X s=tn−t s−t(−1)s−txs−tdx =Z1 0 xt−1(1 −x)n−tdx. Notemos que esta integral es la función beta, que se dene de la forma siguiente: B(p, q) . . =Z1 0 xp−1(1 −x)q−1dx =(p−1)!(q−1)! (p+q−1)! . Por tanto, γi(T) = B(t, n −t+ 1) = (t−1)!(n−t)! n!, y de este modo tenemos que Φi(v) = X T⊂N i∈T (t−1)!(n−t)! n![v(T)−v(T\{i})] . (1.3) 9
1.2. CONSTRUCCIÓN AXIOMÁTICA DEL VALOR DE SHAPLEY Esta es la fórmula explícita del valor de Shapley. Ahora podemos probar que Φ satisface las propiedades de Shapley. Consideremos v∈G(N) . Eciencia: X i∈N Φi(v) = X i∈NX T⊂N i∈T (t−1)!(n−t)! n![v(T)−v(T\{i})] =X i∈NX T⊂N i∈T (t−1)!(n−t)! n!v(T)−X i∈NX T⊂N i∈T (t−1)!(n−t)! n!v(T\{i}) =X T⊂N t(t−1)!(n−t)! n!v(T)−X T⊂N T6=N (n−t)t!(n−t−1)! n!v(T) =v(N). Jugador nulo: Si i∈N es jugador nulo de v , entonces v(T) = v(T\{i}) para todo T⊂N , y por tanto Φi(v) = 0 . Simetría: Consideremos i, j ∈N simétricos en v . Φi(v)−Φj(v) = X T⊂N i∈T (t−1)!(n−t)! n![v(T)−v(T\{i})] −X T⊂N j∈T (t−1)!(n−t)! n![v(T)−v(T\{j})] =X T⊂N i,j∈T (t−1)!(n−t)! n![v(T)−v(T\{i})−v(T) + v(T\{j})] =X T⊂N i,j∈T (t−1)!(n−t)! n![v(T\{j})−v(T\{i})] = 0. Nótese que, como i, j son simétricos en v , se tiene que v(S∪ {i}) = v(S∪ {j}) para todo S⊂N\{i, j} . Tomando S=T\{i, j} , v(S∪ {j}) = v(T\{i}) y v(S∪ {i}) = v(T\{j}) . 10
CAPÍTULO 1. EL VALOR DE SHAPLEY: DEFINICIÓN Y ALGUNOS RESULTADOS Aditividad: Consideremos v, w ∈G(N) . Φi(v)+Φi(w) = X T⊂N i∈T (t−1)!(n−t)! n![v(T)−v(T\{i})] +X T⊂N i∈T (t−1)!(n−t)! n![w(T)−w(T\{i})] =X T⊂N i∈T (t−1)!(n−t)! n![v(T) + w(T)−v(T\{i})−w(T\{i})] =X T⊂N i∈T (t−1)!(n−t)! n![(v+w)(T)−(v+w)(T\{i})] = Φi(v+w). Queda así comprobada la existencia del valor que postulaba el Teorema 1.17. En el caso de que v sea un juego simple, el cálculo del valor de Shapley se simplica especialmente. El término v(T)−v(T\{i}) siempre tendrá valor 0 o 1 , siendo 1 cuando T sea una coalición ganadora pero T\{i} no. Así pues, podemos escribir Φi(v) = X T∈Ti (t−1)!(n−t)! n!, donde Ti es el conjunto de todas las coaliciones ganadoras T tales que T\{i} es perdedora. Ejemplo 1.18. Consideremos una empresa con cuatro accionistas que tienen 10, 20, 30 y 40 acciones de un total de 100, respectivamente. Para tomar una decisión es necesaria la aprobación de accionistas que sostengan una mayoría simple de las acciones. Podemos tratar esta situación como un juego de 4 personas en el que las coaliciones ganadoras son: {2,4} , {3,4} , {1,2,3} , {1,2,4} , {1,3,4} , {2,3,4} y {1,2,3,4} . Para hallar Φ1 3 , notemos que la única coalición ganadora T tal que T\{1} es perdedora es {1,2,3} . Por tanto, t= 3 y Φ1=2!1! 4! =1 12. Las coaliciones ganadoras que se vuelven perdedoras si eliminamos al jugador 2 son {2,4} , {1,2,3} y {1,2,4} . Por tanto, Φ2=1!2! 4! +2!1! 4! +2!1! 4! =1 4. Del mismo modo, observamos que T3={{3,4},{1,2,3},{1,3,4}} y T4= {{2,4},{3,4}, {1,2,4},{1,3,4},{2,3,4}}, obteniendo que Φ3=1 4 y Φ4=5 12 . 3 Cuando no haya posibilidad de ambigüedad, escribiremos Φi en lugar de Φi(v) para evitar una notación demasiado prolija. 11
2.2. INTERPRETACIÓN PROBABILÍSTICA Y APLICACIONES Ejemplo 2.4. Consideremos nuevamente el juego del guante, del que obtuvimos la EML en el Ejemplo 2.2: f(x1, x2, x3) = x1x2+x1x3−x1x2x3. Tenemos que f1(x1, x2, x3) = x2+x3−x2x3, de modo que f1(x, x, x)=2x−x2, e, integrando, Φ1=Z1 0 f1(x, x, ..., x)dx =x2−x3 31 0 =2 3. Del mismo modo, f2(x1, x2, x3) = x1−x1x3, f2(x, x, x) = x−x2, de donde se obtiene que Φ2=Z1 0 f2(x, x, ..., x)dx =x2 2−x3 31 0 =1 6. Por simetría, Φ3 es también 1 6 . Así pues, hemos obtenido con este método el mismo valor de Shapley que en el Ejemplo 1.21. / 2.2. Interpretación probabilística y aplicaciones La EML de un juego v admite una interpretación probabilística. Sea S una coalición formada de manera aleatoria y supongamos que el evento Ai denido por {i∈S} tiene probabilidad xi para i= 1, ..., n , y que estas probabilidades son independientes. Entonces, para cada S⊂N se tiene que Prob {S=S}=Y i∈S xiY i/∈S (1 −xi), y por tanto, E[v(S)] = f(x1, ..., xn). Heurísticamente, podemos decir que si cada jugador i∈N tiene probabilidad xi de unirse a la coalición, entonces la coalición S puede esperar un pago de f(x1, ..., xn) . 18
CAPÍTULO 2. EXTENSIONES MULTILINEALES Teorema 2.5. Sea v un juego de suma constante y f su EML. Entonces, para cualquier (x1, x2, ..., xn) , se tiene que f(1 −x1,1−x2, ..., 1−xn) = v(N)−f(x1, x2, ..., xn). Demostración. Empleando la interpretación probabilística de las EML, es fácil ver que la probabilidad de que se forme la coalición N\S dadas las probabilidades 1−xi es la misma que la probabilidad de que se forme la coalición S dadas las probabilidades xi . Así pues, tenemos que f(1 −x1,1−x2, ..., 1−xn) = E[v(N\S)], donde S es la coalición aleatoria denida anteriormente. Entonces, f(1 −x1,1−x2, ..., 1−xn) + f(x1, x2, ..., xn) = E[v(N\S) + v(S)]. Ahora bien, v es un juego de suma constante, por tanto v(N\S) + v(S) = v(N) para todo S⊂N . Con esto, f(1 −x1,1−x2, ..., 1−xn) + f(x1, x2, ..., xn) = v(N), como queríamos demostrar. En la sección anterior obtuvimos el valor de Shapley integrando las derivadas parciales de f a lo largo de la diagonal principal x1=x2=... =xn del cubo [0,1]N . Sin embargo, esta nueva evaluación contiene el mismo número de sumas que la fórmula original además de una integral, con lo que su computación no se ha simplicado en absoluto. No obstante, la interpretación probabilística de las EML nos permite aplicar algunos teoremas de la teoría de la probabilidad. En particular, será de especial utilidad el teorema central del límite , que establece que la suma de n variables aleatorias independientes e idénticamente distribuidas puede aproximarse a una distribución normal para un n lo sucientemente grande. Consideremos nuevamente la ecuación (2.6). En ella, el coeciente de v(S∪ {i})−v(S) es Y j∈S xjY j /∈S j6=i (1 −xj), que podemos interpretar como la probabilidad de que S=S , donde S es un subconjunto aleatorio de N\{i} , cuya distribución viene dada por el hecho de que, para cada j6=i , Prob {j∈S}=xj, 19
2.2. INTERPRETACIÓN PROBABILÍSTICA Y APLICACIONES y todos los eventos Aj:{j∈S} son independientes. Por tanto, podemos escribir que fi( x ) = E[v(S∪ {i})−v(S)]. (2.7) Supongamos ahora que v es un juego simple en normalización (0,1) . Esto quiere decir que v(S∪ {i})−v(S) es igual a 1 si S pierde pero S∪ {i} gana, y es 0 en cualquier otro caso. Así pues, fi( x ) = Prob {S pierde ,S∪ {i} gana }. Supongamos, además, que v es un juego de mayoría ponderada representado por [ q;p1, ..., pn ]. Tenemos que fi( x ) = Prob {q−pi≤Y < q}, donde Y es la variable aleatoria Y=X j∈S pj, o, equivalentemente, Y=X j∈N j6=i Zj donde Zj es una variable aleatoria igual a pj si j∈S e igual a 0 en caso contrario. Es fácil ver que Zj tiene media pjxj y varianza p2 jxj(1 −xj) . Como las variables Zj son independientes, Y tiene media y varianza µ(Y) = X j6=i pjxj, σ2(Y) = X j6=i p2 jxj(1 −xj). La distribución de Y , que es la suma de n−1 variables aleatorias, en general no es fácil de obtener. Sin embargo, bajo ciertas condiciones (principalmente, que n sea lo sucientemente grande y ninguna variable Zj tenga una varianza considerablemente mayor que las demás), podemos aplicar el teorema central del límite y aproximar Y por una variable aleatoria con distribución normal. Concluimos de este modo que fi( x ) es aproximadamente igual a la probabilidad de que una variable aleatoria normal ˜ Y , con media µ(Y) y varianza σ2(Y) , satisfaga q−pi−1 2≤˜ Y≤q−1 2, donde el término 1 2 se incluye como corrección de continuidad, al estar aproximando una variable aleatoria discreta con valores enteros por una variable continua. En el caso particular x = (x, x, ..., x) , la media y la varianza toman la siguiente forma: µ(Y) = xX j6=i pj, 20
CAPÍTULO 2. EXTENSIONES MULTILINEALES σ2(Y) = x(1 −x)X j6=i p2 j. Así pues, podemos integrar numéricamente esta probabilidad para obtener una aproximación del valor de Shapley. Ejemplo 2.6. Volvamos al juego del guante explicado en el Ejemplo 1.2, pero esta vez generalizado, para ilustrar la utilidad de la interpretación probabilística de las EML. Consideremos L y R dos conjuntos disjuntos de l y r elementos respectivamente, y sea N=L∪R . Cada miembro de L tiene un guante izquierdo y cada miembro de R , uno derecho. El juego del guante v asociado a estos conjuntos viene denido por v(S) = m´ın{|S∩R|,|S∩L|}, para todo S⊂N , ya que v(S) es el número total de pares de guantes que se pueden formar con los miembros de S . Asumamos ahora que i∈R y consideremos la ecuación (2.7). Es fácil ver que, para i /∈S , v(S∪ {i})−v(S) será igual a 1 si sl> sr y 0 en otro caso, donde sl=|S∩L| y sr=|S∩R| . Por tanto, fi( x ) = Prob {sl> sr}, donde, en este caso, sl=|S∩L| y sr=|S∩R| . Sea x = (x, x, ..., x) ; sl es una variable aleatoria que sigue una distribución binomial de parámetros l y x (es decir, sl∼ Bin (l, x) ), mientras que sr sigue una distribución Bin (r−1, x) . Asumiendo que l y r son grandes, podemos aplicar el teorema central del límite para aproximarlas por variables aleatorias con distribución normal con misma media y varianza. Su diferencia Y=sl−sr tiene la media y varianza siguientes: µ(Y) = µ(sl)−µ(sr) = lx −(r−1)x= (l−r+ 1)x, σ2(Y) = σ2(sl) + σ2(sr) = lx(1 −x)+(r−1)x(1 −x)=(l+r−1)x(1 −x). Así pues, aplicando la corrección de continuidad, obtenemos la siguiente aproximación para los i∈R : fi(x, x, ..., x)≈ Prob {Y≥1 2}, donde Y es una variable aleatoria normal con la media y varianza calculadas arriba. Para los i∈L , tan solo hay que intercambiar los parámetros r y l en dichas expresiones. Para calcular el valor de Shapley aplicamos la fórmula (2.5), integrando numéricamente para 0≤x≤1 . La siguiente función creada con el lenguaje de programación nos permite aproximar el valor de Shapley para el juego del guante generalizado: 21
2.3. EXTENSIONES MULTILINEALES DE JUEGOS COMPUESTOS guante<-function(r,l){ fr<-function(x){ media=(l-r+1)*x; desv_tip=sqrt((l+r-1)*x*(1-x)); fi=1-pnorm(0.5,media,desv_tip); return(fi) } shapley_r=integrate(fr,0,1)$value print(paste("Valor de Shapley para jugadores de R=",shapley_r)) fl<-function(x){ media=(r-l+1)*x; desv_tip=sqrt((r+l-1)*x*(1-x)); fi=1-pnorm(0.5,media,desv_tip); return(fi) } shapley_l=integrate(fl,0,1)$value print(paste("Valor de Shapley para jugadores de L=",shapley_l)) } Evaluando para r= 96 y l= 101 , por ejemplo, obtenemos que Φi= 0,66394 para i∈R y Φi= 0,32056 para i∈L . Nótese que 0,66394 ·96 + 0,32056 ·101 ≈96 , debido a la propiedad de eciencia. Se puede apreciar que, a pesar de que el exceso de guantes izquierdos es relativamente pequeño, la ventaja que obtienen los miembros de R es bastante grande en comparación. / 2.3. Extensiones multilineales de juegos compuestos Consideramos, a continuación, el comportamiento de las EML bajo la composición de juegos. Para los juegos simples w1, w2, ..., wn en normalización (0,1) con conjuntos de jugadores M1, M2, ..., Mn y el juego no negativo v∈G(N) , con N={1,2, ..., n} , se dio en la Denición 1.9 la fórmula u(S) = v({j|wj(S∩Mj)=1}), (2.8) 22
CAPÍTULO 2. EXTENSIONES MULTILINEALES para S⊂M∗=Sj∈NMj , que dene el juego compuesto u=v[w1, ..., wn] . Consideremos, sin embargo, la fórmula u(S) = X T⊂NY j∈T wj(Sj)Y j /∈T [1 −wj(Sj)] v(T), (2.9) o, equivalentemente, u(S) = f(w1(S1), ..., wn(Sn)), (2.10) donde Sj=S∩Mj y f es la EML de v . Si los juegos wj son simples, vemos que (w1(S1), w2(S2), ..., wn(Sn)) = αT, donde T⊂N viene dado por T={j|wj(Sj)=1} , y así, u(S) = f(αT) = v(T). De este modo, vemos que las fórmulas (2.8) y (2.9) coinciden para juegos simples. No obstante, la fórmula (2.9) es aplicable también a juegos no simples sujetos a las siguientes condiciones: C1. wj(S)≥0 , para todo S⊂Mj , C2. wj(Mj)=1 , para todo j∈N . Así pues, la fórmula (2.9) es una generalización de (2.8). Sea gj , con j∈N , la EML de wj . Entonces, gj es una función que lleva el cubo [0,1]Mj a los números reales. De hecho, por las condiciones C1 y C2, la imagen de gj es el intervalo unidad [0,1] . El producto cartesiano g=g1×g2×... ×gn es una función cuyo dominio es [0,1]M1×[0,1]M2×... ×[0,1]Mn= [0,1]M∗ y cuya imagen es [0,1]N . La función g viene dada por g( x )=(g1(x1), g2(x2), ..., gn(xn)), donde xj es la restricción del vector x a los índices i∈Mj . La EML de v , f , tiene como dominio [0,1]N . Podemos, por tanto, formar la función compuesta h( x ) = f(g1(x1), g2(x2), ..., gn(xn)), denida en el cubo [0,1]M∗ . Veamos ahora que h es una función multilineal de las variables xi , i∈M∗ . Supongamos que i∈Mj . Por hipótesis, los conjuntos Mk son disjuntos, y por tanto los gk(xk) , para k6=j , no dependen de xi . Por consiguiente, ∂h ∂xi =∂f ∂gj ∂gj ∂xi 23
2.3. EXTENSIONES MULTILINEALES DE JUEGOS COMPUESTOS o, denotando mediante subíndices la diferenciación parcial, hi( x ) = fj(g( x ))(gj)i(xj). Ahora bien, como gj es multilineal, su derivada (gj)i no depende de xi . Por ser f también multilineal, su derivada fj solo depende de los gk(xk) , k6=j , así que no depende de xi . Por tanto, hi( x ) no depende de xi y se concluye que h es lineal con respecto a xi . Esto es cierto para todo i∈M∗ , probando así que h es multilineal. Al ser h multilineal, es la extensión de una función real denida en los vértices del cubo. De hecho, es la extensión del juego compuesto u : Teorema 2.7. Sea v un juego no negativo de G(N) , sean w1, w2, ..., wn unos juegos que cumplen las condiciones C1 y C2 y sea u=v[w1, ..., wn] . Sean f, g1, ..., gn las EML de v, w1, ..., wn , respectivamente, y sea h=f◦g . Entonces, h es la extensión multilineal de u . Demostración. Evaluando h en el S -vértice, αS , del cubo [0,1]M∗ , tenemos que, para S⊂ M∗ , h(αS) = fg1(αS1), g2(αS2), ..., gn(αSn), donde Sj=S∩Mj y αSj es la restricción de αS a los índices i∈Mj . Sabemos por (2.2) que gj(αSj) = wj(Sj) , y por tanto h(αS) = f(w1(S1), w2(S2), ..., wn(Sn)), o, por (2.10), h(αS) = u(S). Hemos visto que h coincide con u en los vértices del cubo en los que ambas están denidas, probando así que h es la EML de u . Este teorema muestra que la composición de juegos se corresponde con la composición de sus EML. Ya que las EML están íntimamente relacionadas con el valor de Shapley, cabría esperar que dicho valor también admitiese la composición, es decir, que se cumpliese que Φi(u)=Φi(wj)Φj(v) , para i∈Mj . Sin embargo, en general, esto no es cierto. Recordemos que, para i∈Mj , hi( x ) = fj(g( x ))(gj)i(xj). Tomando x = (x, x, ..., x) , hi(x, x, ..., x) = fj(y(x))(gj)i(x, x, ..., x), donde, para k∈N , yk(x) = gk(x, x, ..., x). (2.11) 24
CAPÍTULO 2. EXTENSIONES MULTILINEALES Así, Φi(u) = Z1 0 fj(y(x))(gj)i(x, x, ..., x)dx, (2.12) donde Φj(v) = Z1 0 fj(x, x, ..., x)dx y Φi(wj) = Z1 0 (gj)i(x, x, ..., x)dx. Podemos observar dos razones por las que el valor de Shapley no admite, en general, la composición: en primer lugar, generalmente, y(x) no es igual a (x, x, ..., x) ; en segundo lugar, aun en caso de que yk(x) = x para todo k∈N , el producto de dos integrales no es, en general, igual a la integral del producto de sus integrandos. En todo caso, la fórmula (2.12) nos permite calcular el valor de Shapley para juegos compuestos. Ejemplo 2.8. El Consejo de Seguridad de las Naciones Unidas consta de 15 miembros, 5 de los cuales son permanentes (EE. UU., Rusia, Reino Unido, Francia y China). Para aprobar una moción es necesaria la aprobación de todos los miembros permanentes, además de al menos 4 votos positivos de entre los 10 miembros no permanentes. Tenemos así un juego compuesto de 15 jugadores u=v[w1, w2] donde w1 es un juego simple de 5 jugadores en el que solo es ganadora la coalición total ( w1(M1) = 1 ), w2 es un juego simple de 10 jugadores en el que es ganadora cualquier coalición de cuatro jugadores o más, y v es un juego simple de dos jugadores en el que solo la coalición de ambos es ganadora. Para w1 , tenemos la extensión multilineal g1(x1, ..., x5) = x1x2x3x4x5, y por tanto y1(t) = t5. Obtengamos directamente para w2 la derivada parcial (g2)i para los puntos x = (x, x, ..., x) empleando la fórmula (2.4). Tenemos, para todo i∈M2={1,2, ..., 10} , (g2)i(x, x, ..., x) = X T∈Ti xt−1(1 −x)10−t, donde Ti es el conjunto de todas las coaliciones T⊂M2 tales que T gana pero T\{i} pierde y t es la cardinalidad de T . Esto es, Ti es el conjunto de coaliciones de exactamente 4 jugadores que contienen al jugador i . Hay 9 3= 84 elementos en Ti , todos ellos con t= 4 , por lo que (g2)i(x, x, ..., x) = 84x3(1 −x)6. 25
2.3. EXTENSIONES MULTILINEALES DE JUEGOS COMPUESTOS Finalmente, v tiene la extensión f(y1, y2) = y1y2. Empleando la fórmula (2.12) tenemos que, para todo i∈M2 , Φi(u) = Z1 0 f2(y(x))(g2)i(x, x, ..., x)dx =Z1 0 y1(x)(g2)i(x, x, ..., x)dx =Z1 0 x584x3(1 −x)6dx = 84 Z1 0 x8(1 −x)6dx = 84 ·B(9,7) = 848!6! 15! =4 2145. Ya que la suma del valor de Shapley de todos los jugadores de u , por eciencia, debe valer 1 y en M2 hay 10 jugadores, queda un total de 1−40/2145 = 2105/2145 para los jugadores de M1 . Es claro que los 5 jugadores de M1 son simétricos, así que cada uno recibe una quinta parte del total, es decir 421/2145 . Así pues, el juego u tiene el siguiente valor de Shapley: Φi(u) = 421/2145 = 0,19627 si i es un miembro permanente , 4/2145 = 0,00186 en otro caso. Es evidente, por tanto, que los miembros permanentes ostentan prácticamente todo el poder del Consejo de Seguridad de las Naciones Unidas. / 26
Capítulo 3 Otros valores relacionados con el valor de Shapley A lo largo del último medio siglo se han denido en teoría de juegos muchos otros valores. En este capítulo se describirán algunos de ellos y se analizará su relación con el valor de Shapley. 3.1. El índice de poder de Banzhaf-Coleman Fue introducido en 1946 por Lionel Penrose [17] y redenido en décadas posteriores por John F. Banzhaf [4] y James S. Coleman [7]. El concepto de índice de poder se aplica a un valor cuando se emplea en el contexto de los juegos simples, los cuales a menudo modelizan problemas de votación. Denición 3.1. Sea v un juego simple en normalización (0,1) . Un conjunto S⊂N se denomina swing para el jugador i∈S si se cumple que v(S) = 1 y v(S\{i}) = 0 . Denición 3.2. Sea θi el número de swings para el jugador i∈N . Se dene el índice de Banzhaf-Coleman normalizado como βi(v) = θi Pn j=1 θj . Es decir, el índice de poder para el jugador i es la fracción de todos los swings existentes que el jugador i puede realizar. Ejemplo 3.3. Sea v el juego de los cuatro accionistas del Ejemplo 1.18. Nótese que el conjunto Ti , denido como el conjunto de todas las coaliciones ganadoras T tales que T\{i} es perdedora, es el conjunto de swings ; es decir, θi=|Ti| . Así pues, obtenemos los 27
3.2. EL VALOR COALICIONAL DE OWEN distintos si uno trabaja para una empresa con grandes benecios y otro trabaja para un pequeño negocio con dicultades. Finalmente, el axioma O4 es análogo a la propiedad de aditividad, con la restricción de que se mantenga la estructura de coaliciones a través de los distintos juegos. Igual que con el valor de Shapley, podemos dar un teorema de existencia y unicidad: Teorema 3.17. Existe una única aplicación que satisface los axiomas O1-O4 de 3.16. Esta aplicación viene dada, para i∈Tj∈ T , por Ωi(v; T ) = X H⊂M j∈HX S⊂Tj i/∈S h!(m−h−1)!s!(tj−s−1)! m!tj![v(Q∪S∪ {i})−v(Q∪S)], (3.2) donde h , s y tj son las cardinalidades de H , S y Tj , respectivamente, y Q=Sk∈HTk . Demostración. La prueba de la unicidad, igual que para el valor de Shapley, está basada en los juegos de unanimidad wS , S⊂N , los cuales, como se vio en el Lema 1.16, forman una base de G(N) como espacio vectorial. Para el juego wS , S es un soporte. Así pues, por el axioma O1, X i∈S Ωi(wS; T ) = wS(S) = 1 y, como todos los jugadores que no forman parte de S son jugadores nulos, Ωi(wS; T )=0 para todo i /∈S . Sean j y k dos elementos de S/ T . Por el Lema 3.15, wS/ T =wS/ T , y por ser j y k simétricos en wS/ T , Tj y Tk son coaliciones simétricas en wS . Del axioma O3 se sigue que X i∈Tj Ωi(wS; T ) = X i∈Tk Ωi(wS; T ). Sea h(S) la cardinalidad de S/ T , i. e. el número de j∈M tales que S∩Tj6=∅ . Ya que todos los Tj con j∈S/ T reciben el mismo pago y todos juntos reciben un pago 1, tenemos que X i∈Tj Ωi(wS; T )=1/h(S), para j∈S/ T . Sean i y l dos elementos de S∩Tj , para algún j . En particular, i, l ∈S y por tanto son jugadores simétricos en wS . Por tanto, por el axioma O2, Ωi(wS; T )=Ωl(wS; T ) . Sea ahora sj el número de elementos de S∩Tj . Como todos los jugadores de S∩Tj reciben el mismo pago por ser simétricos, y todos juntos reciben 1/h(S) , obtenemos que Ωi(wS; T ) = 1/(sjh(S)) si i∈S∩Tj, Tj∈ T , 0 si i /∈S. 34
CAPÍTULO 3. OTROS VALORES RELACIONADOS CON EL VALOR DE SHAPLEY Así pues, hemos visto que los axiomas O1-O3 caracterizan un único valor para los juegos de unanimidad wS . Como estos juegos forman una base de G(N) , por el axioma O4 se deduce que hay a lo sumo un único valor en el espacio de todos los pares (v, T ) . Para probar la existencia, basta con comprobar que el valor dado por la ecuación (3.2) satisface los axiomas O1-O4. Ejemplo 3.18. Sea v el juego de los cuatro accionistas y u=v/ T el juego cociente con uniones a priori descritos en el Ejemplo 3.9. Para calcular su valor de Owen emplearemos el paquete GameTheoryAllocation de descrito en Saavedra-Nieves [18]. Recordemos que la función característica de v se dene de la forma siguiente: v(1) = 0 v(12) = 0 v(123) = 1 v(1234) = 1 v(2) = 0 v(13) = 0 v(124) = 1 v(3) = 0 v(14) = 0 v(134) = 1 v(4) = 0 v(23) = 0 v(234) = 1 v(24) = 1 v(34) = 1 Teniendo esto en cuenta, ejecutamos la siguiente secuencia de comandos: > install.packages("GameTheoryAllocation") > library(GameTheoryAllocation) > f_caract=c(rep(0,8),rep(1,7)) > union=list(c(1,2),c(3),c(4)) > Owen_value(f_caract,union,game="profit") El valor de Owen obtenido es Ω(v; T ) = 1 12,1 4,1 3,1 3 . Resulta interesante compararlo con el valor de Shapley del juego sin uniones a priori obtenido en el Ejemplo 1.18, que es Φ(v) = 1 12,1 4,1 4,5 12 . La unión de los jugadores 1 y 2 hace que el jugador 4 pierda algo de valor en favor del jugador 3 . Esto se debe a que en el juego cociente u los tres jugadores son simétricos, pues la colaboración entre dos de ellos otorga la mayoría. En esta situación, el mayor número de acciones del jugador 4 no le otorga ningún poder negociador adicional. / 3.3. El valor de Myerson y otros valores relacionados El valor de Myerson fue introducido por Roger B. Myerson [12] en 1977 como una aplicación directa del valor de Shapley para los juegos TU con estructura de comunicación . Para entender esta clase de juegos es necesario denir previamente algunos conceptos: 35
3.3. EL VALOR DE MYERSON Y OTROS VALORES RELACIONADOS Denición 3.19. Un grafo no dirigido es un par (N, Γ) en el que N es un conjunto de nodos y Γ es un conjunto de pares no ordenados de elementos distintos de N , es decir, Γ⊂ {{i, j} ⊂ N|i6=j} . Los elementos de Γ se llaman aristas . Denotaremos por Γ(N) el conjunto de todos los grafos no dirigidos denidos sobre N , y en general nos referiremos a los elementos de esta clase por su conjunto de aristas Γ . Denición 3.20. Dado un grafo Γ∈Γ(N) y un conjunto S∈2N\{∅} , el subgrafo de Γ en S es el grafo (S, Γ|S) con Γ|S={{i, j} ∈ Γ|i, j ∈S} . Denición 3.21. Sea Γ∈Γ(N) . Una secuencia de k nodos distintos (i1, ..., ik) es un camino en Γ|S si {il, il+1} ∈ ΓS para l= 1, ..., k −1 . Dos nodos i, j ∈N están conectados en Γ|S si existe un camino (i1, ..., ik) en Γ|S con i1=i y ik=j . Un subgrafo Γ|S es conexo si todo par de nodos en S está conectado por un camino. Denición 3.22. Un conjunto K⊂S es un componente de Γ|S si K es un subconjunto conexo maximal de S , es decir, K es conexo y para cada i∈S\K el conjunto K∪ {i} no es conexo en Γ . El conjunto de componentes de Γ|S constituye una partición de S y se denota por S/Γ . En el contexto de los juegos TU, el conjunto de nodos N es el conjunto de jugadores y el grafo representa en este caso una estructura de comunicación establecida entre los jugadores. Se considerará que los jugadores de la coalición S se pueden comunicar entre ellos si S es conexo en Γ (i.e., Γ|S es conexo). Un juego TU con estructura de comunicación o juego CO con conjunto de jugadores N viene dado por la tripla (N, v, Γ) , donde (N, v)∈ G(N) y Γ∈Γ(N) . Denotaremos el conjunto de juegos CO con conjunto de jugadores N por GCO(N) . Para un juego CO (N, v, Γ) , asumimos que los jugadores de la coalición S⊂N solo pueden cooperar si pueden comunicarse entre ellos, es decir, si Γ|S es conexo. Denición 3.23. Dado (N, v, Γ) ∈GCO(N) , el juego restringido (de Myerson) , vΓ∈ G(N) , está denido por vΓ(S) = X T∈S/Γ v(T), para todo S⊂N . Denición 3.24. El valor de Myerson para un juego CO, denotado por µ , es el valor de Shapley de su juego restringido, µ(N, v, Γ) = Φ(vΓ). 36
CAPÍTULO 3. OTROS VALORES RELACIONADOS CON EL VALOR DE SHAPLEY Así pues, el valor de Myerson de un juego CO es el valor de Shapley de un juego TU obtenido a partir del juego original teniendo en cuenta las restricciones comunicativas inducidas por el grafo. Ejemplo 3.25. Consideremos el juego de guantes de cuatro jugadores v∈G(N) con N={1,2,3,4} en el que el jugador 1 tiene un guante izquierdo mientras los jugadores 2 , 3 y 4 tienen un guante derecho cada uno. La función característica de este juego está denida de la siguiente manera: v(1) = 0 v(12) = 1 v(123) = 1 v(1234) = 1 v(2) = 0 v(13) = 1 v(124) = 1 v(3) = 0 v(14) = 1 v(134) = 1 v(4) = 0 v(23) = 0 v(234) = 0 v(24) = 0 v(34) = 0 El valor de Shapley de este juego es Φ(v) = 3 4,1 12,1 12,1 12 . Sin embargo, consideremos que existen unas restricciones comunicativas inducidas por el grafo Γ = {{1,2},{2,4}} , por ejemplo porque solo estos jugadores se conocen entre sí. Nótese que, a pesar de que los jugadores 1 y 4 no se conocen, pueden comunicarse a través del jugador 2 , que es un conocido común. El juego restringido de Myerson asociado a este grafo, vΓ , es el siguiente: vΓ(1) = 0 vΓ(12) = 1 vΓ(123) = 1 vΓ(1234) = 1 vΓ(2) = 0 vΓ(13) = 0 vΓ(124) = 1 vΓ(3) = 0 vΓ(14) = 0 vΓ(134) = 0 vΓ(4) = 0 vΓ(23) = 0 vΓ(234) = 0 vΓ(24) = 0 vΓ(34) = 0 El valor de Myerson del juego original, (N, v, Γ) , es el valor de Shapley de vΓ . En el juego restringido, los jugadores 3 y 4 son nulos, mientras que los jugadores 1 y 2 son simétricos. Por tanto, Φ(vΓ) = 1 2,1 2,0,0=µ(N, v, Γ) . En esta situación, el jugador 3 se vuelve nulo al no conocer a nadie que pueda proporcionarle un guante izquierdo. El hecho de que el jugador 4 pueda comunicarse con el jugador 2 no le supone ningún benecio directo, ya que ambos poseen guantes derechos y por tanto su coalición no genera ninguna utilidad. Además, aunque puede comunicarse con el jugador 1 , ha de hacerlo a través del jugador 2 , que también tiene interés en el guante izquierdo del jugador 1 . Por tanto, la inclusión del jugador 4 no genera tampoco ninguna utilidad a la coalición {1,2} formada previamente. De este modo, solo los jugadores 1 y 2 pueden generar utilidad, teniendo ambos el mismo poder. / 37
3.3. EL VALOR DE MYERSON Y OTROS VALORES RELACIONADOS El concepto de grafo admite una generalización. Dado un conjunto base N , un hipergrafo es un par (N, H) donde H⊂ {h⊂N| |h|>1} . Los elementos de H se llaman hiperaristas y pueden relacionar cualquier cantidad de elementos de N , a diferencia de los grafos, donde |h|= 2 . El conjunto de hiperaristas de i∈N se denota por Hi={h∈H|i∈h} . La restricción de H a S∈2N\{∅} se denota por H|S={h∈H|h⊂S} . Un hipergrafo, de manera análoga a lo que ocurre con un grafo, da lugar a una partición del conjunto base (o de cualquier subconjunto de este) en componentes conexas maximales; para un hipergrafo (N, H) , se denota por N/H el conjunto de sus componentes. De manera análoga a como se denieron los juegos CO, un juego TU con estructura de conferencia o juego CF con conjunto de jugadores N viene dado por la tripla (N, v, H) , donde (N, H) es un hipergrafo y v∈G(N) . Se denotará por GCF(N) el conjunto de juegos CF con conjunto de jugadores N . El valor de Myerson puede ser extendido a juegos CF de la siguiente manera (van den Nouweland, Borm y Tijs [21]): µ(N, v, H) = Φ(vH), donde vH(S) = X T∈S/H v(T), para todo S⊂N , siendo S/H la partición de S en componentes conexas maximales inducida por H . Como alternativa al valor de Myerson, Meessen [11] denió el valor de posición para juegos CO, extendido a situaciones de juegos CF con hipergrafos no cíclicos en van den Nouweland, Borm y Tijs [21]. Casajus [6] ofrece una caracterización del valor, expresándolo en términos del valor de Myerson: mientras que este enfatiza el rol de los jugadores, el valor de posición se centra en las aristas (o hiperaristas) que los unen. Este enfoque es el que se describe a continuación: Denición 3.26. Dado un juego (N, v, H)∈GCF(N) , se dene el juego de hiperaristas (H, vN) por vN(F) = X S∈N/F v(S), para todo F⊂H , siendo N/F la partición de N en componentes conexas maximales inducida por F . Denición 3.27. El valor de posición del juego (N, v, H)∈GCF(N) viene dado por πi(N, v, H) = X h∈Hi 1 |h|Φh(H, vN). 38
CAPÍTULO 3. OTROS VALORES RELACIONADOS CON EL VALOR DE SHAPLEY De este modo, el juego de hiperaristas evalúa la importancia de cada subconjunto de hiperaristas en el juego original y el valor de posición reparte a partes iguales el valor de Shapley de cada hiperarista entre los jugadores involucrados en ella. Consideremos ahora la situación opuesta a la descrita por los juegos CO: dado un grafo Γ∈Γ(N) , diremos que dos jugadores i, j ∈N son incompatibles si {i, j} ∈ Γ , es decir, si están unidos por una arista. Un juego TU con incompatibilidades es una tripla (N, v, Γ) , donde (N, v)∈G(N) y Γ∈Γ(N) , considerando esta interpretación alternativa del grafo: en estos juegos, las aristas el grafo representarán la imposibilidad de dos jugadores para comunicarse entre sí y, por tanto, formar coaliciones. Denotaremos por GI(N) el conjunto de juegos TU con incompatibilidades con conjunto de jugadores N . El objetivo es obtener una variación del valor de Shapley útil para estas situaciones. Denición 3.28. Dado un grafo Γ∈Γ(N) , decimos que una coalición S⊂N es Γ - admisible si y solo si {i, j}/∈Γ para todo i, j ∈S . Se denotará por P(S, Γ) el conjunto de todas las particiones de S cuyas clases son Γ -admisibles. Denición 3.29. Dado un grafo Γ∈Γ(N) , se dene su grafo dual como Γ∗={{i, j} ⊂ N|i6=j, {i, j}/∈Γ}. Bergantiños, Carreras y García-Jurado [5] introducen un valor eciente y justo denido en GI(N) . Nuevamente, se denen varias propiedades deseables (en este caso, adaptando las ideas que habían sido introducidas en Myerson [12] al contexto de los juegos con incompatibilidades) y se demuestra que determinan un único valor f:GI(N)−→ Rn . Denición 3.30. Sea f un valor en GI(N) y consideremos las siguientes propiedades deseables: 1. Eciencia en componentes: f satisface la propiedad de eciencia en componentes si, para todo (N, v, Γ) ∈GI(N) , se tiene que X i∈S fi(N, v, Γ) = m´ax P∈P(S,Γ) X T∈P v(T), para todo S∈N/Γ∗ . Nótese que N/Γ∗ particiona N de forma que, si i y j forman parte de distintas clases de la partición, entonces son incompatibles. Estas clases S∈N/Γ∗ están formadas por jugadores compatibles que pueden negociar y formar coaliciones admisibles; la propiedad de eciencia en componentes asegura que los jugadores formarán estas coaliciones de la mejor forma para ellos, es decir, la suma de los pagos obtenidos por los jugadores en cada S∈N/Γ∗ es la mayor posible. 39
3.3. EL VALOR DE MYERSON Y OTROS VALORES RELACIONADOS 2. Justicia: f satisface la propiedad de justicia si, para todo (N, v, Γ) ∈GI(N) , se tiene que fi(N, v, Γ) −fi(N, v, Γ∪ {i, j}) = fj(N, v, Γ) −fj(N, v, Γ∪ {i, j}), para todo {i, j} ∈ Γ∗ . Esta propiedad reeja la simetría de la relación binaria que subyace al grafo: si dos jugadores se vuelven compatibles, ambos ganan o pierden lo mismo. 3. Estabilidad: f satisface la propiedad de estabilidad si, para todo (N, v, Γ) ∈GI(N) , se tiene que fi(N, v, Γ) ≥fi(N, v, Γ∪ {i, j}), fj(N, v, Γ) ≥fj(N, v, Γ∪ {i, j}), para todo {i, j} ∈ Γ∗ . Esta propiedad signica que, para cualquier jugador, ser incompatible con otros solo puede perjudicarle. A continuación, se dene la restricción de un juego con incompatibilidades a un juego TU general. Bajo esta denición subyace la misma idea que en la propiedad de eciencia en componentes antes descrita. Los jugadores de una coalición S forman subcoaliciones Γ -admisibles (que son las únicas posibles) que maximizan la suma de los pagos para los jugadores de S . Denición 3.31. Dado un juego (N, v, Γ) ∈GI(N) , el juego restringido vΓ se dene de la siguiente manera: vΓ(S) = m´ax P∈P(S,Γ) X U∈P v(U), para todo S⊂N . Bergantiños, Carreras y García-Jurado [5] usan esta denición de juego restringido y las propiedades mencionadas arriba para proponer y caracterizar su valor para juegos con incompatibilidades Teorema 3.32. Existe un único valor f denido en GI(N) que satisfaga las propiedades de eciencia en componentes y justicia para todo (N, v, Γ) ∈GI(N) . Este valor viene dado por f(N, v, Γ) = Φ(vΓ). Además, este valor satisface la propiedad de estabilidad y, para todo juego TU v∈G(N) , f(N, v, ∅) = Φ(v) , donde el grafo ∅ representa una situación sin incompatibilidades. 40
Capítulo 4 Aplicaciones El valor de Shapley y sus variaciones se han aplicado en diversidad de problemas: asignación de tasas de aterrizaje a aerolíneas en aeropuertos (Vázquez-Brage, van den Nouweland y García-Jurado [22]), reparto de benecios de pases a museos (Ginsburgh y Zang [9]) o problemas de bancarrota aplicables al reparto de cuotas lácteas (Saavedra- Nieves y Saavedra-Nieves [19]), por ejemplo. En los años más recientes también se han propuesto aplicaciones directas del valor de Shapley o variaciones de este en el contexto del machine learning (Aas, Jullum y Løland [1]; Ghorbani y Zou [8]). En este capítulo se explicarán con más detalle algunas de estas aplicaciones. 4.1. El juego del aeropuerto Este juego fue introducido por Littlechild y Owen [10] como aplicación de la teoría de juegos al problema de asignar los costes de un aeropuerto entre los aviones que lo utilizan y que necesitan pistas de aterrizaje de distintas longitudes. Generalmente, los gastos de un aeropuerto se dividen en dos partes: un gasto variable que es proporcional al número de aviones que lo utilizan y un coste de capital jo, que debe amortizarse durante un cierto período de tiempo. Asignar los gastos variables no suele suponer un problema, ya que son pagados directamente por los aviones al usar el aeropuerto; el problema reside en la asignación de los costes de capital (por ejemplo, la construcción de una pista de aterrizaje o de una terminal) a los distintos tipos de aviones. Los costes de capital del aeropuerto dependen, esencialmente, del avión más grande que vaya a utilizarlo. La longitud (y por tanto el coste) de la pista de aterrizaje será proporcional al tamaño del avión más grande que la vaya a utilizar; una vez la pista es construida, no son necesarios más gastos de capital hasta que solicite su uso un avión más grande. El objetivo será diseñar un programa de tarifas justo que sufrague estos costes. 41
4.1. EL JUEGO DEL AEROPUERTO Podemos dividir los aviones en m tipos distintos. El coste de una pista de aterrizaje acondicionada para los aviones del tipo j , con j∈ {1, ..., m} , es Cj . Sin pérdida de generalidad, podemos asumir que 0 = C0< C1< C2< ... < Cm−1< Cm. Sea Nj el conjunto de movimientos (aterrizajes y despegues) realizados por los aviones del tipo j , y sea nj el número de movimientos realizados por aviones de este tipo. Entonces, N= m [ j=1 Nj es el conjunto de todos los movimientos, y para S⊂N podemos escribir j(S) = m´ax{j∈ {1, ..., m} | S∩Nj6=∅}. j(S) denota el tipo de avión más grande de entre aquellos cuyos movimientos forman parte del conjunto S . De este modo, es claro que el coste de una pista acondicionada para recibir todos los movimientos del conjunto S es c(S) = Cj(S), mientras que c(∅) = 0. Así pues, podemos tratar esta estructura de costes como un juego TU con conjunto de jugadores N y función característica v(S) = −c(S) , para todo S⊂N . Una imputación de v será un vector x que satisfaga 1. xi≥ −c({i}) = −Cj, si i∈Nj , 2. Pi∈Nxi=−c(N) = −Cm . El vector − x = (−x1, ..., −xm) es un posible plan de tarifas, ya que recauda justo lo suciente para recuperar los costes de capital del aeropuerto. En la Proposición 1.19 vimos que, en juegos superaditivos como es este, el valor de Shapley es una imputación, así que es un buen candidato para determinar un plan de tarifas justo. Para computar el valor de Shapley, denotemos Rk= m [ j=k Nj, rk= m X j=k nj, 42
CAPÍTULO 4. APLICACIONES y consideremos las m funciones características v1, v2, ..., vm denidas para todo S⊂N por vk(S) = 0 si S∩Rk=∅, Ck−1−Ck si S∩Rk6=∅. Nótese que, si k≤j(S) , entonces S∩Rk6=∅ ; mientras que, si k > j(S) , entonces S∩Rk=∅ . Por tanto, m X k=1 vk(S) = j(S) X k=1 (Ck−1−Ck) =C0−Cj(S)=−c(S), con lo cual v= m X k=1 vk y, por la propiedad de aditividad, Φ(v) = m X k=1 Φ(vk). Es fácil ver que Rk es un soporte de vk , por lo que todos los i /∈Rk son jugadores nulos. Además, todos los elementos de Rk son jugadores simétricos entre sí en vk . Por tanto, Φi(vk) = 0 si i /∈Rk, (Ck−1−Ck)/rk si i∈Rk. Ahora bien, si i∈Nj , entonces i∈Rk para todo k≤j ; así pues, tenemos que Φi(v) = j X k=1 Ck−1−Ck rk , i ∈Nj y el programa de tarifas dado por el valor de Shapley es simplemente el opuesto de esto, es decir Φi(c) = j X k=1 Ck−Ck−1 rk , i ∈Nj. Esta solución tiene la interpretación siguiente: el coste de construir la primera parte de la pista de aterrizaje, es decir C1 , es incurrido por todos los tipos de aviones y dividido a partes iguales entre todos los movimientos en el aeropuerto. Luego, el coste de la segunda parte de la pista, es decir C2−C1 , es incurrido por todos los tipos de aviones excepto por los del primer tipo y dividido a partes iguales entre todos los movimientos realizados 43
Bibliografía [1] Aas, K., Jullum, M. y Løland, A. (2019). Explaining individual predictions when features are dependent: More accurate approximations to Shapley values . arXiv:1903.10464. [2] Algaba, E., Fragnelli, V. y Sánchez-Soriano, J. (2019). Handbook of the Shapley Value . CRC Press, Taylor & Francis Group, Boca Raton. [3] Aumann, R. y Maschler, M. (1985). Game theoretic analysis of bankruptcy problem from the Talmud. Journal of Economic Theory , 36 (2), 195213. [4] Banzhaf, J. F. (1965). Weighted voting doesn't work: A mathematical analysis. Rutgers Law Review , 19 (2), 317343. [5] Bergantiños, G., Carreras, F. y García-Jurado, I. (1993). Cooperation when some players are incompatible, ZOR Methods and Models of Operations Research , 38 (2), 187201. [6] Casajus, A. (2007). The position value is the Myerson value, in a sense. International Journal of Game Theory , 36 (1), 4755. [7] Coleman, J. S. (1971). Control of collectivities and the power of a collectivity to act. En B. Lieberman (Ed.), Social Choice , Gordon and Breach, 269300. [8] Ghorbani, A. y Zou, J. (2019). Data Shapley: Equitable Valuation of Data for Machine Learning . arXiv:1904.02868. [9] Ginsburgh, V. y Zang, I. (2003). The museum pass game and its value. Games and Economic Behavior , 43 (2), 322325. [10] Littlechild S. C. y Owen, G. (1973). A simple expression for the Shapley value in a special case. Management Science , 20 (3), 370372. [11] Meessen, R. (1988). Communication games . Tesis de Máster, Department of Mathematics, University of Nijmegen, Nijmegen. 51
BIBLIOGRAFÍA [12] Myerson, R. B. (1977). Graphs and cooperation in games. Mathematics of Operations Research , 2 (3), 225229. [13] O'Neil, B. (1982). A problem of rights arbitration from the Talmud. Mathematical Social Sciences , 2 (4), 345371. [14] Owen, G. (1972). Multilinear extensions of games. Management Science , 18 (52), 64 79. [15] Owen, G. (1977). Values of games with a priori unions. En R. Henn, O. Moeschlin (Eds.), Mathematical Economics and Game Theory , Springer Verlag, 7688. [16] Owen, G. (1995). Game Theory . 3 ª ed., Academic Press, New York. [17] Penrose, L. (1946). The elementary statistics of majority voting. Journal of the Royal Statistical Society , 109 (1), 5357. [18] Saavedra-Nieves, A. (2016). Package `GameTheoryAllocation' . R package, versión 2.15.0, http://cran.r-project.org/web/packages/GameTheoryAllocation/ GameTheoryAllocation.pdf . [19] Saavedra-Nieves, A. y Saavedra-Nieves, P. (2020). On systems of quotas from bankruptcy perspective: the sampling estimation of the random arrival rule. European Journal of Operational Research , 285 (2), 655669. [20] Shapley, L. S. (1953). A value for n -person games. En H. Kuhn, A. Tucker (Eds.), Contributions to the Theory of Games , vol. 2, Princeton University Press, 307317. [21] van den Nouweland, A., Borm, P. y Tijs, S. (1992). Allocation rules for hypergraph communication situations. International Journal of Game Theory , 20 (3), 255268. [22] Vázquez-Brage, M., van den Nouweland, A. y García-Jurado, I. (1997). Owen's coalitional value and aircraft landing fees. Mathematical Social Sciences , 34 (3), 273286. 52