#  VISER: A Tractable Solution Concept for Games with Information Asymmetry

Jeremy McMahan
University of Wisconsin-Madison
<EMAIL_ADDRESS>
&Young Wu
University of Wisconsin-Madison
<EMAIL_ADDRESS>
&Yudong Chen
University of Wisconsin-Madison
<EMAIL_ADDRESS>
&Xiaojin Zhu
University of Wisconsin-Madison
<EMAIL_ADDRESS>
&Qiaomin Xie
University of Wisconsin-Madison
<EMAIL_ADDRESS>

###### Abstract

Many real-world games suffer from information asymmetry: one player is only
aware of their own payoffs while the other player has the full game
information. Examples include the critical domain of security games and
adversarial multi-agent reinforcement learning. Information asymmetry renders
traditional solution concepts such as Strong Stackelberg Equilibrium (SSE) and
Robust-Optimization Equilibrium (ROE) inoperative. We propose a novel solution
concept called VISER (Victim Is Secure, Exploiter best-Responds). VISER
enables an external observer to predict the outcome of such games. In
particular, for security applications VISER allows the victim to better defend
itself while characterizing the most damaging attacks available to the
exploiter. We show that each player’s VISER strategy can be computed
independently in polynomial time using linear programming (LP). We extend
VISER to its Markov Perfect counterpart in Markov games, which can also be
solved efficiently by a series of LPs.

##  1 Introduction

As multi-agent systems become increasingly distributed and complex,
information asymmetry amongst agents becomes inevitable. We focus on two-
player general-sum games (and by extension, Markov games) with the following
information asymmetry: the first player knows the game except the second
player’s payoff function, while the second player has full information of the
game. Obviously, the second player can exploit its information advantage to
optimize its own payoff, possibly at the expense of the first player. As such,
we refer to the second player as the _exploiter_ and the first player as the
_victim_. For example, in security applications and adversarial MARL the
victim often does not know the exploiter’s true incentive or cost of taking
each attack action [2, 10]. In contrast, the exploiter knows the victims
payoff in addition to its own. Given such a game with information asymmetry,
can we predict what rational players will do?

#### Prior work.

Incomplete information games were first studied through the framework of
Bayesian games [11, 13, 12] with corresponding solution concept being the
Bayes Nash Equilibrium (BNE). Importantly, the Bayesian approach requires the
players to have “known unknowns”: an accurate distribution of the unknown
parameters of the game. To address the high sensitivity BNE with respect to
the player’s beliefs [25, 16], the work [14] introduced a more robust
equilibrium concept called ex-post equilibrium, which is a NE under all
possible realizations of the uncertain parameters. Then, [21] studied another
robust variation, where the players have multiple belief distributions and
they compute the robust solution (maximin) over the worst possible scenario.
More recently, the Bayesian approach has been extended to deal with type-
uncertainty in Markov security games [26].

Going beyond the need for belief distributions, [1] introduced the notion of
robust games where the uncertainty is defined by a deterministic set over
parameters defining the shape of the payoff functions. The solution concept to
a robust game is a robust-optimization equilibrium (ROE), which is found using
robust optimization techniques with respect to the worst-case parameters in
the uncertainty set. ROE is a distribution-free solution concept that was
shown to be less conservative than ex-post equilibrium in that every ex-post
equilibrium is an ROE [1]. Then, [6] generalized ROE to allow a broader class
of payoff functions and showed that ROE can be seen as an $\epsilon$-NE in the
game without uncertainty. Recently, [7] studied how sensitive ROE is with
respect to the uncertainty levels of the players. However, both the BNE and
ROE approach require non-trivial assumptions about the information structure:
namely, an uncertainty parametrization or distributional assumption on the
opponent’s payoffs. Thus, they do not apply to our setting where the victim
knows nothing about the exploiter’s payoffs.

Besides the issue of requiring a parametrization or distribution of the
opponent’s payoff, computing a NE (BNE and ROE) of a general-sum game is PPAD-
hard. Luckily, using the power of commitment, a Strong Stackelberg Equilibrium
(SSE), which yields the victim a higher payoff than in a NE, can be computed
in polynomial-time for two-player games [4, 5]. In fact, even for security
games with exponentially large strategy spaces, a SSE can still be computed
efficiently [19]. As many real-world security games can satisfy the commitment
assumption, the SSE has been the dominant solution concept for security
applications [28]. For example, Stackelberg strategies are the heart of LAX’s
airport security ARMOR system [15, 24] and are also used in the system IRIS
used by the US Federal Air Marshals [18] with many other important
applications [2]. Recently, the Stackelberg approach has been extended to
Markov security games [20], but at the cost of even stronger assumptions on
the information structure of the players. Information asymmetry has also been
studied for SSE, but only when the asymmetry comes from either the exploiter
being unable to fully see the commitment [29] or the victim has more
information [31, 32], which is virtually the opposite of our setting.

#### Our contributions.

First, (i) we propose and study a new solution concept, VISER, which is
appropriate for games with information asymmetry. VISER stands for victim is
secure and the exploiter best-responds. VISER posits that a rational victim,
lacking information on the exploiter, will necessarily choose from the set of
its own maximin strategies. The exploiter can reason the victim will do this,
but does not know the particular maximin strategy chosen. Thus, a rational
exploiter must best respond to the worst-case member of the victim maximin
strategy set. Importantly, a VISER solution always exists and each player can
independently play its VISER strategy without the need for coordination or
signaling. Also, if either player unilaterally deviates from a VISER solution,
then they will achieve lower payoff in the worst-case, so VISER functions as
an an equilibrium concept. Second, (ii) we show that each player can compute a
VISER strategy independently in polynomial time by solving a linear program
(LP). A key technical insight is that the exploiter can use LP duality to
convert its robust, best-response optimization problem into a single LP.
Third, (iii) we generalize our framework to Markov games (also known as
stochastic games). Here, it is more natural to study Markov-perfect VISER
solutions (MPVISER), which consist of Markovian policies, as standard in the
theory of stochastic games [27]. We show a MPVISER solution is a VISER
solution, it always exists, and each player can compute a MPVISER solution in
polynomial time by solving a sequence of LPs via backward induction.

##  2 Preliminaries

#### Bimatrix Games.

In a (finite) bimatrix game, two players compete simultaneously to maximize
their own payoff. Suppose that the first player, the victim, has $n$ pure
strategies and the second player, the exploiter, has $m$ pure strategies. Let
$A\in\mathbb{R}^{n\times m}$ and $B\in\mathbb{R}^{n\times m}$ denote the
payoff matrices for the victim and exploiter, respectively. We may represent a
pure strategy by a one-hot vector, so $e_{i}\in\mathbb{R}^{n}$ corresponds to
victim’s strategy $i$ and $e_{j}\in\mathbb{R}^{m}$ the exploiter’s strategy
$j$. Let $\Delta(k):=\big{\\{}s\in[0,1]^{k}\mid\sum_{i=1}^{k}s_{i}=1\big{\\}}$
denote the set of mixed strategies, where choosing $s\in\Delta(k)$ corresponds
to playing $e_{i}$ with probability $s_{i}$. For a pair mixed strategies
$x\in\Delta(n)$ and $y\in\Delta(m)$, the expected payoffs to the victim and
exploiter are $x^{\top}Ay$ and $x^{\top}By$, respectively.

#### Nash Equilibrium and Security Strategies.

Solutions to games manifest as equilibrium concepts, among which the most
famous is the _Nash Equilibrium_ (NE) [23]. An NE of a bimatrix game is a pair
of strategies $(x^{*},y^{*})\in\Delta(n)\times\Delta(m)$ satisfying

$x^{*}\in\operatorname*{arg\,max}_{x\in\Delta(n)}x^{\top}Ay^{*},\;\;\text{ and
}\;\;y^{*}\in\operatorname*{arg\,max}_{y\in\Delta(m)}{x^{*}}^{\top}By.$

Another solution concept is a _maximin strategy_ or _security strategy_ ,
which is a pair $(x^{*},y^{*})$ given by

$x^{*}\in\operatorname*{arg\,max}_{x\in\Delta(n)}\min_{y\in\Delta(m)}x^{\top}Ay,\;\;\text{
and
}\;\;y^{*}\in\operatorname*{arg\,max}_{y\in\Delta(m)}\min_{x\in\Delta(n)}x^{\top}By.$
(1)

In a _zero-sum_ game ($B=-A$), the Minimax Theorem [30] implies
$(x^{*},y^{*})$ is a NE if and only if it is a maximin strategy pair. Note
that a game may have multiple NEs and maximin strategies. However, in zero-sum
games, each player receives the same expected payoff in every NE, which we
denote by $p_{v}^{NE}$ and $p_{e}^{NE}$ respectively.

#### Markov Games.

A finite-horizon _Markov game_ [27] is defined by a tuple $G=(S,A,R,P,H,\mu)$
with state space $S$, joint action space $A=A_{v}\times A_{e}=[n]\times[m]$
($[i]:=\left\\{1,\ldots,i\right\\}$), joint reward function $R$, transition
function $P$, horizon $H$, and initial state distribution $\mu$. We denote by
$\pi=\\{\pi_{h}(s)\in\Delta(n)\\}_{h,s}$ a Markovian policy for the victim and
by $\nu=\\{\nu_{h}(s)\in\Delta(m)\\}_{h,s}$ a Markovian policy for the
exploiter. Let $\Pi$ denote the set of all Markovian policies for the victim
and $N$ denote the set of all Markovian policies for the exploiter. For
$u\in\\{v,e\\}$ (victim and exploiter), the value/payoff received by player
$u$ under $(\pi,\nu)$ is the expected cumulative rewards over $H$ time steps:
$V_{u}^{\pi,\nu}\equiv
V_{1u}^{\pi,\nu}:=\operatorname*{E}_{\pi,\nu}\left[\sum_{h=1}^{H}\pi_{h}(s_{h})^{\top}R_{hu}(s_{h})\nu_{h}(s_{h})\right]$.
Similarly define the stage value, $V_{hu}^{\pi^{*},\nu^{*}}(s)$, for each
$h\in[H]$ by summing over steps $h$ through $H$.

