Una solución dinámica para juegos con utilidades transferibles
Resumen:

En este trabajo definimos un tipo de solución dinámica para juegos con utilidades transferibles. La solución dinámica fue introducida por Shenoy (1980) en el marco de juegos abstractos como un medio para describir algunos procesos de negociación. En el contexto de los juegos con utilidades transferibles estudiamos su comportamiento tanto en la clase de los juegos equilibrados (con Core no vacío) como en el de los juegos no equilibrados. En esta última subclase mostramos que la solución dinámica debe contener los elementos de ciertos ciclos de preimputaciones denominados ciclos maximales. Estos ciclos aparecen en relación con un esquema dinámico elaborado originalmente para aproximar puntos en el Core de un juego. En la subclase de los juegos equilibrados, la solución dinámica coincide con el Core, lo que establece un enfoque unificado de solución.

El problema de existencia de ciclos maximales no está completamente resuelto, pero en algunas subclases de juegos podemos exhibir teoremas de existencia y una descripción completa de la solución dinámica.

Abstract:

In this paper we define a particular dynamic solution (Shenoy, 1980) for abstract games related to games with transferable utilities (TU-games). We show that this solution must contain some cycles of pre-imputations, maximal U-cycles (provided this cycles exist). The existence of such cycles is strongly connected to the non-balancedness of the TU-game under study. Besides, the dynamic solution coincides with the core of the game in the case of balanced TU-games. Thus, it provides an unifying solution concept for games with transferable utilities.

Palabras clave:
    • juegos cooperativos;
    • solución dinámica;
    • Core.
Clasificación JEL:
    • C71.

Introducción

En Cesco (2003) se caracteriza a los juegos n-personales no equilibrados como aquellos en los que existe al menos un ciclo de preimputaciones con ciertas propiedades específicas denominado ciclo fundamental (sección I). La clase de ciclos fundamentales incluye la de los U-ciclos y la de los U-ciclos maximales.

Recientemente se ha mostrado que los U-ciclos son suficientes para caracterizar los juegos con Core vacío (Cesco, 2005). Utilizando U-ciclos maximales se han obtenido resultados positivos de caracterización de los juegos no equilibrados sólo en algunos casos particulares (Cesco y Calí, 2004). No obstante ello, los ciclos maximales tienen el atractivo de aparecer como ciclos límite de un algoritmo o esquema de transferencia elaborado en principio para aproximar puntos en el Core de un juego (Cesco, 1998) y desde esta perspectiva, pueden ser aproximados numéricamente. Aparte del problema general de existencia, parece interesante discernir en qué medida los ciclos maximales ofrecen información de este proceso dinámico que puede ser empleado para aproximarlos. En este artículo establecemos una relación con el concepto de solución dinámica para juegos abstractos introducida en Shenoy (1980). Un juego abstracto es un par (X, dom), en el que X describe el conjunto de resultados del juego y dom es una relación definida en los elementos de X (más precisamente, domX × X). La solución dinámica fue introducida para reflejar ciertas características de algunos procesos dinámicos de negociación y fue empleada para modelar algunos procesos de formación de coaliciones (Shenoy, 1979). Por otra parte, cuando el juego abstracto en consideración tiene un conjunto finito de resultados posibles, la solución dinámica coincide con el concepto de conjunto R-admisible de Kalai, Pazner y Schmeidler (1976).

La metodología que nosotros empleamos en este trabajo es la siguiente: con cada juego, que siempre será con utilidades transferibles, asociamos un juego abstracto definiendo una relación dom apropiada en el conjunto de preimputaciones (imputaciones). Mostramos entonces las preimputaciones asociadas a una clase particular de U-ciclos maximales incluidas en la solución dinámica de este juego abstracto. De esta manera, la existencia de una solución dinámica no vacía puede inferirse de la existencia de ciertos ciclos maximales. Es interesante destacar que este problema de existencia está resuelto de manera general sólo en el caso que X sea finito.

La existencia de ciclos maximales sólo puede probarse en el marco de los juegos no equilibrados. No obstante ello, la solución dinámica que nosotros proponemos tiene sentido para cualquier juego. En el caso de que el juego sea equilibrado, la solución dinámica coincide con el Core. Así, la solución dinámica aparece como un concepto de solución unificador que en el caso de los juegos equilibrados se comporta como el concepto de solución más aceptado como es el Core. El Core tiene una geometría en principio simple, poliedral. Mucho menos puede decirse de la solución dinámica en el caso de los juegos no equilibrados, aunque mostramos en esta nota que, en algunos casos, puede describírsela completamente en términos de ciclos maximales.

Los puntos en el Core de un juego son aceptados, en general y sin mayores objeciones, como resultados razonables de cualquier proceso de negociación debido, fundamentalmente, a sus propiedades de estabilidad que los hacen resistentes a objeciones por parte de coaliciones. Por el contrario, en los juegos no equilibrados no hay, hasta la fecha, un concepto que reciba igual consideración por parte de los especialistas. En estos casos existe el convencimiento de que cualquier proceso de negociación generará una serie de objeciones y contraobjeciones sin converger a un punto determinado. Reconocido este hecho, es necesario apelar a segundos argumentos para seleccionar puntos aceptables como resultados de negociaciones; así surgen, entre otras, las nociones de nucleolo en el que se busca que la mayor objeción sea lo más pequeña posible o los conjuntos de regateo con los que sus puntos son tales que a cada objeción que se le presente están en condiciones de contraponerle una contraobjeción o las teorías de valor (Shapley, Banzhaf, etc.) que asignan un peso a cada jugador según diferentes criterios y proponen distribuciones de utilidad acorde con esos pesos. Para una recopilación de los conceptos de solución clásicos que se mencionan en este artículo recomendamos al lector la excelente obra de Owen (1995).

