The Two-Stage Game Approach to Coalition Formation: Where We Stand and Ways to Go

Abstract

Coalition formation is often analysed in an almost non-cooperative way, as a two-stage game that consists of a first stage comprising membership actions and a second stage with physical actions, such as the provision of a public good. We formalised this widely used approach for the case where actions are simultaneous in each stage. Herein, we give special attention to the case of a symmetric physical game. Various theoretical results, in particular, for cartel games, are provided. As they are crucial, recent results on the uniqueness of coalitional equilibria of Cournot-like physical games are reconsidered. Various concrete examples are included. Finally, we discuss research strategies to obtain results about equilibrium coalition structures with abstract physical games in terms of qualitative properties of their primitives.

1. Introduction

Non-cooperative game theory plays an important role in the modern theory of coalition formation.1 Modelling coalition formation as a two-stage game under almost non-cooperative conditions is a very promising approach, albeit theoretically challenged. The roots of this approach can be found in articles such as [3,4] in the context of industrial organisation. However, its further development took place especially in the context of environmental economics, starting with articles such as [5,6]; see [7,8,9] for overviews.

In the present article, we provide a formalisation of a specific variant of the two-stage game approach in the case of complete information, transferable payoffs, and in each stage, independent simultaneous actions. We simply refer to such a game as a “two-stage coalition formation game.” Formally, it is defined by providing a player set N, a membership rule R, and a game in strategic form $\mathrm{\Gamma }$ with N as the player set, called “physical game”; we denote it by $(N;R;\mathrm{\Gamma })$. In the first stage players choose a membership action. This leads via the membership rule to a coalition structure $\mathcal{C}$ and a corresponding coalitional game ${\mathrm{\Gamma }}_{\mathcal{C}}$ which is played in the second stage. In this stage the members of each coalition in $\mathcal{C}$ cooperate and each coalition behaves like a single player, called “meta player.” After each meta player has chosen a physical action, each player obtains his payoff belonging to the played physical action profile. Definition 2 provides a formal definition of $(N;R;\mathrm{\Gamma })$. If we speak below about a two-stage coalition formation game, we always mean such a game.2

The topics of the present article are the equilibrium coalition structures for a two-stage coalition formation game $(N;R;\mathrm{\Gamma })$. In the literature, up to now, the notion of equilibrium coalition structure presupposes that the two-stage coalition formation game is regular, meaning that each possible coalitional game ${\mathrm{\Gamma }}_{\mathcal{C}}$ has a unique Nash equilibrium. Assuming regularity, the procedure to solve the game then is as follows: the unique Nash equilibrium corresponds to a physical action for each individual player, which in turn corresponds to a payoff for each individual player. In this way the two-stage game $(N;R;\mathrm{\Gamma })$ leads to a game in strategic form G, referred to as an “effective game.” Finally, G has to be solved. Usually this is done by determining the Nash equilibria set of G.3 Finally, the membership rule R provides for each Nash equilibrium $\mathbf{m}$ of G, an equilibrium coalition structure $R\left(\mathbf{m}\right)$.

An important special case of a two-stage coalition formation game is the cartel game, where players in the first stage decide whether or not to cooperate. This leads to a coalition structure where there is a (possibly empty) coalition of cooperators and various singleton coalitions. Initially put forward to analyse the incentives of firms to join an industrial cartel ([3]), applications of cartel games have spread to other areas. In particular, the game has been used to examine incentives of countries to join international environmental agreements.4

A two-stage coalition formation game $(N;R;\mathrm{\Gamma })$ contains the very basic structure shared by various coalition formation games that have additional features like sharing and support ([14,15]).5 We will disregard such extensions for three main reasons: (i) The 2-stage structure of the game may be lost;6 (ii) There are many possibilities for such extensions; and (iii) most importantly, because our “simple” coalition formation game $(N;R;\mathrm{\Gamma })$ is, in our opinion, not sufficiently understood. For example, although there are various articles on two-stage coalition formation games, there is, to the best of our knowledge, no theoretical result about equilibrium coalition structures that holds for an abstract class of physical games in terms of qualitative properties (such as convexity, monotonicity and symmetry) of the primitives of the physical game; only results for concrete (mostly symmetric) physical games (mostly with linear or quadratic conditional payoff functions) are available (see, for example, [4,16,17,18,19,20]). This casts serious doubt on the robustness of these results. For the further development of the theory of basic two-stage coalition formation games, various mathematical problems have to be addressed. Therefore, the first thing to do is to make the mathematical structure of such a game more transparent. Highlighting the formal structure is one aim of the present article. As [21] also did for the cartel game, transparency is obtained, among other things, by associating a game in strategic form (i.e., the effective game G) with a two-stage coalition formation game. In this way all results for games in strategic form apply via its effective game G to two-stage coalition formation games. We discuss this further in Section 11.

Our article is self-contained. It is organised as follows. Section 2 formulates the game rules of a two-stage coalition formation game $(N;R;\mathrm{\Gamma })$, and Section 4 provides its formalisation together with an explanation how the game is solved. Section 2 provides also a first example. The formal definition of a two-stage coalition formation game in Section 4 uses various notions which are defined in Section 3. Section 5 introduces a class of physical games which are quite popular in the literature about two-stage coalition formation games: Cournot-like games. Sufficient conditions are provided for the regularity of a two-stage coalition formation game with a Cournot-like game as a physical game. Section 7 deals with two-stage coalition formation games with a symmetric membership rule and a symmetric physical game; preparations for the results therein take place in Section 6. Section 9 further analyses cartel games. As the effective game of a cartel game is a binary action game, Section 8 first presents various useful results about binary action games, particularly concerning the existence of potentials. Section 10 presents some additional examples. In Section 11, we conclude with a discussion of important next steps in order to obtain more comprehensive results.

2. The Rules of the Game

To allow a clear analysis of the two-stage coalition formation game, we describe the rules of the game, and in the next section, provide the ingredients for dealing with these games.

The intended game is a two-stage game with complete information and transferable payoffs, where the players choose independently and simultaneously a (pure) action in each stage. Further rules of the game are as follows.

• The player set is $N=\{1,2,\dots ,n\}$ with $n\ge 2$. Each player i is characterised by a “membership” action set $M_i$, a “physical” action set $X_i$ and with $\mathbf{X}:=X_1\times \cdots \times X_n$, by a payoff function $f_i:\mathbf{X}\to \mathbb{R}$. Let $\mathbf{M}:=M_1\times \cdots \times M_n$.
• At the first stage, the players choose, simultaneously and independently, a membership action from their membership action sets. If each player i chooses $m_i$, then this gives a membership action profile $\mathbf{m}\in \mathbf{M}$. This action profile leads via a given membership rule R to the coalition structure $R\left(\mathbf{m}\right)$ (which is a partition of N).
• In the second stage, the players of each coalition in $R\left(\mathbf{m}\right)$ coordinate their choices of a physical action like a single player, called a “meta player.” The meta players simultaneously and independently choose a physical action by choosing a physical action for each of their members. The in this way a defined action profile for the meta players corresponds to a physical action profile $\mathbf{x}\in \mathbf{X}$. Each meta player $C\in R\left(\mathbf{m}\right)$ obtains a payoff ${\widehat{P}}_C\left(\mathbf{x}\right)={\sum }_{l\in C}{f}_l\left(\mathbf{x}\right)$ and each player i obtains a payoff $f_i\left(\mathbf{x}\right)$.

As time is not explicitly modelled, such a game has an almost static real-world structure. Even for this, seemingly simple, real-word structure of the game it is not trivial how to solve the game. Usually, as mentioned in the introduction (also see Section 4.3), regularity is assumed; i.e., that there is a unique Nash equilibrium for every membership action profile $\mathbf{m}$ of the game played in the second stage, with player set $R\left(\mathbf{m}\right)$, referred to as “coalitional game”. Denoting with $\widehat{\mathbf{x}}\left(\mathbf{m}\right)$ the with this equilibrium corresponding action profile, this leads to a payoff $g_i\left(\mathbf{m}\right)=f_i\left(\widehat{\mathbf{x}}\left(\mathbf{m}\right)\right)$ for each player i and in this way to a game in strategic form G, referred to as "effective game": this game has player set N, for player i action set $M_i$ and payoff function $g_i$. We refer to $g_i$ as the “effective payoff function” of player i. Finally, the Nash equilibria of G are determined; if $\mathbf{m}$ is such an equilibrium, then $R\left(\mathbf{m}\right)$ is an equilibrium coalition structure. (Formal definitions will be given later.)

As the remainder of the article is quite abstract and general, it may be helpful to consider a simple clarifying example of a cartel game. In a cartel game, each player has $M=\{0,1\}$ as membership action set. The membership rule, here denoted by $R_c$, assigns to each membership action profile $\mathbf{m}\in M^n$ a coalition structure $R_c\left(\mathbf{m}\right)$ as follows: all players i with $m_i=1$ jointly form a coalition and each player i with $m_i=0$ forms a singleton coalition. We refer to such a coalition structure as a “cartel coalition structure”. As with a physical game, we take a concrete, symmetric, Cournot-like public good game.

Example 1. 

Consider the cartel game with a physical game, the Cournot-like public good game, with common action set $X={\mathbb{R}}_{+}$ and with payoff functions

$$f_i\left(\mathbf{x}\right)=-\frac{1}{2}a{x}_i^2+b\sum _{l=1}^n{x}_l$$

where $a,b>0$.

The following notations for $\mathbf{m}\in M^n$ are useful:

$$\widehat{S}\left(\mathbf{m}\right)=\{i\in N|m_i=1\}and{\widehat{S}}_{\star }\left(\mathbf{m}\right)=\{i\in N|m_i=0\}.$$

Consider the game in the second stage for a given action profile $\mathbf{m}$ chosen in the first stage. In this game the payoff function ${\widehat{P}}_C$ of meta player $C\in R_c\left(\mathbf{m}\right)$ in terms of the action profile $\mathbf{x}\in \mathbf{X}=X^n$ equals

