# A Note on Strategic Stability of Cooperative Solutions for Multistage Games

Authors: Lei Wang; Cui Liu; Juan Xue; Hongwei Gao
Journal: Discrete Dynamics in Nature and Society
 (2018)

---

## Abstract

The problem of strategic stability of cooperative solutions for multistage games is studied. The sufficient conditions related to discount factors are presented, which guarantee the existence of Nash or strong Nash equilibria in such games and therefore guarantee the strategic stability of cooperative solutions. The deviating payoffs of players are given directly, which are related closely to these conditions and avoid the loss of super-additivity of a class of general characteristic functions. As an illustration, Nash and strong Nash equilibria are found for the repeated infinite stage Prisoner’s dilemma game.


---

## Body

## 1. Introduction

Strategic stability of cooperative solutions in a game means that the outcome of cooperation must be attained in some Nash equilibrium, which is an effective mechanism to guarantee the sustainability of a cooperative agreement. It seeks to make the cooperative solution guaranteed by an equilibrium in an associated noncooperative game. See, for example, [1–4].How can a cooperative agreement made at the start be sustained over time is an important issue in human behavior. Besides strategic stability,time consistency andirrational-behavior-proof condition are also effective aspects to sustain cooperation.Time consistency may be described informally as follows: to sustain cooperation over time, each player’s cooperative payoff should belong to the same optimal principle at any time along the cooperative path. The concept of time consistency and its implement ingredientimputation distribution procedure (IDP) were initially proposed in [5, 6] and further developed in [7–9].Irrational-behavior-proof condition requires that the partners involved in the cooperation must be sure that even in the worst scenario they will not lose compared with the noncooperative behavior. In [10], the irrational-behavior-proof condition is proposed. A further investigation could be found in [11].In their seminal paper [12], Grauer and Petrosyan studied the strategic stability of cooperative solutions in aninfinite stage game (ISG). They introduced a new (general) characteristic function in such a game, which plays a role of computing the cooperative solutions and describing the deviating payoffs of players. This characteristic function plays an essential role to construct Nash or strong Nash equilibria in the ISG. However, the general characteristic function has a drawback: it could not be super-additive, which would lead to the nonexistence of cooperative solutions, e.g., the core.Motivated by the above observations, in this paper, we shall focus on the problem of strategic stability of cooperative solutions in ISGs and present sufficient conditions in terms of discount factors and prove that Nash or strong Nash equilibria exist in such games. The deviation payoffs are given directly, which are related closely to the sufficient condition of strategic stability and avoid the loss of super-additivity of the general characteristic functions. Then we study therepeated infinite stage game (RISG). As an illustration, Nash and strong Nash equilibria are found for the repeated infinite stage Prisoner’s dilemma game.The proof technique is the trigger (penalty) strategy combined with the appropriate construction of the time-consistent IDP. When some player (coalition) deviates from the cooperative trajectory in some stage, other players (coalitions) would use the trigger strategies from the next stage. But this does not include the case, in which the trigger strategies could be used after several stages, perhaps because the information is delayed or the players in one coalition need time to coordinate their actions (see [13–16]). While in a finite stage game, to construct Nash or strong Nash equilibria, we need more strict conditions, which is the case with perfect information (see [17]).The theory we developed could be applied to analyzing the dynamic cooperative behavior in society. A typical example is the global pollution control problem, which requires a joint effort of many countries for a long time. See, for example, [18–20].The paper is organized as follows. In Section2, the basic model about the ISG is introduced. In Section 3, the sufficient conditions are given and the existence of Nash and strong Nash equilibria are proved in ISGs. In Sections 4 and 5, the RISG and the repeated infinite stage Prisoner’s dilemma game are studied. In Section 6, some concluding discussions are provided.


## 2. Formal Definitions and Terminology

