APLICACIÓN DE LOS JUEGOS COOPERATIVOS AL REPARTO DE COSTES. Flor Mª Guerrero Casas Miguel Ángel Hinojosa Ramos Eulalia Romero Palacios Departamento de Economía y Empresa. Universidad Pablo de Olavide. Ctra. de Utrera, Km.1. 41013-SEVILLA. Telf.: 954 349 356 Fax: 954 349 339 e-mail: [email protected] RESUMEN La aplicación de la teoría de juegos a las ciencias sociales ha supuesto un importante avance a todos los niveles. La teoría de juegos estudia situaciones en las que interactúan dos o más jugadores racionales que se plantean un conflicto de intereses. Un juego cooperativo es aquel en que los jugadores pueden tomar acuerdos vinculantes, que estos juegos sean además de utilidad transferible implica que las ventajas que obtengan las coaliciones derivadas de dicha cooperación (mayores beneficios, ahorro de costes, incremento de la producción, etc.) podrán redistribuirse entre sus miembros de cualquier manera. Este trabajo estudia la aplicación de la teoría de juegos cooperativos con utilidad transferible a problemas de reparto de costes asociados a la creación de canales de distribución de un bien suministrado por un único proveedor o fuente. Se propone como concepto de solución el concepto de núcleo y como regla para obtener asignaciones del núcleo la regla de reparto de Bird. Ponemos de manifiesto cómo en el caso vectorial el concepto de núcleo ha de ser revisado y demostramos que la regla de Bird proporciona asignaciones del núcleo de dominancia. Palabras clave: juegos cooperativos, juegos vectoriales, núcleo, árbol de unión de mínimo coste. 1. INTRODUCCIÓN La Teoría de Juegos Cooperativos nos brinda un marco teórico adecuado para el estudio de situaciones de reparto de costes. Dentro de este marco nos centraremos en el estudio de Juegos Cooperativos con Utilidad Transferible (juegos cooperativos TU). El término de utilidad transferible hace referencia a que las ventajas de la cooperación, en nuestro caso el ahorro de costes, pueden distribuirse de cualquier modo entre los miembros de la coalición. El objeto de este trabajo es plantear una aplicación de los juegos cooperativos TU al reparto de costes. En concreto aplicaremos las teoría de juegos definidos a través de árboles de unión de mínimo coste al problema de repartir los costes asociados a la creación de una red de distribución de un servicio entre un conjunto de consumidores y un único proveedor (fuente) de ese servicio. Este problema fue introducido por Claus y Kleitman en 1973. Bird, en 1976, planteó una aproximación teórica a través de la teoría de juegos proponiendo un regla de asignación de costes consistente en asignar a cada consumidor (vértice) el coste de creación del vínculo, arista, incidente en dicho vértice, del único camino que lo conecta con la fuente, en un árbol de unión de mínimo coste definido sobre el grafo que