La solución que nosotros proponemos en este trabajo representa un conjunto de estadios intermedios alcanzables en un proceso definido de negociación y que están caracterizados por una situación de equilibrio o status quo reflejada en la propiedad cíclica de las componentes elementales de la solución dinámica (ciclos maximales). Pretendemos que esta situación de equilibrio entre las coaliciones asociadas a un ciclo permita motivar un concepto de solución que considere como resultados posibles, no sólo distribuciones de utilidad sino también familias de coaliciones asociadas que pudiesen formarse como resultado del proceso de negociación. Hasta el momento hemos definido una noción de core, el M-core cuyos elementos son pares (x, ß) en que y x R n y ß es una familia equilibrada minimal, que coincide con el Core clásico si un juego es equilibrado y en tanto se identifiquen los elementos ( x, N) del M-core con los vectores x del Core clásico, pero que además es no vacío para los juegos no equilibrados y satisface un sistema de axiomas muy similar al que caracteriza al Core clásico (Cesco, 2006). La manera de conectar la solución dinámica con puntos en el M-core está siendo objeto de estudio en un marco que plantea la posibilidad de generar una sucesión de juegos encadenados, cada uno dependiendo del resultado del anterior.

La organización del trabajo es la siguiente. En la sección I establecemos la notación que emplearemos en lo sucesivo y algunos conceptos básico de la teoría de juegos necesarios para el desarrollo del trabajo. En la sección II definimos los ciclos de preimputaciones y dejamos establecido que la existencia de un U-ciclo maximal implica la exsitencia de Core vacío para un juego (teorema 1). Introducimos la solución dinámica en la sección III con base en el enfoque de Shenoy (1980) y probamos varios resultados que la relacionan con los ciclos maximales. En la sección IV tratamos el caso de juegos de tres personas y caracterizamos la solución dinámica como el conjunto de las imputaciones en los dos únicos ciclos maximales que tiene el juego. Extendemos estas obsevaciones a una subclase de juegos con n jugadores en una sección final.

I. Notación

Un juego con utilidades transferibles, o simplemente un juego, es un par (N, v) en el que N = {1, 2, ... , n} representa el conjunto de jugadores y v su función característica. Suponemos que v es una función real definida en la familia de subconjuntos de N , P ( N ) que satisface v( N ) =1 y v({i}) = 0 para cada iN. Llamamos coaliciones a los elementos de P ( N ). Un juego ( N , v) es monótono si v(S) ≥ v(T) toda vez que ST.

Definimos los conjuntos de preimputaciones e imputaciones como E = {x = (x1,…, xn) ∈ R n : Σi∈N xi = 1} y A = {x∈E: xi ≥ 0 para toda i ∈ N}, respectivamente.

Para cada coalición S y preimputación x, el exceso de la coalición con respecto a la preimputación es e(S, x) = v(S) - x(S), en que x( S) = Σ i∈S xi si S ≠ Φ y x(S) = 0 si S = Φ. El exceso e(S, x) representa la ganancia agregada adicional para la coalición (o pérdida si es negativo), en términos de utilidad, si sus miembros deciden abandonar un convenio que asigna x1, ... , xn unidades de utilidad a cada uno de los jugadores en N para formar su propia coalición que les garantiza obtener una utilidad agregada v( S). El Core de un juego (N , v) es C ={xE: e( S, x) ≤ 0 para toda SP(N)}.

El Core es el concepto de solución más aceptado para los juegos con utilidades transferibles pero puede ser vacío. El teorema de Shapley-Bondareva (Bondareva, 1963; Shapley, 1967) caracteriza los juegos con Core no vacío. La noción de familia equilibrada de coaliciones desempeña un papel central para establecerlo. Una familia de coaliciones no vacías ß ⊆ P ( N ) es equilibrada si existe un conjunto de números positivos (λS) S∈ß que satisfacen

para todo iN. Los números (λS)S∈ß se denominan pesos de equilibrada para ß. ß es equilibrada minimal si no contiene una subfamilia propia que sea equilibrida; en este caso, el conjunto de pesos de equilibrio es único. Un juego (N, v) es equilibrado si

para toda familia equilibrada ß con pesos de equilibrio (λS)S∈ß. El teorema de Shapley-Bondareva estabece entonces que un juego (N, v) tiene Core no vacío si y sólo si es equilibrado. Una familia en condiciones de objetar es una familia que no satisface (1).

Para el resto del artículo, la noción de U-transferencia o simplemente transferencia es central. Dada xE y una coalición propia S, decimos que y se obtiene de x por una transferencia desde N \S hacia S (sucintamente, y es una transferencia desde x vía S) si

Aquí

si S es una coalición propia y el vector nulo de R n en caso contrario; |S| indica el número de jugadores en S. El vector βS describe una transferencia de una unidad de utilidad desde los miembros de N \S hacia los de S de manera uniforme, en el sentido que tanto la disminución de utilidad en N \S como el aumento en S se reparte igualitariamente entre sus respectivos participantes. La transferencia es maximal si e(S, x) ≥ e(T , x) para toda TP ( N ).

II. Ciclos de preimputaciones

En esta sección introducimos dos clases de ciclos de preimputaciones y enunciamos, sin su demostración, algunos resultados probados en trabajos anteriores, principalmente en Cesco y Aguirre (2002) y Cesco (2003).

