Dynamic Operational Planning in Warfare: A Stochastic Game Approach to
Military Campaigns Joseph E. McCarthy, Mathieu Dahan, Chelsea C. White III H.
Milton Stewart School of Industrial and Systems Engineering, Georgia Institute
of Technology, Atlanta, Georgia
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
Stochastic Game for Dynamic Operational Planning in Military Campaigns
McCarthy, Dahan, and White

We study a two-player discounted zero-sum stochastic game model for dynamic
operational planning in military campaigns. At each stage, the players manage
multiple commanders who order military actions on objectives that have an open
line of control. When a battle over the control of an objective occurs, its
stochastic outcome depends on the actions and the enabling support provided by
the control of other objectives. Each player aims to maximize the cumulative
number of objectives they control, weighted by their criticality. To solve
this large-scale stochastic game, we derive properties of its Markov perfect
equilibria by leveraging the logistics and military operational command and
control structure. We show the consequential isotonicity of the optimal value
function with respect to the partially ordered state space, which in turn
leads to a significant reduction of the state and action spaces. We also
accelerate Shapley’s value iteration algorithm by eliminating dominated
actions and investigating pure equilibria of the matrix game solved at each
iteration. We demonstrate the computational value of our equilibrium results
on a case study that reflects representative operational-level military
campaigns with geopolitical implications. Our analysis reveals a complex
interplay between the game’s parameters and dynamics in equilibrium, resulting
in new military insights for campaign analysts.

Military operations; campaign analysis; stochastic game; value iteration

This article was first submitted on March 1, 2024.

##  1 Introduction

###  1.1 Motivation

Military leadership plays an indispensable role in a nation state’s security
in times of great competition. Ideally, the leadership can continue to deter
adversaries from escalating to kinetic warfare (HQDA 2021); however, planning
for armed conflict is essential. Rising geopolitical unrest demonstrates the
increasing likelihood of kinetic warfare between great powers (Garamone,
2022). This is evidenced by the continued Russo-Ukrainian war that escalated
to overt, armed conflict in February 2022. This global context demands that
senior military leadership and their staffs continue to conduct planning that
unifies the tactical, operational, and strategic levels to support national
security objectives (JCS 2020).

Operational-level warfare links the tactical employment of forces to national
strategic objectives (JCS 2017). At this level, Joint Force Commanders lead
component commanders (e.g., air, land, and maritime) to fight conflicts. A
sequence of operations and battles form a military _campaign_ (Lynes et al.,
2014), which strategists, planners, and analysts alike analyze to recommend
operational plans and yield geopolitical insights for senior military
leadership (Mueller, 2016, Shlapak & Johnson, 2016, Flanagan et al., 2019,
Mazarr et al., 2019).

However, the main challenge in analyzing military campaigns comes from their
intrinsic uncertainty (Tecott & Halterman, 2021) that extends from three
sources: the adversary’s plan, the interconnected nature of military
operations, and the dynamic flow of warfare. Because the adversary’s plan is
unknown, amidst a complex operational environment (JCS 2020), a battle’s
outcome is uncertain. Synchronizing operations across interconnected
commanders demands joint planning, communication, and coordination to align
efforts (JCS 2017). Finally, the dynamic flow of a military campaign leads to
uncertainty in the transition between potential battles. For instance during
World War II, a successful allied D-Day invasion eventually led to Operation
Market Garden, where U.S. and U.K. setbacks resulted in Soviet forces reaching
Berlin first (Pruitt, 2019). This dynamic facet requires that future uncertain
outcomes must be considered to optimize present decisions.

Existing methods for campaign analysis include wargaming and combat simulation
(Turnitsa et al., 2022). While effective, these tools do not account for the
uncertain or behavioral dynamics of military campaigns, and take substantial
time and resources. Furthermore, game theoretic models that allocate resources
for the control of military objectives do not consider pivotal campaign
aspects including the dynamic, sequenced nature of military battles, supply
chain requirements, or military command structure (Washburn, 2014). Seeking to
augment current methods with a faster technique that scales to evaluate many
inputs, prompts our research question: _How may we design dynamic military
operational plans and yield timely assessments and insights for senior
leadership?_

###  1.2 Contributions

To address the research question, we propose a novel two-player, discounted,
zero-sum, stochastic game model for dynamic operational planning in military
campaigns, building upon the static game model of Haywood, (1954). The
features of the model account for key military characteristics such as the
coordination of multiple commanders, the need for established supply lines,
and the stochasticity of battle outcomes that depend on the control of nearby
objectives.

By leveraging the logistics and military operational command and control
structure, we derive properties satisfied by the Markov perfect equilibria of
the game. Under practically motivated assumptions, we show the consequential
isotonicity of the optimal value function with respect to the partially
ordered state space (Theorem 4.1). This main result, along with game-theoretic
arguments, permit us to determine the set of achievable states as well as
properties of policy profiles in equilibrium (Proposition 4.2). These
properties lead to a significant reduction of the state and action spaces,
which in turn enables the use of Shapley’s value iteration algorithm to solve
this large-scale game.

In the special case of a campaign with one commander, we further show that the
matrix game solved at most states within the value iteration algorithm admits
weakly dominated strategies, and even admits a pure equilibrium when the
commander manages a single axis of objectives (Proposition 4.3). These
structural results lead us to design an accelerated value iteration algorithm
(Algorithms 1-2) that searches for pure equilibria or eliminates weakly
dominated actions before solving the matrix game using linear programming.

We then design a representative case study, built upon a fictional
geopolitical scenario. We analyze and compare the players’ mixed strategies at
different states in equilibrium, and highlight a complex behavior that depends
on the objective criticality, the probabilistic interdependencies between
objectives, and the dynamics of the game. We also show that strategic
investment decisions must be carefully timed, as they have varied impacts on
the optimal value of the game at different initial states. Finally, our
equilibrium results permit us to solve the stochastic game for all considered
military campaigns, using our accelerated value iteration algorithm that
achieves a 72% runtime reduction in comparison with the classical value
iteration algorithm. Our analysis leads to novel operational insights that can
be exploited by military leadership.

The remainder of this article is organized as follows: Section 2 briefly
discusses military campaign analysis and current tools. The review then covers
existing stochastic game literature pertinent to our military domain. We
formulate the stochastic game in Section 3. We then derive our equilibrium
results and present our accelerated value iteration algorithm in Section 4. In
Section 5, we present our computational results and military insights from our
case study. Section 6 provides concluding remarks and avenues for future
research. Finally, the mathematical proofs of our results are derived in
Appendix 7.

##  2 Literature Review

Campaign analysis sits atop the military modeling hierarchy (Figure 1). The
campaign level trades off some detail to yield aggregated insights for
military senior decision makers. Combat simulations and wargaming are two
tools used individually or in tandem to study campaign analysis problems
(Turnitsa et al., 2022). Wargames are ideal to explore human decision making
while simulations are ideal to deliver quantitative assessments and results
under a typically fixed operational plan (Turnitsa et al., 2022). These tools
are vital, yet take substantial time. The campaign wargame is personnel
intensive, often requiring weeks (including rehearsals and participant travel)
to develop one operational plan for one campaign setting (Burns et al., 2015).
The combat simulation takes months to instantiate and assesses one plan at a
time (Sweetser & Bexfield, 2020). As a result, these methods cannot be scaled
to develop a plan for many scenarios while accounting for the behavioral and
uncertain dynamics of military campaigns. To address these limitations, we
propose a stochastic game model to quickly develop initial operational plans
and evaluate campaign inputs.

Figure 1: Department of Defense Modeling and Simulation Hierarchy (Shane et
al., 2020).

While the stochastic game framework has been applied in the overall military
domain, we did not identify any direct application to the campaign analysis
level in the open literature. We assess that existing efforts are largely for
the system/engineering or engagement levels with a few mission-level
applications. At the system/engineering and engagement levels, Ho et al.,
(2022) review many of stochastic game applications. For instance, Bachmann et
al., (2011) and He et al., (2021) study the competitive interaction between
radars and jammers. Deligiannis et al., (2017) study power allocation for a
radar network against multiple jammers. Then, Bogdanovic et al., (2018) and
Gu, (2011) study target selection and tracking in radar networks. Finally,
Krishnamurthy et al., (2008) study transmission in ground sensor networks.
Stochastic games are also used for mission-level problems, involving military
battles between forces. Chang et al., (2022) employ a partially observed
stochastic game to assess modern combat in Mosul. McEneaney et al., (2004)
apply a stochastic game to air operation command and control. These models
consider a fixed role for each player (e.g., attacker versus defender, radar
versus jammer, air force versus ground targets), while the role of opposing
forces in a military campaign is often context-dependent. For instance during
the World War II European campaign, Axis forces were simultaneously on the
offensive or defensive. Furthermore, these models do not consider the
operational level’s interconnected nature of commands and domains.

Other game theoretic models have been studied for settings where opposing
forces seek to gain military objectives by assigning resources to a subset of
objectives. Bier et al., (2007) develop a sequential game to model a defender
who first allocates defensive resources against a subsequent attack from an
unknown attacker. In the Colonel Blotto game framework (Shubik & Weber, 1981,
Coughlin, 1992, Washburn, 2014), zero-sum (static) matrix games are introduced
where opposing military commanders simultaneously assign a fixed number of
forces (e.g., individual soldiers) across a set of military objectives. The
commander who places the highest number of forces on an objective gains
control of that objective. Many extensions have been investigated, including
asymmetry of resources (Chowdhury et al., 2013) and objective heterogeneity
(Kovenock & Roberson, 2021). Kaminsky et al., (1984) and Kharlamov, (2022)
have extended the battle outcomes to be stochastic with a winning probability
proportional to the amount of assigned forces. Such games typically assume
players can assign resources to any objective, and cannot be applied to
settings involving constraints rising from logistics lines or operational-
level command structure. Our model also differs in that we consider the
inherent differences between a player maintaining control of an objective they
control and gaining control of an objective the player’s adversary controls.
Finally, we account for the interdependent nature of warfare, where
controlling one objective changes the future transition dynamics for other
objectives.

Haywood, (1954), who reviews the World War II Battles of the Bismarck Sea
(U.S. versus Japan) and Avranches-Gap (Allies versus Germany), provides a
launching point for our model. He, and later Cantwell, (2003) and Fox, (2016),
demonstrate that portraying military battle decision-making as a matrix game
is a powerful decision support tool. While Haywood, (1954) provides a clear
delineation of military decision making for the single-stage single-battle
problem, we aim to extend his work by building a military campaign that
accounts for the dynamic sequence of simultaneous stochastic battles conducted
across multiple domains, linked through an interdependent transition model.

In summary, current military stochastic game applications often consider
engineering or engagement level problems. On the other hand, existing game
models that allocate resources to military objectives do not consider military
logistics precedence, command structure, or the interdependence and dynamics
of sequential battles. We contend that our work is the first application of
the stochastic game framework to the study of dynamic, multi-battle, military
campaigns.

##  3 Problem Description

In this section, we define the campaign between two military forces. Then, we
model their dynamic and stochastic interactions using a two-person,
discounted, zero-sum stochastic game.

###  3.1 Campaign Model

We consider a competitive operational campaign between two players that
represent opposing military forces. The campaign consists of a set
$\mathcal{O}$ of common _objectives_ that the players aim to control. Each
objective is defined as “a decisive and attainable goal toward which every
operation is directed” (JCS 2016), and may represent controlling operational-
level terrain (e.g., capital city, airport, canal) or a non-geographic goal
such as gaining air superiority. To account for precedence constraints between
military goals during a campaign, we partition objectives into a collection
$\mathcal{X}$ of _axes_. Specifically, each axis $x\in\mathcal{X}$ is a
totally ordered set of objectives, represented as
$x=(o^{x}_{1},\dots,o^{x}_{|x|})$, where $o^{x}_{1}$ (resp. $o^{x}_{|x|}$)
represents the _front_ (resp. _rear_) of axis $x$. As an example of a
precedence relationship, consider that a military may not gain air superiority
until they have neutralized air defenses and achieved air parity first.

Each player $i\in\\{1,2\\}$ manages a collection $\mathcal{C}^{i}$ of
commanders, where each commander $c\in\mathcal{C}^{i}$ is _responsible_ for a
subset $\mathcal{X}_{c}\subseteq\mathcal{X}$ of axes. We denote as
$\mathcal{O}_{c}\coloneqq\\{o\in x,\
\forall\;x\in\mathcal{X}_{c}\\}\subseteq\mathcal{O}$ the objectives under the
responsibility of commander $c$. We assume that each axis $x\in\mathcal{X}$ is
under the responsibility of one commander $c\in\mathcal{C}^{i}$ from each
player $i$, that is, $x\in\mathcal{X}_{c}$. We further assume that
responsibilities are _symmetric_ , that is, for every
$c^{1}\in\mathcal{C}^{1}$, there exists $c^{2}\in\mathcal{C}^{2}$ such that
$\mathcal{X}_{c^{1}}=\mathcal{X}_{c^{2}}$. The collections of commanders and
their associated responsibilities represent the operational command structure.

Each player $i\in\\{1,2\\}$ operates a collection of bases $\mathcal{B}^{i}$,
with each base managed by one of Player $i$’s commanders. For Player 1 (resp.
Player 2), we assume that each commander’s base provides access to the first
objective $o^{x}_{1}$ (resp. last objective $o^{x}_{|x|}$) of each axis $x$
under their responsibility. A base, which may represent one geographic
location (e.g. a port), multiple geographic locations (e.g., a dispersed Army
Corps), or a non-geographic location (e.g., in the Cyber domain), represents
the origin for operational command and control (C2), unit arrival, and the
supply chain for the associated commander.

###  3.2 Stochastic Game Formulation

To capture the competitive and dynamic interactions of armed conflict, we
formulate a two-player discounted zero-sum stochastic game over an infinite
horizon, expressed by the tuple
$\Gamma\coloneqq\langle\mathcal{S},(\mathcal{A}^{1},\mathcal{A}^{2}),P,L,\gamma\rangle$.
The game is played over stages, that is, discrete times where players take
actions. $\mathcal{S}$ represents the finite state space, $\mathcal{A}^{1}$
(resp. $\mathcal{A}^{2}$) the state-dependent action space of Player 1 (resp.
Player 2), $P$ the state transition probability function, $L$ the single-stage
loss function, and $\gamma$ the discount factor between subsequent stages. We
next detail each of these quantities. Following the game-theoretic convention,
when considering Player $i$ (for $i\in\\{1,2\\}$), we refer to their opponent
as Player $-i$.

State space: At any given stage, we model the campaign state using a vector
$s\in\\{1,2\\}^{\mathcal{O}}$, which represents the control of each objective.
Specifically, for any objective $o\in\mathcal{O}$, $s_{o}=1$ (resp. $s_{o}=2$)
if objective $o$ is controlled by Player 1 (resp. Player 2). We denote as
$\mathcal{S}\coloneqq\\{1,2\\}^{\mathcal{O}}$ the campaign state space,
equipped with a partial order $\preceq$, representing the component-wise
inequality between states.

Action spaces: At every stage, the players select actions to vie for control
of objectives. This can be achieved by Player $i$ attempting to maintain
control of their objectives or gain control of their opponent’s objectives.
Each player’s action is comprised of _orders_ for each commander. We assume
that each commander for each player can give one order to attack (_atk_) or
reinforce (_rfc_) a single objective under their responsibility. The order for
all other objectives is none. An attack order on objective $o\in\mathcal{O}$
gives the attacking player a chance of gaining control of $o$. A reinforce
order on objective $o$ adds a defensive layer and reduces the chance of losing
an objective should the opponent attack $o$.

Let us consider a campaign state $s\in\mathcal{S}$. To attack or reinforce an
objective, we assume the military operation requires C2, units, assets, and
supplies such as fuel and ammunition that project from a base along the
objective’s axis. A military operation cannot bypass any interim objective on
the corresponding axis, because these objectives are necessary to maintain the
C2, units, assets, and supplies required to proceed to a subsequent objective.
The military concept of line of communication (LoC) historically originates
from human-delivered communication, but today the concept extends beyond
communication. While maintaining the acronym, we will use the terminology line
of control, which is a route that connects a military unit with its supply
chain. A LoC is deemed “open” if the military controls every objective along
that route. In our setting, this translates as follows: Given an objective
$o^{x}_{k}$ belonging to an axis $x\in\mathcal{X}$, Player 1 (resp. Player 2)
has an open LoC to $o^{x}_{k}$ if $s_{o^{x}_{j}}=1$ for every
$j\in\\{1,\dots,k-1\\}$ (resp. $s_{o^{x}_{j}}=2$ for every
$j\in\\{k+1,\dots,|x|\\}$). We denote as
$\overline{\mathcal{O}}^{i}_{s}\subseteq\mathcal{O}$ the set of objectives
with an open LoC from Player $i$’s bases $\mathcal{B}^{i}$. As a result,
Player $i$ can reinforce an objective $o\in\mathcal{O}$ they control, provided
it has an open LoC from $\mathcal{B}^{i}$ (i.e., if
$o\in\overline{\mathcal{O}}^{i}_{s}$ and $s_{o}=i$). Furthermore, Player $i$
can attack an objective they do not control provided it has an open LoC from
$\mathcal{B}^{i}$ (i.e., if $o\in\overline{\mathcal{O}}^{i}_{s}$ and
$s_{o}=-i$).

