Efficient Computation of Approximate Equilibria in Discrete Colonel Blotto Games

1 Introduction

The past decade has seen a rising interest in using gametheoretic models for security problems, see e.g., [Tambe, 2011]. As the modern world is facing increasingly important security threats, such models are interesting because they allow deriving defenses that are optimized against adaptive adversaries for different specific applications such as patrolling or screening problems, see e.g., [Conitzer and Sandholm, 2006; Boˇsansk´y et al., 2011; Yang et al., 2013; Letchford and Conitzer, 2013; Fang et al., 2015; Gan et al., 2015; Brown et al., 2016] amongst others. Several solutions of game-theoretic models have been implemented in real-world defense applications with positive results, validating the importance and relevance of game theory for security problems [Pita et al., 2011; Yin et al., 2012].

Recently, the community started to gain interest in the celebrated Colonel Blotto game. In the Colonel Blotto game, two players (often referred to as colonels) choose how to distribute a fixed budget of resources (often called troops or soldiers) on a number of battlefields. Each battlefield has a given value and is won by the player who allocates more resources to it; each player maximizes the sum of values of battlefields he wins. As a simple and elegant model for strategic resource allocation problems, the Colonel Blotto game (and in particular the characterization of its equilibrium) has important applications in many domains including security (allocation of defense/attacks resources), but also politics (allocation of campaign resources or lobbying resources), industrial operations (allocation of R&D resources) or advertisement (allocation of ad budgets). Its continuous version, where players can choose any fractional allocation, has received high attention from the economics community since its first introduction in 1921. However, only partial results are known to date; in particular, the equilibrium characterization in the general case of parameters configuration still remains as a challenging open question (see related works below).

The discrete version of the Colonel Blotto game (where allocations can only be integers), which is meaningful in applications where individual troops cannot be divided, started to gain traction much more recently in the algorithmic game theory community. Since it is a finite constant-sum game, it can in principle be solved numerically in general cases through linear programming. However, standard solutions to compute the Nash equilibria face the issue that the strategy space of the players grows exponentially with the number of battlefields and the number of troops. To tackle this problem, two algorithms were proposed in the last two years in [Ahmadinejad et al., 2016] and [Behnezhad et al., 2017]. Both algorithms rely on transforming the linear program formulation which significantly improves the complexity. Yet, these algorithms still become computationally impractical when the number of battlefields and/or the number of troops is large (e.g., it takes over 1 day to solve instances with 45 battlefields and 75 troops in our simulations). In applications such as security or politics, it is frequent that these parameters are large. In that case, the question remains open: how to efficiently compute an equilibrium strategy?

In this work, we take a different approach that relaxes the equilibrium notion considered to gain dramatically in computational efficiency: we propose and analyze an algorithm to compute very efficiently an approximate Nash equilibrium for the discrete Colonel Blotto game with many battlefields and troops. Specifically, denoting by n the number of battlefields and by p the number of troops of the stronger player, we make the following contributions:

1. We propose a mixed strategy, which we term discrete independently uniform strategy (hereinafter DIU strategy). Inspired by partial results on the equilibrium marginals in the continuous version of the game, our strategy first generates allocations independently on each battlefield with appropriately defined distributions, then rescales them and performs a rounding process that guarantees the integer constraint while maintaining the budget constraint. This has complexity O(n).
2. Denoting Vn the total payoff of the game, we prove that the DIU strategy is an ¯ εVn-equilibrium. We give a theoretical bound on ¯ ε that shows how good of an approximation to the Nash equilibrium the DIU strategy is, depending on n and p.
3. We propose a dynamic programing algorithm to compute a best-response of a player to a given set of marginals (on each battlefield) of the adversary. Our algorithm has complexity O(p2 · n). It allows us to efficiently compute the actual value of ¯ ε for any given set of parameters of the game.
4. We perform numerical experiments that illustrate that the proposed DIU strategy provides a good approximation to the equilibrium even for a relatively moderate number of battlefields. We also compare our solution to the exact equilibrium found by the algorithm of [Behnezhad et al., 2017] both in terms of the payoff obtained and the computation time.

Our proposed algorithm computes directly a realization of the strategy, rather than computing the mixed strategy of the players (i.e., the equilibrium distribution) as in [Ahmadinejad et al., 2016; Behnezhad et al., 2017]. In practice, this is what a player would need to generate his allocation. Yet, even though the distribution from which our strategy is drawn is only implicitly defined, we prove that it provides an approximate equilibrium. Besides, it is possible to generate this distribution with arbitrary precision simply by generating many realizations independently using our proposed algorithm.

