Upper-contour strategy-proofness in the probabilistic assignment problem

Abstract

Bogomolnaia and Moulin (J Econ Theory 100:295–328, 2001) show that there is no rule satisfying stochastic dominance efficiency,equal treatment of equals and stochastic dominance strategy-proofness for a probabilistic assignment problem of indivisible objects. Recently, Mennle and Seuken (Partial strategyproofness: relaxing strategy-proofness for the random assignment problem. Mimeo, 2017) show that stochastic dominance strategy-proofness is equivalent to the combination of three axioms, swap monotonicity,upper invariance, and lower invariance. In this paper, we introduce a weakening of stochastic dominance strategy-proofness, called upper-contour strategy-proofness, which requires that if the upper-contour sets of some objects are the same in two preference relations, then the sum of probabilities assigned to the objects in the two upper-contour sets should be the same. First, we show that upper-contour strategy-proofness is equivalent to the combination of two axioms, upper invariance and lower invariance. Next, we show that the impossibility result still holds even though stochastic dominance strategy-proofness is weakened to upper-contour strategy-proofness.

1 Introduction

We consider a problem of allocating indivisible objects to a group of agents when each agent is supposed to receive exactly one object and monetary compensations are not allowed. This problem occurs frequently in many real-life situations: dormitory allocation in the university, work assignment to workers, student assignment to primary schools, etc.

It is obvious that the indivisibility of objects causes a difficulty in achieving fairness. Suppose that there are two objects to be allocated to two agents with the same preference relation. If agents strictly prefer one object to another, then each of the two possible allocations will violate any reasonable notion of fairness. To overcome this difficulty, we follow the literature and use lotteries to assign the objects. This assignment problem was introduced by Hylland and Zeckhauser (1979).

Bogomolnaia and Moulin (2001) show that there is no rule satisfying three reasonable requirements for the assignment problem, namely, stochastic dominance efficiency,equal treatment of equals, and stochastic dominance strategy-proofness.Stochastic dominance efficiency requires that a rule should choose an allocation which is not stochastically dominated by another allocation. Equal treatment of equals requires that if two agents have the same preference relation, then they should end up with the same assignment. Stochastic dominance strategy-proofness requires that an agent should not gain by misrepresenting her preference relation.¹

Recently, Mennle and Seuken (2017) show that stochastic dominance strategy-proofness is equivalent to the combination of three axioms, swap monotonicity,upper invariance, and lower invariance. Swap monotonicity requires that if one agent changes her preference relation to another adjacent one by swapping two adjacent objects, then either her assignment remains the same or a higher probability should be assigned to the object with the higher rank in the revised preference relation. Upper invariance requires that if one agent changes her preference relation to another adjacent one by swapping two adjacent objects, then the probabilities of obtaining any object in the strict upper-contour set of the two objects should not be affected. Finally, lower invariance requires that if one agent changes her preference relation to another adjacent one by swapping two adjacent objects, then the probabilities of obtaining any object in the strict lower-contour set of the two objects should not be affected.

In this paper, we introduce a weakening of stochastic dominance strategy-proofness, called upper-contour strategy-proofness, which requires that if the upper-contour sets of some objects are the same in two preference relations, then the sum of probabilities assigned to the objects in the two upper-contour sets should be the same. First, we show that upper-contour strategy-proofness is equivalent to the combination of the two axioms, upper invariance and lower invariance. Next, we investigate an existence of rules satisfying upper-contour strategy-proofness together with stochastic dominance efficiency and equal treatment of equals, and show that when the number of agents is greater than three, the impossibility result still holds even though stochastic dominance strategy-proofness is weakened to upper-contour strategy-proofness. On the other hand, if the number of agents is three, we can characterize the random serial dictator rule by imposing the three axiom. We present our second impossibility result by deleting upper invariance and strengthening equal treatment of equals to strong equal treatment of equals, which requires that if two agents have the same preference up to some object starting from the most preferred object, then they should end up with the same assignment up to that object.

This paper is organized as follows. Section 2 introduces the model and basic axioms. Section 3 introduces upper-contour strategy-proofness, and investigates its logical relations with other axioms. Section 4 presents our main results.

2 The model

Let $N = \{ 1,\ldots ,n \}$ be a finite set of agents. A typical agent is denoted by $i \in N$. Let $A = \{ a,b,c,d,o_5,\ldots ,o_n\}$ be a finite set of objects. A typical object is denoted by $k \in A$. We assume that $|N| = |A| = n$. Each agent $i \in N$ has a complete, transitive, and antisymmetric binary relation $P_{i}$ over A and a corresponding weak relation $R_i$. Let $P_i$ be the preference relation of agent i and $\mathcal {P}$ be the (universal) domain of preference relations. Let $P = (P_i)_{i \in N}$ be a preference profile and $\mathcal {P}^N$ be the (universal) domain of preference profiles. Also, for each $i \in N,$ let $P_{-i} = (P_j)_{j \in N\backslash \{i\}}$. Since we do not vary either N or A,  we write an assignment problem (simply, a problem) as a list $P \in \mathcal {P}^N$. To simplify our notation, for each $i \in N$, we write $P_{i}$: abcd instead of $aP_{i}bP_{i}cP_{i}d$.

For each $P_{i}\in \mathcal {P}$ and each $a \in A,$ let $rank(P_{i}, a)$ be the rank of object a in $P_{i}$ and $r_{m}(P_{i}),$$m = 1,\ldots ,n,$ be the m-th ranked object according to $P_{i}$. Also, let $U(P_{i}, a) = \{k \in A | k R_{i} a\}$ be the upper contour set of a in $P_{i}$ and $L(P_{i}, a) = \{ k \in A | a R_{i} k \}$ be the lower contour set of a in $P_{i}$. Let $\hat{U}(P_{i}, a) = \{k \in A | k P_{i} a\}$ be the strict upper contour set of a in $P_{i}$ and $\hat{L}(P_{i}, a) = \{ k \in A | a P_{i} k \}$ be the strict lower contour set of a in $P_{i}$.

Let $\Delta (A)$ be the set of lotteries, or probability distributions over A. For all $\lambda \in \Delta (A),$$\lambda _{a}$ denotes the probability assigned to object a. A (probabilistic) allocation is a bi-stochastic matrix $L = [L_{ik}]_{i \in N, k \in A}$, namely a non-negative square matrix whose elements in each row and each column sum to unity. Let $\mathcal L$ be the set of all bi-stochastic matrices.

For each $P_{i} \in \mathcal {P}$ and each $\lambda ,$$\lambda ' \in \Delta (A),$$\lambda$stochastically dominates$\lambda '$ according to $P_{i},$ denoted by $\lambda R_{i}^{sd} \lambda ',$ if $\sum _{\ell =1}^{t}\lambda _{r_{\ell }(P_{i})} \ge \sum _{\ell =1}^{t}\lambda '_{r_{\ell }(P_{i})}$ for each $t = 1, \ldots , n$. If strict inequality holds for some t,  then we write $\lambda P_{i}^{sd} \lambda '$. Similarly, for each $P \in \mathcal {P}^{N},$ an allocation Lstochastically dominates another allocation $L',$ denoted by $L P^{sd} L',$ if for each $i \in N,$$L_{i} R_{i}^{sd} L'_{i}$ and for some $i \in N,$$L_{i} P_{i}^{sd} L'_{i}$. An allocation L satisfies stochastic dominance efficiency (simply, sd-efficiency) if it is not stochastically dominated by any other allocation. For each $P \in \mathcal {P}^{N},$ let $E^{sd}(P)$ be the set of sd-efficient allocations for P.

A rule is a function which associates with each problem an allocation in $\mathcal L$. A generic rule is denoted by $\varphi$. For each $P \in \mathcal {P}^{N}$, let $\varphi _{ik}(P)$ be the probability of agent i receiving object k,  and $\varphi _{i}(P) = (\varphi _{ik}(P))_{k \in A}$ be the assignment to agent i by rule $\varphi$.

We introduce requirements imposed on rules. Sd-efficiency requires that a rule should choose an sd-efficient allocation.

sd-efficiency  For each $P \in \mathcal {P}^{N},$$\varphi (P) \in E^{sd}(P)$.

Stochastic dominance strategy-proofness (simply, sd-strategy-proofness) requires that an agent should not gain by misrepresenting her preference relation.

sd-strategy-proofness  For each $P \in \mathcal {P}^{N},$ each $i \in N,$ and each $P'_{i} \in \mathcal {P},$$\varphi _{i}(P_{i},P_{-i})\; R^{sd}_{i} \;\varphi _{i}(P'_{i}, P_{-i})$.

Next are fairness requirements. Equal treatment of equals requires that if two agents have the same preference relation, then they should end up with the same assignment. Strong equal treatment of equals requires that if two agents have the same preference relation up to some object a starting from the most preferred object, then they should end up with the same assignment up to the object a.

Equal treatment of equals  For each $P \in \mathcal {P}^{N}$ and each i,  $j \in N,$ if $P_i = P_j,$ then $\varphi _i(P) = \varphi _j(P)$.

Strong equal treatment of equals  For each $P \in \mathcal {P}^{N},$ each i,  $j \in N,$ and each $a \in A,$ if $U(P_{i}, a) = U(P_{j}, a)$ and for each $k \in U(P_{i},a),$$rank(P_{i},k) = rank(P_{j},k),$ then for each $k \in U(P_{i},a),$$\varphi _{ik}(P) = \varphi _{jk}(P)$.

Nesterov (2017) shows that strong equal treatment of equals implies equal treatment of equals. He also shows that the converse does not hold in general.

3 Upper-contour strategy-proofness

Sd-strategy-proofness requires that an agent cannot gain by misrepresenting her preference relation. It is a very demanding requirement since we have to consider all possible manipulations of preference relations and its consequences in terms of stochastic dominance. In this paper, we introduce upper-contour stratgy-proofness (simply, uc-strategy-proofness), which is a significant weakening of sd-strategy-proofness and investigate its implications in the context of assignment problems. It requires that for some agent i,  and two preference relations $P_{i}$ and $P'_{i},$ and two objects²a and b,  if the upper-contour set of object a in $P_{i}$ and the upper-contour set of object b in $P'_{i}$ are the same, then the sum of probabilities assigned to the objects in two upper-contour sets should be the same.