Equilibrium concepts can be defined for a Markov Game by viewing it as a (very
large) bimatrix game with payoff matrices $(V_{v}^{\pi,\nu})_{\pi,\nu}$ and
$(V_{e}^{\pi,\nu})_{\pi,\nu}$. To avoid this complexity blowup, many works
focus on _Markov Perfect Equilibrum_ (MPE), which requires the stricter
property that a policy pair is an equilibrium at _every_ stage game, not just
at stage $h=1$. Formally, $(\pi^{*},\nu^{*})$ is a MPE if, for all
$(h,s)\in[H]\times S$,

$V_{hv}^{\pi^{*},\nu^{*}}(s)=\max_{\pi\in\Pi}V^{\pi,\nu^{*}}_{hv}(s)\;\;\text{
and }\;\;V_{he}^{\pi^{*},\nu^{*}}(s)=\max_{\nu\in N}V^{\pi^{*},\nu}_{he}(s).$

##  3 VISER: A New Solution Concept

Suppose the victim and exploiter compete in a bimatrix game $(A,B)$ with
information asymmetry. The victim knows only $A$, but the exploiter knows both
$A$ and $B$. The exploiter naturally wishes to leverage its information
advantage: it seeks to derive a strategy $y^{*}$ that achieves a higher value
than it would from only knowing $B$. On the other hand, the victim is aware of
its information disadvantage and thus simply wants to guarantee a good value
regardless of the exploiter’s strategy.

#### Rationality.

As shown in [9], real players are averse to uncertainty. This is reinforced by
the fact if a player guesses some belief incorrectly, it risks achieving
arbitrarily poor value [25]. Consequently, as argued by worst-case approaches
in game theory [1], it is rational for such players to use a strategy that
optimizes its worst-case scenario since it cannot formulate any accurate
beliefs of the other player’s payoff. We assume the players follow this
reasoning, which we call _worst-case rationality_.

######  Assumption 1.

(Worst-Case Rationality) Both players seek to optimize their worst-case payoff
with respect to the information available to them, and this fact is common
knowledge to both players.

#### Victim’s Perspective.

Absent any information about the exploiter’s strategy or payoff, the safest
option for the victim is to play a security strategy Equation 1. A security
strategy guarantees the victim a baseline payoff regardless of how the
exploiter uses its information advantage to pick a strategy. And, importantly,
a security strategy can be computed from knowledge of $A$ alone. Equivalently,
since the victim has no knowledge whatsoever about $B$, we can view them as
_assuming_ that $B=-A$, i.e., the exploiter is adversarial, and then computing
an NE of the zero-sum game $(A,-A)$.

######  Observation 1.

(Victim Behavior) Under 1, the victim will play:

$x^{*}\in
X^{*}:=\operatorname*{arg\,max}_{x\in\Delta(n)}\min_{y\in\Delta(m)}x^{\top}Ay,$

which guarantees the victim an expected payoff of at least,

$p_{v}:=\max_{x\in\Delta(n)}\min_{y\in\Delta(m)}x^{\top}Ay.$

The intuition is that if the victim does not play some $x^{*}\in X^{*}$ it
could receive _arbitrarily worse_ payoff in the worst case. To illustrate this
point, consider the game in Figure 1(a). If the victim were to optimistically,
but incorrectly, believe the game was actually the one in Figure 1(b), then it
would play action D as part of the NE (D, R). However, in the true game 1(a),
playing D results in the worst-case scenario of receiving $0$ payoff. In
contrast, if the victim were to have played its unique security strategy, U,
it would have received at least a payoff of $x$, which is arbitrarily larger
than $0$.

| L | R
---|---|---
U | (x,y) | (2x,0)
D | (0,y) | (3x,0)
(a) Victim’s Example

| L | R
---|---|---
U | (x,0) | (2x,y)
D | (0,0) | (3x,y)
(b) Victim’s Belief

| L | R
---|---|---
U | (x,2y) | (x,-1)
M | (x,y) | (x,-1)
D | (-1,-1) | (-1,0)
(c) Exploiter’s Example

Figure 1: Example Games

#### Exploiter’s Perspective.

The exploiter could also compute its own security strategy, but this would not
take advantage of its information advantage. The exploiter knows both $A$ and
$B$ and can reason that under 1 the victim will play some $x^{*}\in X^{*}$ as
indicated by 1. However, the exploiter is not completely omniscient. It does
not know which $x^{*}\in X^{*}$ is chosen and so suffers from strategic
uncertainty [22]. Thus, the exploiter should assume the worst-case $x^{*}\in
X^{*}$ is chosen by the victim and simply best-respond to it. Here, we
generalize the best-response function to a function on a set $X^{*}$ by
considering the worst-case best-response.

######  Observation 2.

(Exploiter Behavior) Under 1, the exploiter will play:

$y^{*}\in\operatorname*{BR}(X^{*}):=\operatorname*{arg\,max}_{y\in\Delta(m)}\min_{x^{*}\in
X^{*}}x^{*^{\top}}By,$

which guarantees the exploiter an expected payoff of at least,

$p_{e}:=\max_{y\in\Delta(m)}\min_{x^{*}\in X^{*}}x^{*^{\top}}By.$

Critically, the exploiter uses its information advantage to obtain a payoff
higher than what can be achieved by an unrestricted best response
$y\in\operatorname*{BR}(\Delta(n))$, which consists of its security strategies
as defined in Equation 1. In fact, playing a security strategy could lead to
_arbitrarily worse_ payoff for the exploiter. Consider the game in Figure
1(c). It is clear that any mix of U and M yields a security strategy for the
victim, which achieves the victim a payoff of $x$. The exploiter’s best
response in the worst case is L, which achieves it a payoff of at least $y$.
In contrast, its unique security strategy is R, which achieves a payoff of at
most $0$ in general and at most $-1$ if the victim plays rationally. Thus,
playing the worst-case best-response leads to an arbitrarily higher payoff for
the exploiter.

####  VISER Solution.

Under 1, 1 and 2 imply a game with information asymmetry will play out as
follows: the victim will play a security strategy from $X^{*}$ and the
exploiter plays a worst-case best-response strategy from
$\operatorname*{BR}(X^{*})$. This leads to our solution concept we call VISER
for _v ictim is secure and the exploiter best-responds_.

######  Definition 1.

(VISER)

$\textup{{VISER}}:=X^{*}\times\operatorname*{BR}(X^{*}).$

Importantly, each player can compute its own part of a VISER pair given only
the information available to it: no coordination or signaling schemes are
needed. Also, a VISER solution always exists.

######  Theorem 1.

Under 1, the VISER concept satisfies the following properties:

  * •

A VISER solution always exists ($\textup{{VISER}}\neq\varnothing)$,

  * •

A VISER solution can be deployed in a distributed fashion, and

  * •

Deviating from a VISER solution achieves each player a worse payoff in the
worst case.

Thus, in a bimatrix game where the victim knows only $A$, but the exploiter
knows both $A$ and $B$, under 1, the players will choose a strategy pair
$(x^{*},y^{*})\in\textup{{VISER}}$.

#### Expected Payoffs.

We can characterize the payoffs achieved by both players under VISER. Let
$(x^{*},y^{*})\in\textup{{VISER}}$. We see the victim’s payoff by 1 is at
least as good as the maximin value, $p_{v}$, but could be even higher
depending on the choice of $y^{*}$. Similarly, the exploiter’s payoff by 2 is
at least as good as the $X^{*}$-restricted maximin value, $p_{e}$, but could
be even higher depending on the choice of $x^{*}$. When the game is zero-sum,
the maximin theorem implies that $p_{v}=p_{v}^{\textup{NE}}$ is the unique NE
payoff. Similarly, the exploiter best responds to $X^{*}$ and so best responds
to some Nash strategy, which gives a Nash strategy for the exploiter. Hence,
$p_{e}=p_{e}^{\textup{NE}}$ as well from the definition of Nash as mutual
best-responses.

######  Proposition 1.

For any $(x^{*},y^{*})\in\textup{{VISER}}$,

${x^{*}}^{\top}Ay^{*}\geq p_{v},\text{ and }{x^{*}}^{\top}By^{*}\geq p_{e}.$

If the game is zero-sum, then:

${x^{*}}^{\top}Ay^{*}=p_{v}^{\textup{NE}},\text{ and
}{x^{*}}^{\top}By^{*}=p_{e}^{\textup{NE}}.$

#### Comparison to Stackelberg Strategies.

We can view VISER through the lens of Stackelberg strategies [4, 19]. Our
common knowledge assumption functionally announces to the exploiter that the
victim will play from $X^{*}$. However, unlike typical Stackelberg strategies,
rather than committing to a single mixed strategy, the victim here is
committing to a set of strategies. Consequently, the exploiter now must best
respond to an entire set rather than just a single strategy. Thus, VISER
strategies can be seen as a generalization of Stackelberg strategies with set-
wise commitments and set-wise best responses. In fact, our algorithms in
Section 4 continue to work so long as the victim commits to a succinctly
representable polytope of strategies.

##  4 Linear Programs for Computing VISER in Bimatrix Games

