Teoría de juegos cooperativos

Juego en el que grupos de jugadores pueden imponer un comportamiento cooperativo.

En teoría de juegos , un juego cooperativo (o juego de coalición ) es un juego con grupos de jugadores que forman “coaliciones” vinculantes con una imposición externa del comportamiento cooperativo (por ejemplo, a través de la ley contractual ). Esto es diferente de los juegos no cooperativos en los que no hay posibilidad de forjar alianzas o todos los acuerdos deben ser autoejecutables (por ejemplo, a través de amenazas creíbles ). ^[1]

Los juegos cooperativos se analizan centrándose en las coaliciones que se pueden formar, las acciones conjuntas que pueden realizar los grupos y los resultados colectivos resultantes. ^{[2] [3]}

Definición matemática

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

Definición de teoría de juegos cooperativos

La teoría de juegos cooperativos es una rama de la teoría de juegos que se ocupa del estudio de juegos en los que los jugadores pueden formar coaliciones, cooperar entre sí y llegar a acuerdos vinculantes. La teoría ofrece métodos matemáticos para analizar escenarios en los que dos o más jugadores deben tomar decisiones que afectarán el bienestar de los demás jugadores. ^[5]

Intereses comunes: En los juegos cooperativos, los jugadores comparten un interés común por alcanzar un objetivo o resultado específico. Los jugadores deben identificar y acordar un interés común para establecer la base y el razonamiento para la cooperación. Una vez que los jugadores comprenden claramente su interés compartido, pueden trabajar juntos para lograrlo. ^{[ cita requerida ]}

Intercambio de información necesario: la cooperación requiere comunicación e intercambio de información entre los jugadores. Los jugadores deben compartir información sobre sus preferencias, recursos y limitaciones para identificar oportunidades de beneficio mutuo. Al compartir información, los jugadores pueden comprender mejor los objetivos de los demás y trabajar para alcanzarlos juntos. ^{[ cita requerida ]}

Voluntariedad, igualdad y beneficio mutuo: en los juegos cooperativos, los jugadores se reúnen voluntariamente para formar coaliciones y llegar a acuerdos. Los jugadores deben ser socios iguales en la coalición y cualquier acuerdo debe ser mutuamente beneficioso. La cooperación solo es sostenible si todas las partes sienten que reciben una parte justa de los beneficios. ^{[ cita requerida ]}

Contrato obligatorio: en los juegos cooperativos, los acuerdos entre los jugadores son vinculantes y obligatorios. Una vez que los jugadores han acordado un determinado curso de acción, tienen la obligación de cumplirlo. Los jugadores deben confiar unos en otros para cumplir con sus compromisos, y deben existir mecanismos para hacer cumplir los acuerdos. Al hacer que los acuerdos sean vinculantes y obligatorios, los jugadores pueden asegurarse de que lograrán su objetivo compartido. ^{[ cita requerida ]}

Subjuegos

Sea una coalición no vacía de jugadores. El subjuego en 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 supone 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 }$

Monotonía

Las coaliciones más grandes ganan más:

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

Esto se desprende de la superaditividad , es decir, si los pagos se normalizan, las coaliciones singleton tienen valor cero.

Propiedades para juegos sencillos

Un juego de coalición v se considera simple si los pagos son 1 o 0, es decir, las coaliciones son "ganadoras" o "perdedoras". ^[6]

