Juego hedónico

En la teoría de juegos cooperativos , un juego hedónico ^{[ 1 ] [ 2 ]} (también conocido como juego de formación de coaliciones hedónicas ) es un juego que modela la formación de coaliciones (grupos) de jugadores cuando estos tienen preferencias sobre a qué grupo pertenecen. Un juego hedónico se especifica dando un conjunto finito de jugadores y, para cada jugador, una clasificación de preferencias sobre todas las coaliciones (subconjuntos) de jugadores a las que pertenece. El resultado de un juego hedónico consiste en una partición de los jugadores en coaliciones disjuntas , es decir, a cada jugador se le asigna un grupo único. Dichas particiones se conocen a menudo como estructuras de coalición.

Los juegos hedónicos son un tipo de juego de utilidad no transferible . Su característica distintiva (el "aspecto hedónico" ^{[ 3 ]} ) es que a los jugadores solo les importa la identidad de los jugadores de su coalición, pero no les importa cómo se reparten los demás jugadores, ni nada más que quiénes forman parte de su coalición. Por lo tanto, a diferencia de otros juegos cooperativos , una coalición no elige cómo asignar las ganancias entre sus miembros, ni elige una acción particular para jugar. Algunas subclases bien conocidas de juegos hedónicos son los problemas de emparejamiento, como el matrimonio estable , los compañeros de habitación estables y los problemas de hospital/residentes .

En los juegos hedónicos, se suele entender que los jugadores actúan por interés propio, por lo que estos juegos se analizan generalmente en términos de la estabilidad de las estructuras de coalición, donde se utilizan diversas nociones de estabilidad, como la estabilidad del núcleo y la estabilidad de Nash . Los juegos hedónicos se estudian tanto en economía , donde el enfoque se centra en identificar condiciones suficientes para la existencia de resultados estables, como en sistemas multiagente , donde el enfoque se centra en identificar representaciones concisas de los juegos hedónicos y en la complejidad computacional de encontrar resultados estables. ^{[ 2 ]}

Formalmente, un juego hedónico es un par${\displaystyle (N,(\succcurlyeq _{i})_{i\in N})}$de un conjunto finito${\displaystyle N}$de jugadores (o agentes) y, para cada jugador${\displaystyle i\in N}$una relación de preferencia completa y transitiva${\displaystyle \succcurlyeq _{i}}$sobre el conjunto${\displaystyle \{S\subseteq N:i\in S\}}$de coaliciones que el jugador${\displaystyle i}$pertenece a. Una coalición es un subconjunto${\displaystyle S\subsetequ N}$del conjunto de jugadores. La coalición${\displaystyle N}$Normalmente se la denomina gran coalición .

Una estructura de coalición${\displaystyle \pi }$es una partición de${\displaystyle N}$Por lo tanto, cada jugador${\displaystyle i\in N}$pertenece a una coalición única${\displaystyle \pi (i)}$en${\displaystyle \pi }$.

Al igual que en otras áreas de la teoría de juegos, los resultados de los juegos hedónicos se evalúan mediante conceptos de solución. Muchos de estos conceptos hacen referencia a la noción de estabilidad en la teoría de juegos: un resultado es estable si ningún jugador (o posiblemente ninguna coalición de jugadores) puede desviarse del resultado para alcanzar uno subjetivamente mejor. Aquí presentamos definiciones de varios conceptos de solución extraídos de la literatura. ^{[ 1 ] [ 2 ]}

