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.


1 Answer 1


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/

  • $\begingroup$ @FooBar Thank you kindly for the bounty. :-) $\endgroup$
    – ml0105
    Aug 16, 2015 at 20:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.