N-dimensional Blotto game with heterogeneous battlefield values

Abstract

This paper introduces the irregular N-gon solution, a new geometric method for constructing equilibrium distributions in the Colonel Blotto game with heterogeneous battlefield values, generalising known construction methods. Using results on the existence of tangential polygons, it derives necessary and sufficient conditions for the irregular N-gon method to be applied, given the parameters of a Blotto game. The method does particularly well when the battlefield values satisfy some clearly defined regularity conditions. The paper establishes the parallel between these conditions and the constrained integer partitioning problem in combinatorial optimisation. The properties of equilibrium distributions numerically generated using the irregular N-gon method are illustrated. They indicate that the realised allocations, weighted by battlefield value, are less egalitarian and depend more strongly on battlefield values than previously thought. In the context of the US presidential elections, the explicit construction of equilibria provides new insights into the relation between the size of a state and the campaign resources spent there by presidential candidates.

Appendix

1.1 Bounds on $t_n$ when N is even.

For N even, it follows from (2) that

$$\begin{aligned} 0<t_n<v_n, \quad n=1,\dots ,N. \end{aligned}$$

(9)

Using (2) to express each $t_n$ in terms of $t_1$:

$$\begin{aligned} t_n = \left\{ \begin{array}{ll} -t_1+b_{n-1} &{} n=2,4,\dots ,N, \\ t_1-b_{n-1} &{} n=1,3,\dots ,N-1, \end{array} \right. \end{aligned}$$

(10)

where $b_n=\sum _{j=1}^{n}(-1)^{j+1}v_j$ for $n=1,\dots ,N$ is defined in Corollary 2 and we use the convention $b_0 \equiv 0$. Using (10) in (9), we obtain

$$\begin{aligned} t_n = \left\{ \begin{array}{ll} b_{n-1}>t_1> b_{n-1}-v_n, &{} n=2,4,\dots ,N, \\ b_{n-1}<t_1< b_{n-1}+v_n, &{} n=1,3,\dots ,N-1. \end{array} \right. \end{aligned}$$

Since $b_{n}= b_{n-1}-v_n$ when n is even, and $b_{n}= b_{n-1}+v_n$ when n is odd, the above becomes

$$\begin{aligned} t_n = \left\{ \begin{array}{ll} b_{n-1}>t_1> b_{n}, &{} n=2,4,\dots ,N, \\ b_{n-1}<t_1< b_{n}, &{} n=1,3,\dots ,N-1. \end{array} \right. \end{aligned}$$

The above system of inequalities imposes N / 2 upper bounds and N / 2 lower bounds on $t_1$.

Condition (6) is necessary and sufficient for all N bounds to hold, and the interval in (6) defines the set of admissible values for $t_1$. For a given $t_1$, equation (10) uniquely defines $t_n$ for all remaining $n=2,\dots ,N$.

1.2 Algorithm

The following algorithm is used to build the set $\mathcal {G}^*(\mathcal {V})$ of all permutations of the set $\mathcal {V}$ of battlefield values satisfying Theorem 1, treating a permutation, its cyclic shifts and the order-reversing permutations of all of them as identical.³² Fix $\mathbf {v}:=(v_1,\dots ,v_N)$ and for each permutation $\pi$ of $1,\dots ,N$ let $\mathbf {w}^\pi :=(w^\pi _1,\dots ,w^\pi _N) =(v_{\pi (1)},\dots ,v_{\pi (N)})$ denote the corresponding permutation of $\mathbf {v}$. The existence of a tangential polygon with sides given by $\mathbf {w}^\pi$ requires condition (2) to hold. This implies that for each $n=1,\dots ,N$, we have $0\le t_n\le w^\pi _{n-1}$ and $0\le t_{n+1}\le w^\pi _{n+1}$ and therefore

$$\begin{aligned} w^\pi _n\le w^\pi _{n+1}+w^\pi _{n-1} \quad \forall n=1,\dots ,N. \end{aligned}$$

Observing that this condition is harder to satisfy the larger $w^\pi _n$, we use the following algorithm to construct $\mathcal {G}^*(\mathcal {V})$.

• 1. Let $\mathcal {G}_0( \mathcal {V})$ denote the set of all possible permutations $w^\pi$ of $\mathbf {v}$, treating a permutation, its cyclic shifts and the order-reversing permutations of all of them as identical³³. For each corresponding $\pi$, let $\tilde{n}^\pi :=\arg \max _{n\in \{1,\dots ,N\}} w^\pi _n$ denote the index of the highest valued coordinate of $\mathbf {w}^\pi$.

• 2. Construct the set $\mathcal {G}_1( \mathcal {V}) \subseteq \mathcal {G}_0( \mathcal {V})$ of cyclical permutations satisfying

  $$\begin{aligned} w^\pi _{\tilde{n}^\pi } \le w^\pi _{\tilde{n}^\pi -1}+w^\pi _{\tilde{n}^\pi +1}. \end{aligned}$$

• 3. For $k=2,\dots ,(N-1)/2$, construct the set $\mathcal {G}_k( \mathcal {V}) \subseteq \mathcal {G}_{k-1}( \mathcal {V})$ of cyclical permutations satisfying

  $$\begin{aligned} \left\{ \begin{array}{l} w^\pi _{\tilde{n}^\pi -k+1} \le w^\pi _{\tilde{n}^\pi -k}+w^\pi _{\tilde{n}^\pi -k+2},\\ w^\pi _{\tilde{n}^\pi +k-1} \le w^\pi _{ \tilde{n}^\pi +k}+w^\pi _{\tilde{n}^\pi +k-2}. \end{array} \right. \end{aligned}$$

• 4. Eliminate from $\mathcal {G}_ {\frac{N-1}{2}}( \mathcal {V})$ all permutations that do not satisfy (3).

The surviving permutations constitute the set $\mathcal {G}^*( \mathcal {V})$.

Because the algorithm above exploits the conditions of Theorem 1, it does better at deriving the set $\mathcal {G}^*( \mathcal {V})$ than the brute force method of testing all possible permutations of the elements of $\mathcal {V}$.

1.3 Counter-example

Consider the set $\mathcal {V}=\{1,2,3,109,110,111,325 \}$ of battlefield valuations. The set $\mathcal {G}_1$, defined in Appendix 1, is empty, since $325>110+111$ . Therefore, there exists no permutation of the elements of $\mathcal {V}$ satisfying condition (2).

However, $\mathcal {V}$ satisfies the N integer partitioning problems in Proposition 2 (ii):

$v_n$	partition of $\mathcal {V}\smallsetminus \{v_n\}$ into two subsets of equal cardinality	discrepancy
1	$\big \{\{109,110,111\},\{2,3,325\}\big \}$	0
2	$\big \{\{109,110,111\},\{1,3,325\}\big \}$	1
3	$\big \{\{109,110,111\},\{1,2,325\}\big \}$	2
109	$\big \{\{3,110,111\},\{1,2,325\}\big \}$	104
110	$\big \{\{3,109,111\},\{1,2,325\}\big \}$	105
111	$\big \{\{3,109,110\},\{1,2,325\}\big \}$	106
325	$\big \{\{3,109,111\},\{1,2,110\}\big \}$	110

1.4 Numerically constructing the equilibrium distribution

This section describes the method used for numerically computing the allocation of resources under $F^*_\kappa$. Fix a given permutation $\varvec{w}$ of the vector of battlefield values $\varvec{v}$ such that $\varvec{w} \in \mathcal {G}^*(\mathcal {V})$ and fix a $\kappa \le \left\lfloor \frac{N-1}{2}\right\rfloor$. Using Mathematica, we generate 10, 000 points randomly distributed on the surface of a sphere. Each data point is then used to compute one realisation ${\varvec{x}}$ of the N-dimensional allocation vector. Recall that indices are defined modulo N. We use the notation of Sect. 3.1.

Let $\rho _n$ denote the distance $|O P_{n}|$ and let $\alpha _{n}$ denote the angle $\widehat{T_{n-1} O P_{n}}$ which by construction equals the angle $\widehat{P_{n} O T_{n}}$ (See Fig. 9). The distance $|O T_{n}|$ is given by the radius $r_\kappa$ of the incircle of the tangential N-gon ${\varvec{P}}$. (In this section this radius is indexed by $\kappa$ to emphasise the dependence.)

Consider the right triangle $O T_{n-1} P_{n}$, where $\widehat{T_{n-1} O P_{n}}=\alpha _n$ and where $|O T_{n-1}|=r_\kappa$, $|P_{n} T_{n-1}|=t_n$ and the hypotenuse is $|O P_{n}|=\rho _n$. We have that

$$\begin{aligned} \sin \alpha _n = \frac{t_n}{\sqrt{r_\kappa ^2 + t_n^{\ 2}}}. \end{aligned}$$

Since $\alpha _{n}$ is one of the non-right apices of $O T_{n-1} P_{n-1}$, we have that $- \pi /2<\alpha _{n}< \pi /2$ so that $\arcsin \left( \sin \alpha _n\right)$ is defined³⁴ and

$$\begin{aligned} \alpha _n (r_\kappa )= \arcsin \left( \frac{t_n}{\sqrt{r_\kappa ^2 + t_n^{\ 2}}}\right) . \end{aligned}$$

Since $\arcsin$ is strictly increasing over its domain, $\alpha _n(r)$ is strictly decreasing in $r_\kappa$.

Theorem 2 and Corollary 3 in Radić (2002) give the radius $r_\kappa$ of the incirle of a $\kappa$-tangential polygon as an implicit function of the lengths $t_1,\dots ,t_N$. Based on that, we obtain expressions for $\alpha _n$ and $\rho _n$, $n=1,\dots ,N$.

Fig. 9

Projecting Q onto $(P_n,P_{n+1})$

Let $\theta \in [0,2\pi ]$ and $\phi \in [-\pi /2,\pi /2]$ denote the polar coordinates of R, the point uniformly distributed over the surface of the sphere $\mathscr {S}=(O,r_\kappa )$. Let Q denote the projection of R onto the disc $(O,r_\kappa )$ inscribed in the N-gon ${\varvec{P}}$. Let $h_n$ denote the orthogonal distance of Q from the line $(P_n,P_{n+1})$.

We orient the two-dimensional plane around the origin O by convening that $T_1=r_\kappa e^{i0}$. We then have that

$$\begin{aligned} P_{n }= \rho _n \ e^{i \left( 2 \sum _{j=2}^{n}\alpha _j - \alpha _n \right) }, \end{aligned}$$

and

$$\begin{aligned} T_{n }= r_\kappa \ e^{i 2 \sum _{j=2}^{n}\alpha _j }. \end{aligned}$$

Moreover, since

$$\begin{aligned} Q = r_\kappa \ \sin \phi \ e^{i \theta } , \end{aligned}$$

we obtain that

$$\begin{aligned} h_n = r_\kappa - r_\kappa \sin \phi \ \cos \left( \theta - 2 \sum _{j=2}^{n}\alpha _j\right) , \end{aligned}$$

and have shown in Sect. 3.1 that $X_n=(h_n w_n)/(r_\kappa B) \sim U[0,2w_n/B]$.

1.5 Distribution of electoral votes (Source: www.fec.gov)

State	1981–1990	1991–2000	2001–2010	2011–2020
Alabama	9	9	9	9
Alaska	3	3	3	3
Arizona	7	8	10	11
Arkansas	6	6	6	6
California	47	54	55	55
Colorado	8	8	9	9
Connecticut	8	8	7	7
Delaware	3	3	3	3
D.C	3	3	3	3
Florida	21	25	27	29
Georgia	12	13	15	16
Hawaii	4	4	4	4
Idaho	4	4	4	4
Illinois	24	22	21	20
Indiana	12	12	11	11
Iowa	8	7	7	6
Kansas	7	6	6	6
Kentucky	9	8	8	8
Louisiana	10	9	9	8
Maine	4	4	4	4
Maryland	10	10	10	10
Massachusetts	13	12	12	11
Michigan	20	18	17	16
Minnesota	10	10	10	10
Mississippi	7	7	6	6
Missouri	11	11	11	10
Montana	4	3	3	3
Nebraska	5	5	5	5
Nevada	4	4	5	6
New Hampshire	4	4	4	4
New Jersey	16	15	15	14
New Mexico	5	5	5	5
New York	36	33	31	29
North Carolina	13	14	15	15
North Dakota	3	3	3	3
Ohio	23	21	20	18
Oklahoma	8	8	7	7
Oregon	7	7	7	7
Pennsylvania	25	23	21	20
Rhode Island	4	4	4	4
South Carolina	8	8	8	9
South Dakota	3	3	3	3
Tennessee	11	11	11	11
Texas	29	32	34	38
Utah	5	5	5	6
Vermont	3	3	3	3
Virginia	12	13	13	13
Washington	10	11	11	12
West Virginia	6	5	5	5
Wisconsin	11	11	10	10
Wyoming	3	3	3	3

1.6 Presidential campaign finance summaries

(Data: Federal Election Commission, Presidential Campaign Finance Summaries, http://www.fec.gov/press/bkgnd/pres_cf/pres_cf_Even.shtml)

	Disbursements prior to Super Tuesday$^\text {(i)}$	Total disbursements
2012
Obama$^*$ (D)	${\$} 66,121,822^\dagger$	${\$} 469,930,646$
	${\$} 78,712,495^\ddagger$
Romney (R)	${\$} 55,745,321^\dagger$	${\$} 298,158,415$
	${\$} 68,107,847^\ddagger$
2008
Obama (D)	${\$} 115,689,084^\dagger$	${\$} 488,331,269$
	${\$} 158,579,005^\ddagger$
Mc Cain (R) (II)	${\$} 49,650,185^\dagger$	${\$} 207,523,221$
	${\$} 58,432,608^\ddagger$
2004
Kerry (D) (II)	${\$} 30,119,415^\dagger$	${\$}243,294,897$
	${\$} 37,867,817^\ddagger$
Bush$^*$ (R) (II)	${\$} 38,901,223^\dagger$	${\$}286,628,893$
	${\$} 46,724,159^\ddagger$
2000
Gore (D) (I) (II)	${\$} 25,703,131^\dagger$	${\$} 77,863,579$
	${\$} 34,047,289^\ddagger$
Bush (R) (II)	${\$} 47,964,764^\dagger$	${\$} 136,651,579$
	${\$} 60,724,475^\ddagger$

1. Notation: (D) Democrat, (R) Republican. (I) indicates that the candidate accepted primary matching funds and (II) that he accepted government funds in the general election. $*$ indicates an incumbent, $\dagger$ indicates disbursements up to and including the month of January, $\ddagger$ indicates disbursements up to and including the month of February.
2. (i) “Super Tuesday” took place on the following dates: 6 March 2012, 5 February 2008, 3 February 2004, 7 March 2000. In 2004, many sates held their primaries on 2 March, dubbed “Mini Tuesday”

1.7 One permutation of US states satisfying Theorem 1 (2008 Electoral College)

For clarity, $w_n$, $t_n$ and $t_{n+1}$ are multiplied by 538. (There are 538 electoral votes in total.)

n	$w_n$	$t_n$	$t_{n+1}$	n	$w_n$	$t_n$	$t_{n+1}$
1	31	2	29	26	3	1	2
2	8	6	2	27	3	2	1
3	9	3	6	28	3	1	2
4	10	7	3	29	4	3	1
5	11	4	7	30	4	1	3
6	17	13	4	31	4	3	1
7	20	7	13	32	4	1	3
8	21	14	7	33	5	4	1
9	27	13	14	34	5	1	4
10	21	8	13	35	5	4	1
11	15	7	8	36	6	2	4
12	15	8	7	37	6	4	2
13	15	7	8	38	7	3	4
14	10	3	7	39	7	4	3
15	7	4	3	40	8	4	4
16	7	3	4	41	9	5	4
17	6	3	3	42	9	4	5
18	5	2	3	43	10	6	4
19	5	3	2	44	10	4	6
20	4	1	3	45	11	7	4
21	3	2	1	46	11	4	7
22	3	1	2	47	11	7	4
23	3	2	1	48	12	5	7
24	3	1	2	49	13	8	5
25	3	2	1	50	34	26	8
–	–	–	–	51	55	29	26

1.8 Lorenz curves and Gini coefficients

See Tables 7 and 8 and Fig. 10.

Table 7 Gini Coefficients for $\kappa =1,\dots ,5$

Table 8 First entry in each cell specifies whether the Lorenz curve $L_\kappa$ (row) first order stochastically dominates the Lorenz curve $L_{\kappa '}$ (column) given our sample data, for $\kappa ,\kappa ' \in \{1,\dots ,5\}$

Fig. 10

Lorenz curves for $\kappa =1$ in blue, $\kappa =2$ in red, $\kappa =3$ in green, $\kappa =4$ in black, $\kappa =5$ in orange

1.9 Rank and correlation properties of $F^*_\kappa$

See Figs. 11 and 12.

Fig. 11

Plots of the correlation matrices of $F^*_\kappa$, for $\kappa =1,\dots ,5$

Fig. 12

Plots of rank distributions under $F^*_\kappa$ for $\kappa =1,\dots ,5$