Nucleolo (teoría de juegos)

En la teoría de juegos cooperativos , el nucléolo de un juego cooperativo es la solución (es decir, la asignación de pagos a los jugadores) que maximiza el exceso más pequeño de una coalición (donde el exceso es la diferencia entre el pago dado a la coalición y el valor que la coalición podría obtener al desviarse). Sujeto a eso, el nucléolo satisface el segundo exceso más pequeño; y así sucesivamente, en el orden leximin . El nucléolo fue introducido por David Schmeidler . ^[1]

Fondo

En un juego cooperativo , hay un conjunto N de jugadores que pueden cooperar y formar coaliciones . Cada coalición S (subconjunto de jugadores) tiene un valor , que es la ganancia que S puede obtener si coopera por su cuenta, ignorando a los otros jugadores en N. Los jugadores optan por formar la gran coalición , una coalición que contiene a todos los jugadores en N. Entonces surge la pregunta, ¿cómo debería distribuirse el valor de la gran coalición entre los jugadores? Cada una de estas asignaciones de valor se denomina solución o vector de pagos .

El exceso de cualquier coalición S respecto de un vector de pagos x dado es la diferencia entre el pago total a los miembros de S en x y el valor de S. Nótese que el exceso puede ser positivo, negativo o cero. Intuitivamente, una solución en la que todas las coaliciones tienen un exceso mayor es más estable, ya que las coaliciones tienen menos incentivos para desviarse de la gran coalición.

El nucléolo es una solución única, para la cual el vector de excesos de todas las coaliciones es mayor en el orden leximin . Intuitivamente, el nucléolo maximiza la estabilidad de la solución al minimizar los incentivos de las coaliciones a desviarse.

Definiciones

Un juego cooperativo se representa mediante una función de valor , que asigna un valor a cada posible coalición (cada subconjunto de jugadores). Una solución de un juego cooperativo es un vector , que asigna un pago a cada jugador en N. Una solución debe satisfacer el requisito básico de eficiencia : la suma de los pagos debe ser exactamente igual a v ( N ), el valor de la gran coalición. Una solución de pago que satisface esta condición se denomina imputación . $v:2^{N}\to \mathbb {R}$ $x\in \mathbb {R} ^{N}$

El exceso de un vector de beneficios para una coalición es la cantidad . Es decir, la ganancia que obtienen los jugadores de la coalición si permanecen en la gran coalición y no se desvían. ^{[nota 1]} ${\estilo de visualización x}$ $S\subseteq N$ $\mathrm {exceso} (x,S):=\sum _{i\in S}x_{i}-v(S)$ ${\estilo de visualización S}$ ${\estilo de visualización N}$

Sea el vector de excesos de , ordenado en orden no decreciente: . Para dos vectores de pago , decimos que es lexicográficamente menor que si para algún índice , tenemos y . El nucléolo de es la imputación lexicográficamente más grande , con base en este ordenamiento. En otras palabras, el nucléolo es una imputación cuyo vector de excesos es más grande en el orden leximin . Puede representarse mediante el siguiente problema de optimización: donde k = 2 ^N = el número de posibles coaliciones. $\theta(x)\in \mathbb {R} ^{2^{N}}$ ${\estilo de visualización x}$ $\theta _{i}(x)\leq \theta _{j}(x),\forall ~i<j$ ${\estilo de visualización x,y}$ $\theta(x)$ $\theta(y)$ ${\estilo de visualización k}$ $\theta _{i}(x)=\theta _{i}(y),\forall ~i<k$ $\theta_{k}(x)<\theta_{k}(y)$ ${\estilo de visualización v}$ ${\begin{aligned}\operatorname {lex} \max \min &&\mathrm {exceso} (x,S_{1}),\mathrm {exceso} (x,S_{2}),\ldots ,\mathrm {exceso} (x,S_{k})\\{\text{sujeto a}}&&x~{\text{es una imputación}}\end{aligned}}$

Propiedades

El nucléolo es siempre único. Véase ^[1] y la Sección II.7 de ^[2] para una prueba.

Relación con otros conceptos de solución

El núcleo es, por definición, el conjunto de todas las imputaciones en las que el exceso de cada coalición es al menos 0. Por lo tanto, si el núcleo no está vacío, el nucléolo está en el núcleo.

