# Keep them guessing: The value of randomized resource assignments in General
Lotto games

Keith Paarporn, Rahul Chandan, Mahnoosh Alizadeh, Jason R. Marden

(Department of Electrical and Computer Engineering, University of California
Santa Barbara
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>)

###### Abstract

In this paper, we consider a class of problems where a commander must decide
how to assign costly resources to independent sub-colonels. Each sub-colonel
engages in competition against an opponent, where it is tasked with allocating
its assigned resources towards multiple battlefields. The commander’s
performance is measured by the cumulative rewards attained by the sub-
colonels. Here, we consider General Lotto games, a popular variant of the
well-known Colonel Blotto game, as the underlying model of competition. While
optimal deterministic assignments have been characterized in this context, we
completely characterize optimal randomized assignments. Randomizing induces
informational asymmetries in each competition, where the opponents become
uncertain about the sub-colonels’ actual assigned endowments. We find that
randomized assignments can give up to a four-fold performance improvement over
deterministic ones, when there are costs associated with utilizing resources.
When there are no associated costs, randomization does not offer any
performance improvements. In order to characterize the optimal randomized
assignments, we provide a complete and novel equilibrium analysis of the
underlying incomplete and asymmetric information General Lotto games induced
from randomized assignments.

##  1 Introduction

A central problem in strategic decision-making in adversarial environments is
determining how to assign limited resources towards multiple competitions. It
is consequential to a variety of application domains, including the security
of cyber-physical systems, surveillance, and public safety [1, 47, 44, 42].
For example, a system administrator must decide how to allocate security
resources to protect multiple servers from cyber attacks. Strategies in
military conflicts are also largely based on resource allocation decisions. It
is often the case that a single, centralized decision-maker is not entirely
responsible for how all the resources are ultimately deployed in the
competitions. This can be due to several reasons: it may not have the
capability to operate in multiple competitions on its own because of
computational, coordination, or geographical constraints. Additionally, a
hierarchical decision-making structure may already be in place. As such, we
are interested in the problem of how a commander should assign resources to
multiple independent sub-colonels. The sub-colonels are then tasked with
allocating their assigned resources in competition against opponents. The
commander’s objective is to formulate an assignment so as to maximize the sub-
colonels’ cumulative performance from these competitions.

The randomization of resource assignments to the sub-colonels plays a
significant role here because it causes opponents to be uncertain about the
actual implemented assignment. Essentially, the commander can exploit
informational asymmetries by being unpredictable. Indeed, security systems are
substantially improved from implementing such strategies. Algorithms have been
developed to calculate randomized assignments of security forces, and are
implemented in several public safety domains such as airport security, border
control, and wildlife protection [35, 42, 49, 48].

In this paper, we are interested in characterizing the performance improvement
that randomized assignments offer over deterministic assignments. In our
formulation, we consider General Lotto games as the underlying model of each
competition between sub-colonels and opponents. The General Lotto game is a
popular variant of the well-known Colonel Blotto game, a canonical model of
competitive resource allocation. By randomizing its assignment, the commander
can induce incomplete and asymmetric information Lotto games, in which the
opponents are uncertain about the sub-colonels’ actual resource assignment. We
are interested in whether the commander can exploit such informational
asymmetries to its advantage. Figure 1 depicts the scenario under
consideration.

Figure 1:  (Left) The commander assignment problem. The commander must decide
how to assign costly resources to multiple competitions (two shown here).
Here, we suppose the commander has access to a total of $A$ resources. An
assignment allocates, in expectation, up to $A$ resources to two sub-colonels.
The sub-colonels’ endowments $A_{i}$ ($i=1,2$) are drawn from the commander’s
(possibly randomized) assignment strategy. Sub-colonel $i$ then engages in a
(simultaneous move) General Lotto game against opponent $i$. The performance
of the commander is the cumulative payoff associated with the two
competitions. (Right) The opponents observe the commander’s strategy. In the
case that the assignment to sub-colonel $i$ is deterministic, the competition
between opponent and sub-colonel $i$ becomes a complete information General
Lotto game. If the assignment to sub-colonel $i$ is randomized, the opponent
does not observe its true realized endowment. Hence, they engage in an
incomplete information General Lotto game. The goal of this paper is to derive
the optimal randomized assignment strategies for the commander, and
characterize the performance improvement over deterministic assignments.

In similar formulations, optimal _deterministic_ assignments have been
considered and derived by leveraging equilibrium characterizations of complete
information General Lotto games [26], which are already well-established in
the literature [21, 29]. Here, we completely characterize the commander’s
optimal _randomized_ assignments. To do so, we provide novel and complete
equilibrium solutions for the underlying General Lotto games with incomplete
and asymmetric information. We highlight that an optimal randomized assignment
can give up to a four-fold performance improvement over a corresponding
optimal deterministic assignment.

The Colonel Blotto game models two competing players that strategically
allocate their endowed resources across a set of battlefields. Solutions are
known to be challenging to derive, and characterizations for the most general
settings are still unknown [9, 17, 37, 39, 43]. The General Lotto game offers
more analytical tractability because it relaxes budget support constraints
that are required for mixed strategies in Blotto games [21, 29]. For this
reason, Lotto games are versatile models of competition which have been
utilized to study more complex adversarial settings [26, 19, 18, 14].

The paper is organized as follows. We formulate the commander assignment
problem in Section 2 and summarize our contributions. We state our main
results in Section 3. Section 4 provides the novel and complete equilibrium
payoffs from the underlying General Lotto games with incomplete and asymmetric
information. Leveraging these results, the optimal assignment strategies are
derived in Appendix A and B. Analytical techniques used to characterize the
equilibrium payoffs from Section 4 are detailed in Appendix C.

##  2 Problem formulation

Consider the following two-stage scenario. A commander is responsible for
assigning resources to two sub-colonels engaged in separate competitions
against respective opponents – see Figure 1. We consider General Lotto games
as the underlying model of competition. In stage 1, the commander chooses an
assignment strategy, which can be deterministic or randomized. The strategy
becomes common knowledge to the sub-colonels and the opponents. The commander
has a resource budget of $A>0$. A _deterministic_ assignment strategy is any
pair $(A_{1},A_{2})\in\mathbb{R}_{\geq 0}^{2}$ that satisfies
$A_{1}+A_{2}\leq{A}$. It endows sub-colonel $i$ with $A_{i}$ resources. The
commander pays the cost $c\cdot(A_{1}+A_{2})$, where $c\geq 0$ is its per-unit
cost for assigning resources.

In stage 2, sub-colonel $i$ contests a set of $n$ battlefields against
opponent $i$ in a General Lotto game, which we will soon define. The
battlefield valuations are given by a vector
$\boldsymbol{v}_{i}\in\mathbb{R}_{+}^{n}$. In particular, sub-colonel $i$ must
decide how to allocate its endowed resources among the set of battlefields
$\boldsymbol{v}_{i}$. Simultaneously, opponent $i$ decides how to allocate its
own resources to $\boldsymbol{v}_{i}$. Here, opponent $i$ has a per-unit cost
$c_{i}\geq 0$ associated with utilizing resources, and it has a budget of
$B_{i}>0$ resources. These parameters are common knowledge to the commander
and sub-colonels.

The resource assignment problem centers on how the commander should assign
resources in stage 1 so as to maximize the sub-colonels’ cumulative payoffs
from both competitions in stage 2, assuming the sub-colonels and opponents
implement equilibrium strategies in their respective (simultaneous move)
General Lotto games. A deterministic assignment strategy induces General Lotto
games of complete information in stage 2, for which equilibrium payoffs are
well known [21, 29]. Let us denote
$\pi_{i}(A_{i},B_{i},c_{i}|\boldsymbol{v}_{i})$ as the equilibrium payoff to
sub-colonel $i$ (we will detail its characterization in Section 4.2) in its
corresponding General Lotto game. When restricted to deterministic
assignments, the commander’s optimization problem is

$W_{\text{d}}^{*}:=\max_{A_{1},A_{2}:A_{1}+A_{2}\leq
A}\left\\{\pi_{1}(A_{1},B_{1},c_{1}|\boldsymbol{v}_{1})+\pi_{2}(A_{2},{B}_{2},c_{2}|\boldsymbol{v}_{2})-c\cdot(A_{1}+A_{2})\right\\}$
(2.1)

We note the above formulation encompasses special settings that have been the
focus of existing works in the literature. Notably,

  * •

The _fixed budget setting_. Here, there are zero costs associated with using
the resource budgets ${A}$, ${B}_{i}<\infty$, i.e. $c=c_{i}=0$ for $i=1,2$.
The solution of (2.1) under this setting was the focus of [26], where full
solutions are provided.

  * •

The _per-unit cost setting_. Here, the commander and opponents have costs
$c>0$ and $c_{i}>0$. There are no resource budget limits, i.e.
${A},B_{i}=\infty$. While (2.1) under this setting has not been considered in
the literature (to the best of our knowledge), formulations of two player
Colonel Blotto games are commonly analyzed under similar linear cost models
[30, 27, 22, 28].

###  2.1 Bernoulli randomized assignments

Now, we will consider a class of randomized assignment strategies. In this
paper, the assignment strategies available to the commander are the set of
probability distributions $\mathbb{P}$ on assignments
$(A_{1},A_{2})\in\mathbb{R}_{\geq 0}^{2}$ such that each marginal distribution
$\mathbb{P}_{i}$, $i=1,2$ has at most two values in its support111This class
of randomized assignment strategies is considered due to all of our results
for the underlying incomplete information General Lotto games applying to two-
type budget uncertainty. It is of interest to extend these results to more
than two randomized budget levels. We note there are analytical challenges
associated with these extensions, which we detail in Appendix C.. Furthermore,
we require that the commander assigns no more than ${A}$ resources to the two
sub-colonels _in expectation_ :

$\mathbb{E}_{\mathbb{P}}[A_{1}+A_{2}]=\sum_{(A_{1},A_{2})\in\text{supp}(\mathbb{P})}\mathbb{P}(A_{1},A_{2})\cdot(A_{1}+A_{2})\leq{A}.$
(2.2)

Let us denote $\mathcal{P}({A})$ as the set of all such distributions
$\mathbb{P}$. As such, the marginal distribution $\mathbb{P}_{i}$ is
associated with a probability $p_{i}:=\mathbb{P}_{i}(A_{i}^{(1)})$ on a high
endowment $A_{i}^{(1)}$, and the probability $1-p_{i}$ on a low endowment
$A_{i}^{(2)}$ for sub-colonel $i$, where $A_{i}^{(1)}\geq A_{i}^{(2)}$. We
will often write the marginal as a tuple,
$\mathbb{P}_{i}=(A_{i}^{(1)},A_{i}^{(2)},p_{i})$, to explicitly represent the
distribution.

The commander chooses a distribution $\mathbb{P}\in\mathcal{P}({A})$ in stage
1, which the opponents observe. In stage 2, the sub-colonels’ resource
assignments are drawn according to $\mathbb{P}$, and sub-colonel $i$ decides
how to allocate its endowed resources to $\boldsymbol{v}_{i}$. Opponent $i$
must also deploy simultaneously, where it has a per-unit cost $c_{i}\geq 0$
and budget $B_{i}>0$. However, opponent $i$ does not observe the actual
realization of the assignments, but knows the marginal distribution
$\mathbb{P}_{i}$. As a result, opponent $i$ must compete in stage 2 without
knowing sub-colonel $i$’s true resource endowment. Thus, they engage in
General Lotto games with incomplete and asymmetric information. In this paper,
we provide the novel equilibrium characterizations of such games, which are
needed to determine the commander’s optimal distribution on assignments. Let
us denote $\pi_{i}(\mathbb{P}_{i},B_{i},c_{i}|\boldsymbol{v}_{i})$ as the
(unique) equilibrium payoff to sub-colonel $i$ in the asymmetric information
General Lotto game, which we will characterize in Section 4. The commander’s
optimization problem is

$W^{*}:=\max_{\mathbb{P}\in\mathcal{P}({A})}\left\\{\pi_{1}(\mathbb{P}_{1},B_{1},c_{1}|\boldsymbol{v}_{1})+\pi_{2}(\mathbb{P}_{2},B_{2},c_{2}|\boldsymbol{v}_{2})-c\cdot\mathbb{E}_{\mathbb{P}}[A_{1}+A_{2}]\right\\}.$
(2.3)

Similarly to (2.1), the problem (2.3) encompasses both the fixed budget and
per-unit cost settings as special cases. To the best of our knowledge,
however, neither setting has been considered in the literature. Since the set
of randomized assignments $\mathcal{P}({A})$ includes deterministic
assignments, it necessarily holds that

$W^{*}\geq W_{\text{d}}^{*}.$ (2.4)

The goal in this paper is to compare the performance improvement (if any) that
randomization can yield over deterministic assignments.

###  2.2 Sub-colonel strategies and payoffs

Here, we detail the admissible strategies and payoff functions for each of the
stage 2 General Lotto games. Given the marginal distribution on assignments
$\mathbb{P}_{i}$, suppose sub-colonel $i$ is assigned $A_{i}^{(k)}$ resources,
where $i,k\in\\{1,2\\}$. It is tasked with allocating the resources to the set
of $n$ battlefields, $\boldsymbol{v}_{i}$. An allocation is any vector
$\boldsymbol{x}_{i}=(x_{i,1},\ldots,x_{i,n})\in\mathbb{R}_{+}^{n}$. An
admissible strategy for sub-colonel $i$ is any $n$-variate (cumulative)
distribution $F_{i}^{(k)}$ over $\mathbb{R}_{+}^{n}$ that satisfies its budget
in expectation:

$\mathbb{E}_{\boldsymbol{x}_{i}\sim
F_{i}^{(k)}}\left[\sum_{j\in[n]}x_{i,j}\right]\leq A_{i}^{(k)}.$ (2.5)

In other words, sub-colonel $i$’s allocation of resources can be randomized in
any way, as long as the expenditure is no larger than $A_{i}^{(k)}$ in
expectation. We will call $\mathcal{L}(A_{i}^{(k)})$ the set of all admissible
strategies that satisfy (2.5). Similarly, opponent $i$ simultaneously
implements a strategy $G_{i}\in\mathcal{L}({B}_{i})$. The expected payoff to
sub-colonel $i$ is evaluated according to

$U_{i}(F_{i}^{(k)},G_{i}):=\sum_{j\in[n]}v_{i,j}\int_{0}^{\infty}G_{i,j}(x_{i,j})\,dF_{i,j}^{(k)}(x_{i,j})$
(2.6)

where $F_{i,j}^{(k)}$ ($G_{i,j}$) is the univariate marginal cumulative
distribution on sub-colonel $i$’s (opponent’s) allocations to battlefield
$j\in[n]$. The integral term above is simply the probability that sub-colonel
$i$ allocates more resources to battlefield $j$ than opponent $i$. Opponent
$i$’s expected payoff from competition is $\phi_{i}-U_{i}(F_{i}^{(k)},G_{i})$,
where $\phi_{i}:=\|\boldsymbol{v}_{i}\|_{1}$ is the total sum of battlefield
values in competition $i$.

A strategy for sub-colonel $i$ is thus a pair
$F_{i}=(F_{i}^{(1)},F_{i}^{(2)})$, where it uses the appropriate distribution
contingent on the assignment. The ex-ante expected payoff to the sub-colonel
and opponent are respectively given by

$\displaystyle\Pi_{i}(F_{i},G_{i})$
$\displaystyle:=p_{i}U_{i}(F_{i}^{(1)},G_{i})+(1-p_{i})U_{i}(F_{i}^{(2)},G_{i})$
(2.7) $\displaystyle\Gamma_{i}(G_{i},F_{i})$
$\displaystyle:=\|\boldsymbol{v}_{i}\|_{1}-\Pi_{i}(F_{i},G_{i})-c_{i}\cdot\mathbb{E}_{\boldsymbol{x}\sim
G_{i}}\left[\sum_{j\in[n]}x_{j}\right]$

Note that because the opponent does not know the sub-colonel’s true
assignment, it cannot have a contingency for its own strategy, i.e. it must
commit to a single strategy $G_{i}\in\mathcal{L}({B}_{i})$. We will refer to
the simultaneous-move game with payoffs (2.7) as the _Bernoulli Lotto_ (BL)
game, and denote an instance with $\text{BL}(\mathbb{P}_{i},B_{i},c_{i})$. It
is a game of incomplete information. In the case that either $p_{i}=1$ or
$A_{i}^{(1)}=A_{i}^{(2)}\equiv A_{i}$, it becomes a game of complete
information. When this holds, we will simply refer to this setting as a
_General Lotto_ game, denoted $\text{GL}(A_{i},B_{i},c_{i})$. A strategy
profile $(F_{i}^{*},G_{i}^{*})$ is an _equilibrium_ of
$\text{BL}(\mathbb{P}_{i},B_{i},c_{i})$ if

$\displaystyle\Pi_{i}(F_{i}^{*},G_{i}^{*})\geq\Pi_{i}(F_{i},G_{i}^{*})\quad\text{and}\quad\Gamma_{i}(G_{i}^{*},F_{i}^{*})\geq\Gamma_{i}(G_{i},F_{i}^{*})$
(2.8)

for any $F_{i}\in\mathcal{L}(A_{i}^{(1)})\times\mathcal{L}(A_{i}^{(2)})$ and
$G_{i}\in\mathcal{L}(B_{i})$. As before, we denote the equilibrium payoff to
sub-colonel $i$ as $\pi_{i}(\mathbb{P}_{i},B_{i},c_{i})$.

###  2.3 Contributions

In this paper, we are primarily concerned with identifying the performance
improvement that randomization offers over deterministic assignments. In doing
so, we also derive novel results pertaining to equilibrium characterizations
of BL games. We list three major contributions below.

Performance comparisons. The main results of this paper identify salient
features of the performance improvement that randomized assignments offer over
deterministic ones. We summarize these results in Theorem 3.1. Notably, we
find that under the fixed budget setting, optimal randomized assignments do
not offer strict performance improvements over deterministic ones.
Specifically, $W^{*}=W_{\text{d}}^{*}$. In other words, a commander cannot
profitably exploit informational asymmetries when there are use-it or lose-it
resource budgets. However, under the per-unit cost setting, randomized
assignments can offer up to a four-fold performance improvement, i.e.
$W_{\text{d}}^{*}\leq W^{*}\leq 4\cdot W_{\text{d}}^{*}$. We identify
necessary and sufficient conditions for when $W^{*}=4\cdot W_{\text{d}}^{*}$
holds. A detailed proof outline of these results is given in Section 3.

Solutions to resource assignment problems. In order to identify performance
comparisons, we derive complete solutions to the assignment problems (2.1) and
(2.3) under the fixed budget and per-unit cost settings. Recall that optimal
deterministic assignments (2.1) were first characterized in [26] only under
the fixed budget setting. To the best of our knowledge, optimal randomized
assignments (2.3) have not been considered in the existing literature. Our
characterizations are provided in Appendices A and B.

Equilibrium characterizations of BL games. In order to derive solutions to the
randomized assignment problem (2.3), equilibrium characterizations for
Bernoulli General Lotto games are required. To the best of our knowledge,
these games have not been considered in the existing literature. Indeed, the
novel analysis of BL games is the main technical challenge in this paper. It
is necessary to solve (2.3) in _all settings_. We provide a complete
characterization of equilibrium payoffs in all instances of the game
$\text{BL}(\mathbb{P}_{i},B_{i},c_{i})$ in Section 4. These allow us to
explicitly write and solve the assignment problem (2.3). We utilize a variety
of techniques to derive these characterizations, which includes applying the
equilibrium strategies from all-pay auctions with incomplete information [41].
These details are provided in Appendix C.

We note that such incomplete and asymmetric information General Lotto and
Colonel Blotto games are of interest in their own right. Incomplete
information formulations have received much attention in the recent literature
[2, 25, 22, 34]. In particular, a motivating question is to identify the
interplay between information, resources, and attainable performance levels.

The deterministic assignment problem (2.1) relies on equilibrium payoffs from
General Lotto games with complete information, which are already available
from the existing literature [21, 26, 29]. Nevertheless, the solution of
(2.1), which is provided in Appendix A, is novel (to the best of our
knowledge).

###  2.4 Related literature