For each $i\in\\{1,2\\}$, we denote Player $i$’s action as
$a^{i}\in\\{\textit{atk,rfc,none}\\}^{\mathcal{O}}$, where $a^{i}_{o}$
represents the order for objective $o\in\mathcal{O}$. Action $a^{i}$ is
feasible if it satisfies

$\displaystyle\forall\;o\in\mathcal{O},\
a_{o}^{i}\in\begin{cases}\\{\textit{none}\\}&\text{if
}o\notin\overline{\mathcal{O}}^{i}_{s}\\\ \\{\textit{none,rfc}\\}&\text{if
}o\in\overline{\mathcal{O}}^{i}_{s}\text{ and }s_{o}=i\\\
\\{\textit{{none,atk}}\\}&\text{if }o\in\overline{\mathcal{O}}^{i}_{s}\text{
and }s_{o}=-i\end{cases}$ (1) $\displaystyle\forall\;c\in\mathcal{C}^{i},\
|\\{a^{i}_{o}\in\\{\textit{atk,rfc}\\},\ \forall\;o\in\mathcal{O}_{c}\\}|\leq
1.$ (2)

We denote as $\mathcal{A}^{i}_{s}$ the set of feasible actions for Player $i$
at state $s$.

In Figure 2, we illustrate a campaign containing 6 objectives partitioned into
three axes $x_{1}=\\{1,2\\}$, $x_{2}=\\{3,4\\}$, $x_{3}=\\{5,6\\}$ managed by
2 commanders for each player. For both players, Commander 1 is responsible for
$x_{1}$ and Commander 2 is responsible for $x_{2}$ and $x_{3}$. The current
state is given by $s=(2,2,1,2,1,1)$. In this example, Player 1 selects a
feasible action
$a^{1}=(\textit{atk},\textit{none},\textit{none},\textit{none},\textit{none},\textit{rfc})$
that attacks objective 1 and reinforces objective 6.

$1$$2$$3$$4$$5$$6$Player 1Player 2$\mathcal{B}^{1}$$\mathcal{B}^{2}$Commander
1Commander 1Commander 2Commander 2 Figure 2: Campaign example with 6
objectives and 2 bases for each player. Player 1 controls objectives 3, 5, and
6. Player 2 controls objectives 1, 2, and 4. Player 1 orders Commander 1 to
attack objective 1 and Commander 2 to reinforce objective 6.

Transition probabilities: If an objective is attacked by the non-controlling
player, a battle occurs with an uncertain outcome. We define a transition
probability function $P$ that, given a current state and the players’ actions,
determines the probability of transitioning to a new state. These
probabilities are created by domain experts including wargamers, operational
planners, and weapon system experts. In this article, we model the dynamics of
a battle for an objective as a probability chain with one or two events, where
the second event only occurs if the objective is reinforced by the controlling
player. Specifically, consider a battle occurring for an objective
$o\in\mathcal{O}$ controlled by Player $i$ (i.e., $s_{o}=i$,
$a^{-i}_{o}=atk$). Player $i$ is the _defender_ of $o$, and Player $-i$ is the
_attacker_. There are two possible outcomes for the subsequent state
$s^{\prime}_{o}$ of that objective: the objective is retained by the defender
(i.e., $s^{\prime}_{o}=i$), or the objective is gained by the attacker (i.e.,
$s^{\prime}_{o}=-i$). If $a^{i}_{o}=none$ (i.e., the defender does not
reinforce objective $o$), then Player $i$ still defends the objective $o$ with
a first level of defense (e.g., with units already assigned to the objective),
and Player $-i$ gains control of objective $o$ with a state-dependent _base
attack success probability_ $\alpha^{-i}_{o,s}\in[0,1]$. If
$a^{i}_{o}=\textit{rfc}$ (i.e., the defender does reinforce objective $o$),
then Player $i$ adds another defensive layer, which itself manages to thwart
the attack with a state-dependent _reinforce success probability_
$\rho^{i}_{o,s}\in[0,1]$. A reinforce order indicates that a commander
dedicates additional units and assets along the LoC to protect the objective.
Assuming independence between the two defensive layers, Player $-i$’s attack
becomes successful with probability
$\alpha^{-i}_{o,s}\cdot(1-\rho^{i}_{o,s})$. Figure 3 illustrates the
transition dynamics for one battle.

$s_{o}=i$$\alpha^{-i}_{o,s}=0.7$$1-\alpha^{-i}_{o,s}=0.3$$0.3$$0.7$$s_{o}^{\prime}=i$$s_{o}^{\prime}=-i$Battle
case 1: $a_{o}^{i}=none$Battle case 2:
$a_{o}^{i}=\textit{rfc}$$s_{o}=i$$\alpha^{-i}_{o,s}=0.7$$1-\alpha^{-i}_{o,s}=0.3$$0.3$$s_{o}^{\prime}=i$$1-\rho^{i}_{o,s}=0.6$$\rho^{i}_{o,s}=0.4$$0.28$$0.42$$s_{o}^{\prime}=i$$s_{o}^{\prime}=-i$
Figure 3: Probabilities of battle outcomes when Player $-i$ attacks objective
$o$.

For notational convenience, we let $\alpha^{i}_{o,s}=1$ if $s_{o}=i$ and
$\rho^{i}_{o,s}=0$ if $s_{o}=-i$. Through $\alpha$ and $\rho$, controlling
objectives in one axis may affect operations across all axes. For instance
gaining air superiority, although perhaps not a precedence requirement before
launching a ground attack, will greatly increase its likelihood of succeeding.

We make the following natural assumptions on the base attack and reinforce
success probabilities:

Player 1’s (resp. Player 2’s) base attack and reinforce success probabilities
are antitone (resp. isotone) functions of the state space:

$\displaystyle\forall\;s\preceq s^{\prime}\in\mathcal{S},\
\forall\;o\in\mathcal{O},\ \alpha^{1}_{o,s}\geq\alpha^{1}_{o,s^{\prime}},\
\rho^{1}_{o,s}\geq\rho^{1}_{o,s^{\prime}},\text{ and }\
\alpha^{2}_{o,s}\leq\alpha^{2}_{o,s^{\prime}},\
\rho^{2}_{o,s}\leq\rho^{2}_{o,s^{\prime}}.$

For every player, the probability of gaining control of a reinforced objective
is at most the probability of maintaining control of that reinforced
objective, given an identical control of all other objectives:

$\displaystyle\forall\;i\in\\{1,2\\},\ \forall\;o\in\mathcal{O},\
\forall\;(s,s^{\prime})\in\mathcal{S}^{2}\ |\
s_{o^{\prime}}=s^{\prime}_{o^{\prime}}\
\forall\;o^{\prime}\in\mathcal{O}\setminus\\{o\\},\text{ then }\
1-\alpha^{-i}_{o,s}(1-\rho^{i}_{o,s})\geq\alpha^{i}_{o,s^{\prime}}(1-\rho^{-i}_{o,s^{\prime}}).$

Assumption 3 follows the military intuition that one force can better attack
or reinforce if they control more objectives. For instance, an air mission
will have higher likelihood of success if multiple airbases are controlled.
Similarly, a ground operation will be more successful if multiple key terrain
objectives are already controlled. We do not model the notion of spreading
forces too thin and assume that the players’ commanders have sufficient combat
power in their bases such that it is never a disadvantage to control more
objectives.

Assumption 3.2 is rooted in military doctrine that more forces are required to
attack than to defend an objective. In ancient times, Sun Tzu (Giles, 2013)
advocated a five to one ratio for attacking forces versus defending forces.
More recently the U.S. Army (HQDA 2016) recommends a three to one force ratio
for an attacker versus a prepared defense. In the case study (Section 5.2), we
discuss one process to create $\alpha$ and $\rho$.

When multiple battles occur simultaneously, we assume that their outcomes are
independent. Then, the transition probability function is given as follows:

$\displaystyle\forall\;s\in\mathcal{S},\
\forall\;(a^{1},a^{2})\in\mathcal{A}^{1}_{s}\times\mathcal{A}^{2}_{s},\
\forall\;s^{\prime}\in\mathcal{S},\
P(s^{\prime}\,|\,s,a^{1},a^{2})=\prod_{o\in\mathcal{O}}p_{o}(s_{o}^{\prime}\,|\,s,a^{1}_{o},a^{2}_{o}),$

where,

$\displaystyle\forall\;i\in\\{1,2\\},\ \forall\;o\in\mathcal{O}\ |\
s_{o}^{\prime}=i,\
p_{o}(s_{o}^{\prime}\,|\,s,a^{1}_{o},a^{2}_{o})=\begin{cases}1-\alpha^{-i}_{o,s}\cdot\mathds{1}_{\\{a^{-i}_{o}=\textit{atk}\\}}\cdot(1-\rho^{i}_{o,s}\cdot\mathds{1}_{\\{a^{i}_{o}=\textit{rfc}\\}})&\text{if
}s_{o}=\phantom{-}i\\\
\alpha^{i}_{o,s}\cdot\mathds{1}_{\\{a^{i}_{o}=\textit{atk}\\}}\cdot(1-\rho^{-i}_{o,s}\cdot\mathds{1}_{\\{a^{-i}_{o}=\textit{rfc}\\}})&\text{if
}s_{o}=-i.\end{cases}$

Stage loss: We suppose that each objective $o\in\mathcal{O}$ is associated
with an individual loss value $\ell_{o}\in\mathbb{R}_{\geq 0}$, which is
incurred by Player 1 when objective $o$ is controlled by Player 2. Then, the
total stage loss incurred at state $s\in\mathcal{S}$ is given by
$L(s)=\sum_{o\in\mathcal{O}}\ell_{o}\cdot\mathds{1}_{\\{s_{o}=2\\}}$. Player 1
seeks to minimize the loss, while Player 2 seeks to maximize it.

Discount factor: We suppose that the players interact dynamically over an
infinite horizon, and we consider a discount factor $\gamma\in(0,1)$ that
impacts the importance of future stage losses relative to the current loss
(Leslie et al., 2020). Another interpretation is that $1-\gamma$ represents
the probability that the conflict ends at the end of each stage (Puterman,
2005). For our application, $\gamma$ models the incentive for both sides to
conclude a campaign expediently, before casualties and equipment losses mount.
Since modeling casualties and equipment losses explicitly would necessitate a
prohibitively large state space, we offer that a smaller discount factor
accounts for attrition implicitly, as gaining objectives at a later time will
have less utility due to attrition from a lengthy campaign. From a
geopolitical perspective, a smaller discount factor may represent the
importance of concluding a conflict rapidly before political will subsides. We
assume that concluding a conflict is equally preferable for both sides.

Stationary policies: At any state, each player may benefit from randomizing
their actions to create uncertainty that cannot be exploited by their
opponent. We focus our analysis on _stationary_ (or _Markovian_) _policies_
for each player. A stationary policy $\pi^{i}$ for Player $i$ maps each state
$s\in\mathcal{S}$ to a probability distribution $\pi^{i}(s)$ over Player $i$’s
state-dependent action set $\mathcal{A}^{i}_{s}$. We denote as
$\Delta(\mathcal{A}^{i}_{s})$ the probability simplex over
$\mathcal{A}^{i}_{s}$ and
$\Delta^{i}\coloneqq\prod_{s\in\mathcal{S}}\Delta(\mathcal{A}^{i}_{s})$ the
set of stationary policies for Player $i$. Given a policy
$\pi^{i}\in\Delta^{i}$ for Player $i$,
$\pi^{i}(s)\in\Delta(\mathcal{A}^{i}_{s})$ denotes the mixed strategy
implemented at a given state $s$ and $\pi^{i}(s,a^{i})$ the probability that
action $a^{i}\in\mathcal{A}^{i}_{s}$ is realized at state $s$. Furthermore,
for every state $s\in\mathcal{S}$, we assume that the probability
distributions $\pi^{1}(s)$ and $\pi^{2}(s)$ are independent.

Cumulative loss: Given a policy profile
$(\pi^{1},\pi^{2})\in\Delta^{1}\times\Delta^{2}$, the stochastic game $\Gamma$
starts from an initial state $s^{(0)}=s\in\mathcal{S}$. Then, each player $i$
observes $s^{(0)}$ and simultaneously draws an action
$a^{i,(0)}\sim\pi^{i}(s^{(0)})$. The campaign then transitions to a new state
$s^{(1)}\sim P(\cdot\,|\,s^{(0)},a^{1,(0)},a^{2,(0)})$. The process is
infinitely repeated, resulting in a Markov chain $s^{(0)},s^{(1)},\dots$ Given
the discount factor $\gamma$, the corresponding expected discounted cumulative
loss is then given by:

$\displaystyle
V(s,\pi^{1},\pi^{2})=\mathbb{E}\left[\sum_{t=0}^{+\infty}\gamma^{t}\cdot
L(s^{(t)})\,\Big{|}\,s^{(0)}=s\right],$

where the expectation is taken over the players’ actions
$a^{i,(t)}\sim\pi^{i}(s^{(t)})$ and the state transitions $s^{(t+1)}\sim
P(\cdot\,|\,s^{(t)},a^{1,(t)},a^{2,(t)})$ at each stage $t$. We refer to
$V(s,\pi^{1},\pi^{2})$ as the _value_ function under strategy profile
$(\pi^{1},\pi^{2})$ and initial state $s$. Equivalently, the value function is
given by the following recursive Bellman policy equation:

$\displaystyle\
V(s,\pi^{1},\pi^{2})=\sum_{\begin{subarray}{c}a^{1}\in\mathcal{A}^{1}_{s}\\\
a^{2}\in\mathcal{A}^{2}_{s}\end{subarray}}\pi^{1}(s,a^{1})\cdot\pi^{2}(s,a^{2})\cdot\left(L(s)+\gamma\cdot\sum_{s^{\prime}\in\mathcal{S}}P(s^{\prime}\,|\,s,a^{1},a^{2})\cdot
V(s^{\prime},\pi^{1},\pi^{2})\right).$

Given a starting state $s$, Player $1$ (resp. Player $2$) aims to minimize
(resp. maximize) the value function.

Markov perfect equilibria: In such stochastic games, the optimal solution
concept is given by _Markov perfect equilibria_ (MPE). Specifically, a policy
profile $(\pi^{1^{*}},\pi^{2^{*}})\in\Delta^{1}\times\Delta^{2}$ is an MPE of
the stochastic game $\Gamma$ if

$\displaystyle\forall\;s\in\mathcal{S},\
\forall\;(\pi^{1},\pi^{2})\in\Delta^{1}\times\Delta^{2},\
V(s,\pi^{1^{*}},\pi^{2})\leq V(s,\pi^{1^{*}},\pi^{2^{*}})\leq
V(s,\pi^{1},\pi^{2^{*}}).$

In other words, no player has a unilateral incentive to deviate from their
policy regardless of the initial state. For every $s\in\mathcal{S}$, we denote
as $V^{*}(s)\coloneqq V(s,\pi^{1^{*}},\pi^{2^{*}})$ the optimal value of the
game $\Gamma$ at state $s$. By extension, the approximate solution concept is
given by approximate MPE: Given $\epsilon\in\mathbb{R}_{>0}$, a policy profile
$(\pi^{1^{\prime}},\pi^{2^{\prime}})\in\Delta^{1}\times\Delta^{2}$ is an
$\epsilon$-MPE of the stochastic game $\Gamma$ if

$\displaystyle\forall\;s\in\mathcal{S},\
\forall\;(\pi^{1},\pi^{2})\in\Delta^{1}\times\Delta^{2},\
V(s,\pi^{1^{\prime}},\pi^{2})-\epsilon\leq
V(s,\pi^{1^{\prime}},\pi^{2^{\prime}})\leq
V(s,\pi^{1},\pi^{2^{\prime}})+\epsilon.$

In his fundamental paper, Shapley, (1953) generalized von Neumann,’s minimax
theorem to show the existence of MPE in such discounted zero-sum stochastic
games. The proof contains _Shapley’s value iteration_ , which is an algorithm
to approximately compute the optimal value function and optimal policies.
Since Shapley, numerous algorithms have been proposed to find MPE or
$\epsilon$-MPE solutions to discounted, zero-sum stochastic games (Raghavan &
Filar, 1991). These methods include the Hoffman-Karp, Pollatschek-Avi Itzhak,
van der Wal, and Brown’s fictitious play algorithms (Hoffman & Karp, 1966,
Pollatschek & Avi-Itzhak, 1969, Van der Wal, 1978, Vrieze & Tijs, 1982).
However, stochastic games face the well-known curse of dimensionality, which
hinders the scalability of classical solution algorithms. In the next section,
we exploit the campaign’s structure to mitigate these computational issues and
obtain MPEs more efficiently.