Next, we study the computational complexity of computing VISER solutions. We
show both players can efficiently compute a VISER strategy using linear
programming. For the victim, the LP is derived analogously to the LP for
computing a NE. The exploiter’s problem, however, is more challenging since it
must best respond to $X^{*}$, a potentially infinite set of mixed
strategies.111The polytope $X^{*}$ may have an exponential (in $n,m$) number
of extreme points in the worst-case. Despite its apparent difficulty, we use
linear programming duality to derive an LP that computes the exploiter’s
optimal strategy.

$\displaystyle\max_{x\in\mathbb{R}^{n},z\in\mathbb{R}}\quad\ z$ s.t.
$\displaystyle z\leq x^{\top}Ae_{j},\quad\forall j\in[m]$ $\displaystyle
1^{\top}x=1,\quad x\geq 0.$ (a) Victim’s LP

$\displaystyle\max_{y,w\in\mathbb{R}^{m},\alpha\in\mathbb{R}}\quad\
z^{*}1^{\top}w-\alpha$ s.t. $\displaystyle\alpha+e_{i}^{\top}By-
e_{i}^{\top}Aw\geq 0\quad\forall i\in[n]$ $\displaystyle 1^{\top}y=1,\quad
y\geq 0\quad w\geq 0.$ (b) Exploiter’s LP

Figure 2: VISER LPs

#### Victim’s LP.

The victim must compute a security strategy as suggested in 1. From the
victim’s perspective, it faces a zero-sum game with payoff matrix $A$. As
such, a security strategy can be computed using the standard LP formulation of
computing an NE for this zero-sum game [8]. This LP can be seen in Figure
2(a).

######  Proposition 2.

For any optimal solution $(x^{*},z^{*})$ to LP 2(a), $x^{*}$ is a VISER
strategy for the victim and $z^{*}=p_{v}$ is the victim’s guaranteed payoff.
Furthermore, the set of all VISER strategies for the victim, $X^{*}$, is the
non-empty polytope:

$X^{*}=\left\\{x\in\Delta(n)\mid z^{*}\leq x^{\top}Ae_{j}\ \forall
j\in[m]\right\\}.$

#### Exploiter’s LP.

The exploiter computes its worst-case best-response to $X^{*}$ as suggested in
2. The inner minimization problem in 2 amounts to first fixing an exploiter
strategy $y\in\Delta(m)$ and then identifying the worst-case victim strategy
for the exploiter, $\min_{x\in X^{*}}x^{\top}By$. Notice the optimization
problem involves the implicitly defined set $X^{*}$. Our key technical insight
is that the exploiter can avoid enumerating $X^{*}$ by dualizing the problem.
Observe that the inner minimization problem can be explicitly written as an
LP:

$\displaystyle\min_{x\geq 0}$ $\displaystyle\ x^{\top}By$ (2) s.t.
$\displaystyle z^{*}-x^{\top}Ae_{j}\leq 0\quad\forall j\in[m]$ $\displaystyle
1^{\top}x-1=0,$

where $(x^{*},z^{*})$ is any solution to LP 2(a), which can be constructed by
the exploiter as it knows the victim’s payoff matrix $A$. The exploiter should
optimize its choice of $y$ by maximizing the value of Equation 2, which would
result in a max-min problem. We can convert this problem into a double-max
problem by taking the dual of Equation 2, given as follows:

$\displaystyle\max_{w\geq 0,\alpha}$ $\displaystyle\ z^{*}1^{\top}w-\alpha$
(3) s.t. $\displaystyle\alpha+e_{i}^{\top}By-e_{i}^{\top}Aw\geq 0\quad\forall
i\in[n],$

where $w\in\mathbb{R}^{m}_{\geq 0}$ and $\alpha\in\mathbb{R}$ are the dual
variables corresponding to the first and second constraints in Equation 2,
respectively. Applying $\max_{y\in\Delta(m)}$ on top of Equation 3, yields the
exploiter’s LP, which can be seen in Figure 2(b). We give the full derivation
in the Appendix.

######  Proposition 3.

For any optimal solution $(y^{*},w^{*},\alpha^{*})$ to LP 2(b), $y^{*}$ is a
VISER strategy for the exploiter and $z^{*}1^{\top}w^{*}-\alpha^{*}=p_{e}$ is
the exploiter’s guaranteed payoff. Furthermore, the set of all VISER
strategies for the exploiter, $\operatorname*{BR}(X^{*})$, is the non-empty
projection polytope:

$\operatorname*{BR}(X^{*})=\left\\{y\in\Delta(m)\mid\exists
w\in\mathbb{R}^{m}_{\geq 0},\
e_{i}^{\top}By+(z^{*}1^{\top}-e_{i}^{\top}A)w\geq p_{e}\ \forall
i\in[n]\right\\}.$

In particular, $\operatorname*{BR}(X^{*})$ contains the non-empty polytope
induced by fixing $w=w^{*}$.

Note that the exploiter must first solve LP 2(a) to compute $z^{*}$.
Effectively, the exploiter is using its information advantage to simulate what
the victim will do. After computing $z^{*}$, the exploiter can then compute
its strategy $y^{*}$ using LP 2(b).

######  Theorem 2.

LP 2(a) has $n+1$ variables and $m+1$ constraints, and LP 2(b) has $2m+1$
variables and $n+1$ constraints. Thus, both LPs have polynomially many
variables and constraints, so both players can compute their VISER strategy
for a general-sum game independently in polynomial time.

#### Approximate Rationality.

Although we focus on worst-case rationality, our framework still applies when
the victim is willing to take calculated risks. Suppose the victim will accept
any $\epsilon$-maximin strategy for some $\epsilon\geq 0$, i.e. any strategy
$x^{*}$ satisfying
$\min_{y}{x^{*}}^{\top}Ay\geq\max_{x}\min_{y}{x}^{\top}Ay-\epsilon$. Clearly,
the victim’s approximate maximin set is still a polytope and is given by,

$X^{*}_{\epsilon}=\left\\{x\in\Delta(n)\mid z^{*}-\epsilon\leq x^{\top}Ae_{j}\
\forall j\in[m]\right\\}.$

We then see the best-response for the exploiter to the victim’s set of
strategies takes the same form; the only difference is the objective function
of LP 2(b) is changed to be $(z^{*}-\epsilon)1^{\top}w-\alpha$.

##  5 Algorithms for Computing VISER in Markov Games

We can extend the techniques above to compute VISER solutions for Markov
games. A naive approach is to simply use the techniques from Section 4
directly on the bimatrix representation of the Markov game. However, this
approach is computationally inefficient since the bimatrix representation is
exponentially sized in general. In fact, general VISER solutions to a Markov
game, similar to general NE, consist of history-dependent policies — simply
writing down these policies requires space exponential in the horizon $H$.
Consequently, as traditionally done in the Markov game literature, we focus on
computing Markovian policies for both players, which can be implemented in
practice. To this end, we require a slightly stronger assumption on the
players’ rationality.

######  Assumption 2.

Both players are worst-case rational in every stage game and this is common
knowledge.

In words, the players not only wish to optimize their overall worst-case
payoff, but they also wish to do well against the stage game they may face at
any moment in time. This leads the players to computing even more structured
solutions: namely, Markov-perfect VISER solutions.

####  MPVISER Solutions.

The VISER solutions for the stage game $(h,s)$ are defined as,

$\Pi_{hs}^{*}:=\operatorname*{arg\,max}_{\pi\in\Pi}\min_{\nu\in
N}V^{\pi,\nu}_{hv}(s)\text{ and }N_{hs}^{*}:=\operatorname*{arg\,max}_{\nu\in
N}\min_{\pi^{*}\in\Pi_{hs}^{*}\cap\bigcap_{k>h,s^{\prime}}\Pi^{*}_{ks^{\prime}}}V^{\pi^{*},\nu}_{he}(s).$

The definition of $\Pi^{*}_{hs}$ is standard; however, notice the argument of
the minimum in $N^{*}_{hs}$ reflects the exploiter’s knowledge that the victim
must be optimal at every future stage, not just at stage $(h,s)$. We define a
policy pair $(\pi^{*},\nu^{*})$ to be a _Markov-perfect VISER_ (MPVISER)
solution if $(\pi^{*},\nu^{*})$ is a VISER solution for every stage game, i.e.
$\pi^{*}\in\Pi^{*}_{h,s}$ and $\nu^{*}\in N^{*}_{h,s}$ for all $h,s$.

######  Definition 2.

(MPVISER)

$\textup{{MPVISER}}:=\bigcap_{h,s}\Pi_{hs}^{*}\times\bigcap_{h,s}N^{*}_{hs}.$

Similar to Markov-perfect NE, a MPVISER solution always exists, is a pair of
Markovian policies, and is a VISER solution, so inherits all the properties we
saw from Theorem 1.

######  Proposition 4.

Under 2, $\varnothing\neq\textup{{MPVISER}}\subseteq\textup{{VISER}}$ and so
players will play some $(\pi^{*},\nu^{*})\in\textup{{MPVISER}}$.

Input: Markov Game $G$ without $\\{R_{he}\\}_{h}$

1 for  _$h=H$ down to $1$_ do

2 for  _$s\in S$_ do

3 $Q^{*}_{hv}(s)\leftarrow$ Equation 4

4 $\pi_{h}^{*}(s),V_{hv}^{*}(s)\leftarrow$ LP 2(a)($Q^{*}_{hv}(s)$)

5 end for

6

7 end for

8

9

return $\pi^{*}=\\{\pi_{h}^{*}(s)\\}_{h,s}$

Algorithm 1 Victim

Input: Markov Game $G$

1 for  _$h=H$ down to $1$_ do

2 for  _$s\in S$_ do

3 $Q^{*}_{hv}(s),Q^{*}_{he}(s)\leftarrow$ Equation 4

4 $\pi_{h}^{*}(s),V_{hv}^{*}(s)\leftarrow$ LP 2(a)($Q^{*}_{hv}(s)$)