The primary literature on Colonel Blotto and General Lotto games focuses on
deriving equilibria with the assumption of complete information. That is, the
game’s parameters are common knowledge: each player knows its opponent’s
resource endowment as well as the battlefield valuations. Since Borel’s
initial study in 1921 [9], many works have advanced this line of research over
the last one hundred years. In 1950, Gross and Wagner [17] provided a solution
to the two battlefield case with asymmetric budgets and battlefield values.
Another major contribution is due to Roberson [37] in 2006, which provides
solutions to more than two homogeneous battlefields with asymmetric budgets.
There has since been increased interest that builds on these results to more
general settings [39, 31, 43, 29, 7]. Solutions to the most general settings,
e.g. arbitrary number of heterogeneous battlefields and asymmetric budgets,
remains an open problem [43]. The difficulty is providing a valid joint
distribution on each player’s feasible allocations. That is, a mixed strategy
is described by an $n$-variate distribution with support confined to a
simplex. Roberson [37] was among the first to construct such equilibrium joint
distributions by providing a connection between the equilibria of the Blotto
game and those of $n$ independent all-pay auctions [3]. Other methods utilize
high-dimensional geometric arguments involving uniform distributions on the
surface of an $n$-sphere [17, 43]. Recent threads of research have focused on
multi-player settings [8].

Several variants of the Colonel Blotto game have been featured in the
literature, including Lottery Blotto games [15, 38, 33, 45, 27, 12, 23],
General Lotto games [6, 32, 21, 29], and discrete versions where players’
resource allocations are integer-valued [21, 5, 4, 10]. These variants provide
more analytic or computational tractability in terms of equilibrium solutions
since they serve as approximations to the Colonel Blotto game. The General
Lotto game provides a good approximation when the number of battlefields in
the Colonel Blotto game is large [26]. Indeed, some research has provided
connections between equilibria of the General Lotto game and approximate
equilibria of Colonel Blotto in more general settings [45]. Due to their
tractability, several of these variants are often adopted to study more
complex scenarios. For instance, they have received increased attention in
engineering domains, such as network security [16, 40, 18] and the security of
cyber-physical systems [20, 14].

Our work is similar to a recent body of literature that focuses on the role a
commander plays in assigning resources to sub-colonels. Kovenock and Roberson
[26] first formulated the commander assignment problem under the fixed budget
setting with two opponents. There, they considered and derived optimal
deterministic assignment strategies. Their results focused on whether the two
opponents could form an alliance through a unilateral transfer of resources.
Many follow-up studies have since appeared. Subsequent work in [20, 19]
considered a setting where the two opponents can decide to add battlefields in
addition to transferring resources amongst each other. Counter-intuitively,
the model showed that the team of opponents can achieve better performance if
the transfers are made public to the commander. The model of [11] studied
settings where one of the opponents pre-commits resources before play, which
effectively can alter the commander’s optimal assignment such that the
opponent benefits in subsequent interactions. In these works, deterministic
assignments are considered and hence randomized assignments do not play a
role. Pre-commitment of resources was also considered in [46], but in a
different context that involves favoritism. There, they studied a one-shot
Blotto game with resources that are pre-allocated non-strategically to the
battlefields.

Our work is also relevant to a growing literature on Blotto and Lotto games
with incomplete information. In particular, we formulate and solve General
Lotto games with asymmetric information about the players’ resource
endowments. Few contributions in the literature have shifted the focus away
from complete information settings. However, this direction has received
attention in recent years. Similar to our budget uncertainty setting, the
works [2] and [22] study settings where players have incomplete information
about each other’s resource endowments. That is, the players’ resource
endowments are random variables and each player holds private information only
about their own endowment. The model of [2] consider the players to be equally
uninformed (no information asymmetry) about the budget parameters, and hence
symmetric Bayes-Nash equilibria are identified. Our BL game formulation is
most similar to the model in [22], where they provide equilibria to a Lottery
Blotto game, a variant that generally admits pure strategy Nash equilibria
[15, 38, 24, 45]. Uncertainty about battlefield valuations has also been
featured recently in the literature. In [25, 13], each player’s valuations of
the battlefields are independently drawn from a common joint distribution.
Here, players are equally uninformed about the other players’ valuations, and
hence symmetric Bayes-Nash equilibria are identified. Asymmetric information
about battlefields is investigated in [34], which formulates a Bayesian game
with a finite state space.

##  3 Results

In this section, we present our main results concerning the performance
comparison of resource assignment problems (2.1) and (2.3). Throughout this
paper, we will denote $\phi_{i}=\|\boldsymbol{v}_{i}\|_{1}$ as the value of
competition $i$.

######  Theorem 3.1.

Consider the optimal performance levels $W_{\text{d}}^{*}$ from deterministic
assignments (2.1) and $W^{*}$ from randomized assignments (2.3). The following
relations hold.

  * •

Under the fixed budget setting, i.e. $c=c_{i}=0$ and ${A},B_{i}<\infty$, it
holds that $W^{*}=W_{\text{d}}^{*}$.

  * •

Under the per-unit cost setting, i.e. $c,c_{i}>0$ and ${A},B_{i}=\infty$, it
holds that $0<W_{\text{d}}^{*}\leq W^{*}\leq 4\cdot W_{\text{d}}^{*}$. The
equality $W^{*}=4\cdot W_{\text{d}}^{*}$ holds if and only if
$c>\max\\{\frac{1}{2}\sqrt{\frac{c_{j}}{\phi_{j}}(c_{1}\phi_{1}+c_{2}\phi_{2})},c_{k}(1+\sqrt{3}/2)\\}$,
where
$j=\underset{i=1,2}{\operatorname{arg}\,\operatorname{min}}\;\frac{\phi_{i}}{2c_{i}}$
and $k=\underset{i=1,2}{\operatorname{arg}\,\operatorname{max}}\;c_{i}$.

There are several interesting things to note. The first statement asserts that
the commander cannot profitably exploit informational asymmetries through
randomizing assignments when there are use-it or lose-it resource budgets. A
complete characterization of $W_{\text{d}}^{*}$ under the fixed budget setting
is available in the literature [26]. For brevity, we will not include it here.
The second statement of Theorem 3.1 asserts that the commander can attain up
to a four-fold performance improvement when there are non-zero costs involved.
The four-fold improvement is attainable in a regime where the commander’s per-
unit cost is sufficiently high, i.e. when it is relatively expensive to assign
resources to the sub-colonels.

The above results rely on equilibrium characterizations of the Bernoulli
General Lotto games $\text{BL}(\mathbb{P}_{i},B_{i},c_{i})$ in the
aforementioned settings. To the best of our knowledge, these are unavailable
in the existing literature. As such, we provide complete derivations in this
paper. An outline of the proof of Theorem 3.1 is given as follows.

Step 1. We derive the complete equilibrium characterization of the class of
games $\text{BL}(\mathbb{P}_{i},B_{i},0)$, i.e. in settings where the opponent
has zero per-unit cost and $B_{i}<\infty$. The equilibrium payoffs are
provided in Lemma 4.1. We derive this result through a variety of techniques.
Notably, we are able to apply the equilibrium strategies from all-pay auctions
with incomplete information to the game $\text{BL}(\mathbb{P}_{i},B_{i},0)$
for a certain subset of parameters $(\mathbb{P}_{i},B_{i})$. For the remaining
parameters, we are able to construct equilibrium strategies and calculate
their corresponding payoffs. These techniques and details are illustrated in
Appendix C. These results effectively establish the first statement of Theorem
3.1.

Step 2. For the per-unit cost setting, we need equilibrium characterizations
of the entire class of games $\text{BL}(\mathbb{P}_{i},B_{i},c_{i})$. Indeed,
we leverage the result from Lemma 4.1 to attain these characterizations. The
payoffs in this setting is provided explicitly in Lemma 4.2. We then determine
the optimal randomization $\mathbb{P}_{i}^{*}$ for a single sub-colonel,
subject to a fixed expected assignment constraint (Lemma 4.5).

Step 3. We derive complete solutions of the assignment problems (2.1) and
(2.3) under the per-unit cost setting. Applying the results from step 2, we
can explicitly write the optimization problem (2.3), and analytically solve
it. The derivation of optimal randomized assignments (problem (2.3)) is given
in Appendix B. Note that the novel results from step 2 are not required to
derive optimal deterministic assignments (problem (2.1)), since equilibrium
characterizations of complete information Lotto games are already widely
available. We provide optimal deterministic assignments in Appendix A. We thus
obtain the second statement of Theorem 3.1 by comparing the resulting
performance from these solutions.

Figure 2: (Left) An example of the commander assignment problem under the
general setting – here, the resource budgets are ${A}=1$ and $B_{i}=0.4$. The
per-unit cost for opponents are $c_{i}=1$ for $i=1,2$, and the commander has a
per-unit cost $c<0$. The value of the competitions are $\phi_{1}=1$ and
$\phi_{2}=2$. (Center) Optimal performances from randomized and deterministic
assignments as a function of the commander’s per-unit cost. The red lines
depict performance under the general setting. These values were computed
numerically using the characterizations from Lemmas 4.2 and 4.4. The blue
lines depict performance under the per-unit cost setting, i.e.
${A}=B_{i}=\infty$ and all other parameters remain the same. These values are
explicitly given in Appendices A and B. (Right) The improvement factor,
$W^{*}/W_{\text{d}}^{*}$. In any setting, the commander can attain up to a
four-fold improvement, which is possible when the cost of resources for the
commander are sufficiently high.

In general settings, there can be both positive costs and finite resource
budgets, i.e. $c,c_{i}>0$ and ${A},B_{i}<\infty$. While we do not provide full
solutions of (2.1) and (2.3) in the most generality, we note that their
solutions can still coincide with those from the per-unit cost setting or from
the fixed budget setting. In particular, the solution will coincide with the
per-unit cost setting if the cost $c$ is sufficiently high because the
commander will not utilize all of its available resources ${A}$. The solution
will coincide with the fixed budget setting if all costs are sufficiently low,
such that all available resources ${A},B_{i}$ are utilized in competition.

Figure 2 shows performance levels in an example setup of this general context.
Since the commander in this example has a budget limit of ${A}=1$, it performs
worse for lower costs $c$ in comparison to the per-unit cost setting in which
it has unlimited budget. We also show a comparison of the improvement factors
from the general setting and from the per-unit cost setting. The four-fold
performance improvement factor can only be attained (in both models) for
sufficiently high costs $c$ associated with the commander’s resources.

##  4 Analysis: Equilibrium payoffs in Bernoulli General Lotto games

In this section, we present the unique equilibrium payoffs for every instance
of Bernoulli General Lotto games. Since the focus in this section is on a
single sub-colonel versus its opponent, we will simply refer to the sub-
colonel as player $A$ and the opponent as player $B$. Player $A$ has a high
endowment $A_{1}$ with probability $p\in[0,1]$, and low endowment $A_{2}\leq
A_{1}$ with probability $1-p$. For compactness, we denote $\mathbb{P}_{A}$ as
the (Bernoulli) distribution associated with the triple $(A_{1},A_{2},p)$.
Throughout, we will denote $\bar{A}=pA_{1}+(1-p)A_{2}$ as the expected
resource endowment of player $A$ associated with $\mathbb{P}_{A}$. Player $B$
has a per-unit cost $c\geq 0$, and a resource budget of $B\geq 0$. We also
denote the total sum of battlefield values as $\|\boldsymbol{v}\|_{1}=\phi$.

###  4.1 Zero cost for opponent

We will first focus on the class of games $\text{BL}(\mathbb{P}_{A},B,0)$,
where the opponent has a use-it or lose it budget $B\geq 0$. The complete
characterization of the equilibrium payoffs is given in the result below.

######  Lemma 4.1.

Consider any instance of the Bayesian General Lotto game without costs,
$\text{BL}(\mathbb{P}_{A},B,0)$, where $\phi:=\|\boldsymbol{v}\|_{1}$. The
equilibrium payoff to player $A$ is

$\pi_{A}(\mathbb{P}_{A},B,0)=\phi\cdot\begin{cases}\frac{\bar{A}}{2B},&\text{if
}(A_{1},A_{2})\in\mathcal{R}_{1}\\\ 1-\frac{B\bar{A}^{-1}}{2},&\text{if
}(A_{1},A_{2})\in\mathcal{R}_{2}\\\
p+(1-p)\left(1-\frac{B}{2A_{2}}\right),&\text{if
}(A_{1},A_{2})\in\mathcal{R}_{3}\\\ p+(1-p)\frac{A_{2}}{2B},&\text{if
}(A_{1},A_{2})\in\mathcal{R}_{4}\\\
p+(1-p)\frac{A_{2}}{A_{1}}+\frac{\sqrt{\bar{A}(\bar{A}-pA_{1})}}{A_{1}}-\frac{B\left(\sqrt{(1-p)A_{2}}+\sqrt{\bar{A}}\right)^{2}}{2A_{1}^{2}},&\text{if
}(A_{1},A_{2})\in\mathcal{R}_{5}\\\ \end{cases}$ (4.1)

where $\mathcal{R}_{k}$, $k=1,\ldots,5$, are disjoint subsets of
$\mathcal{R}:=\\{(A_{1},A_{2})\in\mathbb{R}_{+}^{2}:A_{1}\geq A_{2}\\}$, given
by

$\displaystyle\mathcal{R}_{1}$
$\displaystyle=\left\\{(A_{1},A_{2})\in\mathcal{R}:\bar{A}\leq
B\right\\}\setminus\mathcal{R}_{5}$ (4.2) $\displaystyle\mathcal{R}_{2}$
$\displaystyle=\left\\{(A_{1},A_{2})\in\mathcal{R}:\bar{A}\geq B\text{ and
}A_{2}\geq\frac{1-p}{2-p}A_{1}\right\\}$ $\displaystyle\mathcal{R}_{3}$
$\displaystyle=\left\\{(A_{1},A_{2})\in\mathcal{R}:A_{1}\geq\left(2+\frac{p}{1-p}\right)B\text{
and }1\leq A_{2}\leq\frac{1-p}{2-p}A_{1}\right\\}$
$\displaystyle\mathcal{R}_{4}$
$\displaystyle=\left\\{(A_{1},A_{2})\in\mathcal{R}:A_{1}\geq\left(2+\frac{p}{1-p}\right)B\text{
and }\frac{pB^{2}}{(1-p)(A_{1}-2B)}\leq A_{2}\leq B\right\\}$
$\displaystyle\mathcal{R}_{5}$
$\displaystyle=\left\\{(A_{1},A_{2})\in\mathcal{R}:A_{2}\leq B\cdot
H(A_{1}/B)\right\\}$

with the function $H(a)$ defined as

$H(a):=\begin{cases}0,&\text{if }a\in[0,1)\\\
\frac{p(a-1)^{2}}{(1-p)(2-a)},&\text{if }a\in[1,2-p]\\\
\frac{1-p}{2-p}a,&\text{if }a\in\left(2-p,2+\frac{p}{1-p}\right]\\\
\frac{p}{(1-p)\left(a-2\right)},&\text{if }a>2+\frac{p}{1-p}\end{cases}$ (4.3)

The payoff to player $B$ is given by
$\pi_{B}(\mathbb{P}_{A},B,0)=\phi-\pi_{A}(\mathbb{P}_{A},B,0)$.

Figure 3 depicts the five distinct regions of the parameter space for which
(4.1) is defined. We devote Appendix C to the proof of Lemma 4.1, which
details the players’ equilibrium strategies. In particular, we establish a
connection to two-player all-pay auctions with asymmetric information, and
leverage the equilibrium strategies of such auctions to derive a system of
non-linear equations associated with the expected budget constraints (2.5). We
detail all solutions to this system in Proposition C.1, where we find that
they can only exist in the sub-region $\mathcal{R}_{5}$ of Figure 3. We then
provide equilibria for the remaining four regions. The uniqueness of
equilibrium payoffs follows from the BL game being constant-sum in ex-ante
utilities.

We note that only the total value $\phi$ of the battlefields $\boldsymbol{v}$
factors into the analysis, as is also the case in complete information Lotto
games. We will simply refer to the payoff as $\pi_{A}$ when the context of
$\text{BL}(\mathbb{P}_{A},B,0)$ is clear. We note that the payoff $\pi_{A}$ in
regions $\mathcal{R}_{1}$ and $\mathcal{R}_{2}$ coincides with the payoff of
the corresponding benchmark complete information game $\text{GL}(\bar{A},B,0)$
in which player $A$ utilizes its expected endowment $\bar{A}$
deterministically. Indeed, these payoffs are well-known, and are given by

$\pi_{A}^{\text{CI}}(\bar{A},B,0):=\phi\cdot\begin{cases}\frac{\bar{A}}{2B},&\text{if
}\bar{A}<B\\\ 1-\frac{B}{2\bar{A}},&\text{if }\bar{A}\geq B\\\
\end{cases},\quad\pi_{B}^{\text{CI}}:=\phi-\pi_{A}^{\text{CI}}.$ (4.4)

Furthermore, we find that player $A$ can do no better in the BL game with any
$A_{1},A_{2},p$ satisfying $pA_{1}+(1-p)A_{2}=\bar{A}$ than simply engaging in
a complete information General Lotto game in which it uses the budget
$\bar{A}$ deterministically.

Figure 3: A diagram showing the five distinct parameter regions (4.2) that
encompass the entire class of Bayesian Lotto games
$\text{BL}(\mathbb{P}_{A},B,0)$ without costs. Shown here is the space
$A_{1}\geq A_{2}$ for a fixed $p$ and $B$.

######  Proposition 4.1.

It holds that
$\pi_{A}(\mathbb{P}_{A},B,0)\leq\pi_{A}^{\text{CI}}(\bar{A},B,0)$ for any
$\mathbb{P}_{A}$ such that $pA_{1}+(1-p)A_{2}=\bar{A}$.

###### Proof.

Let us denote $F^{*}_{A}\in\mathcal{L}(\bar{A})$ as the equilibrium strategy
for player $A$ in the complete information General Lotto game (without costs),
which ensures a payoff $\pi_{A}^{\text{CI}}$. In the BL game, player $A$
selects a pair of strategies
$(F_{A,1},F_{A,2})\in\mathcal{L}(A_{1})\times\mathcal{L}(A_{2})$. Player $A$
effectively ex-ante competes with a single strategy
$\bar{F}_{A}=pF_{A,1}+(1-p)F_{A,2}$ that belongs to $\mathcal{L}(\bar{A})$.
This follows directly from the linearity of expectations in both (2.5) and
(2.6). However, the set
$\\{\bar{F}_{A}\in\mathcal{L}(\bar{A}):pF_{A,1}+(1-p)F_{A,2}\\}$ is a subset
of $\mathcal{L}(\bar{A})$, which may not contain $F_{A}^{*}$. ∎

Proposition 4.1 effectively establishes the first statement of Theorem 3.1,
i.e. $W^{*}=W_{\text{d}}^{*}$. In other words, randomization does not offer
any performance improvement over deterministic assignments. We note that the
explicit characterization given in Lemma 4.1 was not needed to prove this
statement. However, this characterization is necessary to derive equilibrium
payoffs of the BL game in the per-unit cost setting.

###  4.2 Per-unit cost for opponent

Now, we consider the class of games $\text{BL}(\mathbb{P},B,c)$ in the most
generality: player $B$ has a per-unit cost $c>0$ and a resource budget of
$B>0$. First, we observe that the equilibrium payoffs can be obtained by
leveraging the solutions from the game without costs (Lemma 4.1). Suppose
$(F_{A}^{*},F_{B}^{*})$ is an equilibrium of $\text{BL}(\mathbb{P},B,c)$, and
$B^{*}=\sum_{j\in[n]}\mathbb{E}_{x_{j}\sim F_{B,j}^{*}}[x_{j}]$. It must hold
that $(F_{A}^{*},F_{B}^{*})$ is also an equilibrium of
$\text{BL}(\mathbb{P},B^{*},0)$ (game without costs), which has the unique
payoff $\pi_{B}$ given by Lemma 4.1. Therefore, the equilibrium payoff to
player $B$ in the game with costs must satisfy222Analogous arguments and
properties apply in other variants of the Blotto game as well, e.g. Lottery
Blotto games with per-unit costs for investment [22].

$\pi_{B}(\mathbb{P}_{A},B,c)=\max_{B^{\prime}\in[0,B]}\left\\{\pi_{B}(\mathbb{P}_{A},B^{\prime},0)-c\cdot
B^{\prime}\right\\}.$ (4.5)

This renders player $B$’s choice of investment level as the relevant decision
variable that determines the equilibrium payoffs of
$\text{BL}(\mathbb{P}_{A},B,c)$. We will assume that when there are multiple
maximizers of (4.5), player $B$ prefers the lowest one333This assumption is
for simplification purposes, which circumvents the need to explicitly identify
ranges of equilibria that can exist. These cases only arise in parameter
regimes of measure zero. Specifically, when $c=\lambda$ or
$\frac{(1-p)\phi}{2A_{2}}$. This ensures the optimal investment level is
unique. The following result characterizes the equilibrium payoffs in
$\text{BL}(\mathbb{P}_{A},B,c)$.

######  Lemma 4.2.