In this section we introduce the basic model of ISGs (see also [12] for more details).Aninfinite game tree is an infinite oriented treelike graph K=(Z,F) with the root z0, where Z is the set of vertices and Fz is the set of vertices following after z and F:Z→2Z,F(z)=Fz⊂Z,z∈Z.Asingle stage game is a simultaneous n-player game Γ(z)=〈N;U1z,…,Unz;H1z,…,Hnz〉 corresponding to each vertex z∈Z in the tree K=(Z,F), where N={1,2,…,n} is the set of players, Uiz is the set of strategies of player i and Hiz(u1z,…,unz) is the payoff of player i.Atransition function is defined as T(z;u1z,…,unz)=T(z;uz)=z′∈Fz for each z∈Z. For each game Γ(z), the function T determines the following stage game Γ(z′).Aninfinite stage gameG(z0) in the tree K=(Z;F) is determined by the simultaneous games Γ(z) and the transition function T.Denote a sequence of situationsuz0,uz1,…,uzk,… by an n-tuple of strategies u(·)=(u1(·),…,un(·)), where ui(·)=(uiz0,uiz1,…,uizk,…),i∈N. Define the corresponding sequence of vertices z0,z1,…,zk,… as atrajectory (path) in the graph K, denoted by (z0,z1,…,zk,…).Define(1)Hiz0;u1·,u2·,…,un·=∑k=0∞Hizkuzkδk,δ∈0,1as thepayoff of playeri in the game G(z0). All the payoffs in the single stage games are uniformly bounded, which guarantees the existence of sum (1).In gameG(z0), the players possesscomplete information, which means they know the simultaneous game Γ(z) and remember all the strategies in the game history.Suppose that players inN are playing cooperatively with objective(2)maxuz0,uz1,…,uzk,…⁡∑i=1n∑k=0∞Hizkuzkδk.Suppose there exist ann-tuple of strategies u¯(·)=(u¯1(·),…,u¯n(·)) and a trajectory z¯=(z0,z¯1,…,z¯k,…) satisfying (2). Define z¯ as anoptimal cooperative trajectory of G(z0).ThesubgameG(z) of the game G(z0) is played in the subgraph K(z)=(Zz,F), where Zz is the set of vertices of the subgraph K(z). The payoff of player i in the subgame G(z) is denoted by Hi(z;u1(·),u2(·),…,un(·))=∑l=k∞Hizl(uzl)δl-k.Thecharacteristic functionV(z;S),S⊂N in the subgame G(z) is defined in a classical way: V(z;S)=ValGS,N∖S(z), where ValGS,N∖S(z) is a value of zero-sum game played between coalition S acting as player 1 and coalition N∖S acting as player 2, with the payoff of coalition S equal to ∑i∈SHi(z;u1(·),…,un(·)). It is additionally assumed that the values V(z;S) exist for every z∈Z and S⊂N. Specially,(3)Vz;N=maxuzk,uzk+1,…⁡∑i=1n∑l=k∞Hizluzlδl-k=∑i=1n∑l=k∞Hiz¯lu¯z¯lδl-k.Denote the pair of optimal strategies in the gameGS,N∖S(z) by (u~S(·),u~N∖S(·)), where u~S(·)={u~i(·),i∈S},u~N∖S(·)={u~i(·),i∈N∖S}.Consider a sequence of subgamesG(z¯k) along an optimal cooperative trajectory z¯=(z0,z¯1,…,z¯k,…). In each subgame G(z¯k), one can obtain theimputation setL(z¯k) and thecoreC(z¯k):(4)Lz¯k=α=α1,…,αn:αi≥Vz¯k;i,∀i∈N,∑i∈Nαi=Vz¯k;N,(5)Cz¯k=α=α1,…,αn:∑i∈Sαi≥Vz¯k;S,∀S⊂N,∑i∈Nαi=Vz¯k;N.Suppose the imputationα=(α1,…,αn)∈L(z0). Define animputation distribution procedure (IDP) as a function β(k)=(β1(k),β2(k),…,βn(k)),k=0,1,…, such that(6)αi=∑k=0∞βikδk.For everyα∈L(z0), define thenoncooperative infinite stage gameGα(z0), which differs from the game G(z0) only in the payoffs along the optimal cooperative trajectory z¯. Suppose under the situation u(·)=(u1(·),…,un(·)) the path (z0,z1,…,zk,…) is realized. Denote the payoff in game Gα(z0) by(7)Hiαz0;u1·,…,un·=∑k=0s-1βikδk+∑k=s∞Hizkuzkδk-s,where s=inf{k:zk≠z¯k,k=0,1,…}. In a special case when zk=z¯k,k=0,1,…, we have(8)Hiαz0;u1·,…,un·=∑k=0∞βikδk=αi.Letα(k)∈L(z¯k). Game Gα(z0) is called aregularized game of G(z0) if IDP β is defined in such a way that(9)βik=αik-δαik+1,k=0,1,…In particular, ifα(k)∈C(z¯k),k=0,1,…, Gα(z0) is called astrictly regularized game of G(z0).From (9) we get(10)αi=∑l=0k-1βilδl+αik.Now suppose thatM(z0)⊂L(z0) is some optimality principle in the cooperative game G(z0), and M(z¯k)⊂L(z¯k) is the same optimality principle defined in the subgame G(z¯k) with initial conditions on the cooperative trajectory. M can be the Shapley value, the core, the nucleolus, etc. If α(k)∈M(z¯k),k=0,1,…, condition (10) gives us thetime consistency of the chosen imputation α (or the IDP β) in game G(z0).Ann-tuple u∗(·)=(u1∗(·),…,un∗(·)) is aNash equilibrium of game Gα(z0) if and only if(11)Hiαz0;u∗·≥Hiαz0;u∗·∥ui·for all i∈N and all ui.Ann-tuple u∗(·)=(u1∗(·),…,un∗(·)) is astrong Nash equilibrium of game Gα(z0) if and only if(12)∑i∈SHiαz0;u∗·≥∑i∈SHiαz0;u∗·∥uS·for all S⊂N and all uS={ui,i∈S}.


