GCOE Discussion Paper Series
Global COE Program

Human Behavior and Socioeconomic Dynamics
Discussion Paper No. 361

Notions of anonymity for object assignment:
impossibility theorems

Hikaru Kondo and Shigehiro Serizawa

February 2015

GCOE Secretariat
Graduate School of Economics
OSAKA UNIVERSITY
1-7 Machikaneyama, Toyonaka, Osaka, 560-0043, Japan

Notions of anonymity for object assignment:
impossibility theorems∗
Hikaru Kondo
Graduate School of Economics, Osaka University
1-7, Machikane-yama, Toyonaka, Osaka, 560-0043, Japan
E-mail: nge009kh@student.econ.osaka-u.ac.jp
andShigehiro Serizawa
Institute of Social and Economic Research, Osaka University
6-1, Mihogaoka, Ibaraki, 567-0047, Japan
E-mail: serizawa@iser.osaka-u.ac.jp
February 27, 2015
Abstract
We search for impartiality in the allocation of objects when monetary transfers are notpossible. Our main focus is anonymity. The standard definition requires that if agents’names are permuted, their assignments should be permuted in the same way. Since norule satisfies this definition in this model, we introduce weaker variants, “anonymity on
distinct preferences,” “pairwise-anonymity on distinct preferences,” “pairwise-anonymity
on distinct profiles,” and “independence of others’ permutations.” We show that for morethan two agents and two objects, no rule is pairwise-anonymous on distinct preferences
and Pareto-eﬃcient (Theorem 1), no rule is pairwise-anonymous on distinct preferences
and independent of others’ permutations (Theorem 2), and no rule is pairwise-anonymouson distinct profiles and strategy-proof (Theorem 3). These results suggest that introducing
randomization to object allocation problems is almost inevitable for achieving impartiality.
Keywords: impartiality, anonymity, indivisible goods
JEL Classification Numbers: C78, D71, D78∗

First, we thank William Thomson for his careful reading and detailed and useful comments. We also thank
Masaki Aoyagi, Agustin Bonifacio, Patrick Harless, Kazuhiko Hashimoto, Morimitsu Kurino, Noriaki Matsushima, Anup Pramanik, James Schummer, Tayfun Sonmez, Wataru Tamura, Masashi Tanaka, Utku Unver,
Jun Wako, and participants at Frontiers of Market Design, Osaka University Applied Microeconomic Theory
Workshop, 11th Meeting of Society for Social Choice and Welfare and Osaka-Rochester Theory Workshop for
their helpful comments. We are especially grateful to Shuhei Morimoto and Koji Takamiya for detailed comments and helpful suggestions. This work is supported by Grant-in-Aid for JSPS Fellows. All remaining errors
are our own.

1

Introduction

We consider the problem of assigning a number of indivisible goods, called “objects,” to an
equal number of agents when monetary transfers are not possible.1 Examples include a manager
assigning tasks to workers, or a government assigning housing units to low-income applicants.
Each agent has a strict preference2 over objects and receives exactly one object. A rule is afunction from a class of preference profiles to the set of feasible allocations that assigns objects
to agents.
In the context of such problems, people are often sensitive to impartiality of rules. Thus, it
is important to achieve impartiality. One way to achieve impartiality is using randomization,such as with the “random priority” (RP) rule. 3 However, the following question arises: “Israndomization necessary for achieving impartiality?” In other words, “Are there ways to achieve
impartiality other than randomization?” Motivated by this question, we explore the possibilitiesof achieving impartiality in a deterministic environment.
“Anonymity” is a requirement commonly used to embody impartiality. Anonymity statesthat allocations are independent of agents’ names. Its standard mathematical formulation is
as follows: if agents’ names are permuted, their assignments should be permuted in the sameway. We refer to this definition as “standard anonymity.” Here, standard anonymity implies thatwhen several agents have the same attribute (preference), they are all assigned the same object,which is impossible in our model. However, the following example suggests that impartiality
may be achieved by weakening the standard anonymity requirement.
Example 1: There are two objects, a and b, and two agents, 1 and 2. Consider the following
rule. If the two agents prefer diﬀerent objects, each receives the one he prefers. If both prefera to b, agents 1 and 2 receive a and b, respectively; if both prefer b to a, then agents 1 and 2
receive a and b, respectively.
This rule does not satisfy standard anonymity, because the allocations depend on the agents’names when both agents have the same preferences. However, it still appears to be impartial.
At the two profiles in which both agents have distinct preferences, both obtain their favorite
objects. At the other two profiles, one of the agents must be chosen as the recipient of his
favorite object. In one such profile, agent 1 is chosen, and in the other, agent 2 is chosen.
Therefore, each agent receives his favorite in an equal number of preference profiles. Although
the rule is not impartial at each profile, it seems impartial if we look at the collection of profiles.
Thus, it may be called “impartial across profiles.”4
Based on this observation, we propose several notions of anonymity. “Anonymity on distinct preferences” imposes the same requirement as standard anonymity, except that we do not
permute agents who have the same preferences. “Pairwise-anonymity on distinct preferences”
requires that when two agents have distinct preferences and their preferences are transposed,
their assignments should be transposed and nothing is required of the other agents’ assignments.
1

