Competing for Allocation: The Blotto Game

The pure allocations $(2,2,2)$ and $(3,3,0)$ both guarantee only $-\frac{1}{2}$; in particular, $u((3,3,0),(2,2,2))=2$.

Let $p^{\star }=\frac{1}{7}({\delta }_{(0,2,4)}+{\delta }_{(1,3,2)}+{\delta }_{(1,4,1)}+{\delta }_{(2,1,3)}+{\delta }_{(3,0,3)}+{\delta }_{(3,3,0)}+{\delta }_{(4,1,1)})$. The pair $(p^{\star },p^{\star })$ satisfies $L=U=0$. $p^{\star }$ is a vertex of $P^{\ast }$: 41 active constraints (21 sign constraints, 19 binding columns, one normalisation equality) whose normals have exact rank 28, the dimension of the ambient space. Its marginal on every field is $\frac{1}{7}(1,2,1,2,1)$ on $\{0,\dots ,4\}$.

$P^{\ast }=\{p\ge 0:1^{\top }p=1,p^{\top }G\ge 0\}$ is not a singleton.

• Existence. The uniform mixture over the six permutations of $(0,2,4)$ is optimal. The uniform mixtures over permutations of $(0,3,3)$ and of $(1,1,4)$ guarantee $-\frac{1}{6}$ and $-\frac{1}{2}$; the uniform mixture over all 28 allocations guarantees $-\frac{9}{56}$.

• Necessity. The largest probability a single allocation can carry in an optimal strategy is: $0$ for every allocation with a component $\ge 5$; $\frac{1}{3}$ for permutations of $(0,2,4)$; $\frac{1}{5}$ for permutations of $(0,3,3)$, $(1,1,4)$, $(1,2,3)$; $\frac{1}{7}$ for $(2,2,2)$. Each bound is attained by a primal optimal strategy and matched by a dual certificate $(\lambda ,\mu )$.

In particular, no optimal strategy ever places $5$ or $6$ units on one field, and $(2,2,2)$ appears with probability at most $\frac{1}{7}$.

Against $p^{\star }$, exactly nine pure replies of $B$ lose strictly: $(6,0,0)$ and its permutations by $\frac{5}{14}$, $(5,1,0)$ and its permutations by $\frac{1}{7}$. Against the other 19 pure replies the expected payoff of $p^{\star }$ is exactly $0$. (This is a payoff against the fixed $p^{\star }$, not those replies' own guarantees: $(2,2,2)$ guarantees $-\frac{1}{2}$.)

If $B$ observes $x_1$ before choosing, the conditional values are $-\frac{1}{3},-\frac{1}{3},-\frac{1}{4},-\frac{1}{4},-\frac{1}{2},-\frac{1}{2},-\frac{1}{2}$ for $x_1=0,\dots ,6$, each certified by $L=U$. The value of the game is their maximum, $-\frac{1}{4}$, attained at $x_1=2$ (with $p=\frac{1}{2}({\delta }_{(2,1,3)}+{\delta }_{(2,3,1)})$, $q=\frac{1}{2}({\delta }_{(3,1,2)}+{\delta }_{(3,3,0)})$) and at $x_1=3$ (with $p=\frac{1}{2}({\delta }_{(3,1,2)}+{\delta }_{(3,3,0)})$, $q=\frac{1}{2}({\delta }_{(0,3,3)}+{\delta }_{(4,1,1)})$).

With $s_B(a,b)=1\{a>b\}$ and the same centring, the pair $p=q=\frac{1}{5}({\delta }_{(0,3,3)}+{\delta }_{(1,1,4)}+{\delta }_{(2,4,0)}+{\delta }_{(3,2,1)}+{\delta }_{(4,0,2)})$ satisfies $L=U=-\frac{3}{10}$. Its support is a $5\times 3$ array in which each coordinate takes each value in $\{0,\dots ,4\}$ exactly once (uniform coordinate marginals); it is not a Latin square, since rows repeat values. A direct proof without LP: for any $q$ with these marginals, $\mathbb{E}u(x,Y)={\sum }_j\min (x_j,5)/5\le 6/5$ for every $x$; for any $p$ with these marginals, $\mathbb{E}u(X,y)={\sum }_j\max (4-y_j,0)/5\ge 6/5$ for every $y$; centring at $\frac{3}{2}$ gives $-\frac{3}{10}$ on both sides.

In Model E1:

• Safe fields. Under captured weight a safe field of weight $s$ held by $B$ shifts every entry of the centred matrix by $-s/2$; the optimal strategies of both players are the same with or without it. Under the majority objective a safe field changes the quota $q$, and the payoff depends on the weights only through the family of winning sets.

• Dummy fields. Under the majority objective, moving $A$'s units from a dummy field to any other field never lowers $A$'s payoff against any allocation of $B$. Hence, for any budgets, some optimal strategy of $A$ leaves every dummy field empty.

• Budgets $4:4$. Under captured weight the value is $0$ without a safe field ($\pm s/2$ with one, by (a)); in every optimal strategy of $A$ field 4 is left empty, field 3 receives exactly one unit in expectation, and fields 1 and 2 receive between $\frac{5}{4}$ and $\frac{7}{4}$. Under the majority objective without a safe field ($q=5$; minimal winning sets: any two of fields 1–3) the value is $0$, fields 1, 2 and 3 have the same range of expected units, from $1$ to $\frac{3}{2}$, and field 4, a dummy, is left empty by every optimal strategy. If $B$ holds a safe field of weight $2$ ($q=6$; minimal winning sets $\{1,2\}$, $\{1,3,4\}$, $\{2,3,4\}$) the value is $-\frac{37}{200}$ and every optimal strategy of $A$ places, in expectation, $\frac{7}{5}$ units on each of fields 1 and 2 and $\frac{3}{5}$ on each of fields 3 and 4. The values with a safe field of weight $s$ held by $A$ and by $B$ are opposite: $\pm \frac{37}{200}$ for $s=2$, $\pm \frac{49}{104}$ for $s=4$.

• Budget asymmetry, no safe field. At $5:4$ the values are $\frac{39}{56}$ (captured weight) and $\frac{67}{336}$ (majority); at $6:4$, $\frac{5}{4}$ and $\frac{17}{46}$. The richer side's win probability under the majority objective, $\frac{235}{336}$ and $\frac{20}{23}$, exceeds its expected share of the weight under captured weight, $\frac{97}{168}$ and $\frac{23}{36}$. Under the majority objective every optimal strategy leaves field 4 empty at all three budget pairs; under captured weight field 4 is empty in every optimal strategy at $4:4$ and $5:4$, and receives between $\frac{1}{2}$ and $\frac{11}{14}$ units at $6:4$.

The problems $\max \{t:p^{\top }G\ge t{1}^{\top },1^{\top }p=1,p\ge 0\}$ and $\min \{z:Gq\le z1,1^{\top }q=1,q\ge 0\}$, with free scalars $t$ and $z$, are dual to each other; both optimal values equal $v$.