Discussion Papers In Economics
And Business

A Characterization of
the Randomized Uniform Rule
Wataru KUREISHI

Hideki MIZUKAMI

Discussion Paper 05-20

Graduate School of Economics andOsaka School of International Public Policy (OSIPP)
Osaka University, Toyonaka, Osaka 560-0043, JAPANA Characterization of
the Randomized Uniform Rule
Wataru KUREISHI

Hideki MIZUKAMI

Discussion Paper 05-20

July 2005
この研究は「大学院経済学研究科・経済学部記念事業」
基金より援助を受けた、記して感謝する。
Graduate School of Economics andOsaka School of International Public Policy (OSIPP)
Osaka University, Toyonaka, Osaka 560-0043, JAPANA Characterization of
the Randomized Uniform Rule∗
Wataru KUREISHI†‡
kureishi@iser.osaka-u.ac.jp

Hideki MIZUKAMI§
mizukami@eco.toyama-u.ac.jp

July 1, 2005

Abstract
We consider the problem of allocating several units of an indivisible
object among the agents with single-peaked and risk-averse utility
functions. We introduce equal probability for the best, and show thatthe randomized uniform rule is the only randomized rule satisfying
strategy-proofness, Pareto optimality, and equal probability for the
best. This is an alternative characterization of the result of Ehlers
and Klaus (2004).

JEL classiﬁcation: D63, D71
Keywords: The Randomized Uniform Rule, Single-Peaked Utility
Functions, Equal Probability for the Best, Strategy-Proofness, Indivisibility∗

This paper owes much to thoughtful and helpful comments of Hideshi Itoh, Tatsuyoshi
Saijo, Ken-Ichi Shimomura, and Takuma Wakayama. We also thank Shinji Ohseto, participants of the Japanese Economic Association meeting of May 2001, and seminar participants at Osaka University for their useful comments. The earlier version of this paper
received the Osaka University Institute of Social and Economic Research Moriguchi Prizein January 2003.
†
Graduate School of Economics, Osaka University, Japan.
‡
Corresponding author.
§
Faculty of Economics, Toyama University, Japan.

1Introduction

We consider the situation where the manager of a ﬁrm allocates several recruited workers to some departments such as sales, production, and so on.
Each department has an optimal number of workers, because if the department has fewer workers than the number, it cannot accomplish its task, andif it has more, it needs extra equipment and incurs additional training costs.
The above mentioned problem faced by the manager is an example ofthe problem of allocating several units of an indivisible and identical object among a ﬁnite group of agents with single-peaked, risk-averse, and vonNeumann and Morgenstern utility functions. In this paper, we analyze theproblem axiomatically, which was initiated by Sasaki (1997).
When the objects are inﬁnitely divisible, a deterministic rule known as theuniform rule is a solution to the above problem in the sense that it satisﬁes
strategy-proofness, eﬃciency, and some kind of fairness (Benassy (1982),
Sprumont (1991), and Ching (1994)). The uniform rule works as follows:each agent is allowed to choose his/her own peak subject to a common boundwhich is chosen so as to attain feasibility.
However, the uniform rule cannot be applied to the problem where theobjects are not inﬁnitely divisible but indivisible because the common boundthat the uniform rule allocates can be a fraction. In order to deal with thediﬃculty due to indivisibility, we use not deterministic rules but randomized
rules, which associate with each proﬁle of the utility functions a probability
distribution on feasible allocations. Another justiﬁcation for considering randomized rules rather than deterministic rules is that it is the simplest way
to ensure fairness when the objects are indivisible.
As we consider a probabilistic extension of rules, it is reasonable to consider a probabilistic extension of the uniform rule, which we call the randomized uniform rule. The randomized uniform rule is a randomized rule
which outputs a probability distribution that has the following marginal distribution: the agent who gets his/her own peak under the uniform rule gets
his/her own peak with probability 1, and the rest of the agents get thecommon bound rounded up and that rounded down with the common probabilities which are chosen so as to equate the expected value of each agent
to the common bound.
Sasaki (1997) ﬁrst considered the randomized extension of the uniform
rule. He introduced an equal probability uniform rule, which is a special
case of the randomized uniform rule, and showed that it satisﬁes strategy1

