DP2023-14

Endowments-swapping-proofness andEﬀiciency in Multiple-Type Housing
Markets*

RIEB Junior Research Fellow

Di FENG

June 22, 2023
* This Discussion Paper won the Kanematsu Prize (FY 2022).

Endowments-swapping-proofness and Eﬀiciency inMultiple-Type Housing Markets∗
Di Feng†June 22, 2023

Abstract
For Shapley-Scarf housing markets (Shapley and Scarf, 1974), Fujinaka and Wakayama(2018) propose a new incentive property, endowments-swapping-proofness, that excludes
manipulations that a pair of agents can conduct before the operation of the selected mechanism by swapping their endowments. We investigate endowments-swapping-proofness for
Moulin (1995)’s multiple-type housing markets, which are an extension of Shapley-Scarf
housing markets with multi-unit demands. Differing from Shapley-Scarf housing markets,for multiple-type housing markets, there are various ways to swap endowments. Motivatedby this observation, we introduce three extensions of endowments-swapping-proofness:
bundle endowments-swapping-proofness, one type endowments-swapping-proofness, andflexible endowments-swapping-proofness.
Based on the first two weaker endowments-swapping-proofness properties that we propose, and other well-studied properties (individual rationality, strategy-proofness, andnon-bossiness), on several domains of preference profiles, we provide characterizationsof two extensions of the top-trading-cycles (TTC) mechanism: the bundle top-tradingcycles (bTTC) mechanism and the coordinatewise top-trading-cycles (cTTC) mechanism.
Moreover, we also show that the strongest possible endowments-swapping-proofness property (flexible endowments-swapping-proofness) leads to an impossibility. Furthermore, ourresults explicitly show that our new properties correspond to eﬀiciency notions.
Keywords: multiple-type housing markets; endowments-swapping-proofness; strategyproofness; constrained eﬀiciency; top-trading-cycles (TTC) mechanism; market design.
JEL codes: C78; D61; D47.
∗

This paper was awarded the Kanematsu Prize from the Research Institute for Economics and Business
Administration, Kobe University, in 2022. I thank the review team of the Kanematsu Prize for their valuablecomments.
†
Faculty of Business and Economics, University of Lausanne, 1015 Lausanne, Switzerland; e-mail:di.feng@unil.ch1

1 Introduction
Assignments of scarce resources are attracting a lot of attention in mechanism design and market design.1 Many studies, both theoretical and empirical, focus on indivisible resources, e.g.,
in auctions (Myerson, 1981; Hortaçsu and McAdams, 2010), school choice (Abdulkadiroğlu andSönmez, 2003; Kapor et al., 2020), and medical resource allocation (Pathak et al., 2021). Existing literature has often investigated such indivisible resource allocation problems with “unitdemand”. Additionally, when monetary transfers are not allowed, many studies focus on theso-called housing market model (Shapley and Scarf, 1974). This model is an exchange economy
in which each agent owns an indivisible object (say, a house); each agent has preferences overhouses and wishes to consume exactly one house. When preferences are strict, Shapley and Scarf(1974) show that the strict core (defined by a weak blocking notion) has remarkable features: it
is non-empty,2 and can be easily calculated by the so-called top-trading-cycles (TTC) algorithm(due to David Gale). Moreover, the TTC mechanism that assigns the unique strict core allocation satisfies important incentive properties, strategy-proofness (Roth, 1982) and even group
strategy-proofness (Bird, 1984). Furthermore, Ma (1994) and Svensson (1999) show that the
TTC mechanism is the unique mechanism satisfying Pareto eﬀiciency, individual rationality,
and strategy-proofness.
Although in some important cases (e.g., kidney exchange, school choice, etc.), “unit-demand”
is an appropriate assumption, in many other cases, agents may wish to receive more than one
object, and indeed, many studies have analyzed such situations, e.g., Pápai (2001, 2007), Manjunath and Westkamp (2021), Biró et al. (2022a,b), and Echenique et al. (2022). However, it
is known to be very diﬀicult to extend the results from unit-demand indivisible resource allocation problems to multi-unit demands. In this paper, we consider an extension of the classical
Shapley-Scarf housing markets by allowing multi-unit demands: multiple-type housing markets,
to use the language of Moulin (1995).3 In this model, objects are of different types (say, houses,
cars, etc.) and agents initially own and wish to consume exactly one object of each type.
We believe that the analysis of multiple-type housing markets is relevant for three reasons.
First, from a theoretical point of view, this is a simple extension of Shapley-Scarf housing
markets with multi-unit demands. Therefore, the analysis of multiple-type housing markets, asa benchmark or stepping stone, is potentially useful for addressing issues for other multi-unit
demand models, such as Pápai (2007) and Anno and Kurino (2016). Second, for multiple-type
housing markets, agents are “balanced” in the sense that all agents have the same numbers
and types of endowments and demands. This balanced structure provides some tractability
and hence some hope for positive results.4 Third, similar to Shapley-Scarf housing markets,
1

See the Nobel prize lectures in economic sciences in 2012 and 2020 for examples.
Roth and Postlewaite (1977) show that the strict core is single-valued.
3
In Echenique et al. (2022), multiple-type housing markets are called categorical economies.
4
We provide a discussion to compare a more general model with ours in Subsection 6.3.
22

multiple-type housing markets are applicable to many problems in reality: a familiar example
for most readers would be students’ enrollments at many universities where courses are taught insmall groups and in multiple sessions (Klaus, 2008). Additionally, for term paper presentations
during a course, students may want to exchange their assigned topics and dates (Mackin and Xia,
2016); hospitals may want to improve their surgery schedules for surgeons by swapping surgery
staff, operating rooms, and dates (Huh et al., 2013); and in shift-reallocation, people may wantto switch their shifts for personal reasons (Manjunath and Westkamp, 2021). Furthermore,
nowadays several types of resources can be allocated together due to technological development,e.g., cloud computing (Ghodsi et al., 2011, 2012) and 5G network slicing (Peng et al., 2015; Baget al., 2019; Han et al., 2019). Such situations can also be modeled as multiple-type housing
markets. Thus, the analysis of multiple-type housing markets may also impact the real world.
Despite their importance and generality, there is little research on multiple-type housing
markets. One main reason for this is that for multiple-type housing markets, even with additively
separable preferences, the strict core may be empty, and there is no mechanism satisfying Pareto
eﬀiciency, individual rationality, and strategy-proofness (Konishi et al., 2001).
One could conjecture that for multiple-type housing markets, some extensions of the TTC
mechanism are still desirable, even if they cannot satisfy all of the desirable properties above.
For instance, when preferences are strict, one extension, the bundle TTC (bTTC) mechanism
is group strategy-proof (Feng et al., 2022b). When preferences are also separable, the coordinatewise TTC (cTTC) mechanism, is coalitional proof (Wako, 2005),5 and second-best incentive compatible (Klaus, 2008).6 When preferences are also lexicographic,7 the multi-type TTC(mTTC) mechanism, always assigns a strict core allocation (Sikdar et al., 2017).
However, the works above also lead to a new challenge: to distinguish different extensionsof the TTC mechanism from a normative point of view. More precisely, how can we make acompelling argument for one extension over another? The goal of this paper is to shed lighton desirable properties of different TTC extensions and, in particular, to distinguish between
bTTC and cTTC mentioned above.8
5Feng et al. (2022a) refer to this property as effective group strategy-proofness.
A mechanism is second-best incentive compatible if it is not Pareto dominated by another strategy-proof
mechanism.
7
When preferences are lexicographic, the strict core is non-empty.
8
In this paper, we only focus on strategy-proof mechanisms, Thus we do not consider the mTTC mechanism
as it is not strategy-proof.
63

2 Our contributions
For Shapley-Scarf housing markets, Fujinaka and Wakayama (2018) propose a new incentive
property, endowments-swapping-proofness,9 that excludes manipulations that a pair of agentscan conduct before the operation of the selected mechanism by swapping their endowments.10
They also show that the TTC mechanism is the only mechanism satisfying individual rationality,
strategy-proofness and endowments-swapping-proofness.
Inspired by Fujinaka and Wakayama (2018), we also investigate this property for multipletype housing markets. However, differing from Shapley-Scarf housing markets, for multipletype housing markets, agents can swap their endowments in various ways. For instance, theycan: swap their endowments completely; swap only one type of endowments; swap more thanone (but not all) types of endowments. Motivated by this observation, we introduce three extensions of endowments-swapping-proofness: bundle endowments-swapping-proofness, one typeendowments-swapping-proofness, and flexible endowments-swapping-proofness. Note that ourconcern with ex-ante swapping is also of interest in real life, e.g., it help us to rule out somecollusion that is outside the designer’s control.
We make four contributions to the literature. Our first and most direct contribution is axiomatic.11 Based on two of our new properties (bundle endowments-swapping-proofness and one
type endowments-swapping-proofness), together with other well-studied properties (individual
rationality, strategy-proofness, and non-bossiness), we provide characterizations of bTTC andcTTC on several domains of preference profiles. Such characterizations help us to find the difference between these two mechanisms. Also, our characterization results help us to verify thetrade-off between desirable properties, e.g., the (in)compatibility between incentive properties
and eﬀiciency properties.
Additionally, based on our other new property, flexible endowments-swapping-proofness, we
discuss the cost of adding strategy-proofness for multiple-type housing markets by providing several impossibility results. Our findings suggest that it could even be diﬀicult to find a reasonablestability notion (stronger than individual rationality), that is compatible with strategy-proofness.
Moreover, it is worth noting that on the full domain of strict preference profiles, i.e., when
agents’ preferences are strict but otherwise unrestricted, our characterizations of bTTC consti9

Gale (1974) first proposes the notion of the ex-ante manipulation via endowments. Moulin (1995) proposes
endowments-swapping-proofness in Shapley-Scarf housing markets, but Fujinaka and Wakayama (2018) formallydefine and study it.
10
Apart from Fujinaka and Wakayama (2018), there are many studies that have also examined ex-ante manipulation via endowments in different settings, e.g., Postlewaite (1979); Atlamaz and Klaus (2007) in exchange
economics, Sertel (1994) in public good economies, and Sertel and Özkal-Sanver (2002); Fiestras-Janeiro et al.
(2004) in two-sided matching problems.
11
An axiomatic study often identifies a particular mechanism as the only one satisfying a class of normative
properties. For the meaningfulness of the axiomatic studies, see the discussion in Thomson (2001).

4

tute the first characterizations of an extension of the prominent TTC mechanism to multiple-type
housing markets. The analysis on the domain of strict preference profiles is demanding, because
it allows agents’ preferences to be “complementary”. Thus, our results also contribute to the literature on allocation problems with complements, e.g., Sun and Yang (2006), Rostek and Yoder(2020), and Jagadeesan and Teytelboym (2021).
Finally, the standard proof methods for Shapley-Scarf housing markets cannot be generalized
to our higher dimensional model. Hence, we need to develop a different approach. In particular,
similar to Feng et al. (2022a), we use a novel proof strategy to build results for lexicographic
preferences and a method to extend the results from lexicographic preferences to separable
preferences and strict preferences. Our extension method is potentially useful for addressing
issues in markets other than multiple-type housing markets. Therefore, methodologically, weview our new approach as a separate contribution.

3 Organization
Our paper is organized as follows. In the following section, Section 4, we introduce multiple-type
housing markets, mechanisms and their properties, and two extensions of the TTC mechanism,
bTTC and cTTC.
We state our results in Section 5.
• In Subsection 5.1, we show several impossibility results related to flexible endowmentsswapping-proofness (Theorems 1 and 2).
• In Subsection 5.2, we show that for lexicographic preferences, separable preferences, andstrict preferences, a mechanism is individually rational, strategy-proof, non-bossy, andbundle endowments-swapping-proof if and only if it is bTTC (Theorems 3, 4, and 5).
• In Subsection 5.3, we show that for lexicographic preferences and separable preferences,a mechanism is individually rational, strategy-proof, and one type endowments-swappingproof if and only if it is cTTC (Theorems 6 and 7), and on the domain of strict preference
profiles, these three properties are incompatible (Theorem 8).
• Moreover, in Subsection 5.4, by providing two characterization results (Theorems 9 and
10), we discuss the relation between our new incentive properties and eﬀiciency properties.
In Section 6, we conclude with a discussion of our results and how they relate to the literature.
In Appendix A, we provide the proofs of our results that are not included in the main text. In
Appendix B, we provide several examples to establish the logical independence of the properties
in our characterization results.

5

4 Preliminaries
The basic model setup is similar to Feng and Klaus (2022).

4.1

Multiple-type housing markets

We consider a barter economy without monetary transfers formed by n agents and n × m
indivisible objects. Let N = {1, . . . , n} be a finite set of agents. A nonempty subset of agents
S ⊆ N is a coalition. We assume that there exist m ≥ 1 (distinct) types of indivisible objects
and n (distinct) indivisible objects of each type. We denote the set of types by T = {1, ..., m}.
For each t ∈ T , the set of type-t objects is Ot = {o1t , ..., otn }, and the set of all objects is
O = {o11 , o21 , . . . , o1n , o2n , . . . , omn }. In particular, |O| = n × m. Each agent i ∈ N initially owns
exactly one object of each type t ∈ T , denoted by eti . Hence, each agent i’s endowment is a list
ei = (e1i , . . . , emi ). Moreover, each agent i ∈ N exactly wishes to consume one object of each
type, and hence, each agent i’s (feasible) consumption set is Πt∈T Ot . An element in Πt∈T Ot
is a (consumption) bundle. Note that for m = 1, our model equals the classical Shapley-Scarf
housing market model (Shapley and Scarf, 1974).
An allocation x partitions the set of all objects O into n bundles to agents. Formally,x = {x1 , . . . , xn } is such that for each t ∈ T , ∪i∈N xti = Ot and for each pair i ̸= j, xti ̸= xtj . The
set of all allocations is denoted by X, and the endowment allocation is denoted by e. Given an
allocation x ∈ X, for each agent i ∈ N , we say that xi is agent i’s allotment (at x) and for eachtype t ∈ T , xti is i’s type-t allotment. For simplicity, sometimes we will restate an allocation as
a list x = (x1 , . . . , xn ) ∈ (Πt∈T Ot )N . Given x, we define x−i = (x1 , . . . , xi−1 , xi+1 , . . . , xn ) to be
the list of all agents’ allotments, except for agent i’s allotment; and xS = (xi )i∈S to be the listof allotments of members in coalition S.
First, we assume that each agent i has complete, antisymmetric, and transitive preferences Ri
over all bundles (allotments), i.e., Ri is a linear order over Πt∈T Ot .12 For two allotments xi andyi , xi is weakly better than yi if xi Ri yi , and xi is strictly better than yi if [xi Ri yi and not yi Ri xi ],denoted xi Pi yi . Finally, since preferences over allotments are strict, xi is indifferent to yi only
if xi = yi . We denote preferences as ordered lists, e.g., Ri : xi , yi , zi instead of xi Pi yi Pi zi . The
set of all preferences is denoted by R, which we will also refer to as the strict preference domain.
Furthermore, we assume that when facing an allocation x, there are no consumption externalities and each agent i ∈ N only cares about his own allotment xi . Hence, each agent
i’s preferences over allocations X are essentially equivalent to his preferences over allotments
Πt∈T Ot . With some abuse of notation, we use notation Ri to denote an agent i’s preferences
12

Preferences Ri are complete if for any two allotments xi , yi , xi Ri yi or yi Ri xi ; they are antisymmetric if
xi Ri yi and yi Ri xi imply xi = yi ; and they are transitive if for any three allotments xi , yi , zi , xi Ri yi and yi Ri zi
imply xi Ri zi .