uc-strategy-proofness  For each $P \in \mathcal {P}^{N},$ each $i \in N,$ each $P'_{i} \in {\mathcal {P}},$ and each a,  $b \in A,$ if $U(P_{i},a) = U(P'_{i},b),$ then $\sum _{k \in U(P_{i},a)} \varphi _{ik}(P_{i}, P_{-i}) = \sum _{k \in U(P'_{i},b)} \varphi _{ik}(P'_{i}, P_{-i})$.

Suppose that there are agent $i\in N,$ preference relations $P_{i}$ and $P_{i}',$ and objects a and b such that $U(P_{i},a) = U(P'_{i},b)$. In many situations, an agent might pay an attention on the probability that she receives an object better than or indifferent to a benchmark object (in this case, a in $P_{i}$ and b in $P'_{i}$). If the sum of probabilities assigned to the objects in $U(P'_{i},b)$ is greater than the sum of probabilities assigned to the objects in $U(P_{i},a),$ then she has an incentive to report $P'_{i}$ instead of $P_i$. Uc-strategy-proof prevents such a manipulation by an agent. As we discuss in the following, uc-strategy-proof is much weaker than sd-strategy-proofness.

Example 1

Uc-strategy-proofness does not imply sd-strategy-proofness. Let $N = \{1,2,3\}$ and $A = \{a,b,c\}$. Let $P_{1}^{1}$: abc,  $P_{1}^{2}$: acb,  $P_{1}^{3}$: bac,  $P_{1}^{4}$: bca,  $P_{1}^{5}$: cab,  and $P_{1}^{6}$: cba. We assume that the assignment to agent 1 is given as follows and the assignments to any other agents are fixed regardless of their preference relations.

$$\begin{aligned} \varphi _{1}(P^{1}_{1}, P_{2}, P_{3})= & {} \left( \frac{1}{4}, \frac{1}{2}, \frac{1}{4}\right) , ~~~ \varphi _{1}(P^{2}_{1}, P_{2}, P_{3}) = \left( \frac{1}{4}, \frac{1}{4}, \frac{1}{2}\right) , \\ \varphi _{1}(P^{3}_{1}, P_{2}, P_{3})= & {} \left( \frac{1}{2}, \frac{1}{4}, \frac{1}{4}\right) ,~~~\varphi _{1}(P^{4}_{1}, P_{2}, P_{3}) = \left( \frac{1}{2}, \frac{1}{4}, \frac{1}{4}\right) ,\\ ~~~ \varphi _{1}(P^{5}_{1}, P_{2}, P_{3})= & {} \left( \frac{1}{4}, \frac{1}{4}, \frac{1}{2}\right) , ~~~ \varphi _{1}(P^{6}_{1}, P_{2}, P_{3}) = \left( \frac{1}{2}, 0, \frac{1}{2}\right) . \end{aligned}$$

It is not difficult to show that this rule satisfies uc-strategy-proofness. However, if the true preference relation of agent 1 is $P_{1}^{6},$ then she has an incentive to misrepresent her preference relation as $P_{1}^{5},$ so that this rule does not satisfy sd-strategy-proofness.

Next, in Table 1, we calculate how many comparisons we need to verify the statements of sd-strategy-proofness and uc-strategy-proofness. When the number of agents is 3, sd-strategy-proofness asks to check 10 probability pairs, but uc-strategy-proofness 2 pairs. In Example 1, when the true preference relation of agent 1 is $P_{1}^{1},$sd-strategy-proofness asks agent 1 to compare the other five preference relations, $P_{1}^{2},$$P_{1}^{3},$$P_{1}^{4},$$P_{1}^{5},$ and $P_{1}^{6},$ and compare ten pairs of probabilities.³ On the other hand, uc-strategy-proofness asks agent 1 to compare only two preference relations, $P_{1}^{2}$ and $P_{1}^{3}$, and compare two pairs of probabilities.⁴ In general, if the number of agents is n ($n \ge 3$), then sd-strategy-proofness asks to compare $(n!-1)(n-1)$ pairs, but uc-strategy-proofness$\{\sum _{k=1}^{n-1}k!(n-k)!\} - (n-1)$ pairs. Therefore, the number of pairs needed to check for sd-strategy-proofness is at least n times greater than the number of pairs needed to check for uc-strategy-proofness.⁵

Table 1 The numbers of probability pairs needed to check for sd-strategy-proofness and uc-strategy-proofness

Mennle and Seuken (2017) show that strategy-proofness can be decomposed into three axioms, swap monotonicity,upper invariance, and lower invariance. For each pair $P_{i},$$P_{i}' \in \mathcal {P},$$P_{i}'$ is adjacent to $P_{i}$ if $P_{i}'$ is obtained from $P_{i}$ by swapping two consecutively ranked objects without affecting any other objects. Swap monotonicity requires that if one agent changes her preference relation to another adjacent one, then either the assignment to the agent remains the same or a higher probability should be assigned to the object with the higher rank in the revised preference relation. Upper invariance, introduced by Hashimoto et al. (2014), requires that if one agent changes her preference relation to another adjacent one, then the probabilities of obtaining any object in the strict upper-contour set of the two objects should not be affected. Finally, lower invariance requires that if one agent changes her preference relation to another adjacent one, then the probabilities of obtaining any object in the strict lower-contour set of the two objects should not be affected.

Swap monotonicity  For each $P \in \mathcal {P}^{N},$ each $i \in N,$ each $P'_{i} \in \mathcal {P},$ and each a,  $b \in A,$ if $P_{i}'$ is adjacent to $P_{i}$, $a P_{i} b,$ and $b P'_{i} a,$ then either $\varphi _{i}(P'_{i}, P_{-i}) = \varphi _{i}(P_{i}, P_{-i})$ or $\varphi _{ib}(P'_{i}, P_{-i}) > \varphi _{ib}(P_{i}, P_{-i})$.

Upper invariance  For each $P \in \mathcal {P}^{N},$ each $i \in N,$ each $P'_{i} \in \mathcal {P},$ and each a,  $b \in A,$ if $P_{i}'$ is adjacent to $P_{i}$, $a P_{i} b,$ and $b P'_{i} a,$ then $\varphi _{ik}(P'_{i}, P_{-i}) = \varphi _{ik}(P_{i}, P_{-i})$ for each $k \in {\hat{U}}(P_{i}, a)$.

Lower invariance  For each $P \in \mathcal {P}^{N},$ each $i \in N,$ each $P'_{i} \in \mathcal {P},$ and each a,  $b \in A,$ if $P_{i}'$ is adjacent to $P_{i},$$a P_{i} b,$ and $b P'_{i} a,$ then $\varphi _{ik}(P'_{i}, P_{-i}) = \varphi _{ik}(P_{i}, P_{-i})$ for each $k \in {\hat{L}}(P_{i}, b)$.

Here, we show that uc-strategy-proofness is equivalent to the combination of two axioms, upper invariance and lower invariance. Therefore, uc-strategy-proofness requires that if one agent changes her preference relation to another adjacent one, then the probabilities of obtaining any object either in the strict lower-contour set or in the strict lower-contour set of the two objects should not be affected.

Proposition 1

A rule satisfies uc-strategy-proofness if and only if it satisfies upper invariance and lower invariance.

Proof