5 $\nu_{h}^{*}(s),w_{h}^{*}(s),\alpha_{h}^{*}(s)$ $\leftarrow$

6 LP 2(b)($Q^{*}_{hv}(s)$, $Q^{*}_{he}(s)$)

7 end for

8

9 end for

return $\nu^{*}=\\{\nu_{h}^{*}(s)\\}_{h,s}$

Algorithm 2 Exploiter

Figure 3: VISER Algorithms

#### Algorithms.

In the same spirit as Nash-VI [27, 33, 17], both players can use backward
induction: each can solve their respective LP for the bimatrix stage games
backwards in time. For any $s\in S$, the stage game at the final time step is
just the last bimatrix game: $Q^{*}_{Hu}(s)=R_{hu}(s)$. For each $h<H,s\in
S,u\in\\{v,e\\}$, the bimatrix stage game, $Q^{*}_{hu}(s)$, is defined by,

$Q^{*}_{hu}(s)[a_{v},a_{e}]=\left[R_{hu}(s,a_{v},a_{e})+\sum_{s^{\prime}}P_{h}(s^{\prime}\mid
s,a_{v},a_{e})V^{*}_{(h+1)u}(s^{\prime})\right],$ (4)

where $V_{(h+1)v}^{*}(s^{\prime})$ is the maximin value induced by
$\Pi^{*}_{(h+1)s^{\prime}}$, and and $V_{(h+1)e}^{*}(s^{\prime})$ is the
constrained maximin value induced by $N^{*}_{(h+1)s^{\prime}}$. Overall, for
$h$ in backward order and all $s$, each player computes $Q^{*}_{hu}(s)$ using
Equation 4 and then solves their bimatrix LP with input matrices
$A=Q^{*}_{hv}(s)$ and $B=Q^{*}_{he}(s)$. The product policy constructed from
all stages yields a MPVISER for each player.

#### Victim’s Algorithm.

The victim needs to compute a maximin for each stage game. For each $h,s$ in
backward order, the victim computes $Q^{*}_{hv}(s)$ using Equation 4 and the
previously computed future stage values, $V^{*}_{(h+1)v}(s^{\prime})$. Then,
it solves LP 2(a) with input matrix $A=Q^{*}_{hv}(s)$ to compute a strategy
$\pi^{*}_{h}(s)$ and the current stage value $V^{*}_{hv}(s)$. The total
product policy $\pi^{*}=\\{\pi^{*}_{h}(s)\\}_{h,s}$ is a MPVISER for the
victim. The victim’s full algorithm can be seen in Algorithm 1. The
correctness of Algorithm 1 relies critically on the fact that the Nash value
of each zero-sum stage game, and hence the maximin value of each stage game,
is unique.

######  Proposition 5.

For any output $\pi^{*}$ of Algorithm 1, $\pi^{*}$ is a MPVISER strategy for
the victim, and $\sum_{s}\mu(s)V_{1v}^{*}(s)=p_{v}$ is the victim’s guaranteed
payoff for the game. Furthermore, the set of all VISER strategies for the
victim in the stage game $(h,s)$ is the non-empty polytope,

$\hat{\Pi}_{hs}:=\left\\{\pi_{h}(s)\in\Delta(n)\mid
V_{hv}^{*}(s)\leq\pi_{h}(s)^{\top}Q^{*}_{hv}(s)e_{j}\ \forall
j\in[m]\right\\},$

and the set of MPVISER policies for the game is the non-empty polytope:
$\bigcap_{h,s}\Pi^{*}_{hs}=\bigtimes_{h,s}\hat{\Pi}_{hs}$.

#### Exploiter’s Algorithm.

The exploiter needs to compute a worst-case best-response for each stage game.
First, the exploiter can run Algorithm 1 to compute the optimal values
$V^{*}_{hv}(s)$ that it can use to compute the matrix $Q^{*}_{hv}(s)$ through
Equation 4. Note, the exploiter can accurately compute the victim’s
$Q^{*}_{hv}(s)$ since the maximin value of each future-time stage game,
$V_{(h+1)v}^{*}(s^{\prime})$, is unique. Next, for each $h,s$ in backward
order, it computes $Q^{*}_{he}(s)$ using Equation 4 and the already computed
stage values $V^{*}_{(h+1)s^{\prime}}$. Then, using $V_{hv}^{*}(s)$, it solves
LP 2(b) for the bimatrix game $(Q_{hv}(s),Q_{he}(s))$ to compute a strategy
$\nu_{h}^{*}(s)$. The total product policy
$\nu^{*}=\\{\nu^{*}_{h}(s)\\}_{h,s}$ is a MPVISER for the victim. In fact, as
the victim’s algorithm is also recursive, the exploiter can simultaneously
compute both $Q^{*}_{hv}(s)$ and $Q^{*}_{he}(s)$ in a single loop. The
exploiter’s algorithm is summarized in Algorithm 2.

######  Proposition 6.

For any output $\nu^{*}$ of Algorithm 1, $\nu^{*}$ is a MPVISER strategy for
the exploiter, and $\sum_{s}\mu(s)V_{1e}^{*}(s)=p_{e}$ is the exploiter’s
guaranteed payoff for the game. Furthermore, the set of all VISER strategies
for the exploiter in the stage game $(h,s)$ is the non-empty projection
polytope:

$\hat{N}_{hs}:=\bigcup_{w\in\mathbb{R}^{m}_{\geq
0}}\left\\{\nu_{h}(s)\in\Delta(m)|e_{i}^{\top}Q^{*}_{he}(s)\nu_{h}(s)+(V_{hv}^{*}(s)1^{\top}-e_{i}^{\top}Q^{*}_{hv}(s))w\geq
p_{he}(s)\ \forall i\in[n]\right\\}.$

and the set of MPVISER policies for the game is the non-empty polytope:
$\bigcap_{h,s}N^{*}_{hs}=\bigtimes_{h,s}\hat{N}_{hs}$.

Observe the computations the players must perform in Algorithm 1 and Algorithm
2 can be carried out independently and using only the information available to
them. We also note the algorithms’ runtimes are dominated by the time to solve
$O(H|S|)$ LPs. Each individual LP has polynomially many variables and
constraints with respect to the size of the original Markov game, so can be
solved in polynomial time. As there are polynomially many such LPs, each
player’s algorithm runs in polynomial time.

######  Theorem 3.

Both players can independently compute a MPVISER policy for a general-sum
Markov game in polynomial time.

##  6 Experiments

We illustrate VISER on a generalization of the game from Figure 1(c) and
uniformly random games222Code is available at
https://github.com/jermcmahan/VISER.. Let $A$ and $B$ denote the payoff
matrices from Figure 1(c) with choice of $x=10$ and $y=10$. We consider the
block-diagonal generalizations (with $r$ blocks) defined by,

$\hat{A}=\begin{pmatrix}A&0&\ldots&0\\\ 0&A&\ldots&0\\\
\vdots&\vdots&\ldots&\vdots\\\ 0&0&\ldots&A\end{pmatrix}\text{ and
}\hat{B}=\begin{pmatrix}B&0&\ldots&0\\\ 0&B&\ldots&0\\\
\vdots&\vdots&\ldots&\vdots\\\ 0&0&\ldots&B\end{pmatrix}$

It is easy to verify the form of VISER solution for $(\hat{A},\hat{B})$. The
victim chooses either M or U in each block and evenly mixes between them.
Formally, the victim’s strategy $x$ must satisfy $x_{3i}=0$,
$x_{3i-2}+x_{3i-1}=1/r$, $x_{3i-2}\not=x_{3i-1}$, and $x_{i}\in\\{0,1/r\\}$.
The payoff the victim receives is then $p_{v}=10/r$. The exploiter’s best
response to this set of strategies is any odd column, which achieves it payoff
of at least $p_{e}=10/r$.

We then extend these bimatrix games into Markov games. We define $S=[10]$,
$A=[n]\times[m]$, and $H=10$. The reward matrices are exactly $\hat{A}$ and
$\hat{B}$ at each step: $R_{hv}(s)=\hat{A}$ and $R_{he}(s)=\hat{B}$ for all
$h,s$. For simplicity, we equip the game with uniform transitions
$P(s^{\prime}\mid s,a,b)=\frac{1}{|S|}$. Lastly, we assume the initial state
is state $1$. Given the uniform transition and identical per-step payoff
matrices, the MPVISER solution just consists of a VISER to each per-step game
(each stage game is just the original game plus $(H-h)$ times a constant and
so solutions are not affected). Thus, the expected values are at least
$p_{v}=10H/r$ and $p_{e}=10H/r$ respectively.

(a) Victim

(b) Exploiter

(c) Time

Figure 4: Block Diagonal Example

Running Algorithm 1 on these Markov games with $r$ varying (and thus the
number of entries varying) yields the plot in Figure 4(a). Here, the baseline
curve corresponds to plotting the computed $p_{v}$, the payoff curve
corresponds to plotting $V_{v}^{\pi^{*},\nu^{*}}$ (the actual value achieved),
and the analytic curve corresponds to plotting the exact formula we derived
for $p_{v}=10H/r$. We see that all three match nearly exactly for this game.
We also run Algorithm 2 on the game to create Figure 4(b). Here, we see the
actual payoff achieved by the exploiter is better than the worst-case baseline
of $p_{e}$. In all cases, we see the analytic solution matches the computed
baseline and so the algorithms worked correctly. In Figure 4(c), we see the
algorithms were able to compute MPVISER solutions for Markov games with far
over a million entries (measured by $HSnm$) in under a minute (note that time
is measured in seconds). Unsurprisingly, the victim’s algorithm ran
significantly faster than the exploiter’s.

(a) Victim

(b) Exploiter

(c) Time

Figure 5: Random Game Example