$${\widehat{P}}_C\left(\mathbf{x}\right)=\left\{\begin{array}{c}-\frac{1}{2}a{x}_i^2+b{x}_i+b\sum _{l\ne i}{x}_l if C=\left\{i\right\} with i\in {\widehat{S}}_{\star }\left(\mathbf{m}\right),\hfill \\ \sum _{i\in C}(-\frac{a}{2}{x}_i^2+\#\widehat{S}\left(\mathbf{m}\right)b{x}_i)+\#\widehat{S}\left(\mathbf{m}\right)b\sum _{l\notin C}{x}_l if C=\widehat{S}\left(\mathbf{m}\right).\hfill \end{array}\right.$$

It is clear that in this coalitional game, each meta player has a strictly dominant action: meta player $C=\left\{i\right\}$ has $b/a$ as a strictly dominant action and meta player $C=\widehat{S}\left(\mathbf{m}\right)$ has a strictly dominant action wherein each of its members plays $\#\widehat{S}\left(\mathbf{m}\right)b/a$. Thus, this game has a unique Nash equilibrium, the two-stage coalition formation game is regular and for the with this equilibrium corresponding action profile $\widehat{\mathbf{x}}\left(\mathbf{m}\right)$ we have

$${\widehat{x}}_i\left(\mathbf{m}\right)=\left\{\begin{array}{c}\frac{b}{a}if m_i=0,\hfill \\ \#\widehat{S}\left(\mathbf{m}\right)\frac{b}{a} if m_i=1.\hfill \end{array}\right.$$

The effective payoff function of player i is the function $g_i:M^n\to \mathbb{R}$ given by $g_i\left(\mathbf{m}\right)=f_i\left(\widehat{\mathbf{x}}\left(\mathbf{m}\right)\right)$. Thus

$$g_i\left(\mathbf{m}\right)=\left\{\begin{array}{c}-\frac{a}{2}{\left(\frac{b}{a}\right)}^2+b\left(\#\widehat{S}\left(\mathbf{m}\right)\#\widehat{S}\left(\mathbf{m}\right)\frac{b}{a}+(n-\#\widehat{S}\left(\mathbf{m}\right))\frac{b}{a})\right) if m_i=0,\hfill \\ -\frac{a}{2}{(\#\widehat{S}\left(\mathbf{m}\right)\frac{b}{a})}^2+b\left(\#\widehat{S}\left(\mathbf{m}\right)\#\widehat{S}\left(\mathbf{m}\right)\frac{b}{a}+(n-\#\widehat{S}\left(\mathbf{m}\right))\frac{b}{a}\right) if m_i=1.\hfill \end{array}\right.$$

The next step is to consider the Nash equilibria of the effective game G with player set N, common action set $M^n$, and payoff functions $g_i$. The game G usually is solved by determining its Nash equilibria. As $\#M=2$, G is a binary action game. The action profile $\mathbf{m}$ being a Nash equilibrium of G comes down to $g_i^{\prime }\left(\mathbf{m}\right)\le 0(i\in N)$; here $g_i^{\prime }\left(\mathbf{m}\right)$ is the marginal payoff of i at $\mathbf{m}$; i.e., the payoff change at $\mathbf{m}$ when player i changes his action from $m_i$ to $1-m_i$. As, for $\mathbf{m}$ with $\#\widehat{S}\left(\mathbf{m}\right)=1$, it holds that $R_c\left(\mathbf{m}\right)=R_c\left(\mathbf{0}\right)=\left\{\left\{l\right\}\right|l\in N\}$, $g_i^{\prime }\left(\mathbf{0}\right)=0(i\in N)$ follows, and thus $\mathbf{0}$ is a Nash equilibrium. However, as we will see below, there are other (more interesting) Nash equilibria.

We have, writing $s=\#\widehat{S}\left(\mathbf{m}\right)$ and letting $w_0\left(s\right)=(s^2-s+n-\frac{1}{2})\frac{b^2}{a}(0\le s\le n-1)$ and $w_1\left(s\right)=(\frac{1}{2}{s}^2-s+n)\frac{b^2}{a}(1\le s\le n)$,

$$g_i\left(\mathbf{m}\right)=\left\{\begin{array}{c}{w}_0\left(s\right) if m_i=0,\hfill \\ w_1\left(s\right) if m_i=1.\hfill \end{array}\right.$$

This implies $g_i^{\prime }\left(\mathbf{m}\right)=w_1(s+1)-w_0\left(s\right) if m_i=0$ and $g_i^{\prime }\left(\mathbf{m}\right)=w_0(s-1)-w_1\left(s\right)if{m}_i=1$. With

$$t\left(s\right)=w_1\left(s\right)-w_0(s-1) if 1\le s\le n,$$

we have derived the formula

$$g_i^{\prime }\left(\mathbf{m}\right)=\left\{\begin{array}{c}t(s+1) if m_i=0,\hfill \\ -t\left(s\right) if m_i=1.\hfill \end{array}\right.$$

Letting $t\left(0\right)=+\infty$ and $t(n+1)=-\infty$, this formula implies

$$\mathbf{m} is a Nash equilibrium\iff t(s+1)\le 0\le t\left(s\right).$$

With the above explicit expression for $g_i\left(\mathbf{m}\right)$ we find for $1\le s\le n$

$$t\left(s\right)=\left((\frac{1}{2}{s}^2-s+n)-({(s-1)}^2-(s-1)+n-\frac{1}{2})\right)\frac{b^2}{a}=(-\frac{1}{2}{s}^2+2s-\frac{3}{2})\frac{b^2}{a}.$$

So $t\left(0\right)=+\infty ,t\left(1\right)=0,t\left(2\right)=1/2,t\left(3\right)=0,t\left(4\right)=-3/2,t\left(5\right)=-14,\dots ,t(n+1)=-\infty$.

This implies that, for $n\ge 3$, $\mathbf{m}\in M^n$ is a Nash equilibrium if and only if $\widehat{S}\left(\mathbf{m}\right)\in \{0,2,3\}$ and the equilibrium coalition structures are exactly the cartel coalition structures with $0,2$ or 3 cooperators. For $n=2$ the equilibrium coalition structures are exactly the cartel coalition structures with 0 or 2 cooperators.

Observe that in this example G is a symmetric aggregative game,7 there exists an effective equilibrium cartel coalition structure (i.e., an equilibrium cartel coalition structure not equal to $\left\{\right\{1\},\{2\},\dots ,\{n\left\}\right\}$), that the sign of $t\left(s\right)$ does not depend on a and b and that the functions $w_0$ and $w_1$ are increasing. ⋄

3. Fundamental Objects

In this section we provide the fundamental formalisations for dealing with two-stage coalition formation games.

3.1. Games in Strategic Form

A game in strategic form $\mathrm{\Gamma }$ is an ordered 3-tuple

$$\mathrm{\Gamma }=(I;{\left(X_i\right)}_{i\in I};{\left(f_i\right)}_{i\in I}),$$

where I is a non-empty finite set, every $X_i$ is a non-empty set and every $f_i$ is a function

$$f_i:{\mathbf{X}}_I\to \mathbb{R},$$

where

$${\mathbf{X}}_I:=\prod _{i\in I}{X}_i;$$

i.e., the product of the family ${\left(X_i\right)}_{i\in I}$. The set I is called player set and its elements players. The set $X_i$ is called the action set of player i and its elements actions of player i.8 The function $f_i$ is called the payoff function of player i and the elements of ${\mathbf{X}}_I$, being by I indexed families ${\left(x_i\right)}_{i\in I}$ with $x_i\in X_i$, are called action profiles. For $i\in I$, we write

$$\widehat{ı}:=I\backslash \left\{i\right\} and {\mathbf{X}}_{\widehat{ı}}:=\prod _{j\in \widehat{ı}}{X}_j.$$

For $i\in I$ and $\mathbf{z}={\left(z_j\right)}_{j\in \widehat{ı}}\in {\mathbf{X}}_{\widehat{ı}}$, define the conditional payoff function

$f_i^{\left(\mathbf{z}\right)}:X_i\to \mathbb{R}$ by

$$f_i^{\left(\mathbf{z}\right)}\left(x_i\right):=f_i(x_i;\mathbf{z});$$

here, $(x_i;\mathbf{z})$ is a by I indexed family with $x_i$ for the element with index i and $z_j$ for the element with index $j\ne i$. Also define for $i\in I$ the best-reply correspondence $R_i:{\mathbf{X}}_{\widehat{ı}}⊸X_i$ by

$$R_i\left(\mathbf{z}\right):=\mathrm{argmax}{f}_i^{\left(\mathbf{z}\right)}.$$

Thus, the best-reply correspondence for a player assigns to each given strategy profile of his opponents, the set of actions that maximise his payoff. An action profile $\mathbf{x}={\left(x_i\right)}_{i\in I}\in {\mathbf{X}}_I$ is a (Nash) equilibrium of $\mathrm{\Gamma }$ if, for all $i\in I$, writing (given i) again $\mathbf{x}=(x_i;\mathbf{z})$, $x_i$ is a maximiser of the conditional payoff function $f_i^{\left(\mathbf{z}\right)}$, i.e., $x_i\in R_i\left(\mathbf{z}\right)$. We denote by

$$E\left(\mathrm{\Gamma }\right)$$

the set of Nash equilibria of $\mathrm{\Gamma }$.

Often, when dealing with games in strategic form, one takes $N=\{1,2,\dots ,n\}$ for the player set, and then, for the set of action profiles, instead of the product ${\mathbf{X}}_N={\prod }_{i\in N}{X}_i$, the Cartesian product $\mathbf{X}={\mathsf{X}}_{i=1}^n{X}_i=X_1\times \cdots \times X_n$. However, when dealing below with coalitional games where the players are subsets (so-called “meta players"), it is more natural not to number these subsets with $1,2,\dots$, but just to identify them with the subsets themselves; this then leads to a game with action profiles in a family product (instead of a Cartesian product). Below, in Definition 2, when defining our intended two-stage coalition formation game $(N;R;\mathrm{\Gamma })$, the game in strategic form $\mathrm{\Gamma }$ will have as player set $N=\{1,2,\dots ,n\}$ and the action profiles of the coalitional games will be elements of a family product.

A game in strategic form $\mathrm{\Gamma }=(N;{\left(X_i\right)}_{i\in N};{\left(f_i\right)}_{i\in N})$ where $N=\{1,2,\dots ,n\}$ and $X_1=\cdots =X_n=:X$ is symmetric if for each permutation $\pi$ of N, every $i\in N$ and every $\mathbf{x}\in \mathbf{X}=X^n$

$$f_{\pi \left(i\right)}=f_i\circ T_{{\pi }^{<-1>}};$$

(1)

i.e., $f_{\pi \left(i\right)}(x_1,\dots ,x_n)=f_i(x_{\pi \left(1\right)},\dots ,x_{\pi \left(n\right)})$ for every $(x_1,\dots ,x_n)\in X^n$; here, the mapping $T_{\pi }:X^n\to X^n$ is defined by

$$T_{\pi }(x_1,\dots ,x_n)=(x_{{\pi }^{<-1>}\left(1\right)},\dots ,x_{{\pi }^{<-1>}\left(n\right)}).$$

Many economic games, like Cournot-like games (see Section 5) are aggregative games. Aggregative games admit special, powerful techniques (see for instance [22,23,24]). Various definitions exist for the notion of an aggregative game. Here, we present a general one for a game in strategic form with player set N and actions sets $X_i$, subsets of ${\mathbb{R}}_{+}$. In order to do so, let $Y:={\sum }_{l\in N}{X}_l$ and $T_i:={\sum }_{j\ne i}{X}_j$.9 Also, for $i\in N$, let ${\mathsf{\Delta }}_i:=\{(x_i,y)\in X_i\times Y|y-x_i\in T_i\}$. Next note that the following two properties are equivalent:

• For every $i\in N$ and $z\in T_i$ there exists a function ${\tilde{f}}_i^{\left(z\right)}:X_i\to \mathbb{R}$ such that

  $$f_i\left(\mathbf{x}\right)={\tilde{f}}_i^{\left({\sum }_{j\ne i}{x}_l\right)}\left(x_i\right)(\mathbf{x}\in \mathbf{X}).$$

  (2)
• For every $i\in N$ there exists a function ${\pi }_i:{\mathsf{\Delta }}_i\to \mathbb{R}$ such that $f_i\left(\mathbf{x}\right)={\pi }_i(x_i,{\sum }_l{x}_l)(\mathbf{x}\in \mathbf{X})$.

Having said this, the game is aggregative if it satisfies one, thereby satisfying both properties. Note that if ${\pi }_1=\cdots ={\pi }_n$, then ($X_1=\cdots =X_n$ and) the game is symmetric.

3.2. Coalition Structures

In this subsection n is a positive integer and $N:=\{1,2,\dots ,n\}$. A partition of the set N is a set with as elements non-empty disjoint subsets of N whose union is N.10 A related notion is a partition of the positive integer n; this is a finite sequence $(k_1,\dots ,k_s)$ of positive integers such that $k_1\ge k_2\ge \cdots \ge k_s$ and $k_1+\cdots +k_s=n$.11 We denote the set of partitions of N by ${\mathcal{C}}_N$ and refer to a partition of N also as coalition structure. This last notion is used in order to define now below the notion of congruent “coalition structures.”12

Given a coalition structure $\mathcal{C}$, we denote for $i\in N$ by ${\mathcal{C}}_{\left[i\right]}$ the unique element of $\mathcal{C}$ with

$$i\in {\mathcal{C}}_{\left[i\right]}.$$

Given a coalition structure $\mathcal{C}$, the sizes (i.e., number of elements) of the subsets in $\mathcal{C}$ induce in a natural way a partition $\left[\mathcal{C}\right]$ of n. On ${\mathcal{C}}_N$ the relation ∼ defined by

$$\mathcal{C}\sim {\mathcal{C}}^{\prime } \text{means} \left[\mathcal{C}\right]=\left[{\mathcal{C}}^{\prime }\right],$$

(3)

which is an equivalence relation.13 We refer to $\mathcal{C}\sim {\mathcal{C}}^{\prime }$ as $\mathcal{C}$ and ${\mathcal{C}}^{\prime }$ are congruent. It is clear that coalition structures $\mathcal{C},{\mathcal{C}}^{\prime }$ of N are congruent if and only if there exists a permutation $\pi$ of N such that ${\mathcal{C}}^{\prime }=\left\{\pi \left(C\right)\right|C\in \mathcal{C}\}$.

Finally, the following additional terminology may be useful: we call the coalition structure $\left\{\right\{1\},\dots ,\{n\left\}\right\}$ the ineffective coalition structure and refer to every other coalition structure as effective coalition structure.

3.3. Coalitional Equilibria

In this subsection n is again a positive integer and $N=\{1,2,\dots ,n\}$. Consider a game in strategic form $\mathrm{\Gamma }$ with player set N:

$$\mathrm{\Gamma }=(N;{\left(X_i\right)}_{i\in N};{\left(f_i\right)}_{i\in N}).$$

For every partition $\mathcal{C}$ of N we are going to define a game in strategic form ${\mathrm{\Gamma }}_{\mathcal{C}}$ with a player set the elements of $\mathcal{C}$, being non-empty subsets of N. Therefore, it is useful to refer to a non-empty subset of N as coalition and to a partition of N as a coalition structure (of N).

Given the game in strategic form $\mathrm{\Gamma }$, we introduce the following notations. First, for a coalition C

$$K_C:=\prod _{l\in C}{X}_l.$$

So an element $k_C$ of $K_C$ is a by C indexed family ${\left(k_{C;l}\right)}_{l\in C}$ with $k_{C;l}\in X_l(l\in C)$:

$$k_C={\left(k_{C;l}\right)}_{l\in C}.$$

Second, for a coalition structure $\mathcal{C}$, we define the mapping $J_{\mathcal{C}}:{\prod }_{C\in \mathcal{C}}{K}_C\to \mathbf{X}$ by

$$J_{\mathcal{C}}\left({\left(k_C\right)}_{C\in \mathcal{C}}\right):={\left(k_{{\mathcal{C}}_{\left[i\right]};i}\right)}_{i\in N}.$$

(4)

We refer to it as the canonical mapping. We call $J_{\mathcal{C}}\left(\mathbf{k}\right)$ the with $\mathbf{k}$ associated action profile in $\mathrm{\Gamma }$. Note that $J_{\mathcal{C}}$ is a bijection.

Having these notations, we are ready to formalise the intended notion of coalitional equilibrium (with physical game $\mathrm{\Gamma }$) as already outlined in Section 1.

Definition 1. 

Given a game in strategic form $\mathrm{\Gamma }=(N;{\left(X_i\right)}_{i\in N};{\left(f_i\right)}_{i\in N})$ and a coalition structure $\mathcal{C}$ of N, the (with $\mathcal{C}$ associated) game in strategic form ${\mathrm{\Gamma }}_{\mathcal{C}}$ is defined as the game in strategic form

$${\mathrm{\Gamma }}_{\mathcal{C}}:=(\mathcal{C};{\left(K_C\right)}_{C\in \mathcal{C}};{\left(P_C\right)}_{C\in \mathcal{C}}) where P_C:=\sum _{i\in C}{f}_i\circ J_{\mathcal{C}}.\diamond$$

So $P_C:{\mathbf{K}}_{\mathcal{C}}\to \mathbb{R}$ and $P_C\left(\mathbf{k}\right)={\sum }_{i\in C}{f}_i\left(J_{\mathcal{C}}\left(\mathbf{k}\right)\right)$.

It may be appropriate to define for meta player C his payoff function in terms of physical action profiles by

$${\widehat{P}}_C\left(\mathbf{x}\right)=P_C\left(J_C^{<-1>}\left(\mathbf{x}\right)\right).$$

So ${\widehat{P}}_C\left(\mathbf{x}\right)={\sum }_{i\in C}{f}_i\left(\mathbf{x}\right)$.

Clearly the payoff function $P_C$ of the coalitional game ${\mathrm{\Gamma }}_{\mathcal{C}}$ is completely determined by $\mathcal{C},C$ and the $f_i(i\in C)$.14 The intended interpretation is that in ${\mathrm{\Gamma }}_{\mathcal{C}}$ the players inside each coalition coordinate their actions. We also will refer to the elements of $\mathcal{C}$ as meta players. And we refer to ${\mathrm{\Gamma }}_{\mathcal{C}}$ also as a coalitional game. A Nash equilibrium of ${\mathrm{\Gamma }}_{\mathcal{C}}$ is also called a coalitional Nash equilibrium of $\mathrm{\Gamma }$; more precisely, we speak of a $\mathcal{C}$-equilibrium of $\mathrm{\Gamma }$. As far as we know, coalitional games first were considered in [26]. For more on coalitional equilibria (and related notions), see [27].

The action sets ${\mathbf{X}}_C$ of ${\mathrm{\Gamma }}_{\mathcal{C}}$ are typically more dimensional. Note that if

$$\mathcal{C}=\left\{\right\{1\},\{2\},\dots \{n\left\}\right\},$$

then ${\mathrm{\Gamma }}_{\mathcal{C}}=\mathrm{\Gamma }$ and a $\mathcal{C}$-equilibrium of $\mathrm{\Gamma }$ is nothing else than a Nash equilibrium of $\mathrm{\Gamma }$. And if

$$\mathcal{C}=\left\{N\right\},$$

then a $\mathcal{C}$-equilibrium is nothing else than a maximiser of the total payoff function ${\sum }_{i\in N}{f}_i$.

3.4. Membership Rules

In this subsection n again is a positive integer and $N=\{1,2,\dots ,n\}$. A membership rule (for N) is a mapping

$$R:\mathbf{M}\to {\mathcal{C}}_N,$$

where the $M_l$ non-empty sets and $\mathbf{M}={\mathsf{X}}_{i=1}^n{M}_i$, with the following property: the ineffective coalition structure $\left\{\right\{1\},\dots ,\{n\left\}\right\}$ is in the image of R.15 A classification of membership rules can be found in [28].

Given a membership rule $R:\mathbf{M}\to {\mathcal{C}}_N$, a coalition structure is said to be possible if it belongs to $R\left(\mathbf{M}\right)$. Thus, the ineffective coalition structure is possible.

We call a membership rule symmetric if the membership action sets are identical and for each permutation $\pi$ of N and $\mathbf{m}\in \mathbf{M}$

$$R\left(T_{\pi }\left(\mathbf{m}\right)\right)=\left\{\pi \left(C\right)\right|C\in R\left(\mathbf{m}\right)\}.$$

(5)

The following result should be clear:

Proposition 1. 

For a symmetric membership rule R, a permutation π of N and action profiles $\mathbf{m},{\mathbf{m}}^{\prime }\in \mathbf{M}$ it holds that ${\mathbf{m}}^{\prime }=T_{\pi }\left(\mathbf{m}\right)\Rightarrow R\left(\mathbf{m}\right)\sim R\left({\mathbf{m}}^{\prime }\right)$.16 ⋄

4. Two-Stage Coalition Formation Games

4.1. Notion

After having presented the rules of the game in Section 2, we now focus on the formal definition of the two-stage coalition formation game.

Definition 2. 

A two-stage coalition formation game is a 3-tuple

$$(N;R;\mathrm{\Gamma })$$

where $\mathrm{\Gamma }=(N;{\left(X_i\right)}_{i\in N};{\left(f_i\right)}_{i\in N})$ is a game in strategic form with player set $N=\{1,2,\dots ,n\}$ with $n\ge 2$, called the physical game and $R:\mathbf{M}\to {\mathcal{C}}_N$ is a membership rule for N. ⋄

We call $M_i$ the membership action set of player i and $X_i$ his physical action set.

An additional possibility for the above game is to allow for payoff transfers between the players. This occurs, for example, if players who join a coalition redistribute their payoffs according to some sharing rule; for example, equal sharing, where the total payoff is divided equally among the coalition members. Although sharing is an important issue, we will not deal with it, since a general formalisation is complicated (for example, the additional rules may refer explicitly to the chosen membership actions and physical actions). In addition, sharing would destroy the two-stage structure of the game.17

4.2. Effective Game

As a two-stage coalition formation game is a two-stage game with, in both stages, simultaneous and independent actions, it is not so clear how to “solve” such a game ([31]); an extra complication here is that the player set of the second stage is, in general, not equal to that of the first stage.

The existing literature handles the solving issue by “looking for subgame perfect equilibria”: first one solves the second stage by determining for each possible coalitional game18 its Nash equilibria, and then the first one. In doing so it is assumed that each possible coalitional game has a unique Nash equilibrium. Below we shall make this precise.

Definition 3. 

A two-stage coalition formation game $(N;R;\mathrm{\Gamma })$ is regular if for each possible coalition structure the coalitional game ${\mathrm{\Gamma }}_{\mathcal{C}}$ has a unique Nash equilibrium. In this case this Nash equilibrium is denoted by

$${\mathbf{e}}^{\left(\mathcal{C}\right)}.\diamond$$

Definition 4. 

Let $(N;R;\mathrm{\Gamma })$ be a regular two-stage coalition formation game. Its effective game is the game in strategic form $G=(N;{\left(M_i\right)}_{i\in N};{\left(g_i\right)}_{i\in N})$ defined by

$$g_i\left(\mathbf{m}\right):=f_i\left(\widehat{\mathbf{x}}\left(\mathbf{m}\right)\right).$$

(6)

with $\widehat{\mathbf{x}}:\mathbf{M}\to \mathbf{X}$ given by19

$$\widehat{\mathbf{x}}\left(\mathbf{m}\right)=({\widehat{x}}_1\left(\mathbf{m}\right),\dots ,{\widehat{x}}_n\left(\mathbf{m}\right)):=J_{R\left(\mathbf{m}\right)}\left({\mathbf{e}}^{\left(R\right(\mathbf{m}\left)\right)}\right).$$

We refer to the function $g_i$ as effective payoff of player i and to ${\widehat{x}}_i\left(\mathbf{m}\right)$ as effective physical action (of player i associated with $\mathbf{m})$.20 ⋄

So we have the formula

$$g_i\left(\mathbf{m}\right)=f_i(J_{R\left(\mathbf{m}\right)}\left({\mathbf{e}}^{\left(R\right(\mathbf{m}\left)\right)}\right).$$

(7)

Note that the two-stage coalition formation game is almost completely non-cooperative; the only place where cooperative aspects enter is in the coordination of the choices by the coalition members.

4.3. Solving the Two-Stage Game

Consider a regular two-stage coalition formation game $(N;R;\mathrm{\Gamma })$ with effective game G. The game G is a game in strategic form with $\mathbf{M}$ as set of action profiles. In the literature the two-stage game is solved by determining the Nash equilibria set

$$E\left(G\right)$$

of G. For every $\mathbf{m}\in E\left(G\right)$ we refer to $R\left(\mathbf{m}\right)$ as a equilibrium coalition structure.

In the context of a cartel game (with the cartel membership rule $R_c$), one also is interested in semi-strict Nash equilibria (see Section 9). Denoting the set of semi-strict Nash equilibria by

$$E_{ss}\left(G\right),$$

we refer for every $\mathbf{m}\in E_{ss}\left(G\right)$ to $R_c\left(\mathbf{m}\right)$ as a semi-strict equilibrium coalition structure.

5. Cournot-Like Games

5.1. Notion

When dealing with two-stage coalition formation games, Cournot games and public good games are popular physical games. As such games have a common structure and admit a unified analysis, in [32] the following class of games was introduced:

Definition 5. 

A Cournot-like game is a game in strategic form

$$(N;{\left(X_i\right)}_{i\in N};{\left(f_i\right)}_{i\in N})$$

where every $X_i$ is a subset of21 ${\mathbb{R}}_{+}$ with $0\in X_i$ and

$$f_i\left(\mathbf{x}\right)=p_i\left(x_i\right)-x_i^{{\beta }_i}{q}_i\left(\sum _{l\in N}{\gamma }_l{x}_l\right)$$

where, with (the Minkowski sum) $Y:={\sum }_{l\in N}{\gamma }_l{X}_l$,

• $p_i:X_i\to \mathbb{R}$ and $q_i:Y\to \mathbb{R}$;
• ${\beta }_i\in \{0,1\}$ and ${\gamma }_l>0$. ⋄

The abstract class of Cournot-like games contains various heterogeneous Cournot oligopoly games: take every ${\beta }_i=1$. It contains all22 homogeneous Cournot oligopoly games: take, in addition, all $q_i$ equal and each ${\gamma }_l=1$. It also contains various public good games: take every ${\beta }_i=0$.

5.2. Uniqueness of Coalitional Equilbria

Let us consider the regularity issue for two-stage coalition formation games with a Cournot-like game as physical game. This issue mainly concerns a Nash equilibrium semi-uniqueness problem23 as conditions for existence do not seem to be problematic in the relevant literature;24 in particular equilibrium existence, results, à la Nikaido-Isoda, are useful (see [33]). Already in the case of one-dimensional action sets, for example in the classical Cournot oligopoly, the equilibrium semi-uniqueness problem poses more serious problems than the existence problem (see, for example, [34,35]). For coalitional games this problem is even more complicated, as in such such games action sets may be higher dimensional.

In [36], the above problem was approached by developing an equilibrium semi-uniqueness result for games in strategic form with higher dimensional action sets. The next theorem follows from the results in [36]. This theorem deals with Cournot-like games as physical games.

Theorem 1. 

1. 

Consider a homogeneous Cournot oligopoly game, with $f_i\left(\mathbf{x}\right)=a_i\left(x_i\right)-x_{i}b\left({\sum }_{l\in N}{x}_l\right)$, with compact action sets, differentiable strictly concave $a_i$ and with differentiable increasing convex b. Then for every coalition structure $\mathcal{C}$ the game has a unique $\mathcal{C}$-equilibrium.

2. 

Consider a public good game with $f_i\left(\mathbf{x}\right)=a_i\left(x_i\right)-b_i\left({\sum }_{l\in N}{x}_l\right)$, with compact action sets, differentiable strictly concave $a_i$ and with differentiable increasing convex $b_i$. Then for every coalition structure $\mathcal{C}$ the game has a unique $\mathcal{C}$-equilibrium. ⋄

Proof. 

By Corollary 3 in [36]. □

Corollary 1. 

A two-stage coalition formation game $(N;R;\mathrm{\Gamma })$ with as physical game Γ a Cournot-like game as in Theorem 1 is regular. ⋄

Example 2. 

A simple example of a Cournot-like game that does not have the property that for every coalition structure $\mathcal{C}$ there is a unique $\mathcal{C}$-equilibrium, is the following: each player has action set ${\mathbb{R}}_{+}$ and the payoff functions are

$$f_i\left(\mathbf{x}\right)={\left(\sum _{l\in N}{x}_l\right)}^{1/2}-x_i.$$

In order to see this, consider the coalitional game for the coalition structure $\left\{N\right\}$. This game has one player: the meta-player N. The payoff function of this game is the function $\mathbf{k}\mapsto n{\left({\sum }_{l\in N}{k}_l\right)}^{1/2}-{\sum }_{l\in N}{k}_l.$ The set of Nash equilibria of this game consists of the actions $\mathbf{k}$ with ${\sum }_{l=1}^n{k}_l=n^2/4$. Thus, there are infinitely many $\left\{N\right\}$-equilibria. ⋄

6. Coalitional Equilibria of Symmetric Games

The symmetry notion (1) for a game in strategic form $\mathrm{\Gamma }$ presupposes that each player has the same action set. This implies for a coalitional game ${\mathrm{\Gamma }}_{\mathcal{C}}$ of $\mathrm{\Gamma }$ that “symmetric” may not be well-defined, even if $\mathrm{\Gamma }$ is symmetric, since the coalition structure may comprise meta players of unequal size. Proposition 2 below shows that for a symmetric $\mathrm{\Gamma }$ the Nash equilibria of the coalitional games of $\mathrm{\Gamma }$ nevertheless have some symmetry properties.

In the rest of this section we consider a game in strategic form $\mathrm{\Gamma }=(N;{\left(X_i\right)}_{i\in N};{\left(f_i\right)}_{i\in N})$.

Given a coalition structure $\mathcal{C}$ and a permutation $\pi$ of N, let ${\mathcal{C}}^{\prime }$ be the coalition structure ${\mathcal{C}}^{\prime }=\left\{{\pi }^{<-1>}\left(C\right)\right|C\in \mathcal{C}\}$ and ${\mathcal{U}}_{\pi }:{\prod }_{C\in \mathcal{C}}{K}_C\to {\prod }_{C^{\prime }\in {\mathcal{C}}^{\prime }}{K}_{C^{\prime }}$ be the mapping defined by

$${\mathcal{U}}_{\pi }:=J_{{\mathcal{C}}^{\prime }}^{<-1>}\circ T_{{\pi }^{<-1>}}\circ J_{\mathcal{C}}.$$

${\mathcal{U}}_{\pi }$ is, being a composition of bijections, a bijection. The reason to introduce ${\mathcal{U}}_{\pi }$ is that with it we have the result in Lemma 1(2). Denoting payoff functions of ${\mathrm{\Gamma }}_{\mathcal{C}}$ with $P_C$ and those of ${\mathrm{\Gamma }}_{{\mathcal{C}}^{\prime }}$ with $P_{C^{\prime }}^{\prime }$, we have for this situation the following lemma.

Lemma 1. 

Suppose Γ is symmetric.

1. 

For every $C\in \mathcal{C}$ the identity $P_C=P_{{\pi }^{<-1>}\left(C\right)}^{\prime }\circ {\mathcal{U}}_{\pi }$ holds.

2. 

${\mathcal{U}}_{\pi }\left(E\left({\mathrm{\Gamma }}_{\mathcal{C}}\right)\right)=E\left({\mathrm{\Gamma }}_{{\mathcal{C}}^{\prime }}\right)$. ⋄

Proof. 

1. With (1) we obtain $P_C={\sum }_{i\in C}{f}_i\circ J_{\mathcal{C}}={\sum }_{i\in {\pi }^{<-1>}\left(C\right)}{f}_{\pi \left(i\right)}\circ J_{\mathcal{C}}={\sum }_{i\in {\pi }^{<-1>}\left(C\right)}{f}_i\circ T_{{\pi }^{<-1>}}\circ J_{\mathcal{C}}={\sum }_{i\in {\pi }^{<-1>}\left(C\right)}{f}_i\circ J_{{\mathcal{C}}^{\prime }}\circ {\mathcal{U}}_{\pi }=P_{{\pi }^{<-1>}\left(C\right)}^{\prime }\circ {\mathcal{U}}_{\pi }$.

2. First we prove that ${\mathcal{U}}_{\pi }\left(E\left({\mathrm{\Gamma }}_{\mathcal{C}}\right)\right)\subseteq E\left({\mathrm{\Gamma }}_{{\mathcal{C}}^{\prime }}\right)$. So suppose $\mathbf{k}\in E\left({\mathrm{\Gamma }}_{\mathcal{C}}\right)$. Let ${\mathbf{k}}^{\prime }={\mathcal{U}}_{\pi }\left(\mathbf{k}\right)$. We are going to prove that ${\mathbf{k}}^{\prime }\in E\left({\mathrm{\Gamma }}_{{\mathcal{C}}^{\prime }}\right)$. In order to do so, we fix in ${\mathrm{\Gamma }}_{{\mathcal{C}}^{\prime }}$, a meta player $D^{\prime }$ and an action profile ${\mathbf{k}}^{″}$ with $k_{C^{\prime }}^{\prime }=k_{C^{\prime }}^{″}(C^{\prime }\in {\mathcal{C}}^{\prime } with C^{\prime }\ne D^{\prime })$ of this game and show that

$$P_{D^{\prime }}^{\prime }\left({\mathbf{k}}^{″}\right)\le P_{D^{\prime }}^{\prime }\left({\mathbf{k}}^{\prime }\right).$$

Well, let $A\in \mathcal{C}$ be such that $D^{\prime }={\pi }^{<-1>}\left(A\right)$ and let $\mathbf{d}={\mathcal{U}}_{\pi }^{<-1>}\left({\mathbf{k}}^{″}\right)$; we have

$$J_{\mathcal{C}}\left(\mathbf{d}\right)=(T_{\pi }\circ T_{{\pi }^{<-1>}}\circ J_{\mathcal{C}})\left(\mathbf{d}\right)=(T_{\pi }\circ J_{{\mathcal{C}}^{\prime }})\left({\mathbf{k}}^{″}\right).$$

We first prove

$$d_C=k_C(C\in \mathcal{C} \text{with} C\ne A).$$

In order to do so, we fix $C\in \mathcal{C}$ with $C\ne A$ and $l\in C$.

As ${\pi }^{<-1>}\left(C\right)\ne D^{\prime }$, we have $k_{{\pi }^{<-1>}\left(C\right);{\pi }^{<-1>}\left(l\right)}^{\prime }=k_{{\pi }^{<-1>}\left(C\right);{\pi }^{<-1>}\left(l\right)}^{″}$. With this

$$d_{C;l}={\left(J_{\mathcal{C}}\left(\mathbf{d}\right)\right)}_l={\left((T_{\pi }\circ J_{{\mathcal{C}}^{\prime }})\left({\mathbf{k}}^{″}\right)\right)}_l={\left(J_{{\mathcal{C}}^{\prime }}\left({\mathbf{k}}^{″}\right)\right)}_{{\pi }^{<-1>}\left(l\right)}=k_{{\pi }^{<-1>}\left(C\right);{\pi }^{<-1>}\left(l\right)}^{″}$$

$$=k_{{\pi }^{<-1>}\left(C\right);{\pi }^{<-1>}\left(l\right)}^{\prime }={\left(J_{{\mathcal{C}}^{\prime }}\left({\mathbf{k}}^{\prime }\right)\right)}_{{\pi }^{<-1>}\left(l\right)}$$

$$={\left((T_{{\pi }^{<-1>}}\circ J_{\mathcal{C}})\left(\mathbf{k}\right)\right)}_{{\pi }^{<-1>}\left(l\right)}={\left(J_{\mathcal{C}}\left(\mathbf{k}\right)\right)}_l=k_{C;l}.$$

As $\mathbf{k}\in E\left({\mathrm{\Gamma }}_{\mathcal{C}}\right)$, we have $P_A\left(\mathbf{d}\right)\le P_A\left(\mathbf{k}\right)$. With this, as $\mathrm{\Gamma }$ is symmetric, we obtain with part 1, as desired,

$$P_{D^{\prime }}^{\prime }\left({\mathbf{k}}^{″}\right)=P_{{\pi }^{<-1>\left(A\right)}}^{\prime }\left({\mathcal{U}}_{\pi }\left(\mathbf{d}\right)\right)=P_A\left(\mathbf{d}\right)\le P_A\left(\mathbf{k}\right)=P_{{\pi }^{<-1>\left(A\right)}}^{\prime }\left({\mathcal{U}}_{\pi }\left(\mathbf{k}\right)\right)=P_{D^{\prime }}^{\prime }\left({\mathbf{k}}^{\prime }\right).$$

In the same way as above we can show that ${\mathcal{U}}_{\pi }^{<-1>}\left(E\left({\mathrm{\Gamma }}_{{\mathcal{C}}^{\prime }}\right)\right)\subseteq E\left({\mathrm{\Gamma }}_{\mathcal{C}}\right)$. This implies $E\left({\mathrm{\Gamma }}_{{\mathcal{C}}^{\prime }}\right)=({\mathcal{U}}_{\pi }\circ {\mathcal{U}}_{\pi }^{<-1>})\left(E\left({\mathrm{\Gamma }}_{{\mathcal{C}}^{\prime }}\right)\right)\subseteq {\mathcal{U}}_{\pi }\left(E\left({\mathrm{\Gamma }}_{\mathcal{C}}\right)\right)$. □

Proposition 2. 

Suppose Γ is symmetric. Fix a coalition structure $\mathcal{C}$. Suppose the game ${\mathrm{\Gamma }}_{\mathcal{C}}$ has a unique Nash equilibrium $\mathbf{k}={\left(k_C\right)}_{C\in \mathcal{C}}$.

1. 

For every $C\in \mathcal{C}$, the action $k_C$ of meta player C is constant; i.e., $k_{C;i}=k_{C;j}(i,j\in C)$.

2. 

For every $C,C^{\prime }\in \mathcal{C}$ with $\#C=\#C^{\prime }$, it holds that $k_C$ and $k_{C^{\prime }}$ are the same constant.

3. 

For every $C,C^{\prime }\in \mathcal{C}$ with $\#C=\#C^{\prime }$, it holds that $f_i\left(J_{\mathcal{C}}\left(\mathbf{k}\right)\right)=f_j\left(J_{\mathcal{C}}\left(\mathbf{k}\right)\right)(i\in C,j\in C^{\prime })$.

Further let ${\mathcal{C}}^{\prime }$ be a with $\mathcal{C}$ congruent coalition structure.

4. 

${\mathrm{\Gamma }}_{{\mathcal{C}}^{\prime }}$ has a unique Nash equilibrium ${\mathbf{k}}^{\prime }$.

5. 

For every $C\in \mathcal{C}$ and $C^{\prime }\in {\mathcal{C}}^{\prime }$ with $\#C=\#C^{\prime }$, the actions $k_C$ and $k_{C^{\prime }}^{\prime }$ are the same constant.25

6. 

For every $C\in \mathcal{C}$ and $C^{\prime }\in {\mathcal{C}}^{\prime }$ with $\#C=\#C^{\prime }$, it holds that $f_i\left(J_{\mathcal{C}}\left(\mathbf{k}\right)\right)=f_j\left(J_{{\mathcal{C}}^{\prime }}\left({\mathbf{k}}^{\prime }\right)\right)(i\in C,j\in C^{\prime })$. ⋄

Proof. 

1. By contradiction, suppose $C\in \mathcal{C}$ is such that ${\mathbf{k}}_C$ is not constant. Fix $l,m\in C$ such that $k_{C;l}\ne k_{C;m}$. Let $\pi$ be a permutation of N with $\pi \left(B\right)=B(B\in \mathcal{C})$ such that $\pi \left(l\right)=m$. Now ${\mathcal{C}}^{\prime }$ in Lemma 1 equals $\mathcal{C}$. Let ${\mathbf{k}}^{\prime }={\mathcal{U}}_{\pi }\left(\mathbf{k}\right)$. As $k_{C;l}^{\prime }={\left(J_{\mathcal{C}}\left({\mathbf{k}}^{\prime }\right)\right)}_l=J_{\mathcal{C}}\left({\mathcal{U}}_{\pi }\left(\mathbf{k}\right)\right)={\left((T_{{\pi }^{<-1>}}\circ J_{\mathcal{C}})\left(\mathbf{k}\right)\right)}_l={\left(J_{\mathcal{C}}\left(\mathbf{k}\right)\right)}_{\pi \left(l\right)}=k_{C,\pi \left(l\right)}=k_{C,m}\ne k_{C,l}$, we have ${\mathbf{k}}^{\prime }\ne \mathbf{k}$. By Lemma 1(2), also ${\mathbf{k}}^{\prime }\in E\left({\mathrm{\Gamma }}_{\mathcal{C}}\right)$, a contradiction with $\#E\left({\mathrm{\Gamma }}_{\mathcal{C}}\right)=1$.

2. Fix a permutation $\pi$ of N such that $\pi \left(C^{\prime }\right)=C$. Then $C^{\prime }={\pi }^{<-1>}\left(C\right)$. Fix $j\in C^{\prime }$. By part 1, the proof is complete if we show that $k_{C^{\prime };j}^{\prime }=k_{C;\pi \left(j\right)}$. Well, $k_{C^{\prime };j}^{\prime }={\left(J_{{\mathcal{C}}^{\prime }}\left({\mathbf{k}}^{\prime }\right)\right)}_j={\left((J_{{\mathcal{C}}^{\prime }}\circ {\mathcal{U}}_{\pi })\left(\mathbf{k}\right)\right)}_j={\left((T_{{\pi }^{<-1>}}\circ J_{\mathcal{C}})\left(\mathbf{k}\right)\right)}_j={\left(J_{\mathcal{C}}\left(\mathbf{k}\right)\right)}_{\pi \left(j\right)}=k_{C;\pi \left(j\right)}$.

3. Let $\pi$ be a permutation of N such that $\pi \left(i\right)=j$, $\pi \left(C\right)=C^{\prime }$, $\pi \left(C^{\prime }\right)=C$ and $\pi =\mathrm{Id}$ on $N\backslash (C\cup C^{\prime })$. With ${\mathcal{C}}^{\prime }$ as in Lemma 1, again $\mathcal{C}={\mathcal{C}}^{\prime }$. Lemma 1(2) implies ${\mathcal{U}}_{\pi }\left(\mathbf{k}\right)=\mathbf{k}$ and therefore $(T_{{\pi }^{<-1>}}\circ J_{\mathcal{C}})\left(\mathbf{k}\right)=J_{\mathcal{C}}\left(\mathbf{k}\right)$. With this, we obtain, $f_j\left(J_{\mathcal{C}}\left(\mathbf{k}\right)\right)=f_{\pi \left(i\right)}\left(J_{\mathcal{C}}\left(\mathbf{k}\right)\right)=f_i\left((T_{{\pi }^{<-1>}}\circ J_{\mathcal{C}})\left(\mathbf{k}\right)\right)=f_i\left(J_{\mathcal{C}}\left(\mathbf{k}\right)\right)$.

4. Fix a permutation $\pi$ of N such that ${\mathcal{C}}^{\prime }=\left\{{\pi }^{<-1>}\left(A\right)\right|A\in \mathcal{C}\}$. By Lemma 1(2), ${\mathcal{U}}_{\pi }\left(\mathbf{k}\right)$ is the unique Nash equilibrium of ${\mathrm{\Gamma }}_{{\mathcal{C}}^{\prime }}$.

5. As $\mathcal{C}\sim {\mathcal{C}}^{\prime }$ and $\#C=\#C^{\prime }$, there exists a permutation $\sigma$ of N with ${\mathcal{C}}^{\prime }=\left\{{\sigma }^{<-1>}\left(A\right)\right|A\in \mathcal{C}\}$ and $C^{\prime }={\sigma }^{-1}\left(C\right)$. Fix such an $\sigma$. By the proof of part 4, ${\mathbf{k}}^{\prime }={\mathcal{U}}_{\sigma }\left(\mathbf{k}\right)$. Take an arbitrary $j\in C^{\prime }$; note that $\sigma 9j)\in C$. We obtain, as desired $k_{C^{\prime };j}^{\prime }={\left(J_{{\mathcal{C}}^{\prime }}\left({\mathbf{k}}^{\prime }\right)\right)}_j={\left((J_{{\mathcal{C}}^{\prime }}\circ {\mathcal{U}}_{\sigma })\left(\mathbf{k}\right)\right)}_j={\left((T_{{\sigma }^{<-1>}}\circ J_{\mathcal{C}})\left(\mathbf{k}\right)\right)}_j={\left(J_{\mathcal{C}}\left(\mathbf{k}\right)\right)}_{\sigma \left(j\right)}=k_{C;\sigma \left(j\right)}$.

6. Choose $\sigma$ as in the proof of part 5 such that $\sigma \left(j\right)=i$. Now $f_i\left(J_{\mathcal{C}}\left(\mathbf{k}\right)\right)=f_{\sigma \left(j\right)}\left(J_{\mathcal{C}}\left(\mathbf{k}\right)\right)=f_j\left((T_{{\sigma }^{<-1>}}\circ J_{\mathcal{C}})\left(\mathbf{k}\right)\right)=f_j(J_{{\mathcal{C}}^{\prime }}\circ {\mathcal{U}}_{\sigma })\left(\mathbf{k}\right))=f_j\left(J_{{\mathcal{C}}^{\prime }}\left({\mathbf{k}}^{\prime }\right)\right)$. □

From part 2 of this proposition we see that the actions of the individual players in a unique coalitional equilibrium of a symmetric game only depend on the size of the coalition and not on their composition.

7. Case of a Symmetric Physical Game

Theorem 2. 

Consider a regular two-stage coalition formation game $(N;R;\mathrm{\Gamma })$ with a symmetric physical game Γ and a symmetric membership rule R. Let G be the effective game.

1. 

G is symmetric.

Further, for all $\mathbf{m},{\mathbf{m}}^{\prime }\in M^n$ and $i,j\in N$, writing $\mathcal{C}=R\left(\mathbf{m}\right)$ and ${\mathcal{C}}^{\prime }=R\left({\mathbf{m}}^{\prime }\right)$, if $\mathcal{C}$ and ${\mathcal{C}}^{\prime }$ are congruent, then

2. 

$\#{\mathcal{C}}_{\left[i\right]}=\#{\mathcal{C}}_{\left[j\right]}^{\prime }\Rightarrow [{\widehat{x}}_i\left(\mathbf{m}\right)={\widehat{x}}_j\left({\mathbf{m}}^{\prime }\right)\wedge g_i\left(\mathbf{m}\right)=g_j\left({\mathbf{m}}^{\prime }\right)]$. ⋄

Proof. 

1. In order to prove that G is symmetric, we fix a permutation $\pi$ of N, $j\in N$ and $\mathbf{m}\in \mathbf{M}$. By (1), we have to prove that $g_{\pi \left(j\right)}\left(\mathbf{m}\right)=g_j\left(T_{{\pi }^{<-1>}}\left(\mathbf{m}\right)\right))$. Writing $\mathcal{C}=R\left(\mathbf{m}\right)$ and ${\mathcal{C}}^{\prime }=R\left(T_{{\pi }^{<-1>}}\left(\mathbf{m}\right)\right)$, Proposition 1 guarantees that $\mathcal{C}$ and ${\mathcal{C}}^{\prime }$ are congruent; note that, by (5), ${\mathcal{C}}^{\prime }=\left\{{\pi }^{<-1>}\left(C\right)\right|C\in \mathcal{C}\}$. By (7) we have to prove that $f_{\pi \left(j\right)}\left(J_{\mathcal{C}}\left({\mathbf{e}}^{\left(\mathcal{C}\right)}\right)\right)=f_j\left(J_{{\mathcal{C}}^{\prime }}\left({\mathbf{e}}^{\left({\mathcal{C}}^{\prime }\right)}\right)\right).$ So, with $\mathbf{k}={\mathbf{e}}^{\left(\mathcal{C}\right)}$, ${\mathbf{k}}^{\prime }={\mathbf{e}}^{\left({\mathcal{C}}^{\prime }\right)}$ and $i=\pi \left(j\right)$, we have to prove that $f_i\left(J_{\mathcal{C}}\left(\mathbf{k}\right)\right)=f_j\left(J_{{\mathcal{C}}^{\prime }}\left({\mathbf{k}}^{\prime }\right)\right)$. Fix $C\in \mathcal{C}$ with $i\in \mathcal{C}$. Now $j={\pi }^{<-1>}\left(i\right)\in {\pi }^{<-1>}\left(C\right)\in {\mathcal{C}}^{\prime }$. Applying Proposition 2(6) completes the proof.

2. Suppose $\#{\mathcal{C}}_{\left[i\right]}=\#{\mathcal{C}}_{\left[j\right]}^{\prime }$. Write $\mathbf{k}={\mathbf{e}}^{\left(R\right(\mathbf{m}\left)\right)}$ and ${\mathbf{k}}^{\prime }={\mathbf{e}}^{\left(R\left({\mathbf{m}}^{\prime }\right)\right)}$. Then $\widehat{\mathbf{x}}\left(\mathbf{m}\right)=J_{\mathcal{C}}\left(\mathbf{k}\right)$ and $\widehat{\mathbf{x}}\left({\mathbf{m}}^{\prime }\right)=J_{{\mathcal{C}}^{\prime }}\left({\mathbf{k}}^{\prime }\right)$. Therefore ${\widehat{x}}_i\left(\mathbf{m}\right)=k_{{\mathcal{C}}_{\left[i\right]};i}$ and ${\widehat{x}}_j\left({\mathbf{m}}^{\prime }\right)=k_{{\mathcal{C}}_{\left[j\right]}^{\prime };j}^{\prime }$. Proposition 2(5) guarantees ${\widehat{x}}_i\left(\mathbf{m}\right)={\widehat{x}}_j\left({\mathbf{m}}^{\prime }\right)$.

Further, we have $g_i\left(\mathbf{m}\right)=f_i\left(J_{\mathcal{C}}\left(\mathbf{k}\right)\right)$ and $g_i\left({\mathbf{m}}^{\prime }\right)=f_i\left(J_{{\mathcal{C}}^{\prime }}\left({\mathbf{k}}^{\prime }\right)\right)$. As $\#{\mathcal{C}}_{\left[i\right]}=\#{\mathcal{C}}_{\left[j\right]}^{\prime }$, Proposition 2(6) guarantees $g_i\left(\mathbf{m}\right)=g_j\left({\mathbf{m}}^{\prime }\right)$. □

Some readers may find Theorem 2 intuitively clear. Yes it is. However, the literature uses reasoning based on this theorem, but does not provide a proof. Concerning this, it is good to note that there is almost no literature about general properties of symmetric games in strategic form and systematic studies are lacking; an exception is the recent [37]. Most text books on game theory even do not give a formal definition of a symmetric game. Additionally, there are various misunderstandings about the definition of such a game.26

8. Binary Action Games

In the next section we deal with a special type of two-stage coalition formation game: the cartel game. As the effective game of a cartel game is a binary action game, we first consider below, binary action games. The content of this section is based on [19,38]. For various results also, a proof will be given.

8.1. Internal and External Stability

In the rest of this section we consider, if not stated otherwise, a binary action game; i.e., a game in strategic form with player set $N=\{1,2,\dots ,n\}$ where each player has $M=\{0,1\}$ as action set. We denote the game by G and the payoff function of player i by $g_i$, so $g_i:M^n\to \mathbb{R}$.

Again as in Example 1, for $\mathbf{m}\in M^n$, let

$$\widehat{S}\left(\mathbf{m}\right)=\{i\in N|m_i=1\},{\widehat{S}}_{\star }\left(\mathbf{m}\right)=\{i\in N|m_i=0\}.$$

We refer to the players in $\widehat{S}\left(\mathbf{m}\right)$ as cooperators and to the players in ${\widehat{S}}_{\star }\left(\mathbf{m}\right)$ as non-cooperators.

For $i\in N$ define $T_i:M^n\to M^n$ as follows: $T_i\left(\mathbf{m}\right)$ is the action profile obtained from $\mathbf{m}=(m_1,\dots ,m_n)$ when player i changes his action (i.e., replaces $m_i$ by $1-m_i$). Let $g_i^{\prime }\left(\mathbf{m}\right)$ be the marginal payoff of i at $\mathbf{m}$; i.e.,

$$g_i^{\prime }\left(\mathbf{m}\right)=g_i\left(T_i\left(\mathbf{m}\right)\right)-g_i\left(\mathbf{m}\right).$$

Note that $g_i^{\prime }\left(T_i\left(\mathbf{m}\right)\right)=-g_i^{\prime }\left(\mathbf{m}\right)$ and that $\mathbf{m}$ is a Nash equilibrium if and only if $g_i^{\prime }\left(\mathbf{m}\right)\le 0$ for all $i\in N$.

An interesting notion for binary action games is that of “semi-strict Nash equilibrium”:

Definition 6. 

An action profile $\mathbf{m}$ is

1. 

Weakly internally stable if $g_i^{\prime }\left(\mathbf{m}\right)\le 0$ for each cooperator i.

2. 

Strictly externally stable, $g_i^{\prime }\left(\mathbf{m}\right)<0$ for each non-cooperator i.

3. 

A semi-strict Nash equilibrium if $\mathbf{m}$ is weakly internally stable and strictly externally stable. ⋄

These notions of internal and external stability were essentially introduced in [3] and differ entirely from those in other types of games.

We denote the set of semi-strict Nash equilibria of G by

$$E_{ss}\left(G\right)$$

and the set of weakly internally stable action profiles by

$$\mathcal{I}\left(\widehat{S}\right).$$

Note that $\mathcal{I}\left(\widehat{S}\right)\ne \varnothing$ as $\mathbf{0}\in \mathcal{I}\left(\widehat{S}\right)$. Let

$$U_{\widehat{S}}\left(\mathbf{m}\right):=\{i\in {\widehat{S}}_{\star }\left(\mathbf{m}\right)|g_i^{\prime }\left(\mathbf{m}\right)\ge 0\}.$$

Thus, $U_{\widehat{S}}\left(\mathbf{m}\right)$ is the set of players that violate the strict inequality for strict external stability; $\mathbf{m}$ is strictly externally stable if and only if $U_{\widehat{S}}\left(\mathbf{m}\right)=\varnothing$.

The next result is at the base for various results about binary action games.

Proposition 3. 

Consider an action profile $\mathbf{m}$.

1. 

$\mathbf{m}\in \mathcal{I}\left(\widehat{S}\right)\Rightarrow U_{\widehat{S}}\left(T_i\left(\mathbf{m}\right)\right)\ne \varnothing (i\in \widehat{S}\left(\mathbf{m}\right))$.

2. 

$U_{\widehat{S}}\left(\mathbf{m}\right)=\varnothing \Rightarrow T_i\left(\mathbf{m}\right)\notin \mathcal{I}\left(\widehat{S}\right)(i\in {\widehat{S}}_{\star }\left(\mathbf{m}\right))$.

3. 

If $\mathbf{m}$ is a semi-strict Nash equilibrium, then for every $i\in N$ it holds that $T_i\left(\mathbf{m}\right)$ is not a semi-strict Nash equilibrium. ⋄

Proof. 

See Proposition 3 in [38] (see also Lemma 1 in [19]). □

Proposition 3(1) states that if an action profile $\mathbf{m}$ is weakly internally stable, then for every cooperator i the action profile $T_i\left(\mathbf{m}\right)$ is strictly externally unstable. Its part 2 indicates that if an action profile $\mathbf{m}$ is strictly externally stable, then for every non-cooperator i the action profile $T_i\left(\mathbf{m}\right)$ is weakly internally unstable. Part 3 shows a typical property of semi-strict Nash equilibria: if $\mathbf{m}$ is such an equilibrium, then if one player changes his action, the resulting action profile is no longer a semi-strict Nash equilibrium.

8.2. Deviation Property $D_1$

In [38] three so-called deviation properties (i.e., $D_1,D_2$ and $D_3$) for binary action games are defined. In the present article we only consider the following one:

Definition 7. 

A binary action game has the deviation property $D_1$ if $g_j^{\prime }\left(\mathbf{m}\right)\le 0\iff g_i^{\prime }\left(\mathbf{m}\right)\le 0$ for each action profile $\mathbf{m}$ and cooperators $i,j$. ⋄

Terminology: a finite sequence ${\mathbf{m}}^{\left(0\right)},{\mathbf{m}}^{\left(1\right)},\dots ,{\mathbf{m}}^{\left(k\right)}$ of action profiles is an enlargement sequence if $\widehat{S}\left({\mathbf{m}}^{\left(0\right)}\right)\subset \widehat{S}\left({\mathbf{m}}^{\left(1\right)}\right)\subset \cdots \subset \widehat{S}\left({\mathbf{m}}^{\left(k\right)}\right)$. An enlargement sequence ${\mathbf{m}}^{\left(0\right)},{\mathbf{m}}^{\left(1\right)},\cdots ,{\mathbf{m}}^{\left(k\right)}$ is called elementary if $\#\widehat{S}\left({\mathbf{m}}^{(l+1)}\right)=\#\widehat{S}\left({\mathbf{m}}^{\left(l\right)}\right)+1$ for all l.

Theorem 3. 

Consider a binary action game with the deviation property $D_1$.

1. 

Let $\mathbf{m}\in M^n$. Then $i\in U_{\widehat{S}}\left(\mathbf{m}\right)\Rightarrow T_i\left(\mathbf{m}\right)\in \mathcal{I}\left(\widehat{S}\right)$.

2. 

For each weakly internally stable action profile ${\mathbf{m}}^{\left(0\right)}$ there exists an elementary enlargement sequence ${\mathbf{m}}^{\left(0\right)},{\mathbf{m}}^{\left(1\right)},\dots ,{\mathbf{m}}^{\left(k\right)}$ of weakly internally stable action profiles where ${\mathbf{m}}^{\left(k\right)}$ is a semi-strict Nash equilibrium.

3. 

The game has a semi-strict Nash equilibrium. ⋄

Proof. 

See Proposition 5 and Theorem 1 in [38]. □

Theorem 3(2) implies that each binary action game with the deviation property $D_1$ has a semi-strict Nash equilibrium: indeed, take ${\mathbf{m}}^{\left(0\right)}=\mathbf{0}$.

Definition 8. 

A binary action game:

1. 

Is super-additive if for each action profile $\mathbf{m}$ and $i\in {\widehat{S}}_{\star }\left(\mathbf{m}\right)$

$$\sum _{l\in \widehat{S}\left(T_i\left(\mathbf{m}\right)\right)}{g}_l\left(T_i\left(\mathbf{m}\right)\right)\ge \sum _{l\in \widehat{S}\left(\mathbf{m}\right)}{g}_l\left(\mathbf{m}\right)+g_i\left(\mathbf{m}\right);$$

2. 

Has weak negative spillovers if for each action profile $\mathbf{m}$ and $i,k\in {\widehat{S}}_{\star }\left(\mathbf{m}\right)$ with $i\ne k$

$$g_i\left(T_k\left(\mathbf{m}\right)\right)\le g_i\left(\mathbf{m}\right).\diamond$$

Super-additivity thus means that: given an action profile, the payoff of a meta player consisting of the cooperators together with a non-cooperator is at least the sum of the payoffs of the cooperators and this non-cooperator. Weak negative spillovers, in contrast, indicate that the payoff of a non-cooperator decreases or stays the same if another non-cooperator becomes a cooperator.

Proposition 4. 

Suppose G has the deviation property $D_1$, is super-additive and has weak negative spillovers.

1. 

For all $\mathbf{m}\in \mathcal{I}\left(\widehat{S}\right)$ and $j\in S_{\star }\left(\mathbf{m}\right)$, it holds that $T_j\left(\mathbf{m}\right)\in \mathcal{I}\left(\widehat{S}\right)$.

2. 

Each action profile is weakly internally stable.

3. 

$E_{ss}\left(G\right)=\left\{(1,1,\dots ,1)\right\}$. ⋄

Proof. 

1. Let $\mathbf{p}=T_j\left(\mathbf{m}\right)$. Note that $\mathbf{m}=T_j\left(\mathbf{p}\right)$ and $\widehat{S}\left(\mathbf{p}\right)=\widehat{S}\left(\mathbf{m}\right)\cup \left\{j\right\}$. We obtain

$$\sum _{l\in \widehat{S}\left(\mathbf{p}\right)}{g}_l\left(T_l\left(\mathbf{p}\right)\right)=g_j\left(\mathbf{m}\right)+\sum _{l\in \widehat{S}\left(\mathbf{m}\right)}{g}_l\left(T_j{T}_l\left(\mathbf{m}\right)\right)$$

$$\le g_j\left(\mathbf{m}\right)+\sum _{l\in \widehat{S}\left(\mathbf{m}\right)}{g}_l\left(T_l\left(\mathbf{m}\right)\right)\le g_j\left(\mathbf{m}\right)+\sum _{l\in \widehat{S}\left(\mathbf{m}\right)}{g}_l\left(\mathbf{m}\right)$$

$$\le \sum _{l\in \widehat{S}\left(T_j\left(\mathbf{m}\right)\right)}{g}_l\left(T_j\left(\mathbf{m}\right)\right)=\sum _{l\in \widehat{S}\left(\mathbf{p}\right)}{g}_l\left(\mathbf{p}\right).$$

Here the first inequality holds by weak negative spillovers (noting that $j,l\in {\widehat{S}}_{\star }\left(T_l\left(\mathbf{m}\right)\right)$ and $l\ne j$), the second by $\mathbf{m}\in \mathcal{I}\left(\widehat{S}\right)$, and the third by super-additivity. Thus ${\sum }_{l\in \widehat{S}\left(\mathbf{p}\right)}{g}_l^{\prime }\left(\mathbf{p}\right)\le 0$. The deviation property $D_1$ implies $\mathbf{p}\in \mathcal{I}\left(\widehat{S}\right)$.

2. By part 1, as $\mathbf{0}\in \mathcal{I}\left(\widehat{S}\right)$.

3. As $\mathbf{1}=(1,\dots ,1)$ is strictly externally stable, part 2 implies that $\mathbf{1}\in E_{ss}\left(G\right)$. Next, by contradiction we prove $E_{ss}\left(G\right)\subseteq \left\{\mathbf{1}\right\}$. So suppose $\mathbf{m}\in E_{ss}\left(G\right)$ with $\mathbf{m}\ne \mathbf{1}$. As $\mathbf{m}\in E_{ss}\left(G\right)$, we have $U_S\left(\mathbf{m}\right)=\varnothing$. As $\mathbf{m}\ne \mathbf{1}$, we can fix $i\in {\widehat{S}}_{\star }\left(\mathbf{m}\right)$. By Proposition 3(2), $T_i\left(\mathbf{m}\right)\notin \mathcal{I}\left(\widehat{S}\right)$, a contradiction with part 2. □

8.3. Symmetric Binary Action Games

For a symmetric game in strategic form with a unique Nash equilibrium, this equilibrium may not be strict as the following bi-matrix game shows:

$$\left(\begin{array}{ccc}1;1& 1;0& 0;1\\ 0;1& 0;0& 1;-1\\ 1;0& -1;1& 0;0\end{array}\right).$$

But, as part 2 of the following proposition shows, it is strict if the game is a binary action game.

Proposition 5. 

Consider a symmetric binary action game G.

1. 

G has the deviation property $D_1$ (and thus, a semi-strict Nash equilibrium).

2. 

If G has a unique Nash equilibrium, then this equilibrium is strict. ⋄

Proof. 

See Theorem 5 and Corollary 1 in [38]. □

Lemma 2. 

Consider a symmetric binary action game; let $S=\widehat{S}$ or $S={\widehat{S}}_{\star }$. Then for all action profiles $\mathbf{m},{\mathbf{m}}^{\prime }$ and players $i,j$ with $\#S\left(\mathbf{m}\right)=\#S\left({\mathbf{m}}^{\prime }\right)$, $i\in S\left(\mathbf{m}\right)$ and $j\in S\left({\mathbf{m}}^{\prime }\right)$, it holds that $g_i\left(\mathbf{m}\right)=g_j\left({\mathbf{m}}^{\prime }\right)and{g}_i\left(T_i\left(\mathbf{m}\right)\right)=g_j\left(T_j\left({\mathbf{m}}^{\prime }\right)\right)$. ⋄

Proof. 

By Lemma 2 in [38]. □

For a symmetric binary action game, define27

$$\begin{array}{ccc}\hfill w_0\left(s\right)& =& g_1(0,{\mathbf{1}}_s,\mathbf{0})(0\le s\le n-1),\hfill \end{array}$$

(8)

$$\begin{array}{ccc}\hfill w_1\left(s\right)& =& g_1({\mathbf{1}}_s,\mathbf{0})(1\le s\le n),\hfill \end{array}$$

(9)

and the function $t:\{0,1,\dots ,n+1\}\to \mathbb{R}\cup \{-\infty ,+\infty \}$ by

$$t\left(s\right):=\left\{\begin{array}{c}+\infty \mathrm{if} s=0,\hfill \\ g_1({\mathbf{1}}_s,\mathbf{0})-g_1(0,{\mathbf{1}}_{s-1},\mathbf{0})=w_1\left(s\right)-w_0(s-1) \mathrm{if} 1\le s\le n,\hfill \\ -\infty \mathrm{if} s=n+1.\hfill \end{array}\right.$$

(10)

We refer to t as the stability function.

Theorem 4. 

Suppose G is symmetric. Let $\mathbf{m}\in M^n$; write $s=\#\widehat{S}\left(\mathbf{m}\right)$.

1. 

$\mathbf{m}$ is a Nash equilibrium if and only if, $t(s+1)\le 0\le t\left(s\right)$.

2. 

$\mathbf{m}$ is a semi-strict Nash equilibrium if and only if, $t(s+1)<0\le t\left(s\right)$. ⋄

Proof. 

By Lemma 2, writing $s=\#\widehat{S}\left(\mathbf{m}\right)$, for $i\in \widehat{S}\left(\mathbf{m}\right)$ that $g_i\left(\mathbf{m}\right)=g_1({\mathbf{1}}_s,\mathbf{0})$, $g_i\left(T_i\left(\mathbf{m}\right)\right)=g_1(0,{\mathbf{1}}_{s-1},\mathbf{0})$, and therefore, $g_i^{\prime }\left(\mathbf{m}\right)=g_1(0,{\mathbf{1}}_{s-1},\mathbf{0})-g_1({\mathbf{1}}_s,\mathbf{0})=g_1^{\prime }({\mathbf{1}}_s,\mathbf{0})$. This in turn implies for $i\in {\widehat{S}}_{\star }\left(\mathbf{m}\right)$ that $g_i^{\prime }\left(\mathbf{m}\right)=-g_i^{\prime }\left(T_i\left(\mathbf{m}\right)\right)=-g_1(0,{\mathbf{1}}_s,0)+g_1({\mathbf{1}}_{s+1},\mathbf{0})=-g_1^{\prime }({\mathbf{1}}_{s+1},\mathbf{0})$. Having seen this, observe for all $\mathbf{m}\in M^n$ and $i\in N$

$$g_i^{\prime }\left(\mathbf{m}\right)=\left\{\begin{array}{c}-t(\#\widehat{S}\left(\mathbf{m}\right)) \mathrm{if} i\in \widehat{S}\left(\mathbf{m}\right),\hfill \\ t(\#\widehat{S}\left(\mathbf{m}\right)+1) \mathrm{if} i\in {\widehat{S}}_{\star }\left(\mathbf{m}\right).\hfill \end{array}\right.$$

(11)

2. We use (11). Definition 6(a) together with $t\left(0\right)=\infty$ to imply that $\mathbf{m}$ with $\widehat{S}\left(\mathbf{m}\right)\ge 1$ is weakly internally stable if and only if $t\left(s\right)\ge 0$. Definition 6(b) together with $t(n+1)=-\infty$ implies that $\mathbf{m}$ is strictly externally stable if and only if, $t(s+1)<0$. Thus, the desired results follows.

1. In the same way as 2. □

Proposition 6. 

If G is symmetric, then G is an aggregative game. ⋄

Proof. 

Note that, for every $i\in N$, the set $T_i={\sum }_{l\ne i}{M}_l$ equals $\{0,\dots ,n-1\}$. For $z\in T_i$, define ${\tilde{g}}_i^{\left(z\right)}:M_i\to \mathbb{R}$ by ${\tilde{g}}_i^{\left(z\right)}\left(m_i\right):=g_i(m_i,{\mathbf{1}}_z,0,\dots ,0)$. Lemma 2 (with $j=i$) implies, as desired by (2), that $g_i\left(\mathbf{m}\right)=g_i(m_i;{\mathbf{m}}_{\widehat{ı}})=g_i(m_i;{\mathbf{1}}_{{\sum }_{l\ne i}{m}_l},0,\dots ,0)={\tilde{g}}_i^{\left({\sum }_{l\ne i}{m}_l\right)}\left(m_i\right)$. □

8.4. Potentials

The concept of potential game originated in [39]. As far as we know they still did not find their way into the two-stage game approach to coalition formation. Roughly said, a game is said to be a potential game if the incentive of all players to change their strategy can be expressed using a single global function called the potential function. Nowadays, there exist various types of potential games. Potential games have interesting properties: a maximiser of the potential function is a pure Nash equilibrium, and a potential provides insight into (finite-time) convergence of an iterated game towards a Nash equilibrium and is helpful for performing comparative statics in case the game also has an aggregative structure ([23]). For an extensive treatment of potential games, we refer the reader to [40].

Theorem 5. 

A binary action game with the deviation property $D_1$ is a generalised, ordinal potential game. If in addition for each player his best-reply correspondence is single-valued, then the game is an ordinal potential game. ⋄

Proof. 

See Theorem 3 in [38]. □

By Proposition 5 and Theorem 3, each symmetric binary action game is a generalised ordinal potential game. But we can do better, as the next theorem shows.

Theorem 6. 

Consider a symmetric binary action game G.

1. 

G is an exact potential game. Even, the function $P:M^n\to \mathbb{R}$ defined by $P\left(\mathbf{m}\right):={\sum }_{l=1}^{\#\widehat{S}\left(\mathbf{m}\right)}t\left(l\right)$ is an exact potential.

2. 

G is a congestion game. ⋄

Proof. 

1. By Theorems 4 and 5 in [38].

2. By part 1, as each finite exact potential game is a congestion game ([39]). □

9. Cartel Games

9.1. Notion

An important example of a membership rule is the cartel membership rule, which is defined as follows.

Definition 9. 

The cartel membership rule is the membership rule $R_c:\mathbf{M}\to {\mathcal{C}}_N$ defined by $M_i=M=\{0,1\}(i\in N)$ and28

$$R_c\left(\mathbf{m}\right):=\left\{\begin{array}{c}\left\{\widehat{S}\left(\mathbf{m}\right)\right\}\cup {\cup }_{i\in {\widehat{S}}_{\star }\left(\mathbf{m}\right)}\left\{\left\{i\right\}\right\} if \mathbf{m}\ne \mathbf{0},\hfill \\ \left\{\right\{1\},\dots ,\{n\left\}\right\} if \mathbf{m}=\mathbf{0}.\hfill \end{array}\right.$$

Here $\widehat{S},{\widehat{S}}_{\star }:\mathbf{M}\to \mathbb{R}$ are defined by

$$\widehat{S}\left(\mathbf{m}\right):=\{i\in N|m_i=1\} and {\widehat{S}}_{\star }\left(\mathbf{m}\right):=\{i\in N|m_i=0\}.\diamond$$

We refer to the coalition structures in $R_c\left(\mathbf{M}\right)$ as cartel coalition structures.

Note that

$$\#\widehat{S}\left(\mathbf{m}\right)\le 1\Rightarrow R_c\left(\mathbf{m}\right)=\{\left\{1\right\},\dots ,\left\{n\right\}\}$$

(12)

and that $R_c:\mathbf{M}\backslash \left\{\mathbf{0}\right\}\to {\mathcal{C}}_N$ is injective.

Definition 10. 

A cartel game is a two-stage coalition formation game $(N;R;\mathrm{\Gamma })$ where the membership rule R is the cartel membership rule $R_c$. ⋄

If $\#\widehat{S}\left(\mathbf{m}\right)=\#\widehat{S}\left({\mathbf{m}}^{\prime }\right)$, then there exists a permutation $\pi$ of N with ${\mathbf{m}}^{\prime }=T_{\pi }\left(\mathbf{m}\right)$. Therefore, Proposition 1 implies

$$\#\widehat{S}\left(\mathbf{m}\right)=\#\widehat{S}\left({\mathbf{m}}^{\prime }\right)\Rightarrow R_c\left(\mathbf{m}\right)\sim R_c\left({\mathbf{m}}^{\prime }\right).$$

The cartel membership rule can be generalised as follows by the following membership rule $R_{cc}:\mathbf{M}\to {\mathcal{C}}_N$ defined by $M_i=\{0,1,\dots ,p\}(i\in N)$ and

$$R_{cc}\left(\mathbf{m}\right):={\cup }_{k=1,\dots ,p \mathrm{with} {\widehat{S}}_k\left(\mathbf{m}\right)\ne \varnothing }\left\{{\widehat{S}}_k\left(\mathbf{m}\right)\right\}\cup {\cup }_{i\in {\widehat{S}}_0\left(\mathbf{m}\right)}\left\{\left\{i\right\}\right\}$$

where $p\ge 1$ and ${\widehat{S}}_k\left(\mathbf{m}\right)=\{i\in N|m_i=k\}$.29

Proposition 7. 

The membership rule $R_{cc}$ is symmetric. ⋄

Proof. 

Let $\pi$ be a permutation of N and $\mathbf{m}\in \mathbf{M}$.

First note that ${\widehat{S}}_k\left(T_{\pi }\left(\mathbf{m}\right)\right)={\pi }^{<-1>}\left({\widehat{S}}_k\left(\mathbf{m}\right)\right)$. Indeed: $i\in {\widehat{S}}_k\left(T_{\pi }\left(\mathbf{m}\right)\right)\iff k={\left(T_{\pi }\left(\mathbf{m}\right)\right)}_i=m_{\pi \left(i\right)}\iff \pi \left(i\right)\in {\widehat{S}}_k\left(\mathbf{m}\right)\iff k\in {\pi }^{<-1>}\left({\widehat{S}}_k\left(\mathbf{m}\right)\right)$. This implies, as desired, $R_{cc}\left(T_{\pi }\left(\mathbf{m}\right)\right)=\{{\widehat{S}}_1\left(T_{\pi }\left(\mathbf{m}\right)\right),\dots ,{\widehat{S}}_s\left(T_{\pi }\left(\mathbf{m}\right)\right)\}\cup {\cup }_{i\in {\widehat{S}}_0\left(T_{\pi }\left(\mathbf{m}\right)\right)}\left\{\left\{i\right\}\right\}=\{{\pi }^{<-1>}\left({\widehat{S}}_1\left(\mathbf{m}\right)\right),\dots ,{\pi }^{<-1>}\left({\widehat{S}}_s\left(\mathbf{m}\right)\right)\}\cup {\cup }_{i\in {\pi }^{<-1>}\left({\widehat{S}}_0\left(\mathbf{m}\right)\right)}\left\{\left\{i\right\}\right\}=\left\{{\pi }^{<-1>}\left(C\right)\right|C\in R_{cc}\left(\mathbf{m}\right)\}$. □

9.2. Equilibrium Coalition Structures

In this subsection we consider a regular cartel formation game $(N;R_c;\mathrm{\Gamma })$. Again, G denotes its effective game.

As all membership action sets $M_i$ equal $M:=\{0,1\}$, G is a binary action game. A useful observation is that G has, by (6) and (12), the following property:

$$g_i\left(\mathbf{m}\right)=g_i\left(\mathbf{0}\right)\text{for} \text{all} i\in N \mathrm{and} \mathbf{m}\in M^n \mathrm{with} \#\widehat{S}\left(\mathbf{m}\right)=1.$$

(13)

(13) implies that for each player i the best reply to the strategy profile $\mathbf{0}$ of its opponents equals $\{0,1\}$. Thus, no best-reply correspondence is single-valued.

With the stability function t as given by (10), (13) implies for a symmetric G

$$t\left(1\right)=0.$$

(14)

For the effective game G the literature not only considers its Nash equilibria set $E\left(G\right)$ but also its semi-strict Nash equilibrium set

$$E_{ss}\left(G\right).$$

As $E_{ss}\left(G\right)\subseteq E\left(G\right)$, we then have for every $\mathbf{m}\in E_{ss}\left(G\right)$ a semi-strict equilibrium coalition structure $R_c\left(\mathbf{m}\right)$. Property (13) implies

$$\#\widehat{S}\left(\mathbf{m}\right)\le 1\Rightarrow \mathbf{m}\in \mathcal{I}\left(\widehat{S}\right),\mathbf{0}\in E\left(G\right),\mathbf{0}\notin E_{ss}\left(G\right).$$

(15)

As $R_c\left(\mathbf{0}\right)=\{\left\{1\right\},\dots ,\left\{n\right\}\}$, we obtain:

Proposition 8. 

The ineffective coalition structure $\left\{\right\{1\},\dots ,\{n\left\}\right\}$ is for each cartel game an equilibrium coalition structure. ⋄

However, (15) does not exclude that the ineffective coalition structure is a semi-strict equilibrium cartel coalition structure: indeed, if $\mathbf{m}$ is a semi-strict Nash equilibrium with $\#\widehat{S}\left(\mathbf{m}\right)=1$, then the ineffective coalition structure is a semi-strict equilibrium cartel coalition structure.

Example 3. 

Consider again, Example 1. There we found that for $n\ge 3$ the equilibrium coalition structures are exactly the cartel coalition structures with zero, two, or three cooperators and that for $n=2$ the equilibrium coalition structures are exactly the cartel coalition structures with zero or two cooperators. With Theorem 6(2), we see that the semi-strict equilibrium coalition structures are for $n\ge 3$ exactly the cartel coalition structures with 3 cooperators and for $n=2$ exactly the cartel coalition structures with 2 cooperators. ⋄

Proposition 9. 

If G is a super-additive cartel game and has the deviation property $D_1$, then each action profile $\mathbf{p}$ with $\#\widehat{S}\left(\mathbf{p}\right)=2$ is weakly internally stable. ⋄

Proof. 

We may suppose that $\widehat{S}\left(\mathbf{p}\right)=\{1,2\}$. So ${\widehat{S}}_{\star }\left(\mathbf{p}\right)=N\backslash \{1,2\}$. We have to prove that $g_1\left(\mathbf{p}\right)\ge g_1\left(T_1\left(\mathbf{p}\right)\right)\wedge g_2\left(\mathbf{p}\right)\ge g_2\left(T_2\left(\mathbf{p}\right)\right).$ As the game is a cartel game, this becomes $g_1\left(\mathbf{p}\right)\ge g_1\left(\mathbf{0}\right)\wedge g_2\left(\mathbf{p}\right)\ge g_2\left(\mathbf{0}\right).$ As the game has the deviation property $D_1$, we have $g_1\left(\mathbf{p}\right)\ge g_1\left(T_1\left(\mathbf{p}\right)\right)\iff g_2\left(\mathbf{p}\right)\ge g_2\left(T_2\left(\mathbf{p}\right)\right)$. Thus, the proof is complete if we can show that

$$g_1\left(\mathbf{p}\right)+g_2\left(\mathbf{p}\right)\ge g_1\left(\mathbf{0}\right)+g_2\left(\mathbf{0}\right).$$

Applying Definition 8 with $\mathbf{m}=(1,0,\dots ,0)$ and $i=2$ (and noting that $T_i\left(\mathbf{m}\right)=\mathbf{p})$ gives the result. □

Theorem 7. 

Consider a regular cartel game $(N;R_c;\mathrm{\Gamma })$ with a symmetric physical game Γ. Let G be its effective game.

1. 

G is a symmetric game, an aggregative game, an exact potential game, and a congestion game and has the deviation property $D_1$. The function $P\left(\mathbf{m}\right)={\sum }_{l=1}^{\#\widehat{S}\left(\mathbf{m}\right)}t\left(l\right)$ is an exact potential.

2. 

G has a semi-strict Nash equilibrium, and therefore, a semi-strict equilibrium cartel coalition structure.

3. 

If G has a unique Nash equilibrium, then $\mathbf{1}$ is this equilibrium, this equilibrium is strict, $\left\{N\right\}$ is a semi-strict equilibrium cartel coalition structure and there is no other equilibrium cartel coalition structure.

4. 

If there exists a membership action profile $\mathbf{m}$ with two cooperators such that $g_i\left(\mathbf{m}\right)\ge g_i\left(\mathbf{0}\right)$ for some cooperator i, then there exists an effective semi-strict equilibrium cartel coalition structure. ⋄

Proof. 

1. Noting that by Proposition 7 the membership rule $R_c$ is symmetric, Theorem 2(1) applies and guarantees that G is symmetric. Next, apply Theorem 6, Proposition 5(1) and Proposition 6.

2. As, by part 1, G is a symmetric binary action game, it has by Proposition 5(1) a semi-strict Nash equilibrium.

3. Let $\mathbf{m}$ be this equilibrium. By Proposition 5(2), $\mathbf{m}$ is strict. As G is symmetric, $\mathbf{m}$ is symmetric. As, by (15), $\mathbf{0}$ is not a semi-strict Nash equilibrium, $\mathbf{m}=\mathbf{1}$ follows. Thus $R_c\left(\mathbf{m}\right)=\left\{N\right\}$ is a semi-strict equilibrium cartel coalition structure. Of course, there is no other equilibrium cartel coalition structure.

4. As $\#\widehat{S}\left(\mathbf{m}\right)=2$, we have $\#\widehat{S}\left(T_i\left(\mathbf{m}\right)\right)=1$, and therefore, by (13), $g_i\left(\mathbf{m}\right)\ge g_i\left(\mathbf{0}\right)=g_i\left(T_i\left(\mathbf{m}\right)\right)$. So $g_i\left(\mathbf{m}\right)\ge g_i\left(T_i\left(\mathbf{m}\right)\right)$. As by part 1 the game has the deviation property $D_1$ it follows that $g_k\left(\mathbf{m}\right)\ge g_k\left(T_k\left(\mathbf{m}\right)\right)$ for all $k\in \widehat{S}\left(\mathbf{m}\right)$. Thus $\mathbf{m}$ is weakly internally stable. Theorem 3(2) implies that there exists a semi-strict Nash equilibrium $\mathbf{a}$ with $\#\widehat{S}\left(\mathbf{a}\right)\ge \#\widehat{S}\left(\mathbf{m}\right)=2$. Thus, $R_c\left(\mathbf{a}\right)$ is an effective semi-strict equilibrium cartel coalition structure. □

The nice thing in Theorem 7(1,2,3) is that its results almost solely depend on the qualitative properties of the primitives of the physical game, namely being symmetric. We write “almost” as there is the additional assumption that the cartel game is regular.

It is well-known that each maximiser of a finite exact potential game is a Nash equilibrium. Let us now, for Example 1 identify the Nash equilibria obtained by maximising the potential P in Theorem 7(5):

Example 4. 

Consider again, Example 1. There we obtain for the exact potential P in Theorem 7(1), writing $s=\#\widehat{S}\left(\mathbf{m}\right)$,

$$P\left(\mathbf{m}\right)=\sum _{l=1}^{s}t\left(l\right)=\sum _{l=1}^s(-\frac{1}{2}{l}^2+2l-\frac{3}{2})\frac{b^2}{a}=(-\frac{1}{6}{s}^3+\frac{3}{4}{s}^2-\frac{7}{12}s)\frac{b^2}{a}.$$

The maximisers of P are the strategy profiles with 2 or 3 cooperators (i.e., $s=2$ or $s=3$). ⋄

Proposition 10. 

Consider a regular cartel game $(N;R_c;\mathrm{\Gamma })$. Suppose that the effective game G has deviation property $D_1$.

1. 

G is a generalised ordinal potential game.

2. 

G has a semi-strict Nash equilibrium, and therefore, a semi-strict equilibrium cartel coalition structure.

3. 

If there exists a membership action profile $\mathbf{m}$ with $\#\widehat{S}\left(\mathbf{m}\right)\ge 2$ such that $g_i\left(\mathbf{m}\right)\ge g_i\left(\mathbf{0}\right)$ for some player $i\in \widehat{S}\left(\mathbf{m}\right)$, then there exists an effective semi-strict equilibrium coalition structure. ⋄

Proof. 

1. By Theorem 3 in [38].

2. By Theorem 3(2).

3. Exactly the same (but omitting “by part 1” there) as Theorem 7(4). □

10. Further Examples

To illustrate and compLemmant our general results from the previous section, we now determine the (semi-strict) equilibrium cartel coalition structures for some concrete cartel formation games with a Cournot-like game as physical game.

Example 5. 

Consider the cartel game with a physical game the Cournot-like public good game with common action set $X={\mathbb{R}}_{+}$ and with payoff functions

$$f_i\left(\mathbf{x}\right)=-c_i\left(x_i\right)+b_i\sum _{l=1}^n{x}_l$$

where $c_i$ is continuously differentiable, strictly convex, and strictly increasing with ${lim}_{x_i\to \infty }{c}_i^{\prime }\left(x_i\right)=\infty$, $b_i>0$ and $b_i\ge c_i^{\prime }\left(0\right)$. With this example we provide a more general variant of Example 1: it will relax the assumption of a quadratic (cost) function $c_i$.

Note that $c_i:{\mathbb{R}}_{+}\to [c_i\left(0\right),\infty [$, $c_i^{\prime }:{\mathbb{R}}_{+}\to [c_i^{\prime }\left(0\right),\infty [$, and ${c_i^{\prime }}^{<-1>}:[c_i^{\prime }\left(0\right),\infty [\to {\mathbb{R}}_{+}$. For $A\subseteq N$ we denote $b\left(A\right):={\sum }_{l\in A}{b}_l$.

The payoff function ${\widehat{P}}_C$ of meta player $C\in R_c\left(\mathbf{m}\right)$ in terms of the action profile $\mathbf{x}\in \mathbf{X}=X^n$ equals

$${\widehat{P}}_C\left(\mathbf{x}\right)=\left\{\begin{array}{c}-c_i\left(x_i\right)+b_i{x}_i+b_i\sum _{l\ne i}{x}_l if C=\left\{i\right\}with i\in {\widehat{S}}_{\star }\left(\mathbf{m}\right),\hfill \\ \sum _{i\in C}(-c_i\left(x_i\right)+b\left(C\right)x_i)+b\left(C\right)\sum _{l\notin C}{x}_l if C=\widehat{S}\left(\mathbf{m}\right),\hfill \end{array}\right.$$

the effective physical actions are

$${\widehat{x}}_i\left(\mathbf{m}\right)=\left\{\begin{array}{c}{\underline{x}}_i(i\in {\widehat{S}}_{\star }\left(\mathbf{m}\right)),\hfill \\ {\overline{x}}_i\left(\mathbf{m}\right)(i\in \widehat{S}\left(\mathbf{m}\right)),\hfill \end{array}\right.$$

where ${\underline{x}}_i={c_i^{\prime }}^{<-1>}\left(b_i\right)$ and ${\overline{x}}_i\left(\mathbf{m}\right)={c_i^{\prime }}^{<-1>}\left(b\left(\widehat{S}\left(\mathbf{m}\right)\right)\right)$ and the effective payoffs are

$$g_i\left(\mathbf{m}\right)=\left\{\begin{array}{c}-c_i\left({\underline{x}}_i\right)+b_i(\sum _{l\in \widehat{S}\left(\mathbf{m}\right)}{\overline{x}}_l\left(\mathbf{m}\right)+\sum _{l\in {\widehat{S}}_{\star }\left(\mathbf{m}\right)}{\underline{x}}_l) if m_i=0,\hfill \\ -c_i\left({\overline{x}}_i\left(\mathbf{m}\right)\right)+b_i(\sum _{l\in \widehat{S}\left(\mathbf{m}\right)}{\overline{x}}_l\left(\mathbf{m}\right)+\sum _{l\in {\widehat{S}}_{\star }\left(\mathbf{m}\right)}{\underline{x}}_l) if m_i=1.\hfill \end{array}\right.$$

Although the further analysis also is analogous to that in Example 1, we shall proceed from here on by referring to the theory developed in the meanwhile.

In order to simplify, further suppose that $c_1=\cdots =c_n=:c$ and $b_1=\cdots =b_n=:b$. As the physical game is symmetric, the effective game G is so too by Theorem 2.30

Now let us determine the stability function t. We already know that

$$t\left(0\right)=+\infty ,t\left(1\right)=0,t(n+1)=-\infty .$$

For the functions $w_0$ and $w_1$ in (8) and (9) writing $s=\#\widehat{S}\left(\mathbf{m}\right)$ and $\overline{x}\left(s\right)={c^{\prime }}^{<-1>}\left(sb\right)(s\ge 1)$

$$w_0\left(s\right)=g_1(0,{\mathbf{1}}_s,\mathbf{0})=-c\left(\overline{x}\left(1\right)\right)+b((n-s)\overline{x}\left(1\right)+s\overline{x}\left(s\right))(1\le s\le n-1),$$

$$w_1\left(s\right)=g_1({\mathbf{1}}_s,\mathbf{0})=-c\left(\overline{x}\left(s\right)\right)+b((n-s)\overline{x}\left(1\right)+s\overline{x}\left(s\right))(1\le s\le n).$$

So for $s\ge 2$, we obtain $t\left(s\right)=w_1\left(s\right)-w_0(s-1)=-c\left(\overline{x}\left(s\right)\right)+b((n-s)\overline{x}\left(1\right)+s\overline{x}\left(s\right))-(-c\left(\overline{x}\left(1\right)\right)+b((n-(s-1))\overline{x}\left(1\right)+s\overline{x}(s-1)))=-c\left(\overline{x}\left(s\right)\right)+c\left(\overline{x}\left(1\right)\right)+bs\overline{x}\left(s\right)-b\overline{x}\left(1\right)-b(s-1)\overline{x}(s-1)=-c\left(\overline{x}\left(s\right)\right)+c\left(\overline{x}\left(1\right)\right)+b\left(s(\overline{x}\left(s\right)-\overline{x}(s-1))+\overline{x}(s-1)-\overline{x}\left(1\right)\right)$. Thus for $2\le s\le n$ we get the formula

$$t\left(s\right)=c\left(\overline{x}\left(1\right)\right)-c\left(\overline{x}\left(s\right)\right)+b\left(s(\overline{x}\left(s\right)-\overline{x}(s-1))+\overline{x}(s-1)-\overline{x}\left(1\right)\right).$$

(16)

(For $n\ge 3$) this formula implies $t\left(2\right)=c\left(\overline{x}\left(1\right)\right)-c\left(\overline{x}\left(2\right)\right)+b(2\overline{x}\left(2\right)-2\overline{x}\left(1\right))$ and $t\left(3\right)=c\left(\overline{x}\left(1\right)\right)-c\left(\overline{x}\left(3\right)\right)+b(3\overline{x}\left(3\right)-2\overline{x}\left(2\right)-\overline{x}\left(1\right))$.

Further suppose $c\left(x\right)=\frac{a}{p}{x}^p$ with $a>0$ and $p>1$. Then ${c^{\prime }}^{<-1>}\left(y\right)={(y/a)}^{1/(p-1)}$, $\overline{x}\left(s\right)=s^{1/(p-1)}\overline{x}\left(1\right)$, $\overline{x}\left(1\right)={(b/a)}^{1/(p-1)}$ and $c\left(\overline{x}\left(s\right)\right)=s^{p/(p-1)}\frac{b}{p}\overline{x}\left(1\right))$. Therefore for $2\le s\le n$ we find

$$t\left(s\right)=b\overline{x}\left(1\right)\left(\frac{1}{p}(1-s^{p/(p-1)})+s^{p/(p-1)}-1-{(s-1)}^{p/(p-1)}\right).$$

Let us consider various cases. First suppose $n=2$. We have $t\left(0\right)=\infty ,t\left(1\right)=0$, $t\left(3\right)=-\infty$ and $t\left(2\right)=\overline{x}\left(1\right)b(-\frac{3}{2}+2^{\frac{1}{p-1}})$. This implies $t\left(2\right)\le 0\iff p\ge {log}_{3/2}3$ and $t\left(2\right)=0\iff p={log}_{3/2}3$. It follows that for $n=2$ the equilibrium cartel coalition structures are exactly the cartel coalition structures with 0 and with 1 cooperators if $p>{log}_{3/2}3$, the cartel coalition structures with $0,1$ and 2 cooperators if $p={log}_{3/2}3$ and the cartel coalition structures with 0 or 2 cooperators if $p<{log}_{3/2}3$. Also for $n=2$ the semi-strict equilibrium cartel coalition structures are exactly the cartel coalition structures with 1 cooperator if $p>{log}_{3/2}3$ and the cartel coalition structures with 2 cooperators if $p\le {log}_{3/2}3$.

A further analysis (with numerical simulations) shows that for $n\ge 3$ and p an integer with $p\ge 3$ the equilibrium cartel coalition structures are exactly the cartel coalition structures with 0 and with 2 cooperators. ⋄

Example 6. 

Consider the cartel game with as physical game the Cournot-like public bad game with common action set $X=[0,1]$ and with payoff functions

$$f_i\left(\mathbf{x}\right)=\beta x_i-{\delta }_i\sum _{l=1}^n{x}_l$$

where $0\le {\delta }_i\le 1<\beta$. Also suppose that ${max}_{i\in N}{\delta }_i=1$ and there does not exist $\mathbf{m}\in M^n$ with $\beta ={\sum }_{l\in \widehat{S}\left(\mathbf{m}\right)}{\delta }_l.$

Consider for $\mathbf{m}\in M^n$ the coalitional game ${\mathrm{\Gamma }}_{R_c\left(\mathbf{m}\right)}$. In terms of the action profile $\mathbf{x}\in X^n$ the payoff function of meta player $C\in R_c\left(\mathbf{m}\right)$ equals

$${\widehat{P}}_C\left(\mathbf{x}\right)=\left\{\begin{array}{c}(\beta -{\delta }_i)x_i-{\delta }_i\sum _{l\ne i}{x}_l if C=\left\{i\right\} with i\in {\widehat{S}}_{\star }\left(\mathbf{m}\right),\hfill \\ \sum _{i\in C}(\beta -\sum _{l\in C}{\delta }_l)x_i-\left(\sum _{l\in C}{\delta }_l\right)\sum _{l\notin C}{x}_l if C=\widehat{S}\left(\mathbf{m}\right).\hfill \end{array}\right.$$

It is clear that in this coalitional game each meta player $C=\left\{i\right\}$ has 1 as a strictly dominant action. Additionally, meta player $C=\widehat{S}\left(\mathbf{m}\right)$ has a strictly dominant action: if $\beta >{\sum }_{l\in \widehat{S}\left(\mathbf{m}\right)}{\delta }_l$, then each of its members plays 1 and if $\beta <{\sum }_{l\in \widehat{S}\left(\mathbf{m}\right)}{\delta }_l$, then each of its members plays 0. Thus, this game has a unique Nash equilibrium, the two-stage coalition formation game is regular and for the with this equilibrium corresponding action profile $\widehat{\mathbf{x}}\left(\mathbf{m}\right)$ we have

$${\widehat{x}}_i\left(\mathbf{m}\right)=\left\{\begin{array}{c}1 if i\in {\widehat{S}}_{\star }\left(\mathbf{m}\right),\hfill \\ 1 if i\in \widehat{S}\left(\mathbf{m}\right) in case \beta >\sum _{l\in \widehat{S}\left(\mathbf{m}\right)}{\delta }_l,\hfill \\ 0 if i\in \widehat{S}\left(\mathbf{m}\right) in case \beta <\sum _{l\in \widehat{S}\left(\mathbf{m}\right)}{\delta }_l.\hfill \end{array}\right.$$

Now further suppose that ${\delta }_1=\cdots ={\delta }_n=1$ and let us consider the effective game G. For its effective payoffs $g_i\left(\mathbf{m}\right)=f_i\left(\widehat{\mathbf{x}}\left(\mathbf{m}\right)\right)$, we obtain

$$g_i\left(\mathbf{m}\right)=\left\{\begin{array}{c}\beta -n if i\in {\widehat{S}}_{\star }\left(\mathbf{m}\right) in case \beta >\#\widehat{S}\left(\mathbf{m}\right),\hfill \\ \beta -n+\#\widehat{S}\left(\mathbf{m}\right) if i\in {\widehat{S}}_{\star }\left(\mathbf{m}\right) in case \beta <\#\widehat{S}\left(\mathbf{m}\right),\hfill \\ \beta -n if i\in \widehat{S}\left(\mathbf{m}\right) in case \beta >\#\widehat{S}\left(\mathbf{m}\right),\hfill \\ \#\widehat{S}\left(\mathbf{m}\right)-n if i\in \widehat{S}\left(\mathbf{m}\right) in case \beta <\#\widehat{S}\left(\mathbf{m}\right).\hfill \end{array}\right.$$

Define the integer $s_{\star }$ as follows

$$if \beta <n:s_{\star } is the unique integer such that \beta <s_{\star }<\beta +1,$$

$$if \beta >n:s_{\star }=n.$$

Note that $2\le s_{\star }\le n$. Now, writing $s=\#\widehat{S}\left(\mathbf{m}\right)$,

$$g_i\left(\mathbf{m}\right)=\left\{\begin{array}{c}\beta -n if i\in {\widehat{S}}_{\star }\left(\mathbf{m}\right) in case s\le s_{\star }-1,\hfill \\ \beta -n+s if i\in {\widehat{S}}_{\star }\left(\mathbf{m}\right) in case s\ge s_{\star },\hfill \\ \beta -n if i\in \widehat{S}\left(\mathbf{m}\right) in case s\le s_{\star }-1,\hfill \\ s-n if i\in \widehat{S}\left(\mathbf{m}\right) in case s\ge s_{\star }.\hfill \end{array}\right.$$

Again the effective game is symmetric. Now let us determine the stability function t. For the functions $w_0$ and $w_1$ in (8) and (9) we obtain

$$w_0\left(s\right)=g_1(0,{\mathbf{1}}_s,\mathbf{0})=\left\{\begin{array}{c}\beta -n(0\le s\le s_{\star }-1),\hfill \\ \beta -n+s(s_{\star }\le s\le n-1),\hfill \end{array}\right.$$

$$w_1\left(s\right)=g_1({\mathbf{1}}_s,\mathbf{0})=\left\{\begin{array}{c}\beta -n(1\le s\le s_{\star }-1),\hfill \\ s-n(s_{\star }\le s\le n).\hfill \end{array}\right.$$

With (10) we obtain $t\left(0\right)=\infty ,t\left(s\right)=(\beta -n)-(\beta -n)=0(1\le s\le s_{\star }-1),t_{s_{\star }}=(s_{\star }-n)-(\beta -n)=s_{\star }-\beta >0,t_s=(s-n)-(\beta -n+s-1)=1-\beta <0$, $t(n+1)=-\infty$. It follows that the equilibrium coalition structures are exactly the cartel coalition structures with $0,1,\dots ,s_{\star }-2$ and $s_{\star }$ cooperators. The semi-strict equilibrium coalition structures are exactly the cartel coalition structures with $s_{\star }$ cooperators. ⋄

Example 7. 

Consider the cartel game with as physical game the Cournot-like public good game with common action set $X={\mathbb{R}}_{+}$ and with payoff functions

$$f_i\left(\mathbf{x}\right)=-{\gamma }_i{x}_i+b_i\left(\sum _{l=1}^n{x}_l\right)$$

where $0<{\gamma }_1<\cdots <{\gamma }_n$ and $b_i$ continuously differentiable, strictly concave, and strictly increasing with

$$0<b_i^{\prime }\left(0\right)<{\gamma }_i and \underset{y\to \infty }{lim}{b}_i^{\prime }\left(y\right)=0.$$

We shall prove that for each semi-strict Nash equilibrium ${\mathbf{m}}^{\star }$ its associated physical action profile $\widehat{\mathbf{x}}\left({\mathbf{m}}^{\star }\right)$ is the action profile $\mathbf{0}$.

Consider, for $\mathbf{m}\in M^n$, the coalitional game ${\mathrm{\Gamma }}_{R_c\left(\mathbf{m}\right)}$. In terms of the physical action profile $\mathbf{x}$ the payoff of meta player C is

$${\widehat{P}}_C\left(\mathbf{x}\right)=\left\{\begin{array}{c}{b}_i(x_i+\sum _{l\ne i}{x}_l)-{\gamma }_i{x}_i if C=\left\{i\right\} with i\in {\widehat{S}}_{\star }\left(\mathbf{m}\right),\hfill \\ \sum _{l\in C}{b}_l(\sum _{i\in C}{x}_i+\sum _{j\notin C}{x}_j)-\sum _{l\in C}{\gamma }_l{x}_l if C=\widehat{S}\left(\mathbf{m}\right).\hfill \end{array}\right.$$

It follows that each meta player $C=\left\{i\right\}$ has 0 as strictly dominant strategy. However, the best-reply correspondence of meta player $C=\widehat{S}\left(\mathbf{m}\right)$ depends on ${\sum }_{j\notin C}{x}_j$ which means that such a meta player does not have a strictly dominant strategy.

The above implies that $\mathbf{k}={\left(k_C\right)}_{C\in R_c\left(\mathbf{m}\right)}$ is a Nash equilibrium of ${\mathrm{\Gamma }}_{R_c\left(\mathbf{m}\right)}$ if and only if

$$k_i=0(i\in {\widehat{S}}_{\star }\left(\mathbf{m}\right))$$

and $k_{\widehat{S}\left(\mathbf{m}\right)}$ is, with $Z:={\prod }_{l\in \widehat{S}\left(\mathbf{m}\right)}{\mathbb{R}}_{+}$, a solution of the concave programming problem

$${\mathrm{MAX}}_{\mathbf{k}\in Z}\sum _{l\in \widehat{S}\left(\mathbf{m}\right)}{b}_l\left(\sum _{r\in \widehat{S}\left(\mathbf{m}\right)}{k}_r\right)-\sum _{l\in \widehat{S}\left(\mathbf{m}\right)}{\gamma }_l{k}_l.$$

As Z is not open, special attention has to be given to analyse this problem with a (standard) Karush–Kuhn–Tucker like theorem. Concerning this, we note that $b_i$ can be extended to an open interval J containing ${\mathbb{R}}_{+}$ on which $b_i$ is continuously differentiable, strictly concave, and strictly increasing. The Karush–Kuhn–Tucker theorem guarantees that $k_{\widehat{S}\left(\mathbf{m}\right)}$ is a solution of the concave programming problem if and only if, writing $C=\widehat{S}\left(\mathbf{m}\right)$, there exists ${\lambda }_j(j\in C)$ such that

$$for all i\in C:k_i\ge 0;$$

$$for all j\in C:{\lambda }_j\ge 0;$$

$$for all i\in C:\sum _{l\in C}{b}_l^{\prime }\left(\sum _{r\in C}{k}_r\right)-{\gamma }_i+{\lambda }_i\le 0;$$

$$for all i\in C:k_i\left(\sum _{l\in C}{b}_l^{\prime }\left(\sum _{r\in C}{k}_r\right)-{\gamma }_i+{\lambda }_i\right)=0;$$

$$for all j\in C:{\lambda }_j{k}_j=0.$$

This concave programming problem has a unique solution. In order to formulate this solution we define for a non-empty subset A of N, the function $h_A:{\mathbb{R}}_{+}\to \mathbb{R}$ by $h_A:={\sum }_{l\in A}{b}_l^{\prime }$. Note that $h_A$ is strictly decreasing and that its image $h_A\left({\mathbb{R}}_{+}\right)=]0,h_A\left(0\right)]$ equals $]0,{\sum }_{l\in A}{b}_l^{\prime }\left(0\right)]$. The unique solution is:31

$$k_i=\left\{\begin{array}{cc}0\hfill & ifthereexistsj\in C\backslash \left\{i\right\}with{\gamma }_j<{\gamma }_i,\hfill \\ 0\hfill & ifforallj\in C\backslash \left\{i\right\}onehas{\gamma }_j>{\gamma }_i\wedge h_C\left(0\right)\le {\gamma }_i,\hfill \\ h_C^{<-1>}\left({\gamma }_i\right)\hfill & ifforallj\in C\backslash \left\{i\right\}onehas{\gamma }_j>{\gamma }_i\wedge h_C\left(0\right)>{\gamma }_i.\hfill \end{array}\right.$$

The conclusion is that the two-stage coalition formation game is regular and that its effective physical actions are

$$\widehat{x_i}\left(\mathbf{m}\right)=\left\{\begin{array}{cc}0\hfill & ifi\in \widehat{S_{\star }}\left(\mathbf{m}\right),\hfill \\ 0\hfill & ifi\in \widehat{S}\left(\mathbf{m}\right)and\exists j\in \widehat{S}\left(\mathbf{m}\right)\backslash \left\{i\right\}with{\gamma }_j<{\gamma }_i,\hfill \\ 0\hfill & ifi\in \widehat{S}\left(\mathbf{m}\right)and\forall j\in \widehat{S}\left(\mathbf{m}\right)\backslash \left\{i\right\}onehas{\gamma }_j>{\gamma }_i\wedge h_{\widehat{S}\left(\mathbf{m}\right)}\left(0\right)\le {\gamma }_i,\hfill \\ h_{\widehat{S}\left(\mathbf{m}\right)}^{<-1>}\left({\gamma }_i\right)\hfill & ifi\in \widehat{S}\left(\mathbf{m}\right)and\forall j\in \widehat{S}\left(\mathbf{m}\right)\backslash \left\{i\right\}onehas{\gamma }_j>{\gamma }_i\wedge h_{\widehat{S}\left(\mathbf{m}\right)}\left(0\right)>{\gamma }_i.\hfill \end{array}\right.$$

Introducing for $\mathbf{m}\ne \mathbf{0}$, $i_{\mathbf{m}}:=min\left(\widehat{S}\left(\mathbf{m}\right)\right)$ we can rewrite $\widehat{x_i}\left(\mathbf{m}\right)$ as follows

$$\widehat{x_i}\left(\mathbf{m}\right)=\left\{\begin{array}{cc}0\hfill & ifi\in \widehat{S_{\star }}\left(\mathbf{m}\right),\hfill \\ 0\hfill & ifi\in \widehat{S}\left(\mathbf{m}\right)\backslash i_{\mathbf{m}},\hfill \\ 0\hfill & ifi\in \widehat{S}\left(\mathbf{m}\right)\wedge i=i_{\mathbf{m}}\wedge h_{\widehat{S}\left(\mathbf{m}\right)}\left(0\right)\le {\gamma }_{i_{\mathbf{m}}},\hfill \\ h_{\widehat{S}\left(\mathbf{m}\right)}^{<-1>}\left({\gamma }_{i_{\mathbf{m}}}\right)\hfill & ifi\in \widehat{S}\left(\mathbf{m}\right)\wedge i=i_{\mathbf{m}}\wedge h_{\widehat{S}\left(\mathbf{m}\right)}\left(0\right)>{\gamma }_{i_{\mathbf{m}}}.\hfill \end{array}\right.$$

Note that we have ${\sum }_{l=1}^n{\widehat{x}}_l\left(\mathbf{m}\right)={\widehat{x}}_{i_{\mathbf{m}}}\left(\mathbf{m}\right)(\mathbf{m}\ne \mathbf{0})$ and ${\sum }_{l=1}^n{\widehat{x}}_l\left(\mathbf{0}\right)=0$. For the effective payoffs $g_i\left(\mathbf{m}\right)=f_i\left(\widehat{\mathbf{x}}\left(\mathbf{m}\right)\right)$, we obtain $g_i\left(\mathbf{0}\right)=b_i\left(0\right)$ and, for $\mathbf{m}\ne \mathbf{0}$,

$$g_i\left(\mathbf{m}\right)=-{\gamma }_i{\widehat{x}}_i\left(\mathbf{m}\right)+b_i\left({\widehat{x}}_{i_{\mathbf{m}}}\left(\mathbf{m}\right)\right)$$

$$=\left\{\begin{array}{cc}{b}_i\left({\widehat{x}}_{i_{\mathbf{m}}}\left(\mathbf{m}\right)\right)\hfill & ifi\in {\widehat{S}}_{\star }\left(\mathbf{m}\right),\hfill \\ b_i\left({\widehat{x}}_{i_{\mathbf{m}}}\left(\mathbf{m}\right)\right)\hfill & ifi\in \widehat{S}\left(\mathbf{m}\right)\wedge i\ne i_{\mathbf{m}},\hfill \\ b_{i_{\mathbf{m}}}\left({\widehat{x}}_{i_{\mathbf{m}}}\left(\mathbf{m}\right)\right)\hfill & ifi\in \widehat{S}\left(\mathbf{m}\right)\wedge i=i_{\mathbf{m}}\wedge h_{\widehat{S}\left(\mathbf{m}\right)}\left(0\right)\le {\gamma }_{i_{\mathbf{m}}},\hfill \\ -{\gamma }_{i_{\mathbf{m}}}{\widehat{x}}_{i_{\mathbf{m}}}\left(\mathbf{m}\right)+b_{i_{\mathbf{m}}}\left({\widehat{x}}_{i_{\mathbf{m}}}\left(\mathbf{m}\right)\right)\hfill & ifi\in \widehat{S}\left(\mathbf{m}\right)\wedge i=i_{\mathbf{m}}\wedge h_{\widehat{S}\left(\mathbf{m}\right)}\left(0\right)>{\gamma }_{i_{\mathbf{m}}}.\hfill \end{array}\right.$$

The assumptions on $b_i$ imply that $-{\gamma }_i{x}_i+b_i\left(x_i\right)$ is a strictly decreasing function of $x_i$. With this we obtain for $\mathbf{m}\ne \mathbf{0}$,

$$g_{i_{\mathbf{m}}}\left(\mathbf{m}\right)=\left\{\begin{array}{cc}{b}_{i_{\mathbf{m}}}\left(0\right)\hfill & if{h}_{\widehat{S}\left(\mathbf{m}\right)}\left(0\right)\le {\gamma }_{i_{\mathbf{m}}},\hfill \\ <b_{i_{\mathbf{m}}}\left(0\right)\hfill & if{h}_{\widehat{S}\left(\mathbf{m}\right)}\left(0\right)>{\gamma }_{i_{\mathbf{m}}}.\hfill \end{array}\right.$$

Note that for $\mathbf{m}\ne \mathbf{0}$ we have $h_{\widehat{S}\left(\mathbf{m}\right)}\left(0\right)={\sum }_{l\in \widehat{S}\left(\mathbf{m}\right)}{b}_l^{\prime }\left(0\right)=b_{i_{\mathbf{m}}}^{\prime }\left(0\right)+{\sum }_{l\in \widehat{S}\left(\mathbf{m}\right)\backslash i_{\mathbf{m}}}{b}_l^{\prime }\left(0\right)$. As $b_{i_{\mathbf{m}}}^{\prime }\left(0\right)<{\gamma }_{i_{\mathbf{m}}}$, this implies

$$h_{\widehat{S}\left(\mathbf{m}\right)}\left(0\right)>{\gamma }_{i_{\mathbf{m}}}\Rightarrow \#\widehat{S}\left(\mathbf{m}\right)\ge 2.$$

Now we are ready to prove the desired result, that for each semi-strict Nash equilibrium ${\mathbf{m}}^{\star }$ it holds that $\widehat{\mathbf{x}}\left({\mathbf{m}}^{\star }\right)=\mathbf{0}$. This we do by contradiction. So suppose ${\mathbf{m}}^{\star }$ is a semi-strict Nash equilibrium ${\mathbf{m}}^{\star }$ with $\widehat{\mathbf{x}}\left({\mathbf{m}}^{\star }\right)\ne \mathbf{0}$. Then ${\mathbf{m}}^{\star }\ne \mathbf{0}$. Fix $i\in N$ with ${\widehat{x}}_i\left({\mathbf{m}}^{\star }\right)>0$. By the above $i=i_{{\mathbf{m}}^{\star }}$ and $h_{\widehat{S}\left({\mathbf{m}}^{\star }\right)}\left(0\right)>{\gamma }_{i_{{\mathbf{m}}^{\star }}}$. Noting that $i_{{\mathbf{m}}^{\star }}\in \widehat{S}\left({\mathbf{m}}^{\star }\right)$ and $T_{i_{{\mathbf{m}}^{\star }}}\left({\mathbf{m}}^{\star }\right)\ne \mathbf{0}$ (as $\#\widehat{S}\left({\mathbf{m}}^{\star }\right)\ge 2$) we obtain $g_{i_{{\mathbf{m}}^{\star }}}^{\prime }\left({\mathbf{m}}^{\star }\right)=g_{i_{{\mathbf{m}}^{\star }}}\left(T_{i_{{\mathbf{m}}^{\star }}}\left(\mathbf{m}\right)\right)-g_{i_{{\mathbf{m}}^{\star }}}\left({\mathbf{m}}^{\star }\right)=b_{i_{{\mathbf{m}}^{\star }}}\left({\widehat{x}}_{i_{T_{i_{{\mathbf{m}}^{\star }}}\left({\mathbf{m}}^{\star }\right)}}\left(T_i\left({\mathbf{m}}^{\star }\right)\right)\right)-g_{i_{{\mathbf{m}}^{\star }}}\left({\mathbf{m}}^{\star }\right)>b_{i_{{\mathbf{m}}^{\star }}}\left({\widehat{x}}_{i_{T_{i_{{\mathbf{m}}^{\star }}}\left({\mathbf{m}}^{\star }\right)}}\left(T_{i_{{\mathbf{m}}^{\star }}}\left({\mathbf{m}}^{\star }\right)\right)\right)-b_{i_{{\mathbf{m}}^{\star }}}\left(0\right)\ge 0$, which is impossible as ${\mathbf{m}}^{\star }$ cannot be a semi-strict equilibrium. ⋄

Example 8. 

Consider the cartel game with a physical game the Cournot-like public good game with common action set $X=\{0,1\}$ and with payoff functions

$$f_i\left(\mathbf{x}\right)=-c{x}_i+{\beta }_i\sum _{l=1}^n{x}_l$$

where $c>1$ and ${\beta }_i\in \{\alpha ,1\}$ with $0<\alpha <1$. We suppose that there does not exist integers $k_1,k_2$ with $\alpha k_1+k_2=c$. Let $N_1$ be the set of players i with ${\beta }_i=\alpha$ and $N_2$ be the set of players i with ${\beta }_i=1$. We refer to the players in $N_t$ as “type t players”.

We obtain for the payoff of meta player C in the coalitonal game ${\mathrm{\Gamma }}_{R_c\left(\mathbf{m}\right)}$ in terms of the physical action profile $\mathbf{x}$

$${\widehat{P}}_C\left(\mathbf{x}\right)=\left\{\begin{array}{cc}-c{x}_i+{\beta }_i\sum _{l\in N}{x}_l\hfill & ifC=\left\{i\right\}withi\in \widehat{S_{\star }}\left(\mathbf{m}\right),\hfill \\ -c\sum _{i\in C}{x}_i+\left(\sum _{i\in C}{\beta }_i\right)(\sum _{l\in C}{x}_l+\sum _{l\notin C}{x}_l)\hfill & ifC=\widehat{S}\left(\mathbf{m}\right).\hfill \end{array}\right.$$

From this follows that the coalitional game ${\mathrm{\Gamma }}_{R_c\left(\mathbf{m}\right)}$ has a unique Nash equilibrium in strictly dominant strategies with effective physical actions

$$\widehat{x_i}\left(\mathbf{m}\right)=\left\{\begin{array}{cc}0\hfill & ifi\in {\widehat{S}}_{\star }\left(\mathbf{m}\right),\hfill \\ 0\hfill & ifi\in \widehat{S}\left(\mathbf{m}\right)\wedge \alpha k_1\left(\mathbf{m}\right)+k_2\left(\mathbf{m}\right)<c,\hfill \\ 1\hfill & ifi\in \widehat{S}\left(\mathbf{m}\right)\wedge \alpha k_1\left(\mathbf{m}\right)+k_2\left(\mathbf{m}\right)>c.\hfill \end{array}\right.$$

where $k_t\left(\mathbf{m}\right)=\#\{i\in \widehat{S}\left(\mathbf{m}\right)|i\in N_t\}(t=1,2)$. Thus the two-stage game is regular and the effective payoffs are given by

$$g_i\left(\mathbf{m}\right)=\left\{\begin{array}{cc}0\hfill & ifi\in {\widehat{S}}_{\star }\left(\mathbf{m}\right)\wedge \alpha k_1\left(\mathbf{m}\right)+k_2\left(\mathbf{m}\right)<c,\hfill \\ {\beta }_i(k_1\left(\mathbf{m}\right)+k_2\left(\mathbf{m}\right))\hfill & ifi\in {\widehat{S}}_{\star }\left(\mathbf{m}\right)\wedge \alpha k_1\left(\mathbf{m}\right)+k_2\left(\mathbf{m}\right)>c,\hfill \\ 0\hfill & ifi\in \widehat{S}\left(\mathbf{m}\right)\wedge \alpha k_1\left(\mathbf{m}\right)+k_2\left(\mathbf{m}\right)<c,\hfill \\ -c+{\beta }_i(k_1\left(\mathbf{m}\right)+k_2\left(\mathbf{m}\right))\hfill & ifi\in \widehat{S}\left(\mathbf{m}\right)\wedge \alpha k_1\left(\mathbf{m}\right)+k_2\left(\mathbf{m}\right)>c.\hfill \end{array}\right.$$

Simply writing $k_1=k_1\left(\mathbf{m}\right)$ and $k_2=k_2\left(\mathbf{m}\right)$ we obtain the following formulas for $g_i^{\prime }\left(\mathbf{m}\right)$.

If $i\in \widehat{S_{\star }}\left(\mathbf{m}\right)$, then

$$g_i^{\prime }\left(\mathbf{m}\right)=\left\{\begin{array}{cc}0\hfill & if \alpha (k_1+1)+k_2<c\wedge \alpha k_1+k_2<c\wedge i\in N_1,\hfill \\ \alpha (1+k_1+k_2)-c\hfill & if \alpha (k_1+1)+k_2>c\wedge \alpha k_1+k_2<c\wedge i\in N_1,\hfill \\ (1+k_1+k_2)-c\hfill & if \alpha k_1+k_2+1>c\wedge \alpha k_1+k_2<c\wedge i\in N_2,\hfill \\ 0\hfill & if \alpha k_1+k_2+1<c\wedge \alpha k_1+k_2<c\wedge i\in N_2,\hfill \\ \alpha -c\hfill & if\alpha k_1+k_2>c\wedge i\in N_1,\hfill \\ 1-c\hfill & if \alpha k_1+k_2>c\wedge i\in N_2.\hfill \end{array}\right.$$

And if $i\in \widehat{S}\left(\mathbf{m}\right)$, then

$$g_i^{\prime }\left(\mathbf{m}\right)=\left\{\begin{array}{cc}0\hfill & if \alpha k_1+k_2<c\wedge i\in N_1,\hfill \\ 0\hfill & if \alpha k_1+k_2<c\wedge i\in N_2,\hfill \\ c-\alpha \hfill & if\alpha (k_1-1)+k_2>c\wedge \alpha k_1+k_2>c\wedge i\in N_1,\hfill \\ c-\alpha (k_1+k_2)\hfill & if\alpha (k_1-1)+k_2<c\wedge \alpha k_1+k_2>c\wedge i\in N_1,\hfill \\ c-1\hfill & if\alpha k_1+k_2-1>c\wedge \alpha k_1+k_2>c\wedge i\in N_2,\hfill \\ c-(k_1+k_2)\hfill & if\alpha k_1+k_2-1<c\wedge \alpha k_1+k_2>c\wedge i\in N_2.\hfill \end{array}\right.$$

The conditions for a semi-strict Nash-equilibrium require that $g_i^{\prime }\left(\mathbf{m}\right)\le 0$ for each cooperator i and $g_i^{\prime }\left(\mathbf{m}\right)<0$ for each non-cooperator i. From the possible cases for $g_i^{\prime }\left(\mathbf{m}\right)$ above, we see that for a non-cooperator $g_i^{\prime }\left(\mathbf{m}\right)<0$ is only possible for the cases $2,5,6$ in the above formula of $g_i^{\prime }\left(\mathbf{m}\right)$. Requiring $g_i^{\prime }\left(\mathbf{m}\right)\le 0$ for each cooperator, we see that this only possible for the cases $1,2,4,6$ in the above formula of $g_i^{\prime }\left(\mathbf{m}\right)$. Combining these conditions (5 and 6 for non-cooperators with 4 and 6 for cooperators) it follows that for a membership profile $\mathbf{m}$ with

$$0\le k_1\left(\mathbf{m}\right)\le \#N_1\wedge 0\le k_2\left(\mathbf{m}\right)\le \#N_2,$$

a sufficient condition for being a semi-strict equilibrium is:

$$c+\alpha >\alpha k_1\left(\mathbf{m}\right)+k_2\left(\mathbf{m}\right)>c\wedge \alpha (k_1\left(\mathbf{m}\right)+k_2\left(\mathbf{m}\right))>c;$$

note that here it holds that $k_1\left(\mathbf{m}\right)\ne 0$. But when looking for semi-strict Nash equilibria with $k_1\left(\mathbf{m}\right)\ne 0$ or $k_2\left(\mathbf{m}\right)\ne 0$ each of the following two conditions separately, are sufficient:

$$c+\alpha >\alpha k_1\left(\mathbf{m}\right)>c\wedge k_2\left(\mathbf{m}\right)=0;$$

$$c+1>k_2\left(\mathbf{m}\right)>c\wedge k_1\left(\mathbf{m}\right)=0.\diamond$$

11. Things to Do (Instead of Conclusions)

“The time has come”, the Walrus said, “To talk of many things: Of shoes—and ships—and sealing-wax—Of cabbages—and kings. And why the sea is boiling hot—And whether pigs have wings.”

(Lewis Carroll)

Although two-stage coalition formation games have been studied already for more than 30 years, their theoretical features have still not been sufficiently investigated. For example, to the best of our knowledge, there is no theoretical result about the existence of an effective equilibrium coalition structure for a regular cartel game that holds for a (sufficiently) abstract Cournot-like physical game in terms of its qualitative properties, although it is the simplest type of a two-stage coalition formation game. Only results for concrete (mostly symmetric) physical games with quite simple payoff functions are available. Therefore, all claims in the literature concerning such situations, for example, on the sizes of the coalitions in equilibrium coalition structures, are only supported by specific examples. In this section we make some suggestions how further progress can be made.

We see three reasons why such full results for two-stage coalition formation games are, presently, not available in the literature:

• A lack of sufficient conditions in terms of the primitives of the physical game for each possible coalitional game to have a unique Nash equilibrium.
• A lack of results concerning the qualitative properties of the effective payoffs in terms of the primitives of the physical game.
• A lack of general results concerning the structure of the Nash equilibrium set of finite games, such as binary action games, that arise as effective games in the theory of the two-stage game approach to coalition formation. In particular, for these effective games, a lack of general results on the validity of the “paradox of cooperation.”

These problems may be the basis for a research program. We discuss them now in more detail.

Problem I. This problem concerns regularity of two stage coalition formation games. Regularity is very fundamental for the two-stage approach.32 One needs sufficient conditions in terms of the primitives of the physical game for the two stage coalition formation game to be regular. As the ineffective coalition structure often (as in a cartel game) is a possible coalition structure, one has to understand in particular the Nash equilibria of the physical game. Let us mention here that, although Cournot-like games and in particular Cournot oligopolies belong to the most studied games in the literature, this problem is, as recent literature (e.g., [35,41,42]) shows, still an active research subject. Of course, for coalitional Nash equilibria the equilibrium uniqueness problem is even more complicated. The only abstract result for equilibrium uniqueness for coalitional equilibria in the literature for Cournot-like games is, as far as we know, Theorem 1, taken form [36].33 It may be good to improve this theorem as follows, along various lines.

1. Theorem 1 provides sufficient conditions for each coalitional game to have a unique Nash equilibrium. However in a cartel game not all coalition structures are possible. So for a cartel game, improvements may be possible if we restrict ourselves to the subset of possible coalitional games.

2. Theorem 1 deals with compact action sets. As various games in the literature deal with situations where each player has ${\mathbb{R}}_{+}$ as action set, variants of Theorem 1(using some “effective compactness condition’) for this situation are needed.

3. The results in Theorem 1 use assumptions that, loosely speaking, make that the actions are strategic substitutes (having downward sloping best replies). These assumptions are popular. However, in [20,43] it is argued that one should also give more attention to situations where the actions are strategic complements (and have upward sloping best replies). This could be helpful for the analysis of climate cooperation when countries have the ability to adapt to climate change.34

Problem II. In order to understand the qualitative properties of the payoffs of the effective game G in terms of the primitives of the physical game $\mathrm{\Gamma }$, one first has to have some insight in the properties of the mapping that assigns the membership action profile (via the unique Nash equilibrium of the coalitional game ${\mathrm{\Gamma }}_{R\left(\mathbf{m}\right)}$) to the effective physical action profile $\mathbf{x}\left(\mathbf{m}\right)$. Various initial, simple results concerning this mapping exist (see [46] and references therein). Next one has to obtain insight into the mapping that assigns to a membership action profile $\mathbf{m}$, for $i\in N$, the effective payoff $g_i\left(\mathbf{m}\right)$.

An intuitive general result (with a quite technical proof) in this context is Theorem 2 in the case of a symmetric physical game and a symmetric membership rule: its first part states that the effective game G is symmetric and its second part specifies further qualitative properties of the effective payoff functions. In the literature, other properties of the effective game, such as super-additivity, are dealt with, but there are no results for these properties in terms of the primitives of the physical game (even if it is symmetric). Upon approaching these problems, we suggest the following.

1. A careful study of the concrete examples in the literature in order to find the crucial assumptions. A good starting point is the case of a cartel game with a symmetric physical game.

2. Providing sufficient conditions in terms of the primitives of the physical game for the effective game to be super-additive.

3. A generalisation of a symmetric game, where players are “identical," is a game where there are two types of players (as in Example 8 in Section 10). It would be very interesting to have a variant of Theorem 2 for such a game.

Problem III. Understanding the set of equilibrium coalition structures of a regular two-stage coalition formation game comes down to understanding of the Nash equilibrium set of its effective game G. This game is a finite game, and due to its construction has a special structure. For example, for the popular case of a cartel game, it is a binary action game. We have seen (Proposition 6, Theorem 6, Proposition 5) that a symmetric binary action game is an aggregative game, an exact potential game, a congestion game and has the deviation property $D_1$. Also (Theorem 5) a binary action game with the deviation property $D_1$ is a generalised ordinal potential game and has a semi-strict Nash equilibrium. Next steps in understanding the equilibrium set of the effective game in case of a regular cartel game could entail the following.

1. Give sufficient conditions (in terms of the primitives of the physical game) for the effective game to have single valued best-reply correspondences. And give sufficient conditions (in terms of the primitives of the physical game) for the effective game to have the deviation property $D_1$.

2. There exists nowadays, a considerable literature about aggregative games (see, for instance, [22,47]). However, in the present article this was not exploited. Especially it seems to be interesting to further study aggregative binary action games which allow for a potential function.

3. The structure of the Nash equilibrium set of the effective game ultimately determines the coalition size of the cooperators in equilibrium coalitional structures. Concerning this size it would be interesting to formalise the so-called paradox of cooperation (see [30] and references therein) and to analyse its claim. The “paradox” was first established by [6] for a public good game with quadratic costs and quadratic benefits in a Stackelberg setting (3-stage game). It refers to the finding that large coalitions are stable when the gains from cooperation are small. If gains are large, only small coalitions will be stable, if any. Later, similar features of stable coalitional equilibria were established in 2-stage games. For example in [48] evidence for the “paradox” was found from a large number of simulations.35 Still the paradox is not well understood, let alone characterised more formally.36

4. In (16) in Example 5, $\overline{x}\left(s\right)$ and $c\left(\overline{x}\left(s\right)\right)$ are strictly increasing functions of s. This implies that $w_0$ is a strictly increasing function of s. A further analysis of (16) would be interesting. Concerning this, we want to note that the cartel game in [49] is a variant of Example 5. The formula (16) applies to this variant: instead of our $c\left(x\right)=\frac{a}{p}{x}^p$,49] deals with $c\left(x\right)=x+\frac{a}{p}{x}^p$. This slight modification leads to completely different equilibrium cartel coalition structures.

Needless to say, our list of problems is not exhaustive.