Additive Security Games: Structure and Optimization

# ADDITIVE SECURITY GAMES: STRUCTURE AND OPTIMIZATION

JOE CLANIN<EMAIL_ADDRESS>Department of Computer Science, Iowa State
University
226 Atanasoff Hall, 2434 Osborn Drive,
Ames, Iowa 50011, USA
SOURABH BHATTACHARYA  Department of Mechanical Engineering, Iowa State
University
Department of Computer Science, Iowa State University
Ames, Iowa 50011, USA
<EMAIL_ADDRESS>
((Day Month Year); (Day Month Year))

###### Abstract

In this work, we provide a structural characterization of the possible Nash
equilibria in the well-studied class of security games with additive utility.
Our analysis yields a classification of possible equilibria into seven types
and we provide closed-form feasibility conditions for each type as well as
closed-form expressions for the expected outcomes to the players at
equilibrium. We provide uniqueness and multiplicity results for each type and
utilize our structural approach to propose a novel algorithm to compute
equilibria of each type when they exist. We then consider the special cases of
security games with fully protective resources and zero-sum games. Under the
assumption that the defender can perturb the payoffs to the attacker, we study
the problem of optimizing the defender expected outcome at equilibrium. We
show that this problem is weakly NP-hard in the case of Stackelberg equilibria
and multiple attacker resources and present a pseudopolynomial time procedure
to solve this problem for the case of Nash equilibria under mild assumptions.
Finally, to address non-additive security games, we propose a notion of
nearest additive game and demonstrate the existence and uniqueness of a such a
nearest additive game for any non-additive game.

###### keywords:

Security Games, Nash Equilibrium, Optimization

Subject Classification: 91A68.

##  1 Introduction

The allocation of limited resources by interacting agents has long been a
fundamental object of study in game theory. Classical examples include Colonel
Blotto games ([Gross and Wagner (1950), Hausken(2012), Bhurjee(2016)]), Gale’s
games of finite resources ([Ferguson and Melolidakis (2000)]) such as
inspection games or goofspiel, and fair division problems ([Brams _et al._
(1996)]). Two-player non-cooperative resource allocation games have been the
subject of extensive study. In such games, adversaries such as auditors and
auditees in the case of audit games ([Blocki _et al._ (2013), Blocki _et al._
(2015)]), attackers and defenders in security domains ([Alpcan and Başar
(2010), Manshaei _et al._ (2013), Hausken(2017), Hausken(2021)]), or
environmental regulators and polluting agents ([Perera(2022)]) compete to
allocate their limited resources over some collection of objects. The latter
class of games, known as security games, feature a defender with some limited
number of defensive resources to protect a set of targets and a resource-
constrained attacker seeking to attack some collection of these targets. Such
games are the subject of the present work.

A common assumption in the literature of security games is that targets
exhibit an independence property known as additivity. Informally, players
receive payoffs only for targets that are attacked and the total payoff to a
player for a given set of attacked targets is the sum of their payoffs for
each target. Non-additive security games have received significantly less
attention than additive games. The polynomial time computability of Nash and
Stackelberg equilibria in Non-additive games are addressed by [Xu (2016), Wang
_et al._ (2017), Wang and Shroff (2017)] in which it is shown that equilibrium
computation in general non-additive security games is NP-hard and that the
polynomial time solvable class of such games can be characterized in terms of
the combinatorial problem encoded by the defender pure strategy space.
Intuitively, the assumption of additivity allows for compact representation of
security games leading to efficient solution algorithms. The existing
literature on additive security games is stratified by several key factors:

  * •

Whether or not the game is zero-sum

  * •

The number of resources available to the attacker: single versus multiple

  * •

The manner of play: Nash equilibria in simultaneous games and Stackelberg
equilibria in leader-follower games

  * •

Size and structure of schedules: some resources may be able to cover multiple
targets

  * •

The homogeneity or heterogeneity of the player resources: whether or not all
resources are applicable to all schedules

  * •

Resource protection: whether or not resources are fully protective in the
sense that no payoff is received when an attacked target is also covered by
the defender

The standard multiple LP approach ([Conitzer and Sandholm (2006)]) for
computing Stackelberg equilibria requires time which is polynomial in the
number of player pure strategies. Thus, in security games where a player has
multiple resources and pure strategies correspond to choosing a particular
subset of targets, alternative solution methods must be devised to render the
problem tractable. The first efficient algorithm to compute a Stackelberg
equilibrium in security games with a single attacker resource was proposed in
[Kiekintveld _et al._ (2009)]. This procedure, entitled ‘Efficient Randomized
Allocation of Security Resources’ or ERASER, employs a mixed-integer linear
programming approach to address the case of singleton schedules and
homogeneous resources. Then, after eliminating the assumption that assigning
more than one defensive resource does not benefit the defender or harm the
attacker any more than a single resource (an assumption made by the present
work and by all other works discussed herein), [Kiekintveld _et al._ (2009)]
also proposes an algorithm, ORIGAMI, to compute a Stackelberg equilibrium and
verifies its efficacy through simulation. The relationship between Stackelberg
equilibria and Nash equilibria in security games is studied in [Korzhyk _et
al._ (2011b)]. This work shows that Stackelberg equilibria are also Nash
equilibria in the case of a single attacker resource and under the assumption
that any subset of a schedule is also a schedule but that this need not be the
case when the attacker is allowed more than a single resource. A game is said
to have interchangeable Nash equilibria if any profile in which both players
are playing some equilibrium strategy is itself a Nash equilibrium. A further
result of [Korzhyk _et al._ (2011b)] is that Nash equilibria in additive
security games are interchangeable, and thus there is no equilibrium selection
problem in such games. Equilibria in games with multiple attacker resources
were first addressed by [Korzhyk _et al._ (2011b)], but the authors propose no
efficient solution algorithm and provide only experimental results for the
sake of comparison of the properties of games with varying player resource
counts and manners of play. The first polynomial time algorithm to compute
Nash equilibria in games with multiple attacker resources is given in [Korzhyk
_et al._ (2011a)]. This procedure begins by solving a game in which the
defender has no resources, gradually increases the resources available to the
defender, and transitions between a number of phases in which the player best
responses are computed until the final number of defender resources is
reached. While effective, this quadratic time procedure and its description do
little to elucidate the underlying structure of Nash equilibria in additive
security games.

All approaches to the efficient computation of equilibria (both Nash and
Stackelberg when tractable) in additive security games rely upon the compact
representation of player strategies in terms of marginal probabilities rather
than explicit mixed strategies represented as distributions over exponentially
large pure strategy spaces. This raises the question of whether or not the
computed marginal probabilities can actually be implemented by some pure
strategy. This question is completely resolved for Stackelberg equilibria by
[Korzhyk _et al._ (2010)] wherein the authors demonstrate that in the case of
homogeneous resources and schedules of size at most 2 or in the case of
heterogeneous resources and singleton schedules, such a pure strategy can be
computed in polynomial time. The problem is shown to be NP-hard in all other
cases, even for zero-sum games. Furthermore, existing approaches to
equilibrium computation are shown to have the capability to produce solutions
in terms of marginal probability which are not implementable by any mixed
strategy when schedules exceed size 2. In light of this complexity result for
games with arbitrary schedules and owing to the fact that such schedules are
essential elements of real-world security game implementations such as those
utilized by the U.S. Federal Air Marshals (FAMS) ([Tambe (2011)]), a branch-
and-bound approach to equilibrium computation in games with arbitrary
schedules and a single attacker resource is proposed in [Jain _et al._(2010)].
This algorithm, ASPEN (Accelerated SPARS Engine), generates branching rules
and bounds using ORIGAMI and is shown to exhibit significant performance
improvements over previously existing techniques. Another approach to
circumventing the hardness results given in [Korzhyk _et al._ (2010)] is
studied in [Letchford and Conitzer (2013)] wherein a class of security games
on graphs whose schedules satisfy a necessary condition for implementability
given by the Bihierarchy Birkhoff-Von Neumann theorem ([Budish _et al._
(2013)]). Positive results regarding polynomial time Stackelberg equilibrium
computation are given for games with heterogeneous or homogeneous defender
resources in which the schedules have the structure of paths in a collection
of rooted trees or paths in a path graph (respectively).

A $O(n)$ procedure to compute a Stackelberg equilibrium in games with a single
attacker resource, singleton homogeneous schedules, and resources that are
fully protective in the sense that the attacker receives no payoff when an
attacked target is defended (but the defender may incur some cost) is proposed
by [Lerma _et al._ (2011)]. It is also shown that this algorithm can be
modified to compute Stackelberg equilibria in $O(n\log(n))$ time for with all
of the same assumptions, but non-fully-protective resources. More recent work
([Emadi and Bhattacharya (2019), Emadi and Bhattacharya (2020a)]) has shown
that for zero-sum games with homogeneous singleton schedules, multiple
attacker resources and fully protective resources, there exists a $O(n)$
procedure to compute Nash equilibria. In this work, we extend the structural
approach adopted in [Emadi and Bhattacharya (2019), Emadi and Bhattacharya
(2020a)] to study Nash equilibria in general sum security games with multiple
attacker resources.

In many security settings, it is reasonable to assume that a defender can
alter the payoff structure of the game. Defenders may artificially increase
the vulnerability or inflate the perceived importance of certain targets to
address their true incentives regarding the task of attack mitigation. A
natural optimization problem of maximizing the defender expected utility at
equilibrium in a security game given the possibility of perturbation of the
game parameters by the defender is addressed in [Shi _et al._ (2018)]. The
authors propose a mixed integer linear program approach with an approximation
guarantee to solve this problem under a weighted $L^{1}$ norm constraint as
well as a polynomial time approximation scheme for a restricted version of the
problem. Furthermore, when attacker payoffs are restricted to closed bounded
intervals, it is shown that the optimization problem can be solved in
$O(n^{2}\log(n))$ time by utlizing a modified version of ORIGAMI. The
approaches in [Shi _et al._ (2018)], however, only address the case of
Stackelberg equilibria and a single attacker resource. As mentioned
previously, by [Korzhyk _et al._ (2011b)] this implies that the optimization
problem the case of Nash equilibria in games with a single attacker resource
can be solved in polynomial time but leaves open the case of Nash equilibria
and multiple attacker resources.

We make the following contributions to the theory of general-sum additive
security games with singleton schedules and multiple homogeneous attacker and
defender resources:

  1. 1.

By leveraging necessary structural properties of Nash equilibria, we give a
characterization of the possible Nash equilibria into seven types and
demonstrate the existence of a game exhibiting each type.

  2. 2.

We provide feasibility conditions for each type of equilibrium and propose a
novel $O(m^{3})$ algorithm to compute equilibria based upon our structural
analysis which is far more intuitive than existing approaches.

  3. 3.

In the case of fully protective resources, we show that only five types of
Nash equilibria are possible and that our equilibrium computation algorithm
can be made to run in $O(m^{2})$ time.

  4. 4.

For all types of equilibria, we derive closed-form expressions for the player
equilibrium strategies and expected outcomes at equilibrium and characterize
the uniqueness and multiplicity of the various types of equilibria.

  5. 5.

Under the assumption that the defender can perturb the payoffs to the
attacker, we show that the problem of maximizing the expected outcome to the
defender is weakly NP-hard in the case of Stackelberg equilibria and multiple
attacker resources.

  6. 6.

We propose a pseudopolynomial time procedure based upon our theory of types to
find a globally optimal solution to the problem of maximizing defender
expected utility in the case of Nash equilibria under a disjointness
assumption.

  7. 7.

We propose a notion of nearest additive game and demonstrate the existence and
uniqueness of such a game for any (potentially non-additive) security game.

###  1.1 Security Game Formulation

We now formulate the security game model to be considered in this work. Define
a two player game between an attacker and defender over a target set
$T=\\{1,\dots,m\\}$. The attacker will attack $1\leq k_{a}<m$ targets and the
defender will defend $1\leq k_{d}<m$ targets. We assume that at most one
resource is allocated to a target, an assumption introduced in [Korzhyk _et
al._ (2011a)]. If a target is defended, we say the target is ‘covered’, and if
a target is not defended we shall say this target is ‘uncovered’. Let
$U_{a}^{c}:2^{T}\to(0,\infty)$ and $U_{a}^{u}:2^{T}\to(0,\infty)$ be functions
giving the payoff to the attacker when a set of attacked targets is covered
and uncovered, respectively. Similarly define
$U_{d}^{c},U_{d}^{u}:2^{t}\to(-\infty,0)$ giving the costs to the defender. We
assume the payoffs satisfy

$\Delta_{a}(S)=U_{a}^{u}(S)-U_{a}^{c}(S)>0\hskip 10.00002pt\text{ and }\hskip
10.00002pt\Delta_{d}(S)=U_{d}^{c}(S)-U_{d}^{u}(S)>0.$ (1)

That is, when a set of targets is attacked, it is better for the defender that
the targets are defended and better for the attacker that the targets remain
exposed. Let $s_{1}^{a},\dots,s_{\binom{m}{k_{a}}}^{a}\subseteq T$ be the pure
strategies of the attacker and let
$s_{1}^{d},\dots,s^{d}_{\binom{m}{k_{d}}}\subseteq T$ be the pure strategies
of the defender. The payoffs to the attacker and defender for a given pure
strategy profile $s_{i}^{a},s_{j}^{d}$ are

$U_{a}^{c}(s_{i}^{a}\cap s_{j}^{d})+U_{a}^{u}(s_{i}^{a}\setminus
s_{j}^{d})\text{ and }U_{d}^{c}(s_{i}^{a}\cap
s_{j}^{d})+U_{d}^{u}(s_{i}^{a}\setminus s_{j}^{d})$

respectively. Denote the payoff matrices to the attacker and defender by $A$
and $B$ respectively. By convention we assume the attacker is the row player.
We say that a security game is additive if the payoff functions are additive
over attacked targets. That is, $U_{a}^{c}(S)=\sum_{t\in
S}U_{a}^{c}(\\{t\\})$, and the same is true for
$U_{a}^{u},U_{d}^{c},U_{d}^{u}$. For convenience we will omit braces when
payoff functions are evaluated at singletons. As noted in the previous
section, the case of additive payoff functions is a well-studied security game
model ([Kiekintveld _et al._ (2009), Korzhyk _et al._ (2010), Yin _et al._
(2010), Korzhyk _et al._ (2011b), Korzhyk _et al._ (2011a), Emadi and
Bhattacharya (2019), Emadi and Bhattacharya (2020a), Emadi and Bhattacharya
(2020b), Emadi _et al._ (2021)]). All security games under consideration,
unless stated otherwise, will be assumed to have additive payoff functions.

Under the assumption of additive payoffs, the expected outcome for each player
at equilibrium depends only upon the marginal probabilities with which each
target is attacked and defended. That is:

$\displaystyle v_{a}$
$\displaystyle=p^{T}Aq=\sum_{t=1}^{m}\left[\alpha_{t}U_{a}^{c}(t)\beta_{t}+\alpha_{t}U_{a}^{u}(t)(1-\beta_{t})\right]$
(2) $\displaystyle v_{d}$
$\displaystyle=p^{T}Bq=\sum_{t=1}^{m}\left[\alpha_{t}U_{d}^{c}(t)\beta_{t}+\alpha_{t}U_{d}^{u}(t)(1-\beta_{t})\right]$

Where $\alpha=[\alpha_{1},\dots,\alpha_{m}]^{T}$ and
$\beta=[\beta_{1},\dots,\beta_{m}]^{T}$ are the attack and defense probability
vectors (respectively) given by

$\alpha_{i}=\sum_{i\in S^{a}_{t}}p_{t}\hskip 10.00002pt\text{ and }\hskip
10.00002pt\beta_{i}=\sum_{i\in S^{d}_{t}}q_{t}.$

Note that $\alpha_{i},\beta_{i}\in[0,1]$ (since $p,q$ are probability vectors)
and

$\sum_{i=1}^{m}\alpha_{i}=k_{a}\hskip 10.00002pt\text{ and }\hskip
10.00002pt\sum_{i=1}^{m}\beta_{i}=k_{d}$ (3)

It is worth noting that no information is lost by utilizing the compact
representation given by (2). It is noted in [Korzhyk _et al._ (2010)] that a
mixed strategy $(p^{*},q^{*})$ which realizes any given
$(\alpha^{*},\beta^{*})$ can be computed in $O(m^{4.5})$ time by utilizing the
Birkhoff-Von Neumann theorem ([Horn and Johnson (2012)]) to decompose a doubly
stochastic matrix into a convex combination of permutation matrices. In
general such a $(p^{*},q^{*})$ need not be unique. We rephrase the definition
of Nash equilibrium in terms of the compact representation (2) as follows:

######  Definition 1.1.

A pair $(\alpha^{*},\beta^{*})$ is a Nash equilibrium if for all
$\alpha,\beta$

$v_{a}(\alpha,\beta^{*})\leq v_{a}(\alpha^{*},\beta^{*})\hskip
10.00002pt\text{ and }\hskip 10.00002ptv_{d}(\alpha^{*},\beta)\leq
v_{d}(\alpha^{*},\beta^{*}).$

##  2 Results

We now present our structural approach to equilibrium computation in additive
security games.

###  2.1 Structural Analysis of Nash Equilibria

The following key observation is central to our analysis:

###### Observation 1

Due to (2), a player can unilaterally deviate from $(\alpha,\beta)$ if and
only if they are able to shift marginal probability from one target to
another. By definition, therefore, if $(\alpha^{*},\beta^{*})$ is a Nash
equilibrium:

$\displaystyle\alpha_{i}^{*}>0,\alpha_{j}^{*}<1$ $\displaystyle\implies
U_{a}^{c}(j)\beta_{j}+U_{a}^{u}(j)(1-\beta_{j})\leq
U_{a}^{c}(i)\beta_{i}+U_{a}^{u}(i)(1-\beta_{i})$
$\displaystyle\beta_{i}^{*}>0^{,}\beta_{j}^{*}<1$
$\displaystyle\implies\alpha_{j}\Delta_{d}(j)\leq\alpha_{i}\Delta_{d}(i)$

That is, no player can unilaterally deviate and increase their expected
payoff.

${{\beta_{i}^{*}}}$ ${{\alpha_{i}^{*}}}$ | $=0$ | $\in(0,1)$ | $=1$
---|---|---|---
$=0$ | $i\in I_{1}$ | $i\in I_{2}$ | $i\in I_{3}$
$\in(0,1)$ | $i\in I_{4}$ | $i\in I_{5}$ | $i\in I_{6}$
$=1$ | $i\in I_{7}$ | $i\in I_{8}$ | $i\in I_{9}$
Table 1: Definition of the sets $I_{1},\dots,I_{9}$. For example, $I_{8}$ is
the set $\\{i:\alpha_{i}\in(0,1),\beta_{i}=1\\}$.

We make the following assumption regarding the game parameters:

###### Assumption 1

The parameters
$U_{a}^{c}(1),\dots,U_{a}^{c}(m),U_{a}^{u}(1),\dots,U_{a}^{u}(m)$ are distinct
and the parameters $\Delta_{d}(1),\dots,\Delta_{d}(m)$ are distinct.

To make use of Observation 1, for any $(\alpha^{*},\beta^{*})$ we define a
partition of the target set into nine sets $I_{1},\dots,I_{9}$ defined by
Table 1.

######  Lemma 2.1.

If $(\alpha^{*},\beta^{*})$ is a Nash equilibrium and $I_{4}\cup
I_{7}\neq\emptyset$, then $I_{2}\cup I_{3}\cup I_{5}\cup I_{6}=\emptyset$.

######  Proof 2.2.

Suppose $i\in I_{4}\cup I_{7}$. Then $\alpha_{i}^{*}=0$ and
$\beta_{i}^{*}\in(0,1]$. As $k_{a}\geq 1$ there exists $j$ so that
$\alpha_{j}>0$. We must have $\beta_{j}=1$ for all $j$ such that
$\alpha_{j}>0$ (else the defender has a feasible deviation increasing their
payoff).

This yields the following theorem:

######  Theorem 2.3.

A Nash equilibrium $(\alpha^{*},\beta^{*})$ is of precisely one of the
following two types:

  * •

Type I: $\forall i\in T$, $i\in T\setminus(I_{4}\cup I_{7})$

  * •

Type II: $\forall i\in T$, $i\in I_{1}\cup I_{4}\cup I_{7}\cup I_{8}\cup
I_{9}$, $I_{4}\cup I_{7}\neq\emptyset$

By considering every pair of targets to which Observation 1 applies, we arrive
at the following lemmas which describe the necessary structural relationships
between targets in the sets $I_{1},\dots,I_{9}$ at equilibrium.

######  Lemma 2.4.

If $(\alpha^{*},\beta^{*})$ is a Nash equilibrium, then

  1. (i)

There exists a constant $c_{1}$ so that
$U_{a}^{u}(i)-\beta_{i}^{*}\Delta_{a}(i)=c_{1}$ for all $i\in I_{2}\cup
I_{5}\cup I_{8}$ . Furthermore, for all $i\in I_{2}$ we have
$c_{1}=U_{a}^{u}(i)$ and for all $i\in I_{8}$ we have $c_{1}=U_{a}^{c}(i)$.

  2. (ii)

There exists a constant $c_{2}$ so that $\alpha_{i}^{*}\Delta_{d}(i)=c_{2}$
for all $i\in I_{5}\cup I_{6}$ . Furthermore, for $i\in I_{6}$ we have
$c_{2}=\Delta_{d}(i)$.

######  Proof 2.5.

Assertion (i) follows from application of Observation 1 to the sets
$I_{2},I_{5}$ and $I_{8}$. Similarly, assertion (ii) follows from application
to $I_{5}$ and $I_{6}$.

######  Lemma 2.6.

If $(\alpha^{*},\beta^{*})$ is a Nash equilibrium, then

  1. (i)

For $i\in I_{5}\cup I_{6}\cup I_{8}\cup I_{9}$ and $j\in I_{2}\cup I_{5}$,
$\alpha^{*}_{j}\Delta_{d}(j)\leq\Delta_{d}(i)$

  2. (ii)

For $i\in I_{5}\cup I_{6}\cup I_{8}\cup I_{9}$ and $j\in I_{3}\cup I_{6}$,
$\Delta_{d}(j)\leq\Delta_{d}(i)$. Furthermore $\Delta_{d}(j)<\Delta_{d}(i)$
for $j\in I_{3},i\in I_{6}$.

  3. (iii)

For $i\in I_{5}$ and $j\in I_{6}$, $\Delta_{d}(j)\leq\Delta_{d}(i)$

######  Lemma 2.7.

If $(\alpha^{*},\beta^{*})$ is a Nash equilibrium, then

  1. (i)

For $i\in I_{2}\cup I_{3}\cup I_{5}\cup I_{6}\cup I_{8}\cup I_{9}$ and $j\in
I_{1}\cup I_{2}$, $U_{a}^{u}(j)\leq U_{a}^{u}(i)$. Furthermore,
$U_{a}^{u}(j)<U_{a}^{u}(i)$ for $j\in I_{1}$, $i\in I_{2}$.

  2. (ii)

For $i\in I_{9}$ and $j\in I_{2}\cup I_{5}\cup I_{8}$, $U_{a}^{c}(j)\leq
U_{a}^{c}(i)$. Furthermore, $U_{a}^{c}(j)<U_{a}^{c}(i)$ for $j\in I_{5},i\in
I_{8}$.

  3. (iii)

For $i\in I_{2}\cup I_{3}\cup I_{5}\cup I_{6}\cup I_{8}\cup I_{9}$ and $j\in
I_{1}\cup I_{2}\cup I_{5}\cup I_{8}$, $U_{a}^{c}(j)\leq U_{a}^{u}(i)$

In particular, Lemma 2.6 follows by considering all possible defender
deviations and Lemma 2.7 follows by considering all possible attacker
deviations.

###  2.2 Computing Nash Equilibria

We now utilize the structural characterization of Nash equilibria given in the
section 2.1 to derive a novel algorithm to compute a Nash equilibrium, its
type, and the expected outcomes to the players at equilibrium.

Note that by Assumption 1 and Lemma 2.4 we have
$|I_{2}|,|I_{6}|,|I_{8}|\in\\{0,1\\}$ and at most one of $I_{2}$ and $I_{8}$
is nonempty at equilibrium.

Define six subtypes of Type I equilibrium as follows:

| ${I_{2}=\emptyset\atop I_{8}=\emptyset}$ | ${I_{2}\neq\emptyset\atop I_{8}=\emptyset}$ | ${I_{2}=\emptyset\atop I_{8}\neq\emptyset}$
---|---|---|---
$I_{6}=\emptyset$ | Type I.A.i | Type I.A.ii | Type I.A.iii
$I_{6}\neq\emptyset$ | Type I.B.i | Type I.B.ii | Type I.B.iii

Introduce the parameters $r=|I_{1}|$, $s=|I_{3}|$ and $t=|I_{9}|$. The
equilibrium computation algorithm will function as follows: For each possible
value of the parameters $r,s,t$ and each
$\texttt{type}\in\\{$I.A.i,…,I.B.iii$\\}$ we assign targets to the sets
$I_{1},\dots,I_{9}$ according to the necessary structural properties given by
Lemmas 2.6 and 2.7. Then, utilizing the constant sum property (3) of the
marginal attack and defense probability vectors, Lemma 2.4, and the
definitions of the sets $I_{1},\dots,I_{9}$ we calculate the necessary values
of $\alpha_{i},\beta_{i}$ for each $i$ as well as $c_{1}$ and $c_{2}$ in our
candidate solution. The candidate equilibrium just constructed is then checked
for feasibility. We now give the details of the candidate equilibrium
construction for each type and a fixed $r,s,t$. When $I_{2},I_{6}$ or $I_{8}$
is nonempty, denote their single elements by $j^{[2]},j^{[6]}$ and $j^{[8]}$
respectively. Without loss of generality, assume the targets are ordered such
that $U_{a}^{u}(i)<U_{a}^{u}(j)$ for $i<j$. The following procedure assigns
the targets to the sets $I_{1},\dots,I_{9}$:

  1. 1.

By Lemma 2.7 (i), for all types we take $I_{1}=\\{1,\dots,r\\}$.

  2. 2.

If $\texttt{type}\in\\{$I.A.ii,I.B.ii$\\}$ we set $I_{2}=\\{r+1\\}$ by Lemma
2.7 (i), otherwise $I_{2}=\emptyset$.

  3. 3.

By Lemma 2.6 (ii), $I_{3}$ is taken to be the $s$ targets of least
$\Delta_{d}(i)$ in $T\setminus(I_{1}\cup I_{2})$.

  4. 4.

If $\texttt{type}\in\\{$I.B.i,I.B.ii,I.B.iii$\\}$ we let $I_{6}$ contain the
target of least $\Delta_{d}(i)$ in $T\setminus(I_{1}\cup I_{2}\cup I_{3})$ by
Lemma 2.6 (ii), otherwise $I_{6}=\emptyset$.

  5. 5.

By Lemma 2.7 (ii), we assign the $t$ targets of greatest $U_{a}^{c}(i)$ in
$T\setminus(I_{1}\cup I_{2}\cup I_{3}\cup I_{6})$ to $I_{9}$.

  6. 6.

If $\texttt{type}\in\\{$I.A.iii,I.B.iii$\\}$, by Lemma 2.7 we let $I_{8}$
contain the target of greatest $U_{a}^{c}(i)$ in $T\setminus(I_{1}\cup
I_{2}\cup I_{3}\cup I_{6}\cup I_{9})$, otherwise $I_{8}=\emptyset$.

  7. 7.

Finally, $I_{5}=T\setminus(I_{1}\cup I_{2}\cup I_{3}\cup I_{6}\cup I_{8}\cup
I_{9})$.

Table 2: Expressions for $c_{1}$ and $c_{2}$ for each type of type I
equilibrium and fixed values of $r,s,t$.

| $c_{1}$ | $c_{2}$
---|---|---
I.A.i | ${t-k_{d}+\sum_{j\in I_{5}}{U_{a}^{u}(j)\over\Delta_{a}(j)}\over\sum_{j\in I_{5}}{1\over\Delta_{a}(j)}}$ | ${k_{a}-s-t\over\sum_{j\in I_{5}}{1\over\Delta_{d}(j)}}$
I.A.ii | $U_{a}^{u}(j^{[2]})$ | ${k_{a}-s-t-\alpha_{j^{[2]}}\over\sum_{j\in I_{5}}{1\over\Delta_{d}(i)}}$
I.A.iii | $U_{a}^{c}(j^{[8]})$ | ${k_{a}-s-t-\alpha_{j^{[8]}}\over\sum_{j\in I_{5}}{1\over\Delta_{d}(i)}}$

| $c_{1}$ | $c_{2}$
---|---|---
I.B.i | ${\sum_{i\in I_{5}}{U_{a}^{u}(i)\over\Delta_{a}(i)}-k_{d}+t+\beta_{j^{[6]}}\over\sum_{i\in I_{5}}{1\over\Delta_{a}(i)}}$ | $\Delta_{d}(j^{[6]})$
I.B.ii | $U_{a}^{u}(j^{[2]})$ | $\Delta_{d}(j^{[6]})$
I.B.iii | $U_{a}^{c}(j^{[8]})$ | $\Delta_{d}(j^{[6]})$

After targets are assigned to $I_{1},\dots,I_{9}$, we compute the constants
$c_{1}$ and $c_{2}$ guaranteed by Lemma 2.4 using (3). The result of this
calculation is given in Table 2. It remains to compute the necessary values of
$\alpha_{i}$ and $\beta_{i}$ for each $i$. This is done as follows:

  1. 1.