proofness, Pareto optimality, and anonymity. He also pointed out the importance of risk-averseness of the utility functions. If risk-loving von-Neumann
and Morgenstern utility functions are allowed, the randomized uniform rule
does not satisfy Pareto optimality.
In this paper, we characterize the randomized uniform rule by strategyproofness, Pareto optimality, and equal probability for the best. Equal probability for the best is the axiom relating to fairness. Given an agent anda probability distribution, let us call the number of the object which gives
him/her the highest utility with a strictly positive probability the best for
the agent. Then, equal probability for the best requires the randomized rules
to output the probability distribution which has the following marginal distribution: if two agents have the same utility function, then they should
get the same best with the same probability. For example, suppose that the
manager has to allocate three recruited workers to two departments, A andB. Further, we assume that both departments have the same utility function
and want more than three workers, that is, their peaks are three. Let us consider the case in which a randomized rule outputs a probability distribution
which gives department A the marginal distribution that places probability
zero on getting three workers, and probability 1/3 on getting two, one, andno worker(s) respectively. We can say that getting two workers is the bestfor department A in this case. Then, this axiom requires that the probability
distribution should give department B the marginal distribution where getting two workers is the best for it and is placed probability 1/3 on. However,the probability placed on getting one worker and that on getting no worker
do not need to be equal between the departments.
The contributions of this paper are as follows. First, our paper is the ﬁrst
to introduce the axiom relating to fairness that is indigenous to indivisibilityor randomization. The axioms used in previous papers on randomization of
the uniform rule, such as equal treatment of equals, symmetry, anonymity,
and so on, are just the randomized version of those used in the deterministic
environment. However, equal probability for the best has no counterpart in
the deterministic environment. In addition, equal probability for the best is aweak axiom in the sense that it requires that only a part of the marginal distribution should be equal between the agents with the same utility function,
whereas some other axioms require the whole part should be.
Second, we succeed in characterizing the randomized uniform rule bystrategy-proofness, Pareto optimality, and equal probability for the best.
This result is an alternative characterization of Ehlers and Klaus’ (2004).
2

They succeeded in characterizing the randomized uniform rule by strategyproofness, Pareto optimality, and equal treatment of equals. This implies
that in the presence of strategy-proofness and Pareto optimality, equal probability for the best and equal treatment of equals are identical, whereas equal
probability for the best is logically independent of equal treatment of equals.
This paper is organized as follows: Section 2 describes the model. Several
axioms and the randomized uniform rule are introduced, and our theorem ispresented in Section 3. The proof of our theorem is similar to that of Ching(1994).

2

The Model

We consider the problem of allocating several units X ∈ Z++ of an indivisible
object among a ﬁnite group of agents, N = {1, 2, . . . , n}. The objects are
identical. We denote the set of the indivisible objects by C = {0, 1, 2, . . . , X}.
Each agent i ∈ N has a von-Neumann and Morgenstern utility function
ui : C → R which is single-peaked and risk-averse. ui is single-peaked if there
is a unique peak p(ui ) ∈ C such that for all k, k  ∈ C with p(ui ) ≤ k < k or k  < k ≤ p(ui ), ui(p(ui )) ≥ ui (k) > ui (k  ). ui is risk-averse if for any
k ∈ C\{0, X}, ui (k) − ui (k − 1) > ui (k + 1) − ui (k). We assume that theutility functions are only privately known. Let U be the set of all singlepeaked, risk-averse, and von-Neumann and Morgenstern utility functions.
u = (u1, u2, . . . , un ) ∈ U n is called a proﬁle of the utility functions. u−istands for (u1, . . . , ui−1 , ui+1, . . . , un ) ∈ U n−1 . (N, u, X) is called a problem.
We
say
that
the
problem
isinexcessdemandifi∈N p(ui ) ≥ X. Ifi∈N p(ui ) < X, the problem is in excess supply. A feasible allocation is avector x = (x1 , x2, . . . , xn ) ∈ C n with i∈N xi = X.1 Let A(X) be the setof all feasible allocations.
 f is a probability distribution on A(X) such thatf : A(X) → [0, 1] and x∈A(X ) f(x) = 1. Let S(X) be the set of all probability distributions on A(X). A randomized rule is a function φ : U n → S(X).
We deﬁne the probability with which a probability distribution
f gives kunits of the indivisible object to agent i by fi (k) ≡ x∈{x∈A(X )|xi=k} f(x).
This means that fi is the marginal distribution of f with respect to the number of theobject that the agent i obtains. Given a probability distribution f,
we call k∈C fi (k)ui(k) the expected utility of agent i. We abuse notation,
1Free-disposability is not allowed.

3

and write φ(u)(x) as φ(x; u) and φi (u)(k) as φi (k; u).2
The following example demonstrates that two distinct probability distributions have the same marginal distribution.
Example 1. Let n = 4 and X = 2. Let f = [ 16 ◦ (1, 1, 0, 0), 16 ◦ (1, 0, 1, 0), 16 ◦(1, 0, 0, 1), 16 ◦(0, 1, 1, 0), 16 ◦(0, 1, 0, 1), 16 ◦(0, 0, 1, 1)] and f  = [ 12 ◦(1, 1, 0, 0), 12 ◦(0, 0, 1, 1)]. Both f and f  give each agent i the same marginal distributionfi (k) = fi (k) = 12 for k = 0, 1 and fi (2) = fi (2) = 0.

3

Axioms and the Randomized Uniform Rule

