3.1 The model and the related results

A resource selection game (RSG) is a triplet $\langle N,M,f\rangle$ where

• – $N:\{1, 2, \ldots, n\}$ is the set of agents,

• – $M:\{1, 2, \ldots, m\}$ is the set of resources,

• – $f:(f_{i})_{i = 1}^{m}$ is the profile of strictly monotonic increasing cost functions such that $f_{i}(0) = 0$ for all $i \in \{1,2,\ldots, m\}$ .

When q agents use resource i, each incurs a cost equal to $f_{i}(q)$ . Each agent tries to minimize the cost it incurs. In the rest of the paper, we fix the game $\langle N,M,f\rangle$ .

An allocation is a sequence $a:(a_{i})_{i=1}^{m}$ such that:

• – for each $i\in M$ , we have $a_{i}\subseteq N$ ;

• – for every $i, i ^{\prime}\in M$ such that $i\neq i^{\prime}$ , we have $a_{i} \cap a_{i^{\prime}} = \emptyset$ ;

• – and we have $\bigcup \limits_{i\in M} a_{i} = N$ .

Above, $a_{i}$ denotes the set of agents that are assigned to resource i at allocation a. Thus, at a, each agent in $a_{i}$ incurs a cost equal to $f_{i}(|a_{i}|)$ . Let $\mathcal{A}$ be the domain of allocations.

The maxcost of an allocation a is the maximum cost incurred by an agent at a. That is, the maxcost of allocation a equals $max_{i\in M}$ $f_{i}(|a_{i}|)$ .

The minmaxcost of the RSG, to be denoted by $\alpha$ , is the maxcost of the allocation whose maxcost is smallest. That is, $\alpha=\min_{a\in \mathcal{A}}$ $\{\max_{i\in M}$ $f_{i}(|a_{i}|)\}$ .

Let $q_i=\max\{q| q\in \mathbb{Z}_{\geq 0}, f_i(q)\leq \alpha \}$ . We refer to $q_{i}$ as resource i’s quota. That is, a resource’s quota is the maximum number of agents that can be assigned to it without making its cost exceed $\alpha$ . We distinguish between resources that can and that cannot attain the minmaxcost $\alpha$ . A resource i is a:

• – Type 1 resource if $f_{i}(q_{i}) = \alpha$ ,

• – Type 2 resource if $f_{i}(q_{i}) < \alpha$ .

Let $T_{1}$ and $T_{2}$ denote, respectively, the sets of type 1 and type 2 resources. Since the minmaxcost of the game is $\alpha$ , we have $T_{1}\neq \emptyset$ . Also, for $i\in T_{1}$ , let $\beta_{i}=f_{i}(q_{i}-1)$ . We refer to $\beta_{i}$ as resource i’s beta value. Note that for a type 1 resource i, its beta value is its cost when the number of agents assigned to it is one less than its quota.

Note that an RSG is a noncooperative game in the strategic form, although its formulation here is different from the formulation of a strategic-form game in Section 2. Here, agents’ payoffs are negative (i.e., they incur costs rather than receive payoffs), and an agent’s strategy space is the set M (i.e., each agent selects one of the resources).

In this context, we continue to use the terminology in Section 2 in regard to coalitions and coalition structures. In other words, i.e., c,C, $\mathcal{P}_{=1}(N)$ , $\mathcal{P}_{\geq1}(N)$ , $\mathcal{C}^{sse}$ , $\mathcal{C}^{ne}$ , $\mathcal{C}^{le}$ , $\mathcal{C}^{coe}$ , $\mathcal{C}^{cee}$ are as described in Section 2. We also use the terminology in Section 2 regarding the stability and equilibrium notions, but with one exception: Note that in an RSG, an allocation fully specifies the strategies of agents. Therefore, in this context, we speak of an “allocation” as a substitute for a strategy profile. Hence, in this context, rather than a strategy profile, we speak of an allocation being c-stable or C-stable; or as being a laminar equilibrium or a contiguous equilibrium.

Also, in this context, we represent a deviation by a coalition c as a sequence $(c_{i})_{i=1}^{m}$ such that: (i) $c_{1}\cup c_{2}\cup \cdots \cup c_{m}=c$ ; and (ii) for each $i,i^{\prime}\in M$ and $i\neq i^{\prime}$ , $c_{i}\cap c_{i^{\prime}}=\emptyset$ . That is, a deviation is an agreement by coalition members on which resources that they will use: $c_{i}$ is the set of coalition members who agree to use resource i. We use $a\circ(c_{i})_{i=1}^{m}$ to denote the allocation that results when coalition c takes deviation $(c_{i})_{i=1}^{m}$ at allocation a: i.e., after the deviation the set of agents that are assigned to resource i is $(a_{i}\setminus c)\cup c_{i}$ . Also, note that a deviation is a profitable deviation if at the resulting allocation, each coalition member becomes weakly better off (i.e., the cost that it incurs does not increase) and at least one of them becomes better off (i.e., the cost that it incurs decreases).

The notion of a super strong equilibrium is very appealing since it precludes profitable deviations by any coalition of agents. However, in most game forms, a super strong equilibrium is not guaranteed to exist. This is also true for RSGs; see Example 1 below.

RSGs are a subclass of congestion games introduced by Rosenthal (Reference Rosenthal1971). Rosenthal (Reference Rosenthal1971) showed that in congestion games, the existence of a (pure strategy) Nash equilibria is guaranteed. For the subclass of RSGs, Anshelevich et al. (Reference Anshelevich, Caskurlu and Hate2013) gave a characterization of the Nash Equilibria. We present their result below. ^{Footnote 8}

• – for each $i\in T_{2}$ , $\left \vert a_{i}\right \vert =q_{i}$ ;

• – for each $i\in T_{1}$ , $\left \vert a_{i}\right \vert \in \left \{q_{i}-1,q_{i}\right \} $ ;

• – for some $i\in T_{1}$ , $\left \vert a_{i}\right \vert =q_{i}$ .

Let allocation a be a Nash equilibrium. We need to designate the set of type 1 resources that are not assigned at a up to their quotas: Let $L(a)=\{i\in T_{1}\ |\ |a_{i}|=q_{i}-1\}$ . Also, let $H(a)=M\setminus L(a)$ . We refer to the resources in L(a) and in H(a) as low and high resources at a, respectively. The corollary below immediately follows from the above theorem and it will be useful later on.

Our first set of results resolves an open question in the literature. In their paper, Anshelevich et al. (Reference Anshelevich, Caskurlu and Hate2013) showed that in an RSG, for any given partition coalition structure, there exists a partition equilibrium. They also conjectured that the following more general claim holds: For any given laminar coalition structure, there exists a laminar equilibrium. In Section 3.2, we prove their conjecture in the special setting when there are only two resources (Theorem 5). In Section 3.4, we show that their conjecture also holds when resources are identical (Corollary 5). Alas, in Section 3.3, we show that in the general setting, their conjecture does not hold (Theorem 6).

Below, for reference, we present the main result in Anshelevich et al. (Reference Anshelevich, Caskurlu and Hate2013).

3.2 Laminar equilibrium exists in two-resource RSGs

This section is devoted to showing that laminar equilibrium always exists in two-resource RSGs. The proof is fairly involved. Therefore, to ease reading, we first give an outline of how we will proceed.

First, in Lemma 2, in a two-resource RSG, we give necessary and sufficient conditions for a Nash equilibrium allocation to be c-stable for some coalition c. Therefore, given Lemma 2, we prove the desired result by showing that for any laminar coalition structure C, there exists a Nash equilibrium allocation a such that for each $c \in C$ , a satisfies the conditions given in Lemma 2.

As it turns out, the desired allocation has a “balanced” configuration: First, since the allocation is a Nash equilibrium, by Theorem 2, each resource is assigned up to its quota or one less than its quota. But we show that the desired allocation also satisfies the following two properties: For each $c \in C$ , the members of coalition c are distributed to as many resources as possible. And given that this first property is satisfied, the sum of the resource congestion costs is made as small as possible. These two properties form the essence of what we call the “ $\gamma \beta$ -domination relation.” Thus, to find the desired allocation, we find a Nash equilibrium allocation that is maximal according to the $\gamma \beta$ -domination relation. In showing our result, we benefit from our so-called “two-color theorem of laminarity.” This theorem helps us show that if a Nash equilibrium allocation is not C-stable, then it cannot be maximal according to the $\gamma \beta$ -domination relation.

