Teoría de juegos cooperativos - Cooperative game theory

En la teoría de juegos , un juego cooperativo (o juego de coalición ) es un juego con competencia entre grupos de jugadores ("coaliciones") debido a la posibilidad de aplicación externa del comportamiento cooperativo (por ejemplo, a través del derecho contractual ). Aquellos se oponen a los juegos no cooperativos en los que no hay posibilidad de forjar alianzas o todos los acuerdos deben ser autoaplicables (por ejemplo, a través de amenazas creíbles ).

Los juegos cooperativos a menudo se analizan a través del marco de la teoría de juegos cooperativos, que se centra en predecir qué coaliciones se formarán, las acciones conjuntas que emprenden los grupos y los beneficios colectivos resultantes. Se opone a la teoría tradicional de juegos no cooperativos, que se centra en predecir las acciones y beneficios de los jugadores individuales y analizar los equilibrios de Nash .

La teoría de los juegos cooperativos proporciona un enfoque de alto nivel, ya que solo describe la estructura, las estrategias y los beneficios de las coaliciones, mientras que la teoría de los juegos no cooperativos también analiza cómo los procedimientos de negociación afectarán la distribución de los beneficios dentro de cada coalición. Como la teoría de juegos no cooperativos es más general, los juegos cooperativos pueden analizarse a través del enfoque de la teoría de juegos no cooperativos (lo contrario no es válido) siempre que se hagan suposiciones suficientes para abarcar todas las estrategias posibles disponibles para los jugadores debido a la posibilidad de aplicación externa de la cooperación. Si bien sería posible expresar todos los juegos en un marco no cooperativo, en muchos casos se dispone de información insuficiente para modelar con precisión los procedimientos formales disponibles para los jugadores durante el proceso de negociación estratégica, o el modelo resultante sería demasiado alto. complejidad para ofrecer una herramienta práctica en el mundo real. En tales casos, la teoría de juegos cooperativos proporciona un enfoque simplificado que permite el análisis del juego en general sin tener que hacer ninguna suposición sobre los poderes de negociación.

Definición matemática

Un juego cooperativo se da especificando un valor para cada coalición. Formalmente, el juego de coaliciones consiste en un conjunto finito de jugadores , llamado gran coalición , y una función característica desde el conjunto de todas las posibles coaliciones de jugadores hasta un conjunto de pagos que satisface . La función describe cuánto beneficio colectivo puede obtener un conjunto de jugadores al formar una coalición, y el juego a veces se denomina juego de valor o juego de ganancias . ${\ Displaystyle N}$ ${\ Displaystyle v: 2 ^ {N} \ to \ mathbb {R}}$${\ Displaystyle v (\ emptyset) = 0}$

A la inversa, un juego cooperativo también se puede definir con una función de coste característica satisfactoria . En este entorno, los jugadores deben realizar alguna tarea, y la función característica representa el costo de un conjunto de jugadores que realizan la tarea juntos. Un juego de este tipo se conoce como juego de costo . Aunque la mayoría de la teoría de juegos cooperativos se ocupa de los juegos con fines de lucro, todos los conceptos se pueden traducir fácilmente a la configuración de costos. ${\ Displaystyle c: 2 ^ {N} \ to \ mathbb {R}}$${\ Displaystyle c (\ conjunto vacío) = 0}$${\ Displaystyle c}$

Dividendo de Harsanyi

El dividendo de Harsanyi (llamado así por John Harsanyi , quien lo usó para generalizar el valor de Shapley en 1963) identifica el excedente creado por una coalición de jugadores en un juego cooperativo. Para concretar este superávit, el valor de esta coalición se corrige con el superávit ya creado por las subcoaliciones. Con este fin, el dividendo de la coalición en juego se determina recursivamente por ${\ Displaystyle d_ {v} (S)}$${\ Displaystyle S}$${\ Displaystyle v}$

${\ Displaystyle {\ begin {alineado} d_ {v} (\ {i \}) & = v (\ {i \}) \\ d_ {v} (\ {i, j \}) & = v (\ {i, j \}) - d_ {v} (\ {i \}) - d_ {v} (\ {j \}) \\ d_ {v} (\ {i, j, k \}) & = v (\ {i, j, k \}) - d_ {v} (\ {i, j \}) - d_ {v} (\ {i, k \}) - d_ {x} (\ {j, k \}) - d_ {v} (\ {i \}) - d_ {v} (\ {j \}) - d_ {v} (\ {k \}) \\ & \ vdots \\ d_ {v } (S) & = v (S) - \ sum _ {T \ subsetneq S} d_ {v} (T) \ end {alineado}}}$

Una fórmula explícita para el dividendo viene dada por . La función también se conoce como la inversa de Möbius . De hecho, podemos recuperar a partir de la ayuda de la fórmula . ${\ textstyle d_ {v} (S) = \ sum _ {T \ subseteq S} (- 1) ^ {| S \ setminus T |} v (T)}$${\ Displaystyle d_ {v}: 2 ^ {N} \ to \ mathbb {R}}$${\ Displaystyle v: 2 ^ {N} \ to \ mathbb {R}}$${\ Displaystyle v}$${\ Displaystyle d_ {v}}$${\ estilo de texto v (S) = d_ {v} (S) + \ sum _ {T \ subsetneq S} d_ {v} (T)}$

