Teoría de juegos cooperativos

Juego donde grupos de jugadores pueden imponer un comportamiento cooperativo.

En teoría de juegos , un juego cooperativo (o juego de coalición ) es un juego en el que 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 ). Se oponen a los juegos no cooperativos en los que no existe la posibilidad de forjar alianzas o todos los acuerdos deben ser autoaplicables (por ejemplo, mediante amenazas creíbles ). ^[1]

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 toman los grupos y los resultados colectivos resultantes. Se opone a la tradicional teoría de juegos no cooperativos que se centra en predecir las acciones y pagos de los jugadores individuales y analizar los equilibrios de Nash . ^{[2] [3]}

La teoría de juegos cooperativos proporciona un enfoque de alto nivel, ya que sólo describe la estructura, las estrategias y los beneficios de las coaliciones, mientras que la teoría de juegos no cooperativa 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 mediante el enfoque de la teoría de juegos no cooperativos (lo contrario no se cumple) 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 bajo un marco no cooperativo, en muchos casos no se dispone de información suficiente 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 de demasiado alto nivel. 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 su conjunto sin tener que hacer ninguna suposición sobre el poder de negociación.

Definición matemática

Un juego cooperativo se obtiene especificando un valor para cada coalición. Formalmente, el juego de coalición consta de un conjunto finito de jugadores , llamado gran coalición , y una función característica ^[4] que va del conjunto de todas las coaliciones posibles de jugadores a 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}$

Por el contrario, un juego cooperativo también puede definirse con una función de coste característica que satisfaga . En este escenario, los jugadores deben realizar alguna tarea, y la función característica representa el costo de que un conjunto de jugadores realice la tarea juntos. Un juego de este tipo se conoce como juego de costos . Aunque la mayor parte de la teoría de juegos cooperativos se ocupa de juegos con ganancias, todos los conceptos pueden trasladarse fácilmente a la fijación de costos. ${\displaystyle c:2^{N}\to \mathbb {R} }$ ${\displaystyle c(\emptyset )=0}$ ${\displaystyle c}$

Definición de la 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 otros jugadores. ^[5] La idea clave es que los jugadores pueden lograr resultados superiores trabajando juntos en lugar de trabajar uno contra el otro. Los siguientes puntos proporcionan una explicación detallada de las cuatro características clave de la teoría de juegos cooperativos:

Intereses comunes: en los juegos cooperativos, los jugadores comparten un interés común en lograr un objetivo o resultado específico. Los actores deben identificar y acordar un interés común para establecer las bases y el razonamiento de la cooperación. Una vez que los jugadores tengan una comprensión clara de su interés compartido, podrán trabajar juntos para lograrlo.

Intercambio de información necesario: La cooperación requiere comunicación e intercambio de información entre los actores. 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 juntos para alcanzarlos.

Voluntariedad, igualdad y beneficio mutuo: en los juegos cooperativos, los jugadores se unen 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 sólo es sostenible si todas las partes sienten que están recibiendo una parte justa de los beneficios.

Contrato obligatorio: En los juegos cooperativos, los acuerdos entre jugadores son vinculantes y obligatorios. Una vez que los jugadores han acordado un curso de acción particular, tienen la obligación de cumplirlo. Los actores deben confiar unos en otros para cumplir 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 alcanzar su objetivo compartido.

Dividendo de Harsanyi

El dividendo Harsanyi (llamado así por John Harsanyi , quien lo utilizó para generalizar el valor de Shapley en 1963 ^[6] ) identifica el excedente creado por una coalición de jugadores en un juego cooperativo. Para especificar este superávit, el valor de esta coalición se corrige por el superávit que ya crean las subcoaliciones. Para este fin, el dividendo de la coalición en el juego está determinado recursivamente por ${\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 inversa de Möbius . ^[7] De hecho, podemos recuperarnos 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 tanto juegos como 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 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|}}$

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 coste dual se puede definir de forma idéntica a 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, véase, por ejemplo, (Bilbao 2000). ${\displaystyle S}$ ${\displaystyle N}$ ${\displaystyle c^{*}}$ ${\displaystyle c}$

Subjuegos

