¿Cómo se puede determinar la estricta núcleo en un juego?

Question

Así que tengo un juego en el que los dueños de casa prefieren ciertas casas. Los propietarios son a, B, C, y D con a, b, c, y d se refieren a sus respectivos hogares. Cada uno de ellos prefieren casas de acuerdo a la clasificación

A: bdac
B: cadb
C: dbca
D: acbd

He leído un artículo de Shapley acerca de un algoritmo para encontrar una asignación en el estricto core, pero me piden que "determinar el estricto core", que supongo significa encontrar todas las asignaciones en el estricto núcleo. Cómo se hace eso?

En caso de cualquier uso, voy a describir el algoritmo en el Shapley artículo. Hacer un gráfico de la gente de la cima de las preferencias y seleccione "top ciclos", a continuación, elimine las personas que estaban en la parte superior de los ciclos y hacerlo de nuevo. Repita el proceso hasta que todo el mundo se ha producido en una parte del ciclo y de cada ciclo representa una permutación de las personas y las casas que serán en el estricto núcleo.

Answer 1

Cuando las preferencias son estrictas, el núcleo es único y la parte superior de comercio de procedimiento del ciclo de TTCP) es el único mecanismo de ceder el núcleo fuerte de la asignación. Aquí son los aspectos más destacados.

Lema 1: Deje que $x$ ser la asignación generada por la parte Superior de Comercio de Procedimiento del Ciclo. Entonces $x$ es en el núcleo.

Lema 2: Deje que $P$ el conjunto de jugadores, $\Omega = \{ \omega^{i} = i : i \P \}$ el conjunto de las asignaciones iniciales, y $\e^{i}$ el conjunto de estrictas preferencias. Tenemos $(P, \Omega, (\e^{i})_{i=1}^{|P|})$ como el ejemplo de la casa de la asignación de problema. El núcleo es único.

Prueba: Supongamos que al contrario, que existen dos asignaciones de $x,$ y en el núcleo fuerte y supongamos que $x$ es la asignación devuelto por el TTCP. Como $x \neq de$ y, $S = \{ i : x_{i} \neq y_{i} \}$ tiene al menos dos elementos. Observar que si hay un jugador $i \in S$ que $x_{i} \e^{i} y_{i}$, entonces $x_{i}$ se puede formar una débil mejora de la coalición con el resto de jugadores en $x_{i}$'s del ciclo cuyo destino son el mismo en $x$ y $y$. Como las preferencias son estrictas, cada jugador en $S$ estrictamente prefiere, ya sea $x$ o $y$. Construimos una débilmente la mejora de la coalición para bloquear $y$.

Deje que $i \in S$ que $y_{i} \e^{i} x_{i}$. Deje que $i$ coincide en la iteración $k$ de la TTCP. Desde $y_{i} \e^{i} x_{i}$, tenemos que jugador $i$ prefiere alguna otra casa $j$ a $x_{i}$ y que $j$ fue asignado en una iteración anterior por el hecho de que $x$ pertenece al núcleo fuerte. Y así, mediante la asignación de $y$ desplaza el jugador que recibió la casa $j$ bajo el TTCP. Como las preferencias son estrictas, cada jugador que recibió una casa cuando $j$ fue asignado en virtud de la TTCP puede formar una débil mejora de la coalición para bloquear $y$. Y el hecho de que $S \neq \emptyset$ implica $$ y no en el núcleo. QED.

De hecho tengo una entrada en el blog de entrar en más detalle sobre esto: https://michaellevet.wordpress.com/2015/06/01/algorithmic-game-theory-house-allocation-problem/