Therefore, we will proceed as follows: Below, we present Lemma 2. Then, we present Theorem 4, which presents our two-color theorem of laminarity. We then introduce our “ $\gamma \beta$ -domination relation.” Finally, we present our existence result in Theorem 5, which we prove by using our $\gamma \beta$ -domination relation and the results given in Lemma 2 and Theorem 4.

1. C1. if $\left \vert a_{i^{\prime}}\cap c\right \vert =0$ , then $\left \vert a_{i}\cap c\right \vert \leq1$ ;

2. C2. if $\beta_{i}=\beta_{i^{\prime}}$ and $\left \vert a_{i^{\prime}}\cap c\right \vert >0$ , then $\left \vert a_{i}\cap c\right \vert\leq \left \vert a_{i^{\prime}}\cap c\right \vert +1$ ;

3. C3. if $\beta_{i}<\beta_{i^{\prime}}$ and $\left \vert a_{i^{\prime}}\cap c\right \vert >0$ , then $\left \vert a_{i}\cap c\right \vert\leq \left \vert a_{i^{\prime}}\cap c\right \vert $ .

(only if)

By way of contradiction, suppose that a is c-stable but one of the lemma conditions is not satisfied.

If C1 is not satisfied, then $a_{i^{\prime}}\cap c=\emptyset$ and $\left \vert a_{i}\cap c\right \vert \geq2$ . Consider an agent $j\in a_{i}\cap c$ . But then, when an agent in $a_{i}\cap c$ deviates from resource i to $i^{\prime}$ , the member (or members) of coalition c that remains at resource i becomes better off. Also, note that the coalition member that deviates to resource $i^{\prime}$ becomes equally well-off. But then this is a profitable deviation, a contradiction. Therefore, if a a is c-stable, condition C1 is satisfied.

If C2 is not satisfied, then $\beta_{i}=\beta_{i^{\prime}}$ , $\left \vert a_{i^{\prime}}\cap c\right \vert >0$ , and $\left \vert a_{i}\cap c\right \vert \geq \left \vert a_{i^{\prime}}\cap c\right \vert +2$ . Let $\left \vert a_{i^{\prime}}\cap c\right \vert =k$ and $\left \vert a_{i}\cap c\right \vert =k+2+s$ , where $k>0$ and $s\geq0$ . Let $\widetilde{c}\subset a_{i}\cap c$ be such that $\left \vert \widetilde{c}\right \vert =k+1$ . Consider the deviation $\left( c_{1},c_{2}\right) $ such that $c_{i^{\prime}}=\widetilde{c}$ and $c_{i}=c\setminus \widetilde{c}$ . Note that the deviation makes better off the coalition members in the set $(a_{i}\cap c)\setminus \widetilde{c}$ , which is non-empty. Also, note that the deviation did not change the incurred costs of other members of coalition c. Thus, $\left(c_{1},c_{2}\right)$ is a profitable deviation by coalition c at a. Therefore, if a is c-stable, condition C2 is satisfied.

If C3 is not satisfied, then $\beta_{i}<\beta_{i^{\prime}}$ , $\left \vert a_{i^{\prime}}\cap c\right \vert >0$ , and $\left \vert a_{i}\cap c\right \vert>\left \vert a_{i^{\prime}}\cap c\right \vert $ . Let $\left \vert a_{i^{\prime}}\cap c\right \vert =k$ and $\left \vert a_{i}\cap c\right \vert =k+1+s$ , where $k>0$ and $s\geq0$ . Let $\widetilde{c}\subseteq a_{i}\cap c$ be such that $\left \vert \widetilde{c}\right \vert =k+1$ . Consider the deviation $\left(c_{1},c_{2}\right) $ such that $c_{i^{\prime}}=\widetilde{c}$ and $c_{i}=c\setminus \widetilde{c}$ . It is clear that $\left( c_{1},c_{2}\right) $ is a profitable deviation by coalition c at a, a contradiction. Therefore, if a is c-stable, C3 is satisfied.

Therefore, if a is c-stable, then the conditions given in the lemma are all satisfied.

(if)

By way of contradiction, suppose that for allocation a, the conditions C1, C2, C3 are satisfied but a is not c-stable. Then, there exists a profitable deviation $\left( c_{1},c_{2}\right) $ at allocation a. Let $a^{\prime}=a\circ \left( c_{1},c_{2}\right) $ .

Suppose that for some resource $i^{\prime \prime}\in \left \{ i,i^{\prime}\right \} $ , $\left \vert a_{i^{\prime \prime}}^{\prime}\right \vert>q_{i^{\prime \prime}}$ . Then, $\left \vert a_{i^{\prime \prime}}^{\prime}\right \vert >\left \vert a_{i^{\prime \prime}}\right \vert $ . Since $\left \vert a_{i^{\prime \prime}}^{\prime}\right \vert =\left \vert a_{i^{\prime \prime}}\right \vert -\left \vert a_{i^{\prime \prime}}\cap c\right \vert +\left \vert c_{i^{\prime \prime}}\right \vert $ , we must have $\left \vert c_{i^{\prime\prime}}\right \vert >\left \vert a_{i^{\prime \prime}}\cap c\right \vert $ . Then, $c_{i^{\prime \prime}}\neq \emptyset$ . Let $j\in c_{i^{\prime \prime}}$ . Since $\left \vert a_{i^{\prime \prime}}^{\prime}\right \vert >q_{i}$ , the cost that j incurs at $a^{\prime}$ is greater than the game’s minmaxcost, $\alpha$ . But at a, the cost that j incurs is less than or equal to the game’s minmaxcost (because a is a Nash equilibrium; see Theorem 2). This contradicts that $\left( c_{1},c_{2}\right) $ is a profitable deviation at a. Thus, it must be that for each resource $i^{\prime \prime}\in \left \{ i,i^{\prime}\right \} $ , $a_{i^{\prime \prime}}^{\prime}\leq q_{i^{\prime \prime}}$ .

Note that $\left \vert N\right \vert =\left \vert a_{i}\right \vert +\left \vert a_{i^{\prime}}\right \vert =q_{i}+q_{i^{\prime}}-1$ . Then, the fact that for each resource $i^{\prime \prime}\in \left \{ i,i^{\prime}\right \} $ , $a_{i^{\prime \prime}}^{\prime}\leq q_{i^{\prime \prime}}$ , implies that either $\left \vert a_{i}^{\prime}\right \vert =q_{i}$ and $\left \vert a_{i^{\prime}}^{\prime}\right \vert =q_{i^{\prime}}-1$ , or $\left \vert a_{i}^{\prime}\right \vert =q_{i}-1$ and $\left \vert a_{i^{\prime}}^{\prime}\right \vert=q_{i^{\prime}}$ .

Suppose that $\left \vert a_{i}^{\prime}\right \vert =q_{i}$ and $\left \vert a_{i^{\prime}}^{\prime}\right \vert =q_{i^{\prime}}-1$ . Then, it is clear that the sum of the costs incurred by members of coalition c is the same at allocations a and $a^{\prime}$ . But then, if at $a^{\prime}$ an agent in c is better off (compared to at a), it must be that at $a^{\prime}$ another agent in c is worse off. But then $\left( c_{1},c_{2}\right) $ cannot be a profitable deviation at a, a contradiction. Therefore, we must have $\left \vert a_{i}^{\prime}\right \vert =q_{i}-1$ and $\left \vert a_{i^{\prime}}^{\prime}\right \vert =q_{i^{\prime}}$ .

If $a_{i^{\prime}}\cap c=\emptyset$ , then by C1 we get $\left \vert a_{i}\cap c\right \vert \leq1$ . Since c is nonempty, we get $\left \vert a_{i}\cap c\right \vert =1$ and $\left \vert c\right \vert =1$ . But then $\left(c_{1},c_{2}\right) $ is a profitable deviation by a single-agent coalition, contradicting that a is a Nash equilibrium. Therefore, we obtain that $a_{i^{\prime}}\cap c\neq \emptyset$ . Let $\left \vert a_{i^{\prime}}\cap c\right \vert =k$ where $k>0$ .

Suppose that $\beta_{i}>\beta_{i^{\prime}}$ . Consider an agent $j\in a_{i^{\prime}}\cap c$ . Note that the cost that j incurs at a is $\beta_{i^{\prime}}$ , and the cost that j incurs at $a^{\prime}$ is either $\beta_{i}$ or $\alpha$ . Either way, j is worse off at allocation $a^{\prime}$ , contradicting that $\left( c_{1},c_{2}\right) $ is a profitable deviation at a. Therefore, $\beta_{i}\leq \beta_{i^{\prime}}$ .