##  4 Solution Methodology

In this section, we derive equilibrium properties of the stochastic game
$\Gamma$. This permits us to significantly reduce the state and action spaces,
and accelerate the value iteration algorithm for computing MPEs.

###  4.1 Shapley’s Value Iteration

Shapley’s classical value iteration (VI) algorithm is based on the fact that
the optimal value function $V^{*}=(V^{*}(s))_{s\in\mathcal{S}}$ of the game
$\Gamma$ is the fixed point of the contraction mapping
$T:\mathbb{R}^{\mathcal{S}}\to\mathbb{R}^{\mathcal{S}}$ defined by
$T(V^{\prime})=(T(V^{\prime},s))_{s\in\mathcal{S}}$ for every
$V^{\prime}\in\mathbb{R}^{\mathcal{S}}$ with

$\displaystyle\
T(V^{\prime},s)\coloneqq\min_{\pi^{1}(s)\in\Delta(\mathcal{A}^{1}_{s})}\max_{a^{2}\in\mathcal{A}^{2}_{s}}\sum_{a^{1}\in\mathcal{A}^{1}_{s}}\pi^{1}(s,a^{1})\cdot\left(L(s)+\gamma\cdot\sum_{s^{\prime}\in\mathcal{S}}P(s^{\prime}\,|\,s,a^{1},a^{2})\cdot
V^{\prime}(s^{\prime})\right).$

The contraction mapping $T(V^{\prime})$ consists of solving at every state
$s\in\mathcal{S}$ a zero-sum matrix game $\Gamma(V^{\prime},s)$, where the
payoff matrix is given by
$R(V^{\prime},s)=(R(V^{\prime},s,a^{1},a^{2}))_{(a^{1},a^{2})\in\mathcal{A}^{1}_{s}\times\mathcal{A}^{2}_{s}}$
with

$\displaystyle\forall\;(a^{1},a^{2})\in\mathcal{A}^{1}_{s}\times\mathcal{A}^{2}_{s},\
R(V^{\prime},s,a^{1},a^{2})\coloneqq
L(s)+\gamma\cdot\sum_{s^{\prime}\in\mathcal{S}}P(s^{\prime}\,|\,s,a^{1},a^{2})\cdot
V^{\prime}(s^{\prime}).$

As a reminder, every zero-sum game $\Gamma(V^{\prime},s)$ can be solved using
the following linear program:

$\displaystyle\text{LP}(R(V^{\prime},s),\mathcal{A}^{1}_{s},\mathcal{A}^{2}_{s}):\quad\min_{\pi^{1}(s),\,z}\
$ $\displaystyle z$ s.t.
$\displaystyle\sum_{a^{1}\in\mathcal{A}^{1}_{s}}R(V^{\prime},s,a^{1},a^{2})\cdot\pi^{1}(s,a^{1})\leq
z,\ $ $\displaystyle\forall\;a^{2}\in\mathcal{A}^{2}_{s}$
$\displaystyle\sum_{a^{1}\in\mathcal{A}^{1}_{s}}\pi^{1}(s,a^{1})=1$
$\displaystyle\pi^{1}(s,a^{1})\geq 0,\ $
$\displaystyle\forall\;a^{1}\in\mathcal{A}^{1}_{s}.$

Its optimal primal and dual solutions provide Player $1$’s and Player $2$’s
respective mixed strategies in equilibrium of $\Gamma(V^{\prime},s)$, and its
optimal value provides $T(V^{\prime},s)$.

The VI algorithm first initializes with $V^{(0)}\in\mathbb{R}^{\mathcal{S}}$
(we select $V^{(0)}=L$) and iteratively applies the mapping $T$, thus creating
a sequence of vectors $(V^{(t)})_{t\in\mathbb{Z}_{\geq 0}}$ that converges
towards $V^{*}$. Given $\epsilon\in\mathbb{R}_{>0}$, the algorithm terminates
when $\|V^{(t)}-V^{(t-1)}\|_{\infty}\leq\epsilon(1-\gamma)/(2\gamma)$. This
ensures that $\|V^{*}-V^{(t)}\|_{\infty}\leq\epsilon/2$ and that solving the
zero-sum game $\Gamma(V^{(t-1)},s)$ for every state $s$ provides an
$\epsilon$-MPE
$(\pi^{1^{\prime}},\pi^{2^{\prime}})\in\Delta^{1}\times\Delta^{2}$ (Puterman,
2005, Deng et al., 2022). The algorithm is guaranteed to terminate with
$t\leq\lceil\frac{\log(\epsilon\cdot(1-\gamma)^{2})-\log(2\sum_{o\in\mathcal{O}}\ell_{o})}{\log\gamma}\rceil$.
Since the running time of this algorithm is primarily driven by the number of
states and actions, we next analyze the game’s structure to reduce the state
and action spaces and improve the algorithm’s efficiency.

###  4.2 State and Action Space Reduction

We recall that the stochastic game $\Gamma$ is of large size, namely, its
state space is of size $|\mathcal{S}|=2^{|\mathcal{O}|}$, and Player $i$’s
action space at every state $s\in\mathcal{S}$ is of size
$|\mathcal{A}^{i}_{s}|=\prod_{c\in\mathcal{C}^{i}}(1+|\overline{\mathcal{O}}^{i}_{s}\cap\mathcal{O}_{c}|)$.
By leveraging the military operational C2 and logistics structure, we next
derive equilibrium properties of $\Gamma$.

###### Theorem 4.1

The optimal value of $\Gamma$ is an isotone function of the state space and
satisfies

$\displaystyle\forall\;s\preceq s^{\prime}\in\mathcal{S},\
V^{*}(s^{\prime})-V^{*}(s)\geq\sum_{o\in\mathcal{O}}\ell_{o}\cdot\mathds{1}_{\\{s^{\prime}_{o}=2\text{
and }s_{o}=1\\}}.$ (3)

From Theorem 4.1, we observe that if the initial state is such that more
objectives are controlled by Player 1, then the cumulative loss incurred over
the infinite horizon in equilibrium will be lower. While this result seems
intuitive, its proof is more involved, as typical arguments to show
monotonicity in Markov decision processes do not hold (Puterman, 2005). The
challenge lies in that the state space only has a partial order, the action
spaces are state-dependent, and the likelihood of transitioning to a better
state is not an isotone function of the current state for every action.
Instead, our proof exploits the LoC structure, the game-theoretic interactions
between players, and Assumptions 3 and 3.2 on the characteristics of the
transition probability function. In fact, the following counterexample shows
that the monotonicity property does not necessarily hold in equilibrium
without Assumption 3.2.

Consider a campaign with three objectives $\\{1,2,3\\}$ illustrated in Figure
4. Each objective is on its own axis and is managed by a distinct commander.
The objective losses satisfy $\ell_{1}>0$ and $\ell_{2}=\ell_{3}$, and all
reinforce success probabilities at every state are 0.

We next consider two possible initial states given by $s=(1,1,2)$ and
$s^{\prime}=(2,1,2)$, which satisfy $s\preceq s^{\prime}$. We assume that
Player 1’s base attack success probabilities satisfy
$\alpha^{1}_{1,s^{\prime}}=1$, $\alpha^{1}_{2,s}=\alpha^{1}_{2,s^{\prime}}=0$,
and $\alpha^{1}_{3,s}=\alpha^{1}_{3,s^{\prime}}=1$. Similarly, Player 2’s base
attack success probabilities satisfy $\alpha^{2}_{1,s}=1$,
$\alpha^{2}_{2,s}=\alpha^{2}_{2,s^{\prime}}=1$, and
$\alpha^{2}_{3,s}=\alpha^{2}_{3,s^{\prime}}=0$.

State $s$$1$$2$$3$State $s^{\prime}$$1$$2$$3$State $\tilde{s}$$1$$2$$3$State
$\tilde{s}^{\prime}$$1$$2$$3$ Figure 4: Counterexample to the isotonicity of
the optimal value function without Assumption 3.2.

We also consider four states $s^{1}=(1,1,1)$, $\tilde{s}^{\prime}=(1,2,1)$,
$\tilde{s}=(2,2,1)$, $s^{2}=(2,2,2)$, for which we assume that all base attack
success probabilities of uncontrolled objectives are 0:

$\displaystyle\alpha^{2}_{1,s^{1}}=\alpha^{2}_{2,s^{1}}=\alpha^{2}_{3,s^{1}}=\alpha^{2}_{1,\tilde{s}^{\prime}}=\alpha^{1}_{2,\tilde{s}^{\prime}}=\alpha^{2}_{3,\tilde{s}^{\prime}}=\alpha^{1}_{1,\tilde{s}}=\alpha^{1}_{2,\tilde{s}}=\alpha^{2}_{3,\tilde{s}}=\alpha^{1}_{1,s^{2}}=\alpha^{1}_{2,s^{2}}=\alpha^{1}_{3,s^{2}}=0.$

As a result, $s^{1}$, $\tilde{s}^{\prime}$, $\tilde{s}$, $s^{2}$ are absorbing
states that satisfy

$\displaystyle V^{*}(s^{1})=0,\quad
V^{*}(\tilde{s}^{\prime})=\frac{\ell_{2}}{1-\gamma},\quad
V^{*}(\tilde{s})=\frac{\ell_{1}+\ell_{2}}{1-\gamma},\quad
V^{*}(s^{2})=\frac{\ell_{1}+\ell_{2}+\ell_{3}}{1-\gamma}.$

We note that Assumption 3 holds, but Assumption 3.2 is violated since
$\alpha^{1}_{1,s^{\prime}}+\alpha^{2}_{1,s}>1$.

Let
$a^{2^{\dagger}}=(\textit{atk},\textit{atk},\textit{none})\in\mathcal{A}^{2}_{s}$.
We then obtain the following lower bound:

$\displaystyle
V^{*}(s)\geq\min_{a^{1}\in\mathcal{A}^{1}_{s}}R(V^{*},s,a^{1},a^{2^{\dagger}})=L(s)+\gamma
V^{*}(\tilde{s})=\ell_{3}+\gamma\frac{\ell_{1}+\ell_{2}}{1-\gamma}.$

Similarly, let
$a^{1^{\dagger}}=(\textit{atk},\textit{none},\textit{atk})\in\mathcal{A}^{1}_{s^{\prime}}$.
We then obtain the following upper bound:

$\displaystyle
V^{*}(s^{\prime})\leq\max_{a^{2}\in\mathcal{A}^{2}_{s^{\prime}}}R(V^{*},s^{\prime},a^{1^{\dagger}},a^{2})=L(s^{\prime})+\gamma
V^{*}(\tilde{s}^{\prime})=\ell_{1}+\ell_{3}+\gamma\frac{\ell_{2}}{1-\gamma}.$

Since $\ell_{2}=\ell_{3}$ and $\ell_{1}+\ell_{2}>\ell_{3}$, we then obtain the
non-isotonicity of the optimal value function when $\gamma>0.5$:

$\displaystyle
V^{*}(s)\geq\frac{(1-\gamma)\cdot\ell_{3}+\gamma\cdot(\ell_{1}+\ell_{2})}{1-\gamma}>\frac{(1-\gamma)\cdot(\ell_{1}+\ell_{3})+\gamma\cdot\ell_{2}}{1-\gamma}\geq
V^{*}(s^{\prime}).$

$\triangle$

We next investigate the states that are achievable and the actions that are
selected with positive probability in equilibrium of the stochastic game
$\Gamma$. To this end, we propose the following axis classification at a given
state and define _battle fronts_ for each player. Consider an axis
$x=(o_{1},\dots,o_{n})\in\mathcal{X}$ of size $n$ and a state
$s\in\mathcal{S}$.

If for every $k\in\\{1,\dots,n\\}$, $s_{o_{k}}=1$ (i.e., every objective on
that axis is controlled by Player $1$), then we say that $x$ is of type
$\tau_{x,s}=\textit{c1}$, and the battle front occurs at the objective
$\widetilde{\mathcal{O}}^{i}_{x,s}=\\{o_{n}\\}$ for each player $i$.

If for every $k\in\\{1,\dots,n\\}$, $s_{o_{k}}=2$ (i.e., every objective on
that axis is controlled by Player $2$), then we say that $x$ is of type
$\tau_{x,s}=\textit{c2}$, and the battle front occurs at the objective
$\widetilde{\mathcal{O}}^{i}_{x,s}=\\{o_{1}\\}$ for each player $i$.

If there exists $k\in\\{1,\dots,n-1\\}$ such that
$s_{o_{1}}=\cdots=s_{o_{k}}=1$ and $s_{o_{k+1}}=\cdots=s_{o_{n}}=2$, then we
say that $x$ is of type $\tau_{x,s}=\textit{pf}$, and a pure front exists at
the objectives $\widetilde{\mathcal{O}}^{i}_{x,s}=\\{o_{k},o_{k+1}\\}$ for
each player $i$.

If there exists $k\in\\{1,\dots,n-1\\}$ such that
$s_{o_{1}}=\cdots=s_{o_{k-1}}=1$, $s_{o_{k}}=2$, $s_{o_{k+1}}=1$, and
$s_{o_{k+2}}=\cdots=s_{o_{n}}=2$, then we say that $x$ is of type
$\tau_{x,s}=\textit{sf}$, and a split front exists, i.e., a front exists for
Player 1 at objective $\widetilde{\mathcal{O}}^{1}_{x,s}=\\{o_{k}\\}$ and
another front exists for Player 2 at objective
$\widetilde{\mathcal{O}}^{2}_{x,s}=\\{o_{k+1}\\}$.

We illustrate these axis types and the battle fronts in Figure 5.

$1$$2$$3$$4$$5$$6$$7$$8$$9$$10$$11$$12$$13$$14$$15$$16$c1:c2:pf:sf:FFFFF
Figure 5: Axis classification: In c1, the front (denoted F) for both players
is at objective 4. In c2 the front for both players is at objective 5. In pf
the front for both players is at objectives 10 and 11. Finally, for sf the
front is at objective 14 for Player 1, and at objective 15 for Player 2.

We make the following assumption regarding the initial state of the campaign:

At the initial state $s^{(0)}\in\mathcal{S}$, every axis $x\in\mathcal{X}$ is
of type
$\tau_{x,s^{(0)}}\in\\{\textit{c1},\textit{c2},\textit{pf},\textit{sf}\\}$.

A military campaign postulates opposing forces that are initially separated by
geographic borders or necessary campaign milestones (e.g., a force cannot gain
air parity and then air superiority without suppressing or neutralizing
opponent air defenses first). Assumption 4.2 and the initial distribution of
the campaign extend from the players initial disposition to how an opponent
succeeds at the immediate outset of an attack. Thus, we assume that a force
cannot seize objectives past their supply chains or skip necessary campaign
milestones before achieving subsequent objectives.

In the next proposition, we leverage the game’s structure and Theorem 4.1 to
derive properties of the states and selected actions in equilibrium.

###### Proposition 4.2

The set of achievable states for any policy profile is

$\displaystyle\\{s\in\\{1,2\\}^{\mathcal{O}}\ |\
\tau_{x,s}\in\\{\textit{c1},\textit{c2},\textit{pf},\textit{sf}\\},\
\forall\;x\in\mathcal{X}\\}.$ (4)

There exists an MPE such that for every achievable state $s\in\mathcal{S}$,
each player $i\in\\{1,2\\}$ randomizes over actions
$a^{i}\in\mathcal{A}^{i}_{s}$ satisfying

$\displaystyle\forall\;x\in\mathcal{X},\ \forall\;o\in x,\
a_{o}^{i}\in\begin{cases}\\{\textit{none},\textit{atk}\\}&\text{if
}o\in\widetilde{\mathcal{O}}^{i}_{x,s}\text{ and }s_{o}=-i\\\
\\{\textit{none},\textit{rfc}\\}&\text{if
}o\in\widetilde{\mathcal{O}}^{i}_{x,s}\text{ and }s_{o}=i\\\
\\{\textit{none}\\}&\text{otherwise}\end{cases}$ (5)
$\displaystyle\forall\;c\in\mathcal{C}^{i},\
|\\{a^{i}_{o}\in\\{\textit{atk},\textit{rfc}\\},\
\forall\;o\in\mathcal{O}_{c}\\}|=1.$ (6)

Furthermore, if the game parameters satisfy

$\displaystyle\ell_{o}>0,\quad$ $\displaystyle\forall\;o\in\mathcal{O}$ (7)
$\displaystyle\alpha^{i}_{o,s}>0,\quad$ $\displaystyle\forall\;i\in\\{1,2\\},\
\forall\;s\in\mathcal{S},\ \forall\;o\in\overline{\mathcal{O}}^{i}_{s}\ |\
s_{o}=-i$ (8) $\displaystyle 0<\rho^{i}_{o,s}<1,\quad$
$\displaystyle\forall\;i\in\\{1,2\\},\ \forall\;s\in\mathcal{S},\
\forall\;o\in\overline{\mathcal{O}}^{i}_{s}\ |\ s_{o}=i,$ (9)

