Department of Policy and Planning Sciences
Discussion Paper Series

No.1390

Note on Gale’s conjecture in one-sided matchingproblems

byHidekazu ANNO

February 24, 2024

Revised March 7, 2024

UNIVERSITY OF TSUKUBA
Tsukuba, Ibaraki 305-8573
JAPANNote on Gale’s conjecture in one-sided matchingproblems ∗Hidekazu Anno †March 7, 2024

Abstract
We consider the problem of stochastically allocating n indivisible objects ton agents when each agent assigns cardinal utility values to the objects. In thiscontext, Zhou (1990) demonstrates Gale’s conjecture in a stronger form: No rule
is strategy-proof, ex ante eﬃcient, and symmetric. We further strengthen this
impossibility theorem by relaxing the requirement of symmetry. Consequently,
we indicate that every strategy-proof and ex ante eﬃcient rule satisﬁes neither
symmetry nor the equal division lower bound.
Journal of Economic Literature Classiﬁcation Numbers: C78, D47, D71.
Keywords: Matching; Lottery rule; Strategy-proofness; Ex ante eﬃciency.

1

Introduction

We consider the problem of allocating indivisible objects without monetary transfers, known as the house allocation problem (Hylland and Zeckhauser, 1979; Svensson, 1999). This class of problems, where each agent has unit demand, is not only
important in the sense of possessing direct applications such as on-campus housing(Abdulkadiroğlu and Sönmez, 1999), but also as a special case or at least a building block of more complex and practically important problems, e.g., school choice∗

I gratefully acknowledge JSPS KAKENHI Grant Number 22K13359. All remaining errors are
my own.
†Institute of Systems and Information Engineering, University of Tsukuba, 1-1-1 Tennodai,
Tsukuba, Ibaraki 305-8573, Japan; e-mail: anno.hidekazu.fp@u.tsukuba.ac.jp1

(Abdulkadiroğlu and Sönmez, 2003). Hylland and Zeckhauser (1979) propose using
lotteries to solve the house allocation problem. Under a setup in which each agent
is an expected utility maximizer, they show that the pseudo-market rule can achieve
ex ante eﬃcient and envy-free allocation.1 However, their proposed method may
allow agents to be better oﬀ by misreporting their preferences. Speciﬁcally, it fails tosatisfy the representative incentive compatibility concept of strategy-proofness. Consequently, an important question remained unanswered: Is there a strategy-proof, ex
ante eﬃcient, and fair allocation rule? Gale (1987) oﬀered a concrete formulation ofthis problem and Zhou (1990) later proved a stronger form of Gale’s conjecture. Thatis, he proved that no rule is strategy-proof, ex ante eﬃcient, and symmetric.2 We
further strengthen this impossibility theorem by replacing symmetry with a weakercondition. Consequently, we show that every strategy-proof and ex ante eﬃcient rulesatisﬁes neither symmetry nor the equal division lower bound. In this context, theequal division lower bound requires that a rule always selects a probabilistic allocation that is at least as good as the perfectly fair lottery (uniform distribution) for all
agents. Therefore, one of the implications of our theorem (Corollary 2) is that if asocial planner wishes to design a rule better than the perfectly fair lottery, at least
one of strategy-proofness or ex ante eﬃciency must be abandoned.
Since the publication of Bogomolnaia and Moulin’s (2001) work, many authors
have studied lottery rules based on ordinal preference information. Among them,Martini (2016) and Nesterov (2017) extend the impossibility results presented in
Bogomolnaia and Moulin (2001). Ranjbar and Feizi (2023) also study the same
topic on a restricted preference domain. As we focus on cardinal rules, we do notconsider ordinal rules in this study. Alva and Manjunath (2020) establish a similar
impossibility result in the context of both one- and two-sided matching with outside
options. They demonstrate that no rule is strategy-proof, ex post eﬃcient, and ex
ante individually rational.3 Alongside Zhou (1990), Anno (2023) also studies the1