## 3. Existence of Nash and Strong Nash Equilibria

Consider the following inequality with respect toδ: (13)αis≥Hiz¯su¯z¯s∥u~i+δVTz¯s;u¯z¯s∥u~i;i,s=0,1,2,…where Hiz¯s(u¯z¯s∥u~i)=maxui⁡{Hiz¯s(u¯z¯s∥ui)} is the stage payoff to player i if deviating from her cooperative strategy and playing the best response to opponents’ cooperative strategies. The above inequality is reduced to the following:(14)δ≤miniinfs⁡αis-Hiz¯su¯z¯s∥u~iVTz¯s;u¯z¯s∥u~i;i.Let the value in the right-hand side in (14) be reached. Let (15)δ¯=miniinfs⁡αis-Hiz¯su¯z¯s∥u~iVTz¯s;u¯z¯s∥u~i;i.We can get the following.Theorem 1.
In the regularized gameGα(z0), for any δ satisfying δ≤δ¯, the situation (u1∗(·),…,un∗(·)) with players’ payoffs as (α1,α2,…,αn) guaranteed by the time-consistent IDP β is a Nash equilibrium.Now supposeS⊂N and consider another inequality with respect to δ: (16)∑i∈Sαis≥∑i∈SHiz¯su¯z¯s∥u~S+δVTz¯s;u¯z¯s∥u~S;S,u~S=u~i,i∈S,s=0,1,2,…,where ∑i∈SHiz¯s(u¯z¯s∥u~S)=maxuS{∑i∈SHiz¯s(u¯z¯s∥uS)} is the stage payoff to coalition S if deviating from the cooperative strategy and playing the best response to others’ cooperative strategies. The above inequality is reduced to the following:(17)δ≤minSinfs⁡∑i∈Sαis-∑i∈SHiz¯su¯z¯s∥u~SVTz¯s;u¯z¯s∥u~S;S.Let the value in the right-hand side in (17) be reached. Let (18)δ~=minSinfs⁡∑i∈Sαis-∑i∈SHiz¯su¯z¯s∥u~SVTz¯s;u¯z¯s∥u~S;S.We can also get the following.Theorem 2.
In the strictly regularized gameGα(z0), for any δ satisfying δ≤δ~, the situation (u1∗(·),…,un∗(·)) with players’ payoffs as (α1,α2,…,αn) guaranteed by the time-consistent IDP β is a strong Nash equilibrium.Theorem1 implies the cooperative solution (any imputation) can be strategically supported by a specially constructed Nash equilibrium in a regularized game Gα(z0). Theorem 2 implies the cooperative solution (any core) can be strategically supported by a specially constructed strong Nash equilibrium in a strictly regularized game Gα(z0). Since a strong Nash equilibrium is also a Nash equilibrium in the strictly regularized game Gα(z0), the existence of strong Nash equilibrium implies the existence of Nash equilibrium. We need only to prove Theorem 2 and the proof of Theorem 1 is similar.Proof of Theorem2.
Consider the situationu∗(·)=(u1∗(·),…,un∗(·)) in the strictly regularized game Gα(z0) and define the strategies of player p∈N as follows: (19)up∗·=u¯pz¯k,forz=z¯k;u~pz,forz∈Zz¯s;arbitrary,for  the  other  positionswhere z¯s is the first vertex along the cooperative trajectory z¯=(z0,z¯1,z¯2,…), on which player q∈S⊂N deviates from u¯qz¯s and u~p(·) is the p-th component of strategy u~N∖S(·) in the zero-sum game GS,N∖S(z¯s).
To prove the situationu∗(·)=(u1∗(·),…,un∗(·)) is a strong Nash equilibrium in the game Gα(z0), we have to show that(20)∑q∈SHqαz0;u∗·≥∑q∈SHqαz0;u∗·∥uS·for all S⊂N and all uS={uq,q∈S}.
It is easy to see when then-tuple u∗(·) is played the game develops along the cooperative trajectory z¯. If under the situation u∗(·)∥uS(·) the trajectory z¯ is also realized, then (20) will be true.
Suppose the strategyuS(·) differs from the strategy uS∗(·) in one of the single stage games Γ(z¯k),k=0,1,…. Denote the first vertex of path z¯ by z¯s, on which uqz¯s≠u¯qz¯s,q∈S. In the situation u∗(·)∥uS(·), the deviating coalition S cannot obtain more than(21)δs∑q∈SHqz¯su¯z¯s∥uS+δs+1VTz¯s;u¯z¯s∥uS;S,uS=uq,q∈S,since, after deviating from u¯qz¯s,q∈S, coalition N∖S will play against coalition S in the zero-sum game GS,N∖S(z′), where z′=T(z¯s;u¯z¯s∥uS).
From the time consistency of IDPβ and condition (17), we then obtain(22)∑q∈SHqαz0;u∗·=∑q∈S∑k=0s-1βqkδk+δs∑q∈Sαqs≥∑q∈S∑k=0s-1βqkδk+δs∑q∈SHqz¯su¯z¯s∥u~S+δVTz¯s;u¯z¯s∥u~S;S≥∑q∈SHqαz0;u∗·∥uS·.
This completes the proof of Theorem2.


