# Simple dominance of fixed priority top trading cycles††thanks: I am grateful
to Oishee Banerjee for helpful suggestions. I am particularly indebted to
Szilvia Pápai whose insightful comments led to a significant improvement of
the contents of this paper. Thanks also to Clayton Thomas for his questions
and comments.

Pinaki Mandal E-mail<EMAIL_ADDRESS>Department of Economics, Arizona
State University, USA

###### Abstract

We study the implementation of fixed priority top trading cycles (FPTTC) rules
via simply dominant mechanisms (Pycia and Troyan, 2019) in the context of
assignment problems, where agents are to be assigned at most one indivisible
object and monetary transfers are not allowed. We consider both models – with
and without outside options, and characterize all simply dominant FPTTC rules
in both models. We further introduce the notion of simple strategy-proofness
to resolve the issue with agents being concerned about having time-
inconsistent preferences, and discuss its relation with simple dominance.

Keywords: Fixed priority top trading cycles; Assignment problem; Simple
dominance; Simple strategy-proofness; Indivisible goods

JEL Classification: C78; D82

##  1 Introduction

We consider the well-known assignment problem (also known as house allocation
problem or resource allocation problem) where a set of heterogeneous
indivisible objects are to be allocated among a group of agents so that each
agent receives at most one object and monetary transfers are not allowed. Such
problems arise when, for instance, the Government wants to assign houses to
the citizens, or hospitals to doctors, or a manager wants to allocate offices
to employees, or tasks to workers, or a professor wants to assign projects to
students. Agents are asked to report their strict preferences over the objects
and remaining unassigned (also known as the outside option), and a mechanism
selects an allocation (of the objects among the agents) based on the agents’
reports. Note that an object is acceptable to an agent if and only if she
prefers that object to the outside option.

An important consideration while designing mechanisms is to implement
desirable outcomes when the participating agents are strategic. The standard
notion of strategy-proofness requires truth-telling to be a weakly dominant
strategy, that is, no agent can be strictly better off by misreporting her
(true) preference.

Fixed priority top trading cycles (FPTTC) mechanism (Pápai, 2000) is a well-
known strategy-proof way to assign objects in the absence of
transfers.111Pápai (2000) uses the term “fixed endowment hierarchical exchange
rule” to refer to an FPTTC mechanism. An FPTTC mechanism works in steps. At
each step, the objects (available at that step) are owned by certain agents
who then trade their objects by forming top trading cycles (TTC).222TTC is due
to David Gale and discussed in Shapley and Scarf (1974). Ownership of the
objects at the start of each step is determined by an exogenously given
priority structure – a collection of strict priority rankings of the agents
indexed by the objects.

Apart from strategy-proofness, FPTTC mechanisms also satisfy group strategy-
proofness, Pareto efficiency, and non-bossiness (Satterthwaite and
Sonnenschein, 1981). Group strategy-proofness ensures that no group of agents
can jointly manipulate their reports so that all of them weakly benefit from
this manipulation, while at least one agent in the group strictly benefits.
Pareto efficiency ensures that there is no other way to allocate the objects
so that each agent is weakly better off (and hence some agent is strictly
better-off). Notice that no agent is assigned an unacceptable object in a
Pareto efficient allocation. Non-bossiness says that an agent cannot change
the assignment of another one without changing her own assignment. However,
despite their appealing theoretical properties, the use of FPTTC mechanisms in
practice is rare as participating agents find it difficult to understand them,
particularly the fact that these mechanisms are strategy-proof (see, for
example, Pathak (2017)).333Similar phenomena are also observed in other
settings, see Chen and Sönmez (2006), Hassidim et al. (2017), Hassidim et al.
(2018), Rees-Jones (2018), and Shorrer and Sóvágó (2018) for details.

The notion of obvious strategy-proofness (OSP) (Li, 2017) has emerged as a
remedy by strengthening strategy-proofness in a way so that it becomes
transparent to the participating agents that a mechanism is not manipulable.
The concept of OSP is based on the notion of obvious dominance in an
extensive-form game. A strategy $s_{i}$ of an agent $i$ in an extensive-form
game is obviously dominant if, whenever agent $i$ is called to play, even the
worst possible final outcome from following $s_{i}$ is at least as good as the
best possible outcome from following any deviating strategy $s^{\prime}_{i}$
of agent $i$, where the best and worst cases are determined by considering all
possible strategies that could be played by $i$’s opponents in the future,
keeping her own strategy fixed. A mechanism is OSP-implementable if one can
construct an extensive-form game that has an equilibrium in obviously dominant
strategies.

While OSP relaxes the assumption that the participating agents fully
comprehend how the strategies of opponents will affect outcomes, it still
presumes that they understand how their own future actions will affect
outcomes. In other words, when checking obvious dominance, the worst possible
final outcome and the best possible final outcome are taken only over
opponents’ strategies $s_{-i}$, fixing the agent’s own strategy $s_{i}$. Pycia
and Troyan (2019) argue that in this case the agents might be concerned about
having time-inconsistent strategies or making a mistake while performing
backward induction over their own future actions. As a remedy, they introduce
a natural strengthening of OSP called strongly obvious strategy-proofness
(SOSP) by relaxing the assumption that the agents understand how their own
future actions will affect outcomes. A strategic plan is strongly obviously
dominant if, whenever an agent is called to play, even the worst possible
final outcome from the prescribed action is at least as good as the best
possible outcome from any other action, where what is possible may depend on
all future actions, including actions by the agent’s future-self. Thus,
strongly obviously dominant strategies are those that are weakly better than
all alternative actions even if the agent is concerned that she might have
time-inconsistent strategies.444This verbal description of SOSP is adapted
from Pycia and Troyan (2019).

###  1.1 Our motivation and contribution

Mandal and Roy (2022a, b) study the OSP-implementability of FPTTC mechanisms.
They introduce the notion of dual ownership and show that it is both necessary
and sufficient condition for an FPTTC mechanism to be OSP-implementable. An
FPTTC mechanism satisfies dual ownership if, for each preference profile and
each step of the FPTTC mechanism at that preference profile, there are at most
two agents who own all the objects available at that step. Although dual
ownership is an intuitive property (and thereby, is quite helpful for
explaining it to the participating agents), it is not so convenient for the
designer to check whether a given FPTTC mechanism satisfies this property or
not. This is because, technically, one needs to check at every preference
profile and every step of the FPTTC mechanism at that preference profile,
whether at most two agents are owning all the available objects at that step
or not. This motivates one natural question: Is there any equivalent property
to dual ownership, which is easier for the designer to check?

To tackle this question, we present two conditions for FPTTC mechanisms,
namely acyclicity and strong acyclicity (Troyan, 2019), and show that they are
equivalent to dual ownership in models without and with outside options,
respectively (Theorem 4.2 and Theorem 4.3).555Troyan (2019) uses the term “TTC
mechanism” to refer to an FPTTC mechanism, and the term “weak acyclicity” to
refer to strong acyclicity.,666In a model without outside options, every
object is acceptable to every agent, whereas each object need not be
acceptable to an agent in a model with outside options. Both acyclicity and
strong acyclicity are technical properties, which, as the names suggest,
ensure that certain types of cycles are not present in the associated priority
structure of an FPTTC mechanism. The advantage of checking these properties
for an FPTTC mechanism is that they only involve the associated priority
structure, and not anything about the state of the FPTTC mechanism at
different steps at different preference profiles. Since dual ownership
property is intuitive but not convenient for the designer to check, whereas
(strong) acyclicity property is technical but easier to check, these two
equivalent properties, in a sense, complement each other. It is worth noting
that both acyclicity and strong acyclicity are weaker than Ergin-acyclicity
(Ergin, 2002).777Ergin (2002) introduces this notion in a many-to-one matching
model.,888Ehlers et al. (2002) characterize strategy-proof, Pareto efficient,
and population-monotonic mechanisms as FPTTC mechanisms satisfying Ergin-
acyclicity (they use the term “restricted endowment inheritance rules” to
refer to such FPTTC mechanisms). Later, Ehlers and Klaus (2004) show that
these mechanisms are also the only mechanisms satisfying Pareto efficiency,
independence of irrelevant objects, and resource-monotonicity when there are
more objects than agents (they use the term “mixed dictator-pairwise-exchange
rules” to refer to such FPTTC mechanisms).

Apart from FPTTC mechanisms, another well-known class of priority-based
mechanisms is agent-proposing deferred acceptance (APDA) mechanisms (Gale and
Shapley, 1962). Ashlagi and Gonczarowski (2018) study the OSP-implementability
of these mechanisms, and show that Ergin-acyclicity is a sufficient condition
for an APDA mechanism to be OSP-implementable. We derive Ashlagi and
Gonczarowski (2018)’s result as a corollary of our results (Corollary 4.3). We
further show that strong acyclicity is a necessary condition for an APDA
mechanism to be OSP-implementable (Proposition 4.2).

Next, we characterize the structure of SOSP-implementable FPTTC mechanisms. We
introduce the notion of weak serial dictatorships for this purpose. An FPTTC
mechanism is a weak serial dictatorship if, for any preference profile and any
step of the FPTTC mechanism at that preference profile, if there are more than
two objects available at that step, then there is exactly one agent who owns
all those objects. We characterize all SOSP-implementable FPTTC mechanisms in
a model without outside options as weak serial dictatorships (Theorem 5.1). As
a corollary of this result, we obtain that in a model without outside options
and with more objects than agents, the class of SOSP-implementable FPTTC
mechanisms is characterized by the class of serial dictatorships
(Satterthwaite and Sonnenschein, 1981) (Corollary 5.2). In a serial
dictatorship, the agents choose their top choices among the “remaining”
objects and the outside option, according to an ordering of the agents. We
further show that the serial dictatorships are the only SOSP-implementable
FPTTC mechanisms in a model with outside options (Theorem 5.3).

Finally, we introduce the notion of simple strategy-proofness which
strengthens OSP-implementation to resolve the issue with agents being
concerned about having time-inconsistent preferences. Recall that Pycia and
Troyan (2019) introduce SOSP-implementation for the same purpose. The concept
of simple strategy-proofness is based on obvious dominance in a simple
extensive-form game. An extensive-form game is simple if every agent is called
to play at most once. A mechanism is simple strategy-proof if one can
construct a simple extensive-form game that has an equilibrium in obviously
dominant strategies. We show that simple strategy-proofness is stronger than
SOSP-implementability in general (Proposition 6.1). We further show that the
class of simply strategy-proof FPTTC mechanisms is the same as the class of
SOSP-implementable FPTTC mechanisms in both models – with and without outside
options (Theorem 6.1).

###  1.2 Additional related literature

There is a rapidly growing body of work on OSP-implementability and various
related notions of strategic simplicity. Troyan (2019) shows that strong
acyclicity is a sufficient condition for an FPTTC rule to be OSP-implementable
when there is an equal number of agents and objects.999Theorem 1 in Troyan
(2019) says that in a model without outside options, strong acyclicity is both
necessary and sufficient condition for an FPTTC rule to be OSP-implementable
when there is an equal number of agents and objects. Later, Mandal and Roy
(2022a) point out that while strong acyclicity is a sufficient condition for
the same, it is not necessary (see Footnote 22 in Mandal and Roy (2022a) for
details). Mandal and Roy (2022a) characterize OSP-implementable, Pareto
efficient, and non-bossy assignment rules as hierarchical exchange rules
(Pápai, 2000) satisfying dual ownership.101010Pápai (2000) characterizes all
strategy-proof, Pareto efficient, non-bossy, and reallocation-proof assignment
rules as hierarchical exchange rules. Later, Pycia and Ünver (2017) introduce
the notion of trading cycles rules as a generalization of hierarchical
exchange rules and show that an assignment rule is strategy-proof, Pareto
efficient, and non-bossy if and only if it is a trading cycles rule. Bade and
Gonczarowski (2017) constructively characterize OSP-implementable and Pareto
efficient assignment rules as the ones that can be implemented via a mechanism
they call sequential barter with lurkers. Pycia and Troyan (2019) characterize
the full class of OSP mechanisms in environments without transfers as
millipede games with greedy strategies. They also characterize the full class
of SOSP mechanisms as sequential price mechanisms with greedy strategies.
Thomas (2020) provides a necessary and sufficient condition for an APDA rule
to be OSP-implementable when there is an equal number of agents and objects.
Ashlagi and Gonczarowski (2018) consider two-sided matching with one strategic
side and show that for general preferences, no mechanism that implements a
stable matching is obviously strategy-proof for any side of the market.

###  1.3 Organization of the paper

The organization of this paper is as follows. In Section 2, we introduce basic
notions and notations that we use throughout the paper, define assignment
rules, and introduce the notions of OSP-implementation and SOSP-
implementation. Section 3 introduces the notion of FPTTC rules. In Section 4,
we introduce dual ownership property of an FPTTC rule and present prior
results on the OSP-implementability of FPTTC rules by means of this property.
We also introduce acyclicity property and strong acyclicity property of an
FPTTC rule, and discuss their relationship with dual ownership property. In
Section 5, we discuss the SOSP-implementability of FPTTC rules. In Section 6,
we introduce the notion of simple strategy-proofness, and discuss its relation
with SOSP-implementation. We further characterize all simply strategy-proof
FPTTC rules. All omitted proofs are collected in the Appendix.

##  2 Preliminaries

###  2.1 Basic notions and notations

Let $N=\\{1,\ldots,n\\}$ be a finite set of agents, and $A$ be a non-empty and
finite set of objects. Let $a_{0}$ denote the outside option. An allocation is
a function $\mu:N\to A\cup\\{a_{0}\\}$ such that $|\mu^{-1}(a)|\leq 1$ for all
$a\in A$. Here, $\mu(i)=a$ means agent $i$ is assigned object $a$ under $\mu$,
and $\mu(i)=a_{0}$ means agent $i$ is not assigned any object under $\mu$.
Notice that the outside option $a_{0}$ can be assigned to any number of agents
and that not all objects in $A$ have to be assigned. We denote by
$\mathcal{M}$ the set of all allocations.

Let $\mathbb{L}(A\cup\\{a_{0}\\})$ denote the set of all strict linear orders
over $A\cup\\{a_{0}\\}$.111111A strict linear order is a semiconnex,
asymmetric, and transitive binary relation. An element of
$\mathbb{L}(A\cup\\{a_{0}\\})$ is called a preference over $A\cup\\{a_{0}\\}$.
For a preference $P$, let $R$ denote the weak part of $P$, that is, for all
$a,b\in A\cup\\{a_{0}\\}$, $aRb$ if and only if [$aPb$ or $a=b$]. For a
preference $P\in\mathbb{L}(A\cup\\{a_{0}\\})$ and non-empty
$A^{\prime}\subseteq A\cup\\{a_{0}\\}$, let $\tau(P,A^{\prime})$ denote the
most preferred element in $A^{\prime}$ according to $P$, that is,
$\tau(P,A^{\prime})=a$ if and only if [$a\in A^{\prime}$ and $aPb$ for all
$b\in A^{\prime}\setminus\\{a\\}$]. For ease of presentation, we denote
$\tau(P,A\cup\\{a_{0}\\})$ by $\tau(P)$.

For each object $a\in A$, we define the priority of $a$ as a “preference”
$\succ_{a}$ over $N$.121212In other words, $\succ_{a}\in\mathbb{L}(N)$ for all
$a\in A$. Following our notational convention, for a priority
$\succ\in\mathbb{L}(N)$ and non-empty $N^{\prime}\subseteq N$, let
$\tau(\succ,N^{\prime})$ denote the most preferred agent in $N^{\prime}$
according to $\succ$. For ease of presentation, we denote $\tau(\succ,N)$ by
$\tau(\succ)$. For a priority $\succ\in\mathbb{L}(N)$ and an agent $i\in N$,
by $U(i,\succ)$ we denote the strict upper contour set $\\{j\in N\mid j\succ
i\\}$ of $i$ at $\succ$. Furthermore, for a priority $\succ\in\mathbb{L}(N)$,
an agent $i\in N$, and non-empty $N^{\prime}\subseteq N\setminus\\{i\\}$, we
write $i\succ N^{\prime}$ to mean that $i\succ j$ for all $j\in N^{\prime}$.

We call a collection $\succ_{A}=(\succ_{a})_{a\in A}$ a priority structure.
Let $N^{\prime}\subseteq N$, $A^{\prime}\subseteq A$, and $\succ_{A}$ be a
priority structure. The reduced priority structure
$\succ_{A^{\prime}}^{N^{\prime}}$ is the collection
$(\succ_{a}^{N^{\prime}})_{a\in A^{\prime}}$ such that for all $a\in
A^{\prime}$, (i) $\succ_{a}^{N^{\prime}}\in\mathbb{L}(N^{\prime})$ and (ii)
for all $i,j\in N^{\prime}$, $i\succ_{a}^{N^{\prime}}j$ if and only if
$i\succ_{a}j$. Thus, the reduced priority structure
$\succ_{A^{\prime}}^{N^{\prime}}$ is the restriction of $\succ_{A}$ to the
reduced market $(N^{\prime},A^{\prime})$.131313Thus,
$\succ_{A}^{N}=\succ_{A}$. Furthermore, let
$\mathcal{T}(\succ_{A^{\prime}}^{N^{\prime}})=\\{i\mid\tau(\succ_{a},N^{\prime})=i\mbox{
for some }a\in A^{\prime}\\}$ be the set of agents who have the highest
priority in $N^{\prime}$ for at least one object in $A^{\prime}$ according to
$\succ_{A}$.

###  2.2 Types of domains

We denote by $\mathcal{P}_{i}\subseteq\mathbb{L}(A\cup\\{a_{0}\\})$ the set of
admissible preferences of agent $i$. A preference profile, denoted by
$P_{N}=(P_{1},\ldots,P_{n})$, is an element of
$\mathcal{P}_{N}=\underset{i=1}{\overset{n}{\prod}}\hskip
2.84526pt\mathcal{P}_{i}$, that represents a collection of preferences – one
for each agent. We say an object $a$ is acceptable to agent $i$ if
$aP_{i}a_{0}$.

Our framework encompasses both models – with and without outside options, as
special cases.

  1. (i)

Model with outside options: This model can be captured in our framework by
taking $\mathcal{P}_{i}=\mathbb{L}(A\cup\\{a_{0}\\})$ for all $i\in N$.

  2. (ii)

Model without outside options: Every object is acceptable to every agent in
this model, which can be captured in our framework by considering