Generally, a system of resource allocation is called a rule, which is formalized as a function thatassigns an allocation for each resource allocation problem.
A probabilistic allocation is ex ante eﬃcient if it is impossible to improve any agent without
making another agent worse oﬀ in terms of expected utility. A probabilistic allocation is envy-free if
no agent prefers the probabilistic assignment of other agents to the agent’s own in terms of expectedutility.
2
A rule is symmetric if two agents have an identical utility function, then the rule selects aprobabilistic allocation in which these two agents enjoy the same expected utility.
3
Ex post eﬃciency, which is weaker than ex ante eﬃciency, requires that each deterministic allocation in the support of the selected probabilistic allocation has no Pareto-improving deterministic2

tension between eﬃciency, fairness, and incentives for cardinal rules.
The remainder of this paper is organized as follows. Section 2 introduces themodel and axioms. Section 3 presents the main results, and Section 4 concludes thepaper.

2

Model

2.1

BasicsLet N := {1, . . . , n} be a set of agents. We assume that at least three agents exist.
Let O := {o1 , . . . , om } be a set of objects. Each agent consumes exactly one object.
We assume that |O| = |N |, i.e., m = n, and that there is no outside option.
An assignment for agent i speciﬁes the object agent i receives. Formally, an mdimensional vector Pi = (Pio )o∈O ∈ {0, 1}m is called a deterministic assignment ifPo∈O Pio = 1. Note that Pio = 1 indicates that agent i receives object o. We sometimes interpret a deterministic assignment as an m × 1 matrix. A list of deterministic
assignments P = (P1 , . . . , Pn ) is called a deterministic allocation, or matching, if thesum of each row of P is equal to one. Let M be the set of deterministic allocations.
The purpose of this study is to investigate the house allocation problem when
randomization is introduced. Therefore, we extend the concept of assignment to include randomization. A probabilistic assignment, or assignment, for agent i isa probability distribution over the objects. That is, we call an m-dimensional vector
P
Pi = (Pio )o∈O ∈ [0, 1]m a probabilistic assignment ifo∈O Pio = 1, where Pio denotes
the probability for agent i to receive object o. Let ∆ be the set of probabilistic as
Psignments, i.e., ∆ := Pi = (Pio )o∈O ∈ [0, 1]mo∈O Pio = 1 . A list of probabilisticN
assignments P = (P1 , . . . , Pn ) ∈ ∆ is called a probabilistic allocation, or allocation, if the sum of each row of P is equal to one. Let P be the set of probabilistic
allocations. Note that M ⊆ P.
A probability distribution over M is called a lottery. Let L be the set of lotteries.
P
Remark 1. Note that every lottery ℓ ∈ L induces a probabilistic allocation M ∈M ℓM M .
Conversely, the following theorem, known as Birkhoﬀ-von Neumann theorem, holds:
allocation.
Ex ante individual rationality requires that each agent ﬁnds that the selected probabilistic allocation is at least as good as the agent’s own initial endowment (outside option). This concept iswell-deﬁned only if the model under consideration includes the outside option.

3

P
for any P ∈ P, there exists ℓ ∈ L such that P =M ∈M ℓM M . Thanks to the
Birkhoﬀ-von Neumann theorem, every probabilistic allocation can be implemented
by a lottery.
We assume that the preferences of each agent are embodied by a utility function.
Let U := {ui ∈ RO | maxo∈O ui (o) = 1 and mino∈O ui (o) = 0} be the set of admissible
utility functions over objects. Note that each utility function is standardized to attaina utility level of 1 at the maximizers and 0 at the minimizers.4 The utility function,
which is characterized by the following two features, plays an important role in the
proof of our main theorem: (i) a unique maximizer exists, and (ii) other objects are
indiﬀerent. Formally, a utility function ui ∈ U is single-minded if there exists o ∈ Osuch that ui (O\{o}) = {0}. For each o ∈ O, let U (o) be the set of single-mindedutility functions whose utility-maximizer is o.5
In this study, we assume that each agent is an expected utility maximizer. For
each ui ∈ U and each Pi ∈ ∆, let Eui (Pi ) be the expected utility of agent i with thePutility function ui at a probabilistic assignment Pi , i.e., Eui (Pi ) := o∈O Pio ui (o).
A house allocation problem, or problem for short, is a list (N, O, u), whereu ∈ U N . As we ﬁx N and O throughout this study, a problem is represented simply
by a utility function proﬁle. Thus, U N denotes the set of problems.
A resource allocation system is represented by a rule that assigns a probabilistic
allocation for each problem. That is, a rule is a function from U N to P. Our genericnotation for a rule is φ.