We also tested the algorithms on Markov games with uniformly random
transitions (again with $|S|=H=10$), but with a uniformly-random bimatrix game
at each step. Formally, each $R_{hu}(s)\in U[-1,1]^{n\times n}$ with $n$
varying per Markov game. In such games, a MPVISER solution no longer is simply
a VISER for each bimatrix game separately. In Figure 5(a), we see that the
victim tended to achieve a value that was much higher than its baseline,
maximin, payoff. However, in Figure 5(b), we see the exploiter was unable to
do much better than its baseline payoff in such random games. Regardless, we
again see our algorithms were able to handle games with well over a million
entries in under a minute. This gives evidence of their efficiency in
practice.

##  7 Conclusions

In this paper, we studied games with an information asymmetry structure
particularly prevalent in security applications. Namely, games where a victim
player only knows its own payoff but an exploiter player knows both the
victim’s payoffs and its own. This includes any security game where the victim
would not know the true goal of the exploiter and adversarial MARL when the
exploiter hacks the actions of one of the players. We introduced a new
solution concept called VISER that is appropriate so long as the players are
uncertainty averse and so choose to maximize their worst-case payoffs.
Importantly, both players have no incentive to deviate from a VISER solution.
We then showed VISER solutions for bimatrix games can be efficiently computed
in a distributed fashion using LPs. We also defined MPVISER as the appropriate
solution concept for Markov games and showed MPVISER solutions are VISER
solutions and can also be computed efficiently in a distributed manner via
backward induction.

#### Future Work.

Although VISER addresses many concerns for games with information asymmetry,
there are still two notable directions left open. First, VISER only addresses
two player games. When many players are involved the information structures
become much more complicated. Beyond multiple players, our paper only concerns
the “planning” setting where each player’s own payoffs are known to them in
advance. One could similarly consider a learning setting where the players do
not know even their own payoffs but can learn about them by repeated play.
This direction may have connections to the theory of partially observable
Markov games.

## References

  * [1] Michele Aghassi and Dimitris Bertsimas.  Robust game theory.  Mathematical Programming, 107(1):231–273, 2006.
  * [2] Bo An, Milind Tambe, and Arunesh Sinha.  Stackelberg Security Games (SSG) Basics and Application Overview, page 485–507.  Cambridge University Press, 2017.
  * [3] Dimitris Bertsimas and John N Tsitsiklis.  Introduction to linear optimization, volume 6.  Athena scientific Belmont, MA, 1997.
  * [4] Vincent Conitzer.  On stackelberg mixed strategies.  Synthese, 193(3):689–703, 2016.
  * [5] Vincent Conitzer and Tuomas Sandholm.  Computing the optimal strategy to commit to.  In Proceedings of the 7th ACM Conference on Electronic Commerce, EC ’06, page 82–90, New York, NY, USA, 2006. Association for Computing Machinery.
  * [6] Giovanni Paolo Crespi, Davide Radi, and Matteo Rocca.  Robust games: theory and application to a cournot duopoly model.  Decisions in Economics and Finance, 40(1):177–198, 2017.
  * [7] Giovanni Paolo Crespi, Davide Radi, and Matteo Rocca.  Insights on the theory of robust games, 2020.
  * [8] George B Dantzig.  A proof of the equivalence of the programming problem and the game problem.  Activity analysis of production and allocation, 13, 1951.
  * [9] Larry G. Epstein.  A definition of uncertainty aversion.  The Review of Economic Studies, 66(3):579–608, 1999.
  * [10] Adam Gleave, Michael Dennis, Cody Wild, Neel Kant, Sergey Levine, and Stuart Russell.  Adversarial policies: Attacking deep reinforcement learning, 2021.
  * [11] John C. Harsanyi.  Games with incomplete information played by “bayesian” players, i–iii part i. the basic model.  Management Science, 14(3):159–182, 1967.
  * [12] John C. Harsanyi.  Games with incomplete information played by ‘bayesian’ players, part iii. the basic probability distribution of the game.  Management Science, 14(7):486–502, 1968.
  * [13] John C. Harsanyi.  Games with incomplete information played by “bayesian” players part ii. bayesian equilibrium points.  Management Science, 14(5):320–334, 1968.
  * [14] Bengt Holmström and Roger B. Myerson.  Efficient and durable decision rules with incomplete information.  Econometrica, 51(6):1799–1819, 1983.
  * [15] Manish Jain, James Pita, Milind Tambe, Fernando Ordónez, Praveen Paruchuri, and Sarit Kraus.  Bayesian stackelberg games and their application for security at los angeles international airport.  ACM SIGecom Exchanges, 7(2):1–3, 2008.
  * [16] Philippe Jehiel, Moritz Meyer-ter Vehn, Benny Moldovanu, and William R. Zame.  The limits of ex post implementation.  Econometrica, 74(3):585–610, 2006.
  * [17] Michael Kearns, Yishay Mansour, and Satinder Singh.  Fast planning in stochastic games.  In Proceedings of the Sixteenth Conference on Uncertainty in Artificial Intelligence, UAI’00, page 309–316, San Francisco, CA, USA, 2000\. Morgan Kaufmann Publishers Inc.
  * [18] D. Korzhyk, Z. Yin, C. Kiekintveld, V. Conitzer, and M. Tambe.  Stackelberg vs. nash in security games: An extended investigation of interchangeability, equivalence, and uniqueness.  Journal of Artificial Intelligence Research, 41:297–327, jun 2011\.
  * [19] Dmytro Korzhyk, Vincent Conitzer, and Ronald Parr.  Complexity of computing optimal stackelberg strategies in security resource allocation games.  Proceedings of the AAAI Conference on Artificial Intelligence, 24(1):805–810, Jul. 2010.
  * [20] Joshua Letchford, Liam MacDermed, Vincent Conitzer, Ronald Parr, and Charles Isbell.  Computing optimal strategies to commit to in stochastic games.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 26, pages 1380–1386, 2012.
  * [21] Fabio Maccheroni, Massimo Marinacci, and Aldo Rustichini.  Ambiguity aversion, robustness, and the variational representation of preferences.  Econometrica, 74(6):1447–1498, 2006.
  * [22] Massimo Marinacci.  Ambiguous games.  Games and Economic Behavior, 31(2):191–219, 2000.
  * [23] John Nash.  Non-cooperative games.  Annals of Mathematics, 54(2):286–295, 1951.
  * [24] James Pita, Harish Bellamane, Manish Jain, Chris Kiekintveld, Jason Tsai, Fernando Ordóñez, and Milind Tambe.  Security applications: Lessons of real-world deployment.  SIGecom Exch., 8(2), dec 2009.
  * [25] Ariel Rubinstein.  The electronic mail game: Strategic behavior under "almost common knowledge".  The American Economic Review, 79(3):385–391, 1989.
  * [26] Sailik Sengupta and Subbarao Kambhampati.  Multi-agent reinforcement learning in bayesian stackelberg markov games for adaptive moving target defense, 2020.
  * [27] L. S. Shapley.  Stochastic games*.  Proceedings of the National Academy of Sciences, 39(10):1095–1100, 1953.
  * [28] Arunesh Sinha, Fei Fang, Bo An, Christopher Kiekintveld, and Milind Tambe.  Stackelberg security games: Looking beyond a decade of success.  In Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI-18, pages 5494–5501. International Joint Conferences on Artificial Intelligence Organization, 7 2018\.
  * [29] Eric van Damme and Sjaak Hurkens.  Games with imperfectly observable commitment.  Games and Economic Behavior, 21(1):282–308, 1997.
  * [30] John von Neumann, Oskar Morgenstern, and Ariel Rubinstein.  Theory of Games and Economic Behavior (60th Anniversary Commemorative Edition).  Princeton University Press, 1944.
  * [31] Haifeng Xu, Rupert Freeman, Vincent Conitzer, Shaddin Dughmi, and Milind Tambe.  Signaling in bayesian stackelberg games.  In Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems, AAMAS ’16, page 150–158, Richland, SC, 2016. International Foundation for Autonomous Agents and Multiagent Systems.
  * [32] Haifeng Xu, Zinovi Rabinovich, Shaddin Dughmi, and Milind Tambe.  Exploring information asymmetry in two-stage security games.  Proceedings of the AAAI Conference on Artificial Intelligence, 29(1), Feb. 2015.
  * [33] Yaodong Yang and Jun Wang.  An overview of multi-agent reinforcement learning from game theoretical perspective, 2021.

##  Appendix A Proofs

This section contains all proofs for the theoretical results in the main
paper.

###  A.1 Proofs for Section 3

Proof of 1.

###### Proof.

Suppose the victim chooses any $x\not\in X^{*}$. By definition of $X^{*}$,
there must exist an exploiter strategy $y$ satisfying $x^{\top}Ay<p_{v}$.
Absent any additional information, the victim cannot assume the exploiter will
not play $y$ and so risks achieving a lower payoff than $p_{v}$. Even knowing
2 does not alleviate this risk due to the victim not knowing $B$ which would
be necessary to predict $y^{*}$. Thus, under 1, the victim must play some
$x^{*}\in X^{*}$. ∎

Proof of 2.

###### Proof.

Suppose the exploiter chooses any $y\not\in\operatorname*{BR}(X^{*})$. By
definition of $\operatorname*{BR}(X^{*})$, there must exist a victim strategy
$x^{*}\in X^{*}$ satisfying $x^{*^{\top}}By<p_{e}$. Under 1, the exploiter
knows the victim plays some strategy in $X^{*}$, but is uncertain which
security strategy is chosen. Thus, absent any additional information, the
exploiter cannot assume the victim will not play $x^{*}$ and so risks
achieving lower payoff than $p_{e}$. Thus, under 1, the victim must play some
$y^{*}\in\operatorname*{BR}(X^{*})$. ∎