Note finally that our approximate equilibrium is not "universal" in the sense that it does not provide a good approximation for any set of parameters. Roughly, the approximation is good if the numbers of battlefields and troops are large. Yet, our proposed approximate equilibrium provides an important contribution because (i) it is a realistic case in several applications and (ii) it is precisely the case where exact equilibrium computation algorithms are computationally infeasible.

Related works The Colonel Blotto game was first introduced in 1921 in its continuous version [Borel, 1921]. Since then, a number of partial solutions have been proposed. The case of symmetric players (with identical budgets) with an arbitrary number of battlefields was solved by [Borel and Ville, 1938; Gross and Wagner, 1950; Gross, 1950], who also provided a solution for the asymmetric case with two battlefields (see also [Laslier, 2002]). In 2006, a solution was found for the case of asymmetric players with an arbitrary number of battlefields but only for homogeneous battlefields (all with identical value) [Roberson, 2006]. This solution was extended in [Schwartz et al., 2014] to heterogeneous battlefields but only under some restrictions. Today, the general case of asymmetric players with heterogeneous battlefields remains unsolved for the continuous Blotto game.

Many extensions and variants of the continuous Colonel Blotto game have been studied: relaxing the budget constraint [Myerson, 1993; Kovenock and Roberson, 2015], considering other objectives [Laslier, 2005] or analyzing sequential moves [Powell, 2009; Rinott et al., 2012]. Many applications have also been considered, e.g., to politics [Laslier, 2002], economics [Kovenock and Roberson, 2012], security [Powell, 2009], and social networks [Masucci and Silva, 2014].

The discrete version of the Colonel Blotto game has received far less attention. Partial results for special cases are proven in [Hart, 2008; Hortala-Vallve and Llorente-Saguer, 2012]. In the last two years, the discrete Colonel Blotto game attracted interest from the algorithmic game theory community. Two algorithms were proposed to compute the Nash equilibrium for the general asymmetric and heterogeneous case. A first algorithm was proposed in [Ahmadinejad et al., 2016], based on a reduction to an exponential-size linear program and a clever use of the Ellipsoid method to solve it in polynomial time. In [Behnezhad et al., 2017], another algorithm was proposed that obtains a polynomial-size linear program and solves it using the Simplex method. Although both algorithms are providing polynomial-time/size solutions to find the Nash equilibrium of the discrete Colonel Blotto game, they remain computationally intractable in practice with large numbers of troops and/or battlefields.

2 ProblemFormulation

Game model We consider a discrete Colonel Blotto game between two players denoted A and B. Each player has a fixed amount of troops (or budget), denoted m and p for A and B respectively, where m, p ∈ N. Without loss of generality, we assume that A is the weak player, i.e., m ≤ p. Throughout the paper, we denote by λ := pm the ratio of players budgets.

The game is a one-shot game where players simultaneously allocate their troops to n battlefields (n ≥ 3). A pure strategy of player A is a vector ˆxA ∈ Nn , with integer elements ˆxAi ≥ 0 representing the allocation to battlefield i (i = 1, 2 . . . , n) and satisfying the constraint ∑ni=1 ˆxAi ≤ m. Similarly, a pure strategy of player B is a vector ˆxB ∈ Nn such that the constraint ∑ni=1 ˆxBi ≤ p holds.

Each battlefield i is commonly assessed by players with a fixed value vi > 0. Values can be heterogeneous across battlefields, but we assume that each value belongs to a bounded range: vi ∈ [vmin, vmax], with 0 < vmin ≤ vmax. We denote by Vn = ∑ni=1 vi the total value of all battlefields.

Once players have allocated their troops, the player who has the higher allocation to battlefield i wins that battlefield and gains its whole value vi. In case of a tie, i.e., if xAi = xBi , player A gains αvi and player B gains (1-α) vi for some constant α ∈ [0, 1] fixed. This is a very general tie-breaking rule that includes all previously considered rules such as sharing 50-50 (α = 0.5) or giving the battlefield to the stronger player (α = 0). Each player chooses his strategy to maximize his own payoff equal to the sum of gains on each battlefield. Resources not allocated to any battlefield have no outside value.

