Police versus Guerillas

Police versus Guerillas#

We will investigate a genre of games called Police versus Guerrillas. The idea is that an insurgency (the guerrilla force) is striking against the government (the police). The police have two arsenals filled with weapons and amunition, and the guerrillas would like to take either one of them, or both, if possible.

Game Play#

The police defend $2$ arsenals and the guerrillas win if they can take over either one, or both. The two players know at nightfall when the attack(s) will take place, but the police do not know how many attackers will be which locations. The guerrillas do not know how the police will arrange their forces.

Key: The police hold an arsenal if an equal number of attacking and defending units engage there.

Suppose the police have $4$ units. For a strategy such as

3 - 1

they will randomize their choice of which arsenal to send their greater force to protect.

If the guerrillas have $3$ units with which they can attack, they may play a strategy like

2 - 1

As do the police, the guerrillas will randomly select to which of the arsenals they will the greater force.

Units#

We must decide before analyzing outcomes the configuration of forces for both players. The police will have $p$ units with which they may defend the arsenals while the guerrillas will have $g$ units with which they can attack. Since $p\geq 2g$ implies the police always win by dividing their forces equally, and $p\leq g$ implies the guerrillas always have a winning strategy (send all their forces to one arsenal), we must only solve games where

\[g < p < 2g\]

Common scenarios would have us analyzing

5P vs 3G
7P vs 5G, or
8P vs 7G

Example: 3 Police versus 2 Guerrillas#

The police with $3$ units have only two distinct strategies:

$\textbf{3 - 0}$
$\textbf{2 - 1}$

The strategies of $\textbf{0 - 3}$ and $\textbf{2 - 1}$ are just permutations of the above strategies that will randomize in exactly the same way. Therefore, we only need to analyze the two shown in the bullets above.

The guerrillas with $2$ units have two distinct stragegies:

$\textbf{2 - 0}$
$\textbf{1 - 1}$

Hence, the game they are playing can be shown in matrix form:

\[\begin{split}\begin{array}{cc}&\textbf{Guerrillas}\\\textbf{Police}& \begin{array}{r|cc} & \textbf{2 - 0} & \textbf{1 - 1}\\ \hline \textbf{3 - 0} & \frac{1}{2} & 0 \\ \textbf{2 - 1} & \frac{1}{2} & 1 \end{array} \end{array}\end{split}\]

Notice the outcome of $\textbf{3 - 0}$ versus $\textbf{2 - 0}$ is an expected value. Half the time, the units will be sent to the same arsenal, and the police will win. When the units are sent to different arsenals, the guerrillas win. Thus, $$E(\text{3 - 0 versus 2 - 0}) = \frac{1}{2}(0) + \frac{1}{2}(1) = \frac{1}{2}$$

and the same is true for $\textbf{2 - 1}$ versus $\textbf{2 - 0}$.

For $\textbf{2 - 1}$ versus $\textbf{1 - 1}$, the police always have at least one unit at both arsenals, so they hold both arsenals. In $\textbf{3 - 0}$ versus $\textbf{1 - 1}$, the guerrillas attack both units while the police leave one undefended. Thus, this will always be a win for the guerrillas.

Reducing by Dominance: 3 Police versus 2 Guerrillas#

The analysis is straightforward once we have constructed the matrix game. Police $\textbf{2 - 1}$ dominates $\textbf{3 - 0}$, so the Police will always play it. You should verify the guerrillas do not have a dominated strategy. Yet, once they know the police will all play $\textbf{2 - 1}$, the guerrillas will minimize by playing $\textbf{2 - 0}$.

Solution: 3 Police versus 2 Guerrillas#

Thus, the equilibrium of the game is $$\begin{align}\textbf{Police: }&\textbf{ 2 - 1}\\\textbf{Guerrillas: }&\textbf{ 2 - 0}\\v &= \frac{1}{2}\end{align}$$

Example: 5 Police versus 4 Guerrillas#

Reasoning as above, the game matrix for these forces is as follow:

\[\begin{split}\begin{array}{cc}&\textbf{Guerrillas}\\\textbf{Police}& \begin{array}{r|ccc} & \textbf{4 - 0} & \textbf{3 - 1} & \textbf{2 - 2}\\ \hline \textbf{5 - 0} & \frac{1}{2} & 0 & 0 \\ \textbf{4 - 1} & \frac{1}{2} & \frac{1}{2} & 0 \\ \textbf{3 - 2} & 0 & \frac{1}{2} & 1\end{array} \end{array}\end{split}\]

You should work through each strategy pair to ensure you know how to do the calcuations of the expected values correctly.

Reducing by Dominance: 5 Police versus 4 Guerrillas#

The $\textbf{Police : 5 - 0}$ strategy is dominated. Thus, the game reduces to the following:

\[\begin{split}\begin{array}{cc}&\textbf{Guerrillas}\\\textbf{Police}& \begin{array}{r|ccc} & \textbf{4 - 0} & \textbf{3 - 1} & \textbf{2 - 2}\\ \hline \textbf{4 - 1} & \frac{1}{2} & \frac{1}{2} & 0 \\ \textbf{3 - 2} & 0 & \frac{1}{2} & 1\end{array} \end{array}\end{split}\]

At the second, we see that the guerrillas now have a dominated strategy because $\textbf{4 - 0}$ dominates $\textbf{3 - 1}$. Hence, we can further reduce the game to the following:

\[\begin{split}\begin{array}{cc}&\textbf{Guerrillas}\\\textbf{Police}& \begin{array}{r|ccc} & \textbf{4 - 0} & \textbf{2 - 2}\\ \hline \textbf{4 - 1} & \frac{1}{2} & 0 \\ \textbf{3 - 2} & 0 & 1\end{array} \end{array}\end{split}\]

Oddments: 5 Police versus 4 Guerrillas#

The game now has oddments $\frac{1}{2}$ and $1$ for both players, and thus the optimal strategy mixture for both players is $$\vec r = \vec c = \left[\begin{array}{c} \frac{1}{\frac{3}{2}}\\ \frac{\frac{1}{2}}{\frac{3}{2}} \end{array}\right] = \left[\begin{array}{c} \frac{2}{3}\\ \frac{1}{3} \end{array}\right]$$

and you can verify the value of the game is

\[v = \frac{1}{3}\]