Cuando el núcleo está vacío, es natural considerar una aproximación: el ε-núcleo es el conjunto de todas las imputaciones en las que el exceso de cada coalición es al menos - ε . Para cada ε, si el ε-núcleo no está vacío, entonces el nucléolo está en el ε-núcleo .
El núcleo mínimo es el núcleo ε no vacío más pequeño (para el ε más pequeño para el cual el núcleo ε no está vacío). El nucléolo siempre está en el núcleo mínimo. De hecho, el nucléolo puede verse como un refinamiento del núcleo mínimo. Comenzando con el núcleo mínimo, registre las coaliciones para las cuales el exceso es exactamente - ε . Encuentre un subconjunto del núcleo mínimo en el que el exceso más pequeño de las otras coaliciones sea lo más grande posible. Repita este proceso tantas veces como sea necesario hasta que se hayan registrado todas las coaliciones. El vector de resultados resultante es el nucléolo.
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 ^[2] para más detalles).

Cálculo

Juegos generales

Un juego cooperativo general entre n jugadores se caracteriza por 2 ⁿ valores - un valor para cada coalición posible. El nucléolo de un juego general se puede calcular mediante cualquier algoritmo de optimización lexicográfica máx-mín . Estos algoritmos suelen requerir la resolución de programas lineales con una restricción para cada valor objetivo, más algunas restricciones adicionales. Por lo tanto, el número de restricciones es O(2 ⁿ ). El número de iteraciones requeridas por los algoritmos más eficientes es como máximo n , por lo que el tiempo de ejecución es O( n 2 ⁿ ).

Si el juego cooperativo se da enumerando los valores de todas las coaliciones, entonces el tamaño de entrada es 2 ⁿ y, por lo tanto, los algoritmos anteriores se ejecutan en un tiempo polinomial en el tamaño de entrada. Pero cuando n es grande, incluso representar un juego de este tipo requiere un gran esfuerzo computacional y hay más interés en las clases de juegos cooperativos que tienen una representación compacta.

Juegos de votación ponderada

En un juego de votación ponderada , cada jugador tiene un peso. El peso de una coalición es la suma de los pesos de sus miembros. Una coalición puede forzar una decisión si su peso total es superior a un cierto umbral. Por lo tanto, el valor de una coalición es 1 si su valor es superior al umbral y 0 si su valor es inferior al umbral. Un juego de votación ponderada puede representarse con solo n +1 valores: un peso para cada jugador y el umbral.

En un juego de votación ponderada, el núcleo se puede calcular en un polinomio de tiempo en n . Por el contrario, el núcleo mínimo es NP-duro, pero tiene un algoritmo de tiempo pseudopolinomial : un algoritmo polinomial en n y el peso máximo W . ^[3] De manera similar, el nucléolo es NP-duro, ^[3] pero tiene un algoritmo de tiempo pseudopolinomial. ^[4] La prueba se basa en la resolución de programas lineales de tamaño exponencial sucesivos, mediante la construcción de oráculos de separación basados en programación dinámica .

Juegos de árboles de expansión de costo mínimo

En un juego de árbol de expansión de costo mínimo , cada jugador es un nodo en un gráfico completo . El gráfico contiene un nodo adicional s (el nodo de suministro ). Cada arista del gráfico tiene un costo. El costo de cada coalición S es el costo mínimo de un árbol de expansión que conecta todos los nodos en S al nodo de suministro s . El valor de S es menos el costo de S . Por lo tanto, un juego MCST puede representarse mediante valores O(n ^{2 ).}^[5]

Calcular el nucléolo en juegos MCST generales es NP-difícil, ^[6] pero se puede calcular en tiempo polinomial si la red subyacente es un árbol. ^[7]^[8]

Juegos de emparejamiento cooperativos ponderados

En los juegos cooperativos de emparejamiento ponderado, el nucléolo se puede calcular en tiempo polinomial. ^[9]

Función de valor dado implícitamente

En algunos juegos, el valor de cada coalición no se da explícitamente, pero se puede calcular resolviendo un conjunto de problemas de programación matemática. Utilizando un enfoque de generación de restricciones, es posible calcular solo los valores de las coaliciones que se requieren para el nucléolo. Esto permite calcular el nucléolo de manera eficiente en la práctica, cuando hay como máximo 20 jugadores. ^[10]

Potters, Reijnierse y Ansing ^[11] presentan un algoritmo rápido para calcular el nucléolo utilizando el algoritmo simplex prolongado .

Usando el prekernel

Si el prenúcleo de un juego cooperativo contiene exactamente un vector central, entonces el nucléolo se puede calcular de manera eficiente. ^[12] El algoritmo se basa en el método del elipsoide y en un esquema de Maschler para aproximar el prenúcleo.

Errores en el cálculo del nucléolo

Guajardo y Jornsten ^[13] han encontrado errores en la aplicación de la programación lineal y la dualidad para calcular el nucléolo.

Notas

^ Algunos artículos definen el exceso de S como el valor de S menos su pago total en x, es decir, la ganancia que S podría obtener desviándose. Según esta definición, el objetivo es minimizar el exceso más grande, en lugar de maximizar el exceso más pequeño.