For the claim that $\textup{{VISER}}\neq\varnothing$, this follows from the
fact that both $X^{*}$ and $\operatorname*{BR}(X^{*})$ are non-empty sets as
shown in Proposition 2 and Proposition 3. The proof of Theorem 1 is then
immediate.

###  A.2 Proofs for Section 4

As mentioned in the main text, the proof of Proposition 2 is immediate from
standard bimatrix game theory [8].

Proof of Proposition 3.

###### Proof.

The exploiter wishes to compute

$\operatorname*{arg\,max}_{y\in\Delta(m)}\min_{x^{*}\in X^{*}}x^{*^{\top}}By$

For any fixed $y$, we see that the minimization problem $\min_{x^{*}\in
X^{*}}x^{*^{\top}}By$ can be explicitly written as an LP:

$\displaystyle\min_{x\geq 0}$ $\displaystyle\ x^{\top}By$ s.t. $\displaystyle
z^{*}-x^{\top}Ae_{j}\leq 0\quad\forall j\in[m]$ $\displaystyle 1^{\top}x-1=0,$

where $(x^{*},z^{*})$ is any solution to LP 2(a). Next, we construct the dual
of this program. To this end, we introduce a dual vector
$w\in\mathbb{R}^{m}_{\geq 0}$ corresponding to the inequality constraints and
a dual variable $v\in\mathbb{R}$ corresponding to the equality constraint. We
multiply these dual variables by their respective constraints and add them to
the objective to get the equivalent optimization:

$\max_{w\geq 0,v}\min_{x\geq
0}x^{\top}B\nu+(z^{*}1^{\top}-x^{\top}A)w+(x^{\top}1-1)v$

By rearranging the objective to be in terms of $x$, we get:

$\max_{w\geq 0,v}\min_{x\geq 0}x^{\top}(By-Aw+1v)+z^{*}1^{\top}w-v$

Moving the terms involving $x$ into the constraints then gives the Dual:

$\displaystyle\max_{w\geq 0,\alpha}\quad$ $\displaystyle\
z^{*}1^{\top}w-\alpha$ s.t. $\displaystyle\alpha+e_{i}^{\top}By-
e_{i}^{\top}Aw\geq 0\quad\forall i\in[n],$

Applying $\max_{y\in\Delta(m)}$ outside of the Dual, yields the exploiter’s LP
2(b):

$\displaystyle\max_{y,w\in\mathbb{R}^{m},\alpha\in\mathbb{R}}\quad\
z^{*}1^{\top}w-\alpha$ s.t. $\displaystyle\alpha+e_{i}^{\top}By-
e_{i}^{\top}Aw\geq 0\quad\forall i\in[n]$ $\displaystyle 1^{\top}y=1,\quad
y\geq 0\quad w\geq 0.$

The fact that there exist optimal solutions, i.e.,
$\operatorname*{BR}(X^{*})\neq\varnothing$, follows from LP 2(b) being
feasible and bounded. Specifically, it is easily seen that choosing $y=e_{1}$,
$w=0$, and $\alpha=\max_{i\in[n]}|e_{i}^{\top}Be_{1}$ gives a feasible
solution to LP 2(b). Boundedness follows from the fact that by LP duality, LP
2(b) is value equivalent to the original problem
$\max_{y\in\Delta(m)}\min_{x\in X^{*}}x^{\top}By$, which is clearly bounded
being that $(A,B)$ is a finite bimatrix game.

Suppose that $y^{*},w^{*},\alpha^{*}$ are any solution to LP 2(b). Then, the
optimal objective is exactly $p_{e}:=z^{*}1^{\top}w^{*}-\alpha^{*}$. Any
optimal solution triple must satisfy $z^{*}1^{\top}w-\alpha=p_{e}$. Adding in
this constraint yields the polytope of optimal solutions:

$P^{*}:=\left\\{y\in\Delta(m),w\in\mathbb{R}^{m}_{\geq 0}\mid
e_{i}^{\top}By+(z^{*}1^{\top}-e_{i}^{\top}A)w\geq p_{e}\ \forall
i\in[n]\right\\}.$

To write this as a subset of the exploiter’s strategy space, we simply project
it: for any fixed $w$, the set of $y$s that satisfy the inequality are all
optimal strategies for the exploiter. By taking the union of these sets over
all $w$, we get the set of all the exploiter’s optimal strategies:

$\bigcup_{w\in\mathbb{R}^{m}_{\geq 0}}\left\\{y\in\Delta(m)\mid
e_{i}^{\top}By+(z^{*}1^{\top}-e_{i}^{\top}A)w\geq p_{e}\ \forall
i\in[n]\right\\}.$

Equivalently, we can add an existential quantifier over $w$ to get the set:

$\operatorname*{BR}(X^{*})=\left\\{y\in\Delta(m)\mid\exists
w\in\mathbb{R}_{\geq 0}^{m},\
e_{i}^{\top}By+(z^{*}1^{\top}-e_{i}^{\top}A)w\geq p_{e}\ \forall
i\in[n]\right\\}.$

Since $\operatorname*{BR}(X^{*})$ is a projection of the polytope $P^{*}$,
Corollary 2.4 in [3] implies that $\operatorname*{BR}(X^{*})$ is a polytope. ∎

The proof of Theorem 2 is immediate from Proposition 2 and Proposition 3.

###  A.3 Proofs for Section 5

For a Markov game $G$ under 2, $\textup{{VISER}}=\Pi^{*}\times N^{*}$ where,

$\Pi^{*}:=\operatorname*{arg\,max}_{\pi\in\Pi}\min_{\nu\in
N}V_{v}^{\pi,\nu}\text{ and }N^{*}:=\operatorname*{arg\,max}_{\nu\in
N}\min_{\pi\in\Pi^{*}}V_{e}^{\pi,\nu}.$

Note, absent the assumption, the max’s and min’s would be with respect to full
history dependent policies rather than only Markovian ones. We see VISER for
each stage game $(h,s)$ is given by,

$\Pi_{hs}^{*}:=\operatorname*{arg\,max}_{\pi\in\Pi}\min_{\nu\in
N}V_{hv}^{\pi,\nu}(s)\text{ and }N_{hs}^{*}:=\operatorname*{arg\,max}_{\nu\in
N}\min_{\pi\in\Pi_{hs}^{*}\cap\bigcap_{k>h,s^{\prime}}\Pi^{*}_{ks^{\prime}}}V_{he}^{\pi,\nu}(s).$

The corresponding maximum stage game values are,

$V_{hv}^{*}(s):=\max_{\pi\in\Pi}\min_{\nu\in N}V_{hv}^{\pi,\nu}(s)\text{ and
}V_{he}^{*}(s):=\max_{\nu\in
N}\min_{\pi\in\Pi_{hs}^{*}\cap\bigcap_{k>h,s^{\prime}}\Pi^{*}_{ks^{\prime}}}V_{he}^{\pi,\nu}(s).$

To simplify notation, we define
$\tilde{\Pi}_{hs}=\Pi_{hs}^{*}\cap\bigcap_{k>h,s^{\prime}}\Pi^{*}_{ks^{\prime}}$
and
$\tilde{N}_{hs}=N_{hs}^{*}\cap\bigcap_{k>h,s^{\prime}}N_{ks^{\prime}}^{*}$.
Since $V_{hu}^{\pi,\nu}(s)$ depends only the policies from time $h$ onward, we
only need to consider partial policies that are only defined at time $h$
onward starting from state $s$. Specifically, we need only consider
$\pi=\pi_{h}(s)\cdot\\{\pi_{k}(s^{\prime})\\}_{k,s^{\prime}}\in\Pi_{hs}=\Delta(n)\times\bigtimes_{k>h,s^{\prime}}\Delta(n)$
and $\nu=\nu_{h}(s)\cdot\\{\nu_{k}(s^{\prime})\\}_{k,s^{\prime}}\in
N_{hs}=\Delta(m)\times\bigtimes_{k>h,s^{\prime}}\Delta(m)$ when defining VISER
for stage games. Similarly, when applying the bellman-consistency equations,

$V_{hu}^{\pi,\nu}(s)=\operatorname*{E}_{a_{v}\sim\pi_{h}(s),a_{e}\sim\nu_{h}(s)}\left[R_{hu}(s,a_{v},a_{e})+\sum_{s^{\prime}}P_{h}(s^{\prime}\mid
s,a_{v},a_{e})V_{(h+1)u}^{\pi,\nu}(s^{\prime})\right],$ (5)

we only need to consider the partial policies from time $h+1$ onward starting
from $s^{\prime}$ in the term $V_{(h+1)u}^{\pi,\nu}(s^{\prime})$. Note, the
base case is:
$V_{Hu}^{\pi,\nu}(s)=\operatorname*{E}_{a_{v}\sim\pi_{H}(s),a_{e}\sim\nu_{H}(s)}R_{Hu}(s,a_{v},a_{e})$.

Recall, we define MPVISER to consist of policies that are VISER solutions for
each stage game simultaneously:

$\textup{{MPVISER}}=\bigcap_{h,s}\Pi^{*}_{hs}\times\bigcap_{h,s}N^{*}_{hs}.$

Here, we assume the intersection is with respect to partial policies, so
$\Pi\cap\Pi^{*}_{Hs}$ represents all full policies whose partial policy at the
last step satisfies
$\pi_{H}(s)\in\operatorname*{arg\,max}_{\pi_{H}(s)\in\Delta(n)}\min_{\nu_{H}(s)\in\Delta(m)}V_{hv}^{\pi,\nu}(s)$
only; the partial policies at other times and states are unrestricted. Observe
that if $\pi^{*}_{s}\in\Pi_{1s}^{*}$ for all $s$, then
$\pi^{*}=\\{\pi^{*}_{s}\\}_{s}\in\Pi^{*}$ and if $\nu^{*}_{s}\in N_{1s}^{*}$
for all $s$, then $\nu^{*}=\\{\nu^{*}_{s}\\}_{s}\in N^{*}$. Thus,
$\textup{{MPVISER}}\subseteq\textup{{VISER}}$. We later show that
$\textup{{MPVISER}}\neq\varnothing$.