2.2

AxiomsFirst, we introduce several properties of the probabilistic allocation. The eﬃciency
property we employ is an adaptation of the standard Paretian eﬃciency concept
for our setup. An allocation P ∈ P is ex ante eﬃcient (EAE) at u ∈ U N if
there exists no allocation Q ∈ P such that Eui (Qi ) ≥ Eui (Pi ) for all i ∈ N , andEui (Qi ) > Eui (Pi ) for some i ∈ N . In this note, we consider three types of fairness
properties. An allocation P ∈ P is symmetric (S) at u ∈ U N if for all i, j ∈ Nwith ui = uj , Eui (Pi ) = Eui (Pj ). An allocation P ∈ P satisﬁes the equal division
4

We employ the preference domain adopted by Zhou (1990). As the main result of this note isan impossibility theorem, it is preserved on any broader domains.
5
The set U (o) is a singleton. This notation is useful when we describe an axiom in the next
subsection.

4lower bound (EDLB) at u ∈ U N if for all i ∈ N , Eui (Pi ) ≥ Eui n1 , . . . , n1 . The
following weak fairness property says that every member of a group of agents witha common single-minded preference should get at least n1 utility if it is physicallypossible. Formally, an allocation P ∈ P satisﬁes the equal division lower boundfor single-minded agents (EDLB-SMA) at u ∈ U N if for any S ∈ 2N \{∅},∃o ∈ O s.t. (∀i ∈ S, ui ∈ U (o)) and 1 −

X


Pio ≥

i∈N \S|S| 1⇒ ∀i ∈ S, Eui (Pi ) ≥ .
nnNote that each of S and EDLB implies EDLB-SMA.
Next, we introduce the properties of a rule. A rule φ is ex ante eﬃcient (EAE)(resp. symmetric (S), equal division lower bound (EDLB), equal division
lower bound for single-minded agents (EDLB-SMA)) if for each u ∈ U N ,the selected allocation φ(u) is ex ante eﬃcient (resp. symmetric, equal division
lower bound, equal division lower bound for single-minded agents) at u. Finally, we
introduce an incentive property of a rule. A rule φ is strategy-proof (SP) if foreach u ∈ U N , each i ∈ N , and each u′i ∈ U , Eui (φi (u)) ≥ Eui (φi (u′i , u−i )), where(u′i , u−i ) denotes the proﬁle obtained from u by replacing ui with u′i .

3Result

The following is the main result of this study, which highlights the tripartite tension
between eﬃciency, fairness, and incentives. A proof is presented after providing thethree lemmas.
Theorem 1. No rule is SP, EAE and EDLB-SMA.
Lemma 1 states an intuitively obvious fact regarding EAE allocation. Givenu ∈ U N , let i be an agent such that ui (o) > 0. Suppose that under an EAE allocation
φ(u), each agent j ∈ N \{i} evaluates object o as the worst, or φj (u) = 0. Then,the assignment φi (u) does not contain a positive probability share of objects worse
than o at ui . Additionally, if there is no object indiﬀerent to o at ui , φio (u) =P
1−
φio′ (u).
o′ ∈Oui (o′ )>ui (o)Lemma 1. Suppose that φ is EAE. Let o ∈ O, i ∈ N and u ∈ U N be such that5

(Lem 1-i) ui (o) > 0 and ̸ ∃o′ ∈ O\{o} s.t. ui (o′ ) = ui (o), and(Lem 1-ii) ∀j ∈ N \{i}, [uj (o) > 0 ⇒ φjo (u) = 0].
P
φio′ (u).
Then, φio (u) = 1 −o′ ∈Oui (o′ )>ui (o)Proof. Suppose to the contrary that φio (u) < 1 −Po′ ∈Oui (o′ )>ui (o)φio′ (u). Note that there

