One of the most elegant matching algorthms out there is the Top Trading Cycles algorithm, introduced by Shapley and Scarf in their 1974 paper “On cores and indivisibility”, and attributed to David Gale. This algorithm finds the unique core allocation, and its outcome is therefore individually rational and pareto efficient. In addition, this algorithm makes truth-telling a dominant strategy for all individuals.

In fact, a striking 1994 paper by Ma (“Strategy-Proofness and the Strict Core in a Market with Indivisibilities”) shows that Top Trading Cycles is the only mechanism that is individually rational, pareto efficient, and truthful. More recently, Ozgun Ekici showed in “Pair-efficient Reallocation of Indivisible Objects” (EC 22) that this uniqueness result remains true if pareto efficiency is weakened to pair efficiency.

This post presents short proofs of these results. These proofs are not mine: they are largely copied from work of Jay Sethuraman (“An alternative proof of a characterization of the TTC mechanism”, Operations Research Letters 2016), and were re-organized and written by Felipe Simon, a PhD student at the University of Minnesota. My goal with this post is not to claim credit, but rather to share a clean proof of a fundamental result.

Model and Result

There is a set of agents $N$ . Each agent $i \in N$ is initially endowed with an object $o_{i}$ ; let $O = {o_{i}}$ be the set of all objects. Each agent $i$ has a (complete and transitive) ranking of objects $≻_{i}$ : $o ≻_{i} o^{'}$ means that agent $i$ strictly prefers object $o$ to object $o^{'}$ , and $o ⪰_{i} o^{'}$ means that either $o ≻_{i} o^{'}$ or $o = o^{'}$ .

We use $P = {≻_{i}}_{i \in N}$ to denote a preference profile for all agents, and use $⪰_{i}^{P}$ to refer to the preference order of agent $i$ on profile $P$ . An allocation $μ$ is bijection between agents and objects. We let $μ_{i} \in O$ denote the object allocated to agent $i$ by $μ$ .

Definition 1 Object $o_{j}$ is acceptable to agent $i$ if $o_{j} ⪰_{i} o_{i}$ . Allocation $μ$ is individually rational if each agent receives an acceptable object ( $μ_{i} ⪰_{i} o_{i}$ for all $i \in N$ ).

Definition 2 An allocation $μ$ is pareto efficient if there is no allocation $μ^{'}$ such that $μ_{i}^{'} ⪰_{i} μ_{i}$ for all $i \in N$ , with at least one inequality holding strictly.

Definition 3 An allocation $μ$ is pair efficient if there exists no $i, j \in N$ such that $μ_{j} ≻_{i} μ_{i}$ and $μ_{i} ≻_{j} μ_{j}$ .

A mechanism is a function that maps each preference profile to an allocation. We say that a mechanism is individually rational (pareto efficient, pair efficient) if on any preference profile, it finds an allocation that is individually rational (pareto efficient, pair efficient).

Definition 4 A mechanism is truthful if for each agent $i$ , reporting $≻_{i}$ is a weakly dominant strategy for each agent.

Theorem 1 There exists at most one mechanism that is truthful, individually rational and pareto efficient.

Theorem 2 There exists at most one mechanism that is truthful, individually rational and pair efficient.

Gale’s top trading cycles mechanism (TTC) is known to satisfy all of these properties, so these results imply that TTC is the unique mechanism satisfying these properties.

Proof

Let $Π$ and $Ψ$ represent two mechanisms. For any preference profile $P$ , let $Π_{i}^{P}, Ψ_{i}^{P} \in O$ denote the objects given to agent $i$ by $Π$ and $Ψ$ (respectively). Define $A_{Ψ}, A_{Π}$ and $A$ as follows: $\begin{aligned} (1) & A_{Π} & = {i \in N | Π_{i}^{P} ≻_{i} Ψ_{i}^{P}} \\ (2) & A_{Ψ} & = {i \in N | Ψ_{i}^{P} ≻_{i} Π_{i}^{P}} \\ (3) & A & = A_{Π} \cup A_{Ψ} . \end{aligned}$ That is, $A_{Π}$ is the set of agents that prefer the allocation from $Π$ over the one from $Ψ$ , $A_{Ψ}$ is defined analogously, and $A$ is the set of all agents whose allocations differ.

Definition 5 A preference profile $P$ is a discordant preference profile of mechanisms $Π$ and $Ψ$ if $Π (P) \neq Ψ (P)$ . (That is, $A$ is non-empty.)

Definition 6 The size $s$ of preference profile $P$ is the total number of objects that agents find acceptable in $P$ : $s (P) = \sum_{i \in N} | {o_{j} \in O | o_{j} ⪰_{i} o_{i}} | .$ A discordant profile $P$ of $Π$ and $Ψ$ is said to be of minimal size if there is no preference profile of smaller size.

Lemma 1 Let $Π$ and $Ψ$ be truthful mechanisms. Let $P$ be a discordant preference profile of minimal size, and define $A$ as in (3). Then each agent in $A$ has exactly two acceptable objects.

Proof. Proof by contradiction. Suppose that there is an agent $i \in A$ with more than two acceptable objects and suppose $Π_{i}^{P} ≻_{i} Ψ_{i}^{P}$ . Modify the preference ordering of agent $i$ by removing all objects except for $Π_{i}^{P}$ and $o_{i}$ ; all other agents hold the same preferences. Call this new preference profile $Q$ . From the truthfulness of $Π$ it follows that $Π_{i}^{Q} = Π_{i}^{P}$ , because if under $Q$ , $i$ was allocated a worst object than $Π_{i}^{P}$ , then $i$ could simply use the preference in $P$ and improve its outcome, violating truthfulness. From the truthfulness of $Ψ$ we know that $Π_{i}^{P} ≻_{i} Ψ_{i}^{Q}$ since $Ψ_{i}^{Q} ⪰_{i}^{P} Π_{i}^{P}$ would mean that $i$ could improve its allocation under $P$ by misreporting his preferences. In particular, $Q$ is a profile in which the two mechanisms disagree, and $s (Q) < s (P)$ , contradicting our choice of $P$ .

The definition of size and Lemma @ref{lem:key} are the crucial steps in the proof: they allow us to only reason about “simple” profiles in which agents have only two acceptable objects.

Lemma 2 Let $Π$ and $Ψ$ be two distinct individually rational mechanisms. Let $P$ be a discordant preference profile and let $A_{Π}, A_{Ψ}$ and $A$ be defined as in (1), (2), (3). Furthermore, assume that every agent $i \in A$ has exactly two acceptable objects. Then for every agent $i \in A_{Π}$ his favorite object is the endowment of some other agent $i^{'} \in A_{Π}$ . Similarly, for every agent $j \in A_{Ψ}$ his favorite object is the endowment of some other agent $j^{'} \in A_{Ψ}$ .

Proof. Because $Π$ is individually rational we know that every agent $j \in A_{Ψ}$ retains their initial endowment under $Π$ (that is, $Π_{j}^{P} = o_{j}$ ) since this is the worse of the two acceptable objects. Also, every agent $i \in A_{Π}$ is allocated their first option $Π_{i}^{P} ≻_{i}^{P} o_{i}$ . Analogously, because $Ψ$ is individually rational it assigns every agent $i \in A_{Π}$ to their initial endowment $Ψ_{i}^{P} = o_{i}$ and every agent $j \in A_{Ψ}$ to their first option $Ψ_{j}^{P} ≻_{j}^{P} o_{j}$ . It follows that neither $Π$ nor $Ψ$ can give the endowment of an agent $i \in A$ to an agent $k \notin A$ , since these agents receive the same object in both $Π$ and $Ψ$ .

Therefore, agents in $A$ only trade objects with other agents in $A$ . Furthermore, under $Π$ an agent $i \in A_{Π}$ will not be allocated the endowment from an agent in $j \in A_{Ψ}$ , since these agents all retain their endowment. Thus, agents in $A_{Π}$ only trade with other agents in $A_{Π}$ . Similarly, agents in $A_{Ψ}$ only trade with other agents in $A_{Ψ}$ .

Lemma 3 Let $Π$ and $Ψ$ be two individually rational mechanisms. Let $P$ be a discordant preference profile in which every agent $i \in A$ has exactly two acceptable objects. Then at least one of $Π^{P}$ or $Ψ^{P}$ is not pareto efficient.

Proof. Note that $A_{Π} \cup A_{Ψ} = A$ and by assumption $A$ is nonempty so at least one of these sets is also nonempty. Suppose $A_{Π}$ is nonempty. By assumption we know that agents in $A_{Π}$ strictly prefer their allocation given by $Π$ . In fact, because $Ψ$ is individually rational and agents only have two acceptable object we know that under mechanism $Π$ each agent in $A_{Π}$ is allocated their first option. From Lemma 2 we know that agents in $A_{Π}$ only trade with other agents in $A_{Π}$ . Because $Ψ$ is individually rational we know that agents in $A_{Π}$ retain their endowment under $Ψ$ . Therefore, the allocation $Ψ^{P}$ is not pareto efficient because we could improve the outcome of every agent in $A_{Π}$ by allocating them their first option, without changing the outcome of other agents. Thus, $Ψ^{P}$ is not pareto efficient.

Proof of Theorem 1. Suppose $Π$ and $Ψ$ are two distinct truthful, individually rational mechanisms and let $P$ be a discordant preference profile of minimal size. By Lemma 1 we know that every agent whose allocation differs in $Π$ and $Ψ$ has exactly two acceptable objects. By Lemma 3 at least one of these mechanisms is not pareto efficent.

Proof of Theorem 2. Suppose $Π$ and $Ψ$ are truthful and individually rational. We will show that at least one of them is not pair efficient. Let $P$ be a discordant preference profile of minimal size and et $A_{Π}, A_{Ψ}$ and $A$ be defined as in equations (1),(2),(3). From Lemma 1 we know that every agent in $A$ has exactly two acceptable objects. Suppose $A_{Π}$ is not empty. Because $Ψ$ is individually rational we know that every agent in $i \in A_{Π}$ retains their endowment under mechanism $Ψ$ . Furthermore, by Lemma 3, we know that mechanism $Ψ$ is not pareto efficient. That is, there is at least one set of agents ${i_{1}, i_{2}, . . ., i_{m}} \subseteq A_{Π}$ such that $Ψ_{i_{2}}^{P} ≻_{i_{1}} Ψ_{i_{1}}^{P}, Ψ_{i_{3}}^{P} ≻_{i_{2}} Ψ_{i_{2}}^{P}, . . ., Ψ_{i_{1}}^{P} ≻_{i_{m}} Ψ_{i_{m}}^{P}$ . (Note that $Ψ_{i}^{P} = o_{i}$ for each $i$ in this cycle). Now create a new preference profile $Q$ where agent $i_{1}$ reports the following preferences: $o_{i_{2}} ≻_{i_{1}} o_{i_{3}} ≻_{i_{1}} o_{i_{4}} ≻_{i_{1}} . . . ≻_{i_{1}} o_{i_{m - 1}} ≻_{i_{1}} o_{i_{m}} ≻_{i_{1}} o_{i_{1}}$ (Note that the original preference was: $o_{i_{2}} ≻_{i_{1}} o_{i_{1}}$ so all we are doing is adding the objects from the cycle in a specific order). All other agents hold the same preferences. Because $Ψ$ is strategy-proof, it cannot give object $o_{i_{2}}$ to agent $i_{1}$ on profile $Q$ . Because $Ψ$ is individually rational, it must instead give $i_{1}$ an object $o \in {o_{i_{1}}, o_{i_{3}}, o_{i_{4}}, \dots o_{i_{m}}}$ . But we claim that none of these outcomes can be pair efficient: the agent in the cycle whose favorite object is $o$ must receive their endowment by individual rationality of $Ψ$ , and by construction of profile $Q$ , this agent and $i_{1}$ would both prefer to swap items (according to $Q$ ). Therefore $Ψ$ is not pair efficient.

Short Proofs for Characterizations of Top Trading Cycles

Nick Arnosti

2023/10/31

Model and Result

Proof