Teoría de juegos cooperativos

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

${\displaystyle v(S\cup T)\geq v(S)+v(T)}$cuando sea${\displaystyle S,T\subseteq N}$satisfacer${\displaystyle S\cap T=\emptyset }$.

Las coaliciones más grandes obtienen mayores beneficios:

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

Esto se deduce de la superaditividad , es decir, si las recompensas se normalizan de modo que las coaliciones singleton tengan valor cero.

Un juego de coalición v se considera simple si las recompensas son 1 o 0, es decir, las coaliciones están "ganando" o "perdiendo". ^{[ 7 ]}

De forma 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 asume 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 es ganadora, es decir, si${\displaystyle S\in W}$y${\displaystyle S\subseteq T}$implicar${\displaystyle T\in W}$.
• Un juego simple W es propio si el complemento (oposición) de cualquier coalición ganadora es perdedora, es decir, si${\displaystyle S\in W}$implica${\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${\displaystyle S\notin W}$implica${\displaystyle N\setminus S\en W}$.
  • Si un juego simple W es apropiado y fuerte, entonces una coalición está ganando si y solo si su complemento está perdiendo, es decir,${\displaystyle S\in W}$si y solo si ${\displaystyle N\setminus S\notin W}$. (Si v es un juego simple de coalición que es propio y fuerte,${\displaystyle v(S)=1-v(N\setminus S)}$para cualquier S .)
• Un jugador con derecho a veto (vetador) en un juego simple es un jugador que pertenece a todas las coaliciones ganadoras. Suponiendo que existe un jugador con derecho a veto, cualquier coalición que no lo contenga está perdiendo. Un juego simple W es débil ( colegial ) si tiene un jugador con derecho a veto, es decir, si la intersección${\displaystyle \bigcap W:=\bigcap _ {S\in W}S}$de todas las coaliciones ganadoras no está vacío.
  • En un juego simple, un dictador es un jugador con derecho a veto, de modo que cualquier coalición que lo incluya resulta ganadora. El dictador no pertenece a ninguna coalición perdedora. ( Los juegos de dictador en economía experimental no guardan relación con esto).
• Un portador de un juego simple W es un conjunto${\displaystyle T\subsetequ N}$de tal manera que para cualquier coalición S , tenemos${\displaystyle S\in W}$si y solo si${\displaystyle S\cap T\in W}$Cuando un juego simple tiene un portador, cualquier jugador que no pertenezca a él es ignorado. Un juego simple a veces se denomina finito si tiene un portador 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, este número mide el grado de racionalidad; es un indicador de hasta qué punto una regla de agregación puede generar elecciones bien definidas.

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

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

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

También se estudiaron extensamente las restricciones que varios axiomas para juegos simples imponen a su número de Nakamura . ^{[ 12 ]} 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 .

El conjunto estable de un juego (también conocido como la solución de von Neumann-Morgenstern ( von Neumann y Morgenstern, 1944 ) ) fue la primera solución propuesta para juegos con más de 2 jugadores.${\displaystyle v}$sea ​​un juego y déjalo${\displaystyle x}$,${\displaystyle y}$ser dos imputaciones de${\displaystyle v}$. Entonces${\displaystyle x}$domina${\displaystyle y}$si alguna coalición${\displaystyle S\neq \emptyset }$Satisface${\displaystyle x_{i}>y_{i},\forall ~i\in S}$y${\displaystyle \sum _{i\in S}x_{i}\leq v(S)}$En otras palabras, los jugadores en${\displaystyle S}$prefiero los pagos de${\displaystyle x}$a aquellos de${\displaystyle y}$y pueden amenazar con abandonar la gran coalición si${\displaystyle y}$se utiliza porque la recompensa que obtienen por sí mismos es al menos tan grande como la asignación que reciben en${\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 que se encuentran fuera del conjunto están dominados por al menos un vector que pertenece al conjunto.

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

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

${\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 reside en el conjunto de supuestos bajo los cuales ninguna coalición tiene un valor superior a la suma de las ganancias de sus miembros. Por lo tanto, ninguna coalición tiene incentivos para abandonar la gran coalición y obtener una mayor ganancia.

Para juegos simples, existe otra noción del núcleo, cuando se supone que cada jugador tiene preferencias sobre un conjunto${\displaystyle X}$de alternativas. Un perfil es una lista${\displaystyle p=(\succ _{i}^{p})_{i\in N}}$de preferencias individuales${\displaystyle \succ _{i}^{p}}$en${\displaystyle X}$. Aquí${\displaystyle x\succ _{i}^{p}y}$significa que el individuo${\displaystyle i}$prefiere alternativa${\displaystyle x}$ a${\displaystyle y}$en el perfil${\displaystyle p}$Dado un juego sencillo${\displaystyle v}$y un perfil${\displaystyle p}$, una relación de dominancia${\displaystyle \succ _{v}^{p}}$se define en${\displaystyle X}$por${\displaystyle x\succ _{v}^{p}y}$Si y solo si hay una coalición ganadora${\displaystyle S}$ (es decir,${\displaystyle v(S)=1}$) satisfactorio${\displaystyle x\succ _{i}^{p}y}$a pesar de${\displaystyle i\in S}$El núcleo${\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 _{v}^{p}}$ (el conjunto de elementos máximos de${\displaystyle X}$con respecto a${\displaystyle \succ _{v}^{p}}$):

${\displaystyle x\in C(v,p)}$si y solo si no hay${\displaystyle y\in X}$de tal manera que${\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${\displaystyle C(v,p)}$no está vacío para todos los perfiles${\displaystyle p}$de preferencias acíclicas (o transitivas ) si y solo si${\displaystyle X}$es finito y el número cardinal (el número de elementos) de${\displaystyle X}$es menor que el número de Nakamura de${\displaystyle v}$Una variante de Kumabe y Mihara afirma que el núcleo${\displaystyle C(v,p)}$no está vacío para todos los perfiles${\displaystyle p}$de preferencias que tienen un elemento máximo si y solo si el número cardinal de${\displaystyle X}$es menor que el número de Nakamura de${\displaystyle v}$(Para más detalles, consulte el número de Nakamura ).

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

${\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 fuerte${\displaystyle \varepsilon }$-core es el conjunto de preimputaciones donde ninguna coalición puede mejorar su recompensa abandonando la gran coalición, si debe pagar una penalización de${\displaystyle \varepsilon }$por marcharse.${\displaystyle \varepsilon }$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 fuerte${\displaystyle \varepsilon }$-core no estará vacío para un valor suficientemente grande de${\displaystyle \varepsilon }$y vacío para un valor suficientemente pequeño (posiblemente negativo) de${\displaystyle \varepsilon }$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 conjuntos fuertes no vacíos.${\displaystyle \varepsilon }$-núcleos. También puede verse como el fuerte${\displaystyle \varepsilon }$-núcleo para el valor más pequeño de${\displaystyle \varepsilon }$eso hace que el conjunto no esté vacío ( Bilbao 2000 ) .

El valor de Shapley es el único vector de pagos que es eficiente, simétrico y satisface la monotonicidad. ^{[ 15 ]} 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 )

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

${\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 demás 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${\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, el 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)>s_{ji}^{v}(x)}$, pero el jugador j es inmune a las amenazas del jugador i si${\displaystyle x_{j}=v(j)}$, porque puede obtener esta recompensa por sí mismo. 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 y Maschler 1965 ) .

El dividendo de Harsanyi (llamado así en honor a John Harsanyi , quien lo utilizó para generalizar el valor de Shapley en 1963 ^{[ 16 ]} ) 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 restando el excedente que ya fue creado por las subcoaliciones. Con este fin, el dividendo${\displaystyle d_{v}(S)}$de coalición${\displaystyle S}$en el juego${\displaystyle v}$se determina recursivamente por

${\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${\textstyle d_{v}(S)=\sum _{T\subseteq S}(-1)^{|S\setminus T|}v(T)}$. La función${\displaystyle d_{v}:2^{N}\to \mathbb {R} }$también se conoce como la inversa de Möbius de${\displaystyle v:2^{N}\to \mathbb {R} }$. ^{[ 17 ]} De hecho, podemos recuperar${\displaystyle v}$de${\displaystyle d_{v}}$con ayuda de la fórmula${\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.${\displaystyle \phi _{i}(v)}$del jugador${\displaystyle i}$en el juego${\displaystyle v}$se obtiene sumando la parte que le corresponde a un jugador de los dividendos de todas las coaliciones a las que pertenece,${\textstyle \phi _{i}(v)=\sum _{S\subset N:i\in S}{d_{v}(S)}/{|S|}}$.

Dejar${\displaystyle v:2^{N}\to \mathbb {R} }$sea ​​un juego, y déjalo${\displaystyle x\in \mathbb {R} ^{N}}$ser un vector de pago. El exceso de${\displaystyle x}$para una coalición${\displaystyle S\subseteq N}$es la cantidad${\displaystyle v(S)-\sum _{i\in S}x_{i}}$; es decir, la ganancia que obtienen los jugadores en coalición${\displaystyle S}$pueden obtenerlo si se retiran de la gran coalición.${\displaystyle N}$bajo pago${\displaystyle x}$y en su lugar, tomar la recompensa${\displaystyle v(S)}$. El nucléolo de${\displaystyle v}$es la imputación para la cual el vector de excesos de todas las coaliciones (un vector en${\displaystyle \mathbb {R} ^{2^{N}}}$) es el más pequeño en el orden de las leximinas . El nucléolo fue introducido en ( Schmeidler 1969 ) .

( Maschler, Peleg y Shapley 1979 ) dieron una descripción más intuitiva: Comenzando con el núcleo más pequeño, registre las coaliciones para las cuales el lado derecho de la desigualdad en la definición de${\displaystyle C_{\varepsilon }(v)}$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 se mantienen 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.

Los juegos cooperativos convexos tienen muchas propiedades interesantes:

• La supermodularidad implica trivialmente la superaditividad .
• Los juegos convexos están totalmente equilibrados : el núcleo de un juego convexo no es vacío, y dado que cualquier subjuego de un juego convexo es convexo, el núcleo de cualquier subjuego tampoco es 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${\displaystyle \pi :N\to N}$sea ​​una permutación de los jugadores, y deje que${\displaystyle S_{i}=\{j\in N:\pi (j)\leq i\}}$ser el conjunto de jugadores ordenados${\displaystyle 1}$a través de${\displaystyle i}$en${\displaystyle \pi }$, para cualquier${\displaystyle i=0,\ldots ,n}$, con${\displaystyle S_{0}=\emptyset }$. Luego la recompensa${\displaystyle x\in \mathbb {R} ^{N}}$definido por${\displaystyle x_{i}=v(S_{\pi (i)})-v(S_{\pi (i)-1}),\forall ~i\in N}$es un vértice del núcleo de${\displaystyle v}$Cualquier vértice del núcleo puede construirse de esta manera eligiendo una permutación adecuada.${\displaystyle \pi }$.

Las funciones de conjuntos 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 costo convexo se denomina poliedro base , porque sus elementos generalizan propiedades básicas de los matroides .

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

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

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

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

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

• Lovász, László (1983), "Funciones submodulares y convexidad", en Bachem, A.; Grötschel, M .; Korte, B. (eds.), Programación matemática: estado del arte , Berlín: Springer, pp . 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-1Introducción matemática de 88 páginas; véase el capítulo 8. Disponible gratuitamente en línea (se requiere suscripción). Archivado el 15 de agosto de 2000 en la Wayback Machine de 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: una introducción y un análisis 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 nucleolo y conceptos de solución relacionados", Mathematics of Operations Research , 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 y 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 núcleo de un juego de función característica", SIAM Journal on Applied Mathematics , 17 (6): 1163– 1170, doi : 10.1137/0117107 .

• Shapley, Lloyd S. (1953), "Un valor para${\displaystyle n}$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 . 307–317 

• Shapley, Lloyd S. (18 de marzo de 1952), Un valor para juegos de N personas , 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, de teoría de juegos y lógicos , Nueva York: Cambridge University Press , ISBN 978-0-521-89943-7. Una referencia completa desde una perspectiva computacional; véase el Capítulo 12. Descargable gratuitamente en línea .

• von Neumann, John ; Morgenstern, Oskar (1944), "Teoría de los juegos y el 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 (Springer Series in Operations Research and Financial Engineering), 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