exists o′ ∈ O such that φio′ (u) > 0 and ui (o) > ui (o′ ) (∵ Lem 1-i). Note also that there
exists j ∈ N \{i} such that φjo (u) > 0 (∵ m = n). Letting ε := min{φio′ (u), φjo (u)},consider the following exchange between agents i and j: (i) ε units out of φjo (u) istransferred to agent i, and (ii) ε units out of φio′ (u) is transferred to agent j. The
resulting allocation Pareto-dominates φ(u) at u. However, this contradicts that φ is
EAE.
Before we proceed to Lemma 2, we introduce the following notation. Given o, o′ ∈O with o ̸= o′ , let U (o, o′ ) := {ui ∈ U|ui (o) = 1, ui (o′ ) ∈ (0, 1) and ui (O\{o, o′ }) ={0}}.
Lemma 2 illustrates the eﬀect of the deviation from a single-minded preference.
Suppose that agent i has ui ∈ U (o). Suppose also that an object o′ (̸= o) is a common
worst object for all agents. Then, under the SP and EAE rules, when only agent i’svaluation of object o′ solely increases, the probability share of object o assigned toagent i is invariant.
Lemma 2. Suppose that φ is SP and EAE. Let o, o′ ∈ O with o ̸= o′ , i ∈ N , u ∈ U N
and u′i ∈ U be such that
(Lem 2-i) ui ∈ U (o) and u′i ∈ U (o, o′ ), and(Lem 2-ii) ∀j ∈ N \{i}, uj (o′ ) = 0.
Then, φio (u′i , u−i ) = φio (u).
Proof. Suppose to the contrary that φio (u′i , u−i ) ̸= φio (u). If φio (u′i , u−i ) > φio (u),agent i has the incentive to misreport u′i at u (∵ ui ∈ U (o)). However, this contradicts
that φ is SP. Thus, in the sequel, we assume φio (u′i , u−i ) < φio (u). Note that thefollowing claim holds.
Claim. ∀u′′i ∈ U (o, o′ ), φio (u′′i , u−i ) = φio (u′i , u−i ). 6
Proof of Claim: Suppose the contrary. Assume, without loss of generality, that φio (u′′i , u−i ) <φio (u′i , u−i ). By Lemma 1, φio (u′i , u−i ) + φio′ (u′i , u−i ) = 1 and φio (u′′i , u−i ) + φio′ (u′′i , u−i ) = 1.
Thus, Eu′′i (φi (u′i , u−i )) > Eu′′i (φi (u′′i , u−i )), a violation of SP of φ.
66

Let a ∈ (0, 1) be such that a <u′′i (o′ ) = a. Then,φio (u)−φio (u′i ,u−i ) 7.
1−φio (u′i ,u−i )Eu′′i (φi (u)) = φio (u) + aφio′ (u)≥ φio (u)> φio (u′i , u−i ) + a(1 − φio (u′i , u−i ))Let u′′i ∈ U (o, o′ ) be such that(∵ a <

φio (u)−φio (u′i ,u−i ))
1−φio (u′i ,u−i )= φio (u′′i , u−i ) + a(1 − φio (u′′i , u−i )) (∵ Claim)= φio (u′′i , u−i ) + aφio′ (u′′i , u−i )(∵ Lemma 1)′′′′= Eui (φi (ui , u−i )) ,a violation of SP of φ.

In Lemma 3, we consider a situation where there is an object o which is the uniquemaximizer for all agents. Suppose that agents i and j have a common object o′ (̸= o)that is their second-most preferred, with i having a higher valuation on o′ . Suppose
also that object o′ is the worst object for the agents other than i and j. In this case,if agent i receives a positive probability share of object o, then (i) the probability
share of object o′ will be fully assigned to agents i and j, and (ii) agent i’s assignment
will consist only of the probability share of objects o and o′ .
Lemma 3. Suppose that φ is EAE. Let o, o′ ∈ O with o ̸= o′ , u ∈ U N and i, j ∈ Nwith i ̸= j be such that
(Lem 3-i) ui , uj ∈ U (o, o′ ) and ui (o′ ) > uj (o′ ),(Lem 3-ii) φio (u) > 0, and(Lem 3-iii) ∀k ∈ N \{i, j}, [uk (o) = 1, uk (o′ ) = 0 and {∀o′′ ∈ O\{o}, uk (o′′ ) < 1}].
Then, (i) φio′ (u) + φjo′ (u) = 1, and (ii) φio (u) + φio′ (u) = 1.
Proof. (i) Suppose to the contrary that φio′ (u) + φjo′ (u) < 1. Note that there existso′′ ∈ O\{o, o′ } such that φio′′ (u) > 0 or φjo′′ (u) > 0. Without loss of generality,
assume that φio′′ (u) > 0. Note also that there exists k ∈ N \{i, j} such that φko′ (u) >0 (∵ m = n). Then, an allocation that Pareto-dominates φ(u) is constructed throughthe transfer between agents i and k similar to the one in the proof of Lemma 1, acontradiction.
(ii) For notational simplicity, let a := ui (o′ ) and b := uj (o′ ). Note that φio′ (u) < 1(∵ Lem 3-ii). Thus, thanks to (i), φjo′ (u) > 0.
7