Los dividendos de Harsanyi son útiles para analizar tanto los juegos como los conceptos de solución, por ejemplo, el valor de Shapley se obtiene distribuyendo el dividendo de cada coalición entre sus miembros, es decir, el valor de Shapley del jugador en el juego se obtiene sumando la participación de un jugador en los dividendos de todas las coaliciones que los que pertenece, . ${\ Displaystyle \ phi _ {i} (v)}$${\ Displaystyle i}$${\ Displaystyle v}$${\ textstyle \ phi _ {i} (v) = \ sum _ {S \ subconjunto N: i \ in S} {d_ {v} (S)} / {| S |}}$

Dualidad

Sea un juego de ganancias. El juego dual de es el juego de costos definido como ${\ Displaystyle v}$${\ Displaystyle v}$${\ Displaystyle v ^ {*}}$

${\ Displaystyle v ^ {*} (S) = v (N) -v (N \ setminus S), \ forall ~ S \ subseteq N.}$

Intuitivamente, el juego dual representa el costo de oportunidad para una coalición de no unirse a la gran coalición . Un juego de doble beneficio se puede definir de forma idéntica para un juego de coste . Un juego cooperativo y su dual son en cierto sentido equivalentes y comparten muchas propiedades. Por ejemplo, el núcleo de un juego y su dual son iguales. Para más detalles sobre la dualidad del juego cooperativo, ver, por ejemplo ( Bilbao 2000 ). ${\ Displaystyle S}$${\ Displaystyle N}$${\ Displaystyle c ^ {*}}$${\ Displaystyle c}$

Subjuegos

Sea una coalición de jugadores no vacía. El subjuego encendido se define naturalmente como ${\ Displaystyle S \ subsetneq N}$ ${\ Displaystyle v_ {S}: 2 ^ {S} \ to \ mathbb {R}}$${\ Displaystyle S}$

${\ Displaystyle v_ {S} (T) = v (T), \ forall ~ T \ subseteq S.}$

En otras palabras, simplemente restringimos nuestra atención a las coaliciones contenidas en . Los subjuegos son útiles porque nos permiten aplicar conceptos de solución definidos para la gran coalición en coaliciones más pequeñas. ${\ Displaystyle S}$

Propiedades para caracterización

Superaditividad

A menudo se asume que las funciones características son superaditivas ( Owen 1995 , p. 213). Esto significa que el valor de una unión de coaliciones disjuntas no es menor que la suma de los valores separados de las coaliciones:

${\ Displaystyle v (S \ cup T) \ geq v (S) + v (T)}$ siempre que satisfaga . ${\ Displaystyle S, T \ subseteq N}$${\ Displaystyle S \ cap T = \ emptyset}$

Monotonicidad

Las coaliciones más grandes ganan más:

${\ Displaystyle S \ subseteq T \ Rightarrow v (S) \ leq v (T)}$ .

Esto se deriva de la superaditividad . es decir, si los pagos se normalizan de modo que las coaliciones únicas tengan valor cero.

Propiedades para juegos simples

Un juego de coalición v se considera simple si los pagos son 1 o 0, es decir, las coaliciones están "ganando" o "perdiendo".

De manera equivalente, un juego simple se puede definir como una colección W de coaliciones, donde los miembros de W se denominan coaliciones ganadoras y los demás coaliciones perdedoras . A veces se asume que un juego simple no está vacío o que no contiene un conjunto vacío. Sin embargo, en otras áreas de las matemáticas, los juegos simples también se denominan hipergráficos o funciones booleanas (funciones lógicas).

• Un juego simple W es monótono si cualquier coalición que contenga una coalición ganadora también está ganando, es decir, si e implica . ${\ Displaystyle S \ in W}$${\ Displaystyle S \ subseteq T}$${\ Displaystyle T \ in W}$
• Un juego simple W es apropiado si el complemento (oposición) de cualquier coalición ganadora está perdiendo, es decir, si implica . ${\ Displaystyle S \ in W}$${\ Displaystyle N \ setminus S \ notin W}$
• Un juego simple W es fuerte si gana el complemento de cualquier coalición perdedora, es decir, si implica . ${\ Displaystyle S \ notin W}$${\ Displaystyle N \ setminus S \ in W}$
  • Si un juego simple W es apropiado y fuerte, entonces una coalición está ganando si y solo si su complemento está perdiendo, es decir, si f . (Si v es un juego simple de coalición que es adecuado y fuerte, para cualquier S ). ${\ Displaystyle S \ in W}$${\ Displaystyle N \ setminus S \ notin W}$${\ Displaystyle v (S) = 1-v (N \ setminus S)}$