Definición 1. Un U-ciclo c (o simplemente un ciclo) en un juego (N, v) es una sucesión finita de preimputaciones ( x k ) k = 1 m , m > 1 que tiene asociada una sucesión ( S k ) k = 1 m de coaliciones propias de N (no forzosamente todas diferentes) y cuyos elementos satisfacen la siguiente relación de vecindad:

y

Un ciclo es maximal si e(Sk , xk) ≥ e(S, xk) para toda coalición S y para todo k-1, ... , m. Si e(Sk , xk) > e(S, xk) para toda SS k y para todo k = 1, ... , m, el ciclo es regular; en caso contrario decimos que es singular.

Dado un ciclo c = ( x k ) k = 1 m , denominamos soporte de c a la sucesión asociada ( S k ) k = 1 m y la denotamos supp(c); denotamos con ß(supp(c)) (o simplemente ß(c) al conjunto de coaliciones ensupp(c), esto es, ß(c) ={SP (N): S = Sk para algún k =1, ... , m}. Al conjunto de imputaciones en un ciclo lo denotamos por X(c). Entonces, X( c) ={xE: x = xk para algún k =1, ... , m}.

Un resultado importante mostrado en Cesco (2003), teorema 1, indica que para todo ciclo c , ß(c) es una familia equilibrada de coaliciones. Este resultado fue establecido para una clase aun más amplia de ciclos denominados ciclos fundamentales. Más aun, ß(c) es una familia en condiciones de objetar. Un ciclo es fundamental si en (3) remplazamos e(Sk, xk) por una cantidad 0 < μk (xk ) ≤ e(Sk , xk).

Nota 1. La existencia de ciclos fundamentales en un juego (N, v) está estrechamente relacionada con la no existencia de puntos en el Core del juego. Los teoremas 3 y 9 en Cesco (2003) permiten establecer la siguiente caracterización: un juego (N, v) es equilibrado si y sólo si no existen ciclos fundamentales en (N, v). Recientemente, se ha probado una caracterización similar en término de U-ciclos (Cesco, 2005).

No se ha conseguido todavía un resultado general que caracterice los juegos equilibrados en términos de la no existencia de U-ciclos maximales. En ese sentido sólo disponemos resultados parciales. Consideremos en un juego con n jugadores la siguiente familia equilibrada de coaliciones ß ={S1, ... , S}, en que S1 = N\{n} y Sk = N\{k -1}, k = 2, ... , n. En Cesco y Calí (2004) probamos el siguiente teorema:

Teorema 1. Sea (N, v) un juego con función característica dada por

Las siguientes afirmaciones son equivalentes: i) el juego es equilibrado; ii) no existe un U-ciclo en el juego; si el juego es monótono entonces i) es equivalente a iii) no existe un U-ciclo maximal en el juego.

Nota 2. Una propiedad que poseen lo ciclos maximales es que aparecen como ciclos límites de un sistema dinámico discreto. En Cesco (1998) se introdujo un esquema de transferencia de utilidades que converge a puntos del Core en los juegos equilibrados. Formalmente, el esquema en un juego (N, v) es una sucesión de preimputaciones ( x k ) k = 1 tal que, para todo k =1, 2, …, xk+1 es una transferencia maximal desde xk. Se instrumentó una versión de este esquema de transferencia y cuando se corrió sobre juegos no equilibrados siempre generó ciclos límites que resultaron ser ciclos maximales. No hay todavía una prueba general de este hecho.

III. La solución dinámica

En esta sección introducimos primero el concepto de solución dinámica propuesto por Shenoy (1980) para reflejar algunos de los aspectos de la dinámica de un proceso de negociación. La terminología que utilizamos es similar, aunque con algunas diferencias, a la de Shenoy. Luego, en el contexto de los juegos con utilidades transferibles, y mediante la definición de una relación dom particular, generamos un concepto de solución para esta clase de juegos.

Un juego abstracto es un par (X, dom); aquí X es un conjunto arbitrario cuyos elementos se denominan los resultados del juego y una relación binaria dom definida en X llamada dominación. Un resultado yX es accesible desde el resultado xX si existen resultados

con m un entero positivo tal que

Denotamos esta relación por yx y suponemos que siempre xx. Así, esta relación binaria resulta ser reflexiva y transitiva.

Decimos que dos resultados x, yX se comunican si yx y xy. En este caso escribimos xy. Comunicación es una relación de equivalencia (Shenoy, 1980, proposición 2.1).

Definición 2. Una solución dinámica elemental (d-solución elemental) para un juego abstracto (X, dom) es un conjunto DX tal que i) si xD, yX\D, entonces y x; ii) si x, yD, entonces xy. Si |D|< ∞ decimos que la d-solución elemental D es finita.

La condiciones i) y ii) establecen propiedades de estabilidad externa e interna respectivamente para D en un sentido dinámico. Una d-solución elemental es una clase de equivalencia respecto a la relación de comunicación aunque la afirmación recíproca no es verdadera (Shenoy, 1980, proposición 3.1). Llamemos D = {DX: D es una d-solución elemental}.

Definición 3. La solución dinámica (d-solución) P para un juego abstracto (X, dom) es la unión de todas sus soluciones dinámicas elementales, esto es, P = D D D . La solución dinámica finita (d-solución finita) Pf para (X, dom) es la unión de todas sus soluciones dinámicas finitas.

Nota 3. La solución dinámica siempre existe y es única en un juego abstracto, aunque puede ser vacía (Shenoy, 1980, proposición 3.3). Estos hechos también son válidos en relación con la solución dinámica finita.