The formal study of object allocation problems originates in Shapley and Scarf (1974).
In practice, people may be indiﬀerent among several objects. In this model, however, allowing indiﬀerence
makes it diﬃcult to construct desirable rules (Ehlers (2002)).
3
The RP rule works as follows: For each agent priority, each agent receives his favorite object among theremaining objects. If there are n agents, there are n! possible agent priorities. Then, compute the average
probability of all allocations determined by each priority.
4
Thomson (2012) makes the same point.
2

1

“Pairwise-anonymity on distinct profiles” imposes the same requirement as pairwise-anonymity
on distinct preferences, except that we impose it only on profiles in which all agents have distinct preferences. Again, nothing is required of other agents’ assignments. “Independence ofothers’ permutations” requires that if, for example, the preferences of agents other than agent iare permuted but agent i’s preference remains constant, agent i’s assignment should not change.
Anonymity on distinct preferences is stronger than both pairwise-anonymity on distinct preferences and independence of others’ permutations, and pairwise-anonymity on distinct preferences
is stronger than pairwise-anonymity on distinct profiles.
The rule in Example 1 has other interesting properties. First, it is Pareto-eﬃcient: for eachpreference profile, it chooses an allocation such that there is no other allocation at which eachagent is at least as well oﬀ and at least one agent is better oﬀ. Second, it is strategy-proof:
for each preference profile, truth-telling is a weakly dominant strategy in the direct revelation
game associated with the rule.
This rule shows the compatibility of anonymity on distinct preferences, Pareto-eﬃciency,
and strategy-proofness for two agents and two objects. Naturally, this generates questions
about the general case, which is our focus. Unfortunately, our answers are negative. We showthat for more than two agents and two objects, no rule is pairwise-anonymous on distinct
preferences and Pareto-eﬃcient (Theorem 1). Furthermore, no rule is pairwise-anonymous on
distinct preferences and independent of others’ permutations (Theorem 2). Finally, no rule ispairwise-anonymous on distinct profiles and strategy-proof (Theorem 3). These results suggestthat to achieve impartiality, introducing randomization into object allocation problems is almost inevitable. In this sense, these results motivate the research on probabilistic assignment
problems.
Let us discuss the related literature concerning anonymity for discrete resource allocation
problems. Consider the case in which not receiving an object is an option, termed “null object.”
In such a case, we can construct standard anonymous rules by sacrificing Pareto-eﬃciency(Kesten and Yazici (2012)). 5 In their study, the null object is not necessarily ranked worst.6
Moreover, rules satisfying standard anonymity can exist in the model without the null object. If
we assume that agents initially own the objects, there are standard anonymous rules (Miyagawa(2002)). Miyagawa shows that the core and the no-trade rules are characterized by standard
anonymity and some other properties.7 Then, anonymity in these models is not as demanding
as that in our model. In the model of Kesten and Yazici (2012), the rule that assigns the null
object to all agents at all profiles is obviously standard anonymous. In the standard object
exchange model, standard anonymous rules can also be defined.
No-envy and equal treatment of equals are also well-known fairness requirements. No-envy
says that no agent should prefer someone else’s assignment to his own, and equal treatment ofequals says that agents with the same preferences should be assigned objects between which
they are indiﬀerent. No rule satisfies standard definitions of these axioms in our model. Then,in the hope of achieving fairness, probabilistic rules are considered. However, impossibility
results for the probabilistic assignment concerning fairness may still exist. If agents have avon Neumann—Morgenstern (vNM) utility function, no rule satisfies equal treatment of equals
5

Although their main fairness requirement is no-envy, some of their results also hold if this requirement is
replaced by anonymity.
6
The null object may play an important role as an option. See Kesten and Kurino (2013).
7
The core can be characterized even without anonymity. See, for example, Ma (1994) or Takamiya (2001).

2

together with (ex-ante) Pareto-eﬃciency and strategy-proofness (Zhou (1990)). Instead of thevNM utility function, we can introduce the notion of stochastic dominance (sd) into probabilistic
assignment to compare lotteries. Even in this setting, no rule satisfies equal treatment of equals,(sd) Pareto-eﬃciency and (sd) strategy-proofness (Bogomolnaia and Moulin (2001)). Because(sd) no-envy is stronger than equal treatment of equals, (sd) no-envy is also incompatible withthe other two requirements. Although we find such negative results, we may find better results
if we weaken some properties. For example, the RP rule is anonymous together with (sd)strategy-proof and (ex-post) Pareto-eﬃcient.
When fairness requirements are dropped, rules satisfying other desirable properties are
identified. They use hierarchies of agents. See, for example, Svensson (1999) and Papai (2000a)for the single-unit demand case; Papai (2000b) and Hatfield (2009) for the multi-unit demandcase; and Abdulkadiroglu and Sonmez (1999) for the case in which some agents initially own
objects.
The remainder of this paper is organized as follows: In Section 2, we provide formal definitions of the model and basic requirements. In Section 3, we define three of our new notions andshow some results concerning them. In Section 4, we define “pairwise-anonymity on distinct
profiles” and establish possibility and impossibility results. In Section 5, we show the independence of the axioms of the theorems. In Section 6, we provide some concluding remarks.

2

Model and definitions

