Autonomous coalitions

Abstract

We consider in this paper solutions for TU-games where it is not assumed that the grand coalition is necessarily the final state of cooperation. Partitions of the grand coalition, or balanced collections together with a system of balancing weights interpreted as a time allocation vector are considered as possible states of cooperation. The former case corresponds to the c-core, while the latter corresponds to the aspiration core or d-core, where in both case, the best configuration (called a maximising collection) is sought. We study maximising collections and characterize them with autonomous coalitions, that is, coalitions for which any solution of the d-core yields a payment for that coalition equal to its worth. In particular we show that the collection of autonomous coalitions is balanced, and that one cannot have at the same time a single possible payment (core element) and a single possible configuration. We also introduce the notion of inescapable coalitions, that is, those present in every maximising collection. We characterize the class of games for which the sets of autonomous coalitions, vital coalitions (in the sense of Shellshear and Sudhölter), and inescapable coalitions coincide, and prove that the set of games having a unique maximising coalition is dense in the set of games.

1 Introduction

The main concern of cooperative game theory is to find a rational way to reward players for their cooperation. The traditional view assumes that eventually the grand coalition will form, so that the problem reduces to a sharing of the worth (benefit) created by the grand coalition among all players. Along this view, one of the most popular solutions of this problem is the core (Gillies 1953, 1959): it is the set of allocations (payoff vectors) such that no coalition receives an amount lower than its own worth (this is called coalitional rationality).

It is well known that the main drawback of the core is that it is empty for a large class of games, namely the nonbalanced games. One way to escape this situation, among the many others which have been studied in the literature, is that we allow for a more general situation of cooperation (the grand coalition may be not the only state of cooperation), or a more general notion of allocation. In the latter case, Grabisch and Miranda (2008) have proposed to share the worth of the grand coalition not only among individual players, but also among all coalitions, up to a certain size k. This is called the k-additive core, and this notion has been further refined in (Gonzalez and Grabisch 2015), leading to the negotiation set. In the former case, there exists natural generalizations of the core, once it is admitted that players may eventually form either disjoint coalitions, i.e., a partition of the grand coalition, or a collection of coalitions which has the property to be balanced: interpreting the balancing weights as amounts of time and assuming that each player has one unit of time to spend [see for example Peleg and Sudhölter (2003)], this unit can be split among different coalitions of this collection. The c-core (Guesnerie and Oddou 1979; Sun et al. 2008) corresponds to the case where players form a partition of the grand coalition, while the d-core (a.k.a. aspiration core) (Bennett 1983; Cross 1967; Albers 1979), which is never empty, corresponds to the more general case where players share their unit of time into different coalitions. It is important to note that the partition, or the balanced collection, which represents the final state of cooperation, is chosen so as to maximise the total worth obtained by cooperation, and for this reason, we call them maximising collections. In the case of a partition, the total worth is simply the sum of the worth of the coalitions in the partition, while for a balanced collection, one need to take into account the time allocated to each coalition: considering a utility linear in time, one simply compute the weighted sum of the worths, where the weights corresponds to the allotted times: see Cesco (2012) for an axiomatization of such kind of solution, and Bejan and Gómez (2012a), who implements the d-core in strong Nash equilibria.

In a sense, the coalitions which are present in the maximising collection representing the final state of cooperation, have a strong power compared to the other ones. Then the following questions arise: can these coalitions be characterized by some property? Is there some relation with other special families of coalitions, like the vital coalitions introduced by Shellshear and Sudhölter (2009)? The aim of this paper is to study this question in depth. One of the main contribution of this paper is that the “strong” coalitions are the autonomous coalitions, introduced in (Gonzalez and Grabisch 2015). An autonomous coalition of a game is defined as a coalition such that any d-core element yields a payment for that coalition equal to its worth. For a balanced game, the grand coalition is always autonomous, but it is not the only one in general (see, e.g., the glove game). We prove that the existence of a nontrivial autonomous coalition implies the existence of a covering of autonomous coalitions, and that any balanced covering of autonomous coalitions is a maximising collection, and vice versa: this completely characterizes the strong coalitions of the final cooperation state. Moreover, the set of all autonomous coalitions is balanced. A noticeable consequence of our results is that for balanced games, it is not possible to have at the same time a unique possible payment and a unique (or even a finite number of) configuration of coalitions achieving this payment: if the core is reduced to a singleton, then the set of possible configurations (balanced collections with time allocation) is a polyhedron, not reduced to a singleton.

A second natural question arises: suppose that there exists more than one maximising collection (this is the case of the glove game). Then it is not possible to know what will be the final state of cooperation. However, in this case, there exist coalitions with a special property: every maximising collection contains them, and for this reason we call them inescapable. We show that inescapable coalitions are vital, in the sense of Shellshear and Sudhölter (2009). Games having a unique maximising collection are of particular interest since one can know without ambiguity the final state of cooperation, and for this reason, we call them games with a single state of cooperation (SSC games). We prove that the set of SSC games is dense in the set of games on a given set of players. As a last important result, we give a sufficient and necessary condition for which the sets of autonomous coalitions, vital coalitions, and inescapable coalitions, are all equal.

The paper is organized as follows: Sect. 2 introduces the necessary background on the c-core, d-core and maximising collections. Section 3 introduces autonomous coalitions and characterizes maximising collections in terms of autonomous coalitions. Section 4 deals with inescapable coalitions and SSC games, and establishes the links between the various types of coalitions introduced (vital, autonomous, inescapable). Section 5 concludes the paper by giving some final remarks, in particular related to the k-additive core.

2 Maximising systems

We start by fixing the notation and introducing basic definitions. For any nonempty finite set A, we denote by $\Pi (A)$ the set of partitions over A and |A| the cardinal of A. Let N denote a fixed finite nonempty set with n members, who will be called agents or players. Coalitions of players are nonempty subsets of N, denoted by capital letters S, T, and so on. Whenever possible, we will omit braces for singletons and pairs, denoting $\{i\},\{i,j\}$ by i, ij respectively, in order to avoid a heavy notation

A transferable utility (TU) game on N is a pair (N, v) where v is a mapping $v : 2^N \rightarrow \mathbb {R}$ satisfying $v(\emptyset )=0$. We denote by $\mathcal {G}(N)$ the set of all games over N. For any coalition S, v(S) represents the worth of S, i.e., what coalition S could earn regardless of other players.

A payoff vector is a vector $x\in \mathbb {R}^n$ that assigns to agent i the payoff $x_i$. For any coalition $T\subset N$, we denote by $v_T$ the restriction of v to $2^T$. Given $x\in \mathbb {R}^n$, and $S\subseteq N$, denote by x(S) the sum $\displaystyle {\sum _{i\in S}x_i}$ with the convention that $x(\emptyset )=0$.

A general payoff vector Gonzalez and Grabisch (2015) is a vector $x\in \mathbb {R}^{2^N\setminus \emptyset }$ that assigns to coalition $S\subseteq N$ the payoff $x_S$.