The right-hand side of the inequality is positive because φio (u′i , u−i ) < φio (u) ≤ 1.

7

To prove (ii), suppose to the contrary that φio (u) + φio′ (u) < 1. In this case, there
exists o′′ ∈ O\{o, o′ } such that φio′′ (u) > 0. Choose suﬃciently small ε > 0 such thatε < φio (u), εb < φjo′ (u) and εb (1 − b) < φio′′ (u). Deﬁne P ∈ ∆N as follows:
φio (u) − εφ ′ (u) + ε
iobPiõ :=
φ ′′ (u) − ε (1 − b)

io

b



φ (u)
iõ

if õ = o,if õ = o′ ,if õ = o′′ ,
o.w.




φjo (u) + εφ ′ (u) − εjob
Pj õ :=
φ ′′ (u) + ε (1 − b)

jo

b



φ (u)j õ

if õ = o,if õ = o′ ,if õ = o′′ ,

and

o.w.

Pk := φk (u) for k ∈ N \{i, j}.
Obviously, P is feasible, i.e., P ∈ P. Moreover,ε
Eui (Pi ) = (φio (u) − ε) + a φ (u) +b> φio (u) + aφio′ (u)io′(∵ a > b)= Eui (φi (u)),
and the assignments at P and φ(u) are indiﬀerent for other agents. Thus, P Paretodominates φ(u) at u, a contradiction.
A direct consequence of Lemma 3 is that under the assumptions of Lemma 3, theamount of the probability share of object o assigned to agent i is the same as that ofo′ assigned to agent j. This observation is eﬀectively used in the proof of Theorem 1.
Now, we provide a proof of Theorem 1.
Proof of Theorem 1. Suppose to the contrary that φ is SP, EAE and EDLB-SMA.
Let u0 ∈ U N be such that u0i ∈ U (o1 ) for all i ∈ N . Let u ∈ U N be such that
u1 , u2 ∈ U (o1 , o2 ) and ui ∈ U (o1 , oi ) for each i ∈ N \{1, 2}. The proof proceeds inthree steps.

Step 1. ∀S ∈ 2N , {1, 2} ̸⊆ S ⇒ ∀i ∈ N, φio1 (uS , u0−S ) = n1 .8
Proof of Step 1: We prove this by the induction on |S|. For |S| = 0, φio1 (u0 ) = n1
for each i ∈ N because φ is EDLB-SMA. Let S ∈ 2N be such that |S| ≥ 1. Suppose
8

The notation (uS , u0−S ) denotes the proﬁle in which each agent in S has the preference ui while
each agent in N \S has the preference u0i .

