=Paper=
{{Paper
|id=Vol-1987/paper51
|storemode=property
|title=New Coalition Equilibrium under Uncertainty
|pdfUrl=https://ceur-ws.org/Vol-1987/paper51.pdf
|volume=Vol-1987
|authors=Konstantin N. Kudryavtsev,Vladislav I. Zhukovskiy
}}
==New Coalition Equilibrium under Uncertainty==
https://ceur-ws.org/Vol-1987/paper51.pdf
New Coalition Equilibrium under Uncertainty
Konstantin N. Kudryavtsev Vladislav I. Zhukovskiy
South Ural State University Moscow State University
Lenin prospekt, 76, GSP-1, Leninskie Gory,
454080 Chelyabinsk, Russia 100109 Moscow, Russia
kudrkn@gmail.com zhkvlad@yandex.ru
Abstract
In this article, we suggest a new concept of an optimal solution in 3-
person game under uncertainty, that we call “strongly guaranteed coali-
tional equilibrium”. This equilibrium based on the concepts of Nash
and Berge equilibria obtained. We apply the concept of an optimal
solution that cannot increase the outcome of a deviant coalition. Then
we determine sufficient conditions of existence of a coalitional equilib-
rium using the Germeier resultant. These conditions can be reduced
to building a saddle point in a special antagonistic game that can be
effectively constructed on the mathematical model of the original game.
1 Introduction
We consider a three-person normal-form game with its mathematical model defined by the cortege
Γ = ⟨{1, 2, 3}, {Xi }i=1,2,3 , Y, {fi (x, y)}i=1,2,3 ⟩ .
Here, set {1, 2, 3} of index numbers of players, each of whom selects their own strategy xi ∈ Xi ⊂ Rni ,
i = 1, 2, 3, which results in formation of strategy profile
∏
3 ∑
3
x = (x1 , x2 , x3 ) ∈ X = Xi ⊂ Rn (n = ni ).
i=1 i=1
Uncertainty y ∈ Y ⊂ Rm is realized regardless of the actions of players. Within the set of pair X × Y , payoffs
functions fi (x, y) of each player (i = 1, 2, 3), values of which are called payoffs of player i, are defined.
Next, we follow the concept of “strongly guaranteed equilibrium” [Zhukovskiy, 2013]. Namely, we are consid-
ering a corresponding game (without uncertainty)
Γ3 = ⟨{1, 2, 3}, {Xi }i=1,2,3 , {fi [x]}i=1,2,3 ⟩ .
Here,
fi [x] = min fi (x, y) = fi (x, y (i) (x)) ∀x ∈ X, (i = 1, 2, 3).
y∈Y
Copyright ⃝
c by the paper’s authors. Copying permitted for private and academic purposes.
In: Yu. G. Evtushenko, M. Yu. Khachay, O. V. Khamisov, Yu. A. Kochetov, V.U. Malkova, M.A. Posypkin (eds.): Proceedings of
the OPTIMA-2017 Conference, Petrovac, Montenegro, 02-Oct-2017, published at http://ceur-ws.org
350
Study of conflicts that are mathematically represented by, in particular, by the three-person game Γ3 , is usually
conducted from the standard point of view that defines what players’ behavior should be considered optimal (ra-
tional, reasonable). Main concepts of optimality in the mathematical game theory are [Vorobyov, 1985] intuitive
concepts of profitability, stability, and justice. On stability is based the “dominant” in the noncooperative games
concept of Nash equilibrium [Nash, 1950], [Nash, 1951] as well as the heavily influenced by [Zhukovskiy, 1994]
Berge equilibrium, active equilibrium, and bargaining equilibrium. These and several other conditions of opti-
mality prevail in the non-coalitional game theory. In these, each conflict participant (player) usually pursues
their own aims; additionally, they cannot form coalitions with other players for determining their strategies. The
counterpart to the described case is the cooperative games [Zhukovskiy, 2009], in which any unions – coalitions –
of players for purpose of “scramble” for their common interests as well as the possibility unlimited negotiations
between players which result in choice and application of a common situation; of course, it is implied that “pacta
sunt servanda” (agreements must be kept). For optimality in the cooperative game theory are specific the con-
ditions of individual [Zhukovskiy, 2009] and collective [Zhukovskiy, 2009] rationality. Individual rationality lies
in that each player’s outcome is not less than their guaranteed outcome that each player can “guarantee” by
acting independently (applying their own maximin strategy). Collective rationality involves a vectorial maximum
obtained by consolidation of all players into one coalitions.
The present article heavily relies on the concept of a coalitional structure of a game (partitioning players into
pairwise disjoint subsets). For a three-person game Γ3 , five coalition structures are possible: P1 = {{1}, {2}, {3}},
P2 = = {{1, 2}, {3}}, P3 = {{1, 3}, {2}}, P4 = {{1}, {2, 3}}, P5 = {1, 2, 3}. Here, P1 corresponds to the non-
coalitional nature of a game and P5 corresponds to the coalitional nature of a game. The said conditions of
individual rationality can be formulated for a coalitional structure P1 . We will use the following notations: for
∀i ∈ {1, 2, 3} consider −i = {{1, 2, 3} \ {i}}, i.e. for i = 1 → −i = {2, 3}, for i = 2 → −i = {1, 3}, and, finally,
for i = 3 → −i = {1, 2}.
Then the condition of individual rationality for the strategy profile x∗ = (x∗1 , x∗2 , x∗3 ) ∈ X means that
fi = max min fi [xi , x−i ] =
xi ∈Xi x−i ∈X−i
(1)
= min fi [x0i , x−i ] ≤ fi0 [x∗ ], i = 1, 2, 3,
x−i ∈X−i
i.e. application of the maximin strategy x0i implies the following inequalities:
fi0 ≤ fi [x∗ ], i = 1, 2, 3. (2)
For the coalitional structure P5 in the game Γ3 : within the set of strategy profiles X ∗ ⊆ X strategy profile
x ∈ X ∗ ⊆ X is Pareto optimal in the three-criteria problem
∗
ΓX ∗ = ⟨X ∗ , {fi [x]}i=1,2,3 ⟩
if ∀x ∈ X ∗ the system of inequalities
fi [x] ≥ fi [x∗ ](i = 1, 2, 3),
of which at least one is strict, is incompatible. According to the Karlin lemma [Podinovskiy, 2007], if
∑
3 ∑
3
fi [x∗ ] = max∗ fi [x], (3)
x∈X
i=1 i=1
then the strategy profile x∗ is Pareto optimal in the problem ΓX ∗ .
The ideas of the proposed equilibrium bear a similarity to Sugden’s “Mutually Beneficial Practice”
[Sugden, 2015], [Crettez, 2017]. A mutually beneficial practice for an n-player game is a strategy profile which
embodies two conditions. The first condition requires that each player gain must be higher than his maximin
payoff. The second condition states that the group-based minimum payoffs of each player are no higher than his
gain with the practice. That is, where a group of players follows the practice, the gain of each group member
when non members minimize his utility must be no higher than his gain when all the players follow the practice.
351
2 Strongly Guaranteed Coalition Equilibrium
We will formalize the condition for coalitional structures P2 , P3 and P4 ; for this, we will base on the suitable
union of concepts of Berge and Nash equilibria.
For the coalitional structure P2 it (condition of coalitional rationality) implies satisfaction of four inequalities:
f1 [x∗1 , x∗2 , x3 ] ≤ f1 [x∗ ] ∀x3 ∈ X3 , (4a)
f2 [x∗1 , x∗2 , x3 ] ≤ f2 [x∗ ] ∀x3 ∈ X3 , (4b)
f1 [x1 , x2 , x∗3 ] ≤ f1 [x∗ ] ∀xj ∈ Xj (j = 1, 2), (4c)
f2 [x1 , x2 , x∗3 ] ≤ f2 [x∗ ] ∀xj ∈ Xj (j = 1, 2); (4d)
for P3 :
f1 [x1 , x∗2 , x3 ] ≤ f1 [x∗ ] ∀xk ∈ Xk (k = 1, 3), (5a)
f3 [x1 , x∗2 , x3 ] ≤ f3 [x∗ ] ∀xk ∈ Xk (k = 1, 3), (5b)
f1 [x∗1 , x2 , x∗3 ] ≤ f1 [x∗ ] ∀x2 ∈ X2 , (5c)
f3 [x∗1 , x2 , x∗3 ] ≤ f3 [x∗ ] ∀x2 ∈ X2 ; (5d)
and, finally, for P4 :
f2 [x1 , x∗2 , x∗3 ] ≤ f2 [x∗ ] ∀x1 ∈ X1 , (6a)
f3 [x1 , x∗2 , x∗3 ] ≤ f3 [x∗ ] ∀x1 ∈ X1 , (6b)
f2 [x∗1 , x2 , x3 ] ≤ f2 [x∗ ] ∀xl ∈ Xl (l = 2, 3), (6c)
f3 [x∗1 , x2 , x3 ] ≤ f3 (x∗ ) ∀xl ∈ Xl (l = 2, 3). (6d)
We will call the situation x∗ ∈ X, for which all twelve limitations (4a)–(6d) are satisfied coalitionally rational
for the game Γ3 . The set of these we will note X ∗ ; obviously, X ∗ ⊆ X.
During the determination of the optimal solution of the game Γ3 , we will use, rather than all 15 inequalities
(2), (4a)–(6d), only six of those, as the other nine directly follow from those six.
This fact is the content of the following two statements.
Lemma 1. If (4c), (6c), and (6d) are satisfied, then stems the following:
fi [x∗ ] ≥ fi0 = max min fi [xi , x−i ] =
xi x−i
= min fi [x0i , x−i ] (i = 1, 2, 3).
x−i
Lemma 2. The following implications are correct:
(5a) ⇒ (4a), (4c) ⇒ (5c), (4d) ⇒ (6a),
(6c) ⇒ (4b), (5b) ⇒ (6b), (6d) ⇒ (5d).
From lemmas 1 and 2 immediately follows sufficiency of using six inequalities, namely (5a), (4c), (4d), (6c),
(5b) (6d), instead of all 15 in determining the optimal solution of the game Γ3 .
Consequently, we arrive to the following concept of the optimal solution of the game Γ3 ; from now on,
f = (f1 ,f2 ,f3 )∈R3 .
Definition We will call the pair (x∗ , f [x∗ ]) ∈ X × R3 strongly guaranteed coalitionally equilibrial for the game
Γ3 , if the following takes place:
1. the following six inequalities:
max fj [x1 , x2 , x∗3 ] = fj [x∗ ] (j = 1, 2),
x1 ,x2
max fk [x1 , x∗2 , x3 ] = fk [x∗ ] (k = 1, 3), (7)
x1 ,x3
max fl [x∗1 , x2 , x3 ] = fl [x∗ ] (l = 2, 3);
x2 ,x3
352
2. the situation x∗ ∈ X is Pareto maximal within the set of strongly guaranteed coalitionally equilibrial X ∗ of
the game Γ3 , i.e. ∀x ∈ X ∗ the system of inequalities fi [x] ≥ fi [x∗ ] (i = 1, 2, 3), of which at least one is strict, is
incompatible.
In the game Γ3 , we will consider the following pair as the optimal solution: strategy profile x∗ and corre-
sponding vector of outcomes f [x∗ ] = (f1 [x∗ ], f2 [x∗ ], f3 [x∗ ]), as the existence of the pair (x∗ , f [x∗ ]) immediately
answers to questions that appear in the mathematical game theory:
a) what is to be done for the players in Γ3 ?
b) what will they “obtain” as a result? Answer: follow their strategies x∗i from the situation x∗ = (x∗1 , x∗2 , x∗3 ).
Components f [x∗ ] = (f1 [x∗ ], f2 [x∗ ], f3 [x∗ ]) represent the outcomes of the players after application of their stra-
tegy profile x∗ = (x∗1 , x∗2 , x∗3 ).
We will list the advantages of the suggested strongly guaranteed coalitional equilibrial solution of the game
Γ3 .
First, according to Lemma 1, application of x∗ assures satisfaction of conditions of individual rationality: each
player “obtains” the outcome no less than what he can “guarantee” by acting independently using their own
maximin strategy.
Second, situation x∗ “leads” all players to the “greatest” strategies (Pareto maximal relative to other coali-
tional equilibrial situations of the game Γ3 ). This fact appears to us as an analogue of the collective rationality
of the mathematical theory of cooperative games.
Third, satifsation of requirements (4a)–(6d) means that, for example, for the first player, the dual-purpose
distribution of their resources, namely, not forgetting about their interests:
first, player 1 aims to provide maximal assistance to the player 2 in the union (coalition) {1,2 } as a member
of the coalition structure P2 (requirements (4c) and (4d);
second, player 1 helps player 3 as a member of the union {1,3} of the structure P3 (requirements (5a) (5b)).
Formalization of these two requirements in the first and second lines of (7) appears to us as a modification of the
idea of a Nash equilibrium concept version features two-criteria scoring players; the third line of (7) can already
be viewed as realization of the idea of equilibrium by Berger for the same two-criterion option. Same for the
second and third players.
Finally, the property of coalitional rationality is also based on principle of stability since, thanks to (7),
deviation from x∗ of any coalition (of one or two players) cannot lead to “increase” of outcomes of the members
of the deviant coalition in the game Γ3 (compared to fi (x∗ ) (i = 1, 2, 3).
3 Sufficient Conditions
We will now proceed to the result of the present article. We use the approach from [Zhukovskiy, 2016],
[Kudryavtsev et al., 2016], [Zhukovskiy, 2017 a], [Zhukovskiy, 2017 b].
∑3
We will employ two n-vectors x = (x1 , x2 , x3 ) ∈ X ⊂ Rn (n = i=1 ni ) and z = (z1 , z2 , z3 ) ∈ X as well seven
following scalar functions:
φ1 (x, z) = f1 [x1 , x2 , z3 ] − f1 [z],
φ2 (x, z) = f2 [x1 , x2 , z3 ] − f2 [z],
φ3 (x, z) = f1 [x1 , z2 , x3 ] − f1 [z],
φ4 (x, z) = f3 [x1 , z2 , x3 ] − f3 [z],
(8)
φ5 (x, z) = f2 [z1 , x2 , x3 ] − f2 [z],
φ6 (x, z) = f3 [z1 , x2 , x3 ] − f3 [z],
∑3 ∑3
φ7 (x, z) = fl [x] − fl [z],
l=1 l=1
and using players’ outcome functions in the game Γ3 , we will build the Germeier resultant of these seven functions
φ(x, z) = max φk (x, z), (9)
k=1,...,7
∏3
defined in X × (Z = X) ⊂ R2n , where X = i=1 Xi is the set of situations in the game Γ3 .
The saddle point (x, z ∗ ) ∈ X × Z of the scalar function φ(x, z) (from (8), (9)) in the antagonistic game
Γα = ⟨X, Z = X, φ(x, z)⟩ (10)
353
is defined by the chain of inequalities
φ(x, z ∗ ) ≤ φ(x, z ∗ ) ≤ φ(x, z) ∀x ∈ X, z ∈ X. (11)
∗ ∗
Proposition. If in the game Γ3 there is a saddle point (x, z ), then the minimax strategy z ∈ X of the game
Γα is the situation of the coalitional equilibrium of the original game Γ3 .
By assuming in (11) the situation z = x, we will obtain from (8) that φ(x, x) = 0, as all φk (x, x) = 0
(k = 1, ..., 7). Then, in accordance with (11), (from transitivity) follows
φ(x, z ∗ ) = max{f1 [x1 , x2 , z3∗ ] − f1 [z ∗ ],
f2 [x1 , x2 , z3∗ ] − f2 [z ∗ ], f1 [x1 , z2∗ , x3 ] − f1 [z ∗ ],
f3 [x1 , z2∗ , x3 ] − f3 [z ∗ ], f2 [z1∗ , x2 , x3 ] − f2 [z ∗ ],
f3 [z1∗ , x2 , x3 ] − f1 [z ∗ ],
∑3 ∑3
fi [x1 , x2 , x3 ] − fi [z1∗ , z2∗ , z3∗ ]} ≤ 0
i=1 i=1
for ∀xi ∈ Xi (i = 1, 2, 3). This implies the seven following inequalities:
fj [x1 , x2 , z3∗ ] ≤ fj [z ∗ ] ∀xj ∈ Xj (j = 1, 2),
fk [x1 , z2∗ , x3 ] ≤ fk [z ∗ ] ∀xk ∈ Xk (k = 1, 3),
fl [z1∗ , x2 , x3 ] ≤ fl [z ∗ ] ∀xl ∈ Xl (l = 2, 3),
∑3 ∑
3 (12)
fr [x1 , x2 , x3 ] ≤ fr [z ∗ ]
r=1 r=1
∀x = (x1 , x2 , x3 ) ∈ X ∗ ⊆ X.
The first three (12) mean that the situation z ∗ ∈ X is (because of these inequalities and (7)) coalitionally
rational in the game Γ3 . The last inequality in (12) and inclusion X ∗ ⊆ X “guarantees” [Podinovskiy, 2007] the
Pareto maximality of the strategy profile x∗ in the three-criteria problem
ΓX ∗ = ⟨X ∗ , {fi [x]}i=1,2,3 ⟩ .
From the aforementioned statement we obtain the following constructive method of building a coalitional
equilibrial solution of the game Γ3 :
first, build, using (8) and (9), the function φ(x, z),
second, find a saddle point (x, z ∗ ) of the function φ(x, z) (satisfied the chain of inequalities from (11)),
third, find values of the three functions fi [z ∗ ] (i = 1, 2, 3).
Then the pair
(z ∗ , f [z ∗ ]) = (f1 [z ∗ ], f2 [z ∗ ], f3 [z ∗ ]) ∈ X × R3
forms a coalitional equilibrium of the game Γ3 (or a strongly guaranteed coalitional equilibrium of the game Γ).
Further, we give the existence theorem in mixed-strategy.
Theorem. If in the game Γ the sets Y ∈ comp(Rm ), Xi ∈ comp(Rn ) and fi (·) ∈ C(X, Y ) (i = {1, 2, 3}),
therefore, there is a strongly guaranteed coalitionally equilibrial mixed-strategy profile in this game.
4 Conclusion
First of all, we will note the new results, obtained in the present article.
First, the concept of the strongly guaranteed coalitional equilibrium (SGCE) that takes into account interests
of any coalition has been established.
Second, a practical method of finding SGCE has been established, which can be reduced to searching of a
minimax strategy for a special Germeier resultant that can be built using players’ outcome functions.
We find that:
1. the results can be extended to cooperative games of any number of participants (over three);
2. SGCE “guarantees” stability of coalitional structures against deviation of any coalitions;
3. SGCE is applicable, even if coalitional structures change throughout the game;
4. SGCE can be used for forming stable unions of players;
But there is another advantage that we find important to note.
354
To this day, in theory of cooperative games conditions of individual or collective rationality have been stressed.
But individual interests of players are matched by the concept of Nash equilibrium with its “egoistic” character
(“to each his own”); collective games are matched by the concept of Berge equilibrium with its “altruism” (“help
everyone and forget about your own interests”). However, such “oblivion” is not characteristic for the human
nature of the players. This is overcome by the coalitional rationality.
Indeed, in terms of coalitional rationality, player 1, minding their own interests and being a part of the coalition
{1,2} within the coalitional structure P2 helps player 2 (element of Berge equilibrium), while being a part of
the coalition {1,3} within the coalitional structure P3 supports player 3, but, as we remind the reader, “not
forgetting about themselves”. Same for other players. Therefore, coalitional rationality fills the gap between the
Nash (NE) and Berge (BE) equilibriums, adding “care about the others” to NE and “care about themselves” to
BE.
Acknowledgements
The work was supported by Act 211 Government of the Russian Federation, contract 02.A03.21.0011.
References
[Crettez, 2017] Crettez, B. (2017). On Sugdens “mutually beneficial practice” and Berge equilibrium. Interna-
tional Review of Economics, 64. DOI: 10.1007/s12232-017-0278-3.
[Kudryavtsev et al., 2016] Kudryavtsev, K.N., Zhukovskiy, V.I., & Stabulit, I.S. (2016). One method for con-
structing Pareto-optimal Nash equilibriums. In CEUR Workshop Proceedings, Vol. 1623, (pp. 618-623).
[Nash, 1950] Nash, J. Equillibrium points in N-person games. Proc. Nat. Academ. Sci. USA., 36, 48-49.
[Nash, 1951] Nash, J. Non-cooperative games. Ann. Math., 54, 286-295.
[Podinovskiy, 2007] Podinovskiy, V.V., & Nogin, V.D. (2007). Pareto optimal solutions of multicriteria problems.
Moscow: Fizmatlit. (in Russian)
[Sugden, 2015] Sugden, R. (2015). Team Reasoning and Intentional Cooperation for Mutual Benefit. Journal of
Social Ontology, 1(1), 143-166.
[Vorobyov, 1985] Vorobyov, N. N. (1985). Game theory for economic cyberneticans. Moscow: Nauka. (in Russian)
[Zhukovskiy, 2009] Zhukovskiy, V.I. (2009). Cooperative games under uncertainty and their applications. Moscow:
Editorial URSS. (in Russian)
[Zhukovskiy, 1994] Zhukovskiy, V.I., & Chikriy, A.A. (1994). Linear-quadratic dierential games. Kiev: Naukova
Dumka. (in Russian)
[Zhukovskiy, 2013] Zhukovskiy, V.I., & Kudryavtsev, K.N. (2013). Equilibrating conflicts under uncertainty. II.
Analogue of a maximin. Mat. Teor. Igr Pril., 5(2), 3-45 (in Russian)
[Zhukovskiy, 2016] Zhukovskiy, V.I., & Kudryavtsev, K.N. (2016). Pareto-optimal Nash equilibrium: Sufficient
conditions and existence in mixed strategies. Automation and Remote Control, 77(8), 1500-1510.
[Zhukovskiy, 2017 a] Zhukovskiy, V.I., & Kudryavtsev, K.N. (2017). Mathematical Foundations of the Golden
Rule. I. Static Case. Automation and Remote Control, 78(10), 1920-1940.
[Zhukovskiy, 2017 b] Zhukovskiy, V.I., & Kudryavtsev, K.N. (2017). Coalition equilibrium in a three-person
game. In 2017 Constructive Nonsmooth Analysis and Related Topics (dedicated to the memory of V.F.
Demyanov) (CNSA), St. Petersburg, 2017, (pp. 1-4). doi: 10.1109/CNSA.2017.7974037
355