Monday, October 25, 2021

Should everyone always lose semi-coop games?

Unfortunately, in order to answer this question, we have to do a bit of taxonomy first, as "semi-coop", short for semi-cooperative, means different things to different people.

Some people call hidden team games like Battlestar Galactica and/or cooperative games with a possible traitor like Shadows over Camelot semi-coops. I can see the motivation for this as they look like a "cooperative, but ..." game, yet it doesn't seem necessary to differentiate these from other team games like Space Cadets: Dice Duel, Codenames, and The Resistance.


Instead, we are talking about games like CO2, Legendary, and Dead of Winter. The through-line seems to be that these are games where players do not always win together (like a cooperative game), but they may all lose together. However, that definition includes games like Galaxy Trucker, which I don't think anyone would consider a semi-coop. A more precise definition would be that there is a condition that if not met means that none of the non-traitor players are eligible to win and instead lose. I specify non-traitor because many, but not all, of these games feature a traitor, who is essentially on a team with the game trying to make the rest of the players lose.


Within this definition I see three types of semi-coop, which have important distinctions that we'll get to.


In type I semi-coops, or single-winner semi-coops, either all players lose or one player wins while all other players lose. Examples include CO2 (in "mostly competitive" mode), Robin Hood and the Merry Men, Castaways, and Divided Republic. Examples that include a possible traitor are AuZtralia, Homeland, and Republic of Rome (which has an opt-in traitor).


In type II semi-coops, or group-win semi-coops, there are two types of winning. Either all players lose or all players win, but if all players win there is also an individual winner. Examples include Legendary, Castle Panic (although it only uses the word "win" for the group win), Arkham Horror (group win plus "honorary title of First Citizen of Arkham"), Horizon Zero Dawn (although the terminology is confusing "Although all players have won..., the player with the most victory points...emerges as the winner of the game"), and Tomorrow (mentions "win" for both, but in separate sections of the rulebook). Archipelago is an example with a possible traitor.


Type III semi-coops, or separate-goal semi-coops, have separate win conditions for each player in addition to the group loss. An example is Forgotten Waters. Examples with a possible traitor include Dead of Winter, Nemesis, and New Angeles. Dead of Winter labels itself as a "meta-cooperative" game, but the term doesn't seem to have caught on, though it may be useful to describe type III semi-coops.


Games that don't fit this definition but some may call semi-coops include Cutthroat Caverns, Crisis, Bag of Dungeon (using an optional advanced rule), Hellapagos (whoever gets rescued wins, which can be any subset of players), Fog of Love (each player's performance is determined individually), Pax Emancipation (which has a first phase after which the game may end with any number of players may win except all, as well as a possible second phase which is purely competitive) and Core Space (which has the odd combination of a group win if an objective is completed and an individual win if it is not). While these games do feature the possibility of everyone losing, this is usually still determined on a per-player basis.


Type I: single-winner semi-coops


Let's look at a simplified model of a three player type I semi-coop game. Each player has two moves and chooses simultaneously: cooperate (C) or defect (D). If at least two players cooperate, this prevents the all lose scenario. If one player defects, that player is the winner. If all players cooperate, then the winner is randomly select from them.  This is depicted in Table 1, where each row represents an outcome based on the first player's move (P1), while each column represents the combined moves of the second and third players (P2 & P3).


\begin{align*} \begin{array}{c |c|c|c} \text{P1 \\P2 & P3} & 2 D & 1D, 1C & 2C \\ \hline D & \text{All lose} & \text{All lose} & \text{P1 wins} \\ C & \text{All lose} & \text{P2 or P3 wins} & \text{P1 may win} \end{array} \end{align*} 
Table 1: A simple type I semi-coop game


Type I semi-coops have the issue that the best move is to defect, as defecting is a weakly dominant strategy, meaning that defecting is sometimes better but never worse than cooperating. This is perhaps more clear in Table 2, which is focused on the first player. Additionally, if players put any positive value to have fellow players also lose (that is, any preference for all lose to someone else wins), then defecting is even more incentivized, but remains a weakly dominant strategy.


\begin{align*} \begin{array}{c |c|c|c} \text{P1 \P2 & P3} & 2 D & 1D, 1C & 2C \\ \hline D & \text{Lose} & \text{Lose} & \text{Win} \\ C & \text{Lose} & \text{Lose} & \text{May win} \end{array} \end{align*}

Table 2: First player's outcomes simple type I semi-coop game