For all $s\in S$, define

$\hat{\Pi}_{Hs}=\operatorname*{arg\,max}_{\pi_{H}(s)\in\Delta(n)}\min_{\nu_{H}(s)\in\Delta(m)}\operatorname*{E}_{a_{v}\sim\pi_{H}(s),a_{e}\sim\nu_{H}(s)}R_{Hv}(s,a_{v},a_{e}),$

and for all $h<H$,

$\hat{\Pi}_{hs}=\operatorname*{arg\,max}_{\pi_{h}(s)\in\Delta(n)}\min_{\nu_{h}(s)\in\Delta(m)}\operatorname*{E}_{a_{v}\sim\pi_{H}(s),a_{e}\sim\nu_{H}(s)}\left[R_{hv}(s,a_{v},a_{e})+\sum_{s^{\prime}}P_{h}(s^{\prime}\mid
s,a_{v},a_{e})V^{*}_{hv}(s^{\prime})\right].$

Note, through $Q^{*}$, Equation 4, we see these definitions are equivalent to
the ones we gave in the main text.

######  Lemma 1.

For any $s\in S$, $\tilde{\Pi}_{Hs}=\hat{\Pi}_{Hs}$ and for any $h<H$,

$\tilde{\Pi}_{hs}=\hat{\Pi}_{hs}\times\bigtimes_{s^{\prime}}\tilde{\Pi}_{(h+1)s^{\prime}}.$

Furthermore,

$\tilde{\Pi}_{hs}=\hat{\Pi}_{hs}\times\bigtimes_{k>h,s^{\prime}}\hat{\Pi}_{ks^{\prime}}\neq\varnothing.$

###### Proof.

The lemma follows immediately from standard zero-sum Markov game theory [27,
30]. A direct proof can also be seen as a special case of the exploiter’s
argument that we provide next. ∎

The proof of Proposition 5 is then immediate from Proposition 2 and Lemma 1.

#### Optimality Equations.

To prove the correctness of the exploiter’s algorithm, we first derive
bellman-optimality-like equations for the exploiter’s stage value.

######  Lemma 2.

For any $s\in S$, the exploiter’s VISER value $V_{he}^{*}(s)$ satisfies the
following recursive relation:

$V_{He}^{*}(s)=\max_{\nu_{H}(s)\in\Delta(m)}\min_{\pi_{H}(s)\in\hat{\Pi}_{Hs}}\operatorname*{E}_{\pi_{H}(s),\nu_{H}(s)}R_{He}(s,a_{v},a_{e}),$

and,

$V_{he}^{*}(s)=\max_{\nu_{h}(s)\in\Delta(m)}\min_{\pi_{h}(s)\in\hat{\Pi}_{hs}}\operatorname*{E}_{\pi_{h}(s),\nu_{h}(s)}\left[R_{he}(s,a_{v},a_{e})+\sum_{s^{\prime}}P_{h}(s^{\prime}\mid
s,a_{v},a_{e})V^{*}_{(h+1)e}(s^{\prime})\right],$

where $a_{v}\sim\pi_{h}(s)$ and $a_{e}\sim\nu_{h}(s)$ in both expectations.

###### Proof.

We proceed by induction on $h$. For the base case, consider the final time
step $h=H$ and fix any $s\in S$. By the bellman-consistency equations 5, we
know that for any $\pi$ and $\nu$,
$V_{He}^{\pi,\nu}(s)=\operatorname*{E}_{\pi_{H}(s),\nu_{H}(s)}R_{He}(s,a_{v},a_{e})$.
We also know that by Lemma 1 that $\tilde{\Pi}_{Hs}=\hat{\Pi}_{hs}$ and by the
definition of the set of partial policies $N_{Hs}=\Delta(m)$. Putting these
together shows,

$\displaystyle V^{*}_{He}(s)$ $\displaystyle=\max_{\nu\in
N_{Hs}}\min_{\pi\in\tilde{\Pi}_{Hs}}V^{\pi,\nu}_{He}(s)$
$\displaystyle=\max_{\nu\in
N_{Hs}}\min_{\pi\in\tilde{\Pi}_{Hs}}\operatorname*{E}_{\pi_{H}(s),\nu_{H}(s)}R_{He}(s,a_{v},a_{e})$
$\displaystyle=\max_{\nu_{h}(s)\in\Delta(m)}\min_{\pi_{h}(s)\in\hat{\Pi}_{Hs}}\operatorname*{E}_{\pi_{H}(s),\nu_{H}(s)}R_{He}(s,a_{v},a_{e}).$

For the inductive step, consider any time step $h<H$ and fix any $s\in S$.
Applying the bellman-consistency equations 5 to the definition of
$V^{*}_{he}(s)$ yields:

$V^{*}_{hs}(s)=\max_{\nu\in
N_{hs}}\min_{\pi\in\tilde{\Pi}_{hs}}\operatorname*{E}_{a_{v}\sim\pi_{h}(s),a_{e}\sim\nu_{h}(s)}\left[R_{hu}(s,a_{v},a_{e})+\sum_{s^{\prime}}P_{h}(s^{\prime}\mid
s,a_{v},a_{e})V_{(h+1)u}^{\pi,\nu}(s^{\prime})\right].$

Observe that the expression decomposes: the expectation only considers the
policies at the current state and time, $(\pi_{h}(s),\nu_{h}(s))$, and the
summation only considers the policies at future time steps,
$\Pi_{(h+1)s^{\prime}}\times N_{(h+1)s^{\prime}}$. Consequently, we can break
down the $\max_{\nu\in N_{hs}}$ into the separate optimizations:
$\max_{\nu_{h}(s)\in\Delta(m)}$ and $\max_{\nu\in N_{(h+1)s^{\prime}}}$ for
each $s^{\prime}\in S$. Similarly, from Lemma 1 we know that
$\tilde{\Pi}_{hs}=\hat{\Pi}_{hs}\times\bigtimes_{s^{\prime}}\tilde{\Pi}_{(h+1)s^{\prime}}$
and so we can break down the $\min_{\pi\in\tilde{\Pi}_{hs}}$ into the separate
optimizations: $\min_{\pi_{h}(s)\in\hat{\Pi}_{hs}}$ and
$\min_{\pi\in\tilde{\Pi}_{(h+1)s^{\prime}}}$ for each $s^{\prime}\in S$. This
yields the equivalent optimization:

$\max_{\nu_{h}(s)\in\Delta(m)}\max_{\nu\in\bigtimes_{s^{\prime}}N_{(h+1)s^{\prime}}}\min_{\pi_{h}(s)\in\hat{\Pi}_{hs}}\min_{\pi\in\bigtimes_{s^{\prime}}\tilde{\Pi}_{(h+1)s^{\prime}}}\operatorname*{E}_{\pi_{h}(s),\nu_{h}(s)}\left[\ldots\right].$

Now, consider the summation term inside of the optimization:

$\operatorname*{E}_{\pi_{h}(s),\nu_{h}(s)}\left[\sum_{s^{\prime}}P_{h}(s^{\prime}\mid
s,a_{v},a_{e})V_{(h+1)e}^{\pi,\nu}(s^{\prime})\right].$

We can apply linearity of expectation to get the equivalent term:

$\sum_{s^{\prime}}\operatorname*{E}_{\pi_{h}(s),\nu_{h}(s)}\left[P_{h}(s^{\prime}\mid
s,a_{v},a_{e})V_{(h+1)e}^{\pi,\nu}(s^{\prime})\right].$

Also, since $V_{(h+1)e}^{\pi,\nu}(s^{\prime})$ depends only on the partial
policies at future steps, $V_{(h+1)e}^{\pi,\nu}(s^{\prime})$ is constant with
respect to $(\pi_{h}(s),\nu_{h}(s))$ so can be pulled out of the summation to
get the equivalent term:

$\sum_{s^{\prime}}V_{(h+1)e}^{\pi,\nu}(s^{\prime})\operatorname*{E}_{\pi_{h}(s),\nu_{h}(s)}\left[P_{h}(s^{\prime}\mid
s,a_{v},a_{e})\right].$

Now, by the induction hypothesis, we know for any $s^{\prime}$ at time $h+1$,

$\displaystyle V^{*}_{(h+1)e}(s^{\prime})$
$\displaystyle=\max_{\nu_{h+1}(s^{\prime})\in
N_{(h+1)s^{\prime}}}\min_{\pi_{h+1}(s^{\prime})\in\tilde{\Pi}_{(h+1)s^{\prime}}}$
$\displaystyle\operatorname*{E}_{\pi_{h+1}(s^{\prime}),\nu_{h+1}(s^{\prime})}\left[R_{(h+1)e}(s^{\prime},a_{v},a_{e})+\sum_{s^{\prime}}P_{h+1}(s^{\prime\prime}\mid
s^{\prime},a_{v},a_{e})V^{*}_{(h+2)e}(s^{\prime\prime})\right].$