Suppose that $\beta_{i}=\beta_{i^{\prime}}$ . Then, by C2, we find that $\left \vert a_{i}\cap c\right \vert =s$ where $s\leq k+1$ . Since $\left \vert a_{i}^{\prime}\right \vert =q_{i}-1$ , $\left \vert a_{i}\right \vert =q_{i}$ , and $\left \vert a_{i}^{\prime}\right \vert =\left \vert a_{i}\right \vert -\left \vert a_{i}\cap c\right \vert +\left \vert a_{i}^{\prime}\cap c\right \vert $ , we obtain that $\left \vert a_{i}^{\prime}\cap c\right \vert =\left \vert a_{i}\cap c\right \vert -1$ . Then, $\left \vert a_{i}^{\prime}\cap c\right \vert =s-1$ . At a, the agents in $a_{i^{\prime}}\cap c$ incur a cost equal to $\beta_{i^{\prime}}$ , which is less that the game’s minmaxcost $\alpha$ . Hence, at $a^{\prime}$ , they cannot be assigned to resource $i^{\prime}$ (where the cost incurred is $\alpha$ ). Therefore, $a_{i^{\prime}}\cap c\subseteq a_{i}^{\prime}\cap c$ . Then, $\left \vert a_{i}^{\prime}\cap c\right \vert \geq \left \vert a_{i^{\prime}}\cap c\right \vert $ . Therefore, $s-1\geq k$ . Since we also know that $s\leq k+1$ , we obtain that $s=k+1$ . Then $a_{i^{\prime}}\cap c=a_{i}^{\prime}\cap c$ . This means that at $a^{\prime} $ , agents in $a_{i^{\prime}}\cap c$ are assigned to resource i and incur a cost equal to $\beta_{i}$ , and agents in $a_{i}\cap c$ are assigned to resource $i^{\prime}$ and incur a cost equal to $\alpha$ . But then, all agents are equally well off at $a^{\prime}$ and a, contradicting that $\left( c_{1},c_{2}\right) $ is a profitable deviation at a. Therefore, $\beta_{i}\neq \beta_{i^{\prime}}$ .

Suppose that $\beta_{i}<\beta_{i^{\prime}}$ . Then, by C3, we find that $\left \vert a_{i}\cap c\right \vert =s$ where $s\leq k$ . Since $\left \vert a_{i}^{\prime}\right \vert =q_{i}-1$ , $\left \vert a_{i}\right \vert =q_{i}$ , and $\left \vert a_{i}^{\prime}\right \vert =\left \vert a_{i}\right \vert -\left \vert a_{i}\cap c\right \vert +\left \vert a_{i}^{\prime}\cap c\right \vert $ , we obtain that $\left \vert a_{i}^{\prime}\cap c\right \vert =\left \vert a_{i}\cap c\right \vert -1$ . Then, $\left \vert a_{i}^{\prime}\cap c\right \vert =s-1$ . Note that at a, the agents in $a_{i^{\prime}}\cap c$ incur a cost equal to $\beta_{i^{\prime}}<\alpha$ , and hence, at $a^{\prime}$ , they cannot be assigned to resource $i^{\prime}$ (where the cost incurred is $\alpha$ ). Therefore, $a_{i^{\prime}}\cap c\subseteq a_{i}^{\prime}\cap c$ . Then, $\left \vert a_{i}^{\prime}\cap c\right \vert \geq \left \vert a_{i^{\prime}}\cap c\right \vert$ . Therefore, $s-1\geq k$ . But this contradicts with the fact that $s\leq k$ . Therefore, $\beta_{i}<\beta_{i^{\prime}}$ cannot be true.

Since our supposition that $\left( c_{1},c_{2}\right) $ is a profitable deviation at a always leads to a contradiction, we find that when the conditions C1, C2, C3 are satisfied, the allocation a is c-stable.

This concludes our proof.

We present below our “the two-color theorem of laminarity”. We use it in showing Theorem 5 but we believe it may also be of independent interest in discrete mathematics. In simple terms, it states that for any laminar coalition structure C, given a subset $N^{\prime}\subseteq N$ , $N^{\prime}$ can be partitioned into two almost-equal-size subsets (i.e., into subsets $N_{B}^{\prime}$ and $N_{W}^{\prime}=N^{\prime}\setminus N_{B}^{\prime}$ where $\left \vert \left \vert N_{B}^{\prime}\right \vert -\left \vert N_{W}^{\prime}\right \vert \right \vert \leq1$ ) such that for each $c\in C$ , the partition divides also the members of coalition c into two almost-equal-size subsets (i.e., $\left \vert \left \vert N_{B}^{\prime}\cap c\right \vert -\left \vert N_{W}^{\prime}\cap c\right \vert \right \vert \leq1$ ). (The agents in $N_{B}^{\prime}$ and $N_{W}^{\prime}$ are referred to as “black” and “white” agents, respectively, and hence is the naming of our theorem.)

Let $C=C^{1}\cup C^{2}\cup \cdots \cup C^{t}$ where the sets $C^{1},C^{2},\cdots,C^{t}$ be defined as follows:

\begin{gather*}C^{1}=\left \{ c\in C\left \vert c\text{ is not a child of any coalition}c^{\prime}\in C\right. \right \} \text{,}\\\text{and for }2\leq s\leq t\text{,}\\C^{s}=\left \{ c\in C\left \vert c\text{ is a child of some coalition}c^{\prime}\in C^{s-1}\right. \right \} \text{.}\end{gather*}

For $c\in C$ , let $\#(c)$ be the number of children of c. For $\#(c)>0$ , we label the children of c as $c_{1},c_{2},\cdots,c_{\#(c)}$ . To make our labeling precise, we use the following rule: among coalitions $c_{1},c_{2},\cdots,c_{\#(c)}$ , $c_{1}$ is the one that includes the smallest-index agent; among coalitions $c_{2},\cdots,c_{\#(c)}$ , $c_{2}$ is the one that includes the smallest-index agent; and so on. Note that, since $\mathcal{P}_{=1}(N)\subseteq C$ , $c=c_{1}\cup c_{2}\cup \cdots \cup c_{\#(c)} $ . We are now ready to proceed with our proof.

Note that our assumption that $N\in C$ and $\mathcal{P}_{=1}(N)\subseteq C$ is innocuous: If this does not hold, we can redefine the set C as follows: $C:C\cup \left \{ N\right \} \cup \mathcal{P}_{=1}(N)$ . Then, when we identify the sets $N_{B}^{\prime}$ and $N_{W}^{\prime}$ as stipulated in the theorem statement, the stipulations are clearly also satisfied for our initial C.

We prove the theorem using mathematical induction on s as follows:

Base case: There exist $N_{B}^{1}\subseteq N^{\prime}$ and $N_{W}^{1}=N^{\prime}\setminus N_{B}^{1}$ such that $\left \vert N_{B}^{1}\right \vert =k$ , and for each $c\in C^{1}$ , $\left \vert \left \vert N_{B}^{1}\cap c\right \vert -\left \vert N_{W}^{1}\cap c\right \vert \right \vert\leq1$ .

Inductive Step:

1. (inductive hypothesis) For $s\in \left \{ 1,2,3,\cdots,t-1\right \} $ , let $N_{B}^{s}\subseteq N^{\prime}$ and $N_{W}^{s}=N^{\prime}\setminus N_{B}^{s}$ be such that $\left \vert N_{B}^{s}\right \vert =k$ , and for each $c\in C^{1}\cup C^{2}\cup \cdots \cup C^{s}$ , $\left \vert\left \vert N_{B}^{s}\cap c\right \vert -\left \vert N_{W}^{s}\cap c\right \vert\right \vert \leq1$ .

2. (inductive conclusion) Then, there exist $N_{B}^{s+1}\subseteq N^{\prime}$ and $N_{W}^{s+1}=N^{\prime}\setminus N_{B}^{s+1}$ such that $\left \vert N_{B}^{s+1}\right \vert =k$ , and for each $c\in C^{1}\cup C^{2}\cup \cdots \cup C^{s+1}$ , $\left \vert \left \vert N_{B}^{s+1}\cap c\right \vert-\left \vert N_{W}^{s+1}\cap c\right \vert \right \vert \leq1$ .