$\alpha_{i}$ and $\beta_{i}$ for targets in $I_{1},I_{3}$ and $I_{9}$ are
assigned either $0$ or $1$ according to Table 1.

  2. 2.

As required by Table 1: If $I_{2}\neq\emptyset$, set $\beta_{j^{[2]}}=0$; If
$I_{6}\neq\emptyset$, set $\alpha_{j^{[6]}}=1$; If $I_{8}\neq\emptyset$, set
$\beta_{j^{[8]}}=1$.

  3. 3.

For each $i\in I_{5}$, by Lemma 2.4 we have

$\alpha_{i}={c_{2}\over\Delta_{d}(i)}\hskip 10.00002pt\text{and}\hskip
10.00002pt\beta_{i}={U_{a}^{u}(i)-c_{1}\over\Delta_{a}(i)}$ (4)

where $c_{1}$ and $c_{2}$ are given by the current value of type and the
expressions in Table 2. If $\texttt{type}=$I.A.i, this completes the
assignment of $\alpha$ and $\beta$.

  4. 4.

If $\texttt{type}=$I.B.ii, by (3) we have

$\alpha_{j^{[2]}}=k_{a}-s-t-1-\sum_{j\in
I_{5}}{\Delta_{d}(j^{[6]})\over\Delta_{d}(j)}\hskip 10.00002pt\text{and}\hskip
10.00002pt\beta_{j^{[6]}}=k_{d}-t-\sum_{j\in
I_{5}}{U_{a}^{u}(j)-U_{a}^{u}(j_{[2]})\over\Delta_{a}(j)},$ (5)

completing the assignment of $\alpha$ and $\beta$.

  5. 5.

If $\texttt{type}=$I.B.iii, by (3) we have

$\alpha_{j^{[8]}}=k_{a}-s-t-\sum_{j\in
I_{5}}{\Delta_{d}(j^{[6]})\over\Delta_{d}(i)}\hskip 10.00002pt\text{and}\hskip
10.00002pt\beta_{j^{[6]}}=k_{d}-t-1-\sum_{j\in
I_{5}}{U_{a}^{u}(j)-U_{a}^{c}(j^{[8]})\over\Delta_{a}(j)},$ (6)

completing the assignment of $\alpha$ and $\beta$.

  6. 6.

If $\texttt{type}\in\\{I.A.ii,I.A.iii,I.B.i\\}$, the remaining single
undetermined $\alpha_{i}$ or $\beta_{i}$ is calculated (or determined not to
exist) during feasibility checking.

Once the candidate equilibrium is constructed and $\alpha$ and $\beta$ are
computed (with the possible exception of a single $\alpha_{i}$ or $\beta_{i}$
in the case of $\texttt{type}\in\\{I.A.ii,I.A.iii,I.B.i\\}$), we must verify
whether or not the construction is a feasible Nash equilibrium. The following
result, which we restate using our notation, is noted in [Korzhyk _et al._
(2011a)]:

######  Lemma 2.8.

A pair of marginal attack and defense probability vectors $(\alpha,\beta)$ is
a Nash equilibrium if and only if, for all $t\in T$

$\displaystyle\beta_{t}\neq 0$
$\displaystyle\implies\alpha_{t}\Delta_{d}(t)\geq c_{2}$
$\displaystyle\beta_{t}\neq 1$
$\displaystyle\implies\alpha_{t}\Delta_{d}(t)\leq c_{2}$
$\displaystyle\alpha_{t}\neq 0$
$\displaystyle\implies\beta_{t}U_{a}^{c}(t)+(1-\beta_{t})U_{a}^{u}(t)\geq
c_{1}$ $\displaystyle\alpha_{t}\neq 1$
$\displaystyle\implies\beta_{t}U_{a}^{c}(t)+(1-\beta_{t})U_{a}^{u}(t)\leq
c_{1}$

where $c_{1}$ and $c_{2}$ are the constants guaranteed by Lemma 2.4.

A constructed equilibrium candidate is feasible if it meets the following
conditions:

  1. 1.

For $\texttt{type}=$ I.A.ii, there exists a value of
$\alpha_{j^{[2]}}\in(0,1)$ such that:

    1. (a)

The values of $\alpha_{i},\beta_{i}$ for $i\in I_{5}$ given by (4) lie in the
interval $(0,1)$.

    2. (b)

The values of $c_{1},c_{2}$ given by Table 2 meet the conditions of Lemma 2.8.

    3. (c)

The constant sum condition (3) is met.

  2. 2.

For $\texttt{type}=$ I.A.iii, there exists a value of
$\alpha_{j^{[8]}}\in(0,1)$ such that the conditions 1.(a),(b),(c) above are
met.

  3. 3.

For $\text{type}=$ I.B.i, there exists a value of $\beta_{j^{[6]}}\in(0,1)$
such that the conditions 1.(a),(b),(c) above are met.

  4. 4.

For $\texttt{type}=$ I.B.ii or $\texttt{type}=$ I.B.iii, the values of
$\alpha$ and $\beta$ given by (5) and (6) (respectively) lie in the interval
$(0,1)$ and condition 1.(b) above is met.

  5. 5.

For $\texttt{type}=$ I.A.i, the conditions 1.(a) and 1.(b) above are met.

###### Algorithm 1

Equilibrium Computation

Input: $k_{a},k_{d},U_{a}^{u},U_{a}^{c},U_{d}^{u},U_{d}^{c}$

for $r=0:\min\\{m-k_{a},m-k_{d}\\}$ do

for $s=0:\min\\{k_{a},m-k_{d}-r\\}$ do

for $t=0:\min\\{k_{a}-s,k_{d}\\}$ do

for $\texttt{type}\in\\{$I.A.i,I.A.ii,I.A.iii,I.B.i,I.B.ii,I.B.iii$\\}$ do

if $\Gamma(r,s,t,\texttt{type})$ is feasible then

Output $(\alpha^{*},\beta^{*})$ and $(v_{a}^{*},v_{d}^{*})$

end if

end for

end for

end for

end for

Else: No Type I equilibrium exists.

For a given $r,s,t$ and type, let $\Gamma(r,s,t,\texttt{type})$ denote the
data of the candidate equilibrium corresponding to the given parameters
constructed according to the process just outlined. The Type I equilibrium
computation procedure is given by Algorithm 1.

######  Lemma 2.9.

Under Assumption 1, if $k_{d}\leq k_{a}$ no Type II equilibrium exists.

######  Proof 2.10.

First note that equation 3 must hold, and therefore $I_{8}=\emptyset$. Then,
note that in such a type II equilibrium, we have
$\sum_{i=1}^{m}\alpha_{i}=\sum_{i\in I_{9}}1=k_{a}$. Thus, if $k_{d}\leq
k_{a}$ either $I_{4}\cup I_{7}\neq\emptyset$ or
$\sum_{i=1}^{m}\beta_{i}>k_{d}$ and no type II equilibrium exists.

If $k_{d}>k_{a}$, a Type II equilibrium may exist. By Observation 1, we have
$U_{a}^{c}(i)<U_{a}^{c}(j)$ for $i\in I_{1}\cup I_{4}\cup I_{7}$ and $j\in
I_{9}$. We order $T$ so that $U_{a}^{c}(i)<U_{a}^{c}(j)$ for $i<j$ and set
$I_{9}=\\{m-k_{a}+1,\dots,m\\}$. Let $I_{7}$ contain any $k_{d}-k_{a}$
targets, and let $I_{1}$ contain any remaining targets. Note that $c_{2}=0$
and $c_{1}=U_{d}^{c}(m-k_{a}+1)$ testifies that this constructed
$(\alpha,\beta)$ is a Nash equilibrium.

######  Example 2.11.

It is straightforward to construct a game exhibiting any given type of
equilibrium and feasible parameters $r,s,t$. For example, fix some $k_{a}$ and
$k_{d}$ and constants $c_{1},c_{2}$. Let $n=\max\\{k_{a},k_{d}\\}+1$.
Construct a game on $T=\\{1,\dots,n\\}$ by taking $x_{1},\dots,x_{n}\in(0,1)$
to be distinct reals such that $\sum_{i=1}^{n}x_{i}=k_{a}$ and then picking
any $U_{d}^{u}(i),U_{d}^{c}(i)$ such that $\Delta_{d}(i)=x_{i}$ for each $i$.
Then, take $y_{1},\dots,y_{n}\in(0,1)$ such that $\sum_{i=1}^{n}y_{i}=k_{d}$
and select $U_{a}^{u}(i),U_{a}^{c}(i)$ distinct and such that
$U_{a}^{u}(i)-y_{i}\Delta_{a}(i)=c_{1}$ for each $i$. The resulting game has a
type I.A.i with $r=s=t=0$ and constants $c_{1}$ and $c_{2}$.

As an explicit example, take $k_{a}=3$, $k_{d}=2$ and $c_{1}=1$, $c_{2}=2$.
Then $n=4$ and we take $x_{1}=0.6,x_{2}=0.7,x_{3}=0.9,x_{4}=0.8$ and
$y_{1}=0.3,y_{2}=0.5,y_{3}=0.4,y_{4}=0.8$. We choose

Target: | 1 | 2 | 3 | 4
---|---|---|---|---
$U_{a}^{u}$ | 8/7 | 6/5 | 4/3 | 2
$U_{a}^{c}$ | 2/3 | 4/5 | 1/2 | 3/4
$U_{d}^{u}$ | -8/5 | -27/10 | -39/10 | -24/5
$U_{d}^{c}$ | -1 | -2 | -3 | -4

Clearly, one can introduce new targets meeting the criteria in Lemmas 2.7 and
2.6 to construct an equilibrium of type I.A.i with other values of $r,s,t$.
Furthermore, from a type I.A.i equilibrium with $r=s=t=0$, we can build
equilibria of types I.A.ii,I.A.iii,I.B.i,I.B.ii and I.B.iii by introducing
targets which belong to $I_{2},I_{8}$ or $I_{6}$ by enforcing that
$U_{a}^{u}(i),U_{a}^{c}(i)$ or $\Delta_{d}(i)$ coincide with the fixed value
of $c_{1}$ or $c_{2}$ respectively.

######  Remark 2.12.

For the sake of clarity of presentation, the analysis in this section has been
under Assumption 1. However, it is straightforward to extend our analysis and
modify Algorithm 1 to cases in which Assumption 1 does not hold. When
Assumption 1 is lifted, we may have $|I_{2}|,|I_{6}|,|I_{8}|>1$ and it may be
the case that $I_{2}$ and $I_{8}$ are both nonempty. Thus, two additional
types of equilibrium, I.A.iv and I.B.iv are introduced to account for the
cases in which $I_{2}\neq\emptyset$ and $I_{8}\neq\emptyset$. By Lemma 2.4: If
$I_{2}\neq\emptyset$, we must have $U_{a}^{u}(i)=U_{a}^{u}(j)$ for all $i,j\in
I_{2}$; if $I_{8}\neq\emptyset$, $U_{a}^{c}(i)=U_{a}^{c}(j)$ we must have for
all $i,j\in I_{8}$; and if $I_{6}\neq\emptyset$ we must have
$\Delta_{d}(i)=\Delta_{d}(j)$ for all $i,j\in I_{6}$. Furthermore, for any
Type I.A.iv or I.B.iv, we must have $U_{a}^{u}(i)=U_{a}^{c}(j)$ for $i\in
I_{2}$ and $j\in I_{8}$. When payoffs are possibly indistinct, we modify
Algorithm 1 to include these cases. Note that when checking for feasibility of
any Type I.A.ii,I.A.iii,I.A.iv or I.B.i we must verify that there exists a
collection of $\alpha_{i}$ or $\beta_{i}$ (respectively) in $(0,1)$ meeting
the condition (3) and such that $\alpha_{j},\beta_{J}$ for $j\in I_{5}$ belong
to $(0,1)$. Additionally, when payoffs are possibly indistinct, a Type II
equilibrium may have $I_{8}\neq\emptyset$. We check for feasible Type II
equilibria by introducing a parameter $\ell=|I_{9}|$ and considering, for each
$\ell$, all candidate equilibria in which $U_{a}^{c}(i)=U_{a}^{c}(j)$ for all
$i,j\in I_{8}$.

As the structural analysis of section 2.1 gives closed-form expressions for
$\alpha$ and $\beta$, we obtain as a secondary product a set of closed-form
expressions for the player expected outcomes at equilibrium for each type.
These expressions are presented in the appendix.

###  2.3 Uniqueness and Multiplicity of Nash Equilibria

In this section, we present results regarding the uniqueness and multiplicity
of equilibria of the various types defined in Section 2.1. The following
result is due to [Korzhyk _et al._ (2011a)]

######  Lemma 2.13.

Suppose $(\alpha^{*},\beta^{*})$ and
$(\overline{\alpha}^{*},\overline{\beta}^{*})$ are two Nash equilibria of a
security game.

  1. (i)

For all $t\in T$, $\alpha^{*}_{t}=\overline{\alpha}^{*}_{t}$ or
$\beta^{*}_{t}=\overline{\beta}^{*}_{t}$

  2. (ii)

If $t_{1},t_{2}\in T$ are such that
$\beta^{*}_{t_{1}}\neq\overline{\beta}^{*}_{t_{1}}$ and
$\beta^{*}_{t_{2}}\neq\overline{\beta}^{*}_{t_{2}}$ then

$\alpha^{*}_{t_{1}}\Delta_{d}(t_{1})=\alpha^{*}_{t_{2}}\Delta_{d}(t_{2})=\overline{\alpha}^{*}_{t_{1}}\Delta_{d}(t_{1})=\overline{\alpha}^{*}_{t_{2}}\Delta_{d}(t_{2})$

From this result, we derive the following corollary:

######  Corollary 2.14.

If $(\alpha^{*},\beta^{*})$ and $(\overline{\alpha}^{*},\overline{\beta}^{*})$
are two Nash equilibria of a security game with constants $c_{1},c_{2}$ and
$\overline{c_{1}},\overline{c_{2}}$ respectively then one of the following
holds:

  1. (i)

$c_{1}=\overline{c_{1}}$ and $c_{2}=\overline{c_{2}}$

  2. (ii)

Precisely one of $c_{1}=\overline{c_{1}}$ or $c_{2}=\overline{c_{2}}$ holds.

######  Proof 2.15.

Note that if $\alpha^{*}=\overline{\alpha}^{*}$ and
$\beta^{*}=\overline{\beta}^{*}$, the two equilibria are of precisely the same
type with the same parameters and thus $c_{1}=\overline{c_{1}}$,
$c_{2}=\overline{c_{2}}$. Suppose that there exists $t$ such that
$\alpha_{t}>\overline{\alpha}_{t}$. By Lemma 2.13 (i), we have
$\beta_{i}=\overline{\beta}_{i}$. Therefore