6over allotments as well as his preferences over allocations, i.e., for each agent i ∈ N and for any
two allocations x, y ∈ X, x Ri y if and only if xi Ri yi .13
A preference profile specifies preferences for all agents and is denoted by a list R =(R1 , . . . , Rn ) ∈ RN . We use the standard notation R−i = (R1 , . . . , Ri−1 , Ri+1 , . . . , Rn ) to denote the list of all agents’ preferences, except for agent i’s preferences. Furthermore, for eachcoalition S we define RS = (Ri )i∈S and R−S = (Ri )i∈N \S to be the lists of preferences of themembers in coalitions S and N \ S, respectively.
In addition to the domain of strict preferences, we consider several preference subdomains
based on agents’ “marginal preferences”: assume that for each i ∈ N and for each type t ∈ T ,agent i has complete, antisymmetric, and transitive preferences Rit over the set of type-t objects
Ot . We refer to Rit as agent i’s type-t marginal preferences, and denote by Rt the set of all type-t
marginal preferences. Then, we can define the following two preference domains.
(Strictly) Separable preferences. Agent i’s preferences Ri ∈ R are separable if for eacht ∈ T there exist type-t marginal preferences Rit ∈ Rt such that for any two allotments xi andyi ,if for all t ∈ T, xti Rit yit , then xi Ri yi .
Rs denotes the domain of separable preferences.
We use the standard notation Rt = (R1t , . . . , Rnt ) to denote the list of all agents’ marginal
preferences of type-t, and R−t = (R1 , . . . , Rt−1 , Rt+1 , . . . , Rm ) to denote the list of all agents’marginal preferences of all types except for type-t.
Before defining our next preference domain, we introduce some notation. We use a bijectivefunction πi : T → T to order types according to agent i’s “(subjective) importance,” with πi (1)being the most important and πi (m) being the least important object type. We denote πi as anordered list of types, e.g., by πi = (2, 3, 1), we mean that πi (1) = 2, πi (2) = 3, and πi (3) = 1.
π (m)πi (1)
πi, . . . , xi i ) we
So for each agent i ∈ N and each allotment xi = (x1i , . . . , xmi ), by xi = (xidenote the allotment after rearranging it with respect to the object-type importance order πi .
(Separably) Lexicographic preferences. Agent i’s preferences Ri ∈ R are (separably) lexicographic if they are separable with type-t marginal preferences (Rit )t∈T and there exists anobject-type importance order πi : T → T such that for any two allotments xi and yi ,π (1)π (1) π (1)if xi i Pi i yi iorif there exists a positive integer k ≤ m − 1 such that
π (1)

xi i

π (1)

π (k)

= yi i , . . . , x i i

π (k)= yi iπ (k+1), and xi i

π (k+1) πi (k+1)
yi
,

Pi i

then xi Pi yi .
13

Note that when extending strict preferences over allotments to preferences over allocations without consumption externalities, strictness is lost because any two allocations where an agent gets the same allotment are
indifferent to that agent.

7

Rl denotes the domain of lexicographic preferences.
Note that Ri ∈ Rl can be restated as a m + 1-tuple Ri = (Ri1 , . . . , Rim , πi ) = ((Rit )t∈T , πi ), orπ(1)a strict ordering of all objects,14 i.e., Ri lists first all π(1) objects (according to Ri ), then allπ(2)π(2) objects (according to Ri ), and so on. We provide a simple illustration in Example 1.
Note that when |T | = m > 1,
Rl ⊊ Rs ⊊ R.
A (multiple-type housing) market is a triple (N, e, R); as the set of agents N remains fixed
throughout, we will simply denote the market (N, e, R) by a pair (e, R). Let M be the set of all
markets with strict preferences, i.e., for each (e, R) ∈ M, R ∈ RN . Similarly, let Ms / Ml be
the set of all markets with separable preferences / lexicographic preferences.
Remark 1 (Lexicographic preferences).
There are several examples of markets with lexicographic preferences. Each professor at auniversity may initially have a course to teach per semester, and some professors may preferto exchange their assigned courses. Professors may have expertise for certain courses and solexicographically prefer some to others. For instance, the administrative oﬀice determines theclass schedule for four courses, “microeconomics” and “mathematical economics” in fall, and“macroeconomics” and “econometrics” in spring. A professor who is a game theorist prefers toteach in fall and a professor who focuses on empirical asset pricing prefers to teach in spring.
Similarly, students at a university wish to reschedule their courses by exchanging their assigned
slots, and students may strongly prefer certain timings, e.g., a party boy does not like to attend
the class on Friday.
Moreover, from a theoretical point of view, the domain of lexicographic preference profiles isa good starting point for our analysis. First, this domain is well-studied in the literature, e.g.,
Altuntaş et al. (2021) and Biró et al. (2022b). Thus, it is easy to compare our results with otherstudies on the domain of lexicographic preference profiles. Second, it is well-known that (i) for
Shapley-Scarf housing markets, the top trading cycle (TTC) mechanism coincides with the strict
core-stable mechanism; and (ii) for multiple-type housing markets with lexicographic preferences,
the strict core is non-empty. Thus, starting from the lexicographic preference domain can help us
to understand the difference between strict core-stable mechanisms and the extensions of TTC
mechanisms for multiple-type housing markets.
⋄

4.2

Mechanisms and their properties

Note that all following definitions for the set of markets with strict preferences (M) can alternatively be formulated for markets with separable preferences (Ms ) or with lexicographic
14

See Feng and Klaus (2022, Remark 1) for details.

8preferences (Ml ).
A mechanism is a function f : M → X that assigns to each market (e, R) an allocationf (e, R) ∈ X, and• for each i ∈ N , fi (e, R) denotes agent i’s allotment• for each i ∈ N and each t ∈ T , fit (e, R) denotes agent i’s type-t allotment
under mechanism f at (e, R).
We next introduce and discuss some well-known properties for allocations and mechanisms.
Let (e, R) ∈ M.
Welfare lower bounds
First we consider a voluntary participation condition for an allocation x to be implementablewithout causing agents any harm: no agent will be worse off than at his endowment.
Definition (Individual rationality).
An allocation x ∈ X is individually rational if for each agent i ∈ N , xi Ri oi . A mechanism isindividually rational if for each market, it assigns an individually rational allocation.
Eﬀiciency notions
Next, we consider two well-known eﬀiciency criteria.
Definition (Pareto eﬀiciency).
An allocation y ∈ X Pareto dominates allocation x ∈ X if for each agent i ∈ N , yi Ri xi , andfor at least one agent j ∈ N , yj Pj xj . An allocation x ∈ X is Pareto eﬀicient if there is no
allocation y ∈ X that Pareto dominates it. A mechanism is Pareto eﬀicient if for each market,
it assigns a Pareto eﬀicient allocation.
Definition (Unanimity).
An allocation x ∈ X is unanimously best if for each agent i ∈ N and each allocation y ∈ X, wehave x Ri y.15 A mechanism is unanimous if, for each market, it assigns only the unanimously
best allocation whenever it exists.
If a unanimously best allocation exists for at (e, R), then that allocation is the only Pareto
eﬀicient allocation at (e, R). Hence, Pareto eﬀiciency implies unanimity.
15

Since all preferences are strict, the set of unanimously best allocations is empty or single-valued.

9Incentive properties
Next, we discuss some incentive properties for mechanisms that require that no agent / groupof agents can benefit from untruthful actions.
The next two properties, strategy-proofness and group strategy-proofness, are two of theproperties that are most frequently used in the literature on mechanism design. They modelthat no agent / coalition can benefit from misrepresenting his / their preferences.
Definition (Strategy-proofness).
A mechanism f is strategy-proof if for each market (e, R) ∈ M, each agent i ∈ N , and each preference relation Ri′ ∈ R, fi (e, Ri , R−i ) Ri fi (e, Ri′ , R−i ), i.e., agent i cannot manipulate mechanism
f at R via Ri′ .
Definition (Group strategy-proofness).
A mechanism f is group strategy-proof if for each each market (e, R) ∈ M, there is no coalition
S ⊆ N and no preference list RS′ = (Ri′ )i∈S ∈ RS such that for each i ∈ S, fi (e, RS′ , R−S ) Rifi (e, R), and for some j ∈ S, fj (e, RS′ , R−S ) Pj fj (e, R), i.e., coalition S cannot manipulatemechanism f at R via RS′ .
Next, we consider a well-known property for mechanisms that restricts each agent’s influence:no agent can change other agents’ allotments without changing his own allotment.
Definition (Non-bossiness).
A mechanism f is non-bossy if for each each market (e, R) ∈ M, each agent i ∈ N , and eachRi′ ∈ R, fi (e, Ri , R−i ) = fi (e, Ri′ , R−i ) implies f (e, Ri , R−i ) = f (e, Ri′ , R−i ). Otherwise it is bossy.
Remark 2 (Non-bossiness).
Non-bossiness is proposed by Satterthwaite and Sonnenschein (1981).16 Normally, non-bossiness
together with strategy-proofness is considered as an incentive property because the combinationof them is equivalent to group strategy-proofness. Unfortunately, this equivalence is not valid for
multiple-type housing markets (see Feng et al., 2022a, Proposition 1). However, non-bossinessstill plays an important role as an incentive property. First, non-bossiness itself, can be considered as a “collusion-proofness” property (Miyagawa, 2001). Collusion is observed often in manymarketplaces, e.g., auctions. In particular, non-bossiness is satisfied by the first-price auction
and is violated by the second-price auction, and this is why the first-price auction is becoming
increasingly popular (Pycia and Raghavan, 2022). For instance, in 2019, Google AdX changed
its auction mechanism from a second-price auction to a first-price auction.
Moreover, Alva (2017, Proposition 1) shows the equivalence of (a) effective pairwise strategyproofness and (b) the combination of strategy-proofness and non-bossiness.17 Thus, his study
16
17

See Thomson (2016) for an excellent survey.
The term effective pairwise strategy-proofness is due to Serizawa (2006). It excludes joint misreports by two

10

provides an intuition of why the invariance property non-bossiness can be considered to be an
incentive property as well.18⋄
Stability notions
Next, in order to introduce the standard cooperative solutions of the weak and the strict core,
we introduce two blocking notions: at (e, R), an allocation x ∈ X is strictly blocked by coalition
S ⊆ N if there exists an allocation y ∈ X such that(i) at allocation y agents in S reallocate their endowments, i.e., for each i ∈ S and each t ∈ T ,yit ∈ Πj∈S etj and(ii) all agents in S are strictly better off, i.e., for each i ∈ S, yi Pi xi .
An allocation x ∈ X is weakly blocked by coalition S ⊆ N if there exists an allocation y ∈ Xsuch that (ii) and(ii’) all agents in S are weakly better off with at least one of them being strictly better off, i.e.,
for each i ∈ S, yi Ri xi , and for some j ∈ S, yj Pj xj .
Given the blocking notions above, we can restate individual rationality and Pareto eﬀiciency
as stability notions in the following way: an allocation is individually rational if it is not weakly
or strictly blocked by any singleton coalition {i} and an allocation is Pareto eﬀicient if it is not
weakly blocked by the set of all agents N .
We now introduce the first type of (possibly empty or multi-valued) solution to multiple-type
housing markets that we will consider: core solutions.
Definition (Core allocation and core-stability).
An allocation is a weak core allocation if it is not strictly blocked by any coalition; the set of all
weak core allocations is the weak core, and a mechanism is weakly core-stable if for any markets,
it assigns only weak core allocations.
Similarly, an allocation is a strict core allocation if it is not weakly blocked by any coalition;
the set of all strict core allocations is the strict core, and a mechanism is strictly core-stable if
for any markets, it assigns only strict core allocations.
Next, we introduce a weaker condition than core-stability that considers the blocking with
only one or two agents. Note that pairwise weak stability is appealing because in reality, it isconsidered to be diﬀicult for large coalitions to block, while blocking by two agents is easy.
agents without self-enforcing. In other words, it insists on the robustness of a pairwise misreporting to a further
deviation by one of the misreported agents. For further studies of effective pairwise strategy-proofness, see Alva
(2017) and Shinozaki (2022).
18
Alva’s result applies to our model as well (see Feng et al., 2022a, Lemma 1, for details).

11

Definition (Pairwise stability).
An allocation is a pairwise weak core allocation if it is not strictly blocked by any coalition S ⊆ Nwith |S| ≤ 2; the set of all pairwise weak core allocations is the pairwise weak core. A mechanism
is pairwise weakly stable if for any markets, it assigns only pairwise weak core allocations.
Similarly, an allocation is a pairwise strict core allocation if it is not weakly blocked by any
coalition S ⊆ N with |S| ≤ 2; the set of all pairwise strict core allocations is the pairwise
strict core. A mechanism is pairwise strictly stable if for any markets, it assigns only pairwise
strict / weak core allocations.
Next, we list some pertinent results based on the properties we introduced above.19
Result 1 (Strict core-stability for Shapley-Scarf housing markets).
• A mechanism is strictly core-stable if and only if it is individually rational, Pareto eﬀicient,and strategy-proof (Ma, 1994; Svensson, 1999).
• If a mechanism is strictly core-stable, then it is group strategy-proof (Bird, 1984).
Result 2 (Impossibility for multiple-type housing markets).
• For markets with separable preferences Ms , there is no mechanism satisfying individual
rationality, Pareto eﬀiciency, and strategy-proofness (Konishi et al., 2001).
• For markets with lexicographic preferences Ml , there is no mechanism satisfying individual
rationality, Pareto eﬀiciency, and strategy-proofness (Sikdar et al., 2017).

4.3

Endowments-swapping-proofness and its extensions

In this subsection, we introduce our main incentive properties that exclude the manipulations of
two agents by swapping their endowments before the operation of the selected mechanism. Our
properties are motivated by endowments-swapping-proofness for Shapley-Scarf housing markets(Fujinaka and Wakayama, 2018).
Endowments-swapping-proofness for Shapley-Scarf housing markets
We first introduce endowments-swapping-proofness (Fujinaka and Wakayama, 2018) for ShapleyScarf housing markets as a benchmark. As mentioned before, for m = 1 our model equals theclassical Shapley-Scarf housing market model. Note that for Shapley-Scarf housing markets,
each agent only owns one object.
19

For Shapley-Scarf housing markets, when preferences are strict, but otherwise unrestricted, only the top
trading cycles (TTC) mechanism is strictly core-stable (see Subsection 4.4 for a formal definition of the TTC
mechanism).

12

For each endowment allocation e and a pair of agents {i, j}, let ẽ(i, j) be an endowment
allocation such that agents i and j swap their endowments and all other agents keep theirendowments, i.e., ẽi = ej , ẽj = ei , and for each agent k ̸∈ {i, j}, ẽk = ek . For each market (e, R),
let (ẽ(i, j), R) be the corresponding market according to this swapping.
Definition (Endowments-swapping-proofness).
A mechanism f is endowments-swapping-proof if for each Shapley-Scarf housing market (e, R),
there is no pair of agents {i, j} ⊆ N such that fi (ẽ(i, j), R)Pi fi (e, R) and fj (ẽ(i, j), R)Pj fj (e, R).
Extensions of endowments-swapping-proofness for multiple-type housing markets
Note that for Shapley-Scarf housing markets, endowments-swapping is easy because each agent
only owns one object. However, for multiple-type housing markets, the situation becomes complicated: alternatively, agents can partially swap their endowments. For instance, they can:swap only one type of endowments; swap their endowments completely; swap more than one(but not all) types of endowments.
To model manipulations via endowments-swapping for multiple-type housing markets, we
introduce three different ways of ex-ante endowments-swapping by a pair of agents before theoperation of the selected mechanism.20
Given an endowment allocation e and a pair of agents {i, j} ⊆ N , we consider endowmentsswapping in the following ways: (i) flexible swapping, (ii) (complete) bundle swapping, and (iii)
one type swapping.
(i) Let ē(i, j) = (ē1 , . . . , ēn ) be be a new endowment allocation by flexible swapping, such that{i, j} can swap any subsets of endowments types, i.e., (a) for each k ∈ {i, j} and each t ∈ T ,ētk ∈ {eti , etj }, and (b) for each k ̸∈ {i, j}, ēk = ek .
(ii) Let e′ (i, j) = (e′1 , . . . , e′n ) be a new endowment allocation by bundle swapping, such that{i, j} swap their endowments completely, i.e., (a) e′i = ej , e′j = ei , and (b) for each k ̸∈ {i, j},e′k = ek .
(iii) Let ê(t, i, j) = (ê1 , . . . , ên ) be a new endowment allocation by one type swapping of type-t,t+1tmsuch that {i, j} only swap their type-t endowments, i.e., (a.1) êi = (e1i , . . . , et−1
i , ej , ei , . . . , ei ),t t+1m(a.2) êj = (e1j , . . . , et−1
j , ei , ej , . . . , ej ), and (b) for each k ̸∈ {i, j}, êk = ek .
Next, we introduce three properties of immunity to the three manipulations introduced above.
Definition (Flexible endowments-swapping-proofness).
A mechanism f is flexibly endowments-swapping-proof if for each (e, R) ∈ M, there is no pair ofagents {i, j} ⊆ N and no (ē(i, j), R) such that fi (ē(i, j), R)Pi fi (e, R) and fj (ē(i, j), R)Pj fj (e, R).
20

Similar to Fujinaka and Wakayama (2018, Remark 4), our incentive properties and corresponding results
can be extended to any coalition. That is, the restriction for two agents can be relaxed for any numbers of agents.

13

Definition (Bundle endowments-swapping-proofness).
A mechanism f is bundle endowments-swapping-proof if for each (e, R) ∈ M there is no pair ofagents {i, j} ⊆ N such that fi (e′ (i, j), R) Pi fi (e, R) and fj (e′ (i, j), R) Pj fj (e, R).
Definition (One type endowments-swapping-proofness).
A mechanism f is one type endowments-swapping-proof if for each (e, R) ∈ M, there is no pairof agents {i, j} ⊆ N and no type t ∈ T , such that fi (ê(t, i, j), R) Pi fi (e, R) and fj (ê(t, i, j), R) Pj
fj (e, R).
Discussion of our endowments-swapping properties and their implicit constraints
Our three properties above are extensions of endowments-swapping-proofness for Shapley-Scarf
housing markets (Fujinaka and Wakayama, 2018). When |T | = m = 1, all three properties are equivalent. By definition, it is easy to see that flexible endowments-swappingproofness is the strongest property, i.e., flexible endowments-swapping-proofness implies bundle endowments-swapping-proofness and one type endowments-swapping-proofness. However,there is no logical relation between bundle endowments-swapping-proofness and one typeendowments-swapping-proofness. For instance, our results in Section 5 show that bTTC isbundle endowments-swapping-proof but not one type endowments-swapping-proof, while cTTCis one type endowments-swapping-proof but not bundle endowments-swapping-proof.21
Similar but different to ours, there are some properties that rule out other forms of exante manipulation via endowments, such as transfer-proofness (Atlamaz and Klaus, 2007) andnon-manipulability via pre-arranged matches (Sönmez, 1999a; Kesten, 2012).22 It is worth mentioning that concerns about these types of ex-ante manipulation are often present in real markets(see Kojima and Pathak, 2009, for details).
Our first property, flexible endowments-swapping-proofness is a natural extension because it
allows agents to swap freely, i.e., there is no restriction on how to swap. However, together withother desirable properties (individual rationality and strategy-proofness), this strong property
leads to an impossibility (Theorem 1). To avoid this impossibility, we may want to weaken flexible endowments-swapping-proofness. Thus, we propose two natural ways of restricting ex-ante
swapping and two corresponding weaker properties, bundle endowments-swapping-proofness andone type endowments-swapping-proofness: for bundle endowments-swapping-proofness, agentscan only “bundle swap”, whereas for one type endowments-swapping-proofness, agents can only“one type swap”.
One may argue that such ex-ante swapping constraints are strong. However, note that for
many models with multi-unit demands, constraints on how to trade are necessary to guarantee
21

The definitions of these two mechanisms are in Subsection 4.4.
Transfer-proofness says that no pair of agents can be better off by transferring part of one’s endowment toanother. Non-manipulability via pre-arranged matches means that no pair of a college and a student can benefit
by agreeing to match before receiving their allocations from the centralized matching mechanism.
22

14

positive results, e.g., Pápai (2007); Raghavan (2015), and Shinozaki and Serizawa (2022). On theother hand, in practice, such constraints are weaker than they may seem at first. For instance,in the context of course allocation problems (e.g., Klaus, 2008; Mackin and Xia, 2016) andemergency medicine rotation problems (e.g., Manjunath and Westkamp, 2021), swapping slots
arbitrarily might be impossible due to administrative rules, i.e., to avoid systemic complexity,
the administration might only allow agents to swap their full bundles of slots (or just one slot).
Moreover, we also show that when we keep other desirable properties, such constraints are
suﬀicient and necessary to preserve some eﬀiciency properties (see Subsection 5.4 for details).

4.4

Extensions of the top trading cycles mechanism

Note that two of our endowments-swapping constraints also imply two ways of trading: agents
can trade their endowments completely, or they can trade their endowments type by type, e.g.,
trade your house with others’ houses and trade your car with others’ cars. To simplify notation,
we first introduce an extension of the top trading cycles (TTC) mechanism with “type-by-type”
trading.
Definition (The type-t top trading cycles (TTC) algorithm).
Consider a market (N, e, R) such that R ∈ Rs . For each type t ∈ T , let (N, et , Rt ) =(N, (et1 , . . . , etn ), (R1t , . . . , Rnt )) be its associated type-t submarket.
We define the top trading cycles (TTC) allocation for each type-t submarket as follows.
Input. A type-t submarket (N, et , Rt ).
Step 1. Let N1 := N and O1t := Ot . We construct a directed graph with the set of nodes
N1 ∪ O1t . For each agent i ∈ N1 , there is an edge from the agent to his most preferred type-t
object in O1t according to Rit . For each edge (i, o) we say that agent i points to type-t object o.
For each type-t object o ∈ O1t , there is an edge from the object to its owner.
A trading cycle is a directed cycle in the graph. Given the finite number of nodes, at least
one trading cycle exists. We assign each agent in a trading cycle the type-t object he points
to and remove all trading cycle agents and type-t objects. If there are some agents (and hence
objects) left, we continue with the next step. Otherwise we stop.
Step k. Let Nk be the set of agents that remain after Step k − 1 and Okt be the set of type-t
objects that remain after Step k−1. We construct a directed graph with the set of nodes Nk ∪Okt .
For each agent i ∈ Nk , there is an edge from the agent to his most preferred type-t object in Okt
according to Rit . For each type-t object o ∈ Okt , there is an edge from the object to its owner.
At least one trading cycle exists and we assign each agent in a trading cycle the type-t object hepoints to and remove all trading cycle agents and objects. If there are some agents (and hence
objects) left, we continue with the next step. Otherwise we stop.
Output. The type-t TTC algorithm terminates when each agent in N is assigned an object in15

Ot , which takes at most n steps. We denote the object in Ot that agent i ∈ N obtains in thetype-t TTC algorithm by T T Cit (et , Rt ) and the final type-t allocation by T T C t (et , Rt ).
Definition (The cTTC allocation / mechanism).
The coordinatewise top trading cycles (cTTC) allocation, cT T C(R), is the collection of all type-t
TTC allocations, i.e., for each R ∈ RN
s ,cT T C(e, R) =

((

)
(
))
T T C11 (e1 , R1 ), . . . , T T C1m (em , Rm ) , . . . , T T Cn1 (e1 , R1 ), . . . , T T Cnm (em , Rm ) .

The cT T C mechanism (introduced by Wako, 2005) assigns each market its cTTC allocation.
Next, we consider another extension of the TTC mechanism, which only allows agents totrade their endowments completely.
Definition (The bundle top trading cycles (bTTC) algorithm / mechanism).
The bundle top trading cycles (bTTC) mechanism assigns to each market (e, R) ∈ M the unique
top-trading allocation that results from the TTC algorithm if agents are only allowed to trade
their whole endowments among each other.
Formally, for each market (e, R) and i ∈ N , let Ri |e be the restriction23 of Ri to endowments{e1 , . . . , en } and R|e ≡ (Ri |e )i∈N be the restriction profile. We then use the TTC algorithm
to compute the bTTC allocation for (e, R|e ). Note that the difference with the classical TTC
algorithm (for Shapley-Scarf housing markets) is that instead of an object, each agent can only
point to a whole endowment.
The bT T C mechanism assigns the bTTC allocation above to each market.
Remark 3. Note that bTTC is also well-defined on the domain of strict preference profiles aswell as lexicographic preference profiles and separable preference profiles. Meanwhile, cTTCis only well-defined for lexicographic preferences and separable preferences. Also note that form = 1, cTTC and bTTC reduce to the standard TTC mechanism.
⋄

5 Results
We now focus on the multiple-type extension of the Shapley-Scarf housing market model as
introduced by Moulin (1995), where |N | = n ≥ 2 and |T | = m ≥ 2.24
That is, for each i ∈ N , Ri |e are preferences over {e1 , . . . , en } such that for each ej , ek ∈ {e1 , . . . , en },ej Ri |e ek if and only if ej Ri ek .
24
One agent multiple-type housing market problems are rather trivial since no trade occurs, and for just one
object type we are back to the Shapley-Scarf housing market model.
23

16

5.1

Flexible endowments-swapping-proofness

In this subsection, we focus on the results related to flexible endowments-swapping-proofness.
Note that our results in this subsection are also valid for separable preferences and strict preferences.
The next result shows that flexible endowments-swapping-proofness is strong: it is incompatible with individual rationality and strategy-proofness.
Theorem 1. For multiple-type housing markets with lexicographic preferences Ml , there isno mechanism satisfying individual rationality, strategy-proofness, and flexible endowmentsswapping-proofness.
We prove Theorem 1 in Appendix A.2 by a counterexample. Note that the independence ofstrategy-proofness from the other properties in Theorem 1 is an open problem.
Inspired by Theorem 1, we also find an incompatibility between pairwise weak stability andstrategy-proofness.25
Theorem 2. For multiple-type housing markets with lexicographic preferences Ml , there is no
mechanism satisfying pairwise weak stability and strategy-proofness.
We prove Theorem 2 in Appendix A.2 by a counterexample.
Remark 4 (A trade off between strategy-proofness and stability notions).
The (in)compatibility between strategy-proofness and core-stability has received considerable
attention in economic theory. In a seminal paper, Sönmez (1999b) discusses the link between
strategy-proofness and the single‐valuedness strict core. More precisely, he shows that a strategyproofness mechanism always chooses a strict core allocation only if the strict core is (essentially)
single-valued.26 However, for multiple-type housing markets, usually the strict core (if it is noempty) is not single-valued (Konishi et al., 2001; Sikdar et al., 2017). Also, note that Sönmez
(1999b)’s result relies on his preference domain richness conditions. Without Sönmez (1999b)’s
preference domain richness conditions, Feng and Klaus (2022) show that strict core-stability
and strategy-proofness are still incompatible. In the presence of strategy-proofness, to avoid
this impossibility, it is natural to weaken core-stability. A possibility is weakening core-stability
to the combination of individual rationality and Pareto eﬀiciency. However, this does not work,i.e., there is no mechanism satisfying individual rationality, Pareto eﬀiciency, and strategyproofness (see Result 2). Here, we consider another way, weakening core-stability to pairwise
weak stability. Theorem 2 shows that this does not work either. Therefore, Theorem 2 canbe considered as a complement to Result 2. Furthermore, Result 2 and Theorem 2 together
25

We discuss the relation between flexible endowments-swapping-proofness and pairwise weak stability in
Subsection 6.1.
26
The strict core is (essentially) single-valued if all agents are indifferent between all strict core allocations.

17

indicate that it could be diﬀicult to find a reasonable stability notion (stronger than individual
rationality),27 that is compatible with strategy-proofness.
Overall, together with Result 2, our result (Theorem 2) explores the cost of strategyproofness. If the mechanism designer chooses an individually rational and strategy-proof mechanism, then he has to accept that, the corresponding allocation might be ineﬀicient and unstable:some agents might realize that they could be better off by pairwise trade and the market might
be thin.
⋄

5.2

Bundle endowments-swapping-proofness

In this subsection, we focus on the results related to bundle endowments-swapping-proofness.
5.2.1

Characterizing bTTC for lexicographic preferences

We first characterize bTTC for lexicographic preferences.
Theorem 3. For markets with lexicographic preferences Ml , bTTC is the only mechanism
satisfying individual rationality, strategy-proofness, non-bossiness, and bundle endowmentsswapping-proofness.
We prove Theorem 3 in Appendix A.5. Here we only explain the intuition of the uniquenesspart of the proof. Consider a top trading cycle that forms at the first step of the bTTC algorithm for (e, R). We first show that, by individual rationality, strategy-proofness, and bundle
endowments-swapping-proofness, agents in this top trading cycle receive their most preferredobject (Lemma 2). Next, we show that by individual rationality, strategy-proofness, and nonbossiness, agents in this top trading cycle receive their bTTC allotments (Lemma 3). Once wehave shown that agents who trade at the first step of the bTTC algorithm always receive theirbTTC allotments, we can consider agents who trade at the second step of the bTTC algorithm
by following the same proof arguments as for first step trading cycles, and so on.
Note that since bTTC is group strategy-proof (Feng et al., 2022b), we also have the following
result.
Corollary 1. For markets with lexicographic preferences Ml , bTTC is the only mechanism
satisfying individual rationality, group strategy-proofness, and bundle endowments-swappingproofness.
5.2.2

Characterizing bTTC for separable preferences and strict preferences

Next, we use the result for lexicographic preferences (Theorem 3) as a “stepping stone” to obtaincorresponding results for separable preferences strict preferences.
27

As we mentioned earlier, Pareto eﬀiciency can also be considered as a stability notion via a weak blocking
notion.

18

Theorem 4. For markets with separable preferences Ms , bTTC is the only mechanism satisfying individual rationality, strategy-proofness, non-bossiness, and bundle endowments-swappingproofness.
Theorem 5. For markets with strict preferences M, bTTC is the only mechanism satisfying individual rationality, strategy-proofness, non-bossiness, and bundle endowments-swappingproofness.
We prove Theorems 4 and 5 in Appendix A.5. The proof of Theorem 4 works as follows. We
first consider a preference profile such that only one agent has separable and non-lexicographic
preferences. We show that for this agent, if he (mis)reports lexicographic preferences withoutchanging his marginal preferences, then he must receive the same allotment. According to Theorem 3, the allotment (in fact, the whole allocation) then equals the bTTC allotment (allocation).
Hence, f assigns the bTTC allocation if all but one agent have lexicographic preferences. By
applying this preference replacement argument, one by one, for all other agents, we conclude
that f equals bTTC on the domain of separable preference profiles. Also, Theorem 5 can beproven by exactly the same way above.
Note that Theorems 4 and 5 imply that Corollary 1 is valid for separable preferences andstrict preferences as well.
Corollary 2. For markets with separable preferences Ms , bTTC is the only mechanism satisfying
individual rationality, group strategy-proofness, and bundle endowments-swapping-proofness.
Corollary 3. For markets with strict preferences M, bTTC is the only mechanism satisfying
individual rationality, group strategy-proofness, and bundle endowments-swapping-proofness.

5.3

One type endowments-swapping-proofness

In this subsection, we focus on the results related to one type endowments-swapping-proofness.
5.3.1

Characterizing cTTC for lexicographic preferences

We first characterize cTTC for lexicographic preferences.
Theorem 6. For markets with lexicographic preferences Ml , cTTC is the only mechanism satisfying individual rationality, strategy-proofness, and one type endowments-swapping-proofness.

We prove Theorem 6 in Appendix A.6. The uniqueness part of the proof consists of two
steps. We first consider a restricted domain of preference profiles such that all agents share thesame importance order. We show that f equals cTTC on the restricted domain (Proposition 1).
Then we extend this result to the full domain of lexicographic preference profiles by showingthat changes in agents’ importance orders do not affect the allocation.
19

5.3.2

Characterizing cTTC for separable preferences

Next, we show that Theorem 6 also holds on the domain of separable preference profiles.
Theorem 7. For markets with separable preferences Ms , cTTC is the only mechanism satisfying
individual rationality, strategy-proofness, and one type endowments-swapping-proofness.
The intuition of the proof is similar to Theorem 4: by replacing agents’ preferences, one byone, from the domain of lexicographic preference profiles to the domain of separable preference
profiles, we extend Theorem 6 to the domain of separable preference profiles.
5.3.3

An impossibility for strict preferences

Note that cTTC is not well-defined for strict preferences. Then, a natural question is if there
exists an extension of cTTC for strict preferences that satisfies our properties. Our answer isnegative: there is no extension of cTTC to the domain of strict preference profiles that satisfies
our properties.
Theorem 8. For markets with strict preferences M, there is no mechanism satisfying individual
rationality, strategy-proofness, and one type endowments-swapping-proofness.
We prove Theorem 8 in Appendix A.6 by a counterexample. Note that the independence ofstrategy-proofness from the other properties in Theorem 8 is an open problem.

5.4

Relation to eﬀiciency

In this subsection, we further discuss the relation between two of our incentive properties (bundle endowments-swapping-proofness and one type endowments-swapping-proofness) and two efficiency properties.
Recall that bTTC and cTTC, both are individually rational and strategy-proof, but not
Pareto eﬀicient. Moreover, the example below shows that none of them is more eﬀicient thanthe other.
Example 1. Consider a market with two agents and two types, i.e., N = {1, 2}, T ={H(ouse), C(ar)}, O = {H1 , H2 , C1 , C2 }, and where each agent i’s endowment is ei = (Hi , Ci ).
The preference profile R ∈ RN
l is as follows:
R1 : H2 , H1 , C1 , C2 ,R2 : C1 , C2 , H2 , H1 .
Thus, agent 1, who primarily cares for houses, would like to trade houses but not cars andagent 2, who primarily cares about cars, would like to trade cars but not houses. One easily
20verifies that cT T C(e, R) = e = ((H1 , C1 ), (H2 , C2 )) and bT T C(e, R) = x = ((H2 , C2 ), (H1 , C1 )).
Since preferences are lexicographic, both agents prefer the bT T C allocation to the cT T C allocation at R.
Furthermore, consider another preference profile R′ ∈ RN
l as follows:
R1′ : H1 , H2 , C2 , C1 ,R2′ : H2 , H1 , C1 , C2 .
Thus, both agents primarily care for houses, would like to trade cars but not houses. One easily verifies that cT T C(e, R′ ) = y = ((H1 , C2 ), (H2 , C1 )), bT T C(e, R′ ) = e = ((H1 , C1 ), (H2 , C2 )),and both agents prefer the cT T C allocation to the bT T C allocation at R′ .
⋄To avoid Result 2, one may wonder whether the bT T C mechanism and cT T C mechanism
satisfy some eﬀiciency properties that are weaker than Pareto eﬀiciency. To answer this question,
we consider the following two eﬀiciency properties.
The first one, pairwise eﬀiciency, introduced by Ekici (2022),28 rules out eﬀiciency improvements by pairwise reallocation.
Definition (Pairwise eﬀiciency).
An allocation x ∈ X is pairwise eﬀicient if there is no pair of agents {i, j} ⊆ N such that xj Pi xi
and xi Pj xj . A mechanism is pairwise eﬀicient if for each market, it assigns a pairwise eﬀicient
allocation.
Next, we consider a natural modification of Pareto eﬀiciency for multiple-type housing markets, coordinatewise eﬀiciency, that rules out coordinatewise Pareto-improvements for any type.
Note that coordinatewise eﬀiciency is only well-defined for lexicographic preferences and separable preferences.
Definition (Coordinatewise eﬀiciency).
A mechanism f : Ms → X is type-t-eﬀicient if for each market with separable preferences,(e, R) ∈ Ms , f t (e, R) is Pareto eﬀicient at Rt . Furthermore, f is coordinatewise-eﬀicient if foreach type t ∈ T , f is type-t-eﬀicient.
Recall that the above definitions are also valid for lexicographic preference profile domains.
For |T | = m = 1, coordinatewise eﬀiciency coincides with Pareto eﬀiciency. Moreover, since the
TTC mechanism is Pareto eﬀicient for Shapley-Scarf housing markets, it is easy to see that foreach type t ∈ T , cTTC is type-t-eﬀicient, and hence is coordinatewise eﬀicient.
One easily verifies that Pareto eﬀiciency implies pairwise eﬀiciency and coordinatewise efficiency, and coordinatewise eﬀiciency implies unanimity. However, there is no logical relation
between pairwise eﬀiciency and coordinatewise eﬀiciency.
28

Ekici (2022) originally refers to this property as pair eﬀiciency.

21

Next, we show that together with other desirable properties, the bT T C mechanism can becharacterized by pairwise eﬀiciency.
Theorem 9.
• For markets with lexicographic preferences Ml , bTTC is the only mechanism satisfying
individual rationality, strategy-proofness, non-bossiness, and pairwise eﬀiciency.
• For markets with separable preferences Ms , bTTC is the only mechanism satisfying individual rationality, strategy-proofness, non-bossiness, and pairwise eﬀiciency.
• For markets with strict preferences M, bTTC is the only mechanism satisfying individual
rationality, strategy-proofness, non-bossiness, and pairwise eﬀiciency.
We prove Theorem 9 in Appendix A.7. The proof sketch is similar to Theorem 3. Thatis, by individual rationality, strategy-proofness, non-bossiness, and pairwise eﬀiciency, we showthat agents who trade at the first step of the bTTC algorithm receive their bTTC allotments(Lemmas 6 and 7). Then, we use the same arguments to show that agents who at the second
step, and so on.
Finally, we show that together with other desirable properties, the cT T C mechanism can becharacterized by coordinatewise eﬀiciency.
Theorem 10.
• For markets with lexicographic preferences Ml , cTTC is the only mechanism satisfying
individual rationality, strategy-proofness, and coordinatewise eﬀiciency.
• For markets with separable preferences Ms , cTTC is the only mechanism satisfying individual rationality, strategy-proofness, and coordinatewise eﬀiciency.
This result can be proven similarly to Theorems 6 and 7: the only difference is that insteadof one type endowments-swapping-proofness, we use coordinatewise eﬀiciency to show that top
trading cycles are executed. Thus, we omit the proof.
Note that coordinatewise eﬀiciency is not well-defined on the domain of strict preference
profiles, thus Theorem 10 cannot be extended to markets with strict preferences M.
We next discuss the relation between our incentive properties and eﬀiciency properties. It
is not hard to see that our incentive properties, bundle endowments-swapping-proofness, andone type endowments-swapping-proofness, rule out some ineﬀicient mechanisms, such as the notrade mechanism.29 Unfortunately, there is no direct link between any eﬀiciency properties andour incentive properties. That is, none of our incentive properties, itself implies any eﬀiciency
29

The no-trade mechanism is a mechanism that always assigns the endowment allocation to all markets.

22

properties. However, together with our previous characterization results, Theorems 9 and 10
show that (i) together with individual rationality, strategy-proofness, and non-bossiness, bundle
endowments-swapping-proofness is equivalent to pairwise eﬀiciency, and (ii) together with individual rationality and strategy-proofness, one type endowments-swapping-proofness is equivalent
to coordinatewise eﬀiciency. In other words, in the presence of other properties we mentioned
above, bundle endowments-swapping-proofness and one type endowments-swapping-proofness,each corresponds to an eﬀiciency property.
It is worth mentioning that bundle endowments-swapping-proofness (one type endowmentsswapping-proofness) and pairwise eﬀiciency (coordinatewise eﬀiciency) are logically independent. Ekici (2022) presents two mechanisms for Shapley-Scarf housing markets to show thatendowments-swapping-proofness and pairwise eﬀiciency are logically independent (see Ekici,
2022, Section 4.3, for details). These two mechanisms can be extended to multiple-type housing markets by only trading agents’ endowment bundles. Similarly, Fujinaka and Wakayama(2018) present several mechanisms for Shapley-Scarf housing markets to show that endowmentsswapping-proofness and Pareto eﬀiciency are logically independent (see Fujinaka and Wakayama,
2018, Section 3.3, for details). These mechanisms can be extended to multiple-type housing markets by applying them coordinatewise.
Remark 5 (Constraints and eﬀiciency).
As we mentioned earlier in Subsection 4.3, to avoid negative results, such as Result 2, it is natural to make constraints to restrict trades. For instance, Kalai et al. (1978) impose restrictions
regarding trading among certain agents and Pápai (2007) restricts the set of feasible trades.
However, this also induces a new problem for the mechanism designer: what constraints to enforce? In other words, if any constraint is admissible, which constraint is better? Our results
partially answer this problem: if we still care about eﬀiciency, then, without of loss other properties, allowing agents to trade their endowments completely (type by type) is suﬀicient andnecessary to achieve pairwise eﬀiciency (coordinatewise eﬀiciency).
⋄
Remark 6 (Second-best incentive compatibility).
Klaus (2008) weakens Pareto eﬀiciency to another eﬀiciency property, second-best incentive
compatibility. To be precise, she shows that cTTC is second-best incentive compatible, i.e.,there exists no other strategy-proof mechanism that Pareto dominates cTTC. However, she also
shows that there exists another mechanism that is individually rational, strategy-proofness, andsecond-best incentive compatible. In a follow-up work, Anno and Kurino (2016) consider secondbest incentive compatibility for independent mechanisms.30 They also show that cTTC is not
the unique independent mechanism that satisfies these properties. Thus, Theorem 10 can beconsidered as a complement to Klaus (2008) and Anno and Kurino (2016)’s work: by strengthening second-best incentive compatibility to coordinatewise eﬀiciency, we find that cTTC is30

An independent mechanism treats each submarket independently and separately. That is, the selected
allocation of each type only depends on agents’ marginal preferences of each type.

23

the only independent mechanism that satisfies individual rationality, strategy-proofness, andcoordinatewise eﬀiciency.
⋄

6 Discussion
6.1

A discussion of our new properties in a normative view

In this subsection, we further discuss the role of our new properties. We first review the role ofendowments-swapping-proofness for Shapley-Scarf housing markets.
Result 3 (Endowments-swapping-proof mechanisms (Fujinaka and Wakayama, 2018)).
(a) If an individually rational and strategy-proof mechanism is endowments-swapping-proof,
then it is group strategy-proof.
(b) A mechanism is strict core-stable if and only if it is individually rational, strategy-proof,
and endowments-swapping-proof.
(c) If an individually rational mechanism is endowments-swapping-proof, then it is pairwise
weakly stable.
Note that in Result 3, we always require the presence of individual rationality. The reason
for this is simple: if we ignore property rights that are established via the endowments, thenendowments-swapping-proofness will be very weak. For instance, any constant mechanisms andserial dictatorships are endowments-swapping-proof.31
Result 3 suggests that the role of endowments-swapping-proofness for Shapley-Scarf housing
markets can also be divided into two parts as follows.32(i) endowments-swapping-proofness as an incentive property
By definition, it is easy to see that endowments-swapping-proofness is an incentive property
since it excludes the possibility that two agents within a pair may gain by swapping theirendowments. Moreover, Result 3 (a) shows that, in the presence of individual rationality andstrategy-proofness, endowments-swapping-proofness also implies a stronger incentive property,
group strategy-proofness. Thus, together with individual rationality and strategy-proofness,endowments-swapping-proofness also rules out beneficial joint misreporting.
31

The constant mechanism is one that always assigns a constant allocation to all markets. The serial dictatorship mechanism is determined by the following procedure: agents move sequentially; the first mover obtains
his most preferred allotment in O; the second mover obtains his most preferred allotment from the remaining setof objects, and so on.
32
Together with other properties, endowments-swapping-proofness also contains some eﬀiciency. And in Subsection 5.4, we already show that our new properties inherit this feature.

24

(ii) endowments-swapping-proofness as a stability notion
Fujinaka and Wakayama (2018) discuss the relation between endowments-swapping-proofness
and stability notions. In particular, Result 3 (b) shows that strict core-stability implies endowments-swapping-proofness, and (c) shows that together with individual rationality, endowments-swapping-proofness implies pairwise weak stability. Thus, one can consider
endowments-swapping-proofness as a stability notion.
The role of our new properties
Our results show that the new properties that we have drawn from endowments-swappingproofness, inherits these two feature of endowments-swapping-proofness as well. To be more
precise, together with other desirable properties, (i) bundle endowments-swapping-proofness canbe considered as an incentive property to induce group strategy-proofness (Corollaries 1, 2, and3), and (ii) flexible endowments-swapping-proofness might be considered as a stability notion(see Statement 1 in Appendix A.1).
It is worth mentioning that the last relation is not clear yet. In Statement 1, we show that(a) strict core-stability does not imply endowments-swapping-proofness and (b) together withindividual rationality, endowments-swapping-proofness implies pairwise weak stability. However, Statement 1 (b) is a vacuous truth. That is, the existence of individually rational andendowments-swapping-proof mechanisms is an open problem.

6.2

Comparison of bTTC and cTTC

In this subsection, by comparing bTTC with cTTC, we emphasize the meaning of our characterization results for these two extensions of the TTC mechanism.
First, note that both extensions satisfy several desirable properties: individual rationality,
strategy-proofness, and non-bossiness. Thus, it is hard to make a compelling argument for one
extension over the other. However, our analysis provides some justifications for distinguishing
between these two extensions of the TTC mechanism.
Generalizability
As we mentioned earlier in Remark 3, bTTC can also be used for strict preferences while cTTC
cannot. Moreover, Theorem 8 shows that no extension / modification that inherits properties
from cTTC can be used on the domain of strict preference profiles. Thus, we conclude thatbTTC performs better than cTTC in terms of generalizability (with respect to more complex
preference profiles).
It is worth mentioning that the domain of separable preference profiles is the maximal domain for cTTC, i.e., cTTC cannot be used if any agents’ preferences are not separable, andseparability allows substitutes preferences only. However, sometimes with multi-unit demands,
agents’ preferences might be (strongly) complementary, e.g., Leszczyc and Häubl (2010). Thus,

25

cTTC cannot be used for such a situation. bTTC allows for that but at the cost of limiting
outcomes by only allowing whole endowment bundle trading.
Strategic robustness
Note that each TTC extensions only satisfies one of our new properties. That is, (a) only bTTC
is bundle endowments-swapping-proof, (b) only cTTC is one type endowments-swapping-proof,and (c) none of them is flexibly endowments-swapping-proof. Thus, we cannot say that one ofthem is better in terms of strategic robustness via endowments-swapping. However, since bTTC
is also group strategy-proof (Corollary 1,Corollary 2, and Corollary 3), while cTTC is not (Fenget al., 2022a, Proposition 1), we conclude that bTTC is better if we also take into account agents’joint misreports.

6.3

Relation to other literature

In this subsection, we provide a discussion of our results and how they relate to the literature.
Another characterization result of cTTC
Here, we discuss the relation between our characterization results of cTTC (Theorem 6 andTheorem 7) and Feng et al. (2022a, Theorem 1 and Theorem 2), which characterizes cTTCon the basis of individual rationality, strategy-proofness, non-bossiness, and unanimity. To
distinguish between Feng et al. (2022a)’s results and ours, note that their results are establishedby weakening Pareto eﬀiciency and strengthening strategy-proofness, whereas ours are based onanother approach. We ignore all eﬀiciency notions but consider an additional incentive property
that excludes ex-ante manipulations via endowments-swapping. It is worthwhile to note that
we cannot invoke their results to establish ours. Therefore, while there is a close connection
between our results, there is no direct logical relation between Feng et al. (2022a)’s and ours.
Another characterization result of bTTC
Here, we discuss the relation between our characterization results of bTTC (Theorem 3,Theorem 4, and Theorem 5) and Feng et al. (2022b)’s, which essentially characterize bTTC on thebasis of individual rationality, group strategy-proofness and anonymity.33 34 Since (a) group
strategy-proofness is stronger than the combination of strategy-proofness and non-bossiness(see Remark 2), and (b) there is no link between bundle endowments-swapping-proofness andanonymity,35 our results are logically independent.
33

Anonymity says that the mechanism is defined independently of the names of the agents.
They show that only a class of hybrid mechanisms between bTTC and the no-trade mechanism, satisfies allof their properties.
35
See Subsection 4.2 in Fujinaka and Wakayama (2018) for details.
34

26

Object allocation problems with multi-demands and with ownership
Finally, we compare our results to Altuntaş et al. (2021) and Biró et al. (2022a). Both papers
consider a more general model for allocating objects to the set of agents who can consume any
set of objects. Each object is owned by an agent, but now each agent has strict preferences
over all objects, and his preferences over sets of objects are monotonically responsive to these“objects-preferences”. In our model, we impose more structure by assuming that (i) the set ofobjects is partitioned into sets of exogenously given types and (ii) each agent owns and wishes
to consume one object of each type.
Altuntaş et al. (2021) consider another extension of the TTC mechanism: the generalized top
trading cycles (gTTC) mechanism, which satisfies individual rationality and Pareto eﬀiciency but
violates strategy-proofness.36 By strengthening individual rationality and weakening strategyproofness, they provide a characterization result of the gTTC mechanism (only for lexicographic
preferences). Thus, their results complement ours: if we exclude strategy-proofness, then there
exists another extension of the TTC mechanism, which performs better than our mechanisms,
in terms of eﬀiciency and stability.
Biró et al. (2022a) extend bTTC from multiple type housing markets to their more generalmodel. They show that this extension is neither Pareto eﬀicient nor strategy-proof. Thus, theirresults show the limitation of bTTC: without the structure in our model, bTTC (which is group
strategy-proof in our model) and its extensions might be manipulable.

Acknowledgements
I am grateful to Bettina Klaus for her invaluable advice, support, and encouragement, and forher patient reviews and detailed suggestions. I would like to thank Vikram Manjunath, Takuma
Wakayama, and William Thomson for their very helpful comments and discussions. I also thankthe audience at Waseda University, Hitotsubashi University, the Workshop on Microeconomics
and Game Theory (Kyoto University), the Lausanne Matching and Market Design Workshop
2022 (University of Lausanne), and the Market Design Seminar Series (University of Tokyo) for
helpful comments. All remaining errors are my own. This research is supported by the Swiss
National Science Foundation (SNSF) through Project 100018_192583.
36

In fact, the gTTC mechanism is strictly core-stable and bossy.

27

A

Appendix: proofs

A.1

The link between flexibly endowments-swapping-proofness andstability

Statment 1. For multiple-type housing markets with lexicographic preferences Ml ,37(a) if an individually rational mechanism is flexibly endowments-swapping-proof, then it ispairwise weakly stable.
(b) a strictly core-stable mechanism is not necessarily flexibly endowments-swapping-proof.
Proof. Part (a). Suppose not. Let f be a mechanism that is individually rational and flexibly
endowments-swapping-proof, but not pairwise weakly stable. Thus, there exists a market (e, R),a pair of agents {i, j} ⊆ N , and an allocation y ∈ X such that {i, j} strictly pairwise blocks
f (e, R) via y. By the definition of pairwise blocking, (yi , yj ) is a reallocation among {i, j}themselves, i.e., for each k ∈ {i, j} and t ∈ T , ykt ∈ {eti , etj }. Let ē(i, j) be such that ēi = yi andēj = yj . Let z ≡ f (ē(i, j), R). By individual rationality of f , zi Ri yi and zj Rj yj . Since {i, j}strictly blocks f (e, R) via y, zi Ri yi Pi fi (e, R) and zj Rj yj Pj fj (e, R), which contradicts flexible
endowments-swapping-proofness of f .
Part (b). Consider markets with three agents and two types, i.e., N = {1, 2, 3}, T ={H(ouse), C(ar)}, O = {H1 , H2 , H3 , C1 , C2 , C3 }.38 Consider a market (e, R) ∈ Ml as follows.
Each agent i’s endowment is (Hi , Ci ) and preference profile R ∈ RN
l is as follows:
R1 : C2 , C1 , C3 , H3 , H2 , H1 ;R2 : H1 , H2 , H3 , C1 , C2 , C3 ;R3 : C 3 , C 2 , C 1 , H 1 , H3 , H 2 .
Note that at (e, R), there are two strict core allocations x ≡ (x1 , x2 , x3 ) =((H2 , C2 ), (H1 , C1 ), (H3 , C3 )) and y ≡ (y1 , y2 , y3 ) = ((H3 , C2 ), (H2 , C1 ), (H1 , C3 )).
Let f be a strictly core-stable mechanism such that f (e, R) = x.
Let ē(1, 3) ≡ ((H3 , C1 ), (H2 , C2 ), (H1 , C3 )). Note that at (ē(1, 3), R), there is only one strict
core allocation y. Thus, f (ē(1, 3), R) = y. Since y1 P1 x1 and y3 P3 x3 , we find that {1, 3}
can be strictly better off by swapping their endowments via ē(1, 3). Thus, f is not flexibly
endowments-swapping-proof.
37

Note that for multiple-type housing markets with lexicographic preferences, the strict core is non-empty(Sikdar et al., 2017), hence strictly core-stable mechanisms exist.
38
Note that for two agent cases, i.e., |N | = 2, flexible endowments-swapping-proofness, pairwise weak (orstrict) stability, and weak (or strict) core-stability are equivalent. Thus, our counterexample is made with atleast three agents.

28

A.2

Proof of Theorem 1 and Theorem 2

Consider markets with two types, i.e., T = {1, 2}. Suppose that there is a mechanism f thatis individually rational, strategy-proof, and flexible endowments-swapping-proof (or pairwise
weakly stable).
Let (e, R) ∈ Ml be defined as follows.
At R1 , agent 1’s type order is π1 : 1, 2, and the only object that he prefers to one of his
endowments is the type-1 endowment of agent 2, i.e.,
R11 : e12 , e11 , . . .
R12 : e21 , . . . .
At R2 , agent 2 only prefers the type-1 and type-2 endowments of agent 1 to some of his
endowments, i.e.,
R21 : e11 , e12 , . . .
R22 : e21 , e22 , . . . .
For each i = 3, . . . , n, agent i prefers his full endowment to all other allotments, i.e.,
Ri1 : e1i , . . .
Ri2 : e2i , . . . .
Let x, y ∈ X be such that at x agents 1 and 2 swap their endowments of both types, i.e.,
x1 = (e12 , e22 ),x2 = (e11 , e21 ),and for each i = 3, . . . , n,xi = ei

and at y agents 1 and 2 swap their endowments of type-1, i.e.,y1 = (e12 , e21 ),y2 = (e11 , e22 ),and for each i = 3, . . . , n,y i = ei .

Obviously, x ̸= y. Also note that agent 1 prefers y to x while agent 2 prefers x to y, i.e., y1 P1 x1and x2 P2 y2 .
By individually rationality of f , f (e, R) ∈ {x, y, e}. By flexible endowments-swappingproofness (or pairwise weak stability) of f , f (e, R) ∈ {x, y}.
Next, we define two preferences R1′ , R2′ ∈ Rl for agents 1 and 2.
At R1′ , agent 1’s type order is π1′ : 2, 1, and the marginal preferences of R1′ are the same as
R1 , i.e., R1′1 = R11 , R1′2 = R12 , and R1′ : e21 , . . . , e12 , e11 , . . .
29

At R2′ , agent 2’s type order is π2′ : 2, 1, and the only object that he prefers to one of his
endowments is the type-2 endowment of agent 1, i.e.,R2′1 : e12 , e11 , . . .
R2′2 : e21 , e22 , . . . .
andR2′ : e21 , e11 , . . . , e21 , e22 , . . . .
Suppose that f (e, R) = x. By individually rationality of f , f (e, R1′ , R−1 ) ∈ {y, e}. By
strategy-proofness of f , f1 (e, R1′ , R−1 ) ̸= y1 . Thus, f1 (e, R1′ , R−1 ) = e1 and hence f (e, R1′ , R−1 ) =e. However, this violates flexible endowments-swapping-proofness (or pairwise weak stability) off , because {1, 2} can be strictly better off by swapping their endowments of type-1 (or strictly
block e via y).
Suppose that f (e, R) = y. By individually rationality of f , f (e, R2′ , R−2 ) ∈ {x, e}. By
strategy-proofness of f , f2 (e, R2′ , R−2 ) ̸= x2 . Thus, f2 (e, R2′ , R−2 ) = e2 and hence f (e, R2′ , R−2 ) =e. However, this violates flexible endowments-swapping-proofness (or pairwise weak stability)of f , because {1, 2} can be strictly better off by swapping their endowments of both types (orstrictly block e via x).

A.3

Auxiliary properties and results

We introduce the well-known property of (Maskin) monotonicity, which requires that if an
allocation is chosen, then that allocation will still be chosen if each agent shifts it up in his
preferences. We formulate monotonicity as well as our first auxiliary result for markets withstrict preferences M; however, we could use markets with separable preference Ms and with
lexicographic preferences Ml instead.
Let i ∈ N . Given preferences Ri ∈ R and an allotment xi , let L(xi , Ri ) = {yi ∈ Πt∈T Ot |xi Ri yi } be the lower contour set of Ri at xi . Preference relation Ri′ is a monotonic transformationof Ri at xi if L(xi , Ri ) ⊆ L(xi , Ri′ ). Similarly, given a preference profile R ∈ RN and an allocation
x, a preference profile R′ ∈ RN is a monotonic transformation of R at x if for each i ∈ N , Ri′ isa monotonic transformation of Ri at xi .
Definition (Monotonicity).
A mechanism f is monotonic if for each (e, R) ∈ M and for each monotonic transformation
R′ ∈ RN of R at f (e, R), we have f (e, R′ ) = f (e, R).
Strategy-proofness and non-bossiness imply monotonicity.
Lemma 1 (Lemma 3 in Feng et al. (2022a)).
For markets with strict preferences M ( Ms / Ml , respectively), if a mechanism is strategy-proof
and non-bossy, then it is monotonic.
30

Next, we list some useful results based on strategy-proofness, non-bossiness, and monotonicity.
Fact 1 (Fact 1 in Feng et al. (2022a)).
Let xi be an allotment. Let Ri , R̂i be lexicographic preferences such that (1) πi = π̂i and (2) for
each t ∈ T , R̂it is a monotonic transformation of Rit at xti . Then, R̂i is a monotonic transformationof Ri at xi .
Fact 2. Let f be a strategy-proof and non-bossy mechanism. Let R ∈ RN
l , z ≡ f (e, R), i ∈ N ,∗and Ri ∈ Rl be preferences that only differ with Ri in the marginal preference of the mostimportant type (type-t), i.e., (1) πi = πi∗ where πi∗ (t) = 1, and (2) for each τ ̸= t, Riτ = Ri∗τ .
If fit (e, Ri∗ , R−i ) = zit , then f (e, Ri∗ , R−i ) = z.
Proof. It is without loss of generality to assume that t = 1 and πi : 1, . . . , m. Let y ≡f (e, Ri∗ , R−i ) and assume yi1 = zi1 . By strategy-proofness of f , zi Ri yi and yi Ri∗ zi . Since Ri
are lexicographic preferences, zi Ri yi implies zi2 Ri2 yi2 . Similarly, since Ri∗ are lexicographic
preferences, yi Ri∗ zi implies yi2 Ri∗2 zi2 . Since Ri2 = Ri∗2 , we find that zi2 = yi2 . Applying thesame argument sequentially for type-τ marginal preferences with τ = 3, . . . , m yields zi = yi .
By non-bossiness of f , z = y.

A.4

Alternative definition of bTTC and results

We restate bTTC for lexicographic preferences by adjusting the multiple-type top trading cycles(mTTC) algorithm from Feng and Klaus (2022).
The bundle top trading cycles (bTTC) algorithm / mechanism.
Input. A multiple-type housing market (e, R) ∈ Ml .
Step 1. Building step. Let N (1) = N and U (1) = O. We construct a directed graph G(1)with the set of nodes N (1) ∪ U (1). For each o ∈ U (1), we add an edge from the object to its
owner and for each i ∈ N (1), we add an edge from the agent to his most preferred object in O
(according to the linear representation of Ri ). For each edge (i, o) ∈ N × O we say that agent i
points to object o.
Implementation step. A trading cycle is a directed cycle in graph G(1). Given the finite
number of nodes, at least one trading cycle exists. We assign to each agent i in a trading cycle
the object that he pointed to, and denote the object assigned to him in this step by ai (1).
Moreover, let ei (1) be the whole endowment of object ai (1)’s owner, and assign the allotmentxi (1) = {ei (1)} to agent i. If agent i ∈ N was not part of a trading cycle, then xi (1) = ∅.
Removal step. We remove all agents and objects that were assigned in the implementation
step, let N (2) and U (2) be the remaining agents and objects, respectively. Go to Step 2.
In general, at Step q (≥ 2) we have the following:
31

Step q. If U (q) (or equivalently N (q)) is empty, then stop; otherwise do the following.
Building step. We construct a directed graph G(q) with the set of nodes N (q) ∪ U (q). For
each o ∈ U (q), we add an edge from the object to its owner and for each i ∈ N , we add anedge from the agent to his most preferred feasible continuation object in Ui (q) (according to thelinear representation of Ri ).
Implementation step. A trading cycle is a directed cycle in graph G(q). Given the finite
number of nodes, at least one trading cycle exists. We assign to each agent i in a trading cycle
the object that he pointed to, and denote the object assigned to him in this step by ai (q).
Moreover, let ei (q) be the whole endowment of object ai (q)’s owner, and assign the allotmentxi (q) = {ei (q)} to agent i. If agent i ∈ N was not part of a trading cycle, then xi (q) = ∅.
Removal step. We remove all agents and objects that were assigned in the implementation
step, let N (q+1) and U (q+1) be the remaining agents and objects, respectively. Go to Step q+1.
Output. The bTTC algorithm terminates when all objects in O are assigned (it takes atmost n steps). Assume that the final step is Step q ∗ . Then, the final allocation is x(q ∗ ) ={x1 (q ∗ ), . . . , xn (q ∗ )}.
The bundle top trading cycles (bTTC) mechanism, bT T C, assigns to each market (e, R) ∈ Ml
the allocation x(q ∗ ) obtained by the bTTC algorithm.
Example 2 (bTTC).
Consider (e, R) ∈ Ml with N = {1, 2, 3}, T = {H(ouse), C(ar)}, O = {H1 , H2 , H3 , C1 , C2 , C3 },each agent i’s endowment is ei = (Hi , Ci ), andR1 : H2 , H3 , H1 , C3 , C2 , C1 ,R2 : C1 , C2 , C3 , H3 , H2 , H1 ,R3 : H2 , H1 , H3 , C1 , C3 , C2 .
The bTTC allocation at (e, R) is obtained as follows.
Step 1. Building step. G(1) = (N ∪ O, E(1)) with set of directed edges E(1) ={(H1 , 1), (H2 , 2), (H3 , 3), (C1 , 1), (C2 , 2), (C3 , 3), (1, H2 ), (2, C1 ), (3, H2 )}.
Implementation step. The trading cycle 1 → H2 → 2 → C1 → 1 forms. Then, a1 (1) = H2 ,a2 (1) = C1 , and e1 (1) = {H2 , C2 }, e2 (1) = {H1 , C1 }; thus, x1 (1) = {H2 , C2 }, x2 (1) = {H1 , C1 },and x3 (1) = ∅.
Removal step. N (2) = 3, U (2) = {H3 , C3 }.
Step 2. Building step. G(2) = (N (2) ∪ U (2), E(2)) with set of directed edges E(2) ={(H3 , 3), (C3 , 3), (3, H3 )}.
Implementation step. The trading cycle 3 → H3 → 3 forms. Then, a3 (2) = H3 ande3 (2) = {H3 , C3 }; x1 (2) = {H2 , C2 }, x2 (2) = {H1 , C1 }, and x3 (2) = {H3 , C3 }.
32

Removal step. N (3) = ∅ and U (3) = ∅.
Thus, the bTTC algorithm computes the allocation x = ((H2 , C2 ), (H1 , C1 ), (H3 , C3 )).

⋄Our next lemma states that Fujinaka and Wakayama (2018, Lemma 1) partially extends tomultiple-type housing markets with lexicographic preferences Ml .
Given a market (e, R) ∈ Ml , let C(e, R) be a set of top trading cycles that are obtained atstep 1 of the re-defined bTTC mechanism above at (e, R). We say that a trading cycle C is a
first step top trading cycle if C ∈ C(e, R). For each first step top trading cycle C, let SC ⊆ N
be the set of agents who are involved in C, and for each i ∈ SC , let ci be the object that agent
i points at in C, and ti be the type of object ci , i.e., ci ∈ Oti . We say that a trading cycle C is
executed under f at (e, R) if for each i ∈ SC , agent i receives ci at f (e, R).
Lemma 2. If a mechanism f : Ml → X is individually rational, strategy-proof, and bundle
endowments-swapping proof, then for each (e, R) ∈ Ml , each first step top trading cycle C(∈
C(e, R)) is executed under f at (e, R).
Proof. The proof is a straightforward extension of Fujinaka and Wakayama (2018, Lemma 1).
Let C ∈ C(e, R) be a first step top trading cycle that consists of agents SC ⊆ N . We prove thislemma by induction on |SC |.
Induction basis. |SC | = 1. In this case, agent i ∈ SC points to one of his endowed object, i.e.,ci ∈ ei and hence C = (i → ci (= etii ) → i). Since preferences are lexicographic, i.e., Ri ∈ Rl , iwill be strictly worse off if he receives any other type-ti objects. Thus, C must be executed byindividual rationality of f .
Induction hypothesis. Let K ∈ {2, . . . , n}. Suppose that C is executed when |SC | < K.
Induction step. Let |SC | = K. Without loss of generality, assume that SC = {1, . . . , K}
and C = (1 → c1 → 2 → c2 → . . . → K → cK → 1). See the figure below for the graphicalexplanation.
1

R1

c1

2

R2

c2

cK

3

RK
K

R3
...

R4

33

4

c3

By contradiction, assume that C is not executed. Thus, there is an agent i ∈ SC who does
not receive ci , i.e., fiti (e, R) ̸= ci . Let R̂i be such that i only wants to receive type-ti object ci
and no other objects, i.e.,R̂iti : ci , etii , . . . ,for each t ∈ T \ {ti } : R̂it : eti , . . . , andπ̂i (ti ) = 1.
Note that at R̂i , if i does not receive ci , then from individual rationality of f , he must receive
his full endowment ei .
Let R̂ ≡ (R̂i , R−i ) and M̂i ≡ (e, (R̂i , R−i )). We proceed in two steps.
Step 1. We show that agent i receives ci under f at M̂i , i.e., fiti (M̂i ) = ci .
By individual rationality of f , fiti (M̂i ) ∈ {ci , etii }. By strategy-proofness of f , fiti (e, R) ̸= ci
implies that fiti (R̂i ) ̸= ci , otherwise instead of Ri , agent i has an incentive to misreport R̂i at(e, R). Thus, fiti (M̂i ) = etii . Then, by individual rationality of f , fi (M̂i ) = ei . Thus, agent i − 1cannot receive ci−1 from agent i because it is assigned to agent i. Overall, we find thatti−1
(M̂i ) ̸= ci−1 (∈ ei ).
fiti (M̂i ) = etii ̸= ci and fi−1

(1)

Let agents i − 1 and i swap their endowments completely. i.e., e′ (i − 1, i). Note that at
e′ (i − 1, i), i − 1 owns ei (= e′i−1 ) and i owns ei−1 (= e′i ). Correspondingly, i − 1 owns his most
preferred object ci−1 (∈ ei ), and i owns ci−2 (∈ ei−1 ), recall that ci−2 is agent i−2’s most preferredobject.
Consider M̂i′ ≡ (e′ (i − 1, i), (R̂i , R−i )). at M̂i′ , there are two first step top trading cycles
C ′ = (i − 1 → ci−1 → i − 1) and C ′′ = (1 → c1 → 2 → . . . → i − 2 → ci−2 → i → ci → i + 1 . . . →K → cK → 1) at M̂i′ , i.e., C ′ , C ′′ ∈ C(M̂i′ ). See the figure below for the graphical explanation.
i−2

C ′′

Ri−2

i−1

ci−2

Ri−1

ci−1

ci−3

i

Ri−3
i−3

C′

R̂i
...

Ri+1

i+1

ci

Note that |SC ′ | = 1 and |SC ′′ | = K − 1. Thus, by the induction hypothesis, these twocycles are executed under f at Mi′ . Hence, agents i − 1 and i receive their most preferred
34

i−1
i−1
i−1
object at f (M̂i′ ). Thus, together with (1), we find that fi−1(M̂i′ ) = ci−1 Pi−1
fi−1
(M̂i ) and
ti
ti ti
′
′
′
fi (M̂i ) = ci Pi fi (M̂i ). Therefore, fi−1 (M̂i ) Pi−1 fi−1 (M̂i ) and fi (M̂i ) Pi fi (M̂i ). However, this
implies that f is not bundle endowments-swapping proof, a contradiction.

t

t

t

Step 2. We show that agent i receives ci under f at (e, R), i.e., fiti (e, R) = ci .
Note that ci is agent i’s most preferred object at Ri . By strategy-proofness of f , fi (e, R) Ri
fi (M̂i ). Hence, fiti (e, R) Riti fiti (M̂i ) = ci , which implies that fiti (e, R) = ci .

A.5

Proof of Theorems 3, 4, and 5

Proof of Theorem 3
It is well-known that the TTC mechanism satisfies individual rationality, strategy-proofness,
non-bossiness, and endowments-swapping-proofness for Shapley-Scarf housing markets. By using
similar arguments we also obtain that bTTC inherits individual rationality, strategy-proofness,
non-bossiness, and bundle endowments-swapping-proofness from the underlying top trading cycles algorithm for the restricted market (e, R|e ). So we only show that bTTC is the only mechanism satisfying all our properties above.
Next, we show that all agents who are involved in top trading cycles at step 1 of bTTC,
have to receive the corresponding bTTC allocation. Note that in the proof below, we do not use
bundle endowments-swapping-proofness. That is, we only use individual rationality, strategyproofness, non-bossiness, and monotonicity. Thus, from now and until the end of the proof, wewill denote a market simply by its preference profile, e.g., f (R) instead of f (e, R), when the restin the proof is clear. We will show that for each R ∈ RN
l , f (R) = bT T C(R).
N
Let f : Rl → X be a mechanism satisfying our all properties above. By Lemma 1, f ismonotonic.
For each market R ∈ RN
l , each first step top trading cycle C ∈ C(R), each i ∈ SC and′ci ∈ O, let i be the owner of ci . Since i and i′ are involved in C, i′ ∈ SC . We say that a trading
cycle C is fully executed under f at (e, R) if for each i ∈ SC , agent i receives ei′ at f (e, R), i.e.,fi (e, R) = ei′ .
Lemma 3. For each R ∈ RN
l , each C ∈ C(R), and each i ∈ SC , fi (R) = bT T Ci (R).
Proof. Let C ∈ C(R) be a first step trading cycle that consists of agents SC ⊆ N . We prove
this lemma by induction on |SC |.
Induction basis. |SC | = 1. In this case, agent i ∈ SC points to one of his endowed object,i.e., ci ∈ ei . Without loss of generality, assume that SC = {1} and π1 : t1 , . . .. Thus, C = (1 →et11 → 1).
Let y ≡ f (R). By contradiction, suppose that y1 ̸= e1 . Note that by Lemma 2, C is executed,
and hence y1t1 = et11 . Let t ∈ T \ {ti } be such that y1t ̸= et1 . Without loss of generality, assume
that agent 1 receives agent 2’s endowment of type-t at y, i.e., y1t = et2 .
35

Let R̂ ∈ RN
l be such that each agent j positions yj at the top and changes his importanceorder as π1 , i.e., (i) for each agent j ∈ N , π̂j = π1 : t1 , . . .; and (ii) for each j ∈ N and eachτ ∈ T , R̂jτ : yjτ , . . .
By monotonicity of f , f (R̂) = y.
Let R̄2 be such thatπ̄2 = π̂2 (= π1 ),R̄2t1 : et11 , y2t1 , . . . , andFor each τ ∈ T \ {t1 }, R̄2τ = R̂2τ .
Let
R̄ ≡ (R̄2 , R̂−2 ).
Note that by strategy-proofness of f , agent 2 either receives et11 or y2t1 ; otherwise he has anincentive to misreport R̂2 at R̄. Moreover, C is still a first top trading cycle at R̄, i.e., C ∈ C(R̄).
Thus, by Lemma 2, C is executed and hence agent 1 receives et11 at f (R̄). See the figure below
for the graphical explanation.
1

R̂1

et11

R̄2

et2

2

Thus, agent 2 still receives y2t1 , and hence by Fact 2,
f (R̄) = f (R̂) = y and particularly, f1t1 (R̃) = y1t1 = et11 .

(2)

Let R̃1 be such that agent 1 only changes his importance order as t is the most important,i.e., π̃1 : t, . . . and R̃1 = (R̂11 , . . . , R̂1m , π̃1 ).
Let
R̃ ≡ (R̃1 , R̄−1 ).
By monotonicity of f , f (R̃) = f (R̄) = y. However, at R̃, there is a first step top trading
cycle C ′ ∈ C(R̃) consisting of agents 1 and 2, i.e., C ′ = (1 → et2 (= y1t ) → 2 → et11 → 1). See thefigure below for the graphical explanation.

36

et11

1

R̄2

R̃1

et2

2

By Lemma 2, C ′ is executed under f at R̃. Thus, f2t1 (R̃) = et11 , which contradicts with thefact that f1t1 (R̃) = y1t1 = et11 (see (2)).
Induction hypothesis. Let K ∈ {2, . . . , n}. Suppose C is fully executed when |SC | < K.
Induction step. Let |SC | = K. Without loss of generality, assume that SC = {1, . . . , K}
and C = (1 → et21 → 2 → · · · → K → et1K → 1). We will prove that for each i ∈ SC ,fi (R) = bT T Ci (R) = ei+1 (mod K).
Let x ≡ bT T C(R), y ≡ f (R), and by contradiction, suppose that there is an agent i ∈ SC
such that yi ̸= xi . Without loss of generality, let i = 1. By Lemma 2, C is executed under f at
R. In particular,tK(3)= et1K = xtKK .
y1t1 = et21 = xt11 and yK
Since y1 ̸= x1 (= e2 ), there is a type t ∈ T \ {t1 } and an agent j ̸= 2 such that y1t = etj . There
are two cases.
Case 1: j ∈ SC . Let R̂1 be such that agent 1 positions y1 at the top and moves t to the mostimportant, i.e., (i) π̂1 : t, . . .; and (ii) for each τ ∈ T , R̂1τ : y1τ , . . .. Since R̂1 is a monotonic
transformation of R1 at y, we havef (R̂1 , R−1 ) = f (R) = y and particularly, f1t1 (R̂1 , R−1 ) = et21 .
t

(4)

j
→ j + 1 → ··· →Note that there is a first step top trading cycle C ′ ≡ (1 → etj → j → ej+1
tK
K → e1 → 1) at (R̂1 , R−1 ). i.e., C ′ ∈ C(R̂1 , R−1 ). Since j ̸= 2, cycle C ′ contains less than K
agents. There are two sub-cases.
Sub-case one: K = 2. j ∈ SC implies That j = 1 and C ′ = (1 → et1 → 1), then we are backto the situation in the induction basis, see the figure below for the graphical explanation.

37

1

R̂1

et11

R2

et2

2

Thus, by the the induction basis, f1 (R̂1 , R−1 ) = e1 and hence f1t1 (R̂1 , R−1 ) = et11 , which contradicts with the fact that f1t1 (R̂1 , R−1 ) = et21 (see (4)).
Sub-case two: K > 2. By the induction hypothesis, cycle C ′ is fully executed at f (R̂1 , R−1 ).
Therefore, f1 (R̂1 , R−1 ) = ej and hence f1t1 (R̂1 , R−1 ) = etj1 , which contradicts with the fact thatf1t1 (R̂1 , R−1 ) = et21 (see (4)).
Case 2: j ̸∈ SC . Let R̂j be such that (i) π̂j : tK , . . .; (ii) R̂jtK : et1K , yjtK , . . .; and (iii) for eachτ ∈ T \{tK }, R̂jτ : yjτ , . . ..
LetR̂ ≡ (R̂j , R−j ).
Note that C is still a first step top trading cycle at R̂, and hence, by Lemma 2, C is executed.
In particular, with (3), we havetK
fKtK (R̂) = yK
= et1K .
(5)
So, agent j does not receive et1K at f (R̂). So, by strategy-proofness of f , fj (R̂) = yj ; otherwise
he has an incentive to misreport Rj at R̂. So, by non-bossiness of f , f (R̂) = y.
Let R̄1 be such that agent 1 positions y1 at the top and moves t to the most important, i.e.,(i) π̄1 : t, . . .; and (ii) for each τ ∈ T , R̄1τ : y1τ , . . .. LetR̄ ≡ (R̄1 , R̂−1 ).
Since R̄1 is a monotonic transformation of R̂1 (= R1 ) at y, we havef (R̄) = y and particularly, fKtK (R̄) = et1K .

(6)Note that C ′ ≡ (1 → y1t (= etj ) → j → et1K → 1) is a first step top trading cycle at R̄, i.e.,C ′ ∈ C(R̄). See the figure below for the graphical explanation.

38

et1K

1

R̄1

R̄j (= R̂j )etj

jThus, by Lemma 2, cycle C ′ is executed at f (R̄). Therefore, fjtK (R̄) = et1K . Since j ̸∈ SC , thiscontradicts with the fact that fKtK (R̂) = et1K (see (6)).
By Lemma 3, we have shown that agents who trade at step 1 of the bTTC algorithm always
receive their bTTC allotments under f . Next, we can consider agents who trade at step 2 of thebTTC algorithm by following the same proof arguments as for first step trading cycles, and soon. Thus, the proof of Theorem 3 is completed.
Proof of Theorem 4
Proof. Let f : Ms → X be individually rational, strategy-proof, non-bossy, and bundle
endowments-swapping proof. Note that by Lemma 1, f is monotonic.
Let S ⊆ N and (e, R) ∈ Ms be such that only agents in S do no have lexicographic
preferences, i.e., RS ̸∈ RSl and R−S ∈ R−S
l . We show that f (e, R) = bT T C(e, R) by induction
on |S|.
We first consider S = {i}, i.e., |S| = 1 as the induction basis.
Let x ≡ f (e, R) and y ≡ bT T C(e, R).
Let R̂i ∈ Rl be such that for each t ∈ T , R̂it : xti , . . .
By monotonicity of f , f (e, (R̂i , R−i )) = x. Note that (R̂i , R−i ) ∈ RN
l . Thus, by Theorem 3,f coincides with bTTC, i.e., bT T C(e, (R̂i , R−i )) = f (e, (R̂i , R−i )) = x.
Let R̄i ∈ Rl be such that (a) π̄i = π̂i ; and (b) for each t ∈ T , R̂it : yit , . . .
By monotonicity of bT T C, bT T C(e, (R̄i , R−i )) = y. Note that (R̄i , R−i ) ∈ RN
l . Thus, again
by Theorem 3, f (e, (R̄i , R−i )) = bT T C(e, (R̄i , R−i )) = y.
By strategy-proofness of bT T C, yi = bT T Ci (e, R) Ri bT T Ci (e, (R̂i , R−i )) = xi ; by strategyproofness of f , xi = fi (e, R) Ri fi (e, (R̄i , R−i )) = yi . Thus, xi = yi . Subsequently, by nonbossiness of bT T C, x = bT T C(e, (R̂i , R−i )) = bT T C(e, (R̄i , R−i )) = y.
We can apply repeatedly the same argument to obtain that for |S| ∈ {2, . . . , n}, and foreach profile R ∈ RN
s where exactly |S| agents have non-lexicographic preferences, f (e, R) =bT T C(e, R). Thus, for each (e, R) ∈ Ms , f (e, R) = bT T C(e, R).
Theorem 5 can be proven by exactly the same way to Theorem 4 and hence we omit it.
39

A.6

Proof of Theorems 6, 7, and 8

Feng et al. (2022a) show that cTTC is individual rationality and strategy-proofness. Thus, here
we only show that cTTC is one-type endowments-swapping-proof.
By contradiction, suppose that cTTC is not one-type endowments-swapping-proof. Thus,
there exists a market (e, R), a type t, a pair of agents {i, j}, and a new endowment allocation by
one type swapping ê(t, i, j) such that cT T Ci (ê(t, i, j), R)Pi cT T Ci (e, R) and cT T Cj (ê(t, i, j), R)PicT T Cj (e, R). Let x ≡ cT T C(e, R) and y ≡ cT T C(ê(t, i, j), R). By the definition of cTTC, weknow that(i) for each τ ̸= t, xτi = T T Ciτ (eτ , R) = yiτ and xτj = T T Cjτ (eτ , R) = yjτ .
(ii) xti = T T Cit (e, Rt ) and xtj = T T Cjt (e, Rt ).
(iii) yit = T T Cit (êt (t, i, j), Rt ) and yjt = T T Cjt (êt (t, i, j), Rt ).
Since the TTC mechanism is endowments-swapping-proof (Fujinaka and Wakayama, 2018),
together with (ii) and (iii), we find that for one agent k ∈ {i, j}, xtk Rk ykt . However, by (i),yi Pi xi and yj Pj xj implies that yit Pit xti and yjt Pjt xtj , a contradiction.
Next, we show that cTTC is the only mechanism satisfying all our properties above. Letf : Ml → X be a mechanism that is individual rationality, strategy-proofness, and one-typeendowments-swapping-proof.
A result for restricted preferences
We first consider a restricted domain RN
π such that all agents share the same importance order
π. It is without loss of generality to assume that π : 1, . . . , m.
Proposition 1. For each market (e, R) with restricted preference profile R ∈ RN
π , f (e, R) =cT T C(e, R).
The proof of Proposition 1 consists of three claims.
First, we show that for each market with restricted preferences, f assigns the cTTC allocationof type-1.
11Claim 1. For each (e, R) with R ∈ RN
π , f (e, R) = cT T C (e, R).

Proof. Note that the proof is similar to Lemma 2.
Let C be a first step top trading cycle under T T C 1 at (e, R) that consists of a set of agentsSC ⊆ N . We first show that C is executed at f (e, R) by induction on |SC |.
Induction basis. |SC | = 1. In this case, agent i ∈ SC points to his type-1 endowed object,i.e., C = (1 → e11 → 1). Since preferences are lexicographic, agent 1 will be strictly worse off if
he receives any other type-1 object. Thus, by individual rationality of f , C must be executed.
40

Induction hypothesis. Let K ∈ {2, . . . , n}. Suppose that C is executed when |SC | < K.
Induction step. Let |SC | = K. Without loss of generality, assume that SC = {1, . . . , K} andC = (1 → e12 → 2 → . . . → K → e11 → 1).
By contradiction, assume that C is not executed. Thus, there is an agent i ∈ SC who does
not receive e1i+1 , i.e., fi1 (e, R) ̸= e1i+1 .
Let R̂i ∈ Rπ be such that i only wants to receive one type-1 object e1i+1 than his type-1
endowment, i.e.,R̂i1 : e1i+1 , e1i , . . . ,for each t ∈ T \ {1} : R̂it = Rit , andπ̂1 = π : 1, . . . , m.
Note that at R̂i , if i does not receive e1i+1 , then by individual rationality of f , he must receive
his type-1 endowment e1i .
Let R̂ ≡ (R̂i , R−i ) and M̂i ≡ (e, (R̂i , R−i )). We proceed in two steps.
Step 1. We show that agent i receives e1i+1 under f at M̂i , i.e., fi1 (M̂i ) = e1i+1 .
Since R̂i ∈ Rl and f is individually rational, fi1 (M̂i ) ∈ {e1i+1 , e1i }. By strategy-proofness off , fi1 (e, R) ̸= e1i+1 implies that fi1 (M̂i ) ̸= e1i+1 , otherwise instead of Ri , agent i has an incentive
to misreport R̂i at (e, R). Thus, fi1 (M̂i ) = e1i . Thus, agent i − 1 cannot receive e1i from agent i
because it is assigned to agent i. Overall, we find that1fi1 (M̂i ) = e1i ̸= e1i+1 and fi−1(M̂i ) ̸= e1i .

(7)Consider that agents i − 1 and i swap their type-1 endowments, i.e., ê(t = 1, i − 1, i). Notethat at this new endowment allocation, i − 1 owns his most preferred object e1i , and i owns e1i−1 ,and recall that e1i−1 is agent (i − 2)’s most preferred type-1 object. Consider that M̂i′ ≡ (ê(t =1, i − 1, i), (R̂i , R−i )). At M̂i′ , there are two first step top trading cycles C ′ = (i − 1 → e1i → i − 1)
and C ′′ = (1 → e12 → 2 → . . . → i − 2 → e1i−1 → i → e11+1 → i + 1 . . . → K → e11 → 1) at M̂i′ .
See the figure below for the graphical explanation.
i−2

C ′′

Ri−2

i−1

e1i−1

Ri−1

e1i−1

e1i−3

i

Ri−3
i−3

R̂i
...

Ri+1

41

i+1

e1i

C′

Note that |SC ′ | = 1 and |SC ′′ | = K − 1. Thus, by the induction hypothesis, these two cycles
are executed under f at M̂i′ .
1Hence, agents i − 1 and i receive their most preferred object at f (M̂i′ ). By (7), fi−1(M̂i′ ) =11
e1i Pi−1
fi−1(M̂i ) and fi1 (M̂i′ ) = e1i+1 Pi1 fi1 (M̂i ). Therefore, fi−1 (M̂i′ ) Pi−1 fi−1 (M̂i ) andfi (M̂i′ ) Pi fi (M̂i ). However, this implies that f is not one type endowments-swapping-proof,a contradiction.
Step 2. We show that agent i receives e1i+1 under f at (e, R), i.e., fi1 (e, R) = e1i+1 .
Note that e1i+1 is agent i’s most preferred type-1 object at Ri . By strategy-proofness of f ,fi (e, R) Ri fi (M̂i ). Hence, fi1 (e, R) Ri1 fi1 (M̂i ) = e1i+1 , which implies that fi1 (e, R) = e1i+1 .
It suﬀices to show that C is executed at f (e, R) because once we have shown that agents who
trade at the first step of the TTC algorithm (of type-1) always receive their TTC allotments oftype-1 under f , we can consider agents who trade at the second step of the TTC (of type-1) byfollowing the same proof arguments as for first step trading cycles, and so on. Thus, the proofof Claim 1 is completed.
Note that at step 1 and step 2 of the proof of Claim 1, we only require that agents in SC haverestricted preferences in Rπ , i.e., if RSC ∈ RSπC then for any R−SC ∈ Rl−SC , fS1C (RSC , R−SC ) =cT T CS1C (RSC , R−SC ). Therefore, Claim 1 implies the following fact.
Fact 3 (Restricted preferences).
For each (e, R) with R ∈ RN
π , let C ≡ {C1 , C2 , . . . , CI } be the set of top trading cycles thatare obtained via the TTC algorithm of type-1 at (e1 , R1 ). Moreover, for each top trading cycle
Ci ∈ C, assume that Ci is executed at step si , and without loss of generality, assume that if
i < i′ then si ≤ si′ .
For each Ci ∈ C, if all agents in SC1 , SC2 , . . . , SCi−1 , SCi have restricted preferences, thenC1 , . . . , Ci−1 , Ci are executed, regardless of the preferences of other agents in Ci+1 , . . . , CI .
Formally, for each Ci ∈ C, let S ′ ≡ ∪ik=1 SCk . If (e, R) is such that for each j ∈ S ′ , Rj ∈ Rπ ,then fS1′ (e, R) = cT T CS1 ′ (e, R).
Next, we show that for each agent, his type-2 allotment is weakly better than his type-2
endowment.
2
2 2
Claim 2. For each (e, R) with R ∈ RN
π and each i ∈ N , fi (e, R) Ri ei .

Proof. By contradiction, assume that there exists a market (e, R) with R ∈ RN
π and an agenti ∈ N such that e2i Pi2 fi2 (e, R).
Let y ≡ f (e, R). Recall that by Claim 1, y 1 = cT T C 1 (e, R) = T T C 1 (e1 , R1 ). It is without
loss of generality to assume that i = 1. Since R̂1 ∈ Rl and f is individually rational,y11 ̸= e11 .
42(8)Let R̂1 ∈ Rπ be such thatR̂12 : e21 , y12 , . . . ,for each t ∈ T \ {2}, R̂1t : y1t , et1 , . . . , andπ̂1 = π : 1, . . . , m.
By strategy-proofness of f , f1 (e, R̂1 , R−1 ) = y1 . Note that π̂1 = π : 1, . . . , m and (R̂1 , R−1 ) ∈N
Rπ . By Claim 1, f 1 (e, R̂1 , R−1 ) = cT T C 1 (e, R̂1 , R−1 ) = y 1 .
Let R̄1 ∈ Rl be such that R̄1 and R̂1 only differ in the importance order, where the ordersof type-1 and type-2 are switched, i.e., π̄1 : 2, 1, 3, . . . , m and R̄1 = (R̂11 , . . . , R̂1m , π̄1 ).
By individual rationality of f , f12 (e, R̄1 , R−1 ) = e21 . Therefore, by individual rationality of f ,f11 (e, R̄1 , R−1 ) ∈ {y11 , e11 }.
By strategy-proofness of f , f11 (e, R̄1 , R−1 ) ̸= f11 (e, R̂1 , R−1 ) = y11 ; otherwise agent 1 has anincentive to misreport R̄1 at (R̂1 , R−1 ). Thus,
f11 (e, R̄1 , R−1 ) = e11 .

(9)Next, we show that (9) contradicts with one type endowments-swapping-proofness of f .
let ℓ be the step of the TTC algorithm at which agent 1 receives his type-1 object y11 . Let C
be the corresponding top trading cycle that involves agent 1, i.e., 1 ∈ SC .
Note that by Claim 1 and Fact 3, all top trading cycles that are obtained before step ℓ are
executed at f (e, R̄1 , R−1 ). Thus, by the definition of T T C, we know that for each agent in SC ,the object that he pointed at in C is his most preferred type-1 object among the unassigned
type-1 objects, i.e., for each i ∈ SC , all better type-1 objects for him, are assigned to someone
else via top trading cycles that are obtained before step ℓ.
Since y11 ̸= e11 (see (8)), |SC | > 1. We show a contradiction by induction on |SC |.
Induction basis. |SC | = 2. Without loss of generality, let C = (1 → e12 → 2 → e11 → 1). Since
f11 (e, R̄1 , R−1 ) = e11 (see (9)), agent 2 does not receive his most (feasible) preferred object e11 .
Consider that agents 1 and 2 swap their type-1 endowments, i.e., ê(t = 1, 1, 2). Note thatat this new endowment allocation, agent 1 owns e12 and agent 2 owns e11 . Consider that M ′ ≡(ê(t = 1, 1, 2), R̄1 , R−1 ).
Recall that R̄11 : y11 (= e12 = ê11 ), e11 (= ê12 ), . . ., and for agent 2, all type-1 objects that are better
than y21 (= e11 = ê12 ) are already assigned. Thus, By individual rationality of f , f11 (M ′ ) = ê11 = e12
and f21 (M ′ ) = ê12 = e11 . This implies that agents 1 and 2 are strictly better off by swapping their
type-1 endowments, which is in contradiction with one type endowments-swapping-proofness off.
The following induction arguments for K > 2 are similar to the induction basis part.
Induction hypothesis. Let K ∈ {2, . . . , n}. Suppose that C is executed when |SC | < K.

43

Induction step. Let |SC | = K. Without loss of generality, assume that SC = {1, . . . , K} andhence C = (1 → e12 → 2 → . . . → K − 1 → e1K → K → e11 → 1).
Recall that by (9), agent 1 receives his type-1 endowment and hence agent K does not receive
his most (feasible) preferred object e11 .
Consider that agents 1 and K swap their type-1 endowments, i.e., ê(t = 1, 1, K). Notethat at this new endowment allocation, agent 1 owns e1K and agent K owns e11 . Consider thatM ′ ≡ (ê(t = 1, 1, K), R̄1 , R−1 ).
Recall that for agent K, all type-1 objects that are better than e11 (= ê1K ) are already assigned.
Thus, By individual rationality of f , fK1 (M ′ ) = ê1K = e11 . Moreover, at M ′ , agent 1 is involvedin a (step ℓ) top trading cycle C ′ = (1 → e12 → 2 → . . . → K − 1 → e1K → 1). See the figure
below for the graphical explanation.
K −1

C′

RK−1

e1K

K

RK

e11

e1K−1

1

RK−2
K −2

R̄1
...

R2

2

e12

Since |SC ′ | = K − 1, by the induction hypothesis, C ′ is executed. Thus, f11 (M ′ ) = e12 . Thisimplies that agents 1 and K are strictly better off by swapping their type-1 endowments, whichis in contradiction with one type endowments-swapping-proofness of f .
Next, we show that f also assigns the cTTC allocation of type-2.
22Claim 3. For each (e, R) with R ∈ RN
π , f (e, R) = cT T C (e, R).

Proof. The proof is similar to Claim 1, the main difference is that instead of individual rationality, we use Claim 2.
Let C be a first step top trading cycle under T T C 2 at (e, R) which consists of a set of agentsSC ⊆ N .
Similar to Claim 1, we first show that C is executed at f (e, R) by induction on |SC |.
Induction basis. |SC | = 1. In this case, agent i ∈ SC points to his type-1 endowed object,i.e., C = (i → e2i → i). Thus, by Claim 2, C must be executed.
Induction hypothesis. Let K ∈ {2, . . . , n}. Suppose that C is executed when |SC | < K.

44

Induction step. Let |SC | = K. Without loss of generality, assume that SC = {1, . . . , K} andC = (1 → e22 → 2 → . . . → K → e21 → 1).
By contradiction, assume that C is not executed. Thus, there is an agent i ∈ SC who does
not receive e2i+1 , i.e., fi2 (e, R) ≠ e2i+1 .
Let R̂i ∈ Rπ be such that i only wants to receive one type-2 object e2i+1 rather than his
type-2 endowment, i.e.,R̂i2 : e2i+1 , e2i , . . . ,for each t ∈ T \ {2} : R̂it = Rit , andπ̂1 = π : 1, . . . , m.
Note that at R̂i , if i does not receive e2i+1 , then by Claim 2, he must receive his type-2
endowment e2i .
Let R̂ ≡ (R̂i , R−i ) and M̂i ≡ (e, (R̂i , R−i )). We proceed in two steps. Note that by Claim 1,
1
f (M̂i ) = cT T C 1 (M̂i ) = cT T C 1 (e, R) = f 1 (e, R).
Step 1. We show that agent i receives e21+1 under f at M̂i , i.e., fi2 (M̂i ) = e2i+1 .
By Claim 2, fi2 (M̂i ) ∈ {e2i+1 , e2i }. By strategy-proofness of f , fi2 (e, R) ̸= e2i+1 implies thatfi2 (M̂i ) ̸= e2i+1 , otherwise instead of Ri , agent i has an incentive to misreport R̂i at (e, R). Thus,
fi2 (Mi ) = e2i . Thus, agent i − 1 cannot receive e2i from agent i because it is assigned to agent i.
Overall, we find that2fi2 (M̂i ) = e2i ̸= e2i+1 and fi−1(M̂i ) ̸= e2i .

(10)Consider that agents i − 1 and i swap their type-2 endowments, i.e., ê(t = 2, i − 1, i). Notethat at this new endowment allocation, i − 1 owns his most preferred type-2 object e2i , and iowns e2i−1 , and recall that e2i−1 is agent (i − 2)’s most preferred type-2 object. Consider thatM̂i′ ≡ (ê(t = 2, i − 1, i), (R̂i , R−i )).
At M̂i′ , for type-2, there are two first step top trading cycles C ′ = (i − 1 → e2i → i − 1) andC ′′ = (1 → e22 → 2 → . . . → i − 2 → e2i−1 → i → e21+1 → i + 1 . . . → K → e21 → 1) at M̂i′ .
The graphical explanation is similar to the figure in Claim 1 and hence we omit it (the only
difference is that now the superscript is type-2).
Note that |SC ′ | = 1 and |SC ′′ | = K − 1. Thus, by the induction hypothesis, these two cycles
are executed under f at M̂i′ .
Hence, agents i − 1 and i receive their most preferred type-2 objects at f (M̂i′ ). By (10), we222find that fi−1(M̂i′ ) = e2i Pi−1
fi−1
(M̂i ) and fi2 (M̂i′ ) = e2i+1 Pi2 fi2 (M̂i ) . Moreover, by Claim 1, agentsi− and i still receive their cTTC allocation of type-1 at f (M̂i′ ). Therefore, fi−1 (M̂i′ )Pi−1 fi−1 (M̂i )and fi (M̂i′ ) Pi fi (M̂i ). However, this implies that f is not one type endowments-swapping proof,a contradiction.
Step 2. We show that agent i receives e2i+1 under f at (e, R), i.e., fi2 (e, R) = e21+1 .
45

Note that e21+1 is agent i’s most preferred type-2 object at Ri . By strategy-proofness of f ,fi (e, R) Ri fi (M̂i ). By Claim 1, fi1 (e, R) = fi1 (M̂i ). Hence, fi2 (e, R) Ri2 fi2 (M̂i ) = e2i+1 , which
implies that fi2 (e, R) = e2i+1 .
It suﬀices to show that C is executed at f (e, R) because once we have shown that agents who
trade at the first step of the TTC algorithm (of type-2) always receive their TTC allotments oftype-2 under f , we can consider agents who trade at the second step of the TTC (of type-2) byfollowing the same proof arguments as for first step trading cycles, and so on. Thus, the proofof Claim 3 is completed.
By Claim 1 and Claim 3, we know that for each (e, R) with R ∈ RN
π , the allocations of1
type-1 and type-2 under f are the same as cT T C allocation, i.e., f (e, R) = cT T C 1 (e, R) andf 2 (e, R) = cT T C 2 (e, R). By applying similar arguments, we can also show that f 3 (e, R) =cT T C 3 (e, R) and so on. Thus, we conclude that for each (e, R) with R ∈ RN
π , and each t ∈ T ,ttf (e, R) = cT T C (e, R), which completes the proof of Proposition 1.
Proof of Theorem 6 and 7
The proof of Theorem 6 will be shown by extending Proposition 1 to the full domain of lexicographic preference profiles.
Let S̄ ⊆ N and (e, R) be such that only agents in S̄ do no have restricted (but lexicographic)S̄
preferences, i.e., R−S̄ ∈ R−
π and for each i ∈ S̄, Ri ̸∈ Rπ . We show that f (e, R) = cT T C(e, R)
by induction on |S̄|.
We first consider the case that only agent i does no have restricted (but lexicographic)
preferences, i.e., S̄ = {i}. We will show that f still assigns the cTTC allocation.
Lemma 4. For each (e, R) ∈ Ml , each i ∈ N with Ri ̸∈ Rπ and R−i ∈ R−i
π , f (e, R) =cT T C(e, R).
The proof of Lemma 4 consists of four claims.
It is without loss of generality to assume that i = 1. Thus, R1 ∈ Rl and π1 ̸= π. Lety ≡ f (e, R) and x ≡ cT T C(e, R).
We first show that agent 1 still receives his cTTC allocation at R, i.e., y1 = x1 .
Claim 4. y1 = x1 .
Proof. Suppose not.
Let R̄1 ∈ Rπ be such that R̄1 and R1 are only different in the importance order, i.e., for eacht ∈ T , R̄1t = R1t , and π̄1 = π : 1, . . . , m. Note that (R̄1 , R−1 ) ∈ RN
π and hence by Proposition 1,
f (e, R̄1 , R−1 ) = cT T C(e, R) = x.
Note that if for each t ∈ T , xt1 R1t y1t , then agent 1 has an incentive to misreport R̄1 at R.
Thus, by strategy-proofness of f , there exists one type τ ∈ T such that y1τ P1τ xτ1 .
46

Note that by the definition of cT T C, xτ1 R1τ eτ1 and hence y1τ ̸= et1 . Overall, we havey1τ P1τ xτ1 R1τ eτ1 .

(11)

Let R̂1 ∈ Rπ be such that for each type t ∈ T , agent 1 positions y1t first and et1 second, i.e.,
for each t ∈ T : R̂1t : y1t , et1 , . . . ;π̂1 = π : 1, . . . , m
LetR̂ ≡ (R̂1 , R−1 ).
By strategy-proofness of f , f1 (e, R̂) = f1 (e, R) = y1 . Also note that R̂ ∈ RN
π . Hence, byττProposition 1, f (e, R̂) = cT T C(e, R̂). In particular, y1 = cT T C1 (e, R̂).
Next, we show that cT T C1τ (e, R̂) = eτ1 . By the definition of cT T C,
cT T C1τ (e, R̂) = T T C1τ (e1 , R̂τ ) ∈ {y1τ , eτ1 }.

(12)

Recall that cT T C τ (e, R) = T T C τ (eτ , Rτ ) = xτ and y1τ P1τ xτ1 R1τ eτ1 (see (11)). Thus, bystrategy-proofness of T T C, xτ1 = T T C1τ (e, Rτ ) R1τ T T C1τ (e, R̂τ ). Together with (12), we conclude
that T T C1τ (e, R̂τ ) = eτ1 . It implies that cT T C1τ (e, R̂1 , R−1 ) = eτ1 ̸= y1τ .
N \{1}

Note that Claim 4 implies that for each (e, R) with (R1 , R−1 ) ∈ (Rl \Rπ )×Rπ
, f1 (e, R) =cT T C1 (e, R).
Next, we show that y = x by applying similar arguments in Claims 1, 2, and 3.
N \{1}

Claim 5. For each (e, R) with (R1 , R−1 ) ∈ (Rl \ Rπ ) × Rπ

, f 1 (e, R) = cT T C 1 (e, R).

Proof. Let ℓ be the step of the TTC algorithm at which agent 1 receives type-1 object y11 (=x11 = cT T C11 (e, R)). Let C be the corresponding top trading cycle that involves agent 1, i.e.,
1 ∈ SC .
Note that by Claim 1 and Fact 3, all top trading cycles that are obtained before step ℓ are
executed at f (e, R). Moreover, if C is executed, then again by Claim 1 and Fact 3, all remaining
top trading cycles are also executed. Thus, it suﬀices to show that C is executed, i.e., for eachi ∈ SC , fi1 (e, R) = cT T Ci1 (e, R).
Since all top trading cycles that are obtained before step ℓ are executed, by the definition of
T T C, we know that for each agent in SC , the object that he pointed at in C is his most preferred
type-1 object among the unassigned type-1 objects, i.e., for each i ∈ SC , all better type-1 objects
for him, are assigned to someone else via top trading cycles that are obtained before step ℓ.
Similar to Claim 1, we show that C is executed at f (e, R) by induction on |SC |.
Induction basis. |SC | = 1. In this case, SC = {1}. By Claim 4, f11 (e, R) = cT T C11 (e, R).
Induction hypothesis. Let K ∈ {2, . . . , n}. Suppose that C is executed when |SC | < K.
47

Induction step. Let |SC | = K. Without loss of generality, assume that SC = {1, . . . , K} andC = (1 → e12 → 2 → . . . → K → e11 → 1).
By contradiction, assume that C is not executed. Thus, there is an agent i ∈ SC \ {1} who
does not receive e1i+1 , i.e., fi1 (e, R) ̸= e1i+1 .
Let R̂i ∈ Rπ be such that i only wants to receive one type-1 object e1i+1 than his type-1
endowment, i.e.,R̂i1 : e1i+1 , e1i , . . . ,for each t ∈ T \ {1} : R̂it = Rit , andπ̂1 = π : 1, . . . , m.
Note that at R̂i , if i does not receive e1i+1 , then by individual rationality of f , he must receive
his type-1 endowment e1i .
Let R̂ ≡ (R̂i , R−i ) and M̂i ≡ (e, (R̂i , R−i )). We proceed in two steps.
Step 1. We show that agent i receives e1i+1 under f at M̂i , i.e., fi1 (M̂i ) = e1i+1 .
Since R̂i ∈ Rl and f is individually rational, fi1 (M̂i ) ∈ {e1i+1 , e1i }. By strategy-proofness off , fi1 (e, R) ̸= e1i+1 implies that fi1 (M̂i ) ̸= e1i+1 , otherwise instead of Ri , agent i has an incentive
to misreport R̂i at (e, R). Thus, fi1 (M̂i ) = ei1 . Thus, agent i − 1 cannot receive e1i from agent i
because it is assigned to agent i.
Consider that agents i − 1 and i swap their type-1 endowments, i.e., ê(t = 1, i − 1, i). Notethat at this new endowment allocation, i − 1 owns his most (feasible) preferred type-1 object e1i ,and i owns e1i−1 , and recall that e1i−1 is agent (i − 2)’s most (feasible) preferred type-1 object.
Consider that M̂i′ ≡ (ê(t = 1, i − 1, i), (R̂i , R−i )).
At M̂i′ , there are two first step top trading cycles C ′ = (i − 1 → e1i → i − 1) and C ′′ = (1 →e12 → 2 → . . . → i − 2 → e1i−1 → i → e11+1 → i + 1 . . . → K → e11 → 1) at M̂i′ . The graphicalexplanation is exactly the same as the figure in Claim 1.
Note that |SC ′ | = 1 and |SC ′′ | = K − 1. Thus, by the induction hypothesis, these two cycles
are executed under f at M̂i′ .
Hence, agents i − 1 and i receive their most (feasible) preferred type-1 objects at f (M̂i′ ).
1
1
1
Thus, fi−1(M̂i′ ) = e1i Pi−1
fi−1
(M̂i ) and fi1 (M̂i′ ) = e1i+1 Pi1 fi1 (M̂i ). Therefore, fi (M̂i′ ) Pi fi (M̂i ) andfi−1 (M̂i′ ) Pi−1 fi−1 (M̂i ).39 However, this implies that f is not one type endowments-swapping
proof, a contradiction.
Step 2. We show that agent i receives e1i+1 under f at (e, R), i.e., fi1 (e, R) = e1i+1 .
Note that e1i+1 is agent i’s most (feasible) preferred type-1 object at Ri . By strategy-proofnessof f , fi (e, R)Ri fi (M̂i ). Hence, fi1 (e, R)Ri1 fi1 (M̂i ) = e1i+1 , which implies that fi1 (e, R) = e1i+1 .
Note that this is also true for i − 1 = 1. Because by Claim 4, agent 1 always receives his cTTC allocationof other types, i.e., for each t ̸= 1, cT T C1t (e, R) = f1t (e, R) = f1t (M̂i ) = f1t (M̂i′ ).
39

48

The next two claims, Claims 6 and 7, can be proven by a similar way to Claim 2 and 3,
respectively. Thus, we omit the proofs. Note that the key point is that since agent 1 still receives
his cTTC allocation, we only need to show that agents who still have restricted preferences, will
also receive their cTTC allocation. Thus the proofs of Claim 2 and 3 are still valid for the casewhere only agent 1 does not have restricted preferences.
N \{1}

Claim 6. For each (e, R) with (R1 , R−1 ) ∈ (Rl \ Rπ ) × Rπ

, and each i ∈ N , fi2 (e, R) Ri2 e2i .

N \{1}

Claim 7. For each (e, R) with (R1 , R−1 ) ∈ (Rl \ Rπ ) × Rπ

, f 2 (e, R) = cT T C 2 (e, R).

Thus, similar to the proof of Proposition 1, by Claims 4, 5, 6, and 7, we conclude that forS̄each (e, R) ∈ Ml , and each S̄ ⊆ N , such that |S̄| = 1 and R−S̄ ∈ R−
π , f (e, R) = cT T C(e, R).
Thus, the proof of Lemma 4 is completed.
Now, we are ready to prove Theorem 6. Let (e, R) ∈ Ml and S̄ ⊆ N be such that exactly
only agents in S̄ have non restricted (but lexicographic) preferences, we show that f (e, R) =cT T C(e, R).
S̄
Lemma 5. For each (e, R) ∈ Ml and each S̄ ⊆ N such that R−S̄ ∈ R−
π , f (e, R) = cT T C(e, R).

The proof of Lemma 5 is showing by induction on |S̄|.
Induction basis. |S̄| = 1. This is done by Lemma 4.
Induction hypothesis. Let K ∈ {2, . . . , n}. Suppose that f (e, R) = cT T C(e, R) when|S̄| < K.
Induction step. Let |S̄| = K. Similar to Lemma 4, the proof of this part consists of four
claims.
We first show that agents in S̄ still receive their cTTC allotments.
S̄Claim 8. For each (e, R) with (RS̄ , R−S̄ ) ∈ (Rl \ Rπ )S̄ × R−
π , and each i ∈ S̄, fi (e, R) =cT T Ci (e, R).

Proof. Let y ≡ f (e, R) and x = cT T C(e, R). By contradiction, assume that there is an agenti ∈ S̄ who does not receive his cTTC allotment xi . Without loss of generality, assume that i = 1.
Let R̄1 ∈ Rπ be such that R̄1 and R1 are only different in the importance order, i.e., for eacht ∈ T , R̄1t = R1t , and and π̄1 = π : 1, . . . , m. Let R̄ ≡ (R̄1 , R−1 ).
Note that at R̄, there are only K − 1 agents (in S̄ \ {1}) who have non restricted (butlexicographic) preferences. Thus, by the induction hypothesis and the definition of cT T C,
f (e, R̄) = cT T C(e, R̄) = cT T C(e, R) = x. Then, the remaining proof is exactly the sameas the proof of Claim 4.
Note that if for each t ∈ T , xt1 R1t y1t , then agent 1 has an incentive to misreport R̄1 at R.
Thus, by strategy-proofness of f , there exists one type τ ∈ T such that y1τ P1τ xτ1 .
49

Note that by the definition of cT T C, xτ1 R1τ eτ1 and hence y1τ ̸= et1 . Overall, we havey1τ P1τ xτ1 R1τ eτ1 .

(13)

Let R̂1 ∈ Rπ be such that for each type t ∈ T , agent 1 positions y1t first and et1 second, i.e.,
for each t ∈ T : R̂1t : y1t , et1 , . . . ;π̂1 = π : 1, . . . , m
LetR̂ ≡ (R̂1 , R−1 ).
Note that R̂ ∈ RN
π .
By strategy-proofness of f , f1 (e, R̂) = f1 (e, R) = y1 . Hence, by Proposition 1, f (e, R̂) =cT T C(e, R̂). In particular, y1τ = cT T C1τ (e, R̂).
Next, we show that cT T C1τ (e, R̂) = eτ1 . By the definition of cT T C,
cT T C1τ (e, R̂) = T T C1τ (e1 , R̂τ ) ∈ {y1τ , eτ1 }.

(14)

Recall that cT T C τ (e, R) = T T C τ (eτ , Rτ ) = xτ and y1τ P1τ xτ1 R1τ eτ1 (see (13)). Thus, bystrategy-proofness of T T C, xτ1 = T T C1τ (e, Rτ ) R1τ T T C1τ (e, R̂τ ). Together with (14), we conclude
that T T C1τ (e, R̂τ ) = eτ1 . It implies that cT T C1τ (e, R̂1 , R−1 ) = eτ1 ̸= y1τ .
The following three claims can be proven by a similar way to 5, 6, and 7, respectively. Thus,
we omit the proofs. Note that the key point is that since agents in S̄ still receive their cTTC
allocation, we only need to show that agents who still have restricted preferences, will also receive
their cTTC allocation. Thus the proofs of Claim 6 and 7 are still valid for the case where only
agents in S̄ do not have restricted preferences.
S̄
1
1
Claim 9. For each (e, R) with (RS̄ , R−S̄ ) ∈ (Rl \ Rπ )S̄ × R−
π , f (e, R) = cT T C (e, R).
2 22S̄Claim 10. For each (e, R) with (RS̄ , R−S̄ ) ∈ (Rl \ Rπ )S̄ × R−
π , and each i ∈ N , fi (e, R) Ri ei .
22S̄Claim 11. For each (e, R) with (RS̄ , R−S̄ ) ∈ (Rl \ Rπ )S̄ × R−
π , f (e, R) = cT T C (e, R).

Hence, we conclude that for each (e, R) ∈ Ml , and each S̄ ⊆ N , such that |S̄| = K andS̄
R−S̄ ∈ R−
π , f (e, R) = cT T C(e, R). Thus, the proof of Lemma 5 is completed. Therefore,
Theorem 6 is proven by applying Lemma 5 with S̄ = N .
Theorem 7 can be proven by exactly the same way to Theorem 6. That is, we first showthat f assigns the cTTC allocation if only one agent does not have lexicographic (but separable)
preferences. Then, by applying this preference replacement argument, one by one, for all otheragents, we conclude that f equals cTTC on the domain of separable preference profiles. Notethat in the proof of Lemmas 4 and 5, for each agent in S̄, we only use the characterization ofhis marginal preferences. Thus the proof of Lemmas 4 and 5 are still valid for the case where
only agents in S̄, do not have lexicographic (but separable) preferences.
50

Proof of Theorem 8
Proof. Consider markets with two types, i.e., T = {1, 2}.
Suppose that there is a mechanism f : R → X that is one type endowments-swapping-proof,
individually rational, and strategy-proof.
Let x, y ∈ X\{e} be such that at x agents 1 and 2 swap their endowments of type 2, i.e.,
x1 = (e11 , e22 ),x2 = (e12 , e21 ),and for each i = 3, . . . , n,xi = ei

and at y agents 1 and 2 swap their endowments of type 1, i.e.,y1 = (e12 , e21 ),y2 = (e11 , e22 ),and for each i = 3, . . . , n,y i = ei .

Obviously, x ̸= y.
Let R ∈ RN be such that agents 1 and 2 prefer only their allotments at x and y to theirendowments, they disagree on which allocation is the better one, and each other agent ranks her
endowments highest, i.e.,
R1 : x1 , y1 , e1 , . . . ,R2 : y2 , x2 , e2 , . . . ,and for each i = 3, . . . , n,Ri : ei , . . . .

Note that R ∈ RN \ RN
s . There are only three individually rational allocations at (e, R): x, y,and e. Also note that ê(t = 1, {1, 2}) = y and ê(t = 2, {1, 2}) = x. By individually rationalityof f , f (e, R) ∈ {x, y, e} andf (ê(t = 1, {1, 2}), R) = y and f (ê(t = 2, {1, 2}), R) = x.

(15)

Let
• R1′ : x1 , e1 , . . ., and• R2′ : y2 , e2 , . . ..
Note that by individually rationality of f and (15),f (ê(t = 1, {1, 2}), R2′ , R−2 ) = y and f (ê(t = 2, {1, 2}), R1′ , R−1 ) = x.

51

(16)

Suppose that f (e, R) = e. Then, agents {1, 2} can be strictly better off by swapping theirendowments of type-1 (see (15)), which contradicts one type endowments-swapping-proofness of
f . Therefore, f (e, R) ∈ {x, y}.
Suppose that f (e, R) = y. Then, by strategy-proofness of f , f1 (e, R1′ , R−1 ) ̸= x1 and hence,by individual rationality of f , f (e, R1′ , R−1 ) = e. However, this violates one type endowmentsswapping-proofness of f because agents {1, 2} can be strictly better off by swapping their endowments of type-2 (see (16)).
Suppose that f (e, R) = x. Then, by strategy-proofness of f , f2 (e, R2′ , R−2 ) ̸= y2 and hence
by individual rationality of f , f (e, R2′ , R−2 ) = e. However, this violates one type endowmentsswapping-proofness of f because agents {1, 2} can be strictly better off by swapping their endowments of type-1 (see (16)).

A.7

Proof of Theorem 9

Ekici (2022) shows that the TTC mechanism satisfies pairwise eﬀiciency for Shapley-Scarf housing markets. By using similar arguments we also obtain that bTTC inherits pairwise eﬀiciency
from the underlying top trading cycles algorithm for the restricted market (e, R|e ). So we only
show that bTTC is the only mechanism satisfying all our properties in Theorem 9.
Note that in the proof below, we do not consider any endowments-swapping. Thus, fromnow and until the end of the proof, we will denote a market simply by its preference profile.
Moreover, we only show the first part of Theorem 9, i.e., the characterization for lexicographic
preferences, as the extensions to separable preferences and strict preferences can be proven byexactly the same way to Theorems 4 and 5.
Let f : Ml → X be individually rational, strategy-proof, non-bossy, and pair-eﬀicient. Notethat by Lemma 1, f is monotonic.
Similar to the proof of Theorem 3, we show that all first step top trading cycles are fully
executed.
First, we show that if a first step top trading cycle is formed by only one or two agents, thenit is fully executed.
Lemma 6. If a mechanism f : Ml → X is individually rational, strategy-proof, non-bossy, andpair-eﬀicient, then for each R ∈ RN
l , each first step top trading cycle C(∈ C(R) with |SC | ≤ 2,
C is fully executed under f at R.
Proof. Let C ∈ C(R) be a first step top trading cycle that consists of agents SC with |SC | ≤ 2.
We show it by two steps. First, we show that C is executed.
Claim 12. C is executed.
Proof. When |SC | = 1. In this case, agent i ∈ SC points to one of his endowed object, i.e.,
ci = etii and hence C = (i → ci → i). Since preferences are lexicographic, i.e., Ri ∈ Rl , agent i52will be strictly worse off if he receives any other type-ti objects. Thus, C must be executed byindividual rationality of f .
When |SC | = 2. Without loss of generality, assume that SC = {1, 2}. By contradiction,
assume that C is not executed. Thus, there is an agent i ∈ SC does not receive his most
preferred object ci . Without loss of generality, let i = 2.
Let R̂2 be such that agent 2 only wants to receive type-t2 object c2 and no other objects, i.e.,R̂2t2 : c2 (= et12 ), et22 , . . . ,for each t ∈ T \ {t2 } : R̂2t : et2 , . . . , andπ̂2 = π2 : t2 , . . . .
Note that at R̂2 , if 2 does not receive c2 , then from individual rationality of f , he must receive
his full endowment e2 . LetR̂ ≡ (R̂2 , R−2 ).
By individual rationality of f , f2t2 (R̂) ∈ {c2 , et22 }. By strategy-proofness of f , f2t2 (R) ̸= c2
implies that f2t2 (R̂) ̸= c2 , otherwise instead of R2 , agent 2 has an incentive to misreport R̂2 at
R. Thus, f2t2 (R̂) = et22 . Then, by individual rationality of f , f2 (R̂) = e2 . Thus, agent 1 cannot
receive c1 (∈ e2 ) from agent 2 because it is assigned to agent 2.
Let R̄1 be such that be such that agent 1 only wants to receive type-t1 object c1 and no otherobjects, i.e.,R̄1t1 : c1 (= et21 ), et11 , . . . ,for each t ∈ T \ {t1 } : R̄1t : et1 , . . . andπ̄1 = π̂1 = π1 : t1 , . . . .
Note that at R̄1 , if agent 1 does not receive c1 , then from individual rationality of f , he mustreceive his full endowment e1 . LetR̄ ≡ (R̄1 , R̂2 , R̂3 , . . . , R̂n ) = (R̄1 , R̂2 , R3 , . . . , Rn ).
To obtain the contradiction, we show that at R̄, agent 1 receives c1 and agent 2 receives c2 ,i.e., f1t1 (R̄) = c1 = et21 and f2t2 (R̄) = c2 = et12 .
By individual rationality of f , f1t1 (R̄) ∈ {c1 , et11 }. By strategy-proofness of f , f1t1 (R̂) ̸= c1
̸ c1 , otherwise instead of R̂1 , agent 1 has an incentive to misreport R̄1 at
implies that f1t1 (R̄) =t1
R̂. Thus, f1 (R̄) = et11 . Then, by individual rationality of f , f1 (R̄) = e1 , and in particular,
f1t2 (R̄) = et12 = c2 . Moreover, by individual rationality of f , f2 (R̄) = e2 , and in particular,
f2t1 (R̄) = et21 = c1 . This implies that f2t1 (R̄) P1t1 f1t1 (R̄) and f1t2 (R̄) P2t2 f2t2 (R̄) and hence f2 (R̄) P1
f1 (R̄) and f1 (R̄) P2 f2 (R̄), in which contradicts with pair-eﬀiciency of f .
53

Overall, by contradiction we show that at R̄, agent 1 receives c1 . Thus, by strategy-proofnessof f , he also receives c1 at R̂; otherwise he has an incentive to misreport R̄1 at R̂. Together
with individual rationality of f , it implies that agent 2 receives c2 at R̂. Therefore, by strategyproofness of f , agent 2 also receives c2 at R; otherwise he has an incentive to misreport R̂1 at
R.
Next, we show that C is fully executed. There are two cases.
Case 1. |SC | = 1. In this case, agent i ∈ SC points to one of his endowed object, i.e., ci ∈ ei .
Without loss of generality, assume that SC = {1} and π1 : t1 , . . .. Thus, C = (1 → et11 → 1).
Let y ≡ f (R). By contradiction, suppose that y1 ̸= e1 . Note that by Lemma 2, y1t1 = et11 .
Let t ∈ T \ {ti } be such that y1t ̸= et1 . Without loss of generality, assume that agent 1 receives
agent 2’s endowment of type-t at y, i.e., y1t = et2 .
Let R̂ ∈ RN
l be such that each agent j positions yj at the top and changes his importanceorder as π1 , i.e., for each agent j ∈ N , (i) π̂j = π1 : t1 , . . ., and (ii) for each τ ∈ T , R̂jτ : yjτ , . . .
By monotonicity of f , f (R̂) = y.
Let R̄2 be such thatπ̄2 = π̂2 (= π1 ),R̄2t1 : et11 , y2t1 , . . . , andFor each τ ∈ T \ {t1 }, R̄2τ = R̂2τ .
Let
R̄ ≡ (R̄2 , R̂−2 ).
Note that by strategy-proofness of f , for type-t1 , agent 2 either receives et11 or y2t1 ; otherwise
he has an incentive to misreport R̂2 at R̄. Moreover, C is still a first top trading cycle at R̄, i.e.,C ∈ C(R̄). Thus, by Claim 12, C is executed and hence agent 1 receives et11 at f (R̄). See thefigure below for the graphical explanation.
1

R̂1

et11

R̄2

et2

2

Thus, agent 2 still receives y2t1 , and hence by Fact 2,
f (R̄) = f (R̂) = y and particularly, f1t1 (R̃) = y1t1 = et11 .
54

(17)

Let R̃1 be such that agent 1 only changes his importance order as t is the most important,i.e., π̃1 : t, . . . and R̃1 = (R̂11 , . . . , R̂1m , π̃1 ).
Let
R̃ ≡ (R̃1 , R̄−1 ).
By monotonicity of f , f (R̃) = f (R̄) = y. However, at R̃, there is a first step top trading
cycle C ′ ∈ C(R̃) consisting of agents 1 and 2, i.e., C ′ = (1 → et2 (= y1t ) → 2 → et11 → 1). See thefigure below for the graphical explanation.
et11

1

R̄2

R̃1

et2

2

By Claim 12, C ′ is executed under f at R̃. Thus, f2t1 (R̃) = et11 , which contradicts with thefact that f1t1 (R̃) = y1t1 = et11 (see (17)).
Case 2. |SC | = 2. Without loss of generality, assume that SC = {1, 2}. Thus, C = (1 → c1 (=et21 ) → 2 → c2 (= et12 ) → 1). By contradiction, assume that C is not executed. Without loss ofgenerality, assume that agent 1 does not receive agent 2’s full endowments, i.e., f1 (R) ̸= e2 . Notethat by Claim 12, f1t1 (R) = c1 = et21 . Thus, there is a type t ∈ T \ {t1 } such that f1t (R) ̸= et2 .
Without loss of generality, assume that agent 1 receives agent i’s endowment of type-t, i.e.,f1t (R) = eti . Let y ≡ f (R). There are two sub-cases.
Sub-case 1. i = 1. Let R̂1 be such thatfor eacht ∈ T, R̂1t : y1t , . . . , andπ̂1 (t) = 1.
By monotonicity of f , f (R̂1 , R−1 ) = f (R) = y. Then, we are back to Case 1.
Sub-case 2. i ̸= 1. Without loss of generality, assume that i = 3. Thus, y2t2 = et12 , y1t1 = et21 , and
y2t = et3 . We will obtain a contradiction to complete the proof of this sub-case. Let R̂3 be suchthat
R3t2 : et12 , y3t2 , . . .
for eacht ∈ T \ {t2 }, R̂3t : y3t , . . . , andπ̂3 (t) = t2 .
LetR̂ ≡ (R̂3 , R−3 ).
55Note that C is still a first step top trading cycle at R̂, i.e., C ∈ C(R̂). Thus, by Claim 12, C
is executed. See the figure below for the graphical explanation.
et3

1

3

et12

R̂3

R̂1 (= R1 )

R̂2 (= R2 )

et21

2

Hence, agent 3 cannot receive et12 (= c2 ). Thus, by strategy-proofness of f , he still receives y3 ,i.e., f3 (R̂) = y3 . Therefore, by non-bossiness of f , f (R̂) = y.
Let R̄1 be such thatfor each t ∈ T, R̄1t : y1t , . . . , andπ̄1 (t) = 1.
LetR̄ ≡ (R̄1 , R̂−1 ).
Then, since R̄1 is a monotonic transformation of R̂1 at y, f (R̄) = y. In particular,
f2t1 (R̄) = et12 (= c2 ).

(18)

Note that at R̄, there is a first step top trading cycle C ′ = (1 → y1t (= et3 ) → 3 → et12 → 1)that involves two agents. Thus, by Claim 12, C ′ is executed. See the figure below for thegraphical explanation.
et3

3

R̄1

R̄3 (= R̂3 )

et21

1

et12

R̄2 (= R2 )2

It implies that f3t2 (R̄) = et12 , which contradicts with f (R̄) = y = f (R̂) and (18).
Now we are ready to show that all first step top trading cycles are fully executed.
Lemma 7. If a mechanism f : Ml → X is individually rational, strategy-proof, non-bossy,
and pair-eﬀicient, then for each R ∈ RN
l , each first step top trading cycle C(∈ C(R)) is fully
executed under f at R.
56

Proof. Let C ∈ C(R) be a first step top trading cycle that consists of agents SC ⊆ N . We prove
this lemma by induction on SC .
Induction Basis. |SC | ≤ 2. This is done by Lemma 6.
Induction hypothesis. Let K ∈ {3, . . . , n}. Suppose that C is fully executed when |SC | < K.
Induction step. Let |SC | = K. Without loss of generality, assume that SC = {1, . . . , K} andC = (1 → c1 → 2 → c2 → . . . → K → cK → 1).
Similar to Lemma 6, we first show that C is executed.
Claim 13. C is executed.
Proof. By contradiction, assume that C is not executed. Thus, there is an agent i ∈ SC who
does not receive ci , i.e., fiti (e, R) ̸= ci . Without loss of generality, let i = 2.
Let R̂2 be such that agent 2 only wants to receive type-t2 object c2 and no other objects, i.e.,R̂2t2 : c2 (= et32 ), et22 , . . . ,for each t ∈ T \ {t2 } : R̂2t : et2 , . . . , andπ̂2 = π2 : t2 , . . . .
Note that at R̂2 , if agent 2 does not receive c2 , then from individual rationality of f , he mustreceive his full endowment e2 .
Let R̂ ≡ (R̂2 , R−2 ). We proceed in two steps.
Step 1. We show that agent 2 receives c2 under f at R̂, i.e., f2t2 (R̂) = c2 .
By individual rationality of f , f2t2 (R̂) ∈ {c2 , et22 }. By strategy-proofness of f , f2t2 (R) ̸= c2
implies that f2t2 (R̂) ̸= c2 , otherwise instead of R2 , agent 2 has an incentive to misreport R̂2 at
R. Thus, f2t2 (R̂) = et22 . Then, by individual rationality of f , f2 (R̂) = e2 . Thus, agent 1 cannot
receive c1 (∈ e2 ) from agent 2 because it is assigned to agent 2.
Let y ≡ f (R̂). Overall, we find thaty2 = e2 and y1t1 ̸= c1 (= et21 ).
Let R̄1 be such thatR̄1t1 : c1 (= et21 ), et31 , et11 , . . . ,for each t ∈ T \ {t1 } : R̄1t := R̂1t (= R1t ) andπ̄1 = π̂1 = π1 .
Note that R̄1 and R̂1 only differ in type-t1 marginal preferences. LetR̄ ≡ (R̄1 , R̂2 , R̂3 , . . . , R̂n ).
57

(19)

To obtain the contradiction, we want to show that at R̄, agent 1 receives c1 and agent 2
receives c2 , i.e., f1t1 (R̄) = c1 = et21 and f2t2 (R̄) = c2 = et32 .
By individual rationality of f , f1t1 (R̄) ∈ {et21 , et31 , et11 }. By strategy-proofness of f , f1t1 (R̂) ̸= et21
implies that f1t1 (R̄) ̸= et21 , otherwise instead of R̂1 , agent 1 has an incentive to misreport R̄1 atR̂.
Thus, f1t1 (R̄) ∈ {et31 , et11 }. Next, we show that f1t1 (R̄) = et31 = c2 and f1 (R̄) = e3 .
Let R̃1 be such thatR̃1t1 : et31 , et11 , . . . ,for each t ∈ T \ {t1 } : R̃1t := R̄1t (= R1t ) andπ̃1 = π̄1 = π̂1 = π1 .
Since f1t1 (R̄) ̸= c1 , R̃1 is a monotonic transformation of R̄1 at f (R̄). Thus,
f (R̄) = f (R̃1 , R̄−1 ).

(20)Note that at (R̃1 , R̄−1 ), there is a first step top trading cycle C ′ = (1 → et31 → 3 → c3 →. . . → K → cK → 1). Since C ′ ∈ C(R̃1 , R̄−1 ) and |SC ′ | = K − 1, by the Induction hypothesis, C ′is fully executed. Thus, f1 (R̃1 , R̄−1 ) = e3 , and in particular, f1t2 (R̃1 , R̄−1 ) = et32 = c2 . Together
with (20), we conclude that f1t1 (R̄) = et31 = c2 and f1 (R̄) = e3 . Therefore, f2t2 (R̄) ̸= et31 = c2 .
Hence, by individual rationality of f , f2 (R̄) = e2 , and in particular, f2t1 (R̄) = et21 = c1 .
This implies that c1 = f2t1 (R̄) P̄1t1 f1t1 (R̄) and c2 = f1t2 (R̄) P̄2t2 f2t2 (R̄). Hence, f2 (R̄) P̄1 f1 (R̄)
and f1 (R̄) P̄2 f2 (R̄), in which contradicts with pair-eﬀiciency of f .
Overall, by contradiction we show that at R̄, agent 1 receives c1 . Together with individual
rationality of f , it implies that agent 2 receives c2 at R̄. Subsequently, by strategy-proofnessof f , agent 1 also receives c1 at R̂; otherwise he has an incentive to misreport R̄1 at R̂. Again,
together with individual rationality of f , it implies that agent 2 receives c2 at R̂.
Step 2. We show that agent 2 receives c2 under f at R, i.e., f2t2 (R) = c2 .
Note that c2 is agent 2’s most preferred type-t2 object at R2 . By strategy-proofness of f ,f2 (R) R2 f2 (R̂). Hence, f2t2 (R) R2t2 f2t2 (R̂), which implies that f2t2 (R) = c2 .
Next, we show that C is fully executed. The proof is similar to the induction step part ofLemma 3.
Let x ≡ bT T C(R), y ≡ f (R). Note that if C is fully executed, then for each i ∈ SC ,yi = fi (R) = xi .
By contradiction, suppose that there is an agent i ∈ SC such that yi ̸= xi . Without loss ofgenerality, let i = 1. By Claim 13, C is executed under f at R. In particular,tK= et1K = xtKK .
y1t1 = et21 = xt11 and yK

58

(21)

Since y1 ̸= x1 (= e2 ), there is a type t ∈ T \ {t1 } and an agent j ̸= 2 such that y1t = etj . There
are two cases.
Case 1: j ∈ SC . Let R̂1 such that agent 1 positions y1 at the top and moves t to the mostimportant, i.e., (i) π̂1 : t, . . .; and (ii) for each τ ∈ T , R̂1τ : y1τ , . . .. Since R̂1 is a monotonic
transformation of R1 at y, we havef (R̂1 , R−1 ) = f (R) = y and particularly, f1t1 (R̂1 , R−1 ) = et21 .

(22)

t

j
Note that there is a first step top trading cycle C ′ ≡ (1 → etj → j → ej+1
→ j + 1 → ··· →tK′′
K → e1 → 1) at (R̂1 , R−1 ). i.e., C ∈ C(R̂1 , R−1 ). Since j ̸= 2, cycle C contains less than K
agents. There are two sub-cases.
Sub-case one: K = 2. j ∈ SC implies That j = 1 and C ′ = (1 → et1 → 1), then we are backto the situation in the induction basis, see the figure below for the graphical explanation.

1

R̂1

et11

R2

et2

2

Thus, by the the induction basis, f1 (R̂1 , R−1 ) = e1 and hence f1t1 (R̂1 , R−1 ) = et11 , which contradicts with the fact that f1t1 (R̂1 , R−1 ) = et21 (see (22)).
Sub-case two: K > 2. By the induction hypothesis, cycle C ′ is fully executed at f (R̂1 , R−1 ).
Therefore, f1 (R̂1 , R−1 ) = ej and hence f1t1 (R̂1 , R−1 ) = etj1 , which contradicts with the fact thatf1t1 (R̂1 , R−1 ) = et21 (see (22)).
Case 2: j ̸∈ SC . Let R̂j be such that (i) π̂j : tK , . . .; (ii) R̂jtK : et1K , yjtK , . . .; and (iii) for eachτ ∈ T \{tK }, R̂jτ : yjτ , . . ..
LetR̂ ≡ (R̂j , R−j ).
Note that C is still a first step top trading cycle at R̂, and hence, by Claim 13, C is executed.
In particular, with (21), we havetK
fKtK (R̂) = yK
= et1K .

(23)

So, agent j does not receive et1K at f (R̂). So, by strategy-proofness of f , fj (R̂) = yj ; otherwise
he has an incentive to misreport Rj at R̂. So, by non-bossiness of f , f (R̂) = y.

59Let R̄1 be such that agent 1 positions y1 at the top and moves t to the most important, i.e.,(i) π̄1 : t, . . .; and (ii) for each τ ∈ T , R̄1τ : y1τ , . . .. LetR̄ ≡ (R̄1 , R̂−1 ).
Since R̄1 is a monotonic transformation of R̂1 (= R1 ) at y, we havef (R̄) = y and particularly, fKtK (R̄) = et1K .

(24)

Note that C ′ ≡ (1 → y1t (= etj ) → j → et1K → 1) is a first step top trading cycle at R̄, i.e.,C ′ ∈ C(R̄). See the figure below for the graphical explanation.
et1K

1

R̄1

R̄j (= R̂j )etj

jThus, by Claim 13, cycle C ′ is executed at f (R̄). Therefore, fjtK (R̄) = et1K . Since j ̸∈ SC , thiscontradicts with the fact that fKtK (R̂) = et1K (see (24)).
By Lemma 7, we have shown that agents who trade at step 1 of the bTTC algorithm always
receive their bTTC allotments under f . Next, we can consider agents who trade at step 2 of thebTTC algorithm by following the same proof arguments as for first step trading cycles, and soon. Thus, the proof of Theorem 9 is completed.

B

Appendix: independence of the properties

We provide several examples to establish the logical independence of the properties in our characterization results. We label examples by the property/properties that is/are not satisfied.

60

Mechanisms
IR
SP
NB
FESP
BESP
OESP
PE
pE
CE

no-trade
+
+
+
−
−
−
−
−
−

SD
−
+
+
+
+
+
+
+
+

bTTC
+
+
+
−
+
−
−
+
−

cTTC
+
+
+
−
−
+
−
−
+

Example 9
+
−
+
−
+
−
−
+
−

Example 10
+
+
−
−
+
−
−
+
+

Example 13
+
−
+
−
−
+
−
−
+

Satisfaction of properties of mechanisms. SD denotes the serial dictatorship mechanism. The notation “+” (“−”) in a cell means that the property is satisfied (violated) by thecorresponding mechanism.
Abbreviations in the first column respectively refer to individual rationality, strategyproofness, non-bossiness, flex endowments-swapping-proofness, bundle endowments-swappingproofness, one type endowments-swapping-proofness, Pareto eﬀiciency, pairwise eﬀiciency, andcoordinatewise eﬀiciency.

B.1

Theorem 1

The following examples establish the logical independence of the properties in Theorem 1.
Example 3 (Flexible endowments-swapping-proofness).
The no-trade mechanism that always assigns the endowment allocation to each market is individually rational, group strategy-proof (and hence strategy-proof, and non-bossy), but not
flexibly endowments-swapping-proof.
⋄
Example 4 (Individual rationality).
By ignoring property rights that are established via the endowments, we can easily adjust thewell-known mechanism of serial dictatorship to our setting: based on an ordering of agents, we
let agents sequentially choose their allotments. Serial dictatorship mechanisms have been shownin various resource allocation models to satisfy Pareto eﬀiciency, group strategy-proofness (andhence strategy-proofness, and non-bossiness), and flexible endowments-swapping-proofness (andhence bundle endowments-swapping-proofness and one type endowments-swapping-proofness);since property rights are ignored, they violate individual rationality.
⋄
As we mentioned earlier in the main text, the independence of strategy-proofness from theother properties in Theorem 1 is an open problem.

61

B.2

Theorem 2

The following examples establish the logical independence of the properties in Theorem 2.
Example 5 (Strategy-proofness).
Sikdar et al. (2017) prove that there is an extension of the TTC mechanism, the mTTC mechanism, is strictly core-stable (and hence pairwise weakly stable) but not Strategy-proof.
⋄

Example 6 (Pairwise weak stability).
Same as example 3, the no-trade mechanism is and individually rational and Strategy-proof, but
not pairwise weakly stable.
⋄

B.3

Theorems 3, 4, and 5

The following examples establish the logical independence of the properties in Theorem 3.
Example 7 (Bundle endowments-swapping-proofness).
Same as example 3, the no-trade mechanism is individually rational, Strategy-proof, and nonbossy, but not bundle endowments-swapping-proof.
⋄

Example 8 (Individual rationality).
Same as example 4, serial dictatorship mechanisms are strategy-proof, non-bossy, and bundle
endowments-swapping-proof, but not individually rational.
⋄
Example 9 (Strategy-proofness).
We adapt (Fujinaka and Wakayama, 2018, Example 9) to our multiple-type housing markets.
We first introduce their original example for Shapley-Scarf housing markets.
Let N = {1, 2, 3} and consider a set of markets M̂ ⊊ M such that for each (e, R) ∈ M̂Ri : ej , . . . ;Rj : ei , ek , ej ;Rk : ei , ej , ek .
Let f be a mechanism such that for each (e, R) ∈ M̂,fi (e, R) = ej ;fj (e, R) = ek ;fk (e, R) = ei ;otherwise f (e, R) = T T C(e, R).
62

Fujinaka and Wakayama (2018) show that this mechanism satisfies individual rationality,
Pareto eﬀiciency (and hence pairwise eﬀiciency), non-bossiness, and endowments-swappingproofness but violates strategy-proofness.
We extend f from Shapley-Scarf housing markets to multiple-type housing markets. Let
h be the mechanism that stipulates completely bundle trade through f in all types. Since fsatisfy individual rationality and non-bossiness, h satisfies these two properties as well. Since f
is endowments-swapping-proof but not strategy-proof, h is bundle endowments-swapping-proof
but not strategy-proof.
⋄
Example 10 (Non-bossiness).
Consider markets with three agents and two types, i.e., N = {1, 2, 3} and T = {1, 2}.
Let M̂ ⊊ Ml be a set of markets such that for each (e, R) ∈ M̂, R1 |e is such that there is anagent i ∈ {2, 3} and agent 1 positions agent i’s full endowment at the top, i.e., for each t ∈ T ,R1t : eti , . . ..
Let y ∈ X be such that (i) y1 = ei , (ii) yi = (e11 , e2j ) and yj = (e1j , e21 ), where {i, j} = {2, 3}.
Let f be such that{y, (e, R) ∈ M̂ and y Pareto dominates bT T C(e, R),f (e, R) =bT T C(e, R),
otherwise.
Note that for (e, R) ∈ M̂, if f1 (e, R) ̸= ei , then there is an agent k ∈ {2, 3} (possibly k = i)
who receives ei and prefers ei to yk , i.e., fk (e, R) = bT T Ck (e, R) = ei Pk yk .
It is easy to see that f is individually rational and bossy. We show that f is strategy-proof
and bundle endowments-swapping-proof.
Strategy-proofness.
We first show that agent 1 has no incentive to misreport. For (e, R) ̸∈ M̂, agent 1 positions
his full endowment at the top. Thus, f1 (e, R) = bT T C1 (e, R) = e1 . Clearly, for any misreport
R1′ ̸= R1 , e1 R1 f1 (e, (R1′ , R2 , R3 )).
For (e, R) ∈ M̂, by the definition of f , ei is agent 1’s most preferred allotment among{e1 , e2 , e3 }, and f1 (e, R) ∈ {e1 , ei }. If f1 (e, R) = ei then clearly f1 (e, R) = ei R1 bT T C1 (e, R).
If f1 (e, R) = e1 (= bT T C1 (e, R)) then there is an agent k ∈ {2, 3} such that bT T Ck (e, R)Pk yk
and fk (e, R) = bT T Ck (e, R) ∈ {e2 , e3 }. Let R1′ ̸= R1 be a misreporting. By the definition of bT T C, bT T C(e, R1′ , R−1 ) = bT T C(e, R). Thus, bT T Ck (e, R1′ , R−1 ) Pk yk and hence,f (e, R1′ , R−1 ) = bT T C(e, R1′ , R−1 ), which implies that f1 (e, R1′ , R−1 ) = e1 . Therefore, if(e, R) ∈ M̂, then f1 (e, R) R1 bT T C1 (e, R).
Next, we show that agents 2 and 3 have no incentive to misreport.
For (e, R) ̸∈ M̂, f2 (e, R) = bT T C2 (e, R) and f3 (e, R) = bT T C3 (e, R). Since bT T C is
strategy-proof, agents 2 and 3 have no incentive to misreport.
For (e, R) ∈ M̂, there are two cases.
63

Case 1. f (e, R) = bT T C(e, R). By the definition of f , there is an agent k ∈ {2, 3}
such that bT T Ck (e, R) Pk yk . Let Rk′ ̸= Rk be a misreporting. Then, fk (e, Rk′ , R−k ) ∈{bT T Ck (e, Rk′ , R−k ), yk }. Since bT T C is strategy-proof, bT T Ck (e, R) Rk bT T Ck (e, Rk′ , R−k ), andhence bT T Ck (e, R) = fk (e, R) Rk fk (e, Rk′ , R−k ).
Case 2. f (e, R) = y. By the definition of f , y2 R2 bT T C2 (e, R) and y3 R3 bT T C3 (e, R). Letk ∈ {2, 3} and Rk′ ̸= Rk be a misreporting. Since bT T C is strategy-proof, yk Rk bT T Ck (e, R) Rk
bT T Ck (e, Rk′ , R−k ). By the definition of f , fk (e, Rk′ , R−k ) ∈ {bT T Ck (e, Rk′ , R−k ), yk }. Thus,
fk (e, R) = yk Rk fk (e, Rk′ , R−k ).
Bundle endowments-swapping-proofness.
For (e, R) ̸∈ M̂, f (e, R) = bT T C(e, R). Since bT T C is bundle endowments-swapping-proof,
no pair of agents can be strictly better off by swapping their full endowments.
For (e, R) ∈ M̂, there are three cases.
Case 1. f (e, R) = y. Let {i′ , j ′ } ⊊ N . Let they swap their endowments completely, i.e.,e′ (i′ , j ′ ). Let M ′ ≡ (e′ (i′ , j ′ ), R). Since bT T C is bundle endowments-swapping-proof, there
is an agent k ∈ {i′ , j ′ } such that yk Rk bT T Ck (e, R) Rk bT T Ck (M ′ ). By the definition of f ,fk (M ′ ) ∈ {yk , bT T Ck (M ′ )}. Thus, fk (e, R) = yk Rk fk (M ′ ), which means that agent k cannot
be strictly better off by swapping his full endowments ek .
Case 2. f (e, R) = bT T C(e, R) and f1 (e, R) = ei . In this case, is is easy to see that agent 1
cannot be strictly better off by swapping his full endowments e1 , because he already receives
his best allotment. Moreover, f (e, R) = bT T C(e, R) implies that there is an agent k ∈ {2, 3}
who strictly prefers bT T Ck (e, R) to yk . Let agents {2, 3} swap their endowments completely,i.e., e′ (2, 3). Let M ′ ≡ (e′ (2, 3), R). By the definition of f , fk (M ′ ) ∈ {yk , bT T Ck (M ′ )}. If
fk (M ′ ) = yk . then agent k is worse off after the swapping. If fk (M ′ ) = bT T Ck (M ′ ), thenf (M ′ ) = bT T C(M ′ ). By bundle endowments-swapping-proofness of bT T C, there is an agentℓ ∈ {2, 3} such that fℓ (e, R) = bT T Cℓ (e, R) Rℓ bT T Cℓ (M ′ ) = fℓ (M ′ ), which implies that agentℓ cannot be strictly better off by swapping his full endowments eℓ .
Case 3. f (e, R) = bT T C(e, R) and f1 (e, R) ̸= ei . By the definition of bT T C, we know that
there is an agent k ∈ {2, 3} (possibly k = i) who receives ei and strictly prefers ei to yk . Let
k ′ ̸= k (possibly k ′ = 1) .
First, let agents k and k ′ swap their endowments completely, i.e., e′ (k, k ′ ). Let M ′ ≡(e′ (k, k ′ ), R). If f (M ′ ) = y, then agent k is worse off after the swapping. If f (M ′ ) = bT T C(M ′ ),then by bundle endowments-swapping-proofness of bT T C, there is an agent in ℓ ∈ {k, k ′ } suchthatfℓ (e, R) = bT T Cℓ (e, R)Rℓ bT T Cℓ (M ′ ) = fℓ (M ′ ), which implies that agent ℓ cannot be strictly
better off by swapping his full endowments eℓ . This implies that agent k has no incentive toswap.
Second, let agents {1, k ′′ } ≡ N \ {k} swap their endowments completely, i.e., e′ (1, k ′′ ). Let
M ′′ ≡ (e′ (1, k ′′ ), R). If k = i, then by the definition of f , fi (M ′′ ) ∈ {bT T Ci (M ′′ ), yi }. SincebT T Ci (M ′′ ) = ei Pi yi , fi (M ′′ ) = bT T Ci (M ′′ ) and hence f (M ′′ ) = bT T C(M ′′ ). By bundle
64

endowments-swapping-proofness of bT T C, we conclude that agents 1 and k ′′ cannot be strictly
better off by swapping their full endowments. Recall that f1 (e, R) ̸= ei . Thus, if k ̸= i, thenk ′′ = i. This means that at M ′′ , agent 1 positions his full endowments e′1 (1, k ′′ )(= ei ) at the top.
Thus, M ′′ ̸∈ M̂ and f (M ′′ ) = bT T C(M ′′ ). Since f (e, R) = bT T C(e, R), f (M ′′ ) = bT T C(M ′′ ),and bT T C is bundle endowments-swapping-proof, we know that agents 1 and k ′′ (= i) cannot bestrictly better off by swapping their full endowments.
⋄
Examples 7, 8, 9, and 10 are well defined on the domain of separable preference (strict preference) profiles and establish the logical independence of the properties in Theorem 4 (Theorem 5).
Note that Examples 7, 8, 9, and 10 also establish the logical independence of the properties
in Corollaries 1, 2, and 3 as well.

B.4

Theorems 6 and 7

The following examples establish the logical independence of the properties in Theorems 6 and
7.
Example 11 (One type endowments-swapping-proofness).
Same as example 3, the no-trade mechanism is individually rational, Strategy-proof, and nonbossy, but not one type endowments-swapping-proof.
⋄

Example 12 (Individual rationality).
Same as example 4, serial dictatorship mechanisms are strategy-proof, non-bossy, and bundle
endowments-swapping-proof, but not individually rational.
⋄
Example 13 (Strategy-proofness).
If we modify (Fujinaka and Wakayama, 2018, Example 9) (see details in Example 9) by applying
f coordinatewise to all object types, then we obtain a mechanism which satisfies all properties
excepts for strategy-proofness.
⋄

B.5

Theorem 8

The following examples establish the logical independence of the properties in Theorem 8.
Example 14 (One type endowments-swapping-proofness).
Same as example 3, the no-trade mechanism is individually rational, and Strategy-proof, but
not one type endowments-swapping-proof.
⋄
Example 15 (Individual rationality).
Same as example 4, serial dictatorship mechanisms are strategy-proof and one type endowmentsswapping-proof, but not individually rational.
⋄
65

As we mentioned earlier in the main text, the independence of strategy-proofness from theother properties in Theorem 8 is an open problem.

B.6

Theorem 9

The following examples establish the logical independence of the properties in Theorem 9.
Example 16 (Pairwise eﬀiciency).
Same as example 3, the no-trade mechanism is individually rational, Strategy-proof, and nonbossy, but not pairwise eﬀicient.
⋄
Example 17 (Individual rationality).
Same as example 4, serial dictatorship mechanisms are strategy-proof, non-bossy, and Pareto
eﬀicient (and hence pairwise eﬀicient), but not individually rational.
⋄
Example 18 (Strategy-proofness).
The mechanism in example 9 is individually rational, non-bossy, and pairwise eﬀicient, but not
strategy-proof.
⋄
Example 19 (Non-bossiness).
The mechanism in example 10 is individually rational, strategy-proof, and pairwise eﬀicient, butbossy.
⋄

B.7

Theorem 10

The following examples establish the logical independence of the properties in Theorem 10.
Example 20 (Coordinatewise eﬀiciency).
Same as example 3, the no-trade mechanism is individually rational, Strategy-proof, and nonbossy, but not coordinatewise eﬀicient.
⋄
Example 21 (Individual rationality).
Same as example 4, serial dictatorship mechanisms are strategy-proof and Pareto eﬀicient (andhence coordinatewise eﬀicient), but not individually rational.
⋄
Example 22 (Strategy-proofness).
The mechanism in Example 13 is individually rational and coordinatewise eﬀicient, but not
strategy-proof.
⋄

References
Abdulkadiroğlu, A. and T. Sönmez (2003). School choice: A mechanism design approach.
American economic review 93(3), 729–747.
66

Altuntaş, A., W. Phan, and Y. Tamura (2021). Some characterizations of generalized top trading
cycles. Working paper, https://wphan.wordpress.ncsu.edu/files/2021/11/APT-GTTC.pdf.
Alva, S. (2017). When is manipulation all about the ones and twos?
https://samsonalva.com/PWSP.pdf.

Working paper,

Anno, H. and M. Kurino (2016). On the operation of multiple matching markets. Games andEconomic Behavior 100, 166–185.
Atlamaz, M. and B. Klaus (2007). Manipulation via endowments in exchange markets withindivisible goods. Social Choice and Welfare 28(1), 1–18.
Bag, T., S. Garg, Z. Shaik, and A. Mitschele-Thiel (2019). Multi-numerology based resource
allocation for reducing average scheduling latencies for 5G NR wireless networks. In 2019
European Conference on Networks and Communications, pp. 597–602.
Bird, C. G. (1984). Group incentive compatibility in a market with indivisible goods. Economics
Letters 14(4), 309–313.
Biró, P., F. Klijn, and S. Pápai (2022a). Balanced exchange in a multi-unit Shapley-Scarf market.
Barcelona School of Economics Working Paper 1342.
Biró, P., F. Klijn, and S. Pápai (2022b). Serial rules in a multi-unit shapley-scarf market. Gamesand Economic Behavior 136, 428–453.
Echenique, F., S. Goel, and S. Lee (2022). Stable allocations in discrete economies. arXiv
preprint arXiv:2202.04706.
Ekici, O. (2022). Pair-eﬀicient reallocation of indivisible objects. In Proceedings of the 23rd
ACM Conference on Economics and Computation, New York, NY, USA, pp. 294. Association
for Computing Machinery.
Feng, D. and B. Klaus (2022). Preference revelation games and strict cores of multiple-type
housing market problems. International Journal of Economic Theory 18(1), 61–76.
Feng, D., B. Klaus, and F. Klijn (2022a). A characterization of the coordinate-wise top-tradingcycles mechanism for multiple-type housing markets. Cahier de recherches économiques No.
22.06.
Feng, D., B. Klaus, and F. Klijn (2022b). Group strategy-proofness for multiple-type housing
markets. Work in Progress.
Fiestras-Janeiro, G., F. Klijn, and E. Sánchez (2004). Manipulation of optimal matchings via
predonation of endowment. Mathematical Social Sciences 47 (3), 295–312.
67

Fujinaka, Y. and T. Wakayama (2018). Endowments-swapping-proof house allocation. Gamesand Economic Behavior 111, 187–202.
Gale, D. (1974). Exchange equilibrium and coalitions: an example. Journal of Mathematical
Economics 1(1), 63–66.
Ghodsi, A., V. Sekar, M. Zaharia, and I. Stoica (2012). Multi-resource fair queueing for packet
processing. In Proceedings of the ACM SIGCOMM 2012 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, pp. 1–12.
Ghodsi, A., M. Zaharia, B. Hindman, A. Konwinski, S. Shenker, and I. Stoica (2011). Dominantresource fairness: Fair allocation of multiple resource types. In Proceedings of the 8th USENIX
Conference on Networked Systems Design and Implementation, pp. 323–336.
Han, B., V. Sciancalepore, D. Feng, X. Costa-Perez, and H. D. Schotten (2019). A utility-driven
multi-queue admission control solution for network slicing. In IEEE INFOCOM 2019-IEEE
Conference on Computer Communications, pp. 55–63.
Hortaçsu, A. and D. McAdams (2010). Mechanism choice and strategic bidding in divisible good
auctions: An empirical analysis of the turkish treasury auction market. Journal of Political
Economy 118(5), 833–865.
Huh, W. T., N. Liu, and V.-A. Truong (2013). Multiresource allocation scheduling in dynamic
environments. Manufacturing & Service Operations Management 15(2), 280–291.
Jagadeesan, R. and A. Teytelboym (2021). Matching and money. In Proceedings of the 22nd
ACM Conference on Economics and Computation, pp. 634–634.
Kalai, E., A. Postlewaite, and J. Roberts (1978). Barriers to trade and disadvantageous middlemen: Nonmonotonicity of the core. Journal of Economic Theory 19(1), 200–209.
Kapor, A. J., C. A. Neilson, and S. D. Zimmerman (2020). Heterogeneous beliefs and school
choice mechanisms. American Economic Review 110(5), 1274–1315.
Kesten, O. (2012). On two kinds of manipulation for school choice problems. Economic Theory 51(3), 677–693.
Klaus, B. (2008). The coordinate-wise core for multiple-type housing markets is second-best
incentive compatible. Journal of Mathematical Economics 44(9-10), 919–924.
Kojima, F. and P. A. Pathak (2009). Incentives and stability in large two-sided matching markets.
American Economic Review 99(3), 608–27.
Konishi, H., T. Quint, and J. Wako (2001). On the Shapley–Scarf economy: the case of multiple
types of indivisible goods. Journal of Mathematical Economics 35(1), 1–15.
68Leszczyc, P. T. P. and G. Häubl (2010). To bundle or not to bundle: Determinants of the
profitability of multi-item auctions. Journal of Marketing 74(4), 110–124.
Ma, J. (1994). Strategy-proofness and the strict core in a market with indivisibilities. International Journal of Game Theory 23(1), 75–83.
Mackin, E. and L. Xia (2016). Allocating indivisible items in categorized domains. In Proceedingsof the Twenty-Fifth International Joint Conference on Artificial Intelligence, pp. 359–365.
Manjunath, V. and A. Westkamp (2021). Strategy-proof exchange under trichotomous preferences. Journal of Economic Theory 193, 105197.
Miyagawa, E. (2001). House allocation with transfers. Journal of Economic Theory 100(2),329–355.
Moulin, H. (1995). Cooperative Microeconomics: A Game-Theoretic Introduction. Princeton,
NJ: Princeton University Press.
Myerson, R. B. (1981). Optimal auction design. Mathematics of operations research 6(1), 58–73.
Pápai, S. (2001). Strategyproof and nonbossy multiple assignments. Journal of Public Economic
Theory 3(3), 257–271.
Pápai, S. (2007). Exchange in a general market with indivisible goods. Journal of Economic
Theory 132(1), 208–235.
Pathak, P. A., T. Sönmez, M. U. Ünver, and M. B. Yenmez (2021). Fair allocation of vaccines,
ventilators and antiviral treatments: leaving no ethical value behind in health care rationing.
In Proceedings of the 22nd ACM Conference on Economics and Computation, pp. 785–786.
Peng, M., C. Wang, J. Li, H. Xiang, and V. Lau (2015). Recent advances in underlay heterogeneous networks: Interference control, resource allocation, and self-organization. IEEE
Communications Surveys & Tutorials 17 (2), 700–729.
Postlewaite, A. (1979). Manipulation via endowments. The review of economic studies 46(2),
255–262.
Pycia, M. and M. Raghavan (2022). Non-bossiness and first-price auctions. CEPR Discussion
Paper No. DP16874.
Raghavan, M. (2015). Essays on eﬀiciency, fairness and strategy-proofness in allocation problems
with exact Capacity constraints. Ph. D. thesis, Indian Statistical Institute, New Delhi.
Rostek, M. and N. Yoder (2020). Matching with complementary contracts. Econometrica 88(5),1793–1827.
69

Roth, A. E. (1982). Incentive compatibility in a market with indivisible goods. Economics
Letters 9(2), 127–132.
Roth, A. E. and A. Postlewaite (1977). Weak versus strong domination in a market withindivisible goods. Journal of Mathematical Economics 4(2), 131–137.
Satterthwaite, M. A. and H. Sonnenschein (1981). Strategy-proof allocation mechanisms at
differentiable points. The Review of Economic Studies 48(4), 587–597.
Serizawa, S. (2006). Pairwise strategy-proofness and self-enforcing manipulation. Social Choiceand Welfare 26(2), 305–331.
Sertel, M. R. (1994). Manipulating lindahl equilibrium via endowments.
ters 46(2), 167–171.

Economics Let-

Sertel, M. R. and I. Özkal-Sanver (2002). Manipulability of the men-(women-) optimal matchingrule via endowments. Mathematical Social Sciences 44(1), 65–83.
Shapley, L. S. and H. Scarf (1974). On cores and indivisibility. Journal of Mathematical Economics 1(1), 23–37.
Shinozaki, H. (2022). Characterizing pairwise strategy-proof rules in object allocation problems
with money. ISER Discussion Paper No. 1187.
Shinozaki, H. and S. Serizawa (2022). Eﬀiciency, fairness, and strategy-proofness in constrained
package assignment problems with money. Working Paper.
Sikdar, S., S. Adalı, and L. Xia (2017). Mechanism design for multi-type housing markets. In
Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, pp. 684–690.
Sönmez, T. (1999a). Can pre-arranged matches be avoided in two-sided matching markets?
Journal of Economic theory 86(1), 148–156.
Sönmez, T. (1999b). Strategy-proofness and essentially single-valued cores. Econometrica 67 (3),677–689.
Sun, N. and Z. Yang (2006). Equilibria and indivisibilities: Gross substitutes and complements.
Econometrica 74(5), 1385–1402.
Svensson, L.-G. (1999). Strategy-proof allocation of indivisible goods. Social Choice and Welfare 16(4), 557–567.
Thomson, W. (2001). On the axiomatic method and its recent applications to game theory andresource allocation. Social Choice and Welfare 18(2), 327–386.

70

Thomson, W. (2016). Non-bossiness. Social Choice and Welfare 47 (3), 665–696.
Wako, J. (2005). Coalition-proof Nash allocation in a barter game with multiple indivisible
goods. Mathematical Social Sciences 49(2), 179–199.

71