A balanced system of N is a vector $\lambda =(\lambda _S)_{S\subseteq N}\in [0,1]^{2^N}$ such that

$$\begin{aligned} \sum _{S\subseteq N} \lambda _S \chi ^S=\chi ^N, \end{aligned}$$

where $\chi ^S$ is the characteristic vector of S given by $\chi ^S_i=1$ if $i\in S$ and 0 otherwise. We denote by $\mathbb {B}(N)$ the set of balanced systems over N. For $\lambda \in \mathbb {B}(N)$, we denote by $\mathcal {B}(\lambda )$ the set defined by:

$$\begin{aligned} \mathcal {B}(\lambda )=\{S\subseteq N, \lambda _S>0\}. \end{aligned}$$

A collection $\mathcal {B}\subseteq 2^N$, is called balanced (over N) if there exits a balanced system $\lambda \in \mathbb {B}(N)$ such that $\mathcal {B}=\mathcal {B}(\lambda )$. A balanced collection is minimal if no subcollection of it is balanced. It is well-known that a balanced collection $\mathcal {B}$ is minimal if and only if there is a unique balanced system $\lambda \in \mathbb {B}(N)$ such that $\mathcal {B}=\mathcal {B}(\lambda )$.

Definition 1

For a game $v\in \mathcal {G}(N)$ we define

• (i) The set of preimputations of v as:

  $$\begin{aligned} PI(v):= \{x\in {\mathbb R}^n\mid x(N)=v(N)\}. \end{aligned}$$

• (ii) The set of c-preimputations of v as:

  $$\begin{aligned} \text {c-}PI(v):= \left\{ x\in {\mathbb R}^n\mid x(N)=\max _{\pi \in \Pi (N)}\sum \nolimits _{S\in \pi }v(S)\right\} . \end{aligned}$$

• (iii) The set of d-preimputations of v as:

  $$\begin{aligned} \text {d-}PI(v):= \left\{ x\in {\mathbb R}^n\mid x(N)=\max _{\lambda \in \mathbb {B}(N)}\sum \nolimits _{S\in \mathcal {B}}\lambda _S v(S)\right\} . \end{aligned}$$

• (iv) The set of k-preimputation of v, with $k\in {\mathbb N}$ as:

  $$\begin{aligned} k\text {-}PI(v):=\left\{ (x_S)_{S\subseteq N}\in {\mathbb R}^{2^n}, \, x_S=0 \text { if } |S|>k \text { and } \sum \nolimits _{S\subseteq N}x_S= v(N) \right\} \end{aligned}$$

We remark that in the definition of d-preimputations, we need not write $\sup$ instead of $\max$, since the maximum is attained for some balanced system. Indeed, it is well known that the set $\mathbb {B}(N)$ is a closed convex polytope in ${\mathbb R}^{(2^N)}$, hence compact, and since the function $\sum _{\lambda \in \mathbb {B}(N)}\lambda _Sv(S)$ is a continuous function on this domain, it reaches its maximum at some point (even more, this point will be an extreme point since the function is linear).

In the classical view of preimputations, it is supposed that the grand coalition will form, and its worth is shared among the players. With a c-preimputation, the best partition of the players is sought, in order to maximise the total worth. Now, d-preimputations generalize c-preimputations since partitions are particular balanced collections. More importantly, d-preimputations have an interesting interpretation if one considers $\lambda _S$ for $S\subseteq N$ as an amount of time¹ allocated to S. Assuming that v(S) represents the worth or the production per unit of time, $\lambda _Sv(S)$ is the total worth/production achieved by S. Under this viewpoint, a d-preimputation is a sharing among the players of the total worth which can be achieved by the best arrangement of the players in time.

Definition 2

For any game $v\in \mathcal {G}(N)$ we define

• (i) The core (Gillies 1953) of v as:

  $$\begin{aligned} \mathsf {C}(v):= \{x\in PI(v)\mid x(S)\ge v(S), \forall S\in 2^N\}. \end{aligned}$$

• (ii) The c-core (Guesnerie and Oddou 1979) of v as:

  $$\begin{aligned} \text {c-}\mathsf {C}(v):= \{x\in \text {c-}PI(v)\mid x(S)\ge v(S), \forall S\in 2^N\}. \end{aligned}$$

• (iii) The d-core ² (Albers 1979) of v or aspiration core (Bennett 1983) of v as:

  $$\begin{aligned} \text {d-}\mathsf {C}(v):= \{x\in \text {d-}PI(v)\mid x(S)\ge v(S), \forall S\in 2^N\}.\end{aligned}$$

A game v is totally balanced if, for any $\emptyset \ne S\subseteq N$, $v_S$ is balanced. The totally balanced cover of v denoted by $v^{tb}$ is given by:

$$\begin{aligned} v^{tb}(S)=\max \left\{ \sum \nolimits _{T\subseteq S}\lambda _{T}v(T) \mid \lambda \in \mathbb {B}(S)\right\} \end{aligned}$$

It is well known and easy to prove that $\text {d-}\mathsf {C}(v)=\mathsf {C}(v^{tb})$.

We say that a game v is balanced if $\mathsf {C}(v)$ is nonempty, and c-balanced if $\text {c-}\mathsf {C}(v)$ is nonempty. The following results, proved independently by Bondareva (1963) and Shapley (1967), are well known.

Theorem 1

(The Bondareva–Shapley Theorem, weak form). A necessary and sufficient condition that the core of a game (N, v) is not empty is that for each balanced system $\lambda \in \mathbb {B}(N)$,

$$\begin{aligned} v(N)\ge \sum _{S\subseteq N} \lambda _S v(S). \end{aligned}$$

Theorem 2

(The Bondareva–Shapley Theorem, sharp form). A necessary and sufficient condition that the core of a game (N, v) is not empty is that for each minimal balanced collection $\mathcal {B}$:

$$\begin{aligned} v(N)\ge \sum _{S\subseteq N} \lambda _S v(S) \end{aligned}$$

where $\lambda \in \mathbb {B}(N)$ is the unique balanced system such that $\mathcal {B}(\lambda )=\mathcal {B}$.

Observe that the statement is still true if the minimal balanced collection $\{N\}$ is discarded.

Given a game (N, v) and $t\ge 0$, define its t-expansion $v^t$ by $v^t(S) = v(S)$ for all $S\subset N$, and $v^t(N)=v(N)+t$. Now, to any game (N, v) we assign $\bar{t}(v):=\min \{t\ge 0\mid \mathsf {C}(v)\ne \emptyset \}$, (Bejan and Gómez 2012b) the minimum amount to be given to the grand coalition in order to ensure balancedness.

The following lemma is central in our analysis.

Lemma 1

For any game (N, v), any balanced system $\lambda \in \mathbb {B}(N)$, it holds

$$\begin{aligned} v(N) + \bar{t}(v) \ge \sum _{S\subseteq N}\lambda _Sv(S) \end{aligned}$$

and there exists at least one minimal balanced system for which equality holds.