$c_{1}\leq
U_{a}^{c}(t)\beta_{i}+U_{a}^{u}(t)(1-\beta_{t})=U_{a}^{c}(t)\overline{\beta}_{i}+U_{a}^{u}(t)(1-\overline{\beta}_{t})\leq\overline{c_{1}}.$

Now, as $\sum_{t=1}^{m}\alpha_{i}=k_{a}$, there exists $t^{\prime}$ so that
$\alpha_{t^{\prime}}<\overline{\alpha}_{t^{\prime}}$. By the same argument as
that for $t$, we have $\overline{c_{1}}\leq c_{1}$ and thus
$c_{1}=\overline{c_{1}}$. A similar argument shows $c_{2}=\overline{c_{2}}$ if
there exists $t$ such that $\beta_{t}=\overline{\beta}_{t}$.

######  Lemma 2.16.

  1. (i)

If multiple Type I equilibria exist, they are all of the same subtype

  2. (ii)

If an equilibrium of type I.A.i, I.B.ii or I.B.iii exists, it is unique

  3. (iii)

If an equilibrium of type I.A.ii,I.A.iii or I.B.i exists, a continuum of such
equilibria exist

######  Proof 2.17.

Suppose $(\alpha^{*},\beta^{*}),(\overline{\alpha}^{*},\overline{\beta}^{*})$
are two type I equilibria. By Corollary 2.14,
$\alpha^{*}\neq\overline{\alpha}^{*}$ implies $c_{1}=\overline{c_{1}}$ and
$\beta^{*}\neq\overline{\beta}^{*}$ implies $c_{2}=\overline{c_{2}}$. Consider
the cases:

  * •

$c_{1}=\overline{c_{1}}$ and $c_{2}=\overline{c_{2}}$; We have
$(\alpha^{*},\beta^{*})=(\overline{\alpha}^{*},\overline{\beta}^{*})$.

  * •

$c_{1}=\overline{c_{1}}$ and $c_{2}\neq\overline{c_{2}}$; There must exist $t$
so that $c_{1}=\overline{c_{1}}=U_{a}^{u}(t)-\beta_{i}^{*}\Delta_{a}(t)$ and
thus there exists $t\in I_{2}\cup I_{8}$.

  * •

$c_{1}\neq\overline{c_{1}}$ and $c_{2}=\overline{c_{2}}$; There must exist $t$
so that $c_{2}=\overline{c_{2}}=\alpha_{t}\Delta_{d}(t)$ and thus there must
exist $t\in I_{6}$.

That is, if two distinct equilibria of Type I exist they are of type
$I.A.ii,I.A.iii$ or $I.B.i$. Thus, if a Type I.A.i, I.B.ii or I.B.iii
equilibrium exists, it is unique. Furthermore, by Assumption 1 if two distinct
equilibria exist of types I.A.ii or I.A.iii, they must both be either of type
I.A.ii or I.A.iii.

######  Lemma 2.18.

If an equilibrium of Type II exists, no equilibrium of Type I exists.

######  Proof 2.19.

Suppose $(\alpha^{*},\beta^{*})$ is of Type II and
$(\overline{\alpha}^{*},\overline{\beta}^{*})$ is of Type I. As there is a
feasible Type II equilibrium, we have $k_{d}>k_{a}$. By the interchangeability
of Nash equilibria in additive security games [Korzhyk _et al._ (2011b)], we
have that $(\overline{\alpha}^{*},\beta^{*})$ must be a Nash equilibrium. If
$(\overline{\alpha}^{*},\beta^{*})$ is of Type I, it must be of Type I.A.i
with $|I_{9}|=k_{d}$ as the defender is playing a pure strategy. However, this
implies $\sum_{i=1}^{m}\alpha_{i}\geq\sum_{i\in I_{9}}\alpha_{i}=k_{d}>k_{a}$
in violation of $\eqref{sum_alpha_beta}$. Thus $(\overline{\alpha}^{*},\beta)$
is of type II, so $\overline{\alpha}^{*}$ is a pure strategy. On the other
hand, if $(\alpha,\overline{\beta}^{*})$ is of Type I, it must be of Type
$I.A.i$ with $I_{5}=\emptyset$ and $|I_{9}|=k_{d}$. However this implies
$k_{a}=\sum_{i=1}^{m}\alpha_{i}\geq\sum_{i\in I_{3}\cup I_{9}}1\geq k_{d}$
contradicting $k_{d}>k_{a}$. So $(\alpha,\overline{\beta^{*}})$ is of Type II
and $\overline{\beta}^{*}$ is a pure strategy. Therefore
$(\overline{\alpha}^{*},\overline{\beta}^{*})$ is a Type I.A.i with
$I_{5}=\emptyset$ (as both players are playing pure strategies), but this
implies $k_{d}\leq k_{a}$ \- a contradiction.

###  2.4 Special Case: Fully Protective Resources

In this section we consider the special case of fully protective resources.
That is, $U_{a}^{c}(i)=U_{d}^{c}(i)=0$ for all $i$. A security game model in
which $U_{a}^{c}(i)=0$ for all $i$ and the attacker has a single resource is
studied in [Lerma _et al._ (2011)] in which a linear time algorithm algorithm
was proposed to calculate a Stackelberg equilibrium in such a game.

As in the previous section, we shall make Assumption 1 in the following
analysis, and we present closed-form expressions for the player expected
payoffs at equilibrium in the appendix. We now present the analogues of Lemmas
2.1-2.7 and Theorem 2.3 for the case of fully protective resources. Note that,
for any pair of marginal attack and defense probability vectors
$(\alpha,\beta)$, we have the following, even more compact forms of the
defender expected payoffs (2):

$v_{a}^{*}=\sum_{t=1}^{m}\alpha_{t}U_{a}^{u}(t)(1-\beta_{t})\hskip
10.00002pt\text{and}\hskip
10.00002ptv_{d}^{*}=\sum_{t=1}^{m}\alpha_{i}U_{d}^{u}(t)(1-\beta_{t}).$

Intuitively, the expected payoffs depend only upon the marginal probabilities
with which the targets are attacked and exposed. The structural
characterization of equilibria in the case of fully protective resources will,
as in the previous section, from repeated application of the following
modified version of Observation 1

###### Observation 2

In a game with fully protective resources, a player can unilaterally deviate
from $(\alpha,\beta)$ if and only if they are able to shift marginal
probability from one target to another. By definition, therefore, if
$(\alpha^{*},\beta^{*})$ is a Nash equilibrium:

$\displaystyle\alpha_{i}^{*}>0,\alpha_{j}^{*}<1$ $\displaystyle\implies
U_{a}^{u}(j)(1-\beta_{j})\leq U_{a}^{u}(i)(1-\beta_{i})$
$\displaystyle\beta_{i}^{*}>0,\beta_{j}^{*}<1$
$\displaystyle\implies\alpha_{i}U_{d}^{u}(i)\leq\alpha_{j}U_{d}^{u}(j)$

That is, no player can unilaterally deviate and increase their expected
payoff.

######  Lemma 2.20.

If $(\alpha^{*},\beta^{*})$ is a Nash equilibrium of a security game with
fully protective resources:

  1. (i)

$I_{4}\cup I_{7}=\emptyset$

  2. (ii)

At least one of $I_{8}\cup I_{9}$ and $I_{1}\cup I_{2}\cup I_{5}$ is empty.

  3. (iii)

At least one of $I_{8}\cup I_{9}$ and $I_{6}$ is empty.

######  Theorem 2.21.

A Nash equilibrium $(\alpha^{*},\beta^{*})$ in a security game with fully
protective resources is of one of the following types:

  1. (i)

I.A.i, I.A.ii,I.B.i or I.B.ii with $I_{9}=\emptyset$

  2. (ii)

I.A.iii with $I_{1}\cup I_{5}=\emptyset$

######  Lemma 2.22.

If $(\alpha^{*},\beta^{*})$ is a Nash equilibrium in a security game with
fully protective resources:

  1. (i)

There exists a constant $c_{1}$ such that
$c_{1}=U_{a}^{u}(i)(1-\beta_{i}^{*})$ for all $i\in I_{2}\cup I_{5}$.
Furthermore, for $i\in I_{2}$ we have $c_{1}=U_{a}^{u}(i)$.

  2. (ii)

There exists a constant $c_{2}$ such that $c_{2}=\alpha_{i}^{*}U_{d}^{u}(i)$
for all $i\in I_{5}\cup I_{6}$. Furthermore, for $i\in I_{6}$ we have
$c_{2}=U_{d}^{u}(i)$.

######  Lemma 2.23.

Suppose $(\alpha^{*},\beta^{*})$ is a Nash equilibrium in a security game with
fully protective resources. Then

  1. (i)

For $i\in I_{2}\cup I_{3}\cup I_{5}\cup I_{6}$ and $j\in I_{1}$,
$U_{a}^{u}(j)<U_{a}^{u}(i)$.

  2. (ii)

For $i\in I_{3}\cup I_{6}$, $j\in I_{2}$, $U_{a}^{u}(j)<U_{a}^{u}(i)$.

  3. (iii)

For $i\in I_{3}\cup I_{6}$, $j\in I_{5}$, $U_{a}^{u}(1-\beta_{j})\leq
U_{a}^{u}(i)$.

  4. (iv)

For $i\in I_{5}\cup I_{6}$, $j\in I_{2}$, $U_{d}^{u}(i)\leq\alpha
U_{d}^{u}(j)$.

  5. (v)

For $i\in I_{5}\cup I_{6}$, $j\in I_{3}$, $U_{d}^{u}(i)<U_{d}^{u}(j)$.

Table 3: Expressions for $c_{1}$ and $c_{2}$ for candidate equilibria in the case of fully protective resources. | $c_{1}$ | $c_{2}$
---|---|---
I.A.i with $I_{9}=\emptyset$ | ${k_{d}-m+r+s\over\sum_{j\in I_{5}}{1\over U_{a}^{u}(j)}}$ | ${k_{a}-s\over\sum_{j\in I_{5}}{1\over U_{d}^{u}(i)}}$
I.A.ii with $I_{9}=\emptyset$ | $U_{a}^{u}(j^{[2]})$ | ${k_{a}-s-\alpha_{j^{[2]}}\over\sum_{j\in I_{5}}{1\over U_{d}^{u}(j)}}$
I.B.i with $I_{9}=\emptyset$ | ${k_{d}-m+r+s+1-\beta_{j^{[6]}}\over\sum_{j\in I_{5}}{1\over U_{a}^{u}(j)}}$ | $U_{d}^{u}(j^{[6]})$
I.B.ii with $I_{9}=\emptyset$ | $U_{a}^{u}(j^{[2]})$ | $U_{d}^{u}(j^{[6]})$

######  Corollary 2.24.

In the case of fully protective resources, Algorithm 1 can be modified to be
$O(m^{2})$.

######  Proof 2.25.

By the result in Theorem 2.21, it suffices to consider two cases. Suppose
$(\alpha^{*},\beta^{*})$ is of type I.A.i, I.A.ii,I.B.i or I.B.ii with
$I_{9}=\emptyset$. In each of these types we have $I_{9}=\emptyset$ and
therefore it suffices to run Algorithm 1 without iteration over $t$. The
values of $c_{1}$ and $c_{2}$ for a given $r,s$ or $s,t$ and type in the case
of fully protective resources are given in Table 3, and we take these values
in the modified version of Algorithm 1. To determine the existence of
$(\alpha^{*},\beta^{*})$ of type I.A.iii with $I_{1}\cup I_{5}=\emptyset$,
first note that we have $r=0$. By Observation 2, $i\in I_{8}\cup I_{9}$ and
$j\in I_{3}$ implies $U_{d}^{u}(i)<U_{d}^{u}(j)$, so we order the targets such
that $U_{d}^{u}(i)<U_{d}^{u}(j)$ for $i<j$. By (3), then, we must have
$I_{3}=\\{k_{d}+1,\dots,m\\}$ and so $\alpha_{i}=1$, $\beta_{i}=0$ for
$i=k_{d}+1,\dots,m$. For all remaining $i=1,\dots,k_{d}$ we have $\beta_{i}=1$
and $\alpha_{1},\dots,\alpha_{k_{d}}$ must satisfy

$\sum_{i\in T\setminus I_{3}}\alpha_{i}=k_{a}-m+k_{d}+2\hskip
10.00002pt\text{and}\hskip 10.00002pt{U_{d}^{u}(k_{d}+1)\over
U_{d}^{u}(i)}\leq\alpha_{i}\leq 1$

by (3) and Lemma 2.4. There is a solution if and only if $\sum_{i\in
T\setminus I_{3}}{U_{d}^{u}(k_{d}+1)\over U_{d}^{u}(i)}\leq k_{a}-m+k_{d}+2$.

###  2.5 Zero Sum Games with Fully Protective Resources

In this section, we consider the case of zero-sum security games with fully
protective resources. That is, $U_{a}^{c}(i)=U_{d}^{c}(i)=0$ and
$U_{a}^{u}(i)=-U_{d}^{u}(i)$ for all $i$. By von Neumann’s theorem [Neumann
(1928)], we have

$v^{*}=\max_{p}\min_{1\leq i\leq{m\choose
k_{d}}}(p^{T}A)_{i}=\min_{q}\max_{1\leq j\leq{m\choose k_{a}}}(Aq)_{j}$

where $A=-B$ is the attacker payoff matrix and $p,q$ represent player mixed
strategies Assume without loss of generality that $U_{a}^{u}(i)\leq
U_{a}^{u}(j)$ for $i<j$. Note that

$(p^{T}A)_{i}=\sum_{j=1}^{m\choose k_{a}}p_{j}a_{ji}=\sum_{t\notin
s_{i}^{d}}\alpha_{t}U_{a}^{u}(t)$

where $\alpha_{t}$ is the marginal probability with which $t$ is attacked (as
in previous sections). The above expression implies that $v^{*}$ is the sum of
the least $m-k_{d}$ terms $\alpha_{t}U_{a}^{u}(t)$ at equilibrium. For an
equilibrium of type $I.A.i$ with $I_{9}=\emptyset$, we can introduce a
parameterization such that $I_{1}=\\{1,\dots,r\\}$,
$I_{3}=\\{r+1,\dots,m-s\\}$ and $I_{5}=\\{m-s+1,\dots,m\\}$. For an
equilibrium in which $I_{2}$ or $I_{6}$ is nonempty, we take $j^{[2]}=r+1$ or
$j^{[6]}=m-s+1$. By Lemma 2.23 (and $U_{a}^{u}(i)=-U_{d}^{u}(i)$) we obtain:

  1. 1.

$\alpha^{*}U_{a}^{u}(m)=\dots=\alpha^{*}_{m-s+1}U_{a}^{u}(m-s+1)=c_{2}>\alpha^{*}_{m-s}U_{a}^{u}(m-s)\geq\dots\geq\alpha^{*}_{r+1}U_{a}^{u}(r+1),\alpha^{*}(r)=\dots=\alpha^{*}(1)=0$

  2. 2.