Additional notation For brevity, we denote by CBm,p n the discrete Colonel Blotto game with n battlefields where player A has m troops and player B has p troops. We denote by ΠA (σ, γ) and ΠB (σ, γ) the expected payoffs of players A and B when playing strategies σ and γ respectively. Throughout the paper, we denote by FX the distribution function of a random variable X. We use a hat (ˆ z) to denote integers.

Approximate equilibrium We use the standard definition of an approximate equilibrium as follows: given ε ≥ 0, a strategy profile (σ∗ , γ ∗ ) is an ε-equilibrium of the game CBm,p n if ΠA(σ, γ ∗ ) ≤ ΠA(σ∗ , γ ∗ ) + ε and ΠB(σ∗ , γ) ≤ ΠB(σ∗ , γ ∗ ) + ε for any strategy σ and γ of players A and B. When it is unnecessary to emphasize the approximation error, we use the term approximate equilibrium.

3 Main Results

In this section, we give our proposed strategy and main theoretical results showing that it is an approximate equilibrium.

3.1 The DIU Strategy

Considering the game CBm,p n , we propose a mixed strategy that we call Discrete Independently Uniform strategy (DIU strategy), which will be proven to be an approximate equilibrium of the game. Intuitively, under the DIU strategy, players first draw independently numbers from some particular uniform-type distributions; then they rescale these numbers to guarantee the budget constraints; finally, they use a specific rounding process to ensure the discrete requirements.

To formalize the DIU strategy definition, we introduce, for any i ∈ {1, 2, . . . , n}, the uniform-type distributions:

We observe that FB∗ i is the (continuous) uniform distribution on [0, 2viλ/Vn] and FA∗i is the distribution where we set a probability mass (1-1/λ) at 0 and uniformly distribute the remaining mass on (0, 2viλ/Vn]. We define the rounding function rm : [0, pm ] → {0, 1m , 2m , . . . , pm }, such that ∀x, rm(x) = ˆxm , where ˆx ∈ N is uniquely determined and satisfies ˆxm - 1 2m ≤ x < ˆxm + 1 2m .

Algorithm 1: DIU strategy generation algorithm.

We can now give the formal definition of the DIU strategy. 1

Definition 3.1 (The DIU strategy). In the game CBm,p n , DIUA (respectively, DIUB) is the mixed strategy where player A's allocation ˆxA (respectively, player B's allocation ˆxB ) is randomly generated from Algorithm 1.

Remarks Algorithm 1 guarantees that the allocations are integers and satisfy the budget constraints (with equality, i.e., without any unallocated resource). More importantly, the DIUA (resp., DIUB) strategy is only implicitly defined via Algorithm 1, that is to say it is the joint distribution of all allocations {ˆxAi }i (resp., {ˆxBi }i). Each pure strategy output from Algorithm 1 is only one realization of the DIU strategy.

Algorithm 1 is easy to implement and runs very fast in expected time O(n). Note that the for loop in lines 2-4 is not guaranteed to end in finite time. However, the probability that the loop runs over k times is (1 - 1/λ)kn and converges to zero exponentially fast in k and n. To guarantee that the algorithm ends in finite time, it is possible to put a stopping criterion and assign an arbitrary allocation to player A if it is reached. As this will happen with increasingly low probability as n grows, it can be seen from the proof of Theorem 3.2 that the result will still hold. On the other hand, the summation ∑nj=1 bj equals 0 only with probability zero, therefore we do not need an additional condition for the for loop in lines 5-6.

When applying the DIU strategy, player A's allocation to battlefield i = 1, 2, . . . , n follows the marginal distributions FADi while player B's allocation follows FBD i whose corresponding random variables are defined as:

1 We use the term DIU strategy to commonly address DIUA and/or DIUB when unnecessary to emphasize a particular player.

where for any k = 1, 2, . . . , n,

and random variables A∗k , B∗ k have distributions (3.1)-(3.2).

We end this subsection by briefly describing the intuition behind the construction of the DIU strategy in Definition 3.1. First of all, from the equilibrium analysis done in [Roberson, 2006] and [Schwartz et al., 2014] for the continuous Colonel Blotto game with n battlefields, where player A's budget is 1 and player B's budget is λ, the equilibrium marginal distributions of players' allocations to battlefield i follow distributions FA∗i and FB∗ i . That is to say, a joint distribution (if it exists) satisfying the constraint ∑ni=1 xAi ≤m and yielding the marginal distributions {FA∗i }i will be a feasible strategy of player A which constitutes an equilibrium of this continuous game. However, the construction of such a strategy (and even its existence) remains an open question.

