Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

In the simplest asymmetric Colonel Blotto game with 2 players, dividing their given Ni soldiers (i=1,2) over 2 battlefields, what are their expected utilities, Ui (i.e., expected number of battlefield victories), in a Nash Equilibrium?

If the continuum Ni case is significantly easier to solve, you can consider the individual soldiers to be divisible. I’d also like to see an explicit Nash Equilibrium strategy for the two players, but it seems that there might be many cases, so it can’t be written down simply.

share|improve this question
    
I've seen (and considered on my own) asymmetric Blotto games, but never non-constant-sum Blotto games. How do you define the utilities for the possible outcomes? $\:$ –  Ricky Demer May 12 '13 at 20:27
    
Maybe I shouldn't have used the words "non-constant-sum". All I mean is that the two players start with a non-equal number of total soldiers and use them all ("use it or lose it") on the two battlefields. So, utility is the number of battlefields won (you can say ties are split half-half, so technically the possible utility outcomes are 0, 0.5, 1.0, 1.5, or 2.0, but tie treatment is not statistically important if there are many soldiers). –  bobuhito May 12 '13 at 23:51

1 Answer 1

up vote 1 down vote accepted

O. Gross and R. Wagner, 1950. "A Continuous Colonel Blotto Game," Rand Research Memorandum RM-408 covers this case (pages 2-4) and much more.

If the players have equal resources, then it's always a tie regardless of strategy (since you didn't assign different values to the different battlefields).

If one player has more than twice the resources of the other, splitting them evenly guarantees a complete victory.

Suppose the players have $B$ and $E$ resources, and without loss of generality assume $2E \gt B \gt E$.

Let $m = \lfloor B/(B-E)\rfloor \ge 2$.

The value of the game with optimal play is $2/m$. This is the difference between wins and losses, and twice the probability of a win in both battlefields, $1/m$.

Let $d= B-E, B = md + r$. Let $p$ be any number in $(r, d)$. Let $q = E/(m-1)$.

An optimal strategy for Blotto, the player with $B$, is to have a $1/m$ chance to allocate each of $p, p + d, p + 2d, ... p+(m-1)d$ in the first battlefield.

An optimal strategy for the enemy with $E$ is to have a $1/m$ chance to allocate each of $0, q, 2q, ... (m-1)q$ in the first battlefield.

For example, if $E=1$ and $B=1.6$, then $m=2$ and the enemy can do no better than to commit everything to a random battlefield. Colonel Blotto tries to guess which one, and succeeds with probability $1/2$ (or else they split the battlefields). If $E=1$ and $B=1.4$, then $m=3$ and the enemy should allocate its forces as $(0,1)$, $(1/2,1/2)$, or $(1,0)$ with equal probabilities. Colonel Blotto can only win both battlefields in one of these situations, picks one, and guesses correctly with probability $1/3$.

share|improve this answer
    
Thanks. I'm trying to follow this, but you have some mistakes throwing me off. Please take a look at your definition of r and your example's calculation of m (I get m=8/3). –  bobuhito May 13 '13 at 16:05
    
Perhaps you overlooked the floor function. $m$ is always an integer. It is the floor of $B/d$. If $B=1.6, E=1$ then $m=\lfloor 1.6/0.6 \rfloor = \lfloor 8/3 \rfloor = 2$. Please let me know if you find errors in what I wrote. –  Douglas Zare May 13 '13 at 17:55
    
Yep, sorry, first time I've seen that notation. I'll mark your $m/\lfloor B/(B-E)\rfloor $ as the answer in a moment. By the way, is there a generalization of this formula to more than 2 players and/or more than 2 battlefields? I’m just looking for the value/utility formula, not a full strategy like you graciously gave here. –  bobuhito May 13 '13 at 20:01
    
I'm not sure what is known about the asymmetric case with more than $2$ battlefields. –  Douglas Zare May 13 '13 at 20:31

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.