• Una estructura de coalición${\displaystyle \pi }$está en el núcleo (o es estable en el núcleo) si no hay coalición${\displaystyle S}$cuyos miembros prefieren${\displaystyle S}$a${\displaystyle \pi }$Formalmente, una coalición no vacía${\displaystyle S}$Se dice que bloquea${\displaystyle \pi }$si${\displaystyle S\succ _{i}\pi (i)}$a pesar de${\displaystyle i\in S}$. Entonces${\displaystyle \pi }$está en el núcleo si no hay coaliciones que lo bloqueen.
• Una estructura de coalición${\displaystyle \pi }$está en el núcleo estricto (o es estrictamente estable en el núcleo) si no hay una coalición de bloqueo débil.${\displaystyle S}$donde todos los miembros prefieren débilmente${\displaystyle S}$a${\displaystyle \pi }$y algunos miembros prefieren estrictamente${\displaystyle S}$a${\displaystyle \pi }$. En otras palabras,${\displaystyle \pi }$está en el núcleo estricto si${\displaystyle \not \exists :S\subseteq N:(\forall i\in N:S\succeq \pi )\land (\exists i\in N:S\succ \pi )}$.
• Una estructura de coalición${\displaystyle \pi }$es Nash-estable si ningún jugador desea cambiar de coalición dentro${\displaystyle \pi }$Formalmente,${\displaystyle \pi }$es Nash-estable si no hay${\displaystyle i\in N}$de tal manera que${\displaystyle S\cup \{i\}\succ _{i}\pi (i)}$para algunos${\displaystyle S\in \pi \cup \{\emptyset \}}$Nótese que, según la estabilidad de Nash, se permite una desviación por parte de un jugador incluso si los miembros del grupo${\displaystyle S}$que se unen por${\displaystyle i}$La desviación los perjudica.
• Una estructura de coalición${\displaystyle \pi }$es individualmente estable si ningún jugador desea unirse a otra coalición cuyos miembros dan la bienvenida al jugador. Formalmente,${\displaystyle \pi }$es individualmente estable si no hay${\displaystyle i\in N}$de tal manera que${\displaystyle S\cup \{i\}\succ _{i}\pi (i)}$para algunos${\displaystyle S\in \pi \cup \{\emptyset \}}$dónde${\displaystyle S\cup \{i\}\succeq _{j}S}$a pesar de${\displaystyle j\in S}$.
• Una estructura de coalición${\displaystyle \pi }$es contractualmente estable individualmente si no hay ningún jugador que pertenezca a una coalición dispuesta a dejarlo ir y que quiera unirse a una coalición dispuesta a tenerlo. En otras palabras,${\displaystyle \pi }$es contractualmente estable individualmente si${\displaystyle \not \exists i\in N:(\forall j\in \pi (i):\pi (i)\setminus \{i\}\succeq _{j}\pi (i))~\land ~(\exists C\in \pi$ :(C\cup \{i\}\succ _{i}\pi (i))~\land ~(\forall j\in C:C\cup \{i\}\succeq _{j}C))} .

También se puede definir la optimalidad de Pareto de una estructura de coalición. ^{[ 4 ]} En el caso de que las relaciones de preferencia estén representadas por funciones de utilidad , también se pueden considerar estructuras de coalición que maximicen el bienestar social.

El siguiente juego para tres jugadores se ha denominado " un invitado no deseado ". ^{[ 1 ]}$${\displaystyle {\begin{aligned}&\{1,2\}\succ _{1}\{1\}\succ _{1}\{1,2,3\}\succ _{1}\{1,3\},\\&\{1,2\}\succ _{2}\{2\}\succ _{2}\{1,2,3\}\succ _{2}\{2,3\},\\&\{1,2,3\}\succ _{3}\{2,3\}\succ _{3}\{1,3\}\succ _{3}\{3\}.\end{aligned}}}$$A partir de estas preferencias, podemos ver que${\displaystyle 1}$y${\displaystyle 2}$Se caen bien, pero les disgusta la presencia del jugador.${\displaystyle 3}$.

Consideremos la partición${\displaystyle \pi =\{\{1,2\},\{3\}\}}$. Observe que en${\displaystyle \pi }$El jugador 3 preferiría unirse a la coalición.${\displaystyle \{1,2\}}$, porque${\displaystyle \{1,2,3\}\succ _{3}\{3\}}$y por lo tanto${\displaystyle \pi }$no es estable en el sentido de Nash. Sin embargo, si el jugador${\displaystyle 3}$debían unirse${\displaystyle \{1,2\}}$, jugador${\displaystyle 1}$(y también jugador${\displaystyle 2}$) se vería perjudicado por esta desviación, y por lo tanto el jugador${\displaystyle 3}$La desviación de no contradice la estabilidad individual. De hecho, se puede comprobar que${\displaystyle \pi }$es individualmente estable. También podemos ver que no hay grupo${\displaystyle S\subsetequ N}$de jugadores de tal manera que cada miembro de${\displaystyle S}$prefiere${\displaystyle S}$a su coalición en${\displaystyle \pi }$y por lo tanto la partición también está en el núcleo.

Otro ejemplo de tres jugadores se conoce como " dos son compañía, tres son multitud ". ^{[ 1 ]}$${\displaystyle {\begin{aligned}&\{1,2\}\succ _{1}\{1,3\}\succ _{1}\{1,2,3\}\succ _{1}\{1\},\\&\{2,3\}\succ _{2}\{2,1\}\succ _{2}\{1,2,3\}\succ _{2}\{2\},\\&\{3,1\}\succ _{3}\{3,2\}\succ _{3}\{1,2,3\}\succ _{3}\{3\}.\end{aligned}}}$$En este juego, ninguna partición es estable en el núcleo: La partición${\displaystyle \{\{1\},\{2\},\{3\}\}}$(donde todos están solos) está bloqueado por${\displaystyle \{1,2,3\}}$; la partición${\displaystyle \{\{1,2,3\}\}}$(donde todos están juntos) está bloqueado por${\displaystyle \{1,2\}}$; y las particiones que constan de un par y un único elemento están bloqueadas por otro par, porque las preferencias contienen un ciclo.