Note that this model only holds if two players cannot easily spoil the victory of another. Additionally, it assumes individual victory and avoiding group loss are at odds with each other. This trade-off is not inherent. For example, suppose you have a game where players earn points throughout the game and all players lose if the sum of the points of all players is not sufficiently high. Now, consider two metrics for individual victory. In the first, the player with the fewest number of points is the individual winner. Here, as long as you lack the ability to manipulate other player's points, the lessons we learned above hold and we wouldn't expect there to be a winner (depending on the total point threashold), as all players tries to minimize their own scores. However, in the second metric, the player with the most number of points is the individual winner. Here, actions that avoid a group loss and obtain individual victory are likely perfectly aligned (there are likely some exceptions due to interactions with other players). Since players are trying to maximize their own scores to be the individual winner, the group loss condition is easily avoided. Of course, in such a situation, you may ask why a group loss condition is included in the game. (While I doubt such a game exists, you could include the rule to avoid dominant strategies that end the game very quickly and are not satisfying in some way. There may be better solutions than making the game semi-cooperative.) The defect or cooperate paradigm does not match with this second metric for an individual win.


Type II: group-win semi-coops


Let's move onto the more interesting type II semi-coop. Table 3 shows another model of a simple simultaneous-play semi-coop game. This time we've adjusted the values both to represent a type II semi-coop, but also to look at the payoffs for the first player, so that we can make use of a game theory analysis. We will assume that all lose is valued at 0, while group win or all win ($AW$) and individual win ($IW$) each have some positive unknown value (but common to all players).


\begin{align*}
\begin{array}{c |c|c|c}
\text{P1 \P2 & P3} & 2 D & 1D, 1C & 2C \\ \hline
D & 0 & 0 & AW+IW \\
C & 0 & AW &AW+\frac{1}{3}IW
\end{array}
\end{align*}
Table 3: A simple type II semi-coop game


First, let's acknowledge some fragility to this system. Akin to how competitive games can break down if any of the players are not trying to win (it seems relevant to quote Reiner Knizia: "Remember: When playing a game, the goal is to win, but it is the goal that is important, not the winning..."), semi-cooperative games can break down if players do not accept the payoffs given by the game. While competitive games have their payoffs generally accepted and understood by most people, semi-cooperative games are more rare, especially type II semi-coops, which have multiple types of winning. Some players may ignore one or the other type of winning. If $IW$ is valued at 0, then the game is essentially cooperative, and all players will cooperate as it is a weakly dominant strategy. If $AW$ is valued at 0, then the game reverts to a type I. Some people also reject the idea that a group win is better than a group loss in a type II semi-coop (the interpretation is that in the case of a group loss, all players do as well as each other and so the game ends in a draw, which is preferable to a group win where you are losing to another player; the latter is interpreted as a simple loss), essentially valuing $AW<0$. In that case, as in type I, defecting is a weakly dominant strategy (it's better if exactly one other player cooperates, but doesn't matter if both others either cooperate or defect together). Under such a valuing of the outcomes the game breaks down as it does in a Type I semi-coop. Conversely, players of a Type I semi-coop may value avoiding the all-lose condition such that they effectively add a group win, turning it into a type II semi-coop. We will proceed assuming all players accept the value of both types of winning, while also acknowledging there is some ambiguity in that these games do not specify how much to care about the two types of winning relative to each other.


In this type II semi-coop there is no obviously best move. If both other players defect, it doesn't matter what the first player does. If one other player defects but one cooperates, then cooperation is preferred as this ensures that all win (including player one). On the other hand, if both other players cooperate, then defection is preferred, as that move guarantees obtaining the individual win.


This type II semi-coop has several Nash Equilibria. The first three pure-strategy Nash Equilibria are the cases where one player defects while the other two cooperate. There are three, because there's one for each player being the defector. This is a Nash Equilibrium because no player can do better by changing strategy. Suppose the first player is defecting while the other two are cooperating. This puts us in the third column. The first player is better off with a definite individual win than a one-third chance of an individual win. In both cases, the group win condition is guaranteed. The second and third players each face the choice between a group win and a group loss. Neither can unilaterally do anything to do better given the strategies of the other players. A lesson that we can take from this model is that if you can be the first to convince other players that you either have or will defect, you will likely be the individual winner. As such, these games may have a strong first-player advantage, depending on how quickly a player can establish defection.


Another pure strategy Nash Equilibrium is if all players defect. With all players defecting, the all lose outcome occurs, but no single player is in a position to change it. Here it is evident that the Nash Equilibrium is really about stability not about a how good a set of strategies is. Note that in this situation, though, any player may deviate from a defection strategy without detriment.


