Binary mechanism for the allocation problem with single-dipped preferences

Abstract

In this study, we consider the problem of fairly allocating a fixed amount of a perfectly divisible resource among agents with single-dipped preferences. It is known that any efficient and strategy-proof rule violates several fairness requirements. We alternatively propose a simple and natural mechanism, in which each agent announces only whether he or she demands a resource and the resource is divided equally among the agents who demand it. We show that any Nash equilibrium allocation of our mechanism belongs to the equal-division core. In addition, we show that our mechanism is Cournot stable. In other words, from any message profile, any path of better-replies converges to a Nash equilibrium.

1 Introduction

We consider the problem of fairly allocating a fixed amount of a perfectly divisible resource among agents with single-dipped preferences. An agent’s preference relationship is said to be single-dipped if there is a least preferred amount, called a dip, and his or her welfare increases as the allotment moves away from the dip in either direction.

While Klaus et al. (1997) and Klaus (2001) provided several examples of this problem, we introduce another economically meaningful instance. This problem is closely related to the common-pool resource allocation problem under increasing returns to scale.¹ Consider the situation where no more than a certain amount of fish can be caught from a lake to sustain the ecosystem of the lake. When each fisher’s fixed cost of catching fish is sufficiently large and his or her marginal cost is sufficiently small, his or her total cost function is concave. When the total amount of fish that can be caught is fixed, no fisher can influence the price of the fish, so that his or her revenue function is linear. In this situation, each fisher’s profit function is convex, so he or she has a single-dipped preference over the amount of fish he or she catches.

In the literature of mechanism design, strategy-proofness, which requires that no agent can benefit from misrepresenting his or her true preference, is a key concept. Klaus et al. (1997) and Klaus (2001) showed that any strategy-proof and Pareto efficient rule must allocate the whole resource to one agent. Therefore, such a rule violates several fairness requirements, such as envy-freeness, anonymity, and equal-division lower boundedness. ² Ehlers (2002) extended the deterministic model by allowing the use of probabilistic rules. He characterized all probabilistic rules satisfying strategy-proofness, Pareto efficiency, and envy-freeness.

When it is shown that designing a strategy-proof, efficient and fair rule is impossible, implementation in Nash equilibria is often considered. Doghmi (2013a) showed that in this problem, Maskin monotonicity is a necessary and sufficient condition for Nash implementation and examined the Nash implementability of several solutions.³ However, which mechanism should be used in practice remains an open question, because Doghmi’s (2013a) results are derived from indirectly utilizing Maskin’s (1999) canonical mechanism, whose message space is quite large and has some unnatural features.⁴

In this study, we propose a simple and natural mechanism for this problem. In our mechanism, each agent announces only whether he or she demands a resource. If some agents do, then the resource is divided equally among the agents who demand it; otherwise, the resource is equally divided among all agents. We call this mechanism the binary mechanism.

We confirm the existence of Nash equilibria of the binary mechanism, and then show that in the binary mechanism, (1) if there are at least three agents, then any Nash equilibrium allocation is weakly Pareto efficient and (2) if there are at least four agents, then any Nash equilibrium allocation belongs to the equal-division core.⁵ In addition, we show that the solution implemented by the binary mechanism satisfies equal-division lower boundedness and anonymity.

While these properties of Nash equilibrium allocations might be attractive, the use of Nash equilibrium as an equilibrium concept usually requires the assumption that all agents are fully rational and have complete information about the game being played. In response, we show that the set of Nash equilibria of the strategic form game associated with the binary mechanism is stable in the sense of Cournot–Nash equilibrium. In other words, starting from any message profile, any path of better-replies converges to the set of Nash equilibria. This stability property ensures that myopic learning process based on better-replies to the other agents’ messages results in choosing a Nash equilibrium, even if we do not assume complete information or full rationality of agents.

The remainder of this paper is organized as follows. Section 2 introduces notation and definitions. Section 3 proposes several properties of solutions and notes the difficulties associated with Nash implementation. Section 4 investigates the performance of the binary mechanism. Section 5 shows that the Nash equilibria of the binary mechanism are Cournot stable. Section 6 concludes the study. Some proofs are relegated to the Appendix.

2 Basic definitions

We consider the problem of allocating one unit of an infinitely divisible and non-disposal resource among a set $N=\left\{ 1,...,n\right\}$ of agents. Let $A=\left\{ (x_{1},...,x_{n})\in {\mathbb {R}} _{+}^{n}\text { }|\text { }\sum \nolimits _{i\in N}x_{i}=1\right\}$ be the set of allocations. For each $i\in N$ and each $x=(x_{1},...,x_{n})\in A$, we call $x_{i}$ the allotment of agent i at x. For each $S\subseteq N,$ $\left| S\right|$ denotes the cardinality of the set $S\$ and $\ x^{S}$ denotes the allocation such that (1) if $S\ne \phi ,$ then for each $i\in S,$ $x_{i}^{S}=\frac{1}{\left| S\right| }$ and for each $i\notin S,$ $x_{i}^{S}=0$ and (2) if $S=\phi ,$ then $\ x^{S}=(\frac{1}{\left| N\right| },...,\frac{1}{\left| N\right| })$.

Each agent $i\in N$ has a complete and transitive preference $R_{i}$ over the interval $\left[ 0,1\right]$, whose symmetric and asymmetric parts are denoted by $I_{i}$ and $P_{i}$, respectively. A preference $R_{i}$ is single-dipped if there is $d(R_{i})\in \left[ 0,1\right]$, called i’s dip, such that for each pair $a,b\in \left[ 0,1\right]$, $a<b\le d(R_{i})$ or $a>b\ge d(R_{i})$ implies $a\,P_{i}\,b$. Let ${\mathcal {R}}$ be the set of all single-dipped preferences and ${\mathcal {R}}^{N}=\underset{i\in N}{\prod }{\mathcal {R}}$ be the set of all single-dipped preference profiles.

A solution is a mapping $F:{\mathcal {R}}^{N}\rightarrow 2^{A}\backslash \left\{ \phi \right\}$ that associates with each preference profile $R\in {\mathcal {R}}^{N}$ a non-empty subset of allocations $F(R)\subseteq A.$ These allocations are interpreted as socially desirable allocations for R.

A mechanism is a pair $\Gamma =(\left( M_{i}\right) _{i\in N},g),$ where ${M}_{i}$ denotes agent i’s message space, and $g: \underset{i\in N}{\prod }M_{i}\rightarrow A$ denotes the outcome function that associates with each message profile $m\equiv \left( m_{i}\right) _{i\in N}\in M\equiv$ $\underset{i\in N}{\prod }M_{i}$ an allocation $g(m)\in A$. A message profile $m\in M$ is a Nash equilibrium of $\Gamma$ for R if, for each $i\in N$ and each $m_{i}^{^{\prime }}\in M_{i}$, $g_{i}(m)\,R_{i}\,g_{i}(m_{i}^{^{\prime }},m_{-i})$. Let $NE(\Gamma ,R)$ be the set of Nash equilibria of $\Gamma$ for R and

$$\begin{aligned} NE_{A}(\Gamma ,R)=\left\{ g(m)\in A\text { }|\text { }m\in NE(\Gamma ,R)\right\} \end{aligned}$$

be the set of Nash equilibrium allocations of $\Gamma$ for R. A mechanism $\Gamma$ Nash implements a solution F, if, for each $R\in {\mathcal {R}}^{N}$, $F(R)=NE_{A}(\Gamma ,R).$

A rule is a single-valued solution $f:{\mathcal {R}}^{N}\rightarrow A$ . A rule is strategy-proof if for each $i\in N$, each $R_{i},R_{i}^{\prime }\in {\mathcal {R}}$, and each $R_{-i}\in \underset{j\in N\backslash \left\{ i\right\} }{\prod }{\mathcal {R}}$, $\ f_{i}(R_{i},R_{-i})\,R_{i}\,f_{i}(R_{i}^{\prime },R_{-i})$. A rule is group strategy-proof if for each $S\subseteq N$ and each $R\in {\mathcal {R}}^{N}$, there is no $R_{S}^{\prime }\in \underset{i\in S}{ \prod }{\mathcal {R}}$ such that for each $i\in S,\ f_{i}(R_{S}^{\prime },R_{N\backslash S})\,R_{i}\,f_{i}(R_{S}^{\prime },R_{N\backslash S})$ and for some $j\in S,\ f_{j}(R_{S}^{\prime },R_{N\backslash S})\,P_{j}\,f_{j}(R_{S}^{\prime },R_{N\backslash S}).$

3 Axioms

We introduce several properties of solutions as axioms. The first two axioms refer to efficiency.

Definition 1

An allocation $x\in A$ is strongly Pareto efficient for $R\in {\mathcal {R}}^{N}$ if there is no $y\in A$ such that for each $i\in N,$ $y_{i}\,R_{i}\,x_{i}$, and for some $j\in N,$ $y_{j}\,P_{j}\,x_{j}$. Let SP(R) denote the set of strongly Pareto efficient allocations for R. A solution F satisfies strong Pareto efficiency if for each $R\in {\mathcal {R}}^{N}$, $F(R)\subseteq SP(R)$ .

Definition 2

An allocation $x\in A$ is weakly Pareto efficient for $R\in {\mathcal {R}}^{N}$ if there is no $y\in A$ such that for each $i\in N,$ $y_{i}\,P_{i}\,x_{i}$. Let WP(R) denote the set of weakly Pareto efficient allocations for R. A solution F satisfies weak Pareto efficiency if, for each $R\in {\mathcal {R}}^{N}$, $F(R)\subseteq WP(R)$.

Following this, we introduce several axioms having to do with fairness.⁶ The simplest way to achieve fairness is to allocate the resource equally among all agents. However, the equal division $x^{N}=(\frac{1}{\left| N\right| },..., \frac{1}{\left| N\right| })\in A$ might not be desirable from the perspective of weak Pareto efficiency. We then treat equal division as a reference point. The following axiom requires that each agent’s allotment should be at least as desirable as equal division.

Definition 3

An allocation $x\in A$ satisfies the equal-division lower bound for $R\in {\mathcal {R}}^{N}$ if for each $i\in N$, $x_{i}\,R_{i}\,\frac{1}{\left| N\right| }$. Let ELB(R) denote the set of allocations meeting the equal-division lower bound for R . A solution F satisfies equal-division lower boundedness if for each $R\in {\mathcal {R}}^{N}$, $F(R)\subseteq ELB(R)$.

Equal-division lower boundedness can be generalized by permitting reallocation of the resource among coalitions. The following axiom requires that no coalition can make each of its members better off by reallocating among themselves the resource allotted to them at equal division.

Definition 4

An allocation $x\in A$ belongs to the equal-division core for $R\in {\mathcal {R}}^{N}$ if there is no $S\subseteq N$ and $y\in A$ such that (1)$\ \sum \nolimits _{i\in S}y_{i}=\frac{\left| S\right| }{\left| N\right| }$ and (2) for each $i\in S,\ y_{i}\,P_{i}\,x_{i}$. Let EC(R) denote the set of equal-division core allocations for R. A solution F satisfies the equal-division core property if for each $R\in {\mathcal {R}}^{N},$ $F(R)\subseteq EC(R).$