$\mathcal{P}_{i}=\\{P\in\mathbb{L}(A\cup\\{a_{0}\\})\mid aPa_{0}\mbox{ for all
}a\in A\\}$

for all $i\in N$. With abuse of notation, let
$\mathbb{L}(A)=\\{P\in\mathbb{L}(A\cup\\{a_{0}\\})\mid aPa_{0}\mbox{ for all
}a\in A\\}$ be the set of all preferences where the outside option $a_{0}$ is
the least preferred element in $A\cup\\{a_{0}\\}$.

###  2.3 Assignment rules and their properties

An assignment rule is a function $f:\mathcal{P}_{N}\to\mathcal{M}$. For an
assignment rule $f:\mathcal{P}_{N}\to\mathcal{M}$ and a preference profile
$P_{N}\in\mathcal{P}_{N}$, let $f_{i}(P_{N})$ denote the assignment of agent
$i$ by $f$ at $P_{N}$.

Pycia and Troyan (2019) introduce the notion of simple dominance. In this
paper, we discuss two types of simple dominance in the context of assignment
rules, namely obviously strategy-proofness (OSP) and strongly obviously
strategy-proofness (SOSP). We use the following notions and notations to
present these.

We denote a rooted (directed) tree by $T$. For a rooted tree $T$, we denote
its set of nodes by $V(T)$, set of edges by $E(T)$, root by $r(T)$, and set of
leaves (terminal nodes) by $L(T)$. For a node $v\in V(T)$, let $E^{out}(v)$
denote the set of outgoing edges from $v$. For an edge $e\in E(T)$, let $s(e)$
denote its source node. A path in a tree is a sequence of nodes such that
every two consecutive nodes form an edge.

######  Definition 2.1.

An extensive-form mechanism, or simply a mechanism on $\mathcal{P}_{N}$, is
defined as a tuple $G=\langle T,\eta^{LA},\eta^{NA},\eta^{EP}\rangle$, where

  1. (i)

$T$ is a rooted tree,

  2. (ii)

$\eta^{LA}:L(T)\to\mathcal{M}$ is a leaves-to-allocations function,

  3. (iii)

$\eta^{NA}:V(T)\setminus L(T)\to N$ is a nodes-to-agents function, and

  4. (iv)

$\eta^{EP}:E(T)\to 2^{\mathbb{L}(A\cup\\{a_{0}\\})}\setminus\\{\emptyset\\}$
is an edges-to-preferences function such that

    1. (a)

for all distinct $e,e^{\prime}\in E(T)$ with $s(e)=s(e^{\prime})$, we have
$\eta^{EP}(e)\cap\eta^{EP}(e^{\prime})=\emptyset$, and

    2. (b)

for any $v\in V(T)\setminus L(T)$,

      1. (1)

if there exists a path $(v^{1},\ldots,v^{t})$ from $r(T)$ to $v$ and some
$1\leq t^{\prime}<t$ such that $\eta^{NA}(v^{t^{\prime}})=\eta^{NA}(v)$ and
$\eta^{NA}(v^{s})\neq\eta^{NA}(v)$ for all $s=t^{\prime}+1,\ldots,t-1$, then
$\underset{e\in
E^{out}(v)}{\cup}\eta^{EP}(e)=\eta^{EP}(v^{t^{\prime}},v^{t^{\prime}+1})$, and

      2. (2)

if there is no such path, then $\underset{e\in
E^{out}(v)}{\cup}\eta^{EP}(e)=\mathcal{P}_{\eta^{NA}(v)}$.

For a given mechanism $G$ on $\mathcal{P}_{N}$, every preference profile
$P_{N}\in\mathcal{P}_{N}$ identifies a unique path from the root to some leaf
in $T$ in the following manner: from each node $v$, follow the outgoing edge
$e$ from $v$ such that $\eta^{EP}(e)$ contains the preference
$P_{\eta^{NA}(v)}$. If a node $v$ lies in such a path, then we say that the
preference profile $P_{N}$ passes through the node $v$. Furthermore, we say
two preferences $P_{i}$ and $P_{i}^{\prime}$ of some agent $i$ diverge at a
node $v\in V(T)\setminus L(T)$ if $\eta^{NA}(v)=i$ and there are two distinct
outgoing edges $e$ and $e^{\prime}$ in $E^{out}(v)$ such that
$P_{i}\in\eta^{EP}(e)$ and $P^{\prime}_{i}\in\eta^{EP}(e^{\prime})$.

For a given mechanism $G$ on $\mathcal{P}_{N}$, the assignment rule
$f^{G}:\mathcal{P}_{N}\rightarrow\mathcal{M}$ implemented by $G$ is defined as
follows: for all preference profiles $P_{N}\in\mathcal{P}_{N}$,
$f^{G}(P_{N})=\eta^{LA}(l)$, where $l$ is the leaf that appears at the end of
the unique path characterized by $P_{N}$.

######  Definition 2.2.

A mechanism $G$ on $\mathcal{P}_{N}$ is OSP if for all $i\in N$, all nodes $v$
such that $\eta^{NA}(v)=i$, and all $P_{N},\tilde{P}_{N}\in\mathcal{P}_{N}$
passing through $v$ such that $P_{i}$ and $\tilde{P}_{i}$ diverge at $v$, we
have $f_{i}^{G}(P_{N})R_{i}f_{i}^{G}(\tilde{P}_{N})$.

An assignment rule $f:\mathcal{P}_{N}\rightarrow\mathcal{M}$ is OSP-
implementable (on $\mathcal{P}_{N}$) if there exists an OSP mechanism $G$ on
$\mathcal{P}_{N}$ such that $f=f^{G}$.

In other words, obvious strategy-proofness of an assignment rule implies that,
whenever an agent $i$ is called to play, the worst possible final outcome from
following her true preference $P_{i}$ is at least as good as the best possible
outcome from following any deviating preference $P^{\prime}_{i}$, where the
best and worst cases are determined by considering all possible preferences of
$i$’s opponents in the future, keeping her own preference fixed.

######  Definition 2.3.

A mechanism $G$ on $\mathcal{P}_{N}$ is SOSP if for all $i\in N$, all nodes
$v$ such that $\eta^{NA}(v)=i$, and all
$P_{N},P^{\prime}_{N},\tilde{P}_{N}\in\mathcal{P}_{N}$ passing through $v$
such that (i) $P_{i}$ and $P^{\prime}_{i}$ do not diverge at $v$ and (ii)
$P_{i}$ and $\tilde{P}_{i}$ diverge at $v$, we have
$f_{i}^{G}(P^{\prime}_{N})R_{i}f_{i}^{G}(\tilde{P}_{N})$.141414In other words,
there exists an edge $e\in E^{out}(v)$ such that
$P_{i},P^{\prime}_{i}\in\eta^{EP}(e)$ and $\tilde{P}_{i}\notin\eta^{EP}(e)$.

An assignment rule $f:\mathcal{P}_{N}\rightarrow\mathcal{M}$ is SOSP-
implementable (on $\mathcal{P}_{N}$) if there exists an SOSP mechanism $G$ on
$\mathcal{P}_{N}$ such that $f=f^{G}$.

In other words, strongly obvious strategy-proofness of an assignment rule
implies that, whenever an agent $i$ is called to play, the worst possible
final outcome from following her true preference $P_{i}$ is at least as good
as the best possible outcome from following any deviating preference
$P^{\prime}_{i}$, where the best and worst cases are determined by considering
all possible preferences of all agents in the future.

######  Remark 2.1.

For an arbitrary domain of preference profiles $\mathcal{P}_{N}$, every SOSP-
implementable assignment rule is OSP-implementable.

In Example 2.1, we explain the difference between OSP-implementability and
SOSP-implementability.

######  Example 2.1.

Consider an allocation problem with three agents $N=\\{1,2,3\\}$ and three
objects $A=\\{a_{1},a_{2},a_{3}\\}$. In Figure 1, we provide a mechanism $G$
on $\mathbb{L}^{3}(A)$.151515Recall that
$\mathbb{L}(A)=\\{P\in\mathbb{L}(A\cup\\{a_{0}\\})\mid aPa_{0}\mbox{ for all
}a\in A\\}$. We use the following notations in Figure 1: by $(v_{1}:1)$ we
mean that the node $v_{1}$ is assigned to agent $1$, by $\cdot a_{1}\cdot
a_{2}\cdot$ we denote the set of preferences where $a_{1}$ is preferred to
$a_{2}$, by $a_{1}a_{2}a_{3}a_{0}$ we denote the preference that ranks $a_{1}$
first, $a_{2}$ second, $a_{3}$ third, and $a_{0}$ fourth, and we denote the
allocation $[(1,a_{1}),(2,a_{2}),(3,a_{3})]$ by $(a_{1},a_{2},a_{3})$.

pt$v_{1}$: 1pt$v_{2}$: 2pt$v_{5}$: 3pt$(a_{1},a_{3},a_{2})$$\cdot a_{2}\cdot
a_{3}\cdot$pt$(a_{1},a_{2},a_{3})$$\cdot a_{3}\cdot a_{2}\cdot$$\cdot
a_{2}\cdot a_{3}\cdot$pt$(a_{1},a_{3},a_{2})$$\cdot a_{3}\cdot
a_{2}\cdot$$\tau(P_{1})=a_{1}$pt$v_{3}$: 2pt$(a_{2},a_{1},a_{3})$$\cdot
a_{1}\cdot a_{3}\cdot$pt$(a_{2},a_{3},a_{1})$$\cdot a_{3}\cdot
a_{1}\cdot$$\tau(P_{1})=a_{2}$pt$v_{4}$: 2pt$v_{6}$:
1pt$(a_{1},a_{3},a_{2})$$a_{3}a_{1}a_{2}a_{0}$pt$(a_{2},a_{3},a_{1})$$a_{3}a_{2}a_{1}a_{0}$$\tau(P_{2})=a_{3}$pt$(a_{3},a_{1},a_{2})$$\tau(P_{2})=a_{1}$pt$(a_{3},a_{2},a_{1})$$\tau(P_{2})=a_{2}$$\tau(P_{1})=a_{3}$
Figure 1: Mechanism $G$ for Example 2.1

First, we argue that $G$ is OSP. To see this, consider, for instance, the
preference profiles
$P_{N}^{1}=(a_{3}a_{1}a_{2}a_{0},a_{3}a_{1}a_{2}a_{0},a_{3}a_{1}a_{2}a_{0})$
and
$P_{N}^{2}=(a_{3}a_{2}a_{1}a_{0},a_{1}a_{2}a_{3}a_{0},a_{3}a_{1}a_{2}a_{0})$.161616We
denote by $(a_{1}a_{2}a_{3}a_{0},a_{2}a_{1}a_{3}a_{0},a_{3}a_{1}a_{2}a_{0})$ a
preference profile where agents $1,2$, and $3$ have preferences
$a_{1}a_{2}a_{3}a_{0}$, $a_{2}a_{1}a_{3}a_{0}$, and $a_{3}a_{1}a_{2}a_{0}$,
respectively. Note that both of them pass through the node $v_{4}$ at which
$P_{2}^{1}$ and $P_{2}^{2}$ diverge. Further note that
$f^{G}_{2}(P_{N}^{1})=a_{3}$ and $f^{G}_{2}(P_{N}^{2})=a_{1}$, which means $G$
satisfies OSP property for this instance. Similarly, one can check that $G$
satisfies OSP property for other instances.

Now we argue that $G$ is not SOSP. Consider the preference profile
$P_{N}=(a_{3}a_{1}a_{2}a_{0},a_{3}a_{1}a_{2}a_{0},a_{3}a_{1}a_{2}a_{0})$. Note
that at node $v_{1}$, the worst possible final assignment for agent $1$
(according to $P_{1}$) from following the edge $(v_{1},v_{4})$ is $a_{2}$,
whereas the best possible final assignment from not following the edge
$(v_{1},v_{4})$ is $a_{1}$. Since $a_{1}P_{1}a_{2}$, this implies $G$ does not
satisfy SOSP property. $\Diamond$

##  3 Fixed priority top trading cycles rules

Fixed priority top trading cycles (FPTTC) rules are well-known in the
literature. We explain how such a rule works by means of an example.

We begin by explaining the notion of TTC procedure with respect to a given
endowments of the objects over the agents. Suppose that each object is owned
by exactly one agent. Note that an agent may own more than one object. A
directed graph is constructed in the following manner. The set of nodes is the
same as the set of agents. There is a directed edge from agent $i$ to agent
$j$ if agent $j$ owns agent $i$’s most preferred acceptable object, and a
directed edge from agent $i$ to herself if every object is unacceptable to
her. Notice that each agent has exactly one outgoing edge (though possibly
many incoming edges), and there is a directed edge from an agent to herself if
and only if she owns her most preferred acceptable object or every object is
unacceptable to her. Note that such a graph will always have at least a cycle.
Such a cycle is called a top trading cycle (TTC). After forming a TTC, each
agent in the TTC is assigned her most preferred element among all the objects
and the outside option $a_{0}$.

######  Example 3.1.

An FPTTC rule is based on an exogenously given priority structure. Consider an
allocation problem with four agents $N=\\{1,2,3,4\\}$ and four objects
$A=\\{a_{1},a_{2},a_{3},a_{4}\\}$, and consider the priority structure given
in Table 1. Here, for instance, $\succ_{a_{1}}$ ranks agent $1$ first, agent
$4$ second, agent $3$ third, and agent $2$ fourth.

$\succ_{a_{1}}$ | $\succ_{a_{2}}$ | $\succ_{a_{3}}$ | $\succ_{a_{4}}$
---|---|---|---
$1$ | $2$ | $3$ | $4$
$4$ | $1$ | $2$ | $3$
$3$ | $3$ | $4$ | $2$
$2$ | $4$ | $1$ | $1$
Table 1: Priority structure for Example 3.1

Consider the FPTTC rule based on the priority structure given in Table 1 and
consider the preference profile $P_{N}$ such that
$a_{0}P_{1}a_{2}P_{1}a_{1}P_{1}a_{3}P_{1}a_{4}$,
$a_{1}P_{2}a_{0}P_{2}a_{2}P_{2}a_{3}P_{2}a_{4}$,
$a_{1}P_{3}a_{2}P_{3}a_{3}P_{3}a_{0}P_{3}a_{4}$, and
$a_{3}P_{4}a_{2}P_{4}a_{1}P_{4}a_{4}P_{4}a_{0}$. The outcome is computed
through a number of steps. At each step, endowments of the agents are
determined by means of the priority structure, and TTC procedure is performed
with respect to the endowments.

Step 1. At Step 1, the “owner” of an object $a$ is the most preferred agent
according to $\succ_{a}$. Thus, object $a_{1}$ is owned by agent $1$, object
$a_{2}$ is owned by agent $2$, object $a_{3}$ is owned by agent $3$, and
object $a_{4}$ is owned by agent $4$. TTC procedure is performed with respect
to these endowments to decide the outcome of Step 1, and assigned agents and
assigned objects leave the market. It can be verified that for the given
preference profile $P_{N}$, only agent $1$ is assigned at Step 1 and her
assignment is the outside option $a_{0}$. So, only agent $1$ leaves the
market.

Step 2. The reduced market at Step 2 consists of agents $2,3,4$, and objects
$a_{1},a_{2},a_{3},a_{4}$. As at Step 1, the endowments of the remaining
agents are decided first and then TTC procedure is performed with respect to
the endowments. The owner of a remaining object $a$ is the most preferred
remaining agent according to $\succ_{a}$. Thus, objects $a_{1}$ and $a_{4}$
are owned by agent $4$, object $a_{2}$ is owned by agent $2$, and object
$a_{3}$ is owned by agent $3$. Once the endowments are decided for Step 2, TTC
procedure is performed with respect to the endowments to decide the outcome of
this step, and assigned agents and assigned objects leave the market. It can
be verified that for the current example, agents $3$ and $4$ get objects
$a_{1}$ and $a_{3}$, respectively at this step. So, agents $3$ and $4$ leave
the market with objects $a_{1}$ and $a_{3}$.

Step 3. Step 3 is followed on the reduced market in a similar way as Step 2.
The reduced market at Step 3 consists of agent $2$, and objects $a_{2}$ and
$a_{4}$. Both of the objects $a_{2}$ and $a_{4}$ are owned by agent $2$ at
Step 3. It can be verified that agent $2$ is assigned the outside option
$a_{0}$ at Step 3, and leaves the market.

Every agent is assigned by the end of Step 3 and hence the algorithm stops at
this step. Thus, agents $1$ and $2$ are assigned the outside option $a_{0}$,
and agents $3$ and $4$ are assigned objects $a_{1}$ and $a_{3}$, respectively,
at the outcome of the FPTTC rule at $P_{N}$. $\Diamond$

In what follows, we present a formal description of FPTTC rules. For a given
priority structure $\succ_{A}$, the FPTTC rule $T^{\succ_{A}}$ associated with
$\succ_{A}$ is defined by an iterative procedure as follows. Consider an
arbitrary preference profile $P_{N}\in\mathbb{L}^{n}(A\cup\\{a_{0}\\})$.

  * Step s.

Let $N_{s}(P_{N})\subseteq N$ be the set of agents that remain after Step
$s-1$ and $A_{s}(P_{N})\subseteq A$ be the set of objects that remain after
Step $s-1$.171717Notice that for all
$P_{N}\in\mathbb{L}^{n}(A\cup\\{a_{0}\\})$, $N_{1}(P_{N})=N$ and
$A_{1}(P_{N})=A$. Each object $a\in A_{s}(P_{N})$ is owned by its most
preferred agent in $N_{s}(P_{N})$ according to $\succ_{a}$. TTC procedure is
performed on the reduced market $(N_{s}(P_{N}),A_{s}(P_{N}))$ with respect to
these endowments. Remove all assigned agents and assigned objects at this
step.

This procedure is repeated iteratively until either all agents are assigned or
all objects are assigned. The final outcome is obtained by combining all the
assignments at all steps.

##  4 OSP-implementability of FPTTC rules

Mandal and Roy (2022a) study the OSP-implementability of FPTTC rules on the
restricted domain $\mathbb{L}^{n}(A)$. For this purpose, they introduce the
notion of dual ownership and show that it is both necessary and sufficient
condition for an FPTTC rule to be OSP-implementable on $\mathbb{L}^{n}(A)$.
Later, Mandal and Roy (2022b) extend this result to the unrestricted domain
$\mathbb{L}^{n}(A\cup\\{a_{0}\\})$. In what follows, we present the notion of
dual ownership, as well as the prior results on the OSP-implementability of
FPTTC rules using this notion.

