<p>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.</p>

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

<p><strong>Lemma 2</strong>: 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.</p>

<p><strong>Proof</strong>: 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$.</p>

<p>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.</p>

<p>I actually have a blog entry going into more detail about this: <a href="https://michaellevet.wordpress.com/2015/06/01/algorithmic-game-theory-house-allocation-problem/" rel="nofollow">https://michaellevet.wordpress.com/2015/06/01/algorithmic-game-theory-house-allocation-problem/</a></p>

CC BY-SA 3.0
2015-08-16T20:59:34.877Z
@FooBar Thank you kindly for the bounty. :-)
ml0105
CC BY-SA 3.0
2015-08-09T04:02:43.327Z
2015-08-13T18:47:53.027Z
2015-08-13T18:47:53.027Z
ml0105
<p>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 </p>

<pre><code>A: bdac
B: cadb
C: dbca
D: acbd
</code></pre>

<p>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 <em>all</em> assignments in the strict core.  How does one do that?  </p>

<p>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.  </p>

<game-theory><cooperative-game-theory><search-and-matching>
How do you determine the strict core in a matching game?
Addem
# How do you determine the strict core in a matching game?

(Asked by: username_0 on 2015-08-09)

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.

**Tags:** game-theory, cooperative-game-theory, search-and-matching

---

## 1 answers

### Answer by username_1 on 2015-08-09. Score: 6 | Accepted answer

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/>

> **Comments:**
> **username_1**: @FooBar Thank you kindly for the bounty. :-)  

---