8that for any S ′ ∈ 2N with |S ′ | = |S| − 1, if {1, 2} ̸⊆ S ′ , then φio1 (uS ′ , u0−S ′ ) = n1 for
all i ∈ N .
Let i ∈ S be arbitrary. For S ′ := S\{i}, φio1 (uS ′ , u0−S ′ ) = n1 because of theinduction hypothesis. Note that by Lemma 2, φio1 (uS , u0−S ) = φio1 (uS ′ , u0−S ′ ). Thus,P
φio1 (uS , u0−S ) = n1 . Since i ∈ S is arbitrary, 1 − i∈S φio1 (uS , u0−S ) = |Nn\S| . Thanks
to EDLB-SMA, φjo1 (uS , u0−S ) = n1 for each j ∈ N \S. This completes the proof of
Step 1.
Step 2. Let {i, j} := {1, 2}. Suppose that ui (o2 ) > uj (o2 ). Then, (i) φio1 (u) = n1and φio2 (u) = n−1, and (ii) φjo1 (u) = n1 and φjo2 (u) = n1 .
nProof of Step 2: Applying Step 1 to S = N \{i}, φko1 (u0i , u−i ) = n1 for each k ∈ N .
n−1
n−1
0
Moreover, by Lemma 1, φjo2 (u0i , u−i ) = n , and φkok (ui , u−i ) = n for each k ∈1

 n. 0.
N \{1, 2}. Thus, φi (ui , u−i ) = 
 .  (∵ m = n). Summing up, we obtain
1
n

j

3

···

n

1
 n1
o2 
n
1
o3 
n

1
n
n−1
n

1
n

···
···
···
..
.

1
n

1
n

0



i

o1

φ(u0i , u−i ) =

on

n−1
n

0
..
.


...  ...


0
..
.
0




0 


0 .
.. 
. 


···

n−1
n

(1)

Similarly, applying Step 1 to S = N \{j}, we obtain


i

1
n
 n−1
o2 
 n
o1

φ(u0j , u−j ) =


0
.. 
..
. 
 .
on
0
o3 

j

3

···

n

1
n
1
n
1
n

1
n

···
···
···
...

1
n

..
.

1
n

0
n−1
n

..
.
0

···




0 


0 .
.. 
. 

n−1
n

The following claim is an immediate consequence of (1) and (2).

9(2)

Claim. φio1 (u) ≤ n1 and φjo1 (u) ≤ n1 . 9
Now, we complete the proof of Step 2. As φ is SP, Euj (φj (u)) ≥ Euj (φj (uj0 , u−j )).
Thus, by (2), we haveφjo1 (u) + uj (o2 )φjo2 (u) ≥11+ uj (o2 ).
n n

(3)

This inequality implies that φjo2 (u) ≥ n1 (∵ The latter part of Claim). As an implication of Lemma 3 is φjo2 (u) = φio1 (u), φio1 (u) ≥ n1 . Therefore, combined with theﬁrst part of Claim, we obtain φio1 (u) = n1 . Thus, by (ii) of Lemma 3, φio2 (u) = n−1.
nThe proof of (i) is completed.
Finally, we show (ii). As φio1 (u) = n1 , by the implication of Lemma 3 again,
φjo2 (u) = n1 . Substituting this to (3), we obtain φjo1 (u) ≥ n1 . Thus, combined withthe latter part of Claim, we obtain φjo1 (u) = n1 . This completes the proof of Step 2.
Step 3. Concluding.
We assume that u2 (o2 ) > u1 (o2 ). Let u′1 ∈ U (o1 , o2 ) be such that u′1 (o2 ) >u2 (o2 ). Then, by Step 2, we have (i) φ1o1 (u1 , u−1 ) = n1 and φ1o2 (u1 , u−1 ) = n1 ,. As we assume that n ≥ 3,
and (ii) φ1o1 (u′1 , u−1 ) = n1 and φ1o2 (u′1 , u−1 ) = n−1nEu1 (φ1 (u′1 , u−1 )) > Eu1 (φ1 (u1 , u−1 )), a contradiction.
Note that the three axioms in Theorem 1 are independent. That is, dropping oneof these axioms leads to the existence of a rule. For this, refer to examples of rules
provided by Zhou (1990).
The following two impossibility results are immediate corollaries of Theorem 1.
Corollary 1 (Zhou, 1990; Nesterov, 2017). No rule satisﬁes SP, EAE and S.
Corollary 2 (Anno, 2023). No rule satisﬁes SP, EAE and EDLB.
Remark 2. In this study, Theorem 1 is established under the assumption that |O| =|N |. This assumption is utilized three times within the series of proofs (Lemmas 1, 3,
and Step 2 of Theorem 1). Among these, this assumption is critical only for the proofof Step 2 of Theorem 1. To extend Theorem 1 to general cases, a proof technique forthis part must be developed.
Proof of Claim: To prove the ﬁrst part, suppose to the contrary that φio1 (u) > n1 . Note thatby (1), φio1 (u0i , u−i ) = n1 . Thus, agent i has the incentive to misreport ui at (u0i , u−i ). However,this violates the SP of φ.
Similarly, the latter is proven using (2). This completes the proof of Claim.
9

