In this article, we suggest a new concept of an optimal solution in 3person game under uncertainty, that we call “strongly guaranteed coalitional 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 equilibrium 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.
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 x = (x1, x2, x3) ∈ X = 3 ∏ Xi ⊂ Rn (n = i=1
3 ∑ ni). 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 considering a corresponding game (without uncertainty) Here,
Γ3 = ⟨{1, 2, 3}, {Xi}i=1;2;3, {fi[x]}i=1;2;3⟩ .
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 (rational, reasonable). Main concepts of optimality in the mathematical game theory are [Vorobyov, 1985] intuitive concepts of pro tability, 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 optimality 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 conditions 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 noncoalitional 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 = (x1, x2, x3) ∈ X means that =
min x i2X i fi = max min fi[xi, x i] = xi2Xi x i2X i fi[xi0, x i] ≤ fi0[x ], i = 1, 2, 3, i.e. application of the maximin strategy xi0 implies the following inequalities:
fi0 ≤ fi[x ], i = 1, 2, 3.
For the coalitional structure P5 in the game Γ3: within the set of strategy profiles X x ∈ X ⊆ X is Pareto optimal in the three-criteria problem ⊆ X strategy profile (1) (2) (3) if ∀x ∈ X the system of inequalities of which at least one is strict, is incompatible. According to the Karlin lemma [Podinovskiy, 2007], if ΓX
= ⟨X , {fi[x]}i=1;2;3⟩ fi[x] ≥ fi[x ](i = 1, 2, 3), i=1 3 3 ∑ fi[x ] = max ∑ fi[x], x2X 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.
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: for P3: and, finally, for P4: f1[x1, x2, x3] ≤ f1[x ] f2[x1, x2, x3] ≤ f2[x ] ∀x3 ∈ X3, ∀x3 ∈ X3, f1[x1, x2, x3] ≤ f1[x ]
∀xj ∈ Xj (j = 1, 2), f2[x1, x2, x3] ≤ f2[x ]
∀xj ∈ Xj (j = 1, 2); f1[x1, x2, x3] ≤ f1[x ]
∀xk ∈ Xk (k = 1, 3), f3[x1, x2, x3] ≤ f3[x ]
∀xk ∈ Xk (k = 1, 3), f1[x1, x2, x3] ≤ f1[x ] f3[x1, x2, x3] ≤ f3[x ] f2[x1, x2, x3] ≤ f2[x ] f3[x1, x2, x3] ≤ f3[x ] ∀x2 ∈ X2, ∀x2 ∈ X2; ∀x1 ∈ X1, ∀x1 ∈ X1, f2[x1, x2, x3] ≤ f2[x ]
∀xl ∈ Xl (l = 2, 3), f3[x1, x2, x3] ≤ f3(x )
∀xl ∈ Xl (l = 2, 3).
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 satis ed, then stems the following: Lemma 2. The following implications are correct: fi[x ] ≥ fi0 = max min fi[xi, x i] =
xi x i = min fi[xi0, x i] (i = 1, 2, 3).
x i (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.
De nition 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, x3] = fj [x ] (j = 1, 2), x1;x2 max fk[x1, x2, x3] = fk[x ] (k = 1, 3), x1;x3 max fl[x1, x2, x3] = fl[x ] (l = 2, 3); x2;x3 (4a) (4b) (4c) (4d) (5a) (5b) (5c) (5d) (6a) (6b) (6c) (6d) (7) 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 corresponding 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 xi from the situation x = (x1, x2, x3). Components f [x ] = (f1[x ], f2[x ], f3[x ]) represent the outcomes of the players after application of their strategy profile x = (x1, x2, x3).
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 coalitional 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:
rst, 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
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].
We will employ two n-vectors x = (x1, x2, x3) ∈ X ⊂ Rn (n = ∑3 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], φ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 φ(x, z) =
max φk(x, z), k=1;:::;7 and using players’ outcome functions in the game Γ3, we will build the Germeier resultant of these seven functions defined in X × (Z = X) ⊂ R2n, where X = ∏3
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)⟩ is defined by the chain of inequalities φ(x, z ) ≤ φ(x, z ) ≤ φ(x, z) ∀x ∈ X, z ∈ X.
Proposition. If in the game Γ3 there is a saddle point (x, z ), then the minimax strategy z Γ 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 of the game (11) (12) for ∀xi ∈ Xi (i = 1, 2, 3). This implies the seven following inequalities: φ(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 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 ∑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:
rst, 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 pro le in this game. 4
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.
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 [Zhukovskiy, 2009] Zhukovskiy, V.I. (2009). Cooperative games under uncertainty and their applications. Moscow:
Editorial URSS. (in Russian)