Before defining dual ownership formally, let us first recall a couple of
notations used in the context of FPTTC rules: for a preference profile
$P_{N}\in\mathbb{L}^{n}(A\cup\\{a_{0}\\})$ and an FPTTC rule, $N_{s}(P_{N})$
is the set of remaining agents after Step $s-1$ and $A_{s}(P_{N})$ is the set
of remaining objects after Step $s-1$.

######  Definition 4.1.

On a domain $\mathcal{P}_{N}$, an FPTTC rule $T^{\succ_{A}}$ satisfies dual
ownership if for all $P_{N}\in\mathcal{P}_{N}$, we have
$|\mathcal{T}(\succ_{A_{s}(P_{N})}^{N_{s}(P_{N})})|\leq 2$ for all $s$.

In other words, an FPTTC rule satisfies dual ownership on an arbitrary domain
of preference profiles $\mathcal{P}_{N}$ if, for any preference profile in
$\mathcal{P}_{N}$ and any step of the FPTTC rule at that preference profile,
there are at most two agents who own all the objects that remain in the
reduced market at that step.

######  Note 4.1.

We define dual ownership as a property of FPTTC rules because it depends on
the choice of domain. More precisely, an FPTTC rule satisfying dual ownership
on a smaller domain, may not satisfy dual ownership on a larger domain (see
Example 4.1 for details).

######  Example 4.1.

Consider an allocation problem with four agents
$N=\\{i_{1},i_{2},i_{3},i_{4}\\}$ and four objects
$A=\\{a_{1},a_{2},a_{3},a_{4}\\}$. Let $\succ_{A}$ be as follows:

$\succ_{a_{1}}$ | $\succ_{a_{2}}$ | $\succ_{a_{3}}$ | $\succ_{a_{4}}$
---|---|---|---
$i_{1}$ | $i_{1}$ | $i_{4}$ | $i_{4}$
$i_{2}$ | $i_{2}$ | $i_{2}$ | $i_{3}$
$i_{3}$ | $i_{3}$ | $i_{3}$ | $i_{2}$
$i_{4}$ | $i_{4}$ | $i_{1}$ | $i_{1}$
Table 2: Priority structure for Example 4.1

Consider the FPTTC rule $T^{\succ_{A}}$ associated with the priority structure
given in Table 2. First, we argue that it satisfies dual ownership on the
restricted domain $\mathbb{L}^{n}(A)$. Since either agent $i_{1}$ or agent
$i_{4}$ appears at the top position in each priority, it follows that for any
preference profile in $\mathbb{L}^{n}(A)$, agents $i_{1}$ and $i_{4}$ will own
all the objects at Step 1 of $T^{\succ_{A}}$. Moreover, since there are only
four agents in the original market, for any preference profile in
$\mathbb{L}^{n}(A)$, at any step from Step 3 onward of $T^{\succ_{A}}$, there
will remain at most two agents in the corresponding reduced market and hence
dual ownership will be vacuously satisfied. In what follows, we show that dual
ownership will also be satisfied at Step $2$ for any preference profile in
$\mathbb{L}^{n}(A)$. We distinguish three cases based on the possible
assignments at Step 1.

  1. (i)

Suppose only agent $i_{1}$ is assigned some object at Step 1. No matter
whether agent $i_{1}$ is assigned object $a_{1}$ or object $a_{2}$, agents
$i_{2}$ and $i_{4}$ will own all the remaining objects at Step 2.

  2. (ii)

Suppose only agent $i_{4}$ is assigned some object at Step 1.

    1. (a)

If $i_{4}$ is assigned object $a_{3}$, then agents $i_{1}$ and $i_{3}$ will
own all the remaining objects at Step 2.

    2. (b)

If $i_{4}$ is assigned object $a_{4}$, then agents $i_{1}$ and $i_{2}$ will
own all the remaining objects at Step 2.

  3. (iii)

Suppose both $i_{1}$ and $i_{4}$ are assigned some objects at Step 1. Since
there are only four agents in the original market, only two agents will remain
in the reduced market at Step 2.

Since Cases i, ii, and iii are exhaustive, it follows that $T^{\succ_{A}}$
satisfies dual ownership on $\mathbb{L}^{n}(A)$.

We now proceed to show that $T^{\succ_{A}}$ does not satisfy dual ownership on
the unrestricted domain $\mathbb{L}^{n}(A\cup\\{a_{0}\\})$. Consider the
preference profile $P_{N}\in\mathbb{L}^{n}(A\cup\\{a_{0}\\})$ such that
$\tau(P_{i_{1}})=\tau(P_{i_{2}})=\tau(P_{i_{3}})=a_{3}$ and
$\tau(P_{i_{4}})=a_{0}$. It follows from the construction of $P_{N}$ and the
definition of $T^{\succ_{A}}$ that at Step 2 of $T^{\succ_{A}}$ at $P_{N}$,
objects $a_{1}$ and $a_{2}$ are owned by agent $i_{1}$, object $a_{3}$ is
owned by agent $i_{2}$, and object $a_{4}$ is owned by agent $i_{3}$, and
hence $T^{\succ_{A}}$ violates dual ownership at $P_{N}$. $\Diamond$

######  Theorem 4.1 (Mandal and Roy, 2022a, b).

Suppose
$\mathcal{P}_{N}\in\Big{\\{}\mathbb{L}^{n}(A),\mathbb{L}^{n}(A\cup\\{a_{0}\\})\Big{\\}}$.
On the domain $\mathcal{P}_{N}$, dual ownership is a necessary and sufficient
condition for an FPTTC rule to be OSP-implementable.

######  Remark 4.1.

It follows from Theorem 4.1 and Example 4.1 that the set of FPTTC rules
satisfying OSP-implementability on the restricted domain $\mathbb{L}^{n}(A)$
is a strict superset of those satisfying OSP-implementability on the
unrestricted domain $\mathbb{L}^{n}(A\cup\\{a_{0}\\})$.

Although dual ownership is an intuitive property, it is somewhat time-
consuming to check whether a given FPTTC rule satisfies this property. This is
because, technically, one needs to check at every preference profile whether
at most two agents are owning all the (remaining) objects at every step of the
FPTTC rule. In view of this observation, we introduce equivalent properties to
dual ownership, which involve the priority structure only (and not the
preference profiles), and thus, is more convenient to be checked.

###  4.1 Results on the restricted domain $\mathbb{L}^{n}(A)$

In this subsection, we introduce the notion of acyclicity for FPTTC rules, and
show that it is equivalent to dual ownership property on the restricted domain
$\mathbb{L}^{n}(A)$.

An FPTTC rule is acyclic if the associated priority structure does not contain
any priority cycle. We begin with a verbal description of a priority cycle. A
tuple $[(i_{1},i_{2},i_{3}),(a_{1},a_{2},a_{3})]$ where $i_{1},i_{2},i_{3}\in
N$ and $a_{1},a_{2},a_{3}\in A$ are all distinct, constitutes a priority cycle
in one of two ways. In the first way, $i_{h}$ is the most preferred agent of
$\succ_{a_{h}}$ for all $h=1,2,3$. To explain the second way, let us present a
specific instance where agents $i_{1},i_{2},i_{3}$ and objects
$a_{1},a_{2},a_{3}$ form a priority cycle. Suppose there exist distinct agents
$i_{4},i_{5}\in N\setminus\\{i_{1},i_{2},i_{3}\\}$ and distinct objects
$a_{4},a_{5}\in A\setminus\\{a_{1},a_{2},a_{3}\\}$. For $h=1,\ldots,5$, let
$\succ_{a_{h}}$ be as given below (the dots indicate that all preferences for
the corresponding parts are irrelevant and can be chosen arbitrarily).

$\succ_{a_{1}}$ | $\succ_{a_{2}}$ | $\succ_{a_{3}}$ | $\succ_{a_{4}}$ | $\succ_{a_{5}}$
---|---|---|---|---
$i_{4}$ | $i_{4}$ | $i_{4}$ | $i_{5}$ | $i_{5}$
$i_{1}$ | $i_{2}$ | $i_{3}$ | $i_{4}$ | $\vdots$
$\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ |
Table 3: Priority structure with a priority cycle

The priority structure in Table 3 has the property that for all
$h=1,\ldots,5$, the strict upper contour set of agent $i_{h}$ at
$\succ_{a_{h}}$ is a subset of $\\{i_{4},i_{5}\\}$. For instance, the strict
upper contour set of agent $i_{1}$ is the singleton set $\\{i_{4}\\}$. In this
case, the tuple $[(i_{1},i_{2},i_{3}),(a_{1},a_{2},a_{3})]$ is called a
priority cycle. In general, a tuple
$[(i_{1},i_{2},i_{3}),(a_{1},a_{2},a_{3})]$ is a priority cycle if one can get
hold of agents $i_{4},\ldots,i_{t}$ and objects $a_{4},\ldots,a_{t}$ such that
for all $h=1,\ldots,t$, the strict upper contour set of agent $i_{h}$ at
$\succ_{a_{h}}$ is a subset of $\\{i_{4},\ldots,i_{t}\\}$. In what follows, we
present a formal definition.

######  Definition 4.2.

A tuple $[(i_{1},i_{2},i_{3}),(a_{1},a_{2},a_{3})]$, where
$i_{1},i_{2},i_{3}\in N$ and $a_{1},a_{2},a_{3}\in A$ are all distinct, is
called a priority cycle in a priority structure $\succ_{A}$ if either
$\tau(\succ_{a_{h}})=i_{h}$ for all $h=1,2,3$, or there exist distinct agents
$i_{4},\ldots,i_{t}\in N\setminus\\{i_{1},i_{2},i_{3}\\}$ and distinct objects
$a_{4},\ldots,a_{t}\in A\setminus\\{a_{1},a_{2},a_{3}\\}$ such that for all
$h=1,\ldots,t$, we have
$U(i_{h},\succ_{a_{h}})\subseteq\\{i_{4},\ldots,i_{t}\\}$.181818Notice that
there is a “cycle” in a priority cycle
$[(i_{1},i_{2},i_{3}),(a_{1},a_{2},a_{3})]$ in the sense that
$i_{1}\succ_{a_{1}}\\{i_{2},i_{3}\\}$, $i_{2}\succ_{a_{2}}\\{i_{1},i_{3}\\}$,
and $i_{3}\succ_{a_{3}}\\{i_{1},i_{2}\\}$.

We call a priority structure acyclic if it contains no priority cycles, and
call an FPTTC rule acyclic if it is associated with an acyclic priority
structure.

######  Theorem 4.2.

On the domain $\mathbb{L}^{n}(A)$, an FPTTC rule $T^{\succ_{A}}$ satisfies
dual ownership if and only if it is acyclic.

The proof of this theorem is relegated to Appendix B.

Since dual ownership is both necessary and sufficient condition for an FPTTC
rule to be OSP-implementable on the restricted domain $\mathbb{L}^{n}(A)$ (see
Theorem 4.1), we obtain the following corollary from Theorem 4.2.191919As we
have mentioned earlier, Theorem 1 in Troyan (2019) is not correct. Corollary
4.1 is a correct version of Theorem 1 in Troyan (2019) (in fact, our result is
a general result for arbitrary values of the number of agents and the number
of objects).

######  Corollary 4.1.

On the domain $\mathbb{L}^{n}(A)$, an FPTTC rule $T^{\succ_{A}}$ is OSP-
implementable if and only if it is acyclic.

###  4.2 Results on the unrestricted domain $\mathbb{L}^{n}(A\cup\\{a_{0}\\})$

Troyan (2019) works on the OSP-implementable FPTTC rules on the restricted
domain $\mathbb{L}^{n}(A)$ when there is an equal number of agents and
objects. For this purpose, he introduces the notion of strong acyclicity,
which we present first.

######  Definition 4.3.

A tuple $[(i_{1},i_{2},i_{3}),(a_{1},a_{2},a_{3})]$, where
$i_{1},i_{2},i_{3}\in N$ and $a_{1},a_{2},a_{3}\in A$ are all distinct, is
called a weak cycle in a priority structure $\succ_{A}$ if
$i_{1}\succ_{a_{1}}\\{i_{2},i_{3}\\}$, $i_{2}\succ_{a_{2}}\\{i_{1},i_{3}\\}$,
and $i_{3}\succ_{a_{3}}\\{i_{1},i_{2}\\}$.

We call a priority structure strongly acyclic if it contains no weak cycles,
and call an FPTTC rule strongly acyclic if it is associated with a strongly
acyclic priority structure.

######  Remark 4.2.

Every strongly acyclic priority structure is acyclic. To see this, note that
if a priority structure $\succ_{A}$ contains a priority cycle
$[(i_{1},i_{2},i_{3}),(a_{1},a_{2},a_{3})]$, then
$i_{1}\succ_{a_{1}}\\{i_{2},i_{3}\\}$, $i_{2}\succ_{a_{2}}\\{i_{1},i_{3}\\}$,
and $i_{3}\succ_{a_{3}}\\{i_{1},i_{2}\\}$. Therefore, every priority cycle is
a weak cycle, and hence strong acyclicity implies acyclicity. However, the
converse is not true (see Example 4.2 for details).

######  Example 4.2.

Consider an allocation problem with four agents $N=\\{i,j,k,l\\}$ and four
objects $A=\\{a,b,c,d\\}$. Let $\succ_{A}$ be as follows:

$\succ_{a}$ | $\succ_{b}$ | $\succ_{c}$ | $\succ_{d}$
---|---|---|---
$i$ | $l$ | $l$ | $i$
$j$ | $j$ | $k$ | $j$
$k$ | $k$ | $j$ | $k$
$l$ | $i$ | $i$ | $l$
Table 4: Priority structure for Example 4.2

Note that $i\succ_{a}\\{j,k\\}$, $j\succ_{b}\\{i,k\\}$, and
$k\succ_{c}\\{i,j\\}$, which means $[(i,j,k),(a,b,c)]$ is a weak cycle in
$\succ_{A}$. Furthermore, it is straightforward to verify that $\succ_{A}$ is
acyclic. $\Diamond$

Our next theorem says that dual ownership and strong acyclicity are equivalent
properties of an FPTTC rule on the unrestricted domain
$\mathbb{L}^{n}(A\cup\\{a_{0}\\})$.

######  Theorem 4.3.

On the domain $\mathbb{L}^{n}(A\cup\\{a_{0}\\})$, an FPTTC rule
$T^{\succ_{A}}$ satisfies dual ownership if and only if it is strongly
acyclic.

The proof of this theorem is relegated to Appendix C.

Since dual ownership is both necessary and sufficient condition for an FPTTC
rule to be OSP-implementable on the unrestricted domain (see Theorem 4.1), we
obtain the following corollary from Theorem 4.3.

######  Corollary 4.2.

On the domain $\mathbb{L}^{n}(A\cup\\{a_{0}\\})$, an FPTTC rule
$T^{\succ_{A}}$ is OSP-implementable if and only if it is strongly acyclic.

###  4.3 Relation with Ergin-acyclicity and an illustrative corollary

####  4.3.1 Ergin-acyclicity

Ergin-acyclicity is a well-known acyclicity condition in the literature. In
what follows, we present this notion, and show that it is stronger than strong
acyclicity.

######  Definition 4.4.

A tuple $[(i_{1},i_{2},i_{3}),(a_{1},a_{2})]$, where $i_{1},i_{2},i_{3}\in N$
and $a_{1},a_{2}\in A$ are all distinct, is called an Ergin-cycle in a
priority structure $\succ_{A}$ if
$i_{1}\succ_{a_{1}}i_{2}\succ_{a_{1}}i_{3}\succ_{a_{2}}i_{1}$.

We call a priority structure Ergin-acyclic if it contains no Ergin-cycles, and
call an FPTTC rule Ergin-acyclic if it is associated with an Ergin-acyclic
priority structure.

######  Proposition 4.1.

Every Ergin-acyclic priority structure is strongly acyclic.

###### Proof of Proposition 4.1..

We prove the contrapositive. Let $\succ_{A}$ be a priority structure that
contains a weak cycle $[(i_{1},i_{2},i_{3}),(a_{1},a_{2},a_{3})]$. By the
definition of a weak cycle, we have $i_{1}\succ_{a_{1}}\\{i_{2},i_{3}\\}$,
$i_{2}\succ_{a_{2}}i_{1}$, and $i_{3}\succ_{a_{3}}i_{1}$. We distinguish the
following two cases.

  1. (i)

Suppose $i_{1}\succ_{a_{1}}i_{2}\succ_{a_{1}}i_{3}$.
The facts $i_{1}\succ_{a_{1}}i_{2}\succ_{a_{1}}i_{3}$ and
$i_{3}\succ_{a_{3}}i_{1}$ together imply that
$[(i_{1},i_{2},i_{3}),(a_{1},a_{3})]$ is an Ergin-cycle in $\succ_{A}$.

  2. (ii)

Suppose $i_{1}\succ_{a_{1}}i_{3}\succ_{a_{1}}i_{2}$.
The facts $i_{1}\succ_{a_{1}}i_{3}\succ_{a_{1}}i_{2}$ and
$i_{2}\succ_{a_{2}}i_{1}$ together imply that
$[(i_{1},i_{3},i_{2}),(a_{1},a_{2})]$ is an Ergin-cycle in $\succ_{A}$.

Since Cases i and ii are exhaustive, it follows that $\succ_{A}$ is not Ergin-
acyclic. This completes the proof of Proposition 4.1. ∎

######  Remark 4.3.

For an arbitrary domain of preference profiles $\mathcal{P}_{N}$, every Ergin-
acyclic FPTTC rule is OSP-implementable. To see this, note that every Ergin-
acyclic FPTTC rule is strongly acyclic (see Proposition 4.1) and every
strongly acyclic FPTTC rule is OSP-implementable on the unrestricted domain
$\mathbb{L}^{n}(A\cup\\{a_{0}\\})$ (see Corollary 4.2). Therefore, every
Ergin-acyclic FPTTC rule is OSP-implementable on any domain of preference
profiles.

It is worth noting that the converse of Proposition 4.1 is not true. Below,
Example 4.3 presents a priority structure, which is strongly acyclic but not
Ergin-acyclic.

######  Example 4.3.

