Who has the upper hand in a generalized game of Risk?

So, I played a game of Risk the other day for the first time since I was very little. I was frustrated to discover that I couldn’t compute (at least not in my head) whether the attacker or the defender has the upper-hand in large battles. Based on how the game unfolded, I guessed that the attacker has the advantage, and later I verified this by calculating the expected number of casualties in a round of “combat”. But, my approach was just to brute-force the computation in a spreadsheet. I’m curious whether there is a more elegant approach and also I thought it might be nice to ask a more general question.

Let $A$ and $B$ be two players. Let $a,b,n,k$ be positive integers with $k \leq a,b$. The game is as follows. Person $A$ has $a$ dice. Person $B$ has $b$ dice. All dice have $n$ sides labelled $1,2,\ldots,n$. Both players roll all of their dice, extract their $k$ highest rolls (with repetition) and sort them in (weakly) decreasing order. Say $a_1,\ldots,a_k$ are $A$’s $k$ best rolls and $b_1,\ldots,b_k$ are $B$’s $k$ best rolls. $A$ suffers one “casualty” for each index $i \in \{1,2,\ldots,k\}$ with $a_i \leq b_i$. $B$ suffers one “casualty” for each index $i \in \{1,2,\ldots,k\}$ with $a_i > b_i$. Note that player $B$ wins when the rolls are tied.

What are the expected number casulties that $A$ suffers in terms of $a,b,n,k$? Note by linearity of expectation, the expected number of casualties that $A$ suffers plus the expected number of casualties that $B$ suffers sum to $k$.

Solutions Collecting From Web of "Who has the upper hand in a generalized game of Risk?"

For an actual game of Risk, where the attacker has 3 armies and the defender has 2, I worked it out this way. I think you can generalize easily for other values of $a$ and $n$. Other values of $b$ will make the counting slightly more difficult, but still within reach (I think). Other values of $k$ however will make my counting method a lot more difficult (I think).

If we view the three attacker’s dice as distinguished, then the space of possible rolls for the attacker has size $6^3$. It’s like a giant $6\times6\times6$ cube itself – one dimension for each die. For example, the attacker’s roll might be a $(2,5,4)$ or a $(4,6,6)$. Each such roll has the same probability: $\frac{1}{6^3}$.

We can break this cube into shells that I will try to define. The smallest shell contains the singleton $(1,1,1)$. The next shell contains all possible rolls where the high die is a 2. (This shell therefore has $7$ elements – surrounding $(1,1,1)$.) Continue in this way up to the outermost shell, which will contain all possible rolls where the highest die is a 6. Geometrically, this last shell is three faces of the cube. Each previous shell can also be viewed as having three faces (with the possible exception of $S_1$.) To be more precise,
$$S_i = \{(a,b,c)|\max\{a,b,c\}=i\}$$
for $i =1\ldots6$.
The probability of tossing into shell $i$ is $$P(S_i)=\frac{i^3-(i-1)^3}{6^3}$$
Each shell $S_i$ has subsets $S_{i,j}$ where $j$ is the second highest roll (possibly equal to $i$). Geometrically, $S_{i,j}$ is composed of line segments running along the three faces of $S_i$. $S_{i,i}$ is composed of the three edges converging to the main corner in $S_i$. For $j$ less than $i$, $S_{i,j}$ is composed of three “arrows”, one along each face of $S_i$, each pointing to the main corner of $S_i$. The image below illustrates the cube of possilbe attacker rolls, $S_6$, $S_{6,6}$, and $S_{6,3}$.

Cube representing possible attacker rolls

We find that for the attacker’s roll, with $j$ less than $i$,
\begin{align*}
P(S_{i,i}) & = \frac{3i-2}{i^3-(i-1)^3}\frac{i^3-(i-1)^3}{6^3}=\frac{3i-2}{6^3}\\\\
P(S_{i,j}) & = \frac{6j-3}{i^3-(i-1)^3}\frac{i^3-(i-1)^3}{6^3}=\frac{6j-3}{6^3}\\
\end{align*}

Now we begin to consider the defender’s tosses, conditional upon what $S_{i,j}$ the attacker has rolled into. Similar to the cube that we envisioned for the attacker, the defender has a $6\times 6$ square of possible rolls.

Let’s start counting the number of armies that the attacker loses. Let $X$ be this random variable, which can take values $0$, $1$, or $2$.

Suppose the attacker has rolled into $S_{i,i}$. If both the defender’s dice are less than $i$ (which will happen with $P=\frac{(i-1)^2}{6^2}$), the attacker will lose zero armies. If both of the defender’s dice are $\geq i$ (which will happen with $P=\frac{(7-i)^2}{6^2}$) the attacker will lose two armies. In all other situations ($P=\frac{2(i-1)(7-i)}{6^2}$), each player loses one army.