There is also a mixed-strategy (a mixed-strategy employs one of a number of pure strategies with a given set of corresponding probabilities) Nash Equilibrium of cooperate and defect. The mix depends on the relative valuing of the different outcomes. To find this Nash Equilibrium, we'll make use of the fact that we know that each component strategy must be a best response and have the same average payout. So the payout of defect and cooperate must be the same. Assume in the equilibrium that each player cooperates with probability $p$, and thus defects with probability $1-p$. The probability that both players 2 and 3 cooperate is $p^2$. The probability that they do one of each is $2 \cdot p \cdot (1 - p)$. Recall that the 2 comes from the fact that either player could be the one that cooperates, so there are two ways that it happens. The payoff for player one are thus as follows.

\begin{align}
u(D) &= p^2 \cdot \left ( AW + IW \right ) \\
u(C) &= 2 p(1-p) \cdot AW + p^2 \cdot \left ( AW +\frac{1}{3} IW \right )
\end{align}

So let's set these equal to find $p$.
\begin{align}
u(D) &= u(C) \\
p^2 \cdot \left ( AW + IW \right ) &= 2 p(1-p) \cdot AW + p^2 \cdot \left ( AW +\frac{1}{3} IW \right ) \\
p^2 \cdot \left (\frac{2}{3} IW \right ) &= 2 p(1-p) \cdot AW \\
p\cdot \frac{2}{3} IW &= 2 (1-p) \cdot AW \\
p\cdot \left (\frac{2}{3} IW + 2AW \right ) &= 2\cdot AW \\
p &= \frac{2 AW}{\frac{2}{3} IW + 2AW}
\end{align}


We can see our earlier conclusions about the simplified cases fall out from this. If $AW=0$, then $p=0$, as we're in the type I semi-coop case. If $IW=0$, then the game is cooperative and $p=1$. For positive values of both AW and IW, though, we find $0 < p < 1$. Note that this works even if having everyone win is valued significantly above having the individual win, as an individual win requires a group win. We can rewrite this based on the ratio of the two values, $r = AW / IW$.


\begin{align}
p &= \frac{2 AW}{\frac{2}{3} IW + 2AW} \\
p &= \frac{2 \frac{AW}{IW}}{\frac{2}{3} + 2\frac{AW}{IW}} \\
\require{cancel}p &= \frac{\cancel{2}\cdot 3 \frac{AW}{IW}}{\cancel{2} + \cancel{2}\cdot3\cdot\frac{AW}{IW}} \\
p& = \frac{3r}{1 + 3r}
\end{align}

This is a monotonically increasing function, as shown in Figure 1, so the more we care about the group win compared to the individual win, the more we cooperate (this is expected and perhaps obvious).


Figure 1: Probability of Cooperation in a Type II Semi-cooperative Game with Equal Player Standing


Suppose we value them equally, such that achieving individual victory has twice the total utility as being part of a group win. This means that we'll cooperate with probability $p=3/4$ or 75% of the time.


Operating under this strategy, we can find the probability that the group wins. This occurs when at most one player defects. The probability that all players cooperate is $p^3$. The probability that one player defects is $3\cdot p^2 \cdot (1-p)$. For $p=3/4$, this means the probability of a group win is,

\begin{align}
P(AW) &= p^3 + 3 \cdot p^2 \cdot (1-p) \\
&= 3p^2 - 2p^3 \\
&= 3 \cdot \left (\frac{3}{4} \right ) ^2 - 2 \cdot \left ( \frac{3}{4} \right ) ^3\\
&\approx 0.84.
\end{align}

This is shown in Figure 2 as a function of the ratio $r$.


Figure 2: Probability of Successful Cooperation in a Type II Semi-cooperative Game with Equal Player Standing


Type II with unequal standing


Now, let's consider a case where the players do not have equal standing. This perhaps models the end of the game. Let's assume players 1, 2, and 3 are in that rank, such that if all cooperate, then player 1 will win. However, if any one player defects (with the other two cooperating) the defecting player wins.


\begin{align*}
\begin{array}{c |c|c|c}
\text{P1 \ P2 & P3} & 2 D & 1D, 1C & 2C \\ \hline
D & 0 & 0 & AW+IW \\
C & 0 & AW &AW+IW \\
\end{array}
\end{align*}

Table 4: A simple type II semi-coop game for player 1 while ahead


Here, for player 1, cooperate is weakly dominant, since the individual win is ensured if all player cooperate. Thus, player 1 likely cooperates.


\begin{align*}
\begin{array}{c |c|c|c}
\text{P2/3 \ P1 & P3/2} & 2 D & 1D, 1C & 2C \\ \hline
D & 0 & 0 & AW+IW \\
C & 0 & AW &AW
\end{array}
\end{align*}

Table 5: A simple type II semi-coop game for players 2 or 3 while behind


