Cálculo del núcleo en un juego de utilidad transferible

Question

Una asignación $x^{*}$ se dice que tiene la propiedad central en un juego de $N$ jugadores si no hay coalición $S \subseteq N$ que puede mejorar $x^{*}$ . El núcleo de un juego es el conjunto de asignaciones con la propiedad de núcleo.

Ahora, una coalición $S$ bloqueará una asignación $x$ si existe un $\widetilde{x}$ tal que $\widetilde{x} \succ_{s} x$ para todos $s \in S$ .

En la práctica, para determinar el núcleo de un juego cooperativo solemos tener que calcular las asignaciones que cualquier coalición $S$ no se bloqueará (es decir, las asignaciones que no se pueden mejorar). Si denotamos esta asignación como $A_{S}$ entonces podemos escribir la asignación de núcleos $\mathcal{C}$ como $$\mathcal{C} = \bigcap_{S \in 2^{N}} A_{S} $$

Ahora bien, en cualquier juego con más de dos jugadores puede ser tedioso calcular el núcleo.

Me pregunto, si sabía que el juego era un juego de utilidad transferible ¿hay alguna forma de calcular el núcleo de forma más eficiente?

Se trata sobre todo de una pregunta sobre las consecuencias de que un juego sea un juego de utilidad transferible, y si esto proporciona alguna información que sea útil para calcular el núcleo. Aunque estoy familiarizado con la definición de utilidad transferible, nunca me sentí muy cómodo con sus implicaciones prácticas para el juego.

Answer 1

Depende del conjunto de asignaciones factibles para las coaliciones $S$ . Supongamos que para todo $S$ existe un reparto óptimo (la suma de las utilidades individuales de los miembros de $S$ es máxima). Entonces, como en los juegos cooperativos habituales, a cada coalición se le puede asignar esta suma de mejor utilidad como su valor $v(S)$ . Denotemos el vector de utilidad que cada jugador obtiene de una asignación por $x$ y la suma de las utilidades que obtienen los jugadores por $x(S)$ . Una asignación está en el núcleo si $$ \forall S\subseteq N: x(S) \geq v(S). $$ Esto es una ligera simplificación de lo que has escrito, porque en lugar de comparar todas las asignaciones con $x$ primero encontramos las "mejores" asignaciones para cada coalición y sólo las comparamos con $x$ .

Si haces más suposiciones sobre los valores de la coalición $v$ Por ejemplo, si se asume que el juego es convexo (esto es cierto para las economías de intercambio) entonces el cálculo puede simplificarse un poco, ya que el núcleo de un juego convexo es el conjunto Weber.

Answer 2

El cálculo de los equilibrios es un área de investigación activa. Grandes teóricos de la complejidad, como Lance Fortnow, trabajan en este campo. Cuando se tiene continuidad, el cálculo de la asignación de núcleos es mucho más fácil, ya que normalmente podemos describir el núcleo como un programa lineal.

Cuando las asignaciones factibles son discretas, nos encontramos con problemas de complejidad. Decidir si el núcleo no está vacío es NP-Hard. Sin embargo, si se le da el valor de la gran coalición y todos los pares de valores de la coalición, entonces el problema está en P. No es realista esperar esta cantidad de información sin embargo.

Algunas notas de clase relevantes: http://www.cs.cmu.edu/~arielpro/mfai_papers/lecture11.pdf