# An Algorithmic Solution to the Blotto Game using Multi-marginal Couplings

Vianney Perchet  Crest, ENSAE  Criteo AI LAB<EMAIL_ADDRESS>,
Philippe Rigollet  Department of Mathematics, MIT<EMAIL_ADDRESS>and
Thibaut Le Gouic  Aix Marseille University, Centrale Marseille, CNRS, I2M
<EMAIL_ADDRESS>
###### Abstract.

We describe an efficient algorithm to compute solutions for the general two-
player Blotto game on $n$ battlefields with heterogeneous values. While
explicit constructions for such solutions have been limited to specific,
largely symmetric or homogeneous, setups, this algorithmic resolution covers
the most general situation to date: value-asymmetric game with asymmetric
budget with sufficient symmetry and homogeneity. The proposed algorithm rests
on recent theoretical advances regarding Sinkhorn iterations for matrix and
tensor scaling. An important case which had been out of reach of previous
attempts is that of heterogeneous but symmetric battlefield values with
asymmetric budget. In this case, the Blotto game is constant-sum so optimal
solutions exist, and our algorithm samples from an $\varepsilon$-optimal
solution in time $\tilde{\mathcal{O}}(n^{2}+\varepsilon^{-4})$, independently
of budgets and battlefield values. In the case of asymmetric values where
optimal solutions need not exist but Nash equilibria do, our algorithm samples
from an $\varepsilon$-Nash equilibrium with similar complexity but where
implicit constants depend on various parameters of the game such as
battlefield values.

††conference: ; ;

##  1\. Introduction

A century ago, Emile Borel published his seminal paper on _the theory of play
and integral equations with skew symmetric kernels_ (Bor, 21), see also
(von1959role, Page 157). While perhaps not as conspicuous, it predates von
Neumann’s monumental work _on the theory of games of strategy_ (von, 28) by
several years. In this work, Borel describes what is now called the Blotto
game and introduces the notions of strategy, mixed strategies and even
foresees the fruitful interactions between game theory and economics that are
to be observed throughout the century. As such, the Blotto game is considered
to be the genesis of modern game theory (Fré, 53; Nak, 06). Despite its
prestigious pedigree, equilibrium strategies for this game are only known in
special cases.

Blotto is a resource-allocation game in which two players competes over $n$
different battlefields by simultaneously allocating resources to each
battlefield. The following two additional characteristics are perhaps the most
salient features of the Blotto game:

  1. (1)

_Winner-takes-all_ : For each battlefield, the player allocating the most
resources to a given battlefield wins the battlefield.

  2. (2)

_Fixed budget_ : each player is subject to a fixed—and deterministic—budget
that mixed strategies should satisfy almost surely.

Despite its apparent simplicity the Blotto game captures a variety of
practical situations that extend far beyond the context of the above military
terminology. These include political strategy (Mye, 93; LP, 02; MMT, 05),
network security (LHSR, 15; FSM, 21), and various forms of practical auction
markets (MS, 15; HM, 17).

The goal of this paper is to efficiently construct a Nash equilibrium for this
game or, when they exist, an optimal strategy.

Prior work. Despite its century-long existence, Nash equilibria for the Blotto
game are only known under various restrictions on the main parameters of the
problem: the budget of each player and the value given to each battlefield.

  * •

_Budget._ A large fraction of the literature considers the case where the
players have _symmetric budgets_ , starting with the original problem of Borel
(Bor, 21) and in most of the main contributions throughout the twentieth
century (Bor, 21; BV, 38; Gro, 50; GW, 50; Las, 02; Tho, 18). The case of
symmetric budgets is well understood except in the setup where players may
disagree on the value of battlefield that was recently introduced (KR, 21).

  * •

_Battlefields._ When the two players have a different budget the situation
becomes more complex as the poorest will have to forfeit some battlefields. In
this case, only partial results are known. To understand what “partial” means,
recall that full generality of the battlefield values occurs when (i) players
may assign a different value to a given battlefield—we say that the values are
_asymmetric_ —and (ii) these values may vary across battlefield—we say that
the battlefields are _heterogeneous_. Partial results are known for symmetric
values. Even under this simplifying assumption, the case of heterogeneous
battlefields remains poorly understood, except in the case of two battlefields
(MM, 15). In the case of more than two battlefields, Nash equilibria are known
for homogeneous battlefields (Rob, 06) or under stringent assumptions on the
battlefield values (SLS, 14) that essentially reduce to the homogeneous case.

We refer the reader to Table 1 for a survey of recent advances. While we
tackle the most general setup to date, we stress that an important case was
not covered by prior literature: the case of asymmetric budget, heterogeneous
and symmetric values. Indeed, in this case, the game is constant-sum and
optimal strategies exist. Our results also cover the case of asymmetric values
introduced very recently in (KR, 21) but this setup leads to only Nash
equilibria rather than optimal strategies. Whenever possible, we conflate the
two setups and simply refer to a _solution_ to the Blotto.

A discrete version of the Blotto game where both budgets and allocations are
required to be integral was also introduced in Borel’s original paper (Bor,
21). Explicit optimal solutions were provided in (Har, 08) for the homogeneous
and symmetric version of the discrete game; see also (HVLS, 12) for partial
solutions in the asymmetric-value case. More recently, this discrete version
has seen significant computational advances (ADH+, 19; Bea, 22). Conceptually,
this line of work is close to the present paper in the sense that it provides
an algorithm to sample from approximate solutions. Moreover, the discrete
Blotto game can be seen as a discretization of the continuous version of
interest here and that could be quantified using the arguments of Section 4.
However carrying out this analysis, for instance based on (Bea, 22, Theorem
4.2), leads to worse dependence on $n$ and $\varepsilon$ compared to Theorem 1
here. More strikingly, the complexity bound of Theorem 1 does not depend on
budgets or battlefield values while this dependence is polynomial in the
bounds for discrete Blotto. The two lines of work also differ in more profound
ways. First and foremost, the approach employed here is fundamentally
different: it aims at mixing known solutions for the related Lotto game while
solutions to the discrete Blotto games are more agnostic so that it is unclear
what the marginals of the resulting strategy are. In particular, the present
approach allows us sample from $\varepsilon$-Nash equilibria in the
asymmetric-value case whereas this setup is currently out of reach for
solutions to the discrete Blotto game.

Finally, note that our approach also yields new (existential) results for the
discrete Blotto game. Since they are not the focus of our contribution, they
are relegated to the appendix.

Our contributions. All of the above solutions for two-player games have
consisted in constructing explicit solutions. Because of the budget
constraints, these strategies can be decomposed in two parts: _marginal
distributions_ that indicate which (random) strategy to play on each
battlefield and a _coupling_ that correlates the marginal strategies in such a
way to ensure that the budget constrained is satisfied almost surely.

The first question may be studied independently of the second by considering
what is known as the (General) _Lotto_ game (BC, 80). In this game the budget
constraint need only be enforced in _expectation_ with respect to the
randomization of the mixed strategies. While this setup lacks a defining
characteristic of the Blotto game (fixed budget), it has the advantage of
landing itself to more amenable computations. Indeed, unlike the Blotto game,
a complete solution to the Lotto game was recently proposed in (KR, 21) where
the authors describe an explicit Nash equilibrium in the most general case:
asymmetric budget, asymmetric and heterogeneous values.

In light of this progress a natural question is whether the marginal solutions
discovered in (KR, 21) can be _coupled_ in such a way that the budget
constraint is satisfied almost surely. We provide a positive answer to this
question by appealing to an existing result from the theory of _joint
mixability_ (WW, 16). Mixability asks the following question: Can $n$ random
variables $X_{1},\ldots,X_{n}$ with prescribed marginal distributions
$X_{i}\sim P_{i}$, be coupled in such a way that
$\operatorname{\mathrm{var}}(X_{1}+\cdots+X_{n})=0$. Joint mixability is
precisely the step required to go from a Lotto solution to a Blotto one by
coupling the marginals of the Lotto solution in such a way that the budget
constraint is satisfied.

In this paper we exploit a simple and new connection between joint mixability
and the theory of _multi-marginal couplings_ that has recently received a
regain of interest in the context of optimal transport (AC, 11; DMGN, 17; ABA,
20). In multi-marginal optimal transport, the goal is to optimize a cost over
the space of couplings with given marginals. Unlike the case of two marginals
that arises in traditional optimal transport, this question raises significant
computational challenges and often leads to NP-hardness (ABA, 21). In the
language of optimization, joint mixability merely asks if the set of
constraints is nonempty. We propose an algorithmic solution to the Blotto
problem by efficiently constructing a coupling that satisfies the budget
constraint almost surely and can be easily sampled from. Our construction
relies on three key steps: first we reduce the problem to a small number of
marginals to bypass the inherent NP hardness of multi-marginal problems,
second we discretize the marginals and finally, we employ a multi-marginal
version of the Sinkhorn algorithm (Sin, 64; SK, 67) to construct a coupling of
the discretized marginals. After a simple smoothing step, we produce a
sampling with continuous marginals that are close to the ones prescribed by
the Lotto solutions and from which it is straightforward to sample.
Furthermore, we quantify the combined effect of discretization error and of
the Sinkhorn algorithm on the value of the game, effectively leading to an
_approximate_ Nash equilibrium and even to an approximately optimal solution
in the case of symmetric values.

We exhibit tight—or near-tight in the asymmetric values case—conditions for
the mixability of _specific_ Lotto solutions into Blotto solutions; see
Corollaries 6 and 7 below. While these conditions are reasonable and cover
most cases, some heavily skewed games, either in terms of budget asymmetry or
values inhomogeneity, are not covered by our results. We leave it as an open
question to exhibit Lotto strategies that can be mixed into Blotto ones even
for such games.

The rest of this paper is organized as follows. In the next section, we recall
the solution for the Lotto game and show that they can be turned into
solutions for the Blotto game. This existential result simply appeals to
existing results of joint mixability. We move from an existential to an
algorithmic result in Section 3 by proceeding in three steps: first we reduce
the problem to the case $n=4$, then we discretize the problem and finally we
apply Sinkhorn algorithm to couple the resulting marginals in a appropriate
fashion. The main product of Section 3 is Algorithm 8 which shows how to
sample from an approximate solution to the Blotto game. Finally, we provide a
detailed complexity analysis for this algorithm in Section 4, showing in
particular, that it runs in time polynomial in the parameters of the Blotto
game and the approximation error $\varepsilon$. Finally, our techniques also
yield new results for the discrete Blotto game largely studied by (Har, 08;
HVLS, 12) that are of independent interest. We postpone them to the appendix.

Notation. For any integer $n$, define $[n]=\\{1,\ldots,n\\}$. We use ${\bf 1}$
to denote an all-ones vector or tensor. Note that the dimension of this vector
will be clear from the context but may vary across occurrences. For any two
vectors $x,y$, we denote their entrywise (Hadamard) product $x\odot y$ and
their entrywise division $x\oslash y$ whenever $y$ has only nonzero entries.
For any two real numbers $a,b$ we denote by $a\vee b$ their maximum and by
$a\wedge b$ their minimum.

##  2\. Solutions for Blotto and Lotto games

The goal of this section is to describe the Blotto game and its connection to
the Lotto game for which explicit solutions are known. We first recall a
solution for the Lotto game derived in (KR, 21) and show that it can be
readily turned into a Blotto solution using the theory of joint mixability.

###  2.1. The Blotto game

The classical two-player _Blotto_ game is formalized as follows. Two players,
respectively denoted by $A$ and $B$, are competing over $n\geq 2$ battlefields
denoted by $i\in[n]$. Since we focus on two-player games where both players
obey the same rules, it will be convenient when describing the game to denote
by $P\in\\{A,B\\}$ either player and by $\bar{P}$ the other player so that
$(P,\bar{P})\in\\{(A,B),(B,A)\\}$.

The _datum_ of a Blotto game is as follows. Player $P\in\\{A,B\\}$ has a total
budget of $T_{P}>0$ to allocate across the $n$ battlefields. Moreover, she
valuates battlefield $i\in[n]$ to $v_{P,i}>0$ which may differ from
$v_{\bar{P},i}$. Without loss of generality, we assume that $T_{A}\geq T_{B}$
to break symmetry and that

(1) $\sum_{i\in[n]}v_{A,i}=\sum_{i\in[n]}v_{B,i}=1$

Indeed, multiplying the value of all battlefields by the sames’ constant has
no impact on the players’ strategies.

The _rules_ of the Blotto game are as follows. A pure strategy for player $P$
is an allocation vector $x_{P}=(x_{P,1},\ldots,x_{P,n})$ where $x_{P,i}>0$ is
the amount allocated to battlefield $i\in[n]$. A mixed strategy for player $P$
is a probability distribution over pure strategies. A salient feature of the
Blotto game is that a player $P$ is constrained to playing strategies that
satisfy the budget constraint: $x_{P,1}+\ldots x_{P,n}\leq T_{P}$. In turn,
admissible mixed strategies for the Blotto games are random vectors
$X_{P}\in\mathds{R}^{n}$ such that

(2) $\sum_{i=1}^{n}X_{P,i}\leq T_{P}\quad\text{almost surely.}$

Given two pure strategies $x_{P}$ and $x_{\bar{P}}$ for players $P$ and
$\bar{P}$ respectively, player $P$ wins battlefield $i\in[n]$ if
$x_{P,i}>x_{\bar{P},i}$ and receives a reward $v_{P,i}>0$. Ties
$x_{P,i}=x_{\bar{P},i}$ are broken arbitrarily as they are are irrelevant for
our analysis.

The existence of Nash equilibria is a consequence of standard game theoretic
arguments (Ren, 99). Unfortunately, these general results say little about the
structure of equilibrium strategies. At the end of this section, we make
partial progress towards this question by describing the marginals of such
equilibrium strategies. However, these remain existential results in essence.

This is in stark contrast with the associated Lotto game, described in the
following section, where the hard budget constraint is dropped in favor of a
constraint in expectation, and whose explicit solutions have been computed.

###  2.2. The associated Lotto game

A _Lotto_ game has the same data and rules as its associated Blotto game
except for the almost sure budget constraint (2) which is relaxed to the
following _expected_ budget constraint:

(3) $\sum_{i=1}^{n}\mathds{E}[X_{P,i}]\leq T_{P}$

This relaxation greatly simplifies the game. In fact, Kovenock and Roberson
(KR, 21) have recently elicited an explicit characterization of a non-trivial
Nash equilibrium for the most general version of the Lotto game to date; see
Table 1. In the rest of Section 2.2, we describe their solution in details
since it is the basis for ours.

| Continuous | Asymm. | Heterogeneous | Asymm. | More than 3 | Complete
---|---|---|---|---|---|---
| Strategy | Budget | Values | Values | Battlefields | Results
(BV, 38) | ✓ | ✗ | ✗ | ✗ | ✗ | ✓
(GW, 50) | ✓ | ✗ | ✗ | ✗ | ✓ | ✓
(Wei, 12) | ✓ | ✗ | ✗ | ✗ | ✓ | ✓
(Gro, 50) | ✓ | ✗ | ✓ | ✗ | ✓ | ✓
(Las, 02) | ✓ | ✗ | ✓ | ✗ | ✓ | ✓
(Tho, 18) | ✓ | ✗ | ✓ | ✗ | ✓ | ✓
(GW, 50) | ✓ | ✓ | ✓ | ✗ | ✗ | ✓
(Rob, 06) | ✓ | ✓ | ✗ | ✗ | ✓ | ✓
(MM, 15) | ✓ | ✓ | ✓ | ✗ | ✗ | ✓
(SLS, 14) | ✓ | ✓ | ✓ | ✗ | ✓ | ✗
(KR, 21) | ✓ | ✓ | ✓ | ✓ | ✓ | ✗
This paper | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
Table 1. Variants of the continuous Blotto game and their solutions. The last
column, “complete results” indicates whether results obtained hold with
possibly strong assumptions on the different values (for instance, there
always exist more than 3 battlefields with the exact same value).

Finding an optimal strategy for the Lotto game amounts to finding a stationary
point for an optimization problem subject to constraints of the form (3).
Because of linearity of expectation, the associated Lagrangian is decomposed
as the sum of $n$ terms, one per battlefield, that are each mathematically
equivalent to an “all-pay” auction whose solutions are well known.

More explicitly, Nash equilibria of the Lotto problem depend on two parameters
$\gamma\geq 0$ and $\lambda\geq 0$, that are set later on. First, given any
$\gamma\geq 0$, consider the subsets of battlefields $\mathcal{N}(\gamma)$
that are at least $\gamma$-times more valuable to $A$ than to $B$:

$\mathcal{N}(\gamma)=\\{i\in[n],\ \frac{v_{A,i}}{v_{B,i}}\geq\gamma\\}\,.$

Given a scaling parameter $\lambda\geq 0$ to be defined later, the mixed
strategy of player $A$ at equilibrium prescribes to allocate a (random) budget
of $X_{A,i}$ to battlefield $i$ with distribution given by:

$X_{A,i}\sim\left\\{\begin{array}[]{ll}\displaystyle{\sf
Unif}\left[0,\frac{\gamma v_{B,i}}{\lambda}\right]&\text{if
}i\in\mathcal{N}(\gamma)\\\ \displaystyle\left(1-\frac{v_{A,i}}{\gamma
v_{B,i}}\right)\delta_{0}+\frac{v_{A,i}}{\gamma v_{B,i}}{\sf
Unif}\left[0,\frac{v_{A,i}}{\lambda}\right]&\text{if
}i\notin\mathcal{N}(\gamma)\,.\end{array}\right.\,,$

where $\delta_{0}$ denotes the Dirac point mass at $0$.

The strategy of player $B$ is given by

$X_{B,i}\sim\left\\{\begin{array}[]{ll}\displaystyle\left(1-\frac{\gamma
v_{B,i}}{v_{A,i}}\right)\delta_{0}+\frac{\gamma v_{B,i}}{v_{A,i}}{\sf
Unif}\left[0,\frac{\gamma v_{B,i}}{\lambda}\right]&\text{if
}i\in\mathcal{N}(\gamma)\,,\\\ \displaystyle{\sf
Unif}\left[0,\frac{v_{A,i}}{\lambda}\right]&\text{if
}i\notin\mathcal{N}(\gamma)\end{array}\right.\,.$

Note that the strategy of $A$ and $B$ are the same except that the roles of
$v_{A,i}$ and $\gamma v_{B,i}$ are switched. In that sense, $\gamma$ plays the
role of an “exchange” rate that accounts for discrepancies between budgets and
valuations across the two players.

It remains to find the parameters $\gamma$ and $\lambda$ using the budget
constraints. For this set of strategies, saturating the total budget
constraint (2) readily yields the following two equations:

(4) $\displaystyle\lambda T_{A}$
$\displaystyle=\sum_{i\in\mathcal{N}(\gamma)}\frac{\gamma
v_{B,i}}{2}+\sum_{i\not\in\mathcal{N}(\gamma)}\frac{(v_{A,i})^{2}}{2\gamma
v_{B,i}}=\frac{1}{2}\sum_{i=1}^{n}(\gamma
v_{B,i})\wedge\frac{(v_{A,i})^{2}}{\gamma v_{B,i}}\,,$ (5)
$\displaystyle\lambda T_{B}$
$\displaystyle=\sum_{i\in\mathcal{N}(\gamma)}\frac{(\gamma
v_{B,i})^{2}}{2v_{A,i}}+\sum_{i\not\in\mathcal{N}(\gamma)}\frac{v_{A,i}}{2}=\frac{1}{2}\sum_{i=1}^{n}\frac{(\gamma
v_{B,i})^{2}}{v_{A,i}}\wedge v_{A,i}\,.$

Any pair $(\gamma,\lambda)$ solving the above system of two equations yields a
Nash equilibrium. It remains to show that such solutions may be computed
efficiently. Observe that eliminating $\lambda$ from the equations yields the
following nonlinear equation in $\gamma$:

$\displaystyle f(\gamma):$
$\displaystyle=\gamma^{3}\left(T_{A}\sum_{i\in\mathcal{N}(\gamma)}\frac{v_{B,i}^{2}}{v_{A,i}}\right)-\gamma^{2}T_{B}\sum_{i\in\mathcal{N}(\gamma)}v_{B,i}+\gamma
T_{A}\sum_{i\not\in\mathcal{N}(\gamma)}v_{A,i}-T_{B}\sum_{i\not\in\mathcal{N}(\gamma)}\frac{v_{A,i}^{2}}{v_{B,i}}$
(6) $\displaystyle=\gamma
T_{A}\sum_{i=1}^{n}\left(\gamma^{2}\frac{v_{B,i}^{2}}{v_{A,i}}\wedge
v_{A,i}\right)-T_{B}\sum_{i=1}^{n}\frac{v_{A,i}}{v_{B,i}}\left(\gamma^{2}\frac{v_{B,i}^{2}}{v_{A,i}}\wedge
v_{A,i}\right)=0$

Any solution $\gamma^{*}$ to this equation readily yields a unique
$\lambda^{*}$ by plugging it into either (4) or (5); both equations will yield
the same solution by (6). In turn, the existence and efficient computation of
solutions $\gamma^{*}$ to (6) are ensured by the following proposition. The
bounds on $\gamma^{*}$ presented in the following proposition depend on the
distance between the vectors of battlefield values
$v_{A}:=(v_{A,1},\ldots,v_{A,n})$ and $v_{B}:=(v_{B,1},\ldots,v_{B,n})$.
Interestingly the natural measure of distance that emerges is the
$\chi^{2}$-divergence that commonly arises in information theory and
statistics; see e.g. (PW, 22). The $\chi^{2}$-divergence $\chi^{2}(u\|v)$
between two probability vectors $u=(u_{1},\ldots,u_{n})$ and
$v=(v_{1},\ldots,v_{n})$ is defined by

$\chi^{2}(u\|v)=\sum_{i=1}^{n}\frac{u_{i}^{2}}{v_{i}}-1=\sum_{i=1}^{n}\left(\frac{u_{i}}{v_{i}}-1\right)^{2}v_{i}\,.$

It is clear that $\chi^{2}(u\|v)\geq 0$ with equality if and only if $u=v$.

###### Proposition 1.

Equation (6) has the following properties:

  1. (1)

It always has at least one and at most $3n+3$ solutions $\gamma^{*}$.

  2. (2)

Any solution $\gamma^{*}$ satisfies

$\frac{T_{B}}{T_{A}}\frac{1}{1+\chi^{2}(v_{B}\|v_{A})}\leq\gamma^{*}\leq\frac{T_{B}}{T_{A}}(1+\chi^{2}(v_{A}\|v_{B}))$

  3. (3)

Computing all solutions can be done in $\mathcal{O}(n\log n)$ operations.

The proof is based on standard computations, hence postponed to Appendix B.2,
with the associated Algorithm 2.

###### Remark 2.

In case of symmetric values, that is when $v_{A,i}=v_{B,i}=v_{i}$, the game is
constant-sum and each player has a then unique111In the case of the Lotto
game, it is natural to call a strategy an equivalence class of strategies with
the same marginals. optimal strategy given by a unique pair
$(\gamma^{*},\lambda^{*})$ (KR, 21). In fact, in that case, the unique
$(\gamma^{*},\lambda^{*})$ can be computed analytically as
$\gamma^{*}=T_{B}/T_{A}$ and $\lambda^{*}=T_{B}/(2T_{A}^{2})$; this can be
easily seen from Proposition 1 (point 2.), since
$\chi^{2}(v_{A}\|v_{B})=\chi^{2}(v_{B}\|v_{A})=0$. With these parameters, the
optimal strategy of player $A$ is to choose $X_{A,i}$ uniformly at random on
$[0,2T_{A}v_{i}]$ and that of player $B$ is to forfeit each battlefield with
probability $1-\frac{T_{B}}{T_{A}}$ and, to choose $X_{B,i}$ uniformly at
random on $[0,2T_{A}v_{i}]$ on battlefield $i$ if not forfeited.

###  2.3. From Lotto to Blotto

In the previous section, we described how to compute solutions of a Lotto
game. To turn a strategy for the Lotto game into a strategy for the Blotto
game, one can _couple_ the marginal strategies of a Lotto game, effectively
turning the constraint (3) on the expected budget into the almost sure budget
constraint (2).

Stated otherwise, a solution to the associated Lotto game induces a solution
to the original Blotto game if the random variables $\\{X_{A,i}\\}_{i\in[n]}$
(and similarly $\\{X_{B,i}\\}_{i}$) are _jointly mixable_ (WW, 16).

###### Definition 3.

A family of $k$ random variables $Z_{1},\ldots,Z_{k}$ with finite expectations
is _jointly mixable_ if there exists a coupling $\pi$ such that if
$(Z_{1},\ldots,Z_{k})\sim\pi$,

$\sum_{i=1}^{k}Z_{i}=\sum_{i=1}^{k}\mathds{E}[Z_{i}],\quad\text{almost
surely.}$

In that case, the coupling $\pi$ is called a _joint mix_.

Obviously, not all random $k$-tuples variables are jointly mixable. Take for
example $Z_{1},Z_{2}$ and $Z_{3}$ to be Bernoulli with parameter $1/2$. Then
$\mathds{E}[Z_{1}]+\mathds{E}[Z_{2}]+\mathds{E}[Z_{3}]=3/2$ whereas there is
no coupling of the $Z_{i}$s such that their some equals a fractional number.

While the full characterization of jointly mixable distribution is a complex
question, some conditions, either sufficient or necessary, for joint
mixability have been derived. The following proposition is a simple extension
of a result of (WW, 16) (see also, (Zim, 20)) on the mixability of
distributions with monotone densities.

###### Proposition 4.

For $i=1,\ldots,k$, let $p_{i}\in[0,1]$, $b_{i}>0$ be fixed parameters and let
$Z_{i}$ be a random variable with distribution given by the following mixture:

(7) $Z_{i}\sim(1-p_{i})\delta_{0}+p_{i}{\sf Unif}\left[0,b_{i}\right]\,.$

Then $Z_{1},\ldots,Z_{k}$ are jointly mixable if and only if

(8) $\max_{1\leq i\leq k}b_{i}\leq\frac{1}{2}\sum_{i=1}^{k}p_{i}b_{i}$

This proposition is a consequence of few computations; its proof is delayed to
Section B.3.

We are now in a position to state the main result of this section: the
marginal distributions of the Lotto game described above are jointly mixable
into a solution to the Blotto game. To that end, we instantiate Proposition 4
to the parameters of the marginal distributions described in Section 2.2.

###### Theorem 5.

Let $\gamma^{*},\lambda^{*}$ be the parameters of Nash equilibrium of the
Lotto game described in Section (2.2). Then the marginal distributions can be
coupled into a Nash equilibrium for the corresponding Blotto game if and only
if

(9) $\max_{i\in[n]}(\gamma^{*}v_{B,i}\wedge v_{A,i})\leq\lambda^{*}T_{B}\,.$

Inequality (9) is simply an instantiation of (8), hence details are postponed
to Section B.3

Condition (9) of the previous theorem relies on the values
$\gamma^{*},\lambda^{*}$ that define the solution of the Lotto game. In light
of the bounds obtained in Proposition 1, these parameters may be eliminated to
produce a sufficient condition for the existence of said solution for Blotto
games with symmetric values. Recall that in this case, the game is constant-
sum so a solution is, in fact, an optimal strategy. This result is captured in
the following corollary which is a straightforward consequence of Theorem 5.

###### Corollary 6.

Assume symmetric values: $v_{A}=v_{B}=v$. Then the marginal distributions of
the optimal Lotto strategy described in Section 2.2 with
$\gamma^{*}=T_{B}/T_{A}$ and $\lambda^{*}=T_{B}/(2T_{A}^{2})$ can be coupled
into an optimal strategy for the corresponding Blotto game if and only if

$\max_{i\in[n]}v_{i}\leq\frac{T_{B}}{2T_{A}}\,.$

In fact a sufficient condition may be derived in the case of non-symmetric
values.

###### Corollary 7.

Assume that battlefield are balanced in the sense that there exits $r\in(0,1)$
such that

$\chi^{2}(v_{A}\|v_{B})\vee\chi^{2}(v_{B}\|v_{A})\leq r^{2}$

Then, the marginal distributions of the optimal Lotto strategy described in
Section 2.2 can be coupled into an optimal strategy for the corresponding
Blotto game as long as

$\max_{i\in[n]}v_{B,i}\leq\frac{T_{B}}{2T_{A}}(1-r)\,.$

The proof of this result is based solely on computations; it is postponed to
Section B.4

Note that the result of Corollary 7 is tight in the sense that if $r\to 0$ it
recovers the result of Corollary 6. It is unclear whether the dependence in
$r$ is sharp in our result and it is an interesting question to address in
future work.

Under rather general conditions, the above two corollaries show the
_existence_ of solutions with marginal distributions of the Lotto game derived
in (KR, 21). It remains to show that such a coupling may be realized
efficiently. This is done in the next section.

##  3\. An efficient algorithm to compute solutions

Deriving solutions, either optimal strategies in the constant-sum setting or
Nash equilibria, remains one of the major open problems surrounding the Blotto
game. Previous attempts at this task have focused on deriving an _explicit_
coupling between marginals. This is possible in specific cases. For example,
several explicit couplings between $n$ random variables $X_{i}\sim{\sf
Unif}[0,1],i=1,\ldots,n$ are known (KS, 06; RU, 02). In particular, this
provides a solution to some Blotto problems with sufficient symmetry. However,
this explicit approach fails for more general problems, and, in particular in
the important case of asymmetric budget such as the one covered in Corollary
6. In this paper, we take another route by describing the efficient Algorithm
Lotto2Blotto, whose pseudo-code is postponed to the Appendix B.1, that
computes an $\varepsilon$-approximate solution with time complexity which is
polynomial in $n$ and $1/\varepsilon$.

In light of the previous section, our goal is to find an algorithm that
efficiently computes a coupling between the marginal Lotto strategies
described above. This task faces two major hurdles.

On the one hand, the continuous nature of the marginals described above does
not lend itself to efficient algorithms which typically work with discrete
quantities. Instead, we propose to simply discretize the marginals at a scale
of order $\varepsilon>0$. In particular, this prevents us from replicating
exactly the marginals of the Lotto game but we can show that the error
employed in said discretization remains of the same order once propagated to
the utility of a given player.

On the other hand, the mere description of a coupling between $n$ discrete
marginals on $\mathcal{O}(1/\varepsilon)$ atoms is an object of size
$\mathcal{O}(1/\varepsilon^{n})$, which is exponential in the number $n$ of
battlefields. To overcome this limitation, we develop a careful scheme that
allows us to reduce the problem to the case of $4$ marginals instead of $n$.

Finally, we employ recent developments in computational optimal transport, to
couple our 4 marginals using a variant of Sinkhorn iterations (Sin, 64; SK,
67; Cut, 13).

###  3.1. Reductions

The typical size of a coupling with $n$ marginals is exponential in $n$. While
this issue is, in general, hopeless to overcome, we can exploit some of the
structure of the problem at hand. Indeed, a similar principle has been
recently employed in multi-marginal optimal transport to devise polynomial-
time algorithms under additional structure (ABA, 20). More specifically, we
reduce our problem to the case where there are only four marginals which
remain mixable if the original marginals are mixable.

This reduction is done in two steps. Recall that the marginals for the Lotto
game described in Section 2.2 are either uniform distributions or mixtures of
a uniform distribution with a Dirac point mass at zero. Our first step reduces
to the case where $n-1$ marginals are uniform and only one is a mixture as
above. In our second step, we further reduce to the case where there are three
uniform marginals and one mixture.

Throughout this section we focus on player $A$ for brevity. Reductions for
player $B$ are analogous.

####  3.1.1. Step 1: reduction to a single mixture

The marginal distributions described in Section 2.2 consist of
$|\mathcal{N}(\gamma^{*})|$ uniform distributions and
$n-|\mathcal{N}(\gamma^{*})|$ mixtures of a uniform distribution and a Dirac
point mass at 0 and our goal is to efficiently couple them into a joint mix
coupling $\pi$ that has these marginals and satisfies the Blotto budget
constraint. For clarity, we also regard uniform distributions as mixture
distributions albeit with weight zero on the point mass. Otherwise, we say
that a distribution is a _strict_ mixture. The goal of this first step is to
reduce this coupling problem to the case where there are $n-1$ uniform
distributions and one single strict mixture. To that end, we show that such a
coupling $\pi$ may be obtained as a mixture of $n$ joint mixes
$\pi_{k},k=1,\ldots,n$:

$\pi=\sum_{k=1}^{n}q_{k}\pi_{k}\,,\quad q_{k}\geq 0,\ \sum_{k}q_{k}=1$

where the marginal distributions of $\pi_{k}$ consist of at most one strict
mixture, the rest being uniform distributions. Moreover, this decomposition
can be computed efficiently as the solution of a simple greedy procedure.

###### Lemma 1.

Let $\gamma^{*},\lambda^{*}$ be the parameter of a solution for the Lotto game
and assume that the mixability condition (9) holds. Then, there exists a
family $\pi_{1},\ldots,\pi_{n}$ of couplings and a set of non negative weights
$q_{k}\geq 0,\sum_{k}q_{k}=1$ such that

  1. (1)

The marginal distributions of $(X_{A,1}^{k},\ldots,X_{A,n}^{k})\sim\pi_{k}$
are given by

$X_{A,i}^{k}\sim(1-p^{(k)}_{i})\delta_{0}+p^{(k)}_{i}{\sf
Unif}\left[0,\frac{v_{A,i}\wedge(\gamma^{*}v_{B,i})}{\lambda^{*}}\right]$

for some $p^{(k)}_{i}\in[0,1],i,k\in[n]$ with at most one $p^{(k)}_{i}$ in
$(0,1)$ for each $k$.

  2. (2)

Each coupling $\pi_{k},k=1,\ldots,n$ is a joint mix

  3. (3)

The mixture of couplings

(10) $\pi=\sum_{k=1}^{n}q_{k}\pi_{k}\,.$

is a solution for the Blotto game.

  4. (4)

The total complexity of computing the weights $q_{k},p^{(k)}_{i},i,k\in[n]$
scales as $\mathcal{O}\Big{(}n^{2}\log n\Big{)}$.

Note that the mixture of couplings $\pi$ in (10) is necessarily a joint mix as
a mixture of joint mixes. To sample from it, Player $A$, simply samples
$\pi_{k}$ with probability $q_{k}$ and plays according to the strategy
prescribed by it.

The geometric proof of this lemma is delayed to Section B.5, along with the
pseudo-code of associated Algorithm Decomp.

###### Lemma 2.

Fix $\ell\in\mathbb{R}_{+}^{n}$, $T\in\mathbb{R}$ and let
$\mathcal{H}=\\{x\in\mathbb{R}^{n}\ \text{s.t.}\ \langle\ell,x\rangle=T\\}$ be
an affine hyperplane. For any point
$x\in\mathcal{C}_{n}=\mathcal{H}\cap[0,1]^{n}$, define ${\rm
supp}(x):=\\{i\in[n],x_{i}\in(0,1)\\}$; then there exist $\theta\in[0,1]$, an
extreme point $y\in\mathcal{C}_{n}$ and another vector
$\bar{y}\in\mathcal{C}_{n}$ satisfying ${\rm supp}(\bar{y})\varsubsetneq{\rm
supp}(x)$ (in particular, $\bar{y}$ belongs to some $m$-face of
$\mathcal{C}_{n}$ where $m=|{\rm supp}(\bar{y})|<|{\rm supp}(x)|$) such that

$x=\theta y+(1-\theta)\bar{y}\ .$

The overall complexity of computing $y,\bar{y}$ and $\theta$ is of order
$\mathcal{O}(n\log n)$.

The proof of this Lemma is based on simple geometric arguments, and is
postponed to Section B.6 with the associated pseudo-code of Algorithm
Extremize.

####  3.1.2. Step 2. Reduction to four random variables

The previous step reduces the joint mixability problem of $n$ general
mixtures, to a simpler one where at most one strict mixture is involved.
Still, computing—in fact even describing—a coupling of $n$ variables requires
generically exponential (in $n$) time and memory. To overcome this limitation,
we reduce the number of random variables from $n$ to a constant number.

The following Lemma states that each $\pi_{k}$ can be realized as the coupling
of 3 new uniform random variables and a strict mixture, thus reducing the
mixability question from $n$ to only $4$ random variables. A careful
inspection of the proof of Lemma 3 below indicates that the reduction may lead
to three marginals rather than four. In that case, two marginals are uniform
and one is a strict mixture. To handle this case, some adjustments are needed;
in particular—and obvisouly—with the size of the resulting coupling. However,
extensions from four to three marginals are straightforward and we omit this
case for clarity.

###### Lemma 3.

Fix $n\geq 4$, $k\in[n]$, and assume without loss of generality that the last
marginal of the coupling $\pi_{k}$ from Lemma 1 is a strict mixture. Then
$(X_{A,1},\ldots,X_{A,n})\sim\pi_{k}$ may be constructed from three uniform
random variables $Y_{1},Y_{2},Y_{3}$ and a partition
$\mathcal{I}_{0}\sqcup\mathcal{I}_{1}\sqcup\mathcal{I}_{2}\sqcup\mathcal{I}_{3}=[n-1]$
as follows. Set $X_{A,i}=0$ for all $i\in\mathcal{I}_{0}$, and

$X_{A,i}=\theta_{i}Y_{j}\,,\qquad i\in\mathcal{I}_{j},\quad
j\in\\{1,2,3\\}\,,$

where $\theta_{1},\ldots,\theta_{n-1}\in[0,1]$ are such that

$\sum_{i\in\mathcal{I}_{j}}\theta_{i}=1,\quad j=1,2,3\,.$

In particular, it holds that

$\sum_{i=1}^{n-1}X_{A,i}=Y_{1}+Y_{2}+Y_{3}\quad\text{almost surely,}$

and $(Y_{1},Y_{2},Y_{3},X_{A,n})$ are jointly mixable. The support of $Y_{j}$
is $[0,b^{*}_{j}]$ where

$b^{*}_{j}=\sum_{i\in\mathcal{I}_{j}}\frac{\gamma^{*}v_{B,i}}{\lambda^{*}}\wedge\frac{v_{A,i}}{\lambda^{*}}$

Moreover, the $\theta_{i}$’s, the sets $\mathcal{I}_{j}$, and the parameters
of the distributions of $Y_{1},Y_{2},Y_{3}$ can each be computed in constant
time.

The proof of this Lemma, based on standard mixability arguments, is postponed
to Section B.7, with the pseudo-code of the corresponding Algorithm Reduc.

Note that any joint mix of $(Y_{1},Y_{2},Y_{3},X_{A,n})$ readily yields a
joint mix of $(X_{A,1},\ldots,X_{A,n})$ by defining
$X_{A,i}=\theta_{i}Y_{j(i)}$, where $j(i)\in[3]$ is the unique integer such
that $i\in\mathcal{I}_{j(i)}$.

###  3.2. Discretization

The problem of finding a solution for the Blotto game has been reduced to the
construction of a coupling of (at most) four random variables, three of them
being uniform over some intervals and the fourth one being a mixture between a
Dirac mass at zero and some uniform distribution. Throughout this section we
denote these random variables as $Y_{1},\ldots,Y_{4}$ for simplicity; in the
notation of the previous section, they correspond to $Y_{1},Y_{2},Y_{3}$, and
$X_{A,n}$ respectively.

Unfortunately, even in this simple case, finding explicit, closed-form,
couplings appears to be possible only under stringent additional conditions
that limit the scope of the Blotto game. To overcome this limitation, we take
an algorithmic approach, describing an efficient way to find an approximate
solution. To that end, we obviously need to work with discrete random
variables and describe here a coupling between these discretized random
variables.

Let $(Y_{1},Y_{2},Y_{3},Y_{4})\sim\varpi$ be jointly mixed so that

(11) $Y_{1}+Y_{2}+Y_{3}+Y_{4}=T_{A}\,.$

Moreover, let $h>0$ be some (small) discretization parameter. Define the
quantized random variables $\tilde{Y}_{i}$ by

(12) $\tilde{Y}_{i}=\left\lfloor\frac{Y_{i}}{h}\right\rfloor,\
i=1,2,3\,,\qquad\tilde{Y}_{4}=\frac{T_{A}}{h}-\left\lfloor\frac{T_{A}-Y_{4}}{h}\right\rfloor\,.$

Our goal is to compute any of the joint distributions $\mathsf{D}(\varpi)$ of
the vector
$\tilde{Y}=(\tilde{Y}_{1},\tilde{Y}_{2},\tilde{Y}_{3},\tilde{Y}_{4})$ when
$\varpi$ ranges over joint mixes.

As a first step towards this goal, note that these discretized random
variables need not be jointly mixable. Indeed, in general we have
$\tilde{Y}_{1}+\tilde{Y}_{2}+\tilde{Y}_{3}\leq\lfloor(Y_{1}+Y_{2}+Y_{3})/h\rfloor$
but equality may fail to hold because of discretization errors. To account for
these, let $\varepsilon\in\\{0,1,2\\}$ be defined as

(13)
$\varepsilon=(T_{A}/h-\tilde{Y}_{4})-(\tilde{Y}_{1}+\tilde{Y}_{2}+\tilde{Y}_{3})\,,$

and consider the augmented random vector
$\tilde{Y}_{+}=(\tilde{X},\varepsilon)$. In light of (13),
$\tilde{Y}_{+}\in\mathds{R}^{5}$ lives almost surely on a four dimensional
subspace. As such, its distribution may be represented by a 4-tensor
$(\Gamma_{ijke})$ with entries given by

$\Gamma_{ijke}=\mathds{P}(\tilde{Y}_{1}=i,\tilde{Y}_{2}=j,\tilde{Y}_{3}=k,\varepsilon=e)\,.$

In particular, note that $e\in\\{0,1,2\\}$ while $i,j,k$ each range in a set
of integers of size $\Theta(1/h)$. Using (13) we can read off the distribution
of $\tilde{Y}_{4}$ from this tensor.

This tensor is subject to four sets of linear constraints, one for each of the
marginal constraints given in (12). They are given by

$\sum_{jke}\Gamma_{ijke}=\mathds{P}(\tilde{Y}_{1}=i)\ \forall
i\,,\quad\sum_{ike}\Gamma_{ijke}=\mathds{P}(\tilde{Y}_{2}=j)\ \forall
j\,,\quad\sum_{ije}\Gamma_{ijke}=\mathds{P}(\tilde{Y}_{3}=k)\ \forall k\,,$

and, in light of (13), by

$\sum_{i+j+k+e=\ell}\Gamma_{ijke}=\mathds{P}(T_{A}/h-\tilde{Y}_{4}=\ell)\
\forall\ell\,.$

Note that indeed, any draw from a distribution that satisfies the above
constraints yields a random vector
$(\tilde{Y}_{1},\tilde{Y}_{2},\tilde{Y}_{3},\varepsilon)$. Defining
$\tilde{Y}_{4}$ by solving (13) yields a vector $\tilde{Y}\sim{\sf D}(\varpi)$
for some joint mix $\varpi$ defined as above. In other words, $\tilde{Y}$ is
indeed the discretization of random variables drawn from a joint mix (though
it need not be jointly mixable itself).

Since the random variables $Y_{j}$, for $j\in[3]$, constructed at the previous
step have a support equal to $[0,b^{*}_{j}]$ where
$b^{*}_{j}=\sum_{i\in\mathcal{I}_{j}}\frac{\gamma^{*}v_{B,i}}{\lambda^{*}}\wedge\frac{v_{A,i}}{\lambda^{*}}$,
the reduced (to 4 random variables) and discretized problem reduces to finding
some tensor $(\Gamma_{ijke})$ with
$3\cdot\left\lfloor\frac{b^{*}_{1}}{h}+1\right\rfloor\cdot\left\lfloor\frac{b^{*}_{2}}{h}+1\right\rfloor\cdot\left\lfloor\frac{b^{*}_{3}}{h}+1\right\rfloor$
entries satisfying at most $4\cdot\left\lfloor\frac{\max
b^{*}_{j}}{h}+1\right\rfloor$ linear constraints. Although this can be done
simply via linear programming (hence polynomially in $h^{-1}$, more precisely
in $\tilde{\mathcal{O}}(1/h^{8,5})$ with Vaidya’s algorithm), a quite
efficient and more popular way is to use a variant of Sinkhorn-Knopp algorithm
that quickly finds approximated solutions. This is more relevant as this
linear program is already some approximation of the original problem, hence
there is no point of solving it exactly.

The pseudo-code of the Algorithm Discretize can be found in Section B.8

###  3.3. Tensor scaling using Sinkhorn iterations

In light of the previous sections, we have reduced our problem to that of
finding coupling in the form of a 4-tensor
$(\Gamma_{ijke},i\in[d_{1}],j\in[d_{2}],k\in[d_{3}],e\in\\{0,1,2\\})$ with
non-negative entries subject to marginal constraints. We approach this problem
from a computational perspective and propose and algorithm that converges
rapidly to a feasible solution. To describe this algorithm, recall that its
input are four probability vectors
$\tilde{\mu}_{j}\in\mathds{R}^{d_{j}},j=1,\dots,4$, with
$d_{4}=d_{1}+d_{2}+d_{3}+2$ that represent the probability mass functions of
the discretized random variable
$\tilde{Y}_{1},\tilde{Y}_{2},\tilde{Y}_{3},T_{A}/h-\tilde{Y}_{4}$ defined in
the previous section:
$\tilde{\mu}_{j,\boldsymbol{\cdot}}=\mathds{P}(\tilde{Y}_{j}=\boldsymbol{\cdot})$,
$j=1,\ldots,3$,
$\tilde{\mu}_{4,\boldsymbol{\cdot}}=\mathds{P}(T_{A}/h-\tilde{Y}_{j}=\boldsymbol{\cdot})$.

The linear constraints take the form

(14) $\displaystyle\bar{\Gamma}_{i}^{(1)}$
$\displaystyle:=\sum_{jke}\Gamma_{ijke}=\tilde{\mu}_{1,i}\ $
$\displaystyle\forall i\in[d_{1}]\,,$ (15)
$\displaystyle\bar{\Gamma}_{j}^{(2)}$
$\displaystyle:=\sum_{ike}\Gamma_{ijke}=\tilde{\mu}_{2,j}\ $
$\displaystyle\forall j\in[d_{2}]\,,$ (16)
$\displaystyle\bar{\Gamma}_{k}^{(3)}$
$\displaystyle:=\sum_{ije}\Gamma_{ijke}=\tilde{\mu}_{3,k}\ $
$\displaystyle\forall k\in[d_{3}]\,,$ (17)
$\displaystyle\bar{\Gamma}_{\ell}^{(4)}$
$\displaystyle:=\sum_{i+j+k+e=\ell}\Gamma_{ijke}=\tilde{\mu}_{4,\ell}\ $
$\displaystyle\forall\ell\in[d_{4}]\,.$

Denote by $\mathcal{G}$ the set of tensors $\Gamma=(\Gamma_{ijke})$ that
satisfy these constraints.

To solve this problem, we propose to project the all-ones tensor ${\bf 1}$
onto $\mathcal{G}$ using the Kullback-Leibler (KL) divergence. Recall that the
KL divergence between two nonnegative tensors $\Gamma,\Gamma^{\prime}$ is
given by

$\operatorname{\mathsf{KL}}(\Gamma\|\Gamma^{\prime})=\sum_{ijke}\Gamma_{ijke}\log\left(\frac{\Gamma_{ijke}}{\Gamma^{\prime}_{ijke}}\right)$

In particular, ${\sf KL}(\Gamma\|{\bf 1})$ is simply the (negative) entropy
$\mathsf{H}(\Gamma)$ of $\Gamma$ and we aim to solve the convex optimization
problem

$\min_{\Gamma\in\mathcal{G}}\mathsf{H}(\Gamma)=\sum_{ijke}\Gamma_{ijke}\log\left(\Gamma_{ijke}\right)\,.$

While many algorithms are available to solve this problem (Bub, 15), its
specific structure can be exploited efficiently. Indeed, first order
optimality conditions imply that any optimal $\Gamma$ must be of the form

(18)
$\Gamma_{ijke}=\xi_{1,i}\cdot\xi_{2,j}\cdot\xi_{3,k}\cdot\xi_{4,i+j+k+e}\,,$

for some scaling vectors $\xi_{j}\in(0,\infty)^{d_{j}},j=1,\dots,4$. This
representation readily calls for an iterative tensor scaling algorithm similar
to the Sinkhorn algorithm (Sin, 64; SK, 67; Cut, 13). Tensor scaling has been
investigated in more classical setups (LHCJ, 20; ABA, 20) that slightly differ
from the present setup because the fourth marginal constraint takes a special
form. Nevertheless, the implementation of Algorithm Sinkhorn remains
straightforward and is presented in Section B.9. Its analysis is also a
straightforward extension of that for the traditional matrix case (AWR, 17).
More specifically, following the exact same lines as the one of Theorem 4.3 in
(LHCJ, 20), we readily get the following result.

###### Proposition 4.

Define

$\tilde{\mu}_{\min}=\min_{i\in[4],j,\tilde{\mu}_{i,j}\neq
0}\tilde{\mu}_{i,j}\,.$

Algorithm Sinkhorn terminates and returns a tensor ${\Gamma}$ such that
$\sum_{i=1}^{4}\|\bar{\Gamma}^{(i)}-\tilde{\mu}_{i}\|_{1}\leq\eta$ after at
most $32\eta^{-1}(1-\log\tilde{\mu}_{\min})$ iterations. Moreover, each
marginal $\bar{\Gamma}^{(i)}$ of $\Gamma$ has positive entries that sum to one
and hence is a probability vector.

What have we accomplished so far? Through several reductions and a tensor
scaling algorithm, given the datum of a Blotto game, we are able to compute a
joint distribution that corresponds to an approximate solution. In Section 4,
we evaluate the accuracy of this approximation in terms of the value of the
game by showing that the various approximations (discretization and numerical
precision of the algorithm) do not blow up when propagated back into the
reductions. Before that, we investigate an important operational question: how
to sample a strategy from the resulting coupling $\Gamma$.

###  3.4. From coupling to sampling

Finding an efficient construction of (approximate) equilibria or optimal
strategies is only relevant if it can be associated to some efficient sampling
method so that a player may query a sampler and receive the allocation
$(X_{A,1},\ldots,X_{A,n})$ that they should play on each battlefield. In light
of the various reduction steps employed above, it is sufficient to sample a
4-tuple

$(\tilde{Y}_{1},\tilde{Y}_{2},\tilde{Y}_{3},\varepsilon)\in[0,b^{*}_{1}/h]\times[0,b^{*}_{2}/h]\times[0,b^{*}_{3}/h]\times\\{0,1,2\\}$

from the output $\Gamma$ of Algorithm Sinkhorn. Indeed, from
$(\tilde{Y}_{1},\tilde{Y}_{2},\tilde{Y}_{3},\varepsilon)$, we obtain the
random variables $Y_{i},i=1,\dots,4$ that are approximately distributed from
the joint mix $\varpi$ as follows.

To ensure that the marginal distributions are continuous, let $U\sim{\sf
Unif}[0,1]$ and define

$\displaystyle
Y_{1}^{\prime}=(\tilde{Y}_{1}+\frac{\varepsilon}{3}+\frac{U}{3})h\wedge
b^{*}_{1},\quad
Y_{2}^{\prime}=(\tilde{Y}_{2}+\frac{\varepsilon}{3}+\frac{U}{3})h\wedge
b^{*}_{2},\quad
Y_{3}^{\prime}=(\tilde{Y}_{3}+\frac{\varepsilon}{3}+\frac{U}{3})h\wedge
b^{*}_{3}.$

To correct for potential boundary effects, define
$S=Y_{1}^{\prime}+Y_{2}^{\prime}+Y_{3}^{\prime}$ and

$\zeta=\mathds{1}\\{S>T_{A}\\}\frac{T_{A}-S}{3}+\mathds{1}\\{S<T_{A}-b^{*}_{4}\\}\frac{T_{A}-b^{*}_{4}-S}{3}.$

Then take $\bar{Y}_{1}=Y_{1}^{\prime}+\zeta$,
$\bar{Y}_{2}=Y_{2}^{\prime}+\zeta$, $\bar{Y}_{3}=Y_{3}^{\prime}+\zeta$, and
$\bar{Y}_{4}=T_{A}-(Y_{1}+Y_{2}+Y_{3})$.

We call this procedure the _smoothing_ procedure. Finally, as mentioned
before, just define $X_{A,i}=\theta_{i}\bar{Y}_{j(i)}$, where $j(i)\in[3]$ is
the unique integer such that $i\in\mathcal{I}_{j(i)}$.

Note that the random variable $U\sim{\sf Unif}[0,1]$ is superfluous and
theoretical results would follow by taking $U=0$. Its role is simply to
ensure, for cosmetic reasons, that the random marginal distributions are
continuous apart from the potential point mass at zero.

It remains to sample $(\tilde{Y}_{1},\tilde{Y}_{2},\tilde{Y}_{3},\varepsilon)$
from the output $\Gamma$ of Algorithm Sinkhorn. This is quite straightforward
in light of the factored form of $\Gamma$. Indeed, recall that the coupling
output by Algorithm Sinkhorn has the form (18).

$\Gamma_{ijke}=\xi_{1,i}\cdot\xi_{2,j}\cdot\xi_{3,k}\cdot\xi_{4,i+j+k+e}\,,\
\forall i\in[d_{1}],j\in d_{2},k\in[d_{3}],e\in\\{0,1,2\\}$

As a consequence, we can draw from $\Gamma$ as follows:

  1. (1)

Set $\tilde{Y}_{1}=i\in[d_{1}]$ with probability proportional to $\xi_{1,i}$

  2. (2)

Set $\tilde{Y}_{2}=j\in[d_{2}]$ with probability proportional to $\xi_{2,j}$

  3. (3)

Set $\tilde{Y}_{3}=k\in[d_{3}]$ with probability proportional to $\xi_{3,k}$

  4. (4)

Conditionally on $(\tilde{Y}_{1},\tilde{Y}_{2},\tilde{Y}_{3})$, set
$\varepsilon=e\in\\{0,1,2\\}$ with probability proportional to
$\xi_{4,\tilde{Y}_{1}+\tilde{Y}_{2}+\tilde{Y}_{3}+e.}$

The pseudo-code of Algorithm Sample can be found in Section B.10.

##  4\. Approximation errors and computational complexity

The construction of the previous section relies on various approximations,
each of them inducing some error that can be mitigated at the cost of
additional computational complexity by tuning the discretization parameter $h$
of Section 3.2 and the tolerance parameter $\eta$ in Algorithm Sinkhorn. In
this section we study the computational complexity required to reach an
$\varepsilon$-approximate solution.

###  4.1. From approximate strategies to approximate solutions

Note that the very notion of “approximate solution” strongly depends on
whether the problem is value-symmetric ($v_{A,i}=v_{B,i}$ for all $i$) or
-asymmetric ($v_{A,i}\neq v_{B,i}$ for some $i$). Indeed, in the former case,
the game is constant-sum and optimal strategies do exist. This is no longer
true in the latter case where only Nash equilibria are considered. As a
consequence, we can consider approximation of a single optimal strategies in
value-symmetric games, while we will have to consider approximations of a pair
of equilibrium strategies in value-asymmetric ones. In the following two
sections, we consider each case separately. In the remaining, we shall focus
the analysis on Player $A$, but it is almost identical for player $B$; hence
we do not repeat it for the sake of clarity.

####  4.1.1. The value-symmetric case

A value-symmetric Blotto game, where $v_{A,i}=v_{B,i}=v_{i}$ for all $i$ is
constant-sum and optimal strategies exist for each player. In particular, this
allows us to provide strong approximation guarantees by controlling how sub-
optimal the expected utility of a player is.

To check this well-known fact on our specific instance, consider the utility
of player $A$. Set two equilibrium parameters $\gamma^{*}=T_{B}/T_{A}\leq 1$
and $\lambda^{*}=T_{B}/(2T_{A}^{2})$ (see Corollary 6) defining an optimal
strategy and observe that $\mathcal{N}(\gamma^{*})=[n]$ since $\gamma^{*}\leq
1$. For $i\in[n]$, let $X_{A,i}\sim{\sf Unif}[0,2T_{A}v_{i}]$ denote the
amount allocated by player $A$ to battlefield $i$ according to this optimal
strategy and denote by $F_{A,i}$ its cumulative distribution function (cdf).
The expected utility (a.k.a. reward) of player $A$ if player $B$ chooses
allocation $x_{B}=(x_{B,i})_{i}$ depends only on the sequence
$F_{A}=(F_{A,1},\dots,F_{A,n})$ of marginal cdfs rather than the whole
coupling. It is given by

$\displaystyle\mathcal{U}_{A}(F_{A},x_{B})=\sum_{i=1}^{n}v_{A,i}\mathds{P}(X_{A,i}>x_{B,i})=\sum_{i=1}^{n}v_{i}\big{(}1-F_{A,i}(x_{B,i})\big{)}=1-\sum_{i=1}^{n}v_{i}\wedge\frac{x_{B,i}}{2T_{A}}\geq
1-\frac{T_{B}}{2T_{A}}\,.$

where we used the fact that the $v_{i}$’s sum to 1 and the $x_{B,i}$’s sum to
at most $T_{B}$. Moreover, if $B$ employs the mixed strategy
$X_{B,1},\ldots,X_{B,n}$ described in Corollary 6, the utility of player $A$,
denoted $\mathcal{U}_{A}(F_{A},F_{B})$, changes as follows. Let
$U_{A,i},U_{B,i}\sim{\sf Unif}[0,2T_{A}v_{i}]$ be a sequence of uniform random
variables such that $U_{A,i}$ is independent of $U_{B,i}$. In particular,
$\mathds{P}(U_{A,i}>U_{B,i})=.5$ and

$\displaystyle\mathcal{U}_{A}(F_{A},F_{B})$
$\displaystyle=\big{(}1-\frac{T_{B}}{T_{A}}\big{)}\sum_{i=1}^{n}v_{i}\big{(}1-F_{A,i}(0)\big{)}+\frac{T_{B}}{T_{A}}\sum_{i=1}^{n}v_{i}\mathds{P}(U_{A,i}>U_{B,i})$
$\displaystyle=\big{(}1-\frac{T_{B}}{T_{A}}\big{)}+\frac{T_{B}}{2T_{A}}=1-\frac{T_{B}}{2T_{A}}\,.$

In particular, the strategy of player $A$ given in Corollary 6 is optimal and
its optimal utility is given by $1-T_{B}/(2T_{A})$.

To estimate the cost of the various approximations incurred by player $A$, let
$X_{A,i}^{h,\eta}\sim P_{A,i}^{h,\eta}$ denote the strategy on battlefield
$i\in[n]$. The notation is meant to emphasize that the approximation error
stems from two sources: the precision level $\eta$ of Algorithm Sinkhorn and
the grid size $h$ of discretization procedure in Section 3.2. In particular,
we write $P_{A,i}^{0,0}:=P_{A,i}$. Cognizant of this approximation error,
player $A$ may take advantage of the suboptimality of the strategy of player
$A$ and respond with best-response strategy denoted
$X_{B}^{h,\eta}=(X_{B,1}^{h,\eta},\ldots,X_{B,n}^{h,\eta})$. As a result, the
suboptimality gap of player $A$’s expected utility is controlled as follows

$\displaystyle\mathcal{U}_{A}(F_{A},F_{B})-\mathcal{U}_{A}(F_{A}^{h,\eta},F_{B}^{h,\eta})$
$\displaystyle=\sum_{i=1}^{n}v_{i}\mathds{P}(X_{A,i}>X_{B,i})-\sum_{i=1}^{n}v_{i}\mathds{P}(X_{A,i}^{h,\eta}>X_{B,i}^{h,\eta})$
$\displaystyle\leq\sum_{i=1}^{n}v_{i}\mathds{P}(X_{A,i}>X_{B,i}^{h,\eta})-\sum_{i=1}^{n}v_{i}\mathds{P}(X_{A,i}^{h,\eta}>X_{B,i}^{h,\eta})$
$\displaystyle\leq\sum_{i=1}^{n}v_{i}\sup_{x>0}\left[\mathds{P}(X_{A,i}>x)-\mathds{P}(X_{A,i}^{h,\eta}>x)\right]$

where in the first inequality, we use the fact that $X_{B}$ is an optimal
response for $B$ when $A$ plays $X_{A}$.

It will be convenient in the sequel to further bound the above quantity using
the $\infty$-Wasserstein distance—see (San, 15, Section 5.5.1)—between
$P_{A,i}$ and $P_{A,i}^{h,\eta}$, denoted
$W_{\infty}(P_{A,i},P_{A,i}^{h,\eta})$. Indeed, to show that
$W_{\infty}(P_{A,i},P_{A,i}^{h,\eta})\leq\omega$ for some $\omega\geq 0$, it
is sufficient to exhibit a coupling of $X_{A,i},X_{A,i}^{h,\eta}$ such that
$|X_{A,i}-X_{A,i}^{h,\eta}|<\omega$ almost surely. Below, we often do so
implicitly as such couplings are, in all instances, trivial.

Fix $\omega>0$ and assume $W_{\infty}(P_{A,i},P_{A,i}^{h,\eta})\leq\omega$.
Then for any $\omega\geq 0$, we have

$\mathds{P}(X_{A,i}>x)-\mathds{P}(X_{A,i}^{h,\eta}>x)\leq\mathds{P}(x<X_{A,i}<x+\omega)\leq\frac{\lambda^{*}\omega}{\gamma^{*}v_{i}}\,,$

where we used the fact that $X_{A,i}\sim{\sf
Unif}[0,\gamma^{*}v_{i}/\lambda^{*}]$. The above two displays together yield
that the suboptimality gap for player $A$ is controlled as

$\mathcal{U}_{A}(F_{A},F_{B})-\mathcal{U}_{A}(F_{A}^{h,\eta},F_{B}^{h,\eta})\leq\frac{\lambda^{*}}{\gamma^{*}}\sum_{i=1}^{n}W_{\infty}(P_{A,i},P_{A,i}^{h,\eta})\,.$

Recall that Step 1 in the reduction consists in decomposing $P_{A,i}$ as a
mixture of (at most) $n$ other distributions, i.e.,
$P_{A,i}=\sum_{k}q_{k}P_{A,i}^{(k)}$. Accordingly, we also have constructed
$P_{A,i}^{h,\eta}$ as a mixture
$P_{A,i}^{h,\eta}=\sum_{k}q_{k}P_{A,i}^{h,\eta,(k)}$. It follows readily from
the definition of $W_{\infty}$ that that

$W_{\infty}(P_{A,i},P_{A,i}^{h,\eta})\leq\sum_{k}q_{k}W_{\infty}(P_{A,i}^{(k)},P_{A,i}^{h,\eta,(k)}).$

In particular controlling each term on the right-hand side uniformly in $k$
results in the same control on the desired error. Therefore, without loss of
generality, we may assume that $P^{(k)}_{A,i}=P_{A,i}$ and
$P^{h,\eta,(k)}_{A,i}=P^{h,\eta}_{A,i}$ so as to keep the notation light.
Moreover, as above, we assume without loss of generality the last marginal
$P_{A,n}$ is the only strict mixture.

####  4.1.2. The value-asymmetric case

When values are asymmetric, the game is no longer constant-sum and we shift
our focus from optimal strategies to Nash equilibria. In this context the
notion of approximation is more subtle and has to be carried out jointly for
both players.

For any set of marginal cdfs $G_{A}=(G_{A,1},\ldots,G_{A,n})$ and
$G_{B}=(G_{B,1},\ldots,G_{B,n})$, denote by $\mathcal{U}_{A}(G_{A},G_{B})$ the
expected utility of player $A$ if player $A$ plays according to strategy
$G_{A}$ while player $B$ plays according to strategy $B$.

A pair $(F_{A},F_{B})$ is a Nash equilibrium if

$\mathcal{U}_{A}(F_{A},F_{B})\geq\mathcal{U}_{A}(G_{A},F_{B}),\text{ for all
admissible}\ G_{A}\,.$

Writing

$\displaystyle\mathcal{U}_{A}(F_{A},F_{B})$
$\displaystyle=\mathcal{U}_{A}(F_{A},F_{B})-\mathcal{U}_{A}(F_{A}^{h,\eta},F_{B})+\mathcal{U}_{A}(F_{A}^{h,\eta},F_{B})-\mathcal{U}_{A}(F_{A}^{h,\eta},F_{B}^{h,\eta})+\mathcal{U}_{A}(F_{A}^{h,\eta},F_{B}^{h,\eta})\,,$
$\displaystyle\mathcal{U}_{A}(G_{A},F_{B})$
$\displaystyle=\mathcal{U}_{A}(G_{A},F_{B})-\mathcal{U}_{A}(G_{A},F_{B}^{h,\eta})+\mathcal{U}_{A}(G_{A},F_{B}^{h,\eta})$

it readily follows from the above two displays that

$\mathcal{U}_{A}(F_{A}^{h,\eta},F_{B}^{h,\eta})+\varepsilon\geq\mathcal{U}_{A}(G_{A},F_{B}^{h,\eta}),\text{
for all admissible}\ G_{A}\,,$

where, using similar computations as above,

$\varepsilon\leq\sum_{i=1}^{n}v_{A,i}\left[\frac{\lambda^{*}}{\gamma^{*}v_{B,i}}W_{\infty}(P_{A,i},P_{A,i}^{h,\eta})+\frac{2\lambda^{*}}{v_{A,i}}W_{\infty}(P_{B,i},P_{B,i}^{h,\eta})\right]$

###  4.2. Control of the errors

In both cases, symmetric or asymmetric values, a control of the approximation
error follows from controlling $W_{\infty}(P_{A,i},P_{A,i}^{h,\eta})$. In the
rest of this section, we sightly abuse notation and write $W_{\infty}(X,Y)$
when the distributions of the random variables $X$ and $Y$ are clear from the
context.

Recall that for any $i\in[n]$ since $X_{A,i}=\theta_{i}Y_{k(i)}$ and similarly
for the approximate versions, for some fixed $\theta_{i}\in[0,1]$, we have for
any $h,\eta\geq 0$ that

$W_{\infty}(P_{A,i},P_{A,i}^{h,\eta})=\theta_{i}W_{\infty}(Y_{j(i)},\bar{Y}_{j(i)})$

where $Y_{j}$ is the result of the reductions and is defined in Lemma 3 while
$\bar{Y}_{j}$ is the output the smoothing procedure and is defined in Section
3.4.

Recall that the discrepancy between $\bar{Y}_{j}$ and the target $Y_{j}$ stems
from three approximations: discretization error ($h>0$), numerical error
($\eta>0$), and the error due to smoothing step. The error coming from the
smoothing step is easy to control: for any $j\in[4]$, we have
$W_{\infty}(Y_{j},\bar{Y}_{j})\leq W_{\infty}(Y_{j},h\tilde{Y}_{j})+h$. We
have proved that

(19)
$W_{\infty}(P_{A,i},P_{A,i}^{h,\eta})\leq\theta_{i}W_{\infty}(Y_{j(i)},h\tilde{Y}_{j(i)})+\theta_{i}h$

As a result, it is sufficient to control the discretization error and the
numerical error at the level of the variables $\tilde{Y}_{j}$. To emphasize
the presence of these errors, we employ the same notation as for
$P_{A,i}^{h,\eta}$ and write $\tilde{Y}_{j}=\tilde{Y}_{j}^{h,\eta}$ for $h>0$,
$\eta\geq 0$. By the triangle inequality, we have

$W_{\infty}(Y_{j},h\tilde{Y}_{j})\leq\underbrace{W_{\infty}(Y_{j},h\tilde{Y}_{j}^{h,0})}_{\text{discretization
error}}+\underbrace{W_{\infty}(h\tilde{Y}_{j}^{h,0},h\tilde{Y}_{j}^{h,\eta})}_{\text{numerical
error}}\,.$

The discretization error is trivial to control. Indeed, in light of the
coupling provided by (12), we get that

(20) $W_{\infty}(Y_{j},h\tilde{Y}_{j}^{h,0})\leq h$

Finally, to control the numerical error
$W_{\infty}(h\tilde{Y}_{j}^{h,0},h\tilde{Y}_{j}^{h,\eta})$, recall that the
tolerance $\eta>0$ in Algorithm Sinkhorn controls the $\ell_{1}$ error between
the current marginals and the targets. Hence, we need to bound the
$\infty$-Wasserstein distance by the $\ell_{1}$ distance. This is quite
straightforward since $\tilde{Y}_{j}^{h,\eta}$ has bounded support for
$\eta\geq 0$. Indeed, recall from Lemma 3 that for any $j\in[4]$ we have that
$\tilde{Y}_{j}^{h,\eta}\in[0,b_{j}^{*}/h]$, where

$b_{j}^{*}=\frac{1}{\lambda^{*}}\sum_{i\in\mathcal{I}_{j}}(\gamma^{*}v_{B,i})\wedge
v_{A,i}\,.$

Hence, $W_{\infty}(h\tilde{Y}_{j}^{h,0},h\tilde{Y}_{j}^{h,\eta})\leq
b_{j}^{*}\eta$, and we have proved that

$W_{\infty}(P_{A,i},P_{A,i}^{h,\eta})\leq
2\theta_{i}h+\theta_{i}b_{k(i)}^{*}\eta\,.$

In particular, for the value-symmetric case, since

$b_{k(i)}=\frac{\gamma^{*}}{\lambda^{*}}\sum_{l\in\mathcal{I}_{k(i)}}v_{l}\leq\frac{\gamma^{*}}{\lambda^{*}}\,,$

we get the following simple bound

$W_{\infty}(P_{A,i},P_{A,i}^{h,\eta})\leq
2\theta_{i}h+\frac{\theta_{i}\gamma^{*}\eta}{\lambda^{*}}\,.$

Since $\sum_{i}\theta_{i}=4$, the suboptimality gap for player $A$ is
controlled as

(21)
$\mathcal{U}_{A}(F_{A})-\mathcal{U}_{A}(F_{A}^{h,\eta})\leq\frac{\lambda^{*}}{\gamma^{*}}\sum_{i=1}^{n}W_{\infty}(P_{A,i},P_{A,i}^{h,\eta})\leq
8\frac{\lambda^{*}}{\gamma^{*}}h+4\eta\,.$

In the value-asymmetric case, we get a suboptimality for player $A$ smaller
than

(22)
$\varepsilon_{A}=\left(16+\frac{8}{\gamma^{*}}\max_{i}\frac{v_{A,i}}{v_{B,i}}\right)\lambda^{*}h+\left(8\gamma^{*}+4\max_{i}\frac{v_{A,i}}{v_{B,i}}\right)\eta$

and, with symmetric arguments, a suboptimality for player $B$ smaller than

$\varepsilon_{B}=\left(16+8\max_{i}\frac{v_{B,i}}{v_{A,i}}\right)\frac{\lambda^{*}h}{\gamma^{*}}+\left(8+4\max_{i}\frac{v_{B,i}}{v_{A,i}}\right)\eta\,.$

###  4.3. Computational complexity

In this section, we tally the complexity required to achieve either
$\varepsilon$-suboptimality gap in the value-symmetric case or an
$\varepsilon$-Nash equilibrium in the value-asymmetric case.

Before making this distinction recall the various steps that were employed,
together with their computational complexity.

Lotto Step.:

Computing one (and, actually, all) pair of parameters $(\gamma,\lambda)$
requires $\mathcal{O}(n\log n)$ operations, see Proposition 1.

Step 1::

Computing all couplings $\pi_{k}$ and their associated convex weights $q_{k}$
requires $\mathcal{O}(n^{2})$ operations; see Lemma 1.

Step 2::

Given some coupling $\pi_{k}$ computed at step 1, the reduction from $n$ to
only $4$ random variables requires $\mathcal{O}(n^{2})$ operations; see Lemma
3.

Step 3::

The discretization step is computationally costless.

Step 4::

The Sinkhorn algorithm requires
$\mathcal{O}(\frac{\log(1/\tilde{\mu}_{\min})}{\eta})$ operations; see
Proposition 4. Since the marginal distributions $\mu_{i}$ are
$h$-discretizations of either uniform on an interval of size at most
$\sum\frac{\gamma^{*}v_{B,i}}{\lambda^{*}}\leq\frac{\gamma^{*}}{\lambda^{*}}$,
or uniform on interval of length $\frac{v_{A,i}}{\lambda^{*}}$ with weight
$\frac{v_{A,i}}{\gamma^{*}v_{B,i}}$, it holds that
$\tilde{\mu}_{\min}\geq\frac{h\lambda^{*}}{\gamma^{*}}$. At each iteration of
Sinkhorn, all the components of the tensor are computed, hence a complexity,
per iteration, in
$\mathcal{O}\Big{(}(\frac{\gamma^{*}}{h\lambda^{*}})^{3}\Big{)}$.

Step 5::

The sampling cost comes from the reconstruction of the budget allocation from
the 4 random variables, constructed at Step 2 and sampled from the coupling
computed at step 4. The sampling step has a linear cost with respect to the
discretization size $\mathcal{O}(\frac{\gamma^{*}}{h\lambda^{*}})$ while the
reconstruction complexity scales linearly with respect to the number of
battlefields $\mathcal{O}(n)$ .

We are now in a position to state our main theorems. We begin with the
symmetric-value case for player $A$. The result for player $B$ is completely
analogous and therefore omitted.

###### Theorem 1.

Consider the two-player Blotto game on $n$ battlefields with symmetric values
$v_{1},\ldots,v_{n}$ where player $A$ has budget $T_{A}$ and player $B$ has
budget $T_{B}\leq T_{A}$ and assume that these data satisfy the conditions of
Corollary 6. Fix $\varepsilon>0$ and let $\eta=\varepsilon/4$ and
$h=\varepsilon T_{A}/8$. Then the procedure described in Algorithm Sample
samples from an $\varepsilon$-suboptimal strategy for player $A$ in time

$\mathcal{O}\left(n^{2}+\frac{\log(1/\varepsilon)}{\varepsilon^{4}}\right)$

###### Proof.

Note first that the preprocessing cost associated to steps 1 through 4 is
$\mathcal{O}(n^{2})$.

To compute the cost of Sinkhorn iterations, observe that the parameters $\eta$
and $h$ are chosen in such a way that each term on the right-hand side of (21)
is equal to $\varepsilon/2$:

$8\frac{\lambda^{*}}{\gamma^{*}}h=4\eta=\frac{\varepsilon}{2}$

Hence,

$\tilde{\mu}_{\min}\geq\frac{h\lambda^{*}}{\gamma^{*}}=\frac{\varepsilon}{16}\,,\quad\text{and}\quad\left(\frac{\gamma^{*}}{h\lambda^{*}}\right)^{3}=\left(\frac{16}{\varepsilon}\right)^{3}\,.$

Moreover, since $\eta=\varepsilon/8$, we get that the total complexity of
Sinkhorn iterations is

$\mathcal{O}\left(\left(\frac{\gamma^{*}}{h\lambda^{*}}\right)^{3}\frac{\log\left(1/\tilde{\mu}_{\min}\right)}{\eta}\right)=\mathcal{O}\left(\varepsilon^{-3}\frac{\log\left(1/\varepsilon\right)}{\varepsilon}\right)=\mathcal{O}\left(\varepsilon^{-4}\log(1/\varepsilon)\right)$

Finally, the last step has a total cost of $\mathcal{O}(n+\varepsilon)$ which
is negligible with respect to the combination of previous steps. ∎

It is worth noting that in the value-symmetric case, the computational
complexity of our procedure is _independent_ of the datum of the problem
(budgets and values) under the normalization (1). Note that this normalization
merely scales the utility and should of course affect the desired accuracy
parameter $\varepsilon$.

We now move to the asymmetric-value case and characterize the complexity of
our procedure to compute an $\varepsilon$-Nash equilibrium for the Blotto
game. As above, we focus on player $A$ only.

###### Theorem 2.

Consider the Blotto game on $n$ battlefields with asymmetric values
$v_{P,1},\ldots,v_{P,n}$, $P\in\\{A,B\\}$, where player $P\in\\{A,B\\}$ has
budget $T_{P}$, with $T_{B}\leq T_{A}$ and assume that these data satisfy the
conditions of Corollary 6. Define

$\mathfrak{m}=\max_{i}\frac{v_{A,i}}{v_{B,i}}\vee\frac{v_{B,i}}{v_{A,i}}\,.$

Fix $\varepsilon>0$ and let

$\eta=\frac{\varepsilon}{24\mathfrak{m}}\,,\qquad
h=\frac{\gamma^{*}}{\lambda^{*}}\frac{\varepsilon}{48\mathfrak{m}}\,.$

Then Algorithm Lotto2Blotto samples from an $\varepsilon$-Nash equilibrium in
time

$\mathcal{O}\left(n^{2}+\left(\frac{\mathfrak{m}}{\varepsilon}\right)^{4}\log\left(\frac{\mathfrak{m}}{\varepsilon}\right)\right)$

###### Proof.

Note first that the preprocessing cost associated to steps 1 through 4 is
$\mathcal{O}(n^{2})$.

To compute the cost of Sinkhorn iterations, observe that the parameters $\eta$
and $h$ are chosen in such a way that each term on the right-hand side of (22)
are smaller than $\varepsilon/2$:

$\left(16+\frac{8}{\gamma^{*}}\mathfrak{m}\right)\lambda^{*}h,\left(4\gamma^{*}+2\mathfrak{m}\right)\eta\leq\frac{\varepsilon}{2}$

Hence,

$\tilde{\mu}_{\min}\geq\frac{h\lambda^{*}}{\gamma^{*}}=\frac{\varepsilon}{48\mathfrak{m}}\,,\quad\text{and}\quad\left(\frac{\gamma^{*}}{h\lambda^{*}}\right)^{3}=\left(\frac{48\mathfrak{m}}{\varepsilon}\right)^{3}\,.$

Together with the prescribed value of $\eta$ and since
$\gamma^{*}\leq\mathfrak{m}$ because of Proposition 1, we get that the total
complexity of Sinkhorn iterations is

$\mathcal{O}\left(\left(\frac{\gamma^{*}}{h\lambda^{*}}\right)^{3}\frac{\log\left(1/\tilde{\mu}_{\min}\right)}{\eta}\right)=\mathcal{O}\left(\left(\frac{\mathfrak{m}}{\varepsilon}\right)^{4}\log\left(\frac{\mathfrak{m}}{\varepsilon}\right)\right)$

Finally, the last step has a total cost of $\mathcal{O}(n+\varepsilon)$ which
is negligible with respect to the combination of previous steps. ∎

Acknowledgments. Vianney Perchet acknowledges support from the French National
Research Agency (ANR) under grant number (ANR-19-CE23-0026 as well as the
support grant, as well as from the grant “Investissements d’Avenir” (LabEx
Ecodec/ANR-11-LABX-0047). Philippe Rigollet is supported by NSF grants
IIS-1838071, DMS-2022448, and CCF-2106377.

## References

  * ABA [20] Jason M Altschuler and Enric Boix-Adsera.  Polynomial-time algorithms for multimarginal optimal transport problems with structure.  arXiv preprint arXiv:2008.03006, 2020.
  * ABA [21] Jason Altschuler and Enric Boix-Adsera.  Hardness results for multimarginal optimal transport problems.  Discrete Optim. (to appear), 2021.
  * AC [11] Martial Agueh and Guillaume Carlier.  Barycenters in the Wasserstein space.  SIAM Journal on Mathematical Analysis, 43(2):904–924, 2011.
  * ADH+ [19] AmirMahdi Ahmadinejad, Sina Dehghani, MohammadTaghi Hajiaghayi, Brendan Lucier, Hamid Mahini, and Saeed Seddighin.  From duels to battlefields: Computing equilibria of blotto and other games.  Mathematics of Operations Research, 44(4):1304–1325, 2019.
  * AWR [17] Jason Altschuler, Jonathan Weed, and Philippe Rigollet.  Near-linear time approximation algorithms for optimal transport via sinkhorn iteration.  In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 4-9 December 2017, Long Beach, CA, USA, pages 1961–1971, 2017.
  * BC [80] Robert M. Bell and Thomas M. Cover.  Competitive optimality of logarithmic investment.  Mathematics of Operations Research, 5(2):161–166, 1980.
  * Bea [22] Daniel Beaglehole.  An efficient approximation algorithm for the Colonel Blotto game.  arXiv preprint arXiv:2201.10758, 2022.
  * Bor [21] Emile Borel.  La théorie du jeu et les équations intégrales à noyau symétrique.  C. R. Acad. Sci., Paris, 173:1304–1308, 1921.
  * Bub [15] Sébastien Bubeck.  Convex optimization: Algorithms and complexity.  Foundations and Trends in Machine Learning, 8(3-4):231–357, 2015\.
  * BV [38] Emile Borel and Jean Ville.  Applications de la théorie des probabilités aux jeux de hasard: cours professé à la Faculté des sciences de Paris.  Gauthier-Villars, 1938.
  * Cut [13] Marco Cuturi.  Sinkhorn distances: Lightspeed computation of optimal transport.  In C. J. C. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems 26, pages 2292–2300. Curran Associates, Inc., 2013.
  * DMGN [17] Simone Di Marino, Augusto Gerolin, and Luca Nenna.  Optimal transportation theory with repulsive costs.  Topological Optimization and Optimal Transport: In the Applied Sciences, 17:204–256, 2017.
  * Fré [53] Maurice Fréchet.  Emile Borel, initiator of the theory of psychological games and its application.  Econometrica, 21:95–96, 1953.
  * FSM [21] Aidin Ferdowsi, Walid Saad, and Narayan B. Mandayam.  Colonel Blotto game for sensor protection in interdependent critical infrastructure.  IEEE Internet of Things Journal, 8(4):2857–2874, 2021.
  * Gro [50] Oliver Gross.  The symmetric Blotto game.  Technical report, Rand Corporation, 1950.
  * GW [50] Oliver Gross and Robert Wagner.  A continuous Colonel Blotto game.  Technical report, Rand Corporation, 1950.
  * Har [08] Sergiu Hart.  Discrete Colonel Blotto and general Lotto games.  International Journal of Game Theory, 36(3):441–460, 2008.
  * HM [17] Mohammad Hajimirsaadeghi and Narayan B. Mandayam.  A dynamic Colonel Blotto game model for spectrum sharing in wireless networks.  In 2017 55th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 287–294, 2017.
  * HVLS [12] Rafael Hortala-Vallve and Aniol Llorente-Saguer.  Pure strategy Nash equilibria in non-zero sum Colonel Blotto games.  International Journal of Game Theory, 41(2):331–343, 2012.
  * KR [21] Dan Kovenock and Brian Roberson.  Generalizations of the general Lotto and Colonel Blotto games.  Economic Theory, 71(3):997–1032, 2021.
  * KS [06] Martin Knott and Cyril Smith.  Choosing joint distributions so that the variance of the sum is small.  J. Multivar. Anal., 97(8):1757–1765, sep 2006.
  * Las [02] Jean-François Laslier.  How two-party competition treats minorities.  Review of Economic Design, 7(3):297, 2002.
  * LHCJ [20] Tianyi Lin, Nhat Ho, Marco Cuturi, and Michael I. Jordan.  On the complexity of approximating multimarginal optimal transport, 2020\.
  * LHSR [15] Mina Labib, Sean Ha, Walid Saad, and Jeffrey H. Reed.  A Colonel Blotto game for anti-jamming in the internet of things.  In 2015 IEEE Global Communications Conference (GLOBECOM), pages 1–6, 2015.
  * LP [02] Jean-François Laslier and Nathalie Picard.  Distributive politics and electoral competition.  Journal of Economic Theory, 103(1):106–130, 2002.
  * MM [15] Scott T. Macdonell and Nick Mastronardi.  Waging simple wars: a complete characterization of two-battlefield Blotto equilibria.  Economic Theory, 58(1):183–216, 2015.
  * MMT [05] Jennifer Merolla, Michael Munger, and Michael Tofias.  In play: A commentary on strategies in the 2004 u.s. presidential election.  Public Choice, 123(1/2):19–37, 2005.
  * MS [15] Antonia Maria Masucci and Alonso Silva.  Defensive resource allocation in social networks.  In 2015 54th IEEE Conference on Decision and Control (CDC), pages 2927–2932. IEEE, 2015.
  * Mye [93] Roger B. Myerson.  Incentives to cultivate favored minorities under alternative electoral systems.  The American Political Science Review, 87(4):856–869, 1993.
  * Nak [06] Mikio Nakayama.  The dawn of modern theory of games.  In Advances in mathematical economics. Vol. 9, pages 73–97. Tokyo: Springer, 2006.
  * PW [22] Yury Polyanskiy and Yihong Wu.  Information Theory Information Theory: From Coding to Learning.  Cambridge University Press, Cambridge, 2022.
  * Ren [99] Philip J. Reny.  On the existence of pure and mixed strategy nash equilibria in discontinuous games.  Econometrica, 67(5):1029–1056, 1999.
  * Rob [06] Brian Roberson.  The Colonel Blotto game.  Economic Theory, 29(1):1–24, 2006.
  * RU [02] Ludger Rüschendorf and Ludger Uckelmann.  Variance minimization and random variables with constant sum.  In Distributions with given marginals and statistical modelling, pages 211–222. Springer, 2002.
  * San [15] Filippo Santambrogio.  Optimal transport for applied mathematicians, volume 87 of Progress in Nonlinear Differential Equations and their Applications.  Birkhäuser/Springer, Cham, 2015.
  * Sin [64] Richard Sinkhorn.  A relationship between arbitrary positive matrices and doubly stochastic matrices.  The annals of mathematical statistics, 35(2):876–879, 1964.
  * SK [67] Richard Sinkhorn and Paul Knopp.  Concerning nonnegative matrices and doubly stochastic matrices.  Pacific Journal of Mathematics, 21(2):343–348, 1967.
  * SLS [14] Galina Schwartz, Patrick Loiseau, and Shankar S. Sastry.  The heterogeneous Colonel Blotto game.  In 2014 7th International Conference on NETwork Games, COntrol and OPtimization (NetGCoop), pages 232–238, 2014.
  * Tho [18] Caroline Thomas.  N-dimensional Blotto game with heterogeneous battlefield values.  Economic Theory, 65(3):509–544, 2018.
  * Tsy [09] Alexandre B. Tsybakov.  Introduction to nonparametric estimation.  Springer Series in Statistics. Springer, New York, 2009.
  * von [28] John von Neumann.  Zur Theorie der Gesellschaftsspiele.  Math. Ann., 100:295–320, 1928.
  * Wei [12] Jonathan Weinstein.  Two notes on the Blotto game.  The BE Journal of Theoretical Economics, 12(1), 2012.
  * WW [16] Bin Wang and Ruodu Wang.  Joint mixability.  Mathematics of Operations Research, 41(3):808–826, 2016.
  * Zim [20] Alexander P. Zimin.  On existence of measure with given marginals supported on a hyperplane, 2020.

##  Appendix A The discrete case

During the construction of an approximated solution of the classical Blotto
game, we had to resort to some discretization, and we implicitly proved that
some discrete random variables were jointly mixable. Quite unfortunately, this
result can not be directly generalized to solve the discrete, pure count
Blotto game (where Lotto solutions were computed explicitly [17]).

We recall that in the discrete pure count Blotto problem, the budget of each
player $T_{A}$ and $T_{B}$ are non-negative integers and that the amount
allocated by players to battlefields, $x_{A,i}$ and $x_{B,j}$, are also non-
negative integers. Finally, explicit solutions of the Lotto problem are only
available in the pure count problem, when $v_{A,i}=v_{B,i}=1$, hence we shall
focus on this case. In discrete Lotto/Blotto, the probability of equal forces
$x_{A,i}=x_{B,i}$ is positive and if this happens, we will still assume that
both players wins the battlefield with probability $1/2$.

[17] described optimal strategies in the associated Lotto game with the
following additional notations. The average budget per battlefield are denoted
by $a=T_{A}/n$ and $b=T_{B}/n$, the uniform distribution on even integers
between $0$ and $2m$ is denoted by $U_{e}^{m}={\sf Unif}\\{0,2,...,2m\\}$
while $U_{o}^{m}={\sf Unif}\\{1,3,...,2m-1\\}$ is the uniform distribution on
even integers between 1 and $2m-1$. Those strategies are described in [17,
Fig. 1].

He also introduced the term of a “feasible” distribution, to indicate that $n$
random variable of that distribution are jointly mixable. He then proved the
following

###### Proposition 1.

  * •

If $T_{A}=mn$ then $U^{m}_{o}$ is ”feasible” if and only if $T_{A}$ and $n$
have the same parity

  * •

If $T_{A}=mn$ then $U^{m}_{e}$ is ”feasible” if and only if $X_{A}$ is even

  * •

If $T_{A}=mn+r$ with $1\leq r\leq n-1$ then
$(1-\frac{r}{n})U^{m}_{e}+\frac{r}{n}U^{m+1}_{o}$ is ”feasible”

As a consequence, [17] characterized Nash equilibrium of the discrete Blotto
problem in the following three cases:

  1. (1)

If $T_{A}=T_{B}$ (because of the first and third rows of [17, Fig. 1])

  2. (2)

If $mn<T_{B}<T_{A}<(m+1)n$ for some $m\in\mathds{N}$ (because of the third row
of [17, Fig. 1])

  3. (3)

If $mn=T_{B}<T_{A}<(m+1)n$ for some $m\in\mathds{N}$, if $X_{B}$ is even
(because of the fourth row of [17, Fig. 1])

Now, let us state the following Proposition 2 that will imply the above 3
points. The proof, rather technical (yet algorithmic) is postponed.

###### Proposition 2.

Discrete random variables ${\sf Unif}\\{0,\ldots,\ell_{i}\\}$ are jointly
mixable if and only if their continuous counterparts ${\sf Unif}[0,\ell_{i}]$
are jointly mixable and $\sum_{i}\ell_{i}$ is even.

This proposition allows us to describe solutions of the discrete Blotto game.

###### Theorem 3.

Assume $X_{B}$ is even and $X_{A}$ has the same parity than $n$, then the
optimal strategies of the discrete Blotto game are given by [17, Fig. 1].
Moreover those strategies can be computed using the same algorithmic approach
as in Proposition 2.

###### Proof.

We will prove the theorem first when $T_{A}=mn$ for some $m\in\mathds{N}$ and
then when $T_{B}<mn<T_{A}$, again for some $m\in\mathds{N}$. The other cases
are already covered [17].

  1. 1.

If $T_{B}<mn=T_{A}$, then the optimal strategy of Player $A$ is $U_{o}^{m}$,
which is feasible if $T_{A}$ and $n$ have the same parity. Indeed, since
$U_{o}^{m}={\sf Unif}\\{1,\ldots,2m-1\\}=1+2{\sf Unif}\\{0,\ldots,m-1\\}$, the
problem reduces to mixing $n$ random variables of law ${\sf
Unif}\\{0,\ldots,m-1\\}$; this requires that $n(m-1)=T_{A}-n$ is even.

Player $B$ marginals are $(1-\frac{b}{m})\delta_{0}+\frac{b}{m}U^{m}_{o/e}$.
So it remains to prove that those random variables are jointly mixable. In
particular, this holds if $(1-\frac{b}{m})\delta_{0}+\frac{b}{m}{\sf
Unif}\\{0,\ldots,2m\\}$ are jointly mixable by choosing appropriate weights on
$U^{m}_{o}$ and $U^{m}_{e}$.

In the continuous case (i.e., if uniform distributions are over $[0,m]$
instead of $\\{0,m\\}$), [33] constructed explicit couplings between such
random variables by reducing to coupling of uniform continuous random
variables. We apply the exact same techniques, yet we just need to ensure that
the intervals of the continuous uniform distributions start and end on
integers and that the sums of lengths are always even. But this immediately
happens as soon as $X_{A}/n$ is an integer.

Indeed, all the couplings introduced in [33] involves uniform random variables
over intervals $[\alpha_{i},\beta_{i}]$ where
$\alpha_{i},\beta_{i}\in\\{0,2m,X_{B}-2m,bn-4m,...\\}$. As a consequence, all
interval lengths are even if $T_{B}=bn$ is even, which implies that the
discrete uniform variables over $\\{\alpha_{i},\ldots,\beta_{i}\\}$ are
jointly mixable.

  2. 2.

In the second case, the strategy of player $B$ is to jointly mix $n$ random
variables of distribution $(1-\frac{b}{m})\delta_{0}+\frac{b}{m}{\sf
Unif}\\{0,2,\ldots,2m\\}$ which is equivalent to mixing $n$ distributions
$(1-\frac{b}{m})\delta_{0}+\frac{b}{m}{\sf Unif}\\{0,1,\ldots,m\\}$. Using
again, exactly as above, the construction based on the continuous couplings of
[33], this is possible as soon as $T_{B}$ is even.

On the other hand, Player $A$ marginals are $(1-\alpha)U_{o}^{m}+\alpha
U_{o}^{m+1}$, thus we need to prove that $(1-\alpha){\sf
Unif}\\{0,m-1\\}+\alpha{\sf Unif}\\{0,m\\}$ are jointly mixable. To ensure
this, one just need to select $n\alpha$ battlefields at random and to allocate
${\sf Unif}\\{0,m\\}$ on them (and ${\sf Unif}\\{0,m-1\\}$ on the $n-n\alpha$
remaining battlefields). As a consequence, we end up in mixing $n\alpha$
uniforms ${\sf Unif}\\{0,m\\}$ and $n-n\alpha$ uniforms ${\sf
Unif}\\{0,m-1\\}$, which is possible as soon as $n\alpha
m+(n-n\alpha)(m-1)=T_{A}-n$ is even, i.e., if $T_{A}$ and $n$ have the same
parity.

These two claims give the result. ∎

We finally prove Proposition 2

###### Proof of Proposition 2.

The proof of the necessary part of the condition is identical to the
continuous case. The only difference is the fact that $\sum\ell_{i}$ must be
even. This is naturally implied by the fact that $\sum X_{i}$ is always an
integer, hence $\sum\mathds{E}X_{i}=\sum\ell_{i}/2$ should also be an integer
if these random variables are jointly mixable.

It only remains to prove this statement for $n\geq 3$ as the case $n=2$ is
trivial. Moreover, proving the statement for $n>3$ can be be reduced to the
case $n=3$ with a simple induction over $n$, as in the continuous case [43].
Indeed, since ${\sf Unif}\\{0,\ldots,\ell_{1}\\}$, ${\sf
Unif}\\{0,\ldots,\ell_{2}\\}$ and ${\sf Unif}\\{0,\ldots,\ell_{1}+\ell_{2}\\}$
are jointly mixable (because they satisfy the condition of the Proposition for
$n=3$), it is possible to reduce the joint mixability of $n$ uniform to only
$3$. As a consequence, we will solely focus on $n=3$ and and we assume wlog
that $\ell_{1}\leq\ell_{2}\leq\ell_{3}$

The proof will be based on another induction on the maximal size $\ell_{3}$.
We will distinguish three cases, depending on whether
$\ell_{1}=\ell_{2}=\ell_{3}$, or $\ell_{1}<\ell_{2}=\ell_{3}$, or
$\ell_{2}<\ell_{3}$.

First case: $\ell_{1}=\ell_{2}=\ell_{3}$ (in particular, this implies that
$\ell_{1},\ell_{2},\ell_{3}$ are even since
$\ell_{1}+\ell_{2}+\ell_{3}=3\ell_{i}$ is even by assumption).

If $\ell_{1}=2$, then the uniform coupling on the triplets $(0,1,2)$,
$(1,2,0)$ and $(2,0,1)$ proves joint mixability. If $\ell_{1}=4$, then
considering the uniform distribution on the following set

$\displaystyle\Big{\\{}(3,3,0);(3,0,3);(0,3,3);(4,1,1);(1,4,1);(1,1,4);$
$\displaystyle(0,2,4);(2,4,0);(4,0,2);(2,2,2)\Big{\\}}$

is sufficient to prove joint mixability. From now on, we shall assume that
$\ell_{1}=\ell_{2}=\ell_{3}\geq 6$.

Consider the coupling defined by

$\displaystyle X^{1,-}_{1}\sim\delta_{0},\quad X^{1,-}_{2}\sim{\sf
Unif}\\{\frac{\ell_{1}}{2}+1,\ell_{1}-1\\}\ \ \text{ and }$ $\displaystyle
X^{1,-}_{3}=\frac{3}{2}\ell_{1}-X_{2}^{1,-}\sim{\sf
Unif}\\{\frac{\ell_{1}}{2}+1,\ell_{1}-1\\}.$

Then it immediately follows that
$X^{1,-}_{1}+X^{1,-}_{2}+X^{1,-}_{3}=\frac{3}{2}\ell_{1}$. Similarly, this
property holds with the following alternative coupling

$\displaystyle X^{1,+}_{1}\sim\delta_{\ell_{1}},\quad X^{1,+}_{2}\sim{\sf
Unif}\\{1,\frac{\ell_{1}}{2}-1\\}\ \ \text{ and }$ $\displaystyle
X^{1,+}_{3}=\frac{1}{2}\ell_{1}-X_{2}^{1,+}\sim{\sf
Unif}\\{1,\frac{\ell_{1}}{2}-1\\}.$

We define similarly the coupling $(X_{i}^{2,\pm})_{i\in[3]}$ and
$(X_{i}^{3,\pm})_{i\in[3]}$ where the role of $X_{1}$ is exchanged with
$X_{2}$ and, respectively, $X_{3}$. We also define the last coupling
$X_{i}^{0}=\delta_{\frac{\ell_{i}}{2}}$.

Then $X_{i}$ can be decomposed as follows:

$X_{i}=\frac{1}{\ell_{1}+1}\Big{\\{}\sum_{k\in[3]}X_{i}^{k,-}+\sum_{k\in[3]}X_{i}^{k,+}+\frac{2}{\frac{\ell_{i}}{2}-1}X_{i}^{0}\Big{\\}}+\frac{\ell_{1}-5}{\ell_{1}+1}Y_{i},$

where $Y_{i}\sim{\sf Unif}\\{1,\ldots,\ell_{1}\\}$. A simple induction gives
the joint mixability of $\\{X_{1},X_{2},X_{3}\\}$

Second case: $\ell_{1}<\ell_{2}=\ell_{3}$ (in particular, this implies that
$\ell_{1}$ is even). There are two specifics cases $\ell_{1}=2$ and
$\ell_{2}\in\\{3,4\\}$ that are constructed explicitly as follows.

If $\ell_{1}=2$ and $\ell_{2}=\ell_{3}=3$, a joint mixability coupling is

$\frac{1}{6}\Big{(}\delta_{(0,3,1)}+\delta_{(0,1,3)}+\delta_{(2,2,0)}+\delta_{(2,0,2)}\Big{)}+\frac{1}{12}\Big{(}\delta_{(1,3,0)}+\delta_{(1,0,3)}+\delta_{(1,1,2)}+\delta_{(1,2,1)}\Big{)}$

while if $\ell_{1}=2$ and $\ell_{2}=\ell_{3}=4$, a valid coupling is

$\displaystyle\frac{2}{15}\Big{(}\delta_{(2,3,0)}+\delta_{(2,0,3)}+\delta_{(0,4,1)}+\delta_{(0,1,4)}+\delta_{(1,2,2)}\Big{)}$
$\displaystyle+\frac{1}{15}\Big{(}\delta_{(1,0,4)}+\delta_{(1,4,0)}+\delta_{(0,3,2)}+\delta_{(2,2,1)}+\delta_{(1,1,3)}\Big{)}$

For the other cases, we consider similar couplings as above, i.e.,

$\displaystyle X^{3,-}_{3}\sim\delta_{0},\quad X^{3,-}_{2}\sim{\sf
Unif}\\{\ell_{2}-\frac{\ell_{1}}{2},\ell_{2}-1\\}\ \ \text{ and }$
$\displaystyle X_{1}^{3,-}=\ell_{2}+\frac{\ell_{1}}{2}-X_{2}^{3,-}\sim{\sf
Unif}\\{\frac{\ell_{1}}{2}+1,\ell_{1}\\}$

and also

$\displaystyle X^{3,+}_{3}\sim\delta_{\ell_{3}},\quad X^{3,-}_{2}\sim{\sf
Unif}\\{1,\frac{\ell_{1}}{2}\\}\ \ \text{ and }$ $\displaystyle
X_{1}^{3,+}=\frac{\ell_{1}}{2}-X_{2}^{3,-}\sim{\sf
Unif}\\{0,\frac{\ell_{1}}{2}-1\\}.$

We define $X_{i}^{2,\pm}$ similarly.

If $\ell_{1}\geq 4$, we introduce the following random variables (the case
$\ell_{1}=2$ is detailed just below)

$\displaystyle Y_{1}^{1}\sim\delta_{\frac{\ell_{1}}{2}},Y_{1}^{2}\sim{\sf
Unif}\\{0,\ell_{1}\\},Y_{1}^{3}\sim{\sf Unif}\\{0,\ell_{1}\\}$
$\displaystyle\text{ and }\ Y_{1}^{4}\sim{\sf Unif}\\{0,\ell_{1}\\}$

and similarly

$\displaystyle Y_{2}^{1}\sim{\sf Unif}\\{1,\ell_{2}-1\\},Y_{2}^{2}\sim{\sf
Unif}\\{\frac{\ell_{1}}{2}+1,\ell_{2}-\frac{\ell_{1}}{2}-1\\},Y_{2}^{3}\sim{\sf
Unif}\\{1,\ell_{2}-1\\}$ $\displaystyle\text{ and }\ Y_{2}^{4}\sim{\sf
Unif}\\{1,\ell_{2}-1\\}$

and

$\displaystyle Y_{3}^{1}\sim{\sf Unif}\\{1,\ell_{3}-1\\},Y_{3}^{2}\sim{\sf
Unif}\\{1,\ell_{3}-1\\},Y_{3}^{3}\sim{\sf
Unif}\\{\frac{\ell_{1}}{2}+1,\ell_{2}-\frac{\ell_{1}}{2}-1\\}$
$\displaystyle\text{ and }\ Y_{3}^{4}\sim{\sf Unif}\\{1,\ell_{3}-1\\}$

So that we can decompose

$X_{i}=\frac{1}{\ell_{3}+1}(X_{i}^{3,-}+X_{i}^{3,+}+X_{i}^{2,-}+X_{i}^{2,+})+p_{1}Y_{i}^{1}+p_{2}Y_{i}^{2}+p_{3}Y_{i}^{3}+p_{4}^{i}$

where the probability are defined by

$p_{1}=\frac{4}{\ell_{3}+1}\frac{1}{\ell_{1}},p_{3}=p_{2}=\frac{2}{\ell_{3}+1}\frac{\ell_{2}-\ell_{1}-1}{\ell_{1}}\
\text{ and }p_{4}=1-\frac{4}{\ell_{3}+1}-p_{1}-p_{2}-p_{3}$

Those couplings are well defined and satisfy the theorem length condition,
hence we will be able to proceed by induction.

It remains to consider the case where $\ell_{1}=2$ (plugging $\ell_{1}=2$ in
the above construction would give $p_{4}<0$ which is obviously impossible).

We define the variables

$Z_{1}^{1}\sim\delta_{1}\ \text{ and }\ Z_{1}^{2}\sim{\sf Unif}\\{0,2\\}$

and similarly

$Z_{2}^{1}\sim{\sf Unif}\\{2,\ell_{2}-2\\},\ \text{ and }\ Z_{2}^{2}\sim{\sf
Unif}\\{2,\ell_{2}-2\\}$

and

$Z_{3}^{1}\sim{\sf Unif}\\{2,\ell_{2}-2\\}\ \text{ and }\ Z_{3}^{2}\sim{\sf
Unif}\\{2,\ell_{3}-2\\}$

So that we can decompose

$X_{i}=\frac{1}{\ell_{3}+1}(X_{i}^{3,-}+X_{i}^{3,+}+X_{i}^{2,-}+X_{i}^{2,+})+q_{1}Z_{i}^{1}+q_{2}Z_{i}^{2}$

where the probability are defined by

$q_{1}=\frac{2}{\ell_{3}+1}\ \text{ and
}q_{2}=1-\frac{4}{\ell_{3}+1}-q_{1}=1-\frac{6}{\ell_{3}+1},$

and the result also follows by induction.

Third case: $\ell_{1}<\ell_{2}<\ell_{3}$. We are going to proceed by induction
(on the maximal length) as before, and we consider the following couplings

$\displaystyle X_{3}^{-}=\delta_{0},\quad X_{2}^{-}\sim{\sf
Unif}\\{\frac{\ell_{3}+\ell_{2}-\ell_{1}}{2},\ell_{2}\\}$
$\displaystyle\text{and}\
X_{1}^{-}=\frac{\ell_{3}+\ell_{2}+\ell_{1}}{2}-X_{2}^{-}={\sf
Unif}\\{0,\frac{\ell_{1}+\ell_{2}-\ell_{3}}{2}\\}$

and the similar one

$\displaystyle X_{3}^{-}=\delta_{\ell_{3}},\quad X_{2}^{-}\sim{\sf
Unif}\\{0,\frac{\ell_{1}+\ell_{2}-\ell_{3}}{2})\\}$ $\displaystyle\text{and}\
X_{1}^{-}=\frac{\ell_{3}+\ell_{2}+\ell_{1}}{2}-X_{2}^{-}={\sf
Unif}\\{\frac{\ell_{1}+\ell_{3}-\ell_{2}}{2},\ell_{1}\\}$

It remains to introduce the following random variables

$\displaystyle Y_{1}^{1}\sim{\sf
Unif}\\{\frac{\ell_{1}+\ell_{2}-\ell_{3}}{2}+1,\frac{\ell_{1}+\ell_{3}-\ell_{2}}{2}-1\\},\quad
Y_{1}^{2}\sim{\sf Unif}\\{0,\ell_{1}\\}$ $\displaystyle\text{ and }\
Y_{1}^{3}\sim{\sf Unif}\\{0,\ell_{1}\\}$

and similarly

$\displaystyle Y_{2}^{1}\sim{\sf Unif}\\{0,\ell_{2}\\},\quad Y_{2}^{2}\sim{\sf
Unif}\\{\frac{\ell_{1}+\ell_{2}-\ell_{3}}{2}+1,\frac{\ell_{2}+\ell_{3}-\ell_{1}}{2}-1\\}$
$\displaystyle\text{ and }\ Y_{2}^{3}\sim{\sf Unif}\\{0,\ell_{2}\\}$

and

$\displaystyle Y_{3}^{1}\sim{\sf Unif}\\{1,\ell_{3}-1\\},\quad
Y_{3}^{2}\sim{\sf Unif}\\{1,\ell_{3}-1\\}$ $\displaystyle\text{ and }\
Y_{3}^{3}\sim{\sf Unif}\\{1,\ell_{3}-1\\}.$

So that we can decompose

$X_{i}=\frac{1}{\ell_{3}+1}(X_{i}^{-}+X_{i}^{+})+p_{1}Y_{i}^{1}+p_{2}Y_{i}^{2}+p_{3}Y_{i}^{3}$

where the probability are defined by

$\displaystyle
p_{1}=\frac{1}{\ell_{3}+1}\frac{\ell_{3}-\ell_{2}-1}{\frac{\ell_{1}+\ell_{2}+\ell_{3}}{2}+1},\quad
p_{2}=\frac{1}{\ell_{3}+1}\frac{\ell_{3}-\ell_{1}-1}{\frac{\ell_{1}+\ell_{2}+\ell_{3}}{2}+1}$
$\displaystyle\text{ and }\ p_{3}=1-\frac{2}{\ell_{3}+1}-p_{1}-p_{2}$

The proof relies on a simple induction by noticing that
$\\{Y_{1}^{1},Y_{2}^{1},Y_{3}^{1}\\}$ satisfies the theorem condition (as soon
as $p_{1}>0$) since these three random variables are uniform over intervals of
respective lengths $\ell_{3}-\ell_{2}-2$, $\ell_{2}$ and $\ell_{3}-2$ (in
particular, $\ell_{2}$ is the maximum of these 3 quantities, necessarily
$\ell_{2}=\ell_{3}-1$ and $p_{1}=0$). Similarly
$\\{Y_{1}^{2},Y_{2}^{2},Y_{3}^{2}\\}$ and
$\\{Y_{1}^{3},Y_{2}^{3},Y_{3}^{3}\\}$ satisfy the theorem condition as well. ∎

##  Appendix B Omitted Proofs and algorithms

###  B.1. Algorithm Lotto2Blotto

We provide the simple pseudo-code of the main algorithm; it is decomposed into
several procedures described in subsequent sections.

Data: Length & weight vectors $\mathbf{b}\in\mathds{R}_{+}^{n}$ and
$\mathbf{p}\in[0,1]^{n}$, budget $T$, approximation levels $\eta,h$;

Result: Allocation vector $X\in\mathds{R}_{+}^{n}$;

$\\{(\mathbf{p}^{(j)},q_{j})\\}_{j}\leftarrow\textsc{Decomp}(\mathbf{b},T,\mathbf{p})$
$\triangleright$ Couplings with one strict mixture

Sample $j^{*}=j$ with probability $q_{j}$;

$(\mathcal{I}_{0},\mathcal{I}_{1},\mathcal{I}_{2},\mathcal{I}_{3},\mathcal{I}_{4})\leftarrow\textsc{Reduc}(\mathbf{b},\mathbf{p}^{(j^{*})})$
$\triangleright$ Reduction to 4 random variables

for  _$i\in[4]$_ do

$b^{*}_{i}\leftarrow\sum_{j\in\mathcal{I}_{j}}b_{j}$;
$p^{*}_{j}\leftarrow\sum_{j\in\mathcal{I}_{j}}p_{j}$;

end for

$(\mu_{1},\mu_{2},\mu_{3},\mu_{4})\leftarrow\textsc{Discretize}((b^{*}_{1},b^{*}_{2},b^{*}_{3},b^{*}_{4}),p^{*}_{4},h)$
$\triangleright$ Appropriate Discretization

$(\xi_{1},\xi_{2},\xi_{3},\xi_{4})\leftarrow\textsc{Sinkhorn}((\mu_{1},\mu_{2},\mu_{3},\mu_{4}),\eta)$
$\triangleright$ Numerical computations

$X\leftarrow\textsc{Sample}((\xi_{1},\xi_{2},\xi_{3},\xi_{4}),T,\mathbf{b},(\mathcal{I}_{0},\mathcal{I}_{1},\mathcal{I}_{2},\mathcal{I}_{3},\mathcal{I}_{4}),h)$
$\triangleright$ Reconstruction and sampling

Output: $X$ $\triangleright$ A valid allocation

ALGORITHM 1 Lotto2Blotto

###  B.2. Proof of Proposition 1 and associated Algorithm Lotto

Data: Battlefield values $v_{A,i}$ and $v_{B,i}$, budgets $T_{A}$ and $T_{B}$;

Result: Vector $\mathbf{b}=(b_{i})_{i\in[n]}$ and probability vector
$\mathbf{p}\in[0,1]^{n}$;

$\gamma\leftarrow 0$, $\lambda\leftarrow 0$, $k\leftarrow 0$ $\triangleright$
Initialization

Sort $\big{\\{}\frac{v_{A,i}}{v_{B,i}};i\in[n]\big{\\}}$ $\triangleright$ Sort
to get degree 3 polynomial equation to solve

while  _$\gamma=0$_ do

$\mathcal{S}_{k}\leftarrow\text{roots}\Big{(}\gamma
T_{A}\sum_{i=1}^{k}v_{a,i}+\gamma^{3}T_{A}\sum_{i=k+1}^{n}\frac{v_{B,i}^{2}}{v_{A,i}}-T_{B}\sum_{i=1}^{k}\frac{v^{2}_{A,i}}{v_{B,i}}-T_{B}\gamma^{2}\sum_{i=k+1}^{n}v_{B,i}\Big{)}$;

for  _$g\in\mathcal{S}_{k}$_ do

$\gamma\leftarrow
g\mathds{1}\big{\\{}\gamma\in[\frac{v_{A,k}}{v_{B,k}},\frac{v_{A,k+1}}{v_{B,k+1}}]\big{\\}}$
$\triangleright$ Keep valid root of degree 3 polynomial

end for

$k\leftarrow k+1$ $\triangleright$ Move to next interval between two ratios
$\frac{v{A,k}}{v_{B,k}}$

end while

$\lambda\leftarrow\frac{1}{T_{A}}\frac{1}{2}\sum_{i=1}^{n}(\gamma
v_{B,i})\wedge\frac{(v_{A,i})^{2}}{\gamma v_{B,i}}$;

for  _$i\in[n]$_ do

$b_{i}\leftarrow\frac{\gamma v_{B,i}}{\lambda}\wedge\frac{v_{A,i}}{\lambda}$,
$p_{i}\leftarrow\frac{v_{A,i}}{\gamma v_{B,i}}\wedge 1$ $\triangleright$
Description of Lotto strategies

end for

Output: $(\mathbf{b},\mathbf{p})$ $\triangleright$ lenghts of uniforms and
associated weights

ALGORITHM 2 Lotto

###### Proof.

First, reorder the battlefields by increasing reward ratios $v_{A,i}/v_{B,i}$
so we can assume that

$\frac{v_{A,1}}{v_{B,1}}\leq\frac{v_{A,2}}{v_{B,2}}\leq\cdots\leq\frac{v_{A,n}}{v_{B,n}}$

Recall that $f(\gamma)$ is the left-hand side of (6). We first observe that
$f$ is continuous on $\mathds{R}$. Indeed, $f$ is obviously continuous on each
open interval

$\left(\frac{v_{A,i}}{v_{B,i}},\frac{v_{A,i+1}}{v_{B,i+1}}\right)$

To check that it is continuous at $\gamma_{i_{0}}:=v_{A,i_{0}}/v_{B,i_{0}}$,
note that for $\gamma$ in a small enough neighborhood of $\gamma_{i_{0}}$, we
have

$\mathcal{N}(\gamma)=\left\\{\begin{array}[]{ll}\\{i_{0}+1,\ldots,n\\}&\text{
if }\gamma>\gamma_{i_{0}}\\\ \\{i_{0},\ldots,n\\}&\text{ if
}\gamma\leq\gamma_{i_{0}}\,.\end{array}\right.$

Hence $f$ is left-continuous at $\gamma_{i_{0}}$. Moreover, we can check
right-continuity by observing that

$\displaystyle\lim_{\begin{subarray}{c}\gamma\to\gamma_{i_{0}}\\\
\gamma>\gamma_{i_{0}}\end{subarray}}f(\gamma)=\gamma_{i_{0}}^{3}\left(T_{A}\sum_{i=i_{0}+1}^{n}\frac{v_{B,i}^{2}}{v_{A,i}}\right)-\gamma_{i_{0}}^{2}T_{B}\sum_{i=i_{0}+1}^{n}v_{B,i}+\gamma_{i_{0}}T_{A}\sum_{i=1}^{i_{0}}v_{A,i}-T_{B}\sum_{i=1}^{i_{0}}\frac{v_{A,i}^{2}}{v_{B,i}}=f(\gamma_{i_{0}})$

where the last identity can be readily checked by substitution.

Having proved that $f$ is continuous, note that for $\gamma$ large enough we
have that $\mathcal{N}(\gamma)=\emptyset$ so that

$f(\gamma)=\gamma
T_{A}\sum_{i=1}^{n}v_{A,i}-T_{B}\sum_{i=1}^{n}\frac{v_{A,i}^{2}}{v_{B,i}}\xrightarrow[\gamma\to\infty]{}+\infty\,.$

Moreover, for $\gamma>0$ small enough, we have $\mathcal{N}(\gamma)=[n]$ so
that

$\frac{f(\gamma)}{\gamma^{2}}=\gamma\left(T_{A}\sum_{i=1}^{n}\frac{v_{B,i}^{2}}{v_{A,i}}\right)-T_{B}\sum_{i=1}^{n}v_{B,i}\xrightarrow[\gamma\to
0]{}-T_{B}\sum_{i=1}^{n}v_{B,i}<0\,.$

Hence, by the intermediate value theorem, there exists $\gamma^{*}>0$ such
that $f(\gamma^{*})=0$. Moreover, observe that if one sets
$\mathcal{N}(\gamma)=[N]$ for $N\in\\{0,\dots,n\\}$, with the convention that
$[0]=\emptyset$, Equation (6) becomes a polynomial equation of degree three
with at most three solutions denoted $\gamma_{N,i},i=1,2,3$. Hence,
$\gamma^{*}\in\bigcup_{N=0}^{n}\\{\gamma_{N,1},\gamma_{N,2},\gamma_{N,3}\\}$
can take at most $3n+3$ values.

We now check the bounds on the possible values of $\gamma^{*}$. To that end,
recall from (6) that

$f(\gamma)=\sum_{i=1}^{n}\left(\gamma
T_{A}-T_{B}\frac{v_{A,i}}{v_{B,i}}\right)\cdot\left(\gamma^{2}\frac{v_{B,i}^{2}}{v_{A,i}}\wedge
v_{A,i}\right)\,.$

To prove the an upper bound on $\gamma^{*}$, observe that

$\gamma T_{A}-T_{B}\frac{v_{A,i}}{v_{B,i}}\geq
0\iff\gamma\geq\frac{T_{B}}{T_{A}}\frac{v_{A,i}}{v_{B,i}}\iff\gamma^{2}\frac{v_{B,i}^{2}}{v_{A,i}}\wedge
v_{A,i}\geq\left(\frac{T_{B}}{T_{A}}\right)^{2}v_{A,i}\wedge
v_{A,i}=\left(\frac{T_{B}}{T_{A}}\right)^{2}v_{A,i}\,,$

where the last identity follows from the assumption that $T_{B}\leq T_{A}$.

It yields

$f(\gamma)\geq\left(\frac{T_{B}}{T_{A}}\right)^{2}\sum_{i=1}^{n}\left(\gamma
T_{A}-T_{B}\frac{v_{A,i}}{v_{B,i}}\right)v_{A,i}=\left(\frac{T_{B}}{T_{A}}\right)^{2}\cdot\left(\gamma
T_{A}-T_{B}(1+\chi^{2}(v_{A}\|v_{B})\right)$

Therefore, if

$\gamma>\frac{T_{B}}{T_{A}}(1+\chi^{2}(v_{A}\|v_{B}))\,,$

then $f(\gamma)>0$, which yields the desired upper bound on $\gamma^{*}$.

To prove the lower bound on $\gamma^{*}$, we proceed essentially in the same
fashion:

$\gamma T_{A}-T_{B}\frac{v_{A,i}}{v_{B,i}}\leq
0\implies\gamma\leq\frac{T_{B}}{T_{A}}\frac{v_{A,i}}{v_{B,i}}\implies\gamma^{2}\frac{v_{B,i}^{2}}{v_{A,i}}\wedge
v_{A,i}=\gamma^{2}\frac{v_{B,i}^{2}}{v_{A,i}}\,.$

It yields

$f(\gamma)\leq\gamma^{2}\sum_{i=1}^{n}\left(\gamma
T_{A}-T_{B}\frac{v_{A,i}}{v_{B,i}}\right)\frac{v_{B,i}^{2}}{v_{A,i}}=\gamma^{2}\left((1+\chi^{2}(v_{B}\|v_{A}))\cdot\gamma
T_{A}-T_{B}\right)$

Therefore, if

$\gamma<\frac{T_{B}}{T_{A}}\frac{1}{1+\chi^{2}(v_{B}\|v_{A})}\,,$

then $f(\gamma)<0$, which yields the desired lower bound on $\gamma^{*}$.

To complete the proof of the proposition, it remains to observe that the
computational complexity is dominated by sorting reward ratios which costs
$\mathcal{O}(n\log n)$ operations since finding roots of degree three
polynomials for each of $\mathcal{O}(n)$ polynomials costs $\mathcal{O}(1)$
time.

e if $X_{B}=X_{A}$ and $\frac{v_{A,1}}{v_{B,1}}=\frac{v_{A,n}}{v_{B,n}}$,
which implies that $v_{A,i}=v_{B,i}$ (as they both sum to 1).

∎

###  B.3. Proofs of Proposition 4 and Theorem 5

####  B.3.1. Proof of Proposition 4

###### Proof.

Note first that (8) is necessary. Indeed, denote by $\max\in[k]$ any index
such that $b_{\max}=\max_{i}b_{i}$ and assume $Z_{1},\ldots,Z_{k}$ are coupled
so that

$\sum_{i\in[k]}Z_{i}=\sum_{i\in[k]}\mathds{E}[Z_{i}]=\frac{1}{2}\sum_{i\in[k]}p_{i}b_{i}\quad\text{a.s.}$

We have for $\delta>0$ small enough,

$p_{\max}\delta=\mathds{P}(Z_{\max}>b_{\max}(1-\delta))\leq\mathds{P}\big{(}\sum_{i\in[k]}Z_{i}>b_{\max}(1-\delta)\big{)}=\mathds{P}\big{(}\frac{1}{2}\sum_{i\in[k]}p_{i}b_{i}>b_{\max}(1-\delta)\big{)}\,.$

Hence

$\frac{1}{2}\sum_{i\in[k]}p_{i}b_{i}>b_{\max}(1-\delta)$

since the above deterministic inequality holds with positive probability, it
holds with probability one for all $\delta>0$. Letting $\delta\to 0$ yields
(8).

To show that (8) is sufficient, recall from [43, Theorem 3.2] that a
collection of random variables $Z_{1},\ldots,Z_{k}$ where $Z_{i}$ is a
continuous random variable, with non-increasing density function and supported
on the interval $[0,b_{i}]$ are jointly mixable if and only if

$\max_{i\in[k]}b_{i}\leq\sum_{i\in[k]}\mathds{E}[Z_{i}]\leq\sum_{i\in[k]}b_{i}-\max_{i\in[k]}b_{i}\,.$

In particular, if $\mathds{E}[Z_{i}]=p_{i}b_{i}/2$, these two inequalities
reduce to (8).

Unfortunately the $Z_{i}$s do not have a density so we use the following
approximation. For $i\in[k]$, let $\varepsilon<b_{i}$ and

$Z_{i}^{\varepsilon}\sim(1-q_{i}^{\varepsilon}){\sf
Unif}[0,\varepsilon]+q^{\varepsilon}_{i}{\sf Unif}[0,b_{i}]\,,$

where $q_{i}^{\varepsilon}\in(0,1)$ is chosen precisely so that
$Z_{i}^{\varepsilon}$ has the same expectation and the same support as
$Z_{i}$. Moreover, $Z_{i}^{\varepsilon}$ has a monotone decreasing density and
hence the $Z_{i}^{\varepsilon}$ are jointly mixable under condition (8)
resulting in a coupling $\pi^{\varepsilon}$ over the product space
$\prod_{i\in[k]}[0,b_{i}]$. By Prokhorov’s theorem, letting $\varepsilon\to 0$
implies that $Z_{1},\ldots,Z_{k}$ are jointly mixable.

∎

####  B.3.2. Proof of Theorem 5

###### Proof.

Recall that the marginal strategy $Z_{i}$ of player $A$ on battlefield $i$ has
a distribution of the form (7) with

$\displaystyle p_{i}$ $\displaystyle=1,$ $\displaystyle b_{i}$
$\displaystyle=\frac{\gamma^{*}v_{B,i}}{\lambda^{*}},$ $\displaystyle\text{if
}i$ $\displaystyle\in\mathcal{N}(\gamma^{*})$ $\displaystyle p_{i}$
$\displaystyle=\frac{v_{A,i}}{\gamma^{*}v_{B,i}},$ $\displaystyle b_{i}$
$\displaystyle=\frac{v_{A,i}}{\lambda^{*}},$ $\displaystyle\text{if }i$
$\displaystyle\notin\mathcal{N}(\gamma^{*})$

Plugging this values into (8) yields

$\max_{i\in\mathcal{N}(\gamma^{*})}\frac{\gamma^{*}v_{B,i}}{\lambda^{*}}\vee\max_{i\notin\mathcal{N}(\gamma^{*})}\frac{v_{A,i}}{\lambda^{*}}\leq\frac{1}{2}\left(\sum_{i\in\mathcal{N}(\gamma^{*})}\frac{\gamma^{*}v_{B,i}}{\lambda^{*}}+\sum_{i\notin\mathcal{N}(\gamma^{*})}\frac{v_{A,i}^{2}}{\lambda^{*}\gamma^{*}v_{B,i}}\right)=T_{A}\,,$

where the last equality follows from the saturation of the budget constraint
in (4). It is easy to check that

$\max_{i\in\mathcal{N}(\gamma^{*})}\gamma^{*}v_{B,i}\vee\max_{i\notin\mathcal{N}(\gamma^{*})}v_{A,i}=\max_{i\in[n]}(\gamma^{*}v_{B,i}\wedge
v_{A,i})$

Similarly, we get using (5) that

$\max_{i\in[n]}(\gamma^{*}v_{B,i}\wedge v_{A,i})\leq\lambda^{*}T_{B}\,,$

is a necessary and sufficient condition for mixability the Lotto strategy of
player $B$ into a Blotto strategy. The proof can then be concluded by
recalling that $T_{A}\geq T_{B}$.

∎

###  B.4. Proof of Corollary 7

###### Proof.

Using (5), we get

$\frac{\lambda^{*}T_{B}}{\gamma^{*}}=\frac{1}{2\gamma^{*}}\sum_{i=1}^{n}\frac{(\gamma^{*}v_{B,i})^{2}}{v_{A,i}}\wedge
v_{A,i}\geq\frac{1}{2}\left(\gamma^{*}\wedge\frac{1}{\gamma^{*}}\right)\sum_{i=1}^{n}\frac{v_{B,i}^{2}}{v_{A,i}}\wedge
v_{A,i}\,.$

Next, observe that

$\displaystyle\sum_{i=1}^{n}\frac{v_{B,i}^{2}}{v_{A,i}}\wedge v_{A,i}$
$\displaystyle=\sum_{i=1}^{n}\frac{v_{B,i}^{2}}{v_{A,i}}\mathds{1}(v_{A,i}>v_{B,i})+\sum_{i=1}^{n}v_{A,i}\mathds{1}(v_{A,i}\leq
v_{B,i})$
$\displaystyle=\sum_{i=1}^{n}\frac{v_{B,i}^{2}}{v_{A,i}}\mathds{1}(v_{A,i}>v_{B,i})+1-\sum_{i=1}^{n}v_{A,i}\mathds{1}(v_{A,i}>v_{B,i})$
$\displaystyle=1-\sum_{i=1}^{n}v_{A,i}\left(1-\left(\frac{v_{B,i}}{v_{A,i}}\right)^{2}\right)\mathds{1}(v_{A,i}>v_{B,i})\,.$

Noting now that $1-x^{2}\leq 2-2x$ for $x\in[0,1]$, we get for
$x=v_{B,i}/v_{A,i}$ that

$\displaystyle\sum_{i=1}^{n}\frac{v_{B,i}^{2}}{v_{A,i}}\wedge v_{A,i}$
$\displaystyle\geq
1-\sum_{i=1}^{n}v_{A,i}\left(1-\frac{v_{B,i}}{v_{A,i}}\right)\mathds{1}(v_{A,i}>v_{B,i})=1-{\sf
TV}(v_{A},v_{B})\,,$

where ${\sf TV}$ denotes the total variation distance and is defined as

${\sf TV}(v_{A},v_{B})=\frac{1}{2}\sum_{i=1}^{n}|v_{A,i}-v_{B,i}|\,.$

Using Pinsker’s and Jensen’s inequalities, see, e.g.,[40, Chapter 2], we get
the classical result

${\sf
TV}(v_{A},v_{B})\leq\frac{1}{2}\sqrt{\chi^{2}(v_{B}\|v_{A})}\leq\frac{r}{2}$

Next, note that Proposition 1 yields

$\gamma^{*}\wedge\frac{1}{\gamma^{*}}\geq\frac{T_{B}}{T_{A}}\frac{1}{1+\chi^{2}(v_{B}\|v_{A})}\wedge\frac{T_{A}}{T_{B}}\frac{1}{1+\chi^{2}(v_{A}\|v_{B})}\geq\frac{T_{B}}{T_{A}}\frac{1}{1+r^{2}}\,.$

Hence we have established that

$\displaystyle\frac{\lambda^{*}T_{B}}{\gamma^{*}}$
$\displaystyle\geq\frac{T_{B}}{2T_{A}}\frac{1-r/2}{1+r^{2}}\geq\frac{T_{B}}{2T_{A}}(1-r)\,.$

Together with (9), this completes our proof.

∎

###  B.5. Proof of Lemma 1 and Algorithm Decomp

Data: length vector $\mathbf{b}\in\mathds{R}_{+}^{n}$, budget $T$, weights
vector $\mathbf{p}=(p_{i})_{i\in[n]}\in[0,1]^{n}$;

Result: (at most) $n$ vectors $\mathbf{p}^{(k)}\in[0,1]^{n}$ and weights
$q_{k}\in[0,1]$;

$k\leftarrow 0$ $\triangleright$ Initialization

while  _${\rm supp}(\mathbf{p}) >2$_ do

$k\leftarrow k+1$;

$(\mathbf{p}^{(k)},\bar{\mathbf{p}}^{(k)},\theta_{k})\leftarrow\textsc{Extremize}(\mathbf{b},T,\mathbf{p})$
$\triangleright$ Find an extreme point $\mathbf{p}^{(k)}$

$\mathbf{p}\leftarrow\bar{\mathbf{p}}^{(k)}$;

$q_{k}\leftarrow q_{k-1}\frac{\theta_{k}}{\theta_{k-1}}(1-\theta_{k-1})$
$\triangleright$ Compute convex weight of $\mathbf{p}^{(k)}$

end while

Output: $\\{(\mathbf{p}^{(j)},q_{j})\,;j\in[k]\\}$ $\triangleright$ (a
coupling with its convex weight)

ALGORITHM 3 Decomp

###### Proof.

Throughout this proof we write

$p_{i}=\left\\{\begin{array}[]{cl}1,&\text{if }i\in\mathcal{N}(\gamma^{*})\\\
\frac{v_{A,i}}{\gamma^{*}v_{B,i}},&\text{if
}i\notin\mathcal{N}(\gamma^{*})\end{array}\right.$

so that the $i$th marginal of $\pi$ is given by

$(1-p_{i})\delta_{0}+p_{i}{\sf Unif}\left[0,\frac{\gamma^{*}v_{B,i}\wedge
v_{A,i}}{\lambda^{*}}\right]\,.$

Note that (10) consists in representing $\pi$ as a convex combination of
couplings. To obtain this representation we are going to appeal to
Carathéodory’s theorem. However the latter requires finite dimension so we
first make the following observation: the map
$\mathbf{p}^{(k)}=(p_{1}^{(k)},\ldots,p_{n}^{(k)})\mapsto\pi_{k}$, (resp.
$\mathbf{p}=(p_{1},\ldots,p_{n})\mapsto\pi$) is linear and injective.
Therefore, (10) is sufficient to produce the decomposition

(23) $\mathbf{p}=\sum_{k}q_{k}\mathbf{p}^{(k)}\,.$

Furthermore, we need $\pi_{k}$ to be satisfy the budget constraint (3) of the
Lotto game. The saturation of this constraint translates into the constraint
$\mathbf{p}^{k}\in\mathcal{H},k=1,\ldots,n$, where $\mathcal{H}$ is the affine
hyperplane in $\mathds{R}^{n}$ defined by

(24)
$\mathcal{H}=\left\\{x\in\mathds{R}^{n}\,:\,\sum_{i=1}^{n}x_{i}\frac{\gamma^{*}v_{B,i}\wedge
v_{A,i}}{2\lambda^{*}}=T_{A}\right\\}$

As a result, we must ensure that
$\mathbf{p}^{(k)}\in\mathcal{C}_{n}=\mathcal{H}\cap[0,1]^{n}$; see Figure 1
for a representation of this constraint set. Since this set has dimension
$n-1$, Carathédory’s theorem ensures the existence of a decomposition (23)
where $\mathbf{p}^{(k)}$ are extreme points of $\mathcal{C}_{n}$. In
particular, each such extreme point has at most one coordinate in $(0,1)$;
this completes the proof of point 1.

Note that (23) readily ensures that $\pi$ is a solution for the Lotto game.
Moreover, since $\mathbf{p}^{(k)}\in\mathcal{H}$ by construction, we have that
marginals of $\pi_{k}$ automatically satisfy the mixability condition. Hence,
we can choose $\pi_{k}$ to be a joint mix; this completes the proof of point
2. As stated above, this readily implies that $\pi$ defined in (10) is a joint
mix and hence a solution for the Blotto game; this completes the proof of
point 3.

It remains to find an efficient algorithm that outputs decomposition (10). The
algorithm is initialized at
$\mathbf{p}\in\mathcal{C}_{n}=\mathcal{H}\cap[0,1]^{n}$. From there, we use
Lemma 2 to construct two points
$\mathbf{p}^{(1)},\bar{\mathbf{p}}^{(1)}\in\mathcal{H}\cap\partial[0,1]^{n}$
such that
$\mathbf{p}=\theta_{1}\mathbf{p}^{(1)}+(1-\theta_{1})\bar{\mathbf{p}}^{(1)}$,
for some $\theta_{1}\in[0,1]$, where $\mathbf{p}^{(1)}$ is an extreme point of
$\mathcal{C}_{n}$ and $\bar{\mathbf{p}}^{(1)}$ belongs to a face
$\mathcal{F}_{n_{1}}$ of dimension $n_{1}<n$. We repeat this procedure as
follows. Define by $\mathcal{C}_{n_{1}}=\mathcal{H}\cap\mathcal{F}_{n_{1}}$ so
that $\bar{\mathbf{p}}^{(1)}\in\mathcal{C}_{n_{1}}$. Hence, using again Lemma
2, it may be decomposed as
$\bar{\mathbf{p}}^{(1)}=\theta_{2}\mathbf{p}^{(2)}+(1-\theta_{2})\bar{\mathbf{p}}^{(2)}$
for some $\theta_{2}\in[0,1]$ and $\mathbf{p}^{(2)}$ is an extreme point of
$\mathcal{C}_{n}$ while $\bar{\mathbf{p}}^{(2)}\in\mathcal{C}_{n_{2}}$, where
$\mathcal{C}_{n_{2}}$ is the intersection of $\mathcal{H}$ with a face
$\mathcal{F}_{n_{2}}$ of $[0,1]^{n}$ of dimension $n_{2}<n_{1}$. Moreover,

$\mathbf{p}=\theta_{1}\mathbf{p}^{(1)}+(1-\theta_{1})\theta_{2}\mathbf{p}^{(2)}+(1-\theta_{1})(1-\theta_{2})\bar{\mathbf{p}}^{(2)}$

Iterating this procedure yields the decomposition

$\mathbf{p}=\sum_{i=1}^{N+1}\theta_{i}\prod_{j\leq
i-1}(1-\theta_{j})\mathbf{p}^{(i)}\,,$

with the convention that $\theta_{N+1}=1$ and where $N\leq n$ and the
$\mathbf{p}^{(j)}$s are extreme points of $\mathcal{C}_{n}$. Moreover, one can
readily check that for any sequence $\theta_{1},\ldots\theta_{N}\in[0,1]$,
$\theta_{N+1}=1$, it holds

$\sum_{i=1}^{N+1}\theta_{i}\prod_{j\leq i-1}(1-\theta_{j})=1\,,$

which gives the result by defining $q_{k}=\theta_{k}\prod_{j\leq
k-1}(1-\theta_{j})$.

As we appealed at most $n$ times to Lemma 2, the overall complexity of this
algorithm is of order $\mathcal{O}(n^{2}\log n)$. ∎

$\mathcal{C}_{n}$$\mathcal{H}$$\mathbf{p}^{(1)}$$\mathbf{p}^{(2)}$$\mathbf{p}^{(3)}{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}=\,\bar{\mathbf{p}}^{(2)}}$$\mathbf{p}$$\bar{\mathbf{p}}^{(1)}$
Figure 1. Starting from $\mathbf{p}$, the first step computes a first extreme
point $\mathbf{p}^{(1)}$. Then $\mathbf{p}$ is written as a convex combination
of $\mathbf{p}^{(1)}$ and $\bar{\mathbf{p}}^{(1)}$. The latter is decomposed
(iteratively) into $\mathbf{p}^{(2)}$ and then $\mathbf{p}^{(3)}$.

###  B.6. Proof of Lemma 2 and Algorithm Decomp

Data: vector $\mathbf{b}=(b_{i})_{i\in[n]}\in\mathds{R}^{n}$, budget
$T\in\mathds{R}_{+}$, vector $x\in\mathds{R}^{n}$;

Result: 2 vectors $y,\bar{y}$, convex weight $\theta$;

$t\leftarrow 0$; $k\leftarrow 0$, $z\leftarrow
x\odot\mathds{1}_{\overline{{\rm supp}(x)}}$ $\triangleright$ Initialization

while  _$t <T$_ do

$k\leftarrow k+1$; $z\leftarrow z+\mathds{1}_{\\{k\\}}\odot\mathds{1}_{{\rm
supp}(x)}$; $t\leftarrow z^{\top}\mathbf{b}$ $\triangleright$ Find the index
with non $\\{0,1\\}$ component

end while

$\varepsilon^{\prime}\leftarrow\frac{t-T}{b_{k}}$; $y\leftarrow
z-\varepsilon^{\prime}\mathds{1}_{\\{k\\}}$ $\triangleright$ Compute
explicitly the extreme point $y$

$\delta\leftarrow\min_{i\in\mathcal{S}}\frac{\mathds{1}\\{x_{i}\geq
y_{i}\\}-x_{i}}{x_{i}-y_{i}}$; $\theta\leftarrow\frac{\delta}{1+\delta}$;

$\bar{y}\leftarrow x+\eta(x-y)$;

Output: $(y,\bar{y},\theta)$ $\triangleright$ (two vectors, one convex weight)

ALGORITHM 4 Extremize

###### Proof.

Assume that the coordinates of $\ell$ are sorted as
$\ell_{1}\leq\ell_{2}\leq\ldots\leq\ell_{n}$. For any subset
$\mathcal{S}\subset[n]$, we denote its associated indicator vector by
$\mathds{1}_{\mathcal{S}}=(\mathds{1}\\{i\in\mathcal{S}\\})_{i}\in\\{0,1\\}^{n}$.

First, notice that there exists some $\varepsilon_{k}\in[0,1]$ such that the
following vector $y$ belongs to $\mathcal{C}_{n}\cap\mathcal{H}$:

$y:=x\odot\mathds{1}_{\overline{{\rm
supp}}(x)}+(\underbrace{1,1,\ldots,1}_{k-1\text{
terms}},\varepsilon_{k},0,\ldots,0)\odot\mathds{1}_{{\rm supp}(x)},$

where $\overline{{\rm supp}}(x)=[n]\backslash{\rm supp}(x)$ is the complement
of the support of $x$. The reason is simply that

$x\odot\mathds{1}_{\overline{{\rm supp}}(x)}\leq x\leq
x\odot\mathds{1}_{\overline{{\rm supp}}(x)}+(1,\ldots,1)\odot\mathds{1}_{{\rm
supp}(x)}\ ,$

where the inequalities are component wise.

We now introduce $\bar{y}=x+\delta(x-y),$ where $\delta\in\mathds{R}_{+}$ is
defined by

$\delta=\delta_{i^{*}}:=\min_{i\in{\rm supp}(x)}\delta_{i},\quad\text{with}\
\delta_{i}:=\frac{\mathds{1}\\{x_{i}\geq y_{i}\\}-x_{i}}{x_{i}-y_{i}}\ .$

Then $\bar{y}$ belongs to $\mathcal{H}$ as $x$ and $y$ are two vectors of this
affine hyperplane. Moreover, as $\eta_{i^{*}}=\min\eta_{i}$, it also holds
that $\bar{y}\in[0,1]^{n}$ and $\bar{y}_{i^{*}}=\mathds{1}\\{x_{i^{*}}\geq
y_{i*}\\}$, and therefore ${\rm supp}(\bar{y})\subset{\rm
supp}(x)\backslash\\{i^{*}\\}$. Finally, one just needs to define
$\theta=\delta/(1+\delta)$.

The construction of those quantities requires sorting the coordinates of
$\ell$, finding the $k$-th coordinate of $y$, say, by binary search (computing
the value of $\varepsilon_{k}$ is immediate as the value of $y^{\top}\ell$ is
linear in $p_{k}$) and finding $i^{*}$. ∎

###  B.7. Proof of Lemma 3 and Algorithm Reduc

Data: length vector $\mathbf{b}\in\mathds{R}_{+}^{n}$, weights
$\mathbf{p}\in[0,1]^{n}$;

Result: 5 sets of indices;

$\mathcal{I}_{0}\leftarrow\emptyset$, $\mathcal{I}_{1}\leftarrow[n]$,
$\mathcal{I}_{2}\leftarrow\emptyset$, $\mathcal{I}_{3}\leftarrow\emptyset$,
$\mathcal{I}_{4}\leftarrow\emptyset$ $\triangleright$ Initialization of sets

for  _$i\in[n]$ _ do

if  _$p_{i}=1$_ then

$\mathcal{I}_{0}\leftarrow\mathcal{I}_{0}\cup\\{i\\}$,
$\mathcal{I}_{1}\leftarrow\mathcal{I}_{1}\backslash\\{i\\}$ $\triangleright$
Dirac masses not treated, index removed

else

if  _$p_{i}\in(0,1)$_ then

$\mathcal{I}_{n}\leftarrow\\{i\\}$,
$\mathcal{I}_{1}\leftarrow\mathcal{I}_{1}\backslash\\{i\\}$ $\triangleright$
At most one strict mixture

else

$\mathcal{I}(i)\leftarrow\\{i\\}$ $\triangleright$ End of initialization

end if

end if

end for

while  _$|\mathcal{I}_{1}| >3$_ do

$i_{1}\leftarrow\arg\min_{i\in\mathcal{I}_{1}}b_{i}$,
$\mathcal{I}_{1}\leftarrow\mathcal{I}_{1}\backslash\\{i_{1}\\}$,
$i_{2}\leftarrow\arg\min_{i\in\mathcal{I}_{1}}b_{i}$ $\triangleright$
$i_{1},i_{2}$: 2 smallest uniform lengths $b_{i_{2}}\leftarrow
b_{i_{2}}+b_{i_{1}}$,
$\mathcal{I}(i_{2})\leftarrow\mathcal{I}(i_{2})\cup\mathcal{I}(i_{1})$
$\triangleright$ 2 uniforms combined in 1

end while

$m=|\mathcal{I}_{1}|$, denote
$\mathcal{I}_{1}=\\{i^{*}_{1},\ldots,i^{*}_{m}\\}$;

for  _$j\in[m]$_ do

$\mathcal{I}_{j}\leftarrow\mathcal{I}(i^{*}_{j})$ $\triangleright$ (At most) 3
sets of combined indices

end for

Output:
$(\mathcal{I}_{0},\mathcal{I}_{1},\mathcal{I}_{2},\mathcal{I}_{3},\mathcal{I}_{4})$
$\triangleright$ (Dirac, 3 sets of uniforms - possibly empty-, a strict
mixture)

ALGORITHM 5 Reduc

###### Proof.

Write for simplicity $X_{i}=X_{A,i}$ and

$X_{i}\sim(1-p_{i})\delta_{0}+p_{i}{\sf Unif}[0,b_{i}]\,,$

where $p_{i}\in\\{0,1\\}$ for $i\in[n-1]$, $p_{n}\in[0,1]$, and
$b_{i}=({\gamma^{*}v_{B,i}\wedge v_{A,i}})/{\lambda^{*}}$. If $p_{i}=0$, then
$X_{i}$ is almost surely equal to 0 and this random variable can be removed
from the analysis; we might therefore assume that $p_{i}>0$ for all $i$.

The joint mixability condition (8) rewrites as

(25) $2\max_{k}b_{k}\leq\sum_{i=1}^{n-1}b_{i}+p_{n}b_{n}$

Without loss of generality, assume that $b_{1}\leq b_{2}\leq\ldots\leq
b_{n-1}$ and define $X_{12}\sim{\sf Unif}[0,b_{1}+b_{2}]$. Note that
$\\{X_{1},X_{2},-X_{12}\\}$ are jointly mixable (for instance, consider
$X_{1}=\frac{b_{1}}{b_{1}+b_{2}}X_{12}$ and
$X_{2}=\frac{b_{2}}{b_{1}+b_{2}}X_{12}$), and
$\\{X_{12},X_{3},\ldots,X_{n}\\}$ are also jointly mixable if

(26) $2\max\\{\max_{k\geq
3}b_{k},b_{1}+b_{2}\\}\leq\sum_{i=1}^{n-1}b_{i}+p_{n}b_{n}$

On the one hand, if $b_{1}+b_{2}\leq b_{n-1}$ then (26) follows readily from
(25). On the other hand, if $b_{1}+b_{2}>b_{n-1}$ and $n-1\geq 4$ then

$2(b_{1}+b_{2})\leq b_{1}+b_{2}+b_{3}+b_{4}\leq
b_{1}+b_{2}+\sum_{k=3}^{n-1}b_{k}+t^{(n)}b_{n}$

so that (25) is satisfied. The result follows from sequentially iterating this
construction. Indeed, recall that $X_{12}$ is a variable created by mixing
together $X_{1}$ and $X_{2}$. At a further step, this variable might be mixed
again with another one, ending up with a set of, at least, 3 variables mixed
together. At the end of the procedure, there are at most 3 remaining random
variables $Y_{j}$, that are joint mix of (disjoints) subsets of $X_{i}$.

We denote by $\mathcal{I}_{j}$ the set of indices of variables that are mixed
to form $Y_{j}$ and, for any index $i\in\mathcal{I}_{j}$, we just need to
define $\theta_{i}=\frac{b_{i}}{\sum_{k\in\mathcal{I}_{j}}b_{k}}$. ∎

###  B.8. Algorithm Discretize

Data: 4 lengths $b^{*}_{i}\in\mathds{R}_{+}$, positive weight $p_{4}\in(0,1)$,
discretization parameter $h$;

Result: 4 vectors $\mu_{i}\in\mathds{R}_{+}^{d_{i}}$ with
$d_{i}=\lfloor\frac{b^{*}_{i}}{h}\rfloor+1$;

for  _$i\in[3]$_ do

$\mu_{i}\leftarrow\frac{h}{b^{*}_{i}}\big{(}\underbrace{1,\ldots,1}_{\lfloor\frac{b^{*}_{i}}{h}\rfloor\text{times}},\frac{b^{*}_{1}}{h}-\lfloor\frac{h}{b^{*}_{1}}\rfloor\big{)}$

end for

$\mu_{4}\leftarrow
p_{4}\frac{h}{b^{*}_{i}}\big{(}\frac{b^{*}_{4}}{h}-\lfloor\frac{h}{b^{*}_{4}}\rfloor,\underbrace{1,\ldots,1}_{\lfloor\frac{b^{*}_{4}}{h}\rfloor\text{times}}\big{)}+(1-p_{4})(0,\ldots,0,1)$;

Output: $(\mu_{1},\mu_{2},\mu_{3},\mu_{4})$ $\triangleright$ (4 discrete
ditributions)

ALGORITHM 6 Discretize

###  B.9. Algorithm Sinkhorn

Data: Marginals $\mu_{j}\in\mathds{R}^{d_{j}},j=1,\ldots 4$;

Precision level $\eta>0$;

Result: A Coupling $\Gamma$, represented by
$(\xi_{1},\xi_{2},\xi_{3},\xi_{4})\in\mathds{R}^{d_{1}}\times\mathds{R}^{d_{2}}\times\mathds{R}^{d_{3}}\times\mathds{R}^{d_{4}}$,
with marginals such that
$\sum_{i=1}^{4}\|\bar{\Gamma}^{(i)}-\mu_{i}\|_{1}\leq\eta$;

$\Gamma\leftarrow{\bf 1}\in\mathds{R}^{d_{1}\times d_{2}\times d_{3}\times 3}$
$\triangleright$ Initialization

$\xi_{1}\leftarrow{\bf 1}\in\mathds{R}^{d_{1}}$; $\xi_{2}\leftarrow{\bf
1}\in\mathds{R}^{d_{2}}$; $\xi_{3}\leftarrow{\bf 1}\in\mathds{R}^{d_{3}}$;
$\xi_{4}\leftarrow{\bf 1}\in\mathds{R}^{d_{4}}$;

while  _$\sum_{i\in[4]}\|\mu_{i}-\Gamma_{i}\|_{1} >\eta$_ do

$\displaystyle\tau\leftarrow\operatorname*{\mathrm{argmax}}_{i\in[4]}\operatorname{\mathsf{KL}}(\mu_{i}\|\Gamma_{i})$;

$\displaystyle\xi_{\tau}\leftarrow\xi_{\tau}\odot\mu_{\tau}\oslash\bar{\Gamma}_{\tau}$
$\triangleright$ Matrix scaling

$\Gamma_{ijke}=\xi_{1,i}\cdot\xi_{2,j}\cdot\xi_{3,k}\cdot\xi_{4,i+j+k+e}\,,\
\forall i,j,k,e$ $\triangleright$ Computation of coupling

end while

Output: $(\xi_{1},\xi_{2},\xi_{3},\xi_{4})$

ALGORITHM 7 Sinkhorn

###  B.10. Algorithm Sample

Data: Coupling $(\xi_{1},\xi_{2},\xi_{3},\xi_{4})$, budget
$T\in\mathds{R}_{+}$, length vector $\mathbf{b}\in\mathds{R}_{+}^{n}$, sets of
indices
$(\mathcal{I}_{0},\mathcal{I}_{1},\mathcal{I}_{2},\mathcal{I}_{3},\mathcal{I}_{4})$,
precision $h$ ;

Result: An allocation vector $X\in\mathds{R}_{+}^{n}$;

Set $\\{j_{4}\\}=\mathcal{I}_{4}$; $b_{4}^{*}\leftarrow b_{j_{4}}$
$\triangleright$ Initialization

Sample $\tilde{Y}_{1}\sim\xi_{1}$, $\tilde{Y}_{2}\sim\xi_{2}$,
$\tilde{Y}_{3}\sim\xi_{3}$ $\triangleright$ Sampling from computed coupling

Sample $\varepsilon=e\in\\{0,1,2\\}$ with proba.
$\xi_{4,\tilde{Y}_{1}+\tilde{Y}_{2}+\tilde{Y}_{3}+e}$;

Sample $U\sim{\sf Unif}[0,1]$ $\triangleright$ smoothing

for  _$i\in[3]$_ do

$b_{i}^{*}\leftarrow\sum_{j\in\mathcal{I}_{i}}b_{j}$;

$Y^{\prime}_{i}\leftarrow(\tilde{Y}_{i}+\frac{\varepsilon}{3}+\frac{U}{3})h\wedge
b_{i}^{*}$

end for

$S\leftarrow Y^{\prime}_{1}+Y^{\prime}_{2}+Y^{\prime}_{3}$;

$\zeta\leftarrow\mathds{1}\\{S>T\\}\frac{T-S}{3}+\mathds{1}\\{S<T-b^{*}_{4}\\}\frac{T-b^{*}_{4}-S}{3}$;

for  _$i\in[3]$_ do

$\bar{Y}_{i}\leftarrow Y^{\prime}_{i}+\zeta$;

for  _$j\in\mathcal{I}_{i}$_ do

$X_{j}=\frac{b_{j}}{b^{*}_{i}}\bar{Y}_{i}$ $\triangleright$ Reconstruction of
uniforms

end for

end for

for  _$j\in\mathcal{I}_{0}$_ do

$X_{j}=0$ $\triangleright$ Dirac masses set at 0

end for

$X_{j_{4}}=T-(\bar{Y}_{1}+\bar{Y}_{2}+\bar{Y}_{3})$ $\triangleright$ Budget
saturation

Output: $X$

ALGORITHM 8 Sample