We denote the set of agents by N = {1, 2, · · ·, n} (n ≥ 2) and the set of objects by K, where|K| = n. 8 Each agent i ∈ N has a complete, transitive, and antisymmetric preference Ri
over K.9 We denote the set of all preferences by R. We denote the strict preference associatedwith Ri by Pi , that is, a Pi b if and only if a Ri b and a 6= b. We denote the top-ranked object for
Ri by t(Ri ) and the second-ranked object by st(Ri ). We represent a preference Ri as follows:
Ri : a b c d · ··where a, b, c, d, · · · ∈ K. This means that a = t(Ri ), b = st(Ri ), and so on. Given Ri ∈ R anda ∈ K, we denote the lower contour set of Ri at a as L(Ri , a) = {k ∈ K|a Ri k}.
For each i ∈ N, xi is the object assigned to agent i. A feasible allocation is a list of objects
x = (xi )i∈N such that for each pair {i, j} ⊂ N, xi 6= xj . Let X be the set of all feasible
allocations. Let R = (Ri )i∈N . For each pair {i, j} ⊂ N, R−i denotes a preference profile for
N\{i}, and R−ij denotes a preference profile for N\{i, j}. We denote the set of all preference
profiles for N by RN .
An (assignment) rule f is a function from RN to X. For each pair {i, j} ⊂ N and eachR ∈ RN , we denote the object assigned to i at f (R) as fi (R), and (fi (R), fj (R)) as fi,j (R).
Next, we introduce two properties of rules. Let f be a rule and R ∈ RN . First, for eachpreference profile, a rule should choose an allocation such that there is no allocation at which
each agent is as well oﬀ and at least one agent is better oﬀ. An allocation x̂ ∈ X Paretodominates x at R if for each i ∈ N, x̂i Ri xi and for some j ∈ N, x̂j Pj xj .
8

Most of our results hold even if |N | < |K|.
A preference Ri is complete if for each a, b ∈ K, a Ri b or b Ri a. Ri is transitive if for each a, b, c ∈ K,a Ri b
and b Ri c imply a Ri c. Ri is antisymmetric if for each a, b ∈ K, a Ri b and b Ri a imply a = b.
93

Pareto-eﬃciency: For each R ∈ RN , no allocation Pareto-dominates f (R) at R.
Next, for each preference profile, truth-telling should be a weakly dominant strategy foreach agent in the direct revelation game associated with the rule.
Strategy-proofness: For each R ∈ RN , each i ∈ N and each R̂i ∈ R, fi (R) Ri fi (R̂i , R−i ).

3Several notions of anonymity

The principle of anonymity is that allocations should be determined independently of the agents’names. In this section, we introduce several variants. Given a profile R and a permutation
π : N → N, let Rπ ≡ (Rπ(i) )i∈N be the profile obtained by permuting the agents’ names
according to π. Let Πdist (R) ≡ {π : ∀i ∈ N, π(i) = j 6= i ⇒ Ri 6= Rj } denote the permutations
such that only agents with distinct preferences are permuted. The next requirement is that
if agents are permuted according to π ∈ Πdist (R), the assignments should be permuted in thesame way.
Anonymity on distinct preferences: For each R ∈ RN , each π ∈ Πdist (R), and each i ∈ N,
fi (Rπ ) = fπ(i) (R).
For most models, anonymity implies the axiom called equal treatment of equals.10 Here,however, anonymity on distinct preferences is logically independent of equal treatment of equals.
Anonymity on distinct preferences also requires that if a permutation does not aﬀect someagents, their assignments should not change. Example 1 in Section 1 satisfies anonymity on
distinct preferences in addition to Pareto-eﬃciency and strategy-proofness. That example showsthat our impossibility results are not trivial.
We define two other anonymity axioms. If two agents have distinct preferences and theirpreferences are transposed, their assignments should also be transposed.
Pairwise-anonymity on distinct preferences: For each R ∈ RN and each pair {i, j} ⊂ N,
Ri 6= Rj implies fi (Ri , Rj , R−ij ) = fj (R̂i , R̂j , R−ij ) and fj (Ri , Rj , R−ij ) = fi (R̂i , R̂j , R−ij ),where R̂i = Rj and R̂j = Ri .
Anonymity on distinct preferences implies pairwise-anonymity on distinct preferences. Pairwiseanonymity on distinct preferences allows the existence of agents whose preferences are not
permuted but whose assignments change.
Given i ∈ N, let Πi denote the set of permutations such that only agents other than i are
permuted. That is, π ∈ Πi implies π(i) = i. The following condition states that agent i’s
assignment should not change even if others’ names are permuted.
Independence of others’ permutations: For each R ∈ RN , each i ∈ N, and each π ∈ Πi ,fi (R) = fi (Rπ ).
Anonymity on distinct preferences also implies independence of others’ permutations. Whenn ≤ 3, any rule is independent of others’ permutations. We turn to our impossibility results.
Theorem 1: Let n ≥ 3. Then, no rule is pairwise-anonymous on distinct preferences andPareto-eﬃcient.
Proof: Let f be a rule satisfying the axioms of the theorem. Let R ∈ RN be such that10

Equal treatment of equals: For each R ∈ RN and each pair {i, j} ⊂ N such that Ri = Rj , fi (R) = fj (R).

4