Consider the game $\text{BL}(\mathbb{P}_{A},B,c)$. If
$\frac{A_{2}}{A_{1}}\geq\frac{1-p}{2-p}$, then the equilibrium payoffs
coincide with those of the complete information game $\text{GL}(\bar{A},B,c)$
(Lemma 4.4). If $\frac{A_{2}}{A_{1}}<\frac{1-p}{2-p}$, then the equilibrium
payoff to player $A$ is
$\pi_{A}(\mathbb{P}_{A},B,c)=\max\\{\pi_{A}(\mathbb{P}_{A},B,0),\pi_{A}(\mathbb{P}_{A},\infty,c)\\}$,
where

$\pi_{A}(\mathbb{P}_{A},\infty,c)=\begin{cases}\sqrt{\frac{c\phi\bar{A}}{2}},&\text{if
}c\in[0,\lambda)\\\ p\phi+\sqrt{\frac{c\phi(1-p)A_{2}}{2}},&\text{if
}c\in[\lambda,\frac{(1-p)\phi}{2A_{2}})\\\ \phi,&\text{if
}c\in[\frac{(1-p)\phi}{2A_{2}},\infty)\end{cases}$ (4.6)

The equilibrium payoff to player $B$ is given by
$\pi_{B}(\mathbb{P}_{A},B,c)=\min\\{\pi_{B}(\mathbb{P}_{A},B,0)-cB,\pi_{B}(\mathbb{P}_{A},\infty,c)\\}$,
where

$\pi_{B}(\mathbb{P}_{A},\infty,c)=\begin{cases}\phi-\sqrt{2c\phi\bar{A}},&\text{if
}c\in[0,\lambda)\\\ \phi(1-p)-\sqrt{2c\phi(1-p)A_{2}},&\text{if
}c\in[\lambda,\frac{(1-p)\phi}{2A_{2}})\\\ 0,&\text{if
}c\in[\frac{(1-p)\phi}{2A_{2}},\infty)\end{cases}$ (4.7)

The proof of Lemma 4.2 follows from a series of intermediate results, the
first of which explicitly characterizes player $B$’s optimal investment level,
$B^{*}(\mathbb{P}_{A},B,c)$.

######  Lemma 4.3.

Consider any game $\text{BL}(\mathbb{P}_{A},B,c)$. Then

$B^{*}(\mathbb{P}_{A},B,c)=\min\\{B,B^{*}(\mathbb{P}_{A},\infty,c)\\}$ (4.8)

where $B^{*}(\mathbb{P}_{A},\infty,c)$ is given explicitly as follows. In the
complete information game $\text{GL}(\bar{A},\infty,c)$,

$B^{*}(\bar{A},\infty,c)=\begin{cases}\sqrt{\frac{\bar{A}\phi}{2c}},&\text{if
}c\in[0,\frac{\phi}{2\bar{A}})\\\ 0,&\text{if
}c\geq\frac{\phi}{2\bar{A}}\end{cases}.$ (4.9)

In the game $\text{BL}(\mathbb{P}_{A},\infty,c)$, $B^{*}$ is precisely given
by (4.9) if $\frac{A_{2}}{A_{1}}\geq\frac{1-p}{2-p}$. If
$\frac{A_{2}}{A_{1}}<\frac{1-p}{2-p}$,

$B^{*}(\mathbb{P}_{A},\infty,c)=\begin{cases}\sqrt{\frac{\bar{A}\phi}{2c}},&\text{if
}c\in[0,\lambda)\\\ \sqrt{\frac{(1-p)A_{2}\phi}{2c}},&\text{if
}c\in[\lambda,\frac{(1-p)\phi}{2A_{2}})\\\ 0,&\text{if
}c\geq\frac{(1-p)\phi}{2A_{2}}\end{cases}$ (4.10)

where we haved defined
$\lambda:=\frac{\phi}{2A_{1}^{2}}(\sqrt{(1-p)A_{2}}+\sqrt{\bar{A}})^{2}$.

###### Proof.

Consider the complete information game $\text{GL}(\bar{A},\infty,c)$. Here,
player $B$ has no budget limit, and its optimal investment is the maximizer of
the concave problem $\max_{B^{\prime}\geq
0}\\{\pi_{B}^{\text{CI}}(\bar{A},B^{\prime},0)-c\cdot B^{\prime}\\}$, where
$\pi_{B}^{\text{CI}}$ is given in (4.4). In the case
$c=\frac{\phi}{2\bar{A}}$, any investment in the interval $[0,\bar{A}]$ is a
maximizer. Taking the minimum investment in this interval, we thus obtain
(4.9).

Now, consider $\text{BL}(\mathbb{P}_{A},\infty,c)$. The optimal investment is
the maximizer of the concave problem $\max_{B^{\prime}\geq
0}\\{\pi_{B}(\bar{A},B^{\prime},0)-c\cdot B^{\prime}\\}$. First, suppose
$\frac{A_{2}}{A_{1}}\geq\frac{1-p}{2-p}$. From (4.1), we have
$\pi_{B}(\mathbb{P}_{A},0,B^{\prime})=\pi_{B}^{\text{CI}}(\bar{A},0,B^{\prime})$
for all $B^{\prime}\geq 0$, and therefore $B^{*}$ coincides with (4.9).

Now, suppose $\frac{A_{2}}{A_{1}}<\frac{1-p}{2-p}$. From Lemma 4.1, we can
write $\pi_{B}(\mathbb{P}_{A},B^{\prime},0)$ as

$\phi\cdot\begin{cases}(1-p)\frac{B^{\prime}}{2A_{2}},&\text{if
}B^{\prime}\leq A_{2}\\\
(1-p)\left(1-\frac{A_{2}}{2B^{\prime}}\right),&\text{if }A_{2}<B^{\prime}\leq
Y_{1}\\\
(1-p)(1-\frac{A_{2}}{A_{1}})-\frac{\sqrt{\bar{A}(\bar{A}-pA_{1})}}{A_{1}}+\lambda
B^{\prime},&\text{if }Y_{1}<B^{\prime}\leq Y_{2}\\\
p\left(1-\frac{A_{1}}{2B^{\prime}}\right)+(1-p)\left(1-\frac{A_{2}}{2B^{\prime}}\right),&\text{if
}Y_{2}<B^{\prime}\end{cases}$ (4.11)

where we have written
$Y_{1}:=\frac{A_{1}\sqrt{(1-p)A_{2}}}{\sqrt{(1-p)A_{2}}+\sqrt{\bar{A}}}$, and
$Y_{2}:=\frac{A_{1}\sqrt{\bar{A}}}{\sqrt{(1-p)A_{2}}+\sqrt{\bar{A}}}$. The
entries in the expression above correspond to payoffs in regions
$\mathcal{R}_{3}$, $\mathcal{R}_{4}$, $\mathcal{R}_{5}$, and
$\mathcal{R}_{1}$, respectively (Lemma 4.1). The values for $B^{*}$ result
from solving $\frac{\partial}{\partial
B^{\prime}}\left(\pi_{B}(\mathbb{P}_{A},B^{\prime},0)-cB^{\prime}\right)=0$.
Note that the first and third entries provide linear returns on investment
$B^{\prime}$. Therefore, there are multiple maximizers when the per-unit cost
coincides with these slopes. In particular, when $c=\lambda$ or
$c=\frac{1-p}{2A_{2}}$, the payoff
$\pi_{B}(\mathbb{P}_{A},B^{\prime},0)-c\cdot B^{\prime}$ is constant for all
$B^{\prime}\in[Y_{1},Y_{2}]$ or $B^{\prime}\in[0,A_{2}]$, respectively. Since
player $B$ prefers the lowest investment level, we thus obtain (4.10). With a
finite resource budget $B<\infty$, the optimal investment is generally given
by (4.8). ∎

The next result identifies the equilibrium payoffs in a complete information
game with costs, $\text{GL}(\bar{A},B,c)$.

######  Lemma 4.4.

In the complete information game $\text{GL}(\bar{A},B,c)$, the equilibrium
payoffs are given as follows. If $B<\frac{\phi}{2c}$, then

  * •

If $c\in[0,\frac{\phi}{2\bar{A}})$, then
$\pi_{A}^{\text{CI}}(\bar{A},B,c)=\max\\{\pi_{A}^{\text{CI}}(\bar{A},B,0),\sqrt{\frac{c\phi\bar{A}}{2}}\\}$
and
$\pi_{B}^{\text{CI}}(\bar{A},B,c)=\phi-\min\\{\pi_{A}^{\text{CI}}(\bar{A},B,0)+cB,\sqrt{2c\phi\bar{A}}\\}$

  * •

If $c\geq\frac{\phi}{2\bar{A}}$, then $\pi_{A}^{\text{CI}}(\bar{A},B,c)=\phi$
and $\pi_{B}^{\text{CI}}(\bar{A},B,c)=0$.

The following result highlights the comparisons between the equilibrium
payoffs obtained in $\text{BL}(\mathbb{P}_{A},B,c)$ (Lemma 4.2) to payoffs
from the benchmark complete information setting $\text{GL}(\bar{A},B,c)$
(Lemma 4.4). Notably, player $A$ can obtain payoff improvements, which were
not attainable in the zero cost formulation of Section 4.1.

Figure 4: (Left) Equilibrium payoff $\pi_{A}(\mathbb{P}_{A},\infty,c)$ to
player $A$ as characterized in Lemma 4.2. Here, player $B$ has unlimited
resource budget, $B=\infty$. The dotted green line is $A$’s payoff from a
fixed randomization $(A_{1},A_{2},p)=(2.5,0.5,0.5)$. The dashed black line the
benchmark complete information payoff (Lemma 4.4). We note there is an
interval of costs (approx. $c\in[0.24,1/3]$) in which both players strictly
benefit from this randomization. The solid green line is the payoff it attains
from the optimal randomization
$(A_{1}^{*},A_{2}^{*},p^{*})=(\sqrt{\bar{A}\phi/(2c)},0,\sqrt{2c\bar{A}/\phi})$
for any $c>0$. It improves upon the benchmark payoff two-fold in the interval
$c\in[0,1/3)$. (Right) Equilibrium payoff $\pi_{B}(\mathbb{P}_{A},\infty,c)$
to player $B$. The fixed randomization $(A_{1},A_{2},p)$ does not degrade
$B$’s payoff in comparison to the complete information setting. In fact, there
is a range of costs where $B$ strictly improves.

######  Corollary 4.1.

The following properties hold in $\text{BL}(\mathbb{P}_{A},\infty,c)$. If
$\frac{A_{2}}{A_{1}}\geq\frac{1-p}{2-p}$, then
$\pi_{\ell}(\mathbb{P}_{A},\infty,c)=\pi_{\ell}^{\text{CI}}(\bar{A},\infty,c)$,
$\ell\in\\{A,B\\}$. If $\frac{A_{2}}{A_{1}}<\frac{1-p}{2-p}$, then

  * •

For $c\in[0,\lambda)$, then
$\pi_{\ell}(\mathbb{P}_{A},\infty,c)=\pi_{\ell}^{\text{CI}}(\bar{A},\infty,c)$.

  * •

For $c\in[\lambda,\frac{\phi}{2\bar{A}})$, then
$\pi_{\ell}>\pi_{\ell}^{\text{CI}}$.

  * •

For $c\in[\frac{\phi}{2\bar{A}},\frac{(1-p)\phi}{2A_{2}})$, then
$\pi_{B}>\pi_{B}^{\text{CI}}$ and $\pi_{A}<\pi_{A}^{\text{CI}}$.

  * •

For $c\in[\frac{(1-p)\phi}{2A_{2}},\infty)$, $\pi_{B}=\pi_{B}^{\text{CI}}=0$
and $\pi_{A}=\pi_{A}^{\text{CI}}=1$.

###### Proof.

We outline the arguments for $\frac{A_{2}}{A_{1}}<\frac{1-p}{2-p}$. In this
regime, $\lambda<\frac{\phi}{2\bar{A}}<\frac{(1-p)\phi}{2A_{2}}$. The results
for player $A$ follow from Lemma 4.3: we observe that for $c\in[0,\lambda)$,
the optimal investment coincides with the complete information game. For
$c\in[\lambda,\frac{\phi}{2\bar{X}})$, player $A$ improves because player $B$
under-invests in comparison to the complete information game. For
$c\in[\frac{\phi}{2\bar{A}},\frac{(1-p)\phi}{2A_{2}})$, player $A$ is worse
off because player $B$ over-invests. For
$c\in(\frac{(1-p)\phi}{2A_{2}},\infty)$, $B^{*}=0$. The results for player $B$
follow from the characterization in Lemma 4.2.

∎

Interestingly, there is an interval $c\in[\lambda,\frac{\phi}{2\bar{A}})$
where both players’ performance strictly improve upon the complete information
setting. Moreover, player $B$ never does worse under uncertainty, with strict
improvement in the interval $c\in[\lambda,\frac{(1-p)\phi}{2A_{2}})$.

###  4.3 Optimal randomizations

As Corollary 4.1 suggests, randomized endowments can strictly improve upon
deterministic ones. Here, we derive the optimal randomization
$\mathbb{P}_{A}=(A_{1},A_{2},p)$ for player $A$ subject to a fixed expected
endowment $pA_{1}+(1-p)A_{2}=\bar{A}$, i.e. the one(s) that achieve the payoff

$\Pi_{A}^{*}(\bar{A},B,c):=\max_{\mathbb{P}_{A}=(A_{1},A_{2},p)}\pi_{A}(\mathbb{P}_{A},B,c)\
\text{where }A_{2}=\frac{\bar{A}-pA_{1}}{1-p}.$ (4.12)

If $\mathbb{P}_{A}^{*}$ is an optimal randomization, player $B$ obtains the
payoff $\Pi_{B}^{*}(\bar{A},B,c):=\pi_{B}(\mathbb{P}_{A}^{*},B,c)$. The next
result characterizes the optimal randomization and the resulting payoffs
explicitly.

######  Lemma 4.5.

The payoff (4.12) resulting from an optimal randomization is given by

$\displaystyle\Pi_{A}^{*}(\bar{A},B,c)$
$\displaystyle=\max\left\\{\pi_{A}^{\text{CI}}(\bar{A},B,0),\Pi_{A}^{*}(\bar{A},\infty,c)\right\\}$
(4.13) $\displaystyle\Pi_{B}^{*}(\bar{A},B,c)$
$\displaystyle=\min\left\\{\pi_{B}^{\text{CI}}(\bar{A},B,0)-cB,\pi_{B}^{\text{CI}}(\bar{A},B,c)\right\\}$

where

$\Pi_{A}^{*}(\bar{A},\infty,c)=\begin{cases}2\cdot\pi_{A}^{\text{CI}}(\bar{A},\infty,c)&\text{if
}c\in(0,\frac{\phi}{2\bar{A}})\\\ \phi,&\text{if
}c\geq\frac{\phi}{2\bar{A}}\end{cases}$ (4.14)

If $\pi_{A}^{\text{CI}}(\bar{A},B,0)\leq\Pi_{A}^{*}(\bar{A},\infty,c)$, then
the optimal randomization $\mathbb{P}_{A}^{*}$ is given by

$(A_{1}^{*},A_{2}^{*},p^{*})=\begin{cases}\left(\sqrt{\frac{\bar{A}\phi}{2c}},0,\sqrt{\frac{2c\bar{A}}{\phi}}\right)&\text{if
}c\in(0,\frac{\phi}{2\bar{A}})\\\
\left(\bar{A},\bar{A},\times\right),&\text{if
}c\geq\frac{\phi}{2\bar{A}}\end{cases}$ (4.15)

Otherwise, $(A_{1}^{*},A_{2}^{*},p^{*})=\left(\bar{A},\bar{A},\times\right)$.

An optimal randomization can double player $A$’s payoff compared to the
complete information setting. Meanwhile, the optimal randomization removes any
benefits for player $B$ that were available when non-optimal randomization are
used (Corollary 4.1). When the resource cost is high ($c\geq\phi/2\bar{A}$),
player $B$ does not invest any resources. The proof relies on the following
intermediate result based on the optimal choices of $A_{1}$ and $A_{2}$ for a
fixed probability $p$. Let

$\Pi_{A}^{*}(\bar{A},B,c;p):=\max_{A_{1}}\pi_{A}(\mathbb{P}_{A},B,c)\
\text{where }A_{2}=\frac{\bar{A}-pA_{1}}{1-p}.$ (4.16)

######  Lemma 4.6.

The payoff (4.16) is given by

$\Pi_{A}^{*}(\bar{A},B,c;p)=\max\left\\{\pi_{A}^{\text{CI}}(\bar{A},B,0),\Pi_{A}^{*}(\bar{A},\infty,c;p)\right\\}$
(4.17)

where

$\Pi_{A}^{*}(\bar{A},\infty,c;p)=\begin{cases}\pi_{A}^{\text{CI}}(\bar{A},\infty,c),&\text{if
}c<\frac{p^{2}\phi}{2\bar{A}}\\\
\frac{p\phi}{2}+\sqrt{\frac{c\phi\bar{A}}{2}},&\text{if
}\frac{p^{2}\phi}{2\bar{A}}\leq c<\frac{\phi}{2\bar{A}}\\\ \phi,&\text{if
}\frac{\phi}{2\bar{A}}\leq c\end{cases}$ (4.18)

The optimal randomization is

$(A_{1}^{*},A_{2}^{*})=\left(\phi\frac{2\sqrt{2c\bar{A}/\phi}-p}{2c},\frac{1}{1-p}\left(\bar{A}-\frac{p\phi(2\sqrt{2c\bar{A}/\phi}-p)}{2c}\right)\right)$
(4.19)

###### Proof.

Let us first suppose $B=\infty$. Let us denote
$f=\frac{A_{2}}{A_{1}}\in[0,1]$. The expected endowment constraint in (4.16)
can equivalently be written as $A_{1}=\frac{\bar{A}}{p+(1-p)f}$. Let us denote
$\lambda(f)=\phi\frac{p+(1-p)f}{2\bar{A}}(\sqrt{(1-p)f}+\sqrt{p+(1-p)f})^{2}$.
The value $\lambda$ is the first point of discontinuity of the function
$\pi_{A}(\cdot,\cdot,c)$ (4.6). First, we observe that $\lambda(f)$ is
strictly increasing in $f$, taking the value $\frac{p^{2}\phi}{2\bar{A}}$ for
$f=0$. From (4.6), we then have $\pi_{A}=\pi_{A}^{\text{CI}}$ for all
$c<\frac{p^{2}\phi}{2\bar{A}}$ regardless of $f$. Therefore, (4.16) must take
the value $\pi_{A}^{\text{CI}}$ for $c\leq\frac{p^{2}\phi}{2\bar{A}}$. When
$c\geq\frac{\phi}{2\bar{A}}$, we observe player $A$ can choose $f=1$, i.e.
resort to the complete information setup, to obtain the maximum payoff of 1.

For $c\in[\frac{p^{2}\phi}{2\bar{A}},\frac{\phi}{2\bar{A}})$, we claim that
the $f^{*}$ that satisfies $\lambda(f^{*})=c$ characterizes the solution
$A_{1}^{*},A_{2}^{*}$ to (4.16) (with $B=\infty$). One can solve this equation
for $f^{*}$ as follows: make the substitution $y=p+(1-p)f$ to obtain
$y(\sqrt{y-p}+\sqrt{y})^{2}=2c\bar{A}/\phi$, which has the solution
$y=\frac{2c\bar{A}/\phi}{2\sqrt{2c\bar{A}/\phi}-p}$. We then get
$f^{*}=\frac{2c\bar{A}/\phi}{(1-p)(2\sqrt{2c\bar{A}/\phi}-p)}-\frac{p}{1-p}$
and subsequent endowments $A_{1}^{*}=\phi\frac{2\sqrt{2c\bar{A}/\phi}-p}{2c}$
and
$A_{2}^{*}=\frac{1}{1-p}\left(\bar{A}-\frac{p\phi(2\sqrt{2c\bar{A}/\phi}-p)}{2c}\right)$.
Denoting $\mathbb{P}_{A}^{*}=(A_{1}^{*},A_{2}^{*},p)$, from (4.6) we have
$\pi_{A}(\mathbb{P}_{A}^{*},\infty,c)=p\phi+\sqrt{\frac{c\phi(1-p)A_{2}^{*}}{2}}=\frac{p\phi}{2}+\sqrt{\frac{c\phi\bar{A}}{2}}$.
The second equality follows due to $c\geq\frac{p^{2}\phi}{2\bar{A}}$.

We verify that
$\pi_{A}(\mathbb{P}_{A}^{*},\infty,c)>\pi_{A}(\mathbb{P}_{A},\infty,c)$ for
any other $\mathbb{P}_{A}=(A_{1},A_{2},p)$ satisfying the expected endowment
constraint. Let $f=A_{2}/A_{1}$. For any $f>f^{*}$,
$\lambda(f)>\lambda(f^{*})$. Since $c$ is fixed, we thus obtain