representa todos los posibles interconexiones entre los consumidores y la fuente. Obsérvese que puede haber más de un árbol de unión de mínimo coste en un grafo, lo que puede dar lugar a diferentes asignaciones de Bird para un mismo juego. En 1981, Granot y Huberman demostraron que las asignaciones que se generan siguiendo la regla de reparto sugerida por Bird pertenecen siempre al núcleo de este juego (véase Curiel, 1997). Las situaciones en que el coste asociado a una arista es un vector, en lugar de un escalar, dan lugar a juegos multicriterio definidos mediante árboles de unión de mínimo coste en el sentido de Pareto (véase Ehrgott, 2002, donde se analizan procedimientos de creación de árboles de unión de coste Pareto-mínimo). Estos juegos tienen un tratamiento distinto al que se da a los juegos escalares, pues la función característica del juego asocia a cada coalición un conjunto de vectores, su conjunto característico. Este trabajo esta organizado como sigue. En la sección 2 introducimos unas mínimas nociones sobre grafos y definimos un juego a través de un árbol de unión de mínimo coste. En el caso escalar utilizamos la teoría de juegos convencionales y planteamos el concepto de núcleo como posible solución. Sin embargo, en el caso vectorial no basta con considerar exclusivamente juegos componentes y se hace necesaria una teoría de juegos vectoriales, en la cual el concepto de núcleo ha de ser modificado convenientemente. En la sección 3 estudiamos el núcleo como concepto de solución para ambos tipo de juegos. Se sabe que la regla de Bird proporciona asignaciones de coste que están en el núcleo de un juego escalar, nosotros probaremos además que la extensión de la regla de Bird a juegos multicriterio proporciona asignaciones vectoriales que están en el núcleo que denominaremos de dominancia. Finalizamos con una sección dedicada a las conclusiones. Los desarrollos teóricos se ilustran con ejemplos. 2. JUEGOS DEFINIDOS MEDIANTE ÁRBOLES DE UNIÓN DE MÍNIMO COSTE. Consideremos un juego de N consumidores de un bien que son abastecidos por un mismo proveedor 0, los cuales deben repartirse el coste asociado al sistema de distribución. Esta situación puede formularse como un juego de TU con N jugadores y una función característica, c, que asocia a cada coalición S ⊆ N el coste mínimo de construir el sistema de distribución entre los consumidores de S, c(S). Sea G = ( N 0 , E ) un grafo completo, cuyo conjunto de vértices es N 0 = N U {0} y cuyo conjunto de aristas es E = {ij}i , j∈N . Denotamos por eij=eji el coste de construir la conexión (arista) {ij} ∈ E . Un árbol es un grafo conexo que no contiene ciclos. Un árbol de unión definido sobre un grafo es un árbol, cuyo conjunto de vértices coincide con el del grafo dado y cuyo conjunto aristas está contenido en el conjunto de aristas del grafo dado. Un árbol de unión de mínimo coste de un grafo es el árbol de unión de menor coste entre todos los árboles de unión del grafo dado. 2.1. Caso Escalar. En general, un juego cooperativo de utilidad transferible es un par (N, c), donde N = {1,2, ,..., n} es el conjunto de los jugadores y c asocia a cada posible coalición S ⊆ N un número real, c(S), que en nuestro caso representa el coste asociado la coalición S, de forma que c(∅) = 0.

Definición: Un juego definido mediante árboles de unión de mínimo coste, asociado a un grafo completo , es un par (N, c), donde N es el conjunto de jugadores y c es la función característica definida por: 1. c(∅) = 0 2. Para cada coalición no vacía S ⊆ N , c( S ) = ∑ e ij i , j∈ETS

donde ETS es el conjunto de aristas de un árbol de unión de mínimo coste, TS, en el grafo G S = ( S 0 , E S ) con S 0 = S U {0} . En este tipo de juegos se supone que el conjunto de todos los jugadores llega a un cierto consenso y el problema que se plantea es cómo repartir entre los jugadores la utilidad total alcanzada por la gran coalición, c(N). Un reparto es un vector, de dimensión el número de jugadores, cuyas componentes son los costes imputados a cada uno de ellos. Es, por tanto, un vector n

x = ( x1 , x 2 ,..., x n ) tal que x N = ∑ x i = c( N ) . A la coalición S le corresponde x S = ∑ x i . i =1

El conjunto de todos los repartos del juego lo denotamos por I*(N, c).

i∈S

Ejemplo1: Supongamos que se plantea la necesidad abastecer de electricidad a tres poblaciones. Para ello se construirá una red de tendidos eléctricos que conecte dichas poblaciones con la central eléctrica. En el siguiente grafo se presentan los costes de todos los posibles tendidos que interconectan las poblaciones (1, 2 y 3) y la central eléctrica (0). 1

3 1

2 0 2

2

3 3

3

Un análisis de la situación lleva a la conclusión de que la manera más barata de hacer llegar la electricidad a todas las poblaciones es construir un tendido eléctrico que conecte directamente las población 2 con la fuente y construir otro que conecte la población 3 con la población 1 y la población 1 con la población 2. En este caso el coste total del tendido eléctrico sería de 5 u.m., ahora deberá decidirse la manera más justa de repartir ese coste entre las tres poblaciones. Para ello se plantea un juego definido sobre árboles de unión de mínimo coste asociado a este grafo en el que se asume que cada coalición S pretende construir una tendido que conecte sólo las poblaciones que forman parte de S con la central, bien directamente, bien a través de cualquier otra población, buscando la conexión más barata posible. En la tabla que aparece a continuación se presenta la descripción del juego; para cada coalición S ⊆ N , c(S) representa el coste de construcción del tendido eléctrico necesario para suministrar electricidad a las poblaciones de S.