Any balanced system for which equality holds is called a maximising system.

Proof

Since $v^{\bar{t}(v)}$ is balanced and $\bar{t}(v)\ge 0$, it follows by Theorem 1 that for every balanced system $\lambda$

$$\begin{aligned} v(N) + \bar{t}(v)\ge \sum _{S\in \mathcal {B}}\lambda _Sv^{\bar{t}(v)}(S) \ge \sum _{S\in \mathcal {B}}\lambda _Sv(S). \end{aligned}$$

Now, if v is balanced, then $\bar{t}(v) = 0$, and equality holds taking $\mathcal {B}=\{N\}$. Otherwise, suppose that $\sum _{S\subseteq N}\lambda _Sv(S)<v(N)+\bar{t}(v)$ for every balanced system, and define

$$\begin{aligned} 0<t' = \max _{\lambda \in \mathbb {B}(N)}\sum _{S\subseteq N}\lambda _Sv(S) - v(N) < \bar{t}(v). \end{aligned}$$

(1)

(first inequality comes from the fact that v is not balanced and Theorem 1) Then for every balanced system $\lambda$, $\sum _{S\subseteq N}\lambda _Sv(S)\le v(N) + t'$ holds. We claim that $\sum _{S\subseteq N}\lambda _Sv^{t'}(S)\le v(N) + t'$ holds for every minimal balanced collection, which by the sharp form of Bondareva-Shapley theorem, implies that $v^{t'}$ is balanced, a contradiction with the definition of $\bar{t}(v)$.

Proof of the claim: for the minimal balanced collection $\{N\}$, the inequality trivially holds. Now, any other minimal balanced collection cannot contain N. Therefore