10

4

Conclusion

We investigated the problem of stochastically allocating indivisible objects when eachagent is an expected utility maximizer. In this environment, we demonstrated thatthe combination of strategy-proofness and ex ante eﬃciency is incompatible with the
weak fairness notion called the equal division lower bound for single-minded agents.
In the context of pure exchange economies, resource allocation rules satisfying
both strategy-proofness and Pareto eﬃciency have been shown to violate various
fairness notions (Hurwicz, 1972; Zhou, 1991; Serizawa, 2002). An extreme result inthis research line is given in Momi (2017). He demonstrated that every strategy-proof
and Pareto eﬃcient rule is an alternately dictatorial rule in which each economy has
an individual who consumes all resources. In the context of the stochastic allocationof indivisible objects, such a rule can be interpreted as one in which each problem has
an agent who receives 1 unit of the probability share of the most preferred object. At
this stage, we do not know the exact degree of unfairness provoked by the combinationof strategy-proofness and ex ante eﬃciency. We believe that the analysis in this study
is useful in this research line.10

References
Abdulkadiroğlu, A., and T. Sönmez (1999): “House Allocation with Existing
Tenants,” Journal of Economic Theory, 88, 233–260.
(2003): “School Choice: A Mechanism Design Approach,” American Economic Review, 93, 729–747.
Alva, S., and V. Manjunath (2020): “The Impossibility of Strategy-proof, Paretoeﬃcient, and Individually Rational Rules for Fractional Matching,” Games andEconomic Behavior, 119, 15–29.
Anno, H. (2023): “Eﬃcient and strategy-proof cardinal rules on a restricted domain,”
Discussion paper NO. 1387, University of Tsukuba.

10

When the preference domain is restricted to the one with ordinally-identical utility functions,a rule satisfying strategy-proofness and ex ante eﬃciency may not be alternately dictatorial (Anno,2023).

11

Bogomolnaia, A., and H. Moulin (2001): “A New Solution to the Random
Assignment Problem,” Journal of Economic Theory, 100, 295–328.
Gale, D. (1987): “College Course Assignments and Optimal Lotteries,” Universityof California at Berkeley.
Hurwicz, L. (1972): “On Informationally Decentralized Systems,” in Decision andOrganization, ed. by G. McGuire, and R. Radner. North Holland, Amsterdam.
Hylland, A., and R. Zeckhauser (1979): “The Eﬃcient Allocation of Individuals
to Positions,” Journal of Political Economy, 87, 293–314.
Martini, G. (2016): “Strategy-proof and Fair Assignment is Wasteful,” Games andEconomic Behavior, 98, 172–179.
Momi, T. (2017): “Eﬃcient and Strategy-proof Allocation Mechanisms in Economies
with Many Goods,” Theoretical Economics, 12, 1267–1306.
Nesterov, A. S. (2017): “Fairness and Eﬃciency in Strategy-proof Object Allocation Mechanisms,” Journal of Economic Theory, 170, 145–168.
Ranjbar, H. H., and M. Feizi (2023): “Random Assignments with Uniform Preferences: An Impossibility Result,” Operations Research Letters, 51(3), 304–307.
Serizawa, S. (2002): “Ineﬃciency of Strategy-Proof Rules for Pure Exchange
Economies,” Journal of Economic Theory, 106, 219–241.
Svensson, L.-G. (1999): “Strategy-proof Allocation of Indivisible Goods,” Social
Choice and Welfare, 16, 557–567.
Zhou, L. (1990): “On a Conjecture by Gale about One-Sided Matching Problems,”
Journal of Economic Theory, 52, 123–135.
(1991): “Ineﬃciency of Strategy-Proof Allocation Mechanisms in Pure Exchange Economies,” Social Choice and Welfare, 8, 247–257.

12