STRATEGY-PROOF STOCHASTIC ASSIGNMENT
Aytek Erdil
University of Cambridge
Faculty of Economics, Sidgwick Avenue, Cambridge, CB3 9DD, United Kingdom.
Phone: +441223335198. Email: nae25@cam.ac.uk
Abstract. I study strategy-proof assignment mechanisms where the agents
reveal their preference rankings over the available objects. A stochastic mecha-
nism returns lotteries over deterministic assignments, and mechanisms are com-
pared according to first-order stochastic dominance.
I show that non-wasteful strategy-proof mechanisms are not dominated by
strategy-proof mechanisms, however nonwastefulness is highly restrictive when
the mechanism involves randomization. In fact, the Random Priority mecha-
nism (i.e., the Random Serial Dictatorship), and a recently adopted school choice
mechanism, Deferred Acceptance with Random Tie-breaking, are wasteful. I
find that both these mechanisms are dominated by strategy-proof mechanisms.
In general, strategy-proof improvement cannot be due to merely reshuffling
objects, and therefore must involve assigning more objects.
Keywords : random assignment, strategy-proofness, priority based assignment,
ordinal efficiency, school choice. (JEL: C78, D61, D63.)
1. Introduction
Consider the problem of assigning a number of heterogenous indivisible objects
to individuals, where each individual can receive at most one object. In a wide
range of contexts where this problem arises, such as school choice, course assign-
ment at universities, or office allocation, the procedures typically rule out mon-
etary transfers, and rely on agents’ preference rankings over the objects. Three
properties are crucial for an assignment procedure: efficiency, strategy-proofness,
and fairness.
Indivisibilities make it impossible to treat the agents equally when assignments
are made in a deterministic way. Randomization greatly expands the set of mech-
anisms and allows fairness. For example, the random priority mechanism orders
the agents randomly, and lets them pick their objects in this order. In the richer
1
2 STRATEGY-PROOF STOCHASTIC ASSIGNMENT
set of stochastic mechanisms, agents’ assignments are lotteries over objects. The
assignment at the end of the procedure in application will depend on the real-
ization of the lottery, but the agents, when revealing their preferences, are facing
lotteries over deterministic outcomes. Therefore, the analysis of the mechanism
calls for a stochastic perspective.
Since the agents’ preferences are their private information, it is important for
the mechanism to provide the agents with the right incentives to reveal their
preferences truthfully. Thus efficiency is really a property of the mechanism, rather
than of the assignment resulting from the mechanism after the preferences are
revealed. In our environment the primitives on preferences are ordinal rankings
over the objects, so the appropriate concept for incentive compatibility is strategy-
proofness, and the natural notion of welfare is Pareto efficiency, where lotteries
are compared via first-order stochastic dominance.
A mechanism weakly dominates another if for every preference profile, it assigns
to every agent a lottery which she weakly prefers in the first-order stochastic
dominance sense. As it is with efficiency, non-wastefulness is also extended to
this stochastic environment in a natural way: if an agent would rather have more
of some object, say x, instead of another object she has received with positive
probability, then it must be that all of x is already assigned.
I first show that a non-wasteful strategy-proof mechanism cannot be dominated
by another strategy-proof mechanism. On the other hand, for randomized mech-
anisms, this ordinal, or ex ante, notion of non-wastefulness is a very demanding
condition, much stronger than ex post non-wastefulness. While every non-wasteful
stochastic assignment is a convex combination of non-wasteful deterministic as-
signments, stochastic mechanisms are often wasteful even when they are random-
izations over non-wasteful mechanisms.
My next result, then, sheds light on the nature of strategy-proof improvement:
if a strategy-proof mechanism is dominated by another, such Pareto improvement
cannot be achieved by merely re-allocating the objects, but must involve assigning
more objects. Indeed, in two important applications, I show that the random
priority (RP), i.e., the random serial dictatorship mechanism, and the randomized
deferred acceptance (RDA) mechanism admit strategy-proof improvement. I give
explicit constructions of strategy-proof mechanisms which dominate them.
STRATEGY-PROOF STOCHASTIC ASSIGNMENT 3
Bogomolnaia and Moulin (2001) make the critical observation that the RP is
dominated, but they also show that there is no strategy-proof and efficient mecha-
nism satisfying equal treatment of equals. Zhou (1990) notes that whether the RP
is optimal within the class of symmetric, ex post Pareto optimal, strategy-proof
mechanisms remains an open question. My construction shows that it is not.
A question of the same nature recently emerged from another practical market
design issue. In a typical school choice program, each school has an exogenous pri-
ority ranking over the students. A matching respects these priorities if whenever
a student prefers a school x to her own, it must be that only students of equal
or higher priority for x are assigned to school x. When these priority rankings
are strict, the Deferred Acceptance (DA) mechanism of Gale and Shapley (1962)
returns the constrained efficient assignment (i.e., the student-optimal assignment
among those assignments which respect the priorities). However, in many appli-
cations, large groups of students have equal priority, and therefore the priority
rankings have ties. The leading mechanism in this environment randomly breaks
ties before applying the DA mechanism. Ehlers (2006) observes that some tie-
breaking rules even result in constrained inefficiency. Therefore, unlike the DA
with strict priorities, the randomized deferred acceptance (RDA) mechanism with
weak priorities is short of constrained efficiency. While the DA is strategy-proof
(Dubins and Freedman, 1981; Roth, 1982), Erdil and Ergin (2008) show that no
strategy-proof mechanism is ex post constrained efficient when there are ties in
priorities. In contrast with these impossibility results, I explicitly construct a
strategy-proof mechanism that dominates the RDA.
In large markets where certain regularity conditions hold, Che and Kojima
(2010) show that the RP is asymptotically efficient. More generally Liu and Pycia
(2011) establish that the RP is the only symmetric, strategy-proof and efficient
mechanism. Therefore, the room for strategy-proof improvement over symmetric,
strategy-proof, ex post efficient mechanisms vanishes as the market size grows. My
results complement these findings for the case of small markets. The constructions
of strategy-proof improvement are computationally demanding, and are possibly
intractable for large markets. But the ideas are likely to lend themselves to appli-
cations when the market size is small, where we establish that such improvement
is indeed possible.
One insight that emerges from this paper is that while randomizing over strategy-
proof mechanisms preserves strategy-proofness, it does not necessarily preserve the
4 STRATEGY-PROOF STOCHASTIC ASSIGNMENT
property of being un-dominated within the strategy-proof class. Starting, instead,
with stochastic mechanisms, Pycia and U¨nver (2012) investigate whether their
various desirable properties survive decomposition as a lottery over deterministic
mechanisms each of which also satisfies those properties. They find a sufficient
condition and establish positive results on some restricted preference domains.1
2. Stochastic Assignments
It is common to employ randomization to accommodate various notions of jus-
tice, equity, or fairness. Especially when allocating indivisible resources, the dis-
crete nature of the problem implies that mechanisms with deterministic outcomes
will treat agents asymmetrically. For example, the serial dictatorship mechanism
is highly asymmetric in its treatment of the agents. As Zhou (1990) and Ab-
dulkadirog˘lu and So¨nmez (1998) highlight, choosing, with equal probability, an
exogenous priority order in which the agents get to pick their objects recovers
symmetry between the agents. While this random priority mechanism satisfies
equal treatment of equals, is strategy-proof and returns a lottery over efficient as-
signments, Bogomolnaia and Moulin (2001) show that efficiency, equal treatment
of equals and strategy-proofness are incompatible. Therefore, the efficiency loss
associated with the random priority mechanism cannot be alleviated in a strategy-
proof way. Given the prominence of this mechanism in practice, it is important
to know whether it can be improved upon by a strategy-proof mechanism.
Take, for another important application, the school admissions model, where
schools typically have different priority rankings with ties. Abdulkadirog˘lu et
al. (2009), in their study of the New York City school choice system, show that
for strict priorities, DA is not dominated by a strategy-proof mechanism. The
mechanism used in NYC is of course not the DA with strict priorities, but the
following stochastic mechanism: firstly the mechanism, randomly and with equal
probability, chooses a linear order over the students. Then all ties in priority
rankings are broken according to this order to get strict priorities. And finally
the DA algorithm is run with respect to these strict priorities. We know that this
mechanism is ex post constrained inefficient, and there is no strategy-proof and
ex post student optimal stable mechanism (Erdil and Ergin, 2008). It remains to
be answered whether the stochastic mechanism used in NYC is on the efficient
frontier of strategy-proof mechanisms.
1See also Peters et al. (2013) for related results.
STRATEGY-PROOF STOCHASTIC ASSIGNMENT 5
We now turn to a formal treatment of stochastic assignment mechanisms in
order to answer the above questions. Let N denote a finite set of agents, and X
a finite set of types of objects. There are qx ≥ 1 copies of type x for x ∈ X.
For agent i, the option of staying unassigned (which can also be interpreted as
being assigned one’s outside option) is also denoted by i. Each agent has a strict
preference ranking Ri over Xi := X ∪ {i}. That is, Ri is a complete, transitive
and antisymmetric relation over Xi, with Pi denoting its asymmetric part. An
object x is acceptable to i if xPii. A preference profile is a vector R = (Ri)i∈N
of individual preference relations.
A stochastic assignment, also called a probabilistic assignment, assigns each
agent i a lottery over Xi such that the total probability share of x is at most qx
(where qi = 1). Formally, a stochastic assignment is a profile γ = (γi)i∈N of
vectors γi = (γix)x∈Xi such that γix ∈ R+ for all i ∈ N and x ∈ Xi, and
(a)
∑
x∈Xi γix = 1 for each agent i ∈ N ,
(b)
∑
i∈N γix ≤ qx for each object x ∈ X.
An assignment γ is called deterministic if γix ∈ {0, 1} for all i and x. For
every agent i, there is at most one x such that γix = 1. For every such i and x, we
write γ(i) = x. A generalized version of the Birkhoff-von Neumann theorem (see,
e.g., Kojima and Manea, 2010) says that any stochastic assignment is a convex
combination of deterministic assignments. Hence, every stochastic assignment can
be interpreted as a lottery over deterministic assignments.
The total amount of objects allocated by γ will be called the size of an as-
signment γ, and is formally defined as |γ| = ∑x∈X∑i∈N γix. Given a preference
profile R, a stochastic assignment γ is called wasteful if there exist j ∈ N and
y, z ∈ Xj such that
zPjy, γjy > 0,
∑
i∈N
γiz < qz.
If γ is not wasteful, it is called non-wasteful. Our perspective on mechanisms
is that with the assignment procedures involving randomization, the agents are
actually facing stochastic mechanisms. Kesten and U¨nver (2012) refer to this as
the ex ante approach. It is common in mechanism design to use the term ex ante for
evaluating a mechanism before the agents know their preferences (e.g., Holmstro¨m
and Myerson, 1983). In order to avoid confusion then, throughout the rest of the
paper, I will write non-wasteful with the above definition in mind. This stochastic
analogue of non-wastefulness is not necessarily the same as the assignment being
6 STRATEGY-PROOF STOCHASTIC ASSIGNMENT
a lottery over non-wasteful deterministic assignments. In fact, as we will see in
Remark 2, a randomization over non-wasteful deterministic assignments may be
wasteful.
Unless otherwise stated, I will restrict my attention to individually rational
assignments: no agent is assigned a positive amount of an object she likes less
than her outside option, that is, iPix ⇒ γix = 0. A stochastic assignment
mechanism is a function which associates to each preference profile an individ-
ually rational stochastic assignment. If its outcome is a deterministic assignment
for every preference profile, then the mechanism is said to be deterministic. f
satisfies equal treatment of equals if fi(R) = fj(R) whenever Ri = Rj.
Given an agent i’s ordinal preference relation Ri over Xi, one can easily extend it
to a relation R˜i over lotteries over Xi via first-order stochastic dominance (FOSD)
so that if ωi =
∑
x∈Xi ωixx and γi =
∑
x∈Xi γixx, then
(FOSD) γiR˜iωi ⇐⇒ for every y ∈ Xi,
∑
x:xRiy
γix ≥
∑
x:xRiy
ωix.
This condition is equivalent to the requirement that Eui[γ] ≥ Eui[ω] for any vNM
utility function ui representing Ri. γi is said to FOSD ωi, denoted γiP˜iωi, if in
addition to the above, the inequality on the right hand side of (FOSD) is strict
for at least one y.
An assignment γ weakly dominates another assignment ω if for each agent i,
her assignment under γ weakly first-order stochastically dominates her assignment
under ω, i.e., γiR˜iωi. If we also have γjP˜jωj for some j, we say that γ dominates
ω. If an assignment is not dominated by any other assignment, then it is called
efficient.2 If µ is a convex combination of efficient deterministic assignments, then
it is called ex post efficient. Every efficient assignment is non-wasteful and ex
post efficient, but as Bogomolnaia and Moulin (2001) illustrate, the converse does
not hold. A mechanism g dominates another mechanism f , if for every preference
profile, the outcome of the first weakly dominates that of the latter, with strict
dominance for at least one preference profile. In other words, gi(R)R˜ifi(R) for
each R and for each i; and gj(R
′)P˜ ′jfj(R
′) for some j and R′. A mechanism
2As it is with non-wastefulness, we consider efficiency as a property of lotteries, because the
outcomes of stochastic mechanisms are lotteries, and the realization of these lotteries is not part
of the mechanism. Bogomolnaia and Moulin (2001) use the term ordinally efficient, whereas
Kesten and U¨nver (2012) use ex ante efficient to emphasize that the assignment is viewed before
the lottery has realized.
STRATEGY-PROOF STOCHASTIC ASSIGNMENT 7
f is strategy-proof if fi(R)R˜ifi(R
′
i, R−i) for every R and R
′
i. And finally, a
mechanism is said to be on the efficient frontier of strategy-proof mechanisms
if it is strategy-proof and is not dominated by another strategy-proof mechanism.
3. Random Priority and Randomized Deferred Acceptance
A common method to allocate objects is random assignment. For example, when
there are n agents and n objects, and if each agent is to receive exactly one object,
then there are n! possible deterministic assignments. The Random Assignment
(RA) mechanism is nothing but a random variable over these assignments, with
each assignment having equal probability. As such it satisfies equal treatment
of equals. As it disregards preferences, it is strategy-proof, however it also fails
to be individually rational for some preference profiles. The Serial Dictatorship
mechanism fixes an exogenous ranking over the agents, assigns the first agent
to her favorite object, assigns the second agent to her favorite from among the
remaining objects, and so on. The highly unequal treatment of this mechanism
is remedied by the Random Priority (RP) mechanism, also called the Random
Serial Dictatorship, which is defined as a uniform lottery over all possible serial
dictatorships.
Remark 1. The RP dominates the RA. Note that for any agent, and any integer
k ≤ n, her total share of her most preferred k objects under equal distribution is
k/n. Under the RP, with probability k/n, she receives one of her top k choices.
Hence, the RP weakly dominates the RA. An obvious preference profile at which
the dominance is strict is where one agent’s top choice is bottom ranked by every-
one else.
Note also that the RA is not individually rational. Each agent receives some
fraction of each object even when she does not find them acceptable. If we modify
the RA by allowing free disposal, and thus recover individual rationality, we make
the mechanism “more wasteful” than the RP. ♦
When the demand for some objects exceeds the supply, a common method to
decide who receives the objects is to appeal to an exogenous priority ranking
over the agents. A priority structure is a profile %= (%x)x∈X of weak orders
(complete and transitive relations) on N , where for each x ∈ X, %x ranks agents
with respect to their priority for x. Let x denote the asymmetric part of %x. If
%x is antisymmetric for each x ∈ X, then the priority structure % is called strict.
8 STRATEGY-PROOF STOCHASTIC ASSIGNMENT
Given priorities % and preferences R, let µ be a deterministic assignment. We
say µ violates the priority of i for x, if there is an agent j such that j is
assigned to x whereas i both prefers x to her assigned object and has strictly
higher priority for it, i.e., µ(j) = x, xPiµ(i), and i x j. If µ is non-wasteful and if
it does not violate priorities, then it is called stable. It is constrained efficient
if it is stable, and is not Pareto dominated by any other stable assignment. Given
%, a mechanism is called ex post stable if it associates to every preference profile
R a convex combination of assignments which are stable with respect to R and %.
The Serial Dictatorship (SD) mechanism sets the priority rankings over
the agents as i1 x i2 x · · · x in for each x, and at every preference profile R,
it returns the unique stable assignment. It is Pareto efficient and strategy-proof.
For an arbitrary strict priority structure, Gale and Shapley (1962) prove the
existence of a stable assignment via the following algorithm: Given strict priorities
, and strict preferences R, at step 1, every i applies to her favorite acceptable
object. For each x, the qx applicants who have the highest priority for x are placed
on the waiting list of x, and the others are rejected. At step r, the applicants who
were rejected at step r−1 apply to their next best acceptable objects. For each x,
the highest priority qx agents among the new applicants and those in the waiting
list are placed on the new waiting list, and the rest are rejected. The algorithm
terminates when every agent is either on a waiting list or has been rejected by
every object that is acceptable to her. At the end, objects are assigned to the
agents on their waiting lists.
Gale and Shapley (1962) not only establish existence of stable assignments, but
also show that the outcome of their algorithm is Pareto superior to any other
stable assignment. Fixing strict priorities , the mechanism which associates to
a preference profile the outcome of the above algorithm is called the Deferred
Acceptance mechanism, and is denoted by DA. Moreover, this mechanism is
strategy-proof (Dubins and Freedman, 1981; Roth, 1982), but Roth (1982) also
shows that the outcome of the DA is not always Pareto efficient. In fact Ergin
(2002) shows that the DA is an efficient mechanism only under very restrictive
assumptions on the priorities.3 Since the DA is widely used in real life, it would be
important to recover this welfare loss. Kesten (2010) shows that when priorities are
strict, and all schools are acceptable to all students, no strategy-proof and efficient
3Erdil and Ehlers (2010) give a general characterization of weak priority structures for which
the DA is efficient.
STRATEGY-PROOF STOCHASTIC ASSIGNMENT 9
mechanism dominates the DA. Abdulkadirog˘lu et al. (2009) show that there is no
strategy-proof mechanism which dominates the DA with strict priorities. Kesten
and Kurino (2012) show that this impossibility holds also in the more restricted
preference domain where all schools are acceptable to all students. In some sense
there is a tension between strategy-proofness and efficiency when we take the DA
as a benchmark.
In many applications, the priority rankings have ties. Designing a mechanism
which respects weak priority rankings involves some form of randomization. For
example, in New York City High School Match, large classes of students have
equal priorities, and the ties are broken randomly to ensure fairness between such
students.
In general, a tie-breaking rule is a function τ from the set of priority structures
to the set of strict priority structures such that denoting ′= τ(%), we have
i ′x j =⇒ i %x j.
According to this definition, a tie-breaking rule is independent of agents’ prefer-
ences.
Let T be a set of tie-breaking rules, and pi be a probability distribution over
T . Given a priority structure %, let us denote by DAτ(%) the mechanism which
breaks the ties in % according to the tie-breaking rule τ , and then runs the DA
algorithm. Fixing an exogenously given priority structure %, let us define the
stochastic DA mechanism associated with T and pi as
RDA%,T ,pi =
∑
τ∈T
piτDA
τ(%).
It is strategy-proof, because it is an exogenous randomization over strategy-proof
mechanisms.
Consider a simple tie-breaking rule which fixes a linear order on N , and breaks
all the ties according to that order. Denote both this linear order and the associ-
ated tie-breaking rule by τ . If ′= τ(%), then we should have for all i, j ∈ N and
x ∈ X
i ∼x j and iτj =⇒ i ′x j.
Various school choice mechanisms (such as those in New York City and Boston)
adopt the RDA. If % is the prevailing priority structure, the specific mechanism in
use is based on RDA%,L,pi, where L is the set of linear orders on the set of agents
N , and pi is the uniform distribution over L. Thus, |L| = n!, and piτ = 1/n! for
10 STRATEGY-PROOF STOCHASTIC ASSIGNMENT
every τ ∈ L. In analogy with the random priority mechanism being denoted by
RP, I will use the notation RDA% to denote:
RDA% =
1
n!
∑
τ∈L
DAτ(%).
When all agents are of equal priority for each object, the RDA reduces to the
RP. Given the prominence of the RDA (and its special case the RP) in real life
applications, it is important to know whether it is on the efficient frontier of
strategy-proof mechanisms.
4. Results
My first main result relies on a critical lemma which I state here because of its
centrality.
Reshuffling Lemma. Suppose that an assignment γ first-order stochastically
dominates another assignment ω. If ω is non-wasteful, , then
∑
x∈X
γix =
∑
x∈X
ωix
for every i ∈ N .
Reshuffling Lemma basically says that a first-order stochastic dominance im-
provement over a non-wasteful assignment is nothing but a reshuffling of the as-
signed objects (in probability shares) between the agents.
Proposition 1. If a strategy-proof mechanism is non-wasteful, then it is not dom-
inated by any other strategy-proof mechanism.
While significant applications, such as the RP and the RDA, involve random-
izations over non-wasteful deterministic assignments, the above proposition is not
necessarily conclusive about such mechanisms, because a randomization over non-
wasteful mechanisms can be wasteful.
Remark 2. The RP is wasteful (and, hence, so is the RDA). In order to see why,
suppose there are four agents 1, 2, 3, 4, and three distinct objects a, b, c. Let % be
a trivial priority structure in the sense that i ∼x j for all agents i, j, and objects
x. The preference profile
R1 R2 R3 R4
a c a c
b b
results in
RP(R) a b c
1 1/2 3/8
2 3/8 1/2
3 1/2
4 1/2
.
STRATEGY-PROOF STOCHASTIC ASSIGNMENT 11
Not all of b is assigned, whereas 1 finds b acceptable, and the sum of her assigned
probability shares is less than 1. Hence Proposition 1 is mute about the RDA. ♦
Bogomolnaia and Moulin (2004), in their study of a two-sided matching prob-
lem with dichotomous preferences, find that randomization enables efficiency and
strategy-proofness to hold at the same time where deterministic mechanisms fail
to do so. In our environment too, in principle, randomization over non-strategy-
proof mechanisms might be strategy-proof. For instance, given a priority structure
%, suppose that we have a family T of tie-breaking rules, and a family {gτ}τ∈T
of mechanisms such that gτ weakly dominates DAτ(%) for all τ , with strict dom-
inance for some τ . We know from Abdulkadirog˘lu et al. (2009) that gτ cannot
be strategy-proof if gτ strictly dominates DAτ(%). But perhaps an appropriate
randomization over these mechanisms is strategy-proof. As Remark 2 illustrates,
the size of the assignment DAτ(%)(R) varies depending on the tie-breaking rule τ .
However for any τ , Reshuffling Lemma implies |gτ (R)| = |DAτ(%)(R)|. Hence for
any probability distribution pi on T , and preferences R, we have∣∣∣∣∣∑
τ∈T
piτg
τ (R)
∣∣∣∣∣ =
∣∣∣∣∣∑
τ∈T
piτDA
τ(%)(R)
∣∣∣∣∣ .(1)
Let us say mechanisms f and g are of equal size if |f(R)| = |g(R)| for all R.
If, on the other hand, |g(R)| ≥ |f(R)| for all R with strict inequality for at least
some R, then we say g is of greater size than f .
Proposition 2. If a strategy-proof mechanism g dominates another strategy-proof
mechanism f , then g is of greater size than f .
This result not only applies to several mechanisms studied in the literature and
nests various earlier results of a similar spirit, but also provides a strong conclu-
sion regarding mechanisms which rely on improving strategy-proof mechanisms
via re-allocating objects or shares of objects. Equation 1 says that the mecha-
nism
∑
piτg
τ is of the same size as the strategy-proof mechanism
∑
piτDA
τ(%).
Hence Proposition 2 applies, and
∑
piτg
τ cannot be strategy-proof if it dominates∑
piτDA
τ(%). In particular, when priority rankings have ties, randomization does
not recover strategy-proofness whether we use Kesten’s (2010) improvement over
the DA, or the stable improvement cycles of Erdil and Ergin (2008).
If there is any way to improve upon a strategy-proof mechanism without skew-
ing incentives, Proposition 2 shows us where improvements could come from. The
improving mechanism has to be allocating more objects at some preference profile.
12 STRATEGY-PROOF STOCHASTIC ASSIGNMENT
In fact, we find that wastefulness of the RP (and the RDA) does create an oppor-
tunity for strategy-proof improvement. The mechanisms RP [and RDA] are not
on the efficient frontier of strategy-proof assignment mechanisms. Moreover, the
dominating mechanism is not only strategy-proof, but also ex post efficient [ex post
stable]: the outcome is a lottery over deterministic efficient [stable] assignments.
Proposition 3. (i) The RP is dominated within the class of ex post efficient
strategy-proof mechanisms which satisfy equal treatment of equals.
(ii) The RDA is dominated within the class of strategy-proof and ex post stable
mechanisms.
Sketch of proof. Say there are at least three types objects a, b, c with a single
copy each, and four agents 1, 2, 3, 4. If the preferences of the agents are
R1 R2 R3 R4
a c c c
b a b
,
breaking the ties as 4  3  2  1 or 4  2  3  1 leads to the assignment(
1 2 3 4
1 a b c
)
. Tie-breaking according to 3  1  2  4 or 3  1  4  2 leads to
the assignment
(
1 2 3 4
a 2 c 4
)
. Therefore with probability at least 1/12, agent 1 is not
assigned an object, and b is not assigned to anyone. By replacing
(
1 2 3 4
1 a b c
)
+
(
1 2 3 4
a 2 c 4
)
with
(
1 2 3 4
b a c 4
)
+
(
1 2 3 4
a 2 b c
)
with probability 1/12, we assign an extra 1/12 of b to agent
1, while holding everything else the same. And crucially if 1’s preference ranking
were bP ′1a, her assignment would be increased by 1/12 of object a due to the
symmetry of R−1. This will ensure that 1’s incentives for truthful reporting are
not skewed.
This improvement treats agent 1 differently. To recover equal treatment of
equals, we define analogous improvements for other agents when the names of the
agents are permuted, and randomize over such mechanisms with equal probability.
Since the RP is a special case of the RDA, our proof also establishes that the
RDA is not on the efficient frontier of strategy-proof mechanisms.45 ♦
4For completeness, we show in the Appendix the existence of non-trivial priority structures
% for which the RDA is dominated by a strategy-proof ex post stable mechanism.
5If the priority structure is trivial in the sense that every agent has the same priority for
every object, and if there is a single copy of every object, the RDA boils down to the RP.
Abdulkadirog˘lu and So¨nmez (1998) show that the RP is equivalent to the core of the market
where the agents are initially allocated the objects with a uniform randomization. Pathak and
Sethuraman (2011) and Carroll (2013) generalize this equivalence to the case of multiple copies
STRATEGY-PROOF STOCHASTIC ASSIGNMENT 13
The fact that the RP is not on the efficient frontier of strategy-proof mechanisms
relies on the environments in which objects are scarce and the number of agents
exceeds three. Obviously, if there are sufficiently many copies of each object, the
RP is efficient. Moreover for n ≤ 3, Bogomolnaia and Moulin (2001) show that
the RP is efficient.
By Proposition 2, any strategy-proof mechanism that dominates the RP is nec-
essarily less wasteful than the RP, i.e., for some realization of preferences, such a
mechanism assigns more objects than the RP. However we find that not all of the
waste can be recovered in a strategy-proof way:
Proposition 4. If a strategy-proof mechanism g dominates the RP mechanism,
then g is wasteful.
Thus, if we take the RP as a starting point on which to improve, it is impos-
sible to avoid waste within the class of strategy-proof mechanisms. Among the
strategy-proof mechanisms which dominate the RP, there must be one which is
un-dominated, and hence is on the efficient frontier of strategy-proof mechanisms.
Since this mechanism is necessarily wasteful, I have also established that the con-
verse of Proposition 1 does not hold: being un-dominated in the strategy-proof
class does not imply being non-wasteful.
5. Concluding remarks
I have shown that randomizations over un-dominated strategy-proof mecha-
nisms admit strategy-proof improvements. Specifically, both the Random Priority
and the Randomized Deferred Acceptance are dominated within the strategy-proof
class. While I explicitly demonstrate strategy-proof improvement over the afore-
mentioned mechanisms, the full extent of such improvement is yet to be explored.
One key insight that emerges from my analysis is that for a strategy-proof mech-
anism to improve on another, it must allocate more objects at some preference
profile. A general and computationally efficient method to find strategy-proof im-
provements over the aforementioned popular mechanisms would readily find its use
in real-life market design applications. Designing fair mechanisms on the efficient
frontier of strategy-proof mechanisms remains an important challenge. Taking the
widely popular Random Priority mechanism as a benchmark to improve upon, any
and non-trivial priorities, where the core is replaced by an appropriate formulation of the top
trading cycles mechanism.
14 STRATEGY-PROOF STOCHASTIC ASSIGNMENT
strategy-proof mechanism that dominates it must be wasteful. In connection with
this finding, an open question is whether there exists a non-wasteful strategy-proof
mechanism which satisfies equal treatment of equals.
6. Acknowledgements
I thank Sophie Bade, Salvador Barbera, Jean-Pierre Benoit, Eddie Dekel, Fed-
erico Echenique, Haluk Ergin, Onur Kesten, Philipp Kircher, Morimitsu Kurino,
Tony Kwasnica, Rocco Macchiavello, Jordi Masso, Meg Meyer, Herve Moulin,
Al Roth, Arunava Sen, Tayfun So¨nmez, William Thomson, and seminar partici-
pants at Caltech, Universidad Autonoma de Barcelona, University College Lon-
don, UCLA, Oxford, 2009 Conference for Economic Design, and 2010 Brazilian
Workshop in Game Theory for their comments.
Appendix A. Proofs
Lemma 1. Given Ri over X∪{i}, say there are exactly m objects in X acceptable
to agent i, and enumerate them as x1, x2, . . . , xm ∈ X such that x1Pix2Pi · · ·Pixm.
If the assignment γi =
∑m
t=1 γitx
t strictly first-order stochastically dominates an-
other assignment ωi =
∑m
t=1 ωitx
t, then there exists s such that γis > ωis, and
γit = ωit for all t < s.
Proof of Lemma 1. γi strictly FOSD ωi, i.e., γiP˜iωi, therefore
γi1 ≥ ωi1
γi1 + γi2 ≥ ωi1 + ωi2
...
γi1 + γi2 + · · ·+ γim ≥ ωi1 + ωi2 + · · ·+ ωim
with at least one of the inequalities strict.
If γit ≤ ωit for all t = 1, . . . ,m, then the above inequalities all have to be
equalities, and therefore we must have γi = ωi, contradicting the assumption that
γi FOSD ωi. Then, let s be the smallest positive integer for which γis > ωis. If
s > 1, then γi1 = ωi1, since we already know that γi1 ≥ ωi1. But then, we have
γi2 ≥ ωi2 from the second inequality above, and if s > 2, then γi2 = ωi2. Arguing
inductively in the same fashion, we conclude that γit = ωit for t < s. 
STRATEGY-PROOF STOCHASTIC ASSIGNMENT 15
Proof of Reshuffling Lemma. Let N ′ be the set of agents whose assignments
improved from ω to γ, and let X ′ be the set of objects such that there is some
agent in N ′ whose share of such an object increased from ω to γ.
First, let us show that no object is assigned less at ω than at γ. In order to see
this, assume the contrary. Then there is an object x assigned less than qx at ω,
and an agent i who gets more of x at γ than ω. That is,∑
j∈N
ωjx < qx and γix > ωix.
γ dominates ω, therefore i prefers her assignment γi to ωi. Since γi FOSD ωi, we
have ∑
yPix
γiy ≥
∑
yPix
ωiy.
This, in turn, implies
γix +
∑
xPiy
γiy ≤ ωix +
∑
xPiy
ωiy,
and after re-arranging, and using the fact that γix − ωix > 0, we get
0 < γix − ωix +
∑
xPiy
γiy ≤
∑
xPiy
ωiy.
Thus, i receives a positive amount of objects she likes less than x, whereas not all
of x is assigned under ω, a contradiction with ω being non-wasteful. Hence for
each x ∈ X ∑
i∈N
ωix ≥
∑
i∈N
γix.(2)
Adding up across x, we get∑
x∈X
∑
i∈N
ωix ≥
∑
x∈X
∑
i∈N
γix.(3)
Secondly, since each agent is weakly better off at γ, and ω is individually ratio-
nal, each agent receives at least as much share of acceptable objects at γ as she
did at ω, i.e., for each i ∈ N :∑
x∈X
ωix =
∑
x:xPii
ωix ≤
∑
x:xPii
γix =
∑
x∈X
γix,(4)
which, adding up across i, lead to∑
i∈N
∑
x∈X
ωix ≤
∑
i∈N
∑
x∈X
γix.(5)
16 STRATEGY-PROOF STOCHASTIC ASSIGNMENT
Hence the inequalities (3) and (5) both must be equality. This, in turn, implies
the weak inequalities (2) and (4) are indeed equality for each x and i, respectively.