Definición 4. El Core C(x, dom) de un juego abstracto (X, dom) es el conjunto de resultados no dominados respecto a la relación ←, esto es,

Definición 5. Dado un juego (N, v), su E-juego abstracto asociado es ( X, dom), en que X = E, el conjunto de preimputaciones y dom es la relación binaria definida en E por: y dom x si y sólo si y es una transferencia maximal desde x [véase (2)].

El A-juego abstracto asociado a (N, v) se define similarmente remplazando E por A, el espacio de imputaciones en la definición anterior.

De ahora en adelante, denotaremos al E-juego (A-juego) abstracto asociado a (N, v) por (E, dom) ((A, dom)). Las d-soluciones elementales y d-soluciones que estudiamos a continuación están referidas a estos juegos abstractos asociados a (N, v).

Lema 2. Sea (N, v) un juego y x, yE, xy. Entonces xy si y sólo si existe un ciclo maximal ( x k ) k = 1 tal que x = xi, y = xj para un par de índices ij.

Demostración. Si yx existen x2, ... , xk tal que x 2 dom x1 = x, ... , xk+1 = y dom xk. Similarmente, xy , y, entonces existen xk+2, ... , xm tal que xk+2 dom xk+1 = y, ... , xm+1 = x dom xm . Así, xy implica la existencia de preimputaciones x1, ... , xk+1, ... , xm que satisfacen que xl+1 es una transferencia maximal desde xl para todo l =1, ... , m. Además, xm+1 = x1. De esta manera ( x k ) k = 1 m es un ciclo maximal con x1 = x, xk+1 = y.

Para ver la afirmación recíproca podemos suponer, sin pérdida de generalidad, que x1 = x, x k+1 = y , 1 ≤ k< m. En este caso es claro que x2 dom x1 = x, ... , xk+1 = y dom xk ; así yx. Además, xk+2 dom xk+1 = y , ... , xm+1 = x dom xm y por tanto xy. Concluimos entonces que xy.▪

Proposición 3. Sea (N, v) un juego equilibrado. Entonces D es una d-solución elemental en su juego asociado ( E, dom) no vacía si y sólo si D = {x}, xC.

Demostración. Primero mostraremos que si D es una d-solución elemental finita entonces |D| =1.Si éste no fuese el caso existirían dos preimputaciones xy en D y debido a la propiedad ii) de este conjunto, xy. Por el lema anterior existe un ciclo maximal en (N, v) que une x y y. Pero la existencia de un ciclo maximal implica que el juego es no equilibrado (véase la nota 1), hecho que contradice la hipótesis. Entonces D ={x}. Afirmamos además que xC. Si éste no fuese el caso, existiría una coalición propia S con e(S, x) > 0 y tal que e(S, x) ≥ e(T, x) para toda otra coalición T. Sea y la transferencia maximal desde x vía S.Entonces yD y yx, hecho que contradice entonces la estabilidad externa i) de D.

Para ver la afirmación recíproca, sea D ={x}, xC. La condición ii) de la definición 2 se satisface trivialmente. Por otro lado, puesto que xC, max{e(S, x): SN} = 0 y por tanto no existe una transferencia maximal desde x a cualquier otra preimputación y. Concluimos entonces que si yD, y x, y esto muestra que D es una d-solución elemental. ▪

Los siguientes resultados son conclusiones simples de esta proposición.

Corolario 4. En un juego equilibrado (N, v) la solución dinámica y la solución dinámica finita de ( E, dom) (( A, dom)) coinciden con el Core del juego.

Corolario 5. El Core de un juego equilibrado y el Core de su juego abstracto (E, dom) (( A, dom)) coinciden.