Consider an allocation problem with three agents $N=\\{i,j,k\\}$ and three
objects $A=\\{a,b,c\\}$. Let $\succ_{A}$ be as follows:

$\succ_{a}$ | $\succ_{b}$ | $\succ_{c}$
---|---|---
$i$ | $i$ | $j$
$j$ | $k$ | $k$
$k$ | $j$ | $i$
Table 5: Priority structure for Example 4.3

Note that $i\succ_{b}k\succ_{b}j$ and $j\succ_{c}i$, which means
$[(i,k,j),(b,c)]$ is an Ergin-cycle in $\succ_{A}$. Furthermore, it is
straightforward to verify that $\succ_{A}$ is strongly acyclic. $\Diamond$

####  4.3.2 OSP-implementability of agent-proposing deferred acceptance rules

Apart from FPTTC rules, another well-known class of priority-based assignment
rules is agent-proposing deferred acceptance (APDA) rules. Below, we present a
brief description of such a rule for the sake of completeness. This
description follows Kesten (2006).

For a given priority structure $\succ_{A}$, the APDA rule $D^{\succ_{A}}$
associated with $\succ_{A}$ is defined by an iterative procedure as follows.
Consider an arbitrary preference profile
$P_{N}\in\mathbb{L}^{n}(A\cup\\{a_{0}\\})$.

  * Step 1.

Each agent “applies to” her favorite element among all the objects and the
outside option $a_{0}$. If the outside option is the favorite element of an
agent, then she is assigned the outside option. If the number of agents who
apply to an object, say $a$, is at least one, then the most preferred agent
among them according to $\succ_{a}$ tentatively holds $a$. The remaining
agents are “rejected”.

  * Step $2$.

Each agent, who is rejected by an object at Step $1$, applies to her next
favorite element. If the outside option is the next favorite element of an
agent, then she is assigned the outside option. If the total number of agents
who apply to an object, say $a$, and who is tentatively holding $a$ from
earlier steps, is at least one, then the most preferred agent among them
according to $\succ_{a}$ tentatively holds $a$. The remaining agents are
rejected.

This procedure is repeated iteratively until all agents are assigned. At this
point, the tentative holding of an object becomes permanent. This completes
the description of an APDA rule.

Ashlagi and Gonczarowski (2018) study the OSP-implementability of APDA rules,
and show that Ergin-acyclicity is a sufficient condition for an APDA rule to
be OSP-implementable. We derive their result as a corollary of our results.

######  Corollary 4.3 (Theorem 2 in Ashlagi and Gonczarowski (2018)).

On the domain $\mathbb{L}^{n}(A\cup\\{a_{0}\\})$, an APDA rule $D^{\succ_{A}}$
is OSP-implementable if $\succ_{A}$ is Ergin-acyclic.

###### Proof of Corollary 4.3..

Kesten (2006) shows that for a priority structure $\succ_{A}$, the associated
APDA rule $D^{\succ_{A}}$ and the associated FPTTC rule $T^{\succ_{A}}$ are
equivalent if and only if $\succ_{A}$ is Ergin-acyclic (see Theorem 1 in
Kesten (2006)).202020Kesten (2006) introduces the notion of Kesten-acyclicity
in a many-to-one matching model, and shows that it is both necessary and
sufficient condition for the associated APDA rule and the associated FPTTC
rule to be equivalent. It is well-known that Kesten-acyclicity and Ergin-
acyclicity are equivalent in the context of one-to-one matching. Since Ergin-
acyclicity implies strong acyclicity (see Proposition 4.1), Corollary 4.3
follows from Corollary 4.2 and Kesten (2006)’s result. ∎

Since strong acyclicity is weaker than Ergin-acyclicity (see Proposition 4.1),
in view of Corollary 4.3, one may wonder about the connection between strong
acyclicity and the OSP-implementability of APDA rules: Like Ergin-acyclicity,
is strong acyclicity also a sufficient condition for an APDA rule to be OSP-
implementable? Or is it necessary? In what follows, we show that strong
acyclicity is not a sufficient condition for an APDA rule to be OSP-
implementable (Example 4.4), but is a necessary condition (Proposition 4.2).

######  Example 4.4.

Consider an allocation problem with three agents $N=\\{i,j,k\\}$ and three
objects $A=\\{a,b,c\\}$. Let $\succ_{A}$ be as follows:

$\succ_{a}$ | $\succ_{b}$ | $\succ_{c}$
---|---|---
$i$ | $i$ | $k$
$j$ | $j$ | $i$
$k$ | $k$ | $j$
Table 6: Priority structure for Example 4.4

It is straightforward to verify that $\succ_{A}$ is strongly acyclic.
Furthermore, using similar arguments as for Proposition 1 in Ashlagi and
Gonczarowski (2018), it follows that the APDA rule $D^{\succ_{A}}$ is not OSP-
implementable on the restricted domain $\mathbb{L}^{3}(A)$, and consequently
is not OSP-implementable on the unrestricted domain
$\mathbb{L}^{3}(A\cup\\{a_{0}\\})$. $\Diamond$

######  Proposition 4.2.

On the domain $\mathbb{L}^{n}(A\cup\\{a_{0}\\})$, an APDA rule $D^{\succ_{A}}$
is OSP-implementable only if it is strongly acyclic.

The proof of this proposition is relegated to Appendix D.

##  5 SOSP-implementability of FPTTC rules

Before proceeding with our next results, we first present a well-known class
of assignment rules, namely serial dictatorships. In a serial dictatorship,
agents are ordered, and the first agent in the ordering gets her most
preferred element among all the objects and the outside option $a_{0}$, the
second agent in the ordering gets her most preferred element among the
remaining objects and the outside option $a_{0}$, etc.

Note that serial dictatorships are special cases of FPTTC rules. For example,
consider an allocation problem with three agents $N=\\{1,2,3\\}$ and three
objects $A=\\{a_{1},a_{2},a_{3}\\}$. The priority structure associated with
the FPTTC rule that corresponds to the serial dictatorship with the
exogenously given ordering $(1,2,3)$ is as follows:

$\succ_{a_{1}}$ | $\succ_{a_{2}}$ | $\succ_{a_{3}}$
---|---|---
$1$ | $1$ | $1$
$2$ | $2$ | $2$
$3$ | $3$ | $3$

Further note that serial dictatorships are SOSP-implementable. For example,
consider the allocation problem with three agents $N=\\{1,2,3\\}$ and three
objects $A=\\{a_{1},a_{2},a_{3}\\}$. On the restricted domain
$\mathbb{L}^{3}(A)$, the SOSP mechanism in Figure 2 implements the serial
dictatorship with the exogenously given ordering $(1,2,3)$.

pt1pt2pt$(a_{1},a_{2},a_{3})$$\cdot a_{2}\cdot
a_{3}\cdot$pt$(a_{1},a_{3},a_{2})$$\cdot a_{3}\cdot
a_{2}\cdot$$\tau(P_{1})=a_{1}$pt2pt$(a_{2},a_{1},a_{3})$$\cdot a_{1}\cdot
a_{3}\cdot$pt$(a_{2},a_{3},a_{1})$$\cdot a_{3}\cdot
a_{1}\cdot$$\tau(P_{1})=a_{2}$pt2pt$(a_{3},a_{1},a_{2})$$\cdot a_{1}\cdot
a_{2}\cdot$pt$(a_{3},a_{2},a_{1})$$\cdot a_{2}\cdot
a_{1}\cdot$$\tau(P_{1})=a_{3}$First dictatorSecond dictator Figure 2: SOSP
mechanism that implements the serial dictatorship with ordering $(1,2,3)$ on
$\mathbb{L}^{3}(A)$

Using a similar logic as for Figure 2, one can construct an SOSP mechanism
that implements a serial dictatorship on the unrestricted domain
$\mathbb{L}^{n}(A\cup\\{a_{0}\\})$. We concisely sum up the above discussion
as follows.

######  Remark 5.1.

For an arbitrary domain of preference profiles $\mathcal{P}_{N}$, every serial
dictatorship is an SOSP-implementable FPTTC rule.

Remark 5.1 arises a natural question: Apart from serial dictatorships, are
there any other SOSP-implementable FPTTC rules? Theorem 5.1 and Theorem 5.3
provide answers to this question for the domains $\mathbb{L}^{n}(A)$ and
$\mathbb{L}^{n}(A\cup\\{a_{0}\\})$, respectively.

###  5.1 Results on the restricted domain $\mathbb{L}^{n}(A)$

To characterize all SOSP-implementable FPTTC rules on the restricted domain
$\mathbb{L}^{n}(A)$, we introduce a subclass of FPTTC rules, namely weak
serial dictatorships, in this subsection.

######  Definition 5.1.

An FPTTC rule $T^{\succ_{A}}$ is a weak serial dictatorship if for all
$P_{N}\in\mathbb{L}^{n}(A)$ and all $s$,

$|A_{s}(P_{N})|>2\implies|\mathcal{T}(\succ_{A_{s}(P_{N})}^{N_{s}(P_{N})})|=1.$

In other words, an FPTTC rule is a weak serial dictatorship if, for any
preference profile in $\mathbb{L}^{n}(A)$ and any step of the FPTTC rule at
that preference profile, if there are more than two objects remaining in the
reduced market at that step, then there is exactly one agent who owns all
those remaining objects at that step. Notice that on the restricted domain
$\mathbb{L}^{n}(A)$, a weak serial dictatorship has a similar procedure to a
serial dictatorship as long as there are more than two objects remaining in
the market.

######  Remark 5.2.

Every serial dictatorship is a weak serial dictatorship.

Our next theorem says that on the restricted domain $\mathbb{L}^{n}(A)$, weak
serial dictatorships are the only SOSP-implementable FPTTC rules.

######  Theorem 5.1.

On the domain $\mathbb{L}^{n}(A)$, an FPTTC rule $T^{\succ_{A}}$ is SOSP-
implementable if and only if it is a weak serial dictatorship.

The proof of this theorem is relegated to Appendix E.

Similarly as dual ownership, to verify whether a given FPTTC rule is a weak
serial dictatorship or not, one needs to check its behavior at every step at
every preference profile in the restricted domain $\mathbb{L}^{n}(A)$. In view
of this observation, we present our next result regarding the configuration of
the priority structures associated with these rules. We use the following
terminology to facilitate the result. For $\succ\in\mathbb{L}(N)$ and $i\in
N$, we define $rank(i,\succ)=m$ if $|\\{j\in N\mid j\succ i\\}|=m-1$.

######  Theorem 5.2.

An FPTTC rule $T^{\succ_{A}}$ is a weak serial dictatorship if and only if
$\succ_{A}$ has the following property: for all $a,b\in A$ and all $i\in N$,

$rank(i,\succ_{a})\leq|A|-2\implies rank(i,\succ_{a})=rank(i,\succ_{b}).$

The proof of this theorem is relegated to Appendix F.

As a corollary of Theorem 5.1 and Theorem 5.2, we obtain the configuration of
the priority structures associated with the SOSP-implementable FPTTC rules on
the restricted domain $\mathbb{L}^{n}(A)$.

######  Corollary 5.1.

On the domain $\mathbb{L}^{n}(A)$, an FPTTC rule $T^{\succ_{A}}$ is SOSP-
implementable if and only if $\succ_{A}$ has the following property: for all
$a,b\in A$ and all $i\in N$,

$rank(i,\succ_{a})\leq|A|-2\implies rank(i,\succ_{a})=rank(i,\succ_{b}).$

We obtain the following corollary from Corollary 5.1. It says when there are
more objects than agents, SOSP-implementable FPTTC rules on the restricted
domain $\mathbb{L}^{n}(A)$ are characterized as serial dictatorships.

######  Corollary 5.2.

Suppose $|A|>|N|$. On the domain $\mathbb{L}^{n}(A)$, an FPTTC rule
$T^{\succ_{A}}$ is SOSP-implementable if and only if it is a serial
dictatorship.

###  5.2 Results on the unrestricted domain $\mathbb{L}^{n}(A\cup\\{a_{0}\\})$

Recall that the serial dictatorships are SOSP-implementable FPTTC rules (see
Remark 5.1). In this subsection, we show that on the unrestricted domain
$\mathbb{L}^{n}(A\cup\\{a_{0}\\})$, they are the only SOSP-implementable FPTTC
rules.

######  Theorem 5.3.

On the domain $\mathbb{L}^{n}(A\cup\\{a_{0}\\})$, an FPTTC rule
$T^{\succ_{A}}$ is SOSP-implementable if and only if it is a serial
dictatorship.

The proof of this theorem is relegated to Appendix G.

##  6 Simple strategy-proofness

OSP-implementation presumes that the agents understand how their own future
actions will affect outcomes (the worst and the best possible final outcomes
are taken only over opponents’ future actions), and consequently, they might
be concerned about having time-inconsistent preferences or making a mistake
while performing demanding backward induction over their own future actions.
Pycia and Troyan (2019) introduce SOSP-implementation as a way to resolve this
issue by relaxing the assumption that the agents fully comprehend how their
own future actions will affect outcomes. Another way to resolve this issue
will be by calling each agent to play at most once so that they need not be
worried about their own future actions. In view of this observation, we
introduce the notion of simple strategy-proofness in this section.

The concept of simple strategy-proofness is based on a simple OSP mechanism. A
mechanism is simple if every agent is called to play at most once along a
path. An assignment rule is simply strategy-proof if there exists a simple OSP
mechanism that implements the assignment rule. In what follows, we present
formal definitions of these. Recall the definition of a mechanism $G$ given in
Section 2.3.

######  Definition 6.1.

A mechanism $G=\langle T,\eta^{LA},\eta^{NA},\eta^{EP}\rangle$ on
$\mathcal{P}_{N}$ is simple if $\eta^{NA}(v)\neq\eta^{NA}(v^{\prime})$ for all
distinct $v,v^{\prime}\in V(T)\setminus L(T)$ that appear in the same path.

An assignment rule $f:\mathcal{P}_{N}\rightarrow\mathcal{M}$ is simply
strategy-proof (on $\mathcal{P}_{N}$) if there exists a simple OSP mechanism
$G$ on $\mathcal{P}_{N}$ such that $f=f^{G}$.

By definition, simple strategy-proofness is stronger than OSP-
implementability. Our next result shows that simple strategy-proofness is even
stronger than SOSP-implementability.

######  Proposition 6.1.

For an arbitrary domain of preference profiles $\mathcal{P}_{N}$, every simple
OSP mechanism is SOSP, and consequently, every simply strategy-proof
assignment rule is SOSP-implementable.

The proof of this proposition is relegated to Appendix H.

It is worth mentioning that the converse of Proposition 6.1 is not true in
general. Example 6.1 presents a domain of preference profiles and an FPTTC
rule, which is SOSP-implementable but not simply strategy-proof on the given
domain.

######  Example 6.1.

Consider an allocation problem with two agents $N=\\{1,2\\}$ and four objects
$A=\\{a_{1},a_{2},a_{3},a_{4}\\}$. Let
$\tilde{\mathcal{P}}=\\{a_{1}a_{4}a_{3}a_{2}a_{0},a_{2}a_{3}a_{4}a_{1}a_{0},a_{3}a_{2}a_{4}a_{1}a_{0},a_{4}a_{1}a_{3}a_{2}a_{0}\\}$
be a set of preferences. Let $\succ_{A}$ be as follows:

$\succ_{a_{1}}$ | $\succ_{a_{2}}$ | $\succ_{a_{3}}$ | $\succ_{a_{4}}$
---|---|---|---
$1$ | $2$ | $2$ | $1$
$2$ | $1$ | $1$ | $2$
Table 7: Priority structure for Example 6.1

Consider the FPTTC rule $T^{\succ_{A}}$ on the domain
$\tilde{\mathcal{P}}^{2}$. It is straightforward to verify that the mechanism
in Figure 3 is SOSP and implements $T^{\succ_{A}}$ on
$\tilde{\mathcal{P}}^{2}$.

pt1pt2pt$(a_{1},a_{2})$$a_{2}a_{3}a_{4}a_{0}$pt$(a_{1},a_{3})$$a_{3}a_{2}a_{4}a_{0}$pt$(a_{1},a_{4})$$a_{4}a_{3}a_{2}a_{0}$$\tau(P_{1})=a_{1}$pt2pt1pt$(a_{2},a_{1})$$\tau(P_{1})=a_{2}$pt$(a_{3},a_{1})$$\tau(P_{1})=a_{3}$$\tau(P_{2})=a_{1}$pt$(a_{3},a_{2})$$\tau(P_{2})=a_{2}$pt$(a_{2},a_{3})$$\tau(P_{2})=a_{3}$pt1pt$(a_{2},a_{4})$$\tau(P_{1})=a_{2}$pt$(a_{3},a_{4})$$\tau(P_{1})=a_{3}$$\tau(P_{2})=a_{4}$$\tau(P_{1})\in\\{a_{2},a_{3}\\}$pt2pt$(a_{4},a_{1})$$a_{1}a_{3}a_{2}a_{0}$pt$(a_{4},a_{2})$$a_{2}a_{3}a_{1}a_{0}$pt$(a_{4},a_{3})$$a_{3}a_{2}a_{1}a_{0}$$\tau(P_{1})=a_{4}$

Figure 3: Tree Representation for Example 6.1

We argue that $T^{\succ_{A}}$ is not simply strategy-proof on
$\tilde{\mathcal{P}}^{2}$. Consider the preference profiles (together with the
outcomes of $T^{\succ_{A}}$) presented in Table 8.

Preference profiles | $\mbox{Agent }1$ | $\mbox{Agent }2$ | $T^{\succ_{A}}_{1}$ | $T^{\succ_{A}}_{2}$
---|---|---|---|---
$\tilde{P}_{N}^{1}$ | $a_{2}a_{3}a_{4}a_{1}a_{0}$ | $a_{2}a_{3}a_{4}a_{1}a_{0}$ | $a_{3}$ | $a_{2}$
$\tilde{P}_{N}^{2}$ | $a_{3}a_{2}a_{4}a_{1}a_{0}$ | $a_{3}a_{2}a_{4}a_{1}a_{0}$ | $a_{2}$ | $a_{3}$
$\tilde{P}_{N}^{3}$ | $a_{3}a_{2}a_{4}a_{1}a_{0}$ | $a_{4}a_{1}a_{3}a_{2}a_{0}$ | $a_{3}$ | $a_{4}$
$\tilde{P}_{N}^{4}$ | $a_{2}a_{3}a_{4}a_{1}a_{0}$ | $a_{4}a_{1}a_{3}a_{2}a_{0}$ | $a_{2}$ | $a_{4}$
$\tilde{P}_{N}^{5}$ | $a_{1}a_{4}a_{3}a_{2}a_{0}$ | $a_{1}a_{4}a_{3}a_{2}a_{0}$ | $a_{1}$ | $a_{4}$
$\tilde{P}_{N}^{6}$ | $a_{2}a_{3}a_{4}a_{1}a_{0}$ | $a_{1}a_{4}a_{3}a_{2}a_{0}$ | $a_{2}$ | $a_{1}$
$\tilde{P}_{N}^{7}$ | $a_{4}a_{1}a_{3}a_{2}a_{0}$ | $a_{4}a_{1}a_{3}a_{2}a_{0}$ | $a_{4}$ | $a_{1}$
Table 8: Preference profiles for Example 6.1