$U_{a}^{u}(r+1)\geq(1-\beta^{*})U_{a}^{u}(m)=\dots=(1-\beta^{*}_{m-s+1})U_{a}^{u}(m-s+1)=c_{1}>U_{a}^{u}(r),\beta^{*}_{m-s-1}=\dots=\beta^{*}_{1}=0$

This structural property coincides with the result obtained in [Emadi and
Bhattacharya (2020a)]. Now, define a function

$\sigma_{\alpha}(r,s,\alpha_{r+1},c_{2})=m-(s+r+1)+\alpha_{r+1}-\sum_{k=m-s+1}^{m}{c_{2}\over
U_{a}^{u}(k)}.$

By construction, we have
$\sigma_{\alpha}(r,s,\alpha_{r+1},c_{2})=\sum_{i=1}^{m}\alpha_{i}$. Now, for
each $r$ and $s$ note that $c_{2}\in[-U_{a}^{u}(m-s+1),-U_{a}^{u}(m-s))$,
$\alpha_{r+1}\in[0,1]$ and that $\sigma_{\alpha}(r,s,\alpha_{r+1},c_{2})$ is a
strictly non-increasing function of $r$. Thus,

$\sigma_{\alpha}^{\min}(r,s)\equiv\min_{c_{2},\alpha_{r+1}}\sigma_{\alpha}(r,s,\alpha_{r+1},c_{2})=\sup_{c_{2},\alpha_{(r+1)+1}}\sigma_{\alpha}(r+1,s+1,\alpha_{(r+1)+1},c_{2})\equiv\sigma_{\alpha}^{\sup}(r+1,s+1).$

This implies that when $r^{\prime}>r,s^{\prime}>s$, if
$k_{a}>\sigma_{\alpha}^{\min}(r,s)$,
$k_{a}>\sigma_{\alpha}^{\sup}(r^{\prime},s^{\prime})$. Thus we can search for
feasible equilibria by considering $s\in\\{1,\dots,m\\}$ and only values of
$r$ for which $\sum_{i=1}^{m}\alpha_{i}\leq k_{a}$, yielding a linear time
procedure to compute an equilibrium.

When resources are not fully protective, analogues of properties 1 and 2 above
do not hold, as such relationships are dependent upon the ordering of
$\\{U_{a}^{c}(1),\dots,U_{a}^{c}(m)\\}$ with respect to
$\\{U_{a}^{u}(1),\dots,U_{a}^{u}(m)\\}$ and thus the assumption of a zero-sum
game does not immediately yield a reduction in the complexity of equilibrium
computation.

##  3 Optimization of Defender Expected Utility

In this section, we address the problem: Given that a defender can perturb the
payoffs of a security game prior to play, how should they do so to optimize
their expected outcome at equilibrium? That is, we wish to address the
following optimization problem:

######  Problem 3.1.

$\displaystyle\mathbf{maximize}$ $\displaystyle\hskip 10.00002ptv_{d}^{*}$ (7)
$\displaystyle\mathbf{s.t.}$ $\displaystyle\hskip 10.00002pt\forall t\in
T\hskip
10.00002ptU_{a}^{c}(i)\in[lb_{a}^{c}(i),ub_{a}^{c}(i)],U_{a}^{u}(i)\in[lb_{a}^{u}(i),ub_{a}^{u}(i)]$

######  Definition 3.2.

In a leader-follower security game in which the Defender is the leader, we say
a pair $(\alpha,\beta)$ is a strong Stackelberg equilibrium if and only if
both $\alpha$ and $\beta$ are best responses and $\alpha$ yields maximal
defender expected outcome among all attacker best responses.

In the case of Stackelberg equilibria, a single attacker resource, and the
restriction that the defender payoffs remain fixed, a polynomial time
algorithm to solve Problem 3.1 is given in [Shi _et al._ (2018)] (Theorem 5).
By [Korzhyk _et al._ (2011b)], in the case of a single attacker resource, such
a Stackelberg equilibrium is also a Nash equilibrium and thus a solution to
Problem 3.1 for Nash equilibria can also be found in polynomial time. However,
in the case of multiple attacker resources, a Stackelberg equilibrium need not
be a Nash equilibrium (as shown in [Korzhyk _et al._ (2011b)]). Consider the
following restricted version of Problem 3.1:

######  Problem 3.3.

$\displaystyle\mathbf{maximize}$ $\displaystyle\hskip 10.00002ptv_{d}^{*}$ (8)
$\displaystyle\mathbf{s.t.}$ $\displaystyle\hskip 10.00002pt\forall t\in
T\hskip
10.00002ptU_{a}^{c}(i)\in\\{lb_{a}^{c}(i),ub_{a}^{c}(i)\\},U_{a}^{u}(i)\in\\{lb_{a}^{u}(i),ub_{a}^{u}(i)\\}$

That is, Problem 3.3 restricts Problem 3.1 by allowing each payoff to take
only one of two values, rather than all values in some closed interval.

######  Theorem 3.4.

In the case of Stackelberg equilibrium and multiple attacker resources,
Problem 3.3 is weakly NP-hard.

######  Proof 3.5.

Define a problem TwoWeightKnapsack as follows: given a collection of $k$
objects each with a value $v_{i}$ and a set of two possible weights
$\\{w_{i}^{1},w_{i}^{2}\\}$ determine if there exists a subset of the objects
$S$ and a choice of $w_{i}=w_{i}^{1}$ or $w_{i}=w_{i}^{2}$ for each $i$ such
that

$\sum_{t\in S}w_{t}\leq 1\text{ and }\sum_{t\in S}v_{t}\geq V.$

Clearly, a standard instance of Knapsack can be reduced to an instance of
TwoWeightKnapsack by taking $w_{i}^{1}=w_{i}^{2}$. We adapt a construction
presented in [Korzhyk _et al._ (2011a)]. Suppose
$v_{i},\\{w_{i}^{1},w_{i}^{2}\\},V$,$i=1,\dots,k_{a}$ is an instance of
TwoWeightKnapsack. Define a security game on $2k_{a}$ targets in which
$k_{d}=1$. Take targets $1,\dots,k$ to be the objects in the instance of
TwoWeightKnapsack. For a given choice of $w_{t}=w_{t}^{1}$ or
$w_{t}=w_{t}^{2}$ for each $t$, $1\leq i\leq k$ take

$U_{a}^{u}(i)=w_{i},\hskip 10.00002ptU_{a}^{c}(i)=w_{i}-1,\text{ and
}U_{d}^{c}(i)=U_{d}^{c}=-v_{i}.$

Let targets $k+1,\dots,2k$ be such that

$U_{a}^{u}(i)=U_{a}^{c}(i)=U_{d}^{c}(i)=U_{d}^{u}(i)=0.$

Note that the defender can obtain an expected utility of at least
$V-\sum_{i=1}^{k}v_{i}$ if and only if there is a solution to the instance of
TwoWeightKnapsack.

######  Corollary 3.6.

In the case of Stackelberg equilibria and multiple attacker resources, Problem
3.1 is weakly NP-hard.

The hardness of Problem 3.3 in the case of Stackelberg equilibria is
fundamentally due to the weak NP-hardness of computing Stackelberg equilibria
in security games with multiple attacker resources. The problem of computing
Nash equilibria in such games, however, can be solved in polynomial time (as
demonstrated by [Korzhyk _et al._ (2011a)] or the algorithm of Section 2.1).
The nontrivial nature of Problem 3.3 in the case of Nash equilibria is
illustrated by the following example:

######  Example 3.7.

Consider the instance of Problem 3.3 defined by the following zero-sum game
with fully protective resources, $k_{a}=2$ and $k_{d}=3$:

$U_{d}^{u}(i)$ | -5 | -10 | -7 | -8 | -4 | -1
---|---|---|---|---|---|---
$lb_{a}^{u}(i)$ | 1 | 2 | 9 | 4 | 6 | 10
$ub_{a}^{u}(i)$ | 7 | 3 | 13 | 5 | 8 | 11

If $U_{a}^{u}(i)=lb_{a}^{u}(i)$ for all $i$ or $U_{a}^{u}(i)=ub_{a}^{u}(i)$
for all $i$, we have $v_{d}^{*}=-789/229\approx-3.45$ with
$\alpha^{*}=[56/229,28/229,40/229,35/229,70/229,1]$ in both cases and
$\beta_{lb}^{*}=[1/73,37/73,65/73,$ $55/73,61/73,0]$,
$\beta_{ub}^{*}=[6469/9589,2309/9589,7909/9589,5221/9589,6859/9589,0]$
respectively. However, one can verify by exhaustive search that the maximum
value of $v_{d}^{*}$, $v_{d}^{*}=-453/173\approx-2.62$, is attained when
(among other choices) $U_{a}^{u}(1)=lb_{a}^{u}(1)$ and
$U_{a}^{u}(i)=ub_{a}^{u}(i)$ for all other $i$ with equilibrium strategies:

$\alpha^{*}$ | 0 | 28/173 | 40/173 | 35/173 | 70/173 | 1
---|---|---|---|---|---|---
$\beta^{*}$ | 0 | 627/1147 | 1027/1147 | 835/1147 | 952/1147 | 0

Given the nontrivial nature of the problem, we introduce the following
assumption enforcing that all parameters of distinct targets belong to
distinct intervals, which will allow for solution of problem 3.3.

###### Assumption 2

$lb_{a}^{c}(1)\leq ub_{a}^{c}(1)<lb_{a}^{c}(2)\leq
ub_{a}^{c}(2)<\dots<lb_{a}^{c}(m)\leq ub_{a}^{c}(m)$

and that there exists a permutation $i_{1},\dots,i_{m}$ of $[m]$ such that

$lb_{a}^{u}(i_{1})\leq ub_{a}^{u}(i_{1})<lb_{a}^{u}(i_{2})\leq
ub_{a}^{u}(i_{2})<\dots<lb_{a}^{u}(i_{m})\leq ub_{a}^{u}(i_{m}).$

We now show that there is a pseudopolynomial time algorithm to solve Problem
3.3 for the case of Nash equilibria under Assumptions 1 and 2.

######  Theorem 3.8.

Under Assumptions 1 and 2, in the case of multiple attacker resources and Nash
equilibria, Problem 3.3 can be solved in pseudopolynomial time.

######  Proof 3.9.

Note that by our structural characterization of Nash equilibria given in
Section 2.1, Nash equilibria are of precisely three classes: equilibria in
which $c_{1}$ and $c_{2}$ both coincide with a parameter of the game
(I.B.ii,I.B.ii), those in which precisely one of $c_{1}$ or $c_{2}$ coincides
with a game parameter (I.A.ii,I.A.iii,I.B.i), and those in which neither
$c_{1}$ nor $c_{2}$ coincide with a game parameter (I.A.i). We now present a
procedure to identify the equilibrium of largest $v_{d}^{*}$ within each
class. Consider the cases:

  1. (i)

$\exists i\exists j$ so $c_{1}=U_{a}^{x}(i)$ and $c_{2}=\Delta_{d}(j)$ for
some $x\in\\{u,c\\}$. First consider the problem of computing an equilibrium
of type I.B.ii of maximal $v_{d}^{*}$. We have that $c_{1}$ and $c_{2}$
correspond to some parameters associated with some pair of targets. There are
$2|T|$ choices for $c_{1}$ and $|T|$ choices for $c_{2}$. Fix some choice of
$c_{1}$ and $c_{2}$. For any type I.B.ii equilibrium, there exists some
$\ell\in\\{-\infty,U_{a}^{u}(1),\dots,U-a^{u}(m)\\}$ such that $t\in I_{1}$ if
and only if $U_{a}^{u}(t)\leq\ell$. Note there are $2|T|+1$ choices of $\ell$.
Fix some choice of
$\ell\in\\{-\infty,lb_{a}^{u}(i_{1}),\dots,ub_{a}^{u}(i_{m})\\}$. If
$\ell=lb_{a}^{u}(i)$ or $\ell=ub_{a}^{u}(i)$ we take $U_{a}^{u}(i)=\ell$. Note
that for any $t\in I_{1}$, $v_{d}^{*}$ does not depend upon the choice of
$U_{a}^{u}(t)$ or $U_{a}^{c}(t)$ (as $\alpha_{t}=0$ for $t\in I_{1}$), so we
pick $U_{a}^{u}(t),U_{a}^{c}(t)$ for $t\in I_{1}$ arbitrarily. Assume that
$\ell$ selects $r$ targets to belong to $I_{1}$. We now consider the possible
distributions of the remaining $m-r-2$ targets to the sets $I_{3},I_{5}$ and
$I_{9}$. First note that as $I_{2}\cup I_{6}\neq\emptyset$ we must have
$I_{5}\neq\emptyset$. Recall the notation $s=|I_{3}|$ and $t=|I_{9}|$ from
section 2.2. By Lemma 2.6, for each possible choice of $r$ and $s$ we take
$I_{3}$ to consist of the $s$ targets in $T\setminus I_{1}\cup I_{2}\cup
I_{6}$ of least $\Delta_{a}(i)$ and $I_{9}$ to consist of the $t$ targets in
$T\setminus I_{1}\cup I_{2}\cup I_{3}\cup I_{6}$ of greatest possible choice
of $U_{a}^{c}(i)$. Finally, we take $I_{5}$ to consist of all remaining
targets. For $t\in I_{5}$, we must have $\alpha_{t}=c_{2}/\Delta_{d}(t)$ and
$\beta_{t}=(U_{a}^{u}(t))/\Delta_{d}(t)$. If any target in $I_{5}$ has
$\Delta_{d}(t)$ such that $\alpha_{t}\notin(0,1)$, there is no feasible I.B.ii
equilibrium with the current $c_{1},c_{2},r,s,t$. For each target $t\in I_{5}$
we exclude any choice of $lb_{a}^{u}(t)$ or $ub_{a}^{u}(t)$ which violates
$\beta_{t}\in(0,1)$. If both such choices violate $\beta_{t}\in(0,1)$ for some
$t\in I_{5}$ there is no feasible I.B.ii equilibrium with the current
$c_{1},c_{2},r,s,t$. Additionally, we must have
$\alpha_{j^{[2]}}=k_{a}-s-t-1-\sum_{i\in I_{5}}c_{2}/\Delta_{d}(i)\in(0,1)$
and if this condition is violated there is no feasible I.B.ii equilibrium with
the current parameters. To check for feasible candidate solutions among the
remaining choices, we compute all possible choices of
$lb_{a}^{c}(i),ub_{a}^{c}(i),lb_{a}^{u}(i),ub_{a}^{u}(i)$ for which
$\beta_{j^{[6]}}=k_{a}-t+\sum_{i\in
I_{5}}U_{a}^{u}(j^{[2]})/\Delta_{a}(i)-\sum_{i\in
I_{5}}U_{a}^{u}(i)/\Delta_{a}(i)\in(0,1)$. This is an instance of SubsetSum
which can be solved in pseudopolynomial time using standard dynamic
programming techniques [Cormen _et al._ (2022)]. For each potentially feasible
constructed equilibrium, we check the feasibility conditions given in section
2.1. Finally, we select an equilibrium of type I.B.ii of maximal $v_{d}^{*}$
or output that no such equilibrium exists. The construction for type I.B.iii
equilibria is similar and differs only in that $\\{c_{1}=a_{i}^{c}\\}=I_{8}$
for some $i$ and $I_{2}=\emptyset$.

  2. (ii)