S

{1}

{2}

{3}

{1,2}

{1,3}

{2,3}

N

c(S)

3

2

3

3

5

5

5

2.2. Caso Vectorial. Supongamos que los costes asociados al sistema de distribución son de varios tipos y asociado a cada arco del grafo no hay un coste escalar sino un vector de costes, es decir eij = (e1ij , e2ij ,..., ekij ) . En nuestro ejemplo, podríamos medir el coste económico de la construcción del tendido y el impacto medioambiental que implica la construcción de dicho tendido. En este caso, la función característica que define el juego es una función que asocia a cada coalición un conjunto de vectores no comparables que representan el coste que la coalición puede garantizarse por sí misma. En general, un juego vectorial TU es un par (N, v), donde N ={1,2,...,n} es el conjunto de jugadores y v es una función que asigna a cada coalición S ⊆ N un subconjunto compacto v( S ) ⊂ IR k , que denominamos conjunto característico de la coalición S, de forma que v(∅)=θ. Los vectores de v(S) representan el mínimo coste que los miembros de la coalición S pueden asegurarse por ellos mismos sin cooperar con el resto de jugadores. Nótese que la función característica de estos juegos es una función que a cada coalición asocia un conjunto de vectores de costes, en lugar de un único coste como en el caso escalar. Definición Un juego definido mediante árboles de unión de coste Pareto-mínimo, asociado a un grafo completo , es un par (N, v), donde N es el conjunto de jugadores y v es la función característica definida por: 1. v(∅) =θ . 2. Para cada coalición no vacía S ⊆ N , v( S ) = ∑ e ij i , j∈ETS

donde ETS es el conjunto de aristas de un árbol de unión de coste Paretomínimo, TS, en el grafo G S = ( S 0 , E S ) con S 0 = S U {0} . Entendemos por un árbol de unión de coste Pareto-mínimo para un grafo conexo dado, con coste asignado a sus aristas, un árbol de unión cuyo coste es mínimo en el sentido de Pareto entre todos los árboles de unión de dicho grafo. La cuestión que surge en este tipo de juegos es cómo repartir el coste total de unir todos los puntos entre los jugadores de una manera justa. Para un juego vectorial TU una asignación consiste en una matriz X ∈ IR k ×n , cuyas filas representan el reparto entre los jugadores en uno de los criterios y cuyas columnas son las asignaciones de coste a cada jugador. Así la columna i-ésima de la matriz X i = ( x1i , x 2i ,..., x ki ) t representa lo que paga el jugador i por cada uno de los criterios considerados y la fila jésima de la matriz X j = ( x1j , x 2j ,..., x nj ) representa lo que cada jugador paga por un mismo criterio. La suma X S = ∑i∈S X i es el pago total de la coalición S por los diferentes criterios considerados.

La matriz X es una asignación del juego (N, v) si X N = ∑i∈N X i . Denotamos el

conjunto de asignaciones de un juego por I*(N ,v).

Ejemplo2: Consideremos de nuevo el ejemplo anterior, en el que se pretende suministrar electricidad a las poblaciones 1,2, y 3. Ahora bien, en este caso no sólo nos planteamos reducir el coste de construcción de la red, como en el caso anterior, sino que se tratará además minimizar el impacto medioambiental que produciría la construcción de los posibles tendidos. Representaremos esta nueva situación con un grafo completo de manera que cada arista lleva asociado un vector de coste cuya primera componente representa, como en el caso escalar, el coste de construcción de la red, y cuya segunda componente medirá el impacto medioambiental. 1

1     3

1 1  

 2    2

0 1   2   

 0   3

2

 3  3   

3

El juego bi-criterio definido mediante árboles de unión de coste Pareto- mínimo asociado a este grafo es ahora: S

{1}

{2}

{3}

{1,2}

{1,3}

{2,3}

N

V(S)

1     3 

1     2 

1     5 

 2     3 

 3   2   ,    5   6 

1     5 

 2   4   ,    6   5 

Hay dos árboles de unión de coste Pareto- mínimo asociado a este grafo completo G para la coalición total N. El primero corresponde al pago (2,6)t ∈ v( N ) , y la segundo corresponde al pago (4,5)t ∈ v( N ) . 1