We are interested in the following axioms. The ﬁrst is the requirement thatno agent ever beneﬁts from misrepresenting his/her utility function, which isonly privately known.
Strategy-proofness.For any i ∈ N, any ui , ûi ∈ U, and any u−i ∈ U n−1 ,k∈C φi (k; u)ui (k) ≥k∈C φi (k; ûi , u−i )ui (k).
A standard axiom that needs no further explanation is Pareto optimality.
nPareto optimality.
For any u ∈ U , there is no f ∈ S(X) such that
for
 all i ∈ N, k∈Cfi (k)ui (k) ≥ k∈C φi (k; u)ui(k) and for some j ∈ N,k∈C fj (k)uj (k) >k∈C φj (k; u)uj (k).
Pareto optimality implies same-sidedness, which requires that for any agent
every number of the object which he/she obtains with a strictly positive
probability should be equal to or less (more) than his/her own peak when
the problem is in excess demand (supply).
Same-sidedness.
For any u ∈ U n and any i ∈ N,(i) when j∈N p(uj ) ≥ X, for all k ∈ C, φi (k; u) > 0 implies k ≤ p(ui ), and(ii) when j∈N p(uj ) < X, for all k ∈ C, φi (k; u) > 0 implies k ≥ p(ui ).
Lemma 1. If φ is Pareto optimal, then it is same-sided.
Proof of Lemma 1. See Sasaki (1997).
For the converse statement of Lemma 1 to be true we need property B, which
is presented in the Appendix.
The ﬁnal is related to fairness. We call it equal probability for the best. Givena probability distribution and an agent, there exists a number of the object
2

φ(x; u) is the probability which the randomized rule φ places on the feasible allocationx ∈ A(X) when the reported utility profile is u ∈ U n . φi (k; u) is the probability with which
agent i obtains k units of the object under the randomized rule φ when the reported utility
profile is u.

4which gives him/her the highest utility with a strictly positive probability.
The number is called the best. It should be noted that since every utility
function is single-peaked the agent has at most two bests: one is on theleft side of his/her peak and the other is on the right side. Also note thateach agent has only one best if the randomized rule satisﬁes same-sidedness.
Then, equal probability for the best requires the randomized rule to output
the probability distribution which has the following marginal distribution: if
two agents have the same utility function, then at least one of the bests andthe corresponding probabilities should be same between the agents. Note thatthe marginal distribution of each agent does not need to be same between
the agents.
In order to deﬁne equal probability for the best formally, for any i ∈ N
and any f ∈ S(X), we need Bfi : the set of all pairs consisting of both thenumber of the object which gives agent i the highest utility with a strictly
positive probability and the corresponding probability of the number under
the probability distribution f. Note that Bfi is a singleton or a doubleton.
For any probability distribution f ∈ S(X), any i ∈ N, and any ui ∈ U, let
Bfi ≡ {(b, fi (b)) ∈ C × (0, 1] | ui (b) ≥ ui(k) for all k ∈ C such that fi (k) >0}.
Using Bfi , equal probability for the best can be represented as follows.
Equal probability for the best. For any u ∈ U n and any i, j ∈ N, ifji∩ Bφ(u)= ∅.
ui = uj , then Bφ(u)Equal treatment of equals says that if two agents’ utility functions are same,
their expected utilities should also be same.
Equal
For any u ∈ U n and any i, j ∈ N, if ui = uj ,treatment of equals.
then k∈C φi (k)ui (k) = k∈C φj (k)uj (k).
Remark 1. Both equal probability for the best and equal treatment of equals
are implied by symmetry, 3 which is weaker than anonymity.4 It is easy tocheck that equal probability for the best and equal treatment of equals are
logically independent.
When objects are inﬁnitely divisible, a well-known deterministic rule satisfying strategy-proofness is the uniform rule (Benassy (1982)). It is the3

For any u ∈ U n and any i, j ∈ N , if ui = uj , then φi (k) = φj (k) for all k ∈ C.
For any u ∈ U n , any permutation π of N , any i ∈ N , and any k ∈ C, φi (k; uπ ) =φπ(i) (k; u) where uπ = (uπ(1) , uπ(2) , . . . , uπ(n) ) ∈ U n .
45function Υ : U n → Rn+ such that for any u ∈ U n ,
min{p(uj ), λ} ifi∈N p(ui ) ≥ X,
Υj (u) ≡max{p(uj ), λ} otherwise,for all j ∈ N, where λ ∈ R+ solves i∈N Υi (u) = X.
We must note that the common bound λ can be a fraction so the uniform
rule cannot be used to solve the problems with the indivisible objects. Asan alternative rule, we propose a probabilistic extension of the uniform rule,
the randomized uniform rule, which is a particular randomized rule.
Definition 1. The randomized uniform rule Φ : U n → S(X) is the function
deﬁned asfollows: for any u ∈ U n ,(i) when i∈N p(ui ) ≥ X,
if p(uj ) ≤ λ,
 Φj (p(uj ); u) = 1
Φj (µ + 1; u) = λ − µif p(uj ) > λ,
= 1 − (λ − µ)
Φj (µ; u)(ii) when i∈N p(ui ) < X,
if p(uj ) ≥ λ,
 Φj (p(uj ); u) = 1