• Un jugador con veto (vetoer) en un juego simple es un jugador que pertenece a todas las coaliciones ganadoras. Suponiendo que haya un jugador con veto, cualquier coalición que no contenga un jugador con veto está perdiendo. Un juego simple W es débil ( colegiado ) si tiene un jugador con veto, es decir, si la intersección de todas las coaliciones ganadoras no está vacía. ${\ Displaystyle \ bigcap W: = \ bigcap _ {S \ in W} S}$
  • Un dictador en un juego simple es un jugador con veto de modo que cualquier coalición que contenga a este jugador está ganando. El dictador no pertenece a ninguna coalición perdedora. (Los juegos de dictador en la economía experimental no están relacionados con esto).
• Un portador de un juego simple W es un conjunto tal que para cualquier coalición S , tenemos iff . Cuando un juego simple tiene un portador, se ignora a cualquier jugador que no pertenezca a él. Un juego simple a veces se llama finito si tiene un portador finito (incluso si N es infinito). ${\ Displaystyle T \ subseteq N}$${\ Displaystyle S \ in W}$${\ Displaystyle S \ cap T \ in W}$
• El número de Nakamura de un juego simple es el número mínimo de coaliciones ganadoras con intersección vacía. Según el teorema de Nakamura, el número mide el grado de racionalidad; es un indicador de hasta qué punto una regla de agregación puede producir opciones bien definidas.

Algunas relaciones entre los axiomas anteriores han sido ampliamente reconocidas, como las siguientes (por ejemplo, Peleg, 2002, Sección 2.1):

• Si un juego simple es débil, es apropiado.
• Un juego simple es dictatorial si y solo si es fuerte y débil.

De manera más general, se ha realizado una investigación completa de la relación entre los cuatro axiomas convencionales (monotonicidad, propiedad, fortaleza y no debilidad), finitud y computabilidad algorítmica (Kumabe y Mihara, 2011), cuyos resultados se resumen en la Tabla "Existencia de juegos simples" a continuación.

Las restricciones que varios axiomas para juegos simples imponen sobre su número de Nakamura también se estudiaron extensamente. En particular, un juego simple computable sin un jugador con veto tiene un número de Nakamura mayor que 3 solo si es un juego adecuado y no fuerte .

Relación con la teoría no cooperativa

Sea G un juego estratégico (no cooperativo). Entonces, en el supuesto de que las coaliciones tienen la capacidad de hacer cumplir el comportamiento coordinado, hay varios juegos cooperativos asociados con G . Estos juegos se refieren a menudo como representaciones de G . Las dos representaciones estándar son:

• El juego α-efectivo asocia con cada coalición la suma de ganancias que sus miembros pueden "garantizar" uniendo fuerzas. Por "garantizar", se entiende que el valor es el máximo-mínimo, por ejemplo, el valor máximo del mínimo asumido por las estrategias de la oposición.
• El juego β-efectivo asocia con cada coalición la suma de ganancias que sus miembros pueden "garantizar estratégicamente" uniendo fuerzas. Por "garantizar estratégicamente", se entiende que el valor es el mínimo-máximo, por ejemplo, el valor mínimo del máximo asumido por las estrategias de la oposición.

Conceptos de solución

El supuesto principal en la teoría de juegos cooperativos es que se formará la gran coalición . El desafío es entonces distribuir la recompensa entre los jugadores de una manera justa. (Esta suposición no es restrictiva, porque incluso si los jugadores se separan y forman coaliciones más pequeñas, podemos aplicar conceptos de solución a los subjuegos definidos por las coaliciones que se formen realmente). Un concepto de solución es un vector (o un conjunto de vectores) que representa la asignación a cada jugador. Los investigadores han propuesto diferentes conceptos de solución basados ​​en diferentes nociones de equidad. Algunas propiedades para buscar en un concepto de solución incluyen: ${\ Displaystyle N}$${\ Displaystyle v (N)}$${\ Displaystyle x \ in \ mathbb {R} ^ {N}}$