Proof of Proposition 1. Let f be non-wasteful and strategy-proof, and suppose,
for a contradiction, that a strategy-proof mechanism g dominates f . Then there
must be an agent i and a preference profile R such that gi(R)P˜ifi(R).
Enumerate elements of X so that x1Pix
2Pi · · ·Pixm, where x1, . . . , xm are the
only objects acceptable to i. If the stochastic assignments above are written
explicitly as
gi(R) =
m∑
t=1
γitx
t and fi(R) =
m∑
t=1
ωitx
t,
then we know from Lemma 1 that there exists s with γis > ωis such that γit = ωit
for t < s.
Let the preference relation R′i be the linear order derived from Ri by declaring
everything less preferable than xs according to Ri unacceptable in R
′
i and keeping
the order the same for everything else6, i.e., x1P ′ix
2P ′i · · ·P ′ixs, and iP ′ix if x 6= xt
for some t = 1, . . . , s.
Strategy-proofness of f implies that fi(R)R˜ifi(R
′
i, R−i). Since f is individually
rational, fi(R
′
i, R−i) does not involve any x
t for t > s, and hence can be written
explicitly as
∑s
t=1 ω
′
itx
t, to get
m∑
t=1
ωitx
t R˜i
s∑
t=1
ω′itx
t,
which implies
ωi1 ≥ ω′i1
ωi1 + ωi2 ≥ ω′i1 + ω′i2
...
ωi1 + ωi2 + · · ·+ ωis ≥ ω′i1 + ω′i2 + · · ·+ ω′is
On the other hand, strategy-proofness of g implies that gi(R
′
1, R−1)R˜
′
igi(R).
Writing gi(R
′
i, R−i) explicitly as
∑m
t=1 γ
′
itx
t, we get
m∑
t=1
γ′itx
t R˜′i
m∑
t=1
γitx
t,
6If R′i = Ri, then s = m, and
∑m
t=1 γit >
∑m
t=1 ωit, contradicting Reshuffling Lemma.
STRATEGY-PROOF STOCHASTIC ASSIGNMENT 17
which implies
γ′i1 ≥ γi1
γ′i1 + γ
′
i2 ≥ γi1 + γi2
...
γ′i1 + γ
′
i2 + · · ·+ γ′is ≥ γi1 + γi2 + · · ·+ γis
Combining the sets of inequalities above, we reach the following:
γ′i1 ≥ γi1 ≥ ωi1 ≥ ω′i1
γ′i1 + γ
′
i2 ≥ γi1 + γi2 ≥ ωi1 + ωi2 ≥ ω′i1 + ω′i2
...
...
...
γ′i1 + · · ·+ γ′is ≥ γi1 + · · ·+ γis ≥ ωi1 + · · ·+ ωis ≥ ω′i1 + · · ·+ ω′is
g dominates f , so it must be that g(R′i, R−i) weakly dominates f(R
′
i, R−i). Since
f is non-wasteful, Reshuffling Lemma implies
ω′i1 + ω
′
i2 + · · ·+ ω′is = γ′i1 + γ′i2 + · · ·+ γ′is.(6)
This equation combined with the last inequality above imply that
γi1 + γi2 + · · ·+ γis = ωi1 + ωi2 + · · ·+ ωis.
Since γit = ωit for t = 1, . . . , s − 1, the above equation implies that we also have
γis = ωis, which contradicts with the earlier choice of s such that γis > ωis. Hence
g cannot be strategy-proof. 
Proof of Proposition 2. We will first prove the following variation of Reshuffling
Lemma for assignments of equal size. Suppose that an assignment γ FOSD an
individually rational assignment ω. If |ω| = |γ|, then ∑x∈X γix = ∑x∈X ωix for
every i ∈ N .
Since γ dominates ω, and the latter is individually rational, γ is also individually
rational. Moreover each agent’s total assignment of objects in X under γ is at
least as much as it is under ω:∑
x∈X
γix =
∑
x:xPii
γix ≥
∑
x:xPii
ωix =
∑
x∈X
ωix for each i.(7)
Adding up across i:
|γ| =
∑
i∈N
∑
x:xPii
γix ≥
∑
i∈N
∑
x:xPii
ωix = |ω|.
Since we assumed that |γ| = |ω|, each weak inequality (7) must indeed be equality.
18 STRATEGY-PROOF STOCHASTIC ASSIGNMENT
Now, the proof of Proposition 1 above can be reproduced to conclude. 
Proof of Proposition 3. (i) Given |N | ≥ 4 and |X| ≥ 3, let 1, 2, 3, 4 ∈ N
stand for four distinct agents, whereas a, b, c ∈ X denote three distinct objects.
Consider the preference profile R, where every agent i ∈ N\{1, 2, 3, 4} finds every
object x ∈ X unacceptable. Suppose also that R2, R3 and R4 are as follows
R2 R3 R4
c c c
a b
.
We can express the preference domain for agent 1 as the disjoint union of the
following three sets:
Ra1 = {R1 | aPibPid for all d ∈ Xi\{a, b, c}}
Rb1 = {R1 | bPiaPid for all d ∈ Xi\{a, b, c}}
Rˆ1 = {R1 | There exists d ∈ Xi\{a, b, c} such that dPia or dPib}.
Note that when preferences are R with R1 ∈ Rˆ1, we will treat d as agent 1’s
outside option since there is no one else who finds d acceptable.
Below we will construct a mechanism g which improves over the RP for agent
1 when others’ preferences realize as R−1 specified above.
First of all, if R1 ∈ Rˆ1, then RP(R) is non-wasteful. For such preferences of
agent 1, g is identical to the RP. Hence we look at the cases when R1 ∈ Ra1 ∪Rb1.
Secondly, for all agents i 6= 1, the assignments are kept identical to what they
are under the RP:
gi(Q) = RPi(Q) for all i 6= 1 and for all Q.
Moreover,
if Q−1 6= R−1 or Q1 ∈ Rˆ, then g(Q) = RP(Q).
Note that agent 1’s total assignment at (R1, R−1) is 11/12 for all R1 ∈ Ra1 ∪Rb1.
For such preferences we would like to improve i’s assignment as follows:
g1(R1, R−1) = RP(R) + b if R1 ∈ Ra1,
g1(R1, R−1) = RP(R) + a if R1 ∈ Rb1.
We first need to show that the RP indeed wastes b at (R1, R−1) for all R1 ∈ Ra1,
and wastes a at (R1, R−1) for all R1 ∈ Rb1.
STRATEGY-PROOF STOCHASTIC ASSIGNMENT 19
If the serial dictatorship realizes as 3  1  2  4 or as 3  1  4  2, and
the preferences are (R1, R−1) with R1 ∈ Ra1, then object b is not assigned. This
is because, agent 3 gets c, then agent 1 gets her favorite object from {a, b}, which
is not b, as aP1b. And b is not acceptable to anyone else. Thus b is wasted with
probability at least 1/12.
Likewise, a is not assigned when preferences are (R1, R−1) with R1 ∈ Rb1, and
the serial dictatorship realizes as 2  1  3  4 or 2  1  4  3, because 2
would get c, 1 would get b, and a is not acceptable to agents 3 or 4. Therefore a
is wasted with probability at least 1/12.
Thus choosing  = 1/12 above is feasible, and agent 1 is strictly better off under
the mechanism g.
What remains to be shown is strategy-proofness of g. Note that if agent 1
prefers both a and b to d, the mechanism g improves upon the RP by assigning
her more of her less desired object from {a, b} when possible. If she prefers d over
either of them, she will get as much of d as she likes since she is the only agent
interested in d, and she has no reason to manipulate her preferences to move d
below a and b. Therefore, if R1 ∈ Rˆ1, she has no incentive to report a preference
order in Ra1 ∪ Rb1. For those preferences in Rˆ1, she is facing the RP, which is
strategy-proof, so it is a weakly dominant strategy for her to be truthful.
Now we need to verify that if R1 ∈ Ra1 ∪Rb1, she has no incentive to misreport.
By being truthful, she is doing at least as well as she would be under the RP. If
she were to report a ranking in Rˆ1, the mechanism is assigning just like the RP,
which is strategy-proof. Therefore, she cannot do better by reporting a ranking
in Rˆ1, when her actual preference is in Ra1 ∪ Rb1. Finally we need to show that
she has no incentive to report some other preference order R′1 ∈ Ra1 ∪Rb1. Let us
look at agent 1’s assignments at such announcements, when others’ preferences
are R−1 as specified above. Recall that we can treat d as her outside option since
she is the only agent who finds d acceptable.
If aP1bP11P1c, or aP1bP1cP11, or aP1cP1bP11, then her assignment is (18a +
6b)/24.
If bP1aP11P1c, or bP1aP1cP11, or bP1cP1aP11, then her assignment is (18b +
6a)/24.
If cP1aP1bP11, then her assignment is (6c+ 12a+ 6b)/24.
If cP1bP1aP11, then her assignment is (6c+ 12b+ 6a)/24.
20 STRATEGY-PROOF STOCHASTIC ASSIGNMENT
All these announcements lead to the same total amount of objects assigned to
agent 1. A straightforward pairwise comparison of these four outcomes verifies
that at each preference ranking R1 in Ra1 ∪ Rb1, truthful revelation (weakly or
strongly) first-order stochastically dominates untruthful revelation.
Finally we verify ex post efficiency of g. Note that the RP is ex post efficient
to start with. Improving 1’s assignment when R1 ∈ Ra1 involves increasing her
share of b by 1/12, while holding everyone else’s assignment the same. This can
be done by replacing the assignments on the left below with the assignments on
the right with probability share 1/12 each. Each assignment on the left is realized
with probability 1/12 or more, therefore this improvement is indeed feasible. And
the assignments on the right are efficient, therefore ex post efficiency is preserved.(
1 2 3 4
1 a b c
)
+
(
1 2 3 4
a 2 c 4
)
−→
(
1 2 3 4
b a c 4
)
+
(
1 2 3 4
a 2 b c
)
The argument for the case when R1 ∈ Rb1 is analogous.
This mechanism g treats agent 1 differently. In order to recover equal treatment
of equals, we will appeal to randomization again. Let pi be a permutation of the
agents, i.e., let pi : N → N be a bijection. Then gpi is defined via changing the
roles of the agents in mechanism g according to the permutation pi. Denoting with
Π the set of all permutations of N , we define h as
h =
1
n!
∑
pi∈Π
gpi.
Due to symmetry, h satisfies equal treatment of equals. By construction, for
each agent, there exists a preference profile at which the outcome of g is strictly
better than the outcome of the RP. Moreover, the outcome is always a convex
combination of deterministic efficient assignments. Hence g is a strategy-proof, ex
post efficient mechanism which satisfies equal treatment of equals and dominates
the RP.
(ii) The RP is a special case of the RDA where there is a single copy of each
object, and all agents have equal priority for every object. Therefore any non-
wasteful deterministic assignment is stable. Hence the above proof also shows
that the RDA admits strategy-proof improvement for some priority structure. For
completeness we note a “non-trivial” priority structure % for which the RDA is
STRATEGY-PROOF STOCHASTIC ASSIGNMENT 21
dominated by a strategy-proof mechanism:
%a %b %c %others
1− 4 1− 4 2− 4 others
others others 1 1− 4
others
R1 R2 R3 R4
a c c c
b a b
R′1
b
a
As in the above construction, agent 1’s assignment can be improved by adding
1/12 of b at (R1, R−1), and by adding 1/12 of a at (R′1, R−1) without skewing
incentives. 
Proof of Proposition 4. Let f stand for the RP. For any realization of the
tie-breaking lottery, we implement a serial dictatorship, so if an object x is top-
ranked by someone at R, then it is assigned to someone. Hence x cannot be
wasted at f(R), i.e.,
∑
i fix(R) = 1. Let the preference profile R be such that the
agents other than 1, 2, 3, 4 consider all objects unacceptable. Suppose also that
R1, R2, R3, R4, R
′
1, and Rˆ2 are
R1 R2 R3 R4
a c a c
b b
R′1
b
a
Rˆ2
b
c
.
f is wasteful at R since f(R) assigns the objects as
1 : 1
2
a+ 5
12
b
2 : 1
2
c+ 5
12
b
3 : 1
2
a
4 : 1
2
c
and it wastes b.
On the other hand, f is not wasteful at R′ = (R′1, R−1) nor at Rˆ = (Rˆ2, R−2),
because at both profiles, each acceptable object is top-ranked by someone. If g
dominates f , then g(R′) and g(Rˆ) weakly dominate f(R′) and f(Rˆ), respectively.
Then, by Reshuffling Lemma, we have
|gi(R′)| = |fi(R′)| and |gi(Rˆ)| = |fi(Rˆ)|.
R′1 and Rˆ2 are derived from R1 and R2, respectively, by permuting acceptable
objects, so strategy-proofness of f implies
|f1(R)| = |f1(R′)| and |f2(R)| = |f2(Rˆ)|,
22 STRATEGY-PROOF STOCHASTIC ASSIGNMENT
whereas strategy-proofness of g implies
|g1(R)| = |g1(R′)| and |g2(R)| = |g2(Rˆ)|.
Combining the three sets of equalities above, we get
|f1(R)| = |g1(R)| and |f2(R)| = |g2(R)|.
Since g dominates f , we know that g(R) weakly dominates f(R), and in partic-
ular, |gi(R)| ≥ |fi(R)| for each i. All agents get 1/2 of their top choices at f(R),
and these objects, namely a and c, are completely assigned. Therefore g(R) has
to assign the same fractions of these top choices as did f(R):
fix(R) = gix(R) for all i = 1, 2, 3, 4 and x = a, c.
b is not acceptable to agents 3 and 4, implying that g3(R) = f3(R) and g4(R) =
f4(R). On the other hand |f1(R)| = |g1(R)| and |f2(R)| = |g2(R)|, and hence
agents 1 and 2 are assigned the same amount of b under g(R) as they were under
f(R). Therefore g(R) = f(R), and thus g is wasteful at R. 
References
[1] A. Abdulkadirog˘lu, P. Pathak, and A. Roth, Strategy-proofness versus Efficiency in Match-
ing with Indifferences: Redesigning the NYC High School Match, Amer. Econ. Rev. 99
(2009) 1954–1978.
[2] A. Abdulkadirog˘lu, T. So¨nmez, Random Serial Dictatorship and the Core from Random
Endowments in House Allocation Problems, Econometrica 66 (3) (1998) 689–701.
[3] A. Bogomolnaia, H. Moulin, A New Solution to the Random Assignment Problem, J. Econ.
Theory 100 (2001) 295–328.
[4] A. Bogomolnaia, H. Moulin, Random Matching Under Dichotomous Preferences, Econo-
metrica 72 (1) (2004) 257–279.
[5] G. Carroll, A General Equivalence Theorem for Allocation of Indivisible Objects, Mimeo,
Stanford University, 2013.
[6] Y-K Che, F. Kojima, Asymptotic Equivalence of Probabilistic Serial and Random Priority
Mechanisms, Econometrica 78(5) (2010) 1625–72.
[7] L. Dubins, D. Freedman, Machiavelli and the Gale-Shapley algorithm, Amer. Math. Monthly
88 (1981) 485–494.
[8] L. Ehlers, Respecting Priorities when Assigning Students to Schools, Mimeo, University of
Montreal, 2006.
[9] L. Ehlers, A. Erdil, Efficient Assignment Respecting Priorities, J. Econ. Theory 145 (2010)
1269–1282.
[10] A. Erdil, H. Ergin, What’s the matter with tie-breaking? Improving efficiency in school
choice, Amer. Econ. Rev. 98 (3) (2008), 669–689.
STRATEGY-PROOF STOCHASTIC ASSIGNMENT 23
[11] H. Ergin, Efficient resource allocation on the basis of priorities, Econometrica 70 (2002)
2489–2497.
[12] D. Gale, L. Shapley, College admissions and the stability of marriage, Amer. Math. Monthly
69 (1962) 9–15.
[13] B. Holmstro¨m, R. Myerson, Efficient and Durable Decision Rules with Incomplete Informa-
tion, Econometrica 51(6) (1983) 1799–1819.
[14] O. Kesten, School Choice with Consent, Quart. J. Econ. 125 (2010) 1297–1348.
[15] O. Kesten, M. Kurino, On the (Im)possibility of Improving upon the Student-proposing
Deferred Acceptance Mechanism, WZB Discussion Paper, 2012.
[16] O. Kesten, U. U¨nver, A Theory of School-Choice Lotteries, Mimeo, Carnegie Mellon Uni-
versity and Boston College, 2012.
[17] F. Kojima, M. Manea, Incentives in Probabilistic Serial Mechanism, J. Econ. Theory 145
(2010) 106–123.
[18] Q. Liu, M. Pycia, Ordinal Efficiency, Fairness, and Incentives in Large Markets, Mimeo,
Columbia University and UCLA, 2012.
[19] P. Pathak, J. Sethuraman, Lotteries in student assignment: An equivalence result, Theo-
retical Economics 6 (2011) 1–17.
[20] H. Peters, S. Roy, A. Sen, T. Storcken, Probabilistic Strategy-Proof Rules over Single-
Peaked Domains, Mimeo, Maastricht and Indian Statistical Institute (New Delhi), 2013.
[21] M. Pycia, U. U¨nver, Decomposing Random Mechanisms, Mimeo, UCLA and Boston College,
2012.
[22] A. Roth, The economics of matching: Stability and incentives, Math. Oper. Res. 7 (1982)
617–628.
[23] L. Zhou, On a Conjecture by Gale about One-Sided Matching Problems, J. Econ. Theory
52 (1990) 125–135.