2.1 Transferable utility games

In the following, we use a utility-based approach and we assume that ‘everything has a price’: each agent has a utility function that is expressed in currency units. The use of a common currency enables the agents to directly compare alternative outcomes, and it also enables side-payments.

A TU game involves a set of players N and a characteristic function $$\[--><$> v\,:\,{{2}^N} \, \rightarrow \,{\Bbb R} <$><!--$$ that provides a value for each possible coalition or subset of agents. The characteristic function is common knowledge for the entire population, and the value of a coalition depends only on the players present in its coalition. In the TU games, two questions are asked simultaneously: what coalitions should form (i.e. how to partition the set N into coalitions), and how to share the value of a coalition to each of its members.

In general, it is not always possible to satisfy the interests of all players at the same time. Unfortunately, there is no single criterion for characterizing an acceptable solution. After defining the TU games with more details, we will present some desirable criterion for a solution, and then we will present the main solution concepts.

2.1.1 Notations and types of TU games

We consider a set N of n agents. A coalition is a non-empty subset of N. The set N is also known as the grand coalition. The set of all coalitions is $$\[--><$>{\tf="Times_Script" {C}}<$><!--$$ and its cardinality is 2ⁿ. A coalition structure (CS) $$\[--><$>{\scr S}\, = \,\{ {{{\scr C}}_1},\, \cdots \,,{{{\scr C}}_m}\} <$><!--$$ is a partition of N: each set $$\[--><$> {\scr C}{{}_i} <$><!--$$ is a coalition with $$\[--><$> \cup _{{i\, = \,1}}^{m} {{{\scr C}}_i}\, = \,N <$><!--$$ and $$\[--><$> i\, \ne \,j\, \Rightarrow \,{{{\scr C}}_i}\, \cap \,{{{\scr C}}_j}\, = \,\emptyset <$><!--$$ . The set of all CSs is $$\[--><$>{\tf="Times_Script" {S}}<$><!--$$ and its size is of the order O(n ⁿ) and $$\[--><$> \omega ({{n}^{\frac{n}{2}}} ) <$><!--$$ (Sandholm et al., Reference Sandholm, Larson, Andersson, Shehory and Tohmé1999). The characteristic function (or valuation function) $$\[--><$> v\,:\,{{2}^N} \, \rightarrow \,{\Bbb R} <$><!--$$ provides the worth or utility of a coalition. For TU games, it is assumed that the valuation of a coalition $$\[--><$> {\scr C} <$><!--$$ does not depend on the other coalitions present in the population.

Definition 2.1 (TU game). A transferable utility game (TU game) is defined as a pair (N, v) where N is the set of agents, and $$\[--><$> v\,:\,{{2}^N} \, \rightarrow \,{\Bbb R} <$><!--$$ is a characteristic function.

We now describe some types of valuation functions.

Additive (or inessential): $$\[--><$> \forall {{{\scr C}}_1},{{{\scr C}}_2}\, \subseteq \,N\;|\;{{{\scr C}}_1}\, \cap \,{{{\scr C}}_2}\, = \,\emptyset, \,\,v({{{\scr C}}_1}\, \cup \,{{{\scr C}}_2})\, = \,v({{{\scr C}}_1})\, + \,v({{{\scr C}}_2}) <$><!--$$ . When a TU game is additive, $$\[--><$> v({\scr C})\, = \,{{\sum }_{i\, \in \,{\scr C}}}\,v(\{ i\} ) <$><!--$$ , that is, the worth of each coalition is the same whether its members cooperate or not: there is no gain in cooperation or any synergies between coalitions, which explains the alternative name (inessential) used for such games.

Superadditive: $$\[--><$> \forall {{{\scr C}}_1},{{{\scr C}}_2}\, \subseteq \,N\;|\;{{{\scr C}}_1}\, \cap \,{{{\scr C}}_2}\, = \,\emptyset, \,\;v({{{\scr C}}_1}\, \cup \,{{{\scr C}}_2})\,\geq \,v({{{\scr C}}_1})\, + \,v({{{\scr C}}_2}) <$><!--$$ , in other words, any pair of coalitions is best off by merging into one. In such environments, social welfare is maximized by forming the grand coalition and agents have an incentive to form the grand coalition.

Subadditive: $$\[--><$> \forall {{{\scr C}}_1},{{{\scr C}}_2}\, \subseteq \,N\;|\;{{{\scr C}}_1}\, \cap \,{{{\scr C}}_2}\, = \,\emptyset, \;\,v({{{\scr C}}_1}\, \cup \,{{{\scr C}}_2})\,\leq \,v({{{\scr C}}_1})\, + \,v({{{\scr C}}_2}) <$><!--$$ : the agents are best of when they are on their own, that is, cooperation is not desirable.

Convex games: First, let us call $$\[--><$> v({\scr C}\, \cup \,\{ i\} ){\rm{ - }}v({\scr C}) <$><!--$$ the marginal contribution of a player i to coalition $$\[--><$> {\scr C} <$><!--$$ , that is, it is the increase of value of coalition $$\[--><$> {\scr C} <$><!--$$ because of the presence of agent i. We call a valuation convex if for all $$\[--><$> {\scr C}\, \subseteq \,T <$><!--$$ and $$\[--><$> i\, \notin \,T\,v({\scr C}\, \cup \,\{ i\} ){\rm{ - }}v({\scr C})\,\leq \,v(T\, \cup \,\{ i\} ){\rm{ - }}v(T) <$><!--$$ . Therefore, a valuation function is convex when the marginal contribution of each player increases with the size of the coalition he joins. Convex valuation functions are superadditive. We will see that such games have some nice properties (e.g. the core of a convex game is non-empty).

Unconstrained: The valuation function can be superadditive for some coalitions, and subadditive for others: some coalitions should merge when others should remain separated. This is the most difficult and interesting environment.

The valuation function provides a value to a set of agents, not to individual agents. The payoff distribution $$\[--><$> x\, = \,\langle {{x}_1},\, \cdots \,,{{x}_n}\rangle <$><!--$$ describes how the worth of the coalition is shared between the agents, where x_i is the payoff of agent i. We also use the notation $$\[--><$> x({\scr C})\, = \,{{\sum }_{i\, \in \,{\scr C}}}\,{{x}_i} <$><!--$$ . A payoff configuration (PC) is a pair $$\[--><$> ({\scr S},x) <$><!--$$ , where $$\[--><$> {\scr S}\, \in \,{\tf="Times_Script" S} <$><!--$$ is a CS and x is a payoff distribution. $$\[--><$>{\tf="Times_Script" {P} }<$><!--$$ denotes the set of all PCs.

The solution of a TU game (N, v) is a PC: what are the coalitions that will form and how to distribute the worth of the coalitions (Figure 1). We are now going to present some rationality concepts for PCs, which describe good properties that a solution of the coalition formation should have.

Figure 1

What is solving TU games?

2.1.2 Rationality concepts

We now discuss different rationality concepts for payoff distributions, that is, some properties that link the coalition values to the agents’ individual payoff.

Efficiency:x(N) = v(N), the payoff distribution, is an allocation of the whole worth of the grand coalition to all the players. In other words, no utility is lost at the level of the population.

Individual rationality: An agent i will be a member of a coalition only when $$\[--><$> {{x}_i}\,\geq \,v(\{ i\} ) <$><!--$$ , that is, to be part of a coalition, a player must be better off than when it is on its own.

Group rationality: $$\[--><$> \forall {\scr C}\, \subseteq \,N,\;\,x({\scr C})\,\geq \,v({\scr C}) <$><!--$$ , that is, the sum of the payoffs of a coalition should be at least the value of the coalition (there should not be any loss at the level of a coalition).

Pareto optimal payoff distribution: It may be desirable to have a payoff distribution where no agent can improve its payoff without lowering the payoff of another agent. More formally, a payoff distribution x is Pareto optimal iff

$$ \nexists y\, \in \,{{{\Bbb R}}^n} \;|\;\exists i\, \in \,N\;|\;\left\{ {{{y}_i}\, \gt \,{{x}_i}\:\;{\rm{and}}\;\:\forall j\, \ne \,i,\,{{y}_j}\,\geq \,{{x}_j}} \right\}. $$

Two notions will be helpful to discuss some solution concepts. The first is the notion of imputation, which is a payoff distribution with the minimal acceptable constraints.

Definition 2.2 (Imputation). An imputation is a payoff distribution that is efficient and individually rational for all agents. The set of all imputations is denoted by $$\[--><$> {\scr I}mp <$><!--$$ .

An imputation is a solution candidate for a payoff distribution, and can also be used to object a payoff distribution. The second notion is the excess, which measures the improvement due to a change of coalition in a CS.

Definition 2.3 (Excess). The excess related to a coalition $$\[--><$>{\scr C}<$><!--$$ given a payoff distribution x is $$\[--><$> e({\scr C},x)\, = \,v({\scr C})\,{\rm{ - }}\,x({\scr C}) <$><!--$$ .

We can provide two interpretation of the excess. First, it may measure the total amount that the players would gain or lose if they were to form coalition $$\[--><$> {\scr C} <$><!--$$ . When $$\[--><$> e({\scr C},x)\, \gt \,0 <$><!--$$ , it means agents in $$\[--><$> {\scr C} <$><!--$$ would gain some utility by forming $$\[--><$> {\scr C} <$><!--$$ , and hence they have an incentive in doing so. An agent can use the value of the excess of a coalition $$\[--><$> {\scr C} <$><!--$$ as a measure of its strength, that is, if it were to form the coalition $$\[--><$> {\scr C} <$><!--$$ , the agent would be able to generate an additional value of $$\[--><$> e({\scr C},x) <$><!--$$ . Another interpretation is to view the excess as an amount of complaints: when the excess for a coalition is positive, it means that some utility is lost, which is not acceptable! Some stability concepts (the kernel and the nucleolus, see below) are based on the excess of coalitions. The core can also be defined using the notion of excess.

The solution of the coalition formation problem is a PC $$\[--><$> ({\scr S},x) <$><!--$$ . The problems of finding the CS (i.e. finding which coalitions are formed) and of finding a payoff distribution (i.e. sharing the value of the coalitions between the members) cannot generally be separated. In the following, we are going to present different solution concepts proposed in the literature. Each has pros and cons, and none is clearly better than all others.

2.2 The stable set

A first idea is to use the concept of dominance between outcomes from non-cooperative game theory and to apply it to the context of cooperative games.

Let x and y be two payoff distributions. We say that x dominates y iff $$\[--><$> \exists \:T\, \subseteq \,N <$><!--$$ such that $$\[--><$> \forall i\, \in \,T,\,\,\,{{x}_i}\, \gt \,{{y}_i} <$><!--$$ and $$\[--><$> v(T)\,\geq \,x(T) <$><!--$$ and we note $$\[--><$> x\,{\succ}\,y <$><!--$$ . In other words, there exists a coalition T for which each member prefers the allocation x over y, and they can obtain this utility. This dominance relation may not be complete, that is, two payoff distributions may not be comparable. In addition, dominance may not be transitive. One way to characterize fairness is to ensure, for all agents, that there is no other payoff distribution that dominates the current one. The idea of the stable set is to gather together the payoff distributions that are not comparable between each other, and that dominate some payoff distributions outside the stable set. The formal definition follows:

Internal Stability: $$\[--><$> \forall x\, \in \,V,\,\,\nexists\,y\, \in \,V <$><!--$$ such that $$\[--><$> y\,{\succ}\,x <$><!--$$

External Stability: $$\[--><$> \forall z\, \notin \,V,\,\,\exists \,y\, \in \,V <$><!--$$ such that $$\[--><$> y\,{\succ}\,z <$><!--$$ .

In other words, internal stability ensures that no payoff distribution in the stable set dominates any other payoff distribution in the stable set. External stability ensures that for any payoff distribution that is not in the stable set, there exists one in the stable set that dominates it. Hence, the stable set represents a set of acceptable payoff distribution from a global point of view, which is akin to the Pareto Optimality concept of non-cooperative game theory: individual player can prefer some distributions over others in the stable set, but not all the players will have the same preferences. Just as in non-cooperative game theory, Pareto Optimality is accepted as a desirable equilibrium criterion: the stable set can be viewed as a desirable property of a solution. Although in many situations, the stable set is guaranteed to be non-empty, it is not always the case.

2.3 The core

Let us assume that we have a TU game (N, v) and that we want to form the grand coalition. The core, which was first introduced by Gillies (Reference Gillies1953), is the most attractive and natural way to define stability. A payoff distribution is in the core when no set of agents have any incentive to form a different coalition. More formally:

A payoff distribution is in the core when no group of agents has any interest in rejecting it, that is, no group of agents can gain by forming a different coalition. Note that this condition has to be true for all subsets of N, in particular for all singletons, which ensures individual rationality. The core can thus be defined as a payoff structure that satisfies weak linear inequalities. The core is therefore closed and convex. Another way to define the core is in terms of excess:

In other words, a PC is in the core when there exists no coalition that has a positive excess. This definition is attractive as it shows that no coalition has any complaint: each coalition's demand can be granted.

However, there are multiple concerns associated with using the notion of the core. First, the core can be empty: the conflicts captured by the characteristic function cannot satisfy all the players simultaneously. When the core is empty, at least one player is dissatisfied by the utility allocation and therefore blocks the coalition. Let us consider the following example from Kahan and Rapoport (Reference Kahan and Rapoport1984): $$\[--><$> v(\{ A,B\} )\, = \,90,\,\,v(\{ A,C\} )\, = \,80,\,\,v(\{ B,C\} )\, = \,70 <$><!--$$ , and $$\[--><$> v(N)\, = \,120 <$><!--$$ . In this case, the core is the PC where the grand coalition forms and the associated payoff distribution is (50, 40, 30). If v(N) is increased, the size of the core also increases. However, if v(N) decreases, the core becomes empty.

The other issue with adopting the core as stability concept concerns computational complexity. Checking whether a payoff distribution is in the core is $$\[--><$> {\scr N}{\scr P} <$><!--$$ -hard (Conitzer & Sandholm, Reference Conitzer and Sandholm2004). In addition, determining the non-emptiness of the core, even for a superadditive game, is $$\[--><$> {\scr N}{\scr P} <$><!--$$ -hard (Conitzer & Sandholm, Reference Conitzer and Sandholm2003), although there exists a transfer scheme to converge to the core (Wu, Reference Wu1977). In addition, Dieckmann and Schwalbe (Reference Dieckmann and Schwalbe2002) introduce a process that leads to a core allocation in non-superadditive games.

However, some classes of games are guaranteed to have a non-empty core. For example, a convex game has a non-empty core. The set of games with non-empty core has been characterized independently by Bondareva (1963) and Shapley (1967), and the result is known as the Bondareva–Shapley theorem. The idea is to use a linear program (LP) to define the core:

$$(LP)\;\left\{ {\matrix{ {\min \,x(N)} \hfill \cr{{\rm{subject}}\ {\rm{to}}\ x({\scr C})\,\geq \,v({\scr C})\ {\rm{for}}\ \rm{all}}\ {\scr C}\, \subseteq \,N,S\, \ne \,\emptyset } \hfill \\\end{}} \right.$$

The linear constraints correspond to the group rationality conditions. A feasible solution of (LP) is a group rational payoff distribution. For a solution to be member of the core, it has to be efficient as well. The group rationality assumption for the grand coalition guarantees that $$\[--><$> x(N)\,\geq \,v(N) <$><!--$$ . The idea of (LP) is to minimize x(N). Then, when the objective function reaches the value of v(N), it is clear that the core of the game is non-empty. We now introduce some notations needed to state the theorem.

First, we introduce a notation that encodes the members of a coalition in a vector form. The characteristic vector $$\[--><$> {{\chi }_{\scr C}} <$><!--$$ of a coalition $$\[--><$> {\scr C}\, \subseteq \,N <$><!--$$ is vector of $$\[--><$> {{{\Bbb R}}^N} <$><!--$$ defined by $$\[--><$> \chi _{{\scr C}}^{i} \, = \,\left\{ {\matrix{ 1 \hfill & \!\!\!{{\rm{if}}\,i\, \in \,{\scr C}} \hfill \cr0 \hfill & \!\!\!{{\rm{if}}\,i\, \in \,N\backslash {\scr C}} \hfill \\\end{}} \right <$><!--$$ . Next, we introduce a weight function, which is called a map.

A special kind of map, the balanced map, can be thought of a percentage of time spent by the agents in each coalition. For each agent i, the sum of a balanced map for all coalitions that contain i must sum up to one. The following definition formalizes this idea. Note that the condition is an equality between vectors of $$\[--><$> {{{\Bbb R}}^n} <$><!--$$ .

We provide an example of a balanced map for three players in Table 1. Using the definition of balanced map, we are now ready to define a balanced game.

Table 1

Example of a balanced map for n = 3

The definition of a balanced game may appear artificial. However, it appears in the dual of (LP), which can be shown to be

$$(DLP)\;\left\{ {\matrix{ {\max {{\sum }_{{\scr C}\, \subseteq \,N}}\,{{y}_{\scr C}}v({\scr C})} \hfill \cr{{\rm{subject}}\ {\rm{to}}\,\left\{ {\matrix {{{{\sum }_{{\scr C}\, \subseteq \,N}}\,{{y}_{\scr C}}{{\chi }_{\scr C}}\, = \,{{\chi }_N}\,{\rm{and}},} \hfill \cr\ {{{y}_{\scr C}}\,\geq \,0\ {\rm{for}}\ {\rm{all}}\ {\scr C}\, \subseteq \,N,{\scr C}\, \ne \,\emptyset} \hfill \\\end{}} \right.} \hfill \\\end{}} \right.$$

The Bondareva–Shapley theorem is a consequence of the duality theorem of linear programming. This theorem completely characterizes the set of games with a non-empty core. One standard application of the Bondareva–Shapley theorem is to prove that a market game has a non-empty core (see Osborne & Rubinstein, Reference Osborne and Rubinstein1994, section 13.4).

There are few extensions to the concept of the core. As discussed above, one main issue of the core is that it can be empty. In particular, a member of a coalition may block the formation so as to gain a very small payoff. When the cost of building a coalition is considered, it can be argued that it is not worth blocking a coalition for a small utility gain. The strong and weak ɛ-core concepts model this possibility. The constraints defining the strong (respectively the weak) ɛ-core become $$\[--&#x003E;&#x003C;$&#x003E; \forall T\, \subseteq \,N,x(T)\,\geq \,v(T)\,{\rm{ - }}\, \epsi &#x003C;$&#x003E;&#x003C;!--$$ , (respectively $$\[--&#x003E;&#x003C;$&#x003E; \forall T\, \subseteq \,N,x(T)\,\geq \,v(T)\,{\rm{ - }}\,&#x007C;T&#x007C; \,\cdot \epsi &#x003C;$&#x003E;&#x003C;!--$$ ). In the weak ɛ-core, the minimum amount of utility required to block a coalition is per player, whereas for the strong ɛ-core it is a fixed amount. If one picks ɛ large enough, the strong or weak ɛ-core will be non-empty. When decreasing the value of ɛ, there will be a threshold such that for ɛ′ < ɛ the ɛ′-core ceases to be non-empty. This special ɛ-core is then called the least core.

Another way to relax the requirements of the core is to slightly modify the game. Consider the LP and imagine that a feasible solution does not reach the value of the grand coalition. If one could increase sufficiently the value of the grand coalition, the core of the corresponding game would become non-empty. This is the idea of the cost of stability (Bachrach et al., Reference Bachrach, Elkind, Meir, Pasechnik, Zuckerman, Rothe and Rosenschein2009). Given a TU game (N, v) and a value $$\[--&#x003E;&#x003C;$&#x003E; \rDelta \, \in \,{{{\Bbb R}}_ + } &#x003C;$&#x003E;&#x003C;!--$$ , we consider the game (N,v ^Δ) where $$\[--&#x003E;&#x003C;$&#x003E; \forall {\scr C}\, \subset \,N &#x003C;$&#x003E;&#x003C;!--$$ , $$\[--&#x003E;&#x003C;$&#x003E; {{v}^\rDelta } ({\scr C})\, = \,v({\scr C}) &#x003C;$&#x003E;&#x003C;!--$$ , and $$\[--&#x003E;&#x003C;$&#x003E; {{v}^\rDelta } (N)\, = \,v(N)\, + \,\rDelta &#x003C;$&#x003E;&#x003C;!--$$ . The cost of stability is then defined as the smallest Δ such that the core of (N, v ^Δ) is non-empty.

In most traditional work in game theory, the superadditivity of the valuation function is not explicitly stated, but it is implicitly assumed when the core is defined. In particular, this assumption ensures that the grand coalition always emerges. That is one of the reasons why efficiency is defined with respect to the grand coalition. In case of an unconstrained valuation function, the grand coalition may not form, and instead a different CS may emerge. We can define the core for CS, and we borrow the definitions from a study by Chalkiadakis et al. (Reference Chalkiadakis, Elkind, Markakis and Jennings2008), but the definitions are similar to the study by Dieckmann and Schwalbe (Reference Dieckmann and Schwalbe2002) and Sandholm and Lesser (Reference Sandholm and Lesser1997).

A payoff distribution x is efficient with respect to a CS $$\[--&#x003E;&#x003C;$&#x003E; {\scr S} &#x003C;$&#x003E;&#x003C;!--$$ when $$\[--&#x003E;&#x003C;$&#x003E; \forall {\scr C}\, \in \,{\scr S},\,\,{{\sum }_{i\, \in \,{\scr C}}}\,{{x}_j}\, = \,v({\scr C}) &#x003C;$&#x003E;&#x003C;!--$$ . A payoff distribution is an imputation when it is efficient (with respect to the current CS) and individually rational (i.e. $$\[--&#x003E;&#x003C;$&#x003E; \forall i\, \in \,N,\,\,{{x}_i}\,\geq \,v(\{ i\} ) &#x003C;$&#x003E;&#x003C;!--$$ ). The set of all imputations for a CS $$\[--&#x003E;&#x003C;$&#x003E; {\scr S} &#x003C;$&#x003E;&#x003C;!--$$ is denoted by $$\[--&#x003E;&#x003C;$&#x003E; {\scr I}mp({\scr S}) &#x003C;$&#x003E;&#x003C;!--$$ . We can now state the definition of the core:

We now introduce a special type of TU game that will be usefull to define other stability concepts (the nucleolus and the kernel). Aumann and Drèze (Reference Aumann and Drèze1974) propose the definition of a game with CS: in their definition, the CS formed by the agent is fixed (e.g. because of some external constraints such as location). In these types of games, the agents’ goal is not to change the CS, but simply to obtain a stable payoff distribution. We will provide more information for these types of games in Section 2.8.1. For now, the definition of the game and the statement of the definition of the core suffice.

For these types of games the core can be defined as follows:

2.4 The nucleolus

The nucleolus has been introduced by Schmeidler (Reference Schmeidler1969) for games with CS. Let $$\[--&#x003E;&#x003C;$&#x003E; (N,v,{\scr S}) &#x003C;$&#x003E;&#x003C;!--$$ be a TU game with CS and x be a payoff distribution. Let us start the discussion by recalling the definition of the excess given in Section 2.1.2. The excess $$\[--&#x003E;&#x003C;$&#x003E;e({\scr C},x)&#x003C;$&#x003E;&#x003C;!--$$ of coalition $$\[--&#x003E;&#x003C;$&#x003E; {\scr C} &#x003C;$&#x003E;&#x003C;!--$$ at x is the quantity $$\[--&#x003E;&#x003C;$&#x003E; e({\scr C},x)\, = \,v({\scr C})\,{\rm{ - }}\,x({\scr C}) &#x003C;$&#x003E;&#x003C;!--$$ . For the nucleolus, we use the interpretation that the excess is a measure of complaints: when $$\[--&#x003E;&#x003C;$&#x003E; e({\scr C},x) &#x003C;$&#x003E;&#x003C;!--$$ is positive, the members of $$\[--&#x003E;&#x003C;$&#x003E; {\scr C} &#x003C;$&#x003E;&#x003C;!--$$ should complain that some utility is lost or not given to them. The vector of excesses over all the coalitions is one way to evaluate the amount of complaints about a payoff distribution. The goal of the nucleolus is to minimize this in a certain way.

Let us consider the game in Table 2 and we want to compare two payoff distributions x and y. A priori, it is not clear which payoff should be preferred. One solution is to compare the two vectors of complaints using the lexicographical order (it is the order of a dictionary or a phone bookFootnote ¹).

Table 2

A motivating example for the nucleolus

N = {1, 2, 3}, v({i}) = 0 for i ∈ {1, 2, 3} v({1, 2}) = 5, v({1, 3}) = 6, v({2, 3}) = 6, v(N) = 8

Let us consider two payoff vectors $$\[--&#x003E;&#x003C;$&#x003E; x\, = \,\left\langle {3,3,2} \right\rangle &#x003C;$&#x003E;&#x003C;!--$$ and $$\[--&#x003E;&#x003C;$&#x003E; y\, = \,\left\langle {2,3,3} \right\rangle &#x003C;$&#x003E;&#x003C;!--$$ .

Let l be a sequence of m reals. We denote by $$\[--&#x003E;&#x003C;$&#x003E; {{l}^{\blacktriangleright}} &#x003C;$&#x003E;&#x003C;!--$$ the reordering of l in decreasing order. In the example, $$\[--&#x003E;&#x003C;$&#x003E; e(x)\, = \,\left\langle {{\rm{ - }}3,{\rm{ - }}3,{\rm{ - }}2,{\rm{ - }}1,1,1,0} \right\rangle &#x003C;$&#x003E;&#x003C;!--$$ and then $$\[--&#x003E;&#x003C;$&#x003E; e{{(x)}^{\blacktriangleright}} \, = \,\left\langle {1,1,0,{\rm{ - }}1,{\rm{ - }}2,{\rm{ - }}3,{\rm{ - }}3} \right\rangle &#x003C;$&#x003E;&#x003C;!--$$ . The first entry of $$\[--&#x003E;&#x003C;$&#x003E; e{{(x)}^{\blacktriangleright}} &#x003C;$&#x003E;&#x003C;!--$$ is the maximum excess: the agents involved in the corresponding coalition have the most valid complaint. If the maximum excess of x is larger than the one of y, then y should be preferred. If they have the same maximum complaint, one can check the second entry and iterate the reasoning. Hence, we use the lexicographical ordering for comparing two payoff distributions x and y: we say that x is preferred to y when $$\[--&#x003E;&#x003C;$&#x003E; e{{(x)}^{\blacktriangleright}} \,{{\leq }_{lex}}\,e{{(y)}^{\blacktriangleright}} &#x003C;$&#x003E;&#x003C;!--$$ : there is a smaller amount of complaints in x than in y.

A payoff distribution is in the nucleolus when it yields the ‘least problematic’ sequence of complaints according to the lexicographical ordering. The nucleolus of the game is a set of payoff distributions such that the corresponding vector of excess $$\[--&#x003E;&#x003C;$&#x003E; e{{(x)}^{\blacktriangleright}} &#x003C;$&#x003E;&#x003C;!--$$ is minimal.

$$Nu(N,v)\, = \,\left\{ {x\, \in \,{\scr I}mp\;&#x007C;\;\forall y\, \in \,{\scr I}mp\;\;e{{{(y)}}^{\blacktriangleright}} \,{{\geq }_{lex}}\,e{{{(x)}}^{\blacktriangleright}} } \right\}.$$

Recall that the core is a payoff distribution that has no complaints: for all coalitions $$\[--&#x003E;&#x003C;$&#x003E; {\scr C},\,e({\scr C},x)\,\leq \,0 &#x003C;$&#x003E;&#x003C;!--$$ . The nucleolus relaxes the stability requirements of the core, as it is possible that some coalition has a complaint. This relaxation of the core stability requirements is enough to guarantee that not only the nucleolus is non-empty, but also that it contains at most one element. Hence, agents using the nucleolus are guaranteed to find an agreement, and it is unique.

The next property of the nucleolus shows its relation with the core: when the core of a game is non-empty, the nucleolus is included in the core. Hence, the nucleolus can be seen as a refinement of the core. The intuition behind this result is that the core requires no complaint. For a game with non-empty core, some payoff distributions have no complaints; however, the nucleolus, by picking the one with the lowest complaint, will discriminate between these payoffs in the core.

One drawback of the nucleolus is that it is difficult to compute. It can be computed using a sequence of LPs of decreasing dimensions, but the size of each of these groups is exponential. In some special cases, the nucleolus can be computed in polynomial time (Kuipers et al., Reference Kuipers, Faigle and Kern2001; Deng et al., Reference Deng, Fang and Sun2006; Elkind & Pasechnik, Reference Elkind and Pasechnik2009), but in the general case computing the nucleolus is not guaranteed to be polynomial. Only a few papers in the multiagent systems community have used the nucleolus, for example, Yokoo et al. (Reference Yokoo, Conitzer, Sandholm, Ohta and Iwasaki2006).

2.5 The kernel

The kernel is a stability concept that weakens the stability requirements of the core. It was first introduced by Davis and Maschler (Reference Davis and Maschler1965) and it is based on the idea that the strength of an agent is measured by the maximum excess that agent can obtain by forming a new coalition (i.e. a different interpretation of the kernel). An agent can consider a payoff distribution to be acceptable by comparing its own ‘strength’ with the ‘strength’ of other members of its coalition. When both agents have equal strength, they do not have any incentive to leave the coalition. When their strength differs, the weaker agent can make a payment to the stronger agent to balance out their strength and reach some kind of equilibrium. Although its definition is not as intuitive as the core, the kernel exists and is always non-empty. In addition, there is an algorithm that converges to a payoff distribution in the kernel. The guarantee of finding a payoff distribution and the existence of the algorithm make the kernel an attractive stability concept for applications.

2.5.1 Definition of the kernel

We recall that the excess related to coalition $$\[--&#x003E;&#x003C;$&#x003E;{\scr C} &#x003C;$&#x003E;&#x003C;!--$$ for a payoff distribution x is $$\[--&#x003E;&#x003C;$&#x003E; e({\scr C},x)\, = \,v({\scr C})\,{\rm{ - }}\,x({\scr C}) &#x003C;$&#x003E;&#x003C;!--$$ . We saw that a positive excess can be interpreted as an amount of complaint for a coalition. We can also interpret the excess as a potential to generate more utility. Let us consider that the agents are forming a CS $$\[--&#x003E;&#x003C;$&#x003E; {\scr S}\, = \,\{ {{{\scr C}}_1},\, \ldots \,,{{{\scr C}}_k}\} &#x003C;$&#x003E;&#x003C;!--$$ , and let us consider that the excess of a coalition $$\[--&#x003E;&#x003C;$&#x003E; {\scr C}\, \notin \,S &#x003C;$&#x003E;&#x003C;!--$$ is positive. Agent $$\[--&#x003E;&#x003C;$&#x003E; i\, \in \,{\scr C} &#x003C;$&#x003E;&#x003C;!--$$ can view the positive excess as a measure of his strength: if she leaves its current coalition in $$\[--&#x003E;&#x003C;$&#x003E; {\scr S} &#x003C;$&#x003E;&#x003C;!--$$ and form coalition $$\[--&#x003E;&#x003C;$&#x003E;{\scr C} &#x003C;$&#x003E;&#x003C;!--$$ , she has the power to generate some surplus $$\[--&#x003E;&#x003C;$&#x003E; e({\scr C},x) &#x003C;$&#x003E;&#x003C;!--$$ . When two agents want to compare their strength, they can compare the maximum excess of a coalition that contains them, and the kernel is based on this idea.

Definition 2.15 (Maximum surplus). For a TU game (N, v), the maximum surplus s_k,l(x) of agent k over agent l with respect to a payoff distribution x is

$${{s}_{k,l}}(x)\, = \,\mathop {\max }\limits_{{\scr C}\, \subseteq \,N\;&#x007C;\;k\, \in \,{\scr C},\;l\, \notin \,{\scr C}} e({\scr C},x).$$

For two agents k and l, the maximum surplus s_k,l(x) of agent k over agent l with respect to x is the maximum excess from a coalition that includes k but does exclude l. This maximum surplus can be used by agent k to show its strength over agent l: assuming it is positive and that the agent can claim all of it, agent k can argue that it will be better off without agent l, and hence it should be compensated with more utility for staying in the current coalition. When any two agents in a coalition have the same maximum surplus (except for a special case), the agents are said to be in equilibrium. A payoff distribution is in the kernel when all agents are in equilibrium. The formal definitions follow:

Definition 2.16 (kernel). Let $$\[--&#x003E;&#x003C;$&#x003E; (N,v,{\scr S}) &#x003C;$&#x003E;&#x003C;!--$$ be a TU game with coalition structure. The kernel is the set of imputations $$\[--&#x003E;&#x003C;$&#x003E; x\, \in \,{\scr I}mp({\scr S}) &#x003C;$&#x003E;&#x003C;!--$$ such that for every coalition $$\[--&#x003E;&#x003C;$&#x003E; {\scr C}\, \in \,{\scr S} &#x003C;$&#x003E;&#x003C;!--$$ , if $$\[--&#x003E;&#x003C;$&#x003E; (k,l)\, \in \,{{{\scr C}}^2} &#x003C;$&#x003E;&#x003C;!--$$ , $$\[--&#x003E;&#x003C;$&#x003E; k\, \ne \,l &#x003C;$&#x003E;&#x003C;!--$$ , then we have either $$\[--&#x003E;&#x003C;$&#x003E; {{{s}}_{k,l}}(x)\,\geq \,{{{s}}_{l,k}}(x) &#x003C;$&#x003E;&#x003C;!--$$ or $$\[--&#x003E;&#x003C;$&#x003E; {{x}_k}\, = \,v(\{ k\} ) &#x003C;$&#x003E;&#x003C;!--$$ .

$$\[--&#x003E;&#x003C;$&#x003E; {{s}_{k,l}}(x)\, \lt \,{{s}_{l,k}}(x) &#x003C;$&#x003E;&#x003C;!--$$ calls for a transfer of utility from k to l unless it is prevented by individual rationality, that is, by the fact that $$\[--&#x003E;&#x003C;$&#x003E; {{x}_k}\, = \,v(\{ k\} ) &#x003C;$&#x003E;&#x003C;!--$$ .

The kernel and the nucleolus are linked: the following result shows that the nucleolus is included in the kernel. As a consequence, this guarantees that the kernel is non-empty.

Theorem 2.5 The nucleolus is included in the kernel.

Theorem 2.6 When $$\[--&#x003E;&#x003C;$&#x003E; {\scr I}mp\, \ne \,\emptyset &#x003C;$&#x003E;&#x003C;!--$$ , then the kernel is non-empty.

An approximation of the kernel is the ɛ-kernel, where the equality $$\[--&#x003E;&#x003C;$&#x003E; {{s}_{k,l}}(x)\, = \,{{s}_{l,k}}(x) &#x003C;$&#x003E;&#x003C;!--$$ above is replaced by $$\[--&#x003E;&#x003C;$&#x003E; &#x007C;{{s}_{k,l}}(x)\,{\rm{ - }}\,{{s}_{l,k}}(x)&#x007C;\leq \,\epsi &#x003C;$&#x003E;&#x003C;!--$$ . One property of the kernel is that agents with the same maximum surplus, that is, symmetric agents, will receive equal payoff. For ensuring fairness, this property is important.

2.5.2 Computational issues

One method for computing the kernel is the Stearns method (Stearns, Reference Stearns1968). The idea is to build a sequence of side-payments between agents to decrease the difference of surpluses between the agents. At each step of the sequence, the agents with the largest maximum surplus difference exchange utility so as to decrease their surplus: the agent with smaller surplus makes a payment to an agent with higher surplus so as to decrease their surplus difference. After each side-payment, the maximum surplus over all agents decreases. In the limit, the process converges to an element in the kernel. Computing an element in the kernel may require an infinite number of steps as the side-payments can become arbitrarily small, and the use of the ∈-kernel can alleviate this issue. A criteria to terminate Stearns method is proposed by Shehory and Kraus (Reference Shehory and Kraus1999), and we present the corresponding algorithm in Algorithm 1.

Computing a kernel distribution is of exponential complexity. In Algorithm 1, computing the surpluses is expensive, as we need to search through all coalitions that contains a particular agent and does not contain another agent. Note that when a side-payment is carried out, it is necessary to recompute the maximum surpluses. The derivation of the complexity of the Stearns method to compute a payoff in the ɛ-kernel can be found in studies by Klusch and Shehory (Reference Klusch and Shehory1996b) and Shehory and Kraus (Reference Shehory and Kraus1999), and the complexity for one side-payment is $$\[--&#x003E;&#x003C;$&#x003E; O(n \cdot {{2}^n} ) &#x003C;$&#x003E;&#x003C;!--$$ . Of course, the number of side-payments depends on the precision ɛ and on the initial payoff distribution. They derive an upper bound for the number of iterations: converging to an element of the ɛ-kernel requires $$\[--&#x003E;&#x003C;$&#x003E; n\,{\log }_2 \left( {\frac{{{{\delta }_0}}}{{ \in \cdot v(S)}}} \right) &#x003C;$&#x003E;&#x003C;!--$$ , where δ ₀ is the maximum surplus difference in the initial payoff distribution. To derive a polynomial algorithm, the number of coalitions must be bounded. The solution used by Klusch and Shehory (Reference Klusch and Shehory1996b) and Shehory and Kraus (Reference Shehory and Kraus1999) is to only consider coalitions whose size is bounded in the interval K ₁, K ₂. The complexity of the truncated algorithm is $$\[--&#x003E;&#x003C;$&#x003E; O({{n}^2} \cdot {{n}_{coalitions}}) &#x003C;$&#x003E;&#x003C;!--$$ , where n_coalitions is the number of coalitions with a size between K ₁ and K ₂, which is a polynomial of order K ₂.

2.6 Shapley value

So far, the solution concepts we introduced focus on the stability of the payoff distribution. The Shapley value focuses on fairness. It was introduced by Shapley (Reference Shapley1953), who described the notion of fairness in two different ways. The first one is an axiomatic approach: the Shapley value can be defined by a set of axioms, each of them being a desirable property for fairness. The second approach considers a coalition formation process in which agents enter the coalition one by one and obtain the marginal contribution as payoff. This coalition formation process may be unfair because an agent's payoff depends on the joining order. The Shapley value provides fairness by using an average over all possible joining orders. We present these two views on fairness. Then, we will survey computational issues and present some representations that allows for polynomial computation of the Shapley value.

2.6.2 Ordinal marginal contribution

Another interpretation of the Shapley value is based on the notion of ordered marginal contribution. The marginal contribution of an agent i to a coalition $$\[--&#x003E;&#x003C;$&#x003E; {\scr C}\, \subseteq \,N &#x003C;$&#x003E;&#x003C;!--$$ is $$\[--&#x003E;&#x003C;$&#x003E; m{{c}_i}({\scr C})\, = \,v({\scr C}\, \cup \,\{ i\} ){\rm{ - }}v({\scr C}) &#x003C;$&#x003E;&#x003C;!--$$ . Let us consider that a coalition $$\[--&#x003E;&#x003C;$&#x003E; {\scr C} &#x003C;$&#x003E;&#x003C;!--$$ is built incrementally with one agent at a time entering the coalition. Also consider that the payoff of each agent i is its marginal contribution. For example, $$\[--&#x003E;&#x003C;$&#x003E; \left\langle {m{{c}_1}(\emptyset ),m{{c}_2}(\{ 1\} ),m{{c}_3}(\{ 1,2\} )} \right\rangle &#x003C;$&#x003E;&#x003C;!--$$ is an efficient payoff distribution for a game {1, 2, 3}, v). In this case, the value of each agent depends on the order in which the agents enter the coalition, which may not be fair. For example, consider agents that form a coalition to take advantages of price reduction when buying large quantities of a product. Agents that start the coalition may have to spend large setup costs, and agents that come later benefit from the already large number of agents. To alleviate this issue, the Shapley value averages each agents’ payoff over all possible orderings: the value of agent i in coalition $$\[--&#x003E;&#x003C;$&#x003E; {\scr C} &#x003C;$&#x003E;&#x003C;!--$$ is the average marginal value over all possible orders in which the agents may join the coalition.

Let π represent a joining order of the grand coalition N: π can also be viewed as a permutation of 〈1, …, n〉. We write mc(π) the payoff vector where agent i obtains $$\[--&#x003E;&#x003C;$&#x003E; m{{c}_i}(\{ \pi (j)\;&#x007C;\;j\, \lt \,i\} ) &#x003C;$&#x003E;&#x003C;!--$$ . The payoff vector mc(π) is called the marginal vector. Let us denote the set of all permutations of the sequence 〈1, …, n〉 as Π(N). The Shapley values can then be defined as

$$Sh(N,v)\, = \,\frac{{{{\sum }_{\pi \, \in \,\Pi (N)}}\,mc(\pi )}}{{n!}}.$$

We provide an example in Table 3 in which we list all the orders in which the agents can enter the grand coalition. The sum is over all joining orders, that is, over n! terms. When computing the Shapley value for one agent, one can avoid some redundancy by summing over all coalitions and noticing that

Table 3

Example of a computation of Shapley value

• • Members of $$\[--&#x003E;&#x003C;$&#x003E; {\scr C} &#x003C;$&#x003E;&#x003C;!--$$ precede i in $$\[--&#x003E;&#x003C;$&#x003E; &#x007C;{\scr C}&#x007C;! &#x003C;$&#x003E;&#x003C;!--$$ permutations.

• • The remaining members succede i in $$\[--&#x003E;&#x003C;$&#x003E; &#x007C;N\backslash ({\scr C}\, \cup \,\{ i\} )&#x007C;! &#x003C;$&#x003E;&#x003C;!--$$ permutations, that is, in $$\[--&#x003E;&#x003C;$&#x003E; (n\,{\rm{ - }}\,&#x007C;{\scr C}&#x007C;\,{\rm{ - }\,}1)! &#x003C;$&#x003E;&#x003C;!--$$ permutations.

These observations allow us to rewrite the Shapley value for a given agent i as

$$S{{h}_i}(N,v)\, = \,\mathop{\sum}\limits_{{\scr C}\, \subseteq \,N\backslash \{ i\} } \frac{{&#x007C;{\scr C}&#x007C;!(n{\rm{ - }}&#x007C;{\scr C}&#x007C;{\rm{ - }}1)!}}{{n!}}\left( {v({\scr C}\, \cup \,\{ i\} ){\rm{ - }}v({\scr C})} \right).$$

Note that the example from Table 3 also demonstrates that in general the Shapley value is not in the core or in the nucleolus.

Weigthed graph games

Deng and Papadimitriou (Reference Deng and Papadimitriou1994) introduce a class of games called weighted graph games: they define a TU game using an undirected weighted graph $$\[--&#x003E;&#x003C;$&#x003E; {\scr G}\, = \,({\scr V},{\scr W}) &#x003C;$&#x003E;&#x003C;!--$$ where V is the set of vertices and $$\[--&#x003E;&#x003C;$&#x003E; W\,:\,V\, \rightarrow \,V &#x003C;$&#x003E;&#x003C;!--$$ is the set of edges’ weights. For $$\[--&#x003E;&#x003C;$&#x003E; (i,\,j)\, \in \,{{V}^2} &#x003C;$&#x003E;&#x003C;!--$$ , w_ij is the weight of the edge between the vertices i and j. The coalitional game (N, v) is defined as follows:

• • N = V, that is, each agent corresponds to one vertex of the graph.

• • the value of a coalition $$\[--&#x003E;&#x003C;$&#x003E; {\scr C}\, \subseteq \,N &#x003C;$&#x003E;&#x003C;!--$$ is the sum of the weights between any pairs of members of $$\[--&#x003E;&#x003C;$&#x003E; {\scr C} &#x003C;$&#x003E;&#x003C;!--$$ , that is, $$\[--&#x003E;&#x003C;$&#x003E; v({\scr C})\, = \,{{\sum }_{(i,\,\,j)\, \in \,{{{\scr C}}^2} }}\,{{w}_{ij}} &#x003C;$&#x003E;&#x003C;!--$$ .

We provide an example in Figure 2. This representation is succinct as we only need to provide n ² values to represent the entire game. However, it is not a complete representation as some TU games cannot be represented this way (e.g. it is not possible to represent a majority voting game). If we add some restrictions on the weights, we can further guarantee some properties. For example, when all the weights are non-negative, then the game is convex, and then the game is guaranteed to have a non-empty core. One other nice property of this representation is that the Shapley value can be computed in quadratic time:

Figure 2

Example of a graph with five agents

Theorem 2.8 Let (V, W) be a weighted graph game. The Shapley value of an agent i is given by $$\[--&#x003E;&#x003C;$&#x003E; S{{h}_i}(N,v)\, = \,{{\sum}_{(i,\,j)\, \in \,{{N}^2}, i\, \ne \,j}}\,{{w}_{ij}} &#x003C;$&#x003E;&#x003C;!--$$ .

This theorem can be proved using the axioms defining the Shapley value.

2.7 A special class of TU games: voting games

The formation of coalitions is usual in parliaments or assemblies. Therefore, it is interesting to consider a particular class of coalitional games that models voting in an assembly. For example, we can represent an election between two candidates as a voting game where the winning coalitions are the coalitions of size at least equal to half the number of voters. The formal definition follows:

• • the valuation function takes only two values: 1 for the winning coalitions, 0 otherwise.

• • v satisfies unanimity: v(N) = 1

• • v satisfies monotonicity: $$\[--&#x003E;&#x003C;$&#x003E; S\, \subseteq \,T\, \subseteq \,N\, \Rightarrow \,v(S)\,\leq \,v(T) &#x003C;$&#x003E;&#x003C;!--$$ .

Unanimity and monotonicity are natural assumptions in most cases. Unanimity reflects the fact that all agents agree, and hence the coalition should be winning. Monotonicity tells that the addition of agents in the coalition cannot turn a winning coalition into a losing one, which is reasonable for voting: more supporters should not harm the coalition. A first way to represent a voting game is by listing all winning coalitions. Using the monotonicity property, a more succinct representation is to list only the minimal winning coalitions.

We can now see how we formalize some common terms in voting: dictatorship, veto player, and blocking coalition.

Note that with the requirements of simple games, it is possible to have more than one dictator!

It also follows that a veto player is member of every minimal winning coalitions. Another concept is the concept of a blocking coalition: it is a coalition that, on its own, cannot win, but the support of all its members is required to win. Put another way, the members of a blocking coalition do not have the power to win, but they have the power to lose.

The following theorem characterizes the core of simple games.

A variant of a voting game is a weighted voting game where each agent has a weight and a coalition needs to achieve a threshold or quota to be winning. This is a much more compact representation, as we only use to define a vector of weights and a threshold. However, this is not a complete representation, as some voting games cannot be represented as a weighted voting game. The formal definition follows.

• • $$\[--&#x003E;&#x003C;$&#x003E; w\, = \,({{w}_1},{{w}_2}\, \ldots, \,{{w}_n}) &#x003C;$&#x003E;&#x003C;!--$$ is a vector of weights, one for each voter

• • A coalition $$\[--&#x003E;&#x003C;$&#x003E; {\scr C} &#x003C;$&#x003E;&#x003C;!--$$ is winning (i.e. $$\[--&#x003E;&#x003C;$&#x003E; (v({\scr C})\, = \,1 &#x003C;$&#x003E;&#x003C;!--$$ ) iff $$\[--&#x003E;&#x003C;$&#x003E; {{\sum }_{i\, \in \,C}}\,{{w}_i}\,\geq \,q &#x003C;$&#x003E;&#x003C;!--$$ , it is losing otherwise (i.e. $$\[--&#x003E;&#x003C;$&#x003E; (v({\scr C})\, = \,0 &#x003C;$&#x003E;&#x003C;!--$$ )

• • v satisfies monotonicity: $$\[--&#x003E;&#x003C;$&#x003E; S\, \subseteq \,T\, \subseteq \,N\, \Rightarrow \,v(S)\,\leq \,v(T) &#x003C;$&#x003E;&#x003C;!--$$ .

We will note a weighted voting game $$\[--&#x003E;&#x003C;$&#x003E; (N,{{w}_{i \in N}},q) &#x003C;$&#x003E;&#x003C;!--$$ as $$\[--&#x003E;&#x003C;$&#x003E; [q;\;{{w}_1}, \ldots, {{w}_n}] &#x003C;$&#x003E;&#x003C;!--$$ . Note that the weights may not represent the voting power of the player. Let us consider the following weighted voting games:

• • [10; 7, 4, 3, 3, 1]: The set of minimal winning coalitions is {{1, 2}{1, 3}{1, 4}{2, 3, 4}}. Player 5, although it has some weight, is a dummy. Player 2 has a higher weight than player 3 and 4, but it is clear that player 2, 3, and 4 have the same influence.

• • [51; 49, 49, 2]: The set of winning coalitions is {{1, 2}, {1, 3}, {2, 3}}. It seems that the players have symmetric roles, but it is not reflected in their weights.

The European Union uses a combination of weighted voting games (a decision is accepted when it is supported by 55% of Member States, including at least 15 of them, representing at the same time at least 65% of the Union's population).

The examples raise the subject of measuring the voting power of the agents in a voting game. Multiple indices have been proposed to answer these questions, and we now present few of them. One central notion is the notion of pivotal player (also referred to as swing player): we say that a voter i is pivotal for a coalition $$\[--&#x003E;&#x003C;$&#x003E;{\scr C} &#x003C;$&#x003E;&#x003C;!--$$ when it turns it from a losing to a wining coalition, that is, $$\[--&#x003E;&#x003C;$&#x003E; v({\scr C})\, = \,0 &#x003C;$&#x003E;&#x003C;!--$$ and $$\[--&#x003E;&#x003C;$&#x003E; v({\scr C}\, \cup \,\{ i\} )\, = \,1 &#x003C;$&#x003E;&#x003C;!--$$ . Let w be the number of winning coalitions. For a voter i, let η_i be the number of coalitions for which i is pivotal, that is, $$\[--&#x003E;&#x003C;$&#x003E; {{\eta }_i}\, = \,{{\sum }_{S\, \subseteq \,N\backslash \{ i\} }}\,v(S\, \cup \,\{ i\} )\,{\rm{ - }}\,v(S) &#x003C;$&#x003E;&#x003C;!--$$ .

Shapley–Shubik index: It is the Shapley value of the voting game, its interpretation in this context is the percentage of the permutations of all players in which i is pivotal. ‘For each permutation, the pivotal player gets one more point’. Another interpretation is that the index represent the expected marginal utility assuming all joining orders are equally likely.

$${{I}_{SS}}(N,v,i)\, = \,\mathop{\sum}\limits_{{\scr C}\, \subseteq \,N\backslash \{ i\} } \frac{{&#x007C;{\scr C}&#x007C;!(n\,{\rm{ - }}\,&#x007C;C&#x007C;\,{\rm{ - }}\,1)!}}{{n!}}\left( {v({\scr C}\, \cup \,\{ i\} )\,{\rm{ - }}\,v({\scr C})} \right).$$

One issue is that the voters do not trade the value of the coalition, although the decision that the voters vote about is likely to affect the entire population.

Banzhaff index: For each coalition, we determine which agent is a pivotal agent (more than one agent may be pivotal). The raw Banzhaff index of a player i is

$${{\beta }_i}\, = \,\frac{{\mathop{\sum}\limits_{{\scr C}\, \subseteq \,N\backslash \{ i\} } {v({\scr C}\, \cup \,\{ i\} )\,{\rm{ - }}\,v({\scr C})} }}{{{{2}^{n{\rm{ - }}1}} }}.$$

This index corresponds to the expected marginal utility assuming all coalitions are equally likely.

For a simple game (N, v), v(N) = 1 and $$\[--&#x003E;&#x003C;$&#x003E; v(\emptyset )\, = \,0 &#x003C;$&#x003E;&#x003C;!--$$ , at least one player i has a power index β_i ≠ 0. Hence, $$\[--&#x003E;&#x003C;$&#x003E; B\, = \,{{\sum}_{j\, \in \,N}}\,{{\beta }_j}\, \gt \,0 &#x003C;$&#x003E;&#x003C;!--$$ . The normalized Banzhaff index of player i for a simple game (N, v) is defined as

$${{I}_B}(N,v,i)\, = \,\frac{{{{\beta }_i}}}{B}.$$

Coleman index: Coleman defines three indices (Coleman, Reference Coleman1970): the power of the collectivity to act $$\[--&#x003E;&#x003C;$&#x003E; A\, = \,\frac{w}{{{{2}^n} }} &#x003C;$&#x003E;&#x003C;!--$$ (A is the probability of a winning vote occurring); the power to prevent action $$\[--&#x003E;&#x003C;$&#x003E; {{P}_i}\, = \,\frac{{{{\eta }_i}}}{w} &#x003C;$&#x003E;&#x003C;!--$$ (it is the ability of a voter to change the outcome from winning to losing by changing its vote); and the power to initiate action $$\[--&#x003E;&#x003C;$&#x003E; {{I}_i}\, = \,\frac{{{{\eta }_i}}}{{{{2}^n} {\rm{ - }}w}} &#x003C;$&#x003E;&#x003C;!--$$ (it is the ability of a voter to change the outcome from losing to winning by changing its vote, the numerator is the same as in P_i, but the denominator is the number of losing coalitions, that is, the complement of the one of P_i).

We provide in Table 4 an example of computation of the Shapley–Schubik and Banzhaff indices. This example shows that both indices may be different. There is a slight difference in the probability model between the Banzhaf β_i and Coleman's index P_i: in Banzhaf's, all the voters but i vote randomly, whereas in Coleman's the assumption of random voting also applies to the voter i. Hence, the Banzhaf index can be written as $$\[--&#x003E;&#x003C;$&#x003E; {{\beta }_i}\, = \,2{{P}_i} \cdot A\, = \,2{{I}_i} \cdot (1\,{\rm{ - }\,}A) &#x003C;$&#x003E;&#x003C;!--$$ .

Table 4

Shapley-Schubik and the Banzhaff indices for the weighted voting game [7; 4, 3, 2, 1]

The computational complexity of voting and weighted voting games have been studied in studies by Deng and Papadimitriou (Reference Deng and Papadimitriou1994) and Elkind et al. (Reference Elkind, Goldberg, Goldberg and Wooldridge2007). For example, the problem of determining whether the core is empty is polynomial. The argument for this result is the following theorem: the core of a weighted voting game is non-empty iff there exists a veto player. When the core is non-empty, the problem of computing the nucleolus is also polynomial, otherwise it is an $$\[--&#x003E;&#x003C;$&#x003E; {\scr N}{\scr P} &#x003C;$&#x003E;&#x003C;!--$$ -hard problem. The problem of choosing the weights so that they correspond to a given power index has also been tackled in a study by de Keijzer et al. (Reference de Keijzer, Klos and Zhang2010).

2.8 Games with coalition structure and games with a priori unions

We now turn to two special refinements of TU games that are defined using a CS. The first one assumes that a CS has already been formed and the only problem to solve is how to share the value of each coalition. The second one assumes that the grand coalition forms and that members of a coalition in the CS can be represented as one ‘meta’-agent.

2.8.2 Games with a priori unions

So far, a coalition has represented a set of agents that worked on its own. In a CS, the different coalitions are intended to work independently of each other. We can also interpret a coalition to represent a group of agents that is more likely to work together (because of personal or political affinities). The members of a coalition do not mind working with other agents, but they want to be together and negotiate their payoff together, which may improve their bargaining power. This is the idea used in games with a priori unions. Formally, a game with a priori unions is similar to a game with CS: it consists of a triplet $$\[--&#x003E;&#x003C;$&#x003E; (N,v,{\scr S}) &#x003C;$&#x003E;&#x003C;!--$$ where (N, v) is a TU game and S is a CS. However, we assume that the grand coalition forms. The problem is again to define a payoff distribution.

Definition 2.27 (Game with a priori unions). A game with a priori unions is a triplet $$\[--&#x003E;&#x003C;$&#x003E; (N,v,S) &#x003C;$&#x003E;&#x003C;!--$$ , where (N, v) is a TU game, and S is a particular CS. It is assumed that the grand coalition forms.

Owen (Reference Owen1977) proposes a value that is based on the idea of the Shapley value. The agents form the grand coalition by joining one by one. In the Shapley value, all possible joining orders are allowed. In the Owen value, an agent i may join only when the last agent that joined is a member of i's coalition or when the last agents (j ₁, …, j_k) that joined before formed a coalition in S. This is formally captured using the notion of a consistency with a CS:

Definition 2.28 (Consistency with a coalition structure). A permutation π is consistent with a CS S when, for all $$\[--&#x003E;&#x003C;$&#x003E; (i,\,j)\, \in \,{{{\scr C}}^2} &#x003C;$&#x003E;&#x003C;!--$$ , $$\[--&#x003E;&#x003C;$&#x003E; {\scr C}\, \in \,S &#x003C;$&#x003E;&#x003C;!--$$ and $$\[--&#x003E;&#x003C;$&#x003E; l\, \in \,N &#x003C;$&#x003E;&#x003C;!--$$ , $$\[--&#x003E;&#x003C;$&#x003E; \pi (i)\, \lt \,\pi (l)\, \lt \,\pi (j) &#x003C;$&#x003E;&#x003C;!--$$ implies that $$\[--&#x003E;&#x003C;$&#x003E; l\, \in \,{\scr C} &#x003C;$&#x003E;&#x003C;!--$$ .

We denote by $$\[--&#x003E;&#x003C;$&#x003E; {{\Pi }_S}(N) &#x003C;$&#x003E;&#x003C;!--$$ the set of permutations of N that are consistent with the CS S. The number of such permutations is $$\[--&#x003E;&#x003C;$&#x003E; m\prod\nolimits_{{\scr C}\, \in \,S} &#x007C;{\scr C}&#x007C;! &#x003C;$&#x003E;&#x003C;!--$$ where m is the number of coalitions in S. The Owen value is then defined as follows:

Definition 2.29 (Owen value). Given a game with a priori union (N, v, S), the Owen value O_i(N, v, S) of agent i is given by

$${{O}_i}(N,v,S)\, = \,\mathop{\sum}\limits_{\pi \, \in \,{{\Pi }_S}(N)} \frac{{m{c}(\pi )}}{{&#x007C;{{\Pi }_S}(N)&#x007C;}}.$$

In Table 5, we present the example used for the Shapley value and compute the Owen value. The members of the coalition of two agents improve their payoff by forming a union.

Table 5

Example of the computation of an Owen value

2.9 Games with externalities

A traditional assumption in the literature of coalition formation is that the value of a coalition depends solely on the members of that coalition. In particular, it is independent of non-members’ actions. In general, this may not be true: some externalities (positive or negative) can create a dependency between the value of a coalition and the actions of non-members. Sandholm and Lesser (Reference Sandholm and Lesser1997) attribute these externalities to the presence of shared resources (if a coalition uses some resource, they will not be available to other coalitions), or when there are conflicting goals: non-members can move the world farther from a coalition's goal state. Ray and Vohra (Reference Ray and Vohra1999) state that a ‘recipe for generating characteristic functions is a minimax argument’: the value of a coalition $$\[--&#x003E;&#x003C;$&#x003E;{\scr C} &#x003C;$&#x003E;&#x003C;!--$$ is the value $$\[--&#x003E;&#x003C;$&#x003E;{\scr C} &#x003C;$&#x003E;&#x003C;!--$$ gets when the non-members respond optimally so as to minimize the payoff of $$\[--&#x003E;&#x003C;$&#x003E;{\scr C} &#x003C;$&#x003E;&#x003C;!--$$ . This formulation acknowledges that the presence of other coalitions in the population may affect the payoff of the coalition $$\[--&#x003E;&#x003C;$&#x003E;{\scr C} &#x003C;$&#x003E;&#x003C;!--$$ . As in the studies by Hart and Kurz (Reference Hart and Kurz1983) and Ray and Vohra (Reference Ray and Vohra1999), we can study the interactions between different coalitions in the population: decisions about joining forces or splitting a coalition can depend on the way the competitors are organized. For example, when different companies are competing for the same market niche, a small company might survive against a competition of multiple similar individual small companies. However, if some of these small companies form a viable coalition, the competition significantly changes: the other small companies may now decide to form another coalition to be able to successfully compete against the existing coalition. Another such example is a bargaining situation where agents need to negotiate over the same issues: when agents form a coalition, they can have a better bargaining position, as they have more leverage, and because the other party needs to convince all the members of the coalition. If the other parties also form coalition, the bargaining power of the first coalition may decrease.

Two main types of games with externalities are described in the literature, both are represented by a pair (N, v), but the valuation function has a different signature.

Games in partition function form: (Thrall & Lucas, Reference Thrall and Lucas1963): $$\[--&#x003E;&#x003C;$&#x003E; v\,:\,{{2}^N} \times {\tf=&#x0022;Times_Script&#x0022;{S}}\, \rightarrow \,{\Bbb R} &#x003C;$&#x003E;&#x003C;!--$$ . This is an extension of the valuation function of a TU game by providing the value of a coalition, given the current coalition structure (note that $$\[--&#x003E;&#x003C;$&#x003E; v({\scr C},{\scr S}) &#x003C;$&#x003E;&#x003C;!--$$ is meaningful when $$\[--&#x003E;&#x003C;$&#x003E; {\scr C}\, \in \,{\scr S} &#x003C;$&#x003E;&#x003C;!--$$ ).

Games with valuations: $$\[--&#x003E;&#x003C;$&#x003E; v\,:\,N\,\times \,{\tf=&#x0022;Times_Script&#x0022;{S}}\, \rightarrow \,{\Bbb R} &#x003C;$&#x003E;&#x003C;!--$$ . In these type of games, the valuation function directly assigns a value to an agent given a coalition structure. One possible interpretation is that the problem of sharing the value of a coalition to the members has already been solved.

The definitions of superadditivity, subadditivity, and monotonicity can be adapted to games in partition functions (Bloch, Reference Bloch2003). As an example, we provide the definition for superadditivity.

The partition function may also have some regularities when two coalitions merge: either they always have a positive effect on the other coalition, or they always have a negative one. More precisely, a partition function exhibits positive spillovers when for any CS $$\[--&#x003E;&#x003C;$&#x003E;{\scr S}&#x003C;$&#x003E;&#x003C;!--$$ and any coalitions $$\[--&#x003E;&#x003C;$&#x003E; {{{\scr C}}_1} &#x003C;$&#x003E;&#x003C;!--$$ and $$\[--&#x003E;&#x003C;$&#x003E; {{{\scr C}}_2} &#x003C;$&#x003E;&#x003C;!--$$ in $$\[--&#x003E;&#x003C;$&#x003E; {\scr S} &#x003C;$&#x003E;&#x003C;!--$$ , we have $$\[--&#x003E;&#x003C;$&#x003E; v({\scr C},{\scr S}\,\backslash\, \{ {{{\scr C}}_1},{{{\scr C}}_2}\} \, \cup \,\{ {{{\scr C}}_1}\, \cup \,{{{\scr C}}_2}\} )\,\geq \,v({\scr C},{\scr S}) &#x003C;$&#x003E;&#x003C;!--$$ for all coalitions $$\[--&#x003E;&#x003C;$&#x003E; {\scr C}\, \ne \,{{{\scr C}}_1},{{{\scr C}}_2} &#x003C;$&#x003E;&#x003C;!--$$ in $$\[--&#x003E;&#x003C;$&#x003E; {\scr S} &#x003C;$&#x003E;&#x003C;!--$$ .

These regularities can be exploited when searching for an optimal CS. As shown by Michalak et al. (Reference Michalak, Dowell, McBurney and Wooldridge2008), it is possible that the grand coalition is not the CS with maximal social welfare for a superadditive partition function. If the partition function is both superadditive and exhibits a positive spillover, then the grand coalition has maximum social welfare. The similar property holds for subadditive partition function with negative spillovers.

We now turn to considering solution concepts for such games. The issue of extending the Shapley value has a rich literature in game theory. We want the Shapley value to represent an average marginal contribution, but there is a debate over which set of coalition structures. Michalak et al. (Reference Michalak, Rahwan, Marciniak, Szamotulski and Jennings2010) provide references on different solutions and present three solutions in more details.

Airiau and Sen (Reference Airiau and Sen2010) considers the issue of the stability of the optimal CS and discusses a possible way to extend the kernel for partition function games. Airiau and Sen (Reference Airiau and Sen2009) consider coalition formation in the context of games with valuations and propose a solution for myopic agents (an agent will join a coalition only when it is beneficial, without considering long-term effect).

Michalak et al. (Reference Michalak, Rahwan, Sroka, Dowell, Wooldridge, McBurney and Jennings2009) tackle the problem of representing such games and propose three different representations that depend on the interpretation of the externalities. The first representation considers the value of a coalition in a CS: the value of a coalition can be decomposed into one term that is free of externality and another term that models the sum of the uncertainty because of the formation of the other coalitions. The two other representations consider that the contribution of a coalition in a CS: either by providing the mutual influence of any two coalitions in a CS (outward operational externalities) or by providing the influence of all the other coalitions on a given coalition (inward operational externalities). Michalak et al. (Reference Michalak, Rahwan, Marciniak, Szamotulski and Jennings2010) and Michalak et al. (Reference Michalak, Rahwan, Marciniak, Szamotulski, McBurney and Jennings2010) extend the concept of MC-nets to games with partition function.

2.10 Non-transferable utility games

An underlying assumption behind a TU game is that agents have a common scale to measure the worth of a coalition. Such a scale may not exist in every situation, which leads to the study of games where the utility is non-transferable (NTU games). We start by introducing a particular type of NTU games called Hedonic games.

In these games, agents have preferences over coalitions: each agent knows whether it prefers to be in company of some agents rather than others. An agent may enjoy more the company of members of $$\[--&#x003E;&#x003C;$&#x003E; {{{\scr C}}_1} &#x003C;$&#x003E;&#x003C;!--$$ over members of $$\[--&#x003E;&#x003C;$&#x003E; {{{\scr C}}_2} &#x003C;$&#x003E;&#x003C;!--$$ , but it cannot tell by how much it prefers $$\[--&#x003E;&#x003C;$&#x003E; {{{\scr C}}_2} &#x003C;$&#x003E;&#x003C;!--$$ over $$\[--&#x003E;&#x003C;$&#x003E; {{{\scr C}}_2} &#x003C;$&#x003E;&#x003C;!--$$ . Consequently, an agent cannot be compensated when it is not part of its favorite coalition. More formally, let N be a set of agents and $$\[--&#x003E;&#x003C;$&#x003E;{{{\scr N}}_i} &#x003C;$&#x003E;&#x003C;!--$$ be the set of coalitions that contain agent i, that is, $$\[--&#x003E;&#x003C;$&#x003E; {{{\scr N}}_i}\, = \,\{ {\scr C}\, \cup \,\{ i\} \;&#x007C;\;{\scr C}\, \subseteq \,N\backslash \{ i\} \} &#x003C;$&#x003E;&#x003C;!--$$ . For a CS $$\[--&#x003E;&#x003C;$&#x003E;{\scr S} &#x003C;$&#x003E;&#x003C;!--$$ , we will note $$\[--&#x003E;&#x003C;$&#x003E;{\scr S}(i) &#x003C;$&#x003E;&#x003C;!--$$ the coalition in $$\[--&#x003E;&#x003C;$&#x003E;{\scr S} &#x003C;$&#x003E;&#x003C;!--$$ containing agent i.

• • N is the set of agents

• • $$\[--&#x003E;&#x003C;$&#x003E; {{{\succeq}}_i}\, \subseteq \,2_{i}^{{\scr N}} \,\times \,2_{i}^{{\scr N}} &#x003C;$&#x003E;&#x003C;!--$$ is a complete, reflexive, and transitive preference relation for agent i, with the interpretation that if $$\[--&#x003E;&#x003C;$&#x003E;S\,{{{\succeq}}_i}\,T&#x003C;$&#x003E;&#x003C;!--$$ , agent i prefers coalition T at most as much as coalition S.

The notion of core can be easily extended for these types of games. Weaker versions of stability can also be defined using the current CS formed, and we now give the definition of stability concepts adapted from a study by Bogomolnaia and Jackson (Reference Bogomolnaia and Jackson2002).

Core Stability: A CS $$\[--&#x003E;&#x003C;$&#x003E;{\scr S} &#x003C;$&#x003E;&#x003C;!--$$ is core-stable iff $$\[--&#x003E;&#x003C;$&#x003E; {\nexists}\,{\scr C}\, \subseteq \,N\;&#x007C;\;\forall i\, \in \,{\scr C},{\scr C}\,{{{\succ}}_i}\,{\scr S}(i) &#x003C;$&#x003E;&#x003C;!--$$ .

Nash Stability: A CS $$\[--&#x003E;&#x003C;$&#x003E;{\scr S} &#x003C;$&#x003E;&#x003C;!--$$ is Nash-stable iff $$\[--&#x003E;&#x003C;$&#x003E; (\forall i\, \in \,N)\;(\forall {\scr C}\, \in \,{\scr S}\, \cup \{ \emptyset \} )\;{\scr S}(i){{{\succsim}}_i}\,{\scr C}\, \cup \,\{ i\} &#x003C;$&#x003E;&#x003C;!--$$ . No player would like to join any other coalition in $$\[--&#x003E;&#x003C;$&#x003E;{\scr S}&#x003C;$&#x003E;&#x003C;!--$$ assuming the other coalitions did not change.

Individual Stability: A CS $$\[--&#x003E;&#x003C;$&#x003E;{\scr S} &#x003C;$&#x003E;&#x003C;!--$$ is individually stable iff $$\[--&#x003E;&#x003C;$&#x003E; ({\nexists}i\, \in \,N)\;({\nexists}{\scr C}\, \in \,{\scr S}\, \cup \,\{ \emptyset \} )\;&#x007C;\;({\scr C}\, \cup \,\{ i\} \,{{{\succ}}_i}\,{\scr S}(i))&#x003C;$&#x003E;&#x003C;!--$$ and $$\[--&#x003E;&#x003C;$&#x003E;(\forall j\, \in \,{\scr C},\,{\scr C}\, \cup \,\{ i\} \,{{{\succsim}}_j}\,{\scr C}) &#x003C;$&#x003E;&#x003C;!--$$ . No player can move to another coalition that it prefers without making some members of that coalition unhappy.

Contractually Individual Stability: A CS $$\[--&#x003E;&#x003C;$&#x003E;{\scr S} &#x003C;$&#x003E;&#x003C;!--$$ is contractually individually stable iff $$\[--&#x003E;&#x003C;$&#x003E;{ ({\nexists}\,i\, \in \,N)\;({\nexists}\,{\scr C}\, \in &#x003C;$&#x003E;&#x003C;!--$$ $$\[--&#x003E;&#x003C;$&#x003E;\quad\quad{\scr S} \,\cup \,\{ \emptyset \} )\,&#x007C;\,({\scr C}\, \cup \,\{ i\} \,{{{\succ}}_i}\,{\scr S}(i))\;and \ (\forall j \in {\scr C},\:{\scr C}\, \cup \,\{ i\} \,{{{\succsim}}_j}\,{\scr C})\;and\;(\forall j \:\in \:{\scr S}(i)\,\backslash \:\{ i\}, \,{\scr S}(i)\:\backslash \{ i\} \,{{{\succsim}}_j}\,{\scr S}(i)) \\ \end{} &#x003C;$$&#x003E;&#x003C;[[$$ . No player can move to a coalition it prefers so that the members of the coalition it leaves and it joins are better off.

If a CS is core-stable, no subset of agents has incentive to leave its respective coalition to form a new one; this is the classic definition of the core in the context of hedonic games. In the other stability solution concepts, the possible deviations feature a single agent i that leaves its current coalition $$\[--&#x003E;&#x003C;$&#x003E; {{{\scr C}}_1} &#x003C;$&#x003E;&#x003C;!--$$ to join a different existing coalition $$\[--&#x003E;&#x003C;$&#x003E; {{{\scr C}}_2} &#x003C;$&#x003E;&#x003C;!--$$ or to form a singleton coalition. The difference between the three notions is the behavior of the members of $$\[--&#x003E;&#x003C;$&#x003E; {{{\scr C}}_1} &#x003C;$&#x003E;&#x003C;!--$$ and $$\[--&#x003E;&#x003C;$&#x003E; {{{\scr C}}_2} &#x003C;$&#x003E;&#x003C;!--$$ . For a Nash stable S, they are not considered: if i prefers to join an existing coalition, it is a valid deviation. This assumes that the agents in $$\[--&#x003E;&#x003C;$&#x003E; {{{\scr C}}_2} &#x003C;$&#x003E;&#x003C;!--$$ will accept agent i, which is quite optimistic. In individual stability, the deviation is valid if no agent in $$\[--&#x003E;&#x003C;$&#x003E; {{{\scr C}}_2} &#x003C;$&#x003E;&#x003C;!--$$ is against accepting agent i. Finally, contractual individual stability adds a constraint on the agents from $$\[--&#x003E;&#x003C;$&#x003E; {{{\scr C}}_1} &#x003C;$&#x003E;&#x003C;!--$$ : they have to agree on agent i leaving them. The three stability concepts have the following inclusion: Nash stability is included in individual stability, which is included in contractual individual stability.

The literature in game theory focuses on finding conditions for the existence of the core. In the AI literature, Elkind and Wooldridge have proposed a succinct representation of Hedonic games Elkind and Wooldridge (Reference Elkind and Wooldridge2009).

We now turn to the most general definition of an NTU game, which uses a set of outcomes that can be achieved by the coalitions. The formal definition is the following:

• • a set of agents N;

• • a set of outcomes X;

• • a function $$\[--&#x003E;&#x003C;$&#x003E; V\,:\,{{2}^N} \, \rightarrow \,{{2}^X} &#x003C;$&#x003E;&#x003C;!--$$ that describes the outcomes $$\[--&#x003E;&#x003C;$&#x003E; V({\scr C})\, \subseteq \,X &#x003C;$&#x003E;&#x003C;!--$$ that can be brought about by coalition $$\[--&#x003E;&#x003C;$&#x003E;{\scr C} &#x003C;$&#x003E;&#x003C;!--$$ ;

• • a preference relation ≻_i (transitive and complete) over the set of outcomes for each agent i.

Intuitively, $$\[--&#x003E;&#x003C;$&#x003E; V({\scr C}) &#x003C;$&#x003E;&#x003C;!--$$ is the set of outcomes that $$\[--&#x003E;&#x003C;$&#x003E;{\scr C} &#x003C;$&#x003E;&#x003C;!--$$ can bring about by means of its joint action. The agents have a preference relation over the outcomes.

• • For each coalition $$\[--&#x003E;&#x003C;$&#x003E;{\scr C}\, \subseteq \,N&#x003C;$&#x003E;&#x003C;!--$$ , create a unique outcome $$\[--&#x003E;&#x003C;$&#x003E; {{x}_{\scr C}} &#x003C;$&#x003E;&#x003C;!--$$ .

• • For any two outcomes x_S and x_T corresponding to coalitions S and T that contains agent i, we define ≽_i as follows: x_S ≽_i x_T iff $$\[--&#x003E;&#x003C;$&#x003E; S\,{\succeq}_{i}^{H} \,T &#x003C;$&#x003E;&#x003C;!--$$ .

• • For each coalition $$\[--&#x003E;&#x003C;$&#x003E; {\scr C}\, \subseteq \,N &#x003C;$&#x003E;&#x003C;!--$$ , we define $$\[--&#x003E;&#x003C;$&#x003E; V({\scr C}) &#x003C;$&#x003E;&#x003C;!--$$ as $$\[--&#x003E;&#x003C;$&#x003E; V({\scr C})\, = \,\{ {{x}_{\scr C}}\} &#x003C;$&#x003E;&#x003C;!--$$ .

• • We define X to be the set of all allocations, that is, $$\[--&#x003E;&#x003C;$&#x003E; X\, = \,{{{\Bbb R}}^n} &#x003C;$&#x003E;&#x003C;!--$$ .

• • For any two allocations $$\[--&#x003E;&#x003C;$&#x003E; (x,y)\, \in \,{{X}^2} &#x003C;$&#x003E;&#x003C;!--$$ , we define ≽_i as follows: x ≽_i y iff x_i ≥ y_i.

• • For each coalition $$\[--&#x003E;&#x003C;$&#x003E; {\scr C}\, \subseteq \,N &#x003C;$&#x003E;&#x003C;!--$$ , we define $$\[--&#x003E;&#x003C;$&#x003E; V({\scr C}) &#x003C;$&#x003E;&#x003C;!--$$ as $$\[--&#x003E;&#x003C;$&#x003E; V({\scr C})\, = \,\{ x\, \in \,{{{\Bbb R}}^n} \;&#x007C;\;{{\sum }_{i\, \in \,N}}\,{{x}_i}\,\leq \,v({\scr C})\} &#x003C;$&#x003E;&#x003C;!--$$ . $$\[--&#x003E;&#x003C;$&#x003E; V({\scr C}) &#x003C;$&#x003E;&#x003C;!--$$ lists all the feasible allocation for the coalition $$\[--&#x003E;&#x003C;$&#x003E;{\scr C} &#x003C;$&#x003E;&#x003C;!--$$ .

First, we can note that the definition of the core can easily be modified in the case of NTU games.

An outcome x ∈ X is blocked by a coalition $$\[--&#x003E;&#x003C;$&#x003E;{\scr C} &#x003C;$&#x003E;&#x003C;!--$$ when there is another outcome y ∈ X that is preferred by all the members of $$\[--&#x003E;&#x003C;$&#x003E;{\scr C} &#x003C;$&#x003E;&#x003C;!--$$ . An outcome is then in the core when it can be achieved by the grand coalition and it is not blocked by any coalition. As is the case for TU game, it is possible that the core of an NTU game is empty.

3.1 Task allocation problem

A task allocation problem can be easily represented by a coalition formation problem: a coalition of agents is in charge of performing a task (or a subset of tasks). A task may require multiple agents to be performed because of the following reasons:

• • Complementary expertise may be required to perform a complex task, and many approaches assume that no agent has all the required expertise to perform a complex task on its own (Shehory & Kraus, Reference Shehory and Kraus1998; Kraus et al., Reference Kraus, Shehory and Taase2003, Reference Kraus, Shehory and Taase2004; Manisterski et al., Reference Manisterski, David, Kraus and Jennings2006). In the general case, a task can be decomposed into subtasks, and the agents are able to perform a subset of all possible subtasks.

• • All the agents have the required ability or expertise to perform a task, but they do not have enough resources on their own to perform the task. For example, robots have the ability to move objects in a plant, but multiple robots are required to move a heavy box (Shehory & Kraus, Reference Shehory and Kraus1998; Aknine et al., Reference Aknine, Pinson and Shakun2004).

In addition, the valuation function of a coalitional game has a simple interpretation: it is the benefit of the group of coalitions when the task is performed. The classical stability problem of coalitional games appears as multiple coalitions may be able to perform a complex task, and some coalitions may be better suited to perform a given task. Ideally, an agent should not have any incentive to join a different coalition to work on a different set of tasks.

A generic task allocation problem can be described as follows: a coalition of agents forms to perform a complex task and each agent in the coalition plays a role in the completion of the task (they can all have the same or complementary roles). The completion of a task is rewarded by a payoff. The cost associated with the task completion depends on the coalition members. The value of the coalition is the net benefit (payoff minus cost) of completing the task. Hence, the task allocation problem is well-modeled by a coalition formation problem where the value of a coalition depends only on its members. Note that in the case where agents are not self-interested, the population of agents as a whole may try to maximize the total benefit of completing the tasks. In this case, the agents are trying to optimize utilitarian social welfare and search for the optimal CS (see Section 4.2).

Task allocation problems may be even more complex. First, the tasks may be interdependent. For example, in a study by Shehory and Kraus (Reference Shehory and Kraus1998), there is a partial precedence order between the tasks. This assumption is of particular importance in the transportation domain. The existence of task dependency may promote cooperation between the agents as advocated by Aknine and Shehory (Reference Aknine and Shehory2005): the dependence between the tasks may translate into a certain form of dependence between the agents. If agents realize this fact, they may reciprocally help each other: agent A may help agent B to perform a task needed for the completion of an important task for agent B, and vice versa.

In the generic model, the cost and benefit depends only on the members of the coalition. In environments where the value of a task depends on its completion time, Kraus et al. (Reference Kraus, Shehory and Taase2003, Reference Kraus, Shehory and Taase2004) suggested that there should be a a cost associated with the time it takes to decide on a coalition. They propose a variant of the task allocation problem where at each round the reward to perform a task is reduced. This forces the agents to decide rapidly whether to form a coalition for taking advantage of the high reward. The first coalition that accepts the contract gets it, and if multiple coalitions agree one coalition is chosen at random. Agents that are only capable of performing a subset of the subtasks must propose or join a coalition. At each round, they can propose a coalition or accept to be part of one. Unlike in a study by Shehory and Kraus (Reference Shehory and Kraus1998) where all the tasks are known in advance, in these works, a coalition is formed incrementally for each task. The order of the tasks may play an important role in the overall payoff to the agents.

If tasks arrive in a pattern, it may be efficient to form similar coalitions for similar tasks. Abdallah and Lesser (Reference Abdallah and Lesser2004) assume the existence of a hierarchy of agents. When an agent gets a task for which it does not have the necessary resources, it can ask the agent above it in the hierarchy to take care of the task. If agents placed below it can solve subtasks of the task, the agent can decompose the task and assign it to the agents below in the hierarchy. Learning can be used to choose which agent can perform the task. Abdallah and Lesser show that learning allows for faster and better task assignments.

Another issue that can arise in the task allocation problem is the need to have overlapping coalitions, that is, to have the possibility that agents are members of multiple coalitions. For example, an agent i may have a unique ability that is required to complete two tasks. If i is restricted to be a member of a single coalition, one task cannot be completed, which would be inefficient in the case where i has enough resources to help performing both tasks. An example is in a transportation domain, if each task is to move an item between two points and a coalition is a set of vehicles that carries the item. Overlapping coalitions would model this problem as multiple items could be moved by the same truck (Shehory & Kraus, Reference Shehory and Kraus1998).

The task allocation problem is in general a computationally hard problem: when agents are limited to perform a single task, the coalition problem resembles the set partitioning problem. When agents are able to perform multiple tasks, the allocation problem gets closer to the set covering problem. In both cases, these problems are $$\[--&#x003E;&#x003C;$&#x003E; {\scr N}{\scr P} &#x003C;$&#x003E;&#x003C;!--$$ -complete (Shehory & Kraus, Reference Shehory and Kraus1998). A taxonomy is proposed to distinguish different complexity classes of the task allocation problems (Lau & Zhang, Reference Lau and Zhang2003) on the basis of three factors: (1) Is the same task likely to be offered again? (2) Does the multiagent system have more than enough/just enough/not enough resources to performing a set of tasks? (3) Is the reward intrinsic to the task, or does it only depend on the members performing the task? They show that some combinations of factors lead to polynomial problems, and other combinations have exponential complexity. Shehory and Kraus (Reference Shehory and Kraus1998) restrict the set of possible coalitions by adding a constraint on the size of the coalition. This assumption is motivated by the fact that negotiation with a large number of partners becomes costly, and over a given size, a coalition of agents will not be able to get any benefit. In this case, the size of the set of possible coalitions is a constant, and hence the problem can be solved in polynomial time (possibly a high order polynomial though).

3.2 Electronic marketplace

Coalition formation has also been used to model firms or agents in the electronic marketplace (Tsvetovat et al., Reference Tsvetovat, Sycara, Chen and Ying2001; Li & Sycara, Reference Li and Sycara2002; Vassileva et al., Reference Vassileva, Breban and Horsch2002; Li et al., Reference Li, Rajan, Chawla and Sycara2003; Sarne & Kraus, Reference Sarne and Kraus2003, Reference Sarne and Kraus2005; Cornforth et al., Reference Cornforth, Kirley and Bossomaier2004; Asselin & Chaib-draa, Reference Asselin and Chaib-draa2006). The field originated from a paper by Tsvetovat et al. (Reference Tsvetovat, Sycara, Chen and Ying2001) where consumer agents can form a coalition (i.e. a buying group) to benefit from the quantity discount provided by sellers. From the point of view of a system designer, the problem is to form a CS, and each coalition is forming a buying group. Desirable property of the CS formed include to be Pareto optimal, that is, no other CS should give more to a consumer without giving less to another one (Asselin & Chaib-draa, Reference Asselin and Chaib-draa2006) and social welfare maximization, which provides the greatest revenue to the buyers.

First, this problem can be modeled by coalitional games with NTU, as in practice, a buyer may not pay another buyer to join a buying group (it is recognized that side-payments could allow for more efficient outcomes though). It is the model studied by Asselin and Chaib-draa (Reference Asselin and Chaib-draa2006); their goal is to define protocols that find a Pareto optimal solutions, and they only propose a centralized solution.

One variant of the problem is to consider the cost of searching for other coalition members. For example, there is a cost to advertise the possibility to form a buying group, to look for partners, to negotiate price and payment (Sarne & Kraus, Reference Sarne and Kraus2003). The goal of the agents is to increase the size of the coalition so that the benefit from forming a coalition is worth the effort. The dilemma is about executing the task with the current configuration or starting a costly search to find new partners. The work of Sarne and Kraus analyzes the equilibrium strategies.

Other variants include the problem introduced by Yamamoto and Sycara (Reference Yamamoto and Sycara2001). Unlike in the original problem in a study by Tsvetovat et al. (Reference Tsvetovat, Sycara, Chen and Ying2001), a buying group does not correspond to a particular item: each buyer agent can have a list of single items or a disjunction of items. In addition, sellers can bid discount prices to sell large volume of items. This allows a formulation that is closer to a combinatorial auction. The proposed solution assumes that each buying group is managed by an agent that has to solve the following two problems: (1) given the requests from the buyer agents, the manager agent chooses the sellers and buys the appropriate items, and (2) the manager agent chooses the price paid by each buyer agent. To address the first problem, the proposed algorithm performs a greedy search. To answer the second problem, Yamamoto and Sycara use a surplus sharing rule that ensures a payoff distribution, which is in the core. In a study by Li and Sycara (Reference Li and Sycara2002), the agents can bid in combinatorial auctions: agents bid a reservation value for a bundle of items. This makes the problem even more complex as a winner determination problem has to be solved and a stable payoff distribution must be found. The mechanism design aspect of this problem can be found in a study by Li et al. (Reference Li, Rajan, Chawla and Sycara2003). Li and Sycara (Reference Li and Sycara2002) present an algorithm that computes an optimal coalition and a payoff division in the core, but it is not guaranteed to be of polynomial complexity. Hence, they also present an approximation algorithm that is polynomial.

A mathematical model using first-order differential equations is presented in a study by Lerman and Shehory (Reference Lerman and Shehory2000). The model describes the dynamics of the coalitions and allows for the computation of a steady-state equilibrium. The paper shows that a steady-state equilibrium always exists, and that it yields higher utility gain compared with the case where agents are buying on their own, or when leaving a coalition is not allowed. However, the outcome is not guaranteed to be Pareto optimal.

Vassileva et al. address long-term coalitions (Breban & Vassileva, Reference Breban and Vassileva2002; Vassileva et al., Reference Vassileva, Breban and Horsch2002): in many other papers, a coalition is formed to complete a given task, and the coalition is disbanded when the task is accomplished. In contrast, the goal is to form a coalition of agents that will collaborate for a long period of time. The decision to leave a coalition and join a new one should also be a function of the trust put in another agents, that is, the belief that they will have successful interaction in the future.

Another application of coalition formation in the context of an electronic marketplace is service-oriented computing. A large number of services are offered on the Internet, at different prices and with different quality. Blankenburg et al. (Reference Blankenburg, He, Klusch and Jennings2006) propose the use of service Request Agent that can request one (potentially) complex task and a Service Provider Agent that can provide a service. The latter can also, given a task and a set of service advertisements, compose services to form a plan that implements the task. The service requester agents only pay the service provider agent if the task is performed on time. The service provider agents must evaluate the risk involved in accepting a request. In addition, a service provider may be involved in more than one coalition, that is, it can have multiple clients at the same time. Blankenburg et al. propose the use of fuzzy coalitions to allow agents to be members of multiple coalitions. The agents use a measure of risk from the finance literature and they accept a proposal if the risk is below a threshold. To distribute the payoff, Blankenburg et al. define the kernel for their fuzzy coalition and use Stearns method to converge to a payoff distribution in the kernel.

3.3 Other domains

Coalitions of agents have also been used in many other application domains, and we list some of them in the following. We start with an application for gathering information (Klusch & Shehory, Reference Klusch and Shehory1996a, Reference Klusch and Shehory1996b). An agent is associated with a local database, and to answer a query, an agent may require other agents. When the agents form a coalition, all agents in the coalition must cooperate: the members share some of their private data, for example, dependency information. If an agent does not cooperate, it will not have access to some information schema that are available to members of the coalition. The coalition formation process assumes an utilitarian mechanism, and each agent tries to maximize its expected utility. The BSVis used to determine the payoff distribution in a study by Klusch and Shehory (Reference Klusch and Shehory1996a). A kernel-oriented solution is proposed by Klusch and Shehory (Reference Klusch and Shehory1996b) for the same domain.

Coalitions have been used to track a moving target using a sensor network, a problem introduced by Horling et al. (Reference Horling, Vincent, Mailler, Shen, Becker, Rawlins and Lesser2001). The problem is to ensure that at least three agents are sensing the target at the same time to perform triangulation. The problem becomes complex as the target is moving and sensors and communication can be faulty. In a study by Sims et al. (Reference Sims, Goldman and Lesser2003), the goal is for the agents to self-organize and form an appropriate coalition to track the target. The paper used a variant of the contract net protocol to negotiate a coalition that will be used throughout the tracking. Two valuation functions are studied (local and social utility) and different protocols are empirically tested. Soh et al. (Reference Soh, Tsatsoulis and Sevay2003) also solve a real-time tracking problem. An initiator agent starts the coalition formation process by contacting the neighboring agents that are most suitable for the particular task and engages in negotiation with each of them. Case-based reasoning is used to choose the most promising negotiation protocol. In addition, reinforcement learning is used to estimate the utility of a coalition. The coalition formation process may or may not succeed.

In machine learning, it is possible to combine the results of different classifier to increase the accuracy of the classification. Aknine and Caillou (Reference Aknine and Caillou2004) and Plaza and Ontañón (Reference Plaza and Ontañón2006) applied this idea in a coalition formation setting. For example, in the work of Plaza and Ontañón, agents can form committees (i.e. coalitions) to classify a new species of sponge. Each agent has its own expertise, a set of cases, and uses case-based reasoning for the classification problem. In their work, Plaza and Ontañón show how to decide when a committee is needed and how to select the agents to form a committee for a new species of sponge.

Coalitions of agents have been used in the context of distribution and planning of infrastructure for power transportation (Contreras et al., Reference Contreras, Klusch, Shehory and Wu1997, Reference Contreras, Klusch and Yen1998; Poon et al., Reference Poon, Yeung and Wu1999). Poon et al. (Reference Poon, Yeung and Wu1999) model the trading process between firms that generate, transmit, or distribute power using agents. Agents rank other agents by possible gains and send the BSV of the potential partner when it makes an offer. If both agents send requests to each other, it is beneficial for them to work together and they form a single entity. The process iterates until no further improvement is possible. In the power transmission domain, the problem is to decide whether or not to create a new line or a new plant, and if so, how to share the cost between the different parties involved. Contreras et al. (Reference Contreras, Klusch, Shehory and Wu1997, Reference Contreras, Klusch and Yen1998) use similar solutions as Yeung and Poon.

Coalitions of agents have been used in the context of planning and scheduling. For example, Pěchouček et al. (Reference Pěchouček, Mařík and Bárta2002) tackle the problem of planning humanitarian relief operations and the problem of production planning in a study by Pěchouček et al. (Reference Pěchouček, Mařík and čStépánková2000). For the humanitarian relief operation scenario, different organizations can form coalitions to be more efficient and provide optimal help to the people. However, the different groups that have different capabilities can also have different goals, and hence they might not want to disclose all available information. In that context, the authors propose a formation of alliances: provided some public information, the agents seek to form groups of agents with the same kind of goals. These alliances can be viewed as long-term agreements between agents, and alliances define a partition of the agents. Unlike alliances, coalitions are viewed as short-term agreements to perform a specific task, and to reduce the search space coalitions can form within an alliance. In case of impossibility of forming coalitions within an alliance, agents from different alliances can be used. The authors are interested in the amount of information agents have to disclose: when it sends a request, an agent may reveal private or semi-private information. This can occur when an agent asks an agent of a different alliance to perform a task (revealing that neither it nor its alliance can complete the task). An agent can also decide to disclose private information when it wants to inform other agents, for instance, when they form alliances.

In the context of production planning, instead of using a centralized planning approach, Pěchouček et al. want to use local coalition formation to execute tasks in an efficient manner. One requirement is that agents know their possible collaborators well in order to minimize the communication effort, for example, agents have knowledge of the status of surrounding agents, and thus an agent may ask help from another agent if it knows that the agent is not busy. Caillou et al. (Reference Caillou, Aknine and Pinson2002) use the scenario of scheduling classes in a university where a coalition is a schedule. This work considers NTU. Caillou et al. propose a protocol where a set of acceptable coalitions is passed from agents to agents, and each time agents can add coalitions or remove coalitions that are not acceptable. The result of the protocol is a Pareto optimal schedule. The protocol also considers reusing existing solutions to compute a solution to a modified problem (e.g. when a class is removed from the schedule, or a professor is coming, previous solutions of the problem can be used to accommodate these changes).

3.4 Some interesting classes of games from the computational point of view

We want to briefly introduce some classes of games that have been studied in the AI literature. Some of these classes of games can be represented more compactly than by using 2ⁿ values, one for each coalition, using an underlying graph structure. In some restricted cases, some solution concepts can be computed efficiently.

Graph games:Footnote ² This class of games was introduced by Deng and Papadimitriou (Reference Deng and Papadimitriou1994). A game is a pair 〈V,w〉 where V is the set of agents and is also the set of edges of a weighted undirected graph (V, w) where $$\[--&#x003E;&#x003C;$&#x003E; w\,:\,{{v}^2} \, \rightarrow \,{\Bbb R} &#x003C;$&#x003E;&#x003C;!--$$ is the weight function, mapping an edge $$\[--&#x003E;&#x003C;$&#x003E; (i,\,j)\, \in \,{{V}^2} &#x003C;$&#x003E;&#x003C;!--$$ to a real number. The value of a coalition $$\[--&#x003E;&#x003C;$&#x003E; {\scr C}\, \subseteq \,N &#x003C;$&#x003E;&#x003C;!--$$ is the sum of the weights of the sub-graph induced by $$\[--&#x003E;&#x003C;$&#x003E;{\scr C} &#x003C;$&#x003E;&#x003C;!--$$ .

This representation is succinct but not complete (e.g. a majority game cannot be represented using this representation). If all the weights are non-negative, then the game is convex (and consequently, the core is non-empty), and testing the membership in the core can be performed in polynomial time. In addition, the Shapley value can be computed in polynomial time.

Minimum cost spanning tree games: A game is 〈V, s, w〉 where 〈V, w〉 is as in a graph game and s ∈ V is the source node. For a coalition $$\[--&#x003E;&#x003C;$&#x003E;{\scr C} &#x003C;$&#x003E;&#x003C;!--$$ , we denote by $$\[--&#x003E;&#x003C;$&#x003E; \rGamma ({\scr C}) &#x003C;$&#x003E;&#x003C;!--$$ the minimum cost spanning tree spanning over the set of edges $$\[--&#x003E;&#x003C;$&#x003E; {\scr C}\, \cup \,\{ s\} &#x003C;$&#x003E;&#x003C;!--$$ . The value of a coalition $$\[--&#x003E;&#x003C;$&#x003E; V\,\backslash\: \{ s\} &#x003C;$&#x003E;&#x003C;!--$$ is given by $$\[--&#x003E;&#x003C;$&#x003E; {{\sum }_{(i,\,j)\, \in \,\rGamma ({\scr C})}}\,{{w}_{i,\,j}} &#x003C;$&#x003E;&#x003C;!--$$ .

This class of game can model the problem of connecting some agents to a central node played by the source node s. Computing the nucleolus or checking whether the core is non-empty can be done in polynomial time.

Network flow games: A flow network 〈V, E, c, s, t〉 is composed of a directed graph (V, E) with a capacity on the edge $$\[--&#x003E;&#x003C;$&#x003E; c\,:\,{{V}^2} \, \rightarrow \,{{{\Bbb R}}^ + } &#x003C;$&#x003E;&#x003C;!--$$ , a source vertex s and a sink vertex t. A network flow is a function $$\[--&#x003E;&#x003C;$&#x003E; f:E \rightarrow {{{\Bbb R}}^ + } &#x003C;$&#x003E;&#x003C;!--$$ that satisfies the capacity of an edge $$\[--&#x003E;&#x003C;$&#x003E; (\forall (i,\,j)\, \in \,E,\,\,f(i,\,j)\,\leq \,c(i,\,j)) &#x003C;$&#x003E;&#x003C;!--$$ and that is conserved (except for the source and sink), that is, the total flow arriving at an edge is equal to the total flow leaving that edge $$\[--&#x003E;&#x003C;$&#x003E; (\forall j\, \in \,V,\,\,{{\sum }_{(i,\,j)\, \in \,E}}\,f(i,j)\, = \,{{\sum }_{(j,k)\, \in \,E}}\,f(j,k)) &#x003C;$&#x003E;&#x003C;!--$$ . The value of the flow is the amount flowing out of the sink node.

In network flow game (Kalai & Xemel, Reference Kalai and Xemel1982), 〈V, E, c, s, t〉, the value of a coalition $$\[--&#x003E;&#x003C;$&#x003E; {\scr C}\, \subseteq \,N &#x003C;$&#x003E;&#x003C;!--$$ is the maximum value of the flow going through the flow network $$\[--&#x003E;&#x003C;$&#x003E; \langle {\scr C},E,c,s,t\rangle &#x003C;$&#x003E;&#x003C;!--$$ .

This class of games can model a situation where some cities share a supply of water or some electricity network. Kalai and Xemel (Reference Kalai and Xemel1982) proved that a network flow game is balanced, and hence it has a non-empty core. Bachrach and Rosenschein (Reference Bachrach and Rosenschein2009) study a threshold version of the game and the complexity of computing power indices.

Affinity games: The class of affinity games is a class of hedonic games introduced by Brânzei and Larson (Reference Brânzei and Larson2009a, Reference Brânzei and Larson2009b). An affinity game is defined using a directed weigthed graph 〈V, E, w〉 where V is the set of agents, E is the set of directed edges and $$\[--&#x003E;&#x003C;$&#x003E; w\,:\,E\, \rightarrow \,{\Bbb R} &#x003C;$&#x003E;&#x003C;!--$$ is the weight of the edges. w(i, j) is the value of agent i when it is associated with agent j. The value of agent i for coalition $$\[--&#x003E;&#x003C;$&#x003E;{\scr C} &#x003C;$&#x003E;&#x003C;!--$$ is $$\[--&#x003E;&#x003C;$&#x003E; {{v}_i}({\scr C})\, = \,{{\sum }_{j\, \in \,{\scr C}}}\,w(i,\,j) &#x003C;$&#x003E;&#x003C;!--$$ .

Some special classes of affinity games have a non-empty core (e.g. when the weights are all positive or all negative). In these games, there may be a trade-off between stability and efficiency (in the sense of maximizing social welfare) as the ratio between an optimal CS and a stable CS may be infinite.

Skill games: This class of games, introduced by Bachrach and Rosenschein (Reference Bachrach and Rosenschein2008) is represented by a triplet 〈N, S, T, u〉 where N is the set of agents, S is the set of skills, T is the set of tasks, and $$\[--&#x003E;&#x003C;$&#x003E; u\,:\,{{2}^T} \, \rightarrow \,{\Bbb R} &#x003C;$&#x003E;&#x003C;!--$$ provides a value to each set of tasks that is completed. Each agent i has a set of skills $$\[--&#x003E;&#x003C;$&#x003E; S(i)\, \subseteq \,S &#x003C;$&#x003E;&#x003C;!--$$ , each task t_i requires a set of skills $$\[--&#x003E;&#x003C;$&#x003E; S({{t}_i})\, \subseteq \,S &#x003C;$&#x003E;&#x003C;!--$$ . A coalition $$\[--&#x003E;&#x003C;$&#x003E;{\scr C} &#x003C;$&#x003E;&#x003C;!--$$ can perform a task t when each skill needed for the task is the skill of at least a member of $$\[--&#x003E;&#x003C;$&#x003E;{\scr C} &#x003C;$&#x003E;&#x003C;!--$$ (i.e. $$\[--&#x003E;&#x003C;$&#x003E; \forall s\, \in \,S(t),\,\,\exists i\, \in \,{\scr C} &#x003C;$&#x003E;&#x003C;!--$$ such that $$\[--&#x003E;&#x003C;$&#x003E; S(i)\, = \,s &#x003C;$&#x003E;&#x003C;!--$$ ). The value of a coalition $$\[--&#x003E;&#x003C;$&#x003E;{\scr C} &#x003C;$&#x003E;&#x003C;!--$$ is $$\[--&#x003E;&#x003C;$&#x003E; u({{T}_{\scr C}}) &#x003C;$&#x003E;&#x003C;!--$$ where $$\[--&#x003E;&#x003C;$&#x003E; {{T}_{\scr C}} &#x003C;$&#x003E;&#x003C;!--$$ is the set of tasks that can be performed by $$\[--&#x003E;&#x003C;$&#x003E;{\scr C} &#x003C;$&#x003E;&#x003C;!--$$ .

This representation is exponential in the number of agents, but variants of the representation lead to polynomial representation. For example, when the value of a coalition is the number of tasks it can accomplish, or when each task has a weight and the value of a coalition is the sum of the weights of the accomplished tasks. In general, computing the solution concepts with these polynomial representation is hard. However, in some special cases, checking whether the core is empty or computing an element of the core can be carried out in polynomial time. The problem of finding an optimal CS is found in a study by Bachrach et al. (Reference Bachrach, Meir, Jung and Kohli2010).

Some more papers are studying the computational complexity of some subclasses of games, for example, Greco et al. (Reference Greco, Malizia, Palopoli and Scarcello2009) and Aziz et al. (Reference Aziz, Brandt and Harrenstein2010), to name a few. We do not want to provide a full account of complexity problem, which could be the topic of a survey paper on its own.

4.1 Sharing the computation of the coalition values

Before searching the space of CSs to find an optimal CS, the agents may need to compute the value of each of the coalitions. We are interested in a decentralized algorithm that computes all the coalition values in a minimal amount of time, and that requires minimum communication between the agents.

Shehory and Kraus (Reference Shehory and Kraus1998) were the first to propose an algorithm to share the computation of the coalition values. In their algorithm, the agents negotiate which computation is performed by which agent, which is quite demanding. Rahwan and Jennings proposed an algorithm where agents, once they agree on an identification for each agent participating in the computation, know exactly which coalition values to compute. This algorithm, called DCVC (Rahwan & Jennings, Reference Rahwan and Jennings2007), outperforms the one by Shehory and Kraus. The key observation is that in general it should take longer to compute the value of a large coalition compared with a small coalition (i.e. the computational complexity is likely to increase with the size of the coalition as more agents have to coordinate their activities). Their method improves the balance of the loads by distributing coalitions of the same size to all agents. By knowing the number of agents n participating in the computation and an index number (i.e. an integer in the range {0…n}), the agents determine for each coalition size which coalition values to compute. The algorithm can also be adapted when the agents have different known computational speed so as to complete the computation in a minimum amount of time.

4.2 Searching for the optimal coalition structure

The difficulty of searching for the optimal CS lies in the large search space, as recognized by existing algorithms, and this is even more true in the case where there exists externalities (i.e. when the valuation of a coalition depends on the CS). For TU games with no externalities, some algorithms guarantee finding CSs within a bound from the optimum when an incomplete search is performed. Unfortunately, such guarantees are not possible for games with externalities. We shortly discuss these two cases in the following.

5.1 Stability and dynamic environments

Real-world scenarios often present dynamic environments. Agents can enter and leave the environment at any time, the characteristics of the agents may change with time, the knowledge of the agents about the other agents may change, etc.

The game-theoretic stability criteria are defined for a fixed population of agents and the introduction of a new agent in the environment requires significant computation to update a stable payoff distribution. For example, for the kernel, all the agents need to check whether any coalition that includes the new agent changes the value of the maximum surplus, which requires reevaluating $$\[--&#x003E;&#x003C;$&#x003E; O{{(2}^n} ) &#x003C;$&#x003E;&#x003C;!--$$ coalitions. Given the complexity of the stability concept, one challenge that is faced by the multiagent community is to develop stability concepts that can be easily updated when an agent enters or leaves the environment.

In addition, if an agent drops during the negotiation, this may cause problems for the remaining agents. For example, a protocol that guarantees a kernel stable payoff distribution is shown not to be ‘safe’ when the population of agents is changing: if an agent i leaves the formation process without notifying other agents, the other agents may complete the protocol and find a solution to a situation that does not match the reality. Each time a new agent enters or leaves the population, a new process needs to be restarted (Blankenburg & Klusch, Reference Blankenburg and Klusch2004).

In an open environment, manipulations will be impossible to detect: agents may use multiple identifiers (or false names) to pretend to be multiple agents, or the other way around, multiple agents may collude and pretend to be asingle agent, or agents can hide some of their skills. Hence, it is important to propose solution concepts that are robust against such manipulations. We will come back later to some of the solution that have been proposed: the anonymity-proof core (Yokoo et al., Reference Yokoo, Conitzer, Sandholm, Ohta and Iwasaki2005) and anonymity-proof Shapley value (Ohta et al., Reference Ohta, Conitzer, Satoh, Iwasaki and Yokoo2009).

5.2 Uncertainty about knowledge and task

In real-world scenarios, agents will be required to handle some uncertainty. Different sources of uncertainty have been considered in the literature:

• • The valuation function is an approximation (Sandholm & Lesser, Reference Sandholm and Lesser1997) and agents may not use the same algorithm. Hence, the agents may not know what is the true value.

• • Agents may not know some tasks (Blankenburg & Klusch, Reference Blankenburg and Klusch2004) or the value of some coalitions. In such cases, the agents play a different coalitional game that may reduce the payoff of some agents compared with the solution of the true game.

• • Some information is private, that is, an agent knows some property about itself, but does not know it for other agents. In a study by Kraus et al. (Reference Kraus, Shehory and Taase2003), it is the cost incurred by other agents to perform a task that is private. In studies by Chalkiadakis et al. (Reference Chalkiadakis, Elkind and Jennings2009) and Chalkiadakis and Boutilier (Reference Chalkiadakis and Boutilier2012), agents have a private type, and the valuation function depends on the types of the coalition's members.

• • Uncertainty about the outcome of an action (Chalkiadakis & Boutilier, Reference Chalkiadakis and Boutilier2012): when a coalition makes an action, some external factors may influence the outcome of the actions. This can be captured by a probability of an outcome, given the action taken and the type of the members of the coalition.

• • There are multiple possible worlds (Ieong & Shoham, Reference Ieong and Shoham2008), which models the different possible outcomes of the formation of a coalition. Agents know a probability distribution over the different worlds. In addition, an agent may not be able to distinguish some worlds as it lacks information and they know a partition of the worlds (called information sets), each set of the partition represent worlds that appears as indistinguishable.

Some authors also consider that there is uncertainty in the valuation function without modeling a particular source: for example, in a study by Ketchpel (Reference Ketchpel1994b), each agent has an expectation of the valuation function. In studies by Blankenburg et al. (Reference Blankenburg, Klusch and Shehory2003) and Blankenburg and Klusch (Reference Blankenburg and Klusch2005), fuzzy sets are used to represent the valuation function. In the first paper, the agents enter bilateral negotiations to negotiate Shapley value, and in the second paper they define a fuzzy version of the kernel.

In the uncertainty model by Ieong and Shoham (Reference Ieong and Shoham2008), the definition of the core depends on the time one reasons about it. They proposed three different definitions of the core that depend on the timing of the evaluation: before the world is drawn or ex-ante, not much information can be used; after the world is drawn but before it is known, also called ex-interim, an agent knows to which set of its information set the real world belongs, but does not know which one; finally when the world is announced to the agent or ex-post, everything is known.

The model by Chalkiadakis and Boutilier (Reference Chalkiadakis and Boutilier2012) combines uncertainty about the agent types and uncertainty about the outcome of the action taken by the coalition. Each agent has a probabilistic belief about the types of the other agents in the population. Chalkiadakis and Boutilier propose a definition of the core, the Bayesian core (introduced in a study by Chalkiadakis & Boutilier, Reference Chalkiadakis and Boutilier2004) in which no agent has the belief that there exists a better coalition to form. As it may be difficult to obtain all the probabilities and reason about them, Chalkiadakis et al. (Reference Chalkiadakis, Elkind and Jennings2009) propose to use a ‘point’ belief: an agent guesses the type of the other agents and reason with these guesses. The paper analyzes the core, simple games (proving that the core of a simple game is non-empty iff the game has a veto player) and some complexity result in this games with belief.

5.3 Safety and robustness

It is also important that the coalition formation process is robust. For instance, communication links may fail during the negotiation phase. Hence, some agents may miss some components of the negotiation stages. This possibility is found in a study by Blankenburg and Klusch (Reference Blankenburg and Klusch2004) for the KCA protocol (Klusch & Shehory, Reference Klusch and Shehory1996b): coalition negotiations are not safe when some agents become unavailable (intentionally or otherwise). In particular, the payoff distribution is not guaranteed to be kernel-stable. Belmonte et al. (Reference Belmonte, Conejo, de-la Cruz and Ruiz2004) empirically study the robustness of the use of a central algorithm introduced in their paper (Belmonte et al., Reference Belmonte, Conejo, de-la Cruz and Ruiz2002): the cost to compute a task allocation and payoff distribution in the core is polynomial, but it can still be expensive. In the case of agent failure, the computation needs to be repeated. Belmonte et al. propose an alternative payoff division model that avoids such a recomputation, but the solution is no longer guaranteed to be in the core, it is only close to the core. There is a trade-off between computational efficiency and the utility obtained by the agent. They conclude that, when the number of agents is small, the loss of utility compared with the optimal is small; hence, the improvement of the computational efficiency can be justified. However, for a larger number of agents, the loss of utility cannot justify the improvement in computational cost.

5.4 Communication

Whereas one purpose of better negotiation techniques may be to improve the quality of the outcome for the agents, other goals may include decreasing the time and the number of messages required to reach an agreement. For example, learning is used to decrease negotiation time in a study by Soh and Tsatsoulis (Reference Soh and Tsatsoulis2002). The motivation of Lerman's work (Lerman & Shehory, Reference Lerman and Shehory2000) is to develop a coalition formation mechanism that has low communication and computation cost. In another work, the communication costs are included in the characteristic function Tohmé and Sandholm (Reference Tohmé and Sandholm1999).

The communication complexity of some protocols has been derived. For instance, the exponential protocol in a study by Tohmé and Sandholm (Reference Tohmé and Sandholm1999) and the coalition algorithm for forming BSV stable coalition in a study by Klusch and Shehory (Reference Klusch and Shehory1996a) have communication complexity of $$\[--&#x003E;&#x003C;$&#x003E; O({{n}^2} ) &#x003C;$&#x003E;&#x003C;!--$$ , the negotiation-based protocol in a study by Tohmé and Sandholm (Reference Tohmé and Sandholm1999) is $$\[--&#x003E;&#x003C;$&#x003E; O({{n}^2} {{2}^n} ) &#x003C;$&#x003E;&#x003C;!--$$ , and it is $$\[--&#x003E;&#x003C;$&#x003E; O({{n}^k} ) &#x003C;$&#x003E;&#x003C;!--$$ for the protocol in a study by Shehory and Kraus (Reference Shehory and Kraus1998) (where k is the maximum size of a coalition). The goal of Procaccia and Rosenschein (Reference Procaccia and Rosenschein2006) is to analyze the communication complexity of computing the payoff of a player with different stability concepts: they find that it is $$\[--&#x003E;&#x003C;$&#x003E; \rTheta (n) &#x003C;$&#x003E;&#x003C;!--$$ when either the Shapley value, the nucleolus, or the core are used.

5.5 Scalability

When the population of heterogeneous agents is large, discovering the relevant agents to perform a task may be difficult. In addition, if all agents are involved in the coalition formation process, the cost in time and computation will be large. To alleviate this scalability issue, a hierarchy of agents can be used (Abdallah & Lesser, Reference Abdallah and Lesser2004). When an agent discovers a task that can be addressed by agents below this agent in the hierarchy, the agent picks the best of them to perform the task. If the agents below cannot perform the task, the agent passes the task to the agent above it in the hierarchy and the process repeats. The notion of clans (Griffiths & Luck, Reference Griffiths and Luck2003) and congregations (Brooks & Durfee, Reference Brooks and Durfee2003), where agents gather together for a long period, have been proposed to restrict the search space by considering only a subset of the agents (see Section 5.6).

5.6 Long term vs. short term

In general, a coalition is a short-lived entity that is ‘formed with a purpose in mind and dissolve when that need no longer exists, the coalition ceases to suit its designed purpose, or critical mass is lost as agents depart’ (Horling & Lesser, Reference Horling and Lesser2004). It can be beneficial to consider the formation of long-term coalitions, or the process of repeated coalition formation involving the same agents. Vassileva et al. (Reference Vassileva, Breban and Horsch2002) explicitly study the long-term coalitions, and in particular the importance of trust in this content. Brooks and Durfee (Reference Brooks and Durfee2003) refer to a long-term coalition as a congregation. The purpose of a congregation is to reduce the number of candidates for a successful interaction: instead of searching the entire population, agents will only search in the congregation. The goal of a congregation is to gather agents, with similar or complementary expertise to perform well in an environment in the long run, which is not very different from a coalition. The only difference is that group rationality is not expected in a congregation. The notion of congregation is similar to the notion of clans (Griffiths & Luck, Reference Griffiths and Luck2003): agents gather not for a specific purpose, but for a long-term commitment. The notion of trust is paramount in the clans, and sharing information is seen as another way to improve performance.

5.7 Fairness

Stability does not necessarily imply fairness. For example, let us consider two CSs $$\[--&#x003E;&#x003C;$&#x003E;{\scr S} &#x003C;$&#x003E;&#x003C;!--$$ and $$\[--&#x003E;&#x003C;$&#x003E;{\scr T} &#x003C;$&#x003E;&#x003C;!--$$ with associated kernel–stable payoff distribution $$\[--&#x003E;&#x003C;$&#x003E; {{x}_{\scr S}} &#x003C;$&#x003E;&#x003C;!--$$ and $$\[--&#x003E;&#x003C;$&#x003E; {{x}_{\scr T}} &#x003C;$&#x003E;&#x003C;!--$$ . Agents may have different preferences between the CSs. It may even be the case that there is no CS that is preferred by all agents. If the optimal CS is formed, some agents, especially if they are in a singleton coalition, may suffer from the choice of this CS. Airiau and Sen (Reference Airiau and Sen2010) propose a modification of the kernel to allow side-payment between coalitions to compensate such agents.

Airiau and Sen (Reference Airiau and Sen2009) consider partition function games with externalities. They consider a process where, in turns, agents change coalition to improve their immediate payoff. They propose that the agents share the maximal social welfare, and the size of the share is proportional to the expected utility of the process. The payoff obtained is guaranteed to be at least as high as the expected utility. They claim that using the expected utility as a base of the payoff distribution provides some fairness, as the expected utility can be seen as a global metric of an agent performance over the entire set of possible CSs.

5.8 Overlapping coalitions

It is typically assumed that an agent belongs to a single coalition; however, there are some applications where agents can be members of multiple coalitions. As explained in the task allocation domain (see Section 3.1), the expertise of an agent may be required by different coalitions at the same time, and the agent can have enough resources to be part of two or more coalitions. In a traditional setting, the use of the same agent i by two coalitions $$\[--&#x003E;&#x003C;$&#x003E; {{{\scr C}}_1} &#x003C;$&#x003E;&#x003C;!--$$ and $$\[--&#x003E;&#x003C;$&#x003E; {{{\scr C}}_2} &#x003C;$&#x003E;&#x003C;!--$$ would require a merge of the two coalitions. This larger coalition U is potentially harder to manage, and a priori, there would not be much interaction between the agents in $$\[--&#x003E;&#x003C;$&#x003E; {{{\scr C}}_1} &#x003C;$&#x003E;&#x003C;!--$$ and $$\[--&#x003E;&#x003C;$&#x003E; {{{\scr C}}_2} &#x003C;$&#x003E;&#x003C;!--$$ , except for agent i. Another application that requires the use of overlapping coalition is tracking targets using a sensor networks (Dang et al., Reference Dang, Dash, Rogers and Jennings2006). In this work, a coalition is defined for a target, and as agents can track multiple targets at the same time they can be members of different coalitions.

The traditional stability concepts do not consider this issue. One possibility is for the agent to be considered as two different agents, but this representation is not satisfactory as it does not capture the real power of this agent. Shehory and Kraus (Reference Shehory and Kraus1998) propose a setting with overlapping coalition. Each agent has a capacity, and performing a task may use only a fraction of the agent's capacity. Each time an agent commits to a task, the possible coalitions that can perform a given task can change. A mapping to a set covering problem allows to find the coalition. However, the study of the stability is not considered. Another approach is the use of fuzzy coalition (Blankenburg et al., Reference Blankenburg, He, Klusch and Jennings2006): agents can be members of a coalition with a certain degree that represents the risk associated with being in that coalition. Other work considers that the agents have different degree of membership, and their payoff depends on this degree (Aubin, Reference Aubin1979; Mares, Reference Mares2001; Nishizaki & Masatoshi, Reference Nishizaki and Sakawa2001). The protocols in the study by Lau and Zhang (Reference Lau and Zhang2003) also allow overlapping coalitions.

More recently, Chalkiadakis et al. (Reference Chalkiadakis, Elkind, Markakis and Jennings2010)Footnote ⁴ have studied the notion of the core in overlapping coalition formation. In their model, each agent has one resource and the agent contributes a fraction of that resource to each coalition it participates in. The valuation function v is then $$\[--&#x003E;&#x003C;$&#x003E; {{[0,1]}^n} \, \rightarrow \,{\Bbb R} &#x003C;$&#x003E;&#x003C;!--$$ . A CS is no longer a partition of the agents: a CS S is a finite list of vectors, one for each ‘partial’ coalition, that is, $$\[--&#x003E;&#x003C;$&#x003E; S\, = \,({{r}^1}, \ldots, {{r}^k} ) &#x003C;$&#x003E;&#x003C;!--$$ . The size of S is the number of coalitions, that is, k. The support of $$\[--&#x003E;&#x003C;$&#x003E; {{r}^{\scr C}} \, \in \,S &#x003C;$&#x003E;&#x003C;!--$$ (i.e. the set of indices i ∈ N such that $$\[--&#x003E;&#x003C;$&#x003E; r_{i}^{{\scr C}} \, \ne \,0 &#x003C;$&#x003E;&#x003C;!--$$ ) is the set of agents forming coalition $$\[--&#x003E;&#x003C;$&#x003E;{\scr C} &#x003C;$&#x003E;&#x003C;!--$$ . For all i ∈ N and all coalition $$\[--&#x003E;&#x003C;$&#x003E; {\scr C}\, \in \,S &#x003C;$&#x003E;&#x003C;!--$$ , $$\[--&#x003E;&#x003C;$&#x003E; r_{i}^{{\scr C}} \, \in \,{{[0,1]}^n} &#x003C;$&#x003E;&#x003C;!--$$ represents the fraction of resource that agent i contributes to coalition $$\[--&#x003E;&#x003C;$&#x003E;{\scr C} &#x003C;$&#x003E;&#x003C;!--$$ ; hence, $$\[--&#x003E;&#x003C;$&#x003E; {{\sum }_{{\scr C}\, \in \,S}}\,r_{i}^{{\scr C}} \,\leq \,1 &#x003C;$&#x003E;&#x003C;!--$$ (i.e. agent i cannot contributes more than 100% of its resource). A payoff distribution for a CS S of size k is defined by a k-tuple $$\[--&#x003E;&#x003C;$&#x003E; x\, = \,({{x}^1}, \ldots, {{x}^k} ) &#x003C;$&#x003E;&#x003C;!--$$ where $$\[--&#x003E;&#x003C;$&#x003E; {{x}^{\scr C}} &#x003C;$&#x003E;&#x003C;!--$$ is the payoff distribution that the agents obtain for coalition $$\[--&#x003E;&#x003C;$&#x003E;{\scr C} &#x003C;$&#x003E;&#x003C;!--$$ . If an agent is not in the coalition, it must not receive any payoff for this coalition, and hence $$\[--&#x003E;&#x003C;$&#x003E; (r_{i}^{{\scr C}} \, = \,0)\, \Rightarrow \,(x_{i}^{{\scr C}} \, = \,0) &#x003C;$&#x003E;&#x003C;!--$$ . The total payoff of agent i is the sum of its payoffs over all coalitions $$\[--&#x003E;&#x003C;$&#x003E; {{p}_i}({\scr C}S,x)\, = \,\sum _{{{\scr C}\, = \,1}}^{k} \,x_{i}^{{\scr C}} &#x003C;$&#x003E;&#x003C;!--$$ . The efficiency criterion becomes $$\[--&#x003E;&#x003C;$&#x003E; \forall {{r}^{\scr C}} \in S &#x003C;$&#x003E;&#x003C;!--$$ , $$\[--&#x003E;&#x003C;$&#x003E; \mathop{\sum}\nolimits_{i\, \in \,N} x_{i}^{{\scr C}} \, = \,v({{r}^{\scr C}} ) &#x003C;$&#x003E;&#x003C;!--$$ . An imputation is an efficient payoff distribution that is also individually rational. We denote by I(S) the set of all imputations for the CS S.

We are now ready to define the overlapping core. One issue is the kind of permissible deviations: when an agent deviates, she can completely leave some coalitions, reduce her contribution in other coalitions, or contributes to new coalitions. If she stills contribute to a coalition containing non-deviating agents, how should they behave? They may first refuse to give any payoff to the deviating agent, as she is seen as not trustworthy. However, agents that are not affected by the deviation may consider that the deviators agents did not fail them, and consequently they may continue to share payoffs with the deviators. A last case occurs when the deviators are decreasing their implication in a coalition. This coalition may no longer perform the same tasks, but it can still perform some. If there is enough value to maintain the payoff of the non-deviators, the deviators may be allowed to share the surplus generated. Each of these behaviors give rise to different types of deviations, and consequently different definition of a core: the conservative core, the refined core, and the optimistic core. The paper also provides a characterization of conservative core, properties of the different core, including a result showing that convex overlapping coalitional games have a non-empty core.

5.9 Trust

The notion of trust can be an important metric to determine whom to interact with. This is particularly important when the coalition is expected to live for a long term. In a study by Blankenburg et al. (Reference Blankenburg, Dash, Ramchurn, Klusch and Jennings2005), an agent computes a probability of success of a coalition, on the basis of a notion of trust, which can be used to eliminate some agents from future consideration. This probability is used to estimate the value of different coalitions and help the agent in deciding which coalition to join or form. In a study by Vassileva et al. (Reference Vassileva, Breban and Horsch2002), the decision to leave or join a coalition is function of the trust put in other agents. In this paper, the concept of trust is defined as a belief that agents will have successful interaction in the future; hence, trust is used to consider a subset of the entire population of agents for the formation of future coalitions. Trust is used to compute coalitions, but agents do not compute a payoff distribution. Another work that emphasizes trust is the study by Griffiths and Luck (Reference Griffiths and Luck2003), which introduces the concept of clans. A clan is formed by agents that trust each other with long-term commitments. Given the trust and an estimate of local gain, agents can accept to join a clan. The idea behind this work is that agents that trust each other will be collaborative. Moreover, when an agent needs to form a coalition of agents, it will only search partners in the clan, which reduces the search space. Trust can therefore be very effective for scaling up in large society of agents.

5.10 Learning

When agents have to repeatedly form coalitions in the presence of the same set of agents, learning can be used to improve performance of the coalition formation process, both in terms of speed of the process and in terms of better valuation.

A basic model of iteratively playing many coalitional games is presented in a study by Mérida-Campos and Willmott (Reference Mérida-Campos and Willmott2004): at each time step, a task is offered to agents that are already organized into coalitions. The task is awarded to the best coalition. The model is made richer in a study by Mérida-Campos and Willmott (Reference Mérida-Campos and Willmott2006) where the agents can estimate the value of a coalition and have a richer set of actions: as the agents can fire members from a coalition, join a different coalition, or leave a coalition to replace some agents in a different coalition. However, in both works, the agents are not learning; they have a set of static strategies. Empirical experiments compare the results over populations using either the same strategy or a mix of strategies.

Chalkiadakis and Boutilier (Reference Chalkiadakis and Boutilier2004, Reference Chalkiadakis and Boutilier2008, Reference Chalkiadakis and Boutilier2012) also consider a repeated coalition formation problem, sequentially. The setting is a task allocation problem where agents know their own types (i.e. skill to perform some type of tasks), but do not know the ones of other agents in the population. Each time a coalition is formed, the agents will receive a value for that coalition. From the observation of this value, the agents can update a belief about the types of other agents. When an agent is reasoning about which coalition to form, it uses its beliefs to estimate the value of the coalition. This problem can be formulated using a POMPD (Partially Observable Markov Decision Process) where the agents are maximizing the long-term value of their decision over the repetition of the coalition formation process. Solving a POMPD is a difficult task, and the POMPD for the coalition formation problem grows exponentially with the number of agents. In a study by Chalkiadakis and Boutilier (Reference Chalkiadakis and Boutilier2004), a myopic approach is proposed. More recently, Chalkiadakis & Boutilier (Reference Chalkiadakis and Boutilier2008) propose additional algorithms to solve that POMPD and empirically compare the solutions.