Impossibilities for probabilistic assignment

Abstract

We consider the problem of assigning objects probabilistically among a group of agents who may have multi-unit demands. Each agent has linear preferences over the (set of) objects. The most commonly used extension of preferences to compare probabilistic assignments is by means of stochastic dominance, which leads to corresponding notions of envy-freeness, efficiency, and strategy-proofness. We show that equal treatment of equals, efficiency, and strategy-proofness are incompatible. Moreover, anonymity, neutrality, efficiency, and weak strategy-proofness are incompatible. If we strengthen weak strategy-proofness to weak group strategy-proofness, then when agents have single-unit demands, anonymity, neutrality, efficiency, and weak group strategy-proofness become incompatible.

1 Introduction

We consider the problem of allocating indivisible goods, or objects, among a group of agents who have linear preference relations over the (sets of) objects.¹ The problem has been widely studied in computer science and economics  (Gärdenfors 1973; Svensson 1994, 1999; Young 1995; Abraham et al. 2005; Bouveret et al. 2010). The problem may involve single-unit demands, when each agent receives exactly one object, or multi-unit demands, when each agent receives more than one object. An example of a situation when agents have single-unit demands is when dormitory rooms have to be assigned to new university students (Abdulkadiroğlu and Sönmez 1999; Abraham et al. 2005). The objects could be car-park spaces, kidneys, school seats, etc. A typical example for the case when agents have multi-unit demands is a sport draft, i.e., when non-professional sport players have to be assigned to professional sport teams. Another example is assigning courses to professors in a university department. We assume that each agent receives the same number of objects (Hatfield 2009). This assumption is restrictive and some of the examples mentioned above may not always satisfy it. However, as our results (Theorems  1, 2, and  3) are negative, they hold for any situation that contains the situation we consider.

If the outcome of the problem is deterministic, then it can be inherently unfair. Suppose that agents have single-unit demands. Consider two agents having identical preferences over two objects. Any deterministic allocation will assign one object to one agent and the other object to the other agent. However, such an allocation will violate any reasonable notion of fairness. This difficulty remains when agents have multi-unit demands: consider four objects to be allocated to two agents, each having to receive two, and they have the same strict rankings over pairs of objects. In contrast to the case of single-unit demands, we do not have to assign one of them the set they both most prefer. However, for any deterministic allocation, one agent receives the set less preferred than the set assigned to the other agent. To restore fairness, and as is commonly done in practice, we resort to lotteries over allocations (Hylland and Zeckhauser 1979; Young 1995; Sasaki 1997). Thus, we aim to achieve fairness in a probabilistic sense.

The outcome of a problem is a probabilistic allocation, namely a matrix with rows indexed by agents and columns indexed by objects. Each entry in the matrix specifies the probability of the corresponding object being assigned to the corresponding agent. Each row is the corresponding agent’s probabilistic assignment. For the problem of probabilistic assignment, the earlier work focuses on single-unit demands (Bogomolnaia and Moulin 2001; Katta and Sethuraman 2006). However, as we mentioned earlier, we also consider the case of multi-unit demands (Kojima 2009; Budish et al. 2013; Heo 2014).² The problem of discrete assignment with multi-unit demands has attracted certain attention (Ehlers and Klaus 2003; Hatfield 2009; Bouveret et al. 2010; Bouveret and Lang 2011; Budish 2011).³ A rule is a function which associates with each problem a probabilistic allocation.⁴

When agents express preferences over objects but the outcomes are probabilistic allocations, then we need to extend their preferences over objects to preferences over probabilistic assignments. The most common extension is by means of stochastic dominance: a probabilistic assignment is preferred to another one if and only if the former first-order stochastically dominates the latter.⁵ Note that in general, two assignments may not be related by stochastic dominance. Thus, this relation is not complete. The stochastic dominance relation can be used to define corresponding notions of envy-freeness, efficiency, and strategy-proofness (Bogomolnaia and Moulin 2001; Katta and Sethuraman 2006). Our goal is to investigate which levels of fairness, efficiency, and strategy-proofness can be attained simultaneously.⁶ We assume that preferences are “additive” and comply with von-Neumann-Morgenstern framework, yet we do not know the cardinal utilities nor are we trying to elicit them.⁷ We ask for the least, that is, the ranking over objects. Moreover, additive preferences imply that the standard definition of first-order stochastic dominance applies here as well (by checking the cumulative probabilities over the objects in the upper-contour set for each object). Since our results are negative, they hold for any class of preferences that include additive preferences.

We consider several requirements on rules. A rule satisfies equal treatment of equals if when two agents have the same preference, then they receive the same probabilistic assignment. Next, we require that agents do not “envy” each other. A rule is stochastic dominance envy-free (henceforth sd-envy-free) (Bogomolnaia and Moulin 2001) if for each pair of agents, i and j, agent i’s probabilistic assignment either stochastically dominates agent j’s probabilistic assignment according to agent i’s preference, or the two assignments are the same.⁸ As noted earlier, two assignments may not be related by stochastic dominance. This motivates our next definition. A rule is weakly sd-envy-free (Bogomolnaia and Moulin 2001) if for each pair of agents, i and j, agent j’s assignment does not stochastically dominate agent i’s assignment according to agent i’s preference. We also require rules to satisfy efficiency requirement. A rule is stochastic dominance efficient (henceforth sd-efficient) (Bogomolnaia and Moulin 2001) if it always selects a probabilistic allocation which is not stochastically Pareto dominated by any other probabilistic allocation.⁹

Next, we require that no agent benefits from misrepresenting her preference. A rule is stochastic dominance strategy-proof (henceforth sd-strategy-proof) (Bogomolnaia and Moulin 2001) if for each agent, her probabilistic assignment when telling the truth either stochastically dominates her probabilistic assignment when lying according to her true preference, or the two assignments are the same. Again, because two probabilistic assignments may not be related by stochastic dominance, we consider a weaker definition. A rule is weakly sd-strategy-proof (Bogomolnaia and Moulin 2001) if for each agent, her probabilistic assignment when lying does not stochastically dominate her probabilistic assignment when telling the truth according to her true preference. Finally, we require that no group of agents benefit from misrepresenting their preferences together. A rule is weakly group sd-strategy-proof if for each group of agents and each list of false announcements that agents in the group could make, it is not the case that for each agent in the group, her probabilistic assignment when lying (by the group of agents) stochastically dominates her probabilistic assignment when telling the truth (by the group of agents) according to her true preference.¹⁰

Kojima (2009) investigates the compatibility of fairness, efficiency, and strategy-proofness for the multi-unit demands case. His main result is that no rule is sd-envy-free, sd-efficient, and weakly sd-strategy-proof. Moreover, as he shows, this impossibility holds even under additive preferences and preferences over individual objects are strict.

We add to our understanding of probabilistic assignment by studying the implications of other axiom combinations. First, we weaken sd-envy-freeness to equal treatment of equals, but strengthen weak sd-strategy-proofness to sd-strategy-proofness. We show that, when agents have multi-unit demands, and as soon as there are at least two agents, equal treatment of equals, sd-efficiency, and sd-strategy-proofness are incompatible. As in Kojima (2009), this result holds even under additive preferences with preferences over individual objects being strict. It is worth noting that when agents have single-unit demands, and there are at least four agents, these three axioms are incompatible (Bogomolnaia and Moulin 2001). Their result does not imply ours since our impossibility holds as soon as there are at least two agents.

