Strategy-proofness and identical preferences lower bound in allocation problem of indivisible objects

Abstract

We study an allocation problem of heterogeneous indivisible objects among agents without money. Each agent receives at most one object and prefers any object to nothing. We identify the class of rules satisfying strategy-proofness, Pareto-efficiency, and the identical preferences lower bound. Each rule of this class is included in Pápai’s (Econometrica 68:1403–1433, 2000) rules and can be described by a top trading cycle rule associated with an inheritance structure that satisfies a symmetry condition called U-symmetry.

1 Introduction

We study an allocation problem¹ of heterogeneous indivisible objects among agents without money. Each agent receives at most one object and prefers any object to nothing. A rule assigns the objects depending on the agents’ preferences.

Since the seminal works of Ma (1994) and Pápai (2000), strategy-proofness and Pareto-efficiency have been the most widely² studied properties concerning this problem. Strategy-proofness requires that it be a dominant strategy for any agent to report his true preference relation. Pareto-efficiency requires that the rule assign a Pareto-efficient allocation.

In the private endowment³ setting, the top trading cycle rule is strategy-proof and achieves a Pareto-efficient allocation. Moreover, it is the only rule that satisfies strategy-proofness, Pareto-efficiency, and individual rationality (Ma 1994). Individual rationality requires that the rule assign an allocation under which no agent prefers his endowment to his assignment.

Even in the social endowment⁴ setting, the top trading cycle procedure has an important role. By suitably specifying the ownership of each object at each round in the procedure, the corresponding top trading cycle rule is strategy-proof and achieves a Pareto-efficient allocation. We call such a specification an inheritance structure and the corresponding rule the top trading cycle rule associated with the inheritance structure. There are several inheritance structures, and the corresponding rules coincide with the class of rules satisfying strategy-proofness, Pareto-efficiency, non-bossiness, and reallocation-proofness (Pápai 2000). Non-bossiness requires that if the assignment of an agent remains unchanged when his preference relation changes, then the assignments of the others should also remain unchanged. Reallocation-proofness rules out the possibility that two agents will gain by jointly manipulating the outcome and swapping objects ex post when the collusion is self-enforcing, in the sense that neither agent loses by reporting false preferences in case the other agent does not adhere to the agreement and reports honestly.

Although non-bossiness⁵ has also been a frequently studied property in this field, it is to an extent a technical condition and strong requirement. Indeed, many good rules do not satisfy it, for example, the Vickrey–Clarke–Groves (VCG) rules in auction models and the deferred acceptance rules in school choice models. Reallocation-proofness is also technical.⁶ Hence, for the next step, it is important to investigate the problem without non-bossiness and reallocation-proofness.⁷

Instead of non-bossiness and reallocation-proofness, we focus on another property called the identical preferences lower bound. Imagine the two-agent and two-object case. Suppose that a man prefers object a to object b. Let us compare the following two situations: (i) A woman also prefers object a to object b and (ii) she prefers object b to object a. In (i), the man has to compete with the woman for object a and sometimes might lose it. On the other hand, in (ii), he does not have to compete with her for object a and thus can always get it. This consideration tells us that in a private goods setting, while similarity of preferences means conflict among agents, diversity of preferences means benefits for agents. Moulin (1990) has called these benefits “positive preference externalities.” The identical preferences lower bound says that everyone should enjoy a positive preference externality.⁸ Formally, it requires that the assignment of an agent be no worse than his assignment in the problem where all agents have a preference relation identical to his preference relation.⁹

We identify the class of rules satisfying strategy-proofness, Pareto-efficiency, and the identical preferences lower bound. Each rule of this class is included in Pápai’s (2000) rules and can be described by a top trading cycle rule associated with an inheritance structure satisfying a symmetry condition called U-symmetry. We also¹⁰ show that this class includes all rules¹¹ introduced by Abdulkadiroğlu and Sönmez (1999).

In Sect. 2, we set up the model. In Sect. 3, we define the axioms. In Sect. 4, we introduce several rules. In Sect. 5, we state our results. In Sect. 6, we establish the independence of the axioms. In Sect. 7, we make some concluding remarks. All the proofs are provided in Appendix.

2 Model

Let $N=\{1,2,\dots , n\}$ denote the set of agents. Let K denote the set of indivisible objects. Let 0 represent the null object. Each agent wants at most one object. Each agent $i\in N$ has a complete and transitive preference relation $R_i$ over $K\cup \{0\}$. The associated strict preference relation is denoted by $P_i$. We assume that $R_i$ is strict, that is, for any $k,k'\in K\cup \{0\}$, $kR_i k'$ means either $kP_i k'$ or $k=k'$. Furthermore, we assume that the null object is the worst object, that is, for any $k\in K$, $kP_i 0$. Let $\mathcal {R}$ denote the class of such preference relations. We represent $R_i\in \mathcal {R}$ by an ordered list of the objects:

$$\begin{aligned} R_i=k_1, k_2,k_3, \dots . \end{aligned}$$

A list $R=(R_i)_{i\in N}\in \mathcal {R}^n$ is a preference profile.

A feasible allocation is a list $x=(x_i)_{i\in N}$ as follows: For any $i\in N$, $x_i \in K\cup \{0\}$, and none of the objects in K is assigned to more than one agent.¹² Let X denote the set of feasible allocations. A rule is a function f from $\mathcal {R}^n$ to X. Given a rule f and a preference profile $R\in \mathcal {R}^n$, we denote by $f_i(R)$ agent i’s assignment at f(R). Given $R\in \mathcal {R}^n$ and $S\subset N$, $R_S$ denotes $(R_i)_{i\in S}$. We also use the notation $R_{-S}=R_{N\setminus S}$ and $R_{-i}=R_{N\setminus \{i\}}$.

3 Axioms

We introduce the basic properties. The first property requires that it should be a dominant strategy for any agent to report his true preference relation.

Definition 1

A rule f satisfies strategy-proofness if for any $R\in \mathcal {R}^n$, any $i\in N$, and any $R_{i}^{\prime }\in \mathcal {R}$, we have

$$\begin{aligned} f_i(R)R_i f_i(R_{i}',R_{-i}). \end{aligned}$$

The second property requires that the rule assign a Pareto-efficient allocation.

Definition 2

A rule f satisfies Pareto-efficiency if for any $R\in \mathcal {R}^n$, there exists no $x\in X$ such that for all $i\in N$, it holds that

$$\begin{aligned} x_i R_i f_i(R) \end{aligned}$$

with strict preference holding for some $j\in N$.

To introduce the third property, we need some notation. For any $i\in N$ and any $R_i\in \mathcal {R}$, let $R(R_i)\in \mathcal {R}^n$ denote the preference profile where all agents have preference relation $R_i$, that is, $R(R_i)=(R_i, R_i, \dots , R_i)$. The third property requires that the assignment of each agent be at least as good as his assignment where all agents have the identical preferences with him.

Definition 3

A rule f satisfies the identical preferences lower bound if for any $i\in N$, any $R_i\in \mathcal {R}$, and any $R'_{-i}\in \mathcal {R}^{n-1}$, we have

$$\begin{aligned} f_i(R_i,R'_{-i})R_i f_i(R(R_i)). \end{aligned}$$

The next property requires that if the assignment of an agent remains unchanged when his preference relation changes, then the assignments of the others should also remain unchanged.

Definition 4

A rule f satisfies non-bossiness if for any $R\in \mathcal {R}^n$, any $i\in N$, and any $R'_i\in \mathcal {R}$, we have

$$\begin{aligned} f_i(R)=f_i(R_i',R_{-i}) \text { implies } f(R)=f(R_i',R_{-i}). \end{aligned}$$

The last property rules out the possibility that two agents will gain by jointly manipulating the outcome and swapping objects ex post when the collusion is self-enforcing, in the sense that neither agent loses by reporting false preferences in case the other agent does not adhere to the agreement and reports honestly.

Definition 5

A rule f satisfies reallocation-proofness if there is no $R\in \mathcal {R}^n$, $i,j \in N$, and $\tilde{R}_i, \tilde{R}_j \in \mathcal {R}$ such that

$$\begin{aligned} f_j(\tilde{R}_i,\tilde{R}_j,R_{-\{i,j\}}) R_i f_i(R)\quad \text { and }\quad f_i(\tilde{R}_i,\tilde{R}_j,R_{-\{i,j\}}) P_j f_j(R), \end{aligned}$$

and for any $h=i,j$,

$$\begin{aligned} f_h(R)=f_h(\tilde{R}_h,R_{-h})\ne f_h(\tilde{R}_i,\tilde{R}_j,R_{-\{i,j\}}). \end{aligned}$$

4 Rules

4.1 Pápai’s (2000) Rules

We review the rules¹³ defined by Pápai (2000), each of which is a generalization of David Gale’s top trading cycle (TTC) procedure. To apply the TTC procedure to this model, we need to specify a structure determining the initial priority rights and their inheritance. We specify it by an inheritance structure h as follows.¹⁴ First, for any object $k\in K$, agent h(k) initially has the property right of object k. Next, when agent h(k) is assigned some other object $k'$ and leaves with it, the property right of object k moves to agent $h(k,k')$. Next, when agent $h(k,k')$ is assigned some other object $k''$ and leaves with it, the property right of object k moves to agent $h(k,k',k'')$, and so on.

To define it formally, we introduce some notation. Let $C^1=K$. For any $\ell >1$, define

$$\begin{aligned} C^{\ell }=\{(k_1,k_2,\dots ,k_{\ell })\in K^{\ell }: \ell ' \ne \ell '' \Rightarrow k_{\ell '}\ne k_{\ell ''}\}. \end{aligned}$$

Further, define