$\pi_{A}(\mathbb{P}_{A},\infty,c)=\pi_{A}^{\text{CI}}(\bar{A},\infty,c)<\pi_{A}(\mathbb{P}_{A}^{*},\infty,c)$
(4.20)

where the inequality follows from Corollary 4.1 (second item). For any
$f<f^{*}$, we must have $A_{2}<A_{2}^{*}$ (and $A_{1}>A_{1}^{*}$). We then
have
$\pi_{A}(\mathbb{P}_{A},\infty,c)=p\phi+\sqrt{\frac{c\phi(1-p)A_{2}}{2}}<p\phi+\sqrt{\frac{c\phi(1-p)A_{2}^{*}}{2}}=\pi_{A}(\mathbb{P}_{A},\infty,c)$.

When $B<\infty$, player $B$ can only utilize up to $B$ resources. Suppose it
holds that
$\pi_{A}^{\text{CI}}(\bar{A},B,0)>\pi_{A}(\mathbb{P}_{A}^{*},\infty,c)=\max_{\mathbb{P}_{A}}\pi_{A}(\mathbb{P}_{A},\infty,c)$.
We thus claim that $A_{1}^{*}=A_{2}^{*}=\bar{A}$ optimizes (4.16). This
equates to showing that $B^{*}(\bar{A},B,c)=B$, i.e. player $B$ will use all
of its resources if player $A$’s endowment is deterministically $\bar{A}$.
Recall that player $B$ utilizes $\sqrt{\frac{\bar{A}\phi}{2c}}$ resources in
the absence of a budget limit (Lemma 4.3). Note that
$\pi_{A}(\bar{A},B^{\prime},0)$ is decreasing in $B^{\prime}$, and
$\pi_{A}(\bar{A},\sqrt{\frac{\bar{A}\phi}{2c}},0)=\pi_{A}^{\text{CI}}(\bar{A},\infty,c)<\pi_{A}(\mathbb{P}_{A},\infty,c)$.
Thus, it must be the case that $B<\sqrt{\frac{\bar{A}\phi}{2c}}$. Lastly,
Proposition 4.1 asserts that
$\pi_{A}^{\text{CI}}(\bar{A},B,0)\geq\pi_{A}(\mathbb{P}_{A},B,0)$ for any
$\mathbb{P}_{A}$ satisfying the expected endowment constraint, which proves
(4.17). ∎

###### Proof of Lemma 4.5.

Let us first suppose $B=\infty$. The optimization (4.12) is equivalent to
maximizing $\Pi_{A}^{*}(\bar{A},\infty,c;p)$ (4.18) over $p\in[0,1]$. We
observe player $A$ obtains the maximum payoff $\phi$ for high costs
$c\geq\frac{\phi}{2\bar{A}}$, irrespective of $p$. So, suppose
$c<\frac{\phi}{2\bar{A}}$ is fixed. The expression
$\frac{p\phi}{2}+\sqrt{\frac{c\phi\bar{A}}{2}}$ is strictly increasing on
$p\in[0,\sqrt{2c\bar{A}/\phi}]$. This payoff is attainable only for
$p\in[0,\sqrt{2c\bar{A}/\phi}]$, and hence $\Pi_{A}^{*}(\bar{A},\infty,c;p)$
is maximized at $p^{*}=\sqrt{2c\bar{A}/\phi}$. This gives the payoff
$\sqrt{2c\phi\bar{A}}=2\cdot\pi_{A}^{\text{CI}}$.

When $B<\infty$, we can use similar arguments from the proof of Lemma 4.6 to
show that $A_{1}^{*}=A_{2}^{*}=\bar{A}$ optimizes (4.13). ∎

##  5 Conclusions

This paper considers a class of resource assignment problems, where a
commander must determine how to assign costly resources to two separate
competitions. Within each competition, a sub-colonel is then tasked with
allocating its assigned resources against an opponent. We consider the
framework of General Lotto games as the underlying model of competition. We
are primarily interested in characterizing the performance improvement that
randomized assignments can offer over deterministic assignments. A commander
may be able to exploit informational asymmetries by randomizing, as it induces
the opponents to become uncertain about the sub-colonels’ actual assignments.
We find that randomization can offer up to a four-fold performance improvement
in settings where there are costs associated with utilizing resources. When
there are no associated costs, randomization does not offer any performance
improvements.

The main technical challenge required to derive these results is an analysis
of incomplete and asymmetric information General Lotto games, which have not
been studied in the literature (to the best of our knowledge). We term these
games “Bernoulli General Lotto” games, as one of the players has a randomized
resource endowment on two types. Indeed, we provide novel equilibrium
characterizations for such games, which we then leverage to build a
characterization of the optimal randomized assignment strategies.

There are several interesting directions for future research. The incomplete
information Lotto games are of interest in their own right, and one can
consider extensions in which there are more than two budget types, or where
both competitors have randomized budgets. The equilibria derived in these
games may also serve as equilibria to a class of corresponding all-pay
auctions with incomplete information. It would also be of interest to extend
the assignment problems to account for more than two sub-colonels.

## Acknowledgments

This work is supported by UCOP Grant LFR-18-548175, ONR grant
#N00014-20-1-2359, AFOSR grants #FA9550-20-1-0054 and #FA9550-21-1-0203, and
the Army Research Lab through the ARL DCIST CRA #W911NF-17-2-0181.

## References

  * [1] M. Abdallah, T. Cason, S. Bagchi, and S. Sundaram.  The effect of behavioral probability weighting in a simultaneous multi-target attacker-defender game.  arXiv preprint arXiv:2103.03392, 2021.
  * [2] T. Adamo and A. Matros.  A Blotto game with incomplete information.  Economics Letters, 105(1):100–102, 2009.
  * [3] M. R. Baye, D. Kovenock, and C. G. de Vries.  The all-pay auction with complete information.  Economic Theory, 8(2):291–305, 1996.
  * [4] S. Behnezhad, A. Blum, M. Derakhshan, M. HajiAghayi, M. Mahdian, C. H. Papadimitriou, R. L. Rivest, S. Seddighin, and P. B. Stark.  From battlefields to elections: Winning strategies of Blotto and auditing games.  In Proc. of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2291–2310. SIAM, 2018.
  * [5] S. Behnezhad, S. Dehghani, M. Derakhshan, M. HajiAghayi, and S. Seddighin.  Faster and simpler algorithm for optimal strategies of blotto game.  In Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, AAAI’17, page 369?375. AAAI Press, 2017.
  * [6] R. M. Bell and T. M. Cover.  Competitive optimality of logarithmic investment.  Mathematics of Operations Research, pages 161–166, 1980.
  * [7] E. Boix-Adserà, B. L. Edelman, and S. Jayanti.  The multiplayer colonel blotto game.  In Proceedings of the 21st ACM Conference on Economics and Computation, pages 47–48, 2020.
  * [8] E. Boix-Adserà, B. L. Edelman, and S. Jayanti.  The multiplayer colonel blotto game.  Games and Economic Behavior, 129:15–31, 2021.
  * [9] E Borel.  La théorie du jeu les équations intégrales à noyau symétrique.  Comptes Rendus de l’Académie, 173, 1921.
  * [10] A. Casella, J. Laslier, and A. Macé.  Democracy for polarized committees: The tale of blotto’s lieutenants.  Games and Economic Behavior, 106:239–259, 2017.
  * [11] R. Chandan, K. Paarporn, and J. R. Marden.  When showing your hand pays off: Announcing strategic intentions in colonel blotto games.  In 2020 American Control Conference (ACC), pages 4632–4637, 2020\.
  * [12] M. Drugov and D. Ryvkin.  Biased contests for symmetric players.  Games and Economic Behavior, 103:116–144, 2017.
  * [13] C. Ewerhart and D. Kovenock.  A class of n-player colonel blotto games with multidimensional private information.  Operations Research Letters, 49(3):418–425, 2021.
  * [14] A. Ferdowsi, W. Saad, and N. B. Mandayam.  Colonel blotto game for sensor protection in interdependent critical infrastructure.  IEEE Internet of Things Journal, 8(4):2857–2874, 2021.
  * [15] L. Friedman.  Game-theory models in the allocation of advertising expenditures.  Operations research, 6(5):699–709, 1958.
  * [16] Z. E. Fuchs and P. P. Khargonekar.  A sequential colonel blotto game with a sensor network.  In 2012 American Control Conference (ACC), pages 1851–1857. IEEE, 2012.
  * [17] O. Gross and R. Wagner.  A continuous Colonel Blotto game.  Technical report, RAND Project, Air Force, Santa Monica, 1950.
  * [18] S. Guan, J. Wang, H. Yao, C. Jiang, Z. Han, and Y. Ren.  Colonel Blotto games in network systems: Models, strategies, and applications.  IEEE Transactions on Network Science and Engineering, 7(2):637–649, 2020.
  * [19] A. Gupta, T. Başar, and G. Schwartz.  A three-stage Colonel Blotto game: when to provide more information to an adversary.  In International Conference on Decision and Game Theory for Security, pages 216–233. Springer, 2014.
  * [20] A. Gupta, G. Schwartz, C. Langbort, S. S. Sastry, and T. Başar.  A three-stage colonel blotto game with applications to cyberphysical security.  In 2014 American Control Conference, pages 3820–3825, 2014.
  * [21] S. Hart.  Discrete Colonel Blotto and General Lotto games.  International Journal of Game Theory, 36(3-4):441–460, 2008.
  * [22] J. Kim and B. Kim.  An asymmetric lottery blotto game with a possible budget surplus and incomplete information.  Economics Letters, 152:31 – 35, 2017.
  * [23] T. Klumpp, K. A. Konrad, and A. Solomon.  The dynamics of majoritarian blotto games.  Games and Economic Behavior, 117:402–419, 2019.
  * [24] D. Kovenock and D. R. Arjona.  A full characterization of best-response functions in the lottery colonel blotto game.  Economics Letters, 182:33–36, 2019.
  * [25] D. Kovenock and B. Roberson.  A Blotto game with multi-dimensional incomplete information.  Economics Letters, 113(3):273–275, 2011.
  * [26] D. Kovenock and B. Roberson.  Coalitional colonel blotto games with application to the economics of alliances.  Journal of Public Economic Theory, 14(4):653–676, 2012.
  * [27] D. Kovenock and B. Roberson.  Conflicts with multiple battlefields.  In M.R. Garfinkel and S. Skaperdas, editors, The Oxford Handbook of the Economics of Peace and Conflict. Oxford University Press, Oxford, 2012\.
  * [28] D. Kovenock and B. Roberson.  The optimal defense of networks of targets.  Economic Inquiry, 56(4):2195–2211, 2018.
  * [29] D. Kovenock and B. Roberson.  Generalizations of the general Lotto and Colonel Blotto games.  Economic Theory, pages 1–36, 2020.
  * [30] D. Kvasov.  Contests with limited resources.  Journal of Economic Theory, 136(1):738–748, 2007.
  * [31] S. T. Macdonell and N. Mastronardi.  Waging simple wars: a complete characterization of two-battlefield Blotto equilibria.  Economic Theory, 58(1):183–216, 2015.
  * [32] R. B. Myerson.  Incentives to cultivate favored minorities under alternative electoral systems.  American Political Science Review, 87(4):856–869, 1993.
  * [33] A. Osorio.  The lottery blotto game.  Economics Letters, 120(2):164–166, 2013.
  * [34] K. Paarporn, R. Chandan, M. Alizadeh, and J. R. Marden.  Characterizing the interplay between information and strength in blotto games.  In 2019 IEEE 58th Conference on Decision and Control (CDC), pages 5977–5982, 2019.
  * [35] J. Pita, M. Jain, J. Marecki, F. Ordóñez, C. Portway, M. Tambe, C. Western, P. Paruchuri, and S. Kraus.  Deployed armor protection: the application of a game theoretic model for security at the los angeles international airport.  In Proceedings of the 7th International Joint Conference on Autonomous Agents and Multiagent Systems: Industrial Track, pages 125–132, 2008\.
  * [36] L. Rentschler and T. L. Turocy.  Two-bidder all-pay auctions with interdependent valuations, including the highly competitive case.  Journal of Economic Theory, 163:435 – 466, 2016.
  * [37] B. Roberson.  The Colonel Blotto game.  Economic Theory, 29(1):1–24, 2006.
  * [38] A.R.W. Robson.  Multi-item contests.  Working paper No. 446, The Australian National University, 2005\.
  * [39] G. Schwartz, P. Loiseau, and S. S. Sastry.  The heterogeneous Colonel Blotto game.  In Int. Conf. on NETwork Games, COntrol and OPtimization, pages 232–238, Oct 2014.
  * [40] E. M. Shahrivar and S. Sundaram.  Multi-layer network formation via a Colonel Blotto game.  In 2014 IEEE Global Conference on Signal and Information Processing (GlobalSIP), pages 838–841, Dec 2014.
  * [41] R. Siegel.  Asymmetric all-pay auctions with interdependent valuations.  Journal of Economic Theory, 153:684 – 702, 2014.
  * [42] M. Tambe.  Security and Game Theory: Algorithms, Deployed Systems, Lessons Learned.  Cambridge University Press, 2011.
  * [43] C. Thomas.  N-dimensional Blotto game with heterogeneous battlefield values.  Economic Theory, 65(3):509–544, 2018.
  * [44] K. G. Vamvoudakis, J. P. Hespanha, B. Sinopoli, and Y. Mo.  Detection in adversarial environments.  IEEE Transactions on Automatic Control, 59(12):3209–3223, 2014\.
  * [45] D. Q. Vu.  Models and Solutions of Strategic Resource Allocation Problems: Approximate Equilibrium and Online Learning in Blotto Games.  PhD thesis, Sorbonne Universites, UPMC University of Paris 6, 2020.
  * [46] D. Q. Vu and P. Loiseau.  Colonel blotto games with favoritism: Competitions with pre-allocations and asymmetric effectiveness.  In Proceedings of the 22nd ACM Conference on Economics and Computation, page 862–863, 2021.
  * [47] C. Wu, X. Li, W. Pan, J. Liu, and L. Wu.  Zero-sum game-based optimal secure control under actuator attacks.  IEEE Transactions on Automatic Control, 66(8):3773–3780, 2021.
  * [48] L. Xu, S. Gholami, S. McCarthy, B. Dilkina, A. Plumptre, M. Tambe, R. Singh, M. Nsubuga, J. Mabonga, M. Driciru, F. Wanyama, A. Rwetsiba, T. Okello, and E. Enyel.  Stay ahead of poachers: Illegal wildlife poaching prediction and patrol planning under uncertainty with field test evaluations (short version).  In 2020 IEEE 36th International Conference on Data Engineering (ICDE), pages 1898–1901. IEEE, 2020.
  * [49] R. Yang, B. Ford, M. Tambe, and A. Lemieux.  Adaptive resource allocation for wildlife protection against illegal poachers.  In Proceedings of the 2014 international conference on Autonomous agents and multi-agent systems, pages 453–460, 2014.

##  Appendix A Optimal deterministic assignments

The result below provides the full solution of (2.1) under the per-unit cost
setting.

######  Proposition A.1.

Consider the deterministic assignment problem (2.1). Denote
$j=\underset{i\in\\{1,2\\}}{\operatorname{arg}\,\operatorname{min}}\;\frac{\phi_{i}}{2c_{i}}$
and $k=\underset{i\in{1,2}}{\operatorname{arg}\,\operatorname{max}}\;c_{i}$.
We define the intervals
$I_{\ell}:=c_{-k}\cdot[1-\frac{\sqrt{3}}{2},1+\frac{\sqrt{3}}{2}]$ and
$I_{r}:=c_{k}\cdot[1-\frac{\sqrt{3}}{2},1+\frac{\sqrt{3}}{2}]$. Enumerate the
following four statements.

  1. (i)

For $c\notin I_{\ell}\cup I_{r}$, we have
$W_{d}^{*}=\frac{c_{1}\phi_{1}+c_{2}\phi_{2}}{8c}$,
$A_{j}^{*}=\frac{c_{1}\phi_{1}}{8c^{2}}$, and the expenditure is
$A^{*}=\frac{c_{1}\phi_{1}+c_{2}\phi_{2}}{8c^{2}}$.

  2. (ii)

For $c\in I_{r}\backslash I_{\ell}$ and $j=k$, or $c\in I_{\ell}\backslash
I_{r}$ and $j\neq k$, we have
$W_{d}^{*}=\frac{c_{-j}\phi_{-j}}{8c}+(1-\frac{c}{2c_{j}})\phi_{j}$,
$A_{j}^{*}=\frac{\phi_{j}}{2c_{j}}$, and
$A^{*}=\frac{c_{-j}\phi_{-j}}{8c^{2}}+\frac{\phi_{j}}{2c_{j}}$.

  3. (iii)

For $c\in I_{\ell}\backslash I_{r}$ and $j=k$, or $c\in I_{r}\backslash
I_{\ell}$ and $j\neq k$, we have
$W_{d}^{*}=\frac{c_{j}\phi_{j}}{8c}+(1-\frac{c}{2c_{-j}})\phi_{-j}$,
$A_{j}^{*}=\frac{c_{j}\phi_{j}}{8c^{2}}$, and
$A^{*}=\frac{c_{j}\phi_{j}}{8c^{2}}+\frac{\phi_{-j}}{2c_{-j}}$.

  4. (iv)

For $c\in I_{\ell}\cap I_{r}$, we have
$W_{d}^{*}=(1-\frac{c}{2c_{1}})\phi_{1}+(1-\frac{c}{2c_{2}})\phi_{2}$,
$A_{j}^{*}=\frac{\phi_{j}}{2c_{j}}$, and
$A^{*}=\frac{\phi_{1}}{2c_{1}}+\frac{\phi_{2}}{2c_{2}}$.

Denote
$s_{1}=\frac{1}{2}\sqrt{\frac{c_{j}}{\phi_{j}}(c_{1}\phi_{1}+c_{2}\phi_{2})}$
and
$s_{2}=\frac{c_{-j}}{2}\sqrt{\frac{c_{j}\phi_{-j}}{c_{j}\phi_{-j}-c_{-j}\phi_{j}}}$.
Then the solution of (2.1) is given as follows.

  * •

Suppose $c<\frac{c_{j}}{2}$. Then
$W_{d}^{*}=(1-\frac{c}{2c_{1}})\phi_{1}+(1-\frac{c}{2c_{2}})\phi_{2}$,
$A_{j}^{*}=\frac{\phi_{j}}{2c_{j}}$, and
$A^{*}=\frac{\phi_{1}}{2c_{1}}+\frac{\phi_{2}}{2c_{2}}$.

  * •

Suppose $\frac{c_{j}}{2}\leq c<\min\\{s_{1},s_{2}\\}$. Then the solution
follows from whether the condition of (iii) or (iv) holds.

  * •

Suppose $\min\\{s_{1},s_{2}\\}\leq c<\max\\{s_{1},s_{2}\\}$. If $s_{1}\leq
s_{2}$, then the solution follows from whether the condition of (i), (iii), or
(iv) holds. If $s_{1}>s_{2}$, then the solution follows from whether the
condition of (i), (ii), or (iv) holds.

  * •

Suppose $\max\\{s_{1},s_{2}\\}\leq c$. Then the solution follows from whether
the condition of (i), (ii), (iii), or (iv) holds.

We remark in this result that the objective of (2.1) is generally non-concave,
discontinuous, and can have up to four critical points depending on the values
of $c$, $c_{i}$, and $\phi_{i}$. We note that the most amount of resources the
commander will invest is $\frac{\phi_{1}}{2c_{1}}+\frac{\phi_{2}}{2c_{2}}$,
which occurs for low costs $c<\frac{c_{j}}{2}$. Indeed, the quantity
$\frac{\phi_{i}}{2c_{i}}$ is the amount of resources needed to win competition
$i$ outright.

The proof of Proposition A.1 relies on the following intermediate lemma that
gives the optimal deterministic assignment when the commander has zero cost
and a fixed budget.

######  Lemma A.1.

Suppose $c=0$, ${A}<\infty$, $c_{i}>0$, and $B_{i}=\infty$, $i=1,2$. The
optimal deterministic assignment is given in the following cases. Define
$Q_{i}:=\sqrt{\frac{c_{i}\phi_{i}({A}-\frac{\phi_{-i}}{2c_{-i}})}{2}}$ for
$i=1,2$.