For all $t\in T$, $U_{a}^{u}(t)\neq c_{1}\neq U_{a}^{u}(t)$ and
$c_{2}\neq\Delta_{d}(i)$. Note that such an equilibrium is of type I.A.i.
Either there exists $i\in T$ so that $c_{2}\in(\Delta_{d}(i),\Delta_{d}(i+1)$
or one of $c_{2}\leq\Delta_{d}(1)$, $\Delta_{d}(m)<c_{2}$ holds. Thus, there
are $m+1$ possible choices of interval for $c_{2}$. Additionally, we have that
$c_{1}$ must lie in an interval strictly between some choice of
$U_{a}^{c}(i),U_{a}^{u}(i),U_{a}^{c}(j),U_{a}^{u}(j)$ or strictly larger or
smaller than all such choices. Clearly there are polynomially many such
possible intervals. Fix two intervals $c_{1}\in(a,b)$ and $c_{2}\in(c,d)$. As
in case $(i)$, we establish the parameters $\ell,s$ and $t$, construct every
candidate $I_{1},I_{3},I_{5}$ and $I_{9}$ and eliminate any choices of payoff
for $t\in I_{5}$ that lead to $\alpha_{t}\notin(0,1)$ or
$\beta_{t}\notin(0,1)$ (or determine the current parameters lead to no
feasible equilibrium). We then compute all candidate choices of parameters for
targets in $I_{5}$ such that $c_{1}=(t-k_{d}+\sum_{j\in
I_{5}}U_{a}^{u}(i)/\Delta_{a}(j))/\sum_{j\in I_{5}}1/\Delta_{a}(j)\in(a,b)$
and $c_{2}=(k_{a}-s-t)/\sum_{j\in I_{5}}1/\Delta_{a}(j)\in(c,d)$. This amounts
to the following modified version of SubsetSum: Given a list of numbers
$n_{1},\dots,n_{k}$ and an interval $(a,b)$, compute all subsets which have a
sum belonging to the interval $(a,b)$. Assuming that our game parameters are
represented as floating point numbers, this problem can be solved in
pseudopolynomial time by solving an equivalent problem in which all parameters
are integers and the target interval is $(a^{\prime},b^{\prime})$ by way of
$|\\{i\in(a^{\prime},b^{\prime}):i\in\mathbb{Z}\\}|$ instances of SubsetSum.
Finally, we check each candidate solution for feasibility using the conditions
presented in section 2.1 and select an equilibrium of type I.A.i of maximal
$v_{d}^{*}$ or output that no such equilibrium exists.

  3. (iii)

Precisely one of $c_{1}$ or $c_{2}$ coincides with a game parameter. It is
clear from the constructions for cases $(i)$ and $(ii)$ that this case is also
resolved in pseudopolynomial time.

Figure 1: Decision diagram used to improve the efficiency of the algorithm for
type I.B.ii equilibria presented in Theorem 3.8$i\in
I_{1}$$\Delta_{d}(i)<c_{2}$$i\in
I_{1}$$\Delta_{d}(i)>c_{2}$$U_{a}^{c}(i)<c_{1}$$i\in
I_{3}$$\Delta_{d}(i)<c_{2}$Infeasible$\Delta_{d}(i)>c_{2}$$U_{a}^{c}(i)>c_{1}$$U_{a}^{u}(i)<c_{1}$$i\in
I_{3}$$\Delta_{d}(i)<c_{2}$$i\in
I_{5}$$\Delta_{d}(i)>c_{2}$$U_{a}^{c}(i)<c_{1}$$i\in
I_{3}$$\Delta_{d}(i)<c_{2}$$i\in
I_{9}$$\Delta_{d}(i)>c_{2}$$U_{a}^{c}(i)>c_{1}$$U_{a}^{u}(i)>c_{1}$

######  Remark 3.10.

We note that the efficiency of the algorithm presented in the proof of Theorem
3.8 can be greatly improved by incorporating further paring-down of the search
space. For example, the procedure in case (i) for type I.B.ii equilibria may
be improved by employing the decision diagram in Figure 1 to prune the search
space.

######  Remark 3.11.

It is clear from the proof of Theorem 3.8 that the pseudopolynomial time
algorithm is readily extended to optimization over a domain in which more than
two choices are present for each parameter and these choices satisfy an analog
of Assumption 2.

######  Example 3.12.

Consider the following game on five targets with $k_{a}=3,k_{d}=2$:

Target: | 1 | 2 | 3 | 4 | 5
---|---|---|---|---|---
$lb_{a}^{c}(i)$ | 10 | 48 | 5 | 31 | 25
$ub_{a}^{c}$(i) | 17 | 49 | 9 | 40 | 29
$lb_{a}^{u}$(i) | 20 | 51 | 41 | 63 | 90
$ub_{a}^{c}$(i) | 35 | 60 | 42 | 70 | 95
$U_{a}^{c}$(i) | -1 | -4 | -9 | -3 | -2
$U_{a}^{u}$(i) | -7 | -6 | -12 | -8 | -9

The algorithm described in the proof of Theorem 3.8 finds a feasible choice of
parameters yielding the optimal defender expected outcome $v_{d}=-18$ given by

Target: | 1 | 2 | 3 | 4 | 5
---|---|---|---|---|---
$U_{a}^{c}(i)$ | $ub$ | $lb$ | $lb$ | $ub$ | $lb$
$U_{a}^{u}(i)$ | $lb$ | $ub$ | $lb$ | $ub$ | $ub$

corresponding to a type I.A.i equilibrium with $r=s=t=1$ and

Target: | 1 | 2 | 3 | 4 | 5
---|---|---|---|---|---
$\alpha_{i}$ | 0 | 1 | 7/10 | 1 | 3/10
$\beta_{i}$ | 0 | 0 | $\approx 0.1509$ | 1 | $\approx 0.8491$

##  4 Nearest Additive Games

The structural characterization presented in the previous sections and the
extensive body of literature concerning additive security games suggest the
question: how can we utilize the theory of additive security games to address
the solution of non-additive security games? One line of inquiry concerns
finding, for any non-additive game, an additive game that is ‘close’ in terms
of payoffs. This strategy is adopted to study the class of potential games in
[Candogan _et al._ (2013)] in which a notion of near-potential games is
developed through introducing a distance measure on the space of all games.
Motivated by this work, in this section we propose an answer to the question:
Given a non-additive security game, what is the nearest additive game?

Let $(A,B,k_{a},k_{d},U_{a}^{c},U_{a}^{u},U_{d}^{c},U_{d}^{u})$ be a non-
additive security game over a target set $T=[m]$ expressed as a bimatrix game.
In this section, assume that for each $1\leq k\leq m$ we have fixed an
ordering of each of the sets $2^{\leq k}=\\{S\subseteq[m]:|S|\leq k\\}$.
Consider that each entry of each payoff matrix is the result of the evaluation
of some set function $f:2^{[m]}\to\mathbb{R}$ on a collection of targets.
Accordingly, we first define a notion of nearest additive function to $f$.

######  Definition 4.1.

Let $\mathbf{x}\in\mathbb{R}^{m}$. The additive function defined by
$\mathbf{x}$ is the map $h_{\mathbf{x}}:2^{[m]}\to\mathbb{R}$ given by

$h_{\mathbf{x}}(S)=\sum_{i\in S}x_{i}.$

We represent all set functions as vectors of their codomains as follows:

######  Definition 4.2.

For any $f:2^{[m]}\to\mathbb{R}$ and $1\leq k\leq m$, represent $f$ as a
vector $I_{k}(f)\in\mathbb{R}^{|2^{\leq k}|}$ by

$\langle I_{k}(f)\rangle_{i}=f(S_{i})$

where $S_{i}$ is the $i^{th}$ element of $2^{\leq k}$.

We now introduce the notion of nearest additive function.

######  Definition 4.3.

Let $1\leq k\leq m$ and $f:2^{[m]}\to\mathbb{R}$. A $k-$nearest additive
function to $f$ is a function $h_{\mathbf{x}}$ such that

$\mathbf{x}=\operatorname*{arg\,min}_{\mathbf{y}}||I_{k}(f)-I_{k}(h_{\mathbf{y}})||$

where $||\cdot||$ is the euclidean norm on $\mathbb{R}^{|2^{\leq k}|}$. When
such a function exists, denote it by $[f]_{k}$.

######  Theorem 4.4.

For any $1\leq k\leq m$ and $f:2^{[m]}\to\mathbb{R}$, $[f]_{k}$ exists and is
unique.

######  Proof 4.5.

Let $V=\\{I_{k}(h_{\mathbf{x}})\in\mathbb{R}^{|2^{\leq
k}|}:\mathbf{x}\in\mathbb{R}^{m}\\}$ be the space of functions that are
additive on sets in $2^{\leq k}$. For each $i\in[m]$, let
$\chi_{i}:2^{m}\to\mathbb{R}$ be defined by

$\chi_{i}(S)=\begin{cases}1&\text{ if }i\in S\\\ 0&\text{
otherwise}\end{cases}.$

Note that $V=\text{span}\\{I_{k}(\chi_{1}),\dots,I_{k}(\chi_{m})\\}$ as

$I_{k}(h_{\mathbf{x}})=\sum_{i=1}^{m}x_{i}I_{k}(\chi_{i}).$

Thus $V$ is a linear subspace of $\mathbb{R}^{|2^{\leq k}|}$ and the
projection of any $I_{k}(f)$ onto $V$ is unique and meets the condition of
Definition 4.3.

A direct consequence of Theorem 4.4 is that we can obtain the following
closed-form expression for $\mathbf{x}$:

######  Corollary 4.6.

For any $1\leq k\leq m$ and $f:2^{[m]}\to\mathbb{R}$, the unique
$\mathbf{x}\in\mathbb{R}^{m}$ meeting the condition of Definition 4.3 has the
form

$x_{i}=(\sigma_{1}+\sigma_{2})\sum_{i\in S\atop|S|\leq
k}f(S)+\sigma_{2}\sum_{j\neq i}\sum_{j\in S\atop|S|\leq k}f(S)$ (9)

where

$\sigma_{1}={1\over\sum_{t=0}^{k-1}{m-1\choose t}-\sum_{t=0}^{k-2}{m-2\choose
t}}$

and

$\sigma_{2}={\sum_{t=0}^{k-2}{m-2\choose
t}\over\left(\sum_{t=0}^{k-1}{m-1\choose t}-\sum_{t=0}^{k-2}{m-2\choose
t}\right)\left(\sum_{t=0}^{k-1}{m-1\choose t}-(m+1)\sum_{t=0}^{k-2}{m-2\choose
t}\right)}.$

######  Proof 4.7.

Let $g:\mathbb{R}^{m}\to\mathbb{R}$ be defined by
$g(\mathbf{x})=\|I_{k}(h_{\mathbf{x}})-I_{k}(f)\|^{2}$. Note that

$\displaystyle{\partial g\over\partial x_{i}}$
$\displaystyle=-2\left(\sum_{i\in S\in 2^{\leq
k}}f(S)-\sum_{j=1}^{m}\left|\\{S\in 2^{\leq k}:i,j\in S\\}\right|x_{j}\right)$
$\displaystyle=-2\left(\sum_{i\in S\in 2^{\leq k}}f(S)-\sum_{i\neq
j}\sum_{t=0}^{k-2}{m-2\choose t}x_{j}-\sum_{t=0}^{k-1}{m-1\choose
t}x_{i}\right).$

Therefore $\nabla g=0$ if and only if for all $i$,

$\sum_{i\in S\in 2^{\leq k}}f(S)=\sum_{i\neq j}\sum_{t=0}^{k-2}{m-2\choose
t}x_{j}+\sum_{t=0}^{k-1}{m-1\choose t}x_{i}.$

Equivalently,

$\left(\left[\sum_{t=0}^{k-2}{m-2\choose t}\right](\mathbbm{1}_{m\times
m}-I_{m})+\left[\sum_{t=0}^{k-1}{m-1\choose
t}\right]I_{m}\right)\mathbf{x}=\boldsymbol{\gamma}$

where $\gamma_{i}=\sum_{i\in S\in 2^{\leq k}}f(S)$. Note that for any
$a,b\in\mathbb{R}$ we have

$[(a-b)I_{m}+b\mathbbm{1}_{m\times m}]^{-1}={1\over
a-b}I+{b\over(a-b)(a-b(m+1))}\mathbbm{1}_{m\times m}.$

Thus, $x_{i}$ has the specified form.

We now propose the notion of nearest additive game.

######  Definition 4.8.

Let $G=(A,B,k_{a},k_{d},U_{a}^{c},U_{a}^{u},U_{d}^{c},U_{d}^{u})$ be a
(possibly non-additive) security game. The nearest additive game to $G$ is the
additive game defined by
$k_{a},k_{d},[U_{a}^{c}]_{k_{a}},[U_{a}^{u}]_{k_{a}},[U_{d}^{c}]_{k_{a}},[U_{d}^{u}]_{k_{a}}$.

######  Remark 4.9.

Note that we choose the $k_{a}$-nearest additive payoff functions in our
definition of nearest additive game. We have, for $f:2^{[m]}\to\mathbb{R}$ and
$k\leq k^{\prime}$

$\min_{\mathbf{x}}||I_{k}(f)-I_{k}(h_{\mathbf{x}})||\leq\min_{\mathbf{x}}||I_{k^{\prime}}(f)-I_{k^{\prime}}(h_{\mathbf{x}})||$

as

$\|I_{k^{\prime}}(h_{\mathbf{x}^{\prime}})-I_{k^{\prime}}(f)\|^{2}\geq\sum_{S\in
2^{\leq
k}}(h_{\mathbf{x}^{\prime}}(S)-f(S))^{2}\geq\|I_{k}(h_{\mathbf{x}})-I_{k}(f)\|^{2}.$

Thus, the approximation is better for smaller values of $k$. The payoff
functions will be evaluated on sets of size at most $k_{a}$, and so we select
this value of $k$ in our nearest additive game.

######  Remark 4.10.

The nearest additive game to an additive game is the additive game itself. If
$f=h_{\mathbf{x}}$ is an additive function, $\mathbf{y}=\mathbf{x}$ clearly
minimizes $\|I_{k}(f)-I_{k}(h_{\mathbf{y}})\|=0$.

Suppose $(A,B)$ and $(\overline{A},\overline{B})$ are a non-additive security
game and its nearest additive game respectively. Let $(p,q)$ and
$(\overline{p},\overline{q})$ be Nash equilibrium profiles in the original and
nearest additive games respectively. Observe that $p^{t}Bq$ is the actual
expected outcome to the defender in the original game and
$p^{t}B\overline{q}\leq p^{t}Bq$ is the expected outcome to the defender when
she plays the original game using his strategy from the nearest additive game.
The relative error (for the defender) in using the approximation, therefore,
is given by $|p^{t}Bq-p^{t}B\overline{q}|/p^{t}Bq$.

Figure 2: The underlying graph of our 14 bus power system. In the zero-sum
game we take $k_{a}=k_{d}=2$. The values of $(\alpha_{i},\beta_{i})$ for each
edge $i$ are shown for the nearest additive game (left) and the additive game
defined by the 1-line disturbance values (right). Power supply and demand
values for each node correspond to those in the standard IEEE 14-Bus power
system test case, and line reactances are given in the table found in Appendix
C.

######  Example 4.11.

An example of a function which is well-approximated by an additive function is
given in [Soltan _et al._ (2017)] wherein the notion of disturbance value is
introduced to quantify the effect of $k$-line failures in power grids. The
$k-$line disturbance value of a set of line failures of size $k$ is well
approximated by the sum of the $k$ individual 1-line disturbance values in
large power grids. That is,
$\delta_{k}(\\{e_{1},\dots,e_{k}\\})\approx\sum_{i=1}^{k}\delta_{1}(\\{e_{i}\\})$.
As in [Emadi _et al._ (2021)], we define a zero-sum security game over the
edges of a power grid in which resources are fully protective and the payoffs
to the attacker for a set of successfully attacked lines is given by the
disturbance value. The relative error in $v^{*}$ when the nearest 2-additive
game is solved is less than half of the relative error when the 1-line
disturbance values are taken to be the additive constants. In the game defined
on the grid in Figure 2 we have $v^{*}_{\text{actual}}\approx 15.123$,
$v^{*}_{\text{addapprox}}\approx 17.815$, and $v^{*}_{\text{additive}}\approx
20.614$ giving $error_{addapprox}\approx 17.8\%$ and $error_{additive}\approx
36.3\%$.

The above examples suggest further study to address the following (open)
problems:

######  Problem 4.12.

For what classes of $U_{a}^{c},U_{a}^{u},U_{d}^{c},U_{d}^{u}$ can
$|v_{d}^{*}-[v_{d}^{*}]_{k}|$, where $[v_{d}^{*}]$ is the defender expected
outcome in the nearest additive game, be bounded?

######  Problem 4.13.

Let $(p^{*},q^{*}),(\overline{p}^{*},\overline{q}^{*})$ denote Nash
equilibrium profiles in a non-additive security game and the nearest additive
game respectively. Let $(A,B)$ and $(\overline{A},\overline{B})$ be the
bimatrix representations of these games. For what classes of
$U_{a}^{c},U_{a}^{u},U_{d}^{c},U_{d}^{u}$ can
$|p^{*}Bq^{*}-p^{*}B\overline{q}^{*}|$ be bounded? That is: when is the
defender justified in using the strategy she computes using the nearest
additive game approximation?

##  5 Conclusion

In this work, we have contributed to the theory of Nash equilibria in additive
security games with singleton schedules and multiple homogeneous attacker and
defender resources by proposing a novel structural approach. Our structural
analysis of the necessary properties of equilibria in security games have lead
to a characterization of the possible types of Nash equilibria in these games
and consequently, a new algorithm for computation of such equilibria. Our
characterization yields closed-form expressions for the player expected
outcomes at equilibrium as well as explicit feasibility conditions for
equilibria of each type. We have shown that in the case of fully protective
resources, a restricted structure of equilibrium types emerges and that our
solution algorithm can be made more efficient. Finally, to address the problem
of maximizing the defender expected utility at equilibrium given that the
attacker payoffs may be perturbed, we show that (fundamentally owing to the
NP-hardness of computing Stackelberg equilibria in the case of multiple
attacker resources) this problem is NP hard for Stackelberg equilibria and
propose a pseudopolynomial time algorithm for the case of Nash equilibria
under a disjointness assumption.

We propose the following as promising directions for future work:

  * •

Extension of our structural approach to the classes of games [Korzhyk _et al._
(2010), Letchford and Conitzer (2013)] with schedule structures admitting
polynomial-time solution algorithms and to repeated games.

  * •

Determination of the computational complexity of Problem 3.1 and development
approximation techniques or approaches that solve typical instances
efficiently for the case of Stackelberg equilibria.

  * •

Utilization of the comprehensively understood class of additive security games
to compute approximate solutions to non-additive security games (which are NP-
hard in general) through the development of projection frameworks. In
particular, we seek a classification of the nearly additive games.

## References

  * [Alpcan and Başar (2010)] Alpcan, T. and Başar, T. [2010] _Network security: A decision and game-theoretic approach_ (Cambridge University Press).
  * [Bhurjee(2016)] Bhurjee, A. K. [2016] Existence of equilibrium points for bimatrix game with interval payoffs, _International Game Theory Review_ 18(01), 1650002.
  * [Blocki _et al._ (2015)] Blocki, J., Christin, N., Datta, A., Procaccia, A. and Sinha, A. [2015] Audit games with multiple defender resources, in _Proceedings of the AAAI Conference on Artificial Intelligence_.
  * [Blocki _et al._ (2013)] Blocki, J., Christin, N., Datta, A., Procaccia, A. D. and Sinha, A. [2013] Audit games, _arXiv preprint arXiv:1303.0356_ .
  * [Brams _et al._ (1996)] Brams, S. J., Brams, S. J. and Taylor, A. D. [1996] _Fair Division: From cake-cutting to dispute resolution_ (Cambridge University Press).
  * [Budish _et al._ (2013)] Budish, E., Che, Y.-K., Kojima, F. and Milgrom, P. [2013] Designing random allocation mechanisms: Theory and applications, _American economic review_ 103(2), 585–623.
  * [Candogan _et al._ (2013)] Candogan, O., Ozdaglar, A. and Parrilo, P. A. [2013] Near-potential games: Geometry and dynamics, _ACM Transactions on Economics and Computation (TEAC)_ 1(2), 1–32.
  * [Conitzer and Sandholm (2006)] Conitzer, V. and Sandholm, T. [2006] Computing the optimal strategy to commit to, in _Proceedings of the 7th ACM conference on Electronic commerce_ (ACM), pp. 82–90.
  * [Cormen _et al._ (2022)] Cormen, T. H., Leiserson, C. E., Rivest, R. L. and Stein, C. [2022] _Introduction to algorithms_ (MIT press).
  * [Emadi and Bhattacharya (2019)] Emadi, H. and Bhattacharya, S. [2019] On security games with additive utility, _IFAC-PapersOnLine_ 52(20), 351–356.
  * [Emadi and Bhattacharya (2020a)] Emadi, H. and Bhattacharya, S. [2020a] On the characterization of saddle point equilibrium for security games with additive utility, in _Decision and Game Theory for Security - 11th International Conference,GameSec 2020, College Park, MD, USA, October 28-30, 2020, Proceedings_ , Lecture Notes in Computer Science, Vol. 12513 (Springer), pp. 349–364.
  * [Emadi and Bhattacharya (2020b)] Emadi, H. and Bhattacharya, S. [2020b] On the characterization of saddle point equilibrium for security games with additive utility, _arXiv preprint arXiv:2007.14478_ .
  * [Emadi _et al._ (2021)] Emadi, H., Clanin, J., Hyder, B., Khanna, K., Govindarasu, M. and Bhattacharya, S. [2021] An efficient computational strategy for cyber-physical contingency analysis in smart grids, in _IEEE PES General Meeting_.
  * [Ferguson and Melolidakis (2000)] Ferguson, T. S. and Melolidakis, C. [2000] Games with finite resources, _International Journal of Game Theory_ 29(2), 289–303.
  * [Gross and Wagner (1950)] Gross, O. and Wagner, R. [1950] A continuous colonel blotto game, Tech. rep., Rand Project Air Force Santa Monica Ca.
  * [Hausken(2012)] Hausken, K. [2012] On the impossibility of deterrence in sequential colonel blotto games, _International Game Theory Review_ 14(02), 1250011.
  * [Hausken(2017)] Hausken, K. [2017] Information sharing among cyber hackers in successive attacks, _International Game Theory Review_ 19(02), 1750010\.
  * [Hausken(2021)] Hausken, K. [2021] Governments playing games and combating the dynamics of a terrorist organization, _International Game Theory Review_ 23(02), 2050013.
  * [Horn and Johnson (2012)] Horn, R. A. and Johnson, C. R. [2012] _Matrix analysis_ (Cambridge university press).
  * [Jain _et al._(2010)] Jain, M., Kardes, E., Kiekintveld, C., Ordónez, F. and Tambe, M. [2010] Security games with arbitrary schedules: A branch and price approach, in _Proceedings of the AAAI Conference on Artificial Intelligence_ , pp. 792–797.
  * [Kiekintveld _et al._ (2009)] Kiekintveld, C., Jain, M., Tsai, J., Pita, J., Ordóñez, F. and Tambe, M. [2009] Computing optimal randomized resource allocations for massive security games, in _Proceedings of The 8th International Conference on Autonomous Agents and Multiagent Systems-Volume 1_ (International Foundation for Autonomous Agents and Multiagent Systems), pp. 689–696.
  * [Korzhyk _et al._ (2010)] Korzhyk, D., Conitzer, V. and Parr, R. [2010] Complexity of computing optimal stackelberg strategies in security resource allocation games, in _Twenty-Fourth AAAI Conference on Artificial Intelligence_.
  * [Korzhyk _et al._ (2011a)] Korzhyk, D., Conitzer, V. and Parr, R. [2011a] Security games with multiple attacker resources, in _Twenty-Second International Joint Conference on Artificial Intelligence_.
  * [Korzhyk _et al._ (2011b)] Korzhyk, D., Yin, Z., Kiekintveld, C., Conitzer, V. and Tambe, M. [2011b] Stackelberg vs. nash in security games: An extended investigation of interchangeability, equivalence, and uniqueness, _Journal of Artificial Intelligence Research_ 41, 297–327.
  * [Lerma _et al._ (2011)] Lerma, O., Kreinovich, V. and Kiekintveld, C. [2011] Linear-time resource allocation in security games with identical fully protective resources, in _Workshops at the Twenty-Fifth AAAI Conference on Artificial Intelligence_.
  * [Letchford and Conitzer (2013)] Letchford, J. and Conitzer, V. [2013] Solving security games on graphs via marginal probabilities, in _Twenty-Seventh AAAI Conference on Artificial Intelligence_.
  * [Manshaei _et al._ (2013)] Manshaei, M. H., Zhu, Q., Alpcan, T., Başar, T. and Hubaux, J.-P. [2013] Game theory meets network security and privacy, _ACM Computing Surveys (CSUR)_ 45(3), 25.
  * [Neumann (1928)] Neumann, J. v. [1928] Zur theorie der gesellschaftsspiele, _Mathematische annalen_ 100(1), 295–320.
  * [Perera(2022)] Perera, R. S. [2022] A stackelberg-nash-cournot equilibrium in a pollution reduction scheme, _International Game Theory Review_ 24(02), 2150014.
  * [Shi _et al._ (2018)] Shi, Z. R., Tang, Z., Tran-Thanh, L., Singh, R. and Fang, F. [2018] Designing the game to play: optimizing payoff structure in security games, _arXiv preprint arXiv:1805.01987_ .
  * [Soltan _et al._ (2017)] Soltan, S., Loh, A. and Zussman, G. [2017] Analyzing and quantifying the effect of $k$-line failures in power grids, _IEEE Transactions on Control of Network Systems_ .
  * [Tambe (2011)] Tambe, M. [2011] _Security and game theory: algorithms, deployed systems, lessons learned_ (Cambridge university press).
  * [Wang _et al._ (2017)] Wang, S., Liu, F. and Shroff, N. [2017] Non-additive security games, in _Thirty-First AAAI Conference on Artificial Intelligence_.
  * [Wang and Shroff (2017)] Wang, S. and Shroff, N. [2017] Security game with non-additive utilities and multiple attacker resources, _Proceedings of the ACM on Measurement and Analysis of Computing Systems_ 1(1), 13.
  * [Xu (2016)] Xu, H. [2016] The mysteries of security games: Equilibrium computation becomes combinatorial algorithm design, in _Proceedings of the 2016 ACM Conference on Economics and Computation_ (ACM), pp. 497–514.
  * [Yin _et al._ (2010)] Yin, Z., Korzhyk, D., Kiekintveld, C., Conitzer, V. and Tambe, M. [2010] Stackelberg vs. nash in security games: Interchangeability, equivalence, and uniqueness, in _Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems: Volume 1_ (International Foundation for Autonomous Agents and Multiagent Systems), pp. 1139–1146.

##  Appendix A Closed-Form Expressions for Player Expected Outcome at
Equilibrium

Type I.A.i:

$\displaystyle v_{a}^{*}$ $\displaystyle=\sum_{i\in
I_{3}}U_{a}^{u}(i)+\sum_{i\in I_{9}}U_{a}^{c}(i)+\sum_{i\in
I_{5}}{(k_{a}-s-t)\left(k_{d}-t-\sum_{j\in
I_{5}}{U_{a}^{u}(j)\over\Delta_{a}(j)}\right)\over\Delta_{d}(i)\left(\sum_{j\in
I_{5}}{1\over\Delta_{d}(j)}\right)\left(\sum_{j\in
I_{5}}{1\over\Delta_{a}(j)}\right)}$ (10) $\displaystyle v_{d}^{*}$
$\displaystyle=\sum_{i\in I_{3}}U_{d}^{u}(i)+\sum_{i\in
I_{9}}U_{d}^{c}(i)+\sum_{i\in I_{5}}{(t+s-k_{a})\left(k_{d}-t-\sum_{j\in
I_{5}}{U_{a}^{u}(j)\over\Delta_{a}(j)}\right)\over\Delta_{a}(i)\left(\sum_{j\in
I_{5}}{1\over\Delta_{d}(j)}\right)\left(\sum_{j\in
I_{5}}{1\over\Delta_{a}(j)}\right)}$

Type I.A.ii:

$\displaystyle v_{a}^{*}$
$\displaystyle=\alpha_{j^{[2]}}U_{a}^{u}(j^{[2]})+\sum_{i\in
I_{3}}U_{a}^{u}(i)+\sum_{i\in I_{9}}U_{a}^{c}(i)$ (11)
$\displaystyle+\sum_{i\in
I_{5}}{(k_{a}{-}s{-}t{-}\alpha_{j^{[2]}})[(U_{a}^{u}(i){-}U_{a}^{u}(j^{[2]}))U_{a}^{c}(i){+}(\Delta_{a}(i){-}U_{a}^{u}(i){+}U_{a}^{u}(j^{[2]}))U_{a}^{u}(i)]\over\Delta_{a}(i)\Delta_{d}(i)\sum_{j\in
I_{5}}{1\over\Delta_{d}(j)}}$ $\displaystyle v_{d}^{*}$
$\displaystyle=\alpha_{j^{[2]}}U_{d}^{u}(j^{[2]})+\sum_{i\in
I_{3}}U_{d}^{u}(i)+\sum_{i\in I_{9}}U_{d}^{c}(i)$ $\displaystyle+\sum_{i\in
I_{5}}{(k_{a}{-}s{-}t{-}\alpha_{j^{[2]}})[(U_{a}^{u}(i){-}U_{a}^{u}(j^{[2]}))U_{d}^{c}(i){+}(\Delta_{a}(i){-}U_{a}^{u}(i){+}U_{a}^{u}(j^{[2]}))U_{d}^{u}(i)]\over\Delta_{a}(i)\Delta_{d}(i)\sum_{j\in
I_{5}}{1\over\Delta_{d}(j)}}$

Type I.A.iii:

$\displaystyle v_{a}^{*}$
$\displaystyle=\alpha_{j^{[8]}}U_{a}^{c}(j^{[8]})+\sum_{i\in
I_{3}}U_{a}^{u}(i)+\sum_{i\in I_{9}}U_{a}^{c}(i)$ (12)
$\displaystyle+\sum_{i\in
I_{5}}{(k_{a}-s-t-\alpha_{j^{[8]}})[(U_{a}^{u}(i)-U_{a}^{c}(j^{[8]}))U_{a}^{c}(i)+(\Delta_{a}(i)-U_{a}^{u}(i)+U_{a}^{c}(j^{[8]}))U_{a}^{u}(i)]\over\Delta_{a}(i)\Delta_{d}(i)\sum_{j\in
I_{5}}{1\over\Delta_{d}(j)}}$ $\displaystyle v_{d}^{*}$
$\displaystyle=\alpha_{j^{[8]}}U_{d}^{c}(j^{[8]})+\sum_{i\in
I_{3}}U_{d}^{u}(i)+\sum_{i\in I_{9}}U_{d}^{c}(i)$ $\displaystyle+\sum_{i\in
I_{5}}{(k_{a}-s-t-\alpha_{j^{[8]}})[(U_{a}^{u}(i)-U_{a}^{c}(j^{[8]}))U_{d}^{c}(i)+(\Delta_{a}(i)-U_{a}^{u}(i)+U_{a}^{c}(j^{[8]}))U_{d}^{u}(i)]\over\Delta_{a}(i)\Delta_{d}(i)\sum_{j\in
I_{5}}{1\over\Delta_{d}(j)}}$

Type I.B.i:

$\displaystyle v_{a}^{*}$
$\displaystyle=U_{a}^{u}(j^{[6]})+\beta_{j^{[6]}}\Delta_{a}(j^{[6]})+\sum_{i\in
I_{3}}U_{a}^{u}(i)+\sum_{i\in I_{9}}U_{a}^{c}(i)$ (13)
$\displaystyle+\sum_{i\in
I_{5}}{\Delta_{d}(j^{[6]})\over\Delta_{d}(i)\sum_{j\in
I_{5}}{1\over\Delta_{d}(j)}}\left[\sum_{j\in
I_{5}}{U_{a}^{u}(j)\over\Delta_{a}(j)}{+}{1\over\Delta_{a}(i)}[(U_{a}^{u}(i){+}U_{a}^{c})(t{+}\beta_{j^{[6]}}){-}\Delta_{a}(i)k_{d}]\right]$
$\displaystyle v_{d}^{*}$
$\displaystyle=U_{d}^{u}(j^{[6]})+\beta_{j^{[6]}}\Delta_{d}(j^{[6]})+\sum_{i\in
I_{3}}U_{d}^{u}(i)+\sum_{i\in I_{9}}U_{d}^{c}(i)$ $\displaystyle+\sum_{i\in
I_{5}}{\Delta_{d}(j^{[6]})\over\Delta_{a}(i)\Delta_{d}(i)\sum_{j\in
I_{5}}{1\over\Delta_{a}(j)}}\left[\Delta_{d}(i)k_{d}{+}(U_{d}^{u}(i){+}U_{d}^{c}(i))(t{+}\beta_{j^{[6]}}){-}\Delta_{d}(i)\sum_{j\in
I_{5}}{U_{u}^{a}(j)\over\Delta_{a}(j)}\right]$

Type I.B.ii:

$\displaystyle v_{a}^{*}$ $\displaystyle=\sum_{i\in
I_{3}}U_{a}^{u}(i)+\sum_{i\in I_{9}}U_{a}^{c}(i)+\left[k_{a}-s-t-1-\sum_{i\in
I_{5}}{\Delta_{d}(j^{[6]})\over\Delta_{d}(i)}\right]U_{a}^{u}(j^{[2]})+U_{a}^{u}(j^{[6]})$
(14) $\displaystyle-\left[k_{d}-t-\sum_{i\in
I_{5}}{U_{a}^{u}(i)-U_{a}^{u}(j^{[2]})\over\Delta_{a}(i)}\right]U_{a}^{u}(j^{[6]})$
$\displaystyle+\sum_{i\in
I_{5}}{\Delta_{d}(j^{[6]})[(U_{a}^{u}(i)-U_{a}^{u}(j^{[2]}))U_{a}^{c}(i)+(U_{a}^{u}(j^{[2]})-U_{a}^{c}(i))U_{a}^{u}(i)]\over\Delta_{a}(i)\Delta_{d}(i)}$
$\displaystyle v_{d}^{*}$ $\displaystyle=\sum_{i\in
I_{3}}U_{d}^{u}(i)+\sum_{i\in I_{9}}U_{d}^{c}(i)+\left[k_{a}-s-t-1-\sum_{i\in
I_{5}}{\Delta_{d}(j^{[6]})\over\Delta_{d}(i)}\right]U_{d}^{u}(j^{[2]})+U_{d}^{u}(j^{[6]})$
$\displaystyle-\left[k_{d}-t-\sum_{i\in
I_{5}}{U_{a}^{u}(i)-U_{a}^{u}(j^{[2]})\over\Delta_{a}(i)}\right]U_{d}^{u}(j^{[6]})$
$\displaystyle+\sum_{i\in
I_{5}}{\Delta_{d}(j^{[6]})[(U-a^{u}(i)-U_{a}^{u}(j^{[2]}))U_{d}^{c}(i)+(U_{a}^{u}(j^{[2]})-U_{a}^{c}(i))U_{d}^{u}(i)]\over\Delta_{a}(i)\Delta_{d}(i)}$

Type I.B.iii:

$\displaystyle v_{a}^{*}$ $\displaystyle=\sum_{i\in
I_{3}}U_{a}^{u}(i)+\sum_{i\in
I_{9}}U_{a}^{c}(i)+U_{a}^{u}(j^{[6]})-\left[k_{a}-t-1-\sum_{i\in
I_{5}}{U_{a}^{u}(i)-U_{a}^{c}(j^{[8]})\over\Delta_{a}(i)}\right]\Delta_{a}(j^{[6]})$
(15) $\displaystyle+\left[k_{a}-s-t-\sum_{i\in
I_{5}}{\Delta_{d}(j^{[6]})\over\Delta_{d}(i)}\right]U_{a}^{c}(j^{[8]}))$
$\displaystyle+\sum_{i\in
I_{5}}{\Delta_{d}(j^{[6]})[(U_{a}^{u}(i)-U_{a}^{c}(j^{[8]})U_{a}^{c}(i)+(U_{a}^{c}(j^{[8]}-U_{a}^{c}(i))U_{a}^{u}(i)]\over\Delta_{a}(i)\Delta_{d}(i)}$
$\displaystyle v_{d}^{*}$ $\displaystyle=\sum_{i\in
I_{3}}U_{d}^{u}(i)+\sum_{i\in
I_{9}}U_{d}^{c}(i)+U_{d}^{u}(j^{[6]})+\left[k_{a}-t-1-\sum_{i\in
I_{5}}{U_{a}^{u}(i)-Ua^{c}(j^{[8]})\over\Delta_{a}(i)}\right]\Delta_{d}(j^{[6]})$
$\displaystyle+\left[k_{a}-s-t-\sum_{i\in
I_{5}}{\Delta_{d}(j^{[6]})\over\Delta_{d}(i)}\right]U_{d}^{c}(j^{[8]})$
$\displaystyle+\sum_{i\in
I_{5}}{\Delta_{d}(j^{[6]})[(U_{a}^{u}(i)-U_{a}^{c}(j^{[8]})U_{d}^{c}(i)+(U_{a}^{c}(j^{[8]}-U_{a}^{c}(i))U_{d}^{u}(i)]\over\Delta_{a}(i)\Delta_{d}(i)}$

Type II:

$v_{a}^{*}=\sum_{i\in I_{9}}U_{a}^{c}(i)\hskip 20.00003ptv_{d}^{*}=\sum_{i\in
I_{9}}U_{d}^{c}(i)$ (16)

##  Appendix B Closed-Form Expressions for Player Expected Outcome at
Equilibrium: Fully Protective Resources

I.A.i with $I_{9}=\emptyset$

$\displaystyle v_{a}^{*}$ $\displaystyle=\sum_{i\in
I_{3}}U_{a}^{u}(i)+\sum_{i\in I_{5}}{k_{a}-s\over U_{d}^{u}(i)\sum_{j\in
I_{5}}{1\over U_{d}^{u}(j)}}\left[U_{a}^{u}(i)-{k_{a}-m+r+s\over\sum_{j\in
I_{5}}{1\over U_{a}^{u}(j)}}\right]$ (17) $\displaystyle v_{d}^{*}$
$\displaystyle=\sum_{i\in I_{3}}U_{d}^{u}(i)+\sum_{i\in I_{5}}{k_{a}-s\over
U_{a}^{u}(i)\sum_{j\in I_{5}}{1\over
U_{d}^{u}(j)}}\left[U_{a}^{u}(i)-{k_{a}-m+r+s\over\sum_{j\in I_{5}}{1\over
U_{a}^{u}(j)}}\right]$

I.A.ii with $I_{9}=\emptyset$

$\displaystyle v_{a}^{*}$
$\displaystyle=\alpha_{j^{[2]}}U_{a}^{u}(j^{[2]})+\sum_{i\in
I_{3}}U_{a}^{u}(i)+\sum_{i\in
I_{5}}{(k_{a}-s-\alpha_{j^{[2]}})(U_{a}^{u}(i)-U_{a}^{u}(j^{[2]}))\over
U_{d}^{u}(i)\sum_{j\in I_{5}}{1\over U_{d}^{u}(j)}}$ (18) $\displaystyle
v_{d}^{*}$ $\displaystyle=\alpha_{j^{[2]}}U_{d}^{u}(j^{[2]})+\sum_{i\in
I_{3}}U_{d}^{u}(i)+\sum_{i\in
I_{5}}{(k_{a}-s-\alpha_{j^{[2]}})(U_{a}^{u}(i)-U_{a}^{u}(j^{[2]}))\over
U_{a}^{u}(i)\sum_{j\in I_{5}}{1\over U_{d}^{u}(j)}}$

I.B.i with $I_{9}=\emptyset$

$\displaystyle v_{a}^{*}$ $\displaystyle=\sum_{i\in
I_{3}}U_{a}^{u}(i)+U_{a}^{u}(j^{[6]})(1-\beta_{j^{[6]}})+\sum_{i\in
I_{5}}{U_{d}^{u}(j^{[6]})\over
U_{d}^{u}(i)}\left[U_{a}^{u}(i){-}{k_{d}{-}m{+}r{+}s{+}1{-}\beta_{j^{[6]}}\over\sum_{j\in
I_{5}}{1\over U_{a}^{u}(j)}}\right]$ (19) $\displaystyle v_{d}^{*}$
$\displaystyle=\sum_{i\in
I_{3}}U_{d}^{u}(i)+U_{a}^{u}(j^{[6]})(1-\beta_{j^{[6]}})+\sum_{i\in
I_{5}}{U_{d}^{u}(j^{[6]})\over
U_{a}^{u}(i)}\left[U_{a}^{u}(i){-}{k_{d}{-}m{+}r{+}s{+}1{-}\beta_{j^{[6]}}\over\sum_{j\in
I_{5}}{1\over U_{a}^{u}(j)}}\right]$

I.B.ii with $I_{9}=\emptyset$

$\displaystyle v_{a}^{*}$ $\displaystyle=\left[k_{a}{-}s{-}1{-}\sum_{i\in
I_{5}}{U_{d}^{u}(j^{[6]})\over
U_{d}^{u}(i)}\right]U_{a}^{u}(j^{[2]})+\sum_{i\in
I_{3}}U_{a}^{u}(i)+\sum_{i\in I_{3}}U_{a}^{u}(i)$ (20)
$\displaystyle+\sum_{i\in
I_{5}}{U_{d}^{u}(j^{[6]})[U_{a}^{u}(i)-U_{a}^{u}(j^{[2]})\over U_{d}^{u}(i)]}$
$\displaystyle v_{d}^{*}$ $\displaystyle=\left[k_{a}{-}s{-}1{-}\sum_{i\in
I_{5}}{U_{d}^{u}(j^{[6]})\over
U_{d}^{u}(i)}\right]U_{d}^{u}(j^{[2]})+\sum_{i\in
I_{3}}U_{d}^{u}(i)+\sum_{i\in I_{3}}U_{d}^{u}(i)$ $\displaystyle+\sum_{i\in
I_{5}}{U_{d}^{u}(j^{[6]})[U_{a}^{u}(i)-U_{a}^{u}(j^{[2]})\over U_{a}^{u}(i)]}$

I.B.iii with $I_{1}\cup I_{5}=\emptyset$

$v_{a}^{*}=\sum_{i\in I_{3}}U_{a}^{u}(i)\hskip 20.00003ptv_{a}^{*}=\sum_{i\in
I_{3}}U_{d}^{u}(i)$ (21)

##  Appendix C Line Reactance Values for Example 4.11

Line | Reactance | Line | Reactance
---|---|---|---
1,2 | 0.01938 | 6,12 | 0.022
1,3 | 0.05403 | 6,13 | 0.0137
1,5 | 0.04699 | 7,8 | 0.03181
2,3 | 0.05811 | 7,9 | 0.12711
2,4 | 0.05695 | 8,10 | 0.08205
2,5 | 0.06701 | 9,10 | 0.22092
3,4 | 0.01335 | 9,14 | 0.17093
3,8 | 0.061 | 10,11 | 0.34
4,5 | 0.086 | 10,14 | 0.19
4,7 | 0.154 | 11,12 | 0.27
4,9 | 0.09498 | 11,14 | 0.085
5,6 | 0.12291 | 12,13 | 0.34
6,11 | 0.06615 | 13,14 | 0.345