3_Gangstas_Paradise.RmdIn the newest version of our paper “Reconciliating relational contracting and hold-up: A model of repeated negotiations” by Susanne Goldlücke and me, we introduce the Gangsta’s Paradise game to exemplify that repeated negotiation equilibria (RNE) can fail to exist. This document accompanies our paper and shall help to get a better theoretical intuition of the existence problem and how T-RNE solve it, as well as showcase how the R package RelationialContracts can help to quickly numerically explore these issues.
We first illustrate the existence problem. Then we show how for this example existence can be reestablished by a finer state space and how T-RNE essentially find the approbriate finer state space. Finally, we illustrate how similar effects of state space definition already arise for Markov perfect equilibria, which means it should not be surprising to find such effects also for RNE and T-RNE.
The Gangsta’s Paradise game has two states: a prisoners’ dilemma state x0 and paradise x_paradise. In x0 players play a prisoners’ dilemma game with the following payoff matrix:
| C | D | |
| C | 1,1 | -10,3 |
| D | 3,-10 | 0,0 |
Players move to paradise if and only if both cooperate. In paradise, players laze around and get a fixed payoff of (2,2) without performing any actions. Paradise is an absorbing state in which players stay forever.
The following code creates the game with the RelationalContracts package.
library(RelationalContracts) # Since we will define several similar games, # we define action spaces and payoff functions # as global variables that we can reuse later. # Action spaces in x0 A1 = list(a1=c("C","D")) A2 = list(a2=c("C","D")) # Payoff functions in x0 pi1 = ~case_when( a1 == "C" & a2== "C" ~ 2, a1 == "D" & a2== "C" ~ 3, a1 == "C" & a2== "D" ~ -10, a1 == "D" & a2== "D" ~ 0 ) pi2=~case_when( a1 == "C" & a2== "C" ~ 2, a1 == "D" & a2== "C" ~ -10, a1 == "C" & a2== "D" ~ 3, a1 == "D" & a2== "D" ~ 0 ) g = g0 = rel_game() %>% rel_state("x0", A1=A1, A2=A2, pi1.form=pi1, pi2.form=pi2) %>% rel_state("x.paradise", pi1=2, pi2=2) %>% rel_transition("x0","x.paradise",a1="C",a2="C") %>% rel_compile()
There are combinations of discount factors and negotiation probabilities for which an RNE exists. Since this is a weakly directional game, we can use the function rel_rne to find an RNE (when speaking of RNE, we always mean simple RNE as defined in our paper):
##
## Solve weakly directional state x0 ... ok## # A tibble: 2 x 9
## x ae.lab a1.lab a2.lab r1 r2 U v1 v2
## <chr> <chr> <chr> <chr> <dbl> <dbl> <dbl> <dbl> <dbl>
## 1 x0 "C | C" "D | D" "D | D" 2 2 4 0.182 0.182
## 2 x.paradise " | " " | " " | " 2 2 4 2 2This RNE implements (C,C) on the equilibrium path and as punishment (and under disagreement) mutual defection is played. For a lower discount factor, we can find an RNE where only (D,D) can be implemented on the equilibrium path:
##
## Solve weakly directional state x0 ... ok## # A tibble: 2 x 9
## x ae.lab a1.lab a2.lab r1 r2 U v1 v2
## <chr> <chr> <chr> <chr> <dbl> <dbl> <dbl> <dbl> <dbl>
## 1 x0 "D | D" "D | D" "D | D" 0 0 0 0 0
## 2 x.paradise " | " " | " " | " 2 2 4 2 2For some combinations of delta and rho no RNE exists in this game. An example is delta=0.5 and rho=0.5:
rel_rne(g,delta = 0.5, rho=0.5)
##
## Solve weakly directional state x0 ...## Error in rel_rne(g, delta = 0.5, rho = 0.5): Cannot find an RNE when trying to solve the weakly directional state x0Let us illustrate why no RNE exists. First, assume that the RNE can only implement (D,D) on the equilibrium path. Then paradise would never be reached and each player has zero negotiation payoffs in state x0, i.e. r1(x0)=r2(x0)=0. This is only an RNE if no SPE of the truncated game with these negotiation payoff can implement higher joint payoffs. We can solve for the optimal simple SPE in that truncated game as follows:
g = rel_spe(g, delta=0.5, rho=0.5, r1 = c(0,2), r2=c(0,2)) g %>% get_eq() %>% select(x,ae.lab,r1,r2,U,v1,v2)
## # A tibble: 2 x 7
## x ae.lab r1 r2 U v1 v2
## <chr> <chr> <dbl> <dbl> <dbl> <dbl> <dbl>
## 1 x0 "C | C" 2 2 4 0 0
## 2 x.paradise " | " 2 2 4 2 2We see that the optimal simple SPE can implement (C,C) in the truncated game. This means there is no RNE in which (D,D) is played on the equilibrium path.
Now let us assume that we have an RNE that would implement (C,C) on the equilibrium path. This would yield negotiation payoffs of 2 for each player in state x0. Let us compute the optimal simple SPE in the corresponding truncated game.
# Solve SPE in truncated game assuming given negotiation payoffs # r1 and r2 that result if (C,C) could be implemented g = rel_spe(g, delta=0.5, rho=0.5, r1 = c(2,2), r2=c(2,2)) g %>% get_eq() %>% select(x,ae.lab,r1,r2,U,v1,v2)
## # A tibble: 2 x 7
## x ae.lab r1 r2 U v1 v2
## <chr> <chr> <dbl> <dbl> <dbl> <dbl> <dbl>
## 1 x0 "D | D" 0.667 0.667 1.33 0.667 0.667
## 2 x.paradise " | " 2 2 4 2 2With these negotiation payoffs only (D,D) can be implemented in the truncated game! For the intuition, note that if one deviates from (C,C), one does not move to paradise. Yet, higher negotiation payoffs in state x0 can make this state sufficiently attractive compared to paradise so that deviation from (C,C) cannot be deterred anymore.
So (C,C) could only be implemented if and only if players assume that (D,D) will be implemented in future negotiations. That causes existence failure of RNE.
The non-existence problem arises because any assumed negotiation outcome in state x0 creates a contradiction. One solution to these contradictions might be that players allow different negotiation outcomes if state x0 is reached repeatedly. We can model this by artificially splitting the state x0 into multiple states e.g. x0 and x1 in which exactly the same stage game is played but different negotiation outcomes would be allowed.
Perhaps a first thought that comes to mind is that the first period is different. Let us assume in the first period, we start in state x0 but in in later periods the prisoners’ dilemma state is labeled state x1 and may have a different negotiation outcome.
# Game in which PD state is called x0 in first period # and x1 in later periods. g = rel_game() %>% rel_states(c("x0","x1"), A1=A1, A2=A2, pi1.form=pi1, pi2.form=pi2) %>% rel_state("x.paradise", pi1=2, pi2=2) %>% rel_transition("x0","x.paradise",a1="C",a2="C") %>% rel_transition("x0","x1",a1="D") %>% rel_transition("x0","x1",a2="D") %>% rel_transition("x1","x.paradise",a1="C",a2="C") %>% rel_compile()
As we still have a weakly directional game, we can directly compute the RNE. Simple theoretical arguments can show that an RNE for a coarser state remains an RNE if we create a finer state space by splitting states into multiple states with different labels. We will show further below that an appropriately chosen finer state space can cause an RNE to exist, i.e. in general new RNE can show up with a finer state space. Yet, looking at our previous two examples for which RNE existed, we essentially find again the same RNE:
# RNE with mutual cooperation rel_rne(g,delta = 0.5, rho=0.1) %>% get_eq() %>% select(x,ae.lab, a1.lab, a2.lab, r1,r2,U,v1,v2)
##
## Solve weakly directional state x1 ... ok## # A tibble: 3 x 9
## x ae.lab a1.lab a2.lab r1 r2 U v1 v2
## <chr> <chr> <chr> <chr> <dbl> <dbl> <dbl> <dbl> <dbl>
## 1 x0 "C | C" "D | D" "D | D" 2 2 4 0.182 0.182
## 2 x1 "C | C" "D | D" "D | D" 2 2 4 0.182 0.182
## 3 x.paradise " | " " | " " | " 2 2 4 2 2# Lower discount factor: RNE has mutual defection rel_rne(g,delta = 0.2, rho=0.1) %>% get_eq() %>% select(x,ae.lab, a1.lab, a2.lab, r1,r2,U,v1,v2)
##
## Solve weakly directional state x1 ... ok## # A tibble: 3 x 9
## x ae.lab a1.lab a2.lab r1 r2 U v1 v2
## <chr> <chr> <chr> <chr> <dbl> <dbl> <dbl> <dbl> <dbl>
## 1 x0 "D | D" "D | D" "D | D" 0 0 0 0 0
## 2 x1 "D | D" "D | D" "D | D" 0 0 0 0 0
## 3 x.paradise " | " " | " " | " 2 2 4 2 2Now let’s look at the case delta=0.5 and rho=0.5 for which no RNE existed with a single state x0. Will we now find an RNE where in state x0 (first period) (C,C) is played and in later periods (D,D)?
##
## Solve weakly directional state x1 ...## Error in rel_rne(g, delta = 0.5, rho = 0.5): Cannot find an RNE when trying to solve the weakly directional state x1Unfortunately, not. Still no RNE exists. While in state x0 (C,C) could be implemented, assuming that in state x1 always (D,D) would be played causes the same problem as if there would be just a single state: the continuation equilibria from period 2 onward don’t satisfy the RNE conditions.
However, there is another split of the original state x0 such that an RNE exists. Assume that the states x0 and x1 alternate each period as long as paradise is not yet reached. Then there is an RNE where in state x0 (C,C) is played and in state x1 (D,D) (and another RNE the other way round).
Unfortunately, since this is not a weakly directional game the RelationalContracts package has no function to automatically compute the corresponding RNE. But we can semi-automatically verify that an RNE exists. First, we want to compute the joint continuation payoffs U of a SPE with these action profiles. We can specify it by solving the following helper game, where we have fixed stage game payoffs according to these equilibrium path action profiles:
helper.game = g = rel_game() %>% # Assume (C,C) is played in x0 rel_state("x0", pi1=2, pi2=2) %>% # Assume (D,D) is played in x1 rel_state("x1", pi1=0, pi2=0) %>% rel_state("x.paradise", pi1=2, pi2=2) %>% rel_transition("x0","x.paradise") %>% rel_transition("x1","x0") %>% rel_compile() helper.game %>% rel_spe(delta=0.5, rho=0.5) %>% get_eq() %>% select(x,U)
## # A tibble: 3 x 2
## x U
## <chr> <dbl>
## 1 x0 4
## 2 x1 2
## 3 x.paradise 4We get nice round joint payoffs of U(x0)=4 and U(x1)=2. Negotiation payoffs just split these joint payoffs equally, i.e. r1(x0)=r2(x0)=2 and r1(x1)=r2(x1)=1.
We now specify the true game with alternating states x0 and x1 and solve for the SPE in the truncated game with these negotiation payoffs.
# x0 and x1 alternate g = g01 = rel_game() %>% rel_states(c("x0","x1"), A1=A1, A2=A2, pi1.form=pi1, pi2.form=pi2) %>% rel_state("x.paradise", pi1=2, pi2=2) %>% rel_transition("x0","x1",a1="D") %>% rel_transition("x0","x1",a2="D") %>% rel_transition("x1","x0",a1="D") %>% rel_transition("x1","x0",a2="D") %>% rel_transition("x0","x.paradise",a1="C",a2="C") %>% rel_transition("x1","x.paradise",a1="C",a2="C") %>% rel_compile() g %>% rel_spe(delta=0.5, rho=0.5, r1 = c(2,1,2), r2=c(2,1,2)) %>% get_eq() %>% select(x,ae.lab,r1,r2,U,v1,v2)
## # A tibble: 3 x 7
## x ae.lab r1 r2 U v1 v2
## <chr> <chr> <dbl> <dbl> <dbl> <dbl> <dbl>
## 1 x0 "C | C" 2 2 4 0.4 0.4
## 2 x1 "D | D" 1 1 2 0.6 0.6
## 3 x.paradise " | " 2 2 4 2 2We indeed find that the optimal simple SPE in this truncated game implements (C,C) in state x0 and (D,D) in state x1 which also yields the assumed negotiation payoffs. Hence, we have constructed an RNE!
The intuition is as follows: deviating from (C,C) in state x0 is not too attractive since one would end up in state x1 that has relatively low negotiation payoff since newly negotiated relational contracts in state x1 start with (D,D). This allows to implement (C,C) in state x0 . However, in state x1 it would be more attractive to deviate from (C,C) since one ends up in state x0 with higher negotiation payoffs since newly negotiated relational contracts start with (C,C). Therefore, only (D,D) can be implemented in state x1.
We will now move back to the original game with a single state x0 and solve a T-RNE. We set T=100, which means that in the first 100 periods the relational contract will be newly negotiated with probability rho each period and in later periods no new negotiation takes place and players will essentially follow a Pareto-optimal SPE. A T-RNE essentially makes the actual period t<=T part of the state definition, i.e. negotiation outcome in state x0 can differ between periods. T-RNE always exist and can be quite quickly computed numerically: Let’s directly look at T-RNE for delta=0.5 and rho=0.5 for which no RNE existed in the coarse state space:
g = g0 # Set to initial game without state x1 # Solve a T-RNE g = rel_T_rne(g,T=100, delta=0.5, rho=0.5, save.history = TRUE) # Show results for earliest 6 periods get_T_rne_history(g) %>% filter(x=="x0", t <= 6) %>% arrange(t) %>% select(t,ae.lab,r1,r2,U,v1,v2)
## # A tibble: 6 x 7
## t ae.lab r1 r2 U v1 v2
## <dbl> <chr> <dbl> <dbl> <dbl> <dbl> <dbl>
## 1 1 C | C 2 2 4 0.4 0.4
## 2 2 D | D 1 1 2 0.6 0.6
## 3 3 C | C 2 2 4 0.4 0.4
## 4 4 D | D 1 1 2 0.6 0.6
## 5 5 C | C 2 2 4 0.4 0.4
## 6 6 D | D 1 1 2 0.6 0.6We see that the equilibrium path actions in the T-RNE always alternate each period between (C,C) and (D,D) and one can verify that this alternation indeed continues up to t=T. So essentially, the T-RNE automatically reconstructs the finer state space partition with x0 and x1 for which an RNE exists. So while on first thought cycling T-RNE may seem undesirable, they actually construct here a quite intuitive solution for the Gangsta’s Paradise game.
Note that for other parameter constellations, there can be longer cycles. For example, if we increase the discount factor to delta=0.6 we get three period cycles with (C,C), (C,C), (D,D) :
g = rel_T_rne(g,T=100, delta=0.6, rho=0.5, save.history = TRUE) get_T_rne_history(g) %>% filter(x=="x0", t <= 6) %>% arrange(t) %>% select(t,ae.lab,r1,r2,U,v1,v2)
## # A tibble: 6 x 7
## t ae.lab r1 r2 U v1 v2
## <dbl> <chr> <dbl> <dbl> <dbl> <dbl> <dbl>
## 1 1 D | D 1.2 1.2 2.4 0.835 0.835
## 2 2 C | C 2 2 4 0.783 0.783
## 3 3 C | C 2 2 4 0.610 0.610
## 4 4 D | D 1.2 1.2 2.4 0.835 0.835
## 5 5 C | C 2 2 4 0.783 0.783
## 6 6 C | C 2 2 4 0.610 0.610Here the cycle starts with (D,D), but that is not essential and just depends on our value for T. E.g. with T=102 the cycle starts with the two cooperative periods.
g = rel_T_rne(g,T=102, delta=0.6, rho=0.5, save.history = TRUE) get_T_rne_history(g) %>% filter(x=="x0", t <= 6) %>% arrange(t) %>% select(t,ae.lab,r1,r2,U,v1,v2)
## # A tibble: 6 x 7
## t ae.lab r1 r2 U v1 v2
## <dbl> <chr> <dbl> <dbl> <dbl> <dbl> <dbl>
## 1 1 C | C 2 2 4 0.783 0.783
## 2 2 C | C 2 2 4 0.610 0.610
## 3 3 D | D 1.2 1.2 2.4 0.835 0.835
## 4 4 C | C 2 2 4 0.783 0.783
## 5 5 C | C 2 2 4 0.610 0.610
## 6 6 D | D 1.2 1.2 2.4 0.835 0.835We can verify that splitting the state x0 now into three states x0 , x1 and x2 an RNE with that cycle exists. To specify the truncated game, we can use the negotiation payoffs from the T-RNE outcome. (In other examples, the T-RNE negotiation payoffs may only be approximately correct and improve for large T, but in this example things work out nicely):
g012 = rel_game() %>% rel_states(c("x0","x1","x2"), A1=A1, A2=A2, pi1.form=pi1, pi2.form=pi2) %>% rel_state("x.paradise", pi1=2, pi2=2) %>% rel_transition("x0","x1",a1="D") %>% rel_transition("x0","x1",a2="D") %>% rel_transition("x1","x2",a1="D") %>% rel_transition("x1","x2",a2="D") %>% rel_transition("x2","x0",a1="D") %>% rel_transition("x2","x0",a2="D") %>% rel_transition("x0","x.paradise",a1="C",a2="C") %>% rel_transition("x1","x.paradise",a1="C",a2="C") %>% rel_transition("x2","x.paradise",a1="C",a2="C") %>% rel_compile() # Solve SPE of truncated game. Use r1 and r2 from # T-RNE solved above g012 %>% rel_spe(delta=0.6, rho=0.5, r1 = c(2,2,1.2,2), r2=c(2,2,1.2,2)) %>% get_eq() %>% select(x,ae.lab,r1,r2,U,v1,v2)
## # A tibble: 4 x 7
## x ae.lab r1 r2 U v1 v2
## <chr> <chr> <dbl> <dbl> <dbl> <dbl> <dbl>
## 1 x0 "C | C" 2 2 4 0.783 0.783
## 2 x1 "C | C" 2.00 2 4 0.610 0.610
## 3 x2 "D | D" 1.2 1.2 2.4 0.835 0.835
## 4 x.paradise " | " 2 2 4 2 2We find that the optimal SPE in the truncated game indeed implements the same cycle as the T-RNE and the resulting negotiation payoffs are equal to the assumed ones, i.e. we have found an RNE on this finer state space.
Our theoretical analysis of the Gangsta’s Paradise game in our paper reveals that for delta=1/3 mutual cooperation could be implemented in the truncated game if and only if the negotiation payoffs outside paradise are exactly 0.
As we converge with the discount factor from above towards 1/3 with a positive negotiation probability, the T-RNE cycles become larger and larger. E.g.
g = g0 # Set to initial game without state x1 # Solve a T-RNE g = rel_T_rne(g,T=505, delta=0.3334, rho=0.5, save.history = TRUE,tol=1e-12) # Show results for earliest 6 periods hist = get_T_rne_history(g) hist %>% filter(x=="x0", t <= 12) %>% arrange(t) %>% select(t,ae.lab,r1,r2,U,v1,v2)
## # A tibble: 12 x 7
## t ae.lab r1 r2 U v1 v2
## <dbl> <chr> <dbl> <dbl> <dbl> <dbl> <dbl>
## 1 1 C | C 2 2 4 0.000102 0.000102
## 2 2 D | D 0.000305 0.000305 0.000611 0.000304 0.000304
## 3 3 D | D 0.000916 0.000916 0.00183 0.000909 0.000909
## 4 4 D | D 0.00275 0.00275 0.00549 0.00270 0.00270
## 5 5 D | D 0.00824 0.00824 0.0165 0.00798 0.00798
## 6 6 D | D 0.0247 0.0247 0.0494 0.0232 0.0232
## 7 7 D | D 0.0741 0.0741 0.148 0.0649 0.0649
## 8 8 D | D 0.222 0.222 0.445 0.167 0.167
## 9 9 D | D 0.667 0.667 1.33 0.333 0.333
## 10 10 C | C 2 2 4 0.000102 0.000102
## 11 11 D | D 0.000305 0.000305 0.000611 0.000304 0.000304
## 12 12 D | D 0.000916 0.000916 0.00183 0.000909 0.000909The knife-edge case of delta=1/3 can be seen as the limit case, with an infinitely long cycle. (Due to floating point arithmetic inaccuracies, we will still find a finite cycle when solving this knife-edge case numerically.) In this knife-edge case, splitting the state space into a finite finer partition would not help to reestablish existence of an RNE. Our blackmailing game example seems to be a similar knife-edge case.
Of course, the examples suggest the conjecture that for general stochastic games one could generically (i.e. except for certain knife-edge cases) partition the state space into a finite set of finer states (using only time t not any other aspects of the played history for this partition) such that then an RNE exists. Unfortunately, we honestly have no clue how to prove such a conjecture (nor how to cleanly formulate what generically means in this context). We even don’t have a strong intuition whether the conjecture holds. So we would relegate this question to future research.
One may have wondered whether these cycles are due to some special assumption in the definition of RNE or T-RNE. Yet, in this last section, we want to show that Markov perfect equilibria exhibit similar behavior. The following game finds an MPE of the original game with a single prisoners’ dilemma state x0 for delta=0.5:
rel_mpe(g0,delta = 0.5) %>% get_mpe()
## # A tibble: 2 x 6
## x u1 u2 ae ae.a1 ae.a2
## <chr> <dbl> <dbl> <dbl> <chr> <chr>
## 1 x0 0 0 4 D D
## 2 x.paradise 2 2 1 <NA> <NA>Players will mutually defect. The algorithm tries to find a single MPE but in principle there could be more MPE. The function rel_mpe has the argument a.init.guess that allows to specify an initial guess of the action profiles played in an MPE. If an MPE with these action profiles exists it will be returned. Let us check whether also an MPE with mutual cooperation exists:
# Action profile indeces can be seen by looking at g$ax.grid # 1 = (C,C) 4=(D,D) rel_mpe(g0,delta = 0.5, a.init.guess = c(1,1)) %>% get_mpe()
## # A tibble: 2 x 6
## x u1 u2 ae ae.a1 ae.a2
## <chr> <dbl> <dbl> <dbl> <chr> <chr>
## 1 x0 0 0 4 D D
## 2 x.paradise 2 2 1 <NA> <NA>No. The algorithm again returns the MPE where(D,D) is played. This means the highest MPE payoff is 0 in this game.
Let us now compute MPE in the game variant in which state x0 is split in alternating states x0 and x1. The MPE where always (D,D) is played obviously still exists and it will also be found by default with our algorithm:
rel_mpe(g01,delta = 0.5) %>% get_mpe()
## # A tibble: 3 x 6
## x u1 u2 ae ae.a1 ae.a2
## <chr> <dbl> <dbl> <dbl> <chr> <chr>
## 1 x0 0 0 4 D D
## 2 x1 0 0 4 D D
## 3 x.paradise 2 2 1 <NA> <NA>But let’s check whether there is also an MPE where (C,C) is played in state x0 and (D,D) ins state x1 by providing these action profiles as initial guess:
## # A tibble: 3 x 6
## x u1 u2 ae ae.a1 ae.a2
## <chr> <dbl> <dbl> <dbl> <chr> <chr>
## 1 x0 2 2 1 C C
## 2 x1 1 1 4 D D
## 3 x.paradise 2 2 1 <NA> <NA>Indeed this MPE also exists and it Pareto-dominates the MPE where always (D,D) is played. MPE are not plagued by non-existence because there is no requirement to always pick a Pareto-optimal MPE. But otherwise the behavior seems similar to that of RNE. Picking a finer state space allows more efficient MPE to pop-up. While this point is obvious if one would e.g. define the history of the game as part of the state, it interestingly also arises just by assuming that states alternate each period. In this sense one could argue that the “finer state-space effects” and “cycle effects” of RNE and T-RNE are in some sense inherited from MPE.