Assume for contradiction that $T^{\succ_{A}}$ is simply strategy-proof on
$\tilde{\mathcal{P}}^{2}$. So, there exists a simple OSP mechanism $\tilde{G}$
that implements $T^{\succ_{A}}$ on $\tilde{\mathcal{P}}_{N}$. Note that since
$T^{\succ_{A}}(\tilde{P}_{N}^{1})\neq T^{\succ_{A}}(\tilde{P}_{N}^{2})$, there
exists a node in the simple OSP mechanism $\tilde{G}$ that has at least two
edges. Consider the first node (from the root) $v$ that has at least two
edges. We distinguish the following two cases.

  1. (i)

Suppose $\eta^{NA}(v)=1$.
By obvious strategy-proofness of $\tilde{G}$, the facts
$a_{2}\tilde{P}_{1}^{1}a_{3}$, $T^{\succ_{A}}_{1}(\tilde{P}_{N}^{1})=a_{3}$,
and $T^{\succ_{A}}_{1}(\tilde{P}_{N}^{2})=a_{2}$ together imply that
$\tilde{P}_{1}^{1}$ and $\tilde{P}_{1}^{2}$ do not diverge at $v$. This,
together with the facts that $\tilde{P}_{1}^{1}=\tilde{P}_{1}^{4}$,
$\tilde{P}_{1}^{2}=\tilde{P}_{1}^{3}$, $\tilde{P}_{2}^{3}=\tilde{P}_{2}^{4}$,
and $T^{\succ_{A}}(\tilde{P}_{N}^{3})\neq T^{\succ_{A}}(\tilde{P}_{N}^{4})$,
implies that there exists a node $v^{\prime}$ at which $\tilde{P}_{1}^{1}$ and
$\tilde{P}_{1}^{2}$ diverge. Clearly, $v$ and $v^{\prime}$ are distinct nodes
appearing in the same path such that $\eta^{NA}(v)=\eta^{NA}(v^{\prime})=1$.
This contradicts the fact that $\tilde{G}$ is a simple mechanism.

  2. (ii)

Suppose $\eta^{NA}(v)=2$.
By obvious strategy-proofness of $\tilde{G}$, the facts
$a_{1}\tilde{P}_{2}^{5}a_{4}$, $T^{\succ_{A}}_{2}(\tilde{P}_{N}^{5})=a_{4}$,
and $T^{\succ_{A}}_{2}(\tilde{P}_{N}^{7})=a_{1}$ together imply that
$\tilde{P}_{2}^{5}$ and $\tilde{P}_{2}^{7}$ do not diverge at $v$. This,
together with the facts that $\tilde{P}_{2}^{5}=\tilde{P}_{2}^{6}$,
$\tilde{P}_{2}^{7}=\tilde{P}_{2}^{4}$, $\tilde{P}_{1}^{4}=\tilde{P}_{1}^{6}$,
and $T^{\succ_{A}}(\tilde{P}_{N}^{4})\neq T^{\succ_{A}}(\tilde{P}_{N}^{6})$,
implies that there exists a node $v^{\prime}$ at which $\tilde{P}_{2}^{5}$ and
$\tilde{P}_{2}^{7}$ diverge. Clearly, $v$ and $v^{\prime}$ are distinct nodes
appearing in the same path such that $\eta^{NA}(v)=\eta^{NA}(v^{\prime})=2$.
This contradicts the fact that $\tilde{G}$ is a simple mechanism.

Since Cases i and ii are exhaustive, it follows that $T^{\succ_{A}}$ is not
simply strategy-proof on $\tilde{\mathcal{P}}^{2}$. $\Diamond$

Example 6.1 shows that on an arbitrary domain of preference profiles, every
SOSP-implementable FPTTC rule might not be simply strategy-proof. However, our
next result shows that on the restricted domain $\mathbb{L}^{n}(A)$ and the
unrestricted domain $\mathbb{L}^{n}(A\cup\\{a_{0}\\})$, every SOSP-
implementable FPTTC rule is simply strategy-proof.

######  Theorem 6.1.

Suppose
$\mathcal{P}_{N}\in\Big{\\{}\mathbb{L}^{n}(A),\mathbb{L}^{n}(A\cup\\{a_{0}\\})\Big{\\}}$.
On the domain $\mathcal{P}_{N}$, an FPTTC rule $T^{\succ_{A}}$ is simply
strategy-proof if and only if it is SOSP-implementable.

The proof of this proposition is relegated to Appendix I.

We obtain the following corollary from Theorem 5.1, Theorem 5.3, and Theorem
6.1.

######  Corollary 6.1.

  1. (a)

On the domain $\mathbb{L}^{n}(A)$, an FPTTC rule $T^{\succ_{A}}$ is simply
strategy-proof if and only if it is a weak serial dictatorship.

  2. (b)

On the domain $\mathbb{L}^{n}(A\cup\\{a_{0}\\})$, an FPTTC rule
$T^{\succ_{A}}$ is simply strategy-proof if and only if it is a serial
dictatorship.

Our results show that while the class of simply strategy-proof FPTTC rules is
generally a subset of the class of SOSP-implementable FPTTC rules, the
“richness” of the domains $\mathbb{L}^{n}(A)$ and
$\mathbb{L}^{n}(A\cup\\{a_{0}\\})$ makes these two classes equivalent. In view
of this observation, one may wonder whether the richness drives this
equivalence beyond FPTTC rules. In Appendix J, we show that on both of these
domains, not every SOSP-implementable assignment rule is simply strategy-
proof.

##  Appendix A Some additional notations

It will be convenient to introduce some additional notations for the proofs.
Following our notational terminology in Section 2.1, for a preference
$P\in\mathbb{L}(A\cup\\{a_{0}\\})$ and two disjoint subsets $A^{\prime}$ and
$\hat{A}$ of $A\cup\\{a_{0}\\}$, we write $A^{\prime}P\hat{A}$ to mean that
$aPb$ for all $a\in A^{\prime}$ and all $b\in\hat{A}$. Furthermore, for a
preference profile $P_{N}$ and an FPTTC rule, let $I_{s}(P_{N})$ be the set of
assigned agents at Step $s$, $I^{s}(P_{N})$ be the set of assigned agents up
to Step $s$ (including Step $s$), $X_{s}(P_{N})$ be the set of assigned
objects at Step $s$, $X^{s}(P_{N})$ be the set of assigned objects up to Step
$s$ (including Step $s$), and $O_{s}(i,P_{N})$ be the set of objects owned by
agent $i$ at Step $s$.

##  Appendix B Proof of Theorem 4.2

(If part) Suppose $T^{\succ_{A}}$ does not satisfy dual ownership on
$\mathbb{L}^{n}(A)$. We show that $\succ_{A}$ contains a priority cycle. Since
$T^{\succ_{A}}$ does not satisfy dual ownership on $\mathbb{L}^{n}(A)$, there
exist a preference profile $\tilde{P}_{N}\in\mathbb{L}^{n}(A)$ and a step
$s^{*}$ of $T^{\succ_{A}}$ at $\tilde{P}_{N}$ such that
$|\mathcal{T}(\succ_{A_{s^{*}}(\tilde{P}_{N})}^{N_{s^{*}}(\tilde{P}_{N})})|>2$.
This implies that there exist three agents $i_{1},i_{2},i_{3}\in
N_{s^{*}}(\tilde{P}_{N})$ and three objects $a_{1},a_{2},a_{3}\in
A_{s^{*}}(\tilde{P}_{N})$ such that for all $h=1,2,3$, agent $i_{h}$ owns the
object $a_{h}$ at Step $s^{*}$. We proceed to show that
$[(i_{1},i_{2},i_{3}),(a_{1},a_{2},a_{3})]$ is a priority cycle in
$\succ_{A}$. We distinguish the following two cases.
Case 1: Suppose $s^{*}=1$.

Since for all $h=1,2,3$, agent $i_{h}$ owns the object $a_{h}$ at Step $1$, by
the definition of $T^{\succ_{A}}$, it follows that $\tau(\succ_{a_{h}})=i_{h}$
for all $h=1,2,3$. This means $[(i_{1},i_{2},i_{3}),(a_{1},a_{2},a_{3})]$ is a
priority cycle in $\succ_{A}$.
Case 2: Suppose $s^{*}>1$.

Let $\\{i_{4},\ldots,i_{t}\\}\subseteq N\setminus\\{i_{1},i_{2},i_{3}\\}$ and
$\\{a_{4},\ldots,a_{t}\\}\subseteq A\setminus\\{a_{1},a_{2},a_{3}\\}$ be as
follows.

  1. (i)

$\\{i_{4},\ldots,i_{t}\\}=I^{s^{*}-1}(\tilde{P}_{N})$.

  2. (ii)

For all $h=4,\ldots,t$, $\\{a_{h}\\}=\big{(}X_{s}(\tilde{P}_{N})\cap
O_{s}(i_{h},\tilde{P}_{N})\big{)}$ where $i_{h}\in I_{s}(\tilde{P}_{N})$ for
some $s<s^{*}$. To see that this is well-defined note that by the definition
of $T^{\succ_{A}}$ and the fact $\tilde{P}_{N}\in\mathbb{L}^{n}(A)$, (a) for
every $i_{h}\in I^{s^{*}-1}(\tilde{P}_{N})$, there exists exactly one step $s$
with $s<s^{*}$ such that $i_{h}\in I_{s}(\tilde{P}_{N})$, and (b)
$O_{s}(i_{h},\tilde{P}_{N})\cap X_{s}(\tilde{P}_{N})$ is a singleton set for
all $i_{h}\in I_{s}(\tilde{P}_{N})$ with $s<s^{*}$.

It follows from the definition of $T^{\succ_{A}}$ and the construction of
$\\{i_{4},\ldots,i_{t}\\}$ and $\\{a_{4},\ldots,a_{t}\\}$ that
$U(i_{h},\succ_{a_{h}})\subseteq\\{i_{4},\ldots,i_{t}\\}$ for all
$h=1,\ldots,t$. This implies that $[(i_{1},i_{2},i_{3}),(a_{1},a_{2},a_{3})]$
is a priority cycle in $\succ_{A}$, which completes the proof of the “if” part
of Theorem 4.2.

(Only-if part) Suppose $\succ_{A}$ contains a priority cycle
$[(i_{1},i_{2},i_{3}),(a_{1},a_{2},a_{3})]$. We show that $T^{\succ_{A}}$ does
not satisfy dual ownership on $\mathbb{L}^{n}(A)$. By the definition of a
priority cycle, one of the following two statements must hold.

  1. (1)

$\tau(\succ_{a_{h}})=i_{h}$ for all $h=1,2,3$.

  2. (2)

There exist distinct agents $i_{4},\ldots,i_{t}\in
N\setminus\\{i_{1},i_{2},i_{3}\\}$ and distinct objects $a_{4},\ldots,a_{t}\in
A\setminus\\{a_{1},a_{2},a_{3}\\}$ such that for all $h=1,\ldots,t$, we have
$U(i_{h},\succ_{a_{h}})\subseteq\\{i_{4},\ldots,i_{t}\\}$.

We distinguish the following two cases.
Case 1: Suppose 1 holds.

Since $\tau(\succ_{a_{h}})=i_{h}$ for all $h=1,2,3$, it must be that for any
preference profile, agents $i_{1},i_{2}$, and $i_{3}$ own objects
$a_{1},a_{2}$, and $a_{3}$, respectively, at Step $1$ of $T^{\succ_{A}}$ at
that preference profile. Therefore $T^{\succ_{A}}$ does not satisfy dual
ownership on $\mathbb{L}^{n}(A)$.
Case 2: Suppose 2 holds.

Consider the preference profile $\tilde{P}_{N}\in\mathbb{L}^{n}(A)$ defined as
follows. Each $i_{h}\in\\{i_{4},\ldots,i_{t}\\}$ has a preference
$\tilde{P}_{i_{h}}$ such that $\tau(\tilde{P}_{i_{h}})=a_{h}$ and each $j\in
N\setminus\\{i_{4},\ldots,i_{t}\\}$ has a preference $\tilde{P}_{j}$ such that
$\\{a_{4},\ldots,a_{t}\\}\tilde{P}_{j}(A\setminus\\{a_{4},\ldots,a_{t}\\})$.
The next claim establishes some properties of the outcome of $T^{\succ_{A}}$
at $\tilde{P}_{N}$ at Step 1.

######  Claim B.1.

(a) $I_{1}(\tilde{P}_{N})\subseteq\\{i_{4},\ldots,i_{t}\\}$, and (b)
$T^{\succ_{A}}_{i_{h}}(\tilde{P}_{N})=a_{h}$ for all $h=4,\ldots,t$ with
$i_{h}\in I_{1}(\tilde{P}_{N})$.

###### Proof of Claim B.1..

By the assumptions for Case 2, it follows that
$\\{a_{4},\ldots,a_{t}\\}\subseteq\underset{h=4}{\overset{t}{\cup}}\hskip
2.84526ptO_{1}(i_{h},\tilde{P}_{N})$. Moreover, by the construction of
$\tilde{P}_{N}$, we have $\tau(\tilde{P}_{i})\in\\{a_{4},\ldots,a_{t}\\}$ for
all $i\in N$. Since
$\\{a_{4},\ldots,a_{t}\\}\subseteq\underset{h=4}{\overset{t}{\cup}}\hskip
2.84526ptO_{1}(i_{h},\tilde{P}_{N})$ and
$\tau(\tilde{P}_{i})\in\\{a_{4},\ldots,a_{t}\\}$ for all $i\in N$, it follows
from the definition of $T^{\succ_{A}}$ that
$I_{1}(\tilde{P}_{N})\subseteq\\{i_{4},\ldots,i_{t}\\}$ and
$T^{\succ_{A}}_{i}(\tilde{P}_{N})=\tau(\tilde{P}_{i})$ for all $i\in
I_{1}(\tilde{P}_{N})$. These two facts, along with the construction of
$\tilde{P}_{N}$, complete the proof of Claim B.1. ∎

By Claim B.1, $I_{1}(\tilde{P}_{N})\subseteq\\{i_{4},\ldots,i_{t}\\}$ and
$T^{\succ_{A}}_{i_{h}}(\tilde{P}_{N})=a_{h}$ for all $h=4,\ldots,t$ with
$i_{h}\in I_{1}(\tilde{P}_{N})$. We proceed to show that there will be a step
$s^{*}$ such that $I^{s^{*}}(\tilde{P}_{N})=\\{i_{4},\ldots,i_{t}\\}$ and
$T^{\succ_{A}}_{i_{h}}(\tilde{P}_{N})=a_{h}$ for all $h=4,\ldots,t$. If
$I_{1}(\tilde{P}_{N})=\\{i_{4},\ldots,i_{t}\\}$, then $s^{*}=1$ and we are
done. Suppose $I_{1}(\tilde{P}_{N})\subsetneq\\{i_{4},\ldots,i_{t}\\}$, that
is, $I_{1}(\tilde{P}_{N})$ is a proper subset of $\\{i_{4},\ldots,i_{t}\\}$.
Since $I_{1}(\tilde{P}_{N})\subsetneq\\{i_{4},\ldots,i_{t}\\}$ and
$T^{\succ_{A}}_{i_{h}}(\tilde{P}_{N})=a_{h}$ for all $h=4,\ldots,t$ with
$i_{h}\in I_{1}(\tilde{P}_{N})$, using similar argument as for Claim B.1, it
follows from the assumptions for Case 2 and the construction of
$\tilde{P}_{N}$ that
$I_{2}(\tilde{P}_{N})\subseteq\big{(}\\{i_{4},\ldots,i_{t}\\}\setminus
I_{1}(\tilde{P}_{N})\big{)}$ and $T^{\succ_{A}}_{i_{h}}(\tilde{P}_{N})=a_{h}$
for all $h=4,\ldots,t$ with $i_{h}\in I_{2}(\tilde{P}_{N})$. If
$I_{1}(\tilde{P}_{N})\cup I_{2}(\tilde{P}_{N})=\\{i_{4},\ldots,i_{t}\\}$, then
$s^{*}=2$ and we are done. Otherwise, continuing in this manner, we obtain a
step $s^{*}>2$ of $T^{\succ_{A}}$ at $\tilde{P}_{N}$ such that
$I^{s^{*}}(\tilde{P}_{N})=\\{i_{4},\ldots,i_{t}\\}$ and
$T^{\succ_{A}}_{i_{h}}(\tilde{P}_{N})=a_{h}$ for all $h=4,\ldots,t$.

Since $I^{s^{*}}(\tilde{P}_{N})=\\{i_{4},\ldots,i_{t}\\}$ and
$T^{\succ_{A}}_{i_{h}}(\tilde{P}_{N})=a_{h}$ for all $h=4,\ldots,t$, by the
assumptions for Case 2, we have $a_{h}\in O_{s^{*}+1}(i_{h},\tilde{P}_{N})$
for all $h=1,2,3$. This implies that agents $i_{1}$, $i_{2}$, and $i_{3}$ own
the objects $a_{1}$, $a_{2}$, and $a_{3}$, respectively, at Step $s^{*}+1$ of
$T^{\succ_{A}}$ at $\tilde{P}_{N}$. Therefore $T^{\succ_{A}}$ does not satisfy
dual ownership on $\mathbb{L}^{n}(A)$, which completes the proof of the “only-
if” part of Theorem 4.2. ∎

##  Appendix C Proof of Theorem 4.3

Before we start proving Theorem 4.3, to facilitate the proof we present the
notion of dual dictatorship (Troyan, 2019).

######  Definition C.1.