Demostración. Por Shenoy (1980, proposición 3.4, obtenemos que C(E, dom) P. Por el corolario 4 obtenemos que C(E, dom)C.

La inclusión contraria está de hecho demostrada el la última parte de la demostración de la proposición 3. ▪

Proposición 6. Sea (N, v) un juego no equilibrado. Si D es una d-solución elemental finita no vacía en su juego abstracto ( E, dom), existe un ciclo maximal c = ( x k ) k = 1 m tal que D = X( c ).

Demostración. Sea D una d-solución elemental finita no vacía. Afirmamos que |D | >1.Si éste no fuese el caso, D ={x}y puesto que el juego es supuesto no equilibrado, existiría una coalición S con exceso maximal positivo e( S, x). Entonces, la transferencia maximal y desde x vía X sería tal que yD y yx, lo que contradice la propiedad de estabilidad externa para D. Sean entonces x ≠ y dos preimputaciones en D. Por el lema 2 existe en ciclo maximal c = ( x k ) k = 1 m tal que x = xi , y = xj para un par de índices ij. Sin pérdida de generalidad podemos suponer que i =1. Afirmamos que X(c) ⊆ D. De hecho, si éste no fuese el caso, existiría rm tal que xrD. Debido a la propiedad de estabilidad externa de D, xr x1. Pero puesto que ambos pertenecen al ciclo xrx1 se obtiene así una contradicción. Podemos suponer también que | X(c)| ≥ | X ( c ~ ) | para cualquier otro ciclo maximal c ~ tal que X ( c ~ ) D. En estas condiciones D = X(c). Si no fuese así, existiría yD\x(c), x1y y un ciclo maximal c ~ = ( x ~ 1 ) l = 1 r con x ~ 1 = x 1 y para algún 1< lr. Pero entonces c ~ = ( x 1 , ,   x m ,   x ~ 1 , x ~ r ) es también un ciclo maximal y puede mostrarse, con la misma técnica empleada en el caso de X(c), que X ( c ~ ) D. Pero puesto que |X ( c ~ ) |< | X ( c ~ ) | obtendríamos una contradicción con la maximalidad supuesta en |X(c)| , entonces D = X(c). ▪

En general, no todo ciclo maximal c es tal que X(c) es una d-solución elemental finita. Pero es válido el siguiente recíproco parcial de la proposición 6.

Proposición 7. Sea (N, v) un juego no equilibrado. Si c = ( x k ) k = 1 m es un ciclo maximal regular, entonces D = X(c) es una d-solución elemental finita.

Demostración. Por el lema 2 es claro que D es estable internamente. Supongamos ahora que existe yD. Esto implica que existe y ^ D, xkX(c) tal que y dom xk , de donde seguiría que y ^ = xk + e(S, xk) · βS para algún S con e(S, xk) ≥ e(T , xk) para todo TN. Pero entonces e(S, xk) = e(Sk , xk). Si S = Sk , y = xk+1 D que contradice el hecho que y ^ D y si SSk también obtenemos una contradicción con la regularidad supuesta para c . Por tanto si yD, y x que muestra que D es también estable externamente.▪

Como una consecuencia directa de las dos proposiciones anteriores tenemos la siguiente:

Proposición 8. Sea (N, v) un juego no equilibrado tal que todos sus ciclos maximales sean regulares. Entonces la d-solución finita Pf = c X ( c ) , en que c recorre el conjunto de ciclos maximales regulares.

Podemos caracterizar también aquellos ciclos maximales singulares cuyas preimputaciones generan una d-solución elemental finita.

Proposición 9. Sea c un ciclo maximal singular en (N, v). Entonces X(c) es una d-solución elemental finita D si y sólo si: i) no existe otro ciclo maximal c ~ tal que X ( c ~ ) X(c), y ii) para cada xX(c) tal que existe ST con e(S, x) = e(T , x) ≥ e( T ~ , x) para toda T ~ N, ambos, y = x + e(S, x) · βS y z = x + e(T, x) · βT , pertenecen a X(c).

Demostración. Supongamos que X(c) es una d-solución elemental finita D. Si i) no fuese válida existiría un ciclo maximal c ~ con X ( c ~ ) X(c). Esto implicaría la existencia de xX(c) y yX ( c ~ ) \X(c) tal que yx en contradicción con el hecho de que X(c) es una d-solución. Para probar ii) podemos considerar, por ejemplo, que zX(c). Pero puesto que zx contradiríamos nuevamente el hecho que X(c) es una d-solución elemental.

Para ver el recíproco, sea c un ciclo maximal singular que satisface i) y ii). Debemos mostrar que D = X(c) es una d-solución elemental. La propiedad de estabilidad interna ii) de la definición 2 se satisface trivialmente debido a que c es un ciclo. Para probar la propiedad de estabilidad externa i) de la definición 2, supongamos que existen x ~ D, yD tal que y x ~ . Sea xk la última preimputación en la cadena xm = y dom xm-1 , ... , x2 dom x1 dom x0 = x ~ que pertenezca a D. Es claro que xk es un punto que satisface las hipótesis ii) que implica, en particular, que xk+1 debe pertenecer a X(c) que es claramente una contradicción. Esto completa la prueba. ▪

Como consecuencia de este último resultado, si en la proposición 8 los ciclos recorren tanto la clase de los ciclos regulares como la de los ciclos singulares que satisfacen i) y ii) de la proposición 9 obtenemos una caracterización general para Pf en la subclase de los juegos no equilibrados en términos de ciclos maximales. Como en los juegos equilibrados Pf coincide con el Core, tenemos entonces, para la solución dinámica finita, una descripción completa en la clase de juegos con utilidades transferibles. En la sección IV probamos que, para algunas clases de juegos, restringirse al estudio de soluciones dinámicas finitas no representa ninguna limitación.

La relación binaria ← resulta ser la clausura transitiva de la relación dom. En la terminología de la bibliografía de procesos de formación de coaliciones, la dominación inducida por dom es usualmente llamada dominación directa en tanto que la inducida por ←, dominación indirecta. La noción dom que introducimos en este trabajo podría ser también interpretada como un tipo de dominación directa (fuerte) en el sentido de Sengupta y Sengupta (1994) para propuestas asociadas con la partición ( S, N\S) de N , en que la racionalidad grupal es solamente satisfecha para S. Con base en esta línea de razonamiento, ← representaría, en el contexto estudiado por los mencionados autores, el análogo de la dominación indirecta inducida en el conjunto de propuestas restringidas a esta familia limitada de propuestas. Más aún, cada elemento en un ciclo regular sería una propuesta viable en la terminología de Sengupta y Sengupta y el conjunto de propuestas viables coincidiría con Pf en los juegos en que la condición de la proposición 8 estuviese presente.

Las soluciones (elementales) estudiadas en este artículo se caracterizan por exhibir una propiedad de estabilidad interna y otra de estabilidad externa presentando una similitud formal con el concepto de conjunto estable de Von Neumann y Morgenstern (1944) y que es también exhibida en el enfoque de Sengupta y Sengupta. Sin embargo hay una diferencia importante que debe puntualizarse. La propiedad de extabilidad externa ii) de la definición 2 es conceptualmente diferente de la probada en Sengupta y Sengupta (1994), teorema 3, para el conjunto de propuestas viables. No obstante ello, mostramos en la sección IV que para una cierta clase de juegos una propiedad de estabilidad externa que conceptualmente se asemeja a la introducida por Von Neumann y Morgenstern y recuperada en Sengupta y Sengupta (1994) es satisfecha de manera aproximada (en un sentido que precisaremos en la próxima sección.)