Φj (µ + 1; u) = λ − µif p(uj ) < λ,
= 1 − (λ − µ)
Φj (µ; u)
for all j ∈ N, where λ ∈ R+ solves i∈N k∈C Φi (k)k = X and µ ≡ λ .56
The randomized uniform rule associates with each proﬁle of the utility functions a probability distribution that induces the marginal distribution of thefollowing form. When the problem is in excess demand (supply), the agent
whose peak is equal to or less (more) than the common bound λ gets his/herown peak with probability 1. The rest of the agents get µ+1 with probability
λ − µ and µ with probability 1 − λ + µ respectively. µ is obtained throughrounding down the common bound λ.
The randomized uniform rule outputs “a” probability distribution which
induces each agent’s marginal distribution deﬁned as (i) and (ii) of Deﬁnition 1. Hence, the randomized uniform rule uniquely determines a marginal
5

For any a ∈ R, let a = n be the integer such that n ≤ a < n + 1.
More than one probability distribution can have the marginal distribution defined as(i) and (ii) of Definition 1, as we pointed out in Example 1. The randomized uniform rulechooses one of such probability distributions arbitrarily.
66distribution for each agent, but it does not uniquely determine a probability
distribution (although it uniquely chooses a probability distribution) because,
as we pointed out in Example 1, more than one probability distribution canhave an identical marginal distribution.
A special case of the randomized uniform rule is the equal probability
uniform rule.
Example 2. The equal probability uniform rule Ψ : U n → S(X) is deﬁned asfollows: for any u ∈ U n ,(i) Ψi (u) = Φi (u) for any i ∈ N, and(ii) Ψ(x; u) = Ψ(x; u) for any x, x ∈ A(X) such that Ψ(x; u) > 0 andΨ(x; u) > 0.
The equal probability uniform rule outputs the probability distribution (i)which has the same marginal distribution as that of the randomized uniform
rule, and (ii) where any feasible allocations each of which is given a strictly
positive probability have an equal probability. Sasaki (1997) introduced arandomized uniform rule which is a particular equal probability uniform rule,
which uniquely determines not only a marginal distribution for each agent
but also a probability distribution (see Sasaki (1997) for details).

3.1

An Alternative Characterization of the Randomized Uniform Rule

The randomized uniform rule can be characterized by strategy-proofness,
Pareto optimality, and equal probability for the best.
Theorem. The randomized uniform rule Φ is the only randomized rulesatisfying strategy-proofness, Pareto optimality, and equal probability forthe best.
Proof of the Theorem. Proof of the Theorem is in the Appendix.
The main feature of this Theorem is that our characterization is conductedwith the axiom, equal probability for the best with respect to the axiom relating to fairness. This axiom is indigenous to indivisibility or randomization
so that it has no counterpart in the deterministic environment. On the other
hand, in previous papers on randomization of the uniform rule, all axioms
on fairness, such as equal treatment of equals, symmetry, anonymity, and soon, are just the randomized version of those used in the deterministic environment. Hence, we can say that our characterization is the ﬁrst one that is7

not a mere randomized version of the results obtained in the deterministic
environment.
Ehlers and Klaus (2004) showed that the class of the randomized uniform
rules is characterized by Pareto optimality, strategy-proofness, and equal
treatment of equals. Hence, by our Theorem we succeed in giving an alternative characterization of Ehlers and Klaus’ (2004). This implies thatin the presence of strategy-proofness and Pareto optimality, equal probability for the best and equal treatment of equals are identical, whereas equal
probability for the best is logically independent of equal treatment of equals.
Moreover, by Remark 1 anonymity or symmetry implies equal probability
for the best respectively, and it is obvious that the randomized uniform rulesatisﬁes anonymity and symmetry. These indicate that equal probability forthe best, equal treatment of equals, symmetry, and anonymity are identicalin the presence of strategy-proofness and Pareto optimality.

8References
Benassy, J. P. (1982) The Economics of Market Disequilibrium, New York:
Academic Press.
Ching, S. (1994) “An Alternative Characterization of the Uniform Rule”,
Social Choice and Welfare, Vol. 11, No. 2, pp. 131-136.
Ehlers, L. and B. Klaus (2004) “Probabilistic Assignments of Identical Indivisible Objects and Uniform Probabilistic Rule”, Review of Economic Design,Vol. 8, No. 3, pp. 249-268.
Sasaki, H. (1997) “Randomized Uniform Allocation Mechanism and SinglePeaked Preferences of Indivisible Good”, Waseda University, mimeo.
Sprumont, Y. (1991) “The Division Problem with Single-Peaked Preferences:
A Characterization of the Uniform Allocation Rule”, Econometrica, Vol. 59,
No. 2, pp. 509-519.

9