Dado que las relaciones de preferencia en un juego hedónico se definen sobre la colección de todos${\displaystyle 2^{|N|-1}}$Al almacenar subconjuntos del conjunto de jugadores, un juego hedónico requiere un espacio exponencial. Esto ha inspirado diversas representaciones de juegos hedónicos concisas, en el sentido de que (a menudo) solo requieren un espacio polinomial .

• Las listas de coaliciones racionales individuales ^{[ 5 ]} representan un juego hedónico al enumerar explícitamente las clasificaciones de preferencia de todos los agentes, pero solo enumeran las coaliciones racionales individuales, es decir, las coaliciones${\displaystyle S}$con${\displaystyle S\succcurlyeq _{i}\{i\}}$Para muchos conceptos de solución, es irrelevante cómo el jugador clasifique con precisión las coaliciones inaceptables, ya que ninguna estructura de coalición estable puede contener una coalición que no sea individualmente racional para uno de los jugadores. Cabe señalar que si solo existen un número polinomial de coaliciones individualmente racionales, esta representación solo requiere un espacio polinomial.
• Las redes de coalición hedónicas ^{[ 6 ]} representan juegos hedónicos a través de fórmulas booleanas ponderadas . Como ejemplo, la fórmula ponderada${\displaystyle j\land \lnot k\mapsto _{i}5}$significa que el jugador${\displaystyle i}$recibe 5 puntos de utilidad en coaliciones que incluyen${\displaystyle j}$pero no incluya${\displaystyle k}$. Este formalismo de representación es universalmente expresivo y a menudo conciso ^{[ 6 ]} (aunque, por necesidad, hay algunos juegos hedónicos cuya representación de la red de coalición hedónica requiere un espacio exponencial).
• Los juegos hedónicos aditivamente separables ^{[ 1 ]} se basan en que cada jugador asigna valores numéricos a los demás jugadores; una coalición es tan buena para un jugador como la suma de los valores de los jugadores. Formalmente, los juegos hedónicos aditivamente separables son aquellos para los que existen valoraciones.${\displaystyle v_{i}(j)\in \mathbb {R} }$por cada${\displaystyle i,j\in N}$de tal manera que para todos los jugadores${\displaystyle i}$y todas las coaliciones${\displaystyle S,T\ni i}$, tenemos${\displaystyle S\succcurlyeq _{i}T}$si y solo si${\displaystyle \textstyle \sum _{j\in S}v_{i}(j)\geq \textstyle \sum _{j\in T}v_{i}(j)}$. Una definición similar, que utiliza el promedio en lugar de la suma de valores, conduce a la clase de juegos hedónicos fraccionarios. ^{[ 7 ]}
• En los juegos hedónicos anónimos , ^{[ 8 ]} a los jugadores solo les importa el tamaño de su coalición, y los agentes son indiferentes entre cualesquiera dos coaliciones con la misma cardinalidad: si${\displaystyle |S|=|T|}$entonces${\displaystyle S\sim _{i}T}$Estos juegos son anónimos en el sentido de que la identidad de los individuos no influye en la clasificación de preferencias.
• En los juegos hedónicos booleanos , ^{[ 9 ]} cada jugador tiene una fórmula booleana cuyas variables son los demás jugadores. Cada jugador prefiere las coaliciones que satisfacen su fórmula a las que no la satisfacen, pero por lo demás es indiferente.
• En los juegos hedónicos con preferencias que dependen del peor jugador (o preferencias W ^{[ 10 ]} ), los jugadores tienen una clasificación de preferencias sobre los jugadores y extienden esta clasificación a las coaliciones evaluando una coalición según el peor jugador (subjetivamente) de la misma. Se han definido varios conceptos similares (como las preferencias B ). ^{[ 11 ] [ 12 ] [ 13 ]}

No todos los juegos hedónicos admiten una estructura de coalición estable. Por ejemplo, podemos considerar el juego del acosador , que consta de solo dos jugadores.${\displaystyle N=\{1,2\}}$con${\displaystyle \{1\}\succ _{1}\{1,2\}}$y${\displaystyle \{1,2\}\succ _{2}\{2\}}$Aquí, llamamos al jugador 2 el acosador . Nótese que ninguna estructura de coalición para este juego es Nash-estable: en la estructura de coalición${\displaystyle \pi _{1}=\{\{1\},\{2\}\}}$donde ambos jugadores están solos, el acechador 2 se desvía y se une a 1; en la estructura de coalición${\displaystyle \pi _{2}=\{\{1,2\}\}}$En el caso donde los jugadores están juntos, el jugador 1 se desvía hacia la coalición vacía para no estar con el acosador. Existe un ejemplo bien conocido del problema de compañeros de habitación estables con 4 jugadores que tiene un núcleo vacío, ^{[ 14 ]} y también existe un juego hedónico aditivamente separable con 5 jugadores que tiene un núcleo vacío y no tiene estructuras de coalición individualmente estables. ^{[ 15 ]}