• Eficiencia: El vector de pagos divide exactamente el valor total: . ${\ Displaystyle \ sum _ {i \ in N} x_ {i} = v (N)}$
• La racionalidad individual: Ningún jugador recibe menos de lo que él podría conseguir por su cuenta: . ${\ Displaystyle x_ {i} \ geq v (\ {i \}), \ forall ~ i \ in N}$
• Existencia: El concepto de solución existe para cualquier juego . ${\ Displaystyle v}$
• Singularidad: el concepto de solución es único para cualquier juego . ${\ Displaystyle v}$
• Marginalidad: La recompensa de un jugador depende solo de la contribución marginal de este jugador, es decir, si estas contribuciones marginales son las mismas en dos juegos diferentes, entonces la recompensa es la misma: implica que es la misma en y en . ${\ Displaystyle v (S \ cup \ {i \}) = w (S \ cup \ {i \}), \ forall ~ S \ subseteq N \ setminus \ {i \}}$${\ Displaystyle x_ {i}}$${\ Displaystyle v}$${\ Displaystyle w}$
• Monotonicidad: La recompensa de un jugador aumenta si la contribución marginal de este jugador aumenta: implica que es débilmente mayor en in que en . ${\ Displaystyle v (S \ cup \ {i \}) \ leq w (S \ cup \ {i \}), \ forall ~ S \ subseteq N \ setminus \ {i \}}$${\ Displaystyle x_ {i}}$${\ Displaystyle w}$${\ Displaystyle v}$
• Facilidad de cálculo: el concepto de solución se puede calcular de manera eficiente (es decir, en tiempo polinomial con respecto al número de jugadores ). ${\ Displaystyle | N |}$
• Simetría: La solución concepto asigna pagos iguales a los jugadores simétricos , . Dos jugadores , son simétricos si ; es decir, podemos intercambiar un jugador por otro en cualquier coalición que contenga solo uno de los jugadores y no cambiar la recompensa. ${\ Displaystyle x}$${\ Displaystyle x_ {i} = x_ {j}}$${\ Displaystyle i}$${\ Displaystyle j}$${\ Displaystyle i}$${\ Displaystyle j}$${\ Displaystyle v (S \ cup \ {i \}) = v (S \ cup \ {j \}), \ forall ~ S \ subseteq N \ setminus \ {i, j \}}$
• Aditividad: la asignación a un jugador en una suma de dos juegos es la suma de las asignaciones al jugador en cada juego individual. Matemáticamente, si y son juegos, el juego simplemente asigna a cualquier coalición la suma de los beneficios que obtendría la coalición en los dos juegos individuales. Un concepto de solución aditiva asigna a cada jugador la suma de lo que recibiría en y . ${\ Displaystyle v}$${\ Displaystyle \ omega}$${\ Displaystyle (v + \ omega)}$${\ Displaystyle (v + \ omega)}$${\ Displaystyle v}$${\ Displaystyle \ omega}$
• Asignación cero a jugadores nulos: la asignación a un jugador nulo es cero. Un jugador nulo satisface . En términos económicos, el valor marginal de un jugador nulo para cualquier coalición que no lo contenga es cero. ${\ Displaystyle i}$${\ Displaystyle v (S \ cup \ {i \}) = v (S), \ forall ~ S \ subseteq N \ setminus \ {i \}}$

Un vector de pago eficiente se denomina preimputación , y una preimputación racional individualmente se denomina imputación . La mayoría de los conceptos de solución son imputaciones.

El conjunto estable

El conjunto estable de un juego (también conocido como la solución von Neumann-Morgenstern ( von Neumann & Morgenstern 1944 )) fue la primera solución propuesta para juegos con más de 2 jugadores. Sea un juego y dejemos , sean dos imputaciones de . Entonces domina si alguna coalición satisface y . En otras palabras, los jugadores prefieren las recompensas de a las de , y pueden amenazar con abandonar la gran coalición si se utiliza porque la recompensa que obtienen por sí mismos es al menos tan grande como la asignación que reciben . ${\ Displaystyle v}$${\ Displaystyle x}$${\ Displaystyle y}$${\ Displaystyle v}$${\ Displaystyle x}$ ${\ Displaystyle y}$${\ Displaystyle S \ neq \ emptyset}$${\ Displaystyle x_ {i}> y_ {i}, \ forall ~ i \ in S}$${\ Displaystyle \ sum _ {i \ in S} x_ {i} \ leq v (S)}$${\ Displaystyle S}$${\ Displaystyle x}$${\ Displaystyle y}$${\ Displaystyle y}$${\ Displaystyle x}$

Un conjunto estable es un conjunto de imputaciones que satisface dos propiedades:

• Estabilidad interna: ningún vector de pago en el conjunto estable está dominado por otro vector en el conjunto.
• Estabilidad externa: todos los vectores de pago fuera del conjunto están dominados por al menos un vector en el conjunto.

Von Neumann y Morgenstern vieron el conjunto estable como la colección de comportamientos aceptables en una sociedad: ninguno es claramente preferido a otro, pero para cada comportamiento inaceptable hay una alternativa preferida. La definición es muy general, lo que permite utilizar el concepto en una amplia variedad de formatos de juego.

Propiedades

• Un conjunto estable puede existir o no ( Lucas 1969 ), y si existe, típicamente no es único ( Lucas 1992 ). Los conjuntos estables suelen ser difíciles de encontrar. Esta y otras dificultades han llevado al desarrollo de muchos otros conceptos de solución.
• Una fracción positiva de los juegos cooperativos tiene conjuntos estables únicos que consisten en el núcleo ( Owen 1995 , p. 240).
• Una fracción positiva de los juegos cooperativos tiene conjuntos estables que discriminan a los jugadores. En tales conjuntos se excluye al menos a los jugadores discriminados ( Owen 1995 , p. 240). ${\ Displaystyle n-2}$${\ Displaystyle n-3}$

El núcleo

Sea un juego. El núcleo de es el conjunto de vectores de pago. ${\ Displaystyle v}$${\ Displaystyle v}$

${\ Displaystyle C (v) = \ left \ {x \ in \ mathbb {R} ^ {N}: \ sum _ {i \ in N} x_ {i} = v (N); \ quad \ sum _ { i \ en S} x_ {i} \ geq v (S), \ forall ~ S \ subseteq N \ right \}.}$