then the actions selected with positive probability in _every_ MPE satisfy
(5)-(6).

From this proposition, we obtain that under Assumption 4.2, each axis at each
stage of the campaign will belong to one of the four defined types. As a
result, we can reduce the state space $\mathcal{S}$ to the set of achievable
states (4), which is of size $\prod_{x\in\mathcal{X}}2|x|$. This provides a
substantial memory and runtime improvement: For a campaign instance with 5
axes containing 5 objectives each, the state space will be reduced by 99.7%
(from 33.55 million to 100 thousand states).

Using game-theoretic arguments and the isotonocity of the optimal value
function (Theorem 4.1), we also obtain properties of the players’ mixed
strategies implemented at each achievable state in equilibrium. At any state
$s\in\mathcal{S}$, each player has an incentive to order each commander to
reinforce or attack one objective. We also naturally observe that if a
commander attacks or reinforces an objective in an axis $x\in\mathcal{X}$,
their incentive is to do so at the battle front. If $\tau_{x,s}=\textit{c1}$
(resp. c2) then Player 1’s (resp. Player 2’s) incentive is to reinforce the
last (resp. first) objective of the axis, while Player 2’s (resp. Player 1’s)
incentive is to attack it. If $\tau_{x,s}=\textit{pf}$, then each player may
either reinforce the objective at the front they control, or attack the
objective controlled by their opponent. If each player decides to attack the
objective they do not control, and each resulting battle succeeds, then the
axis’s new type becomes sf, as a split front arises. In any sf situation,
players do not have an open LoC to their farthest controlled objective and are
unable to reinforce that objective or attack farther objectives. Accordingly,
each player $i$ only has an incentive to attack their closest uncontrolled
objective $\widetilde{\mathcal{O}}^{i}_{x,s}$.

Thus, we can reduce the players’ action spaces by removing the actions that do
not satisfy (5)-(6). Proposition 4.2 shows that in almost all cases, this
operation does not remove any MPE of $\Gamma$, while in some edge cases (i.e.,
when the game parameters do not satisfy (7)-(9)), at least one MPE will be
retained. This also provides a computational gain, as the action space sizes
are reduced to
$\prod_{c\in\mathcal{C}^{i}}\sum_{x\in\mathcal{X}_{c}}|\widetilde{\mathcal{O}}^{i}_{x,s}|$
for every player $i\in\\{1,2\\}$ and every achievable state $s\in\mathcal{S}$.
Henceforth, we assume that the state space and the players’ action spaces are
respectively reduced to (4) and (5)-(6).

###  4.3 Accelerated Shapley’s Value Iteration

We propose to accelerate the VI algorithm described in Section 4.1 by reducing
the number or size of linear programs to solve. Indeed, the campaign’s
structure leads to equilibrium properties of the zero-sum matrix game solved
at each iteration of the algorithm. In the next proposition, we analyze the
matrix game when each player has one commander.

###### Proposition 4.3

Consider a campaign with one commander for each player. Let
$t\in\mathbb{Z}_{>0}$ be an iteration of the VI algorithm, and
$s\in\mathcal{S}$ be a state.

  * –

If $|\mathcal{X}|=1$, then the zero-sum matrix game $\Gamma(V^{(t-1)},s)$
admits a pure equilibrium.

  * –

If at least one axis $x\in\mathcal{X}$ is of type $\tau_{x,s}=\textit{pf}$,
then at least one of the players does not reinforce any objective in axis $x$
in at least one equilibrium of $\Gamma(V^{(t-1)},s)$.

By leveraging the game’s structure and the isotonicity result of the function
$V^{(t-1)}$ (showed in the proof of Theorem 4.1), we were able to analytically
characterize pure equilibria of the matrix game solved at each iteration of
the VI algorithm when there is a single axis. Furthermore, when there are
multiple axes under the responsibility of a single commander, Proposition 4.3
shows that the action sets can be further reduced before solving the matrix
game.

This proposition suggests that in general, it is computationally valuable to
search for pure equilibria and eliminate actions before attempting to solve
the game via linear programing. This leads us to implement the following
algorithmic steps: At every iteration $t\in\mathbb{Z}_{>0}$ and every state
$s\in\mathcal{S}$, we first determine whether $\Gamma(V^{(t-1)},s)$ admits an
equilibrium in pure strategies, which occurs when

$\displaystyle\min_{a^{1}\in\mathcal{A}^{1}_{s}}\max_{a^{2}\in\mathcal{A}^{2}_{s}}R(V^{(t-1)},s,a^{1},a^{2})=\max_{a^{2}\in\mathcal{A}^{2}_{s}}\min_{a^{1}\in\mathcal{A}^{1}_{s}}R(V^{(t-1)},s,a^{1},a^{2}).$

If the equality holds, then
$(\pi^{1^{*}}(s),\pi^{2^{*}}(s))\in\Delta(\mathcal{A}^{1}_{s})\times\Delta(\mathcal{A}^{2}_{s})$
defined by $\pi^{1^{*}}(s,a^{1^{*}})=1$, $\pi^{2^{*}}(s,a^{2^{*}})=1$ where

$\displaystyle
a^{1^{*}}\in\argmin_{a^{1}\in\mathcal{A}^{1}_{s}}\max_{a^{2}\in\mathcal{A}^{2}_{s}}R(V^{(t-1)},s,a^{1},a^{2}),\quad\quad\quad
a^{2^{*}}\in\argmax_{a^{2}\in\mathcal{A}^{2}_{s}}\min_{a^{1}\in\mathcal{A}^{1}_{s}}R(V^{(t-1)},s,a^{1},a^{2}),$

form a pure equilibrium of $\Gamma(V^{(t-1)},s)$ and can be efficiently
computed by searching over all values of the matrix $R(V^{(t-1)},s)$.

If a pure equilibrium does not exist, we next seek to simplify the game
$\Gamma(V^{(t-1)},s)$: We implement an iterated elimination of weakly
dominated strategies to remove actions while retaining at least one
equilibrium of $\Gamma(V^{(t-1)},s)$. For Player 1, we say that action
$a^{1}\in\mathcal{A}^{1}_{s}$ _dominates_ action
$a^{1^{\prime}}\in\mathcal{A}^{1}_{s}$ in the game $\Gamma(V^{(t-1)},s)$ if
$R(V^{(t-1)},s,a^{1},a^{2})\leq R(V^{(t-1)},s,a^{1^{\prime}},a^{2})$ for every
$a^{2}\in\mathcal{A}^{2}_{s}$. Similarly, we say that Player 2’s action
$a^{2}\in\mathcal{A}^{2}_{s}$ dominates action
$a^{2^{\prime}}\in\mathcal{A}^{2}_{s}$ in the game $\Gamma(V^{(t-1)},s)$ if
$R(V^{(t-1)},s,a^{1},a^{2})\geq R(V^{(t-1)},s,a^{1},a^{2^{\prime}})$ for every
$a^{1}\in\mathcal{A}^{1}_{s}$.

This algorithm step iteratively removes weakly dominated actions, and stops
when no action is removed for either player, producing smaller sets of actions
$\bar{\mathcal{A}}^{1}_{s}\subseteq\mathcal{A}^{1}_{s}$ and
$\bar{\mathcal{A}}^{2}_{s}\subseteq\mathcal{A}^{2}_{s}$. Once the iterated
elimination terminates, the algorithm solves the smaller linear program
$\operatorname{LP}(R(V^{(t-1)},s),\bar{\mathcal{A}}^{1}_{s},\bar{\mathcal{A}}^{2}_{s})$.
These modifications to solve zero-sum matrix games are described in Algorithm
1 and are embedded into the VI algorithm, resulting in an _accelerated value
iteration_ (AVI) algorithm, summarized in Algorithm 2.

Input : State $s$, action spaces $\mathcal{A}^{1}_{s}$ and
$\mathcal{A}^{2}_{s}$, and payoff matrix
$R\in\mathbb{R}^{\mathcal{A}^{1}_{s}\times\mathcal{A}^{2}_{s}}$

1

Output : Optimal value $V^{\prime}(s)$ and equilibrium
$(\pi^{1^{\prime}}(s),\pi^{2^{\prime}}(s))\in\Delta(\mathcal{A}^{1^{\prime}}_{s})\times\Delta(\mathcal{A}^{2^{\prime}}_{s})$
of the matrix game

2

3Compute
$a^{1^{\prime}}\in\arg\min\limits_{a^{1}\in\mathcal{A}^{1}_{s}}\max\limits_{a^{2}\in\mathcal{A}^{2}_{s}}R(a^{1},a^{2})$
and
$a^{2^{\prime}}\in\arg\max\limits_{a^{2}\in\mathcal{A}^{2}_{s}}\min\limits_{a^{1}\in\mathcal{A}^{1}_{s}}R(a^{1},a^{2})$;

4

5if
$\max\limits_{a^{2}\in\mathcal{A}^{2}_{s}}R(a^{1^{\prime}},a^{2})=\min\limits_{a^{1}\in\mathcal{A}^{1}_{s}}R(a^{1},a^{2^{\prime}})$
then

6

7 $\pi^{i^{\prime}}(s,a^{i^{\prime}})\leftarrow 1$ and
$\pi^{i^{\prime}}(s,a^{i})\leftarrow 0$, $\forall\;i\in\\{1,2\\}$,
$\forall\;a^{i}\in\mathcal{A}^{i}_{s}\setminus\\{a^{i^{\prime}}\\}$;

8

9 $V^{\prime}(s)\leftarrow R(a^{1^{\prime}},a^{2^{\prime}})$;

10

11else

12

13 $\bar{\mathcal{A}}^{i}_{s}\leftarrow\mathcal{A}^{i}_{s}$,
$\forall\;i\in\\{1,2\\}$;

14

15 do

16 $Reduced\leftarrow True$;

17

18 for every $i\in\\{1,2\\}$ and every $a^{i}\neq
a^{i^{\dagger}}\in\bar{\mathcal{A}}^{i}_{s}$ do

19 if $a^{i}$ dominates $a^{i^{\dagger}}$ then

20
$\bar{\mathcal{A}}^{i}_{s}\leftarrow\bar{\mathcal{A}}^{i}_{s}\setminus\\{a^{i^{\dagger}}\\}$;

21

22 $Reduced\leftarrow False$;

23

24

25

26 while $Reduced=False$;

27 Solve
$\operatorname{LP}(R,\bar{\mathcal{A}}^{1}_{s},\bar{\mathcal{A}}^{2}_{s}))$;

28

29 $V^{\prime}(s)\leftarrow$ optimal value,
$(\pi^{1^{\prime}}(s),\pi^{2^{\prime}}(s))\leftarrow$ optimal primal and dual
solutions;

30

31

32return $V^{\prime}(s)$, $(\pi^{1^{\prime}}(s),\pi^{2^{\prime}}(s))$

Algorithm 1 Accelerated Zero-Sum Matrix Game Solution
(AZS($s,\mathcal{A}^{1}_{s},\mathcal{A}^{2}_{s},R$))

Input : Game
$\Gamma=\langle\mathcal{S},(\mathcal{A}^{1},\mathcal{A}^{2}),P,L,\gamma\rangle$
and optimality gap $\epsilon\in\mathbb{R}_{>0}$

Output : $\epsilon/2-$approximate game value
$V^{(t)}\in\mathbb{R}^{\mathcal{S}}$ and $\epsilon$-MPE
$(\pi^{1^{\prime}},\pi^{2^{\prime}})\in\Delta^{1}\times\Delta^{2}$

1

2$t\leftarrow 0$;

3

4$V^{(t)}\leftarrow L$;

5

6do

7 $t\leftarrow t+1$;

8

9 for every $s\in\mathcal{S}$ do

10

11 $R(V^{(t-1)},s,a^{1},a^{2})\leftarrow
L(s)+\gamma\cdot\sum_{s^{\prime}\in\mathcal{S}}P(s^{\prime}\,|\,s,a^{1},a^{2})\cdot
V^{(t-1)}(s^{\prime}),\
\forall\;(a^{1},a^{2})\in\mathcal{A}^{1}_{s}\times\mathcal{A}^{2}_{s}$;

12

13 $(V^{(t)}(s),(\pi^{1^{\prime}}(s),\pi^{2^{\prime}}(s)))\leftarrow$
AZS($s,\mathcal{A}^{1}_{s},\mathcal{A}^{2}_{s},R(V^{(t-1)},s)$);

14

15

16while $\|V^{(t)}-V^{(t-1)}\|_{\infty}>\epsilon(1-\gamma)/(2\gamma)$;

17return $V^{(t)}$, $(\pi^{1^{\prime}},\pi^{2^{\prime}})$

Algorithm 2 Accelerated Value Iteration (AVI)

In the next section, we test the VI and AVI algorithms on representative
campaign instances and show the computational gain provided by the equilibrium
properties derived in this section.

##  5 Case Study

This section illustrates our stochastic game application to military
campaigns. We build our case study upon a fictional geopolitical scenario and
derive insights from the MPE policy and value. We then compare the
computational performance of the VI and AVI algorithms for military campaigns
of various sizes. All algorithms are implemented in Python v.3.8.5 and all
optimization problems are solved using Gurobi v.10.0.1 on an Intel i7-9750H
processor with a 2.60 GHz (1 core) CPU on a single thread with 16 GB of RAM.

###  5.1 Campaign Geography

We consider a fictitious country, Isthia, which is an isthmus under attack
from an aggressor country, Adversary, to their East. Isthia controls a key
canal that bisects the country. Recent geopolitical affairs have inhibited
Adversary’s use of this canal, so they seek to gain control of the canal and
seize a portion of Isthia. Furthermore, Adversary seeks to threaten Isthia’s
sovereignty by seizing their seat of government and controlling their largest
city. Controlling a large portion of Isthia will force favorable negotiations
for Adversary.

Isthia has a large mountain range through the East-West spine of the country
that largely inhibits North-South travel for large military forces. There is a
key corridor between and a road system adjacent to the canal, but other
mountain roads cannot support large military forces. Isthia is surrounded on
the North by the North Ocean and on the South by the South Ocean. The
countries to the West of Isthia are allies and guarantee free maneuver and
travel to coalition forces allied with Isthia. We refer to the coalition
(Isthia and allies) as Player 1 and to Adversary as Player 2.

There are three distinct commanders for each player: The air commander who is
responsible for all airspace in the campaign (air axis), the ground commander
who is responsible for the Northern axis and Southern axis (ground axes), and
the maritime commander who is responsible for maritime operations in the North
and South Oceans (maritime axes). We depict the case study geography and
objectives in Figure 6. The air objectives are either spread out
geospatially—Integrated Air Defense System 1 and 2 (objs. 1 and 4)—or they are
not geographic—Airspace 1 and 2 (objs. 2 and 3).

Figure 6: Campaign geography and objectives. We illustrate the effect of
Player 1 controlling Integrated Air Defense System (obj. 1): Controlling obj.
1 is needed to successfully achieve Airspace 1 (obj. 2) but also increases the
likelihood of successfully seizing objectives 5,6,7,10,11,15,16,19, and 20.

Figure 7 illustrates the axis structure for the 22-objective
($|\mathcal{O}|=22$), five-axis ($|\mathcal{X}|=5$) campaign. There are three
commanders for each player: $|\mathcal{C}^{1}|=|\mathcal{C}^{2}|=3$, where
$|\mathcal{X}_{1}|=1$, $|\mathcal{X}_{2}|=2$, and $|\mathcal{X}_{3}|=2$. To
represent the interconnected nature of warfare, axes are connected
probabilistically. For instance, controlling an airspace objective will make
it more likely to succeed during an attack on a subset of ground axis
objectives. Controlling both air objectives indicates air superiority and will
allow close air support (CAS), enabling higher likelihood of ground attack
success. Similarly, controlling certain naval objectives will enable ground
operations to succeed with higher probability. Controlling seaports and
airports allows a player to generate more naval power or air power, which is
reflected by higher probability of succeeding for actions in the naval and air
axis respectively. Controlling the canal on ground allows naval forces to move
between oceans, as reflected by increased likelihood of naval operational
success. Similarly, controlling the mountain pass increases the likelihood of
ground operational success on both axes. In Figure 8 we provide the objective
losses and highlight one campaign effect for each objective.

Figure 7: Campaign axes and commanders Figure 8: Campaign objectives

###  5.2 Base Attack and Reinforce Success Probabilities

