5

So I have a game in which home owners prefer certain other's homes. The owners are A, B, C, and D with a, b, c, and d referring to their respective homes. They each prefer homes according to the ranking

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

I've read an article by Shapley about an algorithm to find one assignment in the strict core, but I'm asked to "determine the strict core" which I assume means finding all assignments in the strict core. How does one do that?

In case it's of any use, I'll describe the algorithm in the Shapley article. Make a graph of people's top preferences and select "top cycles", then delete the people who were in top cycles and do it again. Repeat the process until everyone has occurred in a top cycle and every cycle represents a permutation of people and houses that will be in the strict core.

ml0105
  • 1,246
  • 8
  • 19
Addem
  • 255
  • 2
  • 7

1 Answers1

6

When preferences are strict, the strong core is unique and the top-trading cycle procedure (TTCP) is the unique mechanism yielding the strong core allocation. Here are the highlights.

Lemma 1: Let $x$ be the allocation generated by the Top-Trading Cycle Procedure. Then $x$ is in the strong core.

Lemma 2: Let $P$ be the set of players, $\Omega = \{ \omega^{i} = i : i \in P \}$ be the set of initial allocations, and $\succ^{i}$ be the set of strict preferences. We have $(P, \Omega, (\succ^{i})_{i=1}^{|P|})$ as the instance of the house allocation problem. The strong core is unique.

Proof: Suppose to the contrary that there exist two allocations $x, y$ in the strong core and suppose $x$ is the allocation returned by the TTCP. As $x \neq y$, $S = \{ i : x_{i} \neq y_{i} \}$ has at least two elements. Observe that if there is a player $i \in S$ such that $x_{i} \succ^{i} y_{i}$, then $x_{i}$ can form a weakly improving coalition with the other players in $x_{i}$'s cycle whose allocations are the same in $x$ and $y$. As preferences are strict, every player in $S$ strictly prefers either $x$ or $y$. We construct a weakly improving coalition to block $y$.

Let $i \in S$ such that $y_{i} \succ^{i} x_{i}$. Let $i$ be matched in iteration $k$ of the TTCP. Since $y_{i} \succ^{i} x_{i}$, we have that player $i$ prefers some other house $j$ to $x_{i}$ and that $j$ was assigned in a previous iteration by the fact that $x$ belongs to the strong core. And so using the allocation $y$ displaces the player who received house $j$ under the TTCP. As preferences are strict, each player who received a house when $j$ was allocated under the TTCP can form a weakly improving coalition to block $y$. And so the fact that $S \neq \emptyset$ implies that $y$ is not in the strong core. QED.

I actually have a blog entry going into more detail about this: https://michaellevet.wordpress.com/2015/06/01/algorithmic-game-theory-house-allocation-problem/

ml0105
  • 1,246
  • 8
  • 19