We define two alternative axioms pertaining to fairness. The following axiom requests that the set of socially desirable allocations should be independent of the names of agents.

Definition 5

A solution F satisfies anonymity if for each $R\in {\mathcal {R}}^{N}$, and each permutation $\pi$ of N, if $x\in F(R)$, then $(x_{\pi (1)},\ldots ,x_{\pi (n)})\in F(R_{\pi (1)},\ldots ,R_{\pi (n)}).$

The following axiom is a well-known property of fair allocation: each agent’s allotment is at least as desirable as any other agent’s allotment.

Definition 6

An allocation $x\in A$ is envy-free for $R\in {\mathcal {R}}^{N}$ if for each $i,j\in N$, $x_{i}\,R_{i}\,x_{j}$. Let EF(R) denote the set of envy-free allocations for R. A solution F satisfies envy-freeness if for each $R\in {\mathcal {R}}^{N}$, $F(R)\subseteq EF(R)$.

Finally, we define an axiom of implementability. A solution F is Nash implementable if there is a mechanism $\Gamma$ such that for each $R\in {\mathcal {R}}^{N}$, $NE_{A}(\Gamma ,R)=F(R).$Maskin (1999) showed that any Nash-implementable solution satisfies Maskin monotonicity. Before introducing the axiom formally, we introduce the following notation. For each $\ R\in {\mathcal {R}}$, and each $a\in \left[ 0,1\right] ,$ let $L(R,a)=\left\{ b\in \left[ 0,1\right] \text { }|\text { }a\,R\,b\right\}$ be the set of points of $\left[ 0,1\right]$ which are less desirable than or at least as desirable as a at R.

Definition 7

A solution F satisfies Maskin monotonicity if for each pair R,  ${\overline{R}}\in {\mathcal {R}}^{N},$ and each $x\in F(R),$ if for each $i\in N,$ $L({\overline{R}}_{i},x_{i})\supseteq L(R_{i},x_{i}),$ then $x\in F({\overline{R}}).$

There are several fundamental difficulties in implementing an efficient and fair solution in the allocation problem with single-dipped preferences.

Remark 1

Doghmi and Ziad (2013) pointed out that the strong Pareto solution does not satisfy Maskin monotonicity. As a corollary of their result, it is shown that if there are at least two agents, then any solution satisfying strong Pareto efficiency does not satisfy Maskin monotonicity, and thus it is not Nash implementable. In other words, if F is Nash implementable, then there is $R\in {\mathcal {R}}^{N}$ be such that $F(R)\nsubseteq SP(R).$ See Appendix for details.

Remark 2

Weak Pareto efficiency is not compatible with envy-freeness. In other words, there is $R\in {\mathcal {R}}^{N}$ such that $WP(R)\cap EF(R)=\phi .$ See Appendix for details.

Remark 3

Klaus et al. (1997) and Klaus (2001) show that no (group) strategy-proof and weak Pareto efficient rule satisfies equal-division lower boundedness, equal-division core property, anonymity, or envy-freeness.

4 The binary mechanism

Faced with the difficulties noted in Remarks 1, 2 and 3, our second-best goal is to design a mechanism that Nash implements a solution satisfying weak Pareto efficiency, equal-division lower boundedness, equal-division core property, and anonymity. We propose the following mechanism.

The binary mechanism, $\Gamma _{B}.$ For each $i\in N,$ $M_{i}=\left\{ 0,1\right\}$, and for each $m\in \underset{i\in N}{\prod } M_{i}$, $g(m)=x^{\left\{ i\in N\text { }|m_{i}=1\right\} }.$

Since $M_{i}$ contains only two messages, the binary mechanism is bounded (Jackson 1992).⁷ Also, it is natural in the sense that each agent’s message consists only of an economically meaningful announcement (Saijo et al. 1996, 1999). For each $i\in N,\ m_{i}=1$ can be interpreted as if agent i demands the resource and $m_{i}=0$ as if agent i does not demand the resource. When some agents demand a resource, then $\Gamma _{B}$ allocates the resource equally among the agents who demand it. When no agent demands the resource, then $\Gamma _{B}$ allocates the resource equally among all agents.

The basic structure of the binary mechanism is similar to Yamamura’s (2016) mechanism for the problem of locating a public facility over a street when agents’ preferences are single-dipped. According to Yamamura’s (2016) mechanism each agent announces only whether he or she wants to move the location in a certain direction or not, and the location is chosen according to the set of agents who want it.

We first identify the set of Nash equilibria of the binary mechanism. For each $S\subseteq N,$ let $\ m^{S}$ $\in \underset{i\in N}{\prod }M_{i}$ be such that for each $i\in S,$ $m_{i}^{S}=1$ and for each $i\notin S,$ $m_{i}^{S}=0.$ Notice that for each $m^{S}\in \underset{i\in N}{\prod } M_{i}$, each agent’s allotment is either $\frac{1}{\left| S\right| }$ or 0. Hence, capturing the set of agents who prefer $\ \frac{1}{ \left| S\right| }$ to 0 is crucially important to identify the set of Nash equilibria. We then introduce the following notation. For each $k\in \left\{ 0,1,...,n,n+1\right\}$, and each $R\in {\mathcal {R}}^{N},$ define $N_{k}(R),N_{k}^{\prime }(R)\subseteq N$ as follows.