(a) R1 = R2 ,(b) for each i ∈ N \{1, 2}, t(Ri ) 6= t(R1 ) and t(Ri ) 6= st(R1 ), and(c) for each i, j ∈ N\{1, 2}, t(Ri ) 6= t(Rj ).
Step 1:f (R) = (t(R1 ), st(R2 ), t(R3 ), t(R4 ), · · ·, t(Rn )) ≡ x1 or
f (R) = (st(R1 ), t(R2 ), t(R3 ), t(R4 ), · · ·, t(Rn )) ≡ x2 .

(1)
(2)

By conditions (a), (b), and (c), x1 and x2 are both feasible. Let x ∈ X\{x1 , x2 }. We show thatx is Pareto-dominated by x1 or x2 . Because x 6= x1 and x 6= x2 , there are two cases:
Case 1: There is i ∈ {1, 2} such that st(Ri ) Pi xi
If i = 1, x21 = st(R1 ) P1 x1 , and for each j ∈ N\{1}, x2j = t(Rj ) Rj xj . Thismeans that x2 Pareto-dominates x. If i = 2, x1 Pareto-dominates x.
Case 2: There is j ∈ N\{1, 2} such that xj 6= t(Rj ).
By condition (a), x1 6= t(R1 ) or x2 6= t(R2 ). If x1 6= t(R1 ), x2 Pareto-dominates
x. If x2 6= t(R2 ), x1 Pareto-dominates x.
Step 2: We derive a contradiction. By Step 1, we may assume that f (R) = x1 , because thecase f (R) = x2 can be treated symmetrically. Let f1 (R) = t(R1 ) ≡ a, f2 (R) = st(R2 ) ≡ b,
and f3 (R) = t(R3 ) ≡ c. Let R2 ≡ (R1 , R3 , R2 , R4 , · · ·, Rn ) be a profile obtained from R bytransposing the preferences of agents 2 and 3. By pairwise-anonymity on distinct preferencesand (b), f2 (R2 ) = f3 (R) = c and f3 (R2 ) = f2 (R) = b. Moreover, by Pareto-eﬃciency, for eachi ∈ N\{2, 3}, fi (R2 ) = t(Ri ). Thus, f (R2 ) = (a, c, b, t(R42 ), · · ·, t(Rn2 )). Similarly, we defineR3 ≡ (R22 , R12 , R32 , R42 , · · ·, Rn2 ) from R2 by transposing the preferences of agents 1 and 2, andwe find that f (R3 ) = (c, a, b, t(R43 ), · · ·, t(Rn3 )). Now, let R4 ≡ (R33 , R23 , R13 , R43 , · · ·, Rn3 ). By
pairwise-anonymity on distinct preferences, f1 (R4 ) = f3 (R3 ) = b. However, R1 = R2 implies
R4 = R, and thus, f1 (R4 ) = f1 (R) = a 6= b. This is a contradiction.
Q.E.D.
Theorem 2: Let n ≥ 3. Then, no rule is pairwise-anonymous on distinct preferences andindependent of others’ permutations.11
Proof: Let f be a rule satisfying the axioms of the theorem. We derive a contradiction. Let
R ∈ RN be such that R1 = R2 6= R3 , R2 ≡ (R1 , R3 , R2 , R4 , · · ·, Rn ), R3 ≡ (R3 , R1 , R2 , R4 , · ··, Rn ), and R4 ≡ (R2 , R1 , R3 , R4 , · · ·, Rn ). Then, by pairwise-anonymity on distinct preferences
and independence of others’ permutations,f (R2 ) = (f1 (R), f3 (R), f2 (R), f4 (R), · · ·, fn (R)),
f (R3 ) = (f3 (R), f1 (R), f2 (R), f4 (R), · · ·, fn (R)), andf (R4 ) = (f2 (R), f1 (R), f3 (R), f4 (R), · · ·, fn (R)).

(3)
(4)
(5)

However, by R1 = R2 ,11

To be exact, if n = 3, any rule satisfies independence of others’ permutations so that no rule is pairwiseanonymous on distinct preferences.

5

f (R4 ) = f (R) = (f1 (R), f2 (R), f3 (R), f4 (R), · · ·, fn (R)). This is a contradiction. Q.E.D.
Because anonymity on distinct preferences implies pairwise-anonymity on distinct preferences and independence of others’ permutations, Corollary 1 follows.
Corollary 1: Let n ≥ 3. Then, no rule is anonymous on distinct preferences.

4

Pairwise-anonymity on distinct profiles

