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$.


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

