Teoría de juegos cooperativos

En la teoría del juego, un juego de cooperativas (o juego de coalición) es un juego con competencia entre grupos de jugadores ("coaliciones") debido a la posibilidad de la ejecución externa del comportamiento cooperativo (por ejemplo, a través de la ley contractual). Estos se oponen a juegos no cooperativos en los que no hay posibilidad de forjar alianzas o todos los acuerdos necesitan ser auto-forzando (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 toman los grupos y los beneficios colectivos resultantes. Se opone a la tradicional teoría de juegos no cooperativos que se centra en predecir las habilidades de los jugadores individuales. acciones y pagos y analizar equilibrios de Nash.

La teoría de 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 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 da especificando un valor para cada coalición. Formally, el juego de coalición consiste en un conjunto finito de jugadores ${displaystyle N}$, llamado el Gran coalicióny un función característica ${displaystyle v:2^{N}to mathbb {R}$ del conjunto de todas las posibles coaliciones de jugadores a un conjunto de pagos que satisfies ${displaystyle v(emptyset)=0}$. La función describe cuánto pago colectivo puede ganar un conjunto de jugadores formando una coalición, y el juego se llama a veces un valor juego o a ganancia juego.

Por el contrario, un juego cooperativo también se puede definir con una función de coste característica ${displaystyle c:2^{N}to mathbb {R}$ satisfacción ${displaystyle c(emptyset)=0}$. En este escenario, los jugadores deben realizar alguna tarea, y la función característica ${displaystyle c}$ representa el costo de un conjunto de jugadores que cumplen la tarea juntos. Un juego de este tipo es conocido como costo juego. Aunque la mayoría de la teoría del juego cooperativo trata con los juegos de ganancia, todos los conceptos se pueden traducir fácilmente a la configuración de costos.

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. 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 cada uno 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 después de John Harsanyi, quien lo usó para generalizar el valor Shapley en 1963) identifica el superávit que es creado por una coalición de jugadores en un juego cooperativo. Para especificar este excedente, el valor de esta coalición es corregido por el superávit que ya está creado por subcoaliciones. Con este fin, el dividendo ${displaystyle d_{v}(S)}$ de coalición ${displaystyle S.$ en juego ${displaystyle v}$ se determina recursivamente por

${fnMicrosoft Sans Serif}$

Una fórmula explícita para el dividendo es dada por ${textstyle d_{v}(S)=sum _{Tsubseteq S}(-1)^{ privacySsetminus Tperu}v(T)}$. La función ${displaystyle - ¿Qué? {R}$ es también conocido como el inverso Möbius de ${displaystyle v:2^{N}to mathbb {R}$. De hecho, podemos recuperarnos. ${displaystyle v}$ desde ${displaystyle d_{v}$ por la ayuda de la fórmula ${textstyle v(S)=d_{v}(S)+sum _{Tsubsetneq S}d_{v}(T)}$.

Los dividendos de Harsanyi son útiles para analizar los conceptos de juegos y 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 ${displaystyle phi _{i}(v)}$ de jugador ${displaystyle i}$ en juego ${displaystyle v}$ se da resumiendo la parte de un jugador de los dividendos de todas las coaliciones a las que pertenece, ${textstyle phi _{i}(v)=sum ¿Por qué?$.

Dualidad

Vamos. ${displaystyle v}$ ser un juego de ganancias. El juego dual de ${displaystyle v}$ es el costo juego ${displaystyle v^{*}$ definidas

${displaystyle v^{*}(S)=v(N)-v(Nsetminus S),forall ~Ssubseteq N.}$

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

Subjuegos

Vamos. ${displaystyle Ssubsetneq N}$ ser una coalición no vacía de jugadores. El subgame ${displaystyle #2^{S}to mathbb {R}$ on ${displaystyle S.$ es naturalmente definido como

${displaystyle v_{S}(T)=v(T),forall ~Tsubseteq S.}$

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

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 disjuntas no es menor que la suma de las coaliciones. valores separados:

${displaystyle v(Scup T)geq v(S)+v(T)}$ siempre ${displaystyle S,Tsubseteq N}$ satisfacer satisfacción ${displaystyle Scap T=emptyset }$.

Monotonicidad

Las coaliciones más grandes ganan más:

${displaystyle Ssubseteq TRightarrow 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, coaliciones. están "ganando" o "perder".

De manera equivalente, un juego simple se puede definir como una colección W de coaliciones, donde las 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 monotónico si cualquier coalición que contenga una coalición ganadora también está ganando, es decir, si ${displaystyle Sin W.$ y ${displaystyle Ssubseteq T}$ implicaciones ${displaystyle Tin W.$.
• Un juego simple W es apropiado si el complemento (oposición) de cualquier coalición ganador está perdiendo, es decir, si ${displaystyle Sin W.$ implicación ${displaystyle Nsetminus Snotin W}$.
• Un juego simple W es fuerte si el complemento de cualquier coalición perdedor está ganando, es decir, si ${displaystyle Snotin W}$ implicación ${displaystyle Nsetminus Sin W}$.
  • Si un juego simple W es apropiado y fuerte, entonces una coalición está ganando si y sólo si su complemento está perdiendo, es decir, ${displaystyle Sin W.$ Sip ${displaystyle Nsetminus Snotin W}$. (Si) v es un juego de coalición simple que es apropiado y fuerte, ${displaystyle v(S)=1-v(Nsetminus S)}$ para cualquier S)
• A veto jugador (vetoer) en un juego simple es un jugador que pertenece a todas las coaliciones ganadoras. Suponiendo que haya un jugador de veto, cualquier coalición que no contenga un jugador de veto está perdiendo. Un juego simple W es débil ()colegial) si tiene un jugador de veto, es decir, si la intersección ${displaystyle bigcap W:=bigcap ¿Por qué?$ de todas las coaliciones ganadoras no es vacía.
  • A dictador en un juego simple es un jugador de veto tal que cualquier coalición que contenga este jugador está ganando. El dictador no pertenece a ninguna coalición perdedora. (Los juegos de dictador en economía experimental no están relacionados con esto.)
• A transportista de un juego simple W es un juego ${displaystyle Tsubseteq N}$ tal que para cualquier coalición S, tenemos ${displaystyle Sin W.$ Sip ${displaystyle Scap Tin W$. Cuando un juego simple tiene un portador, cualquier jugador que no pertenece a él es ignorado. Un juego simple a veces se llama finito si tiene un transportista finito (incluso si N es infinito).
• 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 la medida en que una regla de agregación puede producir opciones bien definidas.

Se han reconocido ampliamente algunas relaciones entre los axiomas anteriores, 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 sólo si es fuerte y débil.

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

También se estudiaron exhaustivamente las restricciones que varios axiomas de juegos simples imponen a su número de Nakamura. 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 tengan 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:

• El juego α-eficaz asocia con cada coalición la suma de ganancias que sus miembros pueden 'guarantee' al unir fuerzas. Por 'garantizar', se entiende que el valor es el máx-min, por ejemplo el valor máximo del mínimo tomado sobre las estrategias de la oposición.
• El juego β-efectivo asocia con cada coalición la suma de ganancias que sus miembros pueden 'asegurarse estratégicamente' al unir fuerzas. Por "asegurar estratégicamente", se entiende que el valor es el min-max, por ejemplo el valor mínimo del máximo tomado sobre las estrategias de la oposición.

Conceptos de solución

La principal suposición en la teoría del juego cooperativo es que la gran coalición ${displaystyle N}$ se formará. El desafío es entonces asignar el pago ${displaystyle v(N)}$ entre los jugadores de alguna manera justa. (Esta suposición no es restrictiva, ya que 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 coaliciones realmente forman). A concepto de solución es un vector ${displaystyle xin mathbb {R} {N}$ (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 a buscar en un concepto de solución incluyen:

• Eficiencia: El vector payoff divide exactamente el valor total: ${displaystyle sum _{iin N}x_{i}=v(N)}$.
• Racionalidad individual: Ningún jugador recibe menos de lo que podría conseguir por su cuenta: ${displaystyle x_{i}gq v({i}),forall ~iin N}$.
• Existencia: El concepto de solución existe para cualquier juego ${displaystyle v}$.
• Uniqueness: 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: ${displaystyle v(Scup {i})=w(Scup {i}),forall ~Ssubseteq Nsetminus {i}}$ implica que ${displaystyle x_{i}}$ es lo mismo ${displaystyle v}$ y dentro ${displaystyle w}$.
• Monotonicity: El pago de un jugador aumenta si la contribución marginal de este jugador aumenta: ${displaystyle v(Scup {i})leq w(Scup {i}),forall ~Ssubseteq Nsetminus {i}}$ implica que ${displaystyle x_{i}}$ es débilmente mayor en ${displaystyle w}$ que en ${displaystyle v}$.
• Fácil computacional: El concepto de solución se puede calcular eficientemente (es decir, en tiempo polinomio con respecto al número de jugadores ${displaystyle Silencioso$)
• Simmetría: El concepto de solución ${displaystyle x}$ asigna iguales pagos ${displaystyle x_{i}=x_{j}$ a jugadores simétricos ${displaystyle i}$, ${displaystyle j}$. Dos jugadores ${displaystyle i}$, ${displaystyle j}$ son simétrica si ${displaystyle v(Scup {i})=v(Scup {j}),forall ~Ssubseteq Nsetminus {i,j}}$; es decir, podemos cambiar un jugador por el otro en cualquier coalición que contenga sólo uno de los jugadores y no cambiar el pago.
• 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 ${displaystyle v}$ y ${displaystyle omega }$ son juegos, el juego ${displaystyle (v+omega)}$ simplemente asigna a cualquier coalición la suma de los pagos que la coalición conseguiría en los dos juegos individuales. Un concepto de solución aditiva asigna a cada jugador en ${displaystyle (v+omega)}$ la suma de lo que recibiría ${displaystyle v}$ y ${displaystyle omega }$.
• Zero Allocation to Null Players: La asignación a un jugador nulo es cero. A null player ${displaystyle i}$ satisfizo ${displaystyle v(Scup {i})=v(S),forall ~Ssubseteq Nsetminus {i}}$. En términos económicos, el valor marginal de un jugador nulo a cualquier coalición que no lo contenga es cero.

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.

El conjunto estable

El conjunto estable de un juego (también conocido como Solución von Neumann-Morgenstern (von Neumann & Morgenstern 1944) fue la primera solución propuesta para juegos con más de 2 jugadores. Vamos. ${displaystyle v}$ ser un juego y dejar ${displaystyle x}$, ${displaystyle y}$ ser dos imputaciones de ${displaystyle v}$. Entonces... ${displaystyle x}$ dominados ${displaystyle y}$ si alguna coalición ${displaystyle Sneq emptyset$ satisfizo ${displaystyle ################################################################################################################################################################################################################################################################ S.$ y ${displaystyle sum _{iin S}x_{i}leq v(S)}$. En otras palabras, jugadores en ${displaystyle S.$ prefiere los pagos de ${displaystyle x}$ a los de ${displaystyle y}$, y pueden amenazar con dejar la gran coalición si ${displaystyle y}$ se utiliza porque el pago que obtienen por su cuenta es al menos tan grande como la asignación que reciben bajo ${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.
• La 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 permitiendo que el concepto sea utilizado en una amplia variedad de formatos de juego.

Propiedades

• Un conjunto estable puede o no existir (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 tienen 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 ${displaystyle n-2}$ jugadores. En tales conjuntos al menos ${displaystyle n-3}$ de los actores discriminados están excluidos (Owen 1995, pág. 240).

El núcleo

Vamos. ${displaystyle v}$ ser un juego. El núcleo ${displaystyle v}$ es el conjunto de vectores de pago

${displaystyle C(v)=left{xin mathbb {R} ^{N}:sum _{iin N}x_{i}=v(N);quad sum _{iin S}x_{i}geq vs,forall ~Ssubseteq Nright}$

En palabras, el núcleo es el conjunto de imputaciones bajo las cuales ninguna coalición tiene un valor mayor que la suma de sus miembros. pagos. 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 Bondareva-Shapley). Juegos con núcleos no vacíos se llaman equilibrado.
• Si no es 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; véase (Driessen 1988) para una prueba.

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

Para juegos simples, hay otra noción del núcleo, cuando se supone que cada jugador tiene preferencias en un conjunto ${displaystyle X}$ de alternativas. A perfil es una lista ${displaystyle p=(succ _{i}{p}_{iin) N}$ de las preferencias individuales ${displaystyle succ _{i} {p}}$ on ${displaystyle X}$. Aquí. ${displaystyle xsucc _{i}{p}y}$ significa que el individuo ${displaystyle i}$ prefiere alternativas ${displaystyle x}$a ${displaystyle y}$ en perfil ${displaystyle p}$. Dado un juego simple ${displaystyle v}$ y un perfil ${displaystyle p}$, a dominación relación ${displaystyle succ _{p}}$ se define on ${displaystyle X}$ por ${displaystyle xsucc _{p}y}$ si y sólo si hay una coalición ganadora ${displaystyle S.$(es decir, ${displaystyle v(S)=1}$) satisfactoria ${displaystyle xsucc _{i}{p}y}$ para todos ${displaystyle iin S}$. El núcleo básico ${displaystyle C(v,p)}$ del juego simple ${displaystyle v}$ con respecto al perfil ${displaystyle p}$ de preferencias es el conjunto de alternativas no dominadas por ${displaystyle succ _{p}}$(el conjunto de elementos maximales de ${displaystyle X}$ con respecto a ${displaystyle succ _{p}}$):

${displaystyle xin C(v,p)}$ si no hay ${displaystyle yin X}$ tales que ${displaystyle ysucc _{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. Teorema de Nakamura declara que el núcleo ${displaystyle C(v,p)}$ no está vacío para todos los perfiles ${displaystyle p}$ de acíclica (alternativamente, transitoria) preferencias si ${displaystyle X}$ es finito y el número cardinal (el número de elementos) de ${displaystyle X}$ es menos que el número de Nakamura ${displaystyle v}$. Una variante de Kumabe y Mihara declara que el núcleo ${displaystyle C(v,p)}$ no está vacío para todos los perfiles ${displaystyle p}$ de preferencias que tienen una elemento maximalsi y sólo si el número cardinal ${displaystyle X}$ es menos que el número de Nakamura ${displaystyle v}$. (Ver número de Nakamura para detalles.)

El fuerte núcleo épsilon

Debido a que el núcleo puede estar vacío, se introdujo una generalización en (Shapley ' Shubik 1966). El fuerte ${displaystyle varepsilon }$-core para algunos números ${displaystyle varepsilon in mathbb {R}$ es el conjunto de vectores de pago

${displaystyle C_{varepsilon }(v)=left{xin mathbb {R} ^{N}:sum _{iin N}x_{i}=v(N);quad sum _{iin S}x_{i}geq v(S)-varepsilonforall -Ssubseteq Nright.$

En términos económicos, los fuertes ${displaystyle varepsilon }$-core es el conjunto de preimputaciones donde ninguna coalición puede mejorar su pago al salir de la gran coalición, si debe pagar una pena de ${displaystyle varepsilon }$ por salir. ${displaystyle varepsilon }$ puede ser negativo, en cuyo caso representa un bono para salir de la gran coalición. Claramente, independientemente de si el núcleo está vacío, el fuerte ${displaystyle varepsilon }$-core no estará vacío por un valor suficiente grande ${displaystyle varepsilon }$ y vacío para un valor lo suficientemente pequeño (posiblemente negativo) ${displaystyle varepsilon }$. Siguiendo esta línea de razonamiento, la mínimo-core, introducido en (Maschler, Peleg " Shapley 1979), es la intersección de todos los no necesitados fuertes ${displaystyle varepsilon }$-cores. También se puede ver como el fuerte ${displaystyle varepsilon }$-core para el valor más pequeño de ${displaystyle varepsilon }$ que hace que el conjunto no vacío (Bilbao 2000).

El valor Shapley

El valor de Shapley es el único vector de resultados que es eficiente, simétrico y satisface la monotonicidad. 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

Vamos. ${displaystyle v:2^{N}to mathbb {R}$ ser un juego, y dejar ${displaystyle xin mathbb {R} {N}$ ser un vector de pago eficiente. El excedente máximo de jugador i sobre el jugador j con respecto a x es

${displaystyle s_{ij}{v}(x)=max left{v(S)-sum _{kin S}x_{k}:Ssubseteq Nsetminus {j},iin Sright}$

el jugador de la cantidad máxima i puede ganar sin la cooperación del jugador j al retirarse de la gran coalición N vector de pagos x, suponiendo que los otros jugadores i 's retirando coalición están satisfechos con sus pagos bajo x. El excedente máximo es una manera de medir el poder de negociación de un jugador sobre otro. El kernel de ${displaystyle v}$ es el conjunto de imputaciones x que satisfacen

• ${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, jugador i tiene más poder de negociación que el jugador j con respecto a la imputación x si ${displaystyle s_{ij} {v}(x)} {ji}{v}(x)}$, pero jugador j es inmune al jugador i 's amenazas si ${displaystyle x_{j}=v(j)}$Porque puede obtener este pago por su cuenta. El núcleo contiene todas las imputaciones donde ningún jugador tiene este poder de negociación sobre otro. Este concepto de solución fue introducido por primera vez en (Davis & Maschler 1965).

El núcleo

Vamos. ${displaystyle v:2^{N}to mathbb {R}$ ser un juego, y dejar ${displaystyle xin mathbb {R} {N}$ ser un vector de pago. El exceso de ${displaystyle x}$ para una coalición ${displaystyle Ssubseteq N}$ es la cantidad ${displaystyle v(S)-sum _{iin S}x_{i}$; es decir, la ganancia que los jugadores en coalición ${displaystyle S.$ puede obtener si se retiran de la gran coalición ${displaystyle N}$ pagaderas ${displaystyle x}$ y en lugar de tomar el pago ${displaystyle v(S)}$. El nucleolo de ${displaystyle v}$ es la imputación por la cual el vector de excesos de todas las coaliciones (un vector en ${displaystyle mathbb {R} {2^{N}}$) es más pequeño en el orden de leximina. El núcleo fue introducido en (Schmeidler 1969).

(Maschler, Peleg & Shapley 1979) dio una descripción más intuitiva: Comenzando con la menor puntuación, registra las coaliciones para las cuales el lado derecho de la desigualdad en la definición de ${displaystyle C_{varepsilon }(v)}$ no se puede reducir aún más sin hacer el set vacío. Continúe disminuyendo el lado derecho de las coaliciones restantes, hasta que no pueda reducirse sin que el conjunto esté vacío. Recordar el nuevo conjunto de coaliciones para las que las desigualdades mantienen en igualdad; continuar disminuyendo el lado derecho de las coaliciones restantes y repetir este proceso tantas veces como sea necesario hasta que se hayan registrado todas las coaliciones. El vector de pago resultante es el núcleo.

Propiedades

• Aunque la definición no lo indica explícitamente, el núcleo siempre es único. (Véase la sección II.7 de (Driessen 1988) para una prueba.)
• Si el núcleo no es vacío, el núcleo está en el núcleo.
• El núcleo está siempre en el núcleo, y puesto que el núcleo está contenido en el conjunto de negociación, siempre está en el conjunto de negociación (ver (Driessen 1988) para detalles.)

Juegos cooperativos convexos

Presentado por Shapley in (Shapley 1971), los juegos de cooperación convexa capturan la propiedad intuitiva algunos juegos tienen de "snowballing". Específicamente, un juego es convex si su función característica ${displaystyle v}$ es supermodular:

${displaystyle v(Scup T)+v(Scap T)geq v(S)+v(T),forall ~S,Tsubseteq N.}$

Se puede mostrar (véase, por ejemplo, la sección V.1 de (Driessen 1988) que la supermodularidad de ${displaystyle v}$ equivale a

${displaystyle v(Scup {i})-v(S)leq v(Tcup {i})-v(T),forall ~Ssubseteq Tsubseteq Nsetminus {i},forall ~iinall N;}$

es decir, "los incentivos para unirse a una coalición aumentan a medida que ésta crece" (Shapley 1971), dando lugar 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 trivialmente implica superadditividad.
• Juegos Convex son totalmente equilibrado: El núcleo de un juego convexo no es vacío, y como cualquier subjuego de un juego convexo es convexo, el núcleo de cualquier subjuego es también no 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 (vertex) del núcleo se puede encontrar en el tiempo polinomio utilizando el algoritmo codicioso: Vamos. ${displaystyle pi:Nto N}$ ser una permutación de los jugadores, y dejar ${displaystyle S_{i}={jin N:pi (j)leq i}$ ser el conjunto de jugadores ordenados ${displaystyle 1}$ a través de ${displaystyle i}$ dentro ${displaystyle pi}$, para cualquier ${displaystyle i=0,ldotsn}$Con ${displaystyle S_{0}=emptyset }$. Entonces el pago ${displaystyle xin mathbb {R} {N}$ definidas por ${displaystyle x_{i}=v(S_{pi (i)})-v(S_{pi (i)-1}),forall ~iin N}$ es un vértice del núcleo ${displaystyle v}$. Cualquier vértice del núcleo se puede construir de esta manera eligiendo una permutación apropiada ${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 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 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. 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.