Department of Policy and Planning Sciences
Discussion Paper Series

No.1343

 On the operation of multiple matching markets
by
Hidekazu ANNO and Morimitsu KURINO

Mar 2016

UNIVERSITY OF TSUKUBA
Tsukuba, Ibaraki 305-8573
JAPANOn the operation of multiple matching markets ∗Hidekazu Anno †Morimitsu Kurino ‡June 19, 2015

Abstract
We provide a new perspective on how to operate matching markets when there are many
types of markets. Our finding is that the market-wise adaptation of strategy-proof and nonwasteful rules yields a strategy-proof rule with the following eﬃciency property: no strategyproof rule Pareto-dominates the rule. Such rules are abundant as they include the market-wiseuse of the well-known priority-based rules of the top trading cycles and the deferred acceptance. This result gives theoretical support to the independent operation of markets observedin real-life markets as well as our practice in Market Design that separately treats each market
for its design.
Journal of Economic Literature Classification Numbers : C78, D47, D71.
Keywords: Market design; Strategy-proofness; Second-best incentive compatibility; Top trading cycles rules; Deferred acceptance rules.

∗

We would like to thank Takashi Akahoshi, Masaki Aoyagi, Umut Dur, Aytek Erdil, Onur Kesten, Fuhito Kojima,
Eiichi Miyagawa, Hervé Moulin, Hiroo Sasaki, Norov Tumennasan, Utku Ünver, Zaifu Yang, and Bumin Yenmez
for helpful discussions. We would also like to thank seminar participants at York, Waseda, the 12th meeting of theSociety for Social Choice and Welfare at Boston College, the 14th SAET conference at Waseda, and the workshop“Designing Matching Markets” at the WZB Berlin for useful comments. The paper was circulated as “Second-best
incentive compatible allocation rules for multiple-type indivisible objects.” Hidekazu Anno greatfully acknowledges
the Waseda University Grant for Special Research Projects (Project number: 2014B-146) and JSPS KAKENHI
Grant Number 24243037. Morimitsu Kurino acknowledges financial support from JSPS KAKENHI Grant number
15H03327, and is thankful to Koichi Takase and the Faculty of Commerce at Waseda University for their hospitality
when he was a visitor there during the initial stage of this work. All remaining errors are our own.
†
Graduate School of Fundamental Science and Engineering, Waseda University, Japan; e-mail: annohidekazu@gmail.com‡
Faculty of Engineering, Information and Systems, University of Tsukuba, 1-1-1 Tennodai, Tsukuba, Ibaraki
305-8573, Japan; e-mail: kurino@sk.tsukuba.ac.jp1

1

Introduction

We have recently witnessed economists’ discovery and design of real-life matching markets such as
school choice (Abdulkadiroğlu and Sönmez, 2003) and organ exchanges (Roth, Sönmez, and Ünver,
2004; Ergin, Sönmez, and Ünver, 2014). In such a market one type of indivisible good, or object
for short, is allocated to agents who demand one unit when monetary transfers are not allowed(Shapley and Scarf, 1974; Hylland and Zeckhauser, 1979).
We often deal with multiple types of objects at the same time — what we call a multiple-type(matching) market. People simultaneously participate in multiple markets, each of which deals
with a diﬀerent type of commodity. Examples are abundant: Many families live in public housing
and have children who go to school — one type of object is public housing and another is a seat in aschool;1 Teaching courses and administrative tasks are assigned to faculty members in universities
where one type of object is courses and another is administrative tasks; About 80 % of pancreas
patients in Japan also need a kidney transplant due to chronic kidney disease where one type ofobject is the pancreas and another the kidney.2 Furthermore, a dynamic matching market is a
special class of multiple-type markets where people dynamically participate in one market multiple
times (Kurino, 2014). This is because the objects consumed in two distinct dates are considered
to be diﬀerent object types. For example, college students take part in the annual assignmentof dormitory rooms; Families with several children participate in a school choice program or a
daycare assignment program at diﬀerent times when each of their children enters the school (Dur,2012; Kennes, Monte, and Tumennasan, 2014); Teachers in public schools move to diﬀerent schools
through annual assignment procedures (Bloch and Cantala, 2013).
In this paper, we focus on a multiple-type market. Each agent has a separable preference,
where a preference over bundles is separable if there is a list of preferences over each single-type
market such that if two bundles x and y are diﬀerent in only t-th type, then the evaluation between
x and y coincides with the evaluation of t-th types xt and y t according to the preference over thet-th market objects.3
One important observation is that in most cases, if not all, assignment procedures for diﬀerent
types of objects are operated by diﬀerent government authorities, and each procedure is independent from the other.4 Corresponding to this practice in real-life markets, the Market Design
literature treats each market independently and then considers the design of stratetgy-proof and
1