As shown, pairwise-anonymity on distinct preferences is too strong in the model. Therefore, inthis section we introduce a weaker condition. Let RN∗ ≡ {R0 ∈ RN | ∀i, j ∈ N, i 6= j ⇒ Ri0 6=
Rj0 } denote the set of preference profiles in which no two agents have the same preferences. We
call such profiles “distinct profiles.” The next requirement is weaker than pairwise-anonymity
on distinct preferences: we impose the same condition only on distinct profiles.
Pairwise-anonymity on distinct profiles: For each R ∈ RN∗ and each pair {i, j} ⊂ N,
fi (Ri , Rj , R−ij ) = fj (R̂i , R̂j , R−ij ) and fj (Ri , Rj , R−ij ) = fi (R̂i , R̂j , R−ij ), where R̂i = Rj andR̂j = Ri .
Pairwise-anonymity on distinct preferences implies pairwise-anonymity on distinct profiles.
Here, we can also consider the weaker notion of no-envy by imposing the requirement only on
RN∗ . 12 However, we do not introduce such a condition, because no rule satisfies it in ourmodel.
Pairwise-anonymity on distinct profiles is logically related to other known conditions. The
first condition states that there should not be an agent who is always assigned his most preferredobject.
Non-dictatorship: There is no agent i ∈ N such that for each R ∈ RN , fi (R) = t(Ri ).
The next condition states that each allocation should be chosen for some preference profile.
Respect of consumer sovereignty: For each x ∈ X, there exists R ∈ RN such that f (R) =x.
There are rules that are non-dictatorial, Pareto-eﬃcient, and strategy-proof (see, e.g., Svensson (1999) or Papai (2000)). We establish two facts.
Fact 1: Let n ≥ 3. If a rule f is pairwise-anonymous on distinct profiles, it is non-dictatorial.
Proof: Suppose not. Then, there is i ∈ N such that for each R ∈ RN , fi (R) = t(Ri ). Let
R ∈ RN∗ be such that there is j ∈ N such that j 6= i and t(Rj ) = t(Ri ). Here, t(Rj ) 6= fj (R).
Then, by pairwise-anonymity on distinct profiles, fi (R̂i , R̂j , R−ij ) = fj (R) 6= t(R̂i ), whereR̂i = Rj and R̂j = Ri . However, fi (R̂i , R̂j , andR−ij ) = t(R̂i ), because i is the dictator. This isa contradiction.
Q.E.D.
Fact 2: If a rule f is pairwise-anonymous on distinct profiles and independent of others’ permutations, it respects consumer sovereignty.
Proof: Let x ∈ X. We show that there is R ∈ RN such that f (R) = x. Let R0 ∈ RN∗ .
Using pairwise-anonymity on distinct profiles and independence of others’ permutations, wefind R as follows:
12

No-envy: For each pair {i, j} ⊂ N and each R ∈ RN , fi (R) Ri fj (R).

6

Step 1: Constructing R1 ∈ RN∗ such that f1 (R1 ) = x1 . Let j ∈ N be such that fj (R0 ) =x1 . If j = 1, let R1 ≡ R0 and proceed to the next step. Let j 6= 1 and let R1 ≡ (Rj , R2 , · ··, Rj−1 , R1 , Rj+1 , · · ·, Rn ) be obtained from R0 by transposing the preferences of agents 1 and j.
Then, by pairwise-anonymity on distinct profiles and independence of others’ permutations,f (R1 ) = (x1 , f2 (R1 ), · · ·, fj−1 (R1 ), f1 (R1 ), fj+1 (R1 ), · · ·, fn (R1 )).

Let j 0 ∈ N be such
Step 2: Constructing R2 ∈ RN∗ such that f1,2 (R2 ) = (x1 , x2 ).
that fj 0 (R1 ) = x2 . If j 0 = 2, let R2 ≡ R1 and proceed to the next step. Let j 0 6= 2 and let
R2 ≡ (R11 , Rj10 , · · ·, Rj10 −1 , R21 , Rj10 +1 , · · ·, Rn1 ) be obtained by transposing Rj10 and R21 . Then, by
pairwise-anonymity on distinct profiles and independence of others’ permutations,f (R2 ) = (x1 , x2 , f3 (R2 ), · · ·, fj 0 −1 (R2 ), f2 (R2 ), fj 0 +1 (R2 ), · · ·, fn (R2 )).
Q.E.D.
Iterating, we obtain Rn ∈ R such that f (Rn ) = (x1 , x2 , · · ·, xn ) = x.
We have already seen that no rule is both pairwise-anonymous on distinct preferences andPareto-eﬃcient. However, there are rules that are pairwise-anonymous on distinct profiles andPareto-eﬃcient. We define a family of such rules next. Preference priorities and agent priorities
are used in the definition. The agent whose preference has the highest priority obtains his mostpreferred object. Then, the agent whose preference has the second-highest priority obtains his
most-preferred object among the remaining objects, and so on. If, at some step, several agents
have the same preferences, we use agent priorities to break ties. The agent with the highest
agent priority among them obtains his most-preferred object among the remaining objects,
the agent with the second-highest agent priority obtains his most-preferred object among theremaining objects, and so on.
Preference-then-Agent Sequential Priority Rule, SP  : Let p : N → N be a one-to-one
and onto function that provides agent priorities, and let q : R → {1, 2, · · ·, n!} be a one-to-one
and onto function that provides preference priorities. For Ri ∈ R, let I(Ri ) ≡ {j ∈ N|Rj = Ri }.
Given a profile R, the allocation SP p,q (R) is determined as follows.
Step 1: Let i ∈ argminj∈N q(Rj ). If |I(Ri )| = 1, agent i obtains his most-preferred object
in K. If |I(Ri )| ≥ 2, agent i0 =argminj∈I(Ri ) p(j) obtains his most-preferred object in K, agent
i00 = argminj∈I(Ri )\{i0 } p(j) obtains his most-preferred object in K\{SPip,q
0 (R)}, and so on.
Step 2: Let l ∈ argminj∈N\I(Ri ) q(Rj ). We use the same procedure as in Step 1. We continue
until no agents remain.
The next example illustrates the definition.
Example 2: Let n = 3 and let K = {a, b, c}. Let p(1) = 2, p(2) = 1, p(3) = 3, q(a R b Rc) = 1, and q(a R c R b) = 2, q(b R a R c) = 3, q(b R c R a) = 4, q(c R a R b) = 5,q(c R b R a) = 6. Consider the following preference profiles:
R1
R11 : a c b
R21 : a b c
R31 : b a c
Final priority: 2 → 1 → 3