Note that when the proof by mathematical induction is done, the sets $N_{B}^{\prime}=N_{B}^{t}$ and $N_{W}^{\prime}=N_{W}^{t}$ satisfy the requirements in the theorem.

The base case is trivial: Since $N\in C$ , $C^{1}=\{N\}$ . Then, any two sets $N_{B}^{1}\subseteq N^{\prime}$ and $N_{W}^{1}=N^{\prime}\setminus N_{B}^{1}$ , where $\left \vert N_{B}^{1}\right \vert =k$ , will be as required.

We now show the inductive step: Suppose the inductive hypothesis is true. Let $N_{B}^{s+1}=N_{B}^{s}$ and $N_{W}^{s+1}=N_{W}^{s}$ . If for each $c\in C^{s+1}$ , $\left \vert \left \vert N_{B}^{s+1}\cap c\right \vert -\left \vert N_{W}^{s+1}\cap c\right \vert \right \vert \leq1$ , we are done. Thus, suppose that for some $c\in C^{s+1}$ , $\left \vert \left \vert N_{B}^{s+1}\cap c\right \vert -\left \vert N_{W}^{s+1}\cap c\right \vert \right \vert \geq2$ . Wlog, let $\left \vert N_{B}^{s+1}\cap c\right \vert -\left \vert N_{W}^{s+1}\cap c\right \vert \geq2$ . (The arguments are similar if $\left \vert N_{W}^{s+1}\cap c\right \vert -\left \vert N_{B}^{s+1}\cap c\right \vert \geq2$ .) Let $c^{\ast}\in C^{s} $ be the mother of c. By the inductive hypothesis,