Case 1: ${A}<\min_{i=1,2}\\{\frac{\phi_{i}}{2c_{i}}\\}$. Then
${A}_{1}^{*}=\frac{c_{1}\phi_{1}}{c_{1}\phi_{1}+c_{2}\phi_{2}}{A}$ and
$W_{\text{d}}^{*}=\sqrt{\frac{{A}(c_{1}\phi_{1}+c_{2}\phi_{2})}{2}}$.

Case 2:
$\min_{i=1,2}\\{\frac{\phi_{i}}{2c_{i}}\\}\leq{A}<\max_{i=1,2}\\{\frac{\phi_{i}}{2c_{i}}\\}$.
Let
$j=\underset{i\in\\{1,2\\}}{\operatorname{arg}\,\operatorname{min}}\;\\{\frac{\phi_{i}}{2c_{i}}\\}$.
If ${A}\geq\frac{c_{1}\phi_{1}+c_{2}\phi_{2}}{2c_{j}^{2}}$, then
${A}_{1}^{*}=\frac{\phi_{j}}{2c_{j}}$ and $W_{\text{d}}^{*}=\phi_{j}+Q_{-j}$.
If ${A}<\frac{c_{1}\phi_{1}+c_{2}\phi_{2}}{2c_{j}^{2}}$, then

$\displaystyle{A}_{j}^{*}$
$\displaystyle=\begin{cases}\frac{\phi_{j}}{2c_{j}},&\text{if
}\phi_{j}+Q_{-j}\geq\sqrt{\frac{{A}(c_{1}\phi_{1}+c_{2}\phi_{2})}{2}}\\\
\frac{c_{j}\phi_{j}}{c_{1}\phi_{1}+c_{2}\phi_{2}}{A},&\text{if
}\phi_{j}+Q_{-j}<\sqrt{\frac{{A}(c_{1}\phi_{1}+c_{2}\phi_{2})}{2}}\\\
\end{cases}$ (A.1) $\displaystyle W_{\text{d}}({A}_{1}^{*})$
$\displaystyle=\max\left\\{\phi_{j}+Q_{-j},\sqrt{\frac{{A}(c_{1}\phi_{1}+c_{2}\phi_{2})}{2}}\right\\}$

Case 3:
$\max_{i=1,2}\\{\frac{\phi_{i}}{2c_{i}}\\}\leq{A}<\frac{\phi_{1}}{2c_{1}}+\frac{\phi_{2}}{2c_{2}}$.
Then

$\displaystyle{A}_{j}^{*}=\begin{cases}{A}-\frac{\phi_{-j}}{2c_{-j}},&\text{if
}\phi_{-j}+Q_{j}\geq\phi_{j}+Q_{-j}\\\ \frac{\phi_{j}}{2c_{j}},&\text{if
}\phi_{-j}+Q_{j}<\phi_{j}+Q_{-j}\\\ \end{cases}\quad\text{and}\quad
W_{\text{d}}^{*}=\max_{i=1,2}\left\\{\phi_{i}+Q_{-i}\right\\}$ (A.2)

Case 4: $\frac{\phi_{1}}{2c_{1}}+\frac{\phi_{2}}{2c_{2}}\leq{A}$. Then
${A}_{1}^{*}\in[\frac{\phi_{1}}{2c_{1}},{A}-\frac{\phi_{2}}{2c_{2}})$ and
$W_{\text{d}}^{*}=\phi_{1}+\phi_{2}$.

###### Proof.

Let us denote the objective of (2.1) as $W_{\text{d}}({A}_{1})$ for
${A}_{1}\in[0,{A}]$.

Case 1: The objective is written as
$W_{\text{d}}({A}_{1})=\sqrt{\frac{c_{1}\phi_{1}{A}_{1}}{2}}+\sqrt{\frac{c_{2}\phi_{2}({A}-{A}_{1})}{2}}$
for all ${A}_{1}\in[0,{A}]$. This function is concave and the derivative is
zero at
${A}_{1}^{*}=\frac{c_{1}\phi_{1}}{c_{1}\phi_{1}+c_{2}\phi_{2}}{A}\in[0,{A}]$.

Case 2: Suppose $\frac{\phi_{1}}{2c_{1}}\leq\frac{\phi_{2}}{2c_{2}}$
(analogous arguments when the opposite holds). The objective is written as

$W_{\text{d}}({A}_{1})=\begin{cases}\sqrt{\frac{c_{1}\phi_{1}{A}_{1}}{2}}+\sqrt{\frac{c_{2}\phi_{2}({A}-{A}_{1})}{2}},&\text{if
}{A}_{1}\in[0,\frac{\phi_{1}}{2c_{1}})\\\
\phi_{1}+\sqrt{\frac{c_{2}\phi_{2}({A}-{A}_{1})}{2}},&\text{if
}{A}_{1}\in[\frac{\phi_{1}}{2c_{1}},{A}]\end{cases}$ (A.3)

It is strictly decreasing on the second interval and takes its highest value
$\phi_{1}+Q_{2}$ at ${A}_{1}=\frac{\phi_{1}}{2c_{1}}$. It is strictly
increasing on the first interval if
$c_{1}<\frac{1}{2}\left[\frac{\phi_{1}}{2{A}}+\sqrt{\left(\frac{\phi_{1}}{2{A}}\right)^{2}+\frac{2c_{2}\phi_{2}}{{A}}}\right]$
(equivalently ${A}\geq\frac{c_{1}\phi_{1}+c_{2}\phi_{2}}{2c_{1}^{2}}$), taking
its highest value $\frac{\phi_{1}}{2}+Q_{2}<\phi_{1}+Q_{2}$. When
${A}<\frac{c_{1}\phi_{1}+c_{2}\phi_{2}}{2c_{1}^{2}}$, it takes its highest
value in the first interval,
$\sqrt{\frac{{A}(c_{1}\phi_{1}+c_{2}\phi_{2})}{2}}$, at
${A}_{1}=\frac{c_{1}\phi_{1}}{c_{1}\phi_{1}+c_{2}\phi_{2}}{A}$.

Case 3: The objective is written as

$W_{\text{d}}({A}_{1})=\begin{cases}\sqrt{\frac{c_{1}\phi_{1}{A}_{1}}{2}}+\phi_{2},&\text{if
}{A}_{1}\in[0,{A}-\frac{\phi_{2}}{2c_{2}})\\\
\sqrt{\frac{c_{1}\phi_{1}{A}_{1}}{2}}+\sqrt{\frac{c_{2}\phi_{2}({A}-{A}_{1})}{2}},&\text{if
}{A}_{1}\in[{A}-\frac{\phi_{2}}{2c_{2}},\frac{\phi_{1}}{2c_{1}})\\\
\phi_{1}+\sqrt{\frac{c_{2}\phi_{2}({A}-{A}_{1})}{2}},&\text{if
}{A}_{1}\in[\frac{\phi_{1}}{2c_{1}},{A}]\end{cases}$ (A.4)

It is strictly increasing (decreasing) on the first (third) interval, taking
the maximum value of $\phi_{2}+Q_{1}$ ($\phi_{1}+Q_{2}$). The value in the
middle interval is upper bounded by
$\sqrt{\frac{{A}(c_{1}\phi_{1}+c_{2}\phi_{2})}{2}}\leq\frac{\phi_{1}+\phi_{2}}{2}$.
The objective will never take the maximal value in the middle interval because
$\phi_{i}+Q_{-i}>\frac{\phi_{1}+\phi_{2}}{2}$ for some $i=1,2$.

Case 4: The objective is written as

$W_{\text{d}}({A}_{1})=\begin{cases}\sqrt{\frac{c_{1}\phi_{1}{A}_{1}}{2}}+\phi_{2},&\text{if
}{A}_{1}\in[0,\frac{\phi_{1}}{2c_{1}})\\\ \phi_{1}+\phi_{2},&\text{if
}{A}_{1}\in[\frac{\phi_{1}}{2c_{1}},{A}-\frac{\phi_{2}}{2c_{2}})\\\
\phi_{1}+\sqrt{\frac{c_{2}\phi_{2}({A}-{A}_{1})}{2}},&\text{if
}{A}_{1}\in[{A}-\frac{\phi_{2}}{2c_{2}},{A}]\end{cases}$ (A.5)

which is maximized for any
${A}_{1}\in[\frac{\phi_{1}}{2c_{1}},{A}-\frac{\phi_{2}}{2c_{2}})$. ∎

###### Proof of Proposition A.1.

The solution of (2.1) under the per-unit cost setting follows from solving the
optimization problem

$\max_{{A}\geq 0}\\{W_{\text{d}}^{*}({A})-c{A}\\}$ (A.6)

where we denote $W_{\text{d}}^{*}({A})$ as the performance characterized from
Lemma A.1. In general, the objective above is not concave and there are at
most three points of discontinuity. There may exist up to four critical points
in ${A}\in[0,\infty)$, depending on the value of $c$. These points are
indicated by ${A}^{*}$ in the enumerated list (i) - (iv) from the Proposition
statement. A critical point exists on the interval
${A}\in(0,\min_{i=1,2}\\{\frac{\phi_{i}}{2c_{i}}\\})$ if
$c>\frac{1}{2}\sqrt{\frac{c_{j}}{\phi_{j}}(c_{1}\phi_{1}+c_{2}\phi_{2})}$, on
the interval ${A}\in[\frac{\phi_{j}}{2c_{j}},\frac{\phi_{-j}}{2c_{-j}})$ if
$c>\frac{c_{-j}}{2}\sqrt{\frac{c_{j}\phi_{-j}}{c_{j}\phi_{-j}-c_{-j}\phi_{j}}}$,
and on the interval
${A}\in[\frac{\phi_{-j}}{2c_{-j}},\frac{\phi_{1}}{2c_{1}}+\frac{\phi_{2}}{2c_{2}})$
if $c>\frac{c_{j}}{2}$. A critical point always exists at
${A}=\frac{\phi_{1}}{2c_{1}}+\frac{\phi_{2}}{2c_{2}}$, as 0 is always
contained in the sub-differential. The largest critical point is determined by
the conditions listed as (i) to (iv) in the statement of Proposition A.1. ∎

##  Appendix B Optimal randomized assignments

The result below gives the solution to (2.3) under the per-unit costs setting.

######  Proposition B.1.

Consider the assignment problem (2.3) under the per-unit cost setting. The
optimal performance $W^{*}$, assignment $\mathbb{P}^{*}$, and expected
resource expenditure ${A}^{*}$ are given as follows. Let
$k=\underset{i=1,2}{\operatorname{arg}\,\operatorname{max}}\;c_{i}$.

$\bullet$ If $c\leq c_{-k}$, then
$W^{*}=(1-\frac{c}{2c_{1}})\phi_{1}+(1-\frac{c}{2c_{2}})\phi_{2}$ and
$\mathbb{P}^{*}(\frac{\phi_{1}}{2c_{1}},\frac{\phi_{2}}{2c_{2}})=1$. The
resource expenditure is
${A}^{*}=\frac{\phi_{1}}{2c_{1}}+\frac{\phi_{2}}{2c_{2}}$.

$\bullet$ If $c_{-k}<c<c_{k}$, then $W^{*}=\phi_{k}+\frac{c_{-k}}{c}\phi_{-k}$
and

$\displaystyle\mathbb{P}_{k}^{*}(\frac{\phi_{k}}{2c_{k}})=1\quad\text{and}\quad\mathbb{P}_{-k}^{*}=\left(\frac{\phi_{-k}}{2c},0,\frac{c_{-k}}{c}\right).$
(B.1)

The expected resource expenditure is
${A}^{*}=\frac{c_{-k}\phi_{-k}}{2c^{2}}+\frac{\phi_{k}}{2c_{k}}$.

$\bullet$ If $c\geq c_{k}$, then
$W^{*}=\frac{c_{1}\phi_{1}+c_{2}\phi_{2}}{2c}$ and

$\displaystyle\mathbb{P}^{*}(0,0)=(1-c_{1}/c)(1-c_{2}/c),\quad$
$\displaystyle\mathbb{P}^{*}\left(0,\frac{\phi_{2}}{2c}\right)=(1-c_{1}/c)\cdot(c_{2}/c)$
(B.2)
$\displaystyle\mathbb{P}^{*}\left(\frac{\phi_{1}}{2c},0\right)=(c_{1}/c)\cdot(1-c_{2}/c),$
$\displaystyle\mathbb{P}^{*}\left(\frac{\phi_{1}}{2c},\frac{\phi_{2}}{2c}\right)=\frac{c_{1}c_{2}}{c^{2}}$

The expected resource expenditure is
${A}^{*}=\frac{c_{1}\phi_{1}+c_{2}\phi_{2}}{2c^{2}}$.

We note in the result above that the optimal assignment is completely
deterministic when the commander’s cost is low ($c\leq c_{-k}$), and is
randomized on both marginals if the cost is sufficiently high ($c\geq c_{k}$).

The proof of Proposition B.1 relies on the following intermediate lemma that
gives the optimal randomized assignment when the commander has zero cost and a
fixed budget.

######  Lemma B.1.

Suppose $c=0$, ${A}<\infty$, and $B_{i}=\infty$, $i=1,2$. The optimal
distribution $\mathbb{P}^{*}$ on resource assignments and the resulting
payoffs are given by the following cases.

Case 1: Suppose
${A}<\min_{i=1,2}\frac{c_{1}\phi_{1}+c_{2}\phi_{2}}{2c_{i}^{2}}$. Let
${A}_{1}^{*}=\frac{c_{1}\phi_{1}{A}}{c_{1}\phi_{1}+c_{2}\phi_{2}}$,
${A}_{2}^{*}=\frac{c_{2}\phi_{2}{A}}{c_{1}\phi_{1}+c_{2}\phi_{2}}$,
$p_{1}^{*}=\sqrt{2c_{1}{A}_{1}^{*}/\phi_{1}}$, and
$p_{2}^{*}=\sqrt{2c_{2}{A}_{2}^{*}/\phi_{2}}$. Then

$\displaystyle\mathbb{P}^{*}(0,0)=(1-p_{1}^{*})(1-p_{2}^{*}),\quad$
$\displaystyle\mathbb{P}^{*}\left(0,\sqrt{\frac{{A}_{2}^{*}\phi_{2}}{2c_{2}}}\right)=(1-p_{1}^{*})p_{2}^{*}$
(B.3)
$\displaystyle\mathbb{P}^{*}\left(\sqrt{\frac{{A}_{1}^{*}\phi_{1}}{2c_{1}}},0\right)=p_{1}^{*}(1-p_{2}^{*}),\quad$
$\displaystyle\mathbb{P}^{*}\left(\sqrt{\frac{{A}_{1}^{*}\phi_{1}}{2c_{1}}},\sqrt{\frac{{A}_{2}^{*}\phi_{2}}{2c_{2}}}\right)=p_{1}^{*}p_{2}^{*}$

The resulting performance is $W^{*}=\sqrt{2{A}(c_{1}\phi_{1}+c_{2}\phi_{2})}$.

Case 2: Suppose
$\min_{i=1,2}\frac{c_{1}\phi_{1}+c_{2}\phi_{2}}{2c_{i}^{2}}\leq{A}<\frac{\phi_{1}}{2c_{1}}+\frac{\phi_{2}}{2c_{2}}$.
Let $k=\underset{i=1,2}{\operatorname{arg}\,\operatorname{max}}\;c_{i}$,
${A}_{k}^{*}=\frac{\phi_{k}}{2c_{k}}$,
${A}_{-k}^{*}={A}-\frac{\phi_{k}}{2c_{k}}$, and
$p_{-k}^{*}=\sqrt{2c_{-k}{A}_{-k}^{*}/\phi_{-k}}$. Then

$\displaystyle\mathbb{P}_{k}^{*}({A}_{k}^{*})=1\quad\text{and}\quad\mathbb{P}_{-k}^{*}=\left(\sqrt{\frac{{A}_{-k}^{*}\phi_{-k}}{2c_{-k}}},0,p_{-k}^{*}\right).$
(B.4)

The resulting performance is
$W^{*}=\phi_{k}+\sqrt{2c_{-k}\phi_{-k}\left({A}-\frac{\phi_{k}}{2c_{k}}\right)}$.

Case 3: Suppose ${A}\geq\frac{\phi_{1}}{2c_{1}}+\frac{\phi_{2}}{2c_{2}}$. Then
any $\mathbb{P}^{*}$ that satisfies
$\mathbb{P}^{*}({A}_{1}^{*},{A}_{2}^{*})=1$ for some
${A}_{1}^{*}\in[\frac{\phi_{1}}{2c_{1}},{A}-\frac{\phi_{2}}{2c_{2}}]$ and
${A}_{2}^{*}={A}-{A}_{1}^{*}$ is an optimal assignment. The resulting
performance is $W^{*}=\phi_{1}+\phi_{2}$.

###### Proof.

Note that any feasible $\mathbb{P}\in\mathcal{P}({A})$ induces expected
endowments ${A}_{i}=p_{i}A_{i}^{(1)}+(1-p_{i})A_{i}^{(2)}$ for each sub-
colonel, where ${A}_{1}+{A}_{2}={A}$ is satisfied. For given expected
endowments ${A}_{1},{A}_{2}$, the distribution $\mathbb{P}$ that maximizes the
objective (2.3) is one whose marginals coincide with the optimal
randomizations for each sub-colonel, which are given by (4.15). The
corresponding optimal payoff to sub-colonel $i$ is given by (4.14), denoted by

$\Pi_{i}^{*}({A}_{i},\infty,c_{i}|\phi_{i})=\begin{cases}\sqrt{2c_{i}\phi_{i}{A}_{i}},&\text{if
}{A}_{i}\leq\frac{\phi_{i}}{2c_{i}}\\\ \phi_{i},&\text{if
}{A}_{i}>\frac{\phi_{i}}{2c_{i}}\\\ \end{cases}$ (B.5)

Thus, the optimization (2.3) is equivalent to determining the optimal expected
endowment to sub-colonel 1:

$\max_{{A}_{1}\in[0,{A}]}\\{\Pi_{1}^{*}({A}_{1},c_{1}|\phi_{1})+\Pi_{2}^{*}({A}-{A}_{1},c_{2}|\phi_{2})\\}$
(B.6)

Let us denote the objective function in the brackets above as $W({A}_{1})$. It
takes distinct forms depending on the values $\\{c_{i},\phi_{i}\\}_{i=1,2}$:

(a) $c_{1}<\frac{\phi_{1}}{2{A}}$ and $c_{2}<\frac{\phi_{2}}{2{A}}$. The
objective is written as
$\sqrt{2c_{1}\phi_{1}{A}_{1}}+\sqrt{2c_{2}\phi_{2}({A}-{A}_{1})},\
\forall{A}_{1}\in[0,{A}]$. This function is concave. Setting the derivative
(w.r.t. ${A}_{1}$) to zero, we obtain
${A}_{1}^{*}=\frac{c_{1}\phi_{1}}{c_{1}\phi_{1}+c_{2}\phi_{2}}{A}$ and the
optimal payoff is $\sqrt{2{A}(c_{1}\phi_{1}+c_{2}\phi_{2})}$. Here, the
distribution $P^{*}$ corresponding to Case 1 in the Theorem statement induces
the randomizations given by (4.15) for each sub-colonel.

(b) ${A}<\frac{\phi_{1}}{2c_{1}}$ and ${A}\geq\frac{\phi_{2}}{2c_{2}}$. The
objective is written as

$W({A}_{1})=\begin{cases}\sqrt{2c_{1}\phi_{1}{A}_{1}}+\phi_{2},&\text{if
}{A}_{1}\in[0,{A}-\frac{\phi_{2}}{2c_{2}})\\\
\sqrt{2c_{1}\phi_{1}{A}_{1}}+\sqrt{2c_{2}\phi_{2}({A}-{A}_{1})},&\text{if
}{A}_{1}\in[{A}-\frac{\phi_{2}}{2c_{2}},{A}]\\\ \end{cases}$ (B.7)

This function is concave and continuous on $[0,{A}]$. It is strictly
increasing on the first interval. It is strictly decreasing for
${A}_{1}>\frac{c_{1}\phi_{1}{A}}{c_{1}\phi_{1}+c_{2}\phi_{2}}$. The maximizer
is given by

${A}_{1}^{*}=\begin{cases}{A}-\frac{\phi_{2}}{2c_{2}},&\text{if
}c_{2}>r_{2}(c_{1})\\\
\frac{c_{1}\phi_{1}}{c_{1}\phi_{1}+c_{2}\phi_{2}}{A},&\text{if }c_{2}\leq
r_{2}(c_{1})\\\ \end{cases}$ (B.8)