q
2
1
3

R2
R12 : a b c
R22 : a c b
R32 : b a c
1→2→3

q
1
2
3

R3
R13 : a b c
R23 : a b c
R33 : b a c
2→1→3

qp
12
11
33

At R1 , all agents have distinct preferences, so only the preference priority q is required todetermine the allocation. The induced final priority sequence is agent 2, agent 1, and agent 3,
7and the allocation is SP p,q (R1 ) = (c, a, b). Similarly, SP p,q (R2 ) = (a, c, b). At R3 , agents 1 and2 have the same preferences, and thus, priority is determined by both q and agent priority levelp. According to q, agents 1 and 2 have higher priority than agent 3. According to p, agent 2
has higher priority than agent 1. Therefore, the final priority sequence is agent 2, agent 1, andagent 3, and the allocation is SP p,q (R3 ) = (b, a, c).
In this example, agent 2 can benefit from misrepresenting his preference at R2 . There aremany types of manipulations that work under this rule. We can infer from this observationthat pairwise-anonymity on distinct profiles seems incompatible with strategy-proofness. As weshow next, these two properties are incompatible.
Theorem 3: Let n ≥ 3. Then, no rule is pairwise-anonymous on distinct profiles and strategyproof.
Proof: Let f be a rule satisfying the axioms of the theorem. Let R ∈ RN be such that R1 = R2
and for each pair {i, j} ⊂ N\{1}, Ri 6= Rj and t(Ri ) 6= t(Rj ). Without loss of generality, assume that f2 (R) P1 f1 (R). Then, there is R0 ∈ R such that L(R1 , f1 (R)) Ã L(R0 , f2 (R))
and R0 6= Ri for each i ∈ N\{1}. Let R0 ≡ (R0 , R2 , R−12 ) and R00 ≡ (R1 , R0 , R−12 ).
By strategy-proofness, f1 (R0 ) ∈ L(R1 , f1 (R)). Thus, L(R1 , f1 (R)) Ã L(R0 , f2 (R)) implies
f2 (R) P0 f1 (R0 ). By pairwise-anonymity distinct profiles and R1 = R2 , f2 (R00 ) = f1 (R0 ). There00
fore, f2 (R2 , R−2) P200 f2 (R00 ). This contradicts strategy-proofness.
Q.E.D.

5

Independence of the axioms

In this section, we demonstrate that no axiom in the theorems is redundant. Because we havealready provided a rule satisfying pairwise-anonymity on distinct profiles and Pareto-eﬃciency,
we next provide one rule satisfying pairwise-anonymity on distinct preferences, one satisfying
independence of others’ permutations, and one satisfying strategy-proofness.
(i) Pairwise-anonymity on distinct preferences.
Proposition 1 states that there is norule that is pairwise-anonymous on distinct preferences when the number of agents is three,four, or five. In general, we have not been able to determine whether a rule is that is pairwiseanonymous on distinct preferences.
Proposition 1: Let 3 ≤ n ≤ 5. Then, no rule is pairwise-anonymous on distinct preferences.
Proof: (a) n = 3
Pairwise-anonymity on distinct preferences implies independence ofother’s permutations. Thus, by Theorem 2, there is no rule that is pairwise-anonymous on
distinct preferences.
(b) n = 4
Let f be pairwise-anonymous on distinct preferences. Let R1 ∈ RN be such1
that R11 = R21 6= R31 6= R41 . We denote f (R1 ) = (a, b, c, d). Let R2 ≡ (R31 , R21 , R−23
) be obtained
1from R by transposing the preferences of agents 2 and 3. Then, by pairwise-anonymity on
1
distinct preferences, f2,3 (R2 ) = (c, b). Let R3 ≡ (R41 , R21 , R−24). Then, by pairwise-anonymity
3
on distinct preferences, f2,4 (R ) = (d, b).
2Here, f1 (R2 ) ∈ {a, d}. Suppose that f1 (R2 ) = a. Let R4 ≡ (R22 , R12 , R−12
) and R5 ≡1
(R31 , R11 , R−13). Because R11 = R21 , R4 = R5 . However, by pairwise-anonymity on distinct
preferences, f2 (R4 ) = a and f3 (R5 ) = a. This contradicts feasibility. Thus, f1 (R2 ) = d, andthus, f (R2 ) = (d, c, b, a).
2
3
By a similar argument, f (R3 ) = (c, d, a, b). Let R6 ≡ (R42 , R32 , R−34
) and R7 ≡ (R33 , R23 , R−23
).
1
1
6
7
6
Because R1 = R2 , R = R . However, by pairwise-anonymity on distinct preferences, f3 (R ) =8