However, players 2 and 3 are much more like the earlier analysis. We can check the previous Nash Equilibria to see if they still hold. All defect still is, as well as cases where any one player defects while the other two cooperate. However, player 1 defecting and others cooperating is now a weak Nash Equilibrium, as player 1 is no worse off for cooperating.


Due to the asymmetry introduced, when looking for an updated mixed-strategy Nash Equilibrium, let's say that the first player cooperates with probability $p_1$ and the second and third players each cooperate with probability $p_2$. We can now employ similar techniques as before, however, we'll have more equations as we have a new variable. We'll still assume that $AW$ and $IW$ are valued equally between all players. First, let's look at the payoffs for player 1.

\begin{align}
u(D_1) &= p_2^2 \cdot \left ( AW + IW \right ) \\
u(C_1) &= 2 p_2(1-p_2) \cdot AW + p_2^2 \cdot \left ( AW + IW \right ) \\
u(D_1) &= u(C_1)
\end{align}

From this point, we just do some algebra.

\begin{align}
\require{cancel}\cancel{p_2^2 \cdot \left ( AW + IW \right )} &= 2 p_2(1-p_2) \cdot AW + \cancel{p_2^2 \cdot \left ( AW + IW \right )}\\
0 &= 2 p_2(1-p_2) \cdot AW
\end{align}

Here there are two solutions, $p_2=0$ and $p_2=1$. This is somewhat of a contradiction, as we assumed a mixed-strategy for players 2 and 3, yet here we get pure strategies. If we look at the payoffs for player 1, we see the incorrect assumption that we made: that player 1 plays a mixed strategy. Cooperating is always as good as defection for player 1, and sometimes better. If players 2 and 3 are playing mixed strategies, then we should expect that sometimes one will cooperate and one will defect, which means that the only way for player 1 to have a best response 100% of the time is to cooperate.


Knowing this, we can actually simplify the game from, since we know player 1 will cooperate.


\begin{align*}
\begin{array}{c|c|c}
\text{P2/3 \ P3/2} & D & C \\ \hline
D & 0 & AW+IW \\
C & AW &AW
\end{array}
\end{align*}

Table 6: A simple type II semi-coop sub-game for players 2 & 3 if player 1 cooperates


Again using $p_2$ for the probability of cooperation for only players 2 and 3, we can find the payoffs for each move. We'll repeat the same method of setting the payoffs equal to each other.

\begin{align}
u(D) &= u(C)\\
p_2 \cdot \left (AW+IW \right ) &= AW\\
p_2 &= \frac{AW}{AW+IW}\\
p_2 &= \frac{r}{1+r}
\end{align}

We find a probability of cooperation which is lower than before (assuming the same values of ratio of the value of the group win AW to the individual win IW). For equal values ($r=1$), $p_2=0.5$, only 50%! This makes sense, as there's less incentive now to cooperate. A graphical comparison is presented in Figure 3.


Figure 3: Probability of Cooperation in a Type II Semi-cooperative Game with 2 Players Behind a Leader compared to Equal Standing

However, did this decrease the probability of a group win?

\begin{align}
P(AW) &= p_2^2 + 2\cdot p_2 \cdot (1-p_2) \\
&=2p_2 - p_2^2\\
&=0.75
\end{align}

This did somewhat decrease the probability of a group win, but perhaps not by as much as we might have thought. As shown in Figure 4, there are even some cases where the probability of successful cooperation is higher than with equal standing, although this is only when the group win is valued at a small fraction of the individual win.


Figure 4: Probability of Successful Cooperation in a Type II Semi-cooperative Game with 2 Players Behind a Leader compared to Equal Standing


Type III: separate-win semi-coops


Since type III semi-cooperative games, or meta-cooperative games, do not rank players to determine a winner, there is not the same kind of concept of cooperating vs. defecting as in the analyses we performed thus far. There may still be tension between avoiding the all-lose outcome and achieving personal goals, but this tension is not directly influenced by the situation of other players.


Conclusion


To recap, we saw that in a simple type I semi-coop game, where either all lose or there is one winner, we somewhat expect that all players lose.  (Note that while this may be a strategically unsatisfying play experience, it may be interesting art or commentary.) This is the only Nash Equilibrium and defecting is a weakly dominant strategy. If we add a group win, thus converting to a type II semi-coop, we can avoid this, as there are stable states where all players win. However, this is subject to the strategies employed by the players. If a majority of the players demand to get advantage for the individual win by defecting, then all will lose, and all players defecting is also a Nash Equilibrium. Additionally, even in the case where the group win is achieved, this could be because a certain player is defecting while the others cooperate. Such a condition may be unpleasantly static.  


So the answer is no, as players in a group-win semi-coop may be able to rationally achieve cooperation.