Seamos una coalición de jugadores no vacía. 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 la 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 separadas 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 "ganan" o "pierden". ^[8]

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 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 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 gana, es decir, si e implican . ${\displaystyle S\in W}$ ${\displaystyle S\subseteq T}$ ${\displaystyle T\in W}$
• Un juego simple W es adecuado 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 el complemento de cualquier coalición perdedora es ganadora, 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 gana si y sólo si su complemento está perdiendo, es decir, si y sólo si . (Si v es un juego simple de coalición, apropiado 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 hay un jugador con veto, cualquier coalición que no contenga un jugador con veto está perdiendo. Un juego simple W es débil ( colegial ) 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 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 sif . 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 una portadora finita (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 generar opciones bien definidas.

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

• 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 ^{[10] (Kumabe y Mihara, 2011 [11]} ), cuyo Los resultados se resumen en la tabla "Existencia de juegos simples" a continuación.

También se estudiaron exhaustivamente las restricciones que varios axiomas de juegos simples imponen a su número de Nakamura . ^[13] En particular, un juego simple computable sin un jugador con veto tiene un número de Nakamura mayor que 3 sólo 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, suponiendo que las coaliciones tienen la capacidad de imponer un comportamiento coordinado, existen varios juegos cooperativos asociados con G. Estos juegos a menudo se denominan representaciones de G. Las dos representaciones estándar son: ^[14]

• 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, es decir, 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, es decir, el valor mínimo del máximo adoptado por las estrategias de la oposición.

Conceptos de solución

El principal supuesto en la teoría de los juegos cooperativos es que se formará la gran coalición . ^[15] El desafío es entonces distribuir la recompensa entre los jugadores de alguna 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 cualquier coalición que realmente se forme). Un concepto de solución es un vector (o un conjunto de vectores) que representa el asignación a cada jugador. Los investigadores han propuesto diferentes conceptos de solución basados ​​en diferentes nociones de justicia. Algunas propiedades a buscar en un concepto de solución incluyen: ${\displaystyle N}$ ${\displaystyle v(N)}$ ${\displaystyle x\in \mathbb {R} ^{N}}$

• Eficiencia: el vector de beneficios 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}$
• Unicidad: El concepto de solución es único para cualquier juego . ${\displaystyle v}$
• Marginalidad: El pago de un jugador depende sólo 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}$
• Monotonicidad: El pago 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 computacional: el concepto de solución se puede calcular de manera eficiente (es decir, en tiempo polinómico 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 otro en cualquier coalición que contenga sólo 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 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 pagos eficiente se llama preimputación , y una preimputación individualmente racional se llama imputación . La mayoría de los conceptos de solución son imputaciones.

.mw-parser-output .vanchor>:target~.vanchor-text{background-color:#b1d2ff}El conjunto estable

El conjunto estable de un juego (también conocido como 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 los pagos que obtienen por sí solos son al menos tan grandes 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 pagos en el conjunto estable está dominado por otro vector del conjunto.
• Estabilidad externa: todos los vectores de pagos fuera del conjunto están dominados por al menos un vector del conjunto.

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

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 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, al menos los jugadores discriminados quedan excluidos (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 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 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 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 llaman 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 único conjunto estable; ver (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 en . Aquí significa que el individuo prefiere una alternativa al perfil . Dado un juego simple y un perfil , una relación de dominancia se define por si y sólo si hay una coalición ganadora (es decir, ) que satisfaga a 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 eso . ${\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 sólo 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 sólo 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 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 pre-imputaciones según las cuales ninguna coalición puede mejorar sus beneficios 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 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 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 de Shapley

El valor de Shapley es el único vector de resultados que es eficiente, simétrico y satisface la monotonicidad. ^[16] Fue introducido por Lloyd Shapley (Shapley 1953), quien demostró que es el único vector de pagos 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 no es cierto en general. (Driessen 1988)

el núcleo

Sea un juego y sea un vector de pago 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 de 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 este pago por sí solo. 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)}$

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 de la coalición pueden obtener si se retiran de la gran coalición bajo pago y en su lugar aceptan 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 nucleolo 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 mínimo, registre las coaliciones para las cuales el lado derecho de la desigualdad en la definición de no se puede reducir más 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 cuales las desigualdades son iguales; 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 indica explícitamente, el nucléolo siempre es único. (Ver 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 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 tienen algunos juegos de "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 (ver, 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 ésta crece" (Shapley 1971), lo que lleva 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 .
• Un punto extremo (vértice) del núcleo se puede encontrar en tiempo polinómico usando el algoritmo codicioso : Sea una permutación de los jugadores, y sea el conjunto de jugadores ordenados en , para cualquiera , 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 adecuada . ${\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 conjuntos submodulares y supermodulares también se estudian en 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 convexo se llama poliedro base , porque sus elementos generalizan las propiedades base de las 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 manejable. Desafortunadamente, esto entra directamente en conflicto 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 CGT pueden simular diferentes instituciones.

Ver también

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

Referencias

1. Corto, Mike. "Juego no cooperativo - Teoría de juegos .net". www.gametheory.net . Consultado el 15 de septiembre de 2016 .
2. Chandrasekaran, R. "Teoría de juegos cooperativos" (PDF) .
3. Brandeburgo, 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 de potencias de . ${\displaystyle 2^{N}}$ ${\displaystyle N}$
5. Javier Muros, Francisco (2019). Herramientas cooperativas de teoría de juegos en redes de control coalicionales (1 ed.). Springer Cham. págs. 9-11. ISBN 978-3-030-10488-7.
6. 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.
7. Establecer funciones, juegos y capacidades en la toma de decisiones | Michel Grabisch | Saltador. Biblioteca de teoría y decisión C. Springer. 2016.ISBN​ 9783319306889.
8. Georgios Chalkiadakis; Edith Elkind; Michael J. Wooldridge (25 de octubre de 2011). Aspectos computacionales de la teoría de juegos cooperativos. Editores Morgan y Claypool. ISBN 978-1-60845-652-9.
9. Peleg, B. (2002). "Capítulo 8 Análisis de la teoría de juegos de la votación en comités". Manual de elección social y bienestar Volumen 1 . Manual de elección social y bienestar. vol. 1. págs. 395–423. doi :10.1016/S1574-0110(02)80012-1. ISBN 9780444829146.
10. Consulte una sección sobre el teorema de Rice para conocer la definición de un juego simple computable. En particular, todos los juegos finitos son computables.
11. Kumabe, M.; Mihara, recursos humanos (2011). "Computabilidad de juegos simples: una investigación completa de las sesenta y cuatro posibilidades" (PDF) . Revista de Economía Matemática . 47 (2): 150-158. arXiv : 1102.4037 . Código Bib : 2011arXiv1102.4037K. doi :10.1016/j.jmateco.2010.12.003. S2CID  775278.
12. Modificado de la Tabla 1 en Kumabe y Mihara (2011). Los dieciséis tipos están definidos por los cuatro axiomas convencionales (monotonía, idoneidad, fortaleza y no debilidad). Por ejemplo, el tipo 1110 indica juegos monótonos (1), propios (1), fuertes (1), débiles (0, porque no no débiles). Entre los juegos del tipo 1110 , no existen finitos no computables, existen finitos computables, no existen infinitos no computables y no existen infinitos computables. Observe que, excepto el tipo 1110 , las últimas tres columnas son idénticas.
13. Kumabe, M.; Mihara, recursos humanos (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.
14. Aumann, Robert J. "El núcleo de un juego cooperativo sin pagos adicionales". Transacciones de la Sociedad Matemática Estadounidense (1961): 539-552.
15. Peters, Hans (2008). Teoría de juegos: un enfoque de múltiples niveles . Saltador. págs.123. doi :10.1007/978-3-540-69291-1_17. ISBN 978-3-540-69290-4.
16. Joven, 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.
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.

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, soluciones y aplicaciones cooperativas, 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 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 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. (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 cooperativas (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 nucleolo de un juego de funciones características", Revista SIAM de Matemáticas Aplicadas , 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 juegos II , Princeton, Nueva Jersey: Princeton University Press, págs. ${\displaystyle n}$

• Shapley, Lloyd S. (18 de marzo de 1952), Un valor para los juegos de N personas, Santa Mónica, California: The RAND Corporation

• Shapley, Lloyd S. (1971), "Núcleos de juegos convexos", Revista internacional de teoría de juegos , 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. Descargable gratis en línea.

• Von Neumann, Juan ; Morgenstern, Oskar (1944), "Teoría de los juegos y comportamiento económico" , Naturaleza , 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 dinámico cooperativo avanzado de juegos (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]