1

0

0

2

1     2

 2  2   

1   1

1   1

 0   3

3

2

1     2

3

3. CONCEPTOS DE NÚCLEO. Aparte de la eficiencia y usando los principios de racionalidad individuales y colectivos, en lo que sigue vamos a establecer los conceptos de núcleo para juegos definidos mediante árboles de unión de mínimo coste en el caso escalar y en el caso vectorial. 3.1. Caso Escalar. El núcleo de un juego convencional está compuesto por aquellas asignaciones de coste tales que ninguna coalición puede proponer una alternativa en la que todos sus miembros mejoren su situación. Por tanto son dos las condiciones que permiten determinar si un reparto x = ( x1 , x 2 ,..., x n ) pertenece o no al núcleo: n

x N = ∑ x i = c( N ) . (Eficiencia)

1.

i =1

x S = ∑ x i ≥ c(S ) ∀S ⊆ N .

2.

i∈ S

(Principios de racionalidad individual y colectiva)

Como es bien conocido, una condición necesaria y suficiente para que el núcleo de un escalar sea no vacío es la condición de balanceo, un juego se dice balanceado o equilibrado si ∑α S c( S ) ≥ c( N ) , donde (α S ) S ⊆ N son números reales y positivos tales que

∑α

S i∈S ⊆ N

S⊂N

S

= 1 ∀i = 1,2,..., n.

Ejemplo1 (continuación): Siguiendo la regla de asignación de costes que propone Bird (1976), asignaríamos a cada población (vértice) el coste de la arista incidente en el vértice, del único camino que lo conecta con la fuente, en un árbol de unión de mínimo coste definido sobre el grafo. Así en este caso la regla de Bird daría lugar al reparto (1,2,2). Como ya hemos mencionado, en Granot y Huberman (1981) se demuestra que el reparto obtenido con la regla de Bird es una asignación del núcleo. 3.2. Caso Vectorial. En el caso vectorial, según sea la relación de preferencia aceptada por los jugadores tenemos dos conceptos distintos de núcleo del juego que denominaremos núcleo de preferencia y el núcleo de dominancia (véase Fernández et al. 2002a y 2002b). 3.2.1.Núcleo de Preferencia. Es razonable pensar que una coalición sólo aceptará una asignación de pagos si en el reparto de costes, los costes asignados a dicha coalición son inferiores o iguales que todos los costes que están en su conjunto característico, es decir, inferiores o iguales a todos los vectores de coste que puede garantizarse por si misma sin colaborar con los demás jugadores. En lo que sigue, para simplificar la notación, entenderemos por X S ≤ v(S ) que X Sj ≤ z Sj , ∀j = 1,2,..., k .∀z Sj ∈ v( S ) .

Definición: Llamamos núcleo de preferencia de un juego (N, v) y lo notaremos por C(N, v; ≤ ) al conjunto de las asignaciones X ∈ I * ( N , v) , tal que X S ≤ v( S )∀S ⊂ N . Para establecer una condición suficiente y necesaria para que el núcleo de preferencia sea no vacío consideremos un vector z ∈ IR k , no necesariamente en v(N), y los k juegos escalares que definimos a continuación. Definición: El juego escalar l-componente, (l =1,2,...,k) asociado a zS es un par (N, vlz ), donde N es el conjunto de jugadores y vlz es la función característica definida por: 1. vlz (O/ ) = 0 2. Para cada coalición no vacía S ⊂ N , vlz ( S ) = min TS

∑e

ij l

i , j∈ETS

donde ETS es el conjunto de aristas de un árbol de unión de mínimo coste, TS, en el grafo G S = ( S 0 , E S ) con S 0 = S U {0} . 3. vlz ( N ) = z l Obsérvese que para cada coalición no vacía, S ⊂ N , vlz (S ) es la solución del problema: min vlS s.a.: z S ∈ v(S ) donde z lS es la l-ésima componente del vector zS, l = 1,2,…,n. Nótese también que para una coalición fija S, si una asignación X del juego (N,v), verifica X S ≤ v(S ) entonces X S ≤ z * ( S ) , donde z * ( S ) = v1z ( S ), v2z ( S ),..., vkz ( S ) denota un vector k-dimensional cuyas componentes son, respectivamente, las soluciones del problema planteado anteriormente. Recíprocamente si X S ≤ z * ( S ) entonces X S ≤ v(S ) .