Para juegos hedónicos simétricos aditivamente separables (aquellos que satisfacen${\displaystyle v_{i}(j)=v_{j}(i)}$a pesar de${\displaystyle i,j\in N}$), siempre existe una estructura de coalición estable de Nash mediante un argumento de función potencial . En particular, las estructuras de coalición que maximizan el bienestar social son estables de Nash. ^{[ 1 ]} Un argumento similar muestra que siempre existe una estructura de coalición estable de Nash en la clase más general de juegos hedónicos neutrales a subconjuntos . ^{[ 16 ]} Sin embargo, hay ejemplos de juegos hedónicos simétricos aditivamente separables que tienen núcleo vacío. ^{[ 8 ]}

Se han identificado varias condiciones que garantizan la existencia de una estructura de coalición central. Este es el caso, en particular, de los juegos hedónicos con la propiedad de clasificación común, ^{[ 17 ] [ 18 ]} con la propiedad de coalición superior, ^{[ 8 ]} con capacidad de respuesta superior o inferior, ^{[ 19 ]} con preferencias separables descendentes, ^{[ 20 ] [ 21 ]} y con preferencias dicotómicas . ^{[ 9 ]} Además, se ha demostrado que la propiedad de clasificación común garantiza la existencia de una estructura de coalición que es estable en el núcleo, estable individualmente y óptima de Pareto al mismo tiempo. ^{[ 22 ]}

Al considerar los juegos hedónicos, el campo de la teoría de juegos algorítmica suele interesarse en la complejidad del problema de encontrar una estructura de coalición que satisfaga un concepto de solución determinado cuando se le da un juego hedónico como entrada (en alguna representación concisa). ^{[ 2 ]} Dado que generalmente no se garantiza que un juego hedónico dado admita un resultado estable, estos problemas a menudo se pueden formular como un problema de decisión que pregunta si un juego hedónico dado admite algún resultado estable. En muchos casos, este problema resulta ser computacionalmente intratable. ^{[ 18 ] [ 23 ]} Las excepciones incluyen juegos hedónicos con propiedad de clasificación común donde siempre existe una estructura de coalición central, y se puede encontrar en tiempo polinomial. ^{[ 17 ]} Sin embargo, sigue siendo NP-difícil encontrar un resultado óptimo de Pareto o socialmente óptimo. ^{[ 22 ]}

En particular, para juegos hedónicos dados por listas de coaliciones individualmente racionales, es NP-completo decidir si el juego admite un resultado estable en el núcleo, un resultado estable en Nash o un resultado individualmente estable. ^{[ 5 ]} Lo mismo es cierto para juegos anónimos. ^{[ 5 ]} Para juegos hedónicos aditivamente separables, es NP-completo decidir la existencia de un resultado estable en Nash o un resultado individualmente estable ^{[ 15 ]} y completo para el segundo nivel de la jerarquía polinomial decidir si existe un resultado estable en el núcleo, ^{[ 24 ]} incluso para preferencias aditivas simétricas. ^{[ 25 ]} Estos resultados de dificultad se extienden a juegos dados por redes de coaliciones hedónicas. Si bien se garantiza la existencia de resultados estables en Nash e individualmente estables para juegos hedónicos aditivamente separables simétricos , encontrar uno aún puede ser difícil si las valoraciones${\displaystyle v_{i}(j)}$se dan en binario; el problema es PLS-completo . ^{[ 26 ]} Para el problema del matrimonio estable, se puede encontrar un resultado núcleo-estable en tiempo polinomial usando el algoritmo de aceptación diferida ; para el problema de compañeros de habitación estables, la existencia de un resultado núcleo-estable se puede decidir en tiempo polinomial si las preferencias son estrictas, ^{[ 27 ]} pero el problema es NP-completo si se permiten empates de preferencia. ^{[ 28 ]} Los juegos hedónicos con preferencias basadas en el peor jugador se comportan de manera muy similar a los problemas de compañeros de habitación estables con respecto al núcleo, ^{[ 10 ]} pero hay resultados de dificultad para otros conceptos de solución. ^{[ 13 ]} Muchos de los resultados de dificultad anteriores se pueden explicar a través de metateoremas sobre la extensión de preferencias sobre jugadores individuales a coaliciones. ^{[ 23 ]}