Véase también

Normativa sobre prendas de vestir controvertida
El nucléolo vs. el núcleo mínimo ^[14]

Referencias

^ ab Schmeidler, D. (1969), "El nucléolo de un juego de funciones características", SIAM Journal on Applied Mathematics , 17 (6): 1163–1170, doi :10.1137/0117107.
^ ab Driessen, Theo (1988), Juegos cooperativos, soluciones y aplicaciones, Kluwer Academic Publishers, ISBN 9789401577878
^ ab Elkind, Edith; Goldberg, Leslie Ann; Goldberg, Paul; Wooldridge, Michael (22 de julio de 2007). "Complejidad computacional de juegos de umbral ponderado". Actas de la 22.ª Conferencia Nacional sobre Inteligencia Artificial - Volumen 1. AAAI'07. Vancouver, Columbia Británica, Canadá: AAAI Press: 718–723. ISBN 978-1-57735-323-2.
^ Elkind, Edith; Pasechnik, Dmitrii (4 de enero de 2009). Cálculo del nucléolo de los juegos de votación ponderada. Actas del Simposio anual ACM-SIAM de 2009 sobre algoritmos discretos (SODA). Sociedad de Matemáticas Industriales y Aplicadas. pp. 327–335. doi :10.1137/1.9781611973068.37. hdl : 10356/93815 . ISBN . 978-0-89871-680-1.
^ Bird, CG (1976). "Sobre la asignación de costos para un árbol de expansión: un enfoque de teoría de juegos". Redes . 6 (4): 335–350. doi :10.1002/net.3230060404.
^ Faigle, Ulrich; Kern, Walter; Kuipers, Jeroen (1998-12-01). "El cálculo del nucléolo de los juegos de árboles de expansión de coste mínimo es NP-hard". Revista internacional de teoría de juegos . 27 (3): 443–450. doi :10.1007/s001820050083. ISSN 0020-7276. S2CID 46730554.
^ Megiddo, Nimrod (agosto de 1978). "Complejidad computacional del enfoque de la teoría de juegos para la asignación de costos de un árbol". Matemáticas de la investigación de operaciones . 3 (3): 189–196. doi :10.1287/moor.3.3.189. ISSN 0364-765X.
^ Galil, Zvi (1980-01-01). "Aplicaciones de montículos fusionables eficientes para problemas de optimización en árboles". Acta Informatica . 13 (1): 53–58. doi :10.1007/BF00288535. ISSN 0001-5903. S2CID 39221796.
^ Könemann, Jochen; Pashkovich, Kanstantsin; Toth, Justin (1 de septiembre de 2020). "Cálculo del nucléolo de juegos de emparejamiento cooperativo ponderados en tiempo polinomial". Programación matemática . 183 (1): 555–581. arXiv : 1803.03249 . doi :10.1007/s10107-020-01483-4. ISSN 1436-4646. S2CID 254135686.
^ Hallefjord, Åsa; Helming, Reidun; Jørnsten, Kurt (1995-12-01). "Cálculo del nucléolo cuando la función característica se da implícitamente: un enfoque de generación de restricciones". Revista internacional de teoría de juegos . 24 (4): 357–372. doi :10.1007/BF01243038. ISSN 1432-1270. S2CID 122124918.
^ Potters, Jos AM; Reijnierse, Johannes H.; Ansing, Michel (agosto de 1996). "Cálculo del nucléolo mediante la resolución de un algoritmo símplex prolongado". Matemáticas de la investigación de operaciones . 21 (3): 757–768. doi :10.1287/moor.21.3.757. hdl : 2066/27990 . ISSN 0364-765X.
^ Faigle, Ulrich; Kern, Walter; Kuipers, Jeroen (1 de septiembre de 2001). "Sobre el cálculo del nucléolo de un juego cooperativo". Revista internacional de teoría de juegos . 30 (1): 79–98. doi :10.1007/s001820100065. ISSN 1432-1270. S2CID 17702694.
^ Guajardo, Mario; Jörnsten, Kurt (16 de marzo de 2015). "Errores comunes en el cálculo del nucléolo". Revista Europea de Investigación Operativa . 241 (3): 931–935. doi :10.1016/j.ejor.2014.10.037. hdl : 11250/194983 . ISSN 0377-2217.
^ Yan, Tom; Procaccia, Ariel D. (18 de mayo de 2021). "Si te gusta Shapley, entonces te encantará el núcleo". Actas de la Conferencia AAAI sobre Inteligencia Artificial . 35 (6): 5751–5759. doi : 10.1609/aaai.v35i6.16721 . ISSN 2374-3468.