En palabras, el núcleo es el conjunto de imputaciones bajo las cuales ninguna coalición tiene un valor mayor que la suma de los pagos de sus miembros. Por lo tanto, ninguna coalición tiene incentivos para dejar la gran coalición y recibir una recompensa mayor.

Propiedades

• El núcleo de un juego puede estar vacío (ver el teorema de Bondareva-Shapley ). Los juegos con núcleos no vacíos se denominan equilibrados .
• Si no está vacío, el núcleo no contiene necesariamente un vector único.
• El núcleo está contenido en cualquier conjunto estable, y si el núcleo es estable, es el conjunto estable único; ver ( Driessen 1988 ) para una prueba.

El núcleo de un juego simple con respecto a las preferencias

Para los juegos simples, existe otra noción del núcleo, cuando se supone que cada jugador tiene preferencias sobre un conjunto de alternativas. Un perfil es una lista de preferencias individuales en . Aquí significa que el individuo prefiere una alternativa a un perfil . Dado un juego simple y un perfil , una relación de dominio se define por si y solo si hay una coalición ganadora (es decir, ) satisfactoria para todos . El núcleo del juego simple con respecto al perfil de preferencias es el conjunto de alternativas no dominadas por (el conjunto de elementos máximos de con respecto a ): ${\ Displaystyle X}$${\ Displaystyle p = (\ succ _ {i} ^ {p}) _ {i \ in N}}$${\ Displaystyle \ succ _ {i} ^ {p}}$${\ Displaystyle X}$${\ Displaystyle x \ succ _ {i} ^ {p} y}$${\ Displaystyle i}$${\ Displaystyle x}$${\ Displaystyle y}$${\ Displaystyle p}$${\ Displaystyle v}$${\ Displaystyle p}$${\ Displaystyle \ succ _ {v} ^ {p}}$${\ Displaystyle X}$${\ Displaystyle x \ succ _ {v} ^ {p} y}$${\ Displaystyle S}$${\ Displaystyle v (S) = 1}$${\ Displaystyle x \ succ _ {i} ^ {p} y}$${\ Displaystyle i \ in S}$ ${\ Displaystyle C (v, p)}$${\ Displaystyle v}$${\ Displaystyle p}$${\ Displaystyle \ succ _ {v} ^ {p}}$${\ Displaystyle X}$${\ Displaystyle \ succ _ {v} ^ {p}}$

${\ Displaystyle x \ en C (v, p)}$ si y solo si no existe tal que . ${\ Displaystyle y \ en X}$${\ Displaystyle y \ succ _ {v} ^ {p} x}$

El número de Nakamura de un juego simple es el número mínimo de coaliciones ganadoras con intersección vacía. El teorema de Nakamura establece que el núcleo no está vacío para todos los perfiles de preferencias acíclicas (alternativamente, transitivas ) si y solo si es finito y el número cardinal (el número de elementos) de es menor que el número de Nakamura de . Una variante de Kumabe y Mihara establece que el núcleo no está vacío para todos los perfiles de preferencias que tienen un elemento máximo si y solo si el número cardinal de es menor que el número de Nakamura de . (Consulte el número de Nakamura para obtener más detalles). ${\ Displaystyle C (v, p)}$${\ Displaystyle p}$${\ Displaystyle X}$${\ Displaystyle X}$${\ Displaystyle v}$${\ Displaystyle C (v, p)}$${\ Displaystyle p}$${\ Displaystyle X}$${\ Displaystyle v}$

El fuerte núcleo épsilon

Debido a que el núcleo puede estar vacío, se introdujo una generalización en ( Shapley y Shubik 1966 ). El núcleo fuerte ${\ Displaystyle \ varepsilon}$ de algún número es el conjunto de vectores de pago ${\ Displaystyle \ varepsilon \ in \ mathbb {R}}$

${\ Displaystyle C _ {\ varepsilon} (v) = \ left \ {x \ in \ mathbb {R} ^ {N}: \ sum _ {i \ in N} x_ {i} = v (N); \ quad \ sum _ {i \ in S} x_ {i} \ geq v (S) - \ varepsilon, \ forall ~ S \ subseteq N \ right \}.}$

En términos económicos, el núcleo fuerte es el conjunto de imputaciones previas en las que ninguna coalición puede mejorar su rentabilidad abandonando la gran coalición, si debe pagar una penalización por marcharse. Tenga en cuenta que puede ser negativo, en cuyo caso representa una bonificación por dejar la gran coalición. Claramente, independientemente de si el núcleo está vacío, el núcleo fuerte no estará vacío para un valor suficientemente grande de y vacío para un valor suficientemente pequeño (posiblemente negativo) de . Siguiendo esta línea de razonamiento, el núcleo mínimo , introducido en ( Maschler, Peleg y Shapley 1979 ), es la intersección de todos los núcleos fuertes no vacíos . También se puede ver como el núcleo fuerte para el valor más pequeño de que hace que el conjunto no esté vacío ( Bilbao 2000 ). ${\ Displaystyle \ varepsilon}$${\ Displaystyle \ varepsilon}$${\ Displaystyle \ varepsilon}$${\ Displaystyle \ varepsilon}$${\ Displaystyle \ varepsilon}$${\ Displaystyle \ varepsilon}$${\ Displaystyle \ varepsilon}$${\ Displaystyle \ varepsilon}$${\ Displaystyle \ varepsilon}$