Concluimos esta sección destacando que nuestra relación ←, y, consecuentemente, todo nuestro enfoque del tema, corresponde a una teoría en la que los jugadores se comportan de una manera “miope”, en contraste con una serie de trabajos que incorporan a los modelos de formación de coaliciones alguna forma de previsión en los procesos de negociación (por ejemplo Chew, 1994; Xue, 1998; Konishy y Ray, 2003; Barbera y Gerber, 2003).

IV. La solución dinámica en juegos con tres jugadores

Los resultados de la sección anterior muestran que las imputaciones asociadas con ciclos maximales son candidatas a conformar soluciones dinámicas elementales y, en algunos casos, hasta pueden caracterizar la solución dinámica. No obstante ello, el problema de existencia de ciclos maximales está todavía abierto. El objetivo de esta sección es estudiar la solución dinámica en juegos monótonos de tres jugadores y mostrar que, en el caso no equilibrado, son válidas las siguientes afirmaciones: i) existen sólo dos ciclos maximales; ii) todos los ciclos son regulares, y iii) el esquema de transferencia descrito en la sección II siempre tiene como ciclo límite uno de estos ciclos maximales para cualquier imputación inicial.

Para esta clase de juegos y de acuerdo con la proposición 8, la d-solución finita está determinada por los ciclos maximales. Pero además coincide con la d-solución dinámica. Finalmente, la afirmación iii) permite advertir que para todo yA \ P y ε > 0 existe xεA, xP tal que xεy con || xe - x || ≤ ε. Esta propiedad es un tipo de estabilidad externa aproximada en el espíritu de la noción dada por Von Neumann y Morgenstern al definir los conjuntos estables.

Consideremos de ahora en adelante un juego (N, v) con N ={1, 2, 3} y función característica dada por

Si 2/3< μ ≤ 1 entonces el juego es monótono y no equilibrado en el que la familia ß = {{1, 2}, {3, 1}} es la única en condiciones de objetar. Llamaremos S1 ={1, 2}, S2 ={2, 3} y S3 ={3, 1}.

Proposición 10. Sea (N, v) un juego con función característica dada por (7) y (8) con 2/3< μ ≤ 1. Entonces c ~ = { x ~ 1 , x ~ 2 , x ~ 3 } en que

es un ciclo maximal en (N, v).

Demostración. Calculando explícitamente los excesos para x ~ 1 obtenemos que

y e(S, x ~ 1 ) ≤ 0 en otro caso. Puesto que μ > 2/3, el máximo exceso es alcanzado solamente en S1. Para esta coalición,

Entonces, como

Así, la sucesión maximal iniciada en x ~ 1 tiene a x ~ 2 como segundo elemento. De manera similar puede mostrarse que el tercer elemento es x ~ 3 = (1 -μ, μ -1/3, 1/3) y que al calcular el cuarto, x ~ 4 , se recupera x ~ 1 . Por tanto ( x ~ 1 , x ~ 2 , x ~ 3 ) es un ciclo maximal. ▪

Nota 4. c - = ( x - 1 , x - 2 , x - 3 ) en que:

es también un ciclo maximal.

Los ciclos c ~ y c - descritos son esencialmente los únicos ciclos maximales en (N, v), que son además, regulares. Para mostrarlo probaremos el siguiente resultado de convergencia:

Teorema 2. Sea (N, v) un juego con función característica dada por (7) y (8) con μ = 1 y sea c ~ = ( x - 1 , x - 2 , x - 3 ) el ciclo

Entonces, si x 1 = ( x 1 1 , x 2 1 , x 3 1 ) es una imputación que satisface x 3 1 > x 1 1 > x 2 1 = 0 , la sucesión maximal (xk)k≥1 que tiene a x1 como imputación inicial posee las siguientes propiedades:

para todo k ≥ 1.

Demostración. Según las hipótesis consideradas, e(S3, x1) = 0. Mostraremos primero que si una preimputación x x - i satisface e(Si , x) = 0 para algún i =1, 2, 3, entonces

en que y = x + e(Si , x) · β S i . En esta demostración los índices i +1 serán considerados mod(3). Es fácil observar que βS es ortogonal a la variedad afín E(S) ={xE: e(S, x) = 0}para toda coalición no trivial S (Cesco, 1998, lema 2.2). Así, puesto que y - x ~ i + 1 son las proyecciones ortogonales en E(S) de x, x ~ i , respectivamente, obtenemos que

Nuestra afirmación sigue ahora advirtiendo que || y - x ||2 = e(Si , x) · || β S i ||2 es diferente de e(Si , x) · || β S i ||2 = || x ~ i + 1 - x ~ i ||2, de manera que la desigualdad estricta es válida en la relación anterior. Más aún, es válido que (véase Gráfica 1):

También se cumple que e(S1, x1) =1 - x 1 1 + x 2 1 = x 3 1 , e S 2 , x 1 = x 1 1 y e S 3 , x 1 = x 2 1 , de manera que el máximo exceso respecto a x1 es alcanzado por la coalición S1, con un valor de x 3 1 . Por tanto, x2 = x1 + x 3 1 · (1/2, 1/2, -1). Es fácil verificar que x 1 2 > x 2 2 > x 3 2 = 0 .Un cálculo simple indica que el máximo exceso respecto a x2 es alcanzado en S2 con un valor de x 1 2 . Por tanto x3= x2 + x 1 2 · (-1, 1/2, 1/2) que satisface x 2 3 > x 3 3 > x 1 3 = 0 , tiene un exceso máximo de x 2 3 alcanzado por S3.Un paso más muestra que x1+3 satisface x 3 1 + 3 > x 1 1 + 3 > x 2 1 + 3 = 0 que satisface una condición similar a la exhibida por x1. La validez de a) se obtiene ahora por un argumento inductivo.