$$\begin{aligned} \mathcal {C}=\bigcup _{\ell =1}^{\min \{\#N,\#K\}} C^{\ell }. \end{aligned}$$

For any $c,c'\in \mathcal {C}$, when $c=(k_1,\dots ,k_\ell )$ and $c'=(k_1,\dots , k_\ell , k_{\ell +1},\dots , k_{\ell '})$ with $\ell \le \ell '$, we denote $c\subset c'$, as an abuse of notation.

Definition 6

An inheritance structure is a function h from $\mathcal {C}$ to N satisfying the following: For any $c, c'\in \mathcal {C}$ such that $c\subset c'$ and $c\ne c'$, it holds that

$$\begin{aligned} h(c)\ne h(c'). \end{aligned}$$

Example 1

In Figs. 1, 2, 3, 4, 5, 6 and 7, we express inheritance structures as trees in the three-agent and three-object case. Each node indicates an object. For each path (arrow) c, the corresponding agent h(c) is expressed.

Definition 7

Given an inheritance structure h, for each $R\in \mathcal {R}^n$, the top trading cycle rule associated with h assigns the allocation calculated by the following algorithm.

1st Round: Each object $k\in K$ points to agent h(k), and each agent points to his most preferred object. Then, we look for cycles. A sequence of objects and agents $(k_1, i_1,\dots , k_m, i_m)$ forms a cycle if $k_1$ points to $i_1$, $i_1$ points to $k_2, \dots ,$ $k_m$ points to $i_m$, and $i_m$ points to $k_1$. Since there are a finite number of objects and agents, there is at least one cycle. Each agent in a cycle is assigned the object he points to and leaves with his assignment. If there is no remaining object or agent, the algorithm terminates. If there is at least one remaining object and agent, proceed with the next round.

t-th Round: Denote K(t, R) and N(t, R) as the set of objects and the set of agents, respectively, that have already left until the beginning of the t-th Round. Each object $k\in K\setminus K(t,R)$ points to an agent in $N\setminus N(t,R)$ determined as follows: When $h(k)\notin N(t,R)$, k points to h(k). Otherwise, go to the next stage. When $h(k,k_1) \notin N(t,R)$, where $k_1$ is agent h(k)’s assignment, k points to $h(k,k_1)$. Otherwise, go to the next stage. When $h(k,k_1, k_2) \notin N(t,R)$, where $k_2$ is agent $h(k,k_1)$’s assignment, k points to $h(k,k_1)$. Otherwise, go to the next stage, which is similar. Since N(t, R) is finite, this procedure determines an agent in $N{\setminus }N(t,R)$. Each remaining agent points to his most preferred object among the remaining objects $K{\setminus }K(t,R)$. Each agent in a cycle is assigned the object he points to and leaves with his assignment. If there is no remaining object or agent, the algorithm terminates. If there is at least one remaining object and agent, proceed with the next round.

Example

(Basic Example). Consider the three-agent and three-object case. Let f be the TTC rule associated with the inheritance structure h expressed in Fig. 1. Let $R \in \mathcal {R}^3$ be as follows:

$$\begin{aligned} R_{1}= & {} k_1,k_2,k_3.\\ R_{2}= & {} k_2,k_3,k_1.\\ R_{3}= & {} k_2,k_1,k_3. \end{aligned}$$

First, we calculate f(R) according to the algorithm.

1st Round: All the objects $k_1$, $k_2$, $k_3$ point to agent $h(k_1)=h(k_2)=h(k_3)=1$. Agents 1, 2, and 3 point to objects $k_1$, $k_2$, and $k_2$, respectively. Then, the cycle $(k_1, 1)$ occurs. Hence, agent 1 is assigned object $k_1$ and leaves with it. We have $K(2,R)=\{k_1\}$ and $N(2,R)=\{1\}$.

2nd Round: All the remaining objects $k_2$, $k_3$ point to agent $h(k_2,k_1)=h(k_3,k_1)=2$ because $h(k_2)=h(k_3)=1\in N(2,R)$ and $f_1(R)=k_1$. Both agents 2 and 3 point to object $k_2$. Then, the cycle $(k_2, 2)$ occurs. Hence, agent 2 is assigned object $k_2$ and leaves with it. We have $K(3,R)=\{k_1,k_2\}$ and $N(2,R)=\{1,2\}$.

3rd Round: Object $k_3$ points to agent $h(k_3,k_1,k_2)=3$ because $h(k_3)=1\in N(3,R)$, $f_1(R)=k_1$, $h(k_3,k_1)=2\in N(3,R)$, and $f_2(R)=k_2$. Agent 3 points to object $k_3$. Then, the cycle $(k_3, 3)$ occurs. Hence, agent 3 is assigned object $k_3$ and leaves with it. Since there is no remaining object (agent), the algorithm terminates. Thus, we have $f(R)=(k_1, k_2, k_3)$.

Let $R'_1 \in \mathcal {R}$ be as follows:

$$\begin{aligned} R'_{1}= & {} k_2,k_1,k_3. \end{aligned}$$

Next, we calculate $f(R_1', R_{-1})$ according to the algorithm.

1st Round: All the objects $k_1$, $k_2$, $k_3$ point to agent $h(k_1)=h(k_2)=h(k_3)=1$. All the agents 1, 2, 3 point to object $k_2$. Then, the cycle $(k_2, 1)$ occurs. Hence, agent 1 is assigned object $k_2$ and leaves with it. We have $K(2,R_1', R_{-1})=\{k_2\}$ and $N(2,R_1', R_{-1})=\{1\}$.

2nd Round: Objects $k_1$ and $k_3$ point to agents $h(k_1,k_2)=2$ and $h(k_3,k_2)=3$, respectively, because $h(k_1)=h(k_3)=1\in N(2,R_1', R_{-1})$ and $f_1(R_1', R_{-1})=k_2$. Agents 2 and 3 point to object $k_3$ and $k_1$, respectively. Then, the cycle $(k_1, 2, k_3, 3)$ occurs. Hence, agents 2 and 3 are assigned objects $k_3$ and $k_1$, respectively, and leave with these. Since there is no remaining object (agent), the algorithm terminates. Thus, we have $f(R_1', R_{-1})=(k_2, k_3, k_1)$.

Fig. 1

This inheritance structure is discussed in Examples labeled as “Basic Example”

The TTC rules associated with inheritance structures include various well-known types of rules.¹⁵

Example

(Serial Dictatorial Rule). The TTC rule associated with the inheritance structure expressed in Fig. 2 corresponds to a serial dictatorial rule, where agent 1 can choose his most preferred object from all the objects, agent 2 can choose his most preferred object from the remaining objects, and so on.

Fig. 2

This inheritance structure is discussed in Examples labeled as “Serial Dictatorial Rule”

Example

(Housing Market Rule). The TTC rule associated with the inheritance structure expressed in Fig. 3 corresponds to a housing market rule (Shapley and Scarf 1974), where agents 1, 2, and 3 initially own objects $k_1$, $k_2$, and $k_3$, respectively.

Fig. 3

This inheritance structure is discussed in Examples labeled as “Housing Market Rule”

Example

(Sequential Dictatorial Rule). The TTC rule associated with the inheritance structure expressed in Fig. 4 corresponds to a sequential dictatorial rule, where agent 1 can choose his most preferred object from all the objects. When agent 1 chose object $k_1$ or $k_2$, agent 2 can choose his most preferred object from the remaining objects, and so on; when agent 1 chose object $k_3$, agent 3 can choose his most preferred object from the remaining objects, and so on.

Fig. 4

This inheritance structure is discussed in Examples labeled as “Sequential Dictatorial Rule”

Example

(MDPE Rule). As analyzed by many studies,¹⁶ simple inheritance structures can be represented also by tables. The inheritance structure represented by Table 1 corresponds to a mixed dictator-pairwise-exchange rule (Ehlers 2002), where agent 1 can choose his most preferred object from all the objects, and then agent 2 inherits object $k_2$ (if it remains) and agent 3 inherits objects $k_1, k_3$ (if they remain), and agents 2 and 3 trade these objects.

Table 1 Tabular representation of the inheritance structure discussed in Examples labeled as “MDPE Rule”

By the following statement, Pápai (2000) has shown that the TTC rules associated with inheritance structures coincide with the class of rules satisfying strategy-proofness, Pareto-efficiency, non-bossiness, and reallocation-proofness.

Theorem

(Pápai 2000). A rule f satisfies strategy-proofness, Pareto-efficiency, non-bossiness, and reallocation-proofness if and only if f is a top trading cycle rule associated with an inheritance structure h.

4.2 Abdulkadiroğlu and Sönmez (1999) rules

Abdulkadiroğlu and Sönmez (1999) have defined a class of rules¹⁷ that include the serial dictatorial and housing market rules as extreme cases. As mentioned by Pápai (2000), Abdulkadiroğlu and Sönmez’s (1999) rules (AS hereafter) are described as a special subclass of the TTC rules associated with inheritance structures.

To describe them, we need some notation. Let $K^e\subset K$ and $N^e\subset N$ be such that $\#K^e=\#N^e$. Denote by E a bijection function from $K^e$ to $N^e$. Denote by $\sigma$ a linear ordering on N, where $\sigma (1)$ means the first-highest priority agent, $\sigma (2)$ means the second-highest priority agent, and so on. For any $\sigma$ and any $S\subset N$, denote by $\sigma ^{-S}$ the linear ordering on $N{\setminus }S$ that preserves the orders of $\sigma$. Hence, $\sigma ^{-S}(1)$ means the first-highest priority agent among $N{\setminus }S$ with $\sigma$, and so on.

In the AS rules, each object k in $K^e$ is initially owned by agent E(k) in $N^e$ as in a housing market rule and inherited according to the linear ordering $\sigma ^{-E(k)}$. The other objects are endowed and inherited according to the linear ordering $\sigma$ as in a serial dictatorial rule.

Definition 8

An inheritance structure h is AS-type for $(E, \sigma )$ if

• 1. for any $k\in K^e$ and any $c\in \mathcal {C}$,

  $$\begin{aligned} h(c)= \left\{ \begin{array}{ll} E(k) &{}\text { if } c=(k)\\ \sigma ^{-E(k)}(\ell ) &{}\text { if } c=(k,k_1,\dots ,k_{\ell }), \end{array} \right. \end{aligned}$$

• 2. for any $k_1\notin K^e$ and any $c=(k_1,\dots , k_{\ell })\in \mathcal {C}$,

  $$\begin{aligned} h(c)=\sigma (\ell ). \end{aligned}$$

The inheritance structures that are AS-types can be also represented by tables as follows.

Example

(Serial Dictatorial Rule). Consider the case $N=\{1,2,3\}$ and $K=\{k_1,k_2,k_3\}$. Let $K^e=\emptyset$ and $N^e=\emptyset$. (Then, E is meaningless.) Let $\sigma$ be such that $\sigma (1)=1$, $\sigma (2)=2$, and $\sigma (3)=3$. Then, the inheritance structure that is AS-type for this $(E, \sigma )$ can be represented by Table 2. This corresponds to a serial dictatorial rule (see Fig. 2).

Table 2 Tabular representation of the inheritance structure expressed in Fig. 2

Example

(Housing Market Rule). Consider the case $N=\{1,2,3\}$ and $K=\{k_1,k_2,k_3\}$. Let $K^e=\{k_1,k_2,k_3\}$ and $N^e=\{1,2,3\}$. Let E be such that $E(k_1)=1$, $E(k_2)=2$, and $E(k_3)=3$. Let $\sigma$ be such that $\sigma (1)=3$, $\sigma (2)=2$, and $\sigma (3)=1$. (In this example, $\sigma$ is arbitrary.) Then, the inheritance structure that is AS-type for this $(E, \sigma )$ can be represented by Table 3. This corresponds to a housing market rule (see Fig. 3).

Table 3 Tabular representation of the inheritance structure expressed in Fig. 3

Example

(Intermediate AS). Consider the case $N=\{1,2,3\}$ and $K=\{k_1,k_2,k_3\}$. Let $K^e=\{k_1,k_2\}$ and $N^e=\{1,2\}$. Let E be such that $E(k_1)=1$ and $E(k_2)=2$. Let $\sigma$ be such that $\sigma (1)=1$, $\sigma (2)=3$, and $\sigma (3)=2$. Then, the inheritance structure that is AS-type for this $(E, \sigma )$ can be represented by Table 4. This corresponds to a combination of a serial dictatorial rule and a housing market rule.

Table 4 Tabular representation of an inheritance structure intermediate among AS-types

Remark

(Basic Example). Consider the inheritance structure expressed in Fig. 1. Although it is not AS-type, the TTC rule associated with it can be regarded as another type of rule that is a combination of a serial dictatorial rule and a housing market rule as follows: First, agent 1 can choose his most preferred object from all the objects. If agent 1 chooses object $k_1$, then the rule goes on a serial dictatorial part. That is, agent 2 can choose his most preferred object from the remaining objects, and so on. If agent 1 chooses an object other than $k_1$, then the rule goes to a housing market part. That is, agent 2 inherits object $k_1$ and agent 3 inherits the remaining object $k_2$ or $k_3$, and then agents 2 and 3 trade these objects.

4.3 Canonical form

As mentioned by Pápai (2000), a rule can be expressed by the TTC rules associated with different inheritance structures h and $h'$. For example, the TTC rule associated with the inheritance structure expressed in Fig. 3 is equivalent to the TTC rule associated with the inheritance structure expressed in Fig. 5, because both these rules correspond to the same housing market rule. Hence, the way of expressing a rule in terms of the TTC rules associated with inheritance structures is not unique.

Fig. 5

This inheritance structure is discussed in Examples labeled as “Housing Market Rule.” This is the canonical form of the one expressed in Fig. 3

To clarify what rules are equivalent, Pápai (2000) has introduced the canonical form of an inheritance structure. The canonical form $h^*$ is converted from the original form h in the following way. First, consider $(k_1)\in \mathcal {C}$ and a preference profile where any agent’s best object is $k_1$. We set the agent who gets object $k_1$ at this preference profile as $h^*(k_1)$. Second, consider $(k_1,k_2)\in \mathcal {C}$ and a preference profile where agent $h^*(k_1)$’s best and second-best objects are $k_2$ and $k_1$, respectively, and any other agent’s best object is $k_1$. We set the agent who gets object $k_1$ at this preference profile as $h^*(k_1,k_2)$. Third, consider $(k_1,k_2,k_3)\in \mathcal {C}$ and a preference profile where agent $h^*(k_1)$’s best and second-best objects are $k_2$ and $k_1$, respectively, and agent $h^*(k_1,k_2)$’s best and second-best objects are $k_3$ and $k_1$, respectively, and any other agent’s best object is $k_1$. We set the agent who gets object $k_1$ at this preference profile as $h^*(k_1,k_2,k_3)$, and so on.

By using the canonical form, we can easily find the equivalence classes of the TTC rules associated with inheritance structures. To define it formally, we introduce some notation.

Given an inheritance structure h and $c=(k_1,\dots , k_{\ell })\in \mathcal {C}$, we denote by R(h, c) a preference profile such that¹⁸ for any $\ell '<\ell$,

$$\begin{aligned} R_{h(k_1,\dots ,k_{\ell '})}(h,c)=k_{\ell '+1}, k_1, \dots , \end{aligned}$$

and for any other agent i,

$$\begin{aligned} R_{i}(h,c)=k_1, \dots . \end{aligned}$$

Definition 9

Let h be an inheritance structure. Denote by f the top trading cycle rule associated with h. An inheritance structure $h^*$ is the canonical form of h if for any $c=(k_1,\dots , k_{\ell })\in \mathcal {C}$, it follows that

$$\begin{aligned} f_{h^*(c)}(R(h^*,c))=k_1. \end{aligned}$$

Example

(Housing Market Rule). Consider the inheritance structure h expressed in Fig. 3. We construct the canonical form $h^*$ of h. Denote by f the TTC rule associated with h. Let $c=(k_1)$. Note that $R(h^*,c)$ is as follows:

$$\begin{aligned} R_{1}(h^*,c)= & {} k_1,\dots ,\\ R_{2}(h^*,c)= & {} k_1,\dots ,\\ R_{3}(h^*,c)= & {} k_1,\dots . \end{aligned}$$

Since $f_1(R(h^*,c))=k_1$, we have

$$\begin{aligned} h^*(c)=1. \end{aligned}$$

Let $c'=(k_1,k_2)$. Then, since $h^*(k_1)=1$, $R(h^*,c')$ is as follows:

$$\begin{aligned} R_{1}(h^*,c')= & {} k_2,k_1,\dots ,\\ R_{2}(h^*,c')= & {} k_1,\dots ,\\ R_{3}(h^*,c')= & {} k_1,\dots . \end{aligned}$$

Since $f_2(R(h^*,c'))=k_1$, we have

$$\begin{aligned} h^*(c')=2. \end{aligned}$$

Let $c''=(k_1,k_2,k_3)$. Then, since $h^*(k_1)=1$ and $h^*(k_1,k_2)=2$, $R(h^*,c'')$ is as follows:

$$\begin{aligned} R_{1}(h^*,c'')= & {} k_2,k_1,\dots ,\\ R_{2}(h^*,c'')= & {} k_3,k_1\dots ,\\ R_{3}(h^*,c'')= & {} k_1,\dots . \end{aligned}$$

Since $f_3(R(h^*,c''))=k_1$, we have

$$\begin{aligned} h^*(c'')=3. \end{aligned}$$

Repeating a similar argument for each element in $\mathcal {C}$, we find that $h^*$ is the inheritance structure expressed in Fig. 5.

Example

(Basic Example). The inheritance structure expressed in Fig. 1 is the canonical form of itself.

Example

(Serial Dictatorial Rule). The inheritance structure expressed in Fig. 2 is the canonical form of itself.

Example

(Sequential Dictatorial Rule). The inheritance structure expressed in Fig. 4 is the canonical form of itself.

Example

(MDPE Rule). The inheritance structure represented by Table 1 is the canonical form of itself.

Example

(Intermediate AS). The inheritance structure expressed in Fig. 6 is the canonical form of the AS-type represented by Table 4.

Fig. 6

This inheritance structure is discussed in Examples labeled as “Intermediate AS.” This is the canonical form of the one expressed in Table 4

By the following statement, Pápai (2000) has shown that the canonical form is useful to analyze the equivalence classes of the TTC rules associated with inheritance structures.

Proposition

(Pápai 2000). Let f be a TTC rule associated with an inheritance structure h. Then, there exists a unique $h^*$ that is the canonical form of h, and it follows that $f=f^*$, where $f^*$ is the top trading cycle rule associated with $h^*$.

Example

(Comprehensive). Consider the three-agent and three-object case. Then, there exist $12^3=1728$ inheritance structures. Among them, 270 inheritance structures are canonical forms.¹⁹ In other words, the rules satisfying Pápai’s axioms consist of 270 different rules in this case.

4.4 U-symmetry

As the following remark shows, a TTC rule associated with some inheritance structure does not satisfy the identical preferences lower bound.

Remark

(Sequential Dictatorial Rule). Consider the inheritance structure h expressed in Fig. 4. Let f be the TTC rule associated with h. For any $i\in N$, let $R_i=k_1,k_3,k_2$. Further, let $R'_1=k_3,k_1,k_2$. Then, $f(R_1,R_2,R_3)=(k_1,k_3,k_2)$ and $f(R'_1,R_2,R_3)=(k_3,k_2,k_1)$. Hence, we have

$$\begin{aligned} f_2(R_1,R_2,R_3)=k_3 P_2 k_2=f_2(R'_1,R_2,R_3). \end{aligned}$$

Thus, f does not satisfy the identical preferences lower bound.

In the following, we define a new subclass of the TTC rules associated with inheritance structures that satisfy the identical preferences lower bound.

Given an inheritance structure h, for any $c\in \mathcal {C}$, define

$$\begin{aligned} H(c)=\bigcup _{c'\subset c} \{h(c')\}. \end{aligned}$$

For any $c,c'\in \mathcal {C}$, when any coordinate of c is some coordinate of $c'$, and vice versa, we denote²⁰ $c\simeq c'$.

Definition 10

An inheritance structure h is U-symmetric if for any $c,c'\in \mathcal {C}$ such that $c\simeq c'$, it holds that

$$\begin{aligned} H(c)=H(c'). \end{aligned}$$

Remark 1

Let h be a U-symmetric inheritance structure and f be the TTC rule associated with h. Consider $c=(k_1,\dots , k_{\ell })\in \mathcal {C}$ and $H(c)\subset N$. Focus on a round of TTC such that, until the beginning of this round, agents in $I \subset H(c)$ have already been assigned²¹ and their assigned objects are in $\{k_1,\dots , k_{\ell }\}$. Then, U-symmetry requires that, on this round, each object remaining in $\{k_1,\dots , k_{\ell }\}$ point to an agent²² in $H(c)\setminus I$. Thus, U-symmetry means, so to speak, a property right of the set of objects $\{k_1,\dots , k_{\ell }\}$ to the group H(c).

Example

(Basic Example). We explain U-symmetry in the three-agent and three-object case. Let $N=\{1,2,3\}$ and $K=\{k_1,k_2,k_3\}$. For $c=(k)\in \mathcal {C}$, U-symmetry obviously requires nothing. For $c=(k,k',k'')\in \mathcal {C}$ also, since $H(c)=\{1,2,3\}$, U-symmetry requires nothing. Hence, it is sufficient to focus on $c=(k,k')\in \mathcal {C}$.

See Fig. 7, which expresses the same inheritance structure as Fig. 1. We can easily judge whether $H(k_1,k_2)=H(k_2,k_1)$ by checking whether two solid circles include the same agents. In this figure, since both the circles include the same agents 1 and 2, we have $H(k_1,k_2)=H(k_2,k_1)$. Similarly, we can easily judge whether $H(k_1,k_3)=H(k_3,k_1)$ by checking whether two dotted circles include the same agents. In this figure, since both the circles include the same agents 1 and 2, we have $H(k_1,k_3)=H(k_3,k_1)$. Similarly, we can easily judge whether $H(k_2,k_3)=H(k_3,k_2)$ by checking whether two dashed circles include the same agents. In this figure, since both the circles include the same agents 1 and 3, we have $H(k_2,k_3)=H(k_3,k_2)$. Thus, the inheritance structure expressed in Fig. 1 is U-symmetric.

Fig. 7

This inheritance structure is the same as in Fig. 1. This is used to explain U-symmetry

Example

(Housing Market Rule). The inheritance structure expressed in Fig. 3 is not U-symmetric, because $H(k_1,k_2)\ne H(k_2,k_1)$. However, its canonical form (the inheritance structure expressed in Fig. 5) is U-symmetric.

Example

(Serial Dictatorial Rule). The inheritance structure expressed in Fig. 2 is U-symmetric.

Example

(Sequential Dictatorial Rule). The inheritance structure expressed in Fig. 4 is not U-symmetric, because $H(k_1,k_3)\ne H(k_3,k_1)$.

Example

(MDPE Rule). The inheritance structure represented by Table 1 is not U-symmetric, because $H(k_1,k_2)\ne H(k_2,k_1)$.

Example

(Intermediate AS). The inheritance structure that is AS-type represented by Table 4 is not U-symmetric, because $H(k_1,k_2)\ne H(k_2,k_1)$. However, its canonical form (the inheritance structure expressed in Fig. 6) is U-symmetric.

Remark 2

In general, U-symmetry can be tested as follows. Take any $c=(k_1,\dots , k_{\ell })\in \mathcal {C}$. Consider $c'=(k'_1,\dots , k'_{\ell })\in \mathcal {C}$ such that for some m, $k'_{m}=k_{m+1}$, $k'_{m+1}=k_m$, and for any $t\ne m,m+1$, $k'_{t}=k_{t}$. That is, the m-th and $m+1$-th coordinates of c are permuted in $c'$. For each t, we denote $h(k_1,\dots ,k_t)$ and $h(k'_1,\dots ,k'_t)$ simply by $i_t$ and $i'_t$, respectively. Then, for any $t<m$, since $k_t=k'_t$, we obviously have $i_t=i'_t$. Since $(k_1,\dots , k_{m+1})\simeq (k'_1,\dots , k'_{m+1})$, U-symmetry implies that $\{i_m,i_{m+1}\}=\{i'_m, i'_{m+1}\}$. For any $t>m+1$, since $(k_1,\dots , k_{t})\simeq (k'_1,\dots , k'_{t})$ and $\{i_1,\dots , i_{m+1}\}=\{i'_1,\dots , i'_{m+1}\}$, U-symmetry means that $i_t=i'_t$. Thus, U-symmetry requires that

$$\begin{aligned} (i'_1,\dots ,i'_{m},i'_{m+1},\dots i'_{\ell })= \left\{ \begin{array}{ll} (i_1,\dots ,i_{m},i_{m+1},\dots i_{\ell }) \\ \text { or }\\ (i_1,\dots ,i_{m+1},i_{m},\dots i_{\ell }). \end{array} \right. \end{aligned}$$

That is, either $(i_1,\dots , i_{\ell })$ and $(i'_1,\dots , i'_{\ell })$ are identical, or the m-th and $m+1$-th coordinates of $(i_1,\dots , i_{\ell })$ are permuted in $(i'_1,\dots , i'_{\ell })$. Therefore, U-symmetry is equivalent²³ to this permutation property for any $c\in \mathcal {C}$ and any coordinate m.

Remark 3

In the supplemental materials,²⁴ we provide an algorithm to construct U-symmetric inheritance structures.

5 Results

Now, we state our results. All proofs are provided in Appendix.

5.1 Main results

First, we identify the class of rules satisfying strategy-proofness, Pareto-efficiency, and the identical preferences lower bound.

Theorem 1

A rule f satisfies strategy-proofness, Pareto-efficiency, and the identical preferences lower bound if and only if f is a top trading cycle rule associated with a U-symmetric inheritance structure h.

Example

(Basic Example). The TTC rule associated with the inheritance structure h expressed in Fig. 1 satisfies the axioms, because h is U-symmetric.

Example

(Serial Dictatorial Rule). The TTC rule associated with the inheritance structure h expressed in Fig. 2 satisfies the axioms, because h is U-symmetric.

Example

(Housing Market Rule). The TTC rule associated with the inheritance structure h expressed in Fig. 5 satisfies the axioms, because h is U-symmetric. Since this rule is equivalent to the TTC rule associated with the inheritance structure $h'$ expressed in Fig. 3, the latter rule also satisfies the axioms, although $h'$ is not U-symmetric.

As mentioned above, a rule satisfying the axioms can be described also by a TTC rule associated with an inheritance structure that is not U-symmetric. This means that even if a rule is described by a TTC rule associated with an inheritance structure that is not U-symmetric, there remains a chance that the rule satisfies the axioms. In the following, we show that the canonical form is useful to clarify not only what rules are equivalent but also what rules satisfy the axioms.²⁵

Proposition 1

If an inheritance structure is U-symmetric, then it is the canonical form of itself.

Since, by this proposition, the canonical form is a necessary condition for U-symmetry, when we want to show that a TTC rule associated with an inheritance structure satisfies the axioms, it is necessary and sufficient to establish that the canonical form of the inheritance structure is U-symmetric. The following corollary states this formally.

Corollary 1

A rule f satisfies strategy-proofness, Pareto-efficiency, and the identical preferences lower bound if and only if f is a top trading cycle rule associated with an inheritance structure h whose canonical form is U-symmetric.

Example

(Housing Market Rule). The TTC rule associated with the inheritance structure h expressed in Fig. 3 satisfies the axioms, because the canonical form of h, expressed in Fig. 5, is U-symmetric.

Example

(Sequential Dictatorial Rule). The TTC rule associated with the inheritance structure h expressed in Fig. 4 does not satisfy the axioms, because the canonical form of h, which is itself, is not U-symmetric.

Example

(MDPE Rule). The TTC rule associated with the inheritance structure h represented by Table 1 does not satisfy the axioms, because the canonical form of h, which is itself, is not U-symmetric.

In the following, we establish that all TTC rules associated with inheritance structures that are AS-types satisfy the axioms. To do so, we show that the canonical form of any inheritance structure that is AS-type is U-symmetric.

Proposition 2

Given $(E,\sigma )$, let h be the inheritance structure that is AS-type for $(E,\sigma )$. Let $h^*$ be the canonical form of h. Then, $h^*$ is U-symmetric.

Corollary 2

All top trading cycle rules associated with the inheritance structures that are AS-types satisfy strategy-proofness, Pareto-efficiency, and the identical preferences lower bound.

Example

(Intermediate AS). From Corollary 2, the TTC rule associated with the inheritance structure that is AS-type represented by Table 4 satisfies the axioms. In fact, its canonical form, expressed in Fig. 6, is U-symmetric.

Example

(Comprehensive). Among the 270 inheritance structures that are canonical forms, in the three-agent and three-object case, 66 inheritance structures are U-symmetric. Of these, while 48 inheritance structures take the canonical forms of AS-types (including the housing market and serial dictatorial rules), 18 inheritance structures²⁶ take the canonical forms discussed in Examples and Remark labeled as “Basic Example.”

6 Independence of axioms

6.1 Axioms in Theorem 1

We verify that none of the axioms in Theorem 1 is redundant. We exhibit rules that satisfy all but one of the axioms. The no-assignment rule (which always assigns the null object to all agents) satisfies strategy-proofness and the identical preferences lower bound, but not Pareto-efficiency. Remark labeled as “Sequential Dictatorial Rule” exhibits a rule satisfying strategy-proofness and Pareto-efficiency but not the identical preferences lower bound. The following example exhibits a rule satisfying Pareto-efficiency and the identical preferences lower bound but not strategy-proofness.

Example 2

Consider the three-agent and three-object case. Denote $K=\{k_1,k_2,k_3\}$. Define f as follows: For any $R\in \mathcal {R}^3$,

• if $R_1=k_1,k_2,k_3$ and

  • 1. if $R_2=k_1,k_2,k_3$ or $k_2,k_1,k_3$ or $k_2,k_3,k_1$, then $f(R)=(k_1,k_2,k_3)$,

  • 2. if $R_2=k_1,k_3,k_2$ or $k_3,k_1,k_2$, then $f(R)=(k_1,k_3,k_2)$,

  • 3. if $R_2=k_3,k_2,k_1$ and $k_2 R_3 k_3$, then $f(R)=(k_1,k_3,k_2)$,

  • 4. if $R_2=k_3,k_2,k_1$ and $k_3 R_3 k_2$, then $f(R)=(k_1,k_2,k_3)$;

• if $R_1=k_1,k_3,k_2$ and

  • 1. if $R_2=k_1,k_2,k_3$ or $k_2,k_1,k_3$, then $f(R)=(k_1,k_2,k_3)$,

  • 2. if $R_2=k_1,k_3,k_2$ or $k_3,k_1,k_2$ or $k_3,k_2,k_1$, then $f(R)=(k_1,k_3,k_2)$,

  • 3. if $R_2=k_2,k_3,k_1$ and $k_2 R_3 k_3$, then $f(R)=(k_1,k_3,k_2)$,

  • 4. if $R_2=k_2,k_3,k_1$ and $k_3 R_3 k_2$, then $f(R)=(k_1,k_2,k_3)$;

• if $R_1=k_2,\dots$ and

  • 1. if $k_1 R_2 k_3$ or $k_3 R_3 k_1$, then $f(R)=(k_2,k_1,k_3)$,

  • 2. if $k_3 R_2 k_1$ and $k_1 R_3 k_3$, then $f(R)=(k_2,k_3,k_1)$;

• if $R_1=k_3,\dots$ and

  • 1. if $k_1 R_2 k_2$ or $k_2 R_3 k_1$, then $f(R)=(k_3,k_1,k_2)$,

  • 2. if $k_2 R_2 k_1$ and $k_1 R_3 k_2$, then $f(R)=(k_3,k_2,k_1)$.

Then, f satisfies Pareto-efficiency and the identical preferences lower bound but not strategy-proofness.

6.2 Identical preferences lower bound versus non-bossiness and reallocation-proofness

From Remark labeled as “Sequential Dictatorial Rule,” we know that non-bossiness and reallocation-proofness do not imply the identical preferences lower bound. The following example exhibits a rule that satisfies the identical preferences lower bound but violates non-bossiness and reallocation-proofness. Thus, the former property does not imply the later ones.

Example 3

Consider the three-agent and three-object case. Denote $K=\{k_1,k_2,k_3\}$. Define f as follows: For any $R\in \mathcal {R}^3$,

• 1. if $R_1=k_1,k_2,k_3$ and $R_2=k_3,k_2,k_1$ and $R_3=k_2,k_3,k_1$, then $f(R)=(k_1,k_3,k_2)$,

• 2. if $R_1=k_1,k_3,k_2$ and $R_2=k_1,\dots$ or $k_3,k_1,k_2$, then $f(R)=(k_2,k_1,k_3)$,

• 3. if $R_1=k_1,k_3,k_2$ and $R_2=k_2,\dots$ or $k_3,k_2,k_1$, then $f(R)=(k_1,k_2,k_3)$,

• 4. otherwise, $f(R)=(k_2,k_1,k_3)$.

This rule satisfies the identical preferences lower bound but not non-bossiness. The proof is left to the reader. We only show that this rule does not satisfy reallocation-proofness.

Let $R_1=k_3,k_1,k_2$, $R_2=k_3,k_1,k_2$, and $R_3=k_2,k_3,k_1$. Then, we have

$$\begin{aligned} f(R_1,R_2,R_3)=(k_2,k_1,k_3). \end{aligned}$$

Let $\tilde{R}_1=k_1,k_2,k_3$ and $\tilde{R}_2=k_3,k_2,k_1$. Then, we have

$$\begin{aligned} f(\tilde{R}_1,R_2,R_3)=(k_2,k_1,k_3)\quad \text { and }\quad f(R_1, \tilde{R}_2,R_3)=(k_2,k_1,k_3), \end{aligned}$$

and

$$\begin{aligned} f(\tilde{R}_1, \tilde{R}_2,R_3)=(k_1,k_3,k_2). \end{aligned}$$

Hence, it holds that

$$\begin{aligned} f_2(\tilde{R}_1, \tilde{R}_2,R_3)=k_3 P_1 k_2= f_1(R_1,R_2,R_3) \end{aligned}$$

and

$$\begin{aligned} f_1(\tilde{R}_1, \tilde{R}_2,R_3)=k_1 R_2 k_1= f_2(R_1,R_2,R_3), \end{aligned}$$

and that

$$\begin{aligned} f_1(R_1,R_2,R_3)=f_1(\tilde{R}_1,R_2,R_3)=k_2\ne k_1=f_1(\tilde{R}_1, \tilde{R}_2,R_3) \end{aligned}$$

and

$$\begin{aligned} f_2(R_1,R_2,R_3)=f_2(R_1,\tilde{R}_2,R_3)=k_1\ne k_3=f_2(\tilde{R}_1, \tilde{R}_2,R_3). \end{aligned}$$

Therefore, this rule does not satisfy reallocation-proofness.

7 Concluding remarks

We have identified the class of rules satisfying strategy-proofness, Pareto-efficiency, and the identical preferences lower bound. We have shown that any rule of this class can be described by a TTC rule associated with a U-symmetric inheritance structure. Thus, if we are interested in the rules satisfying the axioms, it is sufficient to focus on the class of the TTC rules associated with U-symmetric inheritance structures.

Although some rules satisfying the axioms can be described also by a TTC rule associated with an inheritance structure that is not U-symmetric, we have provided the necessary and sufficient condition to clarify whether the rule satisfies the axioms. Thereby, we have shown that this class includes a variety of rules, such as Abdulkadiroğlu and Sönmez’s (1999) rules.

Proofs

1.1 “If” Part of Theorem 1

Let h be a U-symmetric inheritance structure. Denote by f the TTC rule associated with h. Since Pápai (2000) has shown that f satisfies strategy-proofness and Pareto-efficiency, we only show that f satisfies the identical preferences lower bound.

Let $i\in N$ and $R\in \mathcal {R}^n$. Let denote $x_i=f_i(R)$ and $\bar{x}_i=f_i(R(R_i))$. We show that $x_i R_i \bar{x}_i$. Suppose to the contrary that

$$\begin{aligned} \bar{x}_iP_i x_i. \end{aligned}$$

Then, we have

$$\begin{aligned} \bar{x}_i\in K. \end{aligned}$$

We express

$$\begin{aligned} R_i=k_1, k_2, \dots , k_m, \bar{x}_i,\dots , x_i. \end{aligned}$$

Claim 1: $i\in H(k_1,\dots , k_m, \bar{x}_i).$

Note that

$$\begin{aligned} K(m+2,R(R_i))=\{k_1, k_2, \dots , k_m, \bar{x}_i\}. \end{aligned}$$

Since $f_i(R(R_i))=\bar{x}_i$, there exists $(\bar{x}_i, \bar{k}_1,\dots , \bar{k}_{\bar{m}})\in \mathcal {C}$ such that $\{\bar{x}_i, \bar{k}_1,\dots , \bar{k}_{\bar{m}}\} \subset K(m+2,R(R_i))$ and

$$\begin{aligned} h(\bar{x}_i, \bar{k}_1,\dots , \bar{k}_{\bar{m}})=i, \end{aligned}$$

which implies

$$\begin{aligned} i\in H(\bar{x}_i, \bar{k}_1,\dots , \bar{k}_{\bar{m}}). \end{aligned}$$

Since, for any $c,c'\in \mathcal {C}$ such that $c\subset c'$, we have $H(c)\subset H(c')$, by U-symmetry, it holds that

$$\begin{aligned} i\in H(k_1,\dots , k_m, \bar{x}_i). \end{aligned}$$

$\square$

Let t denote the round number at R such that agent i leaves with $x_i$. (When $x_i=0$, set t as the final round number plus 1, and in the following, regard $K(t, R)=K$ and $N(t, R)=\{j\in N:f_j(R)\in K\}$.) Note that for any $k\in K$ such that $k R_i \bar{x}_i$, $k\in K(t, R)$. Hence, we can arrange all elements of K(t, R) in order as follows:

$$\begin{aligned} \left( k_1,k_2,\dots , k_m,\bar{x}_i, k'_1,\dots , k'_{m'}\right) \in \mathcal {C}. \end{aligned}$$

Claim 2: $i\in H(k_1,k_2,\dots , k_m,\bar{x}_i, k'_1,\dots , k'_{m'}).$

Since, for any $c,c'\in \mathcal {C}$ such that $c\subset c'$, we have $H(c)\subset H(c')$, by Claim 1, it holds that

$$\begin{aligned} i\in H \left( k_1,k_2,\dots , k_m,\bar{x}_i, k'_1,\dots , k'_{m'}\right) . \end{aligned}$$

$\square$

Claim 3: $\#H \left( k_1,k_2,\dots , k_m,\bar{x}_i, k'_1,\dots , k'_{m'}\right) =\#N(t, R).$

Note, by definition, that

$$\begin{aligned} \begin{aligned} H&(k_1,k_2,\dots , k_m,\bar{x}_i, k'_1,\dots , k'_{m'})\\&=\{h(k_1)\}\cup \{h(k_1,k_2)\}\cup \cdots \cup \{h(k_1,k_2,\dots , k_m,\bar{x}_i, k'_1,\dots , k'_{m'})\}. \end{aligned} \end{aligned}$$

Since, for any $c, c'\in \mathcal {C}$ such that $c\subset c'$ and $c\ne c'$, we have $h(c)\ne h(c'),$ it holds that

$$\begin{aligned} \#H \left( k_1,k_2,\dots , k_m,\bar{x}_i, k'_1,\dots , k'_{m'}\right) =\#K(t, R). \end{aligned}$$

Since $\#K(t, R)=\#N(t, R)$, it follows that

$$\begin{aligned} \#H \left( k_1,k_2,\dots , k_m,\bar{x}_i, k'_1,\dots , k'_{m'}\right) =\#N(t, R). \end{aligned}$$

$\square$

Claim 4: We have a contradiction.

Let $j\in N(t, R)$. Then, there exists $c\in \mathcal {C}$ such that each coordinate of c is in K(t, R) and $h(c)=j.$ Further, there exists $c'\in \mathcal {C}$ such that $c\subset c'$ and $c'\simeq (k_1,k_2,\dots , k_m,\bar{x}_i, k'_1,\dots , k'_{m'})$. By U-symmetry, it holds that

$$\begin{aligned} j\in H \left( k_1,k_2,\dots , k_m,\bar{x}_i, k'_1,\dots , k'_{m'}\right) . \end{aligned}$$

Hence, we have

$$\begin{aligned} N(t, R) \subset H \left( k_1,k_2,\dots , k_m,\bar{x}_i, k'_1,\dots , k'_{m'}\right) . \end{aligned}$$

Note that $i\notin N(t,R)$. Since, by Claim 2, we have

$$\begin{aligned} i\in H \left( k_1,k_2,\dots , k_m,\bar{x}_i, k'_1,\dots , k'_{m'}\right) , \end{aligned}$$

this implies that

$$\begin{aligned} \#N(t, R)<\#H \left( k_1,k_2,\dots , k_m,\bar{x}_i, k'_1,\dots , k'_{m'}\right) , \end{aligned}$$

which contradicts Claim 3. $\square$

Therefore, f satisfies the identical preferences lower bound. $\square$

1.2 “Only If” Part of Theorem 1

Let f be a rule satisfying strategy-proofness, Pareto-efficiency, and the identical preferences lower bound. We show that there exists a U-symmetric inheritance structure such that f is the TTC rule associated with it.

Step 1: We construct a U-symmetric inheritance structure h from f.

For any non-empty $C \subset K$ such that $\#C\le \#N$, define

$$\begin{aligned} \mathcal {R}(C)=\{R_i\in \mathcal {R}: \text { for any }k\in C\text { and any }k'\notin C, k P_i k' \}. \end{aligned}$$

For any non-empty $C \subset K$ such that $\#C\le \#N$ and any $R_i \in \mathcal {R}(C)$, define

$$\begin{aligned} \hat{H}(C, R_i)=\{j\in N:f_j(R(R_i))\in C \}. \end{aligned}$$

Claim 1-1: For any non-empty $C \subset K$ such that $\#C\le \#N$ and any $R_i, R'_i \in \mathcal {R}(C)$, it holds that

$$\begin{aligned} \hat{H}(C, R_i)=\hat{H}(C, R_i'). \end{aligned}$$

Let $j\in \hat{H}(C, R_i)$, that is, $f_j(R(R_i))\in C$. Let $R_j=R_i$. Then, by the identical preferences lower bound, we have

$$\begin{aligned} f_j(R_j, R(R'_i)_{-j}) R_jf_j(R(R_i)), \end{aligned}$$

which means that

$$\begin{aligned} f_j(R_j, R(R'_i)_{-j})\in C. \end{aligned}$$

Then, by strategy-proofness, we have

$$\begin{aligned} f_j(R(R'_i))\in C, \end{aligned}$$

which implies that

$$\begin{aligned} j\in \hat{H}(C, R'_i). \end{aligned}$$

This means the desired result. $\square$

By Claim 1-1, we can describe $\hat{H}(C,R_i)$ by $\hat{H}(C)$. Then, by Pareto-efficiency, for any non-empty $C \subset K$ such that $\#C\le \#N$, we have

$$\begin{aligned} \#\hat{H}(C)=\#C. \end{aligned}$$

Claim 1-2: For any non-empty $C, C'\subset K$ such that $C\subset C'$ and $\#C'\le \#N$, it holds that

$$\begin{aligned} \hat{H}(C)\subset \hat{H}(C'). \end{aligned}$$

For simplicity of notation, we describe $C=\{k_1,\dots , k_\ell \}$ and $C'=\{k_1,\dots ,k_\ell ,k_{\ell +1},\dots , k_{\ell '}\}$. Let $R_i\in \mathcal {R}$ be as follows:

$$\begin{aligned} R_i=k_1,\dots ,k_\ell ,k_{\ell +1},\dots , k_{\ell '},\dots . \end{aligned}$$

Then, we have $R_i\in \mathcal {R}(C)$ and $R_i\in \mathcal {R}(C')$. Hence, we have

$$\begin{aligned} f_j(R(R_i))\in C \Rightarrow f_j(R(R_i))\in C', \end{aligned}$$

which means that

$$\begin{aligned} \hat{H}(C)\subset \hat{H}(C'). \end{aligned}$$

This is the desired result. $\square$

We construct a function $h:\mathcal {C} \rightarrow N$ as follows: For any $c=(k_1)\in \mathcal {C}$,

$$\begin{aligned} \{h(c)\}=\hat{H}(\{k_1\}). \end{aligned}$$

For any $m> 1$ and any $c=(k_1,\dots , k_{m-1}, k_m)\in \mathcal {C}$,

$$\begin{aligned} \{h(c)\}=\hat{H}(\{k_1,\dots , k_{m-1}, k_m\}){\setminus } \hat{H}(\{k_1,\dots , k_{m-1}\}). \end{aligned}$$

This is well defined.

Claim 1-3: h is an inheritance structure.

Let $c,c'\in \mathcal {C}$ be such that $c\subset c'$ and $c\ne c'$. For simplicity of notation, we describe $c=(k_1,\dots , k_m)$ and $c'=(k_1,\dots , k_m, k_{m+1},\dots , k_{m'})$ with $m<m'$. We show that

$$\begin{aligned} h(c)\ne h(c'). \end{aligned}$$

Remember that

$$\begin{aligned} \{h(c)\}=\hat{H}(\{k_1,\dots , k_{m-1}, k_m\}){\setminus } \hat{H}(\{k_1,\dots , k_{m-1}\}) \end{aligned}$$

and

$$\begin{aligned} \{h(c')\}=\hat{H}(\{k_1,\dots , k_{m-1}, k_{m'}\}){\setminus } \hat{H}(\{k_1,\dots , k_{m'-1}\}). \end{aligned}$$

Since $\{k_1,\dots , k_{m-1}, k_m\}\subset \{k_1,\dots , k_{m'-1}\}$, by Claim 1-2, it holds that

$$\begin{aligned} \hat{H}(\{k_1,\dots , k_{m-1}, k_m\})\subset \hat{H}(\{k_1,\dots , k_{m'-1}\}), \end{aligned}$$

which implies the desired result. $\square$

Claim 1-4: The inheritance structure h is U-symmetric.

Let $c,c'\in \mathcal {C}$ be such that $c\simeq c'$. We show that

$$\begin{aligned} H(c)=H(c'). \end{aligned}$$

For simplicity of notation, we describe $c=(k_1,\dots , k_m)$. Then, by Claim 1-2, it is sufficient to show that

$$\begin{aligned} H(c)\equiv \bigcup _{c''\subset c} \{h(c'')\}=\hat{H}(\{k_1,\dots , k_m\}). \end{aligned}$$

Since, for any $c''=(k_1,\dots , k_\ell ) \subset c$, $\{k_1,\dots , k_\ell \} \subset \{k_1,\dots , k_m\}$, by Claim 1-2, it holds that

$$\begin{aligned} \{h(c'')\}=\hat{H}(\{k_1,\dots , k_{\ell -1}, k_\ell \}){\setminus } \hat{H}(\{k_1,\dots , k_{\ell -1}\}) \subset \hat{H}(\{k_1,\dots , k_m\}). \end{aligned}$$

Hence, we have

$$\begin{aligned} \bigcup _{c''\subset c} \{h(c'')\}\subset \hat{H}(\{k_1,\dots , k_m\}). \end{aligned}$$

Furthermore, since $\#\bigcup _{c''\subset c}\{h(c'')\}=m=\#\hat{H}(\{k_1,\dots , k_m\})$, we also have

$$\begin{aligned} \bigcup _{c''\subset c} \{h(c'')\}= \hat{H}(\{k_1,\dots , k_m\}). \end{aligned}$$

Therefore, h is the U-symmetric inheritance structure.$\square$

Step 2: We show that f coincides with the TTC rule associated with h.

Let $R\in \mathcal {R}^n$. Let $(k_1, i_1, k_2, i_2 , k_3, \dots , i_m)$ be a cycle occurring at 1st Round of the TTC rule associated with h at R. (When $m=1$, go directly to Claim 2-3.) Let $\hat{R}_{\{i_1,\dots ,i_m\}}$ be as follows:

$$\begin{aligned} \hat{R}_{i_1}= & {} k_2,k_1,\dots ,\\ \hat{R}_{i_2}= & {} k_3,k_2,\dots ,\\&\vdots&\\ \hat{R}_{i_m}= & {} k_1,k_m,\dots . \end{aligned}$$

Claim 2-1: For any agent $i_\ell$ in the cycle and any $R'_{-i_\ell }\in \mathcal {R}^{n-1}$, we have

$$\begin{aligned} f_{i_\ell }(\hat{R}_{i_\ell }, R'_{-i_\ell })=k_{\ell } \text { or } k_{\ell +1}, \end{aligned}$$

where we regard $m+1$ as 1.

Without loss of generality, we focus on agent $i_1$. Let $R^*_i\in \mathcal {R}$ be as follows:

$$\begin{aligned} R^*_i=k_1,\dots , \end{aligned}$$

that is, $R^*_i\in \mathcal {R}(\{k_1\})$. Since object $k_1$ points to agent $i_1$, it holds that

$$\begin{aligned} h(k_1)=i_1, \end{aligned}$$

which means that

$$\begin{aligned} f_{i_1}(R(R^*_i))=k_1. \end{aligned}$$

Then, by the identical preferences lower bound, for any $R'_{-i_1}\in \mathcal {R}^{n-1}$, it holds that

$$\begin{aligned} f_{i_1}(R^*_{i_1}, R'_{-i_1}) R^*_{i_1} f_{i_1}(R(R^*_i))=k_1, \end{aligned}$$

where $R^*_{i_1}=R^*_i$. This implies that

$$\begin{aligned} f_{i_1} \left( R^*_{i_1}, R'_{-i_1} \right) =k_1. \end{aligned}$$

Then, by strategy-proofness, we have

$$\begin{aligned} f_{i_1} \left( \hat{R}_{i_1}, R'_{-i_1} \right) \hat{R}_{i_1} k_1, \end{aligned}$$

which means that

$$\begin{aligned} f_{i_1} \left( \hat{R}_{i_1}, R'_{-i_1} \right) =k_1 \text { or } k_2. \end{aligned}$$

$\square$

Claim 2-2: For any agent $i_{\ell }$ in the cycle and any $R'_{-\{i_1,\dots ,i_m\}}\in \mathcal {R}^{n-m}$, we have

$$\begin{aligned} f_{i_\ell }\left( \hat{R}_{\{i_1,\dots ,i_m\}}, R'_{-\{i_1,\dots ,i_m\}} \right) =k_{\ell +1}, \end{aligned}$$

where we regard $m+1$ as 1.

Without loss of generality, we focus on agent $i_1$. Suppose that for some $R'_{-\{i_1,\dots ,i_m\}}\in \mathcal {R}^{n-m}$,

$$\begin{aligned} f_{i_1}\left( \hat{R}_{\{i_1,\dots ,i_m\}}, R'_{-\{i_1,\dots ,i_m\}} \right) =k_1. \end{aligned}$$

Then, by Claim 2-1, we have

$$\begin{aligned} f_{i_m}\left( \hat{R}_{\{i_1,\dots ,i_m\}}, R'_{-\{i_1,\dots ,i_m\}} \right) =k_m. \end{aligned}$$

Repeating the similar arguments, it follows that

$$\begin{aligned} f_{i_1}\left( \hat{R}_{\{i_1,\dots ,i_m\}}, R'_{-\{i_1,\dots ,i_m\}} \right)= & {} k_1,\\ f_{i_2}\left( \hat{R}_{\{i_1,\dots ,i_m\}}, R'_{-\{i_1,\dots ,i_m\}} \right)= & {} k_2,\\&\vdots&\\ f_{i_{m}}\left( \hat{R}_{\{i_1,\dots ,i_m\}}, R'_{-\{i_1,\dots ,i_m\}} \right)= & {} k_m, \end{aligned}$$

which contradict Pareto-efficiency. Hence, by Claim 2-1, for any $R'_{-\{i_1,\dots ,i_m\}}\in \mathcal {R}^{n-m}$, we have

$$\begin{aligned} f_{i_1}\left( \hat{R}_{\{i_1,\dots ,i_m\}}, R'_{-\{i_1,\dots ,i_m\}} \right) =k_2. \end{aligned}$$

$\square$

Claim 2-3: For any agent $i_\ell$ in the cycle and any $R'_{-\{i_1,\dots ,i_m\}}\in \mathcal {R}^{n-m}$, we have

$$\begin{aligned} f_{i_\ell }\left( R_{\{i_1,\dots , i_m\}}, R'_{-\{i_1,\dots ,i_m\}}\right) =k_{\ell +1}, \end{aligned}$$

where we regard $m+1$ as 1.

Let us consider the case $m=1$. Since agent $i_1$’s best object at $R_{i_1}$ is $k_1(=k_{1+1})$, we have $R_{i_1}\in \mathcal {R}(\{k_1\})$. Since object $k_1$ points to agent $i_1$, it holds that

$$\begin{aligned} h(k_1)=i_1, \end{aligned}$$

which means that

$$\begin{aligned} f_{i_1}(R(R_{i_1}))=k_1. \end{aligned}$$

Then, by the identical preferences lower bound, for any $R'_{-i_1}\in \mathcal {R}^{n-1}$, it holds that

$$\begin{aligned} f_{i_1}(R_{i_1}, R'_{-i_1}) R_{i_1} f_{i_1}(R(R_{i_1}))=k_1. \end{aligned}$$

This implies that

$$\begin{aligned} f_{i_1}(R_{i_1}, R'_{-i_1})=k_1. \end{aligned}$$

This is the desired result.

Let us consider the case $m>1$. Pick any one agent, say $i_1$, in the cycle. Since agent $i_1$’s best object at $R_{i_1}$ is $k_2$, by strategy-proofness and Claim 2-2, we have

$$\begin{aligned} f_{i_1}\left( R_{i_1}, \hat{R}_{\{i_2,\dots ,i_m\}}, R'_{-\{i_1,\dots ,i_m\}}\right) =k_{2}. \end{aligned}$$

By Claim 2-1, this implies that for any other agent $i_\ell$ in the cycle,

$$\begin{aligned} f_{i_\ell } \left( R_{i_1}, \hat{R}_{\{i_2,\dots ,i_m\}}, R'_{-\{i_1,\dots ,i_m\}}\right) =k_{\ell +1}, \end{aligned}$$

where we regard $m+1$ as 1.

Next, pick any two agents, say $i_1$ and $i_2$, in the cycle. Then, by strategy-proofness, we have

$$\begin{aligned} f_{i_1}\left( R_{i_1}, R_{i_2}, \hat{R}_{\{i_3,\dots ,i_m\}}, R'_{-\{i_1,\dots ,i_m\}}\right) =k_{2} \end{aligned}$$

and

$$\begin{aligned} f_{i_2}\left( R_{i_1}, R_{i_2}, \hat{R}_{\{i_3,\dots ,i_m\}}, R'_{-\{i_1,\dots ,i_m\}}\right) =k_{3}. \end{aligned}$$

By Claim 2-1, these imply that for any other agent $i_\ell$ in the cycle,

$$\begin{aligned} f_{i_\ell }(R_{i_1}, R_{i_2}, \hat{R}_{\{i_3,\dots ,i_m\}}, R'_{-\{i_1,\dots ,i_m\}})=k_{\ell +1}, \end{aligned}$$

where we regard $m+1$ as 1. Repeating the same argument, it holds that for any agent $i_\ell$ in the cycle and any $R'_{-\{i_1,\dots ,i_m\}}\in \mathcal {R}^{n-m}$,

$$\begin{aligned} f_{i_\ell }\left( R_{\{i_1,\dots , i_m\}}, R'_{-\{i_1,\dots ,i_m\}}\right) =k_{\ell +1}, \end{aligned}$$

where we regard $m+1$ as 1. $\square$

Remark 4

Claim 2-3 means that for any agent i in any cycle occurring at 1st Round at R, $f_i(R)$ coincides with the assignment determined by the TTC rule associated with h at R.

Let $(k'_1, i'_1, k'_2, i'_2 , k'_3, \dots , i'_m)$ be a cycle occurring at 2nd Round of the TTC rule associated with h at R. (When $m=1$, go directly to Claim 2-5.) Let $\hat{R}_{\{i'_1,\dots ,i'_m\}}$ be as follows:

$$\begin{aligned} \hat{R}_{i'_1}= & {} k'_2,k'_1,\dots ,\\ \hat{R}_{i'_2}= & {} k'_3,k'_2,\dots ,\\&\vdots&\\ \hat{R}_{i'_m}= & {} k'_1,k'_m,\dots . \end{aligned}$$

Claim 2-4: For any agent $i'_{\ell }$ in the cycle and any $R'_{-(N(2,R)\cup \{i'_\ell \})}\in \mathcal {R}^{n-\#N(2,R)-1}$, we have

$$\begin{aligned} f_{i'_\ell }\left( \hat{R}_{i'_\ell }, R_{N(2,R)}, R'_{-(N(2,R)\cup \{i'_\ell \})}\right) =k'_\ell \text { or } k'_\ell +1. \end{aligned}$$

where we regard $m+1$ as 1.

Without loss of generality, we focus on agent $i'_1$. For simplicity of notation, we describe $K(2, R)=\{k_1,\dots , k_{\bar{\ell }}\}$. Let $R^*_i\in \mathcal {R}$ be as follows:

$$\begin{aligned} R^*_i=k_1,\dots , k_{\bar{\ell }}, k'_1,\dots , \end{aligned}$$

that is, $R^*_i\in \mathcal {R}(K(2,R) \cup \{k'_1\})$. Since object $k'_1$ points to agent $i'_1$, there exists $(k'_1, \hat{k}_1,\dots , \hat{k}_{\ell '})\in \mathcal {C}$ such that $\{\hat{k}_1,\dots , \hat{k}_{\ell '}\}\subset K(2,R)$ and

$$\begin{aligned} h(k'_1, \hat{k}_1,\dots , \hat{k}_{\ell '})=i'_1, \end{aligned}$$

that is,

$$\begin{aligned} \{i'_1\}=\hat{H}(\{k'_1, \hat{k}_1,\dots , \hat{k}_{\ell '}\}){\setminus }\hat{H}(\{k'_1, \hat{k}_1,\dots , \hat{k}_{\ell '-1}\}). \end{aligned}$$

Hence, by Claim 1-2, we have

$$\begin{aligned} i'_1 \in \hat{H}(K(2,R) \cup \{k'_1\}), \end{aligned}$$

which means that

$$\begin{aligned} f_{i'_1}(R(R^*_i))\in K(2,R) \cup \{k'_1\}. \end{aligned}$$

Since, by the identical preferences lower bound, for any $R'_{-i'_1}\in \mathcal {R}^{n-1}$, it holds that

$$\begin{aligned} f_{i'_1} \left( R^*_{i'_1}, R'_{-i'_1}\right) R^*_{i'_1} f_{i'_1}(R(R^*_i)), \end{aligned}$$

where $R^*_{i'_1}=R^*_i$, we have

$$\begin{aligned} f_{i'_1} \left( R^*_{i'_1}, R'_{-i'_1}\right) \in K(2,R) \cup \{k'_1\}. \end{aligned}$$

From Remark 4, we know that for any $R'_{-N(2,R)}\in \mathcal {R}^{n-\#N(2,R)}$,

$$\begin{aligned} f_{i'_1} \left( R_{N(2,R)}, R'_{-N(2,R)}\right) \notin K(2,R). \end{aligned}$$

Hence, we have

$$\begin{aligned} f_{i'_1}(R^*_{i'_1}, R_{N(2,R)}, R'_{-(N(2,R)\cup \{i'_1\})})=k'_1. \end{aligned}$$

Then, by strategy-proofness, we have

$$\begin{aligned} f_{i'_1} \left( \hat{R}_{i'_1}, R_{N(2,R)}, R'_{-(N(2,R)\cup \{i'_1\})}\right) \hat{R}_{i_1} k'_1, \end{aligned}$$

which means that

$$\begin{aligned} f_{i'_1} \left( \hat{R}_{i'_1}, R_{N(2,R)}, R'_{-(N(2,R)\cup \{i'_1\})}\right) =k'_1 \text { or } k'_2. \end{aligned}$$

$\square$

Claim 2-5: For any agent $i'_\ell$ in the cycle and any $R'_{-(N(2,R)\cup \{i'_1,\dots ,i'_m\})}\in \mathcal {R}^{n-\#N(2,R)-m}$, we have

$$\begin{aligned} f_{i'_{\ell }}(R_{\{i'_1,\dots ,i'_m\}},R_{N(2,R)}, R'_{-(N(2,R)\cup \{i'_1,\dots ,i'_m\})})=k'_{\ell +1}, \end{aligned}$$

where we regard $m+1$ as 1.

By the same argument as 1st Round, we have the desired result. $\square$

Remark 5

Claim 2-5 means that for any agent i in any cycle occurring at 2nd Round at R, $f_i(R)$ coincides with the assignment determined by the TTC rule associated with h at R.

Continuing the argument in the following rounds, we have the desired result. $\square$

1.3 Proof of Proposition 1

Let h be a U-symmetric inheritance structure. Denote by f the TTC rule associated with h. Let $c=(k_1,\dots , k_{\ell })\in \mathcal {C}$. For any $\ell '\le \ell$, we denote simply as follows:

$$\begin{aligned} h(k_1,\dots , k_{\ell '})=i_{\ell '}, \end{aligned}$$

that is,

$$\begin{aligned} H(k_1,\dots ,k_{\ell })=\{i_1,\dots , i_{\ell }\}. \end{aligned}$$

We show that $f_{i_{{\ell }}}(R(h,c))= k_{1}.$

Claim 1: For any $i_{{\ell '}}\in \{i_1,\dots , i_{\ell -1}\}$, we have

$$\begin{aligned} f_{i_{{\ell '}}}(R(h,c))\ne k_1. \end{aligned}$$

Suppose to the contrary that for some $i_{{\ell '}}\in \{i_1,\dots , i_{\ell -1}\}$, it holds that

$$\begin{aligned} f_{i_{{\ell '}}}(R(h,c))= k_1. \end{aligned}$$

Since $R_{i_{{\ell '}}}(h,c)=k_{\ell '+1}, k_1, \dots$ and f satisfies Pareto-efficiency, we must have some $j\ne i_{{\ell '}}$ such that

$$\begin{aligned} f_{j}(R(h,c))= k_{\ell '+1}. \end{aligned}$$

However, since $k_1P_j(h,c)k_{\ell '+1}$, it contradicts Pareto-efficiency of f. $\square$

Let t denote round number at R(h, c) such that a cycle including $k_1$ is formed.

Claim 2: $K(t, R(h,c)) \subset \{k_2,\dots , k_{\ell }\}.$

Since, for any $j\notin \{i_1,\dots , i_{\ell -1}\}$, $R_j(h,c)=k_1,\dots$, and $k_1\notin K(t, R(h,c))$, it holds that

$$\begin{aligned} N(t, R(h,c)) \subset \{i_1,\dots , i_{\ell -1}\}. \end{aligned}$$

Since, for any $i_{{\ell '}}\in \{i_1,\dots , i_{\ell -1}\}$, $R_{i_{{\ell '}}}(h,c)=k_{\ell '+1}, k_1, \dots$, and $k_1 \notin K(t, R(h,c))$, we have

$$\begin{aligned} K(t, R(h,c)) \subset \{k_2,\dots , k_{\ell }\}. \end{aligned}$$

$\square$

Claim 3: At Round t, object $k_1$ points to some agent $i_{\ell ^*} \in \{i_1,\dots , i_{\ell }\}$.

Suppose to the contrary that $k_1$ points to $j\notin \{i_1,\dots , i_{\ell }\}$. That is, for some $(k_1,\hat{k}_2,\dots ,\hat{k}_m)\in \mathcal {C}$ such that $\hat{k}_2,\dots ,\hat{k}_m\in K(t, R(h,c))$,

$$\begin{aligned} h(k_1,\hat{k}_2,\dots ,\hat{k}_m)=j. \end{aligned}$$

Let $(k_1,\hat{k}_2,\dots ,\hat{k}_m,\dots , \hat{k}_{m'})\in \mathcal {C}$ be such that

$$\begin{aligned} (k_1,\hat{k}_2,\dots ,\hat{k}_m,\dots , \hat{k}_{m'}) \simeq (k_1,k_2,\dots ,k_{\ell }), \end{aligned}$$

which is well defined because $\hat{k}_2,\dots ,\hat{k}_m \in K(t, R(h,c)) \subset \{k_2,\dots , k_{\ell }\}$ by Claim 2. Then, we have

$$\begin{aligned} j=h(k_1,\hat{k}_2,\dots ,\hat{k}_m)\in H(k_1,\hat{k}_2,\dots ,\hat{k}_m,\dots , \hat{k}_{m'}). \end{aligned}$$

Since h is U-symmetric, we also have

$$\begin{aligned} j\in H(k_1,\hat{k}_2,\dots ,\hat{k}_m,\dots , \hat{k}_{m'})=H(k_1,k_2,\dots ,k_{\ell }). \end{aligned}$$

However, since $H(k_1,k_2,\dots ,k_{\ell })=\{i_1,\dots , i_{\ell }\}$, it means that $j\in \{i_1,\dots , i_{\ell }\}$, which is a contradiction. $\square$

In the case $i_{\ell ^*}=i_\ell$, since $R_{i_\ell }(h,c)=k_1, \dots$, $(k_1,i_\ell )$ forms a cycle at R(h, c). Thus, we have $f_{i_{{\ell }}}(R(h,c))= k_{1}$, which is the desired result. Hence, in the following, we consider only the case $i_{\ell ^*} \in \{i_1,\dots , i_{\ell -1}\}$.

Claim 4: At Round t, agent $i_{\ell ^*}$ points to object $k_{\ell ^*+1}$.

If $i_{\ell ^*}$ points to $k_1$, then it holds that $f_{i_{{\ell ^*}}}(R(h,c))= k_1$, which contradicts Claim 1. Hence, $i_{\ell ^*}$ does not point to $k_1$. Since $R_{i_{{\ell ^*}}}(h,c)=k_{\ell ^*+1}, k_1, \dots$ and $k_1\notin K(t, R(h,c))$, $i_{\ell ^*}$ points to $k_{\ell ^*+1}$. $\square$

Claim 5: At Round t, object $k_{\ell ^*+1}$ points to some agent $i_{\ell ^{**}} \in \{i_1,\dots , i_{\ell }\}{\setminus }\{i_{\ell ^*}\}$.

As this is shown by a way similar to Claim 3, we omit the detail. $\square$

In the case $i_{\ell ^{**}}=i_\ell$, since $R_{i_\ell }(h,c)=k_1, \dots$, $(k_1,i_{\ell ^{*}}, k_{\ell ^*+1},i_\ell )$ forms a cycle at R(h, c). Thus, we have $f_{i_{{\ell }}}(R(h,c))= k_{1}$, which is the desired result. Hence, in the following, we consider only the case $i_{\ell ^{**}} \in \{i_1,\dots , i_{\ell -1}\}{\setminus } \{i_{\ell ^*}\}$.

Repeating the similar argument, since $\{i_1,\dots , i_{\ell }\}$ is finite, we have

$$\begin{aligned} f_{i_{{\ell }}}(R(h,c))= k_{1}. \end{aligned}$$

Therefore, Proposition 1 is valid. $\square$

1.4 Proof of Proposition 2

For any $c=(k_1,\dots ,k_{\ell })\in \mathcal {C}$, define

$$\begin{aligned} K^e(c)=K^e \cup \{k_1,\dots , k_{\ell }\} \end{aligned}$$

and

$$\begin{aligned} N^e(c)=\cup _{k\in K^e(c)} \{E(k)\}. \end{aligned}$$

It is sufficient to show that for any $c=(k_1,\dots ,k_{\ell })\in \mathcal {C}$,

$$\begin{aligned} H(c)\equiv \bigcup _{c'\subset c} \{h^*(c')\} = N^e(c)\cup \bigcup _{m=1}^{\ell -\#N^e(c)}\{\sigma ^{-N^e(c)}(m)\} \end{aligned}$$

(1)

because the right-hand side depends only on the objects that compose c. We show this by the following induction.

• 1. When $c=(k_1)$, we have (1).

• 2. Assume that when $c=(k_1,\dots , k_{\ell -1})$, we have (1). Then, when $c=(k_1,\dots , k_{\ell })$, we have (1).

Denote by f the TTC rule associated with h.

The first part.

When $k_1\in K^e$, it holds that

$$\begin{aligned} f_{E(k_1)}(R(h^*,c))=k_1, \end{aligned}$$

that is, $\{h^*(c)\}=\{E(k_1)\}= N^e(c)$. Hence, we have (1).

When $k_1\notin K^e$, it holds that

$$\begin{aligned} f_{\sigma (1)}(R(h^*,c))=k_1, \end{aligned}$$

that is, $h^*(c)=\sigma (1)$. Hence, we have (1). Thus, the first part is valid.

The second part.

Let t denote round number at $R(h^*,c)$ such that $k_1$ is included in a cycle under f. Notice that until the end of Round t, no agent points to objects other than $k_1,\dots , k_{\ell }$ at $R(h^*,c)$. Hence, the objects in the cycle that includes $k_1$ at $R(h^*,c)$ belong to $\{k_1,\dots , k_{\ell }\}$. This means that any agent (also $h^*(c)$) in the cycle that includes $k_1$ at $R(h^*,c)$ must be pointed by some object in $\{k_1,\dots , k_{\ell }\}$ at Round t. Since the objects $k_1,\dots , k_{\ell }$ point to only agents in $N^e(c)\cup \bigcup _{m=1}^{\ell -\#N^e(c)}\{\sigma ^{-N^e(c)}(m)\}$ until the end of Round t, it implies that

$$\begin{aligned} h^*(c)\in N^e(c)\cup \bigcup _{m=1}^{\ell -\#N^e(c)}\{\sigma ^{-N^e(c)}(m)\}. \end{aligned}$$

(2)

Denote $\hat{c}=(k_1,\dots ,k_{\ell -1})$. Since $\hat{c}\subset c$, it follows that

$$\begin{aligned} N^e(\hat{c})\cup \bigcup _{m=1}^{(\ell -1)-\#N^e(\hat{c})}\{\sigma ^{-N^e(\hat{c})}(m)\} \subset N^e(c)\cup \bigcup _{m=1}^{\ell -\#N^e(c)}\{\sigma ^{-N^e(c)}(m)\}. \end{aligned}$$

Then, by the induction hypothesis, it means that

$$\begin{aligned} \bigcup _{c'\subset \hat{c}} \{h^*(c')\} \subset N^e(c)\cup \bigcup _{m=1}^{\ell -\#N^e(c)}\{\sigma ^{-N^e(c)}(m)\}. \end{aligned}$$

(3)

Notice that

$$\begin{aligned} \bigcup _{c'\subset c} \{h^*(c')\} =\bigcup _{c'\subset \hat{c}} \{h^*(c')\}\cup \{h^*(c)\}. \end{aligned}$$

By (2) and (3), it implies that

$$\begin{aligned} \bigcup _{c'\subset c} \{h^*(c')\} \subset N^e(c)\cup \bigcup _{m=1}^{\ell -\#N^e(c)}\{\sigma ^{-N^e(c)}(m)\}. \end{aligned}$$

Since both the sides have the same cardinality $\ell$, we have (1).

Therefore, Proposition 2 is valid. $\square$