On the other hand, by employing the DIU strategy in the discrete Colonel Blotto game, players' marginal allocations at battlefield i follow the distributions FADi and FBD i . These distributions are rm-rounded from terms expressed by distributions FAni and FBn i , which in turn, uniformly converge towards FA∗i and FB∗ i when n → ∞. The key idea is that, the requirement to have discrete allocations in the discrete game is less and less significant when the granularity of the game increases (i.e. mn , pn → ∞), which makes it similar to the continuous variant. Thus, based on the optimality in the continuous variant of FA∗i against FB∗ i (and vice versa), we expect to have "near-optimality" in playing DIUA strategy against DIUB strategy (and vice versa), with any arbitrary error ¯ εVn > 0, given large parameters n, m, p.

3.2 Approximate Equilibrium of The Discrete Colonel Blotto Game

Theorem 3.2. The DIU strategy is an ¯ εVn-equilibrium of the Colonel Blotto game CBm,p n (m ≤ p), where ¯ ε ≤max{ ˜O(n-1/2 ),O(n/m)} and Vn is the total value across all battlefields. 2

The upper bound on ¯ ε given by this theorem is important because it allows us to evaluate the approximation error in terms of the number of battlefields and amount of troops. Indeed, we can look at Theorem 3.2 from a different perspective and interpret it by an equivalent statement:

Restatement of Theorem 3.2. Fix λ ≥ 1 and ¯ ε > 0; there exists N ∗ = O ( ¯ ε-2 ln(¯ ε-1 )) such that for n ≥ N ∗ , there exists M ∗ = O(n/¯ ε) such that for m ≥ M ∗ and p = mλ ∈ N, in the game CBm,p n , for any pure strategies ˆxA and ˆxB of player A and B,

2 The ˜O notation is a variant of the big-O notation that "ignores" logarithmic factors.

At a high level, this confirms the intuition that if the number of battlefields and the budgets are large enough, then the DIU strategy yields a near-optimal payoff against the opponent's DIU strategy. The precise result shown in this theorem, however, goes much beyond merely showing this convergence and it is interesting and non-trivial in a number of ways. First, Theorem 3.2 tells us exactly how the parameters m and n should be to reach a given level of approximation. We notice in particular that if the ratio m/n is small, then the approximation may not be good, however large n gets.

Second, Theorem 3.2 involves a double limit, with two growing parameters (n and m), and it identifies a precise scaling regime (i.e., ratio between the two growing parameters) under which the convergence holds. Here, Theorem 3.2 shows that the DIU strategy converges towards an equilibrium as soon as m grows at least as fast as n3/2 . This implies that, if we first make m grow to infinity, and then make n grow to infinity, the result will hold. However, the reverse is not true: if n grows first or simply if m grows too slowly compared to n, then the DIU does not converge towards an equilibrium. Intuitively, if the number of troops is low compared to the number of battlefields, then the average number of troops per battlefield at equilibrium becomes low and the DIU strategy based on a discretization of a uniform-type distribution is no longer close to optimal.

Note that due to space constraints, we limited the statement of our result to emphasize the dependence on n and m but our proof also allows extracting the dependence of ¯ ε on vmin, vmax and λ. One then observes that the convergence is slower if vmax/vmin is larger (i.e., the battlefields heterogeneity is higher) and if λ is larger (i.e., the players asymmetry is higher). Note that we have written the above discussion with m, but the exact same holds with p instead.

Finally, we remark that CBm,p n is a constant-sum game. Therefore, by using inequalities (3.6) and (3.7), we can straightforwardly prove that the DIU strategy is an approximate max-min strategy of the game. This is presented as the following corollary of Theorem 3.2.

Corollary 3.3. ∀λ ≥ 1, ∀¯ ε > 0, ∃N ∗ = O(¯ ε-2 ln(¯ ε-1 )) : ∀n ≥ N ∗ , ∃M ∗ = O(n/¯ ε) : ∀m≥M ∗ , p = mλ ∈ N, in the game CBm,p n , for any strategies σA and σB of players A and B,min