Para probar b) tenemos en cuenta (9). Entonces

relación que generaliza a

para todo k ≥ 1. A partir de ella obtenemos que lim k x 1 + 3 k = x ~ 1 . Los otros casos se muestran en forma similar. ▪

Nota 5. Es válido un resultado completamente análogo para el ciclo c - = ( x - 1 , x - 2 , x - 3 ) con

y una imputación inicial x1 que satisfaga x 1 1 > x 3 1 > x 2 1 = 0 . Entonces el esquema de transferencia maximal iniciado en x1 tiene como ciclo límite a c - . Una importante consecuencia del teorema 2 es el siguiente resultado.

Proposición 11. Sea (N, v) un juego con función característica dada por (7) y (8) con μ =1. Los ciclos c ~ = ( x ~ 1 , x ~ 2 , x ~ 3 ) y c - = ( x - 1 , x - 2 , x - 3 ) dados por

respectivamente, son esencialmente, los dos únicos ciclos maximales de imputaciones en (N, v).

Demostración. Consideremos un ciclo maximal c = ( x k ) k = 1 m con una imputación inicial x1 con x 3 1 > x 1 1 > x 2 1 = 0 . Relacionado al ciclo c hay un esquema de trasferencia maximal que incluye a las imputaciones de c consideradas de manera cíclica. Usando el teorema 2 b) obtenemos que lim k x i + n k = x ~ i para todo i =1, 2, 3, y puesto que las imputaciones xi+n · k , k ≥ 1 provienen de un conjunto finito, concluimos que xi+n · k = x ~ i para todo k ≥ k ~ , i = 1, 2, 3 para un k ~ suficientemente grande. A partir de esta observación se infiere que la secuencia de imputaciones en c =(x1, x2, ... , xm ) debe coincidir con la sucesión ( x ~ 1 , x ~ 2 , x ~ 3 ) o con una repetición cíclica de ella.

Si el ciclo maximal c tiene una imputación inicial x1 que satisface x 1 1 > x 3 1 > x 2 1 = 0 , entonces, con una técnica similar, se muestra que c = c - coincide con una repetición cíclica de c - .

Para completar la demostración tenemos en cuenta las siguientes observaciones: i) para cualquier imputación x1, el máximo exceso se alcanza en alguna de las coaliciones S1, S2 y S3; ii) y = x1 + e(Si , x1) · β S i es siempre una imputación que tiene e(Si , y ) = 0 y por tanto, yi-1= ( i -1 mod(3)); iii) si y = x1 + e(Si , x1) · β S i y x1 satisface x 3 1 = x 1 1 > x 2 1 = 0 entonces y1 > y2 > y3 =0 si i=1 o y3 > y2 >y1 =0 si i=2.

En la Gráfica 2 se ilustran los dos ciclos c ~ y c - .

Nota 6. Las afirmaciones i), ii) y iii) implican que las condiciones supuestas en la imputación inicial x1 de un ciclo maximal no representan restricción alguna.

Nota 7. Considerar que x 2 1 = 0 no es una limitación porque si ese no fuese el caso o x2 o x3 se ponen en esta condición.

Corolario 6. En un juego (N, v) con función característica dada por (7) y (8) con μ = 1 , P f = X ( c ~ ) X ( c - ) , en que Pf es la d-solución dinámica en (A, dom).

Demostración. Inmediata a partir de las proposiciones 8 y 11. ▪

Teorema 3. En un juego (N, v) con función característica dada por (7) y (8) con μ =1, P = Pf , en que ambas son soluciones consideradas en (A, dom).

Demostración. Siempre es válido que PfP. Para ver la inclusión opuesta, consideremos una d-solución dinámica elemental D con tres o más elementos, x, y , z. Por el lema 2 existe un ciclo maximal c = ( x k ) k = 1 m tal que x = xi y y = xj para un par de índices1 ≤ ijm. Pero por la proposición 11, c puede ser elegido como c ~ o como c - .. Hay también otro ciclo maximal que conecta y con z que, con el mismo argumento, puede ser tomado como c ~ o como c - . Pero como el ciclo que vincula x con y y el que vincula y con z tienen a y como punto común, deben coincidir. Esto muestra que {x, y , z} ⊆ X ( c ~ ) o {x, y , z} ⊆ X ( c - ) pero no en ambos. Como este argumento es válido para una selección arbitraria de tres imputaciones concluimos que D = X(c) probando que D es finita. Así, PPf

Conclusiones

El estudio realizado para los juegos de tres personas parece limitado en tanto se ha considerado un juego muy particular, esto es, el juego simple con v(N ) = v(S1) = v(S2) = v(S3) =1 y v(S) = 0 para toda otra coalición. Sin embargo esto tampoco hace perder generalidad a las conclusiones puesto que puede mostrarse que los ciclos maximales de cualquier juego monótono no equilibrado de tres jugadores están en una relación 1 a 1 con los del juego simple estudiado en la sección anterior. La manera de vincularlos implica una traslación y una homotecia adecuadamente elegidas (Cesco y Aguirre, 2002).