where we define
$r_{i}(c_{-i})=\frac{1}{2}\left[\frac{\phi_{i}}{2{A}}+\sqrt{\left(\frac{\phi_{i}}{2{A}}\right)^{2}+\frac{2c_{-i}\phi_{-i}}{{A}}}\right]$
for $i=1,2$. The condition $c_{2}\leq r_{2}(c_{1})$ above arises when the
derivative of the second entry in (B.7) is positive at
${A}_{1}={A}-\frac{\phi_{2}}{2c_{2}}$. Hence, when $c_{2}>r_{2}(c_{1})$,
${A}_{1}^{*}={A}-\frac{\phi_{2}}{2c_{2}}$. Therefore, if $c_{2}\leq
r_{2}(c_{1})$, the solution $\mathbb{P}^{*}$ corresponds to Case 1. If
$c_{2}>r_{2}(c_{1})$, the solution $\mathbb{P}^{*}$ corresponds to Case 2
($k=2$).

(c) $c_{1}\geq\frac{\phi_{1}}{2{A}}$ and $c_{2}<\frac{\phi_{2}}{2{A}}$. The
objective is written as

$W({A}_{1})=\begin{cases}\sqrt{2c_{1}\phi_{1}{A}_{1}}+\sqrt{2c_{2}\phi_{2}({A}-{A}_{1})},&\text{if
}{A}_{1}\in[0,\frac{\phi_{1}}{2c_{1}}]\\\
\phi_{1}+\sqrt{2c_{2}\phi_{2}({A}-{A}_{1})},&\text{if
}{A}_{1}\in(\frac{\phi_{1}}{2c_{1}},{A}]\\\ \end{cases}$ (B.9)

Analogous arguments from (b) yield

${A}_{1}^{*}=\begin{cases}\frac{\phi_{1}}{2c_{1}},&\text{if
}c_{1}>r_{1}(c_{2})\\\
\frac{c_{1}\phi_{1}}{c_{1}\phi_{1}+c_{2}\phi_{2}}{A},&\text{if }c_{1}\leq
r_{1}(c_{2})\\\ \end{cases}$ (B.10)

Here, the optimal distribution $\mathbb{P}^{*}$ corresponds to Case 1 if
$c_{1}\leq r_{1}(c_{2})$ and Case 2 ($k=1$) if $c_{1}>r_{1}(c_{2})$.

(d) $c_{1}\geq\frac{\phi_{1}}{2{A}}$ and $c_{2}\geq\frac{\phi_{2}}{2{A}}$.
First, we consider the sub-case
${A}-\frac{\phi_{2}}{2c_{2}}<\frac{\phi_{1}}{2c_{1}}$. The objective is
written as

$W({A}_{1})=\begin{cases}\sqrt{2c_{1}\phi_{1}{A}_{1}}+\phi_{2},&\text{if
}{A}_{1}\in[0,{A}-\frac{\phi_{2}}{2c_{2}})\\\
\sqrt{2c_{1}\phi_{1}{A}_{1}}+\sqrt{2c_{2}\phi_{2}({A}-{A}_{1})},&\text{if
}{A}_{1}\in[{A}-\frac{\phi_{2}}{2c_{2}},\frac{\phi_{1}}{2c_{1}}]\\\
\phi_{1}+\sqrt{2c_{2}\phi_{2}({A}-{A}_{1})},&\text{if
}{A}_{1}\in(\frac{\phi_{1}}{2c_{1}},{A}]\\\ \end{cases}$ (B.11)

This function is concave, strictly increasing on
$[0,{A}-\frac{\phi_{2}}{2c_{2}})$, and strictly decreasing on
$(\frac{\phi_{1}}{2c_{1}},{A}]$. The maximizer is given by

${A}_{1}^{*}=\begin{cases}{A}-\frac{\phi_{2}}{2c_{2}},&\text{if
}c_{2}>r_{2}(c_{1})\\\
\frac{c_{1}\phi_{1}}{c_{1}\phi_{1}+c_{2}\phi_{2}}{A},&\text{if }c_{2}\leq
r_{2}(c_{1})\text{ and }c_{1}\leq r_{1}(c_{2})\\\
\frac{\phi_{1}}{2c_{1}},&\text{if }c_{1}>r_{1}(c_{2})\end{cases}$ (B.12)

Thus, the optimal distribution $P^{*}$ corresponds to Case 2 ($k=2$) if
$c_{2}>r_{2}(c_{1})$, to Case 1 if $c_{2}\leq r_{2}(c_{1})$ and $c_{1}\leq
r_{1}(c_{2})$, and to Case 2 ($k=1$) if $c_{1}>r_{1}(c_{2})$.

Lastly, we consider the sub-case
${A}-\frac{\phi_{2}}{2c_{2}}\geq\frac{\phi_{1}}{2c_{1}}$. The objective can be
written as

$W({A}_{1})=\begin{cases}\sqrt{2c_{1}\phi_{1}{A}_{1}}+\phi_{2},&\text{if
}{A}_{1}\in[0,\frac{\phi_{1}}{2c_{1}})\\\ \phi_{1}+\phi_{2},&\text{if
}{A}_{1}\in[\frac{\phi_{1}}{2c_{1}},{A}-\frac{\phi_{2}}{2c_{2}}]\\\
\phi_{1}+\sqrt{2c_{2}\phi_{2}({A}-{A}_{1})},&\text{if
}{A}_{1}\in({A}-\frac{\phi_{2}}{2c_{2}},{A}]\\\ \end{cases}$ (B.13)

The optimal distribution $\mathbb{P}^{*}$ here corresponds to Case 3. ∎

###### Proof of Proposition B.1.

The solution of (2.3) under per-unit costs follows from solving the
optimization problem

$\max_{{A}\geq 0}\\{W^{*}({A})-c{A}\\}$ (B.14)

where we denote $W^{*}({A})$ as the performance from Lemma B.1. It is a
concave objective, and the critical point ${A}^{*}$ lies in
$(0,\min_{i=1,2}\frac{c_{1}\phi_{1}+c_{2}\phi_{2}}{2c_{i}^{2}})$,
$[\min_{i=1,2}\frac{c_{1}\phi_{1}+c_{2}\phi_{2}}{2c_{i}^{2}},\frac{\phi_{1}}{2c_{1}}+\frac{\phi_{2}}{2c_{2}})$,
or at ${A}^{*}=\frac{\phi_{1}}{2c_{1}}+\frac{\phi_{2}}{2c_{2}}$ depending on
whether $c\geq\max_{i}c_{i}$, $c\in(\min_{i}c_{i},\max_{i}c_{i})$, or
$c\leq\min_{i}c_{i}$, respectively. ∎

###### Proof of Theorem 3.1, second part.

By comparing the characterizations from Propositions A.1 and B.1, we identify
the four-fold improvement in the regime specified in the statement (first case
in Prop. A.1, last case in Prop. B.1). Outside of this regime, the improvement
factor is less than four. ∎

##  Appendix C Equilibrium characterizations of the BL game

This appendix is devoted to the proof of Lemma 4.1 – the characterization of
equilibrium payoffs in the Bernoulli General Lotto game. To do so, we derive
the equilibrium strategies for player $A$ and $B$ in any game instance
$\text{BL}(\mathbb{P}_{A},B,0)$. First, we establish a connection between the
necessary conditions for equilibrium in two-player all-pay auctions with
asymmetric information and the BL game (Section C.2). We then leverage
equilibrium solutions to such all-pay auctions (Section C.3), provided by
[41], to formulate a system of non-linear equations in the Lagrange
multipliers $\boldsymbol{\lambda}$ associated with the players’ Lotto expected
budget constraints (2.5). This system of equations is stated in Section C.4,
and can take three different forms, which correspond to disjoint regions in
the multiplier space. Hence, solutions to this system are not only algebraic,
but also case-dependent.

We completely characterize solutions to these equations in Proposition C.1,
finding they exist only for a subset of BL games we are interested in (region
$\mathcal{R}_{5}$). Indeed, the algorithm in [41] constructs equilibrium
strategies to the auctions when certain monotonicity conditions are met –
players’ types are required to be somewhat correlated to their valuations.
While these informational requirements hold in the BL games we are interested
in, we find the structure of the auction strategies cannot accommodate all
possible combinations of budget parameters $A_{1},A_{2},B$, limiting the
applicability of [41] to the sub-region $\mathcal{R}_{5}$. Nonetheless, we
prove that solutions to the system of equations, when they exist, correspond
to equilibria of the BL game (Proposition C.1).

We then identify the remaining regions $\mathcal{R}_{i}$, $i=1,\ldots,4$ to
have distinct equilibrium structures that cannot be calculated from the
aforementioned system of equations. For these equilibria, we combine features
of the equilibrium strategies from complete information Lotto games with those
that were computed through the system of equations. These details are given in
the Section C.5, thus completing the proof of Lemma 4.1. We first review all-
pay auctions with asymmetric information, as studied by Siegel in [41].

###  C.1 All-pay auctions with asymmetric information and valuations

In an all-pay auction, two bidders ($A$ and $B$) compete over a single item.
Before bids are submitted, player $A$ privately observes one of two possible
types: $t_{1}$ (type 1) with a probability $p$ and $t_{2}$ (type 2) with
$1-p$. Here, it is assumed $p$ is common knowledge and $p>0$. Player $B$
always observes the same type $t_{B}$. Hence, there are two possible type
profiles444Siegel’s model is general, allowing an arbitrary, finite number of
types for each player. We review the model here with two types, since it
pertains to our BL game, and for simpler exposition., corresponding to whether
A observes $t_{1}$ or $t_{2}$. In type $i\in\\{1,2\\}$, the players’
valuations for the item are $v_{A,i}$ and $v_{B,i}$ for player $A$ and B,
respectively.

A (pure) strategy for player $A$ is a pair
$\boldsymbol{x}_{A}=(x_{1},x_{2})\in\mathbb{R}_{+}^{2}$, where $x_{i}$ is its
bid for the item contingent on receiving type $i$. A strategy for player $B$
is a non-negative bid $x_{B}\geq 0$. The resulting payoffs are given by

$\displaystyle p\left(v_{A,1}\cdot
W_{A}(x_{1},x_{B})-x_{1}\right)+(1-p)\left(v_{A,2}\cdot
W_{A}(x_{2},x_{B})-x_{2}\right)\quad\text{(Player A)}$ (C.1) $\displaystyle
p\left(v_{B,1}\cdot W_{B}(x_{B},x_{1})-x_{B}\right)+(1-p)\left(v_{B,2}\cdot
W_{B}(x_{B},x_{2})-x_{B}\right)\quad\text{(Player B)}$

where $W_{\ell}$, $\ell\in\\{A,B\\}$ is defined as555The choice of tie-
breaking rule can be made arbitrarily, as it will not ultimately affect
equilibrium payoffs. Here, we assume ties favor player $B$.

$W_{\ell}(a,b)=\begin{cases}1,&\text{if }a>b\text{ or }a=b\text{ and
}\ell=B\\\ 0,&\text{otherwise}\end{cases}$ (C.2)

A mixed strategy for player $A$ is a pair $\\{F_{A}^{(i)}\\}_{i=1,2}$, where
$F_{A}^{(i)}$ is a univariate probability distribution on $\mathbb{R}_{+}$. A
mixed strategy for player $B$ is a single univariate distribution $F_{B}$ on
$\mathbb{R}_{+}$. The payoffs are calculated as the expected payoffs with
respect to the distribution $p$ and the mixed strategies. We refer to this
auction as $\text{APA}(v_{A},v_{B},p)$.

Note that we have adapted this model to the information structure of our BL
game. In general, Siegel’s model allows for arbitrary, finite type spaces
$\mathcal{T}_{A}$ and $\mathcal{T}_{B}$ with a joint probability distribution
$\boldsymbol{p}$ on the type profiles. Siegel shows equilibria can be computed
algorithmically, provided the following monotonicity condition is met for some
ordering of the players’ type spaces.

$\text{For any $t_{-\ell}\in\mathcal{T}_{-\ell}$,
}v_{\ell}(t_{\ell},t_{-\ell})\cdot p(t_{-\ell}|t_{\ell})\text{ is non-
decreasing in $t_{\ell}\in\mathcal{T}_{\ell}$,}\quad\ell\in\\{A,B\\}$ (WM)

where $p(t_{-\ell}|t_{\ell})$ denotes conditional probabilities associated
with the joint distribution $\boldsymbol{p}$, and
$v_{\ell}(t_{\ell},t_{-\ell})$ is player $\ell$’s item valuation in type
profile $(t_{\ell},t_{-\ell})$. When (WM) holds, a _monotonic_ 666An
equilibrium is monotonic if any best-response bid for player $\ell$ in type
$t_{\ell}$ against the equilibrium strategy of player $-\ell$ is not lower
than any best-response bid in a lower type $t\preceq_{\ell}t_{\ell}$. When
(WM) is not met, non-monotonic equilibria to APA have been characterized in
[36]. However, for the central case of interest in this paper for which one
player is informed and the other uninformed, (WM) is always met. We leave the
characterization of Lotto equilibria when (WM) is not met as an open problem,
e.g. players have partial and different information. equilibrium in mixed
strategies to APA can explicitly be computed through an iterative procedure
[41] (we refer to as “Siegel’s algorithm”), where the number of iterations is
at most $|\mathcal{T}_{A}|+|\mathcal{T}_{B}|$. When a strict version of (WM)
holds, the constructed monotonic equilibrium is the unique equilibrium of APA.
Observe that (WM) is always satisfied if player $B$ only has a single type
$t_{B}$, and the types of A are ordered according to the valuations
$v_{A}(t_{i},t_{B})$. The informational structure of our BL game belongs to
such “informed-uninformed” settings.

Equilibria of APA have been characterized when (WM) is not met. In fact, [36]
provides an algorithm that generalizes Siegel’s algorithm to calculate such
non-monotonic equilibria. When (WM) is not met, this algorithm can become
quite complex. In the “informed-uninformed” scenarios, this algorithm reduces
to Siegel’s algorithm.

###  C.2 Connection between APA and Bernoulli General Lotto games

We now present some informal intuition that suggests a connection between the
equilibria of APA and $\text{BL}(\mathbb{P}_{A},B,0)$, the Bernoulli Lotto
game with zero cost for player $B$. These insights are analogous to those
drawn between two-player all-pay auctions with complete information and the
Colonel Blotto and General Lotto games [3, 37, 29].

Consider a game instance $\text{BL}(\mathbb{P}_{A},B,0)$, which we will often
refer to as the tuple of parameters $G=(A_{1},A_{2},p,B)$. For ease of
exposition, we will assume that the sum of battlefield values is normalized to
one, i.e. $\|\boldsymbol{v}\|_{1}=1$. The Lotto budget constraint (2.5) must
hold for the strategies associated in each type. Player $A$’s ex-interim
constrained optimization, given type $i$ is realized, can be written as

$\max_{\\{F_{A,j}^{(i)}\\}_{j\in[n]}}\sum_{j\in[n]}\int_{0}^{\infty}\left[v_{j}F_{B,j}(x_{A,j})-\lambda_{i}x_{A,j}\right]\,dF_{A,j}^{(i)}+\lambda_{i}A_{i}$
(C.3)

where $\lambda_{i}$ is the multiplier on player $A$’s expected budget
constraint for type $i$, and we denote $p_{1}=p$ and $p_{2}=1-p$. Player B’s
constrained optimization is written as

$\max_{\\{F_{B,j}\\}_{j\in[n]}}\sum_{j\in[n]}\sum_{i=1,2}p_{i}\int_{0}^{\infty}\left[v_{j}F_{A,j}^{(i)}(,x_{B,j})-\lambda_{B}x_{B,j}\right]\,dF_{B,j}+\lambda_{B}B.$
(C.4)

where $\lambda_{B}$ is the multiplier on player $B$’s budget. The necessary
first-order conditions for equilibrium are

$\displaystyle\frac{d}{dx_{B,j}}\left[\sum_{i=1,2}p_{i}\left(v_{j}F_{A,j}^{(i)}(x_{B,j})-\lambda_{B}x_{B,j}\right)\right]=0$
(C.5)
$\displaystyle\frac{d}{dx_{A,j}}\left[v_{j}F_{B}(x_{A,j})-\lambda_{i}x_{A,j}\right]=0,\quad
i=1,2$

Dividing by the associated (positive) multiplier in each condition, this
coincides with the necessary first-order conditions for equilibrium of $n$
independent two-player all-pay auctions with incomplete information for which
the item valuation in auction $j$ for player $A$ in type $i$ is
$v_{A,i}=\frac{v_{j}}{\lambda_{i}}$, and the valuation for player $B$ when
player $A$’s type is $i$ is $v_{B,i}=\frac{v_{j}}{\lambda_{B}}$.

The equilibria to each of the $n$ APA games can be computed using Siegel’s
algorithm, as long as (WM) is satisfied777As discussed earlier, the algorithm
of [36] can handle APA when (WM) is not met. We do not detail this algorithm
here, however, because of its complexity and because Siegel’s algorithm
suffices for the problems of interest in this paper.. However, since we do not
know the actual ranking of player $A$’s types, i.e. whether
$\lambda_{1}\leq\lambda_{2}$ or vice versa, we must proceed by first imposing
such a ranking. For the sake of demonstration, let us suppose
$\lambda_{1}\leq\lambda_{2}$, so that type 1 is “higher” than type 2, for
instance. This allows us to proceed with Siegel’s algorithm, which generates
bidding distributions $\\{F_{A,j}^{(i),\boldsymbol{\lambda}}\\}_{i=1,2}$ and
$F_{B,j}^{\boldsymbol{\lambda}}$ for each $j\in[n]$. Here, the superscript
indicates the expressions are in terms of the (still) unknown multipliers.
These distributions must be consistent with the Lotto expected budget
constraints (2.5), yielding a system of three equations in
$\boldsymbol{\lambda}=(\lambda_{1},\lambda_{2},\lambda_{B})$.

$\displaystyle\sum_{j\in[n]}\mathbb{E}_{x_{A,j}\sim
F_{A,j}^{(i),\boldsymbol{\lambda}}}[x_{A,j}]=A_{i},\quad i=1,2$ (C.6)
$\displaystyle\sum_{j\in[n]}\mathbb{E}_{x_{B,j}\sim
F_{B}^{\boldsymbol{\lambda}}}[x_{B,j}]=B$ $\displaystyle\text{such that
}0<\lambda_{1}\leq\lambda_{2}$

Hence, we seek to find a solution to (C.6). In the next sections, we detail
the distributions $\\{F_{A}^{(i),\boldsymbol{\lambda}}\\}_{i=1,2}$ and
$F_{B}^{\boldsymbol{\lambda}}$ constructed from Siegel’s algorithm and apply
them to (C.6) to explicitly derive the system of equations.

###  C.3 Equilibrium strategies of APA

In the following, we summarize the resulting equilibria from applying Siegel’s
algorithm to the APA setup of Section C.3.

Define

$\bar{k}:=\begin{cases}1,&\text{if }p\frac{v_{B,1}}{v_{A,1}}\geq 1\\\
2,&\text{if }p\frac{v_{B,1}}{v_{A,1}}+(1-p)\frac{v_{B,2}}{v_{A,2}}\geq 1\text{
and }p\frac{v_{B,1}}{v_{A,1}}<1\\\ 3,&\text{if
}p\frac{v_{B,1}}{v_{A,1}}+(1-p)\frac{v_{B,2}}{v_{A,2}}<1\end{cases}$ (C.7)

In brief, $\bar{k}$ is the iteration at which Siegel’s algorithm terminates.
Denoting $p_{1}=p$ and $p_{2}=1-p$, define

$\displaystyle L_{1}=\begin{cases}v_{A,1},&\text{if }{\bar{k}}=1\\\
pv_{B,1},&\text{if }{\bar{k}}\in\\{2,3\\}\\\ \end{cases},\quad
L_{2}=\begin{cases}0,&\text{if }{\bar{k}}=1\\\
v_{A,2}\left(1-p\frac{v_{B,1}}{v_{A,1}}\right),&\text{if }{\bar{k}}=2\\\
(1-p)v_{B,2},&\text{if }{\bar{k}}=3\\\ \end{cases}$ (C.8)

The $L_{k}$ are lengths of intervals for which the equilibrium marginals have
support. Below, we provide expressions for the equilibrium strategies that
result from applying Algorithm 1.

######  Lemma C.1.

The equilibrium mixed strategies for APA are given as follows888To simplify
exposition and notation where convenient, we sometimes explicitly write CDFs
as a mixture of uniform and point mass distributions. Here, we denote
$\text{Unif}(a,b):=\boldsymbol{1}(x\geq a)\min\\{\frac{x}{b-a},1\\}$ as the
CDF of the uniform distribution on $(a,b)$ and
$\boldsymbol{\delta}_{0}:=\boldsymbol{1}(x\geq 0)$ the CDF of a point mass
centered at zero.:

$\displaystyle\text{If }{\bar{k}}=1:$ $\displaystyle
F_{A}^{(1)}=\left(1-\frac{L_{1}}{pv_{B,1}}\right)\boldsymbol{\delta}_{0}+\frac{L_{1}}{pv_{B,1}}\text{\emph{Unif}}(0,L_{1}),\quad
F_{A}^{(2)}=\boldsymbol{\delta}_{0}$ (C.9) $\displaystyle
F_{B}=\text{\emph{Unif}}(0,L_{1})$ $\displaystyle\text{If }{\bar{k}}=2:$
$\displaystyle F_{A}^{(1)}=\text{\emph{Unif}}(L_{2},L_{2}+L_{1})$
$\displaystyle
F_{A}^{(2)}=\left(1-\frac{L_{2}}{(1-p)v_{B,2}}\right)\boldsymbol{\delta}_{0}+\frac{L_{2}}{(1-p)v_{B,2}}\text{\emph{Unif}}(0,L_{2})$
$\displaystyle
F_{B}=\frac{L_{2}}{v_{A,2}}\text{\emph{Unif}}(0,L_{2})+\frac{L_{1}}{v_{A,1}}\text{\emph{Unif}}(L_{2},L_{2}+L_{1})$
$\displaystyle\text{If }{\bar{k}}=3:$ $\displaystyle
F_{A}^{(1)}=\text{\emph{Unif}}(L_{2},L_{2}+L_{1}),\quad
F_{A}^{(2)}=\text{\emph{Unif}}(0,L_{2})$ $\displaystyle
F_{B}=\left(1-\sum_{i=1}^{2}\frac{L_{i}}{v_{A,i}}\right)\boldsymbol{\delta}_{0}+\frac{L_{2}}{v_{A,2}}\text{\emph{Unif}}(0,L_{2})+\frac{L_{1}}{v_{A,1}}\text{\emph{Unif}}(L_{2},L_{2}+L_{1})$

In summary, the marginals for player $A$ are uniform distributions with
shifted supports, and player $B$’s marginal is a piece-wise uniform
distribution.

###  C.4 Equilibria in the $\mathcal{R}_{5}$ region

We are now ready to apply the methods outlined in Sections C.2 and C.3 to
explicitly state the system of equations (C.6). We then completely
characterize the solutions to these equations in Proposition C.1. In doing so,
we identify the subset of game instances for which solutions to (C.6) exist.
Recall this subset was identified as the $\mathcal{R}_{5}$ region in Lemma 4.1
(Figure 3). We also prove that such solutions and their associated strategies
(constructed from Siegel’s algorithm) constitute equilibria of the BL game.
This serves as the proof of Lemma 4.1 in the $\mathcal{R}_{5}$ region.

The item valuations in one of the $n$ APA games are given by
$v_{A,i}=v_{j}/\lambda_{i}>0$ for player $A$ and $v_{B,i}=v_{j}/\lambda_{B}>0$
for player $B$, in type $i\in\\{1,2\\}$. Since the high budget $A_{1}$ is
associated with type $t_{1}$, we naturally impose the ranking
$\lambda_{1}\leq\lambda_{2}$. Indeed, the distribution $F_{A}^{(1)}$ (C.9)
will have a higher expected budget expenditure under this ranking of types.

The value of ${\bar{k}}$ is not known a priori, as it now depends on the
multipliers. The values it can take, ${\bar{k}}\in\\{1,2,3\\}$, correspond to
transformed multipliers $\boldsymbol{\sigma}=(\sigma_{1},\sigma_{2})$, with
$\sigma_{i}:=\frac{\lambda_{i}}{\lambda_{B}}>0$ for $i\in\\{1,2\\}$, lying in
three disjoint regions of $\mathbb{R}_{+}^{2}$. These regions result directly
from (C.7), and are given below.

$\displaystyle{\bar{k}}=1,\text{ if }$ $\displaystyle p\sigma_{1}\geq 1$
(C.10) $\displaystyle{\bar{k}}=2,\text{ if }$ $\displaystyle
p\sigma_{1}<1\text{ and }p\sigma_{1}+(1-p)\sigma_{2}\geq 1$
$\displaystyle{\bar{k}}=3,\text{ if }$ $\displaystyle
p\sigma_{1}+(1-p)\sigma_{2}<1$

Let us denote these regions as $E_{1},E_{2},E_{3}$, whose union is
$\mathbb{R}_{+}^{2}$. The constructed strategies take three different forms
described in Lemma C.1, contingent on the value of ${\bar{k}}$. Thus, there
are three cases the system of equations (C.6) can take. They are given below,
where we seek to find multipliers $(\sigma_{1},\sigma_{2},\lambda_{B})$ that
satisfies one of the three cases for a given instance
$(A_{1},A_{2},p,B)\in\mathcal{G}$ – note that we can uniquely recover
$(\lambda_{1},\lambda_{2},\lambda_{B})$ from a tuple
$(\sigma_{1},\sigma_{2},\lambda_{B})$.

Case 1 Case 2 Case 3 ($\star$) (i)
$\displaystyle\frac{1}{2p\sigma_{1}^{2}}=\lambda_{B}A_{1}$
$\displaystyle\frac{p}{2}+\frac{1-p\sigma_{1}}{\sigma_{2}}=\lambda_{B}A_{1}$
$\displaystyle\frac{p}{2}+1-p=\lambda_{B}A_{1}$ (ii) $\displaystyle 0=A_{2}$
$\displaystyle\frac{\left(1-p\sigma_{1}\right)^{2}}{2(1-p)\sigma_{2}^{2}}=\lambda_{B}A_{2}$
$\displaystyle\frac{1-p}{2}=\lambda_{B}A_{2}$ (iii) $\displaystyle
p\sigma_{1}A_{1}=B$ $\displaystyle p\sigma_{1}A_{1}+(1-p)\sigma_{2}A_{2}=B$
$\displaystyle p\sigma_{1}A_{1}+(1-p)\sigma_{2}A_{2}=B$ such that such that
such that (iv) $\displaystyle\boldsymbol{\sigma}\in E_{1}$
$\displaystyle\boldsymbol{\sigma}\in E_{2}$
$\displaystyle\boldsymbol{\sigma}\in E_{3}$ (v)
$\displaystyle\sigma_{1}\leq\sigma_{2}$
$\displaystyle\sigma_{1}\leq\sigma_{2}$
$\displaystyle\sigma_{1}\leq\sigma_{2}$

A solution $(\sigma_{1},\sigma_{2},\lambda_{B})$ to ($\star$ ‣ C.4) cannot
satisfy two cases simultaneously, due to the $E_{i}$ being disjoint. Observe
that the individual battlefield values $v_{j}$ (whose sum total is one) do not
appear in these equations. In fact, one would arrive to the system ($\star$ ‣
C.4) when considering Lotto games with any number $n\geq 1$ of battlefields
whose total value is normalized to one – the individual battlefield values do
not play a role in the analysis. For simplified exposition, we will henceforth
consider players’ strategies as allocations to a single battlefield of value
one ($F_{A}$ and $F_{B}$ with no $j$ dependence), noting this is
mathematically equivalent to any arbitrary set of $n$ battlefield valuations
$\boldsymbol{v}$ that sum to one.

Also, note the multiplier $\sigma_{2}$ does not appear in the system of Case
1, but does appear in the condition (v). Here, $\sigma_{2}$ can be set to
$\infty$ to satisfy (v), without affecting other variables. We detail the
complete solutions999If one considers general settings with more than two
budget types, the equations ($\star$ ‣ C.4) generally form an under-determined
system for the unknown variables. Hence, there may not exist unique solutions.
These challenges are considered for future work. to ($\star$ ‣ C.4), and prove
their associated strategies (from (C.9)) constitute equilibria in the result
below.

######  Proposition C.1.

The set of game instances $G=(A_{1},A_{2},p,B)$ for which a solution to
($\star$ ‣ C.4) exists and their corresponding equilibrium strategies and
payoffs are given as follows. Define $\gamma_{i}:=\frac{A_{i}}{B}$.

Case 1: Suppose $\gamma_{1}\leq 1\text{ and }\gamma_{2}=0$. The solution to
($\star$ ‣ C.4) is given by $\lambda_{1}=\frac{1}{2B}$,
$\lambda_{B}=\frac{pA_{1}}{2B^{2}}$, and $\lambda_{2}\geq\frac{1}{2B}$. The
equilibrium strategies are

$F_{A}^{(1)}=(1-\gamma_{1})\boldsymbol{\delta}_{0}+\gamma_{1}\text{\emph{Unif}}(0,2B),\quad
F_{A}^{(2)}=\boldsymbol{\delta}_{0},\quad F_{B}=\text{\emph{Unif}}(0,2B)$
(C.11)

and the (ex-ante) equilibrium payoffs are

$\pi_{A}=\frac{p\gamma_{1}}{2},\quad\quad\pi_{B}=p(1-\frac{\gamma_{1}}{2})+(1-p)$
(C.12)

Case 2: Suppose $\gamma_{2}\leq H\left(\gamma_{1}\right)$, where $H$ is
defined in (4.3). The unique solution to ($\star$ ‣ C.4) is given by
$\sigma_{2}=(1-\frac{B}{A_{1}})\sqrt{\frac{A_{1}/((1-p)A_{2})}{p+(1-p)A_{2}/A_{1}}}$,
$\sigma_{1}=\frac{B-(1-p)\sigma_{2}A_{2}}{pA_{1}}$, and
$\lambda_{B}=\frac{\left(\sqrt{(1-p)A_{2}}+\sqrt{pA_{1}+(1-p)A_{2}}\right)^{2}}{2A_{1}^{2}}$.
The equilibrium strategies are

$\displaystyle F_{A}^{(1)}$
$\displaystyle=\text{\emph{Unif}}\left(L_{2},L_{2}+L_{1}\right),\quad
F_{A}^{(2)}=\left(1-\frac{1-p\sigma_{1}}{(1-p)\sigma_{2}}\right)\boldsymbol{\delta}_{0}+\frac{1-p\sigma_{1}}{(1-p)\sigma_{2}}\text{\emph{Unif}}\left(0,L_{2}\right)$
(C.13) $\displaystyle F_{B}$
$\displaystyle=(1-p\sigma_{1})\text{\emph{Unif}}\left(0,L_{2}\right)+p\sigma_{1}\text{\emph{Unif}}\left(L_{2},L_{2}+L_{1}\right)$

where $L_{1}=\frac{p}{\lambda_{B}}$ and
$L_{2}=\frac{1-p\sigma_{1}}{\lambda_{2}}$. The equilibrium payoffs are

$\pi_{A}=p(1-p\sigma_{1})\left(1-\frac{\sigma_{1}}{\sigma_{2}}\right)+\lambda_{B}B,\quad\quad\pi_{B}=\lambda_{B}B-\frac{1-p\sigma_{1}}{\sigma_{2}}+(1-p)$
(C.14)

Case 3: Suppose $\frac{A_{2}}{A_{1}}=\frac{1-p}{2-p}\text{ and
}2-p<\frac{A_{1}}{B}<2+\frac{p}{1-p}$. A solution to ($\star$ ‣ C.4) is of the
form $\lambda_{B}=\frac{2-p}{2A_{1}}$,
$\sigma_{1}\in\left(\frac{\frac{B}{A_{1}}\left(2+\frac{p}{1-p}-\frac{A_{1}}{B}\right)}{p\left(1+\frac{p}{1-p}\right)},\frac{\frac{B}{A_{1}}\left(2+\frac{p}{1-p}\right)}{p\left(2+\frac{p}{1-p}+\frac{1-p}{p}\right)}\right)$,
and $\sigma_{2}=\frac{B-p\sigma_{1}A_{1}}{(1-p)A_{2}}$. The equilibrium
strategies are

$\displaystyle F_{A}^{(1)}$
$\displaystyle=\text{\emph{Unif}}\left(L_{2},L_{2}+L_{1}\right),\quad
F_{A}^{(2)}=\text{\emph{Unif}}\left(0,L_{2}\right)$ (C.15) $\displaystyle
F_{B}(x)$
$\displaystyle=(1-p\sigma_{1}+(1-p)\sigma_{2})\boldsymbol{\delta}_{0}+(1-p)\sigma_{2}\text{\emph{Unif}}\left(0,L_{2}\right)+p\sigma_{1}\text{\emph{Unif}}\left(L_{2},L_{2}+L_{1}\right)$

where $L_{1}=\frac{p}{\lambda_{B}}$ and
$L_{2}=\frac{1-p}{\lambda_{B}}=2A_{2}$. The equilibrium payoffs are given by

$\pi_{A}=1-\lambda_{B}B,\quad\quad\pi_{B}=\lambda_{B}B.$ (C.16)

###### Proof.

We divide this proof into two parts. In the first part, we detail the steps
used in each Case to calculate the algebraic solution to ($\star$ ‣ C.4) and
the set of game instances for which it is valid. In the second part, we
provide a proof that the corresponding strategies recovered from (C.9) do in
fact constitute an equilibrium to the BL game. We will rely on shorthand
notations $\gamma_{i}=A_{i}/B$ when convenient.

Case 1: The solution to ($\star$ ‣ C.4) can directly be found to be
$\lambda_{1}=\frac{1}{2B}$, $\lambda_{B}=\frac{pA_{1}}{2B^{2}}$, and any
$\lambda_{2}\geq\frac{1}{2B}$ (to satisfy (v)). Such a solution must also
satisfy (iv), $p\sigma_{1}=1/A_{1}\geq 1$. Combined with (ii), the set of
valid game parameters is $\gamma_{1}\leq 1$ and $\gamma_{2}=0$: player $A$’s
budget in type 1 is smaller than player $B$’s budget, and has a budget of zero
in type 2. Since $\lambda_{2}$ does not appear in the algebraic equations of
($\star$ ‣ C.4) (only in the constraints), this is essentially unique.
Plugging these values into (C.9), we obtain the resulting strategies.

Case 2: To solve for $\lambda_{B}$, we have
$1-p_{1}\sigma_{1}=\sqrt{2(1-p)\lambda_{2}\sigma_{2}A_{2}}$ from (ii).
Substituting into (i), we obtain a quadratic equation in
$\sqrt{\lambda_{B}}>0$. Its (positive) solution yields the expression for
$\lambda_{B}$.

Multiplying (ii) by $\frac{A_{1}}{A_{2}}$, the RHS of equations (i) and (ii)
become equivalent. From (iv) of ($\star$ ‣ C.4), we use the substitution
$1-p\sigma_{1}=1-\gamma_{1}^{-1}+(1-p)\sigma_{2}\frac{\gamma_{2}}{\gamma_{1}}$
to obtain
$\sigma_{2}=|1-\gamma_{1}^{-1}|\sqrt{\frac{\gamma_{1}/((1-p)\gamma_{2})}{p+(1-p)\gamma_{2}/\gamma_{1}}}$.
The condition (iv) requires $p\sigma_{1}<1$. Using the substitution
$\sigma_{1}=\frac{1-(1-p)\sigma_{2}\gamma_{2}}{p\gamma_{1}}$ from (iii), we
deduce that $\gamma_{1}>1$:

$\displaystyle p\sigma_{1}$
$\displaystyle=\gamma_{1}^{-1}\left(1-(1-p)\gamma_{2}|1-\gamma_{1}^{-1}|\sqrt{\frac{\gamma_{1}/((1-p)\gamma_{2})}{p+(1-p)\gamma_{2}/\gamma_{1}}}\right)$
(C.17)
$\displaystyle=\gamma_{1}^{-1}-|1-\gamma_{1}^{-1}|\sqrt{\frac{(1-p)\gamma_{2}/\gamma_{1}}{p+(1-p)\gamma_{2}/\gamma_{1}}}<1$
$\displaystyle\Rightarrow
1-\gamma_{1}^{-1}>-|1-\gamma_{1}^{-1}|\Rightarrow\gamma_{1}>1$

We can also deduce from (iii) and $\gamma_{1}\geq\gamma_{2}$ that
$\gamma_{2}\leq 1$. The condition (iv) also requires
$p\sigma_{1}+(1-p)\sigma_{2}\geq 1$. From this, we obtain

$\gamma_{2}\leq\frac{1-p}{2-p}\gamma_{1}.$ (C.18)

Furthermore, the positivity of $\sigma_{2}$ is trivially satisfied. However,
positivity of $\sigma_{1}$ requires that $1-(1-p)\sigma_{2}\gamma_{2}>0$.
Plugging in the expression for $\sigma_{2}$, we obtain
$\gamma_{2}(1-p)\left(2-\gamma_{1}\right)>-p$. Hence, the positivity
constraint $\sigma_{1}>0$ is equivalent to

$\displaystyle\gamma_{1}\leq 2,\text{ or }\gamma_{1}>2\text{ and
}\gamma_{2}<\frac{p}{(1-p)\left(\gamma_{1}-2\right)}.$ (C.19)

Lastly, the constraint (v) requires $\sigma_{1}\leq\sigma_{2}$. Plugging in
the expression for $\sigma_{2}$, we deduce that
$\gamma_{2}\left(1-(\gamma_{1}-1)^{2}\right)\leq(\gamma_{1}-1)^{2}\gamma_{1}\frac{p}{1-p}$.
The term in parentheses on the LHS is positive when $\gamma_{1}<2$, and
negative otherwise. Hence, we obtain

$\gamma_{2}\begin{cases}\leq\frac{\frac{p}{1-p}(\gamma_{1}-1)^{2}}{2-\gamma_{1}},&\text{if
}1<\gamma_{1}\leq 2\\\ \geq 0,&\text{if }\gamma_{1}>2\end{cases}$ (C.20)

The intersection of conditions (C.20),(C.18), and (C.19) on the budget
parameters $A_{1}$ and $A_{2}$, derived directly from (iv) and (v), yields
$\gamma_{2}\leq H\left(\gamma_{1}\right)$, where $H$ was defined in (4.3).
This establishes the set of games for which the system ($\star$ ‣ C.4) has a
solution in Case 2.

Case 3: We can directly obtain $\lambda_{B}=\frac{2-p}{2A_{1}}$. Note that
$\lambda_{B}=\frac{1-p}{2A_{2}}$ as well, from which we obtain
$A_{2}=\frac{1-p}{2-p}A_{1}$. From (iii), we have
$\sigma_{2}=\frac{B-pA_{1}\gamma_{1}}{(1-p)A_{2}}$. Substituting this in the
condition (iv), $p\sigma_{1}+(1-p)\sigma_{2}<1$, we obtain
$\sigma_{1}>\frac{\gamma_{1}^{-1}\left(2+\frac{p}{1-p}-\gamma_{1}\right)}{p\left(1+\frac{p}{1-p}\right)}$.
Similarly, constraint (v), $\sigma_{1}\leq\sigma_{2}$, yields
$\sigma_{1}\leq\frac{\gamma_{1}^{-1}\left(2+\frac{p}{1-p}\right)}{p\left(2+\frac{p}{1-p}+\frac{1-p}{p}\right)}$.
A feasible $\sigma_{1}$ exists within these constraints if and only if
$\gamma_{1}>1+\frac{1+\frac{1-p}{p}}{2+\frac{p}{1-p}+\frac{1-p}{p}}=2-p$
(upper bound must be larger than lower bound), and
$\gamma_{1}<2+\frac{p}{1-p}$ (lower bound must be positive). Subsequently,
(C.9) recovers the strategies (C.15). The union of characterized parameter
sets in all three cases constitutes the $\mathcal{R}_{5}$ region in Lemma 4.1.

Part 2: We prove the strategy profile $(F_{A},F_{B})$ recovered from (C.9) is
an equilibrium101010This proof can be extended to scenarios where player $A$
has an arbitrary number $m$ endowment types. That is, if one can derive a
solution to the system of $m+1$ equations (instead of just 3 in (C.6)), the
profile $(F_{A},F_{B})$ one constructs using Siegel’s algorithm (in analogous
manner to Section C.3) is an equilibrium to the BL game. Characterizing
solutions to a system of $m+1$ equations, however, is a non-trivial extension
that we leave for future study.. We can immediately deduce the strategies in
Case 1 are equilibria to the BL game by observing that player $A$ has zero
budget in type 2, and $(F_{A}^{(1)},F_{B})$ forms the unique equilibrium to
the complete information General Lotto game [21] with a single battlefield of
value $p$. We will focus on the strategies produced from Case 2, as the proof
for Case 3 follows analogous arguments.

We first calculate the (ex-interim) payoffs from the strategies (C.13).