The above result and Kojima (2009)’s result require comparability of probabilistic assignments.¹¹ Indeed, they require sd-strategy-proofness (not the weak form of it) or sd-envy-freeness (here too, not the weak form of it).¹² In fact, the axioms involving comparability of probabilistic assignments often appear in characterizations or impossibility statements (Bogomolnaia and Moulin 2001; Ehlers and Klaus 2003; Kojima 2009; Bogomolnaia and Heo 2012; Hashimoto et al. 2014; Heo and Yilmaz 2015). Next we ask what happens if we do not require comparability.

We impose two auxiliary properties. A rule is anonymous if the names of agents do not matter, and it is neutral if the names of objects do not matter. Our second result is also negative. When agents have multi-unit demands, and there are at least two agents, anonymity, neutrality, sd-efficiency, and weak sd-strategy-proofness are incompatible. Again this result holds even on the restricted domain of strict and additive preferences. When agents have single-unit demands, these four axioms are compatible, however.

Finally, concerning the four axioms just mentioned, we investigate the implications of strengthening weak sd-strategy-proofness to weak group sd-strategy-proofness. We show that even when agents have single-unit demands, and there are at least four agents, anonymity, neutrality, sd-efficiency, and weak group sd-strategy-proofness are incompatible.

The remainder of the paper is organized as follows. Section  2 presents the model and Section  3 presents the results.

2 The model