Appendix
Before proceeding to prove the Theorem, we need some following lemmas.
Lemma 2 says that Pareto optimality implies property B, which requiresthat randomized rules assign the probability distribution where each agent
receives at most two numbers of the object which are adjacent with eachother.
Property B (Sasaki (1997)). For any u ∈ U n and any i ∈ N, there exists
αi ∈ C with φi (αi + 1; u) > 0 such that φi (αi ; u) + φi (αi + 1; u) = 1.
Lemma 2 (Sasaki (1997)). If φ satisﬁes Pareto optimality, then it satisﬁes
property B.
Proof of Lemma 2. See Sasaki (1997).
If we assume that φ satisﬁes same-sidedness, then we can show the converse statement of Lemma 2.
Lemma 3. If φ satisﬁes same-sidedness and property B, then it satisﬁes
Pareto optimality.
Proof of Lemma 3.Suppose the contrary.
There exists f ∈ S(X) suchthatfor all i ∈ N, k∈Cfi (k)ui (k) ≥ k∈C φi (k; u)ui(k) and for some j ∈N, k∈C fj (k)u
 Without loss of generality, we j (k) > k∈C φj (k; u)uj (k).
assume that i∈N p(ui ) ≥ X. Let λi ≡ k∈C fi (k)k and µi ≡ λi for alli ∈ N. From risk-averseness,
we have for all i ∈ N, (1 − λi + µi )ui (µi ) +(λi − µi )ui (µi + 1) ≥ k∈C fi (k)ui (k). From property B, for all i ∈ N, there
existsαi ∈ C such that φi (αi ; u) + φi (αi + 1; u) = 1. Therefore, we haveφk∈C i (k; u)ui (k) = φi (αi ; u)ui(αi ) + φi (αi + 1; u)ui (αi + 1) for all i ∈ N.
Hence, we have (1 − λi + µi )ui (µi ) + (λi − µi )ui (µi + 1) ≥ φi (αi ; u)ui(αi ) +φi (αi +1; u)ui(αi +1) for all i = j and (1−λj +µj )uj (µj )+(λj −µj )uj (µj +1) >φj (αj ; u)uj (αj ) + φj (αj + 1; u)uj (αj + 1).
From same-sidedness, we have for all i ∈ N, p(ui ) ≥k∈C φi (k; u)k.
Hence, single-peakedness implies that for all i = j, (1 − λi + µi )µi + (λi −µi )(µi + 1) ≥ φi (αi ; u)αi + φi (αi + 1; u)(αi + 1) and (1 − λj + µj )µj + (λj −µj )(µj + 1) > φj (αj ; u)αj +φj (αj + 1; u)(αj + 1).  us i∈N (1 − λi + µi )µi + i∈N (λi − µi )(µi + 1) >
 Summing up givesu)αi +