This corollary ensures that the DIU strategy gives the nearoptimal payoff to any player Q ∈ {A, B} even in the worstcase (when the opponent -Q plays the strategy that minimizes Q's payoff). This emphasizes the fact that players can "safely" use the DIU strategy in practice.

4 Numerical Evaluation

In this section, we turn to the numerical computation of quantities related to the DIU strategy, in particular to evaluate the quality of the approximation it gives depending on the game's parameters.

4.1 ADynamic-Programming Algorithm for the Best Response

First, computing the value of ¯ ε (or how close a given mixed strategy of player A is to the equilibrium) requires finding player B's optimal allocation given that player A's allocation to battlefield i = 1, 2 . . . , n follows a given marginal distribution {Gi}i=1,2,...,n . This itself is a non-trivial problem since there is in principle an exponential number of possible allocations to investigate. We propose an efficient algorithm based on dynamic programming [Bertsekas, 2017] to solve this problem. This is formally presented as the following proposition.

Proposition 4.1. Algorithm 2 finds a best response strategy of player B and his optimal payoff against any set of player A's marginals with complexity O (p2 · n).

Note that, although our primary motivation is to compute a best-response of a player to the DIU strategy, the algorithm has broader applicability since it works for any mixed strategy of the adversary. We discuss here the main intuition behind Algorithm 2 and give a descriptive proof of Proposition 4.1. Note firstly that the algorithm is presented here with tie-breaking parameter α = 0 for simplicity but could straightforwardly be adapted to any tie-breaking rule. In this algorithm, H(j, i) denotes the expected payoff that player B gains from battlefield i by allocating j troops to it, which is computed via the equation in line 4. More specifically, since α = 0, by allocating j troops to battlefield i, player B wins the value vi if j is at least equal to player A's allocation. Since Gi is the marginal distribution of player A in this battlefield, then Gi(j) is exactly the probability of this event, which implies the expected gain of player B. There are (p + 1) n terms H(j, i) to compute yielding the complexity O(p · n) to do so.

On the other hand, we denote Π(j, i) the optimal payoff of player B when he is allowed to spend j troops over the set {1, 2, . . . , i} of battlefields; thus, Π(p, n) is exactly the bestresponse payoff of player B. The computation of Π(j, i) is done by working backwards with the recursive equation given in line 5. To spend j troops over i battlefields {1, 2, . . . , i}, player B has to choose k ∈ {0, 1, . . . , j} troops to allocate across the first i - 1 battlefields (whose optimal payoff is denoted Π(k, i - 1)), and put the remaining (j - k) troops on ith-battlefield (which induces the payoff H(j - k, i)). He then optimizes the payoff to find Π(j, i) by selecting the number k which maximizes the summation between the payoffs gained from these two parts. There are O(p · n) terms Π(j, i) needed to compute, each is done by comparing between at most (p + 1) terms; thus it yields the complexity O(p2 · n) to do so. Finally, the algorithm finds a best response strategy yielding this optimal payoff with complexity O(p · n) as in lines 7-9. Hence, we conclude the proof of Proposition 4.1.

Reversing the roles of A and B, we can construct a similar algorithm with complexity O (m2 · n) to find the best response payoff of player A against any given set of player B's marginals. Note also that the algorithm is presented here with α = 0 for simplicity but it could straightforwardly be adapted to any tie-breaking rule.

Input: n, m, p ∈ N, v ∈ [vmin, vmax]n and marginals {Gi}i=1,2,...,n of player A Output: Payoff Π(p, n) and BR strategy { ˆxB1 , · · · , ˆxBn } 1 for j = 0, 1, . . . , p do 2 Π(j, 0) = 0 3 for i = 1, 2, . . . , n do 4 H(j, i) = viGi(j) 5 Π(j, i) = max k=0,...,j {Π (k, i - 1) + H (j - k, i)} 6 j = p 7 for i = n, n-1, . . . , 1 do 8 ˆxBi = argmax k=0,1,...,j {Π (j - k, i - 1) + H(k, i)} 9 j = j - ˆxBi

4.2 Numerical Experiments

In practice, we first observe that a pure strategy instructing players to allocate their resources following the DIU strategy can be generated from Algorithm 1 in time O(n), which is negligible even for extremely large values of the parameters.

On the other hand, since the marginal allocations at battlefield i under the DIU strategy, FADi and FBD i , are not known in closed-form, we approximate them by their corresponding empirical CDFs denoted ¯ FADi and ¯ FBD i computed by drawing "many" realizations of the DIU strategy from Algorithm 1. Indeed, it is known by the Glivenko-Cantelli theorem [Vaart, 1998] that the empirical CDF converges uniformly towards the actual CDF, with a maximum difference in O(K-1/2 ) where K is the number of realizations drawn. Then, to guarantee that the approximation of the DIU's CDF by its empirical CDF does not affect the computed value of ¯ ε, we only need to take K ≥ O(n) (since ¯ ε is of the order ˜O(n-1/2 ) according to the previous section). Overall, generating a good approximation of the DIU's marginal distribution therefore takes time O(n2 ), still negligible even for large values. Finally, to compute ¯ ε, for each player Q ∈ {A, B}, we compare the expected payoff ΠQ(DIUA,DIUB) to player Q's bestresponse payoff obtained from Algorithm 2 against the set of marginal distributions { ¯ F(-Q)Di }i of player -Q.

We construct several numerical experiments using R to illustrate the efficiency of using the DIU strategy as an approximate equilibrium of discrete Colonel Blotto games. 3 Our experiments run on a computer with an Intel core i5-7500U 2.60GHz processor and 8GB of RAM. In all the experiments, we keep α = 0 and λ = p/m fixed, thus the values of m and p always have the same growth rate (up to the multiplicative constant λ); and we vary n and m. For each set of values n,m, p, we independently generate a value for each battlefield uniformly distributed in [vmin, vmax], with vmin = 1 and vmax = 8. Then, for each instance of n,m, p, (v1, v2, . . . , vn) we run the simulation 3 times, each time computing the eCDFs with K = 10 · n to ensure not to affect the evaluation on ¯ ε and running Algorithm 2 with these eCDFs to compute ¯ ε, and take the average of results.

3 Our code for these experiments can be found at https://github. com/dongquan11/Approx discrete Blotto

Figure 1(a) shows the results. We first notice that when m (and p) increases, the error ¯ ε generally decreases in consistency with Theorem 3.2. Moreover, when m is relatively small, the error ¯ ε is higher with instances having higher number of battlefields n. This is consistent with Theorem 3.2, stating that when the ratios m/n and p/n are low (they decrease when n increases), the upper bound of ¯ ε is not good. For instances with higher values of m, these ratios are sufficiently large to ensure that ¯ ε decreases when either m or n (or both) increase. This interpretation is also consistent with the results shown in Figure 1(b). When the value of n increases, at the beginning where the ratio m/n is still sufficiently large, ¯ ε decreases. However, since we keep m (and p) fixed in this experiment, the ratio m/n gradually decreases, which makes the errors to eventually get worse. Recall that, for each experiment presented here, we independently generate a value for each battlefield uniformly distributed in [vmin, vmax]; this process explains the randomness observed in the plots.

We finally compare our work with the algorithm proposed in [Behnezhad et al., 2017], 4 which finds an exact equilibrium of the game (we denote it Algorithm EQ). Table 1 shows the computation time of evaluating the error in using DIU strategy and elapsed time of Algorithm EQ for several instances. We observe that it takes remarkably less time to compute the DIU strategy payoffs and give an upper bound of the potential error by using Algorithm 2. Note that the computation times shown here include the time to compute the empirical CDF of the DIU strategy by drawing sufficiently many realizations (recall that we take K = 10 · n to ensure not to affect the evaluation on ¯ ε) and the elapsed time of Algorithm 2. Moreover, the last column of Table 1 shows that the DIU strategy payoffs are very close to the exact equilibrium payoffs, even for instances with small values of the parameters n,m and p.

In conclusion, it is important to note that we do not claim that our algorithm can replace more efficiently the algorithm of [Behnezhad et al., 2017] (in fact, we are not computing the same thing). However, our results show that, for large values of n, m and p, the DIU strategy, which can be computed very efficiently, can be safely used by the players as it provides a good approximation to the equilibrium.

5 Sketch of The Proof of Theorem 3.2

In this section, we give the main elements of the proof of Theorem 3.2 in its restatement. We note that, although the main idea behind the DIU strategy is quite simple, the proof of this theorem is non-trivial and requires careful analysis to achieve the upper bound on ¯ ε. Due to space constraints, we only give the very rough steps of the proof of inequality (3.6); and we omit less important or more technical details. A complete proof can be found in [Vu et al., 2018].

4 We use the authors' implementation from https://github.com/ Soben713/ColonelBlotto

Step 1: We start by rewriting (3.6). If player A plays DIUA and allocate ˆ y at battlefield i against player B's DIUB strategy, he strictly wins battlefield i with probability FBD i (ˆ y -1) and has a tie with probability P(BD i = ˆ y). Hence, according to our general tie-breaking rule,

Similarly, ΠA ( ˆxA,DIUB) is also expressed as the summation of the terms related to FADi and FBD i . However, the closed-form expressions of these distributions are unknown. Therefore, we need to approximate and compare these payoffs via other terms, in particular the distributions FA∗i and FB∗ i . This can be obtained by using the following lemma:

Lemma 5.1. Fix λ ≥ 1, ∀¯ ε > 0, ∃N ∗ := ˜O ( ¯ ε-2 ln(¯ ε-1 )) : ∀n ≥ N ∗ , ∃M1 := O(n/¯ ε) : ∀m ≥ M1, ∀i = 1, 2, . . . , n,

and similarly for FBD i and FB∗ i .

Proof. To prove (5.2), we first deduce from the special features of the rounding function rm that ∀ˆx ∈ N, ∀i∈{1, 2, . . . , n}, FAni (ˆx/m)≤FADi (ˆx)≤FAni ((ˆx+1)/m).

Based on Hoeffding's inequality and an intuition similar to Slutsky's theorem, we can prove that FAni uniformly converges towards FA∗i with rate n ≥ ˜O ( ¯ ε-2 ln(¯ ε-1 )). Then we get that, ∀n ≥ N ∗ = ˜O ( ¯ ε-2 ln(¯ ε-1 )),

Step 2: Using Lemma 5.1, we can approximate Π1 via FA∗i and FB∗ i . However, we notice that this expression contains a summation of m+1 terms, which leads to an error in O(mε) (a large number when m → ∞) if we naively (approximately) replace FADi and FBD i by FA∗i and FB∗ i . Hence, we must do a finer approximation by noticing that P (ADi > ⌈2 vi Vn p⌉) is upper bounded by O(¯ ε) as n ≥ N ∗ ,m≥M1. Therefore, by carefully analyzing this summation, we have

*The maximum rescaled difference between DIU payoffs and exact equilibrium payoffs

Table 1: Comparison between DIU error evaluation time and Algorithm EQ.

Step 3: On the other hand, for any n ≥ N ∗ and m≥M2 := O(nα/¯ ε), for any pure strategy ˆxA, we can prove that P (BD i = ˆxAi ) ≤ ¯ ε/(2α); therefore 5

Step 4: Finally, using Lemma 5.1, for n ≥ N ∗ ,m ≥ M1, we have the approximation

By combining (5.1), (5.3), (5.4) and (5.5), we conclude (3.6) by choosingM ∗ :=max{M1,M2}.

6 Concluding Discussion

In this work, we propose the DIU strategy, defined by a simple algorithm, and prove it to be an approximate equilibrium of the discrete Colonel Blotto game. Our theoretical results also show precisely how large the number of troops and the number of battlefields of the game should be to ensure a certain level of approximation. We construct a best-response dynamic programming algorithm that efficiently computes the best-response to any marginal allocation of the opponent; and use it to evaluate the approximation error of employing the DIU strategy in practice via several numerical experiments. Our work extends the scope of applications of discrete Colonel Blotto games by trading off the accuracy with the computational efficiency, which is useful for analyzing games with large values of the parameters.

5 Here, we consider α ̸= 0. In case α = 0, we have Π2 = 0 and (3.6) is trivially implied by (5.1), (5.3) and (5.5).

Note finally that Theorem 3.2 proves that the DIU strategy is an approximate equilibrium, i.e., no unilateral deviation can significantly improve a player's payoff. This does not directly imply that the marginals obtained under the DIU strategy are close to the marginals of the exact equilibria, although we conjecture that this is true as well (and leave its proof for future work).

Acknowledgments

This work was supported by the French National Research Agency through the "Investissements d'avenir" program (ANR-15-IDEX-02) and through grant ANR-16-TERC0012; and by the Alexander von Humboldt Foundation. It was partly done at the Laboratory of Information, Networking and Communication Sciences (LINCS). The authors also thank Nicolas Gast and Bruno Gaujal for helpful discussions on this work.