In Section 3, we described the transition probability function $P$ of the
stochastic game $\Gamma$ with respect to the base attack and reinforce success
probabilities $\alpha^{i}_{o,s}$ and $\rho^{i}_{o,s}$ (for
$(i,o,s)\in\\{1,2\\}\times\mathcal{O}\times\mathcal{S}$). Determining these
probabilities requires soliciting input from military domain experts that
could include wargamers, operational planners, and weapon system experts. In
this case study, the base attack success probability $\alpha^{i}_{o,s}$ for
Player $i$ on objective $o$ at a given state $s$ is calculated from two sets
of inputs: an initial attack success probability $q^{i}_{o}$, and improvement
probabilities $q^{i}_{o,O^{\prime}}$ for $O^{\prime}\subset\mathcal{O}$.
Specifically, $q^{i}_{o,O^{\prime}}$ reduces the probability of the attack on
$o$ failing when Player $i$ controls the set of objectives $O^{\prime}$. We
construct the state-dependent base attack success probabilities as follows:

$\displaystyle\forall\;i\in\\{1,2\\},\ \forall\;o\in\mathcal{O},\
\forall\;s\in\mathcal{S},\ \alpha^{i}_{o,s}=1-\left[(1-q^{i}_{o})\cdot\hskip
14.22636pt\prod_{\mathclap{\\{O^{\prime}\subset\mathcal{O}\,|\,s_{o^{\prime}}=i,\,\forall\;o^{\prime}\in
O^{\prime}\\}}}\hskip 14.22636pt(1-q^{i}_{o,O^{\prime}})\right].$ (10)

The reinforce success probabilities are analogously constructed, and ensure
that Assumptions 3 and 3.2 are satisfied. In practice, each base attack and
reinforce success probability is affected by a small number of subsets of
objectives $O^{\prime}$.

We now illustrate the construction of Player 1’s base attack success
probability for NE Terrain (obj. 9) given a state
$s=(1,1,2,2,1,1,1,1,2,1,1,1,2,2,1,1,1,2,1,1,1,2)$, which corresponds to Player
1 controlling objectives $\\{1,2,5,6,7,8,10,11,12,15,16,17,19,20,21\\}$. The
base attack success probability on objective 9 is given by $q^{1}_{9}=0.20$
and positive improvements due to the control of single objectives are given by
$q^{1}_{9,\\{12\\}}=0.20$ and $q^{1}_{9,\\{17\\}}=0.10$. These probabilities
reflect that the coalition could take NE Terrain (obj. 9) with an initial
probability of $0.20$; the control of Mountain Pass South (obj. 12) closes the
gap by $0.20$ and the control of Northern Waters (obj. 17) closes the gap by
$0.10$ due to naval fire support. We also consider the following boosts due to
the control of multiple objectives: $q^{1}_{9,\\{8,11,12\\}}=0.15$ and
$q^{1}_{9,\\{7,11,16,20\\}}=0.05$. These probabilities reflect the auxiliary
force flow into NE Terrain when Player 1 controls the Mountain Pass (objs. 8
and 12 along with obj. 11 to ensure the Southern LoC is open to the pass) and
the Canal (objs. 7, 11, 16, 20). Given these five inputs, Player 1’s resulting
base attack success probability on objective 9 given this state $s$ is
$\alpha^{1}_{s,9}=1-(1-0.20)(1-0.20)(1-0.10)(1-0.15)(1-0.05)=0.535$. This
provides the probability of Player 1 controlling objective 9 in the subsequent
state if Player 1 attacks objective 9 and Player 2 does _not_ reinforce it.

###  5.3 Campaign Scenarios

In this case study, we investigate and compare four campaign instances that
differ in their initial states and transition probabilities. Specifically, we
consider two initial campaign states, which are illustrated in Figure 9. We
assume Adversary will control a subset of objectives at the campaign outset,
so the initial state represents the campaign after their initial assault. In
the first initial state, $s^{1}$, Adversary controls 10 of the 22 objectives
at the campaign outset, while in the second initial state, $s^{2}$, Adversary
controls 7 objectives.

(a) Initial state $s^{1}$

(b) Initial state $s^{2}$

Figure 9: Campaign initial states. Objectives controlled by the coalition
(resp. Adversary) are in blue (resp. red).

Additionally, we assess a binary strategic decision: whether to invest in
Isthia or not. We suppose the coalition has the possibility to invest in a 5th
generation _aircraft squadron_ and military training for Isthia’s ground
forces. The aircraft squadron decreases the probability of failure while
attacking air objectives 2 and 3 by 10%. The second component of the
investment is a partnership program, which is an ongoing activity to train the
Isthia infantry to defend their country. We suppose this will reduce
Adversary’s base attack success probabilities on objectives 8, 9, 12, and 13
by 20%. This reflects the ability of the trained Isthia infantry to defend a
subset of objectives without a commander giving a reinforce order.

###  5.4 Impact of Initial State and Strategic Investment

Given the two different initial states $s^{1}$ and $s^{2}$ and the binary
strategic decision, we analyze four campaign scenarios. We solve each scenario
using AVI, assuming a discount factor equal to $\gamma=0.9$ between each
stage, and an optimality gap given by $\epsilon=0.001$. For the sake of
comparison, we also compute the optimal value of the game for the initial
state $s^{A}$ (resp. $s^{I}$) where Adversary (resp. Isthia) controls all
objectives. We present the corresponding optimal game values in Table 1.

Table 1: Optimal game values for different initial states and investment decisions | Initial state
---|---
| $s^{A}$ | $s^{1}$ | $s^{2}$ | $s^{I}$
Without investment | 59.22 | 21.92 | 11.48 | 3.75
With investment | 59.04 | 19.99 |  19.75 | 3.30

The first interesting observation is the wide differential in total expected
loss across the initial states. Indeed, we find that without coalition
investment, $V^{*}(s^{1})-V^{*}(s^{2})=10.44$, which is significantly larger
than the loss of objectives initially controlled by Adversary in $s^{1}$ but
controlled by Isthia in $s^{2}$. Indeed, since Adversary controls more
objectives in $s^{1}$ than in $s^{2}$, then $s^{2}\preceq s^{1}$ and Theorem
4.1 guarantees that
$V^{*}(s^{1})-V^{*}(s^{2})\geq\ell_{8}+\ell_{17}+\ell_{21}=0.8$. This shows
that controlling more objectives at the campaign outset provides more value
beyond the immediate reward (i.e., stage loss). This phenomenon is also
exacerbated when comparing the two extremes, in which Adversary (resp. Isthia)
initially controls all objectives in $s^{A}$ (resp. $s^{I}$).

Second, we find that the a priori strategic investment has a noticeable effect
on the campaign, which varies with the initial state: The investment results
in an 8.8% (resp. 15.1%) reduction in optimal game value for state $s^{1}$
(resp. state $s^{2}$). The investment benefits the coalition from initial
state $s^{2}$ more since Adversary is further inhibited from successfully
attacking Mountain Pass North (obj. 8). This shows the importance of properly
timing an investment, as it will be more valuable for Isthia before Adversary
controls too many objectives.

Next, for each scenario, we examine the players’ mixed strategies at the
initial state in the $\epsilon$-MPE obtained from the AVI algorithm. Tables 2
and 3 respectively compare Players 1 and 2’s mixed strategies at state $s^{1}$
with and without investment.

Table 2: Player 1’s mixed strategy $\pi^{1}(s^{1})$ in an $\epsilon$-MPE with $\epsilon=0.001$ Action $a^{1}$ | Probability $\pi^{1}(s^{1},a^{1})$
---|---
Commander 1 | Commander 2 | Commander 3 | Without investment | With investment
atk 3 |  atk 18 |  atk 21 | 0.986 | 0.876
atk 3 |  rfc 12 |  atk 21 | 0.014 | 0.014
atk 3 |  rfc 17 |  atk 17 | 0.014 | 0.124
Table 3: Player 2’s mixed strategy $\pi^{2}(s^{1})$ in an $\epsilon$-MPE with $\epsilon=0.001$ Action $a^{2}$ | Probability $\pi^{2}(s^{1},a^{2})$
---|---
Commander 1 | Commander 2 | Commander 3 | Without investment | With investment
rfc 3 |  atk 17 |  atk 16 | 0.094 | 0.977
rfc 3 |  atk 12 |  atk 16 | 0.906 | 0.023

We observe that whether the coalition invests or not, their air commander
should always attack Airspace 2 (obj. 3) to attempt to gain air superiority,
while Adversary reinforces that objective to thwart the coalition’s attack.
Furthermore, when there is no investment, the coalition should always attack
South Waters (obj. 21). They are also interested in controlling the mountain
pass to ensure free flow of supplies between the axes, which is why their
ground commander attacks Mountain Pass North (obj. 8) 98.6% of the time and
reinforces Mountain Pass South (obj. 12) 1.4% of the time (to reduce the
likelihood of losing that objective to Adversary). In contrast, Adversary
always attacks Littoral North - Canal Access (obj. 16), as they aim to provide
naval fire support to their Northern ground forces. While waiting for naval
support, Adversary’s ground commander focuses their attack on Mountain Pass
South (obj. 12) 90.6% of the time, and only attacks Canal North (obj. 7) 9.4%
of the time.

However, the dynamics change when the coalition invests in an air squadron and
training for Isthia ground forces. In particular, Isthia ground forces are now
better trained to protect _Mountain Pass South_ (obj. 12), although the
investment does not equip them to better protect _Canal North_ (obj. 7). As a
result, Adversary’s incentive is to refocus their ground effort, and instead
attack _Mountain Pass South_ 2.3% of the time, while attacking _Canal North_
97.7% of the time.

This has further consequences on Player 1’s mixed strategy. Instead of
reinforcing _Mountain Pass South_ (obj. 12) with some probability, their
ground commander reinforces _Canal North_ (obj. 7) 12.4% of the time.
Interestingly, Player 1 coordinates their maritime and ground commanders, so
that when the ground commander reinforces _Canal North_ , the maritime
commander attacks _Northern Waters_ (obj. 17). This is primarily due to the
interdependencies in the success probabilities between axes: While Player 1
maintains control of the whole _Canal_ (objs. 7, 11, 16, 20), the maritime
commander receives more support to attack _Northern Waters_. Hence, the
investment both obviates the need to reinforce _Mountain Pass South_ due to
the organic capabilities of the Isthian forces and introduces a new action
which aligns the ground order to reinforce _Canal North_ with the naval order
to attack Northern Waters.

Now we present in Tables 4 and 5 the players’ mixed strategies at the initial
state $s^{2}$. While most insights are analogous to those for state $s^{1}$,
we interestingly observe that at state $s^{2}$, Adversary always attacks
_Airspace 1_ (obj. 2). Indeed, Adversary intended to maintain air parity at
state $s^{1}$, and they are now interested in gaining air superiority at state
$s^{2}$. This would provide them with air support to gain control of ground
and maritime objectives, as more objectives are controlled by the coalition at
$s^{2}$.

Table 4: Player 1’s mixed strategy $\pi^{1}(s^{2})$ in an $\epsilon$-MPE with $\epsilon=0.001$ Action $a^{1}$ | Probability $\pi^{1}(s^{2},a^{1})$
---|---
Commander 1 | Commander 2 | Commander 3 | Without investment | With investment
atk 3 |  atk 9 |  atk 22 | 0.677 | 0.681
atk 3 |  atk 9 |  rfc 17 | 0.239 | 0.319
atk 3 |  rfc 8 |  rfc 17 | 0.084 | 0.111
Table 5: Player 2’s mixed strategy $\pi^{2}(s^{2})$ in an $\epsilon$-MPE with $\epsilon=0.001$ Action $a^{2}$ | Probability $\pi^{2}(s^{(0)}=2,a^{2})$
---|---
Commander 1 | Commander 2 | Commander 3 | Without investment | With investment
atk 2 |  atk 18 |  atk 17 | 0.552 | 0.561
atk 2 |  atk 18 |  atk 21 | 0.424 | 0.439
atk 2 |  atk 12 |  atk 21 | 0.024 | 0.111

We note that although Adversary desperately aims to gain control of _Mountain
Pass North_ (obj. 8), Isthia barely reinforces this objective (or does not
reinforce it at all with the coalition investment). This is primarily due to
the support provided by the larger number of objectives in other axes
controlled by the coalition, which impacts the game dynamics via two aspects.
First, the coalition forces can defend reasonably well this objective without
a reinforce order. Second, if the front is swapped—i.e., _NE Terrain_ (obj. 9)
is gained by the coalition and _Mountain Pass North_ is gained by
Adversary—then the coalition is likely to regain control of _Mountain Pass
North_ , while maintaining control of _NE Terrain_ in the next turn. Finally,
it is interesting to note that while Adversary aims to attack each Maritime
front with similar probabilities, the coalition seeks to attack _Adversary
Seaport South_ and fully control axis 5 or reinforce _Northern Waters_ and
maintain the current disposition of axis 4.

A major takeaway from this analysis is that at each state in equilibrium, the
mixed strategy for each player is extremely complex, as it depends on the
state itself (i.e., who controls which objectives), the probabilistic
interdependencies between axes, and the dynamics of the game (i.e., future
states and actions). Furthermore, our examples demonstrate the need to
carefully coordinate orders across commanders in order to achieve an
equilibrium. Finally, we find that strategic investment decisions can
significantly impact operational-level decision making for both players, and
must be precisely analyzed.

###  5.5 Computational Performance

Finally, we compare the performance of the solution algorithms described in
Section 4 on the case study campaign (with 22 objectives, illustrated in
Figure 7) along with four other campaigns comprising 6, 10, 14, and 18
objectives, which are summarized in Table 6.

Table 6: Campaigns # objectives $|\mathcal{O}|$ | # commanders $|\mathcal{C}|$ | # axes $|\mathcal{X}|$
---|---|---
16 | 1 | 2
10 | 2 | 3
14 | 3 | 4
18 | 3 | 4
22 | 3 | 5

For each campaign, we consider two data models. In the first model, we
consider the entire original state space $\\{1,2\\}^{\mathcal{O}}$ and action
spaces given by (1)-(2). In the second model, we consider the reduced state
and actions spaces given by (4) and (5)-(6), as a consequence of Theorem 4.1
and Proposition 4.2. Then, for each campaign and each data model, we run the
VI and AVI algorithms with $\gamma=0.9$ and $\epsilon=0.001$. Table 7 presents
the results.

Table 7: Computational performance comparison

Data | Campaign | # states | Max # actions | Runtime [s] | # iterations
---|---|---|---|---|---
model | per state and player | VI | AVI | VI & AVI
$\begin{array}[]{c}\text{Original}\\\ \text{state and action}\\\ \text{spaces}\end{array}$ |  26 obj. |  4,194,364 |  436 |  20,012.5 |  8,001.1 |  196
10 obj. |  4,191,024 |  416 |  41,048.4 |  8,074.4 | 102
14 obj. |  4,116,384 |  472 | – | – | –
18 obj. |  4,262,144 | 160 | – | – | –
22 obj. | 4,194,304 | 320 | – | – | –
$\begin{array}[]{c}\text{Reduced}\\\ \text{state and action}\\\ \text{spaces}\end{array}$ |  26 obj |  4,194,364 |  434 |  20,002.8 |  8,000.5 |  196
10 obj |  4,194,256 |  438 |  20,030.3 |  8,007.1 | 102
14 obj. |  4,192,304 |  416 |  20,295.0 |  8,085.7 |  161
18 obj. |  4,196,400 |  416 |  21,391.2 |  8,397.0 | 102
22 obj. |  4,151,200 |  432 | 21,310.2 | 8,654.3 |  164

– : Runs out of memory

We first observe that the stochastic game $\Gamma$ with its original state and
action spaces can only be solved for very small instances. For the larger
campaigns, the computational challenge arises from the transition model $P$
exceeding the available memory and from having to iterate through the
$2^{|\mathcal{O}|}$ states.

On the other hand, Table 7 shows significant computational improvements when
solving $\Gamma$ with its reduced state and action spaces. Indeed, thanks to
the LoC and command structure, we were able to reduce the state space of the
largest two instances by 97.5% and 98.8%, respectively. Furthermore, by
showing isotonicity of the optimal value function (Theorem 4.1) and properties
of MPEs (Proposition 4.2), we were able to further reduce the action space of
each player (and at each state) by 90% for these two instances. As a result,
we find that the VI algorithm converges for all campaign instances.

Finally, our AVI algorithm empirically shows the value of reducing the number
and/or size of linear programs to solve for this problem (as hinted by
Proposition 4.3). Even though it requires the same number of iterations as the
classical VI algorithm, it completes each iteration faster, as it is often
able to efficiently find pure equilibria of the matrix game, and is able to
remove weakly dominated actions before solving the linear program. On average
across all reduced state and action space campaigns, the AVI algorithm
requires 28% of the time (8% of the time for the original state and action
spaces) to converge compared to the classical VI algorithm. This numerical
analysis demonstrates the computational value of leveraging the problem’s
structure and deriving equilibrium properties of the stochastic game $\Gamma$.

##  6 Conclusion