The percentage of the population living in public housing is about 10 to 35 in many countries. For
example, Whitehead and Scanlon (2007) report that the percentages in European countries around 2000
are 35 in the Netherlands, 25 in Austria, 21 in Denmark, 20 in Sweden, 18 in England, 17 in France,
8 in Ireland, 6 in Germany, and 4 in Hungary.
Moreover, the percentages are 30 in Hong Kongand 9.9 in Japan (The webpages are http://www.housingauthority.gov.hk/en/public-housing/index.html andhttp://www.stat.go.jp/data/jyutaku/2008/10 3.htm. The webs were accessed on December 18, 2013.) This suggests that about the same percentage of families with children would participate in two types of markets - public
housing assignment and school choice programs.
2
For example see the Handbook of The Japan Society for Transplantation (2013).
3
A model with single-type objects is a special case of ours. Although our main focus is a multiple-type model,
all of our results remain true in single-type models.
4
For example, in the City of Boston, the school choice assignment is operated by Boston Public Schools, while
the public housing assignment is controlled by the Boston Housing Authority.

2

Table 1: An example of ineﬃciency
Agent 1R1
R11 R12(a, c)ac(b, c)bd(a, d)(b, d)..
.

Agent 2R2
R21 R22(a, c)ac(a, d)bd(b, c)(b, d)..
.

Note: Agent i’s preference for bundles is denoted by Ri while that for type-t objects is by Rit . For example, agent
1 prefers bundle (a, c) to (b, c) to (a, d), ... , and she prefers a to b for type 1 while she does c to d.

Pareto eﬃcient (or at least non-wasteful ) rules for only one type of market.5 However, such independent operation of diﬀerent markets leads to ineﬃciency when we take all types of markets into
account.
To illustrate this point, suppose that there are two agents and two types of objects. We have
two objects a, b for type t = 1 market, and two objects c, d for type t = 2 market. Preferences of
agents 1 and 2 are given by Table 1. Now, let us consider the underlined allocation in this table
where agent 1 receives (a, d) and agent 2 gets (b, c). In other words, for type t = 1 the allocationprescribes (1, 2; a, b), while for type t = 2 it does (1, 2; d, c). Note that within each type market
the allocations (1, 2; a, b) and (1, 2; d, c) are Pareto eﬃcient. However, by swapping their bundles
both agents are made better oﬀ. This means that the original allocation is not Pareto eﬃcient,although its allocation for each type is Pareto eﬃcient. One lesson from this example is that anallocation procedure that uses a Pareto eﬃcient rule for each type might result in an ineﬃcient
allocation.6
One of the most serious diﬃculties pertaining to the multiple-type market is that the combination of strategy-proofness and Pareto eﬃciency essentially results in a serial dictatorship rulein which each agent chooses her assignment one by one according to an exogenously fixed priority
order (Monte and Tumennasan, 2013).7 However, such a rule is against the independent operationof markets in real life and is extremely unfair.8
With this diﬃculty, we take a natural research direction of looking for a plausible rule by5

Under a non-wasteful allocation (Balinski and Sönmez, 1999), if some object is preferred to the assigned one
for an agent, it is fully assigned up to its quota. Thus, non-wastefulness is an eﬃciency axiom weaker than Paretoeﬃciency. Note that non-wastefulness is defined only for single-type markets. The lack of a natural second-best
eﬃciency notion in a multiple-type market is another motivation of the current paper.
6
More specifically, this is a Pareto ineﬃcient allocation although it is reached by the market-wise serial dictatorship rule which is strategy-proof and Pareto eﬃcient in each type market. Agent 1 is the dictator of the firstmarket while agent 2 is the dictator of the second market.
7
Rigorously speaking, Monte and Tumennasan’s (2013) model is not a special case of ours due to the diﬀerencein preference domains (See Assumption 2 and footnote 17). They prove that if a rule is strategy-proof, Paretoeﬃcient and non-bossy, then it is a sequential dictatorship rule that is a variant of the serial dictatorship rule.
8
Consider the environment with homogeneous preferences of agents and unit quotas of objects. In the “full”
serial dictatorship (SD) rule, the highest-priority agent receives her favorite objects from all types, and is envied by
all agents in each type. However, we can mitigate the unfairness with a “market-wise” serial dictatorship (SD) rule
where a priority is defined for each type, and the highest-priority agent in a type is diﬀerent from those in the othermarkets. In this case for each agent there is only one type market for which she is envied by all agents. Although
it is Pareto ineﬃcient, the market-wise SD rule to a large extent remedies the unfair feature of the full SD rule.

3

relaxing Pareto eﬃciency while keeping strategy-proofness. That is, we search for “second-best(eﬃcient) incentive compatible” rules. To be precise, we call a rule second-best incentive compatible
if the rule is itself strategy-proof, and is not Pareto-dominated by any other strategy-proof rule. It
is a quite natural second-best eﬃciency concept as far as we are concerned with strategy-proofness
since the notion is a straightforward adaptation of the Pareto criterion for the class of strategy-proof
rules. This paper provides a simple and practical suﬃcient condition for the second-best incentive
compatibility.
To state our main result, it is worth noting that there is a very simple way to construct a
strategy-proof rule in a multiple-type market. Namely, we first consider an independent rule whichapplies a single-type rule in each market, and then consider only strategy-proof single-type rules for
an independent rule. This is made possible due to the separability of preferences. Based on this,our main result (Theorem 1) is the following: An independent rule obtained by the market-wise
application of strategy-proof and non-wasteful single-type rules is second-best incentive compatible.
Now, let us explain the economic implications of Theorem 1. Inspired by Gale’s top trading
cycles (Shapley and Scarf, 1974) and Gale and Shapley’s (1962) deferred acceptance algorithm, theMarket Design literature has uncovered strategy-proof and non-wasteful rules for various singletype matching problems such as school choice problems, on-campus housing assignments andkidney exchange problems for patients (See section 5). However, as we have already seen, even if
we successfully design such a strategy-proof and Pareto eﬃcient rule for each single-type market,
the rules may collectively fail to be Pareto eﬃcient as an allocation procedure for a multiple-type
market. Theorem 1 guarantees that the practices of designing such a rule will lead to second-best
incentive compatibility - the impossibility of being Pareto-improved without sacrificing strategyproofness. Moreover, we have a rich class of second-best incentive compatible rules, since mostof prominent single-type rules, if not all, proposed in the literature are strategy-proof and nonwasteful. The positive result and the richness of rules are in marked contrast to requiring the “firstbest incentive compatibility” (namely, the combination of strategy-proofness and Pareto eﬃciency)
which often results in an extremely unfair rule of serial dictatorship in our multiple-type setting.
That is, the eﬃciency loss in these rules is an inevitable cost of recovering the fairness and operating
markets independently as long as we preserve strategy-proofness.
In sum Theorem 1 provides us with a new perspective for Matching Market Design—the theoretical support for the independent operation and design of matching markets with a strategy-proof
and non-wasteful rule for each type.9 The support is even stronger if we note that a decentralized
trade from an arbitrary allocation would not work in a multiple-type market as the core may be
empty (Konishi, Quint, and Wako, 2001).10
9This is reminiscent of the first welfare theorem in the standard competitive equilibrium theory which guarantees
that if each independent individual “rationally” behaves in markets, the resulting allocation is eﬃcient. Likewise,in our multiple-type market, if each independent designer uses strategy-proof and (at least) non-wasteful rule ineach market, the resulting rule is second-best eﬃcient for the whole market.
10
We mean that a decentralized trade is one where mutually beneficial trades would be made until there areno such trades. The core is defined to be an allocation from which there is no further mutually beneficial trade.
Note that in a single-type market the core is singleton and thus the procedure works well for reaching the uniqueallocation in the core (Shapley and Scarf, 1974; Roth and Postlewaite, 1977).

4

1.1

Related literature

The most basic matching model is a house allocation problem (Shapley and Scarf, 1974; Hylland
and Zeckhauser, 1979) where each agent demands one unit of an object. In addition to real-life
applications mentioned in the Introduction there are on-campus housing assignments for college
students (Abdulkadiroğlu and Sönmez, 1999) and cadet-branch matching problem in the UnitedStates Military Academy (Sönmez and Switzer, 2013). See Sönmez and Ünver (2011) for theircomprehensive knowledge on Matching Market Design.
In contrast to the literature on the above basic problems, there are few papers on multipletype markets: Moulin (1995) introduces the model with an initial endowment, referred to as
multiple-type housing market, or generalized Shapley-Scarf housing market. Konishi, Quint, andWako (2001) show that the core might be empty in a multiple-type housing market. Moreover,they show that no rule is strategy-proof, Pareto eﬃcient, and individually rational. Finally, Klaus(2008) shows that the market-wise core mechanism satisfies the second-best incentive compatibility.
Similar to our paper, Monte and Tumennasan (2013) investigate a multiple-type markets without
endowments, and show that the combination of strategy-proofness, Pareto eﬃciency, and nonbossiness implies the sequential dictatorship.
There is a similar but diﬀerent problem of multiple assignment where people demand multiple
units of objects though there is no type of objects. Thus the multiple assignment problem isless restrictive than a multiple-type market because objects are exogenously divided into diﬀerent
groups in a multiple-type market. Pápai (2001) and Hatfield (2009) show that the combinationof strategy-proofness, Pareto eﬃciency, and non-bossiness results in a sequential dictatorship rule.
Klaus and Miyagawa (2001) also show a dictatorship result under solidarity and consistency when
the population can vary. Moreover, Sönmez and Ünver (2010); Budish and Cantillon (2012) examine course allocations at business schools.
The separability of preference is one of the key features in the theory where each agent consumes
multi unit of objects. The separability is assumed for the many-side agents in a many-to-one
two-sided matching market, agents in multiple-type markets, and those in multiple assignment
problems. Moreover, the studies of social choice functions on product spaces work on the separable
preference domain (e.g., Barberà, Sonnenschein, and Zhou 1991; Le Breton and Sen 1999; Ju 2003;
Barberà, Massó, and Neme 2005). On the other hand, the study under interdependence or nonseparability of preferences has just started in matching models. In particular, Dur (2012) and
Dur and Wiseman (2015) consider a problem to allocate a number of school seats to the families
with siblings and neighbors. They consider a specific non-separable preference domain where eachfamily or neighbors prefer to receive the same school for their children. Thus, it is an important
issue to select a realistic interdependence of preferences corresponding to the multiple-type market
under consideration. Although we focus on separable preferences in this paper, we believe that
our results work as a benchmark and bring insights for non-separable preference domains.
With the separable preferences, an independent rule, which is our focus in our paper, is welldefined where the entire rule consists independently of type-market rules. A few papers deal withdependent rules. For example, in his introduced house allocation problem with the overlapping5

generations structure,11 Kurino (2014) considers a dependent rule under separable preferenceswhere in each period the previously assigned object becomes an endowment and thus aﬀects thecurrent rule through endowments. Kennes, Monte, and Tumennasan (2014) extend Kurino’s (2014)
model to a school choice problem under separable preferences, and focus on dependent rules wherein each period the previously assigned object aﬀects the current priority and thus type-rule.12
The taxation literature has the tradition to consider second-best eﬃcient allocations.13 As
is defined formally in Section 4, the second-best eﬃciency concept in this paper concerns about
the eﬃciency of an allocation rule under the constraint of strategy-proofness. To the best of ourknowledge, a variant of second-best incentive compatibility is first studied in Sasaki (2003) in thecontext of divisible resource allocation problems with multi-dimensional single-peaked preferences.
The second-best incentive compatibility in the current paper is studied in Anno (2008); Anno andSasaki (2013) for the same model as Sasaki (2003). Moreover, Klaus (2008) investigates the concept
in a multiple-type housing market, while Abdulkadiroğlu, Pathak, and Roth (2009), Kesten and
Kurino (2013), Erdil (2014), and Fragiadakis and Troyan (2013) study it in single-type problems.

2

Model and Axioms

2.1

Multiple-type markets

We introduce a general model of multiple-type markets where an agent is interested in being
assigned multiple types of objects when monetary transfers are not allowed. A multiple-type
market is a list (N, T, (Ti )i∈N , (X t )t∈T , q, (Ri )i∈N ): N := {1, . . . , n} is a finite set of agents with
|N | ≥ 2, while T is a finite set of types of objects (i.e., indivisible goods). We identify T with
{1, · · · , |T |}. If |T | = 1, we call a market single type. For each type t ∈ T , objects of type-t areavailable. Let X t be a finite set of type-t objects with |X t | ≥ 2. For each type t ∈ T , q(xt ) is thequota of type-t object xt ∈ X t . That is, q is a function from ∪t∈T X t to Z++ and q(xt ) indicatesthe number of identical type-t object xt . Each agent i ∈ N is interested in at least one type ofobjects, and consumes one object from each type in which she is interested. Let Ti ∈ 2T \{∅} be
the set of types in which agent i is interested (See Table 2). Moreover, for each type t ∈ T , let
N t := {i ∈ N |t ∈ Ti } be the set of agents who are interested in type-t objects. We assume thatfor each t ∈ T , at least one agent is interested in the type-t, i.e., N t �= ∅. Throughout the paper
we maintain the following assumption.14
Assumption 1 (Existence of outside option). For each type t ∈ T , there is the type-t outside
option, denoted by ot , in X t which satisfies q(ot ) ≥ |N t |.
In words, the assumption guarantees that every agent has the right to withdraw from themarket. The condition (q(ot ) ≥ |N t |) means that the outside option ot is suﬃciently available
11

In this interpretation, the set of types is viewed as the set of periods. Since we assume that the set of types isfinite, our model can accommodate a dynamic matching model with a finite horizon.
12
Pereyra (2013) also extends Kurino’s (2014) to a school choice problem and then considers independent rules
under separable preferences.
13
Hammond (2000) provides a good summary of the literature.
14
The only exception is the paragraph right before Corollary 3. There we do not assume Assumption 1.

6

Table 2: An example of a multiple-type market
Agent 1
Agent 2Agent 3

Type 1√√

Type 2Type 3√√√N 1 = {1, 2}

N 2 = {2, 3}

N 3 = {3}T1 = {1}T2 = {1, 2}
T3 = {2, 3}√Note: In this example, there are three agents and three types. The symbol indicates which agent is interested inwhat types of objects. For example, agent 2 is interested in both types 1 and 2.

so that it can be consumed by all agents interested in the type-t market at the same time. We
interpret it as the artificial object that represents the option to withdraw. We discuss in the
conclusion how this assumption aﬀects our main result.
Finally, we describe the preferences of agents. Since each agent i ∈ N consumes one object�from each type in Ti , her consumption space is Xi := t∈Ti X t . An element of Xi is called abundle, generically denoted by xi = (xti )t∈Ti ∈ Xi . For convenience and clarity, we introduce
some notations: For a finite set Y , let R(Y ) be the set of all complete and transitive binary
relations on Y , and P(Y ) the set of all complete, transitive, and anti-symmetric binary relations
on Y .15 Each agent i ∈ N is equipped with a preference relation Ri on Xi , i.e., Ri ∈ R(Xi ). For
each Ri ∈ R(Xi ), Pi and Ii denote the asymmetric and symmetric parts of Ri . We denote R :=��(Ri )i∈N ∈ i∈N R(Xi ) and call it a profile. For each profile R = (R1 , · · · , Rn ) ∈ i∈N R(Xi ), andeach i ∈ N , the subprofile obtained by removing i’s preference is denoted by R−i ; that is, R−i :=(R1 , · · · , Ri−1 , Ri+1 , · · · , Rn ). It is convenient to write the profile (R1 , · · · , Ri−1 , Ri� , Ri+1 , · · · , Rn )as (Ri� ; R−i ).
Now, we introduce two classes of preferences. First, a preference Ri ∈ R(Xi ) is separable
if for each t ∈ Ti there is a preference Rit ∈ P(X t ) on type-t objects such that for each pair ofbundles {xi , x�i } ⊆ Xi ,[ for each t ∈ Ti , xti Rit x�ti ] ⇒ xi Ri x�i .
We denote by Rsep (Xi ) the set of all separable preferences on Xi , and call Rit a type-t preference.
Let Psep (Xi ) be the set of all separable strict preferences on Xi , i.e., Psep (Xi ) = Rsep (Xi ) ∩ P(Xi ).
To introduce the second class of preferences, for each t ∈ T , let U t be the set of strict utility
functions on X t . That is, uti : X t → R belongs to U t if uti is injective. A preference Ri ∈ R(Xi ) is
additively separable if for each t ∈ Ti there is a utility function uti ∈ U t on type-t objects suchthat for each pair of bundles {xi , x�i } ⊆ Xi ,xi Ri x�i ⇔�t∈Tiuti (xti ) ≥�uti (x�ti ).

t∈Ti

We denote by Radd (Xi ) the set of all additively separable preferences on Xi , and by Padd (Xi ) the
set of all additively separable strict preferences on Xi , i.e., Padd (Xi ) = Radd (Xi ) ∩ P(Xi ). The
A binary relation ≥ is complete if for each {y, y � } ⊆ Y , y ≥ y � or y � ≥ y. A binary relation ≥ is transitive
if for each {y, y � , y �� } ⊆ Y , y ≥ y � and y � ≥ y �� imply y ≥ y �� . A binary relation ≥ is anti-symmetric if for each{y, y � } ⊆ Y , y ≥ y � and y � ≥ y imply y = y � .
157

next remark immediately follows from the definitions.
Remark 1. Let i ∈ N .
1. For each Ri ∈ Psep (Xi ) ∪ Radd (Xi ), the list of corresponding type-t preferences (Rit )t∈Ti is
unique.
2. We have the following relations among the classes of preferences.16
Psep (Xi )Radd (Xi )�Rsep (Xi )

�

�

�

Padd (Xi )�Let Di be the set of agent i’s admissible preferences. Let D := i∈N Di be the set of admissible
profiles. In the rest of the paper we keep the following assumption.
Assumption 2 (Admissible preferences). For each i ∈ N , Padd (Xi ) ⊆ Di ⊆ Psep (Xi ) ∪Radd (Xi ).
Our domain covers two types of wide ranges of domains: When one type consists of separable
strict preferences, it ranges from the additively separable domain to the universal one (See Item
2 in Remark 1, in particular Padd (Xi ) ⊆ Psep (Xi )). The other type ranges from the strict domain
to the weak one when it consists of additively separable preferences (See Item 2 in Remark 1, inparticular Padd (Xi ) ⊆ Radd (Xi )). As long as we keep a separability of preferences, ours is the mostnatural and covers the widest range of domains in the literature.17 This completes the descriptionof a multiple-type market (N, T, (Ti )i∈N , (X t )t∈T , q, (Ri )i∈N ). We assume throughout the paperthat N , T , (Ti )i∈N , (X t )t∈T , and q are fixed.
Let us emphasize that our model allows for agents’ partial participation on type markets (Ti ⊆T ) and covers the full participation on all type markets (for each i ∈ N , Ti = T ) considered in theliterature.18

2.2Type markets

Let a multiple-type market (N, T, (Ti )i∈N , (X t )t∈T , q, (Ri )i∈N ) be given. Then, by Assumption 2
and Item 1 in Remark 1, for each i ∈ N and each Ri ∈ Di , each of the corresponding type-t
preference is unique and strict, and thus denoted by Rit . Thus, it makes sense to introduce thetype-t market induced from the multiple-type market. The induced type-t market is the singletype market (N t , X t , q|X t , (Rit )i∈N t ) where each agent i ∈ N t consumes one type-t object in X t ;q|X t is the restriction of q to X t which indicates the quota q(xt ) of each type-t object xt ∈ X t .
16

Non-trivial statements are Padd (Xi ) �= Psep (Xi ), and Radd (Xi ) �= Rsep (Xi ). The proof of the latter can befound on page 43 in Fishburn (1970). The former is proved in Appendix A.
17
See Konishi, Quint, and Wako (2001); Klaus (2008); Monte and Tumennasan (2013) whose domain is the setof separable strict preferences, Psep (Xi ). An exception is Kurino (2014) who allows weak preferences, though his
dynamic model is slightly diﬀerent from the multiple-type goods model. Strictly speaking, Monte and Tumennasan’s(2013) domain additionally assumes that the bundle consisting of outside options is worst.
18
See Moulin (1995); Konishi, Quint, and Wako (2001); Klaus (2008); Monte and Tumennasan (2013).

8

tFinally, Rit is the type-t preference of agent i in P(X t ). We denote Rt := (Rit )i∈N t ∈ P(X t )Nand call it the type-t profile induced from (Ri )i∈N , or just the type profile induced fromttt(Ri )i∈N . 19 Similarly to the notations of profiles, we use R−i= (R1t , · · · , Ri−1
, Ri+1, · · · , Rnt ) andttt(Ri�t ; R−i) = (R1t , · · · , Ri−1
, Ri�t , Ri+1
, · · · , Rnt ).
Note that our single-type market or type market, (N t , X t , q|X t , (Rit )i∈N t ) , is the traditional
house allocation problem (Hylland and Zeckhauser, 1979), which can include the following real life
matching problems; House allocation with existing tenants, Kidney exchange, School choice. Section 5 provides a description of these markets. See Sönmez and Ünver (2011) for a comprehensive
survey on the subject.

2.3

Rules

A type-t allocation is a function at from N t to X t such that each agent i ∈ N t is assigned type-t
object ati , and for each type-t object xt ∈ X t the number of agents who are assigned xt does notexceed the quota q(xt ), i.e., |{i ∈ N t |ati = xt }| ≤ q(xt ). Let At be the set of all type-t allocations.
�
An allocation, consisting of type allocations, is a := (a1 , · · · , a|T | ) ∈ t∈T At where for each�t ∈ T , at is a type-t allocation. Let A := t∈T At be the set of all allocations. Given a ∈ A, foreach i ∈ N , let ai be the agent i’s bundle at a, i.e., ai := (ati )t∈Ti .
We focus on deterministic rules in this paper. A rule selects an allocation for each profile in a
multiple-type market, i.e., it is a function ϕ : D → A. For each R ∈ D, ϕi (R) denotes the agent
i’s bundle at ϕ(R), and ϕt (R) denotes the type-t allocation at ϕ(R). On the other hand, a type-ttrule selects a type-t allocation for each type-t profile, i.e., it is a function Φt : P(X t )N → At .
t
For each Rt ∈ P(X t )N , Φti (Rt ) denotes the agent i’s type-t object at Φt (Rt ). Note that Φt (Rt )depends only on the preferences of N t while ϕt (R) may depend on the preferences of N \N t . In
the conclusion we discuss how our main result can be aﬀected for a lottery rule.
Given a list of type rules, (Φt )t∈T , we can naturally define a rule for bundles due to separable
preferences:
Definition 1. A rule ϕ is independent if there exists a list of type rules (Φt )t∈T such that foreach R ∈ D and each t ∈ T , ϕt (R) = Φt (Rt ). If such a (Φt )t∈T exists, it is unique. Thus, if a rule
ϕ is independent, we denote its corresponding type-t rule by Φt .
An independent rule, ϕ, treats each type market independently and separately in that a type-t
allocation under ϕ depends only on type-t preference profiles. Note also that an independent rule
is less informationally demanding than a dependent one, because the former only requires typepreferences and the latter requires preferences on bundles that contain type preferences.
Finally, we introduce the dominations of rules: An allocation a ∈ A (Pareto) dominates anallocation b ∈ A at R ∈ D, written as a dom(R) b, if for each i ∈ N , ai Ri bi , and for somei ∈ N , ai Pi bi . Similarly, a type-t allocation at ∈ At dominates a type-t allocation bt ∈ Att
at Rt ∈ P(X t )N , written as at dom(Rt ) bt , if for each i ∈ N t , ati Rit bti , and for some i ∈ N t ,19

In the list (N t , X t , q|X t , (Rit )i∈N t ), for simplicity we omit the type set and the structure of interested types.
Note that in the type-t market, the type set is {t} and every agent i ∈ N t is interested in type-t.

9ati Pit bti . Now we can define the domination of rules: A rule ϕ dominates another rule ζ, written
as ϕ dom ζ if for each R ∈ D and each i ∈ N , ϕi (R) Ri ζi (R), and for some R ∈ D, ϕ(R)dominates ζ(R) at R.

2.4

AxiomsWe introduce axioms for both rules and type rules.
The first is an incentive compatibility axiom that says no agent can benefit from misreportingher preference. A rule ϕ is strategy-proof if for each R ∈ D, each i ∈ N and each Ri� ∈ Di ,tϕi (R) Ri ϕi (Ri� ; R−i ). Similarly, a type-t rule Φt is strategy-proof if for each Rt ∈ P(X t )N ,teach i ∈ N t and each Ri�t ∈ P(X t ), Φti (Rt ) Rit Φti (Ri�t ; R−i).
The second is an eﬃciency axiom that says, for each profile, the selected allocation should not
be dominated by any other allocation at the profile. A rule ϕ is Pareto eﬃcient if for eachprofile R ∈ D, there is no allocation a ∈ A such that a dominates ϕ(R) at R. Similarly, a type-ttrule Φt is Pareto eﬃcient if for each type-t profile Rt ∈ P(X t )N , there is no type-t allocation
at ∈ At such that at dominates Φt (Rt ) at Rt .
The third is a weak eﬃciency axiom defined only for a type rule. A type-t rule Φt is nont
wasteful (Balinski and Sönmez, 1999) if for each Rt ∈ P(X t )N , each i ∈ N t and each xt ∈ X t ,xt Pit Φti (Rt ) implies |{j ∈ N t |Φtj (Rt ) = xt }| = q(xt ).
The last one is a very weak form of a voluntary participation axiom that says for each profileno agent can be worse oﬀ than nothing. A rule ϕ is individually rational if for each R ∈ D andeach i ∈ N , ϕi (R) Ri (ot )t∈Ti . Moreover, a type-t rule Φt is individually rational if for eacht
Rt ∈ P(X t )N and each i ∈ N t , Φti (Rt ) Rit ot .
The following results are straightforward from definitions.
Remark 2. Let Φt be a type-t rule.
1. If Φt is Pareto eﬃcient, then Φt is non-wasteful. The converse is not always true.
2. If Φt is non-wasteful, then Φt is individually rational. The converse is not always true.
Remark 3. Suppose that a rule ϕ is independent.
1. For each t ∈ T , Φt is strategy-proof if and only if ϕ is strategy-proof.
2. If for each t ∈ T , Φt is individually rational, then ϕ is individually rational. The converse is
not always true.
3. If ϕ is Pareto eﬃcient, then for each t ∈ T , Φt is Pareto eﬃcient. The convese is not always
true.
Note that the example in Introduction is a proof of the latter statement in Item 3 — anindependent rule consisting of Pareto eﬃcient type-rules is not Pareto eﬃcient in a multiple-type
market.
10

3

Three Classes of Priority-based Rules

We first introduce a priority profile, and then the three priority-based rules that have played central
roles in the literature. The single-type market with priority profiles is called a school choice problem
or a priority-based indivisible goods resource allocation problem in the literature.
A priority is defined for each type-t object that orders all agents who are interested in the type-t
market and expresses how each agent is treated for the object. Formally, a priority of type-t objectt
xt ∈ X t is a linear order in P(N t ), denoted by �txt . We denote �t := (�txt )xt ∈X t ∈ P(N t )X and�
tcall it a type-t priority profile. Moreover, we denote �:= (�t )t∈T ∈ t∈T P(N t )X a priority
profile.

3.1

Market-wise top trading cycles (TTC) rule

The top trading cycles (TTC) rule for a single-type market is introduced by Abdulkadiroğlu andSönmez (2003) who modify Gale’s top trading cycles described in Shapley and Scarf (1974). Giventa type-t profile Rt ∈ P(X t )N , the top trading cycles (TTC) type-rule induced by a type-ttpriority profile �t , denoted by T T C � , selects a type-t allocation as follows:
Step 1: Each agent points to the most favorite object according to her preference and each object
points to the agent who has the highest priority for that object. Note that there is at least one
cycle. 20 Each agent in a cycle receives the object she points to and is removed from the market.
Each object in a cycle whose quota is one is also removed.
Step k(≥ 2): Each agent who has not been removed in previous steps points to the most favorite
object among the remaining objects according to her preference and each remaining object points
to the agent who has the highest priority among the remaining agents for that object. Note that
there is at least one cycle. Each agent in a cycle receives the object she points to and is removed
from the market. Each object in a cycle is also removed if the number of cycles containing theobject formed through k steps is equal to the quota of the object.
The algorithm terminates when no agent remains in the market.
tRemark 4. For each type t ∈ T and each priority profile �t ∈ P(N t )X , the TTC type-rule inducedby �t is strategy-proof and Pareto eﬃcient (Abdulkadiroğlu and Sönmez, 2003), and thus is nonwasteful and individually rational by Remark 2.
Definition 2. The market-wise top trading cycles (TTC) rule induced by a prioritytprofile �= (�t ), denoted by T T C � , selects its type-t allocation as T T C � (Rt ) that is chosen by
the TTC type rule induced by type-t priority profile �t .
Remark 5. Note that by Remarks 3 and 4, a market-wise TTC rule is strategy-proof and individually
rational. However, the example in Introduction can be used to show that it is not Pareto eﬃcientfor the priority profile in Table 3.
20

A cycle is an ordered list of agents and objects (i1 , x1 , i2 , x2 , . . . , im , xm ) such that i1 points to x1 , x1 points to
i2 , i2 points to x2 , ..., im points to xm , and xm points to i1 .

11

Table 3: Priority profile
�1a =�1b�2c =�2d
1
2
2
1

3.2

Market-wise deferred acceptance (DA) rule

The deferred acceptance (DA) rule for a single-type market is introduced by Abdulkadiroğlu andSönmez (2003) who apply Gale and Shapley’s (1962) agent-proposing deferred acceptance algorithm in a college admissions problem to an indivisible goods resource allocation problem. Given attype-t profile Rt ∈ P(X t )N , the deferred acceptance (DA) type-rule induced by a prioritytprofile �t , denoted by DA� , selects a type-t allocation as follows.
Step 1: Each agent applies to the most favorite object according to her preference. Each object
selects agents from its applicants up to its quota according to its priority and tentatively keeps
them. Any remaining agents are rejected.
Step k(≥ 2): Each agent who was rejected in the previous step applies to her next favorite object
according to her preference. Each object selects agents from its new applicants and the tentatively
kept agents up to its quota according to its priority and tentatively keeps them. Any remaining
agents are rejected.
The algorithm terminates when no agent is rejected.
tRemark 6. For each type t ∈ T and each type-priority profile �t ∈ P(N t )X , the DA type-rule
induced by �t is strategy-proof and non-wasteful (Balinski and Sönmez, 1999), and thus is individually rational by Remark 2.21
Definition 3. The market-wise deferred acceptance (DA) rule induced by a prioritytprofile �= (�t )t∈T , denoted by DA� , selects its type-t allocation as DA� (Rt ) that is chosen
by the DA type-rule induced by type-t priority profile �t .
Remark 7. By Remarks 3 and 6, a market-wise DA rule is strategy-proof and individually rational.
However, the example in Introduction can be used to show that for some priority profile such as
in Table 3, each DA type-rule is Pareto eﬃcient but its market-wise DA is not Pareto eﬃcient.

3.3

Market-wise serial dictatorship (SD) rule

The serial dictatorship (SD) rule for a type-t market with respect to a priority order ≥t ∈ P(N t ),twritten as SD≥ , is described as follows: for each type-t preference profile, letting the highestpriority agent with respect to ≥t have her best object, the second-highest-priority agent withrespect to ≥t have her best among those remaining, and so on.
21

Ergin (2002) characterizes the priority profiles under which the type-t DA rule is Pareto eﬃcient. Kesten (2006)
characterizes the priority profiles under which the type-t TTC rule is fair in terms of envies at the selected type-t
allocation.

12

Note that given a priority order ≥t ∈ P(N t ), the serial dictatorship rule for a type-t market
with respect to ≥t is strategy-proof and Pareto eﬃcient, and moreover coincides with the TTCt
and DA rules for a type-t market with the priority profile �t ∈ P(N t )X in which for each object
xt ∈ X t , �txt =≥t .
Definition 4. The market-wise serial dictatorship (SD) rule induced by a list of priority
�torders ≥= (≥t )t∈T ∈ t∈T P(N t ), denoted by SD≥ , selects its type-t allocation as SD≥ (Rt )that is chosen by the SD type-rule induced by type-t priority order ≥t .
Remark 8. Note that by Remarks 2 and 3, a market-wise SD rule is strategy-proof and individually
rational. However, the example in Introduction can be used to show that it is not Pareto eﬃcientfor the priority profile in Table 3.
Remark 9. The serial dictatorship (SD) rule induced by a priority ≥∗ ∈ P(N ) selects an allocationfor each profile R ∈ D as follows: The highest-priority agent under ≥∗ receives her best bundle,
the second-highest-priority agent under ≥∗ receives her best bundle among remaining objects, andso on.
Note that the SD rule induced by ≥∗ coincides with the market-wise SD rule induced by (≥t )t∈T
when the type-t priority ≥t is the same as in ≥∗ |N t . In this sense the SD rule is a special case of
the market-wise SD rule.

4

Main Results

It is known that strategy-proofness and Pareto eﬃciency are compatible in our setting (Monte andTumennasan, 2013). The leading example is a serial dictatorship rule in which agents choose theirfavorite bundle one by one according to a fixed priority order (Remark 9). However, the rule isextremely unfair. For example, when agents have homogeneous preferences and each type object
is of unit quotas, the highest priority agent receives her best object for all types which are envied
by all of the other agents. A natural way to mitigate this extreme unfairnass is to alternate thedictator across types. As we saw in the previous section, we have a rich class of strategy-proof rules
each of whose type rules satisfy a weaker eﬃciency notion of non-wastefulness. Because these might
not be Pareto eﬃcient in general, we turn to a weaker notion of eﬃciency - second-best eﬃciency- rather than Pareto eﬃciency, while focusing on strategy-proof rules: a rule ϕ is second-best
incentive compatible if ϕ is strategy-proof and no strategy-proof rule dominates ϕ. In otherwords, a second-best incentive compatible rule is in the Pareto frontier of the set of strategy-proof
rules.22
We now state the main result of this paper. The proof is in Appendix B.
t

Theorem 1. Suppose that a rule ϕ is independent and for each t ∈ T , its type rule Φt : P(X t )N →At is strategy-proof and non-wasteful. Then, ϕ is second-best incentive compatible.
22

Our research direction here can be summarized as follows: Find the best (the most eﬃcient) strategy-proof
rules. Another natural direction is : Find the best (the most invulnerable to the strategic behaviors) eﬃcient rules.
Pathak and Sönmez (2013) and Chen, Egesdal, Pycia, and Yenmez (2014) study how to make a ranking of rules bymanipulability among stable rules in a single-type market.

13In other words, if we adopt a strategy-proof and non-wasteful rule for each type market, theoverall rule is second-best incentive compatible. In this sense, Theorem 1 supports both the independent operation of type markets currently done in most real-life markets, and our current
practices in Market Design - independent consideration of the design of each type market.
Since TTC type-rules and DA type-rules are strategy-proof and non-wasteful (Remarks 4 and6), we have the following immediate corollaries.
�tCorollary 1. For each priority profile �∈ t∈T P(N t )X , the market-wise top trading cycles rule
T T C � is second-best incentive compatible.23
�tCorollary 2. For each priority profile �∈ t∈T P(N t )X , the market-wise deferred acceptancerule DA� is second-best incentive compatible.
To state our next corollary, we introduce a multiple-type housing market which is avariant of multiple-type markets.24 A multiple-type housing market is a multiple-type market(N, T, (Ti )i∈N , (X t )t∈T , q, ω) in which the outside options do not necessarily exist. In this paragraph only, we do not assume Assumption 1. Instead we only assume that for each t ∈ T ,�tt
xt ∈X t q(x ) ≥ |N |, i.e., there are enough objects for each agent to receive an object in eachmarket in which she is interested. The allocation ω ∈ A describes the system of property rights
in the economy. We interpret that agent i has the property right for the object wit . Note that thepure distributional case, i.e., no agent has the property right in each market, is a special case of
our model. In this case, for each t ∈ T and each i ∈ N t , ωit = ot . Our model is a generalization of
the model in Konishi, Quint, and Wako (2001) and Klaus (2008) in the following four points. (i)Some agents may be interested only in a fraction of T . (ii) For each t ∈ T , |X t | may not be equal
to |N t |. (iii) We do not exclude multiple quota. (iv) We do not exclude indiﬀerence in preferences.
A market-wise top trading cycles rule for a multiple-type housing market is the one�t
induced by a priority profile �= (�t )t∈T ∈ t∈T P(N t )X such that for each type t ∈ T and each
type-t object xt , if an agent i ∈ N t is an owner of xt , namely xt = ωit , then for each j ∈ N t withj �txt i, j is also an owner of xt . In this setup, we have the following result.
Corollary 3. (Klaus, 2008) Every market-wise top trading cycles rule for a multiple-type housing
market is second-best incentive compatible.25
Our Corollary 3 is more general than Klaus’s (2008) original result due to the above four
diﬀerences in the setup. Furthermore, Theorem 1 is a substantial extension of Klaus’s result, as we
use non-wastefulness for type rules instead of Pareto eﬃciency implied by the TTC type-rule.26
If we turn to single-type markets, we have the following corollaries:
23

In a single-type market, a TTC rule is in a subclass of Pápai’s (2000) hierarchical exchange rules or Pycia andÜnver’s (2009) trading cycles rules that are group strategy-proof and Pareto eﬃcient. Thus, by Theorem 1, if we
adopt theirs as type rules, the resulting rule is second-best incentive compatible.
24
This model is sometimes referred to as the generalized Shapley-Scarf housing market. Here, we present a further
generalized version of the model in which multiple quotas are allowed.
25
Rigorously speaking, Corollary 3 is not a direct consequence of Theorem 1 due to Assumption 1. However, ourproof immediately implies Corollary 3, which is given in the Appendix.
26
To employ non-wastefulness for type rules instead of Pareto eﬃciency causes a technical diﬃculty. A discussion
on this point can be found in the Appendix.

14

Corollary 4. (Kesten, 2010) In a single-type market, there is no strategy-proof and Paretoeﬃcient rule that dominates the deferred acceptance rule. 27
Corollary 5. (Abdulkadiroğlu, Pathak, and Roth, 2009; Kesten and Kurino, 2013;
Erdil, 2014). In a single-type market, the deferred acceptance rule is second-best incentive compatible.
Corollary 6. (Erdil, 2014) In a single-type market, a strategy-proof and non-wasteful rule issecond-best incentive compatible.
Corollaries 5 and 6 are respectively counterparts of Corollary 2 and Theorem 1 for a singletype market. However, note that we cannot show Corollary 2 (Theorem 1) by applying Corollary 5(Corollary 6) to each type market. To see this, let us recall the proof technique in Abdulkadiroğlu,
Pathak, and Roth (2009) and Erdil (2014): Like we do, they suppose for a contradiction that a
strategy-proof rule, ζ, dominates a strategy-proof and non-wasteful rule, ϕ. Then they find someagent i and some profile R with ζi (R) Pi ϕi (R) Pi o, and then use a special kind of manipulation
to upgrade the outside option between ζi (R) and ϕi (R) in i’s preference, which eventually leads toa contradiction. However, this technique does not work in a multiple-type market as the situation
is drastically changed in the following sense: A dominating strategy-proof rule ζ may assign an
object which is worse than the outside option in some type markets, because the domination only
requires that the bundle assigned by ζ is at least as good as the bundle assigned by ϕ. Thatis, it is possible that ϕti (R) Pit ot Pit ζit (R) for some type-t. 28 Note that this situation does not
violate ζi (R) Ri ϕi (R) in a multiple-type market. Hence each type-rule in a multiple-type market
behaves very diﬀerently from a rule in a single-type market.
Before we close this section, let us emphasize the technical advantages of our result. Notethat our result is valid in various preference domains including the additively separable weak
preference domain. It is known that several technical diﬃculties arise from the indiﬀerence insingle-type markets (Erdil and Ergin, 2007). Although type preferences are assumed to be strict,
Theorem 1 indicates that the second-best incentive compatibility is robust for the indiﬀerence withrespect to bundles. Furthermore, as pointed out in Kesten and Kurino (2013), the second-best
incentive compatibility is sensitive to domain restriction. Since the set of additively separable strict
preferences is smaller than the set of all separable strict preferences (See Remark 1), Theorem 1− more precisely, the preference construction given in Lemma 1 in the Appendix − clarifies atechnical limitation of domain restriction for the second-best incentive compatibility result.

5Market Design Applications

We briefly describes the representative type-markets and those propsed type-rules discussed in theliterature. The type-rules taken up in each subsection are strategy-proof and at least non-wasteful.
27

We note however that Kesten’s (2010) original theorem is also valid when the outside option does not exist.
Remember that we assume that ϕ is independent and each type-rule Φt is strategy-proof and non-wasteful in
Theorem 1. Thus, for each t ∈ T , ϕti (R) Ri ot .
28

15

Theorem 1 implies that an independent rule of using those type-rules in these type markets issecond-best incentive compatible.

5.1

House allocation with existing tenants

Abdulkadiroğlu and Sönmez (1999) introduce the problem that deals with the on-campus housing
assignments for U.S. college students. The problem can be applied not only to the on-campus
housing assignment but also the public housing assignment. In this setting, the set N t of agentsis divided into the set NNt of newcomers and the set NEt of existing tenants, while objects refer tohouses. Corresponding to each existing tenant i ∈ NEt is a unique occupied house ωit ∈ X t \ {ot }which is interpreted as the house that agent i currently lives in. Each newcomer is assumed tooccupy the outside option ot .
To remedy the welfare losses observed in practice, inspired by Gale’s celebrated assignment
method, Abdulkadiroğlu and Sönmez (1999) propose the top trading cycles (AS-TTC) typerule induced by a priority ordering ≥t ∈ P(N t ). The type-rule is the TTC-type rule induced by
the following type-t priority profile �t that is introduced in Section 3.1: 29 For each xt ∈ X t , let
N t (xt ) := {i ∈ N t |ωit = xt } be the set of agents who occupy xt . Note that N t (xt ) can be empty.
Then, for each xt ∈ X t , �txt satisfies: (i) �txt |N t \N t (xt ) =≥t |N t \N t (xt ) , and (ii) for each {i, j} ⊆ N t ,if i ∈ N t (xt ) and j �txt i , then j ∈ N t (xt ).
Abdulkadiroğlu and Sönmez (1999) show that the AS-TTC type-rule is strategy-proof andPareto eﬃcient, which also follows from Remark 4.

5.2

Kidney exchange

Transplantation is the preferred treatment for patients diagnosed with end-stage kidney disease.
Roth, Sönmez, and Ünver (2004) introduce the problem that aims to eﬃciently organize direct
exchanges among medically incompatible donor-patient pairs as well as indirect exchanges thatinvolve one incompatible donor-patient and deceased donors. In the setting, agents refer to patientsand objects refer to kidneys. Each patient i ∈ N t is paired with a kidney ki ∈ X t \ {ot } withq(ki ) = 1 supplied by her intended donor. Thus |N t | = |X t \ {ot }|. Every patient also has theoption to enter the waiting list for cadaveric kidneys with priority. Let w be the outside option of
waiting lists. 30
Roth, Sönmez, and Ünver (2004) propose an inventory of top trading cycles and chains(TTCC) type-rules as a plausible generalization of the top trading cycles method to this setting.
31
A cycle is an ordered list (k1 , i1 , k2 , i2 , . . . , km , im ) such that kidney k1 points to patient i1 ,patient i1 points to kidney k2 , ..., kidney km points to patient im , and patient im points to kidney29

We modify the original description of AS-TTC type rule to use our description of the TTC type-rule in Section

3.1.
30

Unlike the original framework of Roth, Sönmez, and Ünver (2004) that allows for strict preferences, later modelsof the kidney exchange deal with dichotomous preferences (e.g., Roth, Sönmez, and Ünver, 2005; Yilmaz, 2011).
31
In what follows, for breavity we do not provide a self-contained and thorough description of TTCC type-rules.
We refer the reader to Roth, Sönmez, and Ünver (2004) for a comprehensive account of the rule. See also Sönmez
and Ünver (2013).

16

k1 . A w-chain is an ordered list (k1 , i1 , k2 , i2 , . . . , km , im ) such that kidney k1 points to patient i1 ,patient i1 points to kidney k2 , ..., kidney km points to patient im , and patient im points to w.
The TTCC algorithm is based on iteratively identifying cycles and w-chains in a directed graphand carrying out the induced trades. 32 The way w-chains are handled in the algorithm depends on
the so-called chain selection rule. Roth, Sönmez, and Ünver (2004) discuss various chain selection
rules and investigate their implications for welfare and incentives. Of particular interest to us
among these are those rules that induce strategy-proofness and Pareto eﬃciency of TTCC.

5.3

School choice

Abdulkadiroğlu and Sönmez (2003) introduce the problem that concerns student assignment topublic schools. In this context agents refer to the students, objects refer to the schools, and theoutside option represents other education options such as private schools. Additionally, each schoolxt ∈ X t has a priority �txt over students which is a linear order in P(N t ).
A school choice problem (Abdulkadiroğlu and Sönmez, 2003) is a type market with a typepriority profile. Thus our descriptions of the TTC type-rule and the DA type-rule in Section 3
are for a school choice problem. Thus the TTC type-rule is strategy-proof and Pareto eﬃcient(Remark 4) and the DA type-rule is strategy-proof and non-wasteful (Remark 6).

6

Conclusion

In this paper, we consider eﬃciency for strategy-proof rules in a multiple-type market. The fulleﬃciency is strong enough that we end up with an extremely unfair rule such as the serial dictatorship (Monte and Tumennasan, 2013). We turn to a weaker eﬃciency notion of the second-best
incentive compatibility that requires a rule to be strategy-proof and not be dominated by any otherstrategy-proof rules. Our main result is the second-best incentive compatibility of a market-wise
application of non-wasteful and strategy-proof type rules that include the two well-known prioritybased rules of top trading cycles (TTC) and deferred acceptance (DA). This result shows a richclass of simple and reasonable strategy-proof rules are included in the Pareto frontier of strategyproof rules, and moreover supports our practices of designing a type rule to be strategy-proof andat least non-wasteful in Matching Market Design.
We now discuss the existence of the outside options in Assumption 1. As Kesten and Kurino(2013) point out, Corollary 6 does not hold when there is no outside option: For example, consider
a single-type market with n agents and n objects with unit quotas. Then, a constant allocation
rule is strategy-proof and non-wasteful. However, the rule is dominated by the corresponding corerule which is also strategy-proof. With the same logic, our main result of Theorem 1 no longer holds
32

Although there are clear similarities between the AS-TTC type-rule in a house allocation problem with existing
tenants and the TTCC type-rule in the kidney exchange problem, the adaptations of the top trading cycles method
diﬀer in terms of the role the outside option plays. In the former context the outside option always points to thehighest priority agent, whereas in the latter context, the w-option never points to any agent. This subtle nuance is
one main source of the diﬀerence between the two rules, and the reason why TTCC type-rules are not described asa special case of the TTC type-rules introduced in Section 3.1.

17

without Assumption 1. As Kesten and Kurino (2013) show, for a single-type market without theoutside option, the DA rule is second-best incentive compatible. It is an interesting open question
to prove that for a multiple-type market without outside options, the market-wise DA rule issecond-best incentive compatible.
In this paper we have focused on deterministic rules. There is a growing literature on lottery
rules in matching problems (e.g., Abdulkadiroğlu and Sönmez, 1998; Bogomolnaia and Moulin,
2001; Che and Kojima, 2010). Although the counterpart of Theorem 1 for lottery rules for asingle-type market are still true, Erdil (2014) show that the counterpart cannot be applied to aninteresting class of lottery rules such as the random serial dictatorship (RSD) which randomly
selects a priority and implements the serial dictatorship for the realized priority because RSD iswasteful. Moreover, we have not yet known any strategy-proof and non-wasteful lottery rule evenin a single-type market. Hence we doubt the usefulness of the extension of our Theorem 1 to lottery
rules in a multiple-type market. Therefore the future direction that we could take in the same
spirit of our paper is to find a general strategy-proof rule dominating a practical strategy-proof
rule. For a single-type market, Erdil constructed an artificial lottery rule that is strategy-proof anddominates RSD. However, his rule is quite limited to a small economy and a general dominating
rule against stochastic DA or TTC is not known yet. Thus it is an interesting open question as
to how much room we can have against those interesting lottery rules for eﬃciency while keeping
strategy-proofness. We believe that this paper could be a benchmark in this direction, and could
clarify technical limitations and provide technical tools for the question.

A

Appendix: Proof of Remark 1

Claim 1. Padd (Xi ) �= Psep (Xi ).
Proof. The proof idea is similar to the one in page 43 in Fishburn (1970) that shows Radd (Xi ) �
Rsep (Xi ). Suppose that X 1 = X 2 = {x, y, z} and Xi = X 1 × X 2 . Let Ri be the preference suchthat(x, x) Pi (x, y) Pi (y, x) Pi (z, x) Pi (y, y) Pi (x, z) Pi (y, z) Pi (z, y) Pi (z, z).
Obviously Ri ∈ Psep (Xi ). We show Ri �∈ Padd (Xi ). Suppose to the contrary that (u1 , u2 ) ∈ U 1 × U 2
represents Ri . Since (z, x) Pi (x, z) and (y, z) Pi (z, y), u1 (z) + u2 (x) > u1 (x) + u2 (z) andu1 (y) + u2 (z) > u1 (z) + u2 (y). Thus u1 (z) + u2 (x) + u1 (y) + u2 (z) > u1 (x) + u2 (z) + u1 (z) + u2 (y).
Cancelling out u1 (z) and u2 (z), we obtain u1 (y) + u2 (x) > u1 (x) + u2 (y). This violates that(x, y) Pi (y, x).

B

Appendix: Proof of Theorem 1

We first introduce some notations: For each �∈ R(Y ) and each y ∈ Y , let UC(�, y), SUC(�, y),LC(�, y) and SLC(�, y) be the upper, strict upper, lower, and strict lower contour set of � at y,18

respectively. That is, UC(�, y) := {z ∈ Y |z � y}, SUC(�, y) := {z ∈ Y |z � y and not y � z},LC(�, y) := {z ∈ Y |y � z} and SLC(�, y) := {z ∈ Y |y � z and not z � y}.
Before we prove Theorem 1, we provide four lemmas. Lemma 1 states that the domain D isrich enough to choose the preferences we need in the proofs of subsequent lemmas and theorem.
Lemma 1. Let i ∈ N . Let (R̃it ) ∈(i) ∀t ∈ Ti , Rit = R̃it and�tt∈Ti P(X ) and x̃i ∈ Xi . There exists Ri ∈ Padd (Xi ) such that(ii) ∀xi ∈ Xi , [{∃t ∈ Ti s.t. xti ∈ SLC(R̃it , x̃ti )} ⇒ x̃i Pi xi ].
t

Proof. Without loss of generality, suppose that Ti = T . For each t ∈ T , let X t = {xt1 , · · · , xt|X | },tand assume, without loss of generality, that xt1 R̃it xt2 R̃it · · · R̃it xt|X | . For each t ∈ T , let�kt ∈ Z++ be the cardinality of UC(R̃it , x̃ti ) where xtkt = x̃ti . Let kt� := |X t | − kt , K := t∈T kt and��K � := t∈T kt� . Define (uti ) ∈ t∈T U t as follows:
u1i (x11 ) = 10K−1 ,

u1i (x12 ) = 10K−2 ,

u2i (x21 ) = 10K−(k1 +1) ,..
.

u2i (x22 ) = 10K−(k1 +2) ,
..
.

|T |

ui (x|T |1 ) = 10K−(

�|T |−1
t=1

kt +1),|T |ui (x|T |2 ) = 10K−(

�|T |−1t=1

u1i (x1k1 ) = 10K−k1 ,···u2i (x2k2 ) = 10K−(k1 +k2 ) ,
..
.

···

kt +2)

,

···

|T |

ui (x|T |k|T | ) = 10K−(

�t∈T kt )(= 100 ).

�
Let C � := 2 t∈T uti (xt1 ) and C := C � + 1. 33 In the following, for each t ∈ T , if kt� = 0, thenthe corresponding row should be skipped.
1
u1i (x1(k1 +1) ) = 10
− C,

u1i (x1(k1 +2) ) = 1012 − C,

u2i (x2(k2 +1) ) = k1� +1 − C,
10 1
..
.
|T |

ui (x|T |(k|T | +1) ) =1

�|T |−1 �
10 t=1 kt +1···

u2i (x2(k2 +2) ) = k1� +2 − C,
10 1
..
.
− C,

|T |

�

ui (x|T |(k|T | +1) ) =1

�|T |−1 �
10 t=1 kt +2

···
− C,

···

1

1
� − C,10k1
2
u2i (x2|X | ) = k�1+k� − C,
10 1 2u1i (x1|X | ) =
..
.

|T |

ui (x|T ||X

|T |

|

1

)=
10

�|T | �t=1 ktNow, we define Ri ∈ R(Xi ) as follows: for each {yi , zi } ⊆ Xi ,yi Ri z i ⇔�t∈Tuti (yit ) ≥�uti (zit ).

t∈TObviously, Ri ∈ Radd (Xi ) ⊆ Rsep (Xi ). It is also obvious that (Rit )t∈T = (R̃it )t∈T , i.e., Item (i) is
satisfied.
We show that Ri satisfies Item (ii). Let yi ∈ Xi be such that for some t ∈ T , yit ∈ SLC(Rit , x̃ti ).
Note that yi has at least one coordinate whose utility contains the −C term while x̃i does not.
��
Therefore, t∈T uti (x̃ti ) > 0 > t∈T uti (yit ). Thus, x̃i Pi yi . Thus, Item (ii) is satisfied.
Finally, we prove that Ri ∈ Padd (Xi ). By construction, Ri ∈ Radd (Xi ). Since Padd (Xi ) =��Radd (Xi ) ∩ P(Xi ), we need to show Ri ∈ P(Xi ). Let yi , zi be such that t∈T uti (yit ) = t∈T uti (zit ).

Note that C � is greater than the utility obtained by the bundle (x11 , · · · , x|T |1 ) which is the best bundle according
to the resulting preference Ri .
33

19

− C.

First, we claim that the number of types in which the type object is worse than x̃ti is the same
between yi and zi .
Claim 2. |{t ∈ T |x̃ti Pit yit }| = |{t ∈ T |x̃ti Pit zit }|.

Let α := |{t ∈ T |x̃ti Pit yit }| and β := |{t ∈ T |x̃ti Pit zit }|. Suppose to the contrary that α �= β.
Assume, without loss of generality, that α < β. We can decompose the utility into three parts:�uti (yit ) =t∈TSince 0 ≤ (��uti (yit ) + (t∈T
yit Rit x̃ti

�t∈T
x̃ti Pit yit

uti (yit ) + αC) − αC.

t tt∈T ui (yi ) + αC) < 1, we havex̃ti Pit yit�uti (yit ) − αC ≤

�uti (yit ) ≤�uti (zit ) − βC ≤

�uti (zit ) ≤t∈T
yit Rit x̃tit∈T�uti (yit ) + 1 − αC.

�uti (zit ) + 1 − βC.

t∈Tyit Rit x̃ti

Similarly, we havet∈T
zit Rit x̃ti

t∈T

t∈T
zit Rit x̃ti

Thus, we have
(

�

t∈T
yit Rit x̃ti

uti (yit ) − αC) − (�t∈Tzit Rit x̃ti

≥ −1 + (− 12 C � ) + (β − α)Cuti (zit ) + 1 − βC) = −1 + (
�

∵

�

t∈T
yit Rit x̃ti

uti (yit ) −= −1 + (− 12 C � ) + (β − α)C � + (β − α) ≥ 12 C � > 0.

�t∈T
yit Rit x̃ti�t∈Tzit Rit x̃ti

uti (yit ) −�t∈T
zit Rit x̃ti

uti (zit )) + (β − α)C

1 �
uti (zit ) ≥ − C �
2(∵ α < β)

�
�
t t
t t
Thus,
t∈T ui (zi ) <t∈T ui (yi ), a contradiction. Thus, α = β. The proof of the Claim iscompleted.
�t t
Now we complete the proof of Ri ∈ P(Xi ). Let us express Y :=t∈T ui (yi ) + αC as a
(K + K � ) digits rational number. That is, Y = Y1 Y2 · · · YK .YK+1 YK+2 · · · YK+K � . 34 Note that by
the construction, each digit is equal to 1 or 0. Note also that (Y1 , · · · , Yk1 , YK+1 , · · · , YK+k1� ) tells
us which type-1 object is assigned at yi since for each k ∈ {1, · · · k1 , K + 1, · · · , K + k1� }, Yk = 1 if
and only ifx1k
if 1 ≤ k ≤ k1
1yi =
x1(k−K+k1 ) otherwise
In general, for t ≥ 2, (Y�t� <t kt� +1 , · · · , Y�t� ≥t kt� , YK+�t� <t kt� � +1 , · · · , YK+�t� ≥t kt� � ) tells us the typet object at yi . Therefore, we can identify the bundle yi with the value of Y . Similarly, let
34

Note that Y1 denotes the 10K−1 ’s place of Y (which may be 0), Y2 denotes the 10K−2 ’s place of Y (which may
1be 0) and so on. Similarly, YK+1 denotes the 10’s place of Y , YK+2 denotes the 1012 ’s place of Y and so on.

20

Z :=

�

t t
t∈T ui (zi ) + βC and�

Z = Z1 Z2 · · · ZK .ZK+1 ZK+2 · · · ZK+K � .
�

t t
t t
t∈T ui (yi ) =t∈T ui (zi ) andt tt∈T ui (zi ) + βC = Z. Thus, yi = zi .

Since
�

α = β (∵ Claim), we have Y =�t tt∈T ui (yi ) + αC=

We introduce notations: For each i ∈ N , each t ∈ Ti , each Rit ∈ P(X t ), each Ri ∈ Di and eachR ∈ D, let
B(Rit ) := |SUC(Rit , ot )|,�
B(Ri ) :=B(Rit ), andt∈Ti

B(R) :=

�

B(Ri ).

i∈N

Namely, B is the operator that assigns the number of object(s) which are preferred to the outside
option(s). For each R ∈ D, let I(R) be the number of agents whose preferences are not strict at
R, i.e.,I(R) := |{i ∈ N |Ri �∈ P(Xi )}|.
The following two notions are the key to the proof of Theorem 1. Given R ∈ D, an allocationa ∈ A coordinate-wise weakly dominates b ∈ A at R, written as a cw-dom(R) b, if∀i ∈ N, ∀t ∈ Ti , ati Rit bti .
Given a pair of rules (ζ, ϕ), a profile R ∈ D satisfies the (ζ, ϕ)−reverse property if��
∃i ∈ N s.t. ζi (R) Pi ϕi (R) and {∃t ∈ Ti s.t. ϕti (R) Pit ζit (R)} . 35

Let us sketch the proof of Theorem 1. 36 The proof shall be done by a contradiction. Therefore,
we assume that there exists a strategy-proof rule ζ which dominates ϕ. Let R(1) ∈ D be such that
ζ(R(1) ) dominates ϕ(R(1) ) at R(1) . Starting from this, we inductively construct two sequences of(k) ∞non-negative integers {N (k) }∞}k=1 satisfying Items (seq-i) and (seq-ii).
k=0 and {B(0)(seq-i) {N (k) }∞≥ N (1) ≥ N (2) ≥ · · · .
k=0 is weakly decreasing, i.e., N(seq-ii) If N (k−1) does not decrease (N (k−1) = N (k) ), then the corresponding part of {B (k) }∞
k=1
(k−1)
(k)
(k)
(k+1) 37
decreases, i.e., for each k ∈ N, if N
= N , then B > B.
(k+1)

In each induction step of the proof, we shall choose an agent i(k) and her new preference Ri(k) ,
(k+1)
(k)
and define N (k) := |N \{i(1) , · · · , i(k) }| and B (k+1) := B(Ri(k) ; R−i(k) ). It is a process of successive
35

Note that if ζ dom ϕ and R ∈ D satisfies (ζ, ϕ)−reverse property, then ζ(R) dom(R) ϕ(R).
Our proof is greatly inspired by the one in Klaus (2008).
37
Note that these sequences cause a contradiction since sequences of non-negative integers cannot meet both(seq-i) and (seq-ii).
36

21

preference replacements to satisfy Item (seq-ii) as Item (i) is automatically satisfied by definition,
which is made possible by the (ζ, ϕ)-reverse property at the profile under consideration. 38 The
simplest case is when every profile satisfies the reverse property. One such simple case is: each�
type-rule Φt is Pareto eﬃcient and D = i∈N Psep (Xi ). 39
However, the assumptions of Theorem 1 navigate away the above situation in two ways. First,
we only assume non-wastefulness for each type rule instead of Pareto eﬃciency. Second, thepreference domain contains weak preferences. Even under one of these weak assumptions, it iseasy to show that a given preference profile may not satisfy the (ζ, ϕ)-reverse property. For(k) ∞this reason, in addition to the process constructing {N (k) }∞}k=1 (let us call it the
k=0 and {Bconstructing process), we need another process to transit from a profile without the (ζ, ϕ)-reverse
property toward a profile with the (ζ, ϕ)-reverse property (let us call it the transition process).
Lemmas 2 to 4 show how we transit from one profile to another. Under a given profile without
the (ζ, ϕ)-reverse property, we use two types of transition according to whether the coordinatewise weak domination occurs in the profile or not. Lemma 2 describes the transition when thedomination occurs, while Lemma 3 describes when the domination does not. Lemma 4 guarantees
that repeating these transitions, we finally reach a profile with the (ζ, ϕ)-reverse property. In
sum, the proof of Theorem 1 is the constructing process in which each step contains the transition
process. 40
Note that both the constructing process and the transition process contain preference replacements of agents. When we prove that the resulting sequences satisfy (seq-ii), we need the following:
once an agent is involved in the preference replacement with respect to the constructing process,she is never involved in the preference replacement with respect to the subsequent transition process. In other words, we need to design the transition process so as not to disturb the constructing
process. This trick is realized by Items (lem2-1), (lem3-1) and Item (i) in Lemma 4.
Now, we present Lemma 2. It tells us how we transit from a profile if the coordinate-wise weakdomination occurs in the profile. Item (lem2-2) is needed to terminate the induction process inLemma 4 in a finite number of steps, and it is also needed to prove Item (ii) in Lemma 4, which isalso a trick to prove that two sequences in the proof of Theorem 1 satisfies (seq-ii). Item (lem2-3)
guarantees that the induction argument in Lemma 4 bites.
tLemma 2. Suppose that a rule ϕ is independent and for each t ∈ T , Φt : P(X t )N → At is
strategy-proof and non-wasteful. Suppose also that a strategy-proof rule ζ dominates ϕ. Let R ∈ D
be such that ζ(R) dom(R) ϕ(R). If ζ(R) cw-dom(R) ϕ(R), then there exist i ∈ N and Ri� ∈ Di
such that(lem2-1) ∃ t ∈ Ti s.t. ζit (R) Pit ϕti (R) Pit ot ,(lem2-2) B(Ri� ; R−i ) < B(R) and I(Ri� ; R−i ) ≤ I(R), andThe detailed construction of a new preference is indicated by conditions (1∗ − i), (1∗ − ii), (k ∗ − i) and (k ∗ − ii)in the proof of Theorem 1.
39
See Lemma 1 in Klaus (2008).
40
Therefore, the profiles in the proof of Theorem 1 are doubly indexed. The first index indicates the steps of theconstructing process, and the second index indicates the steps of the transition process.
38

22

(lem2-3) ζ(Ri� ; R−i ) dom(Ri� ; R−i ) ϕ(Ri� ; R−i ).
Proof. First, we show that there exists i ∈ N satisfying (lem2-1). Suppose to the contrary thatfor each i ∈ N and each t ∈ Ti , [ϕti (R) Pit ot ⇒ ϕti (R) Rit ζit (R)]. Since ζ(R) cw-dom(R) ϕ(R), thehypothesis is equivalent to∀i ∈ N, ∀t ∈ Ti , [ϕti (R) Pit ot ⇒ ϕti (R) = ζit (R)].

(1)

Claim 3. ∀i ∈ N, ∀t ∈ Ti , [ϕti (R) = ot ⇒ ζit (R) = ot ].
Suppose not. Let i ∈ N and t ∈ Ti be such that ϕti (R) = ot and ζit (R) �= ot . Let xt := ζit (R) andat := (ϕti (R))i∈N t . We show that at least one unit of the object xt is not assigned to any agent
at the type-t allocation at . By (1), for each j ∈ N t , [atj = xt ⇒ ζjt (R) = xt ]. Thus, since ati = otand ζit (R) = xt , we have |{j ∈ N t |atj = xt }| < |{j ∈ N t |ζjt (R) = xt }| ≤ q(xt ). However, sinceζ(R) cw-dom(R) ϕ(R) and type preferences are strict, xt = ζit (R) Pit ϕti (R) = Φti (Rt ), a violationof non-wastefulness of Φt . This completes the proof of the Claim.
Note that by Remark 2, Φt is individually rational. Thus, by (1) and the Claim, for eachi ∈ N and each t ∈ Ti , ϕti (R) = ζit (R). Thus, ϕ(R) = ζ(R), which violates our assumption that
ζ(R) dom(R) ϕ(R). Therefore, there exists i ∈ N satisfying (lem2-1).
Next, let i ∈ N and t0 ∈ Ti be such that ζit0 (R) Pit0 ϕti0 (R) Pit0 ot0 . We show that there exists
a preference Ri� ∈ Di which satisfies (lem2-2). First, we define a list of type preferences (R̃i�t )t∈Ti .
In words, (R̃i�t )t∈Ti is obtained from (Rit )t∈Ti by changing the ranking of ot0 just above ϕti0 (R) while
the relative rankings of any other objects stay the same. Formally, (R̃i�t )t∈Ti is defined as follows;• [∀t ∈ Ti \{t0 }, R̃i�t = Rit ] and R̃i�t0 |(X t0 \{ot0 })×(X t0 \{ot0 }) = Rit0 |(X t0 \{ot0 })×(X t0 \{ot0 }) ,• ot0 P̃i�t0 ϕti0 (R) and• � ∃xt0 ∈ X t0 \{ot0 , ϕti0 (R)} s.t. ot0 R̃i�t0 xt0 R̃i�t0 ϕti0 (R).
By applying Lemma 1 for (R̃i�t )t∈Ti and ζi (R), we can choose a preference Ri� ∈ Padd (Xi ) such that∀xi ∈ Xi , [{∃t ∈ Ti s.t. xti ∈ SLC(Ri�t , ζit (R))} ⇒ ζi (R) Pi� xi ].

(2)

By (lem2-1) and the construction of (Ri�t )t∈Ti , B(Ri� ) < B(Ri ). Therefore, B(Ri� ; R−i ) < B(R).
Since Ri� ∈ Padd (Xi ), I(Ri� ; R−i ) ≤ I(R).
t0
Finally, we show (lem2-3). Since Φt0 is strategy-proof and individually rational, Φti0 (Ri�t0 ; R−i)=�ttot0 . Note that since ot0 ∈ SLC(Ri 0 , ζi 0 (R)), by (2), we have ζi (R) Pi� ϕi (Ri� ; R−i ). Thus, bystrategy-proofness of ζ, ζi (Ri� ; R−i ) Pi� ϕi (Ri� ; R−i ). Since ζ dom ϕ, we are done.
Next we present Lemma 3. It tells us how we transit from a profile if the coordinate-wise
weak domination does not occur in the profile. Item (lem3-2) is needed to terminate the induction
process in Lemma 4 in a finite number of steps, and it is also needed to prove Item (ii) in Lemma
4, which is also a trick to prove that two sequences in the proof of Theorem 1 satisfies (seq-ii).
Item (lem3-3) guarantees that the induction argument in Lemma 4 bites.
23

To prove Lemma 3, we need a class of preferences. Let Σ(Ti ) be the set of bijections from
{1, · · · , |Ti |} to Ti . A preference Ri ∈ R(Xi ) is lexicographic if there are σ ∈ Σ(Ti ) and list
�of type preferences (Rit )t∈Ti ∈ t∈Ti P(X t ) such that for each pair of bundles {xi , x�i } ⊆ Xi withxi �= x�i ,σ(1)xi Ri x�i ⇔ xi

σ(1)

Pi

�σ(1)

xi

�
�
σ(t� )
�σ(t� )σ(t)σ(t) �σ(t)or ∃t ∈ {1, · · · , |Ti |}\{1} s.t.{∀t� < t, xi= xi } and xi Pi xi.

We denote by Plex (Xi ) the set of all lexicographic preferences on Xi . It is easy to show that
Plex (Xi ) ⊆ Padd (Xi ).41t

Lemma 3. Suppose that a rule ϕ is independent and for each t ∈ T , Φt : P(X t )N → At is
strategy-proof. Suppose also that a strategy-proof rule ζ dominates ϕ. Let R ∈ D. If R does notsatisfy the (ζ, ϕ)-reverse property, and not ζ(R) cw-dom(R) ϕ(R), then there exist i ∈ N andRi� ∈ Di such that(lem3-1) Ri �∈ P(Xi ),(lem3-2) I(Ri� ; R−i ) < I(R) and B(Ri� ; R−i ) ≤ B(R), and(lem3-3) ζ(Ri� ; R−i ) dom(Ri� ; R−i ) ϕ(Ri� ; R−i ).
Proof. First, we show that there exists i ∈ N satisfying (lem3-1). Since not ζ(R) cw-dom(R) ϕ(R),there exist i ∈ N and t0 ∈ Ti such that ϕti0 (R) Pit0 ζit0 (R). Thus, since R does not satisfy the (ζ, ϕ)reverse property, we have ϕi (R) Ri ζi (R). Since ζ dom ϕ, ϕi (R) Ii ζi (R). Since ϕi (R) �= ζi (R), we
obtain that Ri �∈ P(Xi ), i.e., (lem3-1).
�
Next we choose Ri� ∈ Di as follows. By Assumption 2, Ri ∈Radd (Xi ). Let (uti )t∈Ti ∈ t∈Ti U t
be a list of type-utility functions which represents Ri . Since uti0 (ϕti0 (R)) > uti0 (ζit0 (R)) and
�
�
t1 t1
t1
t1
t
t
t t
t∈Ti ui (ϕi (R)) =t∈Ti ui (ζi (R)), there exists t1 ∈ Ti such that ui (ζi (R)) > ui (ϕi (R)), i.e.,
41

Proof
of Plex (Xi ) ⊆ Padd (Xi ). Let Ri ∈ Plex (Xi ). Suppose that Ri is characterized by σ ∈ Σ(Ti ) and (Rit )t∈Ti ∈�ttt∈Ti P(X ). Assume, without loss of generality, that Ti = T and σ is the identity mapping, and (Ri )t∈T is such
that
Ri1
x11
x12
..
.

Ri2
x21
x22
..
.

···

···

|T |

Ri
x|T |1
x|T |2..
.

xx
x|T |K|T |�
where for each t ∈ T , Kt := |X t |. Let K := t∈T Kt . Now we define (uti )t∈T ∈ Πt∈T U t as follows:
1K1

u1i (x11 ) = 10K−1
u1i (x12 ) = 10K−2
..
.

2K2

u2i (x21 ) = 10K−K1 −1
u2i (x22 ) = 10K−K1 −2
..
.

···

|T |

�|T |−1

|T |

�|T |

ui (x|T |1 ) = 10K− t=1 Kt −1
�|T |−1|T |ui (x|T |2 ) = 10K− t=1 Kt −2..
.

ui (x|T |K|T | ) = 10K− t=1 Kt .
�
�
t t
t t
Obviously, for each {yi , zi } ⊆ Xi , yi Ri zi if and only ift∈T ui (yi ) ≥t∈T ui (zi ). Thus Ri ∈ Padd (Xi ).
u1i (x1K1 ) = 10K−K1

u2i (x2K2 ) = 10K−(K1 +K2 )24

ζit1 (R) Pit1 ϕti1 (R). Now we change the preference of agent i. Let (Ri�t )t∈Ti := (Rit )t∈Ti and σ ∈ Σ(Ti )be such that σ(1) = t1 . Let Ri� ∈ Plex (Xi ) be the lexicographic preference defined by σ and (Ri�t )t∈Ti(See Remark 1). Obviously, I(Ri� ; R−i ) < I(R) and B(Ri� ; R−i ) = B(R). Thus, Item (3-2) is satisfied.
Finally we show (lem3-3). First, since ϕ is independent and Ri�t1 = Rit1 , ϕti1 (Ri� ; R−i ) = ϕti1 (R).
Second, since ζ is strategy-proof, ζi (Ri� ; R−i ) Ri� ζi (R). Third, since Ri� is a lexicographic preference
whose first priority is assigned to t1 , we have ζit1 (Ri� ; R−i ) Ri�t1 ζit1 (R). Therefore, since ζit1 (R) Pit1
ϕti1 (R) and Ri�t1 = Rit1 , we have ζit1 (Ri� ; R−i ) Ri�t1 ζit1 (R) Pi�t1 ϕti1 (R) = ϕti1 (Ri� ; R−i ). Since Ri� is alexicographic preference whose first priority is on t1 , ζi (Ri� ; R−i ) Pi� ϕi (Ri� ; R−i ). Since ζ dom ϕ, weare done.
The following lemma is the realization of the transition process we employ. Item (i) is thetrick we need when we prove the two resulting sequences of non-negative integers in the proofof Theorem 1 meet the condition (seq-ii). Item (ii) is also a trick used to prove the condition(seq-ii). Item (iii) asserts that the transition process finally reaches a profile which satisfies the(ζ, ϕ)-reverse property.
tLemma 4. Suppose that a rule ϕ is independent and for each t ∈ T , Φt : P(X t )N → At is strategyproof and non-wasteful. Suppose also that a strategy-proof rule ζ dominates ϕ. Let R(0) ∈ D besuch that ζ(R(0) ) dom(R0 ) ϕ(R(0) ). If R(0) does not satisfy the (ζ, ϕ)-reverse property, then there(�)
exists a finite sequence of agent-preference pairs {(j (�) , Rj (�) )}L�=1 satisfying the following conditions
(�)

(�−1)

(i), (ii) and (iii). For each � = 1, · · · , L, let R(�) := (Rj (�) ; R−j (�) ).

��(�−1)t(�−1)(i) ∀� = 1, · · · , L, {∃t ∈ Tj (�) s.t. |SUC(Rj (�) , ot )| ≥ 2} or Rj (�) �∈ P(Xj (�) )(ii) B(R(0) ) ≥ B(R(1) ) ≥ · · · ≥ B(R(L) ), and(iii) R(L) satisfies the (ζ, ϕ)-reverse property.
Proof. We inductively construct a sequence.
(1)
Step 1: If ζ(R(0) ) cw-dom(R(0) ) ϕ(R(0) ), then by Lemma 2, there exist j (1) ∈ N and Rj (1) ∈ Dj (1)satisfying (lem2-1), (lem2-2) and (lem2-3). If not, then by Lemma 3, there exist j (1) ∈ N and(1)
Rj (1) ∈ Dj (1) satisfying (lem3-1), (lem3-2) and (lem3-3). Then, by (lem2-1) or (lem3-1), {there
(0)t

(0)

is t ∈ Tj (1) s.t. |SUC(Rj (1) , ot )| ≥ 2} or Rj (1) �∈ P(Xj (1) ). Moreover, by (lem2-2) or (lem3-2),(1)

B(R(0) ) ≥ B(R(1) ). Therefore, if R(1) satisfies the (ζ, ϕ)-reverse property, then (j (1) , Rj (1) ) is thedesired sequence with its length 1. If R(1) does not satisfy the (ζ, ϕ)-reverse property, then go to
the next step. Note that by (lem2-3) or (lem3-3), ζ(R(1) ) dom(R(1) ) ϕ(R(1) ). 42
Step � (≥ 2): If ζ(R(�−1) ) cw-dom(R(�−1) ) ϕ(R(�−1) ), then by Lemma 2, there exist j (�) ∈ N and(�)
Rj (�) ∈ Dj (�) satisfying (lem2-1), (lem2-2) and (lem2-3). If not, then by Lemma 3, there ex(�)ist j (�) ∈ N and Rj (�) ∈ Dj (�) satisfying (lem3-1), (lem3-2) and (lem3-3). Then, by (lem2-1)(�−1)t(�−1)or (lem3-1), {there is t ∈ Tj (�) s.t. |SUC(Rj (�) , ot )| ≥ 2} or Rj (�) �∈ P(Xj (�) ). Moreover, by(lem2-2) or (lem3-2), B(R(�−1) ) ≥ B(R(�) ). Therefore, if R(�) satisfies the (ζ, ϕ)-reverse property,
42

Therefore, the induction argument bites.

25

(1)

(�)

then (j (1) , Rj (1) ), · · · , (j (�) , Rj (�) ) is the desired sequence with its length �. If R(�) does not satisfy the (ζ, ϕ)-reverse property, then go to the next step. Note that by (lem2-3) or (lem3-3),
ζ(R(�) ) dom(R(�) ) ϕ(R(�) ).
We claim that the above procedure stops in a finite number of steps, i.e., there exists L ≥ 1such that R(L) satisfies the (ζ, ϕ)-reverse property. Since in each step �, by (lem2-2) or (lem3-2),[B(R(�−1) ) ≥ B(R(�) ) and I(R(�−1) ) ≥ I(R(�) )] and [B(R(�−1) ) > B(R(�) ) or I(R(�−1) ) > I(R(�) )].
Since B(R(0) ) and I(R(0) ) are non-negative integers, the procedure cannot have infinite steps.

Proof of Theorem 1
Suppose to the contrary that a strategy-proof rule ζ dominates ϕ. Let R(1,0) ∈ D be such that
ζ(R(1,0) ) dom(R(1,0) ) ϕ(R(1,0) ). Let b(1,0) := ζ(R(1,0) ) and a(1,0) := ϕ(R(1,0) ). Let N (0) := |N | andB (1) := B(R(1,0) ). We will inductively construct two infinite sequences of non-negative integers(k) ∞{N (k) }∞}k=1 that cause a contradiction.
k=0 and {BInduction step 1. If R(1,0) satisfies the (ζ, ϕ)-reverse property, then let L1 := 0. If R(1,0) does not,(1,�)1then by Lemma 4, there exists a finite sequence of agent-preference pairs {(j (1,�) , Rj (1,�) )}L�=1
satis(1,�)(1,�−1)fying the following (1-i), (1-ii) and (1-iii), where for each � ∈ {1, · · · , L1 }, R(1,�) := (Rj (1,�) ; R−j (1,�) ).
��(1,�−1)t(1,�−1)(1-i) ∀� = 1, · · · , L1 , {∃t ∈ Tj (1,�) s.t. |SUC(Rj (1,�) , ot )| ≥ 2} or Rj (1,�) �∈ P(Xj (1,�) ) ,(1-ii) B(R(1,0) ) ≥ B(R(1,1) ) ≥ · · · ≥ B(R(1,L1 ) ), and(1-iii) R(1,L1 ) satisfies the (ζ, ϕ)-reverse property.
For each � ∈ {1, · · · , L1 }, let b(1,�) := ζ(R(1,�) ) and a(1,�) := ϕ(R(1,�) ).
Since R(1,L1 ) satisfies the (ζ, ϕ)-reverse property,� (1,L ) (1,L ) (1,L )(1,L )t(1,L )t (1,L )t �∃i(1) ∈ N s.t. bi(1) 1 Pi(1) 1 ai(1) 1 and {∃t ∈ Ti(1) s.t. ai(1) 1 Pi(1) 1 bi(1) 1 } .

A(1)(2,0)t

Let N (1) := |N \{i(1) }|. Now, we change the agent i(1) ’s preference. Let (R̃i(1) )t∈Ti(1) be a list
(2,0)tof type preferences satisfying the (1∗ − i) below. By applying Lemma 1 for (R̃i(1) )t∈Ti(1) and(2,0)(2,0)t(2,0)t(ot )t∈Ti(1) , we obtain a preference Ri(1) ∈ Padd (Xi(1) ) with (Ri(1) )t∈Ti(1) = (R̃i(1) )t∈Ti(1) satisfying(1∗ − ii).
(1,L )t(1,L )t(2,0)t(2,0)t(1∗ -i) ∀t ∈ Ti(1) , ∀xt ∈ X t \{bi(1) 1 , ot }, bi(1) 1 R̃i(1) ot P̃i(1) xt and��(2,0)t(2,0)(1∗ -ii) ∀xi(1) ∈ Xi(1) , {∃t ∈ Ti(1) s.t. xti(1) ∈ SLC(Ri(1) , ot )} ⇒ (ot )t∈Ti(1) Pi(1) xi(1) .
(2,0)(1,L )Let R(2,0) := (Ri(1) ; R−i(1)1 ), b(2,0) := ζ(R(2,0) ), a(2,0) := ϕ(R(2,0) ) and B (2) := B(R(2,0) ).

Claim 1.1. b(2,0) dom(R(2,0) ) a(2,0) .
(2,0)(2,0) (2,0)
(2,0)
(2,0)
We show bi(1) Pi(1) ai(1) . Suppose to the contrary that bi(1) = ai(1) . 43 Since ζ is strategy(2,0)(2,0)(1,L )
proof, bi(1) = ζi(1) (R(2,0) ) Ri(1) ζi(1) (R(1,L1 ) ) = bi(1) 1 . Note that by (1∗ -i) and the separability
43

(2,0)

Note that Ri(1) is strict.

26

(2,0)(1,L )

(2,0)

(2,0)

(2,0)

(1,L )of Ri(1) , bi(1) 1 is a best bundle at Ri(1) . Thus, since Ri(1) is strict, bi(1) = bi(1) 1 . Thus,(2,0)(1,L )(2,0)(1,L )(1,L )(1,L )
ai(1) = bi(1) 1 . Hence, by A(1), ϕi(1) (R(2,0) ) = ai(1) = bi(1) 1 Pi(1) 1 ai(1) 1 = ϕi(1) (R(1,L1 ) ), a(2,0)(2,0) (2,0)
violation of strategy-proofness of ϕ. Therefore, bi(1) Pi(1) ai(1) . Since ζ dom ϕ, this completes
the proof of Claim 1.1.
The following claim trivially holds since N (0) > N (1) .
Claim 1.2. N (0) = N (1) ⇒ B (1) > B (2) .
Now, let k ≥ 2.

Induction hypothesis. Suppose that the series of statements below are true for each k � < k. If
�
�
Lk �
Lk �
(k� ,�)(k� ,�)is defined, then it satisfies the{(j (k ,�) , Rj (k� ,�) )}�=1
is not defined, Lk� = 0. If {(j (k ,�) , Rj (k� ,�) )}�=1(k� ,�)�(k� ,�−1)

following (k’-i), (k’-ii) and (k’-iii), where for each � ∈ {1, · · · , Lk� }, R(k ,�) := (Rj (k� ,�) ; R−j (k� ,�) ).
��(k� ,�−1)t(k� ,�−1)(k’-i) ∀� = 1, · · · , Lk� , {∃t ∈ Tj (k� ,�) s.t. |SUC(Rj (k� ,�) , ot )| ≥ 2} or Rj (k� ,�) �∈ P(Xj (k� ,�) ) ,���(k’-ii) B(R(k ,0) ) ≥ B(R(k ,1) ) ≥ · · · ≥ B(R(k ,Lk� ) ), and�(k’-iii) R(k ,Lk� ) satisfies the (ζ, ϕ)-reverse property.
�

�

�

�

�

For each � = 1, · · · , Lk� , let b(k ,�) := ζ(R(k ,�) ) and a(k ,�) := ϕ(R(k ,�) ). For agent i(k ) ∈ N ,�� (k� ,Lk� ) (k� ,Lk� ) (k� ,Lk� )(k� ,L )t(k� ,L )t (k� ,L )t �bi(k� ) Pi(k� )ai(k� )and {∃t ∈ Ti(k� ) s.t. ai(k� ) k� Pi(k� ) k� bi(k� ) k� } .
�(k� +1,0)�Let N (k ) := |N \{i(1) , · · · , i(k ) }|. For agent i(k ) ’s new preference Ri(k� )(k� ,L )t(k� ,L )t(k� +1,0)tA(k’)∈ Padd (Xi(k� ) ),(k� +1,0)t(k’∗ -i) ∀t ∈ Ti(k� ) , ∀xt ∈ X t \{bi(k� ) k� , ot }, bi(k� ) k� Ri(k� )ot Pi(k� )xt , and��(k� +1,0)t t(k� +1,0)(k’∗ -ii) ∀xi(k� ) ∈ Xi(k� ) , {∃t ∈ Ti(k� ) s.t. xti(k� ) ∈ SLC(Ri(k� ), o )} ⇒ (ot )t∈T (k� ) Pi(k� )xi(k� ) .
i(k� +1,0)(k� +1,0)(k� ,L)(k� +1,0):= ζ(R
Letting R:= (Ri(k� ) ; R−i(k�k) � ), b
�
B(R(k +1,0) ).
���Claim k’.1. b(k +1,0) dom(R(k +1,0) ) a(k +1,0) , and����Claim k’.2. N (k −1) = N (k ) ⇒ B (k ) > B (k +1) .

(k� +1,0)), a(k� +1,0)��:= ϕ(R(k +1,0) ) and B (k +1) :=Induction step k. If R(k,0) satisfies the (ζ, ϕ)-reverse property, then let Lk := 0. If R(k,0) does not,(k,�)kthen by Lemma 4, there exists a finite sequence of agent-preference pairs {(j (k,�) , Rj (k,�) )}L�=1
satis(k,�)(k,�−1)fying the following (k-i), (k-ii) and (k-iii), where for each � = 1, · · · , Lk , R(k,�) := (Rj (k,�) ; R−j (k,�) ).
��(k,�−1)t(k,�−1)(k-i) ∀� = 1, · · · , Lk , {∃t ∈ Tj (k,�) s.t. |SUC(Rj (k,�) , ot )| ≥ 2} or Rj (k,�) �∈ P(Xj (k,�) ) ,(k-ii) B(R(k,0) ) ≥ B(R(k,1) ) ≥ · · · ≥ B(R(k,Lk ) ), and(k-iii) R(k,Lk ) satisfies the (ζ, ϕ)-reverse property.

For each � = 1, · · · , Lk , let b(k,�) := ζ(R(k,�) ) and a(k,�) := ϕ(R(k,�) ). Since R(k,Lk ) satisfies the(ζ, ϕ)-reverse property,� (k,L ) (k,L ) (k,L )(k,L )t(k,L )t (k,L )t �∃i(k) ∈ N s.t. bi(k) k Pi(k) k ai(k) k and {∃t ∈ Ti(k) s.t. ai(k) k Pi(k) k bi(k) k } .
27

A(k)

(k+1,0)t

Let N (k) := |N \{i(1) , · · · , i(k) }|. Now, we change the agent i(k) ’s preference. Let (R̃i(k))t∈Ti(k) be(k+1,0)t∗a list of type preferences satisfying the (k − i) below. By applying Lemma 1 for (R̃i(k))t∈Ti(k)(k+1,0)(k+1,0)t(k+1,0)tand (ot )t∈Ti(k) , we obtain a preference Ri(k)∈ Padd (Xi(k) ) with (Ri(k))t∈Ti(k) = (R̃i(k))t∈Ti(k)∗satisfying (k − ii).
(k,L )t(k,L )t(k+1,0)t(k+1,0)t(k∗ -i) ∀t ∈ Ti(k) , ∀xt ∈ X t \{bi(k) k , ot }, bi(k) k R̃i(k)ot P̃i(k)xt and��(k+1,0)t t(k+1,0)(k∗ -ii) ∀xi(k) ∈ Xi(k) , {∃t ∈ Ti(k) s.t. xti(k) ∈ SLC(Ri(k), o )} ⇒ (ot )t∈Ti(k) Pi(k)xi(k) .
(k+1,0)

Let R(k+1,0) := (Ri(k)B(R(k+1,0) ).

(k,L ); R−i(k)k ), b(k+1,0) := ζ(R(k+1,0) ), a(k+1,0) := ϕ(R(k+1,0) ) and B (k+1) :=Claim k.1. b(k+1,0) dom(R(k+1,0) ) a(k+1,0) .
(k+1,0)(k+1,0)(k+1,0)(k+1,0)(k+1,0)We show that bi(k)Pi(k)ai(k) . Suppose to the contrary that bi(k)= ai(k) . 44
(k+1,0)(k+1,0)(k,L )
Since ζ is strategy-proof, bi(k)= ζi(k) (R(k+1,0) ) Ri(k)ζi(k) (R(k,Lk ) ) = bi(k) k . Note that by(k+1,0)(k,L )(k+1,0)(k+1,0)(k∗ -i) and the separability of Ri(k) , bi(k) k is a best bundle at Ri(k) . Since Ri(k)is strict,(k+1,0)(k,Lk )
(k+1,0)(k,Lk )
(k+1,0)(k,L)(k,L )bi(k)= bi(k) . Thus, ai(k)= bi(k) . Hence, by A(k), ϕi(k) (R(k+1,0) ) = ai(k)= bi(k) k Pi(k) k(k,L )(k+1,0)(k+1,0) (k+1,0)ai(k) k = ϕi(k) (R(k,Lk ) ), a violation of strategy-proofness of ϕ. Therefore, bi(k)Pi(k)ai(k) .
Since ζ dom ϕ, this completes the proof of Claim k.1.
Claim k.2. N (k−1) = N (k) ⇒ B (k) > B (k+1) .
Suppose that N (k−1) = N (k) , i.e., i(k) ∈ {i(1) , · · · , i(k−1) }. Let k � be the largest integer with
�(k,L )(k+1,0)k � < k such that i(k ) = i(k) . First, we claim that the preference replacement from Ri(k) k to Ri(k)��(k +1,0)is the first opportunity to change i(k) (= i(k ) )’s preference after we have chosen Ri(k� ) . Formally,(k� +1,0)(k,L )

Claim k.2.1. Ri(k) k = Ri(k� )(k,L )(k� +1,0)

Suppose Ri(k) k �= Ri(k� ).

. By definition of k � ,���∃k �� ∈ {k � + 1, · · · , k}, ∃� ∈ {1, · · · , Lk�� } s.t. i(k ) = j (k ,�) . 45
���

Let (k �� , �) be the first index in which i(k ) = j (k ,�) . 46 However, by the condition (k”-i),(k�� ,�−1)t{∃t ∈ Tj (k�� ,�) s.t. |SUC(Rj (k�� ,�)(k� +1,0)

while Ri(k� )(k�� ,�−1), ot )| ≥ 2} or Rj (k�� ,�)�∈ P(Xj (k�� ,�) )(k�� ,�−1)(= Rj (k�� ,�) ) belongs to P(Xi(k� ) ), and satisfies the condition (k�∗ -i) which(k� +1,0)t

asserts that for each t ∈ Ti(k� ) , |SUC(Ri(k� )the proof of Claim k.2.1.

, ot )| ≤ 1, a contradiction. This completes(k,L )The next claim asserts that for each t ∈ Ti(k) , the type-t obeject at bi(k) k is at least as good as the(k,L )
type-t outside option for agent i(k) according to Ri(k) k .
44(k+1,0)Note that Ri(k)is strict.
45
In words, the preference replacement is accompanied by the application of Lemma 4 in step k �� after k � .
46Namely, k �� is the smallest first coordinate among the pairs satisfying the condition, and � is the smallest second
coordinate among the pairs in which the first coordinate is k �� satisfying the condition.

28

(k,L )t(k,L )t

Claim k.2.2. ∀t ∈ Ti(k) , bi(k) k Ri(k) k ot .

(k,L )t(k,L )tSuppose to the contrary that there exists t ∈ Ti(k) such that ot Pi(k) k bi(k) k . By
(k,L )(k� +1,0)(k,L )
Claim k.2.1., Ri(k) k = Ri(k� ) . Thus, by the condition (k�∗ -ii), (ot )t∈Ti(k) Pi(k) k(k,L )
bi(k) k = ζi(k) (R(k,Lk ) ). Thus, ζ is not individually rational. However, since ζ dom ϕ,ζ is individually rational, which is a contradiction. This completes the proof of Claim
k.2.2.
Now, we turn back to the proof of Claim k.2. By the condition A(k) and Claim k.2.2., there(k,L )t(k,L )t (k,L )t(k,L )t(k,L )t(k+1,0)t
is t ∈ Ti(k) such that ai(k) k Pi(k) k bi(k) k Ri(k) k ot . Thus, B(Ri(k) k ) > B(Ri(k)). Note(k,Lk )t�
(k+1,0)t�∗�that by (k -1) and Claim k.2.2., for each t ∈ Ti(k) \{t}, B(Ri(k) ) ≥ B(Ri(k)). Summing up,(k,Lk )
(k+1,0)(k,Lk )
(k+1,0)(k)
we have B(Ri(k) ) > B(Ri(k) ). Thus, B(R) > B(R) since i ’s preference is the(k,Lk )
(k+1,0)
only diﬀerence between R
and R. By the condition (k-ii), B(R(k,0) ) ≥ · · · ≥ B(R(k,Lk ) ).
Therefore, B (k) = B(R(k,0) ) > B(R(k+1,0) ) = B (k+1) . This completes the proof of Claim k.2.
(k) ∞We have inductively defined two sequences {N (k) }∞}k=1 of non-negative integers.
k=0 and {B(0)
Obviously, {N (k) }∞> N (1) ≥ · · · N (k) ≥ · · · . We show thatk=0 is weakly decreasing, i.e., N�∀k ∈ N, ∃k � > k s.t. N (k) > N (k ) .

(3)

Let k ∈ N be arbitrary. Let K := 1 + B (k+1) and k � := k + K. We prove by contradiction that�N (k) > N (k ) . If N (k) = N (k+1) = · · · = N (k+K) , then by Claims k.2 to (k+K-1).2., we can conclude
that B (k+1) > B (k+2) > · · · > B (k+K+1) . This implies 0 > B (k+K+1) , a contradiction. Thus, (3)holds. However, N (0) is a finite non-negative number, a contradiction. This completes the proofof Theorem 1.
�Proof of Corollary 3
Next we prove Corollary 3. We begin with three lemmas.
t

Lemma 5. Suppose that ϕ is independent, and for each t ∈ T , Φt : P(X t )N → At is strategy-proof
and Pareto eﬃcient. Suppose also that a strategy-proof rule ζ dominates ϕ. Then, for each R ∈ D,
if ζ(R) dom ϕ(R), then ζ(R) does not coordinate-wise weakly dominate ϕ(R) at R.
Proof. Suppose to the contrary that ζ(R) cw-dom(R) ϕ(R). Since ζ(R) dom(R) ϕ(R), there
exists i ∈ N such that ζi (R) Pi ϕi (R). Since Ri is separable, there exists t ∈ Ti such that ζit (R) Pit
ϕti (R) = Φti (Rt ). Since ζ(R) cw-dom(R) ϕ(R), for each j ∈ N t \{i}, ζjt (R) Rjt ϕtj (R) = Φtj (Rt ).
This violates that Φt (Rt ) is Pareto eﬃcient at Rt .
t

Lemma 6. Suppose that ϕ is independent and for each t ∈ T , Φt : P(X t )N → At is strategy-proof
and Pareto eﬃcient. Suppose also that a strategy-proof rule ζ dominates ϕ. Let R ∈ D be suchthat ζ(R) dom(R) ϕ(R). If R does not satisfy the (ζ, ϕ)-reverse property, then there exist i ∈ N
and Ri� ∈ Di such that29

(lem6-1) Ri �∈ P(Xi ),(lem6-2) I(Ri� ; R−i ) < I(R) and (Ri�t )t∈Ti = (Rit )t∈Ti , and(lem6-3) ζ(Ri� ; R−i ) dom(Ri� ; R−i ) ϕ(Ri� ; R−i ).
Proof. Same as the proof of Lemma 3.
tLemma 7. Suppose that a rule ϕ is independent and for each t ∈ T , Φt : P(X t )N → At is
strategy-proof and Pareto eﬃcient. Suppose also that a strategy-proof rule ζ dominates ϕ. Let
R(0) ∈ D be such that ζ(R(0) ) dom(R0 ) ϕ(R(0) ). If R(0) does not satisfy the (ζ, ϕ)-reverse property,(�)then there exists a finite sequence of agent-preference pairs {(j (�) , Rj (�) )}L�=1 satisfying the following
(�)

(�−1)

conditions (i), (ii) and (iii). For each � = 1, · · · , L, let R(�) := (Rj (�) ; R−j (�) ).
(�−1)(i) ∀� = 1, · · · , L, Rj (�)(�)t�∈ P(Xj (�) ),(�−1)t(ii) ∀� = 1, · · · , L, (Rj (�) )t∈Tj(�) = (Rj (�) )t∈Tj(�) and(iii) R(L) satisfies the (ζ, ϕ)-reverse property.
Proof. Same as the proof of Lemma 4.
We introduce notations: For each i ∈ N , each t ∈ Ti , each Rit ∈ P(X t ), each Ri ∈ Di and each��R ∈ D, let B ω (Rit ) := |SUC(Rit , ωit )|, B ω (Ri ) := t∈Ti B ω (Rit ), and B ω (R) := i∈N B ω (Ri ). The
operator B ω assigns the number of object(s) which are preferred to the endowed object(s). Now
we are ready to prove Corollary 3.
Proof of Corollary 3
Replacing B in the proof of Theorem 1 with B ω , the same proof as that for Theorem 1 works,
where for each i ∈ N , ωi plays the role of (ot )t∈Ti in the proof of Theorem 1.
�References
Abdulkadiroğlu, A., P. A. Pathak, and A. E. Roth (2009): “Strategy-proofness versus
Eﬃciency in Matching with Indiﬀerences: Redesigning the NYC High School Match,” American
Economic Review, 99, 1954–1978.
Abdulkadiroğlu, A., and T. Sönmez (1998): “Random Serial Dictatorship and the Core from
Random Endowments in House Allocation Problems,” Econometrica, 66, 689–701.
(1999): “House Allocation with Existing Tenants,” Journal of Economic Theory, 88,
233–260.
(2003): “School Choice: A Mechanism Design Approach,” Americal Economic Review,
93, 729–747.
30

Anno, H. (2008): “Second Best Eﬃciency of Strategy-proof Allocation Rules and a Characterization of the Uniform Rule with Multiple Commodities,” Working paper, Waseda university.
Anno, H., and H. Sasaki (2013): “Second-Best Eﬃciency of Allocation Rules: Strategyproofness and Single-peaked Preferences with Multiple Commodities,” Economic Theory, 54,
693–716.
Balinski, M., and T. Sönmez (1999): “A Tale of Two Mechanisms: Student Placement,”
Journal of Economic Theory, 84, 73–94.
Barberà, S., J. Massó, and A. Neme (2005): “Voting by Committees under Constraints,”
Journal of Economic Theory, 122, 185–205.
Barberà, S., H. Sonnenschein, and L. Zhou (1991): “Voting by Committees,” Econometrica,
59, 595–609.
Bloch, F., and D. Cantala (2013): “Markovian Assignment Rules,” Social Choice and Welfare,40, 1–25.
Bogomolnaia, A., and H. Moulin (2001): “A New Solution to the Random Assignment
Problem,” Journal of Economic Theory, 100, 295–328.
Budish, E., and E. Cantillon (2012): “The Multi-Unit Assignment Problem: Theory andEvidence from Course Allocation at Harvard,” American Economic Review, 102(5), 2237–2271.
Che, Y.-K., and F. Kojima (2010): “Asymptotic Equivalence of Random Priority and Probabilistic Serial Mechainsms,” Econometrica, 78, 1625–1672.
Chen, P., M. Egesdal, M. Pycia, and M. B. Yenmez (2014): “Ranking by manipulability
and quantile stable mechanisms,” Working paper.
Dur, U. (2012): “Dynamic School Choice Problem,” Working paper.
Dur, U., and T. Wiseman (2015): “School Choice with Neighbors,” Working paper.
Erdil, A. (2014): “Strategy-proof Stochastic Assignment,” Journal of Economic Theory, 151,
146–162.
Erdil, A., and H. Ergin (2007): “Two-Sided Matching with Indiﬀerences,” University of Oxford
and Washington University, unpublished mimeo.
Ergin, H. (2002): “Eﬃcient Resource Allocation on the Basis of Priorities,” Econometrica, 70,
2489–2498.
Ergin, H., T. Sönmez, and M. U. Ünver (2014): “Lung Exchange,” Working paper.
Fishburn, P. C. (1970): Utility Theory for Decision Making. John Wiley & Sons, New York.

31

Fragiadakis, D., and P. Troyan (2013): “Market Design under Distributional Constraints:
Diversity in School Choice and Other Applications,” Working paper.
Gale, D., and L. S. Shapley (1962): “College Admissions and the Stability of Marriage,”
American Mathematical Monthly, 69, 9–15.
Hammond, P. J. (2000): “Reassessing the Diamond-Mirrlees Eﬃciency Theorem,” in Incentives,
Organization, and Public Economics: Papers in Honour of Sir James Mirrlees, ed. by P. J.
Hammond, and G. D. Myles, pp. 193–216.
Hatfield, J. W. (2009): “Strategy-proof, Eﬃcient, and Nonbossy Quota Allocations,” Social
Choice and Welfare, 33, 505–515.
Hylland, A., and R. Zeckhauser (1979): “The Eﬃcient Allocation of Individuals to Positions,” Journal of Political Economy, 87, 293–314.
Ju, B.-G. (2003): “A Characterization of Strategy-proof Voting Rules for Separable Weak Orderings,” Social Choice and Welfare, 21, 469–499.
Kennes, J., D. Monte, and N. Tumennasan (2014): “The Daycare Assignment: A Dynamic
Matching Problem,” American Economic Journal: Microeconomics, 6(4), 362–406.
Kesten, O. (2006): “On Two Competing Mechanisms for Priority-based Allocation Problems,”
Journal of Economic Theory, 127, 155–171.
(2010): “School Choice with Consent,” Quaterly Journal of Economics, 125(3), 1297–
1348.
Kesten, O., and M. Kurino (2013): “Do Outside Options Matter in School Choice? A New
Perspective on the Eﬃciency vs. Strategy-proofness Trade-oﬀ,” Working paper.
Klaus, B. (2008): “The Coodinate-Wise Core for Multiple-Type Housing Markets Is Second-Best
Incentive Compatible,” Journal of Mathematical Economics, 44, 919–924.
Klaus, B., and E. Miyagawa (2001): “Strategy-proofness, Solidarity, and Consistency for
Multiple Assignment Problems,” International Journal of Game Theory, 30, 421–435.
Konishi, H., T. Quint, and J. Wako (2001): “On the Shapley-Scarf Economy: The Case ofMultiple Types of Indivisible Goods,” Journal of Mathematical Economics, 35, 1–15.
Kurino, M. (2014): “House Allocation with Overlapping Generations,” American Economic
Journal: Microeconomics, 6 (1), 258–289.
Le Breton, M., and A. Sen (1999): “Separable Preferences, Strategyproofness, and Decomposability,” Econometrica, 67, 605–628.
Monte, D., and N. Tumennasan (2013): “Centralized Allocation in Multiple Markets,” Working Paper.
32

Moulin, H. (1995): Cooperative Microeconomics: A Game-Theoretic Introduction. Princeton
University Press.
Pápai, S. (2000): “Strategyproof Assignment by Hierarchical Exchange,” Econometrica, 68, 1403–
1433.
(2001): “Strategyproof and Nonbossy Multiple Assignments,” Journal of Public Economic
Theory, 3, 257–271.
Pathak, P. A., and T. Sönmez (2013): “School Admissions Reform in Chicago and England:Comparing Mechanisms by Their Vulnerability to Manipulation,” American Economic Review,103(1), 80–106.
Pereyra, J. S. (2013): “A Dynamic School Choice Model,” Games and Economic Behavior, 80,
100–114.
Pycia, M., and M. U. Ünver (2009): “Incentive Compatible Allocation and Exchange ofDiscrete Resources,” Boston College Working Papers in Economics 715.
Roth, A. E., and A. Postlewaite (1977): “Weak Versus Strong Domination in a Market with
Indivisible Goods,” Journal of Mathematical Economics, 4, 131–137.
Roth, A. E., T. Sönmez, and M. U. Ünver (2004): “Kidney Exchange,” Quarterly Journalof Economics, 119, 457–488.
(2005): “Pairwise Kidney Exchange,” Journal of Economic Theory, 125, 151–188.
Sasaki, H. (2003): “Limitation of Eﬃciency: Strategy-proofness and Single-peaked Preferenceswith Many Commodities,” Working Paper.
Shapley, L., and H. Scarf (1974): “On Cores and Indivisibility,” Journal of Mathematical
Economics, 1, 23–37.
Sönmez, T., and T. B. Switzer (2013): “Matching with (Branch-of-Choice) Contracts at theUnited States Military Academy,” Econometrica, 81, 451–488–185.
Sönmez, T., and M. U. Ünver (2010): “Course Bidding at Business Schools,” International
Economic Review, 51, 99–123.
(2013): “Market Design for Kidney Exchange,” in The Handbook of Market Design, ed.
by M. N. Zvika Neeman, and N. Vulkan, pp. 93–137. Oxford University Press, Oxford.
Sönmez, T., and U. Ünver (2011): “Matching, Allocation, and Exchange of Discrete Resources,” in Handbook of Social Economics, ed. by J. Benhabib, A. Bisin, and M. O. Jackson,
vol. 1A, pp. 781–852. North Holland, The Netherlands.
The Japan Society for Transplantation (2013): Fact Book (in Japanese).
33

Whitehead, C., and K. J. Scanlon (2007): Social Housing in Europe. LSE London, Chapter
2.
Yilmaz, Özgür. (2011): “Kidney Exchange: An Egalitarian Mechanism,” Journal of Economic
Theory, 146, 592–618.

34