El valor de Shapley

El valor de Shapley es el vector de pago único que es eficiente, simétrico y satisface la monotonicidad. Fue introducido por Lloyd Shapley ( Shapley 1953 ) quien demostró que es el vector de pago único que es eficiente, simétrico, aditivo y asigna cero pagos a los jugadores ficticios. El valor de Shapley de un juego superaditivo es individualmente racional, pero esto no es cierto en general. ( Driessen 1988 )

El kernel

Sea un juego y sea ​​un vector de pago eficiente. El excedente máximo del jugador i sobre el jugador j con respecto ax es ${\ Displaystyle v: 2 ^ {N} \ to \ mathbb {R}}$${\ Displaystyle x \ in \ mathbb {R} ^ {N}}$

${\ Displaystyle s_ {ij} ^ {v} (x) = \ max \ left \ {v (S) - \ sum _ {k \ in S} x_ {k}: S \ subseteq N \ setminus \ {j \ }, i \ in S \ right \},}$

la cantidad máxima que el jugador i puede ganar sin la cooperación del jugador j retirándose de la gran coalición N bajo el vector de pago x , asumiendo que los otros jugadores en la coalición que se retira de i están satisfechos con sus beneficios bajo x . El excedente máximo es una forma de medir el poder de negociación de un jugador sobre otro. El núcleo de es el conjunto de imputaciones x que satisfacen ${\ Displaystyle v}$

• ${\ Displaystyle (s_ {ij} ^ {v} (x) -s_ {ji} ^ {v} (x)) \ times (x_ {j} -v (j)) \ leq 0}$ , y
• ${\ Displaystyle (s_ {ji} ^ {v} (x) -s_ {ij} ^ {v} (x)) \ times (x_ {i} -v (i)) \ leq 0}$

para cada pareja de jugadores i y j . Intuitivamente, el jugador i tiene más poder de negociación que el jugador j con respecto a la imputación x si , pero el jugador j es inmune a las amenazas del jugador i si , porque puede obtener esta recompensa por sí mismo. El núcleo contiene todas las imputaciones en las que ningún jugador tiene este poder de negociación sobre otro. Este concepto de solución se introdujo por primera vez en ( Davis & Maschler 1965 ). ${\ Displaystyle s_ {ij} ^ {v} (x)> s_ {ji} ^ {v} (x)}$${\ Displaystyle x_ {j} = v (j)}$

El nucléolo

Sea un juego y sea ​​un vector de pago. El exceso de para una coalición es la cantidad ; es decir, la ganancia que los jugadores de la coalición pueden obtener si se retiran de la gran coalición con una recompensa y en su lugar toman la recompensa . ${\ Displaystyle v: 2 ^ {N} \ to \ mathbb {R}}$${\ Displaystyle x \ in \ mathbb {R} ^ {N}}$${\ Displaystyle x}$${\ Displaystyle S \ subseteq N}$${\ Displaystyle v (S) - \ sum _ {i \ in S} x_ {i}}$${\ Displaystyle S}$${\ Displaystyle N}$${\ Displaystyle x}$${\ Displaystyle v (S)}$

Ahora sea ​​el vector de excesos de , dispuesto en orden no creciente. En otras palabras, . Tenga en cuenta que está en el núcleo de si y solo si es una imputación previa y . Para definir el nucleolo, consideramos el orden lexicográfico de los vectores en : Para dos vectores de pago , decimos que es lexicográficamente más pequeño que si para algún índice tenemos y . (El orden se llama lexicográfico porque imita el orden alfabético utilizado para ordenar las palabras en un diccionario). El nucleolo de es la imputación lexicográficamente mínima , basada en este orden. Este concepto de solución se introdujo por primera vez en ( Schmeidler 1969 ). ${\ Displaystyle \ theta (x) \ in \ mathbb {R} ^ {2 ^ {N}}}$${\ Displaystyle x}$${\ Displaystyle \ theta _ {i} (x) \ geq \ theta _ {j} (x), \ forall ~ i <j}$${\ Displaystyle x}$${\ Displaystyle v}$${\ Displaystyle \ theta _ {1} (x) \ leq 0}$${\ Displaystyle \ mathbb {R} ^ {2 ^ {N}}}$${\ Displaystyle x, y}$${\ Displaystyle \ theta (x)}$${\ Displaystyle \ theta (y)}$${\ Displaystyle k}$${\ Displaystyle \ theta _ {i} (x) = \ theta _ {i} (y), \ forall ~ i <k}$${\ Displaystyle \ theta _ {k} (x) <\ theta _ {k} (y)}$${\ Displaystyle v}$