## 4. The Case of Repeated Infinite Stage Game

In this part, we shall consider the case whenG(z0) is arepeated infinite stage game (RISG), in which a normal-form game appears infinite periods.In each single stage gameΓ, thecharacteristic functionV(S),S⊂N is defined by V(S)=ValΓS,N∖S, where ValΓS,N∖S is a value of zero-sum game played between coalition S acting as player 1 and coalition N∖S acting as player 2. In each game Γ, one can construct theimputation setL and thecoreC using the characteristic function V(S).Consider a sequence of subgamesG(z¯k) along the cooperative trajectory z¯=(z0,z¯1,…,z¯k,…). Put Hiz¯k=Hi,u¯z¯k=u¯,k=0,1,…. The value of game GS,N∖S(z¯k) will be equal to(23)Vz¯k;S=∑l=k∞VSδl-k=VS1-δ.For any imputationγ∈L or γ∈C, define the time-consistent IDP β as βi(k)=γi,k=0,1,…. Then αi(k)=∑l=k∞γiδl-k=γi/(1-δ).In the regularized gameGα(z¯k), the existence of IDP is equivalent to the nonemptiness of the imputation set L(z¯k), i.e., the existence of a solution of the following inequalities:(24)αik≥Vz¯k;i,∀i∈N,∑i∈Nαik=Vz¯k;N.It can be simplified as,(25)γi≥Vi,∀i∈N,∑i∈Nγi=VN.In the strictly regularized gameGα(z¯k), the existence of IDP is equivalent to the nonemptiness of the core C(z¯k), i.e., the existence of a solution of the following inequalities:(26)∑i∈Sαik≥Vz¯k;S,S⊂N,∑i∈Nαik=Vz¯k;N.It can be simplified as(27)∑i∈Sγi≥VS,S⊂N,∑i∈Nγi=VN.Under the cooperative agreement, players will choose their cooperative strategies. But if some playeri∈N deviates from her cooperative strategy at some stage s,s=0,1,2,…, she will play her best response to other players’ cooperative strategies and get the payoff Hi(u¯∥u~i)=maxui{Hi(u¯∥ui)} at this stage. Suppose other players will choose their trigger strategies from the next stage until the end and the deviator’s future payoff will be δV({i})/(1-δ). If αi(s)≥Hi(u¯∥u~i)+δV({i})/(1-δ), player i will never deviate from her cooperative strategy. The above inequality can be simplified to δ≥1-(γi-V({i}))/(Hi(u¯∥u~i)-V({i})) when Hi(u¯∥u~i)≠V({i}). When Hi(u¯∥u~i)=V({i}), it will be γi≥V({i}), which always holds. Let(28)δ^=maxi∈N:Hiu¯∥u~i>Vi⁡1-γi-ViHiu¯∥u~i-Vi.The following theorem can be formulated.Theorem 3.
If the imputation setL defined by (25) is not empty and the discount factor satisfies δ≥δ^, then in the repeated infinite stage game Gα(z0), the situation (u1∗(·),…,un∗(·)) with payoffs (α1,α2,…,αn) guaranteed by the time-consistent IDP β is a Nash equilibrium.We can consider the similar deviation for coalitions. If some coalitionS⊂N acts individually and deviates from her cooperative strategy at some stage s, at the current stage she will get the payoff ∑i∈SHi(u¯∥u~S)=maxuS{∑i∈SHi(u¯∥ui)},uS={ui,i∈S},s=0,1,2,…. From the next stage, other players will form a coalition N∖S and choose the trigger strategies. So the deviating coalition’s future payoff will be δV(S)/(1-δ). Coalition S will not deviate from her cooperative strategy, if ∑i∈Sαi(s)≥∑i∈SHi(u¯∥u~S)+δV(S)/(1-δ). It can be simplified to δ≥1-(∑i∈Sγi-VS)/(∑i∈SHiu¯∥u~S-VS) when ∑i∈SHi(u¯∥u~S)≠V(S). When ∑i∈SHi(u¯∥u~S)=V(S), it will be ∑i∈Sγi≥V(S), which always holds. Let(29)δˇ=maxS⊂N:∑i∈SHiu¯∥u~S>VS⁡1-∑i∈Sγi-VS∑i∈SHiu¯∥u~S-VS.The following theorem can be formulated.Theorem 4.
If the coreC defined by (27) is not empty and the discount factor satisfies δ≥δˇ, then in the repeated infinite stage game Gα(z0), the situation (u1∗(·),…,un∗(·)) with payoffs (α1,α2,…,αn) guaranteed by the time-consistent IDP β is a strong Nash equilibrium.