(

)

Teorema: El núcleo de preferencia es no vacío si y sólo si existe al menos un vector z N ∈ v(N ) tal que todos los juegos l-componentes (N, vlN ) son balanceados. N

Demostración: Si cada juego escalar l-componente (N, vlz ) es balanceado, N

consideremos cualquier asignación, Xl en el núcleo de (N, vlz ), l = 1,2,...,k. Entonces la matriz X, cuyas filas son Xl, l = 1,2,...,n., es una asignación asociada a z N . Es más, para cada S ⊂ N , X S ≤ z * ( S ) y X S ≤ v(S ) . Si suponemos que X es una asignación en el núcleo de preferencia tal que N XN = zN ∈ v(N ) entonces X S ≤ v(S ) , y X lS ≤ vlz (S ) ∀S ⊂ N ∀ l = 1,2,...,k. N

Consecuentemente Xl es una asignación del núcleo de (N, vlz ).

Ejemplo2 (continuación): En el ejemplo estudiado anteriormente asignamos (2,6) t ∈ v( N ) mediante la matriz X, que está en el núcleo de preferencia. No obstante no podemos dividir entre los jugadores el vector zN = (4,5) t ∈ v( N ) mediante una N

asignación que pertenezca al núcleo de preferencia, ya que el juego (N, v1z ) no es balanceado. Siendo: 0 1 1  X =  3  1 2 La asignación del ejemplo se ha obtenido aplicando la regla de Bird que asigna a cada jugador i ∈ N el vector de costes de la arista incidente en i, del único camino de 0 a i en el árbol de unión de coste Pareto-mínimo correspondiente (véase Bird, 1976). Desgraciadamente la regla de asignación de costes de Bird no es, en general, una manera de obtener las asignaciones del núcleo de preferencia, como veremos en el siguiente ejemplo. Ejemplo3: Consideremos de nuevo el ejemplo anterior con la siguiente asignación de costes: 1

 2    2

 0    2

1     3

0 1     4

2

 5    5

 0   3

3

El juego bi-criterio definido sobre árboles de unión de coste Pareto- mínimo asociado a este grafo es: S

{1}

{2}

{3}

{1,2}

{1,3}

{2,3}

N

V(S)

1     3 

1     4 

1     5 

 2   3  1   ,  ,    7   5   8 

1     5 

1     7 

 3  1   ,    7   8 

Si consideramos zN = (1,8) t ∈ v( N ) es fácil comprobar que los dos juegos N

componentes escalares (N, vlz ), l =1,2. son balanceados y por consiguiente el vector (1,8)t puede ser dividido entre los tres jugadores mediante asignaciones del núcleo de preferencia. Por ejemplo, X ∈ C ( N , v, ≤) . Sin embargo la asignación de Bird Y ∉ C ( N , v, ≤) , ya que la coalición {1,2} tendría un gasto asociado de X {1, 2} = (1,6)t, por lo que no se verificaría que X {1, 2} ≤ v({1,2}) . Siendo: 1 0 X =  2 3

0  3 

1 0 Y =  3 3

0  2 