In this work, we studied what we believe is the first stochastic game model of
a military campaign, extending the single-battle, single-stage matrix game
model of Haywood, (1954). We formulated a two-person discounted zero-sum
stochastic game played by military forces over an infinite horizon. At each
stage, each player orders each of their commanders to attack or reinforce an
objective, which they can only execute if they have an open line of control
from their base to that objective. When a battle occurs between the players,
its outcome is stochastic and depends on the selected actions as well as the
control of other objectives, accounting for the fire support between a
player’s forces. Each player aims to maximize the accumulated number of
objectives they control, weighted by their criticality.

To solve this large-scale stochastic game and compute its Markov perfect
equilibria, we first derived equilibrium properties of the game by leveraging
its logistics and military operational command and control structure. In
particular, we showed the nontrivial isotonicity of the optimal value function
with respect to the partially ordered state space. This lead to a significant
reduction of the state and action spaces, which in turn lead to the
applicability of Shapley’s value iteration algorithm. We further showed that
the matrix game solved at each iteration of this algorithm admitted additional
equilibrium properties, which we leveraged in our proposed accelerated value
iteration that searches for pure equilibria or eliminates weakly dominated
actions before solving the matrix game.

We then designed a case study with representative campaign instances to test
our solution approach and derive new military insights enabled by the features
of our stochastic game. Our analysis highlighted a complex interplay between
the criticalities of the objectives, the probabilistic interdepedencies
between objectives, and the dynamics of the game, leading to carefully
designed equilibrium mixed strategies at every state. We also showed that
strategic investment decisions can have a varied impact on operational-level
decisions and performance, depending on the campaign outset, suggesting a
careful timing of such investment decisions. Finally, our numerical analysis
demonstrated the value of our equilibrium results in permitting us to
efficiently solve the game with our accelerated value iteration algorithm for
characteristic campaign instances that can be exploited by military decision
makers.

A natural extension of this work is to consider a geopolitical setting
involving multiple adversaries, with possible heterogeneous discount factors
to model differing player military sizes or importance of concluding the
conflict. It would also be worthwhile to integrate strategic-level investment
with operational-level planning, as motivated in our case study. Many
countries must determine how to allocate resources between different forces
located at different theaters, in anticipation of a conflict (HQDA 2019). Such
extensions will lead to even larger and more complex games, requiring the
development of faster approximation algorithms and heuristics, possibly using
techniques from reinforcement learning.

## References

  * Bachmann et al., (2011) Bachmann, Darren J., Evans, Robin J., & Moran, Bill. 2011.  Game theoretic analysis of adaptive radar jamming.  IEEE Transactions on Aerospace and Electronic Systems, 47(2).
  * Bier et al., (2007) Bier, Vicki, Oliveros, Santiago, & Samuelson, Larry. 2007.  Choosing what to protect: Strategic defensive allocation against an unknown attacker.  Journal of Public Economic Theory, 9(4).
  * Bogdanovic et al., (2018) Bogdanovic, Nikola, Driessen, Hans, & Yarovoy, Alexander G. 2018.  Target Selection for Tracking in Multifunction Radar Networks: Nash and Correlated Equilibria.  IEEE Transactions on Aerospace and Electronic Systems, 54(5).
  * Burns et al., (2015) Burns, Shawn, DellaVolpe, David, Babb, Robin, Miller, Nick, & Muir, Gordon. 2015\.  War Gamers Handbook: A Guide for Professional War Gamers.  Newport, R.I., USA: U.S. Naval War College.
  * Cantwell, (2003) Cantwell, Gregory L. 2003.  Can Two Person Zero Sum Game Theory Improve Military Decision-Making Course of Action Selection.  School of Advanced Military Studies, Fort Leavenworth Kansas.
  * Chang et al., (2022) Chang, Yanling, Keblis, Matthew F., Li, Ran, Iakovou, Eleftherios, & III, Chelsea C. White. 2022.  Misinformation and Disinformation in Modern Warfare.  Operations Research, 70(3).
  * Chowdhury et al., (2013) Chowdhury, Subhasish M., Kovenock, Dan, & Sheremeta, Roman M. 2013.  An experimental investigation of Colonel Blotto games.  Economic Theory, 52(3).
  * Coughlin, (1992) Coughlin, P. J. 1992.  Pure strategy equilibria in a class of systems defense games.  International Journal of Game Theory, 20(3).
  * Deligiannis et al., (2017) Deligiannis, Anastasios, Panoui, Anastasia, Lambotharan, Sangarapillai, & Chambers, Jonathon A. 2017.  Game-Theoretic Power Allocation and the Nash Equilibrium Analysis for a Multistatic MIMO Radar Network.  IEEE Transactions on Signal Processing, 65(24).
  * Deng et al., (2022) Deng, Xiaotie, Li, Ningyuan, Mguni, David, Wang, Jun, & Yang, Yaodong. 2022.  On the complexity of computing Markov perfect equilibrium in general-sum stochastic games.  National Science Review, 10(1).
  * Flanagan et al., (2019) Flanagan, Stephen, Osburg, Jan, Binnendijk, Anika, Kepe, Marta, & Radin, Andrew. 2019.  Deterring Russian Agression in the Baltic States Through Resilience and Resistance.  Tech. rept. RAND Corporation.
  * Fox, (2016) Fox, William P. 2016.  Applied Game Theory to Improve Strategic and Tactical Military Decisions.  Journal of Defense Management, 6(2).
  * Garamone, (2022) Garamone, Jim. 2022.  Potential for Great Power Conflict ’Increasing,’ Milley Says.  https://www.defense.gov/News/News-Stories/Article/Article/2989958/potential-for-great-power-conflict-increasing-milley-says/.
  * Giles, (2013) Giles, Lionel. 2013.  Sun Tzu On The Art Of War.  Routledge.
  * Gu, (2011) Gu, Dongbing. 2011.  A game theory approach to target tracking in sensor networks.  IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, 41(1).
  * Haywood, (1954) Haywood, O. G. 1954.  Military Decision and Game Theory.  Journal of the Operations Research Society of America, 2(4), 365–385.
  * He et al., (2021) He, Bin, Su, Hongtao, & Huang, Junsheng. 2021.  Joint beamforming and power allocation between a multistatic MIMO radar network and multiple targets using game theoretic analysis.  Digital Signal Processing: A Review Journal, 115.
  * Headquarters, Department of the Army, (2016) Headquarters, Department of the Army. 2016.  Field Manual 6-0.
  * Headquarters, Department of the Army, (2019) Headquarters, Department of the Army. 2019.  Army Regulation 71-32: Force Development and Documentation.  https://armypubs.army.mil/ProductMaps/PubForm/Details.aspx?PUB_ID=1005524.
  * Headquarters, Department of the Army, (2021) Headquarters, Department of the Army. 2021.  Chief of Staff Paper#2: The Army in Military Competition.
  * Ho et al., (2022) Ho, Edwin, Rajagopalan, Arvind, Skvortsov, Alex, Arulampalam, Sanjeev, & Piraveenan, Mahendra. 2022.  Game Theory in Defence Applications: A Review.  Sensors, 22(3).
  * Hoffman & Karp, (1966) Hoffman, A. J., & Karp, R. M. 1966.  On Nonterminating Stochastic Games.  Journal of Management Science, 12(5), 359–370.
  * Joint Chiefs of Staff, (2016) Joint Chiefs of Staff. 2016.  Joint Publication 1-02: Department of Defense Dictionary of Military and Associated Terms.  https://apps.dtic.mil/sti/pdfs/AD1024397.pdf.
  * Joint Chiefs of Staff, (2017) Joint Chiefs of Staff. 2017.  Joint Publication 3-0: Joint Operations.  https://www.jcs.mil/Doctrine/Joint-Doctine-Pubs.
  * Joint Chiefs of Staff, (2020) Joint Chiefs of Staff. 2020.  Joint Publication 5-0: Joint Planning.  https://www.jcs.mil/Doctrine/Joint-Doctrine-Pubs/5-0-Planning-Series/.
  * Kaminsky et al., (1984) Kaminsky, K. S., Luks, E. M., & Nelson, P. I. 1984.  Strategy, Nontransitive Dominance and the Exponential Distribution.  Australian Journal of Statistics, 26(2), 111–118.
  * Kharlamov, (2022) Kharlamov, V. V. 2022.  On Asymptotic Strategies in the Stochastic Colonel Blotto Game.  Theory of Probability & Its Applications, 67(2), 318–326.
  * Kovenock & Roberson, (2021) Kovenock, Dan, & Roberson, Brian. 2021.  Generalizations of the General Lotto and Colonel Blotto games.  Economic Theory, 71(3).
  * Krishnamurthy et al., (2008) Krishnamurthy, Vikram, Maskery, Michael, & Yin, George. 2008.  Decentralized adaptive filtering algorithms for sensor activation in an unattended ground sensor network.  IEEE Transactions on Signal Processing, 56(12).
  * Leslie et al., (2020) Leslie, David S., Perkins, Steven, & Xu, Zibo. 2020.  Best-response dynamics in zero-sum stochastic games.  Journal of Economic Theory, 189.
  * Lynes et al., (2014) Lynes, Jerome M., West, Jerry, & Katsos, George. 2014.  Campaigning Perspectives Through the Lens of Joint Doctrine and Education.  Campaigning: The Journal of the Joint Forces Staff College, Spring 2014.
  * Mazarr et al., (2019) Mazarr, Michael, Best, Katharina, Laird, Burgess, Larson, Eric, Linick, Michael, & Madden, Dan. 2019.  The U.S. Department of Defense’s Planning Process: Components and Challenges.  Tech. rept. RAND Corporation.
  * McEneaney et al., (2004) McEneaney, William M., Fitzpatrick, Ben G., & Lauko, Istvan G. 2004.  Stochastic game approach to air operations.  IEEE Transactions on Aerospace and Electronic Systems, 40(4).
  * Mueller, (2016) Mueller, Karl P. 2016.  Paper wargames and policy making: Filling the Baltic gap or how I learned to stop worrying and love the D6.  Battles Magazine, 2016(11), 53–57.
  * Pollatschek & Avi-Itzhak, (1969) Pollatschek, M. A., & Avi-Itzhak, B. 1969.  Algorithms for Stochastic Games with Geometrical Interpretation.  Journal of Management Science, 15(7), 399–415.
  * Pruitt, (2019) Pruitt, Sarah. 2019.  The Allies Hoped Operation Market Garden Would End WWII. Here’s What Went Wrong.  https://www.history.com/news/operation-market-garden-failure-allies.
  * Puterman, (2005) Puterman, Martin L. 2005.  Markov Decision Processes: Discrete Stochastic Dynamic Programming.  John Wiley and Sons Inc.
  * Raghavan & Filar, (1991) Raghavan, T.E.S., & Filar, J.A. 1991.  Algorithms for stochastic games - A survey.  ZOR Zeitschrift für Operations Research Methods and Models of Operations Research, 35(6), 437–472.
  * Shane et al., (2020) Shane, Hall N., Wade, Brian M., & Thengvall, Benjamin G. 2020.  Simulation Optimization.  Pages 219–244 of: Scala, Natalie M., & Howard, James P. III (eds), Handbook of Military and Defense Operations Research.  Boca Raton, FL, USA: Taylor & Francis Group.
  * Shapley, (1953) Shapley, L. S. 1953.  Stochastic Games.  Proceedings of the National Academy of Sciences, 39(10).
  * Shlapak & Johnson, (2016) Shlapak, David, & Johnson, Michael. 2016.  Reinforcing Deterrence on NATO’s Eastern Flank: Wargaming the Defense of the Baltics.  Tech. rept. RAND Corporation.
  * Shubik & Weber, (1981) Shubik, Martin, & Weber, Robert James. 1981.  Systems Defense Games: Colonel Blotto, Command and Control.  Naval Research Logistics Quarterly, 28(2).
  * Sweetser & Bexfield, (2020) Sweetser, Al, & Bexfield, Jim. 2020.  Lessons from the MORS Workshop on Advancing Campaign Analytics: Challenges in Modeling Cyber Warfare, Artificial Intelligence, and Command and Control.  Phalanx, 53(1), 42–48.
  * Tecott & Halterman, (2021) Tecott, Rachel, & Halterman, Andrew. 2021.  The case for campaign analysis: A method for studying military operations.  International Security, 45(4).
  * Turnitsa et al., (2022) Turnitsa, Charles, Blais, Curtis, & Tolk, Andreas. 2022.  Simulatation and Wargaming.  Newark, NJ, USA: John Wiley & Sons Inc.
  * Van der Wal, (1978) Van der Wal, J. 1978.  Discounted Markov games: Generalized policy iteration method.  Journal of Optimization Theory and Applications, 25(1), 11–22.
  * von Neumann, (1928) von Neumann, John. 1928.  Zur Theorie der Gesellschaftsspiele.  Math. Ann., 100(1).
  * Vrieze & Tijs, (1982) Vrieze, O. J., & Tijs, S. H. 1982.  Fictitious play applied to sequences of games and discounted stochastic games.  International Journal of Game Theory, 11(2).
  * Washburn, (2014) Washburn, Alan. 2014.  Two-Person Zero-Sum Games. 4th edn.  New York, NY: Springer U.S.

##  7 Proofs of Statements

###### Proof 7.1

Proof of Theorem 4.1. Consider the sequence of functions
$(V^{(t)})_{t\in\mathbb{Z}_{\geq 0}}$ given by $V^{(0)}(s)=L(s)$ for every
$s\in\mathcal{S}$ and $V^{(t+1)}=T(V^{(t)})$ for every $t\in\mathbb{Z}_{\geq
0}$. We show by induction that:

$\displaystyle\forall\;t\in\mathbb{Z}_{\geq 0},\ \forall\;s\preceq
s^{\prime}\in\mathcal{S},\
V^{(t)}(s^{\prime})-V^{(t)}(s)\geq\sum_{o\in\mathcal{O}}\ell_{o}\cdot\mathds{1}_{\\{s_{o}^{\prime}=2\text{
and }s_{o}=1\\}}.$ (11)

By definition of the stage loss function,

$\displaystyle\forall\;s\preceq s^{\prime}\in\mathcal{S},\ \
V^{(0)}(s^{\prime})-V^{(0)}(s)=\sum_{o\in\mathcal{O}}\ell_{o}\cdot\mathds{1}_{\\{s_{o}^{\prime}=2\\}}-\sum_{o\in\mathcal{O}}\ell_{o}\cdot\mathds{1}_{\\{s_{o}=2\\}}=\sum_{o\in\mathcal{O}}\ell_{o}\cdot\mathds{1}_{\\{s_{o}^{\prime}=2\text{
and }s_{o}=1\\}}.$ (12)

We now assume that (11) holds for a given $t\in\mathbb{Z}_{\geq 0}$. We also
consider two states $s^{-}\preceq s^{+}\in\mathcal{S}$ that only differ in one
given objective $o^{\dagger}\in\mathcal{O}$, i.e., $s^{-}_{o^{\dagger}}=1$,
$s^{+}_{o^{\dagger}}=2$, and $s^{-}_{o}=s^{+}_{o}$ for every
$o\in\mathcal{O}\setminus\\{o^{\dagger}\\}$.

We define the mapping
$\phi:\\{\textit{atk,rfc,none}\\}^{\mathcal{O}}\to\\{\textit{atk,rfc,none}\\}^{\mathcal{O}}$
that satisfies

$\displaystyle\forall\;a\in\\{\textit{atk,rfc,none}\\}^{\mathcal{O}},\
\forall\;o\in\mathcal{O},\ \phi(a)_{o}=\begin{cases}\textit{rfc}&\text{ if
}o=o^{\dagger}\text{ and }a_{o}=\textit{atk}\\\ a_{o}&\text{
otherwise}.\end{cases}$

We note that for every action $a^{1}\in\mathcal{A}^{1}_{s^{+}}$,
$\phi(a^{1})\in\mathcal{A}^{1}_{s^{-}}$. Similarly, for every
$a^{2}\in\mathcal{A}^{2}_{s^{-}}$, $\phi(a^{2})\in\mathcal{A}^{2}_{s^{+}}$. We
next show that

$\displaystyle\forall\;a^{1}\in\mathcal{A}^{1}_{s^{+}},\
\forall\;a^{2}\in\mathcal{A}^{2}_{s^{-}},\ \mathbb{E}_{s^{\prime}\sim
P(\cdot\,|\,s^{-},\phi(a^{1}),a^{2})}[V^{(t)}(s^{\prime})]\leq\mathbb{E}_{s^{\prime}\sim
P(\cdot\,|\,s^{+},a^{1},\phi(a^{2}))}[V^{(t)}(s^{\prime})].$