Since the term $V_{(h+2)e}^{*}(s^{\prime\prime})$ is fixed and shared amongst
all $s^{\prime}$ at time $h+1$, we see the only variation in the stage value
$V^{*}_{(h+1)e}(s^{\prime})$ comes from the choice of
$(\pi_{h+1}(s^{\prime}),\nu_{h+1}(s^{\prime}))$ (i.e. varying the future
partial policy cannot increase the objective value). These can be
independently chosen for all $s^{\prime}$ at time $h+1$. Thus, the
optimization problems $\max_{\nu\in
N_{(h+1)s^{\prime}}}\min_{\pi\in\tilde{\Pi}_{(h+1)s^{\prime}}}V^{\pi,\nu}_{(h+1)e}(s^{\prime})=V^{*}_{(h+1)e}(s^{\prime})$
are separable over $s^{\prime}$. Thus, we can bring the maximin over partial
policies into the summation to get the term:

$\sum_{s^{\prime}}\max_{\nu\in
N_{(h+1)s^{\prime}}}\min_{\pi\in\tilde{\Pi}_{(h+1)s^{\prime}}}V_{(h+1)e}^{\pi,\nu}(s^{\prime})\operatorname*{E}_{\pi_{h}(s),\nu_{h}(s)}\left[P_{h}(s^{\prime}\mid
s,a_{v},a_{e})\right].$

Since $V^{*}_{(h+1)e}(s^{\prime})=\max_{\nu\in
N_{(h+1)s^{\prime}}}\min_{\pi\in\tilde{\Pi}_{(h+1)s^{\prime}}}V_{(h+1)e}^{*}(s^{\prime})$,
the expression becomes:

$\displaystyle\sum_{s^{\prime}}V_{(h+1)e}^{*}(s^{\prime})\operatorname*{E}_{\pi_{h}(s),\nu_{h}(s)}\left[P_{h}(s^{\prime}\mid
s,a_{v},a_{e})\right].$

As $V^{*}_{(h+1)e}(s^{\prime})$ is still constant with respect to
$(\pi_{h}(s),\nu_{h}(s))$, we can reverse the previous steps of pulling out
this term and applying linearity of expectation to get the final expression:

$V^{*}_{he}(s)=\max_{\nu_{h}(s)\in\Delta(m)}\min_{\pi_{h}(s)\in\hat{\Pi}_{hs}}\operatorname*{E}_{\pi_{h}(s),\nu_{h}(s)}\left[R_{he}(s,a_{v},a_{e})+\sum_{s^{\prime}}P_{h}(s^{\prime}\mid
s,a_{v},a_{e})V^{*}_{(h+1)e}(s^{\prime})\right].$

∎

#### Solutions Sets.

For any $s\in S$, inductively define:

$\hat{N}_{Hs}=\operatorname*{arg\,max}_{\nu_{H}(s)\in\Delta(m)}\min_{\pi_{H}(s)\in\hat{\Pi}_{Hs}}\operatorname*{E}_{\pi_{H}(s),\nu_{H}(s)}R_{He}(s,a_{v},a_{e}),$

and for any $h<H$,

$\hat{N}_{hs}=\operatorname*{arg\,max}_{\nu_{h}(s)\in\Delta(m)}\min_{\pi_{h}(s)\in\hat{\Pi}_{hs}}\operatorname*{E}_{\pi_{h}(s),\nu_{h}(s)}\left[R_{he}(s,a_{v},a_{e})+\sum_{s^{\prime}}P_{h}(s^{\prime}\mid
s,a_{v},a_{e})V^{*}_{(h+1)e}(s^{\prime})\right],$

to be the set of optimizers of the optimality equations for $V^{*}_{he}(s)$.

######  Corollary 1.

For any $s\in S$, $\tilde{N}_{Hs}=\hat{N}_{Hs}$ and for any $h<H$,

$\tilde{N}_{hs}=\hat{N}_{hs}\times\bigtimes_{k>h,s^{\prime}}\hat{N}_{ks^{\prime}}.$

###### Proof.

We proceed by backward induction on $h$. For the base case, consider the final
time step $h=H$ and fix any $s\in S$. We see that

$\displaystyle\tilde{N}_{Hs}$ $\displaystyle=\operatorname*{arg\,max}_{\nu\in
N_{Hs}}\min_{\pi\in\tilde{\Pi}_{Hs}}V_{He}^{\pi,\nu}(s)$
$\displaystyle=\operatorname*{arg\,max}_{\nu_{h}(s)\in\Delta(m)}\min_{\pi_{h}(s)\in\hat{\Pi}_{Hs}}V_{He}^{\pi,\nu}(s)$
$\displaystyle=\operatorname*{arg\,max}_{\nu_{h}(s)\in\Delta(m)}\min_{\pi_{h}(s)\in\hat{\Pi}_{Hs}}\operatorname*{E}_{\pi_{h}(s),\nu_{h}(s)}R_{He}(s,a_{v},a_{e})$
$\displaystyle=\hat{N}_{Hs}.$

The second equality used the definition of $N_{Hs}$ and Lemma 1. The third
equality used the bellman-consistency equations 5.

For the inductive step, consider any time $h<H$ and fix any $s\in S$. By Lemma
2, we know that

$V^{*}_{he}(s)=\max_{\nu_{h}(s)\in\Delta(m)}\min_{\pi_{h}(s)\in\hat{\Pi}_{hs}}\operatorname*{E}_{\pi_{h}(s),\nu_{h}(s)}\left[R_{he}(s,a_{v},a_{e})+\sum_{s^{\prime}}P_{h}(s^{\prime}\mid
s,a_{v},a_{e})V^{*}_{(h+1)e}(s^{\prime})\right].$

Thus, it is clear that $\nu^{*}\in N_{hs}^{*}$ if and only if
$\nu_{h}(s)^{*}\in\hat{N}_{hs}$ and $\nu^{*}\in N^{*}_{(h+1)s^{\prime}}$ for
all reachable $s^{\prime}$ and $\nu^{*}\in N_{(h+1)s^{\prime}}$ is
unconstrained for unreachable $s^{\prime}$. Then, we see that $N^{*}_{hs}\cap\
\bigcap_{s^{\prime}}N^{*}_{(h+1)s^{\prime}}=\hat{N}_{hs}\times\
\bigtimes_{s^{\prime}}N^{*}_{(h+1)s^{\prime}}$. Applying these facts to the
definition of $\tilde{N}_{hs}$ gives,

$\displaystyle\tilde{N}_{hs}$
$\displaystyle=N_{hs}^{*}\cap\bigcap_{k>h,s^{\prime}}N_{ks^{\prime}}^{*}$
$\displaystyle=(N^{*}_{hs}\cap\bigcap_{s^{\prime}}N^{*}_{(h+1)s^{\prime}})\cap\bigcap_{k>h+1,s^{\prime}}N_{ks^{\prime}}^{*}$
$\displaystyle=(\hat{N}_{hs}\times\bigtimes_{s^{\prime}}N^{*}_{(h+1)s^{\prime}})\cap\bigcap_{k>h+1,s^{\prime}}N_{ks^{\prime}}^{*}$
$\displaystyle=\hat{N}_{hs}\times\bigtimes_{s^{\prime}}(N^{*}_{(h+1)s^{\prime}}\cap\bigcap_{k>h+1,s^{\prime}}N_{ks^{\prime}}^{*})$
$\displaystyle=\hat{N}_{hs}\times\bigtimes_{s^{\prime}}\tilde{N}_{(h+1)s^{\prime}}$
$\displaystyle=\hat{N}_{hs}\times\bigtimes_{s^{\prime}}\bigtimes_{k>h}\tilde{N}_{ks^{\prime}}$
$\displaystyle=\hat{N}_{hs}\times\bigtimes_{k>h,s^{\prime}}\hat{N}_{ks^{\prime}}.$

The second to last line used the induction hypotheses. ∎

#### Algorithm Correctness.

Now, observe that by definition of $Q^{*}$, Equation 4,

$\displaystyle V^{*}_{he}(s)$
$\displaystyle=\max_{\nu_{h}(s)\in\Delta(m)}\min_{\pi_{h}(s)\in\hat{\Pi}_{hs}}\operatorname*{E}_{\pi_{h}(s),\nu_{h}(s)}\left[R_{he}(s,a_{v},a_{e})+\sum_{s^{\prime}}P_{h}(s^{\prime}\mid
s,a_{v},a_{e})V^{*}_{(h+1)e}(s^{\prime})\right]$
$\displaystyle=\max_{\nu_{h}(s)\in\Delta(m)}\min_{\pi_{h}(s)\in\hat{\Pi}_{hs}}\pi_{h}(s)^{\top}Q^{*}_{he}(s)\nu_{h}(s)$
$\displaystyle=val(LP~{}\ref{equ: exploiter-
LP}(Q^{*}_{hv}(s),Q^{*}_{he}(s))).$

Thus, we see at any stage $(s,h)$, $\nu^{*}_{h}(s)$ computed from LP 2(b)
satisfies $\nu^{*}_{h}(s)\in\hat{N}_{hs}$ and so the total partial policy
$\nu^{*}$ computed by Algorithm 2 satisfies
$\nu^{*}\in\hat{N}_{hs}\times\bigtimes_{k>h,s^{\prime}}\hat{N}_{ks^{\prime}}$.
By Corollary 1, we see that $\nu^{*}\in\tilde{N}_{hs}$. Thus, the final policy
constructed by Algorithm 2 satisfies $\nu^{*}\in\bigcap_{h,s}N^{*}_{hs}$ and
so is a MPVISER policy for the exploiter.

Inductively, we also see using Proposition 3 that
$\tilde{N}_{hs}\neq\varnothing$ and so $\textup{{MPVISER}}\neq\varnothing$
completing the proof of Proposition 4. Applying Proposition 3 then shows
$\hat{N}_{hs}$ has the form that appears in the main text. Corollary 1 also
implies that $\bigcap_{h,s}N^{*}_{hs}=\bigtimes_{h,s}\hat{N}_{hs}$, which
completes the proof of Proposition 6.

The proof of Theorem 3 is then immediate from the argument in the main text
along with Proposition 5 and Proposition 6.