($\Rightarrow$) First, we show that uc-strategy-proofness implies upper invariance. Let $\varphi$ be a rule satisfying uc-strategy-proofness. Suppose that there exist $P \in \mathcal {P}^{N},$$i \in N,$$P_{i}' \in \mathcal {P},$ and a,  $b \in A$ such that $P_{i}'$ is adjacent to $P_{i},$$a P_{i} b,$ and $b P'_{i} a$. Note that for each $k \in \hat{U}(P_{i}, a),$$U(P_{i}, k) = U(P'_{i}, k)$. By uc-strategy-proofness, for each $k \in \hat{U}(P_{i}, a) = \hat{U}(P'_{i}, b),$

$$\begin{aligned} \sum _{\ell \in U(P_{i}, k)} \varphi _{i\ell }(P_{i}, P_{-i}) = \sum _{\ell \in U(P'_{i}, k)} \varphi _{i\ell } \left( P'_{i}, P_{-i}\right) , \end{aligned}$$

which implies that

$$\begin{aligned} \varphi _{ik}(P_{i}, P_{-i}) = \varphi _{ik} \left( P'_{i}, P_{-i}\right) , \end{aligned}$$

the desired conclusion.

Next, we show that uc-strategy-proofness implies lower invariance. Suppose that there exist $P \in \mathcal {P}^{N},$$i \in N,$$P_{i}' \in \mathcal {P},$ and a,  $b \in A$ such that $P_{i}'$ is adjacent to $P_{i},$$a P_{i} b,$ and $b P'_{i} a$. Note that $U(P_{i}, b) = U(P'_{i}, a)$ and for each $k \in \hat{L}(P_{i}, b),$$U(P_{i}, k) = U(P'_{i}, k)$. By uc-strategy-proofness, for each $k \in L(P_{i}, b),$

$$\begin{aligned} \sum _{\ell \in U(P_{i}, k)} \varphi _{i\ell }(P_{i}, P_{-i}) = \sum _{\ell \in U(P'_{i}, k)} \varphi _{i\ell } \left( P'_{i}, P_{-i}\right) , \end{aligned}$$

which implies that for each $k \in \hat{L}(P_{i}, b) = \hat{L}(P'_{i}, a),$

$$\begin{aligned} \varphi _{ik}(P_{i}, P_{-i}) = \varphi _{ik} \left( P'_{i}, P_{-i}\right) , \end{aligned}$$

the desired conclusion.

($\Leftarrow$) Now we show that upper invariance and lower invariance together imply uc-strategy-proofness. Let $\varphi$ be a rule satisfying upper invariance and lower invariance. Suppose that there exist $P \in \mathcal {P}^{N},$$i \in N,$$P_{i}' \in \mathcal {P},$ and a,  $b \in A$ such that $U(P_{i},a) = U(P'_{i},b)$. We need to show that

$$\begin{aligned} \sum _{\ell \in U(P_{i},a)} \varphi _{i\ell }(P_{i}, P_{-i}) = \sum _{\ell \in U(P'_{i},b)} \varphi _{i\ell }\left( P'_{i}, P_{-i}\right) . \end{aligned}$$

(1)

Let $P_{i}'' \in \mathcal {P}$ be such that for each $k \in U(P_{i},a) = U(P'_{i},b),$$rank(P_{i}'', k) = rank(P_{i}, k)$ and for each $k \in \hat{L}(P_{i}, a) = \hat{L}(P_{i}', b),$$rank(P_{i}'', k) = rank(P'_{i}, k)$. By swapping two adjacent objects in $U(P'_{i},b)$ finite times, we can construct a sequence of preference relations $\{P_{i}^{0}, P_{i}^{1}, P_{i}^{2}, ..., P_{i}^{h}\}$ such that $P_{i}^{0}=P_{i}'$, $P_{i}^{h}=P_{i}'',$ and for each $h' \in \{0,...,h-1\}$, $P_i^{h'}$ and $P_i^{h'+1}$ are adjacent and for each $k \in \hat{L}(P_{i}, a) = \hat{L}(P_{i}', b),$$rank(P_{i}^{h'}, k) = \hat{L}(P_{i}^{h'+1}, k)$. By applying lower invariance consecutively along the path between $P_{i}'$ and $P_{i}''$, agent i has the same probability of obtaining any object in $A \setminus U(P_{i},a)$. Therefore,

$$\begin{aligned} 1-\sum _{\ell \in U(P'_{i},b)} \varphi _{i\ell }\left( P'_{i}, P_{-i}\right) = 1-\sum _{\ell \in U(P''_{i},a)} \varphi _{i\ell }\left( P''_{i}, P_{-i}\right) , \end{aligned}$$

or equivalently,

$$\begin{aligned} \sum _{\ell \in U(P'_{i},b)} \varphi _{i\ell }\left( P'_{i}, P_{-i}\right) = \sum _{\ell \in U(P''_{i},a)} \varphi _{i\ell }\left( P''_{i}, P_{-i}\right) . \end{aligned}$$

(2)

Similarly, by swapping two adjacent objects in $\hat{L}(P_{i}'', a)$ finite times, we can construct a sequence of preference relations $\{P_{i}^{0}, P_{i}^{1}, P_{i}^{2}, ..., P_{i}^{h}\}$ such that $P_{i}^{0}=P_{i}''$, $P_{i}^{h}=P_{i}$ and for each $h' \in \{0,...,h-1\}$, $P_i^{h'}$ and $P_i^{h'+1}$ are adjacent and for each $k \in U(P_{i}'', a),$$rank(P_{i}^{h'}, k) = rank(P_{i}^{h'+1}, k)$. By applying upper invariance consecutively along the path between $P_{i}''$ and $P_{i}$, agent i has the same probability of obtaining any object in $U(P_{i}'', a)$. Therefore,

$$\begin{aligned} \sum _{\ell \in U(P''_{i},a)} \varphi _{i\ell }\left( P''_{i}, P_{-i}\right) = \sum _{\ell \in U(P_{i},a)} \varphi _{i\ell }(P_{i}, P_{-i}). \end{aligned}$$

(3)

By substituting (3) into (2), we obtain the desired conclusion. $\square$

4 Main results

Bogomolnaia and Moulin (2001) show that when the number of agents is greater than three, there is no rule satisfying sd-efficiency,equal treatment of equals, and sd-strategy-proofness together. In this section, we show that the incompatibility result still holds even though sd-strategy-proofness is weakened to uc-strategy-proofness. Note that sd-strategy-proofness is equivalent to the combination of three axioms, swap monotonicity,upper invariance, and lower invariance, whereas uc-strategy-proofness is equivalent to the combination of two axioms, upper invariance and lower invariance. Our result implies that swap monotonicity is redundant in the impossibility result.

On the other hand, if $n = 3,$ then the random serial dictator rule satisfies sd-efficiency,equal treatment of equals, and uc-strategy-proofness. This rule is defined as follows: (1) assign an equal probability to each ordering of agents, (2) for each ordering, each agent chooses her most preferred object among the available ones when her turn comes, and (3) take an average of all allocations. Moreover, Bogomolnaia and Moulin (2001) show that for $n = 3,$ this rule is characterized by the combination of the three axioms. Here, we show that the characterization can be obtained even if sd-strategy-proofness is weakened to uc-strategy-proofness.

In the proof, we use the following fact established in Bogomolnaia and Moulin (2001)

Fact 1

(Bogomolnaia and Moulin 2001)  Let $N = \{1,\ldots ,n\}$ be such that $n \ge 3$ and $P \in \mathcal {P}^N$. For each $i \in N$ and each a,  $b \in A,$ if $b P_{i} a$ and $a P_{j} b$ for each $j \ne i,$ then sd-efficiency implies that $\varphi _{ia}(P)=0$. Also, for each $I \subset N$ and each a,  $b \in A,$ if $b P_{i} a$ for each $i \in I$ and $a P_{j} b$ for each $j \notin I,$ then sd-efficiency implies that $\varphi _{ia}(P)=0$ for each $i \in I$ and/or $\varphi _{jb}(P)=0$ for each $j \notin I$.

Theorem 1

If $n \ge 4,$ then there is no rule satisfying sd-efficiency, equal treatment of equals, and uc-strategy-proofness together.

Proof

Suppose by way of contradiction that there is a rule $\varphi$ satisfying sd-efficiency,equal treatment of equals, and uc-strategy-proofness. We obtain a contradiction after considering assignments to problems by the rule $\varphi$. We first consider the case when $n = 4$. Let $N = \{1,2,3,4\}$ and $A = \{a,b,c,d\}$. Also, by Proposition 1, uc-strategy-proofness can be decomposed into upper invariance and lower invariance.

Profile 1  $P^{1}$. For each $i \in N,$$P_{i}$: abcd. By equal treatment of equals,

$$\begin{aligned} \varphi (P^{1}) = \left( \begin{array}{cccc} \frac{1}{4} &{}\quad \frac{1}{4} &{}\quad \frac{1}{4} &{}\quad \frac{1}{4} \\ \frac{1}{4} &{}\quad \frac{1}{4} &{}\quad \frac{1}{4} &{}\quad \frac{1}{4} \\ \frac{1}{4} &{}\quad \frac{1}{4} &{}\quad \frac{1}{4} &{}\quad \frac{1}{4} \\ \frac{1}{4} &{}\quad \frac{1}{4} &{}\quad \frac{1}{4} &{}\quad \frac{1}{4} \end{array} \right) \end{aligned}$$

Profile 2  $P^{2}$. For $i=1,$ 2,  3,  $P_{i}$: abcd and $P_{4}$: bacd. By lower invariance,$\varphi _{4c}(P^{2}) = \varphi _{4c}(P^{1})=\frac{1}{4}$ and $\varphi _{4d}(P^{2}) = \varphi _{4d}(P^{1})= \frac{1}{4},$ and by Fact 1 applied to a and b,  $\varphi _{4a}(P^{2}) = 0,$ which together imply that $\varphi _{4b}(P^{2}) = \frac{1}{2}$. Finally, by equal treatment of equals,

$$\begin{aligned} \varphi (P^{2}) = \left( \begin{array}{cccc} \frac{1}{3} &{}\quad \frac{1}{6} &{}\quad \frac{1}{4} &{}\quad \frac{1}{4} \\ \frac{1}{3} &{}\quad \frac{1}{6} &{}\quad \frac{1}{4} &{}\quad \frac{1}{4} \\ \frac{1}{3} &{}\quad \frac{1}{6} &{}\quad \frac{1}{4} &{}\quad \frac{1}{4} \\ 0 &{}\quad \frac{1}{2} &{}\quad \frac{1}{4} &{}\quad \frac{1}{4} \end{array} \right) \end{aligned}$$

Profile 3  $P^{3}$. For $i=1,$ 2,  $P_{i}$: abcd,  and for $i=3,$ 4,  $P_{i}$: bacd. By lower invariance,$\varphi _{3c}(P^{3}) = \varphi _{3c}(P^{2}) = \frac{1}{4}$ and $\varphi _{3d}(P^{3}) = \varphi _{3d}(P^{2}) = \frac{1}{4},$ and by equal treatment of equals,$\varphi _{4c}(P^{3}) = \varphi _{4d}(P^{3}) = \frac{1}{4}$. Also, by equal treatment of equals,$\varphi _{1c}(P^{3}) = \varphi _{2c}(P^{3}) = \frac{1}{4}$ and $\varphi _{1d}(P^{3}) = \varphi _{2d}(P^{3}) = \frac{1}{4}$. By Fact 1 applied to a and b,  $\varphi _{1b}(P^{3}) = \varphi _{2b}(P^{3}) = \varphi _{3a}(P^{3}) = \varphi _{4a}(P^{3})=0$. Therefore, $\varphi _{1a}(P^{3}) = \varphi _{2a}(P^{3}) = \varphi _{3b}(P^{3}) = \varphi _{4b}(P^{3}) = \frac{1}{2}$. Altogether,

$$\begin{aligned} \varphi (P^{3}) = \left( \begin{array}{cccc} \frac{1}{2} &{}\quad 0 &{}\quad \frac{1}{4} &{}\quad \frac{1}{4} \\ \frac{1}{2} &{}\quad 0&{}\quad \frac{1}{4} &{}\quad \frac{1}{4} \\ 0 &{}\quad \frac{1}{2} &{}\quad \frac{1}{4} &{}\quad \frac{1}{4} \\ 0 &{}\quad \frac{1}{2} &{}\quad \frac{1}{4} &{}\quad \frac{1}{4} \end{array} \right) \end{aligned}$$

Profile 4  $P^{4}$.  For $i=1,$ 2,  3,  $P_{i}$: abcd,  and $P_{4}$: bcad. By lower invariance,$\varphi _{4d}(P^{4}) = \varphi _{4d}(P^{2}) = \frac{1}{4}$ and by upper invariance,$\varphi _{4b}(P^{4})= \varphi _{4b}(P^{2}) = \frac{1}{2}$. By Fact 1 applied to a and b,  $\varphi _{4a}(P^{4}) = 0,$ which together imply that $\varphi _{4c}(P^{4}) = \frac{1}{4}$. By equal treatment of equals,

$$\begin{aligned} \varphi (P^{4}) = \left( \begin{array}{cccc} \frac{1}{3} &{}\quad \frac{1}{6} &{}\quad \frac{1}{4} &{}\quad \frac{1}{4} \\ \frac{1}{3} &{}\quad \frac{1}{6} &{}\quad \frac{1}{4} &{}\quad \frac{1}{4} \\ \frac{1}{3} &{}\quad \frac{1}{6} &{}\quad \frac{1}{4} &{}\quad \frac{1}{4} \\ 0 &{}\quad \frac{1}{2} &{}\quad \frac{1}{4} &{}\quad \frac{1}{4} \end{array} \right) \end{aligned}$$

Profile 5  $P^{5}$. For $i=1,$ 2,  $P_{i}$: abcd,  $P_{3}$: bacd,  and $P_{4}$: bcad. By lower invariance,$\varphi _{3c}(P^{5}) = \varphi _{3c}(P^{4}) = \frac{1}{4}$ and $\varphi _{3d}(P^{5}) = \varphi _{3d}(P^{4}) = \frac{1}{4}$. Also, by upper invariance,$\varphi _{4b}(P^{5}) = \varphi _{4b}(P^{3}) = \frac{1}{2}$ and by lower invariance, $\varphi _{4d}(P^{5}) = \varphi _{4d}(P^{3}) =\frac{1}{4}$. By Fact 1 applied to a and c,  $\varphi _{4a}(P^{5})=0,$ which implies that $\varphi _{4c}(P^{5}) = \frac{1}{4}$. By equal treatment of equals,$\varphi _{1c}(P^{5}) = \varphi _{1d}(P^{5}) = \varphi _{2c}(P^{5})=\varphi _{2d}(P^{5})=\frac{1}{4}$. By Fact 1 applied to a and b,  $\varphi _{1b}(P^{5}) = \varphi _{2b}(P^{5}) = \varphi _{3a}(P^{5})=0$. Altogether,

$$\begin{aligned} \varphi (P^{5}) = \left( \begin{array}{cccc} \frac{1}{2} &{}\quad 0 &{}\quad \frac{1}{4} &{}\quad \frac{1}{4} \\ \frac{1}{2} &{}\quad 0&{}\quad \frac{1}{4} &{}\quad \frac{1}{4} \\ 0 &{}\quad \frac{1}{2} &{}\quad \frac{1}{4} &{}\quad \frac{1}{4} \\ 0 &{}\quad \frac{1}{2} &{}\quad \frac{1}{4} &{}\quad \frac{1}{4} \end{array} \right) \end{aligned}$$

Profile 6  $P^{6}$. For $i=1,$ 2,  $P_{i}$: abcd,  and for $i=3,$ 4,  $P_{i}$: bcad. By upper invariance,$\varphi _{3b}(P^{6}) = \varphi _{3b}(P^{5}) = \frac{1}{2}$ and by lower invariance, $\varphi _{3d}(P^{6}) = \varphi _{3d}(P^{5}) = \frac{1}{4}$. By equal treatment of equals,$\varphi _{4b}(P^{6}) = \varphi _{3b}(P^{6}) = \frac{1}{2}$ and $\varphi _{4d}(P^{6}) = \varphi _{3d}(P^{6}) = \frac{1}{4}$. Therefore, $\varphi _{1b}(P^{6}) = \varphi _{2b}(P^{6})=0$ and $\varphi _{1d}(P^{6}) = \varphi _{2d}(P^{6}) = \frac{1}{4}$. By Fact 1 applied to a and c,  $\varphi _{3a}(P^{6}) = \varphi _{4a}(P^{6}) = 0$. Altogether,

$$\begin{aligned} \varphi (P^{6}) = \left( \begin{array}{cccc} \frac{1}{2} &{}\quad 0 &{}\quad \frac{1}{4} &{}\quad \frac{1}{4} \\ \frac{1}{2} &{}\quad 0&{}\quad \frac{1}{4} &{}\quad \frac{1}{4} \\ 0 &{}\quad \frac{1}{2} &{}\quad \frac{1}{4} &{}\quad \frac{1}{4} \\ 0 &{}\quad \frac{1}{2} &{}\quad \frac{1}{4} &{}\quad \frac{1}{4} \end{array} \right) \end{aligned}$$

Profile 7, $P^{7}$. For $i=1,$ 2,  3,  $P_{i}$: abcd,  and $P_{4}$: bcda. By upper invariance,$\varphi _{4b}(P^{7}) = \varphi _{4b}(P^{4}) = \frac{1}{2}$ and $\varphi _{4c}(P^{7}) = \varphi _{4c}(P^{4})= \frac{1}{4}$. By Fact 1 applied to a and b,  $\varphi _{4a}(P^{7})=0,$ which implies that $\varphi _{4d}(P^{7}) = \frac{1}{4}$. By equal treatment of equals,

$$\begin{aligned} \varphi (P^{7}) = \left( \begin{array}{cccc} \frac{1}{3} &{}\quad \frac{1}{6} &{}\quad \frac{1}{4} &{}\quad \frac{1}{4} \\ \frac{1}{3} &{}\quad \frac{1}{6} &{}\quad \frac{1}{4} &{}\quad \frac{1}{4} \\ \frac{1}{3}&{}\quad \frac{1}{6} &{}\quad \frac{1}{4} &{}\quad \frac{1}{4} \\ 0 &{}\quad \frac{1}{2} &{}\quad \frac{1}{4} &{}\quad \frac{1}{4} \end{array} \right) \end{aligned}$$

Profile 8, $P^{8}$. For $i=1,$ 2,  $P_{i}$: abcd,  $P_{3}$: bacd,  and $P_{4}$: bcda. By lower invariance,$\varphi _{3c}(P^{8}) = \varphi _{3c}(P^{7}) = \frac{1}{4}$ and $\varphi _{3d}(P^{8}) = \varphi _{3d}(P^{7}) = \frac{1}{4}$. Also, by upper invariance,$\varphi _{4b}(P^{8}) = \varphi _{4b}(P^{5}) = \frac{1}{2}$ and $\varphi _{4c}(P^{8}) = \varphi _{4c}(P^{5}) = \frac{1}{4}$. By Fact 1 applied to a and d,  $\varphi _{4a}(P^{8}) = 0$. Therefore, $\varphi _{1c}(P^{8}) = \varphi _{1d}(P^{8}) = \varphi _{2c}(P^{8}) = \varphi _{2d}(P^{8}) = \frac{1}{4}$. Also, by Fact 1 applied to a and b,  $\varphi _{1b}(P^{8}) = \varphi _{2b}(P^{8}) = \varphi _{3a}(P^{8}) = 0$. Altogether,

$$\begin{aligned} \varphi (P^{8}) = \left( \begin{array}{cccc} \frac{1}{2} &{}\quad 0 &{}\quad \frac{1}{4} &{}\quad \frac{1}{4} \\ \frac{1}{2} &{}\quad 0 &{}\quad \frac{1}{4} &{}\quad \frac{1}{4} \\ 0&{}\quad \frac{1}{2} &{}\quad \frac{1}{4} &{}\quad \frac{1}{4} \\ 0 &{}\quad \frac{1}{2} &{}\quad \frac{1}{4} &{}\quad \frac{1}{4} \end{array} \right) \end{aligned}$$

Profile 8$'$, $P^{8'}$. $P_{1}$: bacd,  for $i=2,$ 3,  $P_{i}$: abcd,  and $P_{4}$: bcda. From the same reasoning as in Profile 8,

$$\begin{aligned} \varphi (P^{8'}) = \left( \begin{array}{cccc} 0&{}\quad \frac{1}{2} &{}\quad \frac{1}{4} &{}\quad \frac{1}{4} \\ \frac{1}{2} &{}\quad 0 &{}\quad \frac{1}{4} &{}\quad \frac{1}{4} \\ \frac{1}{2} &{}\quad 0 &{}\quad \frac{1}{4} &{}\quad \frac{1}{4} \\ 0 &{}\quad \frac{1}{2} &{}\quad \frac{1}{4} &{}\quad \frac{1}{4} \end{array} \right) \end{aligned}$$

Profile 8$''$, $P^{8''}$. For $i=1,$ 3,  $P_{i}$: abcd,  $P_{2}$: bacd,  and $P_{4}$: bcda. From the same reasoning as in Profile 8,

$$\begin{aligned} \varphi (P^{8''}) = \left( \begin{array}{cccc} \frac{1}{2} &{}\quad 0 &{}\quad \frac{1}{4} &{}\quad \frac{1}{4} \\ 0&{}\quad \frac{1}{2} &{}\quad \frac{1}{4} &{}\quad \frac{1}{4} \\ \frac{1}{2} &{}\quad 0 &{}\quad \frac{1}{4} &{}\quad \frac{1}{4} \\ 0 &{}\quad \frac{1}{2} &{}\quad \frac{1}{4} &{}\quad \frac{1}{4} \end{array} \right) \end{aligned}$$

Profile 9  $P^{9}$. For each $i \in N,$$P_{i}$: bacd. By equal treatment of equals,

$$\begin{aligned} \varphi (P^{9}) = \left( \begin{array}{cccc} \frac{1}{4} &{}\quad \frac{1}{4} &{}\quad \frac{1}{4} &{}\quad \frac{1}{4} \\ \frac{1}{4} &{}\quad \frac{1}{4} &{}\quad \frac{1}{4} &{}\quad \frac{1}{4} \\ \frac{1}{4} &{}\quad \frac{1}{4} &{}\quad \frac{1}{4} &{}\quad \frac{1}{4} \\ \frac{1}{4} &{}\quad \frac{1}{4} &{}\quad \frac{1}{4} &{}\quad \frac{1}{4} \end{array} \right) \end{aligned}$$

Profile 10  $P^{10}$. For $i=1,$ 2,  3,  $P_{i}$: bacd,  and $P_{4}$: bcad. By upper invariance,$\varphi _{4b}(P^{10}) = \varphi _{4b}(P^{9}) = \frac{1}{4}$ and by lower invariance, $\varphi _{4d}(P^{10}) = \varphi _{4d}(P^{9}) = \frac{1}{4}$. By Fact 1 applied to a and c,  $\varphi _{4a}(P^{10})=0$. Altogether, $\varphi _{4c}(P^{10}) = \frac{1}{2}$. By equal treatment of equals,

$$\begin{aligned} \varphi (P^{10}) = \left( \begin{array}{cccc} \frac{1}{3} &{}\quad \frac{1}{4} &{}\quad \frac{1}{6} &{}\quad \frac{1}{4} \\ \frac{1}{3} &{}\quad \frac{1}{4} &{}\quad \frac{1}{6} &{}\quad \frac{1}{4} \\ \frac{1}{3} &{}\quad \frac{1}{4} &{}\quad \frac{1}{6} &{}\quad \frac{1}{4} \\ 0 &{}\quad \frac{1}{4} &{}\quad \frac{1}{2} &{}\quad \frac{1}{4} \end{array} \right) \end{aligned}$$

Profile 11  $P^{11}$. For $i=1,$ 2,  3,  $P_{i}$: bacd,  and $P_{4}$: bcda. By upper invariance,$\varphi _{4b}(P^{11}) = \varphi _{4b}(P^{10}) = \frac{1}{4}$ and $\varphi _{4c}(P^{11}) = \varphi _{4c}(P^{10}) = \frac{1}{2}$. By Fact 1 applied to a and c,  $\varphi _{4a}(P^{11}) = 0,$ which implies that $\varphi _{4d}(P^{11}) = \frac{1}{4}$. By equal treatment of equals,

$$\begin{aligned} \varphi (P^{11}) = \left( \begin{array}{cccc} \frac{1}{3} &{}\quad \frac{1}{4} &{}\quad \frac{1}{6} &{}\quad \frac{1}{4} \\ \frac{1}{3} &{}\quad \frac{1}{4} &{}\quad \frac{1}{6} &{}\quad \frac{1}{4} \\ \frac{1}{3} &{}\quad \frac{1}{4} &{}\quad \frac{1}{6} &{}\quad \frac{1}{4} \\ 0 &{}\quad \frac{1}{4} &{}\quad \frac{1}{2} &{}\quad \frac{1}{4} \end{array} \right) \end{aligned}$$

Profile 12  $P^{12}$. For $i=1,$ 2,  4,  $P_{i}$: bacd and $P_{3}$: abcd. By lower invariance,$\varphi _{3c}(P^{12}) = \varphi _{3c}(P^{9}) = \frac{1}{4}$ and $\varphi _{3d}(P^{12}) = \varphi _{3d}(P^{9}) = \frac{1}{4}$. By Fact 1 applied to a and b,  $\varphi _{3b}(P^{12}) = 0,$ which implies that $\varphi _{3a}(P^{12}) = \frac{1}{2}$. By equal treatment of equals,

$$\begin{aligned} \varphi (P^{12}) = \left( \begin{array}{cccc} \frac{1}{6} &{}\quad \frac{1}{3} &{}\quad \frac{1}{4} &{}\quad \frac{1}{4} \\ \frac{1}{6} &{}\quad \frac{1}{3} &{}\quad \frac{1}{4} &{}\quad \frac{1}{4} \\ \frac{1}{2} &{}\quad 0 &{}\quad \frac{1}{4} &{}\quad \frac{1}{4}\\ \frac{1}{6} &{}\quad \frac{1}{3} &{}\quad \frac{1}{4} &{}\quad \frac{1}{4} \end{array} \right) \end{aligned}$$

Profile 13  $P^{13}$. For $i=1,$ 2,  $P_{i}$: bacd,  $P_{3}$: abcd,  and $P_{4}$: bcad. By upper invariance,$\varphi _{4b}(P^{13}) = \varphi _{4b}(P^{12}) = \frac{1}{3}$.

$$\begin{aligned} \varphi (P^{13}) = \left( \begin{array}{cccc} \cdot &{}\quad \cdot &{}\quad \cdot &{}\quad \cdot \\ \cdot &{}\quad \cdot &{}\quad \cdot &{}\quad \cdot \\ \cdot &{}\quad \cdot &{}\quad \cdot &{}\quad \cdot \\ \cdot &{}\quad \frac{1}{3} &{}\quad \cdot &{}\quad \cdot \end{array} \right) \end{aligned}$$

Profile 14  $P^{14}$. For $i=1,$ 2,  $P_{i}$: bacd,  $P_{3}$: abcd,  and $P_{4}$: bcda. By lower invariance,$\varphi _{2c}(P^{14}) = \varphi _{2c}(P^{8'}) = \frac{1}{4}$ and $\varphi _{2d}(P^{14}) = \varphi _{2d}(P^{8'}) = \frac{1}{4},$ and $\varphi _{1c}(P^{14}) = \varphi _{1c}(P^{8''}) = \frac{1}{4}$ and $\varphi _{1d}(P^{14}) = \varphi _{1d}(P^{8''}) = \frac{1}{4}$. Also, by lower invariance,$\varphi _{3c}(P^{14}) = \varphi _{3c}(P^{11}) = \frac{1}{6}$ and $\varphi _{3d}(P^{14}) = \varphi _{3d}(P^{11}) = \frac{1}{4}$. By Fact 1 applied to a and b,  $\varphi _{3b}(P^{14}) = 0$. Also, by Fact 1 applied to a and d,  $\varphi _{4a}(P^{14}) = 0$. Therefore, $\varphi _{3a}(P^{14}) = \frac{7}{12}$ and $\varphi _{1a}(P^{14}) = \frac{5}{24}$. By upper invariance,$\varphi _{4b}(P^{14}) = \varphi _{4b}(P^{13}) = \frac{1}{3}$. By equal treatment of equals,$\varphi _{1b}(P^{14}) = \varphi _{2b}(P^{14}) = \frac{1}{3}$. However, $\sum _{k \in A}\varphi _{1k}(P^{14}) = \sum _{k \in A}\varphi _{2k}(P^{14}) = \frac{5}{24} + \frac{1}{3} + \frac{1}{4} + \frac{1}{4} > 1,$ a contradiction.

$$\begin{aligned} \varphi (P^{14}) = \left( \begin{array}{cccc} \frac{5}{24} &{}\quad \frac{1}{3} &{}\quad \frac{1}{4} &{}\quad \frac{1}{4} \\ \frac{5}{24} &{}\quad \frac{1}{3} &{}\quad \frac{1}{4} &{}\quad \frac{1}{4} \\ \frac{7}{12} &{}\quad 0 &{}\quad \frac{1}{6} &{}\quad \frac{1}{4} \\ 0 &{}\quad \frac{1}{3} &{}\quad \cdot &{}\quad \cdot \end{array} \right) \end{aligned}$$

Now we consider the case when $n > 5$. Let $N = \{1,\ldots ,n\}$ and $A = \{a,b,c,d,o_{5},\ldots ,o_n\}$. We construct preference profiles $P \in \mathcal {P}^N$ such that for each $i \in \{1,2,3,4\},$ the preference ordering on $\{a,b,c,d\}$ is the same as before in the most preferred 4 positions and for each $i \in \{5,\ldots ,n\},$ the most preferred object is $o_i$. By sd-efficiency, for each $i \in \{5,\ldots ,n\},$$\varphi _{i}o_i(P) = 1$. By using a similar argument as before, we have a contradiction. $\square$

Remark 1

We discuss the independence of axioms in Theorem 1. Serial dictator rules satisfy sd-efficiency, upper invariance and lower invariance, but not equal treatment of equals. The random serial dictator rule satisfies equal treatment of equals, upper invariance and lower invariance, but not sd-efficiency. The probabilistic serial rule satisfies sd-efficiency, equal treatment of equals and upper invariance, but not lower invariance. However, the existence of a rule satisfying sd-efficiency,equal treatment of equals, and lower invariance, but not upper invariance, is an open question.

Remark 2

Let $A=\{a,b,c,d\}$ be linearly ordered as a, b, c, d. The preference relations used in the proof of Theorem 1 is abcd, bacd, bcad, and bcda. Since all four preference relations can be represented to satisfy single-peakedness, our impossibility result holds even if the domain is restricted to be single-peaked.

Now we characterize the random serial dictator rule for $n = 3$.

Proposition 2

If $n = 3,$ then the random serial dictator rule is the only rule satisfying sd-efficiency, equal treatment of equals, and uc-strategy-proofness.

Proof

Let $N = \{1,2,3\}$ and $A = \{a,b,c\}$. It is obvious that the random serial dictator rule satisfies sd-efficiency,equal treatment of equals, and uc-strategy-proofness. We prove the converse statement. Note that if $n = 3,$ then there are 216 preference profiles which can be classified into six types (Bogomolnaia and Moulin 2001). These preference profiles are as follows. The bracket in the preference relation indicates that the proof can be obtained by using similar arguments irrespective of the preference orderings of the objects in the bracket. For example, in Type 1, $P_{1}$: a(bc) means that both $P_1$: abc and $P_1$: acb can be handled in a similar way.

$$\begin{aligned}&\text {Type 1 (48 profiles)} \left\{ \begin{array}{ll} P_{1}: a(bc)\\ P_{2}: b(ac)\\ P_{3}: c(ab) \end{array} \right. ~~~~~~~~~~ \text {Type 2 (6 profiles)} \left\{ \begin{array}{ll} P_{1}: abc\\ P_{2}: abc\\ P_{3}: abc \end{array} \right. \\&\text {Type 3 (18 profiles)} \left\{ \begin{array}{ll} P_{1}: abc\\ P_{2}: abc\\ P_{3}: acb \end{array} \right. ~~~~~~~~~~~ \text {Type 4 (36 profiles)} \left\{ \begin{array}{ll} P_{1}: acb \\ P_{2}: acb \\ P_{3}: b(ac) \end{array} \right. \\&\text {Type 5 (36 profiles)} \left\{ \begin{array}{ll} P_{1}: abc\\ P_{2}: abc\\ P_{3}: b(ac) \end{array} \right. ~~~~~~~~ \text {Type 6 (72 profiles)} \left\{ \begin{array}{ll} P_{1}: abc\\ P_{2}: acb\\ P_{3}: b(ac) \end{array} \right. \end{aligned}$$

Now we consider each type of preference profiles and show that if the rule satisfies the three axioms, then it should choose the same allocation as the random serial dictator rule. Once again, by Proposition 1, uc-strategy-proofness can be decomposed into upper invariance and lower invariance.

Type 1  $P^{1}$. By sd-efficiency,$\varphi _{1a}(P^{1}) = \varphi _{2b}(P^{1}) = \varphi _{3c}(P^{1})=1$. Therefore,

$$\begin{aligned} \varphi (P^{1}) = \left( \begin{array}{ccc} 1 &{}\quad 0 &{}\quad 0 \\ 0 &{}\quad 1 &{}\quad 0 \\ 0 &{}\quad 0 &{}\quad 1 \\ \end{array} \right) \end{aligned}$$

Type 2  $P^{2}$. By equal treatment of equals, for all $i \in N,$$\varphi _{ia}(P^{2})=\varphi _{ib}(P^{2})=\varphi _{ic}(P^{2})=\frac{1}{3}$. That is,

$$\begin{aligned} \varphi (P^{2}) = \left( \begin{array}{ccc} \frac{1}{3} &{}\quad \frac{1}{3} &{}\quad \frac{1}{3} \\ \frac{1}{3}&{}\quad \frac{1}{3} &{}\quad \frac{1}{3} \\ \frac{1}{3} &{}\quad \frac{1}{3} &{}\quad \frac{1}{3} \end{array} \right) \end{aligned}$$

Type 3  $P^{3}$. By upper invariance,$\varphi _{3a}(P^{3}) = \varphi _{3a}(P^{2}) = \frac{1}{3}$. By Fact 1 applied to b and c,  $\varphi _{3b}(P^{3}) = 0$. Therefore, $\varphi _{3c}(P^{3}) = \frac{2}{3}$. By equal treatment of equals,

$$\begin{aligned} \varphi (P^{3}) = \left( \begin{array}{ccc} \frac{1}{3} &{}\quad \frac{1}{2} &{}\quad \frac{1}{6} \\ \frac{1}{3}&{}\quad \frac{1}{2} &{}\quad \frac{1}{6} \\ \frac{1}{3} &{}\quad 0 &{}\quad \frac{2}{3} \end{array} \right) \end{aligned}$$

Next, we consider $P^{3'},$ for $i=1,$ 3,  $P_{i}$: abc and $P_{2}$: acb. From the same reasoning as in $P^3,$

$$\begin{aligned} \varphi (P^{3'}) = \left( \begin{array}{ccc} \frac{1}{3} &{}\quad \frac{1}{2} &{}\quad \frac{1}{6} \\ \frac{1}{3} &{}\quad 0 &{}\quad \frac{2}{3} \\ \frac{1}{3}&{}\quad \frac{1}{2} &{}\quad \frac{1}{6} \\ \end{array} \right) \end{aligned}$$

Type 4  $P^{4}$. By Fact 1 applied to a and b,  $\varphi _{3a}(P^{4})=0$ and by Fact 1 applied to b and c, $\varphi _{3c}(P^{4})=0,$ which together imply that $\varphi _{3b}(P^{4})=1$. By equal treatment of equals,

$$\begin{aligned} \varphi (P^{4}) = \left( \begin{array}{cll} \frac{1}{2} &{}\quad 0 &{}\quad \frac{1}{2} \\ \frac{1}{2}&{}\quad 0 &{}\quad \frac{1}{2} \\ 0 &{}\quad 1 &{}\quad 0 \\ \end{array} \right) \end{aligned}$$

Type 5-1  $P^{5-1}$. $P_{3}$: bac. By lower invariance,$\varphi _{3c}(P^{5-1}) = \varphi _{3c}(P^{2}) = \frac{1}{3}$. By Fact 1 applied to a and b,  $\varphi _{3a}(P^{5-1}) = 0$. Therefore, $\varphi _{3b}(P^{5-1}) = \frac{2}{3}$. By equal treatment of equals,

$$\begin{aligned} \varphi (P^{5-1}) = \left( \begin{array}{ccc} \frac{1}{2} &{}\quad \frac{1}{6} &{}\quad \frac{1}{3} \\ \frac{1}{2}&{}\quad \frac{1}{6} &{}\quad \frac{1}{3} \\ 0 &{}\quad \frac{2}{3} &{}\quad \frac{1}{3} \\ \end{array} \right) \end{aligned}$$

Type 5-2  $P^{5-2}$. $P_{3}$: bca. By Fact 1 applied to a and b,  $\varphi _{3a}(P^{5-2}) = 0$. By upper invariance,$\varphi _{3b}(P^{5-2}) = \varphi _{3b}(P^{5-1}) = \frac{2}{3},$ which implies that $\varphi _{3c}(P^{5-2}) = \frac{1}{3}$. By equal treatment of equals,

$$\begin{aligned} \varphi (P^{5-2}) = \left( \begin{array}{ccc} \frac{1}{2} &{}\quad \frac{1}{6} &{}\quad \frac{1}{3} \\ \frac{1}{2}&{}\quad \frac{1}{6} &{}\quad \frac{1}{3} \\ 0 &{}\quad \frac{2}{3} &{}\quad \frac{1}{3} \\ \end{array} \right) \end{aligned}$$

Type 6-1  $P^{6-1}$. $P_{3}$: bac. By lower invariance,$\varphi _{3c}(P^{6-1}) = \varphi _{3c}(P^{3'}) = \frac{1}{6}$. By Fact 1 applied to a and b,  $\varphi _{3a}(P^{6-1}) = 0,$ which implies that $\varphi _{3b}(P^{6-1}) = \frac{5}{6}$. By upper invariance,$\varphi _{2a}(P^{6-1}) = \varphi _{2a}(P^{5-1}) = \frac{1}{2}$. By Fact 1 applied to b and c,  $\varphi _{2b}(P^{6-1}) = 0,$ which implies that $\varphi _{2c}(P^{6-1})=\frac{1}{2}$. Therefore,

$$\begin{aligned} \varphi (P^{6-1}) = \left( \begin{array}{ccc} \frac{1}{2} &{}\quad \frac{1}{6} &{}\quad \frac{1}{3} \\ \frac{1}{2}&{}\quad 0 &{}\quad \frac{1}{2} \\ 0 &{}\quad \frac{5}{6} &{}\quad \frac{1}{6} \\ \end{array} \right) \end{aligned}$$

Type 6-2  $P^{6-2}$. $P_{3}$: bca. By upper invariance,$\varphi _{3b}(P^{6-2}) = \varphi _{3b}(P^{6-1}) = \frac{5}{6}$. By Fact 1 applied to a and b,  $\varphi _{3a}(P^{6-2}) = 0,$ which implies that $\varphi _{3c}(P^{6-2}) = \frac{1}{6}$. By upper invariance,$\varphi _{2a}(P^{6-2}) = \varphi _{2a}(P^{5-2}) = \frac{1}{2}$. By Fact 1 applied to b and c,  $\varphi _{2b}(P^{6-2})=0,$ which implies that $\varphi _{2c}(P^{6-2})=\frac{1}{2}$. Therefore,

$$\begin{aligned} \varphi (P^{6-2}) = \left( \begin{array}{ccc} \frac{1}{2} &{}\quad \frac{1}{6} &{}\quad \frac{1}{3} \\ \frac{1}{2}&{}\quad 0 &{}\quad \frac{1}{2} \\ 0 &{}\quad \frac{5}{6} &{}\quad \frac{1}{6} \\ \end{array} \right) \end{aligned}$$

$\square$

Next we investigate the consequence of deleting upper invariance from Theorem 1. By strengthening equal treatment of equals to strong equal treatment of equals, we still end up with an impossibility result. A related result is given by Nesterov (2017), who shows that when the number of agents is at least three, there is no rule satisfying ex-post efficiency,⁶upper envy-freeness,⁷ and lower invariance. Our impossibility result uses a stronger efficiency requirement of sd-efficiency, but a weaker fairness requirement of strong equal treatment of equals.

Theorem 2

If $n \ge 4,$ then there is no rule satisfying sd-efficiency, strong equal treatment of equals, and lower invariance together.

Proof

Suppose by way of contradiction that there is a rule $\varphi$ satisfying sd-efficiency,strong equal treatment of equals, and lower invariance. We obtain a contradiction after considering assignments to problems by the rule $\varphi$. We first consider the case $n = 4$. Let $N = \{1,2,3,4\}$ and $A = \{a,b,c,d\}$.

Profile 1  $P^{1}$. For $i=1,$ 2,  3,  $P_{i}$: acbd and $P_{4}$: adcb. By Fact 1 applied to b and d,  $\varphi _{4b}(P^{1}) = 0$ and by Fact 1 applied to c and d,  $\varphi _{4c}(P^{1}) = 0$. By strong equal treatment of equals,$\varphi _{1a}(P^{1}) = \varphi _{2a}(P^{1}) = \varphi _{3a}(P^{1}) = \varphi _{4a}(P^{1}) = \frac{1}{4}$. Then, $\varphi _{4a}(P^{1}) = \frac{3}{4}$. By strong equal treatment of equals,

$$\begin{aligned} \varphi (P^{1}) = \left( \begin{array}{cccc} \frac{1}{4} &{}\quad \frac{1}{3} &{}\quad \frac{1}{3} &{}\quad \frac{1}{12} \\ \frac{1}{4} &{}\quad \frac{1}{3} &{}\quad \frac{1}{3} &{}\quad \frac{1}{12} \\ \frac{1}{4} &{}\quad \frac{1}{3} &{}\quad \frac{1}{3} &{}\quad \frac{1}{12} \\ \frac{1}{4} &{}\quad 0 &{}\quad 0&{}\quad \frac{3}{4} \\ \end{array} \right) \end{aligned}$$

Profile 2  $P^{2}$. For $i=1,$ 2,  $P_{i}$: acbd,  $P_{3}$: abcd,  and $P_{4}$: adcb. By Fact 1 applied to b and d,  $\varphi _{4b}(P^{2}) = 0$ and by Fact 1 applied to c and d,  $\varphi _{4c}(P^{2}) = 0$. By lower invariance,$\varphi _{3d}(P^{2}) = \varphi _{3d}(P^{1}) = \frac{1}{12}$. By strong equal treatment of equals,$\varphi _{1a}(P^{2}) = \varphi _{2a}(P^{2}) = \varphi _{3a}(P^{2}) = \varphi _{4a}(P^{2}) = \frac{1}{4}$. Therefore, $\varphi _{4d}(P^{2})=\frac{3}{4}$. By Fact 1 applied to b and c,  $\varphi _{3c}(P^{2})=0,$ which implies that $\varphi _{3b}(P^{2}) = \frac{2}{3}$. By strong equal treatment of equals,

$$\begin{aligned} \varphi (P^{2}) = \left( \begin{array}{cccc} \frac{1}{4} &{}\quad \frac{1}{6} &{}\quad \frac{1}{2} &{}\quad \frac{1}{12} \\ \frac{1}{4} &{}\quad \frac{1}{6} &{}\quad \frac{1}{2} &{}\quad \frac{1}{12} \\ \frac{1}{4} &{}\quad \frac{2}{3} &{}\quad 0 &{}\quad \frac{1}{12} \\ \frac{1}{4} &{}\quad 0 &{}\quad 0&{}\quad \frac{3}{4} \\ \end{array} \right) \end{aligned}$$

Profile 2$'$, $P^{2'}$. $P_{1}$: abcd,  for $i=2,$ 3,  $P_{i}$: acbd,  and $P_{4}$: adcb. By the same reasoning as in Profile 2,

$$\begin{aligned} \varphi (P^{2'}) = \left( \begin{array}{cccc} \frac{1}{4} &{}\quad \frac{2}{3} &{}\quad 0 &{}\quad \frac{1}{12} \\ \frac{1}{4} &{}\quad \frac{1}{6} &{}\quad \frac{1}{2} &{}\quad \frac{1}{12} \\ \frac{1}{4} &{}\quad \frac{1}{6} &{}\quad \frac{1}{2} &{}\quad \frac{1}{12} \\ \frac{1}{4} &{}\quad 0 &{}\quad 0&{}\quad \frac{3}{4} \\ \end{array} \right) \end{aligned}$$

Profile 3  $P^{3}$. For $i=1,$ 2,  $P_{i}$: acbd,  $P_{3}$: bacd,  and $P_{4}$: adcb. By Fact 1 applied to b and d,  $\varphi _{4b}(P^{3}) = 0$ and by Fact 1 applied to c and d,  $\varphi _{4c}(P^{3})=0$. By lower invariance,$\varphi _{3c}(P^{3}) = \varphi _{3c}(P^{2}) = 0$ and $\varphi _{3d}(P^{3}) = \varphi _{3d}(P^{2}) = \frac{1}{12}$. By Fact 1 applied to a and b,  $\varphi _{3a}(P^{3}) = 0,$ which implies that $\varphi _{3b}(P^{3}) = \frac{11}{12}$. By strong equal treatment of equals,$\varphi _{1a}(P^{2}) = \varphi _{2a}(P^{2}) = \varphi _{4a}(P^{2})=\frac{1}{3}$. Therefore, $\varphi _{4d}(P^{2}) = \frac{2}{3}$. By strong equal treatment of equals,

$$\begin{aligned} \varphi (P^{3}) = \left( \begin{array}{cccc} \frac{1}{3} &{}\quad \frac{1}{24} &{}\quad \frac{1}{2} &{}\quad \frac{1}{8} \\ \frac{1}{3} &{}\quad \frac{1}{24} &{}\quad \frac{1}{2} &{}\quad \frac{1}{8} \\ 0&{}\quad \frac{11}{12} &{}\quad 0 &{}\quad \frac{1}{12} \\ \frac{1}{3} &{}\quad 0 &{}\quad 0&{}\quad \frac{2}{3} \\ \end{array} \right) \end{aligned}$$

Profile 4  $P^{4}$. For $i=1,$ 2,  3,  $P_{i}$: bacd and $P_{4}$: adcb. By Fact 1 applied to b and d,  $\varphi _{4b}(P^{4}) = 0$ and by Fact 1 applied to c and d,  $\varphi _{4c}(P^{4}) = 0$. By strong equal treatment of equals,$\varphi _{1b}(P^{4}) = \varphi _{2b}(P^{4}) = \varphi _{3b}(P^{4}) = \frac{1}{3}$ and $\varphi _{1c}(P^{4}) = \varphi _{2c}(P^{4}) = \varphi _{3c}(P^{4}) = \frac{1}{3}$. Altogether,

$$\begin{aligned} \varphi (P^{4}) = \left( \begin{array}{cccc} \cdot &{}\quad \frac{1}{3} &{}\quad \frac{1}{3} &{}\quad \cdot \\ \cdot &{}\quad \frac{1}{3} &{}\quad \frac{1}{3} &{}\quad \cdot \\ \cdot &{}\quad \frac{1}{3} &{}\quad \frac{1}{3} &{}\quad \cdot \\ \cdot &{}\quad 0 &{}\quad 0 &{}\quad \cdot \\ \end{array} \right) \end{aligned}$$

Profile 5  $P^{5}$. For $i=1,$ 2,  $P_{i}$: bacd,  $P_{3}$: abcd,  and $P_{4}$: adcb. By Fact 1 applied to b and d,  $\varphi _{4b}(P^{5}) = 0$ and by Fact 1 applied to c and d,  $\varphi _{4c}(P^{5}) = 0$. By lower invariance,$\varphi _{3c}(P^{5}) = \varphi _{3c}(P^{4}) = \frac{1}{3}$. By strong equal treatment of equals,$\varphi _{1c}(P^{5}) = \varphi _{2c}(P^{5}) = \frac{1}{3}$. Altogether,

$$\begin{aligned} \varphi (P^{5}) = \left( \begin{array}{cccc} \cdot &{}\quad \cdot &{}\quad \frac{1}{3} &{}\quad \cdot \\ \cdot &{}\quad \cdot &{}\quad \frac{1}{3} &{}\quad \cdot \\ \cdot &{}\quad \cdot &{}\quad \frac{1}{3} &{}\quad \cdot \\ \cdot &{}\quad 0 &{}\quad 0 &{}\quad \cdot \\ \end{array} \right) \end{aligned}$$

Profile 6  $P^{6}$. For $i=1,$ 2,  3,  $P_{i}$: abcd and $P_{4}$: adcb. By Fact 1 applied to b and d,  $\varphi _{4b}(P^{6}) = 0$ and by Fact 1 applied to c and d,  $\varphi _{4c}(P^{6}) = 0$. By strong equal treatment of equals,$\varphi _{1a}(P^{6}) = \varphi _{2a}(P^{6}) = \varphi _{3a}(P^{6}) = \varphi _{4a}(P^{6}) = \frac{1}{4},$ which implies that $\varphi _{4d}(P^{6})=\frac{3}{4}$. By strong equal treatment of equals,

$$\begin{aligned} \varphi (P^{6}) = \left( \begin{array}{cccc} \frac{1}{4} &{}\quad \frac{1}{3} &{}\quad \frac{1}{3} &{}\quad \frac{1}{12} \\ \frac{1}{4} &{}\quad \frac{1}{3} &{}\quad \frac{1}{3} &{}\quad \frac{1}{12} \\ \frac{1}{4} &{}\quad \frac{1}{3} &{}\quad \frac{1}{3} &{}\quad \frac{1}{12} \\ \frac{1}{4} &{}\quad 0 &{}\quad 0&{}\quad \frac{3}{4} \\ \end{array} \right) \end{aligned}$$

Profile 7  $P^{7}$. For $i=1,$ 2,  $P_{i}$: abcd,  $P_{3}$: bacd,  and $P_{4}$: adcb. By Fact 1 applied to b and d,  $\varphi _{4b}(P^{7}) = 0,$ by Fact 1 applied to c and d,  $\varphi _{4c}(P^{7}) = 0,$ and by Fact 1 applied to a and b,  $\varphi _{3a}(P^{7}) = 0$. By strong equal treatment of equals,$\varphi _{1a}(P^{7}) = \varphi _{2a}(P^{7}) = \varphi _{4a}(P^{7}) = \frac{1}{3}$. Therefore, $\varphi _{4a}(P^{7}) = \frac{2}{3}$. By lower invariance,$\varphi _{3c}(P^{7}) = \varphi _{3c}(P^{6}) = \frac{1}{3}$ and $\varphi _{3d}(P^{7}) = \varphi _{3d}(P^{6}) = \frac{1}{12},$ which implies that $\varphi _{3b}(P^{7}) = \frac{7}{12}$. By strong equal treatment of equals,

$$\begin{aligned} \varphi (P^{7}) = \left( \begin{array}{cccc} \frac{1}{3} &{}\quad \frac{5}{24} &{}\quad \frac{1}{3} &{}\quad \frac{1}{8} \\ \frac{1}{3} &{}\quad \frac{5}{24} &{}\quad \frac{1}{3} &{}\quad \frac{1}{8} \\ 0 &{}\quad \frac{7}{12} &{}\quad \frac{1}{3} &{}\quad \frac{1}{12} \\ \frac{1}{3} &{}\quad 0 &{}\quad 0&{}\quad \frac{2}{3} \\ \end{array} \right) \end{aligned}$$

Profile 7$'$, $P^{7'}$. For $i=1,$ 3,  $P_{i}$: abcd,  $P_{2}$: bacd,  and $P_{4}$: adcb. By the same reasoning as in Profile 7,

$$\begin{aligned} \varphi (P^{7'}) = \left( \begin{array}{cccc} \frac{1}{3} &{}\quad \frac{5}{24} &{}\quad \frac{1}{3} &{}\quad \frac{1}{8} \\ 0 &{}\quad \frac{7}{12} &{}\quad \frac{1}{3} &{}\quad \frac{1}{12} \\ \frac{1}{3} &{}\quad \frac{5}{24} &{}\quad \frac{1}{3} &{}\quad \frac{1}{8} \\ \frac{1}{3} &{}\quad 0 &{}\quad 0&{}\quad \frac{2}{3} \\ \end{array} \right) \end{aligned}$$

Profile 7$''$, $P^{7''}$. $P_{1}$: bacd,  for $i=2,$ 3,  $P_{i}$: abcd,  and $P_{4}$: adcb. By the same reasoning as in Profile 7,

$$\begin{aligned} \varphi (P^{7''}) = \left( \begin{array}{cccc} 0 &{}\quad \frac{7}{12} &{}\quad \frac{1}{3} &{}\quad \frac{1}{12} \\ \frac{1}{3} &{}\quad \frac{5}{24} &{}\quad \frac{1}{3} &{}\quad \frac{1}{8} \\ \frac{1}{3} &{}\quad \frac{5}{24} &{}\quad \frac{1}{3} &{}\quad \frac{1}{8} \\ \frac{1}{3} &{}\quad 0 &{}\quad 0&{}\quad \frac{2}{3} \\ \end{array} \right) \end{aligned}$$

Profile 5  $P^{5}$. For $i=1,$ 2, $P_{i}$: bacd,  $P_{3}$: abcd,  and $P_{4}$: adcb. Now we are ready to fix other elements of $\varphi (P^{5})$. By lower invariance,$\varphi _{1d}(P^{5}) = \varphi _{1d}(P^{7'}) = \frac{1}{8}$ and $\varphi _{2d}(P^{5}) = \varphi _{2d}(P^{7''}) = \frac{1}{8}$. By Fact 1 applied to a and b,  $\varphi _{3b}(P^{5})=0$. By strong equal treatment of equals,$\varphi _{1b}(P^{5}) = \varphi _{2b}(P^{5}) = \frac{1}{2}$. Therefore, $\varphi _{1a}(P^{5}) = \varphi _{2a}(P^{5}) = \frac{1}{24}$. By strong equal treatment of equals,$\varphi _{3a}(P^{5}) = \varphi _{4a}(P^{5}) = \frac{11}{24}$. Altogether,

$$\begin{aligned} \varphi (P^{5}) = \left( \begin{array}{cccc} \cdot &{}\quad \cdot &{}\quad \frac{1}{3} &{}\quad \cdot \\ \cdot &{}\quad \cdot &{}\quad \frac{1}{3} &{}\quad \cdot \\ \cdot &{}\quad \cdot &{}\quad \frac{1}{3} &{}\quad \cdot \\ \cdot &{}\quad 0 &{}\quad 0 &{}\quad \cdot \\ \end{array} \right) \Rightarrow \varphi (P^{5}) = \left( \begin{array}{cccc} \frac{1}{24} &{}\quad \frac{1}{2}&{}\quad \frac{1}{3} &{}\quad \frac{1}{8} \\ \frac{1}{24} &{}\quad \frac{1}{2}&{}\quad \frac{1}{3} &{}\quad \frac{1}{8} \\ \frac{11}{24} &{}\quad 0 &{}\quad \frac{1}{3} &{}\quad \frac{5}{24}\\ \frac{11}{24} &{}\quad 0 &{}\quad 0 &{}\quad \frac{13}{24}\\ \end{array} \right) \end{aligned}$$

Profile 5$'$, $P^{5'}$. For $i=1,$ 3,  $P_{i}$: bacd,  $P_{2}$: abcd,  and $P_{4}$: adcb. By the same reasoning as in Profile 5,

$$\begin{aligned} \varphi (P^{5'}) = \left( \begin{array}{cccc} \frac{1}{24} &{}\quad \frac{1}{2}&{}\quad \frac{1}{3} &{}\quad \frac{1}{8} \\ \frac{11}{24} &{}\quad 0 &{}\quad \frac{1}{3} &{}\quad \frac{5}{24}\\ \frac{1}{24} &{}\quad \frac{1}{2}&{}\quad \frac{1}{3} &{}\quad \frac{1}{8} \\ \frac{11}{24} &{}\quad 0 &{}\quad 0 &{}\quad \frac{13}{24}\\ \end{array} \right) \end{aligned}$$

Profile 8  $P^{8}$. $P_{1}$: abcd,  $P_{2}$: acbd,  $P_{3}$: bacd,  and $P_{4}$: adcb. By Fact 1 applied to b and d,  $\varphi _{4b}(P^{8}) = 0,$ by Fact 1 applied to c and d,  $\varphi _{4c}(P^{8}) = 0,$ and by Fact 1 applied to a and b,  $\varphi _{3a}(P^{8}) = 0$. By strong equal treatment of equals,$\varphi _{1a}(P^{8}) = \varphi _{2a}(P^{8}) = \varphi _{4a}(P^{8}) = \frac{1}{3},$ which implies that $\varphi _{4d}(P^{8}) = \frac{2}{3}$. By lower invariance,$\varphi _{1d}(P^{8}) = \varphi _{1d}(P^{3}) = \frac{1}{8},$$\varphi _{2d}(P^{8}) = \varphi _{2d}(P^{7}) = \frac{1}{8},$ and $\varphi _{3d}(P^{8}) = \varphi _{3d}(P^{2'}) = \frac{1}{12}$. Altogether,

$$\begin{aligned} \varphi (P^{8}) = \left( \begin{array}{cccc} \frac{1}{3} &{}\quad \cdot &{}\quad \cdot &{}\quad \frac{1}{8} \\ \frac{1}{3} &{}\quad \cdot &{}\quad \cdot &{}\quad \frac{1}{8} \\ 0 &{}\quad \cdot &{}\quad \cdot &{}\quad \frac{1}{12}\\ \frac{1}{3} &{}\quad 0 &{}\quad 0 &{}\quad \frac{2}{3} \end{array} \right) \end{aligned}$$

Profile 8$'$, $P^{8'}$. $P_{1}$: bacd,  $P_{2}$: acbd,  $P_{3}$: abcd,  and $P_{4}$: adcb. By the same reasoning as in Profile 8,

$$\begin{aligned} \varphi (P^{8'}) = \left( \begin{array}{cccc} 0 &{}\quad \cdot &{}\quad \cdot &{}\quad \frac{1}{12}\\ \frac{1}{3} &{}\quad \cdot &{}\quad \cdot &{}\quad \frac{1}{8} \\ \frac{1}{3} &{}\quad \cdot &{}\quad \cdot &{}\quad \frac{1}{8} \\ \frac{1}{3} &{}\quad 0 &{}\quad 0 &{}\quad \frac{2}{3} \end{array} \right) \end{aligned}$$

Profile 9  $P^{9}$. For $i=1,$ 3,  $P_{i}$: abcd,  $P_{2}$: acbd,  and $P_{4}$: adcb. By Fact 1 applied to b and d,  $\varphi _{4b}(P^{9}) = 0$ and by Fact 1 applied to c and d,  $\varphi _{4c}(P^{9}) = 0$. By lower invariance,$\varphi _{3d}(P^{9}) = \varphi _{3d}(P^{8}) = \frac{1}{12}$ and $\varphi _{1d}(P^{9}) = \varphi _{1d}(P^{8'}) = \frac{1}{12}$. By strong equal treatment of equals,$\varphi _{1a}(P^{9}) = \varphi _{2a}(P^{9}) = \varphi _{3a}(P^{9}) = \varphi _{4a}(P^{9}) = \frac{1}{4}$. Therefore, $\varphi _{4d}(P^{9}) = \frac{3}{4}$ and $\varphi _{2d}(P^{9}) = \frac{1}{12}$. By Fact 1 applied to b and c,  $\varphi _{2b}(P^{9})=0$. By strong equal treatment of equals,$\varphi _{1b}(P^{9}) = \varphi _{3b}(P^{9}) = \frac{1}{2}$. Altogether,

$$\begin{aligned} \varphi (P^{9}) = \left( \begin{array}{cccc} \frac{1}{4} &{}\quad \frac{1}{2} &{}\quad \frac{1}{6}&{}\quad \frac{1}{12} \\ \frac{1}{4} &{}\quad 0 &{}\quad \frac{2}{3} &{}\quad \frac{1}{12}\\ \frac{1}{4} &{}\quad \frac{1}{2} &{}\quad \frac{1}{6}&{}\quad \frac{1}{12} \\ \frac{1}{4} &{}\quad 0 &{}\quad 0 &{}\quad \frac{3}{4}\\ \end{array} \right) \end{aligned}$$

Profile 10  $P^{10}$. For $i=1,$ 3,  $P_{i}$: bacd,  $P_{2}$: acbd,  and $P_{4}$: adcb. By Fact 1 applied to b and d,  $\varphi _{4b}(P^{10}) = 0$ and by Fact 1 applied to c and d,  $\varphi _{4c}(P^{10}) = 0$. By lower invariance,$\varphi _{1d}(P^{10}) = \varphi _{1d}(P^{8}) = \frac{1}{8},$$\varphi _{3d}(P^{10}) = \varphi _{3d}(P^{8'}) = \frac{1}{8},$ and $\varphi _{2d}(P^{10}) = \varphi _{2d}(P^{5'}) = \frac{5}{24},$ which together imply that $\varphi _{4d}(P^{10}) = \frac{13}{24}$. Therefore, $\varphi _{4a}(P^{10}) = \frac{11}{24}$. By strong equal treatment of equals,$\varphi _{2a}(P^{10}) = \frac{11}{24},$ which implies that $\varphi _{1a}(P^{10}) = \varphi _{3a}(P^{10}) = \frac{1}{24}$. By Fact 1 applied to b and c,  $\varphi _{2b}(P^{10}) = 0$. Therefore, $\varphi _{2c}(P^{10})=\frac{1}{3}$. By strong equal treatment of equals,

$$\begin{aligned} \varphi (P^{10}) = \left( \begin{array}{cccc} \frac{1}{24} &{}\quad \frac{1}{2} &{}\quad \frac{1}{3}&{}\quad \frac{1}{8} \\ \frac{11}{24} &{}\quad 0 &{}\quad \frac{1}{3} &{}\quad \frac{5}{24}\\ \frac{1}{24} &{}\quad \frac{1}{2} &{}\quad \frac{1}{3}&{}\quad \frac{1}{8} \\ \frac{11}{24} &{}\quad 0 &{}\quad 0 &{}\quad \frac{13}{24}\\ \end{array} \right) \end{aligned}$$

Profile 8  $P^{8}$. $P_{1}$: abcd,  $P_{2}$: acbd,  $P_{3}$: bacd,  and $P_{4}$: adcb. By lower invariance,$\varphi _{3c}(P^{8}) = \varphi _{3c}(P^{9}) = \frac{1}{6}$ and $\varphi _{1c}(P^{8}) = \varphi _{1c}(P^{10}) = \frac{1}{3}$. Therefore, $\varphi _{3b}(P^{8}) = \frac{3}{4}$ and $\varphi _{1b}(P^{8}) = \frac{5}{24}$. Also, $\varphi _{2b}(P^{8}) = \frac{1}{24}$ and $\varphi _{2c}(P^{8}) = \frac{1}{2}$. However, by Fact 1 applied to b and c,  either $\varphi _{2b}(P^{8}) = \varphi _{4b}(P^{8}) = 0$ or $\varphi _{1c}(P^{8}) = \varphi _{3c}(P^{8}) = 0$. If not, we can find an allocation which stochastically dominates $\varphi (P^8)$. Therefore, we obtain a contradiction.

$$\begin{aligned} \varphi (P^{8}) = \left( \begin{array}{cccc} \frac{1}{3} &{}\quad \cdot &{}\quad \cdot &{}\quad \frac{1}{8} \\ \frac{1}{3} &{}\quad \cdot &{}\quad \cdot &{}\quad \frac{1}{8} \\ 0 &{}\quad \cdot &{}\quad \cdot &{}\quad \frac{1}{12}\\ \frac{1}{3} &{}\quad 0 &{}\quad 0 &{}\quad \frac{2}{3} \end{array} \right) \Rightarrow \varphi (P^{8}) = \left( \begin{array}{cccc} \frac{1}{3} &{}\quad \frac{5}{24}&{}\quad \frac{1}{3} &{}\quad \frac{1}{8} \\ \frac{1}{3} &{}\quad \frac{1}{24}&{}\quad \frac{1}{2}&{}\quad \frac{1}{8} \\ 0 &{}\quad \frac{3}{4} &{}\quad \frac{1}{6} &{}\quad \frac{1}{12}\\ \frac{1}{3} &{}\quad 0 &{}\quad 0 &{}\quad \frac{2}{3}\\ \end{array} \right) \end{aligned}$$

Now we consider the case when $n > 5$. Let $N = \{1,\ldots ,n\}$ and $A = \{a,b,c,d,o_{5},\ldots ,o_n\}$. We construct preference profiles $P \in \mathcal {P}^N$ such that for each $i \in \{1,2,3,4\},$ the preference ordering on $\{a,b,c,d\}$ is the same as before in the most preferred 4 positions and for each $i \in \{5,\ldots ,n\},$ the most preferred object is $o_i$. By sd-efficiency, for each $i \in \{5,\ldots ,n\},$$\varphi _{i}o_i(P) = 1$. By using a similar argument as before, we have a contradiction. $\square$

Remark 3

It is easy to check the independence of axioms in Theorem 2. The random serial dictator rule satisfies strong equal treatment of equals and lower invariance, but not sd-efficiency. Serial dictator rules satisfy sd-efficiency and lower invariance, but not strong equal treatment of equals. The probabilistic serial rule satisfies sd-efficiency and strong equal treatment of equals, but not lower invariance.

Remark 4

Differently from Theorem 1, the preference relations used in the proof of Theorem 2 does not satisfy single-peakedness. It remains an open question whether the impossibility result of Theorem 2 can be carried over to the single-peaked domain.

Remark 5

A weakening of sd-strategy-proofness,sd-adjacent strategy-proofness (Carroll 2012; Sato 2013; Cho 2016) requires that if one agent changes her preference relation to another adjacent one by swapping two adjacent objects, then the probabilities of obtaining any other objects should not be affected and the probability of obtaining the object with the higher rank in the second preference should be greater. Similarly, we can formulate an adjacent version of uc-strategy-proofness, which applies the uc-strategy-proofness only when two preference relations are adjacent to each other.

uc-adjacent strategy-proofness   For each $P \in \mathcal {P}^{N},$ each $i \in N,$ each $P'_{i} \in {\mathcal {P}},$ and each a,  $b \in A,$ if $P_{i}'$ is adjacent to $P_{i}$ and $U(P_{i},a) = U(P'_{i},b),$ then $\sum _{k \in U(P_{i},a)} \varphi _{ik}(P_{i}, P_{-i}) = \sum _{k \in U(P'_{i},b)} \varphi _{ik}(P'_{i}, P_{-i})$.

It is easy to show that uc-strategy-proofness implies uc-adjacent strategy-proofness, which implies upper invariance and lower invariance. Therefore, by Proposition 1, uc-adjacent strategy-proofness is equivalent to uc-strategy-proofness.⁸