$$\begin{aligned} \sum _{S\subseteq N}\lambda _Sv^{t'}(S) = \sum _{S\subseteq N}\lambda _Sv(S), \end{aligned}$$

which proves the claim by (1).

Finally, consider the following linear program in variables $\lambda _S,S\in 2^N$,

$$\begin{aligned} \text {maximize }&\sum _{S\subseteq N}\lambda _Sv(S)\\ \text {subject to }&\sum _{S\ni i}\lambda _S=1,\quad i\in N\\&\lambda _S\ge 0, \quad S\in 2^N \end{aligned}$$

(note that the feasible domain is the set of balancing weights for all balanced collections) The above reasoning has proved that this linear program has an optimal solution, and the value of the objective function is $v(N)+\bar{t}(v)$. Since there is an optimal solution which is a vertex of the feasible domain, and since it is well known that vertices correspond to minimal balanced collections, the proof is complete. $\square$

The following proposition clarifies the position of the different notions introduced so far.

Proposition 1

For any game v in $\mathcal {G}(N)$, we have:

$$\begin{aligned} \mathsf {C}(v)\subseteq \text {c-}\mathsf {C}(v) \subseteq \text {d-}\mathsf {C}(v)=\mathsf {C}(v^{\bar{t}(v)}), \end{aligned}$$

and equality holds everywhere if and only if v is balanced.

We provide a simple proof of this result. The inclusions where shown by, e.g., Bejan and Gómez (2012b), and the last equality by Cross (1967) and Bennett (1983).

Proof

By Lemma 1, $\max _{\lambda \in \mathbb {B}(N)}\sum _{S\subseteq N}\lambda _Sv(S)=v(N)+\bar{t}(v)$, which proves that any element of the d-core is also an element of $\mathsf {C}(v^{\bar{t}(v)})$ and vice versa. The last equality is therefore established.

To see the second inclusion, suppose that $\text {c-}\mathsf {C}(v)\ne \emptyset$, otherwise the result trivially holds. By definition of $\bar{t}(v)$, any $x\in {\mathbb R}^n$ satisfying $x(S)\ge v(S)$ for every $S\in 2^N$ must satisfy $x(N)\ge v(N)+\bar{t}(v)$. If in addition $x\in \text {c-}\mathsf {C}(v)$ and since a partition is a particular balanced collection, it follows by Lemma 1 that $x(N)= v(N)+\bar{t}(v)$, hence x is an element of the d-core.

Finally, if the core is empty, the first inclusion trivially holds. Otherwise, $\bar{t}(v)=0$, so that $\mathsf {C}(v) = \mathsf {C}(v^{\bar{t}(v)})$ and equality holds throughout. $\square$

From the last equality, it is clear that the d-core is never empty. We see immediately that if the core of v is nonempty then $\bar{t}(v)=0$ and $\lambda \in \mathbb {B}(N)$ defined by $\lambda _N=1$ and $\lambda _S=0$ is a maximising system. If the c-core of v is nonempty, then there exists a partition $\pi \in \Pi (N)$ and a maximising system $\lambda \in \mathbb {B}(N)$ such that $\lambda _S>0 \Leftrightarrow S\in \pi$, and $\bar{t}(v)=\sum _{S\in \pi }\lambda _Sv(S)-v(N).$ Otherwise, there exists a maximising system $\lambda \in \mathbb {B}(N)$ such that $\bar{t}(v)=\sum _{S\subseteq N}\lambda _Sv(S)-v(N).$ In his article about the d-core, Cross (1967) described his solution as a set of stable coalitions with their associated payoffs. Literature focuses essentially on the set of payoffs without considering the properties of the set of corresponding coalitions. Cesco (2012) gives and axiomatizes a new kind of solution which associates to each game not only an amount of the d-core but also the coalitions which permit to reach this amount, that is, the coalitions S such that there exists a maximising system $\lambda ^*\in \mathbb {B}(N)$ which satisfies $\lambda (S)>0$. Bejan and Gómez (2012a) implements the d-core in strong Nash equilibria, corresponding strategies consist of giving an amount of the d-core and an arrangement of the players in time given by a maximising system which permits to reach this amount.

As we have seen, a maximising system can be interpreted as the best arrangement of the players in time. For balanced games, players can stay in the grand coalition, in the case of c-balanced games, each player can stay in the coalition given by the best partition while other games require that some players change coalitions over time. The quantity $\bar{t}(v)$ indicates the deviation from balancedness of a game. It may be interesting to study the behavior of $v\mapsto \bar{t}(v)$ and how the configuration of players over time changes when the game slightly changes.

Denote by $\mathbb {B}_N^*$ the mapping which associates to each game $v\in \mathcal {G}(N)$ the set of maximising systems for v. We can interpret $\mathbb {B}_N^*$ as a correspondence, giving for each game all the possible best configurations of players over time. We will show and characterise in Sect. 4.3 the games which possess a unique best configuration for players, that is, games such that $\mathbb {B}_N^*$ gives a singleton.

Example 1

Let $v\in \mathcal {G}(12)$ defined by $v(1)=v(2)=v(12)=0.$ In this case, $\mathbb {B}_{12}^*(v)=\mathbb {B}(12)$, that is, all the arrangements of the players in time are equivalent, their final production will be always equal to zero. Let us propose two perturbations of the game v. For $\epsilon > 0$, we define $v^+$ and $v^-$ by:

• (i) $v^+(1)=v^+(2)=0$ and $v^+(12)=\epsilon >0$

• (ii) $v^-(1)=v^-(2)=0$ and $v^-(12)=-\epsilon <0$

For those two games, as closed as we want to the original game, there exists only one maximising system, that is, a unique way for players to be arranged in time. The configuration given by $v^+$ provides an incentive to stay in the grand coalition, while $v^-$ encourages all the players to stay alone all the time:

$$\begin{aligned} \mathbb {B}_N^*(v^+)= & {} \{(\lambda _1,\lambda _2,\lambda _{12}), \lambda _1=\lambda _2=0, \text { and }\lambda _{12}=1\}\\ \mathbb {B}_N^*(v^-)= & {} \{(\lambda _1,\lambda _2,\lambda _{12}), \lambda _1=\lambda _2=1, \text { and }\lambda _{12}=0\}. \end{aligned}$$

The previous example shows that $\mathbb {B}_N^*$ is not a lower hemicontinuous correspondence. The following Theorem proves in one shot that $\mathbb {B}_N^*$ is upper hemicontinuous and that $v\rightarrow \bar{t}(v)$ is continuous.

Theorem 3

The function $v\rightarrow \bar{t}(v)$ is continuous and the correspondence $v\rightrightarrows \mathbb {B}_N^*(v)$ is upper hemicontinuous on $\mathcal {G}(N)$.

Proof

Let f be the function defined on $\mathcal {G}(N)\times [0,1]^{2^N} \rightarrow {\mathbb R}$ by $f(v,\lambda )=\sum _{S\subseteq N}\lambda _S v(S)$, and $\mathbb {B}_N$ the constant correspondence which associates to each $v\in \mathcal {G}(N)$ the polytope $\mathbb {B}(N)$. f is continuous, $\mathbb {B}_N$ is a constant correspondence, therefore it is continuous, furthermore since $\mathbb {B}(N)$ is a polytope, $\mathbb {B}_N$ is compact-valued. We can apply immediately the Berge’s maximum theorem (Berge 1959) and conclude that

$$\begin{aligned} v\rightarrow \bar{t}(v):=\max \{f(\lambda ,v)|\lambda \in \Lambda \}-v(N) \end{aligned}$$

is continuous, and

$$\begin{aligned} v\rightrightarrows \mathbb {B}_N^*(v):=\{\lambda \in \mathbb {B}(N)\,|\, \sum _{S\subseteq N}\lambda _S v(S)=v(N)+\bar{t}(v). \end{aligned}$$

is upper hemicontinuous. $\square$

3 Autonomous coalitions

3.1 Definition and first properties

The study of cooperative games shows that the core gives sometimes very controversial solutions, the more classical example being the glove game defined on $N=\{1,2,3\}$ by $v(i)=0, \, \forall i \in N$, $v(12)=v(13)=v(123)=1$ and $v(23)=0$. In this game the core gives the unique payoff: $x_1=1, x_2=x_3=0.$ We see that coalition $\{2,3\}$ earns the same amount if it stays in the grand coalition ($x(\{2,3\})=0$) or out of the grand coalition ($v(\{2,3\})=0$). This coalition has a kind of autonomy regarding to the payoff given by the core, making the game unstable. Therefore, a game may be unstable if there exists a subcoalition S of N such that no payoff vector in the core can ensure a strictly better payoff than what S can achieve by itself, i.e., v(S).

More generally, a coalition is autonomous if it cannot earn more than its own worth with a payoff vector given by the d-core. We give in this section a characterisation of the existence of autonomous subcoalitions in the case of balanced games. We will show that if there exists an autonomous subcoalition, then there necessarily exists a collection of autonomous coalitions covering N. Moreover, the restriction of a game to one of its autonomous coalitions is always balanced, and the covering of autonomous coalitions is always a balanced collection which generates the d-core. We say that a collection $\mathcal {A}$ of coalitions is a covering of N if $\cup _{A\in \mathcal {A}}A=N$.

Definition 3

Let (N, v) be a game. A nonempty coalition $T\subseteq N$ is autonomous for (N, v) if for any payoff vector x of $\mathsf {C}(v^{\bar{t}(v)})$, it holds $x(T) = v(T)$. Similarly, a collection $\mathcal {A}\subseteq 2^N$ is an autonomous covering of N for v if it is a covering of N and $\forall S\in \mathcal {A}$, S is autonomous.

Note that N is an autonomous coalition if and only if v is balanced. Let us define a maximising collection as a collection $\mathcal {B}$ such that there exists a maximising system $\lambda \in \mathbb {B}(N)$ with $\mathcal {B}=\mathcal {B}(\lambda )$. A first noteworthy result is the following.

Lemma 2

Let $v\in \mathcal {G}(N)$ be a game. Then any maximising collection is an autonomous covering of N for v.

Proof

Let $\mathcal {B}$ be a maximising collection and take $x\in \mathsf {C}(v^{\bar{t}(v)})$. There exists a maximising system $\lambda \in \mathbb {B}(N)$ such that $\mathcal {B}=\mathcal {B}(\lambda )$. By positivity of $\lambda _S$, $S\in \mathcal {B}$:

$$\begin{aligned} v(N)+\bar{t}(v) = x(N) = \sum _{S\in \mathcal {B}}\lambda _Sx(S) \ge \sum _{S\in \mathcal {B}}\lambda _Sv(S) = v(N)+\bar{t}(v). \end{aligned}$$

Hence equality holds throughout, forcing $x(S)=v(S)$ for all $S\in \mathcal {B}$. It follows that $\mathcal {B}$ is an autonomous covering. $\square$

Definition 4

(Shellshear and Sudhölter 2009, Gillies 1953). Let S be a coalition of N. S is called vital (w.r.t (S, v)) if there exists $x\in \mathsf {C}(v_S)$ such that $x(T)>v(T)$ for all $T\in 2^S\setminus \{\emptyset , S\}$.

Observe that vital coalitions are strongly linked with the notion of autonomous coalition since it is possible to define alternatively a vital coalition as a coalition which is the unique autonomous coalition of the game $v_S$. If S is vital and if there exists a subcoalition T which is autonomous, then for any members x of the core of $v_S$, we have $x(T)=v(T)$ that contradicts the Definition 4.

Proposition 2

(Gillies 1959). S is vital if and only if for any balanced system $\lambda \in \mathbb {B}(S)$ such that $\mathcal {B}(\lambda )\ne \{S\}$, $\displaystyle {\sum _{T\subseteq S}\lambda _Tv(T)<v(S)}.$

Since the restriction $v_S$ of a game v to a vital coalition is necessarily balanced, the following Theorem contains Proposition 2.

Theorem 4

Let $v\in \mathcal {G}(N)$ be a balanced game. The following propositions are equivalent:

• (i) There exists a coalition $S\subset N$ which is autonomous in (N, v).

• (ii) There exists a collection $\mathcal {A} = \{A_1,\ldots ,A_k\}$, with $A_i\ne N$ for $i=1,\ldots ,k$, which is an autonomous covering of N for v.

• (iii) $\forall \epsilon > 0$, $\mathsf {C}(v^{-\epsilon })=\emptyset$.

• (iv) There exists $\lambda ^*\in \mathbb {B}(N)$ such that $\mathcal {B}(\lambda ^*)\ne \{N\}$ is a minimal collection which is maximising:

  $$\begin{aligned} v(N)=\sum _{S\subseteq N} \lambda ^*_S v(S) \end{aligned}$$

• (v) N is not vital.

Proof

• (ii)$\Rightarrow$(i) is obvious.

• (i)$\Rightarrow$(ii): Let $S\ne N$ be an autonomous coalition. Suppose per contra that there exists $i\in N$ such that for any $T\subset N$, $T\ni i$, there exists $x\in \mathsf {C}(v)$ such that $x(T)>v(T)$. Since S is autonomous, we have $i \not \in S$. For each $T\subset N,T\ni i$, choose $x_T\in \mathsf {C}(v)$ such that $x_T(T)>v(T)$, and consider $x'$ the center of gravity of all these $x_T$. By convexity $x'\in \mathsf {C}(v)$ and satisfies $x'(T)>v(T)$ for all $T\subset N$, $T\ni i$. Define

  $$\begin{aligned} \delta =\min _{T\subset N, T\ni i}(x'(T)-v(T))>0, \end{aligned}$$

  and consider $T^*$ for which the minimum is attained. Take $j\in S$ and define the payoff vector $x^*$ by $x^*_i=x'_i-\delta$, $x^*_j=x'_j+\delta$ and $x^*_k=x'_k$ for $k\in N\setminus \{i,j\}$. By construction, $x^*$ belongs to the core of v, and satisfies $x^*(S)>v(S)$, a contradiction with the assumption on S.

• (ii)$\Rightarrow$(iii): Suppose there exists $\epsilon >0$ such that $\mathsf {C}(v^{-\epsilon })\ne \emptyset$. Take $y\in \mathsf {C}(v^{-\epsilon })$ and nonnegative numbers $\epsilon _1,\ldots ,\epsilon _n$ such that $\sum _{i=1}^n\epsilon _i=\epsilon$. Since $(y_1+\epsilon _1,\ldots ,y_n+\epsilon _n)\in \mathsf {C}(v)$ and $A_j$ is an autonomous coalition, we have for every $A_j\in \mathcal {A}$

  $$\begin{aligned} v(A_j) = \sum _{i\in A_j}(y_i+\epsilon _i)\ge y(A_j)\ge v(A_j), \end{aligned}$$

  implying that equality holds throughout, and therefore $\epsilon _i=0$ for all $i\in A_j$. Since this holds for every $A_j\in \mathcal {A}$ and $\mathcal {A}$ is a covering of N, it follows that $\epsilon _1=\cdots =\epsilon _n=0$, which contradicts $\epsilon >0$.

• (iii)$\Rightarrow$(iv): Let us consider

  $$\begin{aligned} F:=\Big \{\sum _{S\subseteq N} \lambda _S v(S)\mid \mathcal {B}(\lambda ) \text { minimal balanced collection }, \mathcal {B}(\lambda )\ne \{N\}\Big \}. \end{aligned}$$

  Since F is a finite subset of ${\mathbb R}$, there exists $\lambda ^*\in \mathbb {B}(N)$, and $\mathcal {B}(\lambda ^*)\ne \{N\}$ minimal balanced collection attaining the maximum of F, and we may define the game $\bar{v}$ by: $\bar{v}(N)=\sum _{S\subseteq N}\lambda ^*_Sv(S)$, and $\bar{v}(S)=v(S)$ for any $S\subset N$. Observe that

  $$\begin{aligned} \bar{v}(N) = \sum _{S\subseteq N}\lambda ^*_Sv(S)\ge \sum _{S\subseteq N}\lambda _Sv(S)= \sum _{S\subseteq N} \lambda _S \bar{v}(S) \end{aligned}$$

  for every $\lambda \in \mathbb {B}(N)$ such that $\mathcal {B}(\lambda )$ is minimal balanced collection different from $\{N\}$, hence by Theorem 2, $\bar{v}$ is balanced. However v is also balanced, hence by Theorem 2 again, we have $\bar{v}(N)= \sum _{S\subseteq N}\lambda ^*_Sv(S)\le v(N)$. If $\bar{v}(N)<v(N)$, we would have $\mathsf {C}(v^{-\epsilon })\ne \emptyset$ with $\epsilon = v(N)-\bar{v}(N)$, a contradiction with (iii). Hence $\lambda ^*$ satisfies $v(N)=\sum _{S\subseteq N}\lambda ^*_Sv(S)$, and (iv) is proved.

• (iv)$\Rightarrow$(ii): Take $\lambda ^*\in \mathbb {B}(N)$ such that $\mathcal {B}(\lambda ^*)$ is a minimal balanced collection different from $\{N\}$ such that $v(N)=\sum _{S\subseteq N} \lambda ^*_S v(S)$. By Lemma 2, $\mathcal {B}(\lambda ^*)$ is an autonomous covering of N, which does not contain N since $\mathcal {B}(\lambda ^*)$ is minimal and different from $\{N\}$.

• (i)$\Leftrightarrow$(v): it is a direct consequence of the Definition 4. $\square$

The following result, which is a corollary of Theorem 4, states that for balanced games, it is impossible to have an exact information about the configuration of agents over time and an exact information about the payoff vector. The uniqueness of a payoff given by the core can only be achieved through the loss of the uniqueness of the configuration of agents over time while by contraposition, the uniqueness of the configuration of players in time, given by $\mathbb {B}_N^*$, implies that the core is not reduced to a point.

Corollary 1

Let v be a balanced game. If $\mathsf {C}(v)$ is a singleton, then $\mathbb {B}_N^*(v)$ is a polytope not reduced to a point.

Proof

If the polytope $\mathsf {C}(v)$ is a singleton, then its dimension is equal to 0, which implies that at least |N| inequality constraints are equality contraints. Hence, v has at least one autonomous coalition different from N, and according to Theorem 4(iv), there exists $\lambda ^*\in \mathbb {B}^{*}_N(v)$ such that $\mathcal {B}(\lambda ^*)\ne \{N\}$ is a minimal collection. However, $\{N\}$ is also a maximising collection, hence $\mathbb {B}^{*}_N(v)$ is not reduced to a singleton. $\square$

The Theorem 4 can be applied to nonbalanced games as well, by applying it to $v^{\bar{t}(v)}$. Observe then that (iii) is always satisfied, which proves that a nonbalanced game has always an autonomous coalition different from N. Hence we obtain:

Corollary 2

Let $v\in \mathcal {G}(N)$ be a nonbalanced game. Then there exists an autonomous covering $\mathcal {A}=\{A_1,\ldots ,A_k\}$ with $A_i\ne N$, $i=1,\ldots ,k$ of N for v, which is a minimal balanced collection with a balanced system $\lambda$ satisfying

$$\begin{aligned} v(N)+\bar{t}(v) = \sum _{i=1}^k\lambda _{A_i}v(A_i). \end{aligned}$$

Note that this result can be directly deduced from Lemmas 1 and 2.

We have seen in the previous subsection that, for balanced games which satisfy one of the assertion of Theorem 4, or for non-balanced games, there exist some autonomous subcoalitions of N such that payoffs given by the d-core are always equal to the worth of those coalitions. Hence, an autonomous coalition has no incentive to stay in the grand coalition or to accept a payoff given by the d-core, and has an equal interest to play alone from the point of view of coalitional rationality: Note that this point of view is enforced by the fact that the restriction of a game to one of these autonomous coalitions has a nonempty core.

Proposition 3

If S is autonomous, then $\mathsf {C}(v_{S})$ is nonempty.

Proof

If S is autonomous for a game v, then a solution $x \in \mathsf {C}(v^{\bar{t}(v)})$ satisfies $x(T)\ge v(T)$ $\forall T\subseteq S$ and $x(S)=v(S)$. Therefore $(x_i)_{i\in S}\in \mathsf {C}({v_S})$. $\square$

Observe that the Proposition 3 is not an equivalence, otherwise every singleton would be an autonomous coalition.

However, since a player can be in several autonomous coalitions, it is difficult to predict which of them will form. For example, the game v, defined on $N=\{1,2,3\}$ by $v(S)=100$ if $|S|=2$, and 0 otherwise, has three autonomous coalitions which are the pairs of N. Each pair has a rational interest to leave the grand coalition, but, if one of them leaves, the “alone player” receives nothing. No player, in this case, knows if he will be the “alone player”. In this kind of game, each player is in a situation of uncertainty regarding to which autonomous coalition will form. The next result shows that the d-core ensures a payoff as good as one autonomous coalition would receive by leaving the grand coalition, while avoiding the situation of uncertainty described above.

Proposition 4

$$\begin{aligned} \mathsf {C}(v^{\bar{t}(v)})\subseteq \bigcap _{\mathop {S\subseteq N } \limits _{S \text { autonomous coalition of } v}} \widehat{\mathsf {C}(v_S)} \end{aligned}$$

where

$$\begin{aligned}\widehat{\mathsf {C}(v_S)}:=\{x\in {\mathbb R}^n \mid (x_i)_{i\in S}\in \mathsf {C}(v_S)\}. \end{aligned}$$

Proof

For any $x\in \mathsf {C}(v^{\bar{t}(v)})$, we have $x(S)=v(S)$ for any autonomous coalition S. Moreover, every coalition of N satisfies the property: $x(T)\ge v(T)$, so in particular $x(T)\ge v(T)$ for $T\subseteq S$. $\square$

Remark 1

The reverse inclusion is not true. For example, let v be the game over $N=\{1,2,3,4\}$ defined by $v(12)=v(34)=2$, $v(13)=1$ and $v(T)=0$ for all other $T\subseteq N$. Then $(1,1,1,1)\in \text {d-}\mathsf {C}(v)$, $S_1=\{1,2\}$ and $S_2=\{3,4\}$ are the unique autonomous coalitions. Let $x=(0,2,0,2)$, then, for $i=1,2$, $x_{S_i}\in \mathsf {C}(v_{S_i})$. However, $x\not \in \text {d-}\mathsf {C}(v)$.

Lastly, we note a concavity property for the set of autonomous coalitions: If S and T are two autonomous coalitions for (N, v), then we have:

$$\begin{aligned}v(S\cup T)+v(S\cap T)\le v(S)+v(T).\end{aligned}$$

Indeed, let $x\in \mathsf {C}(v^{\bar{t}(v)})$, we have:

$$\begin{aligned}v(S\cup T)\le x(S\cup T)=x(S)+x(T)-x(S\cap T)\le v(S)+v(T)-v(S\cap T).\end{aligned}$$

3.2 Links with maximising collections

Given $v\in \mathcal {G}(N)$, let us study the nature of the set $\mathcal {AU}(v)$ of its autonomous coalitions. We prove in this section that $\mathcal {AU}(v)$ is balanced, as corollary, we will see the equivalence between being a maximising collection and being a balanced system of autonomous coalitions. First we need the following result:

Theorem 5

(Zumsteg 1995, Derks and Peters 1998). A collection $\mathcal {B}\in 2^N$ of nonempty sets is balanced if and only if for every vector $y\in \mathbb {R}^n$ such that $y(N)=0$, either $y(S)=0$ for every $S\in \mathcal {B}$ or there exist $S, T \in \mathcal {B}$ such that $y(S)>0$ and $y(T )<0$.

Theorem 6

For all game v, the collection $\mathcal {AU}(v)$ is balanced.

Proof

Let x be the barycentre of $\text {d-}\mathsf {C}(v)$. Let $y\in {\mathbb R}^n$. Suppose there exists $y\in {\mathbb R}^n$ such that $y(S)\ge 0$ $\forall S\in \mathcal {AU}(v)$ and $y(N)=0$. Since x is the barycentre of $\text {d-}\mathsf {C}(v)$, we have $x(S)=v(S)$ for all $S\in \mathcal {AU}(v)$ and $x(S)>v(S)$ for all $S\in 2^N\setminus \mathcal {AU}(v)$. Let $\epsilon$ be the real number defined by:

$$\begin{aligned} \epsilon :=\min _{S\in 2^N\setminus \mathcal {AU}(v)}x(S)-v(S) \end{aligned}$$

There exists $k\in {\mathbb N}$ such that $\frac{max_{S\in 2^N}|y(S)|}{k}<\epsilon .$ We put $\tilde{y}=\frac{y}{k}$. We have: $x(S)+\tilde{y}(S)\ge v(S)$, $\forall S\in 2^N$; and $x(N)+\tilde{y}(N)=x(N)+\frac{y}{k}(N)=x(N)$. Hence $x+\tilde{y}\in \text {d-}\mathsf {C}(v)$. Therefore, $\forall S\in \mathcal {AU}(v)$, $(x+\tilde{y})(S)=v(S)$ and $(x+\tilde{y})(S)=v(S)+\tilde{y}(S)$. It follows $y(S)=0$ for any autonomous coalition S. By application of Theorem 5, we deduce that $\mathcal {AU}(v)$ is balanced. $\square$

Corollary 3

The set of autonomous coalitions of a game v is a maximising collection of v.

Hence, there is an equivalence between belonging to a maximising collection and being an autonomous covering:

Theorem 7

Let v be a game in $\mathcal {G}(N)$. The following properties are equivalent:

• (i) $\mathcal {F}$ is a maximising collection of v

• (ii) $\mathcal {F}$ is a autonomous balanced covering of v

Proof

It is a corollary of Corollary 3 and Lemma 2. $\square$

4 Inescapability

We have seen that our purpose contained two different aspects: the payoff vector, on the one hand, and the configuration of agents in coalition, on the other hand. A natural question for both consists in defining when we have uniqueness. It is fairly simple to know, by the dimension of the d-core, when a game gives a unique payoff vector:

Proposition 5

The dimension of the d-core of a game v is

$$\begin{aligned} dim(\text {d-}\mathsf {C}(v))=n-rank((|S\cap T|)_{S,T\in \mathcal {AU}(v)}). \end{aligned}$$

Proof

The d-core is a polytope, then its dimension is equal to $n-d$, where d is the size of the largest collection of linearly independent equality constraints. Since the collection of equality constraints corresponds to the collection $\{x(S)=v(S)\}_{S\in \mathcal {AU}(v)}$, it comes that the size of the largest linearly independent set of equality constraints is equal to the rank of $\{\chi ^S\}_{S\in \mathcal {AU}(v)}$. We know that the rank of a family of vector in an inner space is equal to the rank of its corresponding Gram matrix. We can conclude by the observation that $\langle \chi ^S,\chi ^T\rangle = |S\cap T|$.

$\square$

We focus now on the conditions of uniqueness of the configuration of agents.

4.1 Definition and first properties of inescapability

The glove game, defined for example in $N=\{1,2,3\}$ by $v(12)=v(13)=v(123)=1$ and 0 otherwise has four autonomous coalitions: 12, 13, 23, 123. We see that the set of autonomous coalitions, which is by Theorem 7 a maximising collection, contains two disjoint maximising collection: $\mathcal {M}_1=\{12,13,23\}$ and $\mathcal {M}_2=\{123\}$, and since $\mathbb {B}_{123}^*$(v) is a polytope not reduced to a point, there exists infinitely many arrangements of the players in time. Hence, even if 12 is an autonomous coalition, that is a strong coalition, it can be “escapable” for the player 1 or 2 which can prefer to belong to the coalition 123. Hence, among the set of autonomous coalitions, we want to differentiate the ones which are escapable from the ones which are not.

Definition 5

Let v be a game in $\mathcal {G}(N)$. A coalition $S\subseteq N$ is said to be inescapable if every maximising collection contains S. Every autonomous coalition which is not inescapable is called escapable.

Proposition 6

Let v be a game in $\mathcal {G}(N)$. If S is an autonomous coalition for (N, v), then S is inescapable for every game $(N,v_{\epsilon })$ defined, for any $\epsilon >0$, by $v_{\epsilon }(S)=v(S)+\epsilon$ and $v_{\epsilon }(T)=v(T), \, \forall T\ne S$.

Proof

Let S be an autonomous coalition for the game v. By Theorem 7, there exists $\lambda \in \mathbb {B}(N)$ a maximising system such that the maximising collection $\mathcal {B}(\lambda )$ contains S. Let $\gamma$ be a balanced system of N such that $S\not \in \mathcal {B}(\gamma )$. Then

$$\begin{aligned} \sum _{T\subseteq N}\gamma _T v_{\epsilon }(T)&= \sum _{T\subseteq N}\gamma _T v(T)\\&\le \sum _{T\subseteq N}\lambda _T v(T) \\&\quad < \sum _{T\subseteq N}\lambda _T v_{\epsilon }(T). \end{aligned}$$

Therefore if $\gamma$ is a balanced system such that $S\not \in \mathcal {B}(\gamma )$, then $\gamma$ is not a maximising system for $v_{\epsilon }$. Therefore S is inescapable for $v_{\epsilon }$. $\square$

4.2 Games with a single state of cooperation.

Note that if every autonomous coalition of a game is inescapable, then the game has a unique maximising collection.

Definition 6

A game $v\in \mathcal {G}(N)$ is said to be with a single state of cooperation (SSC game) if it has a unique maximising collection.

We denote by $\mathcal {SG}(N)$ the set of SSC games.

Theorem 8

The set of SSC games $\mathcal {SG}(N)$ is dense in $\mathcal {G}(N)$.

Proof

We know that for any game $v\in \mathcal {G}(N)$, there always exists a maximising collection $\mathcal {B}$ of v. Let $\mathcal {O}$ be a smallest subcollection of $\mathcal {B}$ which is maximising. Let $\epsilon >0$ and $u_{\epsilon }$ be the game defined by $u_{\epsilon }(S)=v(S)+\frac{|S|}{|N|}\epsilon$ if $S\in \mathcal {O}$, and $u_{\epsilon }(S)=v(S)$ otherwise. Let $x\in \text {d-}\mathsf {C}(v)$. We have $x(S)=v(S)$ if $S\in \mathcal {O}$. We put, for all $i\in N$, $\tilde{x}_i=x_i+\frac{\epsilon }{|N|}$. We have $\tilde{x}(S)=x(S)+\frac{|S|}{|N|}\epsilon$ which is equal to $v(S)+\frac{|S|}{|N|}\epsilon =u_{\epsilon }(S)$ if $S\in \mathcal {O}$, and it is strictly greater otherwise. Hence $\tilde{x}$ belongs to the d-core of $u_{\epsilon }$ and, by Theorem 7, $\mathcal {O}$ is a maximising collection of $u_{\epsilon }$. Suppose there exists a maximising collection of $u_{\epsilon }$ denoted by $\mathcal {A}$ such that $\mathcal {A}\ne \mathcal {O}$.

Firstly, if there exists $S\in \mathcal {A}$ such that $S\not \in \mathcal {O}$ then, since S is autonomous for $u_{\epsilon }$, $\forall y\in \text {d-}\mathsf {C}(u_{\epsilon })$, $y(S)=u_{\epsilon }(S)$. It is a contradiction with $\tilde{x}\in \text {d-}\mathsf {C}(u_{\epsilon })$ and $\tilde{x}(S)>u_{\epsilon }(S).$

Secondly, assume $\mathcal {A}\subseteq \mathcal {O}$. If there exists $S\in \mathcal {O}$ such that $S\not \in \mathcal {A}$ then, by construction of $\mathcal {O}$, we deduce that $\mathcal {A}$ is not balanced, a contradiction. $\square$

4.3 Links between vitality, autonomy and inescapability

In this section we study the relation between the concepts of autonomous coalitions, vital coalitions, and inescapable coalitions. First, by definition, an inescapable coalition is always autonomous. Hence the set of inescapable coalitions is included in the set of autonomous coalitions, with equality if and only if the game is SSC. Shellshear and Sudhölter (2009) proves that there always exists a maximising collection of vital coalitions³, then by Theorem 7, the intersection between the set of vital coalitions and the set of autonomous coalitions is always nonempty.

Proposition 7

Let v be a game. The set of inescapable coalitions of v is included in the set of vital coalitions of v.

Proof

Let S be an inescapable coalition of (N, v) and $\alpha$ a maximising system. S is autonomous and by Proposition 3, $\mathsf {C}(v_S)\ne \emptyset$. Then for any balanced system $\gamma \in \mathbb {B}(S)$,

$$\begin{aligned} v(S)\ge \sum _{T\subseteq S} \gamma _T v(T). \end{aligned}$$

If S is not vital, then by Proposition 2, there exists a minimal balanced system $\lambda \in \mathbb {B}(S)$, such that $\mathcal {B}(\lambda )\ne \{S\}$ and

$$\begin{aligned} v(S)= \sum _{T\subseteq S} \lambda _T v(T). \end{aligned}$$

Let $\alpha '\in \mathbb {B}(N)$ defined by

$$\begin{aligned} \alpha '=\alpha +\alpha (S)\tilde{\lambda }-\delta _S\alpha (S), \end{aligned}$$

where $\tilde{\lambda }\in \mathbb {B}(N)$ and $\delta \in \{0,1\}^{2^N}$ are given by:

$$\begin{aligned} \tilde{\lambda }(T)=\left\{ \begin{array}{ll} \lambda (T), &{} \text { if }T\subseteq S\\ 0 &{} \text { otherwise}, \end{array} \right. \end{aligned}$$

and

$$\begin{aligned}\delta _S(T)= \left\{ \begin{array}{ll} 1, &{} \text { if }T = S\\ 0 &{} \text { otherwise.} \end{array} \right. \end{aligned}$$

The relation

$$\begin{aligned} \sum _{T\subseteq N}\alpha '(T)v(T)=\sum _{T\subseteq N}\alpha (T)v(T) \end{aligned}$$

is satisfied, then $\alpha '$ is a maximising system. Furthermore, $\lambda \in \mathbb {B}(S)$ is a minimal balanced system satisfying $\mathcal {B}(\lambda )\ne \{S\}$, hence $\lambda (S)=0$, which implies $\alpha '(S)=0$. We conclude that $\mathcal {B}(\alpha ')$ is a maximising collection which does not contain S, implying that S is escapable, a contradiction. $\square$

Remark 2

Let v be the glove game on $N=\{1,2,3\}$ defined by $v(12)=v(13)=v(123)=1$ and $v(S)=0$ otherwise. All singletons of this game are vital, but none of them is autonomous. The coalitions 12,13 and 23 are autonomous and vital but not inescapable.

Let us see now a condition on the game v for which these three notions of coalitions become equivalent.

Definition 7

A game v is without imputations if for all coalition $S\subseteq N$, $|S|>1$ $\displaystyle {\sum _{i\in S}v(i)>v(S)}$.

Proposition 8

A game v is without imputations if and only if the set of autonomous coalitions, the set of inescapable coalitions and the set of vital coalitions of v are equal.

Proof

Claim 1: A game v is without imputations if and only if the singletons are the unique maximising collection. If a game is without imputations, then for any coalition S with at least two players, for any balanced collection $\mathcal {B}(\lambda )$ containing S, the balanced system $\lambda '\in \mathbb {B}(N)$ defined by $\lambda '(T)=\lambda (T)$ if $T\ne S$ and $\lambda '(i)=\lambda (i)+\lambda (S)$ $\forall i\in S$ satisfies:

$$\begin{aligned} \sum _{T\subseteq N}\lambda (T)v(T)&\le \sum _{\mathop {T\subseteq N}\limits _{T\ne S}} \lambda (T)v(T)+\lambda (S)v(S)<\sum _{\mathop {T\subseteq N}\limits _{T\ne S}}\lambda (T)v(T)+\lambda (S)\sum _{i\in S}v(i)\\&=\sum _{T\subseteq N}\lambda '(T)v(T). \end{aligned}$$

Conversely, if the singletons are the unique maximising collection, then if there exists a coalition S with at least two players such that $\displaystyle {\sum _{i\in S}v(i)\le v(S)}$ then:

$$\begin{aligned} \sum _{i\in N}v(i)<v(S)+\sum _{i\in N\setminus S}v(i), \end{aligned}$$

a contradiction.

Suppose v is a game without imputations, by Claim 1, v is SSC, and the singletons are the autonomous coalitions (and also the inescapable coalitions). Furthermore, by Proposition 2 the singletons are the unique vital coalitions. Hence the three types of coalition coincide.

Conversely, if v is a game such that the set of autonomous coalitions, the set of inescapable coalitions and the set of vital coalitions of v are equal, then, since the singletons are always vital, the set of singletons is included into the set of autonomous coalitions. Since the set of singletons is a balanced collection and it is an autonomous covering equal to the set of inescapable coalitions, we deduce that it is the unique maximising collection. Hence, by Claim 1, v is without imputations. $\square$

5 Final remarks

The results of our investigation show that t deep links between autonomous coalitions and the concepts of core, c-core, d-core and also the negotiation set:

• (i) A game v is balanced if and only if N is autonomous, and the set of SSC balanced games is dense over the set of balanced games. In this case, not SSC games corresponds to games which satisfies one of the assertions of Theorem 4;

• (ii) A game v is c-balanced if and only if there exists an autonomous covering which is a partition.

We can also define two other concepts of core with the use of k-preimputations, the first one being the k-additive core (Grabisch and Miranda 2008) defined by:

$$\begin{aligned} \mathsf {C}^k(v):=\left\{ (x_S)_{\mathop {S\subseteq N }\limits _{S\ne \emptyset }}\in k\text {-}PI(v), \quad \forall T\subseteq N \sum _{S\subseteq T}x_S\ge v(T)\right\} , \end{aligned}$$

and the second one being the negotiation set (Gonzalez and Grabisch 2015) defined by:

$$\begin{aligned} \mathsf {I}_1^n(v):= {\mathop {\mathrm{argmin}}\limits _{x\in \mathsf {C}^k(v)}}\, \sum \nolimits _{\mathop {S\subseteq N}\limits _{|S|\ge 2}} |x_S| . \end{aligned}$$

The negotiation set of a game v can be interpreted as the set of k-preimputations which are as close as possible to the set of preimputations, and such that the sum of amounts given to the subsets of a coalition is larger than its worth.

It could be interesting to know what is the “largest” autonomous coalition, that is, how many players an autonomous coalition can contain? The negotiation set gives an answer to this question. The greatest (in the sense of inclusion) autonomous coalitions correspond to coalitions T such that $x_T=0$ for all $x\in \mathsf {I}_1^n(v)$, and any superset of T does not satisfy this property. The economic interpretation is the following: The negociation set maximises what we can give to individuals for ensuring coalitional rationality, and shares the debts only to the coalitions of size larger than 2: if $x\in \mathsf {I}_1^n(v)$, then $\forall S\subseteq N$ such that $|S|\ge 2$, we have $x_S\le 0$. The following theorem ensures that the autonomous coalitions do not pay the debts, that is, a coalition has to pay some debt if and only if it is not contained in some autonomous coalition.

Theorem 9

(Gonzalez and Grabisch 2015). Let v be a game on N, and S be a coalition of N such that $|S|\ge 2$. The following properties are equivalent:

• (i) There exists $T\supseteq S$ such that T is autonomous.

• (ii) $\forall x \in \mathsf {I}_1^n(v), x_S=0$.