Now suppose that the attacker has rolled into $S_{i,j}$ with $j<i$. The attacker loses no armies if the defender’s highest die is less than $i$ and the other die is less than $j$. This defines an “L” shaped region of the defender’s square of possibilities. This region has $P=\frac{(i-1)^2-(i-j)^2}{6^2}$. Similarly, the attacker will lose two armies exactly when the defender has his high die at least $i$ and other die at least $j$. This defines an “L” shaped region on the other side of the square. ($P=\frac{(7-j)^2-(i-j)^2}{6^2}$). This leaves three rectangular regions on the square where each player loses one army ($P=\frac{2(j-1)(7-i)+(i-j)^2}{6^2}$).

Altogether now, the probabilities for each value of $X$ can be compute via summation:
\begin{align*}
P(X=0)&=\sum_{i=1}^6\left(P(S_{i,i})\frac{(i-1)^2}{6^2}+\sum_{j=1}^{i-1}P(S_{i,j})\frac{(i-1)^2-(i-j)^2}{6^2}\right)\\\\
&=\sum_{i=1}^6\left(\frac{3i-2}{6^3}\frac{(i-1)^2}{6^2}+\sum_{j=1}^{i-1}\frac{6j-3}{6^3}\frac{(i-1)^2-(i-j)^2}{6^2}\right)\\\\
P(X=1)&=\sum_{i=1}^6\left(P(S_{i,i})\frac{2(i-1)(7-i)}{6^2}+\sum_{j=1}^{i-1}P(S_{i,j})\frac{2(j-1)(7-i)+(i-j)^2}{6^2}\right)\\\\
&=\sum_{i=1}^6\left(\frac{3i-2}{6^3}\frac{2(i-1)(7-i)}{6^2}+\sum_{j=1}^{i-1}\frac{6j-3}{6^3}\frac{2(j-1)(7-i)+(i-j)^2}{6^2}\right)\\\\
P(X=2)&=\sum_{i=1}^6\left(P(S_{i,i})\frac{(7-i)^2}{6^2}+\sum_{j=1}^{i-1}P(S_{i,j})\frac{(7-j)^2-(i-j)^2}{6^2}\right)\\\\
&=\sum_{i=1}^6\left(\frac{3i-2}{6^3}\frac{(7-i)^2}{6^2}+\sum_{j=1}^{i-1}\frac{6j-3}{6^3}\frac{(7-j)^2-(i-j)^2}{6^2}\right)\\\\
\end{align*}

Each of these can be reduced using the sum formulas
\begin{align*}
\sum_{n=1}^m\ 1& =m\\\\
\sum_{n=1}^m\ n&=\frac{1}{2}m(m+1)\\\\
\sum_{n=1}^m\ n^2&=\frac{1}{6}m(m+1)(2m+1)\\\\
\sum_{n=1}^m\ n^3&=\frac{1}{4}m^2(m+1)^2\\\\
\sum_{n=1}^m\ n^4&=\frac{1}{30}m(m+1)(2m+1)(3m^2+3m-1)
\end{align*}

After applying these, we find:
\begin{align*}
P(X=0)&=\frac{2890}{6^5}\\\\
P(X=1)&=\frac{2611}{6^5}\\\\
P(X=2)&=\frac{2275}{6^5}
\end{align*}

These agree with the decimal probabilities reported here. Thus the expected number of casualties is $$0\frac{2890}{6^5}+1\frac{2611}{6^5}+2\frac{2275}{6^5}=\frac{7161}{6^5}$$

Here’s an answer. It’s not very pretty, but it is exact. Let the random variable $C_A$ denote the number of Player $A$ (the attacker)’s casualties. Then

$\begin{align}
E[C_A] = &\sum_{j=0}^{k-1} \sum_{i=1}^n \sum_{l=0}^j \sum_{m=0}^j \binom{b}{l} \binom{a}{m} \left( \left(1 – \frac{i}{n}\right)^l \left( \frac{i}{n}\right)^{b-l} – \left(1- \frac{i-1}{n}\right)^l \left(\frac{i-1}{n}\right)^{b-l} \right) \\
& \times \left(1 – \frac{i}{n}\right)^m \left(\frac{i}{n}\right)^{a-m}.
\end{align}
$

Derivation:

In a particular random roll of the dice, we order $A$’s dice from largest to smallest and $B$’s dice from largest to smallest. This is equivalent to taking two random samples – of size $a$ in $A$’s case and size $b$ in $B$’s case – from the discrete uniform distribution on $\{1, 2, \ldots, n\}$ and computing their order statistics.

If $X_{(j)}$ and $Y_{(j)}$ denote the order statistics from $A$’s dice rolls and from $B$’s dice rolls, respectively, then $A$ suffers a casualty each time $X_{(a-j)} \leq Y_{(b-j)}$, for $0 \leq j \leq k-1$. Let $I_j$ be $1$ if $X_{(a-j)} \leq Y_{(b-j)}$, and $0$ otherwise. Then $C_A = \sum_{j=0}^{k-1} I_j$, and so $$E[C_A] = \sum_{j=0}^{k-1} E[I_j] = \sum_{j=0}^{k-1} P(X_{(a-j)} \leq Y_{(b-j)}).$$

Since $A$’s rolls and $B$’s rolls are independent, so are their order statistics. Conditioning on the value of $Y_{(b-j)}$, then, we have $P(X_{(a-j)} \leq Y_{(b-j)}) = \sum_{i=1}^n P(Y_{(b-j)} = i) P(X_{(a-j)} \leq i).$ There are known formulas for $P(Y_{(b-j)} = i)$ and $P(X_{(a-j)} \leq i)$:
$$P(Y_{(b-j)} = i) = \sum_{l=0}^j \binom{b}{l} \left( \left(1 – \frac{i}{n}\right)^l \left( \frac{i}{n}\right)^{b-l} – \left(1- \frac{i-1}{n}\right)^l \left(\frac{i-1}{n}\right)^{b-l} \right),$$
$$P(X_{(a-j)} \leq i) = \sum_{m=0}^j \binom{a}{m} \left(1 – \frac{i}{n}\right)^m \left(\frac{i}{n}\right)^{a-m}.$$

Putting this all together, we obtain

$\begin{align}
E[C_A] = &\sum_{j=0}^{k-1} \sum_{i=1}^n \sum_{l=0}^j \sum_{m=0}^j \binom{b}{l} \binom{a}{m} \left( \left(1 – \frac{i}{n}\right)^l \left( \frac{i}{n}\right)^{b-l} – \left(1- \frac{i-1}{n}\right)^l \left(\frac{i-1}{n}\right)^{b-l} \right) \\
& \times \left(1 – \frac{i}{n}\right)^m \left(\frac{i}{n}\right)^{a-m}.
\end{align}
$

A comment on implementation:

For simplicity, the formula uses the convention that $0^0 = 1$, which occurs when $i = n$. If you try to use the formula in some computer algebra system that doesn’t have that convention, like Mathematica, you will need to consider the case $i = n$ separately from the rest of the sum on $i$. This would be

$\begin{align}
E[C_A] = &\sum_{j=0}^{k-1} \Bigg(\sum_{i=1}^{n-1} \sum_{l=0}^j \sum_{m=0}^j \binom{b}{l} \binom{a}{m} \left( \left(1 – \frac{i}{n}\right)^l \left( \frac{i}{n}\right)^{b-l} – \left(1- \frac{i-1}{n}\right)^l \left(\frac{i-1}{n}\right)^{b-l} \right) \\
& \times \left(1 – \frac{i}{n}\right)^m \left(\frac{i}{n}\right)^{a-m} + \left(1-\sum_{l=0}^j \binom{b}{l}\left(1-\frac{n-1}{n}\right)^l \left(\frac{n-1}{n}\right)^{b-l}\right) \Bigg).
\end{align}
$

Example:

In the case of standard Risk, with $n = 6, a = 3, b = 2, k = 2$ case, the formula yields $\frac{2387}{2592} = \frac{7161}{6^5}$, in agreement with alex.jordan’s answer.

In[1]:= f[n_, a_, b_, k_] := 
  Sum[Sum[Binomial[b, l]*((1 - i/n)^l*(i/n)^(b - l) - (1 - (i - 1)/n)^l*
        ((i - 1)/n)^(b - l))*Binomial[a, m]*(1 - i/n)^m*(i/n)^(a - m), 
     {i, 1, n - 1}, {l, 0, j}, {m, 0, j}] + 
    (1 - Sum[Binomial[b, l]*(1 - (n - 1)/n)^l*((n - 1)/n)^(b - l), {l, 0, j}]), 
   {j, 0, k - 1}]

In[2]:= f[6, 3, 2, 2]
Out[2]= 2387/2592

In[3]:= N[%]
Out[3]= 0.9209104938271605

In[4]:= N[7161/6^5]
Out[4]= 0.9209104938271605