On a domain $\mathcal{P}_{N}$, an FPTTC rule $T^{\succ_{A}}$ satisfies dual
dictatorship if, for all $N^{\prime}\subseteq N$ and all $A^{\prime}\subseteq
A$, we have $|\mathcal{T}(\succ_{A^{\prime}}^{N^{\prime}})|\leq 2$.

Notice that unlike dual ownership, dual dictatorship does not depend on the
choice of the domain.

###### Completion of the proof of Theorem 4.3..

Mandal and Roy (2022b) show that dual ownership and dual dictatorship are
equivalent properties of an FPTTC rule on the unrestricted domain (see Theorem
4.1 in Mandal and Roy (2022b)).212121For an arbitrary domain of preference
profiles $\mathcal{P}_{N}$, the set of FPTTC rules satisfying dual ownership
is a superset of those satisfying dual dictatorship. See Mandal and Roy
(2022b) for a detailed discussion about the relation between dual ownership
and dual dictatorship. In a setting with equal number of agents and objects,
Troyan (2019) shows that dual dictatorship and strong acyclicity are
equivalent properties of an FPTTC rule on the restricted domain
$\mathbb{L}^{n}(A)$ (see Theorem 2 in Troyan (2019)). His proof works verbatim
on the unrestricted domain $\mathbb{L}^{n}(A\cup\\{a_{0}\\})$ in our setting
(that is, with arbitrary values of the number of agents and the number of
objects), and his result still holds. Combining all these facts, we obtain
that dual ownership, dual dictatorship, and strong acyclicity are equivalent
properties of an FPTTC rule on $\mathbb{L}^{n}(A\cup\\{a_{0}\\})$. This
completes the proof of Theorem 4.3. ∎

##  Appendix D Proof of Proposition 4.2

Let $D^{\succ_{A}}$ be an OSP-implementable APDA rule on the unrestricted
domain $\mathbb{L}^{n}(A\cup\\{a_{0}\\})$. Assume for contradiction that
$\succ_{A}$ contains a weak cycle, say
$[(i_{1},i_{2},i_{3}),(a_{1},a_{2},a_{3})]$. By the definition of a weak
cycle, we have $i_{1}\succ_{a_{1}}\\{i_{2},i_{3}\\}$,
$i_{2}\succ_{a_{2}}\\{i_{1},i_{3}\\}$, and
$i_{3}\succ_{a_{3}}\\{i_{1},i_{2}\\}$.

Fix a preference $\hat{P}\in\mathbb{L}(A\cup\\{a_{0}\\})$ such that
$\tau(\hat{P})=a_{0}$. We distinguish the following cases.
Case 1: Suppose $i_{1}\succ_{a_{1}}i_{2}\succ_{a_{1}}i_{3}$ and
$i_{2}\succ_{a_{2}}i_{1}\succ_{a_{2}}i_{3}$.

Consider the domain
$\tilde{\mathcal{P}}_{N}\subseteq\mathbb{L}^{n}(A\cup\\{a_{0}\\})$ with only
four preference profiles presented (together with the outcomes of
$D^{\succ_{A}}$) in Table D.1. Here, $l$ denotes an agent (might be empty)
other than $i_{1},i_{2}$, and $i_{3}$. Note that such an agent does not change
her preference across the mentioned preference profiles.

Preference profiles | $\mbox{Agent }i_{1}$ | $\mbox{Agent }i_{2}$ | $\mbox{Agent }i_{3}$ | $\ldots$ | $\mbox{Agent }l$ | $D^{\succ_{A}}_{i_{1}}$ | $D^{\succ_{A}}_{i_{2}}$ | $D^{\succ_{A}}_{i_{3}}$
---|---|---|---|---|---|---|---|---
$\tilde{P}_{N}^{1}$ | $a_{2}a_{1}a_{3}a_{0}\ldots$ | $a_{3}a_{2}a_{1}a_{0}\ldots$ | $a_{2}a_{1}a_{3}a_{0}\ldots$ | $\ldots$ | $\hat{P}$ | $a_{2}$ | $a_{3}$ | $a_{1}$
$\tilde{P}_{N}^{2}$ | $a_{3}a_{1}a_{2}a_{0}\ldots$ | $a_{1}a_{3}a_{2}a_{0}\ldots$ | $a_{1}a_{3}a_{2}a_{0}\ldots$ | $\ldots$ | $\hat{P}$ | $a_{1}$ | $a_{2}$ | $a_{3}$
$\tilde{P}_{N}^{3}$ | $a_{3}a_{2}a_{1}a_{0}\ldots$ | $a_{1}a_{3}a_{2}a_{0}\ldots$ | $a_{2}a_{1}a_{3}a_{0}\ldots$ | $\ldots$ | $\hat{P}$ | $a_{3}$ | $a_{1}$ | $a_{2}$
$\tilde{P}_{N}^{4}$ | $a_{3}a_{2}a_{1}a_{0}\ldots$ | $a_{3}a_{2}a_{1}a_{0}\ldots$ | $a_{2}a_{3}a_{1}a_{0}\ldots$ | $\ldots$ | $\hat{P}$ | $a_{1}$ | $a_{2}$ | $a_{3}$
Table D.1: Preference profiles of $\tilde{\mathcal{P}}_{N}$ for Case 1

Since $D^{\succ_{A}}$ is OSP-implementable on
$\mathbb{L}^{n}(A\cup\\{a_{0}\\})$, it must be OSP-implementable on the domain
$\tilde{\mathcal{P}}_{N}$. Let $\tilde{G}$ be an OSP mechanism that implements
$D^{\succ_{A}}$ on $\tilde{\mathcal{P}}_{N}$.

Note that since $D^{\succ_{A}}(\tilde{P}_{N}^{1})\neq
D^{\succ_{A}}(\tilde{P}_{N}^{2})$, there exists a node in the OSP mechanism
$\tilde{G}$ that has at least two edges. Also, note that since each agent
$l\in N\setminus\\{i_{1},i_{2},i_{3}\\}$ has exactly one preference in
$\tilde{\mathcal{P}}_{l}$, whenever there are at least two outgoing edges from
a node, that node must be assigned to some agent in $\\{i_{1},i_{2},i_{3}\\}$.
Consider the first node (from the root) $v$ that has at least two edges.

  1. (i)

Suppose $\eta^{NA}(v)=i_{1}$.
By OSP-implementability, the facts $a_{2}\tilde{P}_{i_{1}}^{4}a_{1}$,
$D^{\succ_{A}}_{i_{1}}(\tilde{P}_{N}^{4})=a_{1}$, and
$D^{\succ_{A}}_{i_{1}}(\tilde{P}_{N}^{1})=a_{2}$ together imply that
$\tilde{P}_{i_{1}}^{4}$ and $\tilde{P}_{i_{1}}^{1}$ do not diverge at $v$.
Similarly, by OSP-implementability, the facts
$a_{3}\tilde{P}_{i_{1}}^{2}a_{1}$,
$D^{\succ_{A}}_{i_{1}}(\tilde{P}_{N}^{2})=a_{1}$, and
$D^{\succ_{A}}_{i_{1}}(\tilde{P}_{N}^{3})=a_{3}$ together imply that
$\tilde{P}_{i_{1}}^{2}$ and $\tilde{P}_{i_{1}}^{3}$ do not diverge at $v$.
Since $\tilde{P}_{i_{1}}^{3}=\tilde{P}_{i_{1}}^{4}$, combining all these
observations, we have a contradiction to the fact that $v$ has at least two
edges.

  2. (ii)

Suppose $\eta^{NA}(v)=i_{2}$.
By OSP-implementability, the facts $a_{3}\tilde{P}_{i_{2}}^{2}a_{2}$,
$D^{\succ_{A}}_{i_{2}}(\tilde{P}_{N}^{2})=a_{2}$, and
$D^{\succ_{A}}_{i_{2}}(\tilde{P}_{N}^{1})=a_{3}$ together imply that
$\tilde{P}_{i_{2}}^{2}$ and $\tilde{P}_{i_{2}}^{1}$ do not diverge at $v$, a
contradiction to the fact that $v$ has at least two edges.

  3. (iii)

Suppose $\eta^{NA}(v)=i_{3}$.
By OSP-implementability, the facts $a_{1}\tilde{P}_{i_{3}}^{2}a_{3}$,
$D^{\succ_{A}}_{i_{3}}(\tilde{P}_{N}^{2})=a_{3}$, and
$D^{\succ_{A}}_{i_{3}}(\tilde{P}_{N}^{1})=a_{1}$ together imply that
$\tilde{P}_{i_{3}}^{2}$ and $\tilde{P}_{i_{3}}^{1}$ do not diverge at $v$.
Similarly, by OSP-implementability, the facts
$a_{2}\tilde{P}_{i_{3}}^{4}a_{3}$,
$D^{\succ_{A}}_{i_{3}}(\tilde{P}_{N}^{4})=a_{3}$, and
$D^{\succ_{A}}_{i_{3}}(\tilde{P}_{N}^{3})=a_{2}$ together imply that
$\tilde{P}_{i_{3}}^{4}$ and $\tilde{P}_{i_{3}}^{3}$ do not diverge at $v$.
Since $\tilde{P}_{i_{3}}^{1}=\tilde{P}_{i_{3}}^{3}$, combining all these
observations, we have a contradiction to the fact that $v$ has at least two
edges.

Case 2: Suppose $i_{2}\succ_{a_{2}}i_{3}\succ_{a_{2}}i_{1}$ and
$i_{3}\succ_{a_{3}}i_{2}\succ_{a_{3}}i_{1}$.

By renaming agents $i_{1},i_{2},i_{3}$ as
$i^{\prime}_{3},i^{\prime}_{2},i^{\prime}_{1}$, respectively, and renaming
objects $a_{1},a_{2},a_{3}$ as $a^{\prime}_{3},a^{\prime}_{2},a^{\prime}_{1}$,
respectively, we obtain an identical situation to Case 1.
Case 3: Suppose $i_{1}\succ_{a_{1}}i_{3}\succ_{a_{1}}i_{2}$ and
$i_{3}\succ_{a_{3}}i_{1}\succ_{a_{3}}i_{2}$.

By renaming agents $i_{1},i_{2},i_{3}$ as
$i^{\prime}_{1},i^{\prime}_{3},i^{\prime}_{2}$, respectively, and renaming
objects $a_{1},a_{2},a_{3}$ as $a^{\prime}_{1},a^{\prime}_{3},a^{\prime}_{2}$,
respectively, we obtain an identical situation to Case 1.
Case 4: Suppose $i_{1}\succ_{a_{1}}i_{2}\succ_{a_{1}}i_{3}$,
$i_{2}\succ_{a_{2}}i_{3}\succ_{a_{2}}i_{1}$, and
$i_{3}\succ_{a_{3}}i_{1}\succ_{a_{3}}i_{2}$.

Consider the domain
$\tilde{\mathcal{P}}_{N}\subseteq\mathbb{L}^{n}(A\cup\\{a_{0}\\})$ with only
three preference profiles presented (together with the outcomes of
$D^{\succ_{A}}$) in Table D.2.

Preference profiles | $\mbox{Agent }i_{1}$ | $\mbox{Agent }i_{2}$ | $\mbox{Agent }i_{3}$ | $\ldots$ | $\mbox{Agent }l$ | $D^{\succ_{A}}_{i_{1}}$ | $D^{\succ_{A}}_{i_{2}}$ | $D^{\succ_{A}}_{i_{3}}$
---|---|---|---|---|---|---|---|---
$\tilde{P}_{N}^{1}$ | $a_{2}a_{1}a_{3}a_{0}\ldots$ | $a_{1}a_{3}a_{2}a_{0}\ldots$ | $a_{2}a_{1}a_{3}a_{0}\ldots$ | $\ldots$ | $\hat{P}$ | $a_{1}$ | $a_{3}$ | $a_{2}$
$\tilde{P}_{N}^{2}$ | $a_{3}a_{2}a_{1}a_{0}\ldots$ | $a_{1}a_{3}a_{2}a_{0}\ldots$ | $a_{1}a_{3}a_{2}a_{0}\ldots$ | $\ldots$ | $\hat{P}$ | $a_{2}$ | $a_{1}$ | $a_{3}$
$\tilde{P}_{N}^{3}$ | $a_{3}a_{2}a_{1}a_{0}\ldots$ | $a_{3}a_{2}a_{1}a_{0}\ldots$ | $a_{2}a_{1}a_{3}a_{0}\ldots$ | $\ldots$ | $\hat{P}$ | $a_{3}$ | $a_{2}$ | $a_{1}$
Table D.2: Preference profiles of $\tilde{\mathcal{P}}_{N}$ for Case 4

Since $D^{\succ_{A}}$ is OSP-implementable on
$\mathbb{L}^{n}(A\cup\\{a_{0}\\})$, it must be OSP-implementable on the domain
$\tilde{\mathcal{P}}_{N}$. Let $\tilde{G}$ be an OSP mechanism that implements
$D^{\succ_{A}}$ on $\tilde{\mathcal{P}}_{N}$.

Note that since $D^{\succ_{A}}(\tilde{P}_{N}^{1})\neq
D^{\succ_{A}}(\tilde{P}_{N}^{2})$, there exists a node in the OSP mechanism
$\tilde{G}$ that has at least two edges. Also, note that since each agent
$l\in N\setminus\\{i_{1},i_{2},i_{3}\\}$ has exactly one preference in
$\tilde{\mathcal{P}}_{l}$, whenever there are at least two outgoing edges from
a node, that node must be assigned to some agent in $\\{i_{1},i_{2},i_{3}\\}$.
Consider the first node (from the root) $v$ that has at least two edges.

  1. (i)

Suppose $\eta^{NA}(v)=i_{1}$.
By OSP-implementability, the facts $a_{2}\tilde{P}_{i_{1}}^{1}a_{1}$,
$D^{\succ_{A}}_{i_{1}}(\tilde{P}_{N}^{1})=a_{1}$, and
$D^{\succ_{A}}_{i_{1}}(\tilde{P}_{N}^{2})=a_{2}$ together imply that
$\tilde{P}_{i_{1}}^{1}$ and $\tilde{P}_{i_{1}}^{2}$ do not diverge at $v$, a
contradiction to the fact that $v$ has at least two edges.

  2. (ii)

Suppose $\eta^{NA}(v)=i_{2}$.
By OSP-implementability, the facts $a_{3}\tilde{P}_{i_{2}}^{3}a_{2}$,
$D^{\succ_{A}}_{i_{2}}(\tilde{P}_{N}^{3})=a_{2}$, and
$D^{\succ_{A}}_{i_{2}}(\tilde{P}_{N}^{1})=a_{3}$ together imply that
$\tilde{P}_{i_{2}}^{3}$ and $\tilde{P}_{i_{2}}^{1}$ do not diverge at $v$, a
contradiction to the fact that $v$ has at least two edges.

  3. (iii)

Suppose $\eta^{NA}(v)=i_{3}$.
By OSP-implementability, the facts $a_{1}\tilde{P}_{i_{3}}^{2}a_{3}$,
$D^{\succ_{A}}_{i_{3}}(\tilde{P}_{N}^{2})=a_{3}$, and
$D^{\succ_{A}}_{i_{3}}(\tilde{P}_{N}^{3})=a_{1}$ together imply that
$\tilde{P}_{i_{3}}^{2}$ and $\tilde{P}_{i_{3}}^{3}$ do not diverge at $v$, a
contradiction to the fact that $v$ has at least two edges.

Case 5: Suppose $i_{1}\succ_{a_{1}}i_{3}\succ_{a_{1}}i_{2}$,
$i_{2}\succ_{a_{2}}i_{1}\succ_{a_{2}}i_{3}$, and
$i_{3}\succ_{a_{3}}i_{2}\succ_{a_{3}}i_{1}$.

By renaming agents $i_{1},i_{2},i_{3}$ as
$i^{\prime}_{1},i^{\prime}_{3},i^{\prime}_{2}$, respectively, and renaming
objects $a_{1},a_{2},a_{3}$ as $a^{\prime}_{1},a^{\prime}_{3},a^{\prime}_{2}$,
respectively, we obtain an identical situation to Case 4.

Since Cases 1 - 5 are exhaustive, this completes the proof of Proposition 4.2.
∎

##  Appendix E Proof of Theorem 5.1

We first make a straightforward observation to facilitate the proof.

######  Observation E.1.

Suppose $|A|=2$. On the domain $\mathbb{L}^{n}(A)$, every FPTTC rule is SOSP-
implementable.

###### Completion of the proof of Theorem 5.1..

(If part) Using Observation E.1, it is straightforward to verify that every
weak serial dictatorship is SOSP-implementable on the restricted domain
$\mathbb{L}^{n}(A)$. This completes the proof of the “if” part of Theorem 5.1.
(Only-if part) Let $T^{\succ_{A}}$ be an SOSP-implementable FPTTC rule on the
restricted domain $\mathbb{L}^{n}(A)$. Since SOSP-implementability is stronger
than OSP-implementability (see Remark 2.1), by Theorem 4.1, $T^{\succ_{A}}$
satisfies dual ownership. Assume for contradiction that $T^{\succ_{A}}$ is not
a weak serial dictatorship. Since $T^{\succ_{A}}$ satisfies dual ownership but
is not a weak serial dictatorship, there exist a preference profile
$P^{\prime}_{N}\in\mathbb{L}^{n}(A)$ and a step $s^{*}$ of $T^{\succ_{A}}$ at
$P^{\prime}_{N}$ such that there are two agents $i,j$ and three objects
$a,b,c$ in the reduced market at Step $s^{*}$ with the property that agent $i$
owns the object $a$, and agent $j$ owns the objects $b$ and $c$ at Step
$s^{*}$. We distinguish the following two cases.
Case 1: Suppose $s^{*}=1$.

Consider the domain $\tilde{\mathcal{P}}_{N}\subseteq\mathbb{L}^{n}(A)$ with
only four preference profiles presented in Table E.1. Here, $l$ denotes an
agent (might be empty) other than $i$ and $j$.

Preference profiles | $\mbox{Agent }i$ | $\mbox{Agent }j$ | $\ldots$ | $\mbox{Agent }l$
---|---|---|---|---
$\tilde{P}_{N}^{1}$ | $abc\ldots$ | $acb\ldots$ | $\ldots$ | $P^{\prime}_{l}$
$\tilde{P}_{N}^{2}$ | $bac\ldots$ | $bac\ldots$ | $\ldots$ | $P^{\prime}_{l}$
$\tilde{P}_{N}^{3}$ | $bca\ldots$ | $abc\ldots$ | $\ldots$ | $P^{\prime}_{l}$
$\tilde{P}_{N}^{4}$ | $cab\ldots$ | $abc\ldots$ | $\ldots$ | $P^{\prime}_{l}$
Table E.1: Preference profiles of $\tilde{\mathcal{P}}_{N}$

