=Paper=
{{Paper
|id=Vol-1975/paper20
|storemode=property
|title=Formation of Coalition Structures as a Non-Cooperative Game
|pdfUrl=https://ceur-ws.org/Vol-1975/paper20.pdf
|volume=Vol-1975
|authors=Dmitry Levando
|dblpUrl=https://dblp.org/rec/conf/aist/Levando17
}}
==Formation of Coalition Structures as a Non-Cooperative Game==
https://ceur-ws.org/Vol-1975/paper20.pdf
Formation of Coalition Structures as a
Non-Cooperative Game
Dmitry Levando
National Research University Higher School of Economics, Moscow, Russia
dlevando@hse.ru
Abstract. 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.
Keywords: Non-cooperative games, Nash equilibrium, cooperative games
1 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 behav-
ior. Comparison of the game theories is in Table 1. The enlisted properties are
important for studying non-cooperative fundamentals of individually motivated
social behavior.
Table 1. Comparison of game theories
CGT NGT
type of a mapping a finite set to a point a vector to a vector
individual action no always
individual motivation no always
explicit allocation
yes no
of players over coalitions
inter-coalition externalities sometimes vague
always, but
intra-coalition externalities no
with vague coalition definition
Cooperative game theories are based on the notion that a coalition, a sub-
set of all players, moves as a whole unit only. This approach seems somewhat
simplified. 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 deci-
sions, 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, [6], and is known now as Nash Program, Serrano, [8].
Practice of social analysis and social design requires studying non-cooperative
and simultaneous formation of multiple coalitions, or coalition structures. This
makes Nash program be too restrictive. Importance of studying externalities be-
tween coalitions, a case impossible within the Nash Program, was mentioned by
Maskin, [4].
The main complication for a non-cooperative coalition structure formation
stems from the necessity to describe complex inter and intra coalition interac-
tions while forming multiple coalition structures.
Cooperative game theory equilibrium concepts (also the strong Nash equilib-
rium) 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 devi-
ate from some joint agreement. Do they have the same reason and deviate as
one group, five different reasons and deviate independently in five 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 conflicts, there could be conflicts between those who
stay and those who deviate, or between deviators from different groups. These
questions are different from those addressed by Aumann [1] in the strong Nash
equilibrium and by Bernheim et all [2] in the coalition proof equilibrium.
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
satisfies 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 refinement. 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 = {{1}, {2}}, if a player chooses to be alone, and indexed
t = {1, 2}, 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 synon-
imes.
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) =
{N Cia , Cia , N Cit , Cit }, i = 1, 2. Table 2 presents strategies and outcomes of
the game. A cell contains a payoff profile and a final coalition structure. Every
strategy profile is mapped to the pair: a payoff profile and a coalition structure.
In the equilibrium a player uses mixed strategies Cia , Cit with equal probabilities.
There are 4 equilibria outcomes with payoff profiles (−2; −2), all being inefficient.
The example uses a unanimous rule for coalition formation, the grand coali-
tion {1, 2} can be formed only if both choose it. Otherwise a player obtains
the singleton coalition. From twelve possible strategy profile only four result in
the grand coalition. Table 2 presents a game with two types of externalities,
inter-coalition {{1}, {2}} and intra-coalition in {1, 2}. So the example satisfies
all desirable properties from Table 1.
Table 2. Payoff for the unanimous coalition structure formation rule: the same effi-
cient payoffs (0;0) in different partitions. What is a cooperation then?
N C2,a C2,a N C2,t C2,t
(0;0) (-5;3) (0;0) (-5;3)
N C1,a
{{1},{ 2} } {{1}, {2}} {{1},{ 2} } {{1}, {2}}
(3;-5) (−2; −2)⋆,⋆⋆ (3;-5) (−2; −2)⋆⋆
N1,a
{{1}, {2}} {{1}, {2}} {{1}, {2}} {{1}, {2}}
(0;0) (-5;3) (0;0) (−5; 3)
N C1,t
{{1},{ 2} } {{1}, {2}} {1, 2 } {1, 2}
(3;-5) (−2; −2)⋆⋆ (3; −5) (−2; −2)⋆⋆
C1,t
{{1}, {2}} {{1}, {2}} {1, 2} {1, 2}
For the coalition structure {{1}, {2}} 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 {1, 2} a player has two more equilibrium strate-
gies. Final equilibria are marked with two upper stars, ∗∗ . The equilibria belong
to different coalition structures, what make this game be a stochastic game,
Shapley, [9]. Stochastic property appears here not from outside shock, but from
strategic actions of the players.
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 coali-
tion structures, used in example with introvert and extravert players further.
3 A game
A game is parametrized by a number K, K = 1, . . . , N , a size of maximum coali-
tion 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 pro-
file of all players is mapped into a coalition structure (an allocation of players
into coalitions) and a payoff profile for all players. Payoffs are defined separately
for every feasible coalition structure.
Definition 1 (a simultaneous coalition structure formation game). A
non-cooperative game for coalition structure formation with maximum coalition
size K is
⟨ ⟩
Γ (K) = N, {K, P(K), R(K)} , (Si (K), Ui (K))i∈N ,
where {K, P(K), R(K)} - coalition structure formation mechanism, K is maxi-
mum 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))i∈N are properties of
players (individual strategies and payoffs), such that:
R(K) { }
×i∈N Si (K) → P(K), (Ui (K) = {Ui (P ) : P ∈ P(K)})i∈N
Every individual strategy set Si (K) is a topological space, and every family
of utility functions Ui (K) is integrable and bounded over ×i∈N Si (K).
.
Definition 2 (an equilibrium in a game ( Γ (K)).
) For a non-cooperative game
∗ ∗
Γ (K) a mixed strategies profile σ (K) = σi (K) is an equilibrium if for
i∈N
every subset n(k) from N , with a size 1 ≤ k ≤ K, and for every player i ∈ n(k) a
deviation from an equilibrium, ∀σi (K) ̸= σi∗ (K), does not generate an individual
gain:
Γ (K) ( ∗ ∗
) Γ (K) ( ∗
)
EUi σi (K), σ−i (K) ≥ EUi σi (K), σ−i (K) .
Definition of an equilibrium makes a claim only about strategy profiles, but not
about resulting coalition structures.
Theorem 1 (existence). An equilibrium for a game Γ (K) exists for any K =
1, . . . , N .
In short, a proof follows from standard properties of finite number of bounded
integral operators with a final application of a fixed point theorem. If every Si (K)
is a topological space, then we can always define a dual space of probability mea-
sure ∆i (Si ) on it, ∆i (Si ) is a set of mixed strategies, with a weak convergence.
Γ (K)
Then for every i ∈ N expected utility operator EUi is bounded, continu-
ous and compact. Finally a fixed point theorem is applied. Complete proof is in
Appendix.
An increment in K generates a family of nested games with nested compo-
nents: P(K̄) ⊂ P(K̄ + 1), Si (K̄) ⊂ Si (K̄ + 1), Ui (K̄) ⊂ Ui (K̄ + 1), for ∀i ∈ N
and every K̄ = 1, . . . , N − 1.
Definition 3 (family of nested games).
A family of games G = {Γ (K) : K = 1, . . . , N } 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 ∈ 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 profile from only part of players. Let this
profile 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 beneficiary 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 refinement in the example
Non-cooperative game theory extensively studied refinement of the Nash equi-
librium. We can demonstrate equilibrium refinement 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 {1, 2}, but player i = 2
is an “introvert” and always prefers to be alone {{1}, {2}}. 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 agree-
ment for coalition formation the grand coalition, {1, 2}, can never be formed,
what leaves only one equilibrium payoffs (−2; −2) for the game in {{1}, {2}}.
Players differ in number of equilibrium strategies. Player i = 2 has one equilib-
rium 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, ⋆⋆
Table 3. Payoff for a game when player 1 is ”extrovert” and player 2 is ”introvert”.
N C2,a C2,a N C2,t C2,t
(0; 0 + δ) (−5; 3 + δ) (0; 0 + δ) (−5; 3 + δ)
N C1,a
{{1}, {2}} {{1}, {2}} {{1}, {2}} {{1}, {2}}
(3; −5 + δ) (−2; −2 + δ)⋆,⋆⋆ (3; −5 + δ) (−2; −2 + δ)
C1,a
{{1}, {2}} {{1}, {2}} {{1}, {2}} {{1}, {2}}
(0; 0 + δ) (−5; 3 + δ) (0 + ϵ; 0) (−5 + ϵ; )
N C1,t
{{1}, {2}} {{1}, {2}} {1, 2} {1, 2}
(3; −5 + δ) (−2; −2 + δ)⋆⋆ (3 + ϵ; −5) (−2 + ϵ; −2)
C1,t
{{1}, {2}} {{1}, {2}} {1, 2} {1, 2}
If both players are extroverters with a premium ϵ > 0 for being together in
{1, 2}, then a change in a game from K = 1 to K = 2 changes the equilibrium
strategy profile, 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 {1, 2} with a unique equilibrium, but a resulting payoff is
still inefficient.
Table 4. Payoff for two extrovert players who prefer to be together. Uniqueness of an
equilibrium is fixed.
L2,a H2,a L2,t H2,t
(0;0) (-5;3) (0;0) (-5;3)
L1,a
{{1}, {2}} {{1}, {2}} {{1}, {2}} {{1}, {2}}
(3;-5) (−2; −2)⋆ (3;-5) (−2; −2)
H1,a
{{1}, {2}} {{1}, {2}} {{1}, {2}} {{1}, {2}}
(0;0) (-5;3) (0 + ϵ; 0 + ϵ) (−5 + ϵ; 3 + ϵ)
L1,t
{{1}, {2}} {{1}, {2}} {1, 2} {1, 2}
(3;-5) (-2;-2) (3 + ϵ; −5 + ϵ) (−2 + ϵ; −2 + ϵ)⋆⋆
H1,t
{{1}, {2}} {{1}, {2}} {1, 2} {1, 2}
5 Conclusion
The paper suggest a new family of simultaneous non-cooperative games which
satisfy the following criteria: be non-cooperative, be able to form multiple-
coalition 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 Gel-
man, 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.
References
1. Aumann, R.Y., Acceptable points in games of perfect information. Pacific
Journal of Mathematics, 10(2), 381-417 (1960)
2. Bernheim, B.D., Peleg, B. and Whinston, M.D., Coalition-proof nash equi-
libria i. concepts. Journal of Economic Theory, 42(1), 1-12 (1987)
3. Lyusternik, L.A. and Sobolev, V.I., A short course in functional analysis.
Vysshaya Shkola, Moscow (1982)
4. Maskin, E., Commentary: Nash equilibrium and mechanism design. Games
and Economic Behavior, 71(1), 9-11 (2011)
5. Nash, J., Non-cooperative games. Annals of mathematics, 286-295 (1951)
6. Nash, J., Two-person cooperative games. Econometrica: Journal of the
Econometric Society, 128-140 (1953)
7. Schilling, R.L., Measures, integrals and martingales. Cambridge University
Press, 2017.
8. Serrano, R., Fifty years of the Nash program, 1953-2003, (2004).
9. Shapley, L.S., Stochastic games. Proceedings of the national academy of sci-
ences, 39(10), 1095-1100 (1953)
Appendix. Proofs
Theorem 1. Let K be a maximum size of a coalition. For fixed K a game Γ (K)
has the Nash equilibrium in mixed strategies.
The parameter K is omitted everywhere below for simplicity, besides ex-
pected utility.
Step 1 Preliminary step.
Let Si be a topological space for every i ∈ 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 [7] the space ∆i can be
uniquely assigned. The space (Si , B(Si ), ∆i ) has weak convergence, what we do
not prove here.
Lemma 1. The space (Si , B(Si ), ∆i (Si )) is complete.
{ }∞
(k)
Proof. Let σi , be a mixed strategy, σi ∈ ∆i , and σi be a sequence
k=1
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.
(0) (k)
Let σi be a limit point of a sequence σi , and
k=1
∫ ∫
(0)
σi (si )dsi = lim σ (k) (si )i dsi .
Si k→∞ Si
Existence of a limit point in the weak convergence sense follows from the weak
compactness property of the set ∆i , by Prohorov’s theorem, [7]. From this im-
mediately follows completeness of the set of mixed strategies ∆i .
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 ∈ ∆−i .
Step 2 Expected utility of one player.
√∫Let Ui : ×i∈N Si → R+ be a payoff function of i, continuous on Si × S−i and
2
Si ×S
(Ui (si , s−i )) dsi ds−i < ∞.
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
∫
K Γ (K)
EUi (σi , σ−i ) := EUi (σi , σ−i ) = Ui (si , s−i ) σi (si )σ−i (s−i )d(si )d(s−i ).
Si ×S−i
Probability measures for all players and each partition-contingent payoffs
Ui (si , s−i ) were defined above, so expected utility EUiK (σi , σ−i ) is well defined.
Theorem { 2. Expected
}∞ utility operator EUiK (σi , σ−i ) maps
{ a weakly
( converging
)}∞
(k) K (k)
sequence σi into a bounded converging sequence EUi σi , σ−i .
k=1 k=1
∫ ∫ { }∞
(k) (0) (k)
Proof. Let limk→∞ Si σi (si )dsi = Si σi (si )dsi , where σi is a bounded
k=1
weakly converging sequence from ∆i . Then
( ) ∫
(k) (k)
lim EUiK σi , σ−i = lim Ui (si , s−i ) σi (si )σ−i (s−i )d(si )d(s−i )
k→∞ k→∞ S ×S
−i
∫ i
( )
(k) (0)
= Ui (si , s−i ) σi (si )σ−i (s−i )d(si )d(s−i ) = EUiK σi , σ−i ,
Si ×S−i
Expected utility EUiK (σi , σ−i ) inherits compactness and weak convergence
over ∆i (Si ).
{ ( )}∞
(k)
Lemma 2. The sequence EUiK σi , σ−i is continuous on ∆i , ∀σ−i ∈
k=1
∆−i .
Proof.
( ( ) ( ))
(k) (0 )
lim EUiK σi , σ−i − EUiK σi i , σ−i
ki →∞
(∫ )
( )
(k) (0i )
= lim Ui (si , s−i ) σi (si ) − σi (si ) σ−i (s−i )dsi ds−i
k→∞ Si ×S−i
∫ (∫ )
( )
(k) (0 )
≤ Ui (si , s−i )dsi ds−i lim σi (si ) − σi i (si ) σ−i (s−i )dsi ds−i =0
Si ×S−i ki →∞ Si ×S−i
(1)
Let Fi (σ−i ) = arg maxσi ∈∆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 profile 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 ∈ 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σi ∈∆i (Si ) EUiK (σi , σ−i ) is also compact.
{ }∞
(k )
Proof. The set X−i is a compact set. Let σi i be a sequence from ∆i .
ki =1 ( )
(k) (k) (k) (k)
For every point σi we take one of the pre-images X−i , Fi X−i = σi . The
{ }∞
(k)
set Xi is compact, then from the sequence X−i ∈ X−i we can extract
{ }∞ k=1
(k(r)) (0 )
a converging sub-sequence X−i , which converges to X−ii ∈ X−i .
k(r)=1 ( )
(0 ) (k(r)) (k(r))
By continuity of Fi (X−i ) on Xi at X−ii there is σi = Fi X−i →
( )
(0 ) (0 )
Fi X−ii = σi i ∈ ∆i .
Step 3 Fixed point argument for the game
To apply fixed point theorem we construct a system of N equations and
demonstrate existence( of a fixed point
) for the whole system. Let a vector
operator EU K (σ) = EUiK (σi , σ−i ) i∈N be a list of expected utility oper-
ators 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
∞
(k)
probability measures σi in the sense of the weak convergence,
k=1 i∈N
(k) weak (0)
s.t. σi −−−→ σi . We want to construct a finite 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
Fi (σ−i ) = arg max EUiK (σi , σ−i ) ,
σi ∈∆i
where ∆i is a bounded, closed, convex set with weak convergence. Let
{ }∞
{ }
(k) (k)
Fi = arg max EUiK (σi , σ−i )
(k)
σi ∈∆
k=1
be a sequence of vectors of operators.
Let
( )∞
(k) (k)
F1 , . . . , F N =
k=1
( )∞
(k) (k)
arg max EU1K (σ1 , σ−1 ), . . . , arg max K
EUN (σN , σ−N ) (2)
(k) (k)
σ1 ∈∆1 σN ∈∆N
k=1
be a sequence of best response( operators.
)
(k)
Every vector operator F (k) = Fi is a finite vector, and by Tykhonov
i∈N
theorem it is also a compact and closed set. Every mapping F (k) transforms
a convex, closed, compact set ∆ = (∆i )i∈N into itself.
Lemma 3 (Schauder). Any operator F compact on (∆i )i∈N has a uniform
limit(on ∆ = (∆i )i∈N
) as a sequence of continuous finite dimensional opera-
∞
(k) (k)
tors F1 , . . . , FN , and maps (∆i (Si ), ∆−i (S−i )) → (∆i (Si ), ∆−i (S−i )).
k=1
The proof follows Sobolev and Ljusternik, (1976).
Proof. Operator F is a compact operator, hence F (∆) is a compact set.
Let there is a sequence of positive numbers {ϵ1 , ϵ2 , ϵk , . . .}, which converges
to zero. Let y ∈ F (∆) be an element of ∆. For every small positive ϵk
(k) (k) (k) (k)
we construct L(k) = {y1 , . . . , yN }, y (k) = (y1 , . . . , yN ) ∈ F (∆), where
(k) (k)
for every i there( is y)
i ∈ {σi }i∈N . All L(k) are continuous on a mixed
(k)
strategy profile σi in a sense of the weak convergence, and denote
∫
i∈N
(k)
∥y − y (k) ∥ = maxi∈N Si ×S−i
|yi (si ) − yi (si )|y−i (s−i )dsi ds−i . Define on
F (∆) an operator J (k) such that for any y ∈ F (∆) there is
∑N (k) (k)
(k) i=1 θi (y)yi
J (y) = ∑N (k)
,
i=1 θi (y)
where
{
(k) (k)
(k) ϵk − ∥y − yi ∥, ∥y − yi ∥ < ϵk
θi (y) = (k) .
0, ∥y − yi ∥ > ϵk
(k) (k)
Operator J (k) (y) is well defined for every y ∈ F (∆) as θi ≥ 0 and θi > 0
at least for one j. Operator J (k) (y) is continuous on F (∆). This follows from
(k) ∑N (k)
that all θi (y) are continuous over y, i=1 θi (y) is continuous over y. For
∑N (k)
every y ∈ F (∆) there is i=1 θi (y) > 0, from where follows continuity of
(k)
θ (y)
∑Ni (k) . Then
1 θi (y)
∑N (k) (k) ∑N (k) (k)
i=1 θi (y)yi i=1 θi (y)(y − yi )
∥y − J (k) (y)∥ = y − ∑N (k) = ∑N (k) ≤
i=1 θi (y) i=1 θi (y)
∑N
(k) (k) ∑N (k)
i=1 θi (y)∥y − yi ∥ i=1 θi (y)
≤ ∑N (k) ≤ ϵk ∑N (k)
= ϵk .
i=1 θi (y) i=1 θi (y)
(k) (k)
If there is ∥y − yi ∥ ≥ ϵk then a corresponding coefficient θi (y) = 0.
Let
{ (k)F} σ = J (F σ), then for any σ ∈ ∆ there is a sequence of operators
(k) (k)
∞
F k=1
such that
∥F σ − F (k) σ∥ = ∥F σ − F (k) (F σ)∥ ≤ ϵ,
for any σ ∈ ∆.
For every y (k) there is y (k) ∈ F (∆), so the values of the constructed operators
belong to a convex closure of F (∆).
{ }∞
Lemma 4. Let a sequence of operators F (k) 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 = ∪∞ k=1 L
(k)
is compact.
The proof follows Sobolev and Ljusternik, (1976).
Proof. According to the Lemma { (k) }above an operator F (0) is compact, as there
∞
is a sequence of operators, F k=1
, which converges to F (0) . Then for any
ϵk > 0 and when k̄ ≥ k, for every σ ∈ L(k) there is y (0) ∈ 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̄k=1 L(k) . This set is compact. We need to show
that it is an ϵ-net for L. Let y ∈ K. If y ∈ ∪k̄k=1 L(k) , then the result of the
Lemma is trivial. If y ∈ L(k) for k̄ > k, then there is y (0) ∈ L(0) , such that
∥y − y (0) ∥ < ϵk . Thus ∪∞ k=k̄+1
L(k) is compact for ϵk from set L, and thus L
is compact.
Theorem 4 (Schauder fixed point theorem). If a compact operator F
maps a bounded closed convex set ∆ into itself, then the mapping has a fixed
point, σ ∈ ∆, F σ = σ.
The proof follows Sobolev and Ljusternik, [3].
Proof. Take a sequence of positive {ϵ(k) }∞ k=1 , converging to zero, and as
above construct a sequence of continuous finite-dimension operators {F (k) }∞ k=1 ,
which uniformly converges on ∆ to F .
The infinite set of all probability distributions ∆ is convex, {F (k) }∞ k=1 =
{σ (k) }∞k=1 ⊂ ∆ for every σ ∈ ∆. Let X (k)
be a finite 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 fixed-point theorem there is a fixed point of this mapping, i.e.
F (k) σ (k) = σ (k) . From another side ∆(k) ⊂ ∆, thus σ (k) is a fixed point also
for the
{ (k)
(k)
}∞mapping F (∆). As the point σ (k) ∈ F (k) (∆), and the sequence
˜ = ∪ ∞
σ belongs to the set ∆ F (k) (∆) ⊂ ∆. Thus the set ∆ ˜ is
k=1 { k=1 }
(k) ∞
compact. Then from the sequence σ we can extract a converging
{ }∞ k=1
subsequence σ (kr ) kr =1 and a limit of this subsequence is in ∆, as ∆ is
closed. ∫ ( )
(k ) (k ) (0) (0)
We can define ∥F (kr ) σ (kr ) , σ (0) ∥ = maxi∈N Si ×S−i Fi r σ−ir − σi σ−i dsi ds−i ,
(k ) (k ) (k )
Fi r σ−ir = σi r . We need to demonstrate that σ (0) is a fixed point. This
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 fixed ϵ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 ′′
} that for k̄ ≥ k there is ∥F σ, F σ ) < ϵk̄ /3
{ enough
(k̄)
∞
is uniform on ∆ for all σ (k̃) . Then for some k̄ ≥ max{k ′ , k ′′ } 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 fixed point.
The proof does not depend on K, thus every game in the family G has an
equilibrium in mixed strategies.