3.2.1.Núcleo de Dominancia. Imponer que las coaliciones sólo aceptan las asignaciones con coste inferior o igual, componente a componente, que todos los vectores de su conjunto característico es una condición demasiado fuerte. Supongamos que las coaliciones aceptaran un reparto de costes si este no fuese superior en todas las componentes a otro que pudiera garantizarse, es decir, a otro de su conjunto característico. Notaremos entonces X S ≥/ v(S ) , para expresar que XS ≥/ zS ∀z S ∈ v(S ) , esto es, no existe z S ∈ v(S ) tal que X Sj ≥ z Sj ∀j = 1,2,..., k . y X S ≠ z S . Con esta relación de preferencia aceptada por los jugadores, el concepto de núcleo sería ahora el siguiente: Definición: El núcleo de dominancia de (N,v) es el conjunto de asignaciones, X ∈ I * ( N , v) , tal que X S ≥/ v(S) ∀S ⊂ N . Denotaremos este conjunto por C(N, v, ≥/ ). En el siguiente resultado probamos que una asignación de costes de Bird vectorial es una asignación del núcleo de dominancia. Teorema: Sea TN un árbol de unión de coste Pareto-mínimo de un grafo completo, sea z N ∈ v(N ) su coste asociado. La asignación de Bird vectorial correspondiente, X, es una asignación del núcleo de dominancia. Demostración: es claro que XN =v(S) ∈ v(N ) y por consiguiente X ∈ I * ( N , v) . Dada una coalición no vacía S ⊂ N y dado TS un árbol de unión de coste Pareto-mínimo del grafo G S = ( S 0 , E S ) con S 0 = S U {0} . Construimos el árbol de unión TˆN para N0 como sigue, añadimos todos los nodos de N \S a TS y por cada i ∈ N \S añadimos a las aristas de TS la arista incidente en i del único camino de 0 a i en TN. El árbol TˆN así construido es un árbol de unión para N0. Así si z S (TS ) ∈ v( S ) es el vector de costes asociado al árbol de unión TS, z (TˆN ) = z S (TS ) + X N / S es el vector de costes asociado al árbol de S N/S . unión Tˆ . Por lo que z N ≥/ z (Tˆ ) , esto es, z N =X N =X S + X N \S ≥/ z (TS ) + X N

N

Entonces X ≥/ z (TS ) . Como TS es cualquier árbol de unión de mínimo coste del grafo S

S

G S = ( S 0 , E S ) , podemos concluir que X S ≥/ v(S). Ejemplo2 (continuación): En el ejemplo estudiado anteriormente vimos que el vector (4,5) t ∈ v( N ) no podía ser dividido entre los jugadores mediante una asignación que perteneciera al núcleo de preferencia, no obstante, como acabamos de probar, la regla de asignación de costes de Bird nos proporciona un reparto que pertenece al núcleo de dominancia, que vendría dado por: X ∈ C ( N , v, ≥/) . Siendo: 1 1 X=  1 2

2  2 

4. CONCLUSIONES. La aplicación de los juegos cooperativos al reparto de costes ha sido una de las cuestiones más ampliamente estudiada en la literatura de los últimos tiempos. Cuando se trata de repartir costes de distinta índole se hace necesario ampliar la teoría de juegos al terreno multicriterio. La generalización al campo vectorial pone de manifiesto que considerar los repartos de costes componente a componente no es suficiente y da una visión de la situación pobre y demasiado restrictiva. De hecho, la extensión natural de los resultados de la teoría de juegos escalares se establece cuando se considera una estructura de preferencia que permita aceptar un coste peor que el que garantizamos en algún otro criterio. Así se pone de manifiesto en este trabajo, al estudiar cómo la extensión de la regla de Bird proporciona asignaciones del núcleo de preferencia, que no están necesariamente en el núcleo de dominancia. Otras cuestiones interesantes que no se responden en este trabajo podrían ser las siguientes: Búsqueda de condiciones para que la regla de Bird nos proporcione asignaciones en el núcleo de preferencia. Consideración de otras estructuras de preferencia. Consideración de distintos órdenes tipológicos. Pueden ser particularmente interesantes aquellos basados en funciones de utilidad, cuyo tratamiento es sencillo en el caso lineal. BIBLIOGRAFÍA. Bird C. G., 1976. On cost allocation for a spanning tree: A game theoretic Approach. Networks 6, 335-350. Claus A.,Kleitman D.J., 1973. Cost Allocation for a Spanning Tree. Networks 3, 289304. Curiel, I., 1997. Cooperative Game Theory and Applications. Kluwer Academic Publisher. Ehrgott, M., 2000. Multicriteria Optimisation. In Lecture Notes in Economics and Mathematical Systems 491. Springer. Fernández, F. R., Hinojosa, M. A. and Puerto, J., 2002a.Multiobjective Linear Production Games. In Petrosjan L.A. and Mazalov V.V. (eds.) Game Theory and Applications VII. Nova Science Publishers. Fernández, F. R., Hinojosa, M. A. and Puerto, J., 2002b. Core Concepts in VectorValued Games. Journal of Optimisation Theory and Applications 112, 331-360. Granot, D., Huberman, G., 1981. Minimum Cost Spanning Tree Games. Mathematical Programming 21, 1-18.