Let $a^{1}\in\mathcal{A}^{1}_{s^{+}}$, $a^{2}\in\mathcal{A}^{2}_{s^{-}}$, and
$o\in\mathcal{O}$. If $o\neq o^{\dagger}$, then we know that
$s_{o}^{-}=s_{o}^{+}$, $\phi(a^{1})_{o}=a^{1}_{o}$ and
$\phi(a^{2})_{o}=a^{2}_{o}$. Then, by Assumption 3,
$\alpha_{o,s^{-}}^{2}\leq\alpha_{o,s^{+}}^{2}$,
$\rho_{o,s^{-}}^{1}\geq\rho_{o,s^{+}}^{1}$,
$\alpha_{o,s^{-}}^{1}\geq\alpha_{o,s^{+}}^{1}$, and
$\rho_{o,s^{-}}^{2}\leq\rho_{o,s^{+}}^{2}$, which implies

$\displaystyle p_{o}(1\,|\,s^{-},\phi(a^{1})_{o},a^{2}_{o})$
$\displaystyle=\begin{cases}1-\alpha^{2}_{o,s^{-}}\cdot\mathds{1}_{\\{a^{2}_{o}=\textit{atk}\\}}\cdot(1-\rho^{1}_{o,s^{-}}\cdot\mathds{1}_{\\{\phi(a^{1})_{o}=\textit{rfc}\\}})&\text{if
}s_{o}^{-}=1\\\
\alpha^{1}_{o,s^{-}}\cdot\mathds{1}_{\\{\phi(a^{1})_{o}=\textit{atk}\\}}\cdot(1-\rho^{2}_{o,s^{-}}\cdot\mathds{1}_{\\{a^{2}_{o}=\textit{rfc}\\}})&\text{if
}s_{o}^{-}=2\end{cases}$
$\displaystyle\geq\begin{cases}1-\alpha^{2}_{o,s^{+}}\cdot\mathds{1}_{\\{\phi(a^{2})_{o}=\textit{atk}\\}}\cdot(1-\rho^{1}_{o,s^{+}}\cdot\mathds{1}_{\\{a^{1}_{o}=\textit{rfc}\\}})&\text{if
}s_{o}^{+}=1\\\
\alpha^{1}_{o,s^{+}}\cdot\mathds{1}_{\\{a^{1}_{o}=\textit{atk}\\}}\cdot(1-\rho^{2}_{o,s^{+}}\cdot\mathds{1}_{\\{\phi(a^{2})_{o}=\textit{rfc}\\}})&\text{if
}s_{o}^{+}=2\end{cases}$
$\displaystyle=p_{o}(1\,|\,s^{+},a^{1}_{o},\phi(a^{2})_{o}).$

For the remaining objective $o^{\dagger}$, recall that $s_{o^{\dagger}}^{-}=1$
and $s_{o^{\dagger}}^{+}=2$. If $a^{1}_{o^{\dagger}}\neq\textit{atk}$, then:

$\displaystyle
p_{o^{\dagger}}(1\,|\,s^{-},\phi(a^{1})_{o^{\dagger}},a^{2}_{o^{\dagger}})\geq
0=p_{o^{\dagger}}(1\,|\,s^{+},a^{1}_{o^{\dagger}},\phi(a^{2})_{o^{\dagger}}).$

Similarly, if $a^{2}_{o^{\dagger}}\neq\textit{atk}$, then:

$\displaystyle
p_{o^{\dagger}}(1\,|\,s^{-},\phi(a^{1})_{o^{\dagger}},a^{2}_{o^{\dagger}})=1\geq
p_{o^{\dagger}}(1\,|\,s^{+},a^{1}_{o^{\dagger}},\phi(a^{2})_{o^{\dagger}}).$

Finally, if $a^{1}_{o^{\dagger}}=a^{2}_{o^{\dagger}}=\textit{atk}$, then
$\phi(a^{1})_{o^{\dagger}}=\phi(a^{2})_{o^{\dagger}}=\textit{rfc}$ and
Assumption 3.2 implies

$\displaystyle
p_{o^{\dagger}}(1\,|\,s^{-},\phi(a^{1})_{o^{\dagger}},a^{2}_{o^{\dagger}})=1-\alpha^{2}_{o^{\dagger},s^{-}}\cdot(1-\rho^{1}_{o^{\dagger},s^{-}})\geq\alpha^{1}_{o^{\dagger},s^{+}}\cdot(1-\rho^{2}_{o^{\dagger},s^{+}})=p_{o^{\dagger}}(1\,|\,s^{+},a^{1}_{o^{\dagger}},\phi(a^{2})_{o^{\dagger}}).$

Thus, we obtain that

$\displaystyle\forall\;a^{1}\in\mathcal{A}^{1}_{s^{+}},\
\forall\;a^{2}\in\mathcal{A}^{2}_{s^{-}},\ \forall\;o\in\mathcal{O},\
p_{o}(1\,|\,s^{-},\phi(a^{1})_{o},a^{2}_{o})\geq
p_{o}(1\,|\,s^{+},a^{1}_{o},\phi(a^{2})_{o}),$

which implies that $p_{o}(\cdot\,|\,s^{+},a^{1}_{o},\phi(a^{2})_{o})$ first-
order stochastically dominates
$p_{o}(\cdot\,|\,s^{-},\phi(a^{1})_{o},a^{2}_{o})$. Since $V^{(t)}$ is
isotone, and by construction of the transition probability function, we then
obtain the desired inequality:

$\displaystyle\forall\;a^{1}\in\mathcal{A}^{1}_{s^{+}},\
\forall\;a^{2}\in\mathcal{A}^{2}_{s^{-}},\ \mathbb{E}_{s^{\prime}\sim
P(\cdot\,|\,s^{-},\phi(a^{1}),a^{2})}[V^{(t)}(s^{\prime})]\leq\mathbb{E}_{s^{\prime}\sim
P(\cdot\,|\,s^{+},a^{1},\phi(a^{2}))}[V^{(t)}(s^{\prime})].$

A direct implication is that

$\displaystyle\forall\;a^{1}\in\mathcal{A}^{1}_{s^{+}},\
\forall\;a^{2}\in\mathcal{A}^{2}_{s^{-}},\ $
$\displaystyle\ell_{o^{\dagger}}+R(V^{(t)},s^{-},\phi(a^{1}),a^{2})=L(s^{+})+\gamma\cdot\mathbb{E}_{s^{\prime}\sim
P(\cdot\,|\,s^{-},\phi(a^{1}),a^{2})}[V^{(t)}(s^{\prime})]$ $\displaystyle\leq
L(s^{+})+\gamma\cdot\mathbb{E}_{s^{\prime}\sim
P(\cdot\,|\,s^{+},a^{1},\phi(a^{2}))}[V^{(t)}(s^{\prime})]=R(V^{(t)},s^{+},a^{1},\phi(a^{2})).$

Next, we define

$\displaystyle\pi^{1^{+}}(s^{+})\in\argmin_{\pi^{1}(s^{+})\in\Delta(\mathcal{A}^{1}_{s^{+}})}\max_{a^{2}\in\mathcal{A}^{2}_{s^{+}}}\mathbb{E}_{a^{1}\sim\pi^{1}(s^{+})}[R(V^{(t)},s^{+},a^{1},a^{2})].$

In the final step, we construct
$\pi^{1^{-}}(s^{-})\in\Delta(\mathcal{A}^{1}_{s^{-}})$ defined by
$\pi^{1^{-}}(s^{-},\phi(a^{1}))=\pi^{1^{+}}(s^{+},a^{1})$ for every
$a^{1}\in\mathcal{A}^{1}_{s^{+}}$, which provides the desired result:

$\displaystyle V^{(t+1)}(s^{-})+\ell_{o^{\dagger}}$
$\displaystyle\leq\max_{a^{2}\in\mathcal{A}^{2}_{s^{-}}}\sum_{a^{1}\in\mathcal{A}^{1}_{s^{-}}}\pi^{1^{-}}(s^{-},a^{1})\cdot(\ell_{o^{\dagger}}+R(V^{(t)},s^{-},a^{1},a^{2}))$
$\displaystyle=\max_{a^{2}\in\mathcal{A}^{2}_{s^{-}}}\sum_{a^{1}\in\mathcal{A}^{1}_{s^{+}}}\pi^{1^{-}}(s^{-},\phi(a^{1}))\cdot(\ell_{o^{\dagger}}+R(V^{(t)},s^{-},\phi(a^{1}),a^{2}))$
$\displaystyle=\max_{a^{2}\in\mathcal{A}^{2}_{s^{-}}}\sum_{a^{1}\in\mathcal{A}^{1}_{s^{+}}}\pi^{1^{+}}(s^{+},a^{1})\cdot(\ell_{o^{\dagger}}+R(V^{(t)},s^{-},\phi(a^{1}),a^{2}))$
$\displaystyle\leq\max_{a^{2}\in\mathcal{A}^{2}_{s^{-}}}\sum_{a^{1}\in\mathcal{A}^{1}_{s^{+}}}\pi^{1^{+}}(s^{+},a^{1})\cdot
R(V^{(t)},s^{+},a^{1},\phi(a^{2}))$
$\displaystyle\leq\max_{a^{2}\in\mathcal{A}^{2}_{s^{+}}}\sum_{a^{1}\in\mathcal{A}^{1}_{s^{+}}}\pi^{1^{+}}(s^{+},a^{1})\cdot
R(V^{(t)},s^{+},a^{1},a^{2})$ $\displaystyle=V^{(t+1)}(s^{+}).$

By repeating this process, we deduce that for every $s\preceq
s^{\prime}\in\mathcal{S}$,
$V^{(t+1)}(s^{\prime})-V^{(t+1)}(s)\geq\sum_{o\in\mathcal{O}}\ell_{o}\cdot\mathds{1}_{\\{s^{\prime}_{o}=2\text{
and }s_{o}=1\\}}$. By induction, we then conclude that:

$\displaystyle\forall\;t\in\mathbb{Z}_{\geq 0},\ \forall\;s\preceq
s^{\prime}\in\mathcal{S},\
V^{(t)}(s^{\prime})-V^{(t)}(s)\geq\sum_{o\in\mathcal{O}}\ell_{o}\cdot\mathds{1}_{\\{s^{\prime}_{o}=2\text{
and }s_{o}=1\\}}.$

Taking the limit as $t$ goes to $+\infty$, we obtain:

$\displaystyle\forall\;s\preceq s^{\prime}\in\mathcal{S},\
V^{*}(s^{\prime})-V^{*}(s)\geq\sum_{o\in\mathcal{O}}\ell_{o}\cdot\mathds{1}_{\\{s^{\prime}_{o}=2\text{
and }s_{o}=1\\}}.$

Thus, the optimal value of the game $\Gamma$ is an isotone function of the
state space.

###### Proof 7.2

Proof of Proposition 4.2.

Property 1: First, we show that under Assumption 4.2, the set of achievable
states for any policy profile is (4). Consider a state $s\in\mathcal{S}$ and
assume that
$\tau_{x,s}\in\\{\textit{c1},\textit{c2},\textit{pf},\textit{sf}\\}$ for every
axis $x\in\mathcal{X}$. Let $a^{1}\in\mathcal{A}^{1}_{s}$ and
$a^{2}\in\mathcal{A}^{2}_{s}$ be the actions drawn from the policies selected
by both players and let $s^{\prime}$ be the subsequent state. Consider an
individual axis $x=(o_{1},\dots,o_{n})$ of size $n\geq 2$ (since the case
$n=1$ is trivial).

  * –

If $\tau_{x,s}=\textit{c1}$ and $a^{2}_{o_{n}}=\textit{atk}$, then two
possible outcomes occur: If the attack succeeds, then $s^{\prime}_{o_{n}}=2$
and $\tau_{x,s^{\prime}}=\textit{pf}$ with the new front occurring at
objectives $o_{n-1}$ and $o_{n}$. If instead the attack fails, then
$s^{\prime}_{o_{n}}=1$ and $\tau_{x,s^{\prime}}=\textit{c1}$.

  * –

If $\tau_{x,s}=\textit{c2}$ and $a^{1}_{o_{1}}=\textit{atk}$, then two
possible outcomes occur: If the attack succeeds, then $s^{\prime}_{o_{1}}=1$
and $\tau_{x,s^{\prime}}=\textit{pf}$. If instead the attack fails, then
$s^{\prime}_{o_{1}}=2$ and $\tau_{x,s^{\prime}}=\textit{c2}$.

  * –

If $\tau_{x,s}=\textit{pf}$ with the front occurring at $\\{o_{k},o_{k+1}\\}$
for some $k\in\llbracket 1,n-1\rrbracket$, $a^{1}_{o_{k+1}}=\textit{atk}$, and
$a^{2}_{o_{k}}\neq\textit{atk}$, then two similar outcomes may occur: If the
attack succeeds, then $\tau_{x,s^{\prime}}=\textit{pf}$ if $k<n-1$ or
$\tau_{x,s^{\prime}}=\textit{c1}$ if $k=n-1$. If the attack fails, then
$\tau_{x,s^{\prime}}=\textit{pf}$. Similar conclusions can be drawn if
$a^{2}_{o_{k}}=\textit{atk}$, and $a^{1}_{o_{k+1}}\neq\textit{atk}$.

  * –

If $\tau_{x,s}=\textit{pf}$ with the front occurring at $\\{o_{k},o_{k+1}\\}$
for some $k\in\llbracket 1,n-1\rrbracket$, $a^{1}_{o_{k+1}}=\textit{atk}$, and
$a^{2}_{o_{k}}=\textit{atk}$, then additional outcomes may occur: If none or
only one of the attacks succeeds, then
$\tau_{x,s^{\prime}}\in\\{\textit{c1},\textit{c2},\textit{pf}\\}$. If both
attacks succeed, then $\tau_{x,s^{\prime}}=\textit{sf}$ with a front for
Player 1 at objective $\widetilde{\mathcal{O}}^{1}_{x,s^{\prime}}=\\{o_{k}\\}$
and another front for Player 2 at objective
$\widetilde{\mathcal{O}}^{2}_{x,s^{\prime}}=\\{o_{k+1}\\}$.

  * –

If $\tau_{x,s}=\textit{sf}$ with a front for Player 1 at
$\widetilde{\mathcal{O}}^{1}_{x,s^{\prime}}=\\{o_{k}\\}$ and another front for
Player 2 at $\widetilde{\mathcal{O}}^{2}_{x,s^{\prime}}=\\{o_{k+1}\\}$ for
some $k\in\llbracket 1,n-1\rrbracket$, then
$a^{1}_{o_{k}}\in\\{\textit{atk},\textit{none}\\}$,
$a^{2}_{o_{k+1}}\in\\{\textit{atk},\textit{none}\\}$, and multiple outcomes
may occur: If one or two attacks are successful, then
$\tau_{x,s^{\prime}}\in\\{\textit{c1},\textit{c2},\textit{pf}\\}$. If no
attack is successful, then $\tau_{x,s^{\prime}}=\textit{sf}$.

  * –

In all other cases, $\tau_{x,s^{\prime}}=\tau_{x,s}$.

Thus, we obtain that
$\tau_{x,s^{\prime}}\in\\{\textit{c1},\textit{c2},\textit{pf},\textit{sf}\\}$
for every $x\in\mathcal{X}$. By induction, we conclude that at each stage of
the campaign, each axis type will belong in
$\\{\textit{c1},\textit{c2},\textit{pf},\textit{sf}\\}$. Henceforth, we assume
that $\mathcal{S}$ is given by (4).

Property 2: Next, we show that in at least one equilibrium of the stochastic
game $\Gamma$, the players randomize at every state over actions satisfying
(5)-(6). Consider a state $s\in\mathcal{S}$, a commander
$c\in\mathcal{C}^{1}$, and let $a^{1^{\dagger}}\in\mathcal{A}^{1}_{s}$ be an
action for Player 1 such that $a^{1^{\dagger}}_{o}=\textit{none}$ for every
$o\in\cup_{x\in\mathcal{X}_{c}}\widetilde{\mathcal{O}}^{1}_{x,s}$. In other
words, the commander $c$ for Player 1 does not reinforce nor attack any
objective at any of the fronts in the axes under their responsibility. This is
either because the commander $c$ reinforces an objective $o^{\dagger}$
belonging to an axis $x^{\dagger}$ that is not at the front (i.e.,
$a^{1^{\dagger}}_{o^{\dagger}}=\textit{rfc}$ with
$o^{\dagger}\in\overline{\mathcal{O}}^{1}_{s}\setminus\widetilde{\mathcal{O}}^{1}_{x^{\dagger},s}$),
or commander $c$ does not attack nor reinforce any objective in that state. In
the latter case, we still consider an arbitrary objective $o^{\dagger}$
belonging to an axis $x^{\dagger}\in\mathcal{X}_{c}$.

Let us assume that there exists an axis $x^{\prime}\in\mathcal{X}_{c}$ such
that $\tau_{x^{\prime},s}\neq\textit{c1}$. Then, there exists
$o^{\prime}\in\widetilde{\mathcal{O}}^{1}_{x^{\prime},s}$ such that
$s_{o^{\prime}}=2$. We next show that attacking $o^{\prime}$ provides a better
or equal value for Player 1 in the zero-sum matrix game $\Gamma(V^{*},s)$
regardless of Player 2’s action. Let $a^{1^{\prime}}$ be defined as follows:

$\displaystyle\forall\;o\in\mathcal{O},\
a^{1^{\prime}}_{o}=\begin{cases}\textit{atk}&\text{if }o=o^{\prime}\\\
\textit{none}&\text{if }o=o^{*}\\\
a^{1^{\dagger}}_{o}&\text{otherwise}.\end{cases}$ (13)

Note that $a^{1^{\prime}}\in\mathcal{A}^{1}_{s}$. Then, for every
$a_{2}\in\mathcal{A}^{2}_{s}$, we obtain the following:

$\displaystyle\forall\;o\in\mathcal{O}\setminus\\{o^{\prime}\\},\ $
$\displaystyle
p_{o}(1\,|\,s,a^{1^{\prime}}_{o},a^{2}_{o})=p_{o}(1\,|\,s,a^{1^{\dagger}}_{o},a^{2}_{o})$
$\displaystyle
p_{o^{\prime}}(1\,|\,s,a^{1^{\prime}}_{o^{\prime}},a^{2}_{o^{\prime}})=\alpha^{1}_{o^{\prime},s}\cdot(1-\rho^{2}_{o^{\prime},s}\cdot\mathds{1}_{\\{a^{2}_{o^{\prime}}=\textit{rfc}\\}})\geq
0=p_{o^{\prime}}(1\,|\,s,a^{1^{\dagger}}_{o^{\prime}},a^{2}_{o^{\prime}}).$
(14)

Since $V^{*}$ is isotone (Theorem 4.1), we deduce that:

$\displaystyle\forall\;a^{2}\in\mathcal{A}^{2}_{s},\
R(V^{*},s,a^{1^{\prime}},a^{2})\leq R(V^{*},s,a^{1^{\dagger}},a^{2}).$ (15)

Thus, if $a^{1^{\dagger}}$ is selected with positive probability in
equilibrium, then we can construct another equilibrium that instead assigns
that probability to $a^{1^{\prime}}$.

Now, let us assume that for every axis $x\in\mathcal{X}_{c}$,
$\tau_{x,c}=\textit{c1}$. Let $x^{\prime}\in\mathcal{X}_{c}$ and
$o^{\prime}\in\widetilde{\mathcal{O}}^{1}_{x^{\prime},s}$. Then, we show that
reinforcing $o^{\prime}$ provides a better or equal objective for Player 1 in
$\Gamma(V^{*},s)$ regardless of Player 2’s action. Let $a^{1^{\prime}}$ be
defined as follows:

$\displaystyle\forall\;o\in\mathcal{O},\
a^{1^{\prime}}_{o}=\begin{cases}\textit{rfc}&\text{if }o=o^{\prime}\\\
\textit{none}&\text{if }o=o^{*}\\\
a^{1^{\dagger}}_{o}&\text{otherwise}.\end{cases}$ (16)

Note that $a^{1^{\prime}}\in\mathcal{A}^{1}_{s}$. Then, for every
$a_{2}\in\mathcal{A}^{2}_{s}$, we obtain the following:

$\displaystyle\forall\;o\in\mathcal{O}\setminus\\{o^{\prime}\\},\
p_{o}(1\,|\,s,a^{1^{\prime}}_{o},a^{2}_{o})=p_{o}(1\,|\,s,a^{1^{\dagger}}_{o},a^{2}_{o}).$
$\displaystyle
p_{o^{\prime}}(1\,|\,s,a^{1^{\prime}}_{o^{\prime}},a^{2}_{o^{\prime}})=1-\alpha^{2}_{o^{\prime},s}\cdot\mathds{1}_{\\{a^{2}_{o^{\prime}}=\textit{atk}\\}}\cdot(1-\rho^{1}_{o^{\prime},s})\geq
1-\alpha^{2}_{o^{\prime},s}\cdot\mathds{1}_{\\{a^{2}_{o^{\prime}}=\textit{atk}\\}}=p_{o^{\prime}}(1\,|\,s,a^{1^{\dagger}}_{o^{\prime}},a^{2}_{o^{\prime}}).$
(17)

Since $V^{*}$ is isotone (Theorem 4.1), we similarly deduce that:

$\displaystyle\forall\;a^{2}\in\mathcal{A}^{2}_{s},\
R(V^{*},s,a^{1^{\prime}},a^{2})\leq R(V^{*},s,a^{1^{\dagger}},a^{2}).$

Thus, if $a^{1^{\dagger}}$ is selected with positive probability in
equilibrium, then we can construct another equilibrium that instead assigns
that probability to $a^{1^{\prime}}$.

A similar proof can be derived to show that there exists an equilibrium policy
for Player 2 such that at every state $s\in\mathcal{S}$, no probability is
assigned to an action $a^{2^{\dagger}}\in\mathcal{A}^{2}_{s}$ satisfying
$a^{2^{\dagger}}_{o}=\textit{none}$ for every objective
$o\in\cup_{x\in\mathcal{X}_{c}}\widetilde{\mathcal{O}}^{2}_{x,s}$ under the
responsibility of some commander $c\in\mathcal{C}^{2}$. Therefore, there
exists an MPE of $\Gamma$ such that at any state $s\in\mathcal{S}$, each
player randomizes over actions that satisfy (5)-(6).

Property 3: Finally, let us show that when the game parameters satisfy
(7)-(9), every action selected with positive probability in equilibrium at any
state satisfies (5)-(6). Let $s\in\mathcal{S}$ and assume that there exists a
commander $c\in\mathcal{C}^{1}$ for Player 1 and an axis
$x^{\prime}\in\mathcal{X}_{c}$ such that $\tau_{x^{\prime},s}\neq\textit{c1}$.
Let $a^{1^{\dagger}}\in\mathcal{A}^{1}_{s}$ be such that
$a^{1^{\dagger}}_{o}=\textit{none}$ for every
$o\in\cup_{x\in\mathcal{X}_{c}}\widetilde{\mathcal{O}}^{1}_{x,s}$ and let
$a^{1^{\prime}}\in\mathcal{A}^{1}_{s}$ defined in (13). Since the game
parameters satisfy (7)-(9), then (14) becomes a strict inequality and $V^{*}$
becomes a strictly isotone function (Theorem 4.1). Thus, (15) also becomes a
strict inequality for every $a^{2}\in\mathcal{A}^{2}_{s}$, and
$a^{1^{\dagger}}$ cannot receive any positive probability in equilibrium.

Similarly, if there exists a commander $c\in\mathcal{C}^{2}$ for Player 2 and
an axis $x^{\prime}\in\mathcal{X}_{c}$ such that
$\tau_{x^{\prime},s}\neq\textit{c2}$, then any
$a^{2^{\dagger}}\in\mathcal{A}^{2}_{s}$ such that
$a^{2^{\dagger}}_{o}=\textit{none}$ for every
$o\in\cup_{x\in\mathcal{X}_{c}}\widetilde{\mathcal{O}}^{2}_{x,s}$ cannot
receive any positive probability in equilibrium.

Next, we consider a state $s\in\mathcal{S}$ and a commander
$c\in\mathcal{C}^{1}$ for Player 1 such that for every axis
$x\in\mathcal{X}_{c}$, $\tau_{x,c}=\textit{c1}$. Let
$x^{\prime}\in\mathcal{X}_{c}$ and
$o^{\prime}\in\widetilde{\mathcal{O}}^{1}_{x^{\prime},s}$ such that
$s_{o^{\prime}}=1$. Consider an MPE
$(\pi^{1^{*}},\pi^{2^{*}})\in\Delta^{1}\times\Delta^{2}$ of $\Gamma$. Since
these axes are not of type c2, the previous argument shows that
$\pi^{2^{*}}(s)$ cannot assign any positive probability to any action
$a^{2}\in\mathcal{A}^{2}_{s}$ such that $a^{2}_{o}=\textit{none}$ for every
$o\in\cup_{x\in\mathcal{X}_{c}}\widetilde{\mathcal{O}}^{2}_{x,s}$. Let
$a^{2^{\prime}}\in\mathcal{A}^{2}_{s}$ be such that
$\pi^{2^{*}}(s,a^{2^{\prime}})>0$. There exists an axis
$x^{\prime}\in\mathcal{X}_{c}$ and an objective
$o^{\prime}\in\widetilde{\mathcal{O}}^{1}_{x^{\prime},s}$ such that
$a^{2^{\prime}}_{o^{\prime}}=\textit{atk}$ (since commander $c$ for Player 2
cannot reinforce any objective under their responsibility when the axes are of
type c1).

Let $a^{1^{\prime}}\in\mathcal{A}^{1}_{s}$ defined in (16). When the game
parameters satisfy (7)-(9), (17) becomes a strict inequality for
$a^{2^{\prime}}$ and $V^{*}$ a strictly isotone function (Theorem 4.1). Since
$\pi^{2^{*}}(s,a^{2^{\prime}})>0$, we deduce that:

$\displaystyle\mathbb{E}_{a^{2}\sim\pi^{2^{*}}(s)}[R(V^{*},s,a^{1^{\prime}},a^{2})]<\mathbb{E}_{a^{2}\sim\pi^{2^{*}}(s)}[R(V^{*},s,a^{1^{\dagger}},a^{2})],$

and $a^{1^{\dagger}}$ cannot receive any positive probability in equilibrium.

A similar argument can be derived to show that if there exists a commander
$c\in\mathcal{C}^{2}$ for Player 2 such that for every $x\in\mathcal{X}_{c}$,
$\tau_{x,s}=\textit{c2}$, then any $a^{2^{\dagger}}\in\mathcal{A}^{2}_{s}$
such that $a^{2^{\dagger}}_{o}=\textit{none}$ for every
$o\in\cup_{x\in\mathcal{X}_{c}}\widetilde{\mathcal{O}}^{2}_{x,s}$ cannot
receive any positive probability in equilibrium. In conclusion, when (7)-(9)
hold, in _every_ MPE of $\Gamma$, each player randomizes at every state
$s\in\mathcal{S}$ over actions that satisfy (5)-(6).

###### Proof 7.3

Proof of Proposition 4.3. Consider a campaign with one commander for each
player, an iteration $t\in\mathbb{Z}_{>0}$ of the VI algorithm (initialized
with $V^{(0)}=L$), and a state $s\in\mathcal{S}$. First, we investigate when
the campaign has a single axis $x=(o_{1},\dots,o_{n})$ of size $n$.

If $\tau_{x,s}\in\\{\textit{c1},\textit{c2},\textit{sf}\\}$, then (5)-(6)
imply that $|\mathcal{A}^{1}_{s}|=|\mathcal{A}^{2}_{s}|=1$ and
$\Gamma(V^{(t-1)},s)$ admits a pure equilibrium. If $\tau_{x,s}=\textit{pf}$
with the front occurring at $\\{o_{k},o_{k+1}\\}$ for some $k\in\llbracket
1,n-1\rrbracket$, let $s^{-}$ (resp. $s^{+}$) be the state that differs from
$s$ at objective $o_{k+1}$ (resp. $o_{k}$). That is, $s^{-}_{o_{k+1}}=1$ and
$s^{+}_{o_{k}}=2$. Each player $i\in\\{1,2\\}$ has two feasible actions at
state $s$: the action $\hat{a}^{i}$ (resp. $\check{a}^{i}$) that attacks
(resp. reinforces) the uncontrolled (resp. controlled) objective at the front.
We obtain the following equalities:

$\displaystyle\mathbb{E}_{s^{\prime}\sim
P(\cdot\,|\,s,\check{a}^{1},\check{a}^{2})}[V^{(t-1)}(s^{\prime})]=V^{(t-1)}(s)$
$\displaystyle\mathbb{E}_{s^{\prime}\sim
P(\cdot\,|\,s,\hat{a}^{1},\check{a}^{2})}[V^{(t-1)}(s^{\prime})]=p_{o_{k+1}}(1\,|\,s,\hat{a}^{1}_{o_{k+1}},\check{a}^{2}_{o_{k+1}})\cdot
V^{(t-1)}(s^{-})+p_{o_{k+1}}(2\,|\,s,\hat{a}^{1}_{o_{k+1}},\check{a}^{2}_{o_{k+1}})\cdot
V^{(t-1)}(s)$ $\displaystyle\mathbb{E}_{s^{\prime}\sim
P(\cdot\,|\,s,\check{a}^{1},\hat{a}^{2})}[V^{(t-1)}(s^{\prime})]=p_{o_{k}}(1\,|\,s,\check{a}^{1}_{o_{k}},\hat{a}^{2}_{o_{k}})\cdot
V^{(t-1)}(s)+p_{o_{k}}(2\,|\,s,\check{a}^{1}_{o_{k}},\hat{a}^{2}_{o_{k}})\cdot
V^{(t-1)}(s^{+}).$

Since $V^{(t-1)}$ is isotone, we deduce the following inequalities:

$\displaystyle R(V^{(t-1)},s,\hat{a}^{1},\check{a}^{2})\leq
R(V^{(t-1)},s,\check{a}^{1},\check{a}^{2})\leq
R(V^{(t-1)},s,\check{a}^{1},\hat{a}^{2}).$

Thus, a pure equilibrium of $\Gamma(V^{(t-1)},s)$ is

$\displaystyle\begin{cases}(\hat{a}^{1},\check{a}^{2})&\text{ if
}R(V^{(t-1)},s,\hat{a}^{1},\hat{a}^{2})\leq
R(V^{(t-1)},s,\hat{a}^{1},\check{a}^{2})\\\ (\hat{a}^{1},\hat{a}^{2})&\text{
if
}R(V^{(t-1)},s,\hat{a}^{1},\hat{a}^{2})\in[R(V^{(t-1)},s,\hat{a}^{1},\check{a}^{2}),R(V^{(t-1)},s,\check{a}^{1},\hat{a}^{2})]\\\
(\check{a}^{1},\hat{a}^{2})&\text{ if
}R(V^{(t-1)},s,\hat{a}^{1},\hat{a}^{2})\geq
R(V^{(t-1)},s,\check{a}^{1},\hat{a}^{2}).\end{cases}$

Now, we investigate when the campaign has possibly multiple axes (under the
responsibility of a single commander) and when the state $s$ is such that at
least one axis $x=(o_{1}^{x},\dots,o_{|x|}^{x})$ is of type
$\tau_{x,s}=\textit{pf}$ with the front occurring at
$\\{o_{k}^{x},o_{k+1}^{x}\\}$ for some $k\in\llbracket 1,|x|-1\rrbracket$. We
consider two feasible actions for each player $i\in\\{1,2\\}$: an action
$\hat{a}^{i}$ (resp. $\check{a}^{i}$) that attacks (resp. reinforces) the
uncontrolled (resp. controlled) objective at the front of axis $x$.

Consider $a^{2}\in\mathcal{A}^{2}_{s}\setminus\\{\hat{a}^{2}\\}$. Then,

$\displaystyle\forall\;o\in\mathcal{O}\setminus\\{o_{k+1}^{x}\\},\ $
$\displaystyle
p_{o}(1\,|\,s,\hat{a}^{1}_{o},a^{2}_{o})=p_{o}(1\,|\,s,\check{a}^{1}_{o},a^{2}_{o})$
$\displaystyle
p_{o_{k+1}^{x}}(1\,|\,s,\hat{a}^{1}_{o_{k+1}^{x}},a^{2}_{o_{k+1}^{x}})\geq
p_{o_{k+1}^{x}}(1\,|\,s,\check{a}^{1}_{o_{k+1}^{x}},a^{2}_{o_{k+1}^{x}}).$

Since $V^{(t-1)}$ is isotone, we deduce that for every
$a^{2}\in\mathcal{A}^{2}_{s}\setminus\\{\hat{a}^{2}\\}$,
$R(V^{(t-1)},s,\hat{a}^{1},a^{2})\leq R(V^{(t-1)},s,\check{a}^{1},a^{2})$.
Thus, if the inequality $R(V^{(t-1)},s,\hat{a}^{1},\hat{a}^{2})\leq
R(V^{(t-1)},s,\check{a}^{1},\hat{a}^{2})$ holds, then Player 1 will not
reinforce $o_{k}^{x}$ in at least one equilibrium of $\Gamma(V^{(t-1)},s)$.

A similar argument shows that when the inequality
$R(V^{(t-1)},s,\hat{a}^{1},\hat{a}^{2})\geq
R(V^{(t-1)},s,\hat{a}^{1},\check{a}^{2})$ holds, then Player 2 will not
reinforce $o_{k+1}^{x}$ in at least one equilibrium of $\Gamma(V^{(t-1)},s)$.

Since $R(V^{(t-1)},s,\hat{a}^{1},\check{a}^{2})\leq
R(V^{(t-1)},s,\check{a}^{1},\check{a}^{2})\leq
R(V^{(t-1)},s,\check{a}^{1},\hat{a}^{2})$, then
$R(V^{(t-1)},s,\hat{a}^{1},\hat{a}^{2})$ always satisfies at least one of the
two above-mentioned inequalities, providing the desired result.