In Table E.2, we present some facts regarding the outcome of $T^{\succ_{A}}$
on the domain $\tilde{\mathcal{P}}_{N}$. These facts are deduced by the
construction of $\tilde{\mathcal{P}}_{N}$ along with the assumptions for Case
1.

Preference profiles | $\mbox{Agent }i$ | $\mbox{Agent }j$ | $T^{\succ_{A}}_{i}$ | $T^{\succ_{A}}_{j}$
---|---|---|---|---
$\tilde{P}_{N}^{1}$ | $abc\ldots$ | $acb\ldots$ | $a$ | $c$
$\tilde{P}_{N}^{2}$ | $bac\ldots$ | $bac\ldots$ | $a$ | $b$
$\tilde{P}_{N}^{3}$ | $bca\ldots$ | $abc\ldots$ | $b$ | $a$
$\tilde{P}_{N}^{4}$ | $cab\ldots$ | $abc\ldots$ | $c$ | $a$
Table E.2: Partial outcome of $T^{\succ_{A}}$ on $\tilde{\mathcal{P}}_{N}$

Since $T^{\succ_{A}}$ is SOSP-implementable on $\mathbb{L}^{n}(A)$, it must be
SOSP-implementable on the domain $\tilde{\mathcal{P}}_{N}$. Let $\tilde{G}$ be
an SOSP mechanism that implements $T^{\succ_{A}}$ on
$\tilde{\mathcal{P}}_{N}$.

Note that since $T^{\succ_{A}}(\tilde{P}_{N}^{1})\neq
T^{\succ_{A}}(\tilde{P}_{N}^{2})$, there exists a node in the SOSP mechanism
$\tilde{G}$ that has at least two edges. Also, note that since each agent
$l\in N\setminus\\{i,j\\}$ has exactly one preference in
$\tilde{\mathcal{P}}_{l}$, whenever there are at least two outgoing edges from
a node, that node must be assigned to some agent in $\\{i,j\\}$. Consider the
first node (from the root) $v$ that has at least two edges.

  1. (i)

Suppose $\eta^{NA}(v)=i$.
By SOSP-implementability, the facts $b\tilde{P}_{i}^{2}a$,
$T^{\succ_{A}}_{i}(\tilde{P}_{N}^{2})=a$, and
$T^{\succ_{A}}_{i}(\tilde{P}_{N}^{3})=b$ together imply that
$\tilde{P}_{i}^{2}$ and $\tilde{P}_{i}^{3}$ do not diverge at $v$. Since
$\tilde{P}_{i}^{2}$ and $\tilde{P}_{i}^{3}$ do not diverge at $v$, by SOSP-
implementability, the facts $c\tilde{P}_{i}^{3}a$,
$T^{\succ_{A}}_{i}(\tilde{P}_{N}^{2})=a$, and
$T^{\succ_{A}}_{i}(\tilde{P}_{N}^{4})=c$ together imply that
$\tilde{P}_{i}^{3}$ and $\tilde{P}_{i}^{4}$ do not diverge at $v$. Moreover,
since $\tilde{P}_{i}^{3}$ and $\tilde{P}_{i}^{4}$ do not diverge at $v$, by
SOSP-implementability, the facts $a\tilde{P}_{i}^{4}b$,
$T^{\succ_{A}}_{i}(\tilde{P}_{N}^{1})=a$, and
$T^{\succ_{A}}_{i}(\tilde{P}_{N}^{3})=b$ together imply that
$\tilde{P}_{i}^{1}$ and $\tilde{P}_{i}^{4}$ do not diverge at $v$. Combining
all these observations, we have a contradiction to the fact that $v$ has at
least two edges.

  2. (ii)

Suppose $\eta^{NA}(v)=j$.
By SOSP-implementability, the facts $a\tilde{P}_{j}^{1}c$,
$T^{\succ_{A}}_{j}(\tilde{P}_{N}^{1})=c$, and
$T^{\succ_{A}}_{j}(\tilde{P}_{N}^{3})=a$ together imply that
$\tilde{P}_{j}^{1}$ and $\tilde{P}_{j}^{3}$ do not diverge at $v$. Since
$\tilde{P}_{j}^{1}$ and $\tilde{P}_{j}^{3}$ do not diverge at $v$, by SOSP-
implementability, the facts $b\tilde{P}_{j}^{3}c$,
$T^{\succ_{A}}_{j}(\tilde{P}_{N}^{1})=c$, and
$T^{\succ_{A}}_{j}(\tilde{P}_{N}^{2})=b$ together imply that
$\tilde{P}_{j}^{2}$ and $\tilde{P}_{j}^{3}$ do not diverge at $v$. Combining
all these observations, we have a contradiction to the fact that $v$ has at
least two edges.

Case 2: Suppose $s^{*}>1$.

Recall that $X^{s^{*}-1}(P^{\prime}_{N})$ is the set of assigned objects up to
Stage $s^{*}-1$ (including Stage $s^{*}-1$) of $T^{\succ_{A}}$ at
$P^{\prime}_{N}$. Fix a preference
$\hat{P}\in\mathbb{L}(X^{s^{*}-1}(P^{\prime}_{N}))$ over these objects.
Consider the domain $\tilde{\mathcal{P}}_{N}\subseteq\mathbb{L}^{n}(A)$ with
only four preference profiles presented in Table E.3.222222For instance,
$\hat{P}abc\ldots$ denotes a preference where objects in
$X^{s^{*}-1}(P^{\prime}_{N})$ are ranked at the top according to the
preference $\hat{P}$, objects $a$, $b$, and $c$ are ranked consecutively after
that (in that order), and the ranking of the rest of the objects is
arbitrarily.

Preference profiles | $\mbox{Agent }i$ | $\mbox{Agent }j$ | $\ldots$ | $\mbox{Agent }l$
---|---|---|---|---
$\tilde{P}_{N}^{1}$ | $\hat{P}abc\ldots$ | $\hat{P}acb\ldots$ | $\ldots$ | $P^{\prime}_{l}$
$\tilde{P}_{N}^{2}$ | $\hat{P}bac\ldots$ | $\hat{P}bac\ldots$ | $\ldots$ | $P^{\prime}_{l}$
$\tilde{P}_{N}^{3}$ | $\hat{P}bca\ldots$ | $\hat{P}abc\ldots$ | $\ldots$ | $P^{\prime}_{l}$
$\tilde{P}_{N}^{4}$ | $\hat{P}cab\ldots$ | $\hat{P}abc\ldots$ | $\ldots$ | $P^{\prime}_{l}$
Table E.3: Preference profiles of $\tilde{\mathcal{P}}_{N}$

In Table E.4, we present some facts regarding the outcome of $T^{\succ_{A}}$
on the domain $\tilde{\mathcal{P}}_{N}$ that can be deduced by the
construction of the domain $\tilde{\mathcal{P}}_{N}$ along with the
assumptions for Case 2. The verification of these facts is left to the reader.

Preference profiles | $\mbox{Agent }i$ | $\mbox{Agent }j$ | $T^{\succ_{A}}_{i}$ | $T^{\succ_{A}}_{j}$
---|---|---|---|---
$\tilde{P}_{N}^{1}$ | $\hat{P}abc\ldots$ | $\hat{P}acb\ldots$ | $a$ | $c$
$\tilde{P}_{N}^{2}$ | $\hat{P}bac\ldots$ | $\hat{P}bac\ldots$ | $a$ | $b$
$\tilde{P}_{N}^{3}$ | $\hat{P}bca\ldots$ | $\hat{P}abc\ldots$ | $b$ | $a$
$\tilde{P}_{N}^{4}$ | $\hat{P}cab\ldots$ | $\hat{P}abc\ldots$ | $c$ | $a$
Table E.4: Partial outcome of $T^{\succ_{A}}$ on $\tilde{\mathcal{P}}_{N}$

Using a similar argument as for Case 1, we get a contradiction. This completes
the proof of the “only-if” part of Theorem 5.1. ∎

##  Appendix F Proof of Theorem 5.2

The “if” part of the theorem is straightforward. We proceed to prove the
“only-if” part. To do so, we prove the contrapositive. Suppose there exist an
agent $i^{*}\in N$ and two objects $a^{*},b^{*}\in A$ such that
$rank(i^{*},\succ_{a^{*}})\leq|A|-2$ and $rank(i^{*},\succ_{a^{*}})\neq
rank(i^{*},\succ_{b^{*}})$. Without loss of generality, assume that for all
$l\in U(i^{*},\succ_{a^{*}})$, $rank(l,\succ_{a^{*}})=rank(l,\succ_{b})$ for
all $b\in A$. Let $rank(i^{*},\succ_{a^{*}})=m^{*}$ and let
$A^{\prime}\subseteq A\setminus\\{a^{*},b^{*}\\}$ be such that
$|A^{\prime}|=m^{*}-1$. Clearly, $m^{*}\leq|A|-2$. Furthermore, $A^{\prime}$
is well-defined since $m^{*}\leq|A|-2$.

Fix a preference $\hat{P}\in\mathbb{L}(A)$ such that
$A^{\prime}\hat{P}(A\setminus A^{\prime})$. Consider the preference profile
$\tilde{P}_{N}\in\mathbb{L}^{n}(A)$ such that $\tilde{P}_{i}=\hat{P}$ for all
$i\in N$. Since $rank(l,\succ_{a^{*}})=rank(l,\succ_{b})$ for all $l\in
U(i^{*},\succ_{a^{*}})$ and all $b\in A$, and
$rank(i^{*},\succ_{a^{*}})=m^{*}$, it follows from the construction of
$\tilde{P}_{N}$ that $I^{m^{*}-1}(\tilde{P}_{N})=U(i^{*},\succ_{a^{*}})$ and
$X^{m^{*}-1}(\tilde{P}_{N})=A^{\prime}$. The facts $A^{\prime}\subseteq
A\setminus\\{a^{*},b^{*}\\}$ and $X^{m^{*}-1}(\tilde{P}_{N})=A^{\prime}$
together imply $a^{*},b^{*}\in A_{m^{*}}(\tilde{P}_{N})$. Since
$I^{m^{*}-1}(\tilde{P}_{N})=U(i^{*},\succ_{a^{*}})$,
$rank(l,\succ_{a^{*}})=rank(l,\succ_{b^{*}})$ for all $l\in
U(i^{*},\succ_{a^{*}})$, $rank(i^{*},\succ_{a^{*}})\neq
rank(i^{*},\succ_{b^{*}})$, and $a^{*},b^{*}\in A_{m^{*}}(\tilde{P}_{N})$, it
follows that $|N_{m^{*}}(\tilde{P}_{N})|\geq 2$. Moreover, since
$X^{m^{*}-1}(\tilde{P}_{N})=A^{\prime}$, $|A^{\prime}|=m^{*}-1$, and
$m^{*}\leq|A|-2$, we have $|A_{m^{*}}(\tilde{P}_{N})|\geq 3$. However, the
facts $|N_{m^{*}}(\tilde{P}_{N})|\geq 2$ and $|A_{m^{*}}(\tilde{P}_{N})|\geq
3$ together imply that $T^{\succ_{A}}$ is not a weak serial dictatorship. This
completes the proof of the “only-if” part of Theorem 5.2. ∎

##  Appendix G Proof of Theorem 5.3

The “if” part of the theorem is straightforward. We proceed to prove the
“only-if” part. Let $T^{\succ_{A}}$ be an SOSP-implementable FPTTC rule on the
unrestricted domain $\mathbb{L}^{n}(A\cup\\{a_{0}\\})$. Assume for
contradiction that $T^{\succ_{A}}$ is not a serial dictatorship. Then, there
exist two agents $i,j\in N$ and two objects $a,b\in A$ such that $i\succ_{a}j$
and $j\succ_{b}i$.

Fix a preference $\hat{P}\in\mathbb{L}(A\cup\\{a_{0}\\})$ such that
$\tau(\hat{P})=a_{0}$. Consider the domain
$\tilde{\mathcal{P}}_{N}\subseteq\mathbb{L}^{n}(A\cup\\{a_{0}\\})$ with only
three preference profiles presented (together with the outcomes of
$T^{\succ_{A}}$) in Table G.1. Here, $l$ denotes an agent (might be empty)
other than $i$ and $j$.

Preference profiles | $\mbox{Agent }i$ | $\mbox{Agent }j$ | $\ldots$ | $\mbox{Agent }l$ | $T^{\succ_{A}}_{i}$ | $T^{\succ_{A}}_{j}$
---|---|---|---|---|---|---
$\tilde{P}_{N}^{1}$ | $aba_{0}\ldots$ | $aa_{0}\ldots$ | $\ldots$ | $\hat{P}$ | $a$ | $a_{0}$
$\tilde{P}_{N}^{2}$ | $ba_{0}\ldots$ | $baa_{0}\ldots$ | $\ldots$ | $\hat{P}$ | $a_{0}$ | $b$
$\tilde{P}_{N}^{3}$ | $baa_{0}\ldots$ | $aba_{0}\ldots$ | $\ldots$ | $\hat{P}$ | $b$ | $a$
Table G.1: Preference profiles of $\tilde{\mathcal{P}}_{N}$

Since $T^{\succ_{A}}$ is SOSP-implementable on
$\mathbb{L}^{n}(A\cup\\{a_{0}\\})$, it must be SOSP-implementable on the
domain $\tilde{\mathcal{P}}_{N}$. Let $\tilde{G}$ be an SOSP mechanism that
implements $T^{\succ_{A}}$ on $\tilde{\mathcal{P}}_{N}$.

Note that since $T^{\succ_{A}}(\tilde{P}_{N}^{1})\neq
T^{\succ_{A}}(\tilde{P}_{N}^{2})$, there exists a node in the SOSP mechanism
$\tilde{G}$ that has at least two edges. Also, note that since each agent
$l\in N\setminus\\{i,j\\}$ has exactly one preference in
$\tilde{\mathcal{P}}_{l}$, whenever there are at least two outgoing edges from
a node, that node must be assigned to some agent in $\\{i,j\\}$. Consider the
first node (from the root) $v$ that has at least two edges. We distinguish the
following two cases.
Case 1: Suppose $\eta^{NA}(v)=i$.

By SOSP-implementability, the facts $b\tilde{P}_{i}^{2}a_{0}$,
$T^{\succ_{A}}_{i}(\tilde{P}_{N}^{2})=a_{0}$, and
$T^{\succ_{A}}_{i}(\tilde{P}_{N}^{3})=b$ together imply that
$\tilde{P}_{i}^{2}$ and $\tilde{P}_{i}^{3}$ do not diverge at $v$. Since
$\tilde{P}_{i}^{2}$ and $\tilde{P}_{i}^{3}$ do not diverge at $v$, by SOSP-
implementability, the facts $a\tilde{P}_{i}^{3}a_{0}$,
$T^{\succ_{A}}_{i}(\tilde{P}_{N}^{2})=a_{0}$, and
$T^{\succ_{A}}_{i}(\tilde{P}_{N}^{1})=a$ together imply that
$\tilde{P}_{i}^{1}$ and $\tilde{P}_{i}^{3}$ do not diverge at $v$. Combining
all these observations, we have a contradiction to the fact that $v$ has at
least two edges.
Case 2: Suppose $\eta^{NA}(v)=j$.

By SOSP-implementability, the facts $a\tilde{P}_{j}^{1}a_{0}$,
$T^{\succ_{A}}_{j}(\tilde{P}_{N}^{1})=a_{0}$, and
$T^{\succ_{A}}_{j}(\tilde{P}_{N}^{3})=a$ together imply that
$\tilde{P}_{j}^{1}$ and $\tilde{P}_{j}^{3}$ do not diverge at $v$. Since
$\tilde{P}_{j}^{1}$ and $\tilde{P}_{j}^{3}$ do not diverge at $v$, by SOSP-
implementability, the facts $b\tilde{P}_{j}^{3}a_{0}$,
$T^{\succ_{A}}_{j}(\tilde{P}_{N}^{1})=a_{0}$, and
$T^{\succ_{A}}_{j}(\tilde{P}_{N}^{2})=b$ together imply that
$\tilde{P}_{j}^{2}$ and $\tilde{P}_{j}^{3}$ do not diverge at $v$. Combining
all these observations, we have a contradiction to the fact that $v$ has at
least two edges.

Since Cases 1 and 2 are exhaustive, this completes the proof of the “only-if”
part of Theorem 5.3. ∎

##  Appendix H Proofs of Proposition 6.1

Fix an arbitrary domain of preference profiles $\mathcal{P}_{N}$. Let $G$ be a
simple OSP mechanism on $\mathcal{P}_{N}$. Consider the assignment rule
$f^{G}$ on $\mathcal{P}_{N}$ implemented by $G$. Consider an agent $i\in N$, a
node $v$ such that $\eta^{NA}(v)=i$, and preference profiles
$P_{N},P^{\prime}_{N},\tilde{P}_{N}\in\mathcal{P}_{N}$ passing through $v$
such that (i) $P_{i}$ and $P^{\prime}_{i}$ do not diverge at $v$ and (ii)
$P_{i}$ and $\tilde{P}_{i}$ diverge at $v$. We show that
$f^{G}_{i}(P^{\prime}_{N})R_{i}f^{G}_{i}(\tilde{P}_{N})$.

Since $P_{i}$ and $P^{\prime}_{i}$ do not diverge at $v$, the fact that $G$ is
a simple mechanism implies that
$f^{G}(P^{\prime}_{N})=f^{G}(P_{i},P^{\prime}_{-i})$. This, in particular,
means

$f^{G}_{i}(P^{\prime}_{N})=f^{G}_{i}(P_{i},P^{\prime}_{-i}).$ (H.1)

