The paper proposes a list of requirements for a game able to describe individually motivated social interactions: be non-cooperative, able to construct multiple coalitions in an equilibrium and incorporate intra and inter coalition externalities. For this purpose the paper presents a family of non-cooperative games for coalition structure construction with an equilibrium existence theorem for a game in the family. Few examples illustrate the approach. One of the results is that efficiency is not equivalent to cooperation as an allocation in one coalition. Further papers will demonstrate other applications of the approach.
Introduction There is a conventional dichotomy in existing game theories: the cooperative game theory (CGT) versus the non-cooperative game theory (NGT). CGT deals with coalitions as elementary items, NGT deals with strategic individual behavior. Comparison of the game theories is in Table 1. The enlisted properties are important for studying non-cooperative fundamentals of individually motivated social behavior. type of a mapping individual action individual motivation
explicit allocation of players over coalitions inter-coalition externalities intra-coalition externalities
CGT a nite set to a point no no sometimes yes no
NGT a vector to a vector always always
no vague always, but with vague coalition de nition
Cooperative game theories are based on the notion that a coalition, a subset of all players, moves as a whole unit only. This approach seems somewhat simpli ed. Usually economic agents are self-interested, and do not necessarily make the same move even being together. From another side non-cooperative approach is based on a notion that every player is able to make individual decisions, but there is a low interest to partitioning players into coalitions or coalition structures.1
Studying formation of only one coalition from a non-cooperative game, was
introduced by Nash, [
The main complication for a non-cooperative coalition structure formation stems from the necessity to describe complex inter and intra coalition interactions while forming multiple coalition structures.
Cooperative game theory equilibrium concepts (also the strong Nash
equilibrium) evade such issues. Consider an example with 10 members in a committee,
which make the grand coalition. Let there are 5, who do not agree and
deviate from some joint agreement. Do they have the same reason and deviate as
one group, ve different reasons and deviate independently in ve groups, two
reasons and deviate in some groups of two and three, etc? And every deviator
may have more than one deviating strategy inside a deviating group. Deviating
groups may have internal con icts, there could be con icts between those who
stay and those who deviate, or between deviators from different groups. These
questions are different from those addressed by Aumann [
The central idea of the presented model is to incorporate possible cases of deviation into individual strategy sets of players. This is done by parametrizing possible coalition structures by maximum coalition size. A constructed game satis es properties in Table 1, and has an equilibrium in mixed strategies. As a result it is possible to study deviations of more than one player. The game differs from those existing in CGT and NGT. Varying a maximum coalition size we construct a family of games.
Section 2 contains an example of a game, Section 3 presents a mechanism to construct such games. The last Section 4 shows an example with preferences over coalition structures for an equilibrium re nement. The proof is in Appendix. 2
Example There are 2 players, i = 1; 2. They can make choices over a desirable coalition structure, indexed as a = ff1g; f2gg, if a player chooses to be alone, and indexed t = f1; 2g, if a player chooses to be together.2 A player has two strategies N C 1 The terms a coalition structure and a partition of players are considered as synonimes. 2 An example with preferences over coalition structures in in Section 4. and C for every coalition structure.3 A set of strategies of i is Si(K = 2) = fN Cia; Cia; N Cit; Citg, i = 1; 2. Table 2 presents strategies and outcomes of the game. A cell contains a payoff pro le and a nal coalition structure. Every strategy pro le is mapped to the pair: a payoff pro le and a coalition structure. In the equilibrium a player uses mixed strategies Cia; Cit with equal probabilities. There are 4 equilibria outcomes with payoff pro les ( 2; 2), all being inefficient.
The example uses a unanimous rule for coalition formation, the grand coalition f1; 2g can be formed only if both choose it. Otherwise a player obtains the singleton coalition. From twelve possible strategy pro le only four result in the grand coalition. Table 2 presents a game with two types of externalities, inter-coalition ff1g; f2gg and intra-coalition in f1; 2g. So the example satis es all desirable properties from Table 1. N C1;a N1;a N C1;t
C1;t
N C2;a (0;0) ff1g,f 2g g
(3;-5) ff1g; f2gg
(0;0) ff1g,f 2g g
(3;-5) ff1g; f2gg
C2;a (-5;3) ff1g; f2gg ( 2; 2)⋆;⋆⋆ ff1g; f2gg
(-5;3) ff1g; f2gg ( 2; 2)⋆⋆ ff1g; f2gg
N C2;t (0;0) ff1g,f 2g g
(3;-5) ff1g; f2gg (0;0) f1, 2 g (3; 5) f1; 2g
C2;t (-5;3) ff1g; f2gg ( 2; 2)⋆⋆ ff1g; f2gg ( 5; 3) f1; 2g ( 2; 2)⋆⋆ f1; 2g
For the coalition structure ff1g; f2gg with a maximum coalition size K = 1 every player has two equilibrium strategies. A respective equilibrium is marked with an upper star, and it is inefficient.
For the coalition structure f1; 2g a player has two more equilibrium
strategies. Final equilibria are marked with two upper stars, . The equilibria belong
to different coalition structures, what make this game be a stochastic game,
Shapley, [
The presented example let players think that they can deviate either alone or together. If both can deviate, then i has and anticipate another has also the following strategies: a move within the same or a different coalition structure with strategies N C or C for each case. Every such possibility is in individual strategy set Si. 3 For simplicity of the motivating example players do not have preferences over coalition structures, used in example with introvert and extravert players further.
A game A game is parametrized by a number K, K = 1; : : : ; N , a size of maximum coalition size in any feasible coalition structure. The parameter K has two meanings: no more than K agents are required to make this largest coalition, and at the same this coalition needs no more than the same K agents to dissolve. Every player has a set of strategies for every feasible coalition structure. A strategy prole of all players is mapped into a coalition structure (an allocation of players into coalitions) and a payoff pro le for all players. Payoffs are de ned separately for every feasible coalition structure.
De nition 1 (a simultaneous coalition structure formation game). A non-cooperative game for coalition structure formation with maximum coalition size K is
(K) = ⟨N; fK; P(K); R(K)g ; (Si(K); Ui(K))i2N ⟩ ; where fK; P(K); R(K)g - coalition structure formation mechanism, K is maximum coalition size, P(K) is a family of allowed coalition structures, R(K) is a family of coalition structure partition rules, (Si(K); Ui(K))i2N are properties of players (individual strategies and payoffs), such that:
i2N Si(K) R!(K) {P(K); (Ui(K) = fUi(P ) : P 2 P(K)g)i2N }
Every individual strategy set Si(K) is a topological space, and every family of utility functions Ui(K) is integrable and bounded over i2N Si(K).
.
De nition 2 (an equilibrium in a game (K)). For a non-cooperative game (K) a mixed strategies pro le (K) = ( i (K)) is an equilibrium if for i2N k K, and for every player i 2 n(k) a i (K), does not generate an individual every subset n(k) from N , with a size 1 deviation from an equilibrium, 8 i(K) ̸= gain:
EUi (K) ( i (K); i(K))
EUi (K) ( i(K); i(K)): De nition of an equilibrium makes a claim only about strategy pro les, but not about resulting coalition structures.
Theorem 1 (existence). An equilibrium for a game 1; : : : ; N . (K) exists for any K =
In short, a proof follows from standard properties of nite number of bounded integral operators with a nal application of a xed point theorem. If every Si(K) is a topological space, then we can always de ne a dual space of probability measure ∆i(Si) on it, ∆i(Si) is a set of mixed strategies, with a weak convergence. Then for every i 2 N expected utility operator EUi (K) is bounded, continuous and compact. Finally a xed point theorem is applied. Complete proof is in Appendix.
An increment in K generates a family of nested games with nested components: P(K) P(K + 1), Si(K) Si(K + 1), Ui(K) Ui(K + 1), for 8i 2 N and every K = 1; : : : ; N 1.
De nition 3 (family of nested games).
A family of games G = f (K) : K = 1; : : : ; N g is nested if : (K = 1) : : : (K) : : : (K = N ); i.e. for any two games (K) and (K + 1) there is P(K) P(K + 1), R(K) R(K + 1), Si(K) Si(K + 1), Ui(K) Ui(K + 1), for every i 2 N and every K = 1; : : : ; N 1.
Clearly, every game in a family has an equilibrium in mixed strategies 3.1
Why not to use a "threat", Nash (1953) In the paper on cooperative behavior Nash (1953) offered to used a \threat "as a basic concept for coalition formation analysis. Further development of this concept was transformed into a \blocking coalition "(Aumann, 1960).
The reason not to take them for non-cooperative coalition structure formation is the following. Consider a strategy pro le from only part of players. Let this pro le be a threat to someone, beyond this subset. The threatening players may produce externalities for each other (and negative externalities not excluding!). How credible could be such threat? From an other side, there may be some other player beyond the subset of players who may obtain a bonanza from this threat. But this bene ciary may not join the group due to some intra-group negative externalities for members or from members of this group. Resulting internal complexity and recursive nature of the example was the reason not to use a threat and blocking coalition concepts to establish non-cooperative formation of coalition structures. 4
Equilibrium re nement in the example Non-cooperative game theory extensively studied re nement of the Nash equilibrium. We can demonstrate equilibrium re nement for the game above with an introduction of individual preferences over coalition structures. Let player i = 1 be an \extrovert" and always prefers to be together, in f1; 2g, but player i = 2 is an \introvert" and always prefers to be alone ff1g; f2gg. Player i = 1 has an additional gain from being together (in comparison to Table 2) ϵ, 0 < ϵ, from being together with another. From another side player i = 2 has an additional gain from being alone, , 0 < .
Payoffs of the Table 3 are adjusted according to these assumptions and present the payoff matrix for the new game. Using the rule of unanimous agreement for coalition formation the grand coalition, f1; 2g, can never be formed, what leaves only one equilibrium payoffs ( 2; 2) for the game in ff1g; f2gg. Players differ in number of equilibrium strategies. Player i = 2 has one equilibrium strategy C2;a. Player i = 1 has two pure equilibrium strategies, C1;a and C1;t and mixes them with equal weights. Equilibrium for K = 1 is labeled with one star, ⋆, for K = 2 with two starts, ⋆⋆
If both players are extroverters with a premium ϵ > 0 for being together in f1; 2g, then a change in a game from K = 1 to K = 2 changes the equilibrium strategy pro le, and a resulting equilibrium coalition structure as well. Table 4 contains payoffs for this game. The additional payoff makes players form only the grand coalition f1; 2g with a unique equilibrium, but a resulting payoff is still inefficient. The paper suggest a new family of simultaneous non-cooperative games which satisfy the following criteria: be non-cooperative, be able to form multiplecoalition structures and to contain two types of externalities, intra and inter - coalition. Further application of the proposed mechanism to follow in the next papers. Earlier version of the paper with more applications was published at SSRN.
Acknowledgments. Special thanks for the support to Fuad Aleskerov, Lev Gelman, Dimitrios Tsomocos, Marc Kelbert, Nadezhda Likhacheva, Olga Pushkarev, Shlomo Weber and some others. Earlier version of the paper was published at SSRN and at arXiv. Appendix. Proofs Theorem 1. Let K be a maximum size of a coalition. For xed K a game (K) has the Nash equilibrium in mixed strategies.
The parameter K is omitted everywhere below for simplicity, besides expected utility.
Let Si be a topological space for every i 2 N . Let B(Si) be -algebra on Si, and
the pair (Si; B(Si)) be a measurable set. Let a non-negative measure ∆i on Si
be a mapping ∆i : B(Si) ! [0; 1], and (Si; B(Si); ∆i(Si)) be a measure space of
mixed strategies with ∆i(Si) = 1. By theorem 5 from [
Lemma 1. The space (Si; B(Si); ∆i(Si)) is complete.
Proof. Let i, be a mixed strategy, i 2 ∆i, and { i(k)}k1=1 be a sequence of mixed strategies of i. All the sequences in (Si; B(Si); ∆i) are bounded. By Bolzano-Weirstrass theorem every bounded sequence has a least one limit point. Let i(0) be a limit point of a sequence { i(k)}k1=1 , and ∫
Si
i(0)(si)dsi = lim
k!1 Si
∫
(k)(si)idsi:
Existence of a limit point in the weak convergence sense follows from the weak
compactness property of the set ∆i, by Prohorov's theorem, [
A set of probability measures ∆ i := (∆j )j̸=i of all other players besides i is bounded. Let i be a mixed strategy of all other players, i 2 ∆ i.
Let Ui :
i2N Si ! R+ be a payoff function of i, continuous on Si √∫Si S (Ui(si; s i))2 dsids i < 1.
i
We will use the word operator to emphasize, that player i controls only own strategies, variables indexed with i, but does not control variables indexed with i controlled by other players. Expected utility operator of i in a game (K) is a Lebegue integral
S i and i) = ∫ Proof. Let limk!1 ∫Si i(k)(si)dsi = ∫Si i(0)(si)dsi, where { i(k)}k1=1 weakly converging sequence from ∆i. Then is a bounded i
∫ ) = lim k!1 Si S i
Ui (si; s i) i(k)(si) i(s i)d(si)d(s i) Ui (si; s i) i(k)(si) i(s i)d(si)d(s i) = EUiK ( i(0); ) i ; = lim EUiK ( i(k); k!1 ∫
i) inherits compactness and weak convergence Lemma 2. The sequence {EUiK ( i(k); ∆ i. i )}1 k=1 Proof. is continuous on ∆i, 8 lim (EUiK ( i(k); ki!1 = lim k!1 ( ∫
Let Fi ( i) = arg max i2∆i EUiK ( i; i), Fi : ∆i ! ∆ i. Operator Fi is a best response operator, it is bounded, compact and continuous.
Best response correspondence Fi determines the best mixed strategies of i to maximize expected utility given mixed strategy pro le from other players. Expected utility operator EUiK ( i; i) maps a convex, closed, compact set ∆i, Fi ∆i, to a convex, closed, compact set.
Theorem 3. Let ∆i be a set of probability measures of i 2 N , and Xi = EUiK (∆i; ∆ i) be a bounded and compact set of i′s expected utility values. Then the set Fi(X i) = arg max i2∆i(Si) EUiK ( i; i) is also compact. Proof. The set X i is a compact set. Let { i(ki)}k1i=1 be a sequence from ∆i. For every point i(k) we take one of the pre-images X(ki), Fi (X(ki)) = i(k). The set Xi is compact, then from the sequence {X(ki)}k1=1 2 X i we can extract a converging sub-sequence {X(ki(r))}1
k(r)=1 By continuity of Fi(X i) on Xi at X(0ii) there is Fi (X(0ii)) = i(0i)
, which converges to X(0ii) 2 X i.
(k(r)) = Fi (X(ki(r))) i ! Step 3 Fixed point argument for the game
To apply xed point theorem we construct a system of N equations and demonstrate existence of a xed point for the whole system. Let a vector operator EU K ( ) = (EUiK ( i; i))i2N be a list of expected utility operators of all players. By the Tykhonov theorem the set of expected payoff values EU K (∆), s.t. ∆ = ∆i ∆ i, is compact, ∆ i = j̸=i∆i. Thus the set EU K (∆) is also bounded and continuous over the set of probability measures, as every component of EUiK (∆i; ∆ i) has this property. Let k be a number of a probability measure (mixed strategy) of i in a sequence of probability measures {{ i(k)}1 } in the sense of the weak convergence, s.t. i(k) wea!k i(0). We want to construct a nite collection of converging expected utility operators.
For every i exists an argmax operator:
Fi(
i) : ∆ i 7! ∆i; i.e. the best response operator, that allows to choose the best mixed strategy from ∆i in response to i from ∆ i, such that where ∆i is a bounded, closed, convex set with weak convergence. Let Fi( i) = arg max EUiK ( i; i2∆i
i) ; {F (k)} = i { arg max EUiK ( i(k); i(k)2∆ i) } 1 k=1 be a sequence of vectors of operators.
Let (F1(k); : : : ; F N(k))1 k=1
= ( arg max EU1K ( 1(k); 1(k)2∆1 1); : : : ; arg max N(k)2∆N
EUNK ( N(k);
N ) ) 1 k=1 (2) be a sequence of best response operators.
Every vector operator F (k) = (Fi(k))
i2N theorem it is also a compact and closed set. Every mapping F (k) transforms a convex, closed, compact set ∆ = (∆i)i2N into itself.
is a nite vector, and by Tykhonov k=1 Lemma 3 (Schauder). Any operator F compact on (∆i)i2N has a uniform nite dimensional operaltiomrsit(oFn1(k∆); :=: :(;∆FiN()ki)2)N1as a sequence of continuous
, and maps (∆i(Si); ∆ i(S i)) ! (∆i(Si); ∆ i(S i)).
Proof. Operator F is a compact operator, hence F (∆) is a compact set. Let there is a sequence of positive numbers fϵ1; ϵ2; ϵk; : : :g, which converges to zero. Let y 2 F (∆) be an element of ∆. For every small positive ϵk we construct L(k) = fy1(k); : : : ; yN(k)g, y(k) = (y1(k); : : : ; yN(k)) 2 F (∆), where for every i there is yi(k) 2 f i(k)gi2N . All L(k) are continuous on a mixed strategy pro le ( i(k)) in a sense of the weak convergence, and denote i2N ∥y y(k)∥ = maxi2N ∫Si S i jyi(k)(si) yi(si)jy i(s i)dsids i. De ne on F (∆) an operator J (k) such that for any y 2 F (∆) there is where
J (k)(y) = ∑iN=1 i(k)(y)yi(k) ;
i=1 i(k)(y) ∑N i(k)(y) = { ϵk 0; ∥y y(k) ; i ∥ ∥y ∥y yyi((kk))∥ < ϵk : i ∥ > ϵk (k)(y) . Then i ∑1N i(k)(y) ∥y
J (k)(y)∥ = y Operator J (k)(y) is well de ned for every y 2 F (∆) as i(k) 0 and i(k) > 0 at least for one j. Operator J (k)(y) is continuous on F (∆). This follows from that all i(k)(y) are continuous over y, ∑iN=1 i(k)(y) is continuous over y. For i=1 i(k)(y) > 0, from where follows continuity of every y 2 F (∆) there is ∑N ∑iN=1 i(k)(y)yi(k)
i=1 i(k)(y) ∑N = ∑iN=1 i(k)(y)(y
i=1 i(k)(y) ∑N yi(k)) ∑iN=1 i(k)(y)∥y
i=1 i(k)(y) ∑N y(k) i ∥
∑iN=1 i(k)(y) ϵk ∑N i=1 i(k)(y) = ϵk: If there is ∥y y(k) ϵk then a corresponding coefficient i(k)(y) = 0. Let F (k) = J (k)i(F∥ ), then for any 2 ∆ there is a sequence of operators {F (k)}k1=1 such that ∥F
F (k) ∥ = ∥F
F (k)(F )∥ ϵ; for any
For every y(k) there is y(k) 2 F (∆), so the values of the constructed operators belong to a convex closure of F (∆).
Lemma 4. Let a sequence of operators {F (k)}1 k=1 be continuous on ∆ and it uniformly converges to an operator F on ∆. Let L(k) = F (k)(∆), k = 1; 2; : : :. Then the set L = [k1=1L(k) is compact.
Proof. According to the Lemma above an operator F (0) is compact, as there is a sequence of operators, {F (k)}1
k=1, which converges to F (0). Then for any ϵk > 0 and when k k, for every 2 L(k) there is y(0) 2 L(0) such that ∥y y(0)∥ < ϵk. This is possible as y is an element from L(k) and is one of pre-images of y under the mapping F (k). So we can take y(0) = F (0) . Now we construct the set [k=1L(k). This set is compact. We need to show k that it is an ϵ-net for L. Let y 2 K. If y 2 [k=1L(k), then the result of the k Lemma is trivial. If y 2 L(k) for k > k, then there is y(0) 2 L(0), such that ∥y y(0)∥ < ϵk. Thus [k1=k+1L(k) is compact for ϵk from set L, and thus L is compact.
Theorem 4 (Schauder xed point theorem). If a compact operator F maps a bounded closed convex set ∆ into itself, then the mapping has a xed point, 2 ∆, F = .
The proof follows Sobolev and Ljusternik, [
Proof. Take a sequence of positive fϵ(k)gk1=1, converging to zero, and as above construct a sequence of continuous nite-dimension operators fF (k)gk1=1, which uniformly converges on ∆ to F .
The in nite set of all probability distributions ∆ is convex, fF (k)gk1=1 = f (k)gk1=1 ∆ for every 2 ∆. Let X(k) be a nite dimension subspace with the set F (k)(∆), F (k)(∆) X(k). Take the operator F (k) on the subset ∆(k) = ∆ \ F (k) from X(k). The set ∆(k) is also a closed convex set. As F (k)(∆) ∆ and F (k) (∆) ∆(k), then F (k)(∆) ∆(k), and therefore F (k)(∆(k)) ∆.
Thus the operator F (k) in ∆(k), ∆(k) ∆, maps a closed convex set ∆(k). By the Bauer xed-point theorem there is a xed point of this mapping, i.e. F (k) (k) = (k). From another side ∆(k) ∆, thus (k) is a xed point also for the mapping F (k)(∆). As the point (k) 2 F (k)(∆), and the sequence { (k)}k1=1 belongs to the set ∆~ = [k1=1F (k)(∆) ∆. Thus the set ∆~ is compact. Then from the sequence { (k)}1 k=1 we can extract a converging subsequence { (kr)}1
kr=1 and a limit of this subsequence is in ∆, as ∆ is closed.
We can de ne ∥F (kr) (kr); (0)∥ = maxi2N ∫Si S i (Fi(kr) (kir) (kr). We need to demonstrate that (0) is a xed point. This i F (kr) (kr) =
i i follows from ∥F (0); (0)∥ ∥F (0); F (kr)∥ + ∥F (kr); F (kr) (kr)∥ + ∥F (k) (kr); (0)∥ = = ∥F (0); F (kr)∥ + ∥F (kr); F (k) (kr)∥ + ∥ (kr); (0)∥: For any xed ϵk > 0 we choose k′ be big enough that for any k > k′ there is ∥ (k); (0)∥ < ϵk=3 and ∥F (0); F k∥ < ϵk=3.
Then we choose k′′ be big enough that for k k′′ there is ∥F ; F (k)) < ϵk=3 is uniform on ∆ for all { (k~)}1 . Then for some k maxfk′; k′′g there is k~=k ∥F (0); (0)∥ < ϵk=3. As ϵk > 0, then this is possible only if F ϵ(0) = ϵ(0). Then ϵ(0) is a xed point.
The proof does not depend on K, thus every game in the family G has an equilibrium in mixed strategies.