$$\begin{aligned} N_{k}(R)=\left\{ \begin{array}{cc} N &{} \text {if }k=0 \\ \left\{ i\in N\text { }|\text { }1\,P_{i}\,\frac{1}{n}\right\} &{} \text {if }k=1\\ \left\{ i\in N\text { }|\text { }\frac{1}{k}\,P_{i}\,0\right\} &{} \text {if } 2\le k\le n \\ \phi &{} \text {if }k=n+1, \end{array} \right. \\ N_{k}^{\prime }(R)=\left\{ \begin{array}{cc} N &{} \text {if }k=0 \\ \left\{ i\in N\text { }|\text { }1\,R_{i}\,\frac{1}{n}\right\} &{} \text {if }k=1 \\ \left\{ i\in N\text { }|\text { }\frac{1}{k}\,R_{i}\,0\right\} &{} \text {if } 2\le k\le n \\ \phi &{} \text {if }k=n+1. \end{array} \right. \end{aligned}$$

Intuitively, $N_{k}(R)$ denotes the set of agents who like to be allocated the resource when k agents demand the resource, and $N_{k}^{\prime }(R)$ denotes the set of agents who do not dislike to be allocated the resource when k agents demand the resource.

Note that by the definitions of $N_{k}(R)$ and $N_{k}^{\prime }(R)$, for each $\ k,k^{\prime }\in \left\{ 0,1,...,n,n+1\right\}$, such that $k>k^{\prime }$, we have

$$\begin{aligned} N_{k}(R)\subseteq N_{k}^{\prime }(R)\subseteq N_{k^{\prime }}(R)\subseteq N_{k^{\prime }}^{\prime }(R). \end{aligned}$$

Theorem 1

For each $R\in {\mathcal {R}}^{N},$ and each $S\subseteq N$ , $m^{S}\in NE(\Gamma _{B},R)$ if and only if $N_{\left| S\right| +1}(R)\subseteq S\subseteq N_{\left| S\right| }^{^{\prime }}(R).$

Proof

See Appendix.■

Theorem 1 identifies agents’ behavior in Nash equilibria. It states that at a Nash equilibrium $m_{S}$ of the binary mechanism (1) all members of $N_{\left| S\right| +1}$ announce $m_{i}=1$, (2) all members of $N\backslash N_{\left| S\right| }^{^{\prime }}$ announce $m_{i}=0$, (3) $\left| S\right| -\left| N_{\left| S\right| +1}(R)\right|$ members of $N_{\left| S\right| }^{^{\prime }}(R)\backslash N_{\left| S\right| +1}(R)$ announce $m_{i}=1$, and (4) $\left| N_{\left| S\right| }^{^{\prime }}(R)\right| -\left| S\right|$ members of $N_{\left| S\right| }^{^{\prime }}(R)\backslash N_{\left| S\right| +1}(R)$ announce $m_{i}=0.$ As a corollary of Theorem 1, we know the number of agents who receive the resource at a Nash equilibrium of the binary mechanism. For each $R\in {\mathcal {R}}^{N},$ define $k^{*}\in \left\{ 0,1,\ldots ,n\right\}$ as

$$\begin{aligned} k^{*}\equiv \max \left\{ k\in \left\{ 0,1,\ldots ,n\right\} \text { }| \text {\ }\left| N_{k}(R)\right| \ge k\right\}.\end{aligned}$$

⁸The following proposition states that the number of agents who receive the resource at a Nash equilibrium is either $k^{*}$ or $k^{*}+1$.

Proposition 1

• (1) For each $R\in {\mathcal {R}}^{N},$ there is $m^{S}\in NE(\Gamma _{B},R)$ such that $\left| S\right| =k^{*}.$

• (2) For each $R\in {\mathcal {R}}^{N},$ if $m^{S}\in NE(\Gamma _{B},R)$ , then $\left| S\right| =k^{*}$ or $k^{*}+1.$

Proof

First, we show that for each $R\in R^{N},$ there is $m^{S}\in NE(\Gamma _{B},R)$ such that $\left| S\right| =k^{*}.$ For each $R\in {\mathcal {R}}^{N},$ since $\left| N_{k^{*}}(R)\right| \ge k^{*}$, $\left| N_{k^{*}+1}(R)\right| <k^{*}+1$, and $N_{k^{*}+1}(R)\subseteq N_{k^{*}}(R)$, there is $S\subseteq N$ such that $\left| S\right| =k^{*}$ and

$$\begin{aligned} N_{k^{*}+1}(R)\subseteq S\subseteq N_{k^{*}}(R)\subseteq N_{k^{*}}^{\prime }(R). \end{aligned}$$

Hence, by Theorem 1, $m^{S}\in NE(\Gamma _{B},R).$

Next, we show that for each $R\in R^{N},$ if $m^{S}\in NE(\Gamma _{B},R)$, then $\left| S\right| =k^{*}$ or $k^{*}+1.$ If $\left| S\right| \le k^{*}-1,$ then since $N_{\left| S\right| +1}(R)\supseteq N_{k^{*}}(R),$ we have that

$$\begin{aligned} \left| N_{\left| S\right| +1}(R)\right| \ge \left| N_{k^{*}}(R)\right| \ge k^{*}>\left| S\right| . \end{aligned}$$

Hence, $N_{\left| S\right| +1}(R)\subseteq S$ does not hold. By Theorem 1, $m^{S}\notin NE(\Gamma _{B},R).$

If $\left| S\right| \ge k^{*}+2,$ then since $N_{\left| S\right| }^{\prime }(R)\subseteq N_{k^{*}+1}(R)$, we have that

$$\begin{aligned} \left| N_{\left| S\right| }^{\prime }(R)\right| \le \left| N_{k^{*}+1}(R)\right|<k^{*}+1<\left| S\right| . \end{aligned}$$

Hence, $S\subseteq N_{\left| S\right| }^{\prime }(R)$ does not hold. By Theorem 1, $m^{S}\notin NE(\Gamma _{B},R).$■

We next investigate the properties of the Nash equilibrium allocations of the binary mechanism. Let $F_{B}:{\mathcal {R}}^{N}\longrightarrow 2^{A}\setminus \left\{ \emptyset \right\}$ denote the solution implemented by the binary mechanism. In other words, for each $R\in {\mathcal {R}}^{N}$, $F_{B}(R)=NE_{A}(\Gamma _{B},R)$. The following theorem exhibits several desirable properties of the solution implemented by the binary mechanism.

Theorem 2

• (1) Suppose $\left| N\right| \ge 4$. Then, $F_{B}$ satisfies the equal-division core property.

• (2) Suppose $\left| N\right| \ge 3$ . Then, $F_{B}$ satisfies weak Pareto efficiency.

• (3) $F_{B}$ satisfies equal-division lower boundedness and anonymity.

Proof

See Appendix.$\blacksquare$

According to Theorem 2, if there are at least four agents, then any Nash equilibrium allocation of the binary mechanism belongs to the equal-division core. Since for each $R\in {\mathcal {R}}^{N}$, $EC(R)\subseteq WP(R)$ and $EC(R)\subseteq ELB(R),$ the equal-division core property must imply weak Pareto efficiency and equal-division lower boundedness.⁹ Also, Theorem 2 says that if there are three agents, then while $F_{B}$ does not satisfy the equal-division core property, $F_{B}$ satisfies weak Pareto efficiency and equal-division lower boundedness. In addition, the solution implemented by the binary mechanism satisfies equal-division lower boundedness and anonymity. As seen in Remarks 1 and 2, whenever a solution is weakly Pareto efficient and Nash implementable, it violates envy-freeness and strong Pareto efficiency, respectively. Since $F_{B}$ satisfies all the axioms defined in Sect. 3, other than strong Pareto efficiency and envy-freeness, we can achieve our second-best goal through the binary mechanism.¹⁰

We end this section by noting that (1) if $\left| N\right| <3$, then $F_{B}$ does not satisfy weak Pareto efficiency, (2) if $\left| N\right| <4$, then $F_{B}$ does not satisfy the equal-division core property, and (3) if $\left| N\right| \ge 4,$ then the binary does not fully implement $WP\cap ELD$ or EC in Nash equilibria.

Remark 4

If $\left| N\right| =2$, then there are $R\in {\mathcal {R}}^{N}$ and $S\subseteq N$ such that $x^{S}\in F_{B}(R)$ and $x^{S}\notin WP(R)$. Let $N=\left\{ 1,2\right\}$ and $R=(R_{1},R_{2})\in {\mathcal {R}}^{N}$ be such that (1) $d(R_{1})=\frac{1}{2}$ and $0\,P_{1}\,1,$ and (2) $d(R_{2})=\frac{1}{2}$ and $1\,P_{2}\,0.$ We can easily check that $m^{\left\{ 1\right\} }\in NE(\Gamma _{B},R),$ and thus, $x^{\left\{ 1\right\} }\in F_{B}(R)$. However, for $y=(0,1)\in A,$ we must have $y_{1}=0\,P_{1}\,1=x_{1}^{\left\{ 1\right\} }$, and $y_{2}=1\,P_{2} \,0=x_{2}^{\left\{ 1\right\} }.$ Therefore, $x^{\left\{ 1\right\} }\notin WP(R)$.

Remark 5

If $\left| N\right| =3$, then there are $R\in {\mathcal {R}}^{N}$ and $S\subseteq N$ such that $x^{S}\in F_{B}(R)$ and $x^{S}\notin EC(R)$. Let $N=\left\{ 1,2,3\right\}$ and $R=(R_{1},R_{2},R_{3})\in {\mathcal {R}}^{N}$ be such that (1) for $i=1,$ $d(R_{i})=\frac{1}{3}$ and $0\,P_{i}\,1,$ and (2) for each $i\in \left\{ 2,3\right\} ,$ $d(R_{i})=\frac{1}{2}$ and $\frac{2}{3}\,P_{i}\,0.$ We can easily show that $m^{\left\{ 1\right\} }\in NE(\Gamma _{B},R),$ and thus, $x^{\left\{ 1\right\} }\in F_{B}(R)$. However, for $y=(0,\frac{2}{3},\frac{1}{ 3})\in A,$ we must have $y_{1}=0\,P_{1}\,1=x_{1}^{\left\{ 1\right\} }$, $y_{2}=\frac{2}{3}\,P_{2}\,0=x_{2}^{\left\{ 1\right\} }$, and $y_{1}+y_{2}= \frac{2}{3}.$ Therefore, $x^{\left\{ 1\right\} }\notin EC(R)$.

Remark 6

If $\left| N\right| \ge 4$, then there is $R\in {\mathcal {R}}^{N}$ such that $x\in EC(R)\subseteq WP\cap ELB(R)$ and $x\notin F_{B}(R).$ Let $R=(R_{1},R_{2},\ldots ,R_{n})\in {\mathcal {R}}^{N}$ be such that (1) for $i=1,$ $d(R_{i})=1,$ and for each $i\in \left\{ 2,\ldots ,n\right\} ,$ $d(R_{i})=0.$ We can easily check that $(0,\frac{2}{n},\frac{1 }{n},\ldots ,\frac{1}{n})\in EC(R)\subseteq WP\cap ELB(R)$ and $(0,\frac{2}{n },\frac{1}{n},\ldots ,\frac{1}{n})\notin F_{B}(R)=\left\{ (0,\frac{1}{n-1}, \frac{1}{n-1},\ldots ,\frac{1}{n-1})\right\}$. Hence, $F_{B}(R)\subsetneq EC(R)\subseteq WP\cap ELB(R)$.

5 Better-reply dynamics

In the previous section, we show several attractive properties of Nash equilibrium allocations of the binary mechanism. When we employ the concept of Nash equilibrium for the analysis of a game, we usually impose the assumption that preferences be common knowledge. However, when a game additionally has some dynamic stability properties, the agents who follow some adjustment process learn to choose a Nash equilibrium, even if preferences are not common knowledge.

The class of ordinal potential games, introduced by Monderer and Shapley (1996), is a well-known class of games in which the set of Nash equilibria is stable in the following sense. Let $G\equiv \left( N,\left( S_{i}\right) _{i\in N},A,f,\left( R_{i}\right) _{i\in N}\right)$ be a strategic form game, in which N is the set of agents, $\ S_{i}$ is the set of i’s strategies, A is the set of outcomes, $f:\prod \limits _{i\in N}S_{i}\rightarrow A$ is the outcome function, and $R_{i}$ is i’s preference over A. A game G is finite if for each $i\in N$, $\left| S_{i}\right| <\infty$ and ordinal potential if there is $P:\prod \limits _{i\in N}S_{i}\rightarrow {\mathbb {R}}$, called a potential function, such that for each $i\in N,$ each pair$\ s_{i},s_{i}^{\prime }\in S_{i},$ and each $s_{-i}\in S_{-i},$ $f(s_{i},s_{-i})\,R_{i}\,f(s_{i}^{\prime },s_{-i})$ if and only if $P(s_{i},s_{-i})\ge P(s_{i}^{\prime },s_{-i})$.

A path is a sequence of strategy profiles $\left( s^{t}\right) _{t\in {\mathbb {N}} }$. A path $\left( s^{t}\right) _{t\in {\mathbb {N}} }$ is a better-reply path of G if for each pair $t,t+1\in {\mathbb {N}} ,$ $s_{t+1}\ne s_{t}$ if and only if there is $i\in N$ such that $s^{t+1}=(s_{i}^{t+1},s_{-i}^{t})$ and $f(s_{i}^{t+1},s_{-i}^{t})\,P_{i} \,f(s_{i}^{t},s_{-i}^{t})$. A better-reply path $\left( s_{t}\right) _{t\in {\mathbb {N}} }$ is finite if there is $t\in {\mathbb {N}}$ such that for each $t^{\prime }>t,$ $s_{t^{\prime }}=s_{t}$. Monderer and Shapley (1996) showed that in a finite ordinal potential game, any better-reply path is finite.

For each $R\in {\mathcal {R}}^{N}$ and each mechanism $\Gamma =(\left( M_{i}\right) _{i\in N},g),$ let $G(\Gamma ,R)\equiv \left( N,\left( M_{i}\right) _{i\in N},A,g,\left( R_{i}\right) _{i\in N}\right)$ denote the strategic form game associated with $\Gamma$ and R. We show that any better-reply path of the binary mechanism is finite by proving that for each $R\in {\mathcal {R}}^{N}$, $G(\Gamma _{B},R)$ is an ordinal potential game.

Theorem 3

For each $R\in {\mathcal {R}}^{N}$ , any better-reply path of $G(\Gamma _{B},R)$ is finite.

Proof

See Appendix.■

In order to prove Theorem 3, we introduce the following potential function $P:\prod \limits _{i\in N}\left\{ 0,1\right\} \rightarrow {\mathbb {R}} .$ We need some notation. For each $R_{i}\in {\mathcal {R}}$, define $\delta (R_{i})\in \left[ 0,1\right]$ as follows. When $1\,R_{i}\,0,$ let $\ \delta (R_{i})\in \left[ 0,\frac{1}{2}\right]$ be such that $2\delta (R_{i})\,I_{i}\,0$. Here, $\ 2\delta (R_{i})\in \left[ 0,1\right]$ denotes the allotment that is indifferent to 0. When $0\,P_{i}\,1$, let $\delta (R_{i})\in \left( \frac{1}{2},1\right]$ be such that $(2\delta (R_{i})-1)\,I_{i}\,1$. Here, $(2\delta (R_{i})-1)\in \left( 0,1\right] \$ denotes the allotment that is indifferent to 1 (see Fig. 1).

Fig. 1

Definition of $\delta (R)$

For each $R\in {\mathcal {R}}^{N},$ define $P:\prod \limits _{i\in N}\left\{ 0,1\right\} \rightarrow {\mathbb {R}}$ as

$$\begin{aligned} P(m)=\left\{ \begin{array}{cc} \sum \limits _{i\in N}\frac{m_{i}^{2}}{\delta (R_{i})}-2\sum \limits _{i\in N}m_{i}-2\sum \limits _{i\in N}\sum \limits _{j\in N\backslash \left\{ i\right\} }m_{i}m_{j} &{} \text {if there is }i\in N,\text { }m_{i}=1 \\ \frac{2n}{1+n}-2 &{} \text {otherwise.} \end{array} \right. \end{aligned}$$

We show in the appendix that $P:\prod \limits _{i\in N}\left\{ 0,1\right\} \rightarrow {\mathbb {R}}$ is a potential function of $G(\Gamma _{B},R).$

The proof of Theorem 3 relies on the properties of potential games. Once we prove that $G(\Gamma _{B},R)$ is a finite ordinal potential game, we also know that any better-reply path of $G(\Gamma _{B},R)$ is finite (Monderer and Shapley 1996). This method was also used by Sandholm (2002, 2005, 2007), who considered economies with externalities, and Yamamura and Kawasaki (2013), who considered economies with one public good when agents’ preferences are single-peaked.

The main difference between these studies and ours stems from the different concepts of potential games used, which results in different adjustment processes that are considered in showing the stability of Nash equilibria. Since Sandholm (2002, 2005, 2007) applied the “exact” potential games of Monderer and Shapley (1996), his results imply stability for more general dynamic processes, but they require the specification of cardinal utility functions. Meanwhile since Yamamura and Kawasaki (2013) applied the “best-reply” potential games of Voorneveld (2000) and Jensen (2009), which is weaker than the notion of ordinal potential games, their results imply stability for more specific dynamic processes.¹¹

6 Conclusion

In the allocation problem with single-dipped preferences, no Pareto efficient and strategy-proof rule satisfies equal-division lower boundedness, the equal-division core property, and anonymity. Also, envy-freeness is incompatible with weak Pareto efficiency and strong Pareto efficiency is incompatible with Maskin monotonicity. We alternatively propose a mechanism that we call the binary mechanism and show that it Nash implements a solution satisfying weak Pareto efficiency, equal-division lower boundedness, the equal-division core property, and anonymity. Moreover, we show that the binary mechanism is Cournot stable in the sense that from any message profile, any path of better-reply converges to a Nash equilibrium.

As the next step, we plan to conduct a laboratory experiment to explore whether the binary mechanism works well in practice. In the context of public goods economies, several experimental studies, such as Chen and Gazzale (2004) and Healy (2006) suggested that supermodularity is a sufficient condition for subjects to learn to choose a Nash equilibrium. Since all games induced by the binary mechanism are ordinal potential games, experiments on the binary mechanism might suggest that potential games are another sufficient conditions for the convergence to a Nash equilibrium. While the theory of potential games tells us that any path of better reply is convergent, how rapid the convergence speed is remains an open question. Experimental studies might help us investigate the actual speed of agents’ learning under mechanisms inducing potential games.

Appendix

1.1 Proof of Theorem 1

Claim 1

For each $R\in {\mathcal {R}}^{N},$ and each $S\subseteq N$ , if $m^{S}\in NE(\Gamma _{B},R)$ , then $S\subseteq N_{\left| S\right| }^{^{\prime }}(R).$

Proof

We distinguish three cases.

Case 1: $\left| S\right| =0.$ Since $S=\phi$, $S=\phi \subseteq N_{\left| S\right| }^{^{\prime }}(R)$.

Case 2: $\left| S\right| =1.$ Suppose there is $i\in S$ such that $i\notin N_{1}^{^{\prime }}(R).$ Since $i\notin N_{1}^{^{\prime }}(R)=\left\{ i\in N\text { }|\text { }1\,R_{i}\,\frac{1}{n}\right\}$,

$$\begin{aligned} g_{i}\left( 0,m_{-i}^{S}\right) =\frac{1}{n}\,P_{i}\,1=g_{i}\left( m^{S}\right) . \end{aligned}$$

Hence, $m^{S}\notin NE(\Gamma ,R).$

Case 3: $\left| S\right| =k\ge 2.$ Suppose there is $i\in S$ such that $i\notin N_{k}^{^{\prime }}(R).$ Since $i\notin N_{k}^{^{\prime }}(R)=\left\{ i\in N\text { }|\text { }\frac{1}{k} \,R_{i}\,0\right\}$,

$$\begin{aligned} g_{i}\left( 0,m_{-i}^{S}\right) =0\,P_{i}\,\frac{1}{k}=g_{i}\left( m^{S}\right) . \end{aligned}$$

Hence, $m^{S}\notin NE(\Gamma _{B},R).\blacksquare$

Claim 2

For each $R\in {\mathcal {R}}^{N},$ and each $S\subseteq N$, if $m^{S}\in NE(\Gamma _{B},R)$, then $N_{\left| S\right| +1}\subseteq S.$

Proof

We distinguish three cases.

Case 1: $\left| S\right| =0.$ Suppose there is $i\in N_{1}(R)$ such that $i\notin S$. Since $i\in N_{1}(R)=\left\{ i\in N\text { }| \text { }1\,P_{i}\,\frac{1}{n}\right\}$

$$\begin{aligned} g_{i}\left( 1,m_{-i}^{S}\right) =1\,P_{i}\,\frac{1}{n}=g_{i}\left( m^{S}\right) . \end{aligned}$$

Hence, $m^{S}\notin NE(\Gamma _{B},R).$

Case 2: $\left| S\right| =k\in \left\{ 1,\ldots ,n-1\right\} .$ Suppose there is $i\in N_{k+1}(R)$ such that $i\notin S$. Then, since $i\in N_{k+1}(R)=\left\{ i\in N\text { }|\text { }\frac{1}{k+1} \,P_{i}\,0\right\}$

$$\begin{aligned} g_{i}\left( 1,m_{-i}^{S}\right) =\frac{1}{k+1}\,P_{i}\,0=g_{i}\left( m^{S}\right) . \end{aligned}$$

Hence, $m^{S}\notin NE(\Gamma _{B},R).$

Case 3: $\left| S\right| =n$. Since $N_{n+1}(R)=\phi$, $N_{n+1}=\phi \subseteq S$.■

Claim 3

For each $R\in {\mathcal {R}}^{N},$ and each $S\subseteq N$, if $N_{\left| S\right| +1}(R)\subseteq S\subseteq N_{\left| S\right| }^{^{\prime }}(R)$, then $m^{S}\in NE(\Gamma _{B},R).$

Proof

We distinguish four cases. Case 1: $\left| S\right| =0.$ For each $j\in N\backslash S=N$, since $j\notin N_{1}(R)=\left\{ i\in N\text { }|\text { }1\,P_{i}\, \frac{1}{n}\right\} ,$

$$\begin{aligned} g_{j}\left( m^{S}\right) =\frac{1}{n}\,R_{j}\,1=g_{j}\left( 1,m_{-j}^{S}\right) . \end{aligned}$$

Hence, $m^{S}\in NE(\Gamma _{B},R).$

Case 2: $\left| S\right| =1.$ For each $i\in S,$ since $\ i\in N_{1}^{^{\prime }}(R)=\left\{ i\in N\text { }|\text { }1\,R_{i}\,\frac{1}{ n}\right\} ,$

$$\begin{aligned} g_{i}\left( m^{S}\right) =1\,R_{i}\,\frac{1}{n}=g_{i}\left( 0,m_{-i}^{S}\right) . \end{aligned}$$

For each $j\in N\backslash S$, since $j\notin N_{2}(R)=\left\{ i\in N\text { } |\text { }\frac{1}{2}\,P_{i}\,0\right\} ,$

$$\begin{aligned} g_{j}\left( m^{S}\right) =0\,R_{j}\,\frac{1}{2}=g_{j}\left( 1,m_{-j}^{S}\right) . \end{aligned}$$

Hence, $m^{S}\in NE(\Gamma _{B},R).$

Case 3: $\left| S\right| =k\in \left\{ 2,\ldots ,n-1\right\} .$ For each $i\in S,$ since $\ i\in N_{k}^{^{\prime }}(R)=\left\{ i\in N\text { }|\text { }\frac{1}{k}\,R_{i}\,0\right\} ,$

$$\begin{aligned} g_{i}\left( m^{S}\right) =\frac{1}{k}\,R_{i}\,0=g_{i}\left( 0,m_{-i}^{S}\right) . \end{aligned}$$

For each $j\in N\backslash S$, since $j\notin N_{k+1}(R)=\left\{ i\in N\text { }|\text { }\frac{1}{k+1}\,P_{i}\,0\right\} ,$

$$\begin{aligned} g_{j}\left( m^{S}\right) =0\,R_{j}\,\frac{1}{k+1}=g_{j}\left( 1,m_{-j}^{S}\right) . \end{aligned}$$

Hence, $m^{S}\in NE(\Gamma _{B},R).$

Case 4: $\left| S\right| =n.$ For each $i\in S=N,$ since $\ i\in N_{n}^{^{\prime }}(R)=\left\{ i\in N\text { }|\text { }\frac{1}{n} \,R_{i}\,0\right\} ,$

$$\begin{aligned} g_{i}\left( m^{S}\right) =\frac{1}{n}\,R_{i}\,0=g_{i}\left( 0,m_{-i}^{S}\right) . \end{aligned}$$

Hence, $m^{S}\in NE(\Gamma _{B},R).$■

1.2 Proof of Theorem 2

Claim 4

Suppose $\left| N\right| \ge 3$ . Then, for each $R\in {\mathcal {R}}^{N},$ and each $S\subseteq N,$ if $m^{S}\in NE(\Gamma _{B},R)$ , then $x^{S}\in WP(R).$

Proof

We distinguish three cases.

Case 1: $\left| S\right| =0.$ Suppose that $m^{S}\in NE(\Gamma _{B},R).$ By Theorem 1, since for each $i\in N\backslash S=N,$ $i\notin N_{1}(R)=\left\{ i\in N\text { }|\text { }1\,P_{i}\,\frac{1}{n} \right\} ,$ we obtain $x_{i}^{S}=\frac{1}{n}\,R_{i}\,1$. Hence, by single-dippedness of $R_{i}$, for each $i\in N,$ if $y_{i}\,P_{i}\,x_{i}^{S}$ then $y_{i}<\frac{1}{n}$. Suppose there is $y\in A$ such that for each $i\in N,$ $y_{i}\,P_{i}\,x_{i}^{S}$. Then, since for each $i\in N,\ y_{i}<\frac{1}{ n},$

$$\begin{aligned} \sum \limits _{i\in N}y_{i}<\frac{\left| N\right| }{n}=1, \end{aligned}$$

which contradicts $y\in A=\left\{ (x_{1},...,x_{n})\in {\mathbb {R}} _{+}^{n}\text { }|\text { }\sum \nolimits _{i\in N}x_{i}=1\right\} .$ Therefore, $x^{S}\in WP(R).$

Case 2: $\left| S\right| =1.$ Let $S=\left\{ j\right\} .$ Suppose that $m^{S}\in NE(\Gamma _{B},R).$ By Theorem 1, since for each $i\in N\backslash \left\{ j\right\} ,$ $i\notin N_{2}(R)=\left\{ i\in N\text { }|\text { }\frac{1}{2}\,P_{i}\,0\right\} ,$ $x_{i}^{S}=0\,R_{i}\,\frac{1}{2}$ . Hence, by single-dippedness of $R_{i}$, for each $i\in N\backslash \left\{ j\right\} ,$ if $y_{i}\,P_{i}\,x_{i}^{S}$ then $y_{i}>\frac{1}{2}$. Suppose that there is $y\in A$ such that for each $i\in N,$ $y_{i}\,P_{i}\,x_{i}^{S}$ . Then, since for each $i\in N\backslash \left\{ j\right\} ,\ y_{i}>\frac{1}{ 2},$

$$\begin{aligned} \sum \limits _{i\in N}y_{i}\ge \sum \limits _{i\in N\backslash \left\{ j\right\} }y_{i}>\frac{\left| N\right| -1}{2}\ge 1, \end{aligned}$$

which contradicts $y\in A.$ Therefore, $x^{S}\in WP(R).$

Case 3: $\left| S\right| \ge 2.$ Let $k=\left| S\right| \ge 2.$ Suppose that $m^{S}\in NE(\Gamma _{B},R^{N})$. By Theorem 1, since for each $i\in S,$ $i\in N_{k}^{\prime }(R)=\left\{ i\in N \text { }|\text { }\frac{1}{k}\,P_{i}\,0\right\} ,$ $x_{i}^{S}=\frac{1}{k} \,R_{i}\,0$. Hence, by single-dippedness of $R_{i}$, for each $i\in S$, if $y_{i}\,P_{i}\,x_{i}^{S}$, then, $y_{i}>\frac{1}{k}$. Suppose there is $y\in A$ such that for each $i\in N,$ $y_{i}\,P_{i}\,x_{i}^{S}$. Then, since for each $i\in S,\ y_{i}>\frac{1}{k},$

$$\begin{aligned} \sum \limits _{i\in N}y_{i}\ge \sum \limits _{i\in S}y_{i}>\frac{\left| S\right| }{k}=1, \end{aligned}$$

which contradicts $y\in A.$ Therefore, $x^{S}\in WP(R).$■

Claim 5

Suppose $\left| N\right| \ge 4$ . Then, for each $R\in {\mathcal {R}}^{N}$ , and each $S\subseteq N,$ if $m^{S}\in NE(\Gamma _{B},R)$ , then $x^{S}\in EC(R).$

Proof

We distinguish four cases.

Case 1: $\left| S\right| =0.$ Suppose that $m^{S}\in NE(\Gamma _{B},R)$ and that there are $T\subseteq N$ and $y\in A$ such that for each $i\in T,$ $y_{i}\,P_{i}\,x_{i}^{S}$ and $\ \sum \nolimits _{i\in T}y_{i}=\frac{\left| T\right| }{n}$. We know from the proof of Claim 4 that for each $i\in N$, if $\ y_{i}\,P_{i}\,x_{i}^{S}$, then $y_{i}< \frac{1}{n}$. Hence,

$$\begin{aligned} \sum \limits _{i\in T}y_{i}<\frac{\left| T\right| }{n}, \end{aligned}$$

which is a contradiction. Therefore, $x^{S}\in EC(R).$

Case 2: $\left| S\right| =1.$ Suppose that $m^{S}\in NE(\Gamma _{B},R)$ and that there are $T\subseteq N$ and $y\in A$ such that for each $i\in T,$ $y_{i}\,P_{i}\,x_{i}^{S}$ and $\ \sum \nolimits _{i\in T}y_{i}=\frac{\left| T\right| }{n}$. If $T=\left\{ j\right\} ,$ then since $j\in \left\{ i\in N\text { }|\text { }1\,R_{i}\,\frac{1}{n}\right\} ,$ we have $\ x_{i}^{S}=1\,R_{i}\,\frac{1}{n}=\frac{\left| T\right| }{n}$ , which is a contradiction. Hence, $T\backslash \left\{ j\right\} \ne \phi$ . We know from the proof of Claim 4 that for each $i\in N\backslash \left\{ j\right\}$, if $\ y_{i}\,P_{i}\,x_{i}^{S}$ then $y_{i}>\frac{1}{2}$. Hence,

$$\begin{aligned} \frac{\left| T\right| }{n}=\sum \limits _{i\in T}y_{i}\ge \sum \limits _{i\in T\backslash \left\{ j\right\} }y_{i}>\frac{\left| T\backslash \left\{ j\right\} \right| }{2}\ge \frac{1}{2}. \end{aligned}$$

Since $n\ge 4$ and $\frac{\left| T\right| }{n}>\frac{1}{2}$, we have $\left| T\right| \ge 3$. Hence, $\left| T\backslash \left\{ j\right\} \right| \ge 2$, so that

$$\begin{aligned} \sum \limits _{i\in T}y_{i}\ge \sum \limits _{i\in T\backslash \left\{ j\right\} }y_{i}>\frac{\left| T\backslash \left\{ j\right\} \right| }{2}\ge 1\ge \frac{\left| T\right| }{n}, \end{aligned}$$

which is a contradiction. Therefore, $x^{S}\in EC(R).$

Case 3: $\left| S\right| \in \left\{ 2,\ldots ,n-1\right\} .$ Let $k=\left| S\right| \ge 2.$ Suppose that $m^{S}\in NE(\Gamma _{B},R^{N})$ and that there are $T\subseteq N$ and $y\in A$ such that for each $i\in T,$ $y_{i}\,P_{i}\,x_{i}^{S}$ and$\ \sum \nolimits _{i\in T}y_{i}= \frac{\left| T\right| }{n}$. We know from the proof of Claim 4 that for each $i\in S,$ if $y_{i}\,P_{i}\,x_{i}^{S}$, then $y_{i}>\frac{1}{k}$. By Theorem 1, since for each $i\in N\backslash S,$ $i\notin N_{k+1}(R)=\left\{ i\in N\text { }|\text { }\frac{1}{k+1}\,P_{i}\,0\right\} ,$ we obtain $x_{i}^{S}=0\,R_{i}\,\frac{1}{k+1}$. By single-dippedness of $R_{i}$, for each $i\in N\backslash S,$ if $y_{i}\,P_{i}\,x_{i}^{S}$, then $y_{i}>\frac{1}{k+1}$. Hence,

$$\begin{aligned} \sum \limits _{i\in T}y_{i}=\sum \limits _{i\in T\cap S}y_{i}+\sum \limits _{i\in T\backslash S}y_{i}>\frac{\left| T\cap S\right| }{k}+\frac{\left| T\backslash S\right| }{k+1}\ge \frac{ \left| T\cap S\right| }{n}+\frac{\left| T\backslash S\right| }{n}=\frac{\left| T\right| }{n}, \end{aligned}$$

which is a contradiction. Therefore, $x^{S}\in EC(R).$

Case 4: $\left| S\right| =n.$ Let $m^{S}\in NE(\Gamma _{B},R).$ Suppose there are $T\subseteq N$ and $y\in A$ such that for each $i\in T,$ $y_{i}\,P_{i}\,x_{i}^{S}$ and $\ \sum \nolimits _{i\in T}y_{i}=\frac{ \left| T\right| }{n}$. We know from the proof of Claim 4 that for each $i\in N$, if $\ y_{i}\,P_{i}\,x_{i}^{S}$, then $y_{i}>\frac{1}{n}$. Hence,

$$\begin{aligned} \sum \limits _{i\in T}y_{i}>\frac{\left| T\right| }{n}, \end{aligned}$$

which is a contradiction. Therefore, $x^{S}\in EC(R).$■

Claim 6

For each $R\in {\mathcal {R}}^{N}$ , and each $S\subseteq N,$ if $m^{S}\in NE(\Gamma _{B},R)$ , then $x^{S}\in ELB(R).$

Proof

Obvious.■

Claim 7

$F_{B}$ satisfies anonymity.

Proof

Obvious.■

1.3 Proof of Theorem 3

Let us recall some notation. For each $R_{i}\in {\mathcal {R}}$, define $\delta (R_{i})\in \left[ 0,1\right]$ as follows. If $1\,R_{i}\,0,$ then let $\ \delta (R_{i})\in \left[ 0,\frac{1}{2}\right]$ be such that $2\delta (R_{i})\,I_{i}\,0$. If $0\,P_{i}\,1$, then let $\delta (R_{i})\in \left( \frac{1}{2},1\right]$ be such that $(2\delta (R_{i})-1)\,I_{i}\,1$. For each $R\in {\mathcal {R}}^{N},$ let $P:\prod \limits _{i\in N}\left\{ 0,1\right\} \rightarrow {\mathbb {R}}$ be such that for each $m\in \prod \limits _{i\in N}\left\{ 0,1\right\}$,

$$\begin{aligned} P(m)=\left\{ \begin{array}{cc} \sum \limits _{i\in N}\frac{m_{i}^{2}}{\delta (R_{i})}-2\sum \limits _{i\in N}m_{i}-2\sum \limits _{i\in N}\sum \limits _{j\in N\backslash \left\{ i\right\} }m_{i}m_{j} &{} \text {if there is }i\in N,\text { }m_{i}=1 \\ \frac{2n}{1+n}-2 &{} \text {otherwise} \end{array} \right. \end{aligned}$$

We show that for each $R\in {\mathcal {R}}^{N},$ P is a potential function of $G(R,\Gamma _{B}).$

We distinguish two cases.

Case 1 There is $j\in N\backslash \left\{ i\right\}$ such that $m_{j}=1.$

In this case, $g_{i}(0,m_{-i})=0$ and $g_{i}(1,m_{-i})=\frac{1}{ 1+\sum \nolimits _{j\in N\backslash \left\{ i\right\} }m_{j}}.$ By the definition of $\delta (R_{i}),$ $g_{i}(1,x_{-i})\,R_{i}\,g_{i}(0,x_{-i})$ if and only if $2\delta (R_{i})\le \frac{1}{1+\sum \nolimits _{j\in N\backslash \left\{ i\right\} }m_{j}}.$

The potential function can be written as

$$\begin{aligned} P(m_{i},m_{-i})= & {} \frac{m_{i}^{2}}{\delta (R_{i})}-2m_{i}\left( 1+\sum \limits _{j \in N\backslash \left\{ i\right\} }m_{j}\right) +Q_{1}\left( m_{-i}\right) \\= & {} \frac{1}{\delta (R_{i})}\left( m_{i}-\delta (R_{i})\left( 1+\sum \limits _{j\in N\backslash \left\{ i\right\} }m_{j}\right) \right) ^{2}+Q_{2}\left( m_{-i}\right) \end{aligned}$$

where $Q_{1}$ and $Q_{2}$ represent the collective terms that do not depend on $m_{i}$. We know from this equation that $P(1,m_{-i})\ge P(0,m_{-i})$ if and only if

$$\begin{aligned} \delta (R_{i})\left( 1+\sum \limits _{j\in N\backslash \left\{ i\right\} }m_{j}\right) \le \frac{1}{2}. \end{aligned}$$

This inequality can be transformed into

$$\begin{aligned} 2\delta (R_{i})\le \frac{1}{1+\sum \nolimits _{j\in N\backslash \left\{ i\right\} }m_{j}}. \end{aligned}$$

Therefore, $g_{i}(1,m_{-i})\,R_{i}\,\,g_{i}(0,m_{-i})$ if and only if $P(1,m_{-i})\ge P(0,m_{-i}).$

Case 2 For each $j\in N\backslash \left\{ i\right\}$, $m_{j}=0.$

In this case, $g_{i}(0,m_{-i})=\frac{1}{n}$ and $g_{i}(1,m_{-i})=1.$ By the definition of $\delta (R_{i}),$ $g_{i}(1,m_{-i})\,R_{i}\,\,g_{i}(0,m_{-i})$ if and only if $2\delta (R_{i})-1\le \frac{1}{n}.$

Since $\ P(0,m_{-i})=\frac{2n}{1+n}-2$ and $P(1,m_{-i})=\frac{1}{\delta (R_{i})}-2$, $P(1,m_{-i})\ge P(0,m_{-i})$ if and only if

$$\begin{aligned} \frac{1}{\delta (R_{i})}-2\ge \frac{2n}{1+n}-2. \end{aligned}$$

This inequality can be transformed into

$$\begin{aligned} 2\delta (R_{i})-1\le \frac{1}{n}. \end{aligned}$$

Therefore, $g_{i}(1,m_{-i})\,R_{i}\,\,g_{i}(0,m_{-i})$ if and only if $P(1,m_{-i})\ge P(0,m_{-i}).\blacksquare$■

1.4 Logical relationships among axioms

Here we investigate several relationships among axioms and check whether $F_{B}$ satisfies several well-known axioms.

Example 1

As mentioned in Remark 1, strong Pareto efficiency is incompatible with Maskin monotonicity. To confirm this, suppose $\left| N\right| \ge 2$ and let $R\in {\mathcal {R}}^{N}$ be such that for each $i\in N,$ $d(R_{i})=\frac{1}{2}$ and $1\,P_{i}\,0.$ We can easily check that

$$\begin{aligned} SP(R)=\left\{ x^{\left\{ i\right\} }\in A\text { }|i\in N\right\} =\left\{ x\in A\text { }|\exists i\in N,\text { }x_{i}=1\right\} . \end{aligned}$$

Suppose there is a solution $F:{\mathcal {R}}\longrightarrow 2^{A}\setminus \left\{ \emptyset \right\}$ satisfying both strong Pareto efficiency and Maskin monotonicity. Then, there is $i\in N$ such that $\ x^{\left\{ i\right\} }\in F(R).$ Let ${\overline{R}}\in {\mathcal {R}}^{N}$ be such that (1) for $i\in N,\ d({\overline{R}}_{i})=\frac{1}{2}$ and $1\,{\overline{I}} _{i}\,0$, and (2) for each $j\in N\backslash \left\{ i\right\} ,$ $\overline{ R}_{j}=R_{j}.$ Since for each $j\in N\backslash \left\{ i\right\} ,$ $L( {\overline{R}}_{j},0)=L(R_{j},0),$ and for $i\in N,$

$$\begin{aligned} L({\overline{R}}_{i},1)= & {} \left[ 0,1\right] \\\supseteq & {} L(R_{i},1), \end{aligned}$$

by Maskin monotonicity of F, we have $x^{\left\{ i\right\} }\in F( {\overline{R}}).$ However, since $SP({\overline{R}})=\left\{ x^{\left\{ j\right\} }\in A\text { }|j\in N\backslash \left\{ i\right\} \right\}$, $x^{\left\{ i\right\} }\notin SP({\overline{R}})$. Therefore, $F({\overline{R}} )\nsubseteq SP({\overline{R}}).$

Example 2

As mentioned in Remark 2, envy-freeness is incompatible with weak Pareto efficiency. To confirm this, let $R\in {\mathcal {R}}^{N}$ be such that for each $i\in N,$ $d(R_{i})=\frac{1}{2}$ and $1\,P_{i}\,0.$ We first show that if $x\in WP(R),$ then there is $i\in N$ such that $x_{i}=0.$ If for each $i\in N,$ $x_{i}>0$, then there is $j\in N$ such that $1>x_{j}>0$ and for each $i\ne j,$ $0<x_{i}\le \frac{1}{2}.$ By single-dippedness of $R_{i},$ for $j\in N,\ 1\,P_{j}\,x_{j}$ and for each $i\ne j,$ $0\,P_{i}\,x_{i}$. Hence, $x\notin WP(R).$ Therefore,

$$\begin{aligned} WP(R)\subseteq \left\{ x\in A\text { }|\exists i\in N,\text { }x_{i}=0\right\} . \end{aligned}$$

Let $x^{\prime }\in \left\{ x\in A\text { }|\exists i\in N,\text { } x_{i}=0\right\}$ be such that there are distinct $i,j,k\in N$ such that $x_{i}^{\prime }=0$, $x_{j}^{\prime }>0$, and $x_{k}^{\prime }>0$. If $x^{\prime }\in EF(R),$ then $x_{j}^{\prime }\,R_{j}\,x_{i}^{\prime }=0$ and $x_{k}^{\prime }\,R_{k}\,x_{i}^{\prime }=0$. By single-dippedness of $R_{j}$ and $R_{k}$, we have $x_{j}^{\prime }>\frac{1}{2}$ and $x_{k}^{\prime }> \frac{1}{2}.$ Hence,

$$\begin{aligned} \sum \limits _{i\in N}x_{i}^{\prime }\ge x_{j}^{\prime }+x_{k}^{\prime }> \frac{1}{2}+\frac{1}{2}=1, \end{aligned}$$

which contradicts $x^{\prime }\in A.$ Therefore, whenever $x\in WP(R)\cap EF(R)$, there is $i\in N$ such that $x_{i}=1,$ so that

$$\begin{aligned} WP(R)\cap EF(R)\subseteq \left\{ x^{\left\{ i\right\} }\in A\text { }|i\in N\right\} . \end{aligned}$$

For each $x^{\left\{ i\right\} }\in A,$ since for each $j\ne i,\ 1=x_{i}\,P_{j}\,x_{j}=0$, we have $x^{\left\{ i\right\} }\notin EF(R).$ Therefore,

$$\begin{aligned} WP(R)\cap EF(R)=\phi . \end{aligned}$$

Remark 7

A solution F satisfies welfare-domination under preference replacement if for each $R\in {\mathcal {R}}^{N},$ each $x\in F(R),$ each $i\in N,$ each $R_{i}^{\prime }\in {\mathcal {R}}$, and each $x^{\prime }\in F(R_{i}^{\prime },R_{-i}),$ either $x_{j}\,R_{j}\,x_{j}^{ \prime }$, for each $j\in N\backslash \left\{ i\right\}$ or $x_{j}^{\prime }\,R_{j}\,x_{j}$, for each $j\in N\backslash \left\{ i\right\}$ (Thomson 1993; Klaus et al. 1997). Note that if F satisfies weak Pareto efficiency, anonymity, and Maskin monotonicity, then $\ F$ does not satisfy welfare-domination under preference replacement. Hence, $F_{B}$ also violates welfare-domination under preference replacement.

To confirm this, suppose $\left| N\right| \ge 3$ and F satisfies weak Pareto efficiency, anonymity, and Maskin monotonicity. Let $R\in {\mathcal {R}}^{N}$ be such that for each $i\in N,$ $d(R_{i})=\frac{1}{2}$ and $1\,P_{i}\,0\,I_{i}\,\frac{9}{10}.$ As seen in Example 2, since

$$\begin{aligned} WP(R)\subseteq \left\{ x\in A\text { }|\exists i\in N,\text { }x_{i}=0\right\} , \end{aligned}$$

there is $i\in N$ such that $x_{i}=0.$ Let $x\in \left\{ x\in A\text { } |\exists i\in N,\text { }x_{i}=0\right\}$ be such that $x_{i}=0$ and for each $j\in N\backslash \left\{ i\right\} ,$ $x_{j}\in \left( 0,\frac{9}{10} \right) .$ Then, for $x^{\left\{ i\right\} }\in A,$ we have $x_{i}^{\left\{ i\right\} }=1\,P_{i}\,0=x_{i}$ and for each $j\in N\backslash \left\{ i\right\} ,$ $x_{j}^{\left\{ i\right\} }=0\,P_{j}\ x_{j},$ so that $x\notin WP(R).$ Hence, for each $x\in F(R)\subseteq WP(R),$ either (1) there are distinct $i,j\in N$ such that $x_{i}=0$ and $\ x_{j}>\frac{9}{10},$ (2) there are distinct $i,j,k\in N$ such that $x_{i}=0,$ $x_{j}=\frac{9}{10},$ and $x_{k}\in \left( 0,\frac{1}{10}\right]$, or (3) there are distinct $i,j,k\in N$ such that $x_{i}=x_{j}=0$ and $x_{k}\in \left( 0,\frac{9}{10} \right)$ holds. Let $x\in F(R).$ We distinguish three cases.

Case 1: There are distinct $i,j\in N$ such that $x_{i}=0,$ and $\ x_{j}>\frac{9}{10}.$ Let $x^{\prime }\in WP(R)$ be such that $x_{i}^{\prime }=x_{j},$ $x_{j}^{\prime }=x_{i},$ and for each $k\in N\backslash \left\{ i,j\right\} ,$ $x_{k}^{\prime }=x_{k}.$ Since F satisfies anonymity, $x^{\prime }\in F(R).$ For $k\in N\backslash \left\{ i,j\right\} ,$ let $R_{k}^{\prime }\in {\mathcal {R}}$ be such that $\frac{9}{10}\,P_{k}^{\prime }\,0$ and $L(R_{k},x_{k})=L(R_{k}^{\prime },x_{k}).$ Then, by Maskin monotonicity of F, $x,x^{\prime }\in F(R_{k}^{\prime },R_{-k}).$ For $x\in F(R)$ and $x^{\prime }\in F(R_{k}^{\prime },R_{-k}),$ we must have $x_{i}^{\prime }\,P_{i}\,x_{i},$ and $x_{j}\,P_{j}\,x_{j}^{\prime }.$ Therefore, F does not satisfy welfare-domination under preference replacement.

Case 2: There are distinct $i,j,k\in N$ such that $x_{i}=0,$ $x_{j}= \frac{9}{10},$ and $x_{k}\in \left( 0,\frac{1}{10}\right] .$ Let $x^{\prime }\in WP(R)$ be such that $x_{j}^{\prime }=x_{k},$ $x_{k}^{\prime }=x_{j},$ and for each $i\in N\backslash \left\{ j,k\right\} ,$ $x_{i}^{\prime }=x_{i}.$ Since F satisfies anonymity, $x^{\prime }\in F(R).$ Let $R_{i}^{\prime }\in {\mathcal {R}}$ be such that $d(R_{i}^{\prime })=1.$ Since $L(R_{i},0)\subseteq L(R_{i}^{\prime },0)=\left[ 0,1\right] ,$ by Maskin monotonicity of F, $x,x^{\prime }\in F(R_{i}^{\prime },R_{-i}).$ For $x\in F(R)$ and $x^{\prime }\in F(R_{i}^{\prime },R_{-i}),$ we must have $x_{j}\,P_{j}\,x_{j}^{\prime },$ and $x_{k}^{\prime }\,P_{k}\,x_{k}.$ Therefore, F does not satisfy welfare-domination under preference replacement.

Case 3: There are distinct $i,j,k\in N$ such that $x_{i}=x_{j}=0$ and $x_{k}\in \left( 0,\frac{9}{10}\right)$. Let $x^{\prime }\in WP(R)$ be such that $x_{j}^{\prime }=x_{k},$ $x_{k}^{\prime }=x_{j},$ and for each $i\in N\backslash \left\{ j,k\right\} ,$ $x_{i}^{\prime }=x_{i}.$ Since F satisfies anonymity, $x^{\prime }\in F(R).$ Let $R_{i}^{\prime }\in \mathcal { R}$ be such that $d(R_{i}^{\prime })=1.$ Since $L(R_{i},0)\subseteq L(R_{i}^{\prime },0)=\left[ 0,1\right] ,$ by Maskin monotonicity of F, $x,x^{\prime }\in F(R_{i}^{\prime },R_{-i}).$ For $x\in F(R)$ and $x^{\prime }\in F(R_{i}^{\prime },R_{-i}),$ we must have $x_{j}\,P_{j}\,x_{j}^{\prime },$ and $x_{k}^{\prime }\,P_{k}\,x_{k}.$ Therefore, F does not satisfy welfare-domination under preference replacement.

Remark 8

A solution F satisfies weak non-bossiness if for each $R\in {\mathcal {R}}^{N},$ each $x\in F(R),$ each $i\in N,$ each $R_{i}^{\prime }\in {\mathcal {R}}$, and each $x^{\prime }\in F(R_{i}^{\prime },R_{-i}),$ if $x_{i}=x_{i}^{\prime }$, then $x=x^{\prime }$ (Klaus 2001; Thomson 2016). Note that if F satisfies weak Pareto efficiency, anonymity, and Maskin monotonicity, then $\ F$ does not satisfy weak non-bossiness. Hence, $F_{B}$ also violates weak non-bossiness.

To confirm this, suppose $\left| N\right| \ge 3$ and F satisfies weak Pareto efficiency, anonymity, and Maskin monotonicity. Let $R\in {\mathcal {R}}^{N}$ be such that for each $i\in N,$ $d(R_{i})=\frac{1}{2}$ and $1\,P_{i}\,0\,I_{i}\,\frac{9}{10}.$ As seen in Example 3, if $x\in F(R)\subseteq WP(R),$ then either (1) there are distinct $i,j\in N$ such that $x_{i}=0,$ and $\ x_{j}>\frac{9}{10},$ (2) there are distinct $i,j,k\in N$ such that $x_{i}=0,$ $x_{j}=\frac{9}{10},$ and $x_{k}\in \left( 0,\frac{1 }{10}\right]$, or (3) there are distinct $i,j,k\in N$ such that $x_{i}=x_{j}=0$ and $x_{k}\in \left( 0,\frac{9}{10}\right)$ holds. Let $x\in F(R).$ We distinguish three cases.

Case 1: There are distinct $i,j\in N$ such that $x_{i}=0,$ and $\ x_{j}>\frac{9}{10}.$ Let $x^{\prime }\in WP(R)$ be such that $x_{i}^{\prime }=x_{j},$ $x_{j}^{\prime }=x_{i},$ and for each $k\in N\backslash \left\{ i,j\right\} ,$ $x_{k}^{\prime }=x_{k}.$ Since F satisfies anonymity, $x^{\prime }\in F(R).$ For $k\in N\backslash \left\{ i,j\right\} ,$ let $R_{k}^{\prime }\in {\mathcal {R}}$ be such that $\frac{9}{10}\,P_{k}^{\prime }\,0$ and $L(R_{k},x_{k})=L(R_{k}^{\prime },x_{k}).$ Then, by Maskin monotonicity of F, $x,x^{\prime }\in F(R_{k}^{\prime },R_{-k}).$ For $x\in F(R)$ and $x^{\prime }\in F(R_{k}^{\prime },R_{-k}),$ we must have $x_{k}=x_{k}^{\prime },$ and $x_{i}\ne x_{i}^{\prime }.$ Therefore, F does not satisfy weak non-bossiness.

Case 2: There are distinct $i,j,k\in N$ such that $x_{i}=0,$ $x_{j}= \frac{9}{10},$ and $x_{k}\in \left( 0,\frac{1}{10}\right] .$ Let $x^{\prime }\in WP(R)$ be such that $x_{j}^{\prime }=x_{k},$ $x_{k}^{\prime }=x_{j},$ and for each $i\in N\backslash \left\{ j,k\right\} ,$ $x_{i}^{\prime }=x_{i}.$ Since F satisfies anonymity, $x^{\prime }\in F(R).$ Let $R_{i}^{\prime }\in {\mathcal {R}}$ be such that $d(R_{i}^{\prime })=1.$ Since $L(R_{i},0)\subseteq L(R_{i}^{\prime },0)=\left[ 0,1\right] ,$ by Maskin monotonicity of F, $x,x^{\prime }\in F(R_{i}^{\prime },R_{-i}).$ For $x\in F(R)$ and $x^{\prime }\in F(R_{i}^{\prime },R_{-i}),$ we must have $x_{i}=x_{i}^{\prime },$ and $x_{j}\ne x_{j}^{\prime }.$ Therefore, F does not satisfy weak non-bossiness.

Case 3: There are distinct $i,j,k\in N$ such that $x_{i}=x_{j}=0$ and $x_{k}\in \left( 0,\frac{9}{10}\right)$. Let $x^{\prime }\in WP(R)$ be such that $x_{j}^{\prime }=x_{k},$ $x_{k}^{\prime }=x_{j},$ and for each $i\in N\backslash \left\{ j,k\right\} ,$ $x_{i}^{\prime }=x_{i}.$ Since F satisfies anonymity, $x^{\prime }\in F(R).$ Let $R_{i}^{\prime }\in \mathcal { R}$ be such that $d(R_{i}^{\prime })=1.$ Since $L(R_{i},0)\subseteq L(R_{i}^{\prime },0)=\left[ 0,1\right] ,$ by Maskin monotonicity of F, $x,x^{\prime }\in F(R_{i}^{\prime },R_{-i}).$ For $x\in F(R)$ and $x^{\prime }\in F(R_{i}^{\prime },R_{-i}),$ we must have $x_{i}=x_{i}^{\prime },$ and $x_{j}\ne x_{j}^{\prime }.$ Therefore, F does not satisfy weak non-bossiness.

Finally, we extend the model so that changes in the set of agents and the amount to be allocated are allowed. We introduce some notation. Let ${\mathbb {N}}$ be the set of potential agents indexed by natural numbers. Let ${\mathcal {N}}$ be the class of non-empty and finite subsets of ${\mathbb {N}}$. Each agent $i\in {\mathbb {N}}$ has a single-dipped preference $R_{i}$ over ${\mathbb {R}} _{+}.$ Let ${\mathcal {R}}_{+}$ denote the set of single-dipped preferences over ${\mathbb {R}} _{+}.$ Let $\Omega \in {\mathbb {R}} _{+}$ denote the amount of the resource.

An economy is defined by $e\equiv \left( N,\left( R_{i}\right) _{i\in N},\Omega \right)$, in which $N\in {\mathcal {N}}$ is the set of agents, $\ R_{i}\in {\mathcal {R}}_{+}$ is i’s preference over ${\mathbb {R}} _{+}$, and $\Omega \in {\mathbb {R}} _{+}$ is the amount of the resource to be allocated among N. For each $N\in {\mathcal {N}},$ let ${\mathcal {E}}^{N}$ denote the set of economies in which the set of agents is denoted by N. For each $e\in {\mathcal {E}}^{N}$, an allocation $x\in {\mathbb {R}} _{+}^{N}$ is feasible for e if $\sum \nolimits _{i\in N}x_{i}=\Omega .$ A solution is a mapping F which associates with each economy $e\in {\mathcal {E}}^{N}$, a non-empty subset of feasible allocations for e.

For each $e\in {\mathcal {E}}^{N},$ the binary mechanism $\Gamma _{B}$ is defined such that for each $i\in N,$ $M_{i}=\left\{ 0,1\right\}$, and for each $m\in \underset{i\in N}{\prod }M_{i}$,

$$\begin{aligned} g_{i}(e,m)=\left\{ \begin{array}{cc} \frac{\Omega }{\left| \left\{ i\in N\text { }|m_{i}=1\right\} \right| } &{} \text {if }m_{i}=1 \\ 0 &{} \text {if }m_{i}=0\text { and }\left\{ i\in N\text { }|m_{i}=1\right\} \ne \emptyset \\ \frac{\Omega }{\left| N\right| } &{} \text {if }m_{i}=0\text { and } \left\{ i\in N\text { }|m_{i}=1\right\} =\emptyset . \end{array} \right. \end{aligned}$$

Let $F_{B}$ denote the solution implemented by the binary mechanism.

Remark 9

A solution F satisfies consistency if for each $N\in {\mathcal {N}}$, each $e=\left( N,\left( R_{i}\right) _{i\in N},\Omega \right) \in {\mathcal {E}}^{N}$, each $x\in F(e)$, each $N^{\prime }\subset N,$ and each $e^{\prime }=\left( N,\left( R_{i}\right) _{i\in N^{\prime }},\Omega -\sum \nolimits _{i\in N\backslash N^{\prime }}x_{i}\right) \in {\mathcal {E}}^{N^{\prime }},$ we have $\left( x_{i}\right) _{i\in N^{\prime }}\in F(e^{\prime })$ (Thomson 1994). Here we show that $F_{B}$ satisfies consistency.

Without loss of generality let $\left| N\right| \ge 3,$ $e=\left( N,\left( R_{i}\right) _{i\in N},1\right) \in {\mathcal {E}}^{N},$ and $x^{S}\in F_{B}(e).$ It suffices to show that for each $i\in N,$ and each $e^{\prime }=\left( N\backslash \left\{ i\right\} ,\left( R_{j}\right) _{i\in N\backslash \left\{ i\right\} },1-x_{i}^{S}\right) \in {\mathcal {E}} ^{N\backslash \left\{ i\right\} },$ we have $\left( x_{j}^{S}\right) _{j\in N\backslash \left\{ i\right\} }\in F_{B}(e^{\prime }).$ We distinguish six cases.

Case 1: $\left| S\right| =0.$ Since $m^{S}$ is a Nash equilibrium of $\ \Gamma _{B}$ for $e\in {\mathcal {E}}^{N}$, for each $j\in N\backslash \left\{ i\right\} ,$

$$\begin{aligned} g_{j}\left( e,0,m_{N\backslash \left\{ j\right\} }^{S}\right) =\frac{1}{\left| N\right| }\,R_{j}\,1=g_{j}\left( e,1,m_{N\backslash \left\{ j\right\} }^{S}\right) , \end{aligned}$$

so that by single-dippeness of $R_{j},$ $\frac{1}{\left| N\right| } \,R_{j}\,\frac{\left| N\right| -1}{\left| N\right| }.$ Since $x_{i}^{S}=\frac{1}{\left| N\right| },$ for each $j\in N\backslash \left\{ i\right\} ,$

$$\begin{aligned} g_{j}\left( e^{\prime },0,m_{N\backslash \left\{ i,j\right\} }^{S}\right) =\frac{1}{ \left| N\right| }\,R_{j}\,\frac{\left| N\right| -1}{ \left| N\right| }=g_{j}\left( e^{\prime },1,m_{N\backslash \left\{ i,j\right\} }^{S}\right) , \end{aligned}$$

so that $\left( m_{j}^{S}\right) _{j\in N\backslash \left\{ i\right\} }$ is a Nash equilibrium of $\ \Gamma _{B}$ for $e^{\prime }\in {\mathcal {E}} ^{N\backslash \left\{ i\right\} }$. Hence, $\left( x_{j}^{S}\right) _{j\in N\backslash \left\{ i\right\} }\in F_{B}(e^{\prime }).$

Case 2: $\left| S\right| =1$ and $i\in S.$ Since $x_{i}^{S}=1,$ the set is feasible allocations for $e^{\prime }=\left( N\backslash \left\{ i\right\} ,\left( R_{j}\right) _{i\in N\backslash \left\{ i\right\} },1-x_{i}^{S}\right)$ is a singleton. Hence, by non-emptiness of $F_{B},$ $\left( x_{j}^{S}\right) _{j\in N\backslash \left\{ i\right\} }\in F_{B}(e^{\prime }).$

Case 3: $\left| S\right| =1$ and $i\notin S.$ Let $\left| S\right| =\left\{ j\right\} .$ Since $m^{S}$ is a Nash equilibrium of $\ \Gamma _{B}$ for $e\in {\mathcal {E}}^{N}$ , for $j\in N\backslash \left\{ i\right\} ,$ we have

$$\begin{aligned} g_{j}\left( e,1,m_{N\backslash \left\{ j\right\} }^{S}\right) =1\,R_{j}\,\frac{1}{ \left| N\right| }=g_{j}\left( e,0,m_{N\backslash \left\{ j\right\} }^{S}\right) , \end{aligned}$$

so that by single-dippeness of $R_{j},$ $1\,P_{j}\,\frac{1}{\left| N\right| -1}.$ Since $x_{i}^{S}=0,$ for $j\in N\backslash \left\{ i\right\} ,$

$$\begin{aligned} g_{j}\left( e^{\prime },1,m_{N\backslash \left\{ i,j\right\} }^{S}\right) =1\,P_{j}\, \frac{1}{\left| N\right| -1}=g_{j}\left( e^{\prime },0,m_{N\backslash \left\{ i,j\right\} }^{S}\right) . \end{aligned}$$

Since $m^{S}$ is a Nash equilibrium of $\ \Gamma _{B}$ for $e\in {\mathcal {E}} ^{N}$ , for each $k\in N\backslash \left\{ i,j\right\} ,$ we have

$$\begin{aligned} g_{k}\left( e,0,m_{N\backslash \left\{ k\right\} }^{S}\right) =0\,R_{k}\,\frac{1}{2} =g_{k}\left( e,1,m_{N\backslash \left\{ k\right\} }^{S}\right) . \end{aligned}$$

Since $x_{i}^{S}=0,$ for each $k\in N\backslash \left\{ i,j\right\} ,$

$$\begin{aligned} g_{k}\left( e^{\prime },0,m_{N\backslash \left\{ i,k\right\} }^{S}\right) =0\,R_{k}\, \frac{1}{2}=g_{k}\left( e^{\prime },1,m_{N\backslash \left\{ i,k\right\} }^{S}\right) , \end{aligned}$$

so that $\left( m_{j}^{S}\right) _{j\in N\backslash \left\{ i\right\} }$ is a Nash equilibrium of $\ \Gamma _{B}$ for $e^{\prime }\in {\mathcal {E}} ^{N\backslash \left\{ i\right\} }$. Hence, $\left( x_{j}^{S}\right) _{j\in N\backslash \left\{ i\right\} }\in F_{B}(e^{\prime }).$

Case 4: $\left| S\right| =2$ and $i\in S.$ Let $\left| S\right| =\left\{ i,j\right\} .$ Since $m^{S}$ is a Nash equilibrium of $\ \Gamma _{B}$ for $e\in {\mathcal {E}}^{N}$ , for $j\in S\backslash \left\{ i\right\} ,$ we have

$$\begin{aligned} g_{j}\left( e,1,m_{N\backslash \left\{ j\right\} }^{S}\right) =\frac{1}{2} \,R_{j}\,0=g_{j}\left( e,0,m_{N\backslash \left\{ j\right\} }^{S}\right) , \end{aligned}$$

so that by single-dippeness of $R_{j},$ $\frac{1}{2}\,R_{j}\,\frac{1}{ \left| N\right| -1}.$ Since $x_{i}^{S}=\frac{1}{2},$ for $j\in S\backslash \left\{ i\right\} ,$

$$\begin{aligned} g_{j}\left( e^{\prime },1,m_{N\backslash \left\{ i,j\right\} }^{S}\right) =\frac{1}{2} \,R_{j}\,\frac{1}{\left| N\right| -1}=g_{j}\left( e^{\prime },0,m_{N\backslash \left\{ i,j\right\} }^{S}\right) . \end{aligned}$$

Since $m^{S}$ is a Nash equilibrium of $\ \Gamma _{B}$ for $e\in {\mathcal {E}} ^{N}$ , for each $k\in N\backslash \left\{ i,j\right\} ,$ we have

$$\begin{aligned} g_{k}\left( e,0,m_{N\backslash \left\{ k\right\} }^{S}\right) =0\,R_{k}\,\frac{1}{3} =g_{k}\left( e,1,m_{N\backslash \left\{ k\right\} }^{S}\right) , \end{aligned}$$

so that by single-dippedness of $R_{k},$ $0\,P_{k}\,\frac{1}{4}.$ Since $x_{i}^{S}=\frac{1}{2},$ for each $k\in N\backslash \left\{ i,j\right\} ,$

$$\begin{aligned} g_{k}\left( e^{\prime },0,m_{N\backslash \left\{ i,k\right\} }^{S}\right) =0\,P_{k}\, \frac{1}{4}=g_{k}\left( e^{\prime },1,m_{N\backslash \left\{ i,k\right\} }^{S}\right) , \end{aligned}$$

so that $\left( m_{j}^{S}\right) _{j\in N\backslash \left\{ i\right\} }$ is a Nash equilibrium of $\ \Gamma _{B}$ for $e^{\prime }\in {\mathcal {E}} ^{N\backslash \left\{ i\right\} }$. Hence, $\left( x_{j}^{S}\right) _{j\in N\backslash \left\{ i\right\} }\in F_{B}(e^{\prime }).$

Case 5: $\left| S\right| \ge 2$ and $i\notin S.$ Since $m^{S}$ is a Nash equilibrium of $\Gamma _{B}$ for $e\in {\mathcal {E}}^{N}$ , for each $j\in S,$ we have

$$\begin{aligned} g_{j}\left( e,1,m_{N\backslash \left\{ j\right\} }^{S}\right) =\frac{1}{\left| S\right| }\,R_{j}\,0=g_{j}\left( e,0,m_{N\backslash \left\{ j\right\} }^{S}\right) . \end{aligned}$$

Since $x_{i}^{S}=0,$ for each $j\in S,$

$$\begin{aligned} g_{j}\left( e^{\prime },1,m_{N\backslash \left\{ i,j\right\} }^{S}\right) =\frac{1}{ \left| S\right| }\,R_{j}\,0=g_{j}\left( e^{\prime },0,m_{N\backslash \left\{ i,j\right\} }^{S}\right) . \end{aligned}$$

Since $m^{S}$ is a Nash equilibrium of $\ \Gamma _{B}$ for $e\in {\mathcal {E}} ^{N}$ , for each $k\in N\backslash S,$ $k\ne i$, we have

$$\begin{aligned} g_{k}\left( e,0,m_{N\backslash \left\{ k\right\} }^{S}\right) =0\,R_{k}\,\frac{1}{ \left| S\right| +1}=g_{k}\left( e,1,m_{N\backslash \left\{ k\right\} }^{S}\right) , \end{aligned}$$

Since $x_{i}^{S}=0,$ for each for each $k\in N\backslash S,$ $k\ne i$, we have, 

$$\begin{aligned} g_{k}\left( e^{\prime },0,m_{N\backslash \left\{ i,k\right\} }^{S}\right) =0\,R_{k}\, \frac{1}{\left| S\right| +1}=g_{k}\left( e^{\prime },1,m_{N\backslash \left\{ i,k\right\} }^{S}\right) , \end{aligned}$$

so that $\left( m_{j}^{S}\right) _{j\in N\backslash \left\{ i\right\} }$ is a Nash equilibrium of $\Gamma _{B}$ for $e^{\prime }\in {\mathcal {E}} ^{N\backslash \left\{ i\right\} }$. Hence, $\left( x_{j}^{S}\right) _{j\in N\backslash \left\{ i\right\} }\in F_{B}(e^{\prime }).$

Case 6: $\left| S\right| \ge 3$ and $i\in S.$ Since $m^{S}$ is a Nash equilibrium of $\Gamma _{B}$ for $e\in {\mathcal {E}}^{N}$ , for each $j\in S\backslash \left\{ i\right\} ,$ we have

$$\begin{aligned} g_{j}\left( e,1,m_{N\backslash \left\{ j\right\} }^{S}\right) =\frac{1}{\left| S\right| }\,R_{j}\,0=g_{j}\left( e,0,m_{N\backslash \left\{ j\right\} }^{S}\right) , \end{aligned}$$

Since $x_{i}^{S}=0,$ for each $j\in S\backslash \left\{ i\right\} ,$

$$\begin{aligned} g_{j}\left( e^{\prime },1,m_{N\backslash \left\{ i,j\right\} }^{S}\right) =\frac{1}{ \left| S\right| }\,R_{j}\,0=g_{j}\left( e^{\prime },0,m_{N\backslash \left\{ i,j\right\} }^{S}\right) . \end{aligned}$$

Since $m^{S}$ is a Nash equilibrium of $\Gamma _{B}$ for $e\in {\mathcal {E}} ^{N}$ , for each $k\in N\backslash S,$ $k\ne i$, we have

$$\begin{aligned} g_{k}\left( e,0,m_{N\backslash \left\{ k\right\} }^{S}\right) =0\,R_{k}\,\frac{1}{ \left| S\right| +1}=g_{k}\left( e,1,m_{N\backslash \left\{ k\right\} }^{S}\right) , \end{aligned}$$

so that by single-dippedness of $R_{k},$ $0\,P_{k}\,\frac{\left| S\right| -1}{\left| S\right| }\times \frac{1}{\left| S\right| }.$¹² Since $x_{i}^{S}= \frac{1}{\left| S\right| },$ for each for each $k\in N\backslash S,$ $k\ne i$, we have, 

$$\begin{aligned} g_{k}\left( e^{\prime },0,m_{N\backslash \left\{ i,k\right\} }^{S}\right) =0\,P_{k}\, \frac{\left| S\right| -1}{\left| S\right| }\times \frac{1}{ \left| S\right| }=g_{k}\left( e^{\prime },1,m_{N\backslash \left\{ i,k\right\} }^{S}\right) , \end{aligned}$$

so that $\left( m_{j}^{S}\right) _{j\in N\backslash \left\{ i\right\} }$ is a Nash equilibrium of $\Gamma _{B}$ for $e^{\prime }\in {\mathcal {E}} ^{N\backslash \left\{ i\right\} }$. Hence, $\left( x_{j}^{S}\right) _{j\in N\backslash \left\{ i\right\} }\in F_{B}(e^{\prime }).$