The fact that both $P_{N}$ and $P^{\prime}_{N}$ pass through $v$ implies that
$(P_{i},P^{\prime}_{-i})$ passes through $v$. Consider the preference profiles
$(P_{i},P^{\prime}_{-i})$ and $\tilde{P}_{N}$. Since both of them pass through
$v$ at which $P_{i}$ and $\tilde{P}_{i}$ diverge, by obvious strategy-
proofness of $G$, we have
$f^{G}_{i}(P_{i},P^{\prime}_{-i})R_{i}f^{G}_{i}(\tilde{P}_{N})$. This,
together with (H.1), implies
$f^{G}_{i}(P^{\prime}_{N})R_{i}f^{G}_{i}(\tilde{P}_{N})$. This completes the
proof of Proposition 6.1. ∎

##  Appendix I Proof of Theorem 6.1

We first make a straightforward observation to facilitate the proof.

######  Observation I.1.

Suppose $|A|=2$. On the domain $\mathbb{L}^{n}(A)$, every FPTTC rule is simply
strategy-proof.

###### Completion of the proof of Theorem 6.1..

The “only-if” part of the theorem follows from Proposition 6.1, we proceed to
prove the “if” part. Let $T^{\succ_{A}}$ be an SOSP-implementable FPTTC rule
on $\mathcal{P}_{N}$. We distinguish the following two cases.
Case 1: Suppose $\mathcal{P}_{N}=\mathbb{L}^{n}(A)$.

From Theorem 5.1, it follows that $T^{\succ_{A}}$ is a weak serial
dictatorship. This, along with Observation I.1, implies that $T^{\succ_{A}}$
is simply strategy-proof.
Case 2: Suppose $\mathcal{P}_{N}=\mathbb{L}^{n}(A\cup\\{a_{0}\\})$.

The proof for this case is straightforward. ∎

##  Appendix J Relation between SOSP-implementability and simple strategy-
proofness beyond FPTTC rules

Example J.1 shows that not every SOSP-implementable assignment rule is simply
strategy-proof on the restricted domain $\mathbb{L}^{n}(A)$. A similar result
for the unrestricted domain $\mathbb{L}^{n}(A\cup\\{a_{0}\\})$ is shown in
Example J.2. It should be noted that the assignment rules constructed in these
two examples are not Pareto efficient.

######  Example J.1.

Consider an allocation problem with three agents $N=\\{1,2,3\\}$ and three
objects $A=\\{a_{1},a_{2},a_{3}\\}$. In Figure J.1, we provide an SOSP
mechanism $G$ on $\mathbb{L}^{3}(A)$.

pt1pt2pt$(a_{1},a_{2},a_{3})$$\cdot a_{2}\cdot
a_{3}\cdot$pt$(a_{1},a_{3},a_{2})$$\cdot a_{3}\cdot a_{2}\cdot$$\cdot
a_{1}\cdot
a_{2}\cdot$pt2pt$(a_{2},a_{1},a_{3})$$\tau(P_{2})=a_{1}$pt$(a_{1},a_{2},a_{3})$$\tau(P_{2})=a_{2}$pt1pt$(a_{2},a_{3},a_{1})$$\tau(P_{1})=a_{2}$pt$(a_{2},a_{3},a_{0})$$a_{3}a_{2}a_{1}a_{0}$$\tau(P_{2})=a_{3}$$\cdot
a_{2}\cdot a_{1}\cdot$ Figure J.1: SOSP mechanism $G$ for Example J.1

Consider the assignment rule $f^{G}$ on $\mathbb{L}^{3}(A)$ implemented by
$G$. By definition, $f^{G}$ is SOSP-implementable on $\mathbb{L}^{3}(A)$. We
argue that $f^{G}$ is not simply strategy-proof on $\mathbb{L}^{3}(A)$. To do
that, it is enough to show that $f^{G}$ is not simply strategy-proof on some
subdomain of $\mathbb{L}^{3}(A)$.

Consider the domain $\tilde{\mathcal{P}}_{N}\subseteq\mathbb{L}^{3}(A)$ with
only five preference profiles presented (together with the outcomes of
$f^{G}$) in Table J.1.

Preference profiles | $\mbox{Agent }1$ | $\mbox{Agent }2$ | $\mbox{Agent }3$ | $f^{G}_{1}$ | $f^{G}_{2}$ | $f^{G}_{3}$
---|---|---|---|---|---|---
$\tilde{P}_{N}^{1}$ | $a_{1}a_{2}a_{3}a_{0}$ | $a_{1}a_{2}a_{3}a_{0}$ | $a_{1}a_{2}a_{3}a_{0}$ | $a_{1}$ | $a_{2}$ | $a_{3}$
$\tilde{P}_{N}^{2}$ | $a_{2}a_{1}a_{3}a_{0}$ | $a_{1}a_{3}a_{2}a_{0}$ | $a_{1}a_{2}a_{3}a_{0}$ | $a_{2}$ | $a_{1}$ | $a_{3}$
$\tilde{P}_{N}^{3}$ | $a_{2}a_{1}a_{3}a_{0}$ | $a_{3}a_{1}a_{2}a_{0}$ | $a_{1}a_{2}a_{3}a_{0}$ | $a_{2}$ | $a_{3}$ | $a_{1}$
$\tilde{P}_{N}^{4}$ | $a_{3}a_{2}a_{1}a_{0}$ | $a_{2}a_{1}a_{3}a_{0}$ | $a_{1}a_{2}a_{3}a_{0}$ | $a_{1}$ | $a_{2}$ | $a_{3}$
$\tilde{P}_{N}^{5}$ | $a_{3}a_{2}a_{1}a_{0}$ | $a_{3}a_{1}a_{2}a_{0}$ | $a_{1}a_{2}a_{3}a_{0}$ | $a_{2}$ | $a_{3}$ | $a_{0}$
Table J.1: Preference profiles for Example J.1

Assume for contradiction that $f^{G}$ is simply strategy-proof on
$\tilde{\mathcal{P}}_{N}$. So, there exists a simple OSP mechanism $\tilde{G}$
that implements $f^{G}$ on $\tilde{\mathcal{P}}_{N}$. Note that since
$f^{G}(\tilde{P}_{N}^{1})\neq f^{G}(\tilde{P}_{N}^{2})$, there exists a node
in the simple OSP mechanism $\tilde{G}$ that has at least two edges. Also,
note that since agent 3 has exactly one preference in
$\tilde{\mathcal{P}}_{3}$, whenever there are at least two outgoing edges from
a node, the node must be assigned either to agent 1 or to agent 2. Consider
the first node (from the root) $v$ that has at least two edges. We distinguish
the following two cases.

  1. (i)

Suppose $\eta^{NA}(v)=1$.
By obvious strategy-proofness of $\tilde{G}$, the facts
$a_{2}\tilde{P}_{1}^{4}a_{1}$, $f^{G}_{1}(\tilde{P}_{N}^{4})=a_{1}$, and
$f^{G}_{1}(\tilde{P}_{N}^{3})=a_{2}$ together imply that $\tilde{P}_{1}^{3}$
and $\tilde{P}_{1}^{4}$ do not diverge at $v$. This, together with the facts
that $\tilde{P}_{1}^{4}=\tilde{P}_{1}^{5}$,
$\tilde{P}_{2}^{3}=\tilde{P}_{2}^{5}$, and $f^{G}(\tilde{P}_{N}^{3})\neq
f^{G}(\tilde{P}_{N}^{5})$, implies that there exists a node $v^{\prime}$ at
which $\tilde{P}_{1}^{3}$ and $\tilde{P}_{1}^{4}$ diverge. Clearly, $v$ and
$v^{\prime}$ are distinct nodes appearing in the same path such that
$\eta^{NA}(v)=\eta^{NA}(v^{\prime})=1$. This contradicts the fact that
$\tilde{G}$ is a simple mechanism.

  2. (ii)

Suppose $\eta^{NA}(v)=2$.
First note that since $\tilde{G}$ is a simple OSP mechanism on
$\tilde{\mathcal{P}}_{N}$, by Proposition 6.1, $\tilde{G}$ is SOSP on
$\tilde{\mathcal{P}}_{N}$. By obvious strategy-proofness of $\tilde{G}$, the
facts $a_{1}\tilde{P}_{2}^{1}a_{2}$, $f^{G}_{2}(\tilde{P}_{N}^{1})=a_{2}$, and
$f^{G}_{2}(\tilde{P}_{N}^{2})=a_{1}$ together imply that $\tilde{P}_{2}^{1}$
and $\tilde{P}_{2}^{2}$ do not diverge at $v$. Since $\tilde{P}_{2}^{1}$ and
$\tilde{P}_{2}^{2}$ do not diverge at $v$, by strongly obvious strategy-
proofness of $\tilde{G}$, the facts $a_{3}\tilde{P}_{2}^{2}a_{2}$,
$f^{G}_{2}(\tilde{P}_{N}^{1})=a_{2}$, and $f^{G}_{2}(\tilde{P}_{N}^{3})=a_{3}$
together imply that $\tilde{P}_{2}^{2}$ and $\tilde{P}_{2}^{3}$ do not diverge
at $v$. This, together with the facts that
$\tilde{P}_{1}^{2}=\tilde{P}_{1}^{3}$ and $f^{G}(\tilde{P}_{N}^{2})\neq
f^{G}(\tilde{P}_{N}^{3})$, implies that there exists a node $v^{\prime}$ at
which $\tilde{P}_{2}^{2}$ and $\tilde{P}_{2}^{3}$ diverge. Clearly, $v$ and
$v^{\prime}$ are distinct nodes appearing in the same path such that
$\eta^{NA}(v)=\eta^{NA}(v^{\prime})=2$. This contradicts the fact that
$\tilde{G}$ is a simple mechanism.

Since Cases i and ii are exhaustive, it follows that $f^{G}$ is not simply
strategy-proof on $\tilde{\mathcal{P}}_{N}$. $\Diamond$

######  Example J.2.

Consider an allocation problem with three agents $N=\\{1,2,3\\}$ and three
objects $A=\\{a_{1},a_{2},a_{3}\\}$. In Figure J.2, we provide an SOSP
mechanism $G$ on $\mathbb{L}^{3}(A\cup\\{a_{0}\\})$. We use the following
notation in Figure J.2: by $\cdot a_{1}\cdot\\{a_{2},a_{3}\\}\cdot$, we denote
the set of preferences where $a_{1}$ is preferred to both $a_{2}$ and $a_{3}$.

pt1pt2pt$(a_{0},a_{0},a_{0})$$\cdot a_{0}\cdot
a_{2}\cdot$pt$(a_{0},a_{2},a_{0})$$\cdot a_{2}\cdot a_{0}\cdot$$\cdot
a_{0}\cdot a_{1}\cdot$pt2pt$(a_{1},a_{0},a_{0})$$\cdot
a_{0}\cdot\\{a_{1},a_{2}\\}\cdot$pt$(a_{0},a_{1},a_{0})$$\cdot
a_{1}\cdot\\{a_{0},a_{2}\\}\cdot$pt3pt1pt$(a_{1},a_{2},a_{3})$$\cdot
a_{3}\cdot a_{0}\cdot$pt$(a_{1},a_{2},a_{0})$$\cdot a_{0}\cdot
a_{3}\cdot$$\cdot a_{3}\cdot a_{0}\cdot$pt$(a_{1},a_{2},a_{0})$$\cdot
a_{0}\cdot a_{3}\cdot$$\cdot a_{2}\cdot\\{a_{0},a_{1}\\}\cdot$$\cdot
a_{1}\cdot a_{0}\cdot$ Figure J.2: SOSP mechanism $G$ for Example J.2

Consider the assignment rule $f^{G}$ on $\mathbb{L}^{3}(A\cup\\{a_{0}\\})$
implemented by $G$. By definition, $f^{G}$ is SOSP-implementable on
$\mathbb{L}^{3}(A\cup\\{a_{0}\\})$. We argue that $f^{G}$ is not simply
strategy-proof on $\mathbb{L}^{3}(A\cup\\{a_{0}\\})$. To do that, it is enough
to show that $f^{G}$ is not simply strategy-proof on some subdomain of
$\mathbb{L}^{3}(A\cup\\{a_{0}\\})$.

Consider the domain
$\tilde{\mathcal{P}}_{N}\subseteq\mathbb{L}^{3}(A\cup\\{a_{0}\\})$ with only
five preference profiles presented (together with the outcomes of $f^{G}$) in
Table J.2.

Preference profiles | $\mbox{Agent }1$ | $\mbox{Agent }2$ | $\mbox{Agent }3$ | $f^{G}_{1}$ | $f^{G}_{2}$ | $f^{G}_{3}$
---|---|---|---|---|---|---
$\tilde{P}_{N}^{1}$ | $a_{0}a_{1}a_{2}a_{3}$ | $a_{1}a_{0}a_{2}a_{3}$ | $a_{3}a_{2}a_{1}a_{0}$ | $a_{0}$ | $a_{0}$ | $a_{0}$
$\tilde{P}_{N}^{2}$ | $a_{1}a_{3}a_{0}a_{2}$ | $a_{1}a_{2}a_{0}a_{3}$ | $a_{3}a_{2}a_{1}a_{0}$ | $a_{0}$ | $a_{1}$ | $a_{0}$
$\tilde{P}_{N}^{3}$ | $a_{1}a_{3}a_{0}a_{2}$ | $a_{2}a_{0}a_{1}a_{3}$ | $a_{3}a_{2}a_{1}a_{0}$ | $a_{1}$ | $a_{2}$ | $a_{3}$
$\tilde{P}_{N}^{4}$ | $a_{2}a_{1}a_{0}a_{3}$ | $a_{1}a_{0}a_{2}a_{3}$ | $a_{3}a_{2}a_{1}a_{0}$ | $a_{0}$ | $a_{1}$ | $a_{0}$
$\tilde{P}_{N}^{5}$ | $a_{2}a_{1}a_{0}a_{3}$ | $a_{2}a_{0}a_{1}a_{3}$ | $a_{3}a_{2}a_{1}a_{0}$ | $a_{1}$ | $a_{2}$ | $a_{0}$
Table J.2: Preference profiles for Example J.2

Using a similar argument as for Example J.1, it follows from Table J.2 that
$f^{G}$ is not simply strategy-proof on $\tilde{\mathcal{P}}_{N}$. $\Diamond$

## References

  * Ashlagi and Gonczarowski (2018) Itai Ashlagi and Yannai A Gonczarowski.  Stable matching mechanisms are not obviously strategy-proof.  _Journal of Economic Theory_ , 177:405–425, 2018.
  * Bade and Gonczarowski (2017) Sophie Bade and Yannai A. Gonczarowski.  Gibbard-satterthwaite success stories and obvious strategyproofness.  _arXiv preprint arXiv:1610.04873_ , 2017.
  * Chen and Sönmez (2006) Yan Chen and Tayfun Sönmez.  School choice: an experimental study.  _Journal of Economic theory_ , 127(1):202–231, 2006.
  * Ehlers and Klaus (2004) Lars Ehlers and Bettina Klaus.  Resource-monotonicity for house allocation problems.  _International Journal of Game Theory_ , 32(4):545–560, 2004.
  * Ehlers et al. (2002) Lars Ehlers, Bettina Klaus, and Szilvia Pápai.  Strategy-proofness and population-monotonicity for house allocation problems.  _Journal of Mathematical Economics_ , 38(3):329–339, 2002.
  * Ergin (2002) Haluk I Ergin.  Efficient resource allocation on the basis of priorities.  _Econometrica_ , 70(6):2489–2497, 2002.
  * Gale and Shapley (1962) David Gale and Lloyd S Shapley.  College admissions and the stability of marriage.  _The American Mathematical Monthly_ , 69(1):9–15, 1962.
  * Hassidim et al. (2017) Avinatan Hassidim, Déborah Marciano, Assaf Romm, and Ran I Shorrer.  The mechanism is truthful, why aren’t you?  _American Economic Review_ , 107(5):220–24, 2017\.
  * Hassidim et al. (2018) Avinatan Hassidim, Assaf Romm, and Ran I Shorrer.  ’strategic’ behavior in a strategy-proof environment.  _Available at SSRN 2784659_ , 2018.
  * Kesten (2006) Onur Kesten.  On two competing mechanisms for priority-based allocation problems.  _Journal of Economic Theory_ , 127(1):155–171, 2006.
  * Li (2017) Shengwu Li.  Obviously strategy-proof mechanisms.  _American Economic Review_ , 107(11):3257–87, 2017.
  * Mandal and Roy (2022a) Pinaki Mandal and Souvik Roy.  Obviously strategy-proof implementation of assignment rules: A new characterization.  _International Economic Review_ , 63(1):261–290, 2022a.
  * Mandal and Roy (2022b) Pinaki Mandal and Souvik Roy.  On obviously strategy-proof implementation of fixed priority top trading cycles with outside options.  _Economics Letters_ , 211:110239, 2022b.
  * Pápai (2000) Szilvia Pápai.  Strategyproof assignment by hierarchical exchange.  _Econometrica_ , 68(6):1403–1433, 2000.
  * Pathak (2017) Parag A Pathak.  What really matters in designing school choice mechanisms.  _Advances in Economics and Econometrics_ , 1:176–214, 2017\.
  * Pycia and Troyan (2019) Marek Pycia and Peter Troyan.  A theory of simplicity in games and mechanism design.  _Available at SSRN 2853563_ , 2019.
  * Pycia and Ünver (2017) Marek Pycia and M Utku Ünver.  Incentive compatible allocation and exchange of discrete resources.  _Theoretical Economics_ , 12(1):287–329, 2017\.
  * Rees-Jones (2018) Alex Rees-Jones.  Suboptimal behavior in strategy-proof mechanisms: Evidence from the residency match.  _Games and Economic Behavior_ , 108:317–330, 2018.
  * Satterthwaite and Sonnenschein (1981) Mark A Satterthwaite and Hugo Sonnenschein.  Strategy-proof allocation mechanisms at differentiable points.  _The Review of Economic Studies_ , 48(4):587–597, 1981.
  * Shapley and Scarf (1974) Lloyd Shapley and Herbert Scarf.  On cores and indivisibility.  _Journal of mathematical economics_ , 1(1):23–37, 1974.
  * Shorrer and Sóvágó (2018) Ran I Shorrer and Sándor Sóvágó.  Obvious mistakes in a strategically simple college admissions environment: Causes and consequences.  _Available at SSRN 2993538_ , 2018.
  * Thomas (2020) Clayton Thomas.  Classification of priorities such that deferred acceptance is obviously strategyproof.  _arXiv preprint arXiv:2011.12367_ , 2020.
  * Troyan (2019) Peter Troyan.  Obviously strategy-proof implementation of top trading cycles.  _International Economic Review_ , 60(3):1249–1261, 2019.