i∈N φi (αi ;
 i∈N φi (αi + 1; u)(αi + 1). The left hand side becomes
λ
=
i∈N i
i∈N
k∈C fi (k)k = X. The last equalityfollows from feasibility.
Moreover, the right hand side also becomes i∈N k∈C φi (k; u)k = X byfeasibility. This is a contradiction.
10

Property B is the key property in the sense that the problem of allocating
X units of the identical and indivisible object among n individuals withsingle-peaked and risk-averse utility functions reduces to that of allocating
X amount of the inﬁnitely divisible object among them, as explained in
Ehlers and Klaus (2004).
The rest closely follows Ching (1994). Lemma 4 says that Pareto optimality and strategy-proofness imply own peak monotonicity, which requires thatthe expected value of the marginal distribution of each agent is monotonic
with respect to his/her reported peak.
Own peak monotonicity.
For all i ∈ N, allui , ui ∈ U, and all u−i ∈ U n−1 ,
if p(ui ) ≤ p(ui ), then k∈C φi (k; ui, u−i )k ≤ k∈C φi (k; u)k.
Lemma 4. If φ satisﬁes Pareto optimality and strategy-proofness, then it isown peak monotonic.
Proof of Lemma 4. Suppose
the contrary. We have p(ui ) ≤ p(ui ) andk∈C φi (k; ui , u−i )k >k∈C φi (k; u)k. By property B, there exist αi , αi ∈ Csuch that φi (αi ; u)+φ i(αi +1; u) = 1 and φi (αi ; ui, u−i )+φi (αi +1; ui , u−i ) = 1.
Hence,
we havek∈C φi (k; u)k = φi (αi ; u)αi + φi (αi + 1; u)(αi + 1) andφi (k; ui , u−i )k = φi (αi ; ui, u−i )αi + φi (αi + 1; ui ,
u−i )(αi + 1).
k∈C 
If j∈N p(uj ) ≤X, by same-sidedness, p(ui ) ≤ k∈C φi (k; u)k. Then,

)
≤
we
have
p(u
i
k∈C φi (k; u)k = φi (αi ; u)αi + φi (αi + 1; u)(αi + 1) <








k∈C φi (k; ui , u−i )k = φi (αi ; ui, u−i )αi +φi (αi + 1; ui , u−i )(αi + 1). By single
> φi (αi ; ui , u−i )ui (αi )+peakedness, we have φi (αi ; u)ui(αi )+φi (αi +1; u)ui (αi +1)
φi (αi +1; ui , u−i )ui (αi +1). Hence, k∈C φi (k; u)ui(k) > k∈C φi (k; ui , u−i )ui (k),contradicting
strategy-proofness.
> X, then for all j ∈ N, k∈C φj (k; u)k ≤ p(uj ). There are
If j∈N p(uj )
two cases: (i) If j=i p(uj ) + p(ui ) ≥X, then, by same-sidedness, we have−i )k ≤ p(ui ). Then,k∈C φi (k; ui , uk∈C φi (k; u)k = φi (αi ; u)αi + φi (αi +1; u)(αi +1) < k∈C φi (k; ui , u−i )k = φi (αi ; ui , u−i )αi +φi (αi +1; ui , u−i )(αi +1) ≤ p(ui ) ≤ p(ui ). Single-peakedness implies that φi (αi ; u)ui(αi ) + φi (αi +






1; u)ui (αi +1) < φi (αi ; ui , u−i )ui (αi )+φi (αi +1; ui , u−i )ui (αi +1). This meansthat 
k∈C φi (k; u)ui(k) <k∈C φi (k; ui , u−i )ui (k).



p(u
)
+
p(u
)
<
X,
then
p(u
)
<
(ii) If ji(k; u)k (otherwise,iij=ik∈C φ
φ
(k;
u)k.
Since
for
all
j
∈
N,
p(u
)
≥
p(ui ) ≥ jk∈C i
k∈C φj (k; u)k, wehave X = j∈N k∈C φj (k; u)k ≤ p(ui ) + j=i p(uj ) < X).Hence, we havep(ui ) < k∈C φi (k; u)k = φi (αi ; u)αi +φi (αi +1; u)(αi +1) < k∈C φi (k; ui , u−i )k =φi (αi ; ui , u−i )αi +φi (αi +1; ui , u−i )(αi +1). Single-peakedness implies φi (αi ; u)ui (αi )+φi (αi + 1; u)ui (αi + 1) > φi (αi ; ui , u−i )ui (αi ) + φi (αi + 1; ui , u−i )ui (αi + 1).
11This implies that k∈C φi (k; u)ui(k) > k∈C φi (k; ui , u−i )ui (k).
In both cases, we obtain a contradiction to strategy-proofness.

Uncompromisingness requires that given u−i , the expected value of agent i’s
marginal distribution does not change if his/her initial peak is less (more)than his/her initial expected value and his/her new peak is equal to or less(more) than his/her initial expected value. Lemma 5 shows that Pareto
optimality and strategy-proofness imply uncompromisingness.
Uncompromisingness.
For all i ∈ N, all 
ui , ui ∈ U, and all u−i ∈n−1[p(ui ) >Uk∈C φi (k;k∈C φi (k; u)k] or 
 , if [p(ui ) <u)k and p(ui ) ≤ 


φ
(k;
u)k
and
p(u
)
≥
φ
(k;
u)k],
then
φ
(k;
u)k
=
i
k∈C i
k∈C i
k∈C i
k∈C φi (k; ui, u−i )k.
Lemma 5. If φ satisﬁes Pareto optimality and strategy-proofness, then it isuncompromising.
)<φi (k; u)k andProof of 
Lemma 5. Suppose the contrary.
Then,
[p(u
i
k∈C 

≤ k∈C φi (k; u)k]
or [p(ui ) > k∈C φi (k; u)k and p(ui ) ≥ k∈C φi (k; u)k]p(ui )and k∈C φi (k; u)k = k∈C φi (k; ui , u−i )k. Without
 loss of generality, weassume that p(ui ) < k∈C φi (k; u)k and p(ui ) ≤ k∈C φi (k; u)k. By property B, there exist αi , αi ∈ C such that φi(αi ; u) + φi (αi+ 1; u) = 1 andφi (αi ; ui , u−i ) + φi (αi + 1; ui , u−i ) =1. Hence, we have k∈C φi (k; u)k =φi (αi ; u)αi +φi (αi +1; u)(αi +1) and k∈C φi (k; ui , u−i )k = φi (αi ; ui , u−i )αi +φi (αi + 1; ui , u−i )(αi + 1).

There are two cases: (i) If k∈C φi (k; u)k < k∈C φi (k; ui, u−i )k, thenp(ui ) ≤ φi (αi ; u)αi + φi (αi + 1; u)(αi + 1) < φi (αi ; ui , u−i )αi + φi (αi +1; ui , u−i )(αi + 1). Single-peakedness implies that φi(αi ; u)ui(αi ) + φi (αi +)ui (αi )+φi (αi +1; ui , u−i )ui (αi +1).
1; u)ui (αi +1) > φi (αi ; ui , u−i This implies



that
k∈C φi (k; u)ui(k) >k∈C φi (k; ui , u−i )ui (k). (ii) If
k∈C φi (k; u)k >








k∈C φi (k; ui , u−i )k, let ui ∈ U be such that p(ui ) = p(ui ) and φi (αi ; ui , u−i )ui (αi )+






φi (αi +1; ui , u−i )ui (αi +1) > φi (αi ; u)ui (αi )+φi (αi +1; u)ui (αi +1). By property B, 
there exists αi ∈ C such that φi (αi ; ui , u−i ) + φi (αi + 1; ui , u−i ) = 1.






Hence, k∈C φi (k; ui , u−i )k = φi (αi ; ui , u−i )αi + φi (αi + 1; ui , u−i )(αi + 1).
By Lemma 4, we have k∈C φi (k; u)k = k∈C φi (k; ui , u−i )k. This implies
that αi = αi and φi (αi ; u) = φi (αi ; ui , u−i ). Hence, we have φi (αi ; u)ui (αi )+φi (αi + 1; u)ui (αi + 1) = φi (αi ; ui , u−i )ui (αi ) + φi (αi + 1; ui , u−i )ui (αi +1). Therefore, we have φi (αi ; ui , u−i )ui (αi ) +φi (αi + 1; ui , u−i )ui (αi + 1) >








This gives us thatφi + 1; ui , u−i )ui (αi + 1).
i (αi ; ui , u−i)ui (αi ) + φi (α



φ
(k;
u
,
u
)u
(k)
>
φ
(k;
u
,
u
)u
(k).
−i i
−i i
i
i
k∈C i
k∈C i
In both cases, we obtain a contradiction to strategy-proofness.
Proof of the Theorem. The randomized uniform rule obviously satisﬁes equal12probability for the best. Since it satisﬁes same-sidedness and property B,
Lemma 3 implies that it satisﬁes Pareto optimality. An argument similar to
Sprumont (1991) can be used to show strategy-proofness.
Let φ be a randomized rule satisfying strategy-proofness, Pareto optimality, and equal probability for the best. Suppose the contrary. Then,φ(u) violates (i) and (ii) of Deﬁnition 1 for some u ∈ U n . Hence, we havethere exists some(φ1(u), . . . , φn (u)) = (Φ1 (u), . . . , Φn (u)), or equivalently agenth ∈ N such that φh (u)= Φh (u). This implies
 that k∈C φh (k; u)k =

Φ
(k;
u)k
since
each
of
φ
(k;
u)k
and
k∈C h
k∈C h
k∈C Φh (k; u)k is obtained
as a convex combination of two integers by property B
and Deﬁnition 1 respectively. Without loss of generality, we assume that j∈N p(uj ) ≥ X andp(u1 ) ≤ · · · ≤ p(un ).
Suppose u = (un , . . . , un ). Note that i∈N p(ui ) = n · p(un ). By property B, for any agent i ∈ N, there exists αi ∈ C with φi (αi + 1; u) > 0
such that φi (αi ; u) + φi (αi + 1; u) = 1. From same-sidedness, we havep(un ) = p(ui ) ≥ αi + 1 > αi for all i ∈ N. Hence, the best for agent i
is αi + 1. Therefore, equal probability for the best gives us that for any
i, j ∈ N,
αi = αj , φi (αi ; u) = φj (αj ; u), and φi (αi + 1; u) = φj (αj + 1; u).
Hence, k∈C φi (k; u)k =φi (αi ; u)αi + φi (αi + 1; u)(αi + 1) = φj (αj ; u)αj +φj (αj + 1; u)(αj + 1) = k∈C φj (k; u)k for any i, j ∈ N. This implies thatk∈C φh (k; u)k = X/n from feasibility. On the other hand, the expectedvalue
 of the marginal distribution induced from the randomized uniform rule(λ−µ)(µ+1)+(1−λ+µ)µ = λ for all i ∈ N whenk∈C Φi (k; u)k is equal toi ∈ N receives p(un ) =i∈N p(ui ) > X. Whenj∈N p(uj ) = X, any agent
λ with probability1. Hence, feasibility
impliesthatk∈C Φh (k; u)k = X/n.

These contradict k∈C φh (k; u)k = k∈C Φh (k; u)k. If u = (un , . . . , un ), we
proceed as follows.
u)k, there exists m ∈ N (perStep 1. Since k∈C φh (k;u)k = k∈C Φh (k;haps 
m = h) such that  k∈C φm (k; u)k > k∈C Φm (k; u)k (otherwise, we
φ
(k;
u)k
≤
Φ
(k;
u)k
for
all
i
∈
N.
If
have
k∈C i
k∈C i
k∈C φh (k; u)k >
then we have a contradiction.
If k∈Ck∈C Φh (k;φh (k;u)k,u)k < k∈C Φh (k; u)k,
φ
(k;
u)k
+
φ
(k;
u)k
<
then
X
=
i=h
k∈C i
k∈C h
i=h
k∈C Φi (k; u)k +which is a contradiction). Samek∈C Φh (k; u)k = X from feasibility,
Let um ≡ un . Note
sidedness implies that p(um ) ≥k∈C φm (k; u)k.



p(u
)
+
p(u
)
≥
that p(um ) = p(un ) ≥ p(um ) andii=mi∈N p(ui ) ≥ m(k; um , u−m)k ≥X.
k∈C φm) implies that
 By Lemma 4, p(um ) ≥ p(um

φ
(k;
u)k.
By
Deﬁnition
1,
Φ
(k;
u
,
u
)k
=
−m
m
k∈C m
k∈C m
k∈C Φm (k; u)k.
This is because agent m obtains not his/her own peak with certainty but µ
13and µ + 1 with thecommon probabilities when his/her utility function isum (k; u)k >k∈C Φm (k; u)k. Altogether, we havem since p(um ) ≥ k∈C φ
k∈C φm (k; um , u−m )k >k∈C Φm (k; um , u−m )k.
Suppose (um , u−m ) = (un , . . . , un ). Note thati=m p(ui ) + p(um ) =n · p(un ). By property B, for all i ∈ N there exists αi ∈ C with φi (αi +that φi (αi ; um , u−m ) + φi (αi + 1; um , u−m ) = 1. Since1;um , u−m ) > 0 such
i=m p(ui ) + p(um ) ≥ X, same-sidedness implies that p(ui ) ≥ αi + 1 > αifor all i = m and p(um ) ≥ αm + 1 > αm . Hence, the best for agent i is αi + 1.
Therefore, equal probability for the best gives us that for any i, j ∈ N, αi =
αj , φi (αi ; um , u−m) = φj (αj ; um, u−m), and φi (αi + 1; um , u−m ) = φj (αj +1; um , u−m ). Hence, we have k∈C φi (k; um , u−m )k = φi (αi ; um , u−m )αi +







um , u−m)(αj +1) =φi (αi +1; um , u−m )(αi +1) = φj (αj ; um , u−m)αj +φj (αj +1;k∈C φj (k; um , u−m )k for any i, j ∈ N. This implies thatk∈C φm (k; um , u−m )k =X/n from feasibility. On the other hand, the expected
value of the marginal
distribution induced from the randomized uniform rule k∈C Φi (k; um , u−m )kλ + µ )µ = λ for all i ∈ N whenis
 equal to (λ − µ )(µ + 1) + (1 −i=m p(ui ) + p(um ) > X. Wheni=m p(ui ) + p(um ) = X, any agentthati∈ N receives p(un ) = λ with probability 1. Hence,
 feasibility implies


Φ
(k;
u
,
u
)k
=
X/n.
These
contradict
φ
(k;
u
,
u
)k
>
−m
−m
m
m
k∈C m
k∈C mk∈C Φm (k; um , u−m )k. If (um , u−m ) = (un , . . . , un ), we proceed to Step 2.
Step 2. Since um = un , equal probability for the best gives us αm =1; um , u−m) = φn (αn +
αn , φm (αm ; um , u−m) = φn (αn ; um, u−m ), and φm (αm +
1; um , u−m ). Hence, we have k∈C φm (k; um , u−m)k = k∈C φn (k; um , u−m )k.
, u−m)k = k∈C Φn (k; um , u−m)k.
Deﬁnition 1 gives
us that k∈C Φm (k; umHence, we have k∈C φi (k; um , u−m)k > k∈C Φi (k; um , u−m )k for i = m, n(perhaps
m = n), whichgives us that there exists l = m, n such that


φ
(k;
, u−m)k < k∈C Φl (k; um , u−m)k. (otherwise, we have that
k∈C l umum , u−m)k ≥k∈C φi (k; k∈C Φi (k; um , u−m)k forall i ∈ N.  Then, wehave X = i=m,n k∈C φi (k; um , u−m )k
+ i=m,n  k∈C φi(k; um , u−m )k >

Φ
(k;
u
,
u
)k+
, u−m)k = X from fea−mmi=m,nk∈C i
i=m,nk∈C Φi (k; um
(k; um , u−m )k ≤sibility, which is a contradiction). Deﬁnition 1 gives us k∈C Φlp(ul ). Let ul ≡un . Note that p(ul ) = p(un ) ≥ p(ul )and i=m,l p(ui ) +p(um )+p(ul ) ≥l) >i∈N p(ui ) ≥ X. By Lemma 5, p(uk∈C φl (k; um , u−m )kand p(ul ) > k∈C φl (k; um , u−m )k imply that k∈C φl (k; um , ul, u−m,l )k =, u−m)k. By Deﬁnition 1, we have  k∈C Φl (k; um , ul, u−m,l )k ≥
k∈C φl (k; um, u−m )k. Hence, we have thatk∈C φl (k; um, ul , u−m,l )k <
k∈C Φl (k; umk∈C Φl (k; um , ul , u−m,l )k.
Suppose (um , ul, u−m,l ) = (un , . . . , un ). Then, the same argument as the14latter part of Step 1 leads to a contradiction. If (um , ul , u−m,l ) = (un , . . . , un ),we apply Step 1 to the utility proﬁle (um , ul, u−m,l ).
At each step, we replace the utility function of an agent by un . Since n
is ﬁnite, such replacements lead to a contradiction.


15