$\displaystyle U_{A}(F_{A}^{(1)},F_{B})$
$\displaystyle=\int_{0}^{\infty}F_{B}(x)\,dF_{A}^{(1)}=\int_{L_{2}}^{L_{2}+L_{1}}\left[L_{2}\lambda_{2}+\lambda_{1}(x-L_{2})\right]\frac{\lambda_{B}}{p}dx$
(C.21)
$\displaystyle=(1-p\sigma_{1})\left(1-\frac{\sigma_{1}}{\sigma_{2}}\right)+\lambda_{1}A_{1}$
$\displaystyle U_{A}(F_{A}^{(2)},F_{B})$
$\displaystyle=\int_{0}^{\infty}F_{B}(x)\,dF_{A}^{(2)}=\int_{0}^{L_{2}}\lambda_{2}x\cdot\frac{\lambda_{B}}{1-p}dx=\lambda_{2}A_{2}$

The expected payoff (first equation of (2.7)) to player $A$ is then
$\pi_{A}=p(1-p\sigma_{1})\left(1-\frac{\sigma_{1}}{\sigma_{2}}\right)+\lambda_{B}B$
(using (iii)). The payoff to player $B$ is $\pi_{B}=1-\pi_{A}$. We need to
show $F_{A}$ is a best-response to $F_{B}$, and vice versa.

For any $F_{A}^{\prime(1)}\in\mathcal{L}(A_{1})$, the payoff in type 1 is

$\displaystyle U_{A}(F_{A}^{\prime(1)},F_{B})$
$\displaystyle=\int_{0}^{L_{2}}\lambda_{2}x\,dF_{A}^{\prime(1)}+\int_{L_{2}}^{L_{2}+L_{1}}\left[L_{2}\lambda_{2}+\lambda_{1}(x-L_{2})\right]\,dF_{A}^{\prime(1)}+\int_{L_{2}+L_{1}}^{\infty}dF_{A}^{\prime(1)}$
(C.22)
$\displaystyle=(\lambda_{2}-\lambda_{1})\left(\int_{0}^{L_{2}}x\,dF_{A}^{\prime(1)}-L_{2}\int_{0}^{L_{2}}dF_{A}^{\prime(1)}\right)$
$\displaystyle\quad+\lambda_{1}\left((L_{2}+L_{1})\int_{L_{2}}^{L_{2}+L_{1}}dF_{A}^{\prime(1)}-\int_{L_{2}}^{L_{2}+L_{1}}x\,dF_{A}^{\prime(1)}\right)+\lambda_{1}A_{1}+L_{2}(\lambda_{2}-\lambda_{1})$
$\displaystyle\leq\lambda_{1}A_{1}+L_{2}(\lambda_{2}-\lambda_{1})=\lambda_{1}A_{1}+(1-\frac{\lambda_{1}}{\lambda_{2}})(1-p\sigma_{1}).$

In the second equality, we used the identities
$\int_{L_{2}}^{L_{2}+L_{1}}x\,dF_{A}^{\prime(1)}=A_{1}-\int_{0}^{L_{2}}x\,dF_{A}^{\prime(1)}-\int_{L_{2}+L_{1}}^{\infty}x\,dF_{A}^{\prime(1)}$
and
$\int_{L_{2}}^{L_{2}+L_{1}}dF_{A}^{\prime(1)}=1-\int_{0}^{L_{2}}dF_{A}^{\prime(1)}-\int_{L_{2}+L_{1}}^{\infty}dF_{A}^{\prime(1)}$.
The inequality follows from two applications of Markov’s inequality:
$\int_{0}^{L_{2}}x\,dF_{A}^{\prime(1)}\leq
L_{2}\int_{0}^{L_{2}}dF_{A}^{\prime(1)}$, and
$-\int_{L_{2}}^{L_{2}+L_{1}}x\,dF_{A}^{\prime(1)}\leq-(L_{2}+L_{1})\int_{L_{2}}^{L_{2}+L_{1}}dF_{A}^{\prime(1)}$.
Hence, the payoff in type 1 is upper-bounded by
$\lambda_{1}A_{1}+(1-\frac{\lambda_{1}}{\lambda_{2}})(1-p\sigma_{1})$, which
can be attained whenever
$\text{supp}(F_{A}^{\prime(1)})\subseteq[L_{2},L_{2}+L_{1}]$ (for which the
Markov inequalities hold with equality). We provide analogous calculations for
any $F_{A}^{\prime(2)}\in\mathcal{L}(A_{2})$:

$\displaystyle U_{A}(F_{A}^{\prime(2)},F_{B})$
$\displaystyle=\int_{0}^{L_{2}}\lambda_{2}x\,dF_{A}^{\prime(2)}+\int_{L_{2}}^{L_{2}+L_{1}}\left[L_{2}\lambda_{2}+\lambda_{1}(x-L_{2})\right]\,dF_{A}^{\prime(2)}+\int_{L_{2}+L_{1}}^{\infty}dF_{A}^{\prime(2)}$
(C.23)
$\displaystyle=(\lambda_{2}-\lambda_{1})\left(L_{2}\int_{L_{2}}^{L_{2}+L_{1}}dF_{A}^{\prime(2)}-\int_{L_{2}}^{L_{2}+L_{1}}x\,dF_{A}^{\prime(2)}\right)$
$\displaystyle\quad+\left(\int_{L_{2}+L_{1}}^{\infty}dF_{A}^{\prime(2)}-\lambda_{2}\int_{L_{2}+L_{1}}^{\infty}dF_{A}^{\prime(2)}\right)+\lambda_{2}A_{2}$
$\displaystyle\leq-p(\sigma_{2}-\sigma_{1})\int_{L_{2}+L_{1}}^{\infty}dF_{A}^{\prime(2)}+\lambda_{2}A_{2}$
$\displaystyle\leq\lambda_{2}A_{2}$

The first inequality is similarly obtained from two applications of Markov’s
inequality. The second inequality follows from the condition (v),
$\sigma_{2}\geq\sigma_{1}$. Hence, the payoff in type 2 is upper-bounded by
$\lambda_{2}A_{2}$, which can be attained whenever
$\text{supp}(F_{A}^{\prime(2)})\subseteq[0,L_{2}]$. The strategy $F_{A}$
satisfies these properties, and hence is a best-response to $F_{B}$.

For any $F_{B}^{\prime}\in\mathcal{L}(B)$, player $B$’s expected payoff (2.7)
is

$\displaystyle\Pi_{B}(F_{B}^{\prime},F_{A})$
$\displaystyle=p\left[\int_{L_{2}}^{L_{2}+L_{1}}\frac{\lambda_{B}}{p}(x-L_{2})\,dF_{B}^{\prime}+\int_{L_{2}+L_{1}}^{\infty}dF_{B}^{\prime}\right]$
(C.24)
$\displaystyle\quad+(1-p)\left[\int_{0}^{L_{2}}\left(1-\frac{\lambda_{B}L_{2}}{1-p}+\frac{\lambda_{B}}{1-p}x\right)\,dF_{B}^{\prime}+\int_{L_{2}}^{\infty}dF_{B}^{\prime}\right]$
$\displaystyle=\lambda_{B}\left(\int_{0}^{L_{2}+L_{1}}x\,dF_{B}^{\prime}-L_{2}\int_{0}^{L_{2}+L_{1}}dF_{B}^{\prime}\right)+p\int_{L_{2}+L_{1}}^{\infty}dF_{B}^{\prime}+(1-p)$
$\displaystyle=\lambda_{B}B-\lambda_{B}L_{2}+(1-p)+\lambda_{B}\left((L_{1}+L_{2})\int_{L_{2}+L_{1}}^{\infty}dF_{B}^{\prime}-\int_{L_{2}+L_{1}}^{\infty}x\,dF_{B}^{\prime}\right)$
$\displaystyle\leq\lambda_{B}B-\lambda_{B}L_{2}+(1-p)=\pi_{B}$

Player B’s expected payoff is upper-bounded by $\pi_{B}$, which can be
attained for any strategy with
$\text{supp}(F_{B}^{\prime})\subseteq[0,L_{2}+L_{1}]$. Because $F_{B}$ is one
such strategy, it is a best-response to $F_{A}$. ∎

###  C.5 Equilibria in regions $\mathcal{R}_{1}$ \- $\mathcal{R}_{4}$

Here, we provide all derivations of equilibria corresponding to the payoffs in
regions $\mathcal{R}_{i}$, $i=1,\ldots,4$ (Lemma 4.1). As shown in Proposition
C.1, such equilibria cannot be generated through the methods of Section C.2.

To first give some informal intuition, we provide some descriptions of the
equilibria in these regions. The equilibrium strategies in $\mathcal{R}_{1}$
and $\mathcal{R}_{2}$ are convex combinations between an equilibrium strategy
on the border111111Since equilibria on the border are not necessarily unique,
i.e. Case 3 parameters of Proposition C.1, the equilibria in the regions
$\mathcal{R}_{1}$ and $\mathcal{R}_{2}$ are not unique. However, all
equilibria in one game instance yield identical payoffs, since it is a
constant sum game (in ex-ante payoffs). of $\mathcal{R}_{5}$ and equilibrium
in its corresponding benchmark complete information game
$\text{GL}(\bar{A},B,0)$. As a result, the equilibrium payoff for any $G$ in
$\mathcal{R}_{1}$ or $\mathcal{R}_{2}$ coincides with the equilibrium payoff
of its corresponding benchmark game. In regions $\mathcal{R}_{3}$ and
$\mathcal{R}_{4}$, the “high” budget $A_{1}$ is disproportionately higher than
the “low” budget $A_{2}$. We find an equilibrium strategy for the uninformed
player is to not compete against the high budget at all, thus giving up a
payoff $p$ to the obfuscating player. In the forthcoming proofs, we make
extensive use of Markov’s inequality: $\int_{a}^{b}x\,dF\leq b\int_{a}^{b}dF$
for any distribution $F$.

Region  $\mathcal{R}_{3}$: Suppose the game parameters belong to region

$\mathcal{R}_{3}=\left\\{(\gamma_{1},\gamma_{2})\in\mathcal{R}:\gamma_{1}\geq
2+\frac{p}{1-p}\text{ and
}1\leq\gamma_{2}\leq\frac{1-p}{2-p}\gamma_{1}\right\\}.$ (C.25)

The following is an equilibrium.

$F_{A}^{(1)}=\text{Unif}\left(2A_{2},2(A_{1}-A_{2})\right),\quad
F_{A}^{(2)}=\text{Unif}\left(0,2A_{2}\right),\quad
F_{B}=(1-\gamma_{2}^{-1})\boldsymbol{\delta}_{0}+\gamma_{2}^{-1}\text{Unif}\left(0,2A_{2}\right)$
(C.26)

The equilibrium payoff is given by
$\pi_{A}=p+(1-p)\left(1-\frac{1}{2\gamma_{2}}\right)$.

###### Proof.

First, we show $F_{A}$ is a best-response to $F_{B}$. For any
$\left\\{F_{A}^{\prime(i)}\in\mathcal{L}(A_{i})\right\\}_{i=1,2}$, player
$A$’s expected payoff is

$\displaystyle
p\left[\int_{0}^{2A_{2}}\left(1-\gamma_{2}^{-1}+\frac{\gamma_{2}^{-1}}{2A_{2}}x\right)\,dF_{A}^{\prime(1)}+\int_{2A_{2}}^{\infty}dF_{A}^{\prime(1)}\right]$
(C.27)
$\displaystyle\quad+(1-p)\left[\int_{0}^{2A_{2}}\left(1-\gamma_{2}^{-1}+\frac{\gamma_{2}^{-1}}{2A_{2}}x\right)\,dF_{A}^{\prime(2)}+\int_{2A_{2}}^{\infty}dF_{A}^{\prime(2)}\right]$
$\displaystyle\leq
p+(1-p)\left[\int_{0}^{2A_{2}}\left(1-\gamma_{2}^{-1}+\frac{\gamma_{2}^{-1}}{2A_{2}}x\right)\,dF_{A}^{\prime(2)}+\int_{2A_{2}}^{\infty}dF_{A}^{\prime(2)}\right]$

The inequality follows by selecting any $F_{A}^{\prime(1)}$ such that
$\text{supp}(F_{A}^{\prime(1)})\subset[2A_{2},\infty)$, which awards player
$A$ the payoff $p$ from state 1 outright. This is possible because
$\gamma_{1}\geq 2+\frac{p}{1-p}>2$, from the assumption. The expression above
can be re-written and upper-bounded as follows:

$\displaystyle
p+(1-p)\left[\left(1-\gamma_{2}^{-1}\right)\int_{0}^{2A_{2}}dF_{A}^{\prime(2)}+\frac{\gamma_{2}^{-1}}{2}+\int_{2A_{2}}^{\infty}dF_{A}^{\prime(2)}-\frac{\gamma_{2}^{-1}}{2A_{2}}\int_{2A_{2}}^{\infty}x\,dF_{A}^{\prime(2)}\right]$
(C.28) $\displaystyle\quad\leq
p+(1-p)\left(1-\frac{\gamma_{2}^{-1}}{2}\right)$

The inequality holds with equality if and only if
$\text{supp}(F_{A}^{\prime(2)})\subseteq[0,2A_{2}]$. We have thus established
an upper bound on A’s payoff to $F_{B}$ that is achieved by $F_{A}$.

Now we show $F_{B}$ is a best-response to $F_{A}$. Let
$K:=(1-p)-\frac{p\gamma_{2}}{\gamma_{1}-2\gamma_{2}}\geq 0$, which is non-
negative due to the assumption $\gamma_{2}\leq\frac{1-p}{2-p}\gamma_{1}$. For
any $F_{B}^{\prime}\in\mathcal{L}(B)$, player $B$’s payoff is

$\displaystyle
p\left[\int_{2A_{2}}^{2(A_{1}-A_{2})}\frac{x-2A_{2}}{2(A_{1}-2A_{2})}\,dF_{B}^{\prime}+\int_{2(A_{1}-A_{2})}^{\infty}dF_{B}^{\prime}\right]+(1-p)\left[\int_{0}^{2A_{2}}\frac{x}{2A_{2}}\,dF_{B}^{\prime}+\int_{2A_{2}}^{\infty}dF_{B}^{\prime}\right]$
(C.29)
$\displaystyle=\frac{1-p}{2A_{2}}\int_{0}^{2A_{2}}x\,dF_{B}^{\prime}+\frac{p}{2(A_{1}-2A_{2})}\int_{2A_{2}}^{2(A_{1}-A_{2})}x\,dF_{B}^{\prime}-\left(\frac{pA_{2}}{A_{1}-2A_{2}}-(1-p)\right)\int_{2A_{2}}^{2(A_{1}-A_{2})}\,dF_{B}^{\prime}$
$\displaystyle\quad\quad+\int_{2(A_{1}-A_{2})}^{\infty}dF_{B}^{\prime}$

Applying the identity
$\int_{0}^{2A_{2}}x\,dF_{B}^{\prime}=B-\int_{2A_{2}}^{2(A_{1}-A_{2})}x\,dF_{B}^{\prime}-\int_{2(A_{1}-A_{2})}^{\infty}x\,dF_{B}^{\prime}$,
we then obtain

$\displaystyle=K\left(-\frac{1}{2A_{2}}\int_{2A_{2}}^{2(A_{1}-A_{2})}x\,dF_{B}^{\prime}+\int_{2A_{2}}^{2(A_{1}-A_{2})}\,dF_{B}^{\prime}\right)+(1-p)\frac{\gamma_{2}^{-1}}{2}$
(C.30)
$\displaystyle\quad+\int_{2(A_{1}-A_{2})}^{\infty}dF_{B}^{\prime}-\frac{1-p}{2A_{2}}\int_{2(A_{1}-A_{2})}^{\infty}x\,dF_{B}^{\prime}$
$\displaystyle\leq(1-p)\frac{\gamma_{2}^{-1}}{2}+\left(p+(1-p)\left(2-\frac{\gamma_{1}}{\gamma_{2}}\right)\right)\int_{2(A_{1}-A_{2})}^{\infty}dF_{B}^{\prime}$
$\displaystyle\leq(1-p)\frac{\gamma_{2}^{-1}}{2}$

The first inequality results from applying Markov’s inequality to
$\int_{2A_{2}}^{2(A_{1}-A_{2})}x\,dF_{B}^{\prime}$ and
$\int_{2(A_{1}-A_{2})}^{\infty}x\,dF_{B}^{\prime}$. The second inequality
follows from non-positivity of term in parentheses (from assumption of the
Lemma). This inequality holds with equality if and only if
$\text{supp}(F_{B}^{\prime})\subseteq[0,2A_{2}]$. We have thus established an
upper bound on player $B$’s payoff to $F_{A}$ that is achieved by $F_{B}$.

∎

Region  $\mathcal{R}_{4}$: Suppose the game parameters belong to region

$\mathcal{R}_{4}:=\left\\{(\gamma_{1},\gamma_{2})\in\mathcal{R}:\gamma_{1}\geq
2+\frac{p}{1-p}\text{ and }\frac{p}{(1-p)(\gamma_{1}-2)}\leq\gamma_{2}\leq
1\right\\}.$ (C.31)

The following is an equilibrium:
$F_{A}^{(1)}=\text{Unif}\left(2B,2(A_{1}-B)\right)$,
$F_{A}^{(2)}=(1-\gamma_{2})\boldsymbol{\delta}_{0}+\gamma_{2}\text{Unif}\left(0,2B\right)$,
$F_{B}=\text{Unif}\left(0,2B\right)$, and the equilibrium payoff is given by
$\pi_{A}(G)=p+(1-p)\frac{\gamma_{2}}{2}$.

###### Proof.

First, show $F_{A}$ is a best-response to $F_{B}$. Player $A$’s payoff for any
$\left\\{F_{A}^{\prime(i)}\in\mathcal{L}(A_{i})\right\\}_{i=1,2}$ is

$\displaystyle
p\left[\int_{0}^{2B}\frac{x}{2B}\,dF_{A}^{\prime(1)}+\int_{2B}^{\infty}dF_{A}^{\prime(1)}\right]+(1-p)\left[\int_{0}^{2A_{2}}\frac{x}{2B}\,dF_{A}^{\prime(2)}+\int_{2B}^{\infty}dF_{A}^{\prime(2)}\right]$
(C.32) $\displaystyle\leq
p+(1-p)\left[\int_{0}^{2A_{2}}\frac{x}{2B}\,dF_{A}^{\prime(2)}+\int_{2B}^{\infty}dF_{A}^{\prime(2)}\right]$
$\displaystyle=p+(1-p)\left[\frac{\gamma_{2}}{2}+\int_{2B}^{\infty}dF_{A}^{\prime(2)}-\frac{1}{2B}\int_{2B}^{\infty}x\,dF_{A}^{\prime(2)}\right]$
$\displaystyle\leq p+(1-p)\frac{\gamma_{2}}{2}.$

The first inequality follows by selecting any $F_{A}^{\prime(1)}$ such that
$\text{supp}(F_{A}^{\prime(1)})\subset[2B,\infty)$, which awards player $A$
the payoff $p$ outright. This is possible because $\gamma_{1}\geq 2$, from the
assumption. The second inequality follows by applying Markov’s inequality to
$\int_{2B}^{\infty}x\,dF_{A}^{\prime(2)}$. This inequality holds if and only
if $\text{supp}(F_{A}^{\prime(2)})\subseteq[0,2B]$.

Now we show $F_{B}$ is a best-response to $F_{A}$. For any
$F_{B}\in\mathcal{L}(B)$, player $B$’s payoff is

$\displaystyle\frac{(1-p)\gamma_{2}}{2B}\int_{0}^{2B}x\,dF_{B}^{\prime}+(1-p)\left(1-\gamma_{2}\right)\int_{0}^{2B}dF_{B}^{\prime}$
(C.33)
$\displaystyle\quad+\frac{p}{2(A_{1}-2B)}\int_{2B}^{2(A_{1}-B)}x\,dF_{B}^{\prime}+\left((1-p)\gamma_{2}-\frac{p}{\gamma_{1}-2}\right)\int_{2B}^{2(A_{1}-B)}dF_{B}^{\prime}+\int_{2(A_{1}-B)}^{\infty}dF_{B}^{\prime}$
$\displaystyle=K\left(\int_{2B}^{2(A_{1}-B)}dF_{B}^{\prime}-\frac{1}{2B}\int_{2B}^{2(A_{1}-B)}x\,dF_{B}^{\prime}\right)$
$\displaystyle\quad+\left(p+(1-p)\gamma_{2}\right)\int_{2(A_{1}-B)}^{\infty}dF_{B}^{\prime}-\frac{(1-p)\gamma_{2}}{2B}\int_{2(A_{1}-B)}^{\infty}x\,dF_{B}^{\prime}+(1-p)\left(1-\frac{\gamma_{2}}{2}\right)$
$\displaystyle\leq(1-p)\left(1-\frac{\gamma_{2}}{2}\right)$

where $K:=(1-p)\gamma_{2}-\frac{p}{\gamma_{1}-2}>0$, from the assumption. In
the equality, we substituted