a and f2 (R7 ) = a. This contradicts feasibility.
(c) n = 5
Let f be pairwise-anonymous on distinct preferences. Let R ∈ RN be suchthat R1 = R2 = R3 = R4 6= R5 . We denote f (R) ≡ (a, b, c, d, e). Let R1 ≡ (R5 , R2 , R3 , R4 , R1 ),R2 ≡ (R1 , R5 , R3 , R4 , R2 ), R3 ≡ (R1 , R2 , R5 , R4 , R3 ), and R4 ≡ (R1 , R2 , R3 , R5 , R4 ) be obtainedby transposing two preferences of R. Then, by pairwise-anonymity on distinct preferences,
f1,5 (R1 ) = (e, a), f2,5 (R2 ) = (e, b), f3,5 (R3 ) = (e, c), and f4,5 (R4 ) = (e, d).
Suppose that f2 (R1 ) = b. Then, by pairwise-anonymity on distinct preferences, f1 (R2 ) = b
because R2 can be obtained from R1 by transposing R11 and R21 . However, f5 (R2 ) = b, which
is a contradiction. Therefore, f2 (R1 ) 6= b. Similarly f3 (R1 ) 6= c and f4 (R1 ) 6= d. Thus,
f (R1 ) = (e, c, d, b, a) or (e, d, b, c, a).
Let f (R1 ) = (e, c, d, b, a). Then, by pairwise-anonymity on distinct preferences, f1 (R2 ) = c
because R2 can be obtained from R1 by transposing R11 and R21 . Similarly, f1 (R3 ) = d. At R2 ,either agents 3 or 4 must be assigned d. Assume that f3 (R2 ) = d. Then, pairwise-anonymity on
distinct preferences implies f2 (R3 ) = d. However, we have already obtained that f1 (R3 ) = d.
This is a contradiction. We have the same contradiction even if agent 4 is assigned d at R,
and this means that if f (R1 ) = (e, c, d, b, a), a contradiction occurs. Similarly, we can derive acontradiction even if f (R1 ) = (e, d, b, c, a).
Q.E.D.
(ii) Independence of others’ permutations.
We show an example of a rule that is
independent of others’ permutations but not pairwise-anonymous on distinct preferences. Let
q : R → {1, 2, · · ·, n!} be a one-to-one and onto function that gives preference priorities. The
rule is as follows: If all agents have distinct preferences, each agent obtains his most-preferredobject according to his preference priority q. This process is the same as that of the Preferencethen-Agent sequential priority rule, except that we do not use agent priority p. If several agents
have the same preferences, we use the constant rule, meaning that all allocations are the samefor each such profile. Formally,(
constant(R) if ∃i, j ∈ N such that Ri = Rj
f (R) =SP q (R)otherwise(iii) Strategy-proofness.
The rule defined next is strategy-proof but not pairwise-anonymouson distinct profiles.13
Sequential priority rule: Let π : N → N. For each R ∈ RN , agent π(1) obtains his most
preferred object in K, agent π(2) obtains his most preferred object in K\{fπ(1) (R)}, agent π(3)obtains his most preferred object in K\{fπ(1) (R), fπ(2) (R)}, and so on.

6

Summary and concluding remarks

In this section, we provide a summary table of our properties and some remarks on our results.
In the following table, Eﬀ, STP, and IOP respectively indicate Pareto-eﬃciency, strategyproofness, and independence of others’ permutations. “+” means that the two properties arecompatible, and “−” means that they are incompatible. “?” means that it is unknown to us
whether the two properties are compatible.
13

For example, consider the case in which agent 1 has highest priority, agent 2 has the lowest priority, anda P1 b P1 · · · and a P2 c P2 · · ·, where a, b, c ∈ K.

9

Anonymity on distinct preferences
Pairwise-anonymity on distinct preferences
Pairwise-anonymity on distinct profiles

existence Eﬀ
−
−
?
−
+
+

STP
−
−
−

IOP
−
−
+

(i) Introducing the null object.
In our model, the number n of agents and the number
m of objects are equal. If n < m, all of our results still hold except for Fact 2.14
If n > m, some agents inevitably receive a “null object,” which means that they obtainnothing. In this case, there are rules satisfying standard anonymity and strategy-proofness. A
trivial example of such rules is constant rules in which all agents receive the null object. In thecase where preferences ranking the null object higher than some real objects are admissible,
Kesten and Yazici (2012) analyze nontrivial rules satisfying standard anonymity and strategyproofness.
The case that has not yet been analyzed is that where n > m and all real objects aredesirable, that is, all real objects are preferred to the null object. We discuss the diﬃculty ofthis case.
First, if n is substantially greater than m, our notions of anonymity are weaker or evencompletely meaningless. For example, assume that n = 7 and m = 3. Then, an agent’s
preference is chosen among six preferences so that in each preference profile, at least two agents
have the same preferences. It follows that pairwise-anonymity of distinct profiles requires
nothing. Although the other notions of anonymity require something, the number of admissible
permutations decreases so that these notions will be weaken.
There are other diﬃculties in characterizing rules satisfying anonymity requirements. For
example, if n = 7 and m = 3, there are four agents who must obtain the null object. Recall thatthe key point of our proofs of characterizations are that two agents with the same preferencesmust receive distinct objects. This point fails to hold, so our proofs do not work.
Owing to these diﬃculties, we leave the case where n > m and all real objects are desirable
for future research.
(ii) Characterization of pairwise-anonymous on distinct profiles and Pareto-eﬃcient rules.
As we demonstrated in Section 4, there are rules satisfying pairwise-anonymity on distinct
profiles and Pareto-eﬃciency. They are the Preference-then-Agent sequential priority rules.
Other rules satisfying the two properties exist. Consider the following example:(
SP p,q (R) if ∃i, j ∈ N such that Ri = Rj
f (R) =SP q (R)otherwise
where SP q is a simple sequential priority rule with agent priority q. This rule also satisfies
both pairwise-anonymity on distinct profiles and Pareto-eﬃciency. The answer to which classof rules satisfies these two conditions remains unknown.
(iii) The strongest condition of anonymity.
In this paper, we proposed several variantsof the anonymity condition. For each variant, a class of preference profiles is specified, and we
14

If n < m, choose n objects among m, and then apply the rule for the example in Section 5 (ii) to the nobjects. This rule satisfies pairwise-anonymous on distinct profiles and independent of others’ permutations,but does not respect consumer sovereignty.

10permute preferences of profiles only if the profile belongs to the class. Note that the smaller the
specified class of preference profiles is, the weaker the corresponding anonymity condition is.
For example, consider preference profiles such that for each pair {i, j} ⊂ N, t(Ri ) 6= t(Rj ), thatis, it is possible for each agent to receive his favorite object. We call such profiles “no-conflictprofiles.” The requirement of anonymity on only no-conflict profiles is suﬃciently weak that it
is compatible with both Pareto-eﬃciency and strategy-proofness. Determining the conditions
where the strongest variant of anonymity is compatible with these two properties is of interest.
When n = 3, anonymity requirement on the class of no-conflict profiles is the strongest
variant compatible with the two properties. That is, if we impose anonymity requirement onsome profiles in addition to no-conflict profiles, no rule satisfies this anonymity condition alongwith Pareto-eﬃciency and strategy-proofness. We sketch the proof of this claim.
Let R1 , R2 and R3 ∈ RN be as follows:
R1
R11 : a b c
R21 : a b c
R31 : b a c

R2
R12 : a c b
R22 : a b c
R32 : b a c

R3
R13 : a b c
R23 : a c b
R33 : b a cwhere R2 and R3 are the only profiles to which the anonymity condition can be applicable
other than no-conflict profiles. By Pareto-eﬃciency, either agents 1 or 2 receives a at R1 .
Without loss of generality, let f1 (R1 ) = b or c and f2 (R1 ) = a. Then, by strategy-proofness,
f1 (R2 ) = b or c. Furthermore, by the anonymity condition, f2 (R3 ) = b or c. However, thiscontradicts strategy-proofness because f2 (R1 ) R23 f2 (R3 ). We can derive the same contradiction
using similar argument in the other cases.
Determining which conditions are the strongest variant of anonymity together with Paretoeﬃciency and strategy-proofness when n > 3 remains unanswered.

References
Abdulkadiroglu, A and Sonmez, T (1999) House allocation with existing tenants, Journal of
Economic Theory, Volume 88, Issue 2, 233—260.
Bogomolnaia, A and Moulin, H (2001) A new solution to the random assignment problem,
Journal of Economic Theory, Volume 100, Issue 2, 295—328.
Ehlers, L (2002) Coalitional strategy-proof house allocation, Journal of Economic Theory,
Volume 105, Issue 2, 298—317.
Hatfield, J W (2009) Strategy-proof, eﬃcient, and nonbossy quota allocations, Social Choiceand Welfare, Volume 33, Issue 3, 505—515.
Kesten, O and Kurino, M (2013) Do outside options matter in school choice? A new perspective on the eﬃciency vs. strategy-proofness trade-oﬀ, mimeo.
Kesten, O and Yazici, A (2012) The Pareto dominant strategy-proof and equitable rule forproblems with indivisible goods, Economic Theory, Volume 50, Number 2, 463—488.
11

Ma, J (1994) Strategy-proofness and the strict core in a market with indivisibilities, International Journal of Game Theory, Volume 23, Issue 1, 75—83.
Miyagawa, E (2002) Strategy-proofness and the core in house allocation problems, Games andEconomic Behavior, Volume 38, Issue 2, 347—361.
Papai, S (2000a) Strategyproof assignment by hierarchical exchange, Econometrica, Volume
68, Issue 6, 1403—1433.
Papai, S (2000b) Strategyproof multiple assignment using quotas, Review of Economic Design,
Volume 5, Issue 1, 91—105.
Shapley, L and Scarf, H (1974) On cores and indivisibility, Journal of Mathematical Economics,
Volume 1, Issue 1, 23—37.
Svensson, L (1999) Strategy-proof allocation of indivisible goods, Social Choice and Welfare,
Volume 16, Issue 4, 557—567.
Takaymiya, K (2001) Coalition Strategy-proofness and monotonicity in Shapley—Scarf housing
markets, Mathematical Social Sciences, Volume 41, Issue 2, 201—213.
Thomson, W (2012) On the axiomatics of resource allocation: interpreting the consistency
principle, Economics and Philosophy, Volume 28, Issue 3, 385—421.
Zhou, L (1990) On a conjecture by Gale about one-sided matching problems, Journal of
Economic Theory, Volume 52, Issue 1, 123—135.

12