Let ${\varvec{O}}$ be a finite set of distinct indivisible goods, or objects. A typical object is denoted by $k\in O$. Let ${\varvec{N}}\equiv \{1,2,\dots ,n\}$ be a set of agents. A typical agent is denoted by $i\in N$. Let ${\varvec{q}}\in \mathbb {Z}$ be such that $q\ge 1$. Each agent is supposed to receive q objects. We assume that $|O|=q|N|$. When $q=1$, we say that agents have single-unit demands. When $q\ge 2$, we say that agents have multi-unit demands. Each agent $i\in N$ has a complete and transitive binary relation ${\varvec{R_i}}$ over sets of objects. We refer to $R_i$ as agent i’s preference relation. Preferences have additive representations, i.e., for each $i\in N$, there is a function $v_{i}:O\rightarrow \mathbb {R}_{+}$ such that for each pair $O^{\prime },O^{\prime \prime }\subseteq O$, $O^{\prime }\,R_i\,O^{\prime \prime }$ if and only if $\sum _{k\in O^{\prime }}v_{i}(k)\ge \sum _{k\in O^{\prime \prime }}v_{i}(k)$ (when an agent receives one object, each of the sets O and $O'$ contains one element).¹³ Furthermore, preferences restricted to individual objects are strict, i.e., for each $i\in N$ and each pair $k,k^{\prime }\in O$ such that $k\ne k^{\prime }$, $v_{i}(k)\ne v_{i}(k^{\prime })$. These restrictions are strong. However, as our results (Theorems 1, 2, and 3) are negative, they are made stronger by the restrictions (our results hold for any domain that contains the domain we consider). Let $\varvec{{\mathcal {R}}}$ be a domain of preferences. Let $R\equiv (R_{i})_{i\in N}$ be the preference profile. Let $\varvec{{\mathcal {R}}^{N}}$ be a domain of preference profiles. Since we vary neither O nor N, we simply write a problem as a list $R\in {\mathcal {R}}^{N}$.

A probabilistic allocation is a $|N|\times |O|$ matrix $M\equiv [M_{ik}]_{i\in N, k\in O}$ such that (1) for each $i\in N$ and each $k\in O$, $0\le M_{ik}\le 1$, (2) for each $i\in N$, $\sum _{k\in O}M_{ik}=q$, and (3) for each $k\in O$, $\sum _{i\in N}M_{ik}=1$. Each entry is interpreted as the probability with which the agent indexing the row receives the object indexing the column. For each $i\in N$, the i-th row of M (i.e., a vector ${M}_{i}\equiv [M_{ik}]_{k\in O}$) represents her probabilistic assignment in M. A probabilistic allocation $M\equiv [M_{ik}]_{i\in N, k\in O}$ is called a deterministic allocation if for each $i\in N$ and each $k\in O$, $M_{ik}\in \{0,1\}$.

Every probabilistic allocation can be written as a convex combination of deterministic allocations (this is a straightforward generalization of the Birkhoff-von Neumann theorem; see Kojima and Manea 2010).¹⁴ Let $\varvec{{\mathcal {M}}}$ be the set of all probabilistic allocations. A rule is a function which associates with each problem a matrix in ${\mathcal {M}}$. The generic rule is denoted $\varphi$.

For simplicity, hereafter we simply call a probabilistic allocation an allocation and a probabilistic assignment an assignment.

We consider several requirements on rules. Again, let $\varphi$ be an arbitrary rule.

First, if the names of agents are permuted, the rule should permute the rows of the allocation it selects in the same way (in short, the names of agents should not matter). Formally, let $\pi$ be a bijection from N to itself. Let $\varPi ^{N}$ be a class of such bijections. Given $\pi \in \varPi ^{N}$ and $R\in {\mathcal {R}}^{N}$, we write $\pi (R)$ for the preference profile $(R_{\pi (1)},R_{\pi (2)},...,R_{\pi (n)})\,$. Similarly, given $\pi \in \varPi ^{N}$ and $M\in {\mathcal {M}}$, we write $\pi (M)$ for the list $(M_{\pi (1)},M_{\pi (2)},...,M_{\pi (n)})\,$.

Anonymity: For each $R\in {\mathcal {R}}^{N}$ and each $\pi \in \varPi ^{N}$, $\varphi (\pi (R))=\pi (\varphi (R))$.

Second, if the names of objects are permuted, the rule should permute the columns of the chosen allocation in the same way (in short, the names of objects should not matter). Formally, let $\overline{\pi }$ be a bijection from O to itself. Let $\overline{\varPi }^{O}$ be a class of such bijections. Given $\overline{\pi }\in \overline{\varPi }^{O}$ and $O^{\prime }\equiv \{a^{\prime },b^{\prime },\dots \}\subseteq O$, we write $\overline{\pi }(O^{\prime })$ for the set $\{\overline{\pi }(a^{\prime }),\overline{\pi }(b^{\prime }),\dots \}$. Given $\overline{\pi }\in \overline{\varPi }^{O}$, we write $\overline{\pi }(R)$ for the preference profile such that for each agent $i\in N$, $R_{i}$ is permuted according to $\overline{\pi }$, i.e., for each pair $O^{\prime },O^{\prime \prime }\subseteq O$, $O^{\prime }\,R_i\,O^{\prime \prime }$ if and only if $\overline{\pi }(O^{\prime })\,R_i\,\overline{\pi }(O^{\prime \prime })$. Similarly, given $\overline{\pi }\in \overline{\varPi }^{O}$ and $M\in {\mathcal {M}}$, we write $\overline{\pi }(M)$ for the list $(M_{\overline{\pi }(a)},M_{\overline{\pi }(b)},...)\,$.

Neutrality: For each $R\in {\mathcal {R}}^{N}$, and each $\overline{\pi }\in \overline{\varPi }^{O}$, $\varphi (\overline{\pi }(R))=\overline{\pi }(\varphi (R))$.

Third, agents with the same preferences should receive the same assignment.

Equal treatment of equals: For each $R\in {\mathcal {R}}^{N}$ and each pair $i,j\in N$, if $R_{i}=R_{j}$, then $\varphi _{i}(R)=\varphi _{j}(R)$.

Note that anonymity implies equal treatment of equals.

Next, we define how an agent compares her assignment to another agent’s assignment. An assignment ${\varvec{M}}_{i}\equiv [M_{ik}]_{k\in O}$ for $i\in N$ weakly stochastically dominates an assignment ${\varvec{M}} _{j}\equiv [M_{jk}]_{k\in O}$ for $j\in N$ at ${\varvec{R}}_{i}$ (or $M_i$ is at least as sd-desirable as $M_j$ at $R_i$), which we write ${\varvec{M}}_{i}\varvec{\mathrel {R^{sd}_i}}{\varvec{M}}_{j}$, if for each $k\in O$, $\sum _{\{x\in O:v_{i}(x)\ge v_{i}(k)\}} M_{ix}\ge \sum _{\{x\in O:v_{i}(x)\ge v_{i}(k)\}} M_{jx}$. If strict inequality holds for some k, then $\varvec{M_i}$ stochastically dominates $\varvec{M_j}$ at ${\varvec{R_i}}$ (or $M_i$ is sd-better than $M_j$ at $R_i$), which we write ${\varvec{M}}_{i}\varvec{\mathrel {P^{sd}_i}}{\varvec{M}}_{j}$. Note that two different assignments $M_i$ and $M_j$ may not be comparable in the stochastic dominance sense.

An allocation M is stochastic dominance envy-free (simply, sd-envy-free) at R if for each pair $i,j\in N$, $M_{i}\mathrel {R^{sd}_i}M_{j}$. At an sd-envy-free allocation, each agent finds her assignment at least as sd-desirable as anyone else’s assignment. Thus it requires comparability of the assignments. The next requirement says that the rule should always select an sd-envy-free allocation.

Stochastic dominance envy-freeness, (simply, sd-envy-freeness): For each $R\in {\mathcal {R}}^{N}$, $\varphi (R)$ is sd-envy-free at R.

Instead of insisting that two agents’ assignments be comparable, the next axiom only requires the rule to select an allocation such that no agent finds some other agent’s assignment sd-better than her own assignment. An allocation M is weakly stochastic dominance envy-free (simply, weakly sd-envy-free) at R if there are no $i,j\in N$ such that $M_{j}\mathrel {P^{sd}_i}M_{i}$.

Weak stochastic dominance envy-freeness, (simply, weak sd-envy-freeness): For each $R\in {\mathcal {R}}^{N}$, $\varphi (R)$ is weakly sd-envy-free at R.

How an agent compares two of her assignments is defined similarly. An assignment ${\varvec{M}}_{i}\equiv [M_{ik}]_{k\in O}$ for $i\in N$ weakly stochastically dominates another assignment ${\varvec{M}} _{i}^{\prime }\equiv [M_{ik}^{\prime }]_{k\in O}$ for $i\in N$ at ${\varvec{R}}_{i}$ (or $M_i$ is at least as sd-desirable as $M_i^{\prime }$ at $R_i$), which we write ${\varvec{M}}_{i}\varvec{\mathrel {R^{sd}_i}}{\varvec{M}}_{i}^{\prime }$, if for each $k\in O$, $\sum _{\{x\in O:v_{i}(x)\ge v_{i}(k)\}} M_{ix}\ge \sum _{\{x\in O:v_{i}(x)\ge v_{i}(k)\}} M_{ix}^{\prime }$. If strict inequality holds for some k, then $\varvec{M_i}$ stochastically dominates $\varvec{M_i^{\prime }}$ at ${\varvec{R_i}}$ (or $M_i$ is sd-better than $M_i^{\prime }$ at $R_i$), which we write ${\varvec{M}}_{i}\varvec{\mathrel {P^{sd}_i}}{\varvec{M}}_{i}^{\prime }$. An allocation ${\varvec{M}}\equiv [M_{ik}]_{i\in N,k\in O}$ stochastically Pareto dominates another allocation ${\varvec{M}} ^{\prime }\equiv [M_{ik}^{\prime }]_{i\in N,k\in O}$ at ${\varvec{R}}$, which we write ${\varvec{M}}\varvec{~\mathrel {R^{sd}}~}{\varvec{M}}^{\prime }$, if (1) for each $i\in N$, $M_{i}\mathrel {R^{sd}_i}M_{i}^{\prime }$, and (2) for some $i\in N$, $M_{i}\mathrel {P^{sd}_i}M_{i}^{\prime }$.

An allocation M is stochastic dominance efficient (simply, sd-efficient) at R if there is no $M^{\prime }\in {\mathcal {M}}$ such that $M^{\prime }\mathrel {R^{sd}}M$. The next requirement says that the rule should always select an sd-efficient allocation.

Stochastic dominance efficiency, (simply, sd-efficiency): For each $R\in {\mathcal {R}}^{N}$, $\varphi (R)$ is sd-efficient at R.

Next, consider an arbitrary agent, say agent i, and fix the other agents’ preferences. The next axiom requires the rule to select an allocation such that according to her true preference, her assignment when she tell the truth is at least as sd-desirable as her assignment when she lies.

Stochastic dominance strategy-proofness, (simply, sd-strategy-proofness): For each $R\in {\mathcal {R}}^{N}$, each $i\in N$, and each $R_{i}^{\prime } \in {\mathcal {R}}$, $\varphi _{i}(R)\mathrel {R^{sd}_i}\varphi _{i}(R_{i}^{\prime },R_{-i})$.¹⁵

Again, consider an arbitrary agent, say agent i, and fix the other agents’ preferences. In the previous axiom, we insist that two assignments (when telling the truth and lying) be comparable. The next axiom only requires the rule to select an allocation such that according to agent i’s true preference, she never finds her assignment when she lies, to be sd-better than her assignment when she tells the truth.

Weak stochastic dominance strategy-proofness, (simply, weak sd-strategy-proofness): For each $R\in {\mathcal {R}}^{N}$, each $i\in N$, and each $R_{i}^{\prime } \in {\mathcal {R}}$, it is not the case that $\varphi _{i}(R_{i}^{\prime },R_{-i} )~\mathrel {P^{sd}_i}~\varphi _{i}(R)$.

Finally, consider an arbitrary group of agents, say group S, and fix the other agents’ preferences. As in the previous axiom, we do not insist on two assignments (when telling the truth and lying) to be comparable. The next axiom requires the rule to select an allocation such that according to the true preferences of each of the agents in S, it is not the case that the agent finds her assignment when agents in S lie, to be sd-better than her assignment when agents in S tell the truth.

Weak group stochastic dominance strategy-proofness, (simply, weak group sd-strategy-proofness): For each $R\in {\mathcal {R}}^{N}$, each $S\subseteq N$, each $i\in S$, and each $R_{S}^{\prime } \in {\mathcal {R}}^S$, it is not the case that for each $i\in S$, $\varphi _{i}(R_{S}^{\prime },R_{-S} )~\mathrel {P^{sd}_i}~\varphi _{i}(R)$.¹⁶

3 Results

We present three results.

First, we investigate the compatibility of equal treatment of equals, sd-efficiency, and sd-strategy-proofness. When agents have single-unit demands, and there are at least four agents, Bogomolnaia and Moulin (2001) [Theorem 2, p.310] show that these three axioms are incompatible. Our first theorem states that, when agents have multi-unit demands, they are again incompatible —but here, the result holds as soon as there are two or more agents and even when preferences have additive representations.¹⁷

Theorem 1

For $n\ge 2$ and $q\ge 2$, no rule satisfies equal treatment of equals, sd-efficiency, and sd-strategy-proofness.

Proof

Let $N\equiv \{1,2\}$, $O\equiv \{a,b,c,d\}$ and $q=2$. Suppose by way of contradiction that there exists a rule $\varphi$ that satisfies the three axioms.

Step 1: Let $(R_1,R_2)\in {\mathcal {R}}^{N}$ be the following:¹⁸

$$\begin{aligned} R_1:&\quad a,b,c,d\\ R_2:&\quad a,b,c,d. \end{aligned}$$

By equal treatment of equals,

Step 2: Let $(R_1,R_2^{\prime })\in {\mathcal {R}}^{N}$ be the following:

$$\begin{aligned} R_1:&\quad a,b,c,d\\ R'_2:&\quad b,a,c,d. \end{aligned}$$

We claim that

By sd-strategy-proofness and Step 1,

• (i) If agent 2’s true preference is $R_{2}$, but she announces $R_{2}^{\prime }$, then

  $$\begin{aligned} \varphi _{2a}(R_{1},R_{2})= & {} \frac{1}{2}\ge \varphi _{2a}\left( R_{1} ,R_{2}^{\prime }\right) ,\\ \sum _{k\in \{a,b\}}\varphi _{2k}(R_{1},R_{2})= & {} 1\ge \sum _{k\in \{a,b\}}\varphi _{2k}\left( R_{1},R_{2}^{\prime }\right) ,\quad \text {and} \\ \sum _{k\in \{a,b,c\}}\varphi _{2k}(R_{1},R_{2})= & {} \frac{3}{2}\ge \sum _{k\in \{a,b,c\}}\varphi _{2k}\left( R_{1},R_{2}^{\prime }\right) . \end{aligned}$$

• (ii) If agent 2’s true preference is $R_{2}^{\prime }$, but she announces $R_{2}$, then

  $$\begin{aligned} \varphi _{2b}(R_{1},R_{2})= & {} \frac{1}{2}\le \varphi _{2b}\left( R_{1} ,R_{2}^{\prime }\right) , \\ \sum _{k\in \{b,a\}}\varphi _{2k}(R_{1},R_{2})= & {} 1\le \sum _{k\in \{b,a\}}\varphi _{2k}\left( R_{1},R_{2}^{\prime }\right) ,\quad \text {and} \\ \sum _{k\in \{b,a,c\}}\varphi _{2k}(R_{1},R_{2})= & {} \frac{3}{2}\le \sum _{k\in \{b,a,c\}}\varphi _{2k}\left( R_{1},R_{2}^{\prime }\right) . \end{aligned}$$

Thus, $\sum _{k\in \{a,b\}}\varphi _{2k}(R_{1},R_{2}^{\prime })=1$ and $\sum _{k\in \{a,b,c\}}\varphi _{2k}(R_{1},R_{2}^{\prime })=\frac{3}{2}$.

Hence,

Then $\varphi _{1a}(R_1,R_2')+\varphi _{1b}(R_1,R_2')=\varphi _{2a}(R_1,R_2') +\varphi _{2b}(R_1,R_2')=1$. By sd-efficiency, $\varphi _{1a}(R_1,R_2')=\varphi _{2b}(R_1,R_2')=1$. Thus, the claim is true.

Step 3: Let $(R_1^{\prime },R_2^{\prime })\in {\mathcal {R}}^{N}$ be the following:

$$\begin{aligned} R'_1:&\quad a,c,b,d\\ R'_2:&\quad b,a,c,d. \end{aligned}$$

We claim that

By sd-strategy-proofness and Step 2,

• (i) If agent 1’s true preference is $R_{1}$, but she announces $R_{1}^{\prime }$, then

  $$\begin{aligned} \varphi _{1a}\left( R_{1},R_{2}^{\prime }\right)= & {} 1\ge \varphi _{1a}\left( R_{1}^{\prime } ,R_{2}^{\prime }\right) , \\ \sum _{k\in \{a,b\}}\varphi _{1k}\left( R_{1},R_{2}^{\prime }\right)= & {} 1\ge \sum _{k\in \{a,b\}}\varphi _{1k}\left( R_{1}^{\prime },R_{2}^{\prime }\right) ,\quad \text {and} \\ \sum _{k\in \{a,b,c\}}\varphi _{1k}\left( R_{1},R_{2}^{\prime }\right)= & {} \frac{3}{2}\ge \sum _{k\in \{a,b,c\}}\varphi _{1k}\left( R_{1}^{\prime },R_{2}^{\prime }\right) . \end{aligned}$$

• (ii) If agent 1’s true preference is $R_{1}^{\prime }$, but she announces $R_{1}$, then

  $$\begin{aligned} \varphi _{1a}(R_{1},R_{2}^{\prime })= & {} 1\le \varphi _{1a}\left( R_{1}^{\prime } ,R_{2}^{\prime }\right) , \\ \sum _{k\in \{a,c\}}\varphi _{1k}\left( R_{1},R_{2}^{\prime }\right)= & {} \frac{3}{2}\le \sum _{k\in \{a,c\}}\varphi _{1k}\left( R_{1}^{\prime },R_{2}^{\prime }\right) ,\quad \text {and} \\ \sum _{k\in \{a,c,b\}}\varphi _{1k}\left( R_{1},R_{2}^{\prime }\right)= & {} \frac{3}{2}\le \sum _{k\in \{a,c,b\}}\varphi _{1k}\left( R_{1}^{\prime },R_{2}^{\prime }\right) . \end{aligned}$$

Thus, $\varphi _{1a}(R_{1}^{\prime },R_{2}^{\prime })=1$ and $\sum _{k\in \{a,b,c\}}\varphi _{1k}(R_{1}^{\prime },R_{2}^{\prime })=\frac{3}{2}$.

Hence,

By (i), $\sum _{k\in \{a,b\}}\varphi _{1k}(R'_1,R_2')\le 1$. Then, $\varphi _{1b}(R_{1}^{\prime },R_{2}^{\prime })=0$. Therefore, the claim is true.

Step 4: Let $(R_1^{\prime },R_2)\in {\mathcal {R}}^{N}$ be the following:

$$\begin{aligned} R'_1:&\quad a,c,b,d\\ R_2:&\quad a,b,c,d. \end{aligned}$$

We claim that

By sd-strategy-proofness and Step 3,

• (i) If agent 2’s true preference is $R_{2}^{\prime }$, but she announces $R_{2}$, then

  $$\begin{aligned} \varphi _{2b}\left( R_{1}^{\prime },R_{2}^{\prime }\right)= & {} 1\ge \varphi _{2b}\left( R_{1}^{\prime } ,R_{2}\right) , \\ \sum _{k\in \{b,a\}}\varphi _{2k}\left( R_{1}^{\prime },R_{2}^{\prime }\right)= & {} 1\ge \sum _{k\in \{b,a\}}\varphi _{2k}\left( R_{1}^{\prime },R_{2}\right) ,\quad \text {and} \\ \sum _{k\in \{b,a,c\}}\varphi _{2k}\left( R_{1}^{\prime },R_{2}^{\prime }\right)= & {} \frac{3}{2}\ge \sum _{k\in \{b,a,c\}}\varphi _{2k}\left( R_{1}^{\prime },R_{2}\right) . \end{aligned}$$

• (ii) If agent 2’s true preference is $R_{2}$, but she announces $R_{2}^{\prime }$, then

  $$\begin{aligned} \varphi _{2a}\left( R_{1}^{\prime },R_{2}^{\prime }\right)= & {} 0\le \varphi _{2a}(R_{1}^{\prime } ,R_{2}), \\ \sum _{k\in \{a,b\}}\varphi _{2k}\left( R_{1}^{\prime },R_{2}^{\prime }\right)= & {} 1\le \sum _{k\in \{a,b\}}\varphi _{2k}\left( R_{1}^{\prime },R_{2}\right) ,\quad \text {and} \\ \sum _{k\in \{a,b,c\}}\varphi _{2k}\left( R_{1}^{\prime },R_{2}^{\prime }\right)= & {} \frac{3}{2}\le \sum _{k\in \{a,b,c\}}\varphi _{2k}\left( R_{1}^{\prime },R_{2}\right) . \end{aligned}$$

Thus, $\sum _{k\in \{a,b\}}\varphi _{2k}(R_{1}^{\prime },R_{2})=1$ and $\sum _{k\in \{a,b,c\}}\varphi _{2k}(R_{1}^{\prime },R_{2})=\frac{3}{2}$.

Hence,

By sd-strategy-proofness and Step 1,

• (i) If agent 1’s true preference is $R_{1}$, but she announces $R_{1}^{\prime }$, then $\varphi _{1a}(R_{1},R_{2})=\frac{1}{2}\ge \varphi _{1a}(R_{1}^{\prime },R_{2})$.

• (ii) If agent 1’s true preference is $R_{1}^{\prime }$, but she announces $R_{1}$, then $\varphi _{1a}(R_{1},R_{2})=\frac{1}{2}\le \varphi _{1a}(R_{1}^{\prime },R_{2})$.

Thus, $\varphi _{1a}(R_{1}^{\prime },R_{2})=\frac{1}{2}$. Therefore, the claim is true.

Step 5:

in violation of sd-efficiency.

For $n>2$, we let each agent receives two objects from among the set of objects $\{a,b,c,d, o_5,o_6,\ldots , o_{2n}\}$. For each new agent $i\in \{3,\ldots , n\}$, her top two objects are $o_{2i-1}, o_{2i}$ and for each existing agent $i\in ~\{1,2\}$, her top four objects are a, b, c, d. By sd-efficiency, each agent $i\in \{3,\ldots , n\}$ is assigned the probability 1 for both objects $o_{2i-1}$ and $o_{2i}$. For $q>2$, we add new objects as bottom objects for the existing agents and each agent receives a equal fraction of these objects at the bottom of the preference lists. $\square$

Theorem 1 is tight. The serial rule (Bogomolnaia and Moulin 2001; Kojima 2009) satisfies all the properties but sd-strategy-proofness.¹⁹

The random priority rule (Abdulkadiroğlu and Sönmez 1998; Kojima 2009) satisfies all the properties but sd-efficiency.²⁰

Let ${\mathcal {O}}^{N}$ be the set of strict orders on N. For each $\prec \in {\mathcal {O}}^{N}$, the priority rule associated with $\prec$ is defined as follows: for each $R\in {\mathcal {R}}^{N}$, each agent selects her q best objects among the remaining ones according to the order $\prec$. This rule satisfies all the properties but equal treatment of equals.²¹

A related result is that of Zhou (1990) who proved that when each agent receives at most one object, there exist no rule that satisfies “equal treatment of equals,” “ex-ante efficiency,” and “strategy-proofness.” The result is for $n\ge 3$ and concerns cardinal rules that elicit von-Neumann-Morgenstern utilities.

Second, we investigate the compatibility of anonymity, neutrality, sd-efficiency, and weak sd-strategy-proofness. Notice that these four axioms do not require comparability of assignments. When agents have single-unit demands, they are compatible.²² However, our next theorem states that, when agents have multi-unit demands, they become incompatible.

Theorem 2

For $n\ge 2$ and $q\ge 2$, no rule satisfies anonymity, neutrality, sd-efficiency, and weak sd-strategy-proofness.

Proof

Let $N\equiv \{1,2\}$, $O\equiv \{a,b,c,d\}$ and $q=2$. Suppose by way of contradiction that there exists a rule $\varphi$ that satisfies the four axioms.

Step 1: Let $R\equiv (R_1,R_2)\in {\mathcal {R}}^{N}$ be the following:

$$\begin{aligned} R_1:&\quad a,b,c,d\\ R_2:&\quad b,a,c,d. \end{aligned}$$

We claim that

Let $(\widetilde{R}_1,\widetilde{R}_2)\in {\mathcal {R}}^{N}$ be the following:

$$\begin{aligned} \widetilde{R}_1:&\quad b,a,c,d\\ \widetilde{R}_2:&\quad a,b,c,d. \end{aligned}$$

By neutrality ($a\rightarrow b$, $b\rightarrow a$, $c\rightarrow c$, $d\rightarrow d$),

$$\begin{aligned} \varphi (\widetilde{R}_{1},\widetilde{R}_{2})= \begin{pmatrix} \varphi _{1b}(R)&{}\quad \varphi _{1a}(R)&{}\quad \varphi _{1c}(R)&{}\quad \varphi _{1d}(R)\\ \varphi _{2b}(R)&{}\quad \varphi _{2a}(R)&{}\quad \varphi _{2c}(R)&{}\quad \varphi _{2d}(R) \end{pmatrix}. \end{aligned}$$

By anonymity,

$$\begin{aligned} \varphi (R_1,R_2)= \begin{pmatrix} \varphi _{2b}(R)&{}\quad \varphi _{2a}(R)&{}\quad \varphi _{2c}(R)&{}\quad \varphi _{2d}(R)\\ \varphi _{1b}(R)&{}\quad \varphi _{1a}(R)&{}\quad \varphi _{1c}(R)&{}\quad \varphi _{1d}(R) \end{pmatrix}. \end{aligned}$$

Thus, $\varphi _{1c}(R)=\varphi _{2c}(R)$ and $\varphi _{1d}(R)=\varphi _{2d}(R)$.

Since $\varphi _{1c}(R)+\varphi _{2c}(R)=1$, $\varphi _{1c} (R)=\varphi _{2c}(R)=\frac{1}{2}$.

Similarly, since $\varphi _{1d}(R)+\varphi _{2d}(R)=1$, $\varphi _{1d} (R)=\varphi _{2d}(R)=\frac{1}{2}$.

Therefore,

Then $\varphi _{1a}(R)+\varphi _{1b}(R)=\varphi _{2a}(R)+\varphi _{2b}(R)~=~1$. By sd-efficiency, $\varphi _{1a}(R)=\varphi _{2b}(R)~=~1$. Thus, the claim is true.

Step 2: Let $(R'_1,R'_2)\in {\mathcal {R}}^{N}$ be the following:

$$\begin{aligned} R'_1:&\quad b,a,c,d\\ R'_2:&\quad b,c,a,d. \end{aligned}$$

By an argument similar to that used to prove Step 1, anonymity, neutrality, and sd-efficiency imply that

Step 3: Consider the profile $(R_1,R'_2)\in {\mathcal {R}}^{N}$. First, we claim that

$$\begin{aligned} \sum _{k\in \{a,b,c\}}\varphi _{1k}(R_{1},R'_2)>\frac{3}{2}. \end{aligned}$$

(1)

If $\sum _{k\in \{a,b,c\}}\varphi _{1k}(R_{1},R'_2)<\frac{3}{2}$, then by Step 2,

$$\begin{aligned} \varphi _{1a}\left( R'_{1},R'_{2}\right)= & {} 1\ge \varphi _{1a}\left( R_{1} ,R_{2}^{\prime }\right) , \\ \sum _{k\in \{a,b\}}\varphi _{1k}\left( R'_{1},R'_{2}\right)= & {} \frac{3}{2}>\sum _{k\in \{a,b\}}\varphi _{1k}\left( R_{1},R_{2}^{\prime }\right) , \\ \sum _{k\in \{a,b,c\}}\varphi _{1k}\left( R'_{1},R'_{2}\right)= & {} \frac{3}{2}>\sum _{k\in \{a,b,c\}}\varphi _{1k}\left( R_{1},R_{2}^{\prime }\right) ,\quad \text {and} \\ \sum _{k\in \{a,b,c,d\}}\varphi _{1k}\left( R'_{1},R'_{2}\right)= & {} 2\ge \sum _{k\in \{a,b,c,d\}}\varphi _{1k}\left( R_{1},R_{2}^{\prime }\right) . \end{aligned}$$

But then (given that agent 2 announces $\mathrel {R'_2}$), if $R_{1}$ is agent 1’s true preference, she is sd-better off by announcing $R'_{1}$, i.e., $\varphi _{1}(R'_{1},R'_{2})\mathrel {P^{sd}_{1}}\varphi _{1}(R_{1},R'_{2})$, a contradiction to $\varphi$ being weakly sd-strategy-proof.

If $\sum _{k\in \{a,b,c\}}\varphi _{1k}(R_{1},R'_2)=\frac{3}{2}$, then $\varphi _{1a}(R_{1},R'_2)=1$, $\varphi _{1b}(R_{1},R'_2)=\frac{1}{2}$, and $\varphi _{1c}(R_{1},R'_2)=0$, otherwise $\varphi _{1}(R'_{1},R'_{2})\mathrel {P^{sd}_{1}}\varphi _{1}(R_{1},R'_{2})$, a contradiction to $\varphi$ being weakly sd-strategy-proof. Thus, $\varphi _{2a}(R_{1},R'_2)=0$, $\varphi _{2b}(R_{1},R'_2)=\frac{1}{2}$, and $\varphi _{2c}(R_{1},R'_2)~=~1$. But then, by Step 1,

$$\begin{aligned} \varphi _{2b}(R_{1},R_{2})= & {} 1>\varphi _{2b}(R_{1} ,R_{2}^{\prime })=\frac{1}{2}, \\ \sum _{k\in \{b,c\}}\varphi _{2k}(R_{1},R_{2})= & {} \frac{3}{2}\ge \sum _{k\in \{b,c\}}\varphi _{2k}(R_{1},R_{2}^{\prime })=\frac{3}{2}, \\ \sum _{k\in \{b,c,a\}}\varphi _{2k}(R_{1},R_{2})= & {} \frac{3}{2}\ge \sum _{k\in \{b,c,a\}}\varphi _{2k}(R_{1},R_{2}^{\prime })=\frac{3}{2},\quad \text {and} \\ \sum _{k\in \{b,c,a,d\}}\varphi _{2k}(R_{1},R_{2})= & {} 2\ge \sum _{k\in \{b,c,a,d\}}\varphi _{2k}(R_{1},R_{2}^{\prime })=2. \end{aligned}$$

Now (given that agent 1 announces $\mathrel {R_1}$), if $R'_{2}$ is agent 2’s true preference, she is sd-better off by announcing $R_{2}$, i.e., $\varphi _{2}(R_{1},R_{2})\mathrel {P'^{sd}_{2}}\varphi _{2}(R_{1},R'_{2})$, a contradiction to $\varphi$ being weakly sd-strategy-proof.

Therefore, (1) is true.

Next we claim that

$$\begin{aligned} \sum _{k\in \{b,c,a\}}\varphi _{2k}(R_{1},R'_2)>\frac{3}{2}. \end{aligned}$$

(2)

By an argument similar to that used to prove (1), if $\sum _{k\in \{b,c,a\}}\varphi _{2k}(R_{1},R'_2)<\frac{3}{2}$, then by Step 1, if $R'_{2}$ is agent 2’s true preference, she is sd-better off by announcing $R_{2}$, i.e., $\varphi _{2}(R_{1},R_{2})\mathrel {P'^{sd}_{2}}\varphi _{2}(R_{1},R'_{2})$, a contradiction to $\varphi$ being weakly sd-strategy-proof.

If $\sum _{k\in \{b,c,a\}}\varphi _{2k}(R_{1},R'_2)=\frac{3}{2}$, then $\varphi _{2b}(R_{1},R'_2)=1$, $\varphi _{2c}(R_{1},R'_2)=\frac{1}{2}$, and $\varphi _{2a}(R_{1},R'_2)=0$, otherwise $\varphi _{2}(R_{1},R_{2})\mathrel {P'^{sd}_{2}}\varphi _{2}(R_{1},R'_{2})$, a contradiction to $\varphi$ being weakly sd-strategy-proof. Thus, $\varphi _{1a}(R_{1},R'_2)=1$, $\varphi _{1b}(R_{1},R'_2)=0$, and $\varphi _{1c}(R_{1},R'_2)~=~\frac{1}{2}$. But then, by Step 2, $\varphi _{1}(R'_{1},R'_{2})\mathrel {P^{sd}_{1}}\varphi _{1}(R_{1},R'_{2})$, a contradiction to $\varphi$ being weakly sd-strategy-proof.

Therefore, (2) is true. By (1) and (2),

$$\begin{aligned} \sum _{k\in \{a,b,c\}}\varphi _{1k}(R_{1},R'_2)+\sum _{k\in \{b,c,a\}} \varphi _{2k}(R_{1},R'_2)>3. \end{aligned}$$

But this is impossible since $\sum _{k\in \{a,b,c\}}\varphi _{1k}(R_{1},R'_2)+\sum _{k\in \{b,c,a\}}\varphi _{2k}(R_{1},R'_2)= \sum _{i\in \{1,2\}}\varphi _{ia}(R_{1},R'_2)+\sum _{i\in \{1,2\}}\varphi _{ib}(R_{1},R'_2)+\sum _{i\in \{1,2\}}\varphi _{ic}(R_{1},R'_2)=3$. Hence if a rule is anonymous, neutral, and sd-efficient, then it cannot be weakly sd-strategy-proof.

The above argument can be extended to an arbitrary number of agents when each agent requires two objects from among $a,b,c,d, o_5,o_6,\ldots , o_{2n}$. For each new agent $i\in \{3,\ldots , n\}$, her top two objects are $o_{2i-1}, o_{2i}$ and for each existing agent $i\in ~\{1,2\}$, her top four objects are a, b, c, d. By sd-efficiency, each agent $i\in \{3,\ldots , n\}$ is assigned the probability 1 for both objects $o_{2i-1}$ and $o_{2i}$. Similarly, the argument for $q=2$ can also be extended to the case $q>2$. One can add more objects to the bottom of the preference lists of both agents and each agent receives a equal fraction of these objects at the bottom of the preference lists. $\square$

The serial rule satisfies all the properties of Theorem  2 but weak sd-strategy-proofness.²³ The random priority rule satisfies all the properties but sd-efficiency. For each $\prec \in {\mathcal {O}}^{N}$, the priority rule associated with $\prec$ satisfies all the properties but anonymity. We do not know whether a rule can be anonymous, sd-efficient, weakly sd-strategy-proof but not neutral.²⁴ Our current proof relies on the combination of anonymity and neutrality.

Theorem 2 differs from Kojima (2009)’s result [Theorem 1, p.139] in that sd-envy-freeness is replaced by anonymity and neutrality. Obviously, anonymity and neutrality together do not imply sd-envy-freeness. Thus, Kojima (2009)’s result and our result (Theorem 2) are not directly related. In fact, we show that anonymity and neutrality together do not even imply weak sd-envy-freeness. Consider the “Reverse random priority rule ($RP^{r}$),” described as follows: (1) for each order on the set of agents, let each agent choose her q worst objects among the remaining ones when her turn comes; and (2) place equal probabilities on the allocations obtained for all possible orders. Obviously, this rule satisfies anonymity and neutrality. However, the following example shows that it violates weak sd-envy-freeness.

Let $N\equiv \{1,2\}$ and $O\equiv \{a,b,c,d\}$. Let $(R_1,R_2)\in {\mathcal {R}}^{N}$ be the following:

$$\begin{aligned} R_1:&\quad a,b,c,d\\ R_2:&\quad b,d,c,a. \end{aligned}$$

Then,

But then, $RP_{2}^{r}(R_{1},R_{2})~\mathrel {P^{sd}_1}~RP_{1}^{r}(R_{1},R_{2} )$, in violation of weak sd-envy-freeness.

Finally, we further consider the list of axioms in Theorem 2 and ask what happens if we strengthen weak sd-strategy-proofness to weak group sd-strategy-proofness. Note that as for Theorem 2, these four axioms do not require comparability of assignments. Our finding is that even when agents have single-unit demands, if there are at least four agents, anonymity, neutrality, sd-efficiency, and weak group sd-strategy-proofness are incompatible. The proof of Theorem 2 can be extended by cloning agents 1 and 2 to prove the following statement.

Theorem 3

For $n\ge 4$ and $q\ge 1$, no rule satisfies anonymity, neutrality, sd-efficiency, and weak group sd-strategy-proofness.

Proof

Let $N\equiv \{1,2,3,4\}$, $O\equiv \{a,b,c,d\}$ and $q=1$. Suppose by way of contradiction that there exists a rule $\varphi$ that satisfies the four axioms.

Step 1: Let $R\equiv (R_1,R_2,R_3,R_4)\in {\mathcal {R}}^{N}$ be the following:

$$\begin{aligned} R_1,R_2:&\quad a,b,c,d\\ R_3,R_4:&\quad b,a,c,d. \end{aligned}$$

We claim that

By anonimity,

$$\begin{aligned} \varphi (R_1,R_2,R_3,R_4)= \begin{pmatrix} \varphi _{1a}(R)&{}\quad \varphi _{1b}(R)&{}\quad \varphi _{1c}(R)&{}\quad \varphi _{1d}(R)\\ \varphi _{1a}(R)&{}\quad \varphi _{1b}(R)&{}\quad \varphi _{1c}(R)&{}\quad \varphi _{1d}(R)\\ \varphi _{3a}(R)&{}\quad \varphi _{3b}(R)&{}\quad \varphi _{3c}(R)&{}\quad \varphi _{3d}(R)\\ \varphi _{3a}(R)&{}\quad \varphi _{3b}(R)&{}\quad \varphi _{3c}(R)&{}\quad \varphi _{3d}(R) \end{pmatrix}. \end{aligned}$$

Let $(\widetilde{R}_1,\widetilde{R}_2,\widetilde{R}_3,\widetilde{R}_4)\in {\mathcal {R}}^{N}$ be the following:

$$\begin{aligned} \widetilde{R}_1,\widetilde{R}_2:&\quad b,a,c,d\\ \widetilde{R}_3,\widetilde{R}_4:&\quad a,b,c,d. \end{aligned}$$

By neutrality ($a\rightarrow b$, $b\rightarrow a$, $c\rightarrow c$, $d\rightarrow d$),

$$\begin{aligned} \varphi (\widetilde{R}_1,\widetilde{R}_2,\widetilde{R}_3,\widetilde{R}_4)= \begin{pmatrix} \varphi _{1b}(R)&{}\quad \varphi _{1a}(R)&{}\quad \varphi _{1c}(R)&{}\quad \varphi _{1d}(R)\\ \varphi _{1b}(R)&{}\quad \varphi _{1a}(R)&{}\quad \varphi _{1c}(R)&{}\quad \varphi _{1d}(R)\\ \varphi _{3b}(R)&{}\quad \varphi _{3a}(R)&{}\quad \varphi _{3c}(R)&{}\quad \varphi _{3d}(R)\\ \varphi _{3b}(R)&{}\quad \varphi _{3a}(R)&{}\quad \varphi _{3c}(R)&{}\quad \varphi _{3d}(R) \end{pmatrix}. \end{aligned}$$

By anonymity ($1\rightarrow 3$, $2\rightarrow 4$, $3\rightarrow 1$, $4\rightarrow 2$),

$$\begin{aligned}\varphi (R_1,R_2,R_3,R_4)= \begin{pmatrix} \varphi _{3b}(R)&{}\quad \varphi _{3a}(R)&{}\quad \varphi _{3c}(R)&{}\quad \varphi _{3d}(R)\\ \varphi _{3b}(R)&{}\quad \varphi _{3a}(R)&{}\quad \varphi _{3c}(R)&{}\quad \varphi _{3d}(R)\\ \varphi _{1b}(R)&{}\quad \varphi _{1a}(R)&{}\quad \varphi _{1c}(R)&{}\quad \varphi _{1d}(R)\\ \varphi _{1b}(R)&{}\quad \varphi _{1a}(R)&{}\quad \varphi _{1c}(R)&{}\quad \varphi _{1d}(R) \end{pmatrix}. \end{aligned}$$

Thus, for each $k\in \{c,d\}$, $\varphi _{1k}(R)=\varphi _{2k}(R)=\varphi _{3k}(R)=\varphi _{4k}(R)$. Since for each $k\in \{c,d\}$, $\varphi _{1k}(R)+\varphi _{2k}(R)+\varphi _{3k}(R)+\varphi _{4k}(R)=1$, we have for each $k\in \{c,d\}$, $\varphi _{1k}(R)=\varphi _{2k}(R)=\varphi _{3k}(R)=\varphi _{4k}(R)=\frac{1}{4}$.

Therefore,

Then by sd-efficiency, $\varphi _{1a}(R)=\frac{1}{2}$ and $\varphi _{3b}(R)=\frac{1}{2}$. Thus, the claim is true.

Step 2: Let $(R'_1,R'_2,R'_3,R'_4)\in {\mathcal {R}}^{N}$ be the following:

$$\begin{aligned} R'_1, R'_2:&\quad b,a,c,d\\ R'_3, R'_4:&\quad b,c,a,d. \end{aligned}$$

By an argument similar to that used to prove Step 1, anonymity, neutrality, and sd-efficiency imply that

Step 3: Consider the profile $(R_1,R_2,R'_3,R'_4)\in {\mathcal {R}}^{N}$.

By anonymity, for each $k\in \{a,b,c,d\}$,

$$\begin{aligned} \varphi _{1k}(R_1,R_2,R'_3,R'_4)=\varphi _{2k}(R_1,R_2,R'_3,R'_4)\le ~\frac{1}{2} \end{aligned}$$

(3)

and

$$\begin{aligned} \varphi _{3k}(R_1,R_2,R'_3,R'_4)=\varphi _{4k}(R_1,R_2,R'_3,R'_4)\le ~\frac{1}{2}. \end{aligned}$$

(4)

Next, we claim that

$$\begin{aligned} \sum _{k\in \{a,b,c\}}\varphi _{1k}(R_1,R_2,R'_3,R'_4)= \sum _{k\in \{a,b,c\}}\varphi _{2k}(R_1,R_2,R'_3,R'_4)>\frac{3}{4}. \end{aligned}$$

(5)

The first equality is true by (3).

If $\sum _{k\in \{a,b,c\}}\varphi _{1k}(R_1,R_2,R'_3,R'_4)<\frac{3}{4}$, then by Step 2 and (3), for each $i\in \{1,2\}$,

$$\begin{aligned} \varphi _{ia}\left( R'_1,R'_2,R'_3,R'_4\right)= & {} \frac{1}{2}\ge \varphi _{ia}\left( R_1,R_2,R'_3,R'_4\right) , \\ \sum _{k\in \{a,b\}}\varphi _{ik}\left( R'_1,R'_2,R'_3,R'_4\right)= & {} \frac{3}{4}>\sum _{k\in \{a,b\}}\varphi _{ik}\left( R_1,R_2,R'_3,R'_4\right) , \\ \sum _{k\in \{a,b,c\}}\varphi _{ik}\left( R'_1,R'_2,R'_3,R'_4\right)= & {} \frac{3}{4}>\sum _{k\in \{a,b,c\}}\varphi _{ik}\left( R_1,R_2,R'_3,R'_4\right) ,\quad \text {and} \\ \sum _{k\in \{a,b,c,d\}}\varphi _{ik}\left( R'_1,R'_2,R'_3,R'_4\right)= & {} 1\ge \sum _{k\in \{a,b,c,d\}}\varphi _{ik}\left( R_1,R_2,R'_3,R'_4\right) . \end{aligned}$$

Then (given that agents 3 and 4 announce $\mathrel {R'_3}$ and $\mathrel {R'_4}$ respectively), if $R_{1}$ and $R_{2}$ are respectively agents 1’s and 2’s true preferences, they are sd-better off by announcing $R'_{1}$ and $R'_{2}$, i.e., for each $i\in \{1,2\}$, $\varphi _{i}(R'_1,R'_2,R'_3,R'_4)\mathrel {P^{sd}_{i}}\varphi _{i}(R_1,R_2,R'_3,R'_4)$, a contradiction to $\varphi$ being weakly group sd-strategy-proof.

If $\sum _{k\in \{a,b,c\}}\varphi _{1k}(R_1,R_2,R'_3,R'_4)=\frac{3}{4}$, then for each $i\in \{1,2\}$, $\varphi _{ia}(R_1,R_2,R'_3,R'_4)=\frac{1}{2}$, $\varphi _{ib}(R_1,R_2,R'_3,R'_4)=\frac{1}{4}$, and $\varphi _{ic}(R_1,R_2,R'_3,R'_4)=0$,²⁵ otherwise for each $i\in \{1,2\}$, $\varphi _{i}(R'_1,R'_2,R'_3,R'_4)\mathrel {P^{sd}_{i}}\varphi _{i}(R_1,R_2,R'_3,R'_4)$, a contradiction to $\varphi$ being weakly group sd-strategy-proof. Thus, for each $i\in \{3,4\}$, $\varphi _{ia}(R_1,R_2,R'_3,R'_4)=0$, $\varphi _{ib}(R_1,R_2,R'_3,R'_4)=\frac{1}{4}$, and $\varphi _{ic}(R_1,R_2,R'_3,R'_4)=\frac{1}{2}$. But then, by Step 1, (given that agents 1 and 2 announce $\mathrel {R_1}$ and $\mathrel {R_2}$ respectively), if $R'_{3}$ and $R'_{4}$ are respectively agents 3’s and 4’s true preferences, they are sd-better off by announcing $R_{3}$ and $R_{4}$, i.e., for each $i\in \{3,4\}$, $\varphi _{i}(R_1,R_2,R_3,R_4)\mathrel {{P'^{sd}_{i}}}\varphi _{i}(R_1,R_2,R'_3,R'_4)$, a contradiction to $\varphi$ being weakly group sd-strategy-proof.

Therefore, (5) is true.

Next we claim that

$$\begin{aligned} \sum _{k\in \{b,c,a\}}\varphi _{3k}(R_1,R_2,R'_3,R'_4) =\sum _{k\in \{b,c,a\}}\varphi _{4k}(R_1,R_2,R'_3,R'_4)>\frac{3}{4}. \end{aligned}$$

(6)

The first equality is true by (4). By an argument similar to that used to prove (5), if $\sum _{k\in \{b,c,a\}}\varphi _{3k}(R_1,R_2,R'_3,R'_4)<\frac{3}{4}$, then by Step 1 and (4), if $R'_{3}$ and $R'_{4}$ are respectively agents 3’s and 4’s true preferences, they are sd-better off by announcing $R_{3}$ and $R_{4}$, i.e., for each $i\in \{3,4\}$, $\varphi _{i}(R_1,R_2,R_3,R_4)\mathrel {{P'^{sd}_{i}}}\varphi _{i}(R_1,R_2,R'_3,R'_4)$, a contradiction to $\varphi$ being weakly group sd-strategy-proof.

If $\sum _{k\in \{a,b,c\}}\varphi _{3k}(R_1,R_2,R'_3,R'_4)=\frac{3}{4}$, then for each $i\in \{3,4\}$, $\varphi _{ib}(R_1,R_2,R'_3,R'_4)=\frac{1}{2}$, $\varphi _{ic}(R_1,R_2,R'_3,R'_4)=\frac{1}{4}$, and $\varphi _{ia}(R_1,R_2,R'_3,R'_4)=0$, otherwise for each $i\in \{3,4\}$, $\varphi _{i}(R_1,R_2,R_3,R_4)\mathrel {{P'^{sd}_{i}}}\varphi _{i}(R_1,R_2,R'_3,R'_4)$, a contradiction to $\varphi$ being weakly group sd-strategy-proof. Thus, for each $i\in \{1,2\}$, $\varphi _{ia}(R_1,R_2,R'_3,R'_4)=\frac{1}{2}$, $\varphi _{ib}(R_1,R_2,R'_3,R'_4)=0$, and $\varphi _{ic}(R_1,R_2,R'_3,R'_4)=\frac{1}{4}$. But then, by Step 2, for each $i\in \{1,2\}$, $\varphi _{i}(R'_1,R'_2,R'_3,R'_4)\mathrel {P^{sd}_{i}}\varphi _{i}(R_1,R_2,R'_3,R'_4)$, a contradiction to $\varphi$ being weakly group sd-strategy-proof.

Therefore, (6) is true. By (5) and (6),

$$\begin{aligned} \sum _{k\in \{a,b,c\}}\sum _{i\in \{1,2\}}\varphi _{ik}(R_1,R_2,R'_3,R'_4) +\sum _{k\in \{b,c,a\}}\sum _{i\in \{3,4\}}\varphi _{ik}(R_1,R_2,R'_3,R'_4)>3. \end{aligned}$$

But this is impossible since the left hand side is equal to $\sum _{i\in \{1,2,3,4\}}\varphi _{ia}(R_1,R_2,R'_3,R'_4)+\sum _{i\in \{1,2,3,4\}}\varphi _{ib}(R_1,R_2,R'_3,R'_4)+\sum _{i\in \{1,2,3,4\}}\varphi _{ic}(R_1,R_2,R'_3,R'_4)=3$. Hence if a rule is anonymous, neutral, and sd-efficient, then it cannot be weakly group sd-strategy-proof.

By an argument similar to that used to prove Theorem 2, we can extend the proof to arbitrary number of agents and objects. $\square$