\begin{equation*}-1\leq \left \vert N_{B}^{s+1}\cap c^{\ast}\right \vert -\left \vert N_{W}^{s+1}\cap c^{\ast}\right \vert ={\textstyle \sum \limits_{l=1}^{\#(c^{\ast})}}\left( \left \vert N_{B}^{s+1}\cap c_{l}^{\ast}\right \vert -\left \vert N_{W}^{s+1}\cap c_{l}^{\ast}\right \vert \right) \leq1\text{.}\end{equation*}

Since c is a child of $c^{\ast}$ and $\left \vert N_{B}^{s+1}\cap c\right \vert -\left \vert N_{W}^{s+1}\cap c\right \vert \geq2$ , the above inequality implies that there exists $l\in \left \{ 1,\cdots,\#(c^{\ast})\right \} $ such that

\begin{equation*}\left \vert N_{B}^{s+1}\cap c_{l}^{\ast}\right \vert -\left \vert N_{W}^{s+1}\cap c_{l}^{\ast}\right \vert \leq-1\text{.}\end{equation*}

Thus, $\left \vert N_{W}^{s+1}\cap c_{l}^{\ast}\right \vert \geq \left \vert N_{B}^{s+1}\cap c_{l}^{\ast}\right \vert +1\geq1$ . Let $j^{W}\in N_{W}^{s+1}\cap c_{l}^{\ast}$ .

From above, we also know that $\left \vert N_{B}^{s+1}\cap c\right \vert \geq \left \vert N_{W}^{s+1}\cap c\right \vert +2\geq2$ . Let $j^{B}\in N_{B}^{s+1}\cap c$ .

We now redefine the sets $N_{B}^{s+1}$ and $N_{W}^{s+1}$ as follows:

\begin{equation*}N_{B}^{s+1}:N_{B}^{s+1}\setminus \left \{ j^{B}\right \} \cup \left \{j^{W}\right \} \text{ and }N_{W}^{s+1}:N_{W}^{s+1}\setminus \left \{j^{W}\right \} \cup \left \{ j^{B}\right \} \text{.}\end{equation*}

Note that:

• – for $c_{l}^{\ast}$ , after $N_{B}^{s+1}$ and $N_{W}^{s+1}$ are redefined, the value $\left \vert \left \vert N_{B}^{s+1}\cap c_{l}^{\ast}\right \vert-\left \vert N_{W}^{s+1}\cap c_{l}^{\ast}\right \vert \right \vert $ becomes smaller or the same as before;

• – for c, after $N_{B}^{s+1}$ and $N_{W}^{s+1}$ are redefined, the value $\left \vert \left \vert N_{B}^{s+1}\cap c\right \vert -\left \vert N_{W}^{s+1}\cap c\right \vert \right \vert $ becomes smaller;

• – for $\widetilde{c}\in C^{1}\cup C^{2}\cup \cdots \cup C^{s+1}\setminus \left \{ c,c_{l}^{\ast}\right \} $ , after $N_{B}^{s+1} $ and $N_{W}^{s+1}$ are redefined, the value $\left \vert \left \vert N_{B}^{s+1}\cap \widetilde{c}\right \vert -\left \vert N_{W}^{s+1}\cap \widetilde{c}\right \vert \right \vert $ remains unchanged.

Obviously, the above process can be iterated, and the sets $N_{B}^{s+1}$ and $N_{W}^{s+1}$ can be redefined until the inductive conclusion is satisfied. This concludes our proof.

We introduce next our $\gamma \beta$ -dominance relation:

For an allocation a, its $\gamma$ -value w.r.t. a coalition structure C, which we denote by $\gamma(a,C)$ , is defined as follows:

\begin{align*}\gamma(a,C) & ={\textstyle \sum_{i\in M}}\{{\textstyle \sum \limits_{c\in C}}1(c,a_{i})\}\text{, where}\\1(c,a_{i}) & :\left \{\begin{array}[c]{l}1,\text{ if }c\cap a_{i}\neq \emptyset \\0,\text{ otherwise}\end{array}\right.\end{align*}

Loosely speaking, the $\gamma$ -value of allocation a is a cumulative measure of how “widely” coalitions are spread to resources at allocation a.

The $\beta$ -value of an allocation a, to be denoted by $\beta(a)$ , is defined as follows:

\begin{equation*}\beta(a)={\textstyle \sum \limits_{i\in M}}f_{i}(\left \vert a_{i}\right \vert )\text{.}\end{equation*}

That is, the $\beta$ -value of allocation a is the sum of the costs at resources at allocation a.

We say that allocation $a^{\prime}$ $\gamma \beta$ -dominates allocation a w.r.t. C if $\gamma(a^{\prime},C)>\gamma(a,C)$ or if $\gamma(a^{\prime},C)=\gamma(a,C)$ and $\beta(a^{\prime})<\beta(a)$ .

Let $A\subseteq \mathcal{A}$ be a subset of allocations. Clearly, there exists $a\in A$ such that, for each $a^{\prime}\in A\setminus \left \{ a\right \}$ , either a $\gamma \beta$ -dominates $a^{\prime}$ w.r.t. C, or a and $a^{\prime}$ cannot be compared according to the $\gamma \beta$ -domination relation w.r.t. C. We refer to such an allocation a as a “maximal element in A according to the $\gamma \beta$ -domination relation w.r.t. C.” Note that there may be more than one maximal elements in A.

We are now ready to present the main result of this section.

• – Case 1: $T_{2}\neq \emptyset$ .

• – Case 2: $T_{1}=\left \{ 1,2\right \} $ and $\beta_{1}=\beta_{2}$ .

• – Case 3: $T_{1}=\left \{ 1,2\right \} $ and $\beta_{1}\neq \beta_{2}$ .

Let allocation a be a Nash equilibrium. (Its existence is by Theorem 2.)

Case 1: $T_{2}\neq \emptyset$ .

By Theorem 2, $\left \vert T_{1}\right \vert =\left \vert T_{2}\right \vert=1$ , and $\left \vert a_{1}\right \vert =q_{1}$ , $\left \vert a_{2}\right \vert=q_{2}$ . But then it is trivial to see that a is a super strong equilibrium, and hence it is C-stable.

Case 2: $T_{1}=\left \{ 1,2\right \} $ and $\beta_{1}=\beta_{2}$ .

By Theorem 2, either $\left \vert a_{1}\right \vert =q_{1}-1$ and $\left \vert a_{2}\right \vert =q_{2}$ , or $\left \vert a_{1}\right \vert =q_{1}$ and $\left \vert a_{2}\right \vert =q_{2}-1$ . Thus, $\left \vert N\right \vert=q_{1}+q_{2}-1$ .

Let $k\geq1$ be such that $\left \vert N\right \vert =2k-1$ or $\left \vert N\right \vert =2k$ . Wlog, let $q_{1}\leq q_{2}$ . Then, $q_{1}\leq k\leq q_{2} $ .

By Theorem 4, there exist $N_{B}^{\prime}\subseteq N$ and $N_{W}^{\prime}=N\setminus N_{B}^{\prime}$ such that $\left \vert N_{B}^{\prime}\right \vert =k$ and for each $c\in C$ , $\left \vert N_{B}^{\prime}\cap c\right \vert \leq \left \vert N_{W}^{\prime}\cap c\right \vert +1$ .

Let $\widetilde{N}_{B}\subseteq N_{B}^{\prime}$ be such that $\left \vert\widetilde{N}_{B}\right \vert =q_{1}$ . Let $\widetilde{N}_{W}=N\setminus\widetilde{N}_{B}$ . Note that $\left \vert \widetilde{N}_{W}\right \vert=q_{2}-1$ . Since $\widetilde{N}_{B}\subseteq N_{B}^{\prime} $ and $N_{W}^{\prime}\subseteq \widetilde{N}_{W}$ , we obtain that for each $c\in C$ , $\left \vert \widetilde{N}_{B}\cap c\right \vert \leq \left \vert \widetilde{N}_{W}\cap c\right \vert +1$ . Therefore, for allocation $a^{\prime}$ such that $a_{1}^{\prime}=\widetilde{N}_{B}$ and $a_{2}^{\prime}=\widetilde{N}_{W}$ , the conditions C1 and C2 in Lemma 2 are satisfied, while the condition C3 is not applicable. (To ease comparison with lemma conditions, note that i and $i^{\prime}$ in the lemma statement are 1 and 2 in here, in order.) Therefore, by Lemma 2, $a^{\prime}$ is C-stable.

Case 3: $T_{1}=\left \{ 1,2\right \} $ and $\beta_{1}\neq \beta_{2}$ .

If a is C-stable, we are done. If not, we proceed as follows: We show the existence of an allocation $a^{\prime}$ such that $a^{\prime}$ is a Nash equilibrium and $a^{\prime}$ $\gamma \beta$ -dominates a w.r.t. C. This proves that a C-stable allocation exists because: If $a^{\prime}$ turns out to be C-stable, we are done. Otherwise, we can iterate the same arguments: We can find an allocation $a^{\prime \prime}$ such that $a^{\prime \prime}$ is a Nash equilibrium and $a^{\prime \prime}$ $\gamma \beta$ -dominates $a^{\prime}$ w.r.t. C, and so on. Since there exists a $\gamma \beta$ -maximal allocation in A w.r.t. C, our iterations must eventually yield a C-stable allocation.

Therefore, suppose that a is not C-stable. Let $i,i^{\prime}\in \left \{1,2\right \} $ be such that $\left \vert a_{i}\right \vert =q_{i}$ and $\left \vert a_{i^{\prime}}\right \vert =q_{i^{\prime}}-1$ .

By Lemma 2, there exists $c\in C$ such that one of the conditions C1, C2, C3 in Lemma 2 is not satisfied. Since $\beta_{1}\neq \beta_{2}$ , C2 is not applicable. Thus, either C1 or C3 is not satisfied.

Suppose that C1 is not satisfied. Then, there exists $c\in C$ such that $\left \vert a_{i^{\prime}}\cap c\right \vert =0$ and $\left \vert a_{i}\cap c\right \vert \geq2$ . Let $j,j^{\prime}\in a_{i}\cap c$ , $j\neq j^{\prime}$ . Let allocation $a^{\prime}$ be such that $a_{i}^{\prime}=a_{i}\setminus \left \{ j^{\prime}\right \} $ and $a_{i^{\prime}}^{\prime}=a_{i^{\prime}}\cup \left \{ j^{\prime}\right \} $ ; hence, $j\in a_{i}^{\prime}\cap c$ , $j^{\prime}\in a_{i^{\prime}}^{\prime}\cap c$ , and $1\left( c,a_{i}^{\prime}\right) =1\left( c,a_{i^{\prime}}^{\prime}\right)=1$ . By Theorem 2, $a^{\prime}$ is a Nash equilibrium. Also, note that $\gamma \left( a^{\prime},C\right) >\gamma \left( a,C\right) $ because:

• – For each $c^{\prime}\in C$ such that $c^{\prime}\cap c=\emptyset$ ,

  \begin{equation*}1\left( c^{\prime},a_{i}\right) +1\left( c^{\prime},a_{i^{\prime}}\right)=1\left( c^{\prime},a_{i}^{\prime}\right) +1\left( c^{\prime},a_{i^{\prime}}^{\prime}\right) \text{.}\end{equation*}
  (Because agents in $N\setminus c$ are allocated to resources in exactly the same way at allocations a and $a^{\prime}$ .)

• – For each $c^{\prime}\in C$ such that $c\subset c^{\prime}$ ,

  \begin{equation*}1\left( c^{\prime},a_{i}^{\prime}\right) +1\left( c^{\prime},a_{i^{\prime}}^{\prime}\right) \geq1\left( c^{\prime},a_{i}\right) +1\left( c^{\prime},a_{i^{\prime}}\right).\end{equation*}
  (Because $1\left( c,a_{i}^{\prime}\right) +1\left( c,a_{i^{\prime}}^{\prime}\right) =2$ and hence $1\left( c^{\prime},a_{i}^{\prime}\right)+1\left( c^{\prime},a_{i^{\prime}}^{\prime}\right) =2$ .)

• – For c,

  \begin{equation*}1\left( c,a_{i}^{\prime}\right) +1\left( c,a_{i^{\prime}}^{\prime}\right)>1\left( c,a_{i}\right) +1\left( c,a_{i^{\prime}}\right) \text{.}\end{equation*}
  (Because $1\left( c,a_{i}^{\prime}\right) +1\left( c,a_{i^{\prime}}^{\prime}\right) =2$ and $1\left( c,a_{i}\right) +$ $1\left(c,a_{i^{\prime}}\right) =1$ .)

• – For each $c^{\prime}\in C$ such that $c^{\prime}\subset c$ ,

  \begin{equation*}1\left( c^{\prime},a_{i}^{\prime}\right) +1\left( c^{\prime},a_{i^{\prime}}^{\prime}\right) \geq1\left( c^{\prime},a_{i}\right) +1\left( c^{\prime},a_{i^{\prime}}\right) \text{.}\end{equation*}
  (Because $1\left( c,a_{i}\right) +1\left( c,a_{i^{\prime}}\right) =1$ , and hence, $1\left( c^{\prime},a_{i}\right) +1\left( c^{\prime},a_{i^{\prime}}\right) =1$ .)

Thus, as required, allocation $a^{\prime}$ is a Nash equilibrium and $a^{\prime}$ $\gamma \beta$ -dominates a w.r.t. C.

Suppose that C3 is not satisfied. Thus, $\beta_{i}<\beta_{i^{\prime}}$ , and there exists $c\in C$ such that $\left \vert a_{i}\cap c\right \vert >\left \vert a_{i^{\prime}}\cap c\right \vert >0$ . Let k be such that $\left \vert a_{i^{\prime}}\cap c\right \vert =k-1$ . Note that $\left \vert a_{i}\cap c\right \vert \geq k\geq2$ .

For each $j\in a_{i^{\prime}}\cap c$ , we define agent $\widetilde{j}$ as follows: Let $\widetilde{c}\in C$ be such that $j\in \widetilde{c}\subseteq c$ , $a_{i}\cap \widetilde{c}\neq \emptyset$ , and there does not exist $\overline{c}\in C$ such that $j\in \overline{c}\subset \widetilde{c}$ and $a_{i}\cap\overline{c}\neq \emptyset$ . We pick $\widetilde{j}$ from inside the set $a_{i}\cap \widetilde{c}$ . (For precision, we may pick the smallest-index agent.)

Let $S_{i} =\left \{\widetilde{j}\left \vert j \in a_{i^{ \prime }} \cap c\right .\right \}$ . Note that, since $\left \vert a_{i^{\prime}}\cap c\right \vert =k-1$ , $\left \vert S_{i}\right \vert \leq k-1$ . Let $\overline{S}_{i}$ be such that $S_{i}\subset \overline{S}_{i}\subseteq \left( a_{i}\cap c\right) $ and $\left \vert \overline{S}_{i}\right \vert =k$ . Let $\overline{S}_{i,i^{\prime}}=\overline{S}_{i}\cup \left( a_{i^{\prime}}\cap c\right) $ . Note that:

• – $\left \vert \overline{S}_{i,i^{\prime}}\right \vert =2k-1\geq3$ , and

• – for each $c^{\prime}\in C$ such that $c^{\prime}\subseteq c$ and $1(c^{\prime},a_{i})+1(c^{\prime},a_{i^{\prime}})=2$ , $\left \vert \overline{S}_{i,i^{\prime}}\cap c^{\prime}\right \vert \geq2$ . (This is because of how we defined $\widetilde{j}$ and $\widetilde{c}$ above: for $j\in a_{i^{\prime}}\cap c$ , agent $\widetilde{j}$ is selected from inside the set $a_{i}\cap \widetilde{c}$ where $\widetilde{c}\subseteq c^{\prime}$ ; thus, $\widetilde{j}\neq j$ and $j,\widetilde{j}\in \overline{S}_{i,i^{\prime}}\cap c^{\prime}$ .)

We now apply Theorem 4 by setting $N^{\prime}=\overline{S}_{i,i^{\prime}}$ : There exist $N_{B}^{\prime}\subseteq\overline{S}_{i,i^{\prime}}$ and $N_{W}^{\prime}=\overline{S}_{i,i^{\prime}}\setminus \overline{S}_{i,i^{\prime}}$ such that $\left \vert N_{B}^{\prime}\right \vert =k$ and for each $\widetilde{c}\in C$ , $\left \vert\left \vert N_{B}^{\prime}\cap \widetilde{c}\right \vert -\left \vert N_{W}^{\prime}\cap \widetilde{c}\right \vert \right \vert \leq1$ . Let $a^{\prime}$ be the allocation such that $a_{i}^{\prime}=\left( a_{i}\setminus c\right) \cup N_{W}^{\prime}$ and $a_{i^{\prime}}^{\prime}=\left(a_{i}\setminus c\right) \cup N_{B}^{\prime}$ . Clearly, at $a^{\prime}$ , we have $\left \vert a_{i}^{\prime}\right \vert =q_{i}-1$ and $\left \vert a_{i^{\prime}}^{\prime}\right \vert =q_{i^{\prime}}$ . Hence, by Theorem 2, $a^{\prime}$ is a Nash equilibrium. Note that $\gamma \left( a^{\prime},C\right) \geq \gamma \left( a,C\right) $ because:

• – For each $c^{\prime}\in C$ such that $c^{\prime}\cap c=\emptyset$ ,

  \begin{equation*}1\left( c^{\prime},a_{i}\right) +1\left( c^{\prime},a_{i^{\prime}}\right)=1\left( c^{\prime},a_{i}^{\prime}\right) +1\left( c^{\prime},a_{i^{\prime}}^{\prime}\right) \text{.}\end{equation*}
  (Note that agents in $N\setminus c$ are allocated to resources in exactly the same way at allocations a and $a^{\prime}$ .)

• – For each $c^{\prime}\in C$ such that $c\subseteq c^{\prime}$ ,

  \begin{equation*}1\left( c^{\prime},a_{i}^{\prime}\right) +1\left( c^{\prime},a_{i^{\prime}}^{\prime}\right) \geq1\left( c^{\prime},a_{i}\right) +1\left( c^{\prime},a_{i^{\prime}}\right) \text{.}\end{equation*}
  (Note that $\overline{S}_{i,i^{\prime}}\subseteq c$ and $\left \vert \overline{S}_{i,i^{\prime}}\right \vert \geq3$ . Hence, via our application of Theorem 4, we obtain that $1\left( c^{\prime},a_{i}^{\prime}\right) =1\left( c^{\prime},a_{i^{\prime}}^{\prime}\right)=1$ .)

• – For each $c^{\prime}\in C$ such that $c^{\prime}\subset c$ and $\left \vert c^{\prime}\right \vert =1$ ,

  \begin{equation*}1\left( c^{\prime},a_{i}^{\prime}\right) +1\left( c^{\prime},a_{i^{\prime}}^{\prime}\right) =1\left( c^{\prime},a_{i}\right) +1\left( c^{\prime},a_{i^{\prime}}\right) =1\text{.}\end{equation*}
  (This is trivial: At any allocation, a single agent is assigned to exactly one resource.)

• – For each $c^{\prime}\in C$ such that $c^{\prime}\subset c$ and $\left \vert c^{\prime}\right \vert \geq2$ ,

  \begin{equation*}1\left( c^{\prime},a_{i}^{\prime}\right) +1\left( c^{\prime},a_{i^{\prime}}^{\prime}\right) \geq1\left( c^{\prime},a_{i}\right) +1\left( c^{\prime},a_{i^{\prime}}\right) \text{.}\end{equation*}
  (Note that: If $c^{\prime}\subseteq \left( a_{i}\cap c\right) $ or $c^{\prime}\subseteq \left( a_{i^{\prime}}\cap c\right) $ , we get $1\left( c^{\prime},a_{i}\right) +1\left( c^{\prime},a_{i^{\prime}}\right) =1$ , and the desired result follows trivially. If $1(c^{\prime},a_{i})+1(c^{\prime},a_{i^{\prime}})=2$ , then $\left \vert \overline{S}_{i,i^{\prime}}\cap c^{\prime}\right \vert\geq2$ . (See the bullet argument above indicated with ♣.) Hence, by our choices of $N_{B}^{\prime}$ and $N_{W}^{\prime}$ (via Theorem 4), we find that $1\left( c^{\prime},a_{i}\right)= 1\left( c^{\prime},a_{i^{\prime}}\right)=1$ .)

Note that $\beta(a^{\prime})=\alpha +\beta_{i}$ , $\beta(a)= \alpha +\beta_{i^{\prime}}$ , and since $\beta_{i}<\beta_{i^{\prime}}$ , we get $\beta(a^{\prime})<\beta(a)$ . Since $\gamma \left( a^{\prime},C\right) \geq \gamma \left( a,C\right) $ and $\beta(a^{\prime})<\beta(a)$ , we obtain that $a^{\prime} $ $\gamma \beta$ -dominates a w.r.t. C. Thus, as required, allocation $a^{\prime}$ is a Nash equilibrium and $a^{\prime}$ $\gamma \beta$ -dominates a w.r.t. C.

This concludes our proof.

3.3 Laminar equilibriummay not exist in general RSGs

This section is devoted to showing that a laminar equilibrium does not necessarily exist in RSGs (Theorem 6). The example that we use to show this result is an intricate one, consisting of a large number of agents and resources. We present it below.

• There are $n=14,052$ agents and $m=2001$ resources.

• Every resource is of type 1.

• The set of resources can be written as $M=M_{x}\cup M_{y}\cup M_{z}$ such that:

  1. – $M_{x}=\{x\}$ and $q_{x}=53$ .

  2. – $M_{y}=\{y_{1},y_{2},\ldots,y_{1000}\}$ , each resource in $M_{y}$ has the same cost function, and for $y\in M_{y}$ , $q_{y}=8$ .

  3. – $M_{z}=\{z_{1},z_{2},\ldots,z_{1000}\}$ , each resource in $M_{z}$ has the same cost function, and for $z\in M_{z}$ , $q_{z}=7$ .

  4. – For $y\in M_{y}$ and $z\in M_{z}$ , $\beta_{x}>\beta_{y}>\beta_{z}>$ $f_{x}\left( q_{x}-2\right)$ . $\diamond$

Note that C is laminar. We prove the theorem by showing that no C-stable allocation exists in Example 2. By way of contradiction, suppose that in Example 2, there exists an allocation a that is C-stable.

Note that by Corollary 1: $|L(a)|=1001$ ( $=53+8\times1000+7\times1000-14,052$ ). And $|H(a)|=2001-1001=1000$ . Since $\mathcal{P}_{=1}(N)\subset C$ , a is a Nash equilibrium. Therefore, using Corollary 1, at allocation a there are 1001 low resources and 1000 high resources.

We divide the proof into six parts:

(1) We show that $x\in L\left( a\right) $ .

By way of contradiction, suppose that $x\in H\left( a\right) $ . Then, in $M_{y}\cup M_{z}$ , there are 1001 resources that are low. Let $i,i^{\prime}$ be two of them ( $i\neq i^{\prime}$ ). Consider the agents $a_{i}\cup a_{i^{\prime}}$ . Note that $\left\vert a_{i}\cup a_{i^{\prime}}\right\vert=q_{i}+q_{i^{\prime}}-2\leq14$ . Let $N_{1}\cup N_{2}\subset a_{x}$ be such that $N_{1}$ and $N_{2}$ are disjoint, $\left\vert N_{1}\right\vert =q_{i}$ , and $\left\vert N_{2}\right\vert =q_{i^{\prime}}$ . We define allocation $a^{\prime}$ from a as follows.

• – Remove the agents in $N_{1}\cup N_{2}\cup a_{i}\cup a_{i^{\prime}}$ from their assigned resources.

• – Assign agents in $N_{1}$ to resource i, agents in $N_{2}$ to resource $i^{\prime}$ , agents in $a_{i}\cup a_{i^{\prime}}$ to resource x.

(The assignments of remaining agents are the same as before.)

At allocation $a^{\prime}$ , the agents assigned to resource x are now better off (since x is now assigned $q_{x}-2$ agents). All other agents are equally well-off at the two allocations. But then a is not N-stable, a contradiction. Thus, $x\in L\left( a\right) $ .

(2) We show that $\left\vert H\left( a\right) \cap M_{y}\right\vert\leq7$ . (Hence, $\left\vert H\left( a\right) \cap M_{z}\right\vert \geq993$ .)

By (1), we know that $x\in L\left( a\right) $ . Then, at a, in $M_{y}\cup M_{z}$ there are 1000 high resources and 1000 low resources. By way of contradiction, suppose that $\left\vert H\left( a\right) \cap M_{y}\right\vert \geq8$ . This implies that $\left\vert L\left( a\right) \cap M_{z}\right\vert \geq8$ . We define allocation $a^{\prime}$ from a as follows. We pick 7 high resources in $M_{y}$ : Wlog, let $y_{1},\cdots,y_{7}\in H\left( a\right) \cap M_{y}$ . We pick 8 low resources in $M_{z}$ : Wlog, let $z_{1},\cdots,z_{8}\in L\left( a\right) \cap M_{z}$ . We pick 49 agents assigned to x at a: Let $N_{x}\subset a_{x}$ be such that $\left\vert N_{x}\right\vert =49$ . Then:

• – Remove the agents in $N_{x}\cup a_{y_{1}}\cup\cdots\cup a_{y_{7}}\cup a_{z_{1}}\cup\cdots\cup a_{z_{8}}$ from their assigned resources.

• – Assign the 49 agents in $N_{x}$ to resources $y_{1},\cdots,y_{7}$ such that each resource is assigned 7 agents.

• – Assign the 56 agents in $a_{y_{1}}\cup\cdots\cup a_{y_{7}}$ to resources $z_{1},\cdots,z_{8}$ such that each resource is assigned 7 agents.

• – Assign the 48 agents in $a_{z_{1}}\cup\cdots\cup a_{z_{8}}$ to resource x. (The assignments of remaining agents are the same as before.)

At allocation $a^{\prime}$ , the agents assigned to resource x are now better off (since x is now assigned $q_{x}-2$ agents). The agents assigned to resources $y_{1},\cdots,y_{7}$ are also better off (because they are now assigned to low resources for which the beta value is smaller). The agents assigned to resources $z_{1},\cdots,z_{8}$ are equally well-off (because they are assigned to high resources at both a and $a^{\prime}$ ). The agents assigned to remaining resources are equally well-off. But then a is not N-stable, a contradiction. Thus, $\left\vert H\left( a\right) \cap M_{y}\right\vert \leq7$ . Hence, we also have $\left\vert H\left( a\right)\cap M_{z}\right\vert \geq993$ .

(3) We show that there exists $c\in\left\{ c_{1},\ldots,c_{6}\right\} $ such that there are at least 1159 agents in c that are assigned to resources in $H\left( a\right) \cap M_{z}$ at allocation a.

Above, by (2), at a there are at least 993 high resources in $M_{z}$ . Since each of them is assigned 7 agents, at a the number of agents assigned to high resources in $M_{z}$ is at least $993\times7=6951$ . But then by the generalized pigeonhole principle, there is a coalition $c\in\left\{c_{1},\ldots,c_{6}\right\} $ such that at a the number of agents in c that are assigned to high resources in $M_{z}$ is at least $\left\lceil\frac{6951}{6}\right\rceil =1159$ .

(4) Let $c\in\left\{ c_{1},\ldots,c_{6}\right\} $ be as described in (3). We show that there exists $z\in H\left( a\right) \cap M_{z}$ such that there are at least two agents in c that are assigned to z at allocation a.

Note that at a, the number of high resources in $M_{z}$ is at most 1000 (because $\left\vert M_{z}\right\vert =1000$ ). By (3), we also know that there are at least 1159 agents in c that are assigned to high resources in $M_{z}$ at allocation a. But then, by the pigeonhole principle, there exists $z\in H\left( a\right) \cap M_{z}$ such that there are at least two agents in c that are assigned to z at allocation a.

(5) Let $c\in\left\{ c_{1},\ldots,c_{6}\right\} $ be as described in (3). We show that for each resource $y\in L\left( a\right)\cap\left( M_{x}\cup M_{y}\right) $ , there are at least two agents in c that are assigned to y at allocation a.

By (4) there exists $z\in H\left( a\right) \cap M_{z}$ such that there are at least two agents in c that are assigned to z at allocation a. Thus, let $j,j^{\prime}\in c$ be such that $j\neq j^{\prime}$ and at a the agents j and $j^{\prime}$ are assigned to resource z.

By way of contradiction, suppose that there exists $y\in L\left( a\right)\cap\left( M_{x}\cup M_{y}\right) $ such that $\left\vert c\cap a_{y}\right\vert \leq1$ .

Suppose that $\left\vert c\cap a_{y}\right\vert =0$ . We define allocation $a^{\prime}$ from a as follows: Agent j is removed from resource z and then assigned to resource y. It is clear that at $a^{\prime}$ , coalition c is better off. But then a is not C-stable, a contradiction. Thus, $\left\vert c\cap a_{y}\right\vert \neq0$ .

Suppose that $\left\vert c\cap a_{y}\right\vert =1$ . Let $\widetilde{j}$ be the agent in $c\cap a_{y}$ . We define allocation $a^{\prime}$ from a as follows: Agents j and $j^{\prime}$ are removed from resource z and then assigned to resource y, and agent $\widetilde{j}$ is removed from resource y and then assigned to resource z. Note that at $a^{\prime}$ , the agents j and $j^{\prime}$ are equally well-off (they are still assigned to high resources), and the agents in c that are assigned to z ( $\widetilde{j}$ and perhaps some other agents) are better off (because z is now a low resource, and the beta value for z is smaller than the beta value for y). The remaining agents in c are equally well-off. But then a is not C-stable, a contradiction. Thus, $\left\vert c\cap a_{y}\right\vert \neq1$ . Therefore, $\left\vert c\cap a_{y}\right\vert \geq2$ .

(6) We conclude the proof as follows: Let c be as described in (3). By (1) and (2), there are at least 994 resources in $L(a)\cap\left( M_{x}\cup M_{y}\right) $ . By (5), the number of agents in coalition c that are assigned to resources in $L(a)\cap\left( M_{x}\cup M_{y}\right) $ is at least $2\times994=1988$ at allocation a. By (3), there are at least 1159 agents in c which are assigned to resources in $H\left( a\right) \cap M_{z}$ at allocation a. But then we get $\left\vert c\right\vert \geq1988+1159=3147$ . This contradicts the fact that $\left\vert c\right\vert =2342$ .

In light of our findings in Section 2, Theorem 6 also has the following corollary:

Feldman and Tennenholtz (Reference Feldman and Tennenholtz2010) showed that in RSGs, a super strong equilibrium is not guaranteed to exist. Above, we considered less restrictive notions of equilibrium. Alas, as shown in Theorem 6, an existence result cannot be obtained even for our less-restrictive equilibrium notions. Feldman and Tennenholtz (Reference Feldman and Tennenholtz2010) showed their negative result in an RSG where there are only two identical resources. A natural question is then whether or not existence results can be obtained for our less restrictive notions of equilibrium: (i) when resources are identical and/or (ii) when the number of resources is two. We elaborate on this question in the rest of the paper.

3.4 The existence results for contiguous and centralized equilibrium notions

In this section, we present several existence and non-existence results for contiguous and centralized equilibrium notions. First, we prove that a contiguous equilibrium exists when resources are identical (Theorem 7), but it may not exist when there are two non-identical resources (Theorem 8). Then, we prove that a centralized equilibrium may not exist even for the two-identical-resources case (Theorem 9).

(1) Let a be a Nash equilibrium allocation. Let c be some coalition of agents. We show that a is c-stable if for every pair of resources $i\in H(a)$ and $i^{\prime}\in L(a)$ , $|a_{i}\cap c|\leq|a_{i^{\prime}}\cap c|+1$ .

By way of contradiction, suppose that c satisfies the above condition and yet $(c_{i})_{i=1}^{m}$ is a profitable deviation at a. Let $\overline{a}=a\circ(c_{i})_{i=1}^{m}$ .

Since resources are identical, their quotas and beta values are the same. Let their quotas be q and their beta values be $\beta$ .

Suppose that for resource i, $\left\vert \overline{a}_{i}\right\vert >q$ . Then, it is clear that $c_{i}\neq\emptyset$ . Let $j\in c_{i}$ . Then, agent j is clearly worse off at $\overline{a}$ than at a. This contradicts that $(c_{i})_{i=1}^{m}$ is a profitable deviation at a. Thus, for each resource i, we have $\left\vert \overline{a}_{i}\right\vert \leqq_{i}$ . This implies that at $\overline{a}$ , there are at least as many high resources as at a.

Consider a resource, say x, that was low at a and that becomes high at $\overline{a}$ . Recall that for every pair of resources $i\in H(a)$ and $i^{\prime}\in L(a)$ , $|a_{i}\cap c|\leq|a_{i^{\prime}}\cap c|+1$ . This implies that at $\overline{a}$ , the number of coalition members assigned to resource x is bigger than or equal to the number of coalition members assigned to any high resource at a. But the above facts imply that: (1) The allocations a and $\overline{a}$ are both Nash equilibrium allocations. (2) Under both allocations, the number of coalition members incurring the minmaxcost is the same. Similarly, under both allocations, the number of coalition members incurring the cost $\beta$ is the same.

But then, the total cost incurred by coalition members is the same at allocations a and $\overline{a}$ . This contradicts that $(c_{i})_{i=1}^{m}$ is a profitable deviation at a, proving the desired conclusion.

(2) We show that for each $C\in\mathcal{C}^{coe}$ , there exists an allocation a such that a is a Nash equilibrium and the condition in (1) is satisfied for every $c\in C$ .

Let $C\in\mathcal{C}^{coe}$ . Let P be a path in accordance with coalition structure C. Wlog, let $P = 1-2-\cdots-n$ . To show (2), we will show that for C, there exists an allocation a that satisfies the condition in (1) for every $c\in C$ . We will construct this allocation with the following algorithm:

The above algorithm takes agents from the path order, and it places them to resources one by one. And when it reaches the last resource, it rolls over to the first resource and continues. And so forth. Notice that agents in a coalition (subsequently ordered in P) are placed to resources subsequently. Therefore, when the algorithm places a coalition member to a high resource, before it placies another coalition member to it, it places one coalition member to every other resource. Therefore, at the allocation a induced by the above algorithm, for each coalition $c\in C$ , the condition in (1) is satisfied.

This completes our proof.

In light of our findings in Section 2, Theorem 7 also has the following corollary:

• – $N=\{1,\ldots,6\}$ and $M=\{1,2\}$ .

• – $f_{1}$ is such that $f_{1}(1)=1,f_{1}(2)=2,f_{1}(3)=4$ .

• – $f_{2}$ is such that $f_{2}(1)=1,f_{2}(2)=2,f_{2}(3)=3,f_{2}(4)=4$ .

Let $C=\mathcal{P}_{=}(N)\cup\left\{ c_{1},c_{2},c_{3},c_{4},c_{5}\right\} $ be such that the coalitions are as illustrated below.

It is clear from the figure that $C\in\mathcal{C}^{coe}$ . In this game, we will show that no allocation is C-stable. By way of contradiction, suppose that there exists a C-stable allocation a.

Since $\mathcal{P}_{=1}(N)\subset C$ , a is a Nash equilibrium. Using Theorem 2, we obtain that there are two possibilities: $\left\vert a_{1}\right\vert =3$ and $\left\vert a_{2}\right\vert =3$ , or $\left\vert a_{1}\right\vert =2$ and $\left\vert a_{2}\right\vert =4$ . Note that at a, it must be that at most one agent in $c_{1}$ is assigned to the high resource. Otherwise, at a coalition $c_{1}$ has a profitable deviation: If one agent in the coalition deviates to the other resource, the other resource now becomes high. Thus, the well-being of the deviating agent remains the same (it is still assigned to a high resource) while the other agent (now assigned to a low resource) becomes better off. The same argument applies for coalitions $c_{2}$ and $c_{3}$ .

Note that if resource 2 is high at a (i.e., $\left\vert a_{2}\right\vert=4$ ), it must be that $c_{1}\subset a_{2}$ or $c_{2}\subset a_{2}$ or $c_{3}\subset a_{2}$ . We showed that this cannot be true. Therefore, at a resource 1 is high and resource 2 is low (i.e., $\left\vert a_{1}\right\vert =3$ and $\left\vert a_{2}\right\vert =3$ ).

Since resource 1 is high, we cannot have $c_{1}\subset a_{1}$ or $c_{2}\subset a_{1}$ or $c_{3}\subset a_{1}$ . But then, since $\left\vert a_{1}\right\vert =3$ , it must be that $\left\vert a_{1}\cap c_{1}\right\vert=\left\vert a_{1}\cap c_{2}\right\vert =\left\vert a_{1}\cap c_{3}\right\vert=1$ . Consider coalition $c_{2}$ . If $3\in a_{1}$ , we obtain that $c_{4}$ is such that $\left\vert a_{1}\cap c_{4}\right\vert =2$ and $\left\vert a_{2}\cap c_{4}\right\vert =1$ . If $4\in a_{1}$ , we obtain that $c_{5}$ is such that $\left\vert a_{1}\cap c_{5}\right\vert =2$ and $\left\vert a_{2}\cap c_{5}\right\vert =1$ . Wlog, suppose that the former case is true. But then, at a, consider the following deviation for $c_{4}$ : Each agent in $c_{4}$ deviates to the other resource. The deviation makes resource 1 low and resource 2 high. Note that at the induced allocation, the agents that deviated to resource 2 are equally well-off (they are still assigned to a high resource), and the agent that deviated to resource 1 is better off (because it is now assigned to a low resource for which the beta value is smaller). But then this is a profitable deviation, a contradiction.

In this game, we will show that no allocation is C-stable. By way of contradiction, suppose that there exists an allocation a such that a is C-stable.

Since $\mathcal{P}_{=1}(N)\subset C$ , a is a Nash equilibrium. Using Theorem 2, we obtain that at a, one resource is assigned two agents, and the other one is assigned three agents. Wlog, let $\left\vert a_{1}\right\vert =2$ and $\left\vert a_{2}\right\vert =3$ .

Suppose that $1\in a_{1}$ . Then, in $\{5,2,3,4\}$ there is one agent assigned to resource 1 and there are three agents assigned to resource 2. But then at a the coalition $\{5,2,3,4\}$ has a profitable deviation: Wlog, let $a_{1}=\left\{ 1,2\right\} $ and $a_{2}=\{3,4,5\}$ . At a, if agent 2 deviates to resource 2 and agents 3,4 deviate to resource 1, agent 5 becomes better off and the well-beings of the remaining agents in coalition $\{5,2,3,4\}$ do not change. This contradicts that a is C-stable. Thus, $1\in a_{2}$ . Now suppose that $4\in a_{1}$ . But then, the preceding arguments can be repeated for coalition $\{1,2,3,5\}$ , leading to a contradiction. Thus, $4\in a_{2}$ . Therefore, $a_{2}$ is $\{1,2,4\}$ or $\{1,3,4\}$ or $\{1,4,5\}$ . But then, we obtain that for coalitions $\left\{ 1,2\right\} $ or $\left\{3,4\right\} $ or $\left\{ 5,4\right\} $ , at least one of them is a subset of $a_{2}$ . But then at a, this coalition has a profitable deviation: If one agent in the coalition deviates to resource 1, this agent’s well-being remains the same while the other agent in the coalition becomes better off. This contradicts that a is C-stable. Therefore, a is not C-stable.