De manera equivalente, un juego simple puede definirse 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 supone que un juego simple no es 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 hipergrafos 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 y implican . ${\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 es perdedora, es decir, si implica . ${\displaystyle S\in W}$ ${\displaystyle N\setminus S\notin W}$
• Un juego simple W es fuerte si el complemento de cualquier coalición perdedora es ganador, es decir, si implica . ${\displaystyle S\notin W}$ ${\displaystyle N\setminus S\in W}$
  • Si un juego simple W es propio y fuerte, entonces una coalición está ganando si y sólo si su complemento está perdiendo, es decir, si y solo si . (Si v es un juego simple de coalición que es propio 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 (vetador) en un juego simple es un jugador que pertenece a todas las coaliciones ganadoras. Suponiendo que hay 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}$
  • En un juego simple, un dictador es un jugador con poder de veto, de modo que cualquier coalición que contenga a este jugador resulta ganadora. El dictador no pertenece a ninguna coalición perdedora. ( Los juegos de dictadores en economía experimental no tienen relación con esto).
• Un portador de un juego simple W es un conjunto tal que para cualquier coalición S , tenemos si y solo si . Cuando un juego simple tiene un portador, se ignora a cualquier jugador que no pertenezca a él. A veces se dice que un juego simple es 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 del grado en que una regla de agregación puede producir elecciones bien definidas.

Se han reconocido ampliamente algunas relaciones entre los axiomas anteriores, como las siguientes (por ejemplo, Peleg, 2002, Sección 2.1 ^[7] ):

• Si un juego simple es débil, es apropiado.
• Un juego simple es dictatorial si y sólo 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 (monotonía, propiedad, fortaleza y no debilidad), finitud y computabilidad algorítmica ^{[8] (Kumabe y Mihara, 2011 [9]} ), cuyos resultados se resumen en la Tabla "Existencia de Juegos Simples" a continuación.

También se estudiaron ampliamente las restricciones que imponen varios axiomas para juegos simples sobre su número de Nakamura . ^[11] 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 propio y no fuerte .

Relación con la teoría no cooperativa

Sea G un juego estratégico (no cooperativo). Entonces, suponiendo que las coaliciones tienen la capacidad de imponer un comportamiento coordinado, existen varios juegos cooperativos asociados con G. Estos juegos suelen denominarse representaciones de G. Las dos representaciones estándar son: ^[12]

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

Conceptos de solución

El supuesto principal de la teoría de juegos cooperativos es que se formará la gran coalición. ^[13] El desafío es entonces distribuir el pago entre los jugadores de alguna manera. (Este supuesto no es restrictivo, 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 realmente se formen). 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 que se deben 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)}$
• Racionalidad individual: Ningún jugador recibe menos de lo que podría conseguir por sí solo: . ${\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 la solución es único para cada juego . ${\displaystyle v}$
• Marginalidad: El pago de un jugador depende únicamente de la contribución marginal de este jugador, es decir, si estas contribuciones marginales son las mismas en dos juegos diferentes, entonces el pago es el mismo: implica que es el mismo 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}$
• Monotonía: La ganancia de un jugador aumenta si la contribución marginal de este jugador aumenta: implica que es débilmente mayor en 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: El concepto de solución asigna pagos iguales a jugadores simétricos , . Dos jugadores , son simétricos si ; es decir, podemos intercambiar un jugador por el otro en cualquier coalición que contenga solo uno de los jugadores y no cambiar el pago. ${\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 pagos que la coalición obtendría en los dos juegos individuales. Un concepto de solución aditiva asigna a cada jugador en 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 resultados eficiente se denomina preimputación y una preimputación individualmente racional se denomina imputación . La mayoría de los conceptos de solución son imputaciones.

.mw-parser-output .vanchor>:target~.vanchor-text{background-color:#b1d2ff}@media screen{html.skin-theme-clientpref-night .mw-parser-output .vanchor>:target~.vanchor-text{background-color:#0f4dc9}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .vanchor>:target~.vanchor-text{background-color:#0f4dc9}}El conjunto estable

El conjunto estable de un juego (también conocido como la solución de 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 sean , dos imputaciones de . Entonces domina si alguna coalición satisface y . En otras palabras, los jugadores en prefieren los pagos de a los de , y pueden amenazar con abandonar la gran coalición si se utiliza porque el pago que obtienen por sí solos es al menos tan grande como la asignación que reciben bajo . ${\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 del conjunto.

Von Neumann y Morgenstern consideraron que el conjunto estable es el conjunto de conductas aceptables en una sociedad: ninguna es claramente preferida a otra, pero para cada conducta inaceptable existe una alternativa preferida. La definición es muy general, lo que permite que el concepto se utilice en una amplia variedad de formatos de juego. ^{[ cita requerida ]}

Propiedades

• Un conjunto estable puede existir o no (Lucas 1969), y si existe, normalmente 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 juegos cooperativos tiene conjuntos estables únicos que consisten en el núcleo (Owen 1995, pág. 240).
• Una fracción positiva de los juegos cooperativos tienen conjuntos estables que discriminan a los jugadores. En dichos conjuntos, al menos uno de los jugadores discriminados queda excluido (Owen 1995, p. 240). ${\displaystyle n-2}$ ${\displaystyle n-3}$

El núcleo

Sea un juego cuyo núcleo es el conjunto de vectores de pagos . ${\displaystyle v}$ ${\displaystyle v}$

${\displaystyle C(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),\forall ~S\subseteq N\right\}.}$

En otras palabras, el núcleo es el conjunto de imputaciones según 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 abandonar la gran coalición y recibir un pago mayor.

Propiedades

• El núcleo de un juego puede estar vacío (véase 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 necesariamente contiene un vector único.
• El núcleo está contenido en cualquier conjunto estable, y si el núcleo es estable es el único conjunto estable; véase (Driessen 1988) para una prueba.

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

Para los juegos simples, existe otra noción de núcleo, cuando se supone que cada jugador tiene preferencias sobre un conjunto de alternativas. Un perfil es una lista de preferencias individuales sobre . Aquí significa que el individuo prefiere una alternativa a en el perfil . Dado un juego simple y un perfil , una relación de dominio se define sobre 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\in C(v,p)}$si y sólo si no existe tal que . ${\displaystyle y\in 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 . (Véase el número de Nakamura para 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 núcleo épsilon fuerte

Como el núcleo puede estar vacío, se introdujo una generalización en (Shapley y Shubik 1966). El núcleo fuerte ${\displaystyle \varepsilon }$ para algún número es el conjunto de vectores de pagos. ${\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 preimputaciones donde ninguna coalición puede mejorar su resultado abandonando la gran coalición, si debe pagar una penalización de por abandonarla. puede ser negativo, en cuyo caso representa una bonificación por abandonar la gran coalición. Claramente, independientemente de si el núcleo está vacío, el núcleo fuerte será no 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 puede verse 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 Shapley

El valor de Shapley es el único vector de pagos que es eficiente, simétrico y satisface la monotonía. ^[14] Fue introducido por Lloyd Shapley (Shapley 1953) quien demostró que es el único vector de pagos que es eficiente, simétrico, aditivo y asigna pagos cero 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 núcleo

Sea un juego y sea un vector de pagos eficiente. El excedente máximo del jugador i sobre el jugador j con respecto a x 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 al retirarse de la gran coalición N bajo el vector de pagos x , suponiendo que los otros jugadores en la coalición que se retira de i están satisfechos con sus pagos 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 par 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 y Maschler 1965). ${\displaystyle s_{ij}^{v}(x)>s_{ji}^{v}(x)}$ ${\displaystyle x_{j}=v(j)}$

Dividendo de Harsanyi

El dividendo de Harsanyi (llamado así por John Harsanyi , quien lo utilizó para generalizar el valor de Shapley en 1963 ^[15] ) identifica el excedente que crea una coalición de jugadores en un juego cooperativo. Para especificar este excedente, el valor de esta coalición se corrige por el excedente que ya crean las subcoaliciones. Para este fin, el dividendo de la coalición en el juego se determina recursivamente mediante ${\displaystyle d_{v}(S)}$ ${\displaystyle S}$ ${\displaystyle v}$

${\displaystyle {\begin{aligned}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_{v}(\{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{aligned}}}$

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 . ^[16] De hecho, podemos recuperarnos de con 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}}$ ${\textstyle v(S)=d_{v}(S)+\sum _{T\subsetneq S}d_{v}(T)}$

Los dividendos de Harsanyi son útiles para analizar juegos y 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 de un jugador en un juego se obtiene sumando la parte de un jugador de los dividendos de todas las coaliciones a las que pertenece . ${\displaystyle \phi _{i}(v)}$ ${\displaystyle i}$ ${\displaystyle v}$ ${\textstyle \phi _{i}(v)=\sum _{S\subset N:i\in S}{d_{v}(S)}/{|S|}}$

El nucléolo

Sea un juego y sea un vector de pagos. El exceso de para una coalición es la cantidad ; es decir, la ganancia que los jugadores en coalición pueden obtener si se retiran de la gran coalición bajo pago y en su lugar toman el pago . El nucléolo de es la imputación para la cual el vector de excesos de todas las coaliciones (un vector en ) es más pequeño en el orden leximin . El nucléolo fue introducido en (Schmeidler 1969). ${\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)}$ ${\displaystyle v}$ ${\displaystyle \mathbb {R} ^{2^{N}}}$

(Maschler, Peleg y Shapley 1979) dieron una descripción más intuitiva: comenzando con el núcleo menor, registre las coaliciones para las cuales el lado derecho de la desigualdad en la definición de no se puede reducir más sin hacer que el conjunto quede vacío. Continúe disminuyendo el lado derecho para las coaliciones restantes, hasta que no se pueda reducir sin hacer que el conjunto quede vacío. Registre el nuevo conjunto de coaliciones para las cuales 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 pagos resultante es el nucléolo. ${\displaystyle C_{\varepsilon }(v)}$

Propiedades

• Aunque la definición no lo indica explícitamente, el nucléolo es siempre único. (Véase la Sección II.7 de (Driessen 1988) para una prueba).
• Si el núcleo no está vacío, el nucléolo está en el núcleo.
• El nucléolo está siempre 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 tienen algunos juegos de "efecto bola 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.}$

Se puede demostrar (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 conduce al efecto bola de nieve antes mencionado. Para los juegos de costos, las desigualdades se invierten, de modo 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 .
• Se puede encontrar un punto extremo (vértice) del núcleo en tiempo polinomial utilizando el algoritmo voraz : Sea una permutación de los jugadores, y sea el conjunto de jugadores ordenados a través de en , para cualquier , con . Entonces el pago definido 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\to 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 conjunto submodulares y supermodulares también se estudian en la optimización combinatoria . Muchos de los resultados de (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 costes convexos se denomina poliedro base , porque sus elementos generalizan las propiedades base de los matroides .

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

La relación entre la teoría de juegos cooperativos y la empresa

Las decisiones estratégicas corporativas pueden desarrollarse y crear valor a través de la teoría de juegos cooperativos. ^[17] Esto significa que la teoría de juegos cooperativos puede convertirse en la teoría estratégica de la empresa, y diferentes soluciones de CGT pueden simular diferentes instituciones.

Véase también

• Toma de decisiones por consenso
• Juego de coordinación
• Negociación dentro del hogar
• Juego hedónico
• Juego de producción lineal
• Juego de árbol de expansión de mínimo costo : una clase de juegos cooperativos.

Referencias

1. Shor, Mike. "Juego no cooperativo - Game Theory .net". www.gametheory.net . Consultado el 15 de septiembre de 2016 .
2. Chandrasekaran, R. "Teoría de juegos cooperativos" (PDF) .
3. Brandenburger, Adam. "Teoría de juegos cooperativos: funciones características, asignaciones, contribución marginal" (PDF) . Archivado desde el original (PDF) el 27 de mayo de 2016.
4. denota el conjunto potencia de . ${\displaystyle 2^{N}}$ ${\displaystyle N}$
5. Javier Muros, Francisco (2019). Herramientas de teoría de juegos cooperativos en redes de control de coalición (1.ª ed.). Springer Cham. pp. 9–11. ISBN 978-3-030-10488-7.
6. Georgios Chalkiadakis; Edith Elkind; Michael J. Wooldridge (25 de octubre de 2011). Aspectos computacionales de la teoría de juegos cooperativos. Morgan & Claypool Publishers. ISBN 978-1-60845-652-9.
7. Peleg, B. (2002). "Capítulo 8 Análisis de la votación en comités mediante teoría de juegos". Handbook of Social Choice and Welfare Volumen 1. Vol. 1. págs. 395–423. doi :10.1016/S1574-0110(02)80012-1. ISBN 9780444829146.
8. Véase una sección sobre el teorema de Rice para obtener la definición de un juego simple computable. En particular, todos los juegos finitos son computables.
9. Kumabe, M.; Mihara, HR (2011). "Computabilidad de juegos simples: una investigación completa de las sesenta y cuatro posibilidades" (PDF) . Journal of Mathematical Economics . 47 (2): 150–158. arXiv : 1102.4037 . Bibcode :2011arXiv1102.4037K. doi :10.1016/j.jmateco.2010.12.003. S2CID  775278.
10. Modificado de la Tabla 1 en Kumabe y Mihara (2011). Los dieciséis tipos están definidos por los cuatro axiomas convencionales (monotonía, propiedad, fortaleza y no debilidad). Por ejemplo, el tipo 1110 indica juegos monótonos (1), propios (1), fuertes (1), débiles (0, porque no son no débiles). Entre los juegos del tipo 1110 , no existen juegos finitos no computables, existen juegos finitos computables, no existen juegos infinitos no computables y no existen juegos infinitos computables. Observe que, excepto por el tipo 1110 , las últimas tres columnas son idénticas.
11. Kumabe, M.; Mihara, HR (2008). "Los números de Nakamura para juegos simples computables". Elección social y bienestar . 31 (4): 621. arXiv : 1107.0439 . doi :10.1007/s00355-008-0300-5. S2CID  8106333.
12. Aumann, Robert J. "El núcleo de un juego cooperativo sin pagos secundarios". Transactions of the American Mathematical Society (1961): 539-552.
13. Peters, Hans (2008). Teoría de juegos: un enfoque multinivel . Springer. pp. 123. doi :10.1007/978-3-540-69291-1_17. ISBN . 978-3-540-69290-4.
14. Young, HP (1 de junio de 1985). "Soluciones monótonas de juegos cooperativos". Revista internacional de teoría de juegos . 14 (2): 65–72. doi :10.1007/BF01769885. ISSN  0020-7276. S2CID  122758426.
15. Harsanyi, John C. (1982). "Un modelo de negociación simplificado para el juego cooperativo de n personas". Artículos sobre teoría de juegos . Biblioteca de teoría y decisión. Springer, Dordrecht. págs. 44–70. doi :10.1007/978-94-017-2527-9_3. ISBN 9789048183692.
16. Funciones, juegos y capacidades de los conjuntos en la toma de decisiones | Michel Grabisch | Springer. Biblioteca de teoría y decisión C. Springer. 2016. ISBN 9783319306889.
17. Ross, David Gaddis (1 de agosto de 2018). "Uso de la teoría de juegos cooperativos para contribuir a la investigación estratégica". Revista de gestión estratégica . 39 (11): 2859–2876. doi :10.1002/smj.2936. S2CID  169982369.

Lectura adicional

• 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.), Combinatorial Structures and Their Applications , Nueva York: Gordon and 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) Archivado el 15 de agosto de 2000 en Wayback Machine en muchas universidades.

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

• Lucas, William F. (1992), "Conjuntos estables de Von Neumann-Morgenstern", en Aumann, Robert J .; Hart, Sergiu (eds.), Manual de teoría de juegos, volumen I , Ámsterdam: Elsevier , págs. 543–590

• Luce, RD y Raiffa, H. (1957) Juegos y decisiones: Introducción y estudio crítico , Wiley & Sons. (véase el Capítulo 8).
• Maschler, M .; Peleg, B.; Shapley, Lloyd S. (1979), "Propiedades geométricas del núcleo, el nucléolo 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 (ver capítulos 13, 14 y 15)
• Moulin, Herve (1988), Axiomas de la toma de decisiones cooperativa (1.ª ed.), Cambridge: Cambridge University Press , ISBN 978-0-521-42458-5

• Owen, Guillermo (1995), Teoría de juegos (3.ª ed.), San Diego: Academic Press , ISBN 978-0-12-531151-9

• Schmeidler, D. (1969), "El nucléolo de un juego de funciones características", SIAM Journal on Applied Mathematics , 17 (6): 1163–1170, doi :10.1137/0117107.

• Shapley, Lloyd S. (1953), "Un valor para los juegos de dos 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. (18 de marzo de 1952), A Value for N-Person Games, Santa Mónica, California: The RAND Corporation

• Shapley, Lloyd S. (1971), "Núcleos de juegos convexos", 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 completa desde una perspectiva computacional; consulte el Capítulo 12. Descargable gratuitamente en línea.

• von Neumann, John ; Morgenstern, Oskar (1944), "Teoría de juegos y comportamiento económico" , Nature , 157 (3981), Princeton: Princeton University Press : 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 avanzado de juegos dinámicos cooperativos (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]