## 5. Example

To illustrate the theoretical result, we consider a repeated infinite stage gameG in which the two-person Prisoner’s dilemma game Γ=〈N;U1,U2;H1,H2〉 is played at each stage.For each playeri, Ui consists of two strategies C and D. Hi(u1,u2) is the payoff of player i defined by Hi(C,C)=6,Hi(C,D)=0,Hi(D,C)=9,Hi(D,D)=1,i=1,2. Since strategy D dominates strategy C for each i, situation (D,D) is a Nash equilibrium in game Γ. But it is not Pareto optimal since situation (C,C) is better off for both players.The following strategies describe the cooperative behaviors for two players: they chooseu¯1=C,u¯2=C at each stage game. In Table 1, values of the characteristic function V(S) and the deviation payoffs in stage games are presented. Using these values, we find the Shapley value γi as the cooperative solution in each stage game, the imputation αi(k) from stage k, and the time-consistent IDP βi(k),k=0,1,2,… (see Table 2).Table 1
Characteristic function and deviating payoff.
S { 1,2 } { 1 } { 2 } ∅ V ( S ) 12 1 1 0 ∑ i ∈ S H i ( u ¯ ∥ u ~ S ) 12 9 9 0Table 2
Shapley value and IDP.
Playeri Player1 Player2 γ i 6 6 α i ( k ) 6 1 - δ 6 1 - δ β i ( k ) 6 6From (28) and (29), we get δ^=δˇ=3/8. Therefore, following Theorem 3, for all δ∈[3/8,1), the strategy profile (C,C) with players payoffs (6/(1-δ),6/(1-δ)) is a Nash equilibrium in the class of trigger strategies. It can be checked that condition (27) holds for the Shapley value in each stage game, which implies the Shapley value is in the core of each stage game. This is also true for the repeated infinite stage game G. Therefore, following Theorem 4, for all δ∈[3/8,1), the strategy profile (C,C) with players payoffs (6/(1-δ),6/(1-δ)) is also a strong Nash equilibrium.


## 6. Conclusions

In this paper, the sufficient conditions are presented to guarantee the existence of Nash or strong Nash equilibria in multistage games, which guarantee the strategic stability of cooperative solutions. They are related closely to the discount factors and are simplified in the repeated infinite stage games. These conditions avoid the loss of super-additivity of a class of general characteristic functions. Furthermore, if random influences are taken into account, the considered problem is quite involved and this is one of our future research works.



---

*Source: 3293745-2018-11-01.xml*