Aunque la definición de nucleolo parece abstracta, ( Maschler, Peleg & Shapley 1979 ) dio una descripción más intuitiva: comenzando con el núcleo mínimo, registre las coaliciones para las cuales el lado derecho de la desigualdad en la definición de no puede ser más extenso. reducido sin dejar el conjunto vacío. Continúe disminuyendo el lado derecho para las coaliciones restantes, hasta que no se pueda reducir sin dejar el conjunto vacío. Registre el nuevo conjunto de coaliciones para las que las desigualdades se mantienen en igualdad; continúe disminuyendo el lado derecho de las coaliciones restantes y repita este proceso tantas veces como sea necesario hasta que se hayan registrado todas las coaliciones. El vector de pago resultante es el nucleolo. ${\ Displaystyle C _ {\ varepsilon} (v)}$

Propiedades

• Aunque la definición no lo establece explícitamente, el nucléolo es siempre único. (Ver la Sección II.7 de ( Driessen 1988 ) para una prueba).
• Si el núcleo no está vacío, el nucleolo está en el núcleo.
• El nucléolo siempre está en el núcleo, y dado que el núcleo está contenido en el conjunto de negociación, siempre está en el conjunto de negociación (ver ( Driessen 1988 ) para más detalles).

Juegos cooperativos convexos

Introducidos por Shapley en ( Shapley 1971 ), los juegos cooperativos convexos capturan la propiedad intuitiva que algunos juegos tienen de "hacer bolas de nieve". En concreto, un juego es convexo si su función característica es supermodular : ${\ Displaystyle v}$

${\ Displaystyle v (S \ cup T) + v (S \ cap T) \ geq v (S) + v (T), \ forall ~ S, T \ subseteq N.}$

Puede demostrarse (véase, por ejemplo, la Sección V.1 de ( Driessen 1988 )) que la supermodularidad de es equivalente a ${\ Displaystyle v}$

${\ Displaystyle v (S \ cup \ {i \}) - v (S) \ leq v (T \ cup \ {i \}) - v (T), \ forall ~ S \ subseteq T \ subseteq N \ setminus \ {i \}, \ forall ~ i \ in N;}$

es decir, "los incentivos para unirse a una coalición aumentan a medida que la coalición crece" ( Shapley 1971 ), lo que lleva al efecto bola de nieve antes mencionado. Para los juegos de costos, las desigualdades se invierten, por lo que decimos que el juego de costos es convexo si la función característica es submodular .

Propiedades

Los juegos cooperativos convexos tienen muchas propiedades interesantes:

• La supermodularidad implica trivialmente superaditividad .
• Los juegos convexos están totalmente equilibrados : el núcleo de un juego convexo no está vacío y, dado que cualquier subjuego de un juego convexo es convexo, el núcleo de cualquier subjuego tampoco está vacío.
• Un juego convexo tiene un conjunto estable único que coincide con su núcleo .
• El valor de Shapley de un juego convexo es el centro de gravedad de su núcleo .
• Un punto extremo (vértice) del núcleo se puede encontrar en el tiempo polinomio utilizando el algoritmo voraz : Vamos a ser una permutación de los jugadores, y dejar que el conjunto de jugadores ordenó a través de , por cualquier , con . Entonces la recompensa definida por es un vértice del núcleo de . Cualquier vértice del núcleo se puede construir de esta manera eligiendo una permutación apropiada . ${\ Displaystyle \ pi: N \ a N}$${\ Displaystyle S_ {i} = \ {j \ in N: \ pi (j) \ leq i \}}$${\ Displaystyle 1}$${\ Displaystyle i}$${\ Displaystyle \ pi}$${\ Displaystyle i = 0, \ ldots, n}$${\ Displaystyle S_ {0} = \ emptyset}$${\ Displaystyle x \ in \ mathbb {R} ^ {N}}$${\ Displaystyle x_ {i} = v (S _ {\ pi (i)}) - v (S _ {\ pi (i) -1}), \ forall ~ i \ in N}$${\ Displaystyle v}$ ${\ Displaystyle \ pi}$

Similitudes y diferencias con la optimización combinatoria

Las funciones de conjuntos submodulares y supermodulares también se estudian en la optimización combinatoria . Muchos de los resultados en ( Shapley 1971 ) tienen análogos en ( Edmonds 1970 ), donde las funciones submodulares se presentaron por primera vez como generalizaciones de matroides . En este contexto, el núcleo de un juego de costos convexos se denomina poliedro base , porque sus elementos generalizan las propiedades básicas de las matroides .

Sin embargo, la comunidad de optimización generalmente considera que las funciones submodulares son análogos discretos de las funciones convexas ( Lovász 1983 ), porque la minimización de ambos tipos de funciones es computacionalmente manejable. Desafortunadamente, esto entra en conflicto directamente con la definición original de Shapley de funciones supermodulares como "convexas".

Ver también

• Toma de decisiones por consenso
• Juego de coordinacion
• Negociación intrafamiliar
• Juego hedónico
• Juego de producción lineal

Referencias

Otras lecturas

• Bilbao, Jesús Mario (2000), Juegos cooperativos sobre estructuras combinatorias , Kluwer Academic Publishers, ISBN   9781461543930

• Davis, M .; Maschler, M. (1965), "El núcleo de un juego cooperativo", Naval Research Logistics Quarterly , 12 (3): 223–259, doi : 10.1002 / nav.3800120303

• Driessen, Theo (1988), juegos cooperativos, soluciones y aplicaciones , Kluwer Academic Publishers, ISBN   9789401577878

• Edmonds, Jack (1970), "Funciones submodulares, matroides y ciertos poliedros", en Guy, R .; Hanani, H .; Sauer, N .; Schönheim, J. (eds.), Estructuras combinatorias y sus aplicaciones , Nueva York: Gordon y Breach, págs. 69–87

• Lovász, László (1983), "Funciones submodulares y convexidad", en Bachem, A .; Grötschel, M .; Korte, B. (eds.), Programación matemática: el estado del arte , Berlín: Springer, págs. 235–257

• Leyton-Brown, Kevin; Shoham, Yoav (2008), Fundamentos de la teoría de juegos: una introducción concisa y multidisciplinaria , San Rafael, CA: Morgan & Claypool Publishers, ISBN   978-1-59829-593-1 . Una introducción matemática de 88 páginas; consulte el Capítulo 8. Gratis en línea (se requiere suscripción) en muchas universidades.

• Lucas, William F. (1969), "La prueba de que un juego puede no tener solución", Transactions of the American Mathematical Society , 136 : 219-229, doi : 10.2307 / 1994798 , JSTOR   1994798 .

• Lucas, William F. (1992), "Von Neumann-Morgenstern Stable Sets", en Aumann, Robert J .; Hart, Sergiu (eds.), Handbook of Game Theory, Volumen I , Amsterdam: Elsevier , págs. 543–590

• Luce, RD y Raiffa, H. (1957) Juegos y decisiones: Introducción y estudio crítico , Wiley & Sons. (ver Capítulo 8).
• Maschler, M .; Peleg, B .; Shapley, Lloyd S. (1979), "Propiedades geométricas del núcleo, nucleolo y conceptos de solución relacionados", Matemáticas de la investigación de operaciones , 4 (4): 303–338, doi : 10.1287 / moor.4.4.303

• Osborne, MJ y Rubinstein, A. (1994) Un curso de teoría de juegos , MIT Press (véanse los capítulos 13, 14, 15)
• Moulin, Herve (1988), Axiomas de la toma de decisiones cooperativa (1a ed.), Cambridge: Cambridge University Press , ISBN   978-0-521-42458-5

• Owen, Guillermo (1995), Game Theory (3.a ed.), San Diego: Academic Press , ISBN   978-0-12-531151-9

• Schmeidler, D. (1969), "El nucleolo de un juego de funciones característico", SIAM Journal on Applied Mathematics , 17 (6): 1163-1170, doi : 10.1137 / 0117107 .

• Shapley, Lloyd S. (1953), "Un valor para los juegos de personas", en Kuhn, H .; Tucker, AW (eds.), Contribuciones a la teoría de los juegos II , Princeton, Nueva Jersey: Princeton University Press, págs. 307–317 ${\ Displaystyle n}$

• Shapley, Lloyd S. (1971), "Cores of convex games", International Journal of Game Theory , 1 (1): 11-26, doi : 10.1007 / BF01753431 , S2CID   123385556

• Shapley, Lloyd S .; Shubik, M. (1966), "Cuasi-núcleos en una economía monetaria con preferencias no convexas", Econometrica , 34 (4): 805–827, doi : 10.2307 / 1910101 , JSTOR   1910101

• Shoham, Yoav; Leyton-Brown, Kevin (2009), Sistemas multiagente: fundamentos algorítmicos, teóricos de juegos y lógicos , Nueva York: Cambridge University Press , ISBN   978-0-521-89943-7 . Una referencia integral desde una perspectiva computacional; consulte el Capítulo 12. Descarga gratuita en línea .

• von Neumann, John ; Morgenstern, Oskar (1944), "Theory of Games and Economic Behavior" , Nature , Princeton: Princeton University Press , 157 (3981): 172, Bibcode : 1946Natur.157..172R , doi : 10.1038 / 157172a0 , S2CID   29754824

• Yeung, David WK y Leon A. Petrosyan. Juegos diferenciales estocásticos cooperativos (serie Springer en investigación de operaciones e ingeniería financiera), Springer, 2006. Tapa blanda- ISBN   978-1441920942 .
• Yeung, David WK y Leon A. Petrosyan. Optimización económica consistente en subjuegos: un análisis de juego dinámico cooperativo avanzado (teoría de juegos estáticos y dinámicos: fundamentos y aplicaciones), Birkhäuser Boston; 2012. ISBN   978-0817682613

enlaces externos

• "Juego cooperativo" , Enciclopedia de Matemáticas , EMS Press , 2001 [1994]