Destacamos también que los resultados expuestos en la sección IV pueden extenderse a los juegos monótonos no equilibrados con n jugadores que tienen función característica dada por (5) y (6). La metodología es similar a la aquí expuesta, aunque la demostración de un teorema de convergencia similar a la proposición 11 requiere el uso de argumentos más complejos que los trigonométricos empleados en su prueba (Cesco y Calí, 2004b).

Finalizamos comentando que la solución dinámica introducida en este artículo tiende, básicamente, a encontrar otro concepto del Core para juegos no equilibrados. El elemento básico para su desarrollo es la noción de exceso maximal. Salvo en casos muy simétricos no hemos hallado relaciones directas con otros conceptos de solución de la teoría de juegos con utilidades transferibles, aunque un estudio comparativo está pendiente. No obstante ello es interesante destacar que cada uno los puntos de cada ciclo está en un ε-core con ε igual a su exceso maximal y, por ende, cada ciclo maximal proporciona una cota para el menor ( que genera un ε-core no vacío (least ε-core), aunque no sabemos todavía que tan ajustadas pueden ser estas cotas. Es también posible determinar, en función de los puntos en los ciclos maximales, regiones en las que se ubica el nucleolo. Determinar que tan precisamente acotan la región de búsqueda del nucleolo es también un problema abierto de cierto interés en virtud de ciertos algoritmos recientes para el cálculo del nucleolo cuyo desempeño numérico depende de una buena selección de un punto inicial.

Referencias bibliográficas
  • Barberà, S., y A. Gerber (2003), “On Coalition Formation: Durable Coalition Structures”, Math. Soc. Sci. 45, pp. 185-203.
  • Bondareva, O. N. (1963), “Some Applications of Linear Programming Methods to the Theory of Cooperative Games [in Russian]”, Problemy Kibernetiki 10, páginas 119-139.
  • Cesco, J. C. (1998), “A Convergent Transfer Scheme to the Core of a TU-Game”, Rev. Mat. Aplicada 19, 23-35.
  • ______, N. Aguirre (2002), “About U-Cycles in TU-Games”, Annals of 31 JAIIO, Simposium in Operation Research, Argentina, pp. 1-12.
  • ______ (2003), “Fundamental Cycles of Pre-imputations in Non-Balanced TU-games”, Int. J. Game Theory 32, pp. 211-222.
  • ______ (2005), “A general Characterization for Non-Balanced Games in Terms of U-Cycles”, Working Paper, IMASL, San Luis, Argentina.
  • ______ (2006), “The M-core”, Working Paper, IMASL, San Luis, Argentina.
  • ______, A. L., Calí (2004a), “U-Cycles in n-Person TU-Games with Only 1, n-1 and n-Person Permissible Coalitions”, Int. Game Theory Rev.
  • ______, y ______ (2004b), “Maximal U-Cycles and Dynamic Solutions in n-Person TU-Games”, Working Paper, IMASL, San Luis, Argentina.
  • Chew, M. S. Y. (1994), “Farsighted Coalitional Stability”, J. Econ. Theory 63, páginas 299- 325.
  • Kalai, E., E. A. Pazner y D. Schmeidler (1976), “Collective Choice Correspondences as Admissible Outcomes of Social Bargaining Processes”, Econometrica 44, pp. 223-240.
  • Konishi, H., y D. Ray (2003), “Coalition Formation as a Dynamic Process”, J. Econ. Theory 110, pp. 1-41.
  • Owen, G. (1995), Game Theory, Academic Press.
  • Sengupta, A., y K. Sengupta (1994), “Viable Proposals”, Int. Econ. Rev. 35, páginas 345-359.
  • Shapley, L. (1967), “On Balanced Sets and Cores”, Nav. Res. Log. Quart, 14, páginas 453-460.
  • Shenoy, P. P. (1979), “On Coalition Formation: A Game Theoretical Approach”, Int. J. Game Theory 8, pp. 133-164.
  • ______ (1980), “A Dynamic Solution for Abstract Games”, J. Opt. Theory Appl. 32, pp. 151-169.
  • Von Neumann, J., y O. Morgenstern (1944), Theory of Games and Economic Behavior, Princeton University Press.
  • Xue, L. (1998), “Coalitional Stability under Perfect Foresight”, Econ. Theory 11, pp. 603-627.
Historial:
  • » Publición impresa: 01/2008

Enlaces refback

  • No hay ningún enlace refback.


Revista El Trimestre Económico, volumen LXXXVI (2), número 342, abril-junio de 2019. Es una publicación trimestral que aparece en enero, abril, julio y octubre, editada por el Fondo de Cultura Económica, con domicilio en  Carretera Picacho Ajusco número 227, Col. Bosques del Pedregal, Delegación Tlalpan, C.P.  14738, Ciudad de México, teléfono (55) 5227 4672, ext. 1850, http://www.eltrimestreeconomico.com.mx/. Reserva de derechos al uso exclusivo  Número 04-2016-052612421000-203, ISSN 2448-718X. Ambos otorgados por el Instituto del Derecho de Autor.  Responsable de la última actualización de este número: Nuria Pliego Vinageras, Secretaria Técnica, Fecha de la última actualización:  28 de enero de 2019. La responsabilidad por lo expresado en los artículos, notas y reseñas es  estrictamente de sus autores; en consecuencia El Trimestre Económico, el Fondo de Cultura Económica y las instituciones a las que estén asociados los autores son ajenos a ella. Todos los derechos reservados. Se autoriza la reproducción total o parcial de los artículos  aquí presentados, siempre y cuando no se mutile y se incluya en todos los casos, junto con la ficha completa, el nombre del autor al que se cite y la  dirección electrónica de la revista; de otra forma, requerirá la autorización por escrito de El Trimestre Económico.