The Price of Defense

Abstract

We consider a game on a graph $G=\langle V, E\rangle$ with two confronting classes of randomized players: $\nu$ attackers, who choose vertices and seek to minimize the probability of getting caught, and a single defender, who chooses edges and seeks to maximize the expected number of attackers it catches. In a Nash equilibrium, no player has an incentive to unilaterally deviate from her randomized strategy. The Price of Defense is the worst-case ratio, over all Nash equilibria, of $\nu$ over the expected utility of the defender at a Nash equilibrium.

We orchestrate a strong interplay of arguments from Game Theory and Graph Theory to obtain both general and specific results in the considered setting:

(1) Via a reduction to a Two-Players, Constant-Sum game, we observe that an arbitrary Nash equilibrium is computable in polynomial time. Further, we prove a general lower bound of $\frac{\textstyle |V|}{\textstyle 2}$ on the Price of Defense. We derive a characterization of graphs with a Nash equilibrium attaining this lower bound, which reveals a promising connection to Fractional Graph Theory; thereby, it implies an efficient recognition algorithm for such Defense-Optimal graphs.

(2) We study some specific classes of Nash equilibria, both for their computational complexity and for their incurred Price of Defense. The classes are defined by imposing structure on the players’ randomized strategies: either graph-theoretic structure on the supports, or symmetry and uniformity structure on the probabilities. We develop novel graph-theoretic techniques to derive trade-offs between computational complexity and the Price of Defense for these classes. Some of the techniques touch upon classical milestones of Graph Theory; for example, we derive the first game-theoretic characterization of König-Egerváry graphs as graphs admitting a Matching Nash equilibrium.

1 Introduction

1.1 Motivation and Framework

We revisit a network game with $\nu$ attackers and a single defender, introduced by Mavronicolas et al. [28] and further extended and studied in [12, 28, 29]; played on a graph $G = \langle V, E \rangle$, the game was conceived as a theoretical model of security attacks and defenses in emerging complex networks like the Internet. In this game, nodes are vulnerable to infection by attackers. Available to the network is a security software (for example, a firewall [5]), called the defender, which cleans some part of the network. So, attackers model threats, while the defender models a protection mechanism.

Network games addressing security attacks and defenses have been receiving a lot of interest and attention and have been studied from multiple points of view; see, e.g., [4, 6, 9, 13,14,15,16, 18, 23,24,25, 33, 34, 37, 38]. This network game is partially motivated by Network Edge Security [26], a firewall architecture where a firewall is implemented by a distributed algorithm, which protects the internetwork spanned by the nodes participating in the implementation. The simplest case where the internetwork is a single link offered the basis for the model proposed in [28]. Understanding the induced mathematical intricacies for this simplest case is a necessary prerequisite for making rigorous progress in the analysis of more involved topologies.

An attacker, called a vertex player, chooses a vertex of the graph via a probability distribution on a set of vertices, called the support; the defender, called the edge player, chooses an edge of the graph via a probability distribution on a set of edges, also called support. The vertex chosen by an attacker is destroyed unless it crosses the edge chosen by the defender, whence the attacker is caught. The expected utility of an attacker is the probability that it is not caught; the (expected) utility of the defender is the (expected) number of attackers caught.

For the network game we consider, we evaluate the impact of selfish behavior by introducing and studying the Defense-Ratio, defined as the ratio of $\nu$ over the defender’s expected utility; so, the Defense-Ratio accounts for the effectiveness of the security software against the attacks. We shall analyze the Defense-Ratio for Nash equilibria [31, 32], where no player has an incentive to deviate from her randomized strategy. The Price of Defense is the worst-case Defense-Ratio over all Nash equilibria. The Price of Defense is inspired by the celebrated Price of Anarchy [22], which has been used to evaluate the worst-case impact of selfish behavior in strategic games.

We are motivated to pose a genre of mathematical questions: How does the Defense-Ratio vary with Nash equilibria and network structure? Are there structured classes of tractable Nash equilibria achieving small Defense-Ratio? How are such effective Nash equilibria recognized for their small Defense-Ratio? How does the Price of Defense vary with network structure?

1.2 Contribution

We deliver a comprehensive collection of trade-offs between the Defense-Ratio (in particular, the Price of Defense) and the computational complexity of Nash equilibria. We consider specific classes of Nash equilibria defined by imposing structure on the players’ randomized strategies: either graph-theoretic structure on the supports, or symmetry and uniformity structure on the probabilities. We consider six such classes.

1.2.1 Arbitrary Nash Equilibria

It is natural to ask first whether an arbitrary Nash equilibrium for the network game can be computed in polynomial time. Towards this end, we observe a polynomial time reduction of the general case to the Two-Players, Constant-Sum case, where there are only two players, a single attacker and the defender, and the sum of their utilities is constant.¹ Since a Nash equilibrium for a Two-Players, Constant-Sum game can be computed in polynomial time via a reduction to Linear Programming [40], there follows a corresponding polynomial time algorithm to compute an arbitrary Nash equilibrium (Theorem 5.2).

Further, we analyze an arbitrary Nash equilibrium to prove that the Price of Defense is at least $\frac{\textstyle |V|}{\textstyle 2}$ (Theorem 5.4). The proof is from first principles. We provide a very simple example of a network game to show that the lower bound of $\frac{\textstyle |V|}{\textstyle 2}$ is tight (Proposition 5.5). This lower bound establishes that the Price of Defense must scale with network size.

1.2.2 Defense-Optimal Nash Equilibria

Naturally we are interested in Nash equilibria with Defense-Ratio attaining the tight lower bound of $\frac{\textstyle |V|}{\textstyle 2}$. We call such Nash equilibria Defense-Optimal. Say that a graph is Defense-Optimal if it admits a Defense-Optimal Nash equilibrium (Definition 5.2). We are interested in both characterizing and recognizing Defense-Optimal graphs and computing a Defense-Optimal Nash equilibrium for Defense-Optimal graphs.

We show that a graph is Defense-Optimal if and only if it has a Fractional Perfect Matching (Theorem 6.3); so, the characterization reveals an intriguing connection of the network game to Fractional Graph Theory [35]. Both directions of the characterization are shown using efficient constructions (Propositions 6.1 and 6.2). This already provides a polynomial time algorithm to decide the existence of and compute a Defense-Optimal Nash equilibrium, if there is one (Corollary 6.4). We proceed to consider Nash equilibria with a special structure.

1.2.3 Matching Nash Equilibria

Matching Nash equilibria were defined in [28] to account for the graph-theoretic structure of mixed Nash equilibria. Their definition builds on a Covering profile [28, Definition 4.1], where the support of the defender is an Edge Cover of the graph G and the union of the supports of the attackers is a Vertex Cover of the graph induced by the support of the defender. In turn, an Independent Covering profile [28, Definition 4.2] is a Covering profile in which all attackers use a common and uniform probability distribution over their common support, which is an Independent Set such that each vertex in the support of the attackers is incident to exactly one edge in the support of the defender. Moreover, in such a profile, the defender uses also a uniform probability distribution over its support. (See Fig. 1 for an illustration.) An Independent Covering profile is a Nash equilibrium [28, Proposition 4.6]. Furthermore, the support of the defender in an Independent Covering profile contains a Matching that matches each vertex outside the support of the attackers to some vertex in the support of the attackers [28, Proposition 4.7]. So, a Matching Nash equilibrium is defined as an Independent Covering profile. In the following, we use the two terms interchangeably.

Fig. 1

An illustration of an Independent Covering profile in an example graph G. The edges of the support of the defender are indicated with bold edges

A characterization of graphs admitting a Matching Nash equilibrium, called Matching graphs, has been presented in [28, Theorem 5.1] (restated here as Proposition 8.1): A graph is Matching if and only if it has an Expanding Independent Set: an Independent Set whose complementary vertex set is an Expander for the graph G.

Here we provide a new characterization of Matching graphs: A Matching graph G has its Independence Number $\alpha (G)$ equal to its Edge Covering Number $\beta ' (G)$ (Theorem 8.2). Quite interestingly, these are the graphs which were first introduced and studied back in 1931 by König [20] and independently by Egerváry [8]; they are well known as König-Egerváry graphs (cf. [7, 36]). So the admittance of a Matching Nash equilibrium is the first game-theoretic characterization of König-Egerváry graphs.

We extend the characterization of Matching graphs into a polynomial time algorithm to decide the existence of and compute a Matching Nash equilibrium, if there is one (Theorem 8.4). This follows from a new polynomial time algorithm we develop to recognize a König-Egerváry graph, and compute a Maximum Independent Set of size $\alpha (G) = \beta ^{\prime }(G)$ in case it is (Proposition 4.12); to the best of our knowledge, this is a new problem. The new algorithm amounts to the computation of a Minimum Edge Cover, followed by a reduction of the computation of a Maximum Independent Set to 2SAT [30, Theorem 4.1].

We show that the Defense-Ratio for a Matching Nash equilibrium is $\alpha (G)$ (Proposition 8.5). The proof exploits the property that the union of the attackers’ supports is a Maximum Independent Set, that the support of the defender is a Minimum Edge Cover and that these two sets are of equal size (Proposition 7.9). These are properties of Generalized Independent Covering profiles we introduce, which are a broader class than the class of Independent Covering profiles (Definition 7.4).

1.2.4 Perfect-Matching Nash Equilibria

A Perfect-Matching Nash equilibrium is the special case of a Matching Nash equilibrium where the support of the defender, which is an Edge Cover, is a Perfect Matching of G. Say that a graph is Perfect-Matching if it admits a Perfect-Matching Nash equilibrium. Recall that a graph is Defense-Optimal if and only if it has a Fractional Perfect Matching (Theorem 6.3). Since a Perfect-Matching graph contains a Perfect Matching and a Perfect Matching is also a Fractional Perfect Matching (with integer weights), it follows that a Perfect-Matching graph is Defense-Optimal. Thus, Perfect-Matching graphs lie at the intersection of the sets of Matching graphs and Defense-Optimal graphs, respectively. Interestingly, we show that the intersection is exactly equal to the class of Perfect-Matching graphs (Proposition 9.4).

We provide a characterization of Perfect-Matching graphs: A Perfect-Matching graph G has a Perfect Matching and its Independence Number $\alpha (G)$ equals $\frac{\textstyle |V|}{\textstyle 2}$ (Theorem 9.2). So, Perfect-Matching graphs make a strict subclass of graphs with a Perfect Matching. The characterization benefits from a basic structural property of Perfect-Matching Nash equilibria we prove, namely that the union of the supports of the attackers has size $\frac{\textstyle |V|}{\textstyle 2}$ (Proposition 9.1).

We observe that the class of Perfect-Matching graphs is strictly contained into the class of Defense-Optimal graphs. Towards this end, we identify the simplest Defense-Optimal graph that is not a Perfect-Matching graph (Proposition 9.3); this is the clique of size 3.

We extend the characterization of Perfect-Matching graphs into a polynomial time algorithm to decide the existence of and compute a Perfect-Matching Nash equilibrium, if there is one (Theorem 9.7). Towards this end, we design a polynomial-time algorithm for the graph-theoretic problem of deciding, given a graph G with a Perfect Matching, whether its Independence Number $\alpha (G)$ equals $\frac{\textstyle |V|}{\textstyle 2}$, and yielding, if so, a Maximum Independent Set for G (Proposition 4.14); to the best of our knowledge, this is a new problem. The algorithm amounts to the computation of a Perfect Matching and a subsequent reduction to 2SAT; a Maximum Independent Set is computed from a satisfying assignment (if any) for the 2SAT instance.

We show that the Defense-Ratio for a Perfect-Matching Nash equilibrium is $\frac{\textstyle |V| }{\textstyle 2}$ (Theorem 9.8). The proof exploits (i) the requirement that attackers are symmetric and uniform in a Perfect-Matching Nash equilibrium, and (ii) the established property that the union of the supports of the attackers has size $\frac{\textstyle |V| }{\textstyle 2}$ (Proposition 9.1). Compared to the lower bound of $\frac{\textstyle |V| }{\textstyle 2}$ on the Defense-Ratio (Theorem 5.4), this sets that the lower bound is tight for the large class of Perfect-Matching graphs, which witnesses the suitability of the definition of Defense-Ratio.

We observe that the relation between the Prices of Defense for Matching and Perfect-Matching Nash equilibria goes by the relation between $\frac{\textstyle |V|}{\textstyle 2}$ and $\alpha (G)$, respectively: For a graph G with a Perfect-Matching Nash equilibrium, Theorem 9.2 implies that $\alpha (G) =\frac{\textstyle |V|}{\textstyle 2}$; hence, the two Prices of Defense coincide, as also do the two classes of Nash equilibria. Interestingly, we show that if a graph has both a Matching and a Perfect-Matching Nash equilibrium, then each Matching Nash equilibrium is a Perfect-Matching Nash equilibrium (Proposition 9.5). On the other hand, a graph G with a Matching Nash equilibrium but without a Perfect-Matching Nash equilibrium has $\alpha (G) > \frac{\textstyle |V|}{\textstyle 2}$ (Proposition 9.6).

The last two classes of Nash equilibria we study assume uniformity on the attackers and the defenders, respectively.

1.2.5 Attacker-Symmetric and Uniform Nash Equilibria

In an Attacker-Symmetric&Uniform Nash equilibrium, all attackers share a common support on which each attacker uses a uniform probability distribution. So, attackers are symmetric and uniform. Note that a Matching Nash equilibrium is a special case of an Attacker-Symmetric&Uniform Nash equilibrium.

We provide a characterization of graphs admitting an Attacker-Symmetric&Uniform Nash equilibrium (Theorem 10.3); call them Attacker-Symmetric&Uniform graphs: An Attacker-Symmetric&Uniform graph G either (1) has a Fractional Perfect Matching, or (2) is König-Egerváry (with $\alpha (G) = \beta ^{\prime }(G)$) (Conditions (1) and (2), respectively, in Theorem 10.3). By Theorems 6.3 and  8.2, the characterization implies that an Attacker-Symmetric&Uniform graph is either Defense-Optimal or Matching, and no other case is possible.

We extend the characterization into a polynomial time algorithm to decide the existence of and compute an Attacker-Symmetric&Uniform Nash equilibrium, if there is one (Theorem 10.4). The polynomial time algorithm combines together the polynomial time algorithm to decide the existence of and compute a Fractional Perfect Matching (if there is one), and the polynomial time algorithm to check the condition $\alpha (G) = \beta ^{\prime }(G)$.

We finally show that the Price of Defense for Attacker-Symmetric&Uniform Nash equilibria is either $\frac{\textstyle |V| }{\textstyle 2}$ or bounded by $\alpha (G)$ (Theorem 10.5). These two values correspond to Conditions (1) and (2), respectively, in the characterization of Attacker-Symmetric&Uniform graphs (Theorem 10.3).

1.2.6 Defender-Uniform Nash Equilibria

In a Defender-Uniform Nash equilibrium, the defender chooses each edge in her support with uniform probability. We provide a characterization of graphs admitting a Defender-Uniform Nash equilibrium (Theorem 11.1); call them Defender-Uniform graphs. The characterization involves Regular Subgraphs, Independent Sets and Expanders. Not surprisingly, Regular Subgraphs were also encountered in the work of Bonifaci et al. [2] on Uniform Nash equilibria.

We next use the characterization to show that recognizing a Defender-Uniform graph is $\mathcal{NP}$-complete (Theorem 11.4). The proof employs a reduction from the DIRECTED PARTITION INTO HAMILTONIAN SUBGRAPHS problem [11, Problem GT13], originally shown $\mathcal{NP}$-complete by Valiant [39]. A significant milestone of the reduction is an intermediate reduction to a certain undirected version of the problem. This version has been claimed as $\mathcal{NP}$-complete in the discussion following [11, Problem GT13], with attribution to (personal communication with) Papadimitriou. This work provides the first published proof of this result. This intractability result stands in contrast to the polynomial time solvability of Attacker-Symmetric&Uniform Nash equilibria (Theorem 10.4).

We proceed to show that the Defense-Ratio of a Defender-Uniform Nash equilibrium is $\frac{\textstyle 1 }{\textstyle 2} \cdot (1+\lambda )\cdot |V|$, where $0\le \lambda \le 1$ (Theorem 11.13). Thus, compared to Perfect-Matching Nash equilibria, Defender-Uniform Nash equilibria are both suboptimal with respect to Price of Defense and hard to compute (unless $\mathcal{P}=\mathcal{NP}$).

Table 1 Summary of results in this work

1.3 Discussion and Related Work

The results in this work are summarized in Table 1. These results reveal a case of strong interplay between Game Theory and Graph Theory. In particular, the structure of the underlying graph is discovered to influence quantitative performance measures of Nash equilibria, such as the Defense-Ratio and the Price of Defense. This influence suggests certain ways of network design; for example, the provision of graphs with Fractional Perfect Matchings will induce Nash equilibria with optimal Defense-Ratio (Theorem 6.3).

The first polynomial time algorithm for recognizing a König-Egerváry graph and computing a Maximum Independent Set for such a graph was explicitly given by Deming [7]. Deming’s algorithm proceeds by computing a Maximum Matching; our presented algorithm MISEqualMEC (Proposition 4.12) starts with computing a Minimum Edge Cover. While the MISEqualMEC algorithm continues via a simple reduction to 2SAT, Deming’s algorithm continues with a direct procedure for coloring vertices and either obtaining a Maximum Independent Set, or concluding, through a consideration of colored vertices, that the graph is not König-Egerváry. We view our algorithm as a much simpler alternative to Deming’s algorithm [7].

An alternative characterization of Matching graphs, and a corresponding non-deterministic polynomial time algorithm to recognize them, was derived in [28], yielding a deterministic polynomial time algorithm for bipartite graphs. The current deterministic, polynomial time algorithm, used for the König-Egerváry characterization, is applicable to all graphs.

Both Matching and Perfect-Matching Nash equilibria are Defender-Uniform. Such equilibria are inspired by the Uniform Nash equilibria studied recently by Bonifaci et al. [2] for bimatrix games. Bonifaci et al. [2] reveal the equivalence between the existence of a Uniform Nash equilibrium and the existence of certain graph-theoretic structures, such as Regular Subgraphs of large size or regularity; hence, deciding the existence of a Uniform Nash equilibrium for a certain restricted class of win-lose bimatrix games is $\mathcal{NP}$-complete [2, Theorem 1].

Ghani and Tanaka [13] extended the network game considered in this paper by interchanging the roles of vertex and edge players so that attacks and defenses are represented by edge and vertex players, respectively; for their variant of the network game, they considered both pure and mixed Nash equilibria with multiple attackers and defenders in both the standard strategic game and a repeated (asynchronous) game where two players repeatedly execute simultaneous choices. Ghani and Tanaka [13] presented existence, characterization and algorithmic results for the Nash equilibria in the resulting network game.

1.4 Road Map

Some background from Graph Theory is articulated in Sect. 2. The game on graphs is revisited in Sect. 3. Section 4 treats the graph-theoretic problems we shall encounter. Arbitrary and Defense-Optimal Nash equilibria are considered in Sects. 5 and 6, respectively. Section 7 introduces Covering profiles and their properties, which are used in the development of Matching and Perfect-Matching Nash equilibria in Sects. 8 and 9, respectively. Attacker-Symmetric&Uniform and Defender-Uniform Nash equilibria are treated in Sects. 10 and 11, respectively. We conclude, in Sect. 12, with a summary and some open problems.

2 Background from Graph Theory

We assume some basic familiarity of the reader with the elementary concepts of Graph Theory, as articulated, for example, in [41].

2.1 Notation

Throughout, we consider an undirected graph $G=\langle V, E\rangle$ with no isolated vertices; so $|V|\ge 2$. For a vertex $v\in V$, denote as $d_G(v)$ the degree of vertex v. For a vertex set $U\subseteq V$, denote as G(U) the subgraph of G induced by U. For an edge set $F\subseteq E$, denote as G(F) the subgraph of G induced by F. Denote as $\mathsf{Edges}_{G}(U)=\{(u,v) \in E\mid \; u \in U \text { and } v \not \in U \}$; in particular, for a vertex $u\in V$, $\mathsf{Edges}_{G}(u)=\{(u,v) \in E \mid \; v \in V \}$. For a vertex set $U\subseteq V$, denote as $\mathsf{Neigh}_{G}(U)=\{ v \notin U \mid (u,v)\in E \text { for some vertex } u\in U\}$.

The graph G is bipartite if $V=V_1\cup V_2$ for some disjoint (non-empty) vertex sets $V_1,V_2\subset V$ such that for each edge $(u,v)\in E$, $u \in V_1$ and $v \in V_2$. Call G a $(V_1,V_2)$-bipartite graph. For each integer $n\ge 2$, denote as $K_n$ the clique on n vertices.

In some part of this work, we shall consider directed graphs. An edge $(u,v)\in E^d$ in a directed graph $G^d=\langle V^d,E^d \rangle$ is single (resp., double) if $(v,u)\not \in E^d$ (resp., $(v,u)\in E^d$).

2.2 Independent Set

A vertex set $IS\subseteq V$ is an Independent Set if for all pairs of vertices $u, v \in IS$, $(u,v)\notin E$. A Maximum Independent Set is an Independent Set with maximum size; denote as $\alpha (G)$ the size of a Maximum Independent Set, called the Independence Number. Deciding, given a graph, the existence of an Independent Set with a given size is one of the original $\mathcal{NP}$-complete problems [11, Problem GT20]; so, determining the Independence Number of a given graph is $\mathcal{NP}$-hard.

Fix now a vertex set $U \subseteq V$. The graph G is a U-Expander graph, and the set U is an Expander of G, if the size of each subset $U'\subseteq U$ is at most the size of its open neighborhood $\mathsf{Neigh}_{G} (U') \cap (V \backslash U)$, where vertices in U are excluded. An Expanding Independent Set [28, Section 2.2] is an Independent Set IS such that the vertex set $V\backslash IS$ is an Expander.

2.3 Covers

A Vertex Cover is a vertex set $VC\subseteq V$ such that for each edge $(u,v) \in E$ either $u\in VC$ or $v \in VC$. Clearly, VC is a Vertex Cover if and only if $V\backslash VC$ is an Independent set. A Minimum Vertex Cover is one with minimum size; denote as $\beta (G)$ the size of a Minimum Vertex Cover, called the Vertex Cover Number or Traversal Number [36]. Computing the Vertex Cover Number, given a graph, is also one of the original $\mathcal{NP}$-complete problems [11, problem SP5].

An Edge Cover is an edge set $EC\subseteq E$ such that for every vertex $v\in V$, there is an edge $(v,u) \in EC$. A Minimum Edge Cover is one with minimum size; denote as $\beta ^{\prime }(G)$ the size of a Minimum Edge Cover, called the Edge Covering Number. Since an Edge Cover may not cover more than two vertices per edge, it follows that $\beta ^{\prime }(G)\ge \frac{\textstyle |V| }{\textstyle 2}$. It is known that a Minimum Edge Cover consists of vertex-disjoint star graphs² [41, Theorem 3.1.22].

A Domination Set is a vertex set $DS\subseteq V$ such that for any vertex $v\in V$ either $v\in DS$ or there is a vertex $u \in DS$ such that $(u,v) \in E$. A vertex set DS is an Independent Domination Set if it is both a Domination Set and an Independent Set of G.

2.4 Matchings and Fractional Matchings

A Matching is a set $M\subseteq E$ of non-incident edges. A Maximum Matching is one with maximum size; denote as $\alpha ^{\prime }(G)$ the size of a Maximum Matching, called the Matching Number. It is known that a Minimum Edge Cover can be computed in polynomial time via computing a Maximum Matching. (See, e.g., [41, Section 3.1].) A Perfect Matching is a Matching that is also an Edge Cover; so, a Perfect Matching has size $\frac{\textstyle |V| }{\textstyle 2}$. It follows that $\alpha ^{\prime }(G) \le \frac{\textstyle |V| }{\textstyle 2}$.

A Fractional Matching is a function $f:E\rightarrow [0,1]$ such that for each vertex $v\in V$, $\sum _{e\in \mathsf{Edges}_{G}(v) } f(e) \le 1$. When $f(e) \in \{0,1\}$ for every edge $e\in E$, f represents a Matching. The Fractional Matching Number denoted as $\alpha ^{\prime }_F(G)$ is the supremum of $\sum _{e\in E} f(e)$ over all Fractional Matchings f of a graph G. It is a basic fact in Fractional Graph Theory [35] that $\alpha ^{\prime }_F(G)\le \frac{\textstyle |V|}{\textstyle 2}$; see, for example, [35, Lemma 2.1.2]. A Fractional Maximum Matching is one that achieves the Fractional Matching Number. A Fractional Perfect Matching is a Fractional Matching f such that for each vertex $v\in V$, $\sum _{e\in \mathsf{Edges}_G(v) } f(e)=1$. Hence, for a Fractional Perfect Matching f, $\sum _{e\in E} f(e)=\frac{\textstyle |V|}{\textstyle 2}$, achieving the upper bound of $\alpha ^{\prime }_F(G)$.

The Fractional Matching Number of a graph is polynomial time computable through formulating the corresponding algorithmic problem as a Linear Program of polynomial size (precisely, of size $|V|\cdot |E|$). (See, also, [3] for an efficient combinatorial algorithm.) Since a graph G has a Fractional Perfect Matching if and only if its Fractional Matching Number is equal to $\frac{\textstyle |V|}{\textstyle 2}$, it follows that a graph with a Fractional Perfect Matching is polynomial time recognizable.

2.5 König-Egerváry Graphs

For a graph G, it holds trivially that $\alpha (G)+\beta (G) = |V|$; it also holds that $\alpha ^{\prime }(G) + \beta ^{\prime }(G) = |V|$ (Gallai’s Theorem [10]). Since a Vertex Cover must include at least one vertex incident to each edge in a Matching, it follows that $\alpha ^{\prime }(G)\le \beta (G)$. Since $\alpha (G)+\beta (G)= \alpha ^{\prime }(G)+\beta ^{\prime }(G)$, this implies that $\alpha (G) \le \beta ^{\prime }(G)$. A graph G with $\alpha ^{\prime }(G) = \beta (G)$ is called König-Egerváry [8, 21]; hence, in a König-Egerváry graph, it also holds that $\alpha (G) = \beta ^{\prime }(G)$. König-Egerváry graphs are recognizable in polynomial time [7, 36].

2.6 Paths and Circuits

A (simple) path is a sequence $v_1,v_2,\ldots , v_k$ of distinct vertices from V such that $(v_{i}, v_{i+1})\in E$ for $1\le i < k$; the path has size k. A Hamiltonian path is a path including all vertices from V. A circuit is a path $v_1,v_2,\ldots , v_k$ with $(v_k, v_1)\in E$. A Hamiltonian circuit is a circuit including all vertices from V. Say that the collection of sets $V_1, V_2, \ldots , V_k$, for some k with $V_i\subseteq V$ for each $i\in [k]$, is a collection of Hamiltonian circuits covering the graph G if (i) the sets are mutually disjoint and their union is V, and (ii) each set $V_i$ contains at least three vertices and induces a subgraph of G with a Hamiltonian circuit. Denote as $\mathcal{C}_n$ the cycle on n vertices.

3 A Game on Graphs

Associated with a graph G is a game $\mathsf{AD}( G)= \langle {{\mathcal {N}}},\{ S_i\}_{i \in {{\mathcal {N}}}},$ $\{ \mathsf{U}_i \}_{i \in {{\mathcal {N}}}} \rangle$ on G [28]:

• The set of players is ${{\mathcal {N}}}= \mathcal{A} \cup \mathcal{D }$, where $\mathcal{A}$ has $\nu$ players $\mathsf{a}_i$, called attackers, $1 \le i \le \nu$, and $\mathcal{D}$ has a single player $\mathsf{d}$, called defender.

• The strategy set $S_i$ of each attacker $\mathsf{a}_i$ is V; the strategy set $S_{\mathsf{d}}$ of the defender $\mathsf{d}$ is E. So, the strategy set ${{\mathcal {S}}}$ of the game is ${{\mathcal {S}}}= \left( \times _{{\mathsf{a}_{i} \; \in \; \mathcal{A}}} S_i \right) \times S_{\mathsf{d}} = V^{\nu } \times E$.

• Fix a profile ${\mathbf {s}} = \langle s_1, \dots , s_{\nu }, s_{\mathsf{d}} \rangle \in {{\mathcal {S}}}$.

  • The Utility of attacker $\mathsf{a}_i$ is the function ${\mathsf {U}}_{i}: {{\mathcal {S}}}\rightarrow \{0,1\}$ with ${\mathsf {U}}_{i}({\mathbf {s}} ) = \left\{ \begin{array}{ll} 0, &{} s_i \in s_{\mathsf{d}} \\ 1, &{} s_i \not \in s_{\mathsf{d}} \end{array} \right.$; so, the Utility of $\mathsf{a}_i$ is 1 if she is not caught by the defender $\mathsf{d}$, and 0 otherwise.

  • The Utility of the defender $\mathsf{d}$ is the function ${\mathsf {U}}_\mathsf{d}: {{\mathcal {S}}}\rightarrow {\mathbb {N}}$ such that ${\mathsf {U}}_\mathsf{d} ({\mathbf {s}}) =|\{ i: s_i \in s_{\mathsf{d}} \}|$; so, the Utility of $\mathsf{d}$ is the number of attackers it catches on her chosen edge.

3.1 Strategies and Mixed Profiles

A mixed strategy for player $i \in {{\mathcal {N}}}$ is a probability distribution $\varvec{\sigma }$ over $S_i$; thus, a mixed strategy for an attacker (resp., the defender) is a probability distribution $\sigma _i$ on vertices (resp., edges); $\sigma _i(v)$ is the probability that attacker $\mathsf{a}_i$ chooses vertex v and $\sigma _{\mathsf{d}}(e)$ is the probability that the defender $\mathsf{d}$ chooses edge e. A mixed profile $\varvec{\sigma }=\langle \sigma _1, \dots , \sigma _{\nu }, \sigma _{\mathsf{d}} \rangle$ is a collection of mixed strategies, one per player. For a mixed profile $\varvec{\sigma }$, $(\varvec{\sigma }_{ - i}, \sigma '_{i} )$ denotes the mixed profile resulting from $\varvec{\sigma }$ by replacing $\sigma _i$ by $\sigma '_{i}$.

The support of player $i\in {{\mathcal {N}}}$ in the mixed profile $\varvec{\sigma }$, denoted as $\mathsf{Supp}_{\varvec{\sigma }}(i)$, is the set of strategies in her strategy set to which $\sigma _i$ assigns a strictly positive probability. Set $\mathsf{Supp}_{\varvec{\sigma }}(\mathcal{A}) : = \bigcup _{i \in \mathcal{A}} \mathsf{Supp}_{\varvec{\sigma }}(i)$ and $\mathsf{Edges}_{\varvec{\sigma }} (v) :=\left\{ (u,v)\in E \mid \; (u,v) \in \mathsf{Supp}_{\varvec{\sigma }}(\mathsf{d}) \right\}$. So, $\mathsf{Edges}_{\varvec{\sigma }}(v)$ contains all edges incident to v that are included in the support of the defender. For a vertex set $U\subseteq V$, set $\mathsf{Edges_{\varvec{\sigma }}}(U)=\{ e=(u,v)\in \mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d})\mid u\in U\}$. So, $\mathsf{Edges_{\varvec{\sigma }}}(U)$ contains all edges incident to a vertex in U that are included in the support of the defender. In a similar way, $\mathsf{Vertices_{\varvec{\sigma }}}(e)$ is defined as $\mathsf{Vertices_{\varvec{\sigma }}}(e) = \{ v, u \in \mathsf{Supp_{\varvec{\sigma }}}(\mathsf{{{\mathcal {A}}}}) \mid (v,u) \in \mathsf{Supp}_{\varvec{\sigma }}(\mathsf{d}) \}$, where $e \in E$.

A mixed profile $\varvec{\sigma }$ is Uniform if each player uses a uniform probability distribution on her support. Then, for each attacker $\mathsf{a}_i\in {{\mathcal {A}}}$ and for each vertex $v\in \mathsf{Supp}_{\varvec{\sigma }}(i)$, $\sigma _i(v) =\frac{\textstyle 1 }{\textstyle |\mathsf{Supp}_{\varvec{\sigma }}(i)|}$; for the defender $\mathsf{d}$, for each edge $e \in \mathsf{Supp}_{\varvec{\sigma }}(\mathsf{d})$, $\sigma _{\mathsf{d}}(e)= \frac{\textstyle 1 }{\textstyle |\mathsf{Supp}_{\varvec{\sigma }}(\mathsf{d})|}$.

A mixed profile $\varvec{\sigma }$ is Attacker-Symmetric if for each vertex $v\in V$, for each pair of attackers $\mathsf{a}_i$, $\mathsf{a}_k \in {{\mathcal {A}}}$, $\sigma _{i}(v)=\sigma _{k}(v)$; so, $\mathsf{Supp}_{\varvec{\sigma }}(i) = \mathsf{Supp}_{\varvec{\sigma }}(k)$. An Attacker-Symmetric&Uniform mixed profile is an Attacker-Symmetric and Uniform mixed profile. A mixed profile is Defender-Uniform if the defender uses a uniform probability distribution on her support. A mixed profile is Attacker-FullyMixed (resp., Defender-FullyMixed) if $\mathsf{Supp_{\varvec{\sigma }}}(i)=V$ for each attacker $\mathsf{a}_i\in {{\mathcal {A}}}$ (resp., $\mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d})=E).$

For a vertex $v\in V$, ${\mathbb {P}}_{\varvec{\sigma }}(\mathsf{Hit}(v) )$, called the Hitting Probability for v, denotes the probability that the defender $\mathsf{d}$ chooses an edge incident to v. So,

$$\begin{aligned} {\mathbb {P}}_{\varvec{\sigma }}(\mathsf{Hit}(v))& = \sum _{e\in \mathsf{Edges}_{\varvec{\sigma }}(v)} \sigma _{\mathsf{d}}(e). \end{aligned}$$

For a vertex $v\in V$, $\mathsf{A}_{\varvec{\sigma }}(v)$ denotes the expected number of attackers choosing vertex v; $\varvec{\sigma }$; so,

$$\begin{aligned} \mathsf{A}_{\varvec{\sigma }}(v)& = \sum _{\mathsf{a}_i \in {{\mathcal {A}}}} \sigma _i(v). \end{aligned}$$

So, for an Attacker-Symmetric&Uniform mixed profile $\varvec{\sigma }$, for each vertex $v\in \mathsf{Supp_{\varvec{\sigma }}}(\mathcal{A})$,

$$\begin{aligned} \mathsf{A_{\varvec{\sigma }}}(v)& = \frac{\textstyle \nu }{\textstyle |\mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})|} . \end{aligned}$$

For each edge $e=(u,v) \in E$, $\mathsf{A}_{\varvec{\sigma }}(e)$ is the expected number of attackers choosing either the vertex u or the vertex v; so, $\mathsf{A}_{\varvec{\sigma }}(e) = \mathsf{A}_{\varvec{\sigma }}(u) + \mathsf{A}_{\varvec{\sigma }}(v)$. Here is a preliminary observation:

Lemma 3.1

For a mixed profile $\varvec{\sigma }$, $\sum _{v\in V}{{\mathbb {P}}}_{\varvec{\sigma }}(\mathsf{Hit}(v))=2$.

Proof

Clearly,

$$\begin{aligned} \sum _{v\in V}{{\mathbb {P}}}_{\varvec{\sigma }}(\mathsf{Hit}(v)) &= \sum _{v\in V} \sum _{e\in \mathsf{Edges_{\varvec{\sigma }}}(v)} \sigma _{\mathsf{d}} (e)\nonumber \\&= \sum _{e\in E} \sum _{v\in \mathsf{Vertices_{\varvec{\sigma }}}(e) } \sigma _{\mathsf{d}}(e)\nonumber \\&= 2 \sum _{e\in E} \sigma _{\mathsf{d}} (e)\nonumber \\&= 2, \end{aligned}$$

as needed. $\square$

A mixed profile $\varvec{\sigma }$ induces random variables for the utilities of players. Clearly, the Conditional Expected Utility of attacker $\mathsf{a}_{i} \in {{\mathcal {A}}}$ when she chooses vertex v is

$$\begin{aligned} {\mathsf {U}}_{i} (v, \varvec{\sigma }_{-i} )& = 1 - \sum _{e \in \mathsf{Edges}_{\varvec{\sigma }}(v)} \sigma _{\mathsf{d}}(e) \ \ = \ \ 1 - {\mathbb {P}}_{\varvec{\sigma }} (\mathsf{Hit}(v )) ; \end{aligned}$$

the Conditional Expected Utility of the defender $\mathsf{d}$ when she chooses edge $e=(u,v)$ is

$$\begin{aligned} {\mathsf {U}}_{\mathsf{d}} (e, \varvec{\sigma }_{-\mathsf{d }} )& = \sum _{\mathsf{a}_{i} \in {{\mathcal {A}}}} \left( \sigma _i(u) +\sigma _i(v) \right) \ \ = \ \ \mathsf{A_{\varvec{\sigma }}}(e). \end{aligned}$$

Thus, the mixed profile $\varvec{\sigma }$ induces an Expected Utility ${\mathsf {U}}_{i}(\varvec{\sigma })$ for each player $i \in {{\mathcal {N}}}$, which is the expectation according to $\varvec{\sigma }$ of the Utility of player i. It follows that for an attacker $\mathsf{a}_i \in {{\mathcal {A}}}$,

$$\begin{aligned} {\mathsf {U}}_{i}(\varvec{\sigma })& = \sum _{v\in V} \sigma _i(v) \cdot \left( 1-\sum _{e \in \mathsf{Edges}_{\varvec{\sigma }}(v)} \sigma _{\mathsf{d}}(e) \right) ; \end{aligned}$$

for the defender $\mathsf{d}$,

$$\begin{aligned} {\mathsf {U}}_{\mathsf{d}}(\varvec{\sigma })& = \sum _{e=(u,v) \in E } \sigma _{\mathsf{d}}(e) \cdot \left( \sum _{\mathsf{a}_i \in {{\mathcal {A}}}} \left( \sigma _i(u) +\sigma _i(v) \right) \right) . \end{aligned}$$

3.2 Nash Equilibria

The mixed profile $\varvec{\sigma }$ is a Nash equilibrium [31, 32] if for each player $i\in {{\mathcal {N}}}$, for each mixed strategy $\tau _i$ of player ${\mathsf {U}}_{i}(\varvec{\sigma }) \ge {\mathsf {U}}_{i}(\varvec{\sigma }_{-i},\tau _i)$. By Nash’s result [31, 32], there is at least one Nash equilibrium. Clearly, in a Nash equilibrium, for each attacker $\mathsf{a}_i \in {{\mathcal {A}}}$, for any vertex $v\in \mathsf{Supp}_{\varvec{\sigma }}(\mathsf{a}_i )$,

$$\begin{aligned} {\mathsf {U}}_{i}(\varvec{\sigma })& = {\mathsf {U}}_{i}(v, \varvec{\sigma }_{-i}) \ \ = \ \ 1 -\sum _{e\in \mathsf{Edges}_{\varvec{\sigma }}(v)} \sigma _{\mathsf{d}}(e) ; \end{aligned}$$

for the defender $\mathsf{d}$, for any edge $e= (u,v) \in \mathsf{Supp_{\varvec{\sigma }}}_{}(\mathsf{d})$,

$$\begin{aligned} {\mathsf {U}}_{\mathsf{d}}({\varvec{\sigma }})& = {\mathsf {U}}_{\mathsf{d}}(e, \varvec{\sigma }_{-\mathsf{d}} )\ \ = \ \ \sum _{\mathsf{a}_i \in {{\mathcal {A}}}} \left( \sigma _{i}(u)+\sigma _{i}(v)\right) . \end{aligned}$$

We recall a characterization of Nash equilibrium for the game $\mathsf{AD}( G)$ from [29, Theorem 3.1]:

Proposition 3.2

([28], Theorem 3.1) A mixed profile $\varvec{\sigma }$ is a Nash equilibrium if and only if:

(C.1):

For each vertex $v\in \mathsf{Supp}_{\varvec{\sigma }}({{\mathcal {A}}})$, ${\mathbb {P}}_{\varvec{\sigma }}(\mathsf{Hit}(v)) = \min _{v^{\prime }\in V} {\mathbb {P}}_{\varvec{\sigma }} (\mathsf{Hit}(v^{\prime }))$.

(C.2):

For each edge $e \in \mathsf{Supp}_{\varvec{\sigma }}(\mathsf{d})$, $\mathsf{A}_{\varvec{\sigma }}(e) = \max _{e^{\prime }\in E} \mathsf{A}_{\varvec{\sigma }}(e^{\prime })$ .

By Proposition 3.2, a Nash equilibrium is polynomial time verifiable. We now observe a preliminary property of Nash equilibria.

Proposition 3.3

Consider a Nash equilibrium $\varvec{\sigma }$. Then,

$$\begin{aligned} \min _{v^{\prime }\in V} {{\mathbb {P}}}_{\varvec{\sigma }}(\mathsf{Hit}(v^{\prime }))\le & {} \frac{\textstyle 2}{\textstyle |V|} . \end{aligned}$$

Proof

Clearly,

$$\begin{aligned} \sum _{v\in V}{{\mathbb {P}}}_{\varvec{\sigma }}(\mathsf{Hit}(v)) & \ge \sum _{v \in V} \min _{v^{\prime }\in V} {{\mathbb {P}}}_{\varvec{\sigma }}(\mathsf{Hit}(v^{\prime })) \\ &= |V| \cdot \min _{v^{\prime }\in V} {{\mathbb {P}}}_{\varvec{\sigma }}(\mathsf{Hit}(v^{\prime })). \end{aligned}$$

By Lemma 3.1, the claim follows. $\square$

3.3 Algorithmic Problems for Nash Equilibria

We shall study particular instances of algorithmic problems of deciding the existence of and computing a Nash equilibrium for the considered network game, which belongs to a certain class. Thus, each such algorithmic problem is parameterized by a class $\mathcal{C}$ of Nash equilibria:

$\exists$ ${{\mathcal {C}}}$ NE

Instance: A graph $G = \left\langle V, E\right\rangle$.

Question: Does $\mathsf{AD}( G)$ admit a Nash equilibrium in the class ${{\mathcal {C}}}$?

There follows a search version of $\exists$ ${{\mathcal {C}}}$ NE:

F ${{\mathcal {C}}}$ NE

Instance: A graph $G = \langle V, E\rangle$.

Output: A Nash equilibrium for $\mathsf{AD}(G)$ in the class $\mathcal{C}$, or No if such does not exist.

The class ${\mathcal {C}}$ may be any of ARBITRARY, DEFENSE-OPTIMAL, MATCHING, PERFECT-MATCHING, ATTACKER-SYMMETRIC&UNIFORM and DEFENDER-UNIFORM, denoting the classes of Arbitrary, Defense-Optimal, Matching, Perfect-Matching, Attacker-Symmetric&Uniform and Defender-Uniform Nash equilibria, respectively. We note that for each such class ${\mathcal {C}}$, membership of a mixed profile in ${\mathcal {C}}$ can be verified in polynomial time; hence, by Proposition 3.2, this implies that $\exists$ ${{\mathcal {C}}}$ NE $\in \mathcal{NP}$ and F ${\mathcal {C}}$ NE $\in \mathsf{F}\; \mathcal { NP}$.

3.4 The Price of Defense

For a Nash equilibrium $\varvec{\sigma }$, the ratio $\frac{\textstyle \nu }{\textstyle {\mathsf {U}}_ \mathsf{d}(\varvec{\sigma })}$ is called the Defense Ratio of $\varvec{\sigma }$ and denoted as $\mathsf{DR}_{\varvec{\sigma }}$. The Price of Defense is the worst-case value, over all Nash equilibria $\varvec{\sigma }$ for G, of the Defense Ratio $\mathsf{DR}_{\varvec{\sigma }}$; it is denoted as $\mathsf{PoD}_G$. (By worst-case, we mean maximum.)

4 Four Graph-Theoretic Problems

Sections 4.1 and 4.2 treat two $\mathcal{NP}$-complete problems and two problems in $\mathcal{P}$, respectively, from Graph Theory, stated here in the style of Garey and Johnson [11]; i. and q. stand for Input and Question, respectively.

4.1 The Two $\mathcal{NP}$-Complete Problems

For our negative results, we shall use reductions from two $\mathcal{NP}$-complete graph-theoretic problems about covering a graph with Hamiltonian circuits:

DIRECTED PARTITION INTO HAMILTONIAN SUBGRAPHS

i.: A directed graph $G^d= \langle V^d,E^d \rangle$.

q.: Is there a collection of Hamiltonian circuits covering the graph $G^d$?

DIRECTED PARTITION INTO HAMILTONIAN SUBGRAPHS was proved $\mathcal{NP}$-complete in [39, Theorem 1]; see [11, GT13]. Here is an undirected version of DIRECTED PARTITION INTO HAMILTONIAN SUBGRAPHS, which applies to graphs where every cycle has size at least 4.

UNDIRECTED PARTITION INTO HAMILTONIAN SUBGRAPHS OF SIZE AT LEAST 6

i.: An undirected graph $G= \langle V,E \rangle$ such that every cycle in G has size at least 4.

q.: Is there a collection of Hamiltonian circuits of size at least 6 covering the graph G?

Clearly, UNDIRECTED PARTITION INTO HAMILTONIAN SUBGRAPHS OF SIZE AT LEAST 6 $\in \mathcal{NP}$: given a collection of k disjoint sets $\{ V_1, \ldots , V_k\}$, for some k, such that $V_i\subseteq V$, for each $i \in [k]$, verify in polynomial time that each such set induces a subgraph of G that contains a Hamiltonian circuit.

Note that if a graph G is a YES instance for UNDIRECTED PARTITION INTO HAMILTONIAN SUBGRAPHS OF SIZE AT LEAST 6, each Hamiltonian circuit $V_i$, $i\in [k]$, in the collection has size at least 6.³ We prove:

Theorem 4.1

UNDIRECTED PARTITION INTO HAMILTONIAN SUBGRAPHS OF SIZE AT LEAST 6 is $\mathcal{NP}$-hard.

Proof

By reduction from DIRECTED PARTITION INTO HAMILTONIAN SUBGRAPHS. Fix an instance $G^d=\langle V^d, E^d \rangle$ of DIRECTED PARTITION INTO HAMILTONIAN SUBGRAPHS. We construct an instance $G=\langle V,E\rangle$ of UNDIRECTED PARTITION INTO HAMILTONIAN SUBGRAPHS OF SIZE AT LEAST 6 as follows:

• (1) For each vertex $v \in V^d$, add vertices $v_{1} , v_{2} , v_{3}$ to V and edges $(v_{1} , v_{2}), (v_{2}, v_{3})$ to E. Call the vertices $v_{1} , v_{2} , v_{3}$ normal vertices; call the edges $(v_{1} , v_{2}), (v_{2}, v_{3})$ normal edges.

• (2) For each single edge $(u, v)\in E^d$, add edge $(u_{3},v_{1})$ to E; call it a cross edge.

• (3) For each double edge $(u,v)\in E^d$, add a $\{u,v\}$-gadget to G:

  • (3/a) The $\{u,v\}$-vertices are $v_{0}, v_{4}, v_{5}$ and $u_{0}, u_{4}, u_{5}$. The $\{u,v\}$-vertices, over all double edges (u, v), are called gadget vertices.

  • (3/b) The $\{u,v\}$-edges are $(v_{1},v_{4})$, $(v_{3},v_{4})$, $(v_{4},v_{5})$, $(v_{5}, v_{0})$, $(v_{0}, u_{0})$, $(v_{4}, u_{0})$, $(v_{0},u_{4})$, $(u_{0}, u_{5})$, $(u_{5},u_{4})$, $(u_{4}, u_{3})$ and $(u_{4},u_{1})$. The $\{u,v\}$ -edges, over all double edges (u, v), are called gadget edges.

Figures 2 and  3 demonstrate Steps (2) and (3) of the construction, respectively. Figure 4 provides an example of the transformation of a directed graph $G^d$ into the undirected graph G. Observe that, by construction, every cycle in the graph G has size at least 4.

Fig. 2

A single edge $(u,v)\in E^d$ induces a cross edge $(u_3,v_1)\in E$ (Step (2))

Fig. 3

A double edge $(u,v)\in E^d$ induces a $\{u,v\}$-gadget in the graph G (Step (3))

Fig. 4

An example for the transformation of a directed graph $G^d$ into the undirected graph G

Note that the sequence $u_4,u_5, u_0,v_4,v_5,v_0,u_4$ is a Hamiltonian circuit for the subgraph induced by the $\{u,v\}$-vertices in a $\{ u,v\}$-gadget and has size 6. Hence, we obtain:

Lemma 4.2

The subgraph induced by the $\{u,v\}$-vertices in a $\{u,v\}$-gadget is Hamiltonian with a Hamiltonian circuit of size six: $u_4,u_5, u_0,v_4,v_5,v_0,u_4$.

We continue to prove a second significant property of a $\{u,v\}$-gadget.

Lemma 4.3

There is a single Hamiltonian path that cannot be extended to a Hamiltonian circuit for the subgraph induced by the $\{u,v\}$-vertices in a $\{u,v\}$-gadget; this is the path $u_4,u_5,u_0,$ $v_0,v_5,v_4$.

Proof

There are only two Hamiltonian paths in the subgraph induced by the $\{u,v\}$-vertices: (i) the path $u_4,u_5,u_0, v_4,v_5,v_0$, which, returning to vertex $u_4$, extends to a cycle, and (ii) the path $u_4,u_5,u_0,v_0,v_5,v_4$, which cannot be extended to a cycle. $\square$

We now prove:

Lemma 4.4

Consider a collection of Hamiltonian circuits covering G. Then, for each vertex $v\in V$, the normal vertices $v_1,v_2$ and $v_3$ are in the same Hamiltonian circuit.

Proof

Since the vertex $v_2$ has degree 2, its two neighboring vertices in a Hamiltonian circuit are its neighbors $v_1$ and $v_3$. $\square$

We continue to prove:

Lemma 4.5

Consider a collection of Hamiltonian circuits covering G. Then, for each $\{u,v\}$-gadget, the gadget vertices $u_4,u_5$ and $u_0$ (resp., $v_4$, $v_5$ and $v_0$) are in the same Hamiltonian circuit.

Proof

Since the vertex $u_5$ (resp., $v_5$) has degree 2, its two neighboring vertices in a Hamiltonian circuit are its neighbors $u_4$ and $u_0$ (resp., $v_4$ and $v_0$). $\square$

We proceed to prove:

Lemma 4.6

Consider a collection of Hamiltonian circuits covering G. Then, for each $\{u,v\}$-gadget, all $\{u,v\}$-vertices are in the same Hamiltonian circuit.

Proof

Consider vertex $u_0$ in the $\{u,v\}$-gadget. By Lemma 4.5, $u_5$ is one of the two neighboring vertices of vertex $u_0$ in a Hamiltonian circuit. By the construction of a $\{u,v\}$-gadget, the other neighboring vertex of $u_0$ is either $v_0$ or $v_4$. By Lemmas 4.2 and 4.3, the claim follows. $\square$

We now define a function $\phi$ that maps edges in $G^d$ to simple paths in G:

$$\begin{aligned} \phi (u,v)& = \left\{ \begin{array}{ll} u_3, v_1, v_2, &{} {\text {if}}\;(u, v)\;{\text {is}}\;{\text {a}}\;{\text {single}}\;{\text {edge}} \\ u_3, u_4, u_5, u_0, v_0, v_5, v_4, v_1, v_2 , &{} {\text {if}}\;(u, v)\;{\text {is}}\;{\text {a}}\;{\text {double}}\;{\text {edge}} \end{array} . \right. \end{aligned}$$

Note that, by Lemma 4.3, this extends a unique Hamiltonian path that is not a Hamiltonian circuit for the subgraph induced by the $\{u,v\}$-vertices (i.e., the path $u_4,u_5,u_0,v_0,v_5,v_4$ in Lemma 4.3). Call it a cross path. We now prove:

Claim 4.7

The function $\phi$ is extendible to a function $\widehat{\phi }$ mapping simple paths in $G^d$ to simple paths in G.

Proof

Consider each vertex v participating in a path in $G^d$ through directed edges (u, v), (v, w) . By the definition of function $\phi$, the first vertex of the path in G corresponding to edge (u, v) (resp., edge (v, w)) of $G^d$ is vertex $u_3$ (resp., $v_3$), independently of whether edge (u, v) (resp., (v, w) ) is a double edge or not. Moreover, by the definition of function $\phi$, the last vertices of the path in G corresponding to edge (u, v) (resp., edge (v, w)) are the vertices $v_1,v_2$ (resp., $w_1,w_2$) in this order, independently of whether edge (u, v) (resp., (v, w)) is a double edge or not. We define the function $\widehat{\phi }$ that maps each path (u, v), (v, w) of $G^d$ to the path $u_3, \ldots , v_1, v_2, v_3, \ldots , w_1,w_2$ in G:

$$\begin{aligned} \widehat{\phi } ((u,v),(u,w))& = u_3, \ldots , v_1, v_2, v_3, \ldots , w_1,w_2. \end{aligned}$$

The first (resp., second) group of dots in the sequence is empty when (u, v) (resp., (u, w)) is a single edge. Otherwise, the first (resp., second) group of dots is equal to the path $u_4, u_5,u_0, v_0, v_5,v_4$ (resp., $v_4, v_5,v_0, w_0, w_5,w_4$) of G when (u, v) (resp., (v, w)) is a double edge. Thus, the function $\widehat{\phi }$ maps simple paths in $G^d$ to simple paths in G.$\square$

We continue to prove:

Lemma 4.8

Assume that $G^d$ is a YES instance for DIRECTED PARTITION INTO HAMILTONIAN SUBGRAPHS. Then, G is a YES instance for UNDIRECTED PARTITION INTO HAMILTONIAN SUBGRAPHS OF SIZE AT LEAST 6.

Proof

By Claim 4.7, a Hamiltonian circuit for $G^d$ is mapped to a not necessarily Hamiltonian circuit for G.

We now use function $\widehat{\phi }$ to prove that in this case, G is a YES instance for the problem UNDIRECTED PARTITION INTO HAMILTONIAN SUBGRAPHS OF SIZE AT LEAST 6. Note first that, by construction, every cycle contained in graph G is of size at least 6. Thus, G is an input for UNDIRECTED PARTITION INTO HAMILTONIAN SUBGRAPHS OF SIZE AT LEAST 6. Now take a collection $\mathcal{C}^d = \{c^d_1, \ldots , c^d_k\}$ of Hamiltonian circuits covering $G^d$. Applying function $\widehat{\phi }$ on $\mathcal{C}^d$, we get a collection of circuits $\mathcal{C} = \{c _1, \ldots ,c _k\}$ for G. We prove:

Claim 4.9

$\mathcal{C}$ can be extended so that to cover G.

Proof

Recall that V consists of (i) normal vertices and (ii) gadget vertices. Consider first any vertex $v \in V^d$ and the corresponding normal vertices $v_1, v_2, v_3$ in V. Let $c^d$ be the cycle in $\mathcal{C}^d$ covering vertex v in $V^d$. By the construction of $\widehat{\phi }$, there exists a path $v_1, v_2, v_3$ corresponding to a cycle c in $\mathcal{C}$. It follows that $\mathcal{C}$ covers all normal vertices of G. $\square$

Consider now the rest of the vertices of V. These are the gadget vertices obtained for each double edge of $G^d$ (of the form $u_0,u_4, u_5$ for a vertex u of $V^d$). Consider any double edge (u, v) contained in the collection $\mathcal{C}^d$. By the construction of $\widehat{\phi }$, the path $u_4, u_5,u_0, v_0, v_5,v_4$ is contained in $\mathcal{C}$. Thus, the gadget vertices corresponding to double edges contained in the collection $\mathcal{C}^d$ are covered by $\mathcal{C}$. So, the only vertices of V not covered by $\mathcal{C}$ are the gadget vertices corresponding to double edges not contained in $\mathcal{C}^d$. We now extend the collection $\mathcal{C}$ to get the collection $\widehat{\mathcal{C}}$ that covers those vertices as well as follows:

For each directed double edge (u, v) of $G^d$ not contained in $\mathcal{C}^d$, add the cycle $(u_4,u_5 ,u_0,v_4,v_5,v_0,u_4)$ to $\widehat{\mathcal{C}}$.

Clearly, each such cycle covers all (u, v)-gadget vertices. It follows that the collection $\widehat{\mathcal{C}}$ covers all vertices of V. So, $\widehat{\mathcal{C}}$ is a collection of Hamiltonian circuits that cover G. We finally prove:

Claim 4.10

Each cycle in the collection $\widehat{\mathcal{C} }$ has size at least six.

Proof

Recall that the collection consists of (1) cycles obtained by function $\widehat{\phi }$ and (2) the extension of $\mathcal{C}$ to $\widehat{\mathcal{C}}$ to cover also the gadget vertices of G corresponding to double edges of $G^d$ not contained in $\mathcal{C}^d$. For case (1), consider first any cycle of $\widehat{\mathcal{C}}$ obtained by function $\widehat{\phi }$. Recall that, by the construction of G, each vertex v of $G^d$ is replaced by three vertices in G. Moreover, since $\widehat{\mathcal{C}}$ is a collection of Hamiltonian circuits that cover G, Lemma  4.4 implies that the normal vertices $v_1, v_2, v_3$ are included in the same Hamiltonian circuit in the collection. Since any circuit in $\mathcal{C}^d$ has size at least two, by the definition of the function $\widehat{\phi }$, the corresponding cycle in $\widehat{\mathcal{C}}$ covering the corresponding normal vertices has size at least 6. For case (2), consider any cycle of $\widehat{\mathcal{C}}$ obtained by a double edge (u, v) of $G^d$ that is not included in the collection $\mathcal{C}^d$. By the construction of the set $\widehat{\mathcal{C}}$, the cycle is of size 6; this is, the cycle $u_4,u_5 ,u_0,v_4,v_5,v_0,u_4$. $\square$

The claim now follows. $\square$

We proceed to prove:

Lemma 4.11

If G is a YES instance for UNDIRECTED PARTITION INTO HAMILTONIAN SUBGRAPHS OF SIZE AT LEAST 6, then $G^d$ is a YES instance for DIRECTED PARTITION INTO HAMILTONIAN SUBGRAPHS.

Proof

Consider a collection $\widehat{\mathcal{C}}$ of Hamiltonian circuits, each of size at least 6, covering G. By Lemma 4.2, $\widehat{\mathcal{C}}$ may contain a Hamiltonian cycle for the subgraph induced by a $\{u,v\}$-gadget $u_4,u_5 ,u_0,v_4,v_5,v_0,u_4$. Call such a cycle a gadget Hamiltonian cycle. Restrict $\widehat{\mathcal{C}}$ to $\mathcal{C}$ by excluding all such gadget Hamiltonian cycles. By Lemmas  4.4 and 4.6, each circuit c in $\mathcal{C}$ consists of an alternating sequence of two incident normal edges followed by a cross edge or a cross path. Each pair of incidence normal edges $(u_1,u_2), (u_2,u_3)$ determines a vertex in $G^d$, i.e. vertex u, while the following cross edge $u_3,v_1$ or cross path $u_4,u_5,u_0,v_0,v_5,v_4,v_1$ determines a following vertex in $G^d$, which is vertex v. This induces a function $\widehat{\psi }$ that maps the collection $\widehat{\mathcal{C}}$ in G to a collection $\mathcal{C}^d$ of Hamiltonian circuits in $G^d$. Since $\widehat{\mathcal{C}}$ is a collection of Hamiltonian circuits covering G, it follows that $\mathcal{C}^d$ is a collection of Hamiltonian circuits covering $G^d$, as needed. $\square$

Lemmas 4.8 and 4.11 together imply the claim. $\square$

4.2 Two Problems in $\mathcal{P}$

For our positive results, we shall consider two graph-theoretic problems; both are concerned with the size of a Maximum Independent Set.

MAXIMUM INDEPENDENT SET EQUAL MINIMUM EDGE COVER

i.: An undirected graph $G = \langle V, E \rangle$.

o.: A Maximum Independent Set of size $\beta ^{\prime }(G)$ if $\alpha (G)=\beta ^{\prime }(G)$, or No if $\alpha (G) < \beta ^{\prime }(G)$.

MAXIMUM INDEPENDENT SET EQUAL HALF ORDER

i.: An undirected graph $G = \langle V, E \rangle$.

o.: A Maximum Independent Set of size $\frac{\textstyle |V|}{\textstyle 2}$ if $\alpha (G)=\frac{\textstyle |V|}{\textstyle 2}$, or No if $\alpha (G)\ne \frac{\textstyle |V|}{\textstyle 2}$.

We establish that these two new problems are polynomial time computable by establishing reductions to 2SAT, which is solvable in polynomial time via the folklore purge algorithm (see, for example, [30, Section 4.2.2]).

4.2.1 Maximum Independent Set Equal Minimum Edge Cover

We show:

Proposition 4.12

MAXIMUM INDEPENDENT SET EQUAL MINIMUM EDGE COVER is solvable in time Minimum Edge Cover.

Proof

We present a polynomial time algorithm MISEqualMEC for MAXIMUM INDEPENDENT SET EQUAL MINIMUM EDGE COVER:

Algorithm MISEqualMEC

Input: A graph $G= \langle V, E \rangle$.

Output: A Maximum Independent Set IS of size $\beta ^{\prime }(G)$ if $\alpha (G)=\beta ^{\prime }(G)$, or No if $\alpha (G)<\beta ^{\prime }(G)$.

• (1) Choose a Minimum Edge Cover EC.

• (2) Construct an instance $\phi$ of 2SAT as a collection of clauses on the variable set V:

  • (2/a) For each edge $(u,v)\in E$, add the clause $({\bar{u}} \vee {\bar{v}})$.

  • (2/b) For each edge $(u,v)\in EC$, add the clause $(u \vee v)$.

  • (2/c) For each multiple-edge star graph of EC with center vertex u, add the clause $({\bar{u}} \vee {\bar{u}})$.

• (3) Compute a satisfying assignment $\chi$ for $\phi$, or output No if such does not exist.

• (4) Set $IS:= \{ u \in V \mid \chi (u) = 1\}$.

Denote as $\phi _1$, $\phi _2$ and $\phi _3$ the collections of clauses obtained at the steps (2/a), (2/b) and (2/c), respectively, of the algorithm MISEqualMEC. We prove:

Lemma 4.13

G has a Maximum Independent Set of size $\alpha (G)=\beta ^{\prime }(G)$ if and only if $\phi$ is satisfiable.

Proof

Assume first that G has a Maximum Independent Set $\widehat{IS}$ of size $|\widehat{IS}| = \alpha (G)= \beta ^{\prime }(G)$. We construct an assignment $\chi$ for $\phi$ as follows:

For each variable $u\in V$, set $\chi (u):=1$ if $u\in \widehat{IS}$, and $\chi (u):=0$ otherwise.

Since $|\widehat{IS}|= \beta ^{\prime }(G)$ and EC is a Minimum Edge Cover, it follows that $|\widehat{IS}|=|EC|$. Since EC is an Edge Cover, this implies that $\widehat{IS}$ contains (i) exactly one vertex for each single-edge star graph in EC and (ii) all terminal vertices for each multi-edge star graph in EC. We prove that $\chi$ is a satisfying assignment for $\phi$. Consider each of the clause collections $\phi _1$, $\phi _2$ and $\phi _3$:

• Take any clause $({\bar{u}} \vee {\bar{v}})$ in $\phi _1$; so, $(u,v)\in E$. Since $\widehat{IS}$ is an Independent Set, either $u\not \in \widehat{IS}$ or $v\not \in \widehat{IS}$. Hence, by construction of $\chi$, either $\chi (u)=0$ or $\chi (v)=0$. So, the clause $({\bar{u}} \vee {\bar{v}})$ is satisfied by $\chi$; hence, so is $\phi _1$.

• Take any clause $(u \vee v)$ in $\phi _2$; so, (u, v) is an edge in EC. Recall that $\widehat{IS}$ contains exactly one vertex of each edge single-edge star graph of EC and all terminal vertices of each multi-edge star graph of EC. Thus, in any case, exactly one of u and v is in $\widehat{IS}$. Hence, by construction of $\chi$, either $\chi (u)=1$ or $\chi (v)=1$. So, the clause $(u \vee v)$ is satisfied by $\chi$; hence, so is $\phi _2$.

• Take any clause $({\bar{u}} \vee {\bar{u}})$ in $\phi _3$; so, u is the center vertex of some multiple-edge star graph in EC. Recall that $u\not \in \widehat{IS}$. Hence, by construction of $\chi$, $\chi (u)=0$. So, the clause $({\bar{u}} \vee {\bar{u}})$ is satisfied by $\chi$; hence, so is $\phi _3$.

Since $\chi$ satisfies all clause sets $\phi _1$, $\phi _2$ and $\phi _3$, $\chi$ satisfies $\phi$ and $\phi$ is satisfiable. Hence, if $\phi$ is not satisfiable, then there is no Maximum Independent Set of size $\alpha (G)= \beta ^{\prime }(G)$, and the output No in Step (3) is correct.

Assume now that $\phi$ is satisfiable. We shall prove that G has a Maximum Independent Set of size $\alpha (G)= \beta ^{\prime }(G)$. We prove that the set IS constructed in Step (4) is such a Maximum Independent Set. Consider a satisfying assignment $\chi$ for $\phi$. Consider an arbitrary pair of vertices $u,v \in IS$. By construction of IS, it follows that both $\chi (u)=1$ and $\chi (v)=1$. So, $\chi ({\bar{u}} \vee {\bar{v}})=0$. Since $\chi$ satisfies $\phi$, it follows that the clause $({\bar{u}} \vee {\bar{v}})$ is not included in $\phi$. By construction of $\phi$ (Step (2/a)), this implies that $(u,v)\not \in E$. Hence, IS is an Independent Set. It remains to prove that IS is a Maximum Independent Set.

• Consider a single-edge star with a single edge $(u,v)\in EC\subseteq E$. By construction of $\phi$, both clauses $({\bar{u}} \vee {\bar{v}})$ and $(u \vee v)$ are included in $\phi$ (by Steps (2/a) and (2/b), respectively). Since $\chi$ satisfies $\phi$, it satisfies both $({\bar{u}} \vee {\bar{v}})$ and $( u \vee v )$. Hence, it follows that either $\chi (u)=1$ and $\chi (v)=0$, or $\chi (u)=0$ and $\chi (v)=1$. By construction of IS, this implies that either $u\in IS$ or $v\in IS$ but not both. So, IS contains exactly one vertex for each single-edge star graph in EC.

• Consider now a multiple-edge star graph with a center vertex $u\in EC$ and edges $(u,v_1), (u,v_2), \ldots ,\; (u,v_k)$. By construction of $\phi$, the clauses $({\bar{u}} \vee {\bar{u}})$, $( u \vee v_1 )$, $( u \vee v_2) , \ldots , ( u \vee v_k)$ are included in $\phi$ (by Steps (2/b)) and (2/c)). Since $\chi$ satisfies $\phi$, it follows that $\chi (u)=0$ and $\chi (v_1)=\chi (v_2)= \cdots = \chi (v_k)= 1$. By construction of IS, it follows that $u\not \in IS$ and $v_1, v_2, \ldots , v_k \in IS$, for each multiple-edge star graph in EC.

Hence, it follows that $|IS|=|EC|$. Since EC is a Minimum Edge Cover, it follows that $|IS|= \beta ^{\prime }(G)$. Since $\beta ^{\prime }(G)\ge \alpha (G)$, this implies that $|IS|\ge \alpha (G)$. Since IS is an Independent Set, $|IS|\le \alpha (G)$. It follows that $|IS|= \alpha (G)$, so that IS is a Maximum Independent Set of size $\alpha (G)=\beta ^{\prime }(G)$, as needed. $\square$

The proof is now complete. $\square$

4.2.2 MAXIMUM INDEPENDENT SET EQUAL HALF ORDER

We show:

Proposition 4.14

MAXIMUM INDEPENDENT SET EQUAL HALF ORDER is solvable in time Perfect Matching, when restricted to the class of graphs with a Perfect Matching.

Proof

We present a polynomial time algorithm MISEqualHO for MAXIMUM INDEPENDENT SET EQUAL HALF ORDER:

Algorithm MISEqualHO

Input: A graph $G= \langle V, E \rangle$ with a Perfect Matching.

Output: A Maximum Independent Set IS of size $\frac{\textstyle |V|}{\textstyle 2}$ if $\alpha (G)= \frac{\textstyle |V|}{\textstyle 2}$, or No if $\alpha (G)\ne \frac{\textstyle |V|}{\textstyle 2}$.

• (1) Choose a Perfect Matching M.

• (2) Construct an instance $\phi$ of 2SAT as a collection of clauses on the variable set V:

  • (2/a) For each edge $(u,v)\in E$, add the clause $({\bar{u}} \vee {\bar{v}})$.

  • (2/b) For each edge $(u,v)\in M$, add the clause $(u \vee v)$.

• (3) Compute a satisfying assignment $\chi$ for $\phi$, or output No if such does not exist.

• (4) Set $IS:= \{ u \in V \mid \chi (u) = 1\}$.

Denote as $\phi _{1}$ and $\phi _{2}$ the sets of clauses obtained at the steps (2/a) and (2/b), respectively, of MISEqualHO. We prove:

Lemma 4.15

G has a Maximum Independent Set of size $\alpha (G)= \frac{\textstyle |V|}{\textstyle 2}$ if and only if $\phi$ is satisfiable.

Proof

Assume first that G has a Maximum Independent Set $\widehat{IS}$ of size $\alpha (G)=\frac{\textstyle |V|}{\textstyle 2}$. We construct an assignment $\chi$ for $\phi$ as follows:

For each variable $u\in V$, set $\chi (u):=1$ if $u\in \widehat{IS}$, and $\chi (u):=0$ otherwise.

Since $|\widehat{IS}|= \frac{\textstyle |V|}{\textstyle 2}$ and M is a Perfect Matching, it follows that $|\widehat{IS}|=|M|$. Since $|\widehat{IS}|=|M|$ and M is a Perfect Matching, $\widehat{IS}$ contains exactly one vertex for each edge in M. We consider separately each of the clause collections $\phi _1$ and $\phi _2$.

• Take any clause $({\bar{u}} \vee {\bar{v}})$ in $\phi _1$; so, $(u,v)\in E$. Since $\widehat{IS}$ is an Independent Set, either $u\not \in \widehat{IS}$ or $v\not \in \widehat{IS}$. Hence, by construction of $\chi$, either $\chi (u)=0$ or $\chi (v)=0$. So, the clause $({\bar{u}} \vee {\bar{v}})$ is satisfied by $\chi$, and so is $\phi _1$.

• Take any clause $(u \vee v)$ in $\phi _2$; so, $(u,v) \in M$. Recall that exactly one of u and v is in $\widehat{IS}$. Hence, by construction of $\chi$, either $\chi (u)=1$ or $\chi (v)=1$. So, the clause $(u \vee v)$ is satisfied by $\chi$, and so is $\phi _2$.

Since $\chi$ satisfies all clause sets $\phi _1$ and $\phi _2$, $\chi$ satisfies $\phi$ and $\phi$ is satisfiable. Hence, if $\phi$ is not satisfiable, then there is no Maximum Independent Set of size $\alpha (G)=\frac{\textstyle |V|}{\textstyle 2}$, and the output No in Step (3) is correct.

Assume now that $\phi$ is satisfiable. We shall prove that the set IS constructed in Step (4) is a Maximum Independent Set of size $\alpha (G) = \frac{\textstyle |V|}{\textstyle 2}$. Consider a satisfying assignment $\chi$ for $\phi$. Consider an arbitrary pair of vertices $u,v \in IS$. By construction of IS, it follows that both $\chi (u)=1$ and $\chi (v)=1$. So, $\chi ({\bar{u}} \vee {\bar{v}})=0$. Since $\chi$ satisfies $\phi$, it follows that the clause $({\bar{u}} \vee {\bar{v}})$ is not included in $\phi$. By construction of $\phi$ (Step (2)), this implies that $(u,v)\not \in E$. Hence, IS is an Independent Set. It remains to prove that IS is a Maximum Independent Set of size $\alpha (G) = \frac{\textstyle |V|}{\textstyle 2}$.

Consider an edge $(u,v)\in M\subseteq E$. By construction of $\phi$, both clauses $({\bar{u}} \vee {\bar{v}})$ and $(u \vee v)$ are included in $\phi$ (by steps (2/a) and (2/b), respectively). Since $\chi$ satisfies $\phi$, it follows that either $\chi (u)=1$ and $\chi (v)=0$, or $\chi (u)=0$ and $\chi (v)=1$. By construction of IS, this implies that either $u\in IS$ or $v\in IS$ but not both. Hence, IS contains exactly one vertex for each edge in M. It follows that $|IS|=|M|$. Since M is a Perfect Matching, the vertex set including exactly one vertex for each edge in M is an Independent Set, and this implies that $| \alpha (G) |\ge |M|$. Since M is a Perfect Matching, $|M|= \frac{\textstyle |V|}{\textstyle 2}$. So, $|IS|= |M|= \frac{\textstyle |V|}{\textstyle 2}$. Since M is a Perfect Matching, it is also an Edge Cover, so that $|M| \ge \beta ^{\prime }(G)$. Since $\alpha (G)\le \beta ^{\prime }(G)$, it follows that $|M| \ge \alpha (G)$. It follows that $|M| = \alpha (G)$. Since $|IS|=|M|=\frac{\textstyle |V|}{\textstyle 2}$, this implies that IS is a Maximum Independent Set of size $\alpha (G)=\frac{\textstyle |V|}{\textstyle 2}$, as needed.$\square$

The proof is now complete. $\square$

5 Arbitrary Nash Equilibria

The complexity and the Price of Defense of arbitrary Nash equilibria are considered in Sections 5.1 and 5.2, respectively.

5.1 Complexity

Denote as $\mathsf{\widehat{AD}} ( G)$ the special case of $\mathsf{AD}( G)$ with $\nu =1$; denote as $\mathsf{a}$ the (single) attacker for $\mathsf{\widehat{AD}} ( G)$. So, $\mathsf{\widehat{AD}} ( G)$ is a Two-Players game. Consider a mixed profile $\mathbf {\widehat{\varvec{\sigma }}}$ for $\mathsf{\widehat{AD}} ( G)$. Construct from $\mathbf {\widehat{\varvec{\sigma }}}$ an Attacker-Symmetric mixed profile $\varvec{\sigma }$ for $\mathsf{AD}( G)$, where for each attacker $\mathsf{a}_i$, for each vertex $v\in V$, $\sigma _i(v)=\widehat{\sigma }_{\mathsf{a}}(v)$; for the defender $\mathsf{d}$, for each edge $e\in E$, $\sigma _{\mathsf{d}}(e) = \widehat{\sigma }_{\mathsf{d}}(e)$; so, $\varvec{\sigma }$ results from copying the single attacker $\mathsf{a}$’s mixed strategy in $\mathbf {\widehat{\varvec{\sigma }}}$ to each attacker’s mixed strategy in $\varvec{\sigma }$, and copying the defender’s mixed strategy in $\mathbf {\widehat{\varvec{\sigma }}}$ to the defender’s mixed strategy in $\varvec{\sigma }$. Note that for each attacker $\mathsf{a}_i$, $\mathsf{Supp_{\varvec{\sigma }}}(\mathsf{a}_i) = \mathsf{Supp}_{ \mathbf {\widehat{\varvec{\sigma }}}} (\mathsf{a})$. We prove:

Proposition 5.1

Assume that $\widehat{{ \varvec{\sigma }}}$ is a Nash equilibrium for $\mathsf{\widehat{AD}} ( G)$. Then, $\varvec{\sigma }$ is a Nash equilibrium for $\mathsf{AD}( G)$.

Proof

We prove that $\varvec{\sigma }$ fulfills the characterization of Nash equilibria (Proposition 3.2) for $\mathsf{AD}( G)$. Since $\sigma _{\mathsf{d}}(e) = \widehat{\sigma } _{\mathsf{d}}(e)$ for each edge $e\in E$, it follows that for each vertex $v\in V$, ${\mathbb {P}}_{\varvec{\sigma }}(\mathsf{Hit}(v)) = {\mathbb {P}}_{\widehat{\varvec{\sigma }}}(\mathsf{Hit}(v))$. Since $\widehat{\varvec{\sigma }}$ is a Nash equilibrium, Proposition 3.2 (Condition (C.1)) gives that for each vertex $v\in \mathsf{Supp}_{\widehat{\sigma }}(\mathsf{a})$, ${\mathbb {P}}_{\widehat{\varvec{\sigma }}}(\mathsf{Hit}(v)) = \min _{v^{\prime }\in V} {\mathbb {P}}_{\widehat{\varvec{\sigma }}} (\mathsf{Hit}(v^{\prime }))$. Since for each attacker $\mathsf{a}_i \in {{\mathcal {A}}}$, $\mathsf{Supp_{\varvec{\sigma }}}(\mathsf{a}_i) =\mathsf{Supp}_{\widehat{\sigma }}(\mathsf{a})$, we get that for each vertex $v\in \mathsf{Supp}_{\varvec{\sigma }}({{\mathcal {A}}})$, ${\mathbb {P}}_{\varvec{\sigma }}(\mathsf{Hit}(v)) = \min _{v^{\prime }\in V}{\mathbb {P}}_{\varvec{\sigma }} (\mathsf{Hit}(v^{\prime }))$ and Condition (C.1) follows. We proceed to prove Condition (C.2). Fix an arbitrary edge $(u,v) \in E$. Then,

$$\begin{aligned} \mathsf{A_{\varvec{\sigma }}}( u,v)& = \sum _{\mathsf{a}_i\in {{\mathcal {A}}}} \sigma _i(u) + \sum _{\mathsf{a}_i\in {{\mathcal {A}}}} \sigma _i(v) \\& = \nu \cdot \left( \widehat{\sigma }_{\mathsf{a}}(u) + \widehat{\sigma }_{\mathsf{a}}(v) \right) \quad ({\text {by}}\;{\text {the}}\;{\text {construction}}\; {\text {of}}\;\varvec{\sigma }\;{\text {from}}\;\widehat{\varvec{\sigma }}).\\& = \nu \cdot \mathsf{A}_ {\widehat{\varvec{\sigma }}} (u,v). \end{aligned}$$

By Proposition 3.2 (Condition (C.2)), it follows that for each edge $e \in \mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d})$, $\mathsf{A_{\varvec{\sigma }}}(e) = \max _{e^{\prime } \in E} \mathsf{A_{\varvec{\sigma }}}(e^{\prime })$ and $\mathsf{A}_{\widehat{\varvec{\sigma }}} (e) = \max _{e^{\prime }\in E} \mathsf{A}_{\mathbf {\widehat{\varvec{\sigma }}}}(e^{\prime })$. Since $\mathsf{Supp}_{\widehat{\varvec{\sigma }}} (\mathsf{d}) = \mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d})$, Condition (C.2) for $\varvec{\sigma }$ follows. $\square$

Proposition 5.1 implies that a Nash equilibrium $\varvec{\sigma }$ for $\mathsf{AD}( G)$ is polynomial time computable from a Nash equilibrium $\mathbf {\widehat{\varvec{\sigma }}}$ for $\mathsf{\widehat{AD}} ( G)$.

We now establish that $\mathsf{\widehat{AD}} ( G)$ is Constant-Sum: for each mixed profile $\mathbf {\widehat{\varvec{\sigma }}}$, ${\mathsf {U}}_{ \mathsf{a}}( \mathbf {\widehat{\varvec{\sigma }}})+{\mathsf {U}}_{\mathsf{d}}( \mathbf {\widehat{\varvec{\sigma }}})$ evaluates to some constant (independent of $\mathbf {\widehat{\varvec{\sigma }}}$). Clearly,

$$\begin{aligned} {\mathsf {U}}_{\mathsf{a}}( \mathbf {\widehat{\varvec{\sigma }}})+{\mathsf {U}}_{ \mathsf{d}}( \mathbf {\widehat{\varvec{\sigma }}})& = \sum _{v\in V} \widehat{\sigma }_{\mathsf{a}}(v) \cdot \left( 1 - \sum _{e\in \mathsf{Edges}_{\widehat{\varvec{\sigma }}} (v)}\widehat{\sigma }_{\mathsf{d}}(e)\right) + \sum _{(u,v)=e \; \in E} \widehat{\sigma }_{\mathsf{d}}(e) \cdot \left( \widehat{\sigma }_{\mathsf{a}}(u) +\widehat{\sigma }_{\mathsf{a}}(v)\right) \\& = \sum _{v\in V} \widehat{\sigma }_{\mathsf{a}}(v) -\sum _{v\in V} \widehat{\sigma }_{\mathsf{a}}(v) \left( \sum _{e\in \mathsf{Edges}_{\widehat{\varvec{\sigma }}} (v)}\widehat{\sigma }_{\mathsf{d}}(e)\right) + \sum _{(u,v)=e \; \in E} \widehat{\sigma }_{\mathsf{d}}(e) \cdot \left( \widehat{\sigma }_{\mathsf{a}}(u) +\widehat{\sigma }_{\mathsf{a}}(v)\right) \\& = 1 - \sum _{(u,v)=e \; \in E} \widehat{\sigma }_{\mathsf{d}}(e) \cdot \left( \widehat{\sigma }_{\mathsf{a}}(u) +\widehat{\sigma }_{\mathsf{a}}(v)\right) +\sum _{(u,v)=e \; \in E} \widehat{\sigma }_{\mathsf{d}}(e) \cdot \left( \widehat{\sigma }_{\mathsf{a}}(u) +\widehat{\sigma }_{\mathsf{a}}(v)\right) \\& = 1. \end{aligned}$$

Since a Nash equilibrium for a Two-Players, Constant-Sum game is polynomial time reducible to Linear Programming [40], which is polynomial time solvable [19], we obtain:

Theorem 5.2

F ARBITRARY NE is solvable in time Linear Programming.

5.2 The Price of Defense

We first evaluate the Defense Ratio of an arbitrary Nash equilibrium.

Proposition 5.3

Consider a Nash equilibrium $\varvec{\sigma }$. Then,

$$\begin{aligned} \mathsf{DR}_{\varvec{\sigma }}& = \frac{\textstyle 1}{\textstyle \min _{v^{\prime }\in V} {{\mathbb {P}}}_{\varvec{\sigma }}(\mathsf{Hit}(v^{\prime })) }. \end{aligned}$$

Proof

Clearly,

$$\begin{aligned} \mathsf{DR}_{\varvec{\sigma }}& = \frac{\textstyle \nu }{\textstyle {\mathsf {U}}_ {\mathsf{d}}(\varvec{\sigma })} \\& = \frac{\textstyle \nu }{\textstyle \sum _{i\in {{\mathcal {A}}}} \left( \sum _{v\in V} \sigma _i(v) \cdot {{\mathbb {P}}}_{\varvec{\sigma }}(\mathsf{Hit}(v))\right) } \\& = \frac{\textstyle \nu }{\textstyle \sum _{i\in {{\mathcal {A}}}} \left( \sum _{v\in \mathsf{Supp_{\varvec{\sigma }}}(i)} \sigma _i(v) \cdot {{\mathbb {P}}}_{\varvec{\sigma }}(\mathsf{Hit}(v))\right) } \\& = \frac{\textstyle \nu }{\textstyle \sum _{i\in {{\mathcal {A}}}} \left( \sum _{v\in \mathsf{Supp_{\varvec{\sigma }}}(i)} \sigma _i(v) \cdot \min _{v^{\prime }\in V}{{\mathbb {P}}}_{\varvec{\sigma }}(\mathsf{Hit}(v^{\prime }))\right) } \quad ({\text {by}}\;{\text {Proposition}}\;3.2\;({\text {Condition}}\;\mathsf{(C.1)}))\\& = \frac{\textstyle \nu }{\textstyle \sum _{i\in {{\mathcal {A}}}} \min _{v^{\prime }\in V} {{\mathbb {P}}}_{\varvec{\sigma }}(\mathsf{Hit}(v^{\prime })) } \\& = \frac{\textstyle 1}{\textstyle \min _{v^{\prime }\in V} {{\mathbb {P}}}_{\varvec{\sigma }}(\mathsf{Hit}(v^{\prime })) }, \\ \end{aligned}$$

as needed. $\square$

We now show:

Theorem 5.4

$\mathsf{PoD}_G \ge \frac{\textstyle |V|}{\textstyle 2}$.

Proof

Clearly, for any fixed Nash equilibrium $\varvec{\sigma }$,

$$\begin{aligned} \mathsf{PoD}_G\ge \, & {} \frac{\textstyle \nu }{\textstyle {\mathsf {U}}_{ \mathsf{d}}(\varvec{\sigma }) } \quad ({\text {by}}\; {\text {definition}}\;{\text {of}}\;\mathsf{PoD}_G)\\& = \frac{\textstyle 1}{\textstyle \min _{v^{\prime }\in V} {{\mathbb {P}}}_{\varvec{\sigma }}(\mathsf{Hit}(v^{\prime }))} \quad ({\text {by}}\; {\text {Proposition}}\;5.3)\\\ge \, & {} \frac{\textstyle |V|}{\textstyle 2} \quad ({\text {by}}\;{\text {Proposition}}\; 3.3), \end{aligned}$$

as needed. $\square$

We introduce:

Definition 5.1

A Nash equilibrium $\varvec{\sigma }$ is Defense-Optimal if its Defense Ratio $\frac{\textstyle \nu }{\textstyle {\mathsf {U}}_{ \mathsf{d}}(\varvec{\sigma })}$ equals $\frac{\textstyle |V|}{\textstyle 2}$; that is, ${\mathsf {U}}_{ \mathsf{d}} (\varvec{\sigma })=\frac{\textstyle 2 \nu }{\textstyle |V|}$.

We define:

Definition 5.2

A graph G is Defense-Optimal if it admits a Defense-Optimal Nash equilibrium.

We prove that there are Defense-Optimal graphs.

Proposition 5.5

$K_3$ is Defense-Optimal.

Proof

Consider the Uniform&Fully-Mixed Nash equilibrium $\varvec{\sigma }$ for $K_3$. (Clearly, $\varvec{\sigma }$ is a Nash equilibrium as it can be easily shown to satisfy the conditions in Proposition 3.2.) Clearly,

$$ \begin{aligned} {\mathsf {U}}_ {\mathsf{d}}(\varvec{\sigma })& = \sum _{v\in V} \mathsf{A_{\varvec{\sigma }}}(v)\cdot {{\mathbb {P}}}_{\varvec{\sigma }}(\mathsf{Hit}(v) ) \\& = 3\cdot \frac{\textstyle \nu }{\textstyle 3} \cdot \frac{\textstyle 2}{\textstyle 3} \quad ({\text {since}}\;\varvec{\sigma }\;{\text {is}}\;{\text {Uniform}} \& {\text {Fully-Mixed}})\\& = \frac{\textstyle 2\nu }{\textstyle |V| }, \\ \end{aligned}$$

so that $\varvec{\sigma }$ is Defense-Optimal. Hence, $K_3$ is Defense-Optimal. $\square$

Finally we prove:

Proposition 5.6

Consider a Defense-Optimal Nash equilibrium $\varvec{\sigma }$. Then, for each vertex $v\in V$, ${{\mathbb {P}}}_{\varvec{\sigma }}(\mathsf{Hit}(v)) =\frac{\textstyle 2}{\textstyle |V|}$.

Proof

By Proposition  5.3 and Definition 5.1, $\min _{v^{\prime }\in V} {{\mathbb {P}}}_{\varvec{\sigma }}(\mathsf{Hit}(v^{\prime })) = \frac{\textstyle 2}{\textstyle |V|}$. By Lemma 3.1, $\sum _{v\in V}{{\mathbb {P}}}_{\varvec{\sigma }}(\mathsf{Hit}(v)) =2$. It follows that for each vertex $v\in V$, ${{\mathbb {P}}}_{\varvec{\sigma }}(\mathsf{Hit}(v)) =\frac{\textstyle 2}{\textstyle |V|}$. $\square$

Together with Proposition 3.3, Proposition 5.6 implies that Defense-Optimal Nash equilibria maximize the Minimum Hitting Probability.

6 Defense-Optimal Nash Equilibria

Section 6.1 provides a characterization of Defense-Optimal graphs. The characterization is used in Sect. 6.2 to derive a polynomial time algorithm to decide the existence of and compute a Defense-Optimal Nash equilibrium (if there is one).

6.1 Characterization of Defense-Optimal Graphs

We first prove:

Proposition 6.1

Assume that G has a Fractional Perfect Matching. Then, G is Defense-Optimal, and there is a Defense-Optimal Nash equilibrium which is Attacker-Symmetric&Uniform&FullyMixed.

Proof

Consider a Fractional Perfect Matching ${\mathsf {f}} : E \rightarrow [0,1]$. Define an Attacker-Symmetric& Uniform&FullyMixed profile $\varvec{\sigma }$ where, for each edge $e\in E$,

$$\begin{aligned} \sigma _{\mathsf{d}}(e):& = \frac{\textstyle 2}{\textstyle |V|}\cdot {\mathsf {f}} (e) . \end{aligned}$$

Recall that we consider only non-trivial graphs with $|V|\ge 2$. So, $\frac{\textstyle 2}{\textstyle |V|} \le 1$. By the construction of $\mathsf {f}$, it follows that for each edge $e\in E$, $0 \le \sigma _{\mathsf{d}}(e)\le 1$. Since ${\mathsf {f}}$ is a Fractional Perfect Matching, $\sum _{e\in E} {\mathsf {f}} (e) = \frac{\textstyle |V|}{\textstyle 2}$, which implies that $\sum _{e\in E} \sigma _{\mathsf{d}}(e) = 1$. It follows that $\sigma _{\mathsf{d}}$ is a probability distribution on E.

We establish Conditions (C.1) and (C.2) for $\varvec{\sigma }$ in the characterization of Nash equilibria (Proposition 3.2).

• For Condition (C.1), consider a vertex $v\in V$. Clearly,

  $$\begin{aligned} {{\mathbb {P}}}_{\varvec{\sigma }}(\mathsf{Hit}(v))& = \sum _{e\in \mathsf{Edges_{\varvec{\sigma }}}(v)} \sigma _{\mathsf{d}}(e)\\& = \frac{\textstyle 2}{\textstyle |V|} \sum _{e\in \mathsf{Edges_{\varvec{\sigma }}}(v)} {\mathsf {f}} (e) \quad ({\text {by}}\;{\text {construction}})\\& = \frac{\textstyle 2}{\textstyle |V|} \quad ({\text {since}}\;{\mathsf {f}}\;{\text {is}}\;{\text {a}}\;Fractional\;Perfect\;Matching). \end{aligned}$$

  So, for a vertex $v\in \mathsf{Supp_{\varvec{\sigma }}}(\mathcal{A})$, ${{\mathbb {P}}}_{\varvec{\sigma }}(\mathsf{Hit}(v)) =\min _{v^{\prime }\in V} {{\mathbb {P}}}_{\varvec{\sigma }}(\mathsf{Hit}(v^{\prime }))$. Condition (C.1) follows.

• For Condition (C.2), consider an edge $e=(u,v)\in E$. Clearly,

  $$ \begin{aligned} \mathsf{A_{\varvec{\sigma }}}(e)& = \mathsf{A_{\varvec{\sigma }}}(u) +\mathsf{A_{\varvec{\sigma }}}(v)\\& = \frac{\textstyle 2\nu }{\textstyle |V|} \quad ({\text {since}}\;\varvec{\sigma }\;{\text {is}}\; {\text {Attacker-Symmetric}}\; \&\; {\text {Uniform}}\; \&\; {\text {Fully-Mixed}}). \end{aligned}$$

  So, for an edge $e\in \mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d})$, $\mathsf{A_{\varvec{\sigma }}}(e) =\max _{e^{\prime }\in E} \mathsf{A_{\varvec{\sigma }}}(e^{\prime })$. Condition (C.2) follows.

Hence, $\varvec{\sigma }$ is a Nash equilibrium. We finally prove that $\varvec{\sigma }$ is Defense-Optimal. Clearly, for any edge $e\in \mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d})$, ${\mathsf {U}}_{\mathsf{d}}(\varvec{\sigma })=\mathsf{A_{\varvec{\sigma }}}(e)$, so that $\frac{\textstyle \nu }{\textstyle {\mathsf {U}}_{\mathsf{d}}(\varvec{\sigma })} = \ \frac{\textstyle |V|}{\textstyle 2}$; hence, $\varvec{\sigma }$ is Defense-Optimal. $\square$

We now prove:

Proposition 6.2

A Defense-Optimal graph has a Fractional Perfect Matching.

Proof

Consider a Defense-Optimal Nash equilibrium $\varvec{\sigma }$ for the Defense-Optimal graph G. Proposition 5.6 implies that for each vertex $v\in V$, ${{\mathbb {P}}}_{\varvec{\sigma }}(\mathsf{Hit}(v)) =\frac{\textstyle 2}{\textstyle |V|}$. Define the function $\mathsf {f}:E \rightarrow [0,1]$ with ${\mathsf {f}}(e) := \frac{\textstyle \sigma _{\mathsf{d}}(e) \cdot |V|}{\textstyle 2}$ for each edge $e=(u,v)\in E$.

Clearly, for each edge $e=(u,v)\in E$, ${{\mathbb {P}}}_{\varvec{\sigma }}(\mathsf{Hit}(v)) \ge \sigma _{\mathsf{d}}(e)$, so that ${\mathsf {f}} (e) \le 1$. Furthermore, for each vertex $v\in V$,

$$\begin{aligned} \sum _{e\in \mathsf{Edges_{\varvec{\sigma }}}(v)} {\mathsf {f}}(e)& = \sum _{e\in \mathsf{Edges_{\varvec{\sigma }}}(v)} \frac{\textstyle \sigma _{\mathsf{d}} (e) \cdot |V|}{ \textstyle 2} \quad ({\text {by}}\; {\text {construction}})\\& = \frac{\textstyle |V| }{\textstyle 2} \cdot {{\mathbb {P}}}_{\varvec{\sigma }}(\mathsf{Hit}(v)) \quad ({\text {by}}\; {\text {definition}}\;{\text {of}}\;{{\mathbb {P}}}_{\varvec{\sigma }}(\mathsf{Hit}(v)) )\\& = 1 \quad ({\text {since}}\;{{\mathbb {P}}}_{\varvec{\sigma }}(\mathsf{Hit}(v)) =\frac{\textstyle 2 }{\textstyle |V| },\; {\text {by}}\; {\text {Proposition}}\;5.6). \end{aligned}$$

Hence, ${\mathsf {f}}$ is a Fractional Perfect Matching, as needed. $\square$

Propositions 6.1 and 6.2 together imply:

Theorem 6.3

(Defense-Optimal Graphs) A graph is Defense-Optimal if and only if it has a Fractional Perfect Matching.

6.2 Complexity

Since Fractional Perfect Matching graphs are polynomial time recognizable, and a Fractional Perfect Matching is polynomial time computable for such graphs, Theorem 6.3 immediately implies:

Corollary 6.4

F DEFENSE-OPTIMAL NE is solvable in time Fractional Perfect Matching.

7 Covering Properties

7.1 Covering Profiles

A Covering profile [28, Definition 4.1] is a mixed profile $\varvec{\sigma }$ such that:

(1):

$\mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d})$ is an Edge Cover of G.

(2):

$\mathsf{Supp}_{\varvec{\sigma }}({{\mathcal {A}}})$ is a Vertex Cover of the graph $G(\mathsf{Supp}_{\varvec{\sigma }}(\mathsf{d}))$.

Covering profiles are known to enjoy an interesting property:

Proposition 7.1

(Propositions 4.1, 4.2 & 4.4 [28]) A Nash Equilibrium is a Covering profile, but not vice versa.

Applying Condition (1) in the definition of a Covering profile to Proposition 7.1, we get:

Corollary 7.2

Fix a Nash equilibrium $\varvec{\sigma }$. Then, $| \mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d}) | \ge \beta ^{\prime }(G)$.

7.2 (Generalized) Independent Covering Profiles

We recall:

Definition 7.3

(Definition 4.2 [28]) An Independent Covering profile is an Attacker-Symmetric& Uniform and Defender-Uniform Covering profile $\varvec{\sigma }$ satisfying the additional conditions:

(1):

$\mathsf{Supp}_{\varvec{\sigma }}({{\mathcal {A}}})$ is an Independent Set of G.

(2):

Each vertex in $\mathsf{Supp}_{\varvec{\sigma }}({{\mathcal {A}}})$ is incident to exactly one edge in $\mathsf{Supp}_{\varvec{\sigma }}(\mathsf{d})$.

Note that an Independent Covering profile is Uniform. We define:

Definition 7.4

A Generalized Independent Covering profile is a Covering profile which satisfies conditions (1) and (2) in the definition of an Independent Covering profile.

Note that a Generalized Independent Covering profile is not necessarily Attacker-Symmetric&Uniform or Defender-Uniform. For an Independent Covering profile, we recall:

Proposition 7.5

(Proposition 4.6 [28]) An Independent Covering profile is a Nash equilibrium.

Proposition 7.6

(Proposition 4.7 [28]) For an Independent Covering profile $\varvec{\sigma }$, there is a Matching $M \subseteq \mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d})$ that matches each vertex in $V\backslash \mathsf{Supp_{\varvec{\sigma }}}(\mathcal{A})$ to a vertex in $\mathsf{Supp_{\varvec{\sigma }}}(\mathcal{A})$, with $|M|= |V \backslash \mathsf{Supp_{\varvec{\sigma }}}(\mathcal{A})|$.

Using Propositions 7.5 and 7.6, a Matching Nash equilibrium is introduced as an Independent Covering profile.

For a Generalized Independent Covering profile, we now show:

Lemma 7.7

In a Generalized Independent Covering profile $\varvec{\sigma }$, $|\mathsf{Supp}_{\varvec{\sigma }}({{\mathcal {A}}}) |= |\mathsf{Supp}_{\varvec{\sigma }}(\mathsf{d})|$.

Proof

By Condition (2) in the definition of a Covering profile $\varvec{\sigma }$, $\mathsf{Supp_{\varvec{\sigma }}}(\mathcal{A})$ is a Vertex Cover of $G(\mathsf{Supp}_{\varvec{\sigma }}(\mathsf{d}))$. By Condition (2) in the definition of a Generalized Independent Covering profile, each vertex in $\mathsf{Supp}_{\varvec{\sigma }}({{\mathcal {A}}})$ is incident to exactly one edge in $\mathsf{Supp}_{\varvec{\sigma }}(\mathsf{d})$. It follows that a different vertex from $\mathsf{Supp_{\varvec{\sigma }}}(\mathcal{A})$ is needed to cover each edge of $\mathsf{Supp}_{\varvec{\sigma }}(\mathsf{d})$; so, $|\mathsf{Supp_{\varvec{\sigma }}}(\mathcal{A}) |\ge |\mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d})|$.

Fix now any vertex $u \in \mathsf{Supp_{\varvec{\sigma }}}(\mathcal{A})$. Since $\mathsf{Supp}_{\varvec{\sigma }}(\mathsf{d})$ is an Edge Cover of the graph (Condition (1) in the definition of a Covering profile), there is an edge $(u,v)\in \mathsf{Supp}_{\varvec{\sigma }}(\mathsf{d})$. Since $\mathsf{Supp_{\varvec{\sigma }}}(\mathcal{A})$ is an Independent Set of G (Condition (1) in the definition of a Generalized Independent Covering profile), a different edge from $\mathsf{Supp_{\varvec{\sigma }}}({\mathsf{d}})$ is needed to cover each vertex of $\mathsf{Supp}_{\varvec{\sigma }}(\mathcal{A})$; so, $|\mathsf{Supp_{\varvec{\sigma }}}({\mathsf{d}}) |\ge |\mathsf{Supp_{\varvec{\sigma }}}(\mathcal{A})|$. Hence, the claim follows. $\square$

We note:

Lemma 7.8

In a Generalized Independent Covering profile $\varvec{\sigma }$, $\mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})$ is an Independent Domination Set.

Proof

By Condition (1) in the definition of a Generalized Independent Covering profile, $\mathsf{Supp_{\varvec{\sigma }}}(\mathcal{A})$ is an Independent Set. To show that it is also a Domination Set, consider any vertex $v \in V$. If $v \in \mathsf{Supp_{\varvec{\sigma }}}(\mathcal{A})$, we are done. So, assume that $v\not \in \mathsf{Supp_{\varvec{\sigma }}}(\mathcal{A})$. By Condition (1) of a Covering profile, $\mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d})$ is an Edge Cover of G. So, there is an edge $(u,v) \in \mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d})$. Now, since $\mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})$ is a Vertex Cover of $G(\mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d}))$ (Condition (2) in the definition of a Covering profile), either u or v belong to $\mathsf{Supp_{\varvec{\sigma }}}(\mathcal{A})$. Since, by assumption $v\not \in \mathsf{Supp_{\varvec{\sigma }}}(\mathcal{A})$, it follows that $u\in \mathsf{Supp_{\varvec{\sigma }}}(\mathcal{A})$. Thus, vertex v is “hit” by set $\mathsf{Supp_{\varvec{\sigma }}}(\mathcal{A})$ through its (neighbour) vertex $u\in \mathsf{Supp_{\varvec{\sigma }}}(\mathcal{A})$ and the set $\mathsf{Supp_{\varvec{\sigma }}}(\mathcal{A})$ is a Domination Set. $\square$

We finally prove a necessary condition for the broader class of Generalized Independent Covering profiles.

Proposition 7.9

For a Generalized Independent Covering profile $\varvec{\sigma }$, $|\mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}}) | = |\mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d}) | = \alpha (G) = \beta ^{\prime }(G)$. So, the graph G is König-Egerváry.

Proof

By Lemma 7.7, $|\mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})| = |\mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d})|$. By Condition (1) in the definition of a Covering profile, $\mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d})$ is an Edge Cover of G. So, $| \mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d}) | \ge \beta ^{\prime }(G)$. It follows that $|\mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}}) | = |\mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d}) | \ge \beta ^{\prime }(G)$. Moreover, by Condition (1) in the definition of a Generalized Independent Covering profile, $\mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})$ is an Independent Set of G. So, $| \mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}}) | \le \alpha (G)$. Finally, for any graph $\alpha (G) \le \beta ^{\prime }(G)$ (see Section 2.5). Thus, $|\mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}}) | = |\mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d}) | \le \alpha (G) \le \beta ^{\prime }(G)$. It follows that $|\mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}}) | = |\mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d}) | = \alpha (G) = \beta ^{\prime }(G)$. $\square$

7.3 Properties of Nash Equilibria

We continue with two properties of an arbitrary Nash equilibrium for which the support of the attackers is an Independent Set of G:

Lemma 7.10

Consider a Nash equilibrium $\varvec{\sigma }$ such that $\mathsf{Supp_{\varvec{\sigma }}}(\mathcal{A})$ is an Independent Set. Then, for each edge $e=(u,v) \in \mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d})$, exactly one of u and v is contained in $\mathsf{Supp_{\varvec{\sigma }}}(\mathcal{A})$.

Proof

Since $\mathsf{Supp_{\varvec{\sigma }}}(\mathcal{A})$ is an Independent Set, at most one of u and v is in $\mathsf{Supp_{\varvec{\sigma }}}(\mathcal{A})$. By Proposition 7.1, $\varvec{\sigma }$ is a Covering profile. Since $\mathsf{Supp_{\varvec{\sigma }}}(\mathcal{A})$ is a Vertex Cover of the graph $G(\mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d}))$ (by Condition (2) in the definition of a Covering profile) and $e\in \mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d})$, at least one of u and v is in $\mathsf{Supp_{\varvec{\sigma }}}(\mathcal{A})$. Hence, exactly one of u and v is contained in $\mathsf{Supp_{\varvec{\sigma }}}(\mathcal{A})$. $\square$

Proposition 7.11

Consider a Nash equilibrium $\varvec{\sigma }$ such that $\mathsf{Supp_{\varvec{\sigma }}}(\mathcal{A})$ is an Independent Set. Then, $\mathsf{Supp_{\varvec{\sigma }}}(\mathcal{A})$ is an Expanding Independent Set.

Proof

Assume, by way of contradiction, that $\mathsf{Supp_{\varvec{\sigma }}}(\mathcal{A})$ is not an Expanding Independent Set; that is, the set $V\backslash \mathsf{Supp_{\varvec{\sigma }}}(\mathcal{A})$ is not an Expander. So, there is a set $U \subseteq V\backslash \mathsf{Supp_{\varvec{\sigma }}}(\mathcal{A})$ such that

$$\begin{aligned} |\mathsf{Neigh}_{G}(U )\cap \mathsf{Supp_{\varvec{\sigma }}}(\mathcal{A})|< & {} |U|. \end{aligned}$$

Let $EC = \mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d}) \cap \mathsf{Edges}_{G}(U)$ and $V^{\prime } = \mathsf{Neigh}_{G}(U) \cap \mathsf{Supp_{\varvec{\sigma }}}(\mathcal{A})$. Consider first set $V^{\prime }$. Then,

$$ \begin{aligned}&\sum _{v\in V^{\prime }} {\mathbb {P}}_{\varvec{\sigma }}(\mathsf{Hit}(v))\\&\quad = \sum _{v\in V^{\prime } }\sum _{ (u,v) \in \mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d})} \sigma _{\mathsf{d}} ( u,v) \quad ({\text {by}}\;{\text {the}}\; {\text {definition}}\;{\text {of}}\;{\mathbb {P}}_{\varvec{\sigma }}(\mathsf{Hit}(v)))\\&\quad = \sum _{v\in V^{\prime } }\sum _{\begin{array}{c} (u,v) \in \mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d})\\ u \in U \end{array}} \sigma _{\mathsf{d}}( u,v ) \quad ({\text {since}}\;V^{\prime }\;{\text {is}}\;{\text {an}}\;{\text {Independent}}\;{\text {Set}} \& V^{\prime } = \mathsf{Neigh}_{G}(U ) \cap \mathsf{Supp_{\varvec{\sigma }}}(\mathcal{A}))\\&\quad = \sum _{v\in V^{\prime } }\sum _{ (u,v) \in EC} \sigma _{\mathsf{d}}( u,v ) \quad ({\text {by}}\;{\text {the}}\;{\text {definition}}\;{\text {of}}\;{\text {EC}})\\&\quad = \sum _{(u,v) \in EC } \sigma _{\mathsf{d}}( u,v ). \end{aligned}$$

Consider now set U. Then,

$$\begin{aligned}&\sum _{u\in U} {\mathbb {P}}_{\varvec{\sigma }}(\mathsf{Hit}(u))\\&\quad = \sum _{u\in U } \sum _{ (u,v) \in \mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d})} \sigma _{\mathsf{d}}(u,v )\\&\quad = \sum _{u\in U }\sum _{\begin{array}{c} (u,v) \in \mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d})\\ v \in V^{\prime } \end{array}} \sigma _{\mathsf{d}}( u,v ) \quad ({\text {by}}\;{\text {Lemma}}\;7.10\;{\text { and}}\;{\text {since}}\;(u, v) \in \mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d})) \\&\quad = \sum _{u\in U }\sum _{ (u,v) \in EC} \sigma _{\mathsf{d}}( u,v ) \quad ({\text {by}}\;{\text {the}}\;{\text {definition}}\;{\text {of}}\;{\text {EC}})\\&\quad = \sum _{(u,v) \in EC } \sigma _{\mathsf{d}}(u,v). \end{aligned}$$

It follows that

$$\begin{aligned}&\sum _{(u,v) \in EC } \sigma _{\mathsf{d}}(u,v)\\&\quad = \sum _{u\in U} {\mathbb {P}}_{\varvec{\sigma }}(\mathsf{Hit}(u))\\&\quad = \sum _{v\in V^{\prime }} {\mathbb {P}}_{\varvec{\sigma }}(\mathsf{Hit}(v)) \\&\quad = |V^{\prime }| \cdot \min _{v^{\prime }\in V}{\mathbb {P}}_{\varvec{\sigma }}(\mathsf{Hit}(v^{\prime })) \quad ({\text {by}}\;{\text {Proposition}} \;3.2\;({\text {Condition}}\;\mathsf{(C.1)}), {\text {since}}\;V^{\prime }\subseteq \mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})). \end{aligned}$$

So,

$$\begin{aligned} \sum _{u\in U} {\mathbb {P}}_{\varvec{\sigma }}(\mathsf{Hit}(u)) \ \ = \ \ |V^{\prime }| \cdot \min _{v^{\prime }\in V}{\mathbb {P}}_{\varvec{\sigma }}(\mathsf{Hit}(v^{\prime })) . \end{aligned}$$

Since, by assumption,

$$\begin{aligned} \mathsf{Neigh}_{G}(U) \cap \mathsf{Supp_{\varvec{\sigma }}}(\mathcal{A}) \ \ = \ \ |V^{\prime }| \ \ < \ \ |U|, \end{aligned}$$

it follows that, in the summation $\sum _{u\in U} {\mathbb {P}}_{\varvec{\sigma }}(\mathsf{Hit}(u))$, there exists a vertex $u \in U$, such that

$$\begin{aligned} {\mathbb {P}}_{\varvec{\sigma }}(\mathsf{Hit}(u)) \ \ < \ \ \min _{v^{\prime }\in V}{\mathbb {P}}_{\varvec{\sigma }}(\mathsf{Hit}(v^{\prime })) . \end{aligned}$$

A contradiction to Proposition 3.2 (Condition (C.1)). $\square$

8 Matching Nash Equilibria

A Matching graph is a graph that admits a Matching Nash equilibrium. A characterization of Matching graphs is known:

Proposition 8.1

(Theorem 5.1 [28])(First Characterization of Matching Graphs) A graph G is Matching if and only if it has an Expanding Independent Set.

In Sect. 8.1, we derive an alternative characterization of Matching graphs. In Sect. 8.2, the characterization is used to derive a polynomial time algorithm to decide the existence of and compute a Matching Nash equilibrium (if there is one). The Defense-Ratio of a Matching Nash equilibrium is derived in Sect. 8.3.

8.1 Characterization of Matching Graphs

We show:

Theorem 8.2

(Second Characterization of Matching Graphs) The graph G is Matching if and only if it is König-Egerváry.

Proof

Assume first that $\alpha (G)= \beta ^{\prime }(G)$. Let IS and EC be a Maximum Independent Set and a Minimum Edge Cover, respectively, so that $|IS|=|EC|$. Consider a Uniform and Attacker-Symmetric mixed profile $\varvec{\sigma }$ with $\mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})=IS$ and $\mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d})=EC$. Thus, $|\mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})|=|\mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d})|$. We shall prove that $\varvec{\sigma }$ is an Independent Covering profile.

By construction, $\mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d})$ is an Edge Cover of G and $\mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})$ is an Independent Set of G. Thus, the mixed profile $\varvec{\sigma }$ satisfies Condition (1) for a Covering profile and Condition (1) for an Independent Covering profile. It remains to establish Condition (2) for a Covering profile and Condition (2) for an Independent Covering profile. Since EC is a Minimum Edge Cover, it is a union of vertex-disjoint star graphs. Since $|\mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})|=|\mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d})|$ and $\mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})$ is an Independent Set of G, it follows that $\mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})$ consists of all terminal vertices of the star graphs in $\mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d})$. (Otherwise, if a center vertex of a star graph were contained in IS, then no terminal vertex of the star graph would have been included in IS, implying that $IS<|\mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d})|$.) This implies that both (i) $\mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})$ is a Vertex Cover of the graph $G(\mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d}))$ (Condition (2) for a Covering profile) and (ii) each vertex in $\mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})$ is incident to exactly one edge of $\mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d})$ (Condition (2) for an Independent Covering profile). Hence, $\varvec{\sigma }$ is an Independent Covering profile. Since an Independent Covering profile is a Nash equilibrium (Proposition 7.5), the claim follows.

Assume now that G admits a Matching Nash equilibrium. Then, by Proposition 7.9 and since a Matching Nash equilibrium is a special case of a Generalized Independent Covering profile, it follows that $\alpha (G)= \beta ^{\prime }(G)$. $\square$

Theorems 8.1 and 8.2 imply together a graph-theoretic result of independent interest:

Corollary 8.3

A graph has an Expanding Independent Set if and only if it is König-Egerváry.

8.2 Complexity

The constructive parts of the sufficiency proofs of Proposition 4.12 and Theorem 8.2 yield together the polynomial time algorithm MatchingNE to decide the existence of and compute a Matching Nash equilibrium, if there is one:

Algorithm MatchingNE

Input: A graph $G = \langle V, E \rangle$.

Output: The supports for a Matching Nash equilibrium $\varvec{\sigma }$, or No if such does not exist.

• 1. Choose a Minimum Edge Cover EC.

• 2. Construct an instance $\phi$ of 2SAT with variable set V as follows:

  • (2/a) For each edge $(u,v)\in E$, add the clause $({\bar{u}} \vee {\bar{v}})$ to $\phi$.

  • (2/b) For each edge $(u,v)\in EC$, add the clause $(u \vee v)$ to $\phi$.

  • (2/c) For each multiple-edge star graph of EC with center vertex u, add the clause $({\bar{u}} \vee {\bar{u}})$ to $\phi$.

• 3. Compute a satisfying assignment $\chi$ of $\phi$, or output No if such does not exist.

• 4. Set $IS:=\{u\in V \mid \chi (u)=1\}$.

• 5. Set $\mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d}):= EC$ and $\mathsf{Supp_{\varvec{\sigma }}}(\mathcal{A} ):= IS$.

Theorem 8.4

F MATCHING NE is solvable in time Minimum Edge Cover.

8.3 Defense Ratio

We prove:

Proposition 8.5

The Defense-Ratio of a Matching Nash equilibrium is $\alpha (G)$.

Proof

Fix a Matching Nash equilibrium $\varvec{\sigma }$. Since $\varvec{\sigma }$ is an Independent Covering profile, Condition (1) in the definition of an Independent Covering profile yields that $\mathsf{Supp_{\varvec{\sigma }}}(\mathcal{A})$ is an Independent Set. Thus, by Lemma 7.10, for each edge $e=(u,v) \in \mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d})$, exactly one of the endpoints, say v, of the edge e is included in $\mathsf{Supp_{\varvec{\sigma }}}(\mathcal{A})$; so, $\mathsf{A}_{\varvec{\sigma }}( e) = \mathsf{A}_{\varvec{\sigma }}( v)$. By Proposition 7.9 and since a Matching Nash equilibrium is a special case of a (Generalized) Independent Covering profile,

$$\begin{aligned} |\mathsf{Supp_{\varvec{\sigma }}}({\mathsf{d}})|& = |\mathsf{Supp_{\varvec{\sigma }}}(\mathcal{A})| \ \ = \ \alpha (G) . \end{aligned}$$

Since $\varvec{\sigma }$ is a Nash equilibrium and Attacker-Uniform, it follows that

$$\begin{aligned} {\mathsf {U}}_{\mathsf{d}}(\varvec{\sigma })& = \sum _{e=(u,v)\in E} \sigma _\mathsf{d}(e) \ \ = \ \ \sum _{\mathsf{a}_i\in {{\mathcal {A}}}} \left( \sigma _i(u)+\sigma _i(v) \right) \ \ = \ \ \sum _{\mathsf{a}_i\in {{\mathcal {A}}}} \sigma _{i} (v) \ \ = \ \ \frac{\textstyle \nu }{\textstyle |\mathsf{Supp_{\varvec{\sigma }}}(\mathcal{A})|} . \end{aligned}$$

Thus,

$$\begin{aligned} {\mathsf {U}}_{\mathsf{d}}({\varvec{\sigma }})& = \frac{\textstyle \nu }{\textstyle |\mathsf{Supp_{\varvec{\sigma }}}(\mathcal{A})|} \ \ = \ \ \frac{\textstyle \nu }{\textstyle \alpha (G) } . \end{aligned}$$

Hence, $\frac{\textstyle \nu }{\textstyle {\mathsf {U}}_{\mathsf{d}}({\varvec{\sigma }}) } = \alpha (G)$, as needed. $\square$

Proposition 8.5 immediately implies:

Corollary 8.6

Assume that G is Matching. Then, $\mathsf{PoD}_G\ge \alpha (G)$.

9 Perfect-Matching Nash Equilibria

A Perfect-Matching Nash equilibrium is a Matching Nash equilibrium $\varvec{\sigma }$ such that $\mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d})$ is a Perfect Matching of G; so, $|\mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d}) | = \frac{\textstyle |V|}{\textstyle 2}$. A Perfect-Matching graph admits a Perfect-Matching Nash equilibrium.

In Sect. 9.1, we derive structural properties of Perfect-Matching Nash equilibria and a characterization of Perfect-Matching graphs. In Sect. 9.2, we use the characterization to derive a polynomial time algorithm to decide the existence of and compute a Perfect-Matching Nash equilibrium, if there is one. The Defense-Ratio of a Perfect-Matching Nash equilibrium is derived in Sect. 9.3.

9.1 Characterization of Perfect-Matching Graphs

We start with a preliminary graph-theoretic property of a Perfect-Matching Nash equilibrium $\varvec{\sigma }$. By definition, $| \mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d}) |= \frac{\textstyle |V|}{\textstyle 2}$. Since a Perfect-Matching Nash equilibrium is also a Matching Nash equilibrium, and since a Matching Nash equilibrium is a special case of a Generalized Independent Covering profile, Proposition 7.9 yields that $|\mathsf{Supp_{\varvec{\sigma }}}({\mathsf{d}})| = |\mathsf{Supp_{\varvec{\sigma }}}(\mathcal{A})|$. So, $|\mathsf{Supp_{\varvec{\sigma }}}(\mathcal{A })|= \frac{\textstyle |V|}{\textstyle 2}$:

Proposition 9.1

For a Perfect-Matching Nash equilibrium $\varvec{\sigma }$, $|\mathsf{Supp_{\varvec{\sigma }}}(\mathcal{A })|= \frac{\textstyle |V|}{\textstyle 2}$.

We are now ready to show:

Theorem 9.2

(Perfect-Matching Graphs) A graph G is Perfect-Matching if and only if G has a Perfect Matching and $\alpha (G) =\frac{\textstyle |V|}{\textstyle 2}$.

Proof

Assume first that G has a Perfect Matching and $\alpha (G)=\frac{\textstyle |V|}{\textstyle 2}$. Since for any graph G, $\alpha (G) \le \beta ^{\prime }(G)$ and $\beta ^{\prime }(G)\ge \frac{\textstyle |V|}{\textstyle 2}$, it follows that $\alpha (G)= \beta ^{\prime }(G)$. So, by Proposition 8.2, the graph contains a Matching Nash equilibrium $\varvec{\sigma }$. Since a Matching Nash equilibrium is a special case of a Generalized Independent Covering profile, Proposition 7.9 yields that $|\mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}}) | = |\mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d}) | = \alpha (G) = \beta ^{\prime }(G)$. Since $\alpha (G)=\frac{\textstyle |V|}{\textstyle 2}$, it follows that $|\mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d}) | = \frac{\textstyle |V|}{\textstyle 2}$; so $\varvec{\sigma }$ is a Perfect-Matching Nash equilibrium.

Assume now that G admits a Perfect-Matching Nash equilibrium $\varvec{\sigma }$. Since a Perfect-Matching Nash equilibrium is a special case of a Matching Nash equilibrium and since a Matching Nash equilibrium is a special case of a Generalized Independent Covering profile, Proposition 7.9 yields that $|\mathsf{Supp_{\varvec{\sigma }}}(\mathcal{A})|=|\mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d}) | = \alpha (G) = \beta ^{\prime }(G)$. Since in a Perfect-Matching Nash equilibrium, $| \mathsf{Supp_{\varvec{\sigma }}}({\mathsf{d}}) | = \frac{\textstyle |V|}{\textstyle 2}$, it follows that $\alpha (G)= \beta ^{\prime }(G) = \frac{\textstyle |V|}{\textstyle 2}$. $\square$

Note that there is a graph G with a Perfect Matching and with $\alpha (G) = 1 \ne \frac{\textstyle |V|}{\textstyle 2}$; this is the clique graph. By Theorem 9.2, this implies that the class of Perfect-Matching graphs is strictly contained in the class of graphs with a Perfect Matching. Since a Perfect Matching is a special case of a Fractional Perfect Matching, this implies that the class of Perfect-Matching graphs is strictly contained in the class of graphs with a Fractional Perfect Matching. Hence, by Theorem 6.3, the class of Perfect-Matching graphs is strictly contained in the class of Defense-Optimal graphs. We provide a particular example to demonstrate that the inclusion is strict:

Proposition 9.3

$K_3$ is Defense-Optimal but not Perfect-Matching.

Proof

By Proposition 5.5, $K_3$ is Defense-Optimal. Since $K_3$ does not have a Perfect Matching, Theorem 9.2 implies that $K_3$ is not Perfect-Matching. $\square$

Regarding Defense-Optimal and Matching and Perfect-Matching graphs, we show:

Proposition 9.4

(Defense-Optimal & Matching = Perfect-Matching) A graph is Defense-Optimal and Matching if and only if it is Perfect-Matching.

Proof

Assume, by way of contradiction, that there is a (i) Matching and (ii) Fractional Perfect Matching graph (Theorem 6.3), which does not have a Perfect-Matching Nash equilibrium. Since for any graph $\beta ^{\prime }(G)\ge \frac{\textstyle |V|}{\textstyle 2}$, property (i) and Theorem 8.2 imply that $\alpha (G)\ge \frac{\textstyle |V|}{\textstyle 2}$. Since the graph is not a Perfect-Matching graph, by Gallai’s Theorem, $\beta ^{\prime }(G) > \frac{\textstyle |V|}{\textstyle 2}$ so that the graph does not have a Perfect Matching. Consider an Independent Covering (i.e. a Matching Nash Equilibrium, by Proposition 7.5) $\varvec{\sigma }$, and take the set $I = \mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})$. Recall that by Condition (1) in the definition of an Independent Covering profile, the set I is an Independent Set. Furthermore, since an Independent Covering is a special case of a Generalized Independent Covering profile, Proposition 7.9 yields that $|\mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}}) | = |\mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d}) | = \alpha (G) = \beta ^{\prime }(G)$. So, $|\mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}}) | > \frac{\textstyle |V|}{\textstyle 2}$.

Now consider a Fractional Perfect Matching $\mathsf{f}$ of G. Then, for any vertex $v\in V$, it holds that $\sum _{e\in \mathsf{Edges}_{G}(v)} \mathsf{f} (e) =1$. Then,

$$\begin{aligned}&\sum _{v\in I } \sum _{e=(u,v) \in \mathsf{Edges}_G(v)} \mathsf{f}(e)\\&\quad = \sum _{v\in I } \sum _{e=(u,v)\in \mathsf{Edges}_G(v), \; u \in V\backslash I } \mathsf{f}(e) \quad ({\text {since}}\;I\;{\text {is}}\;{\text {an}}\;{\text {Independent}}\;{\text {Set}}) \\&\quad = 1 \cdot |I| \quad ({\text {since}}\;\mathsf{f}\;{\text {is}}\;{\text {a}}\; {\text {Fractional}}\;{\text {Perfect}}\;{\text {Maching}}) \\&\quad > \frac{\textstyle |V|}{\textstyle 2} . \end{aligned}$$

Consider now a vertex $u \in V \backslash I$. Then,

$$\begin{aligned}&\sum _{u \in V\backslash I } \sum _{e= (u,v) \in \mathsf{Edges}_{G}(u)} \mathsf{f} (e) \\&\quad \ge \sum _{u \in V\backslash I } \sum _{e=(u,v)\in \mathsf{Edges}_{G}(u) \cap \mathsf{Edges}_{G}(I) } \mathsf{f}(e) \\&\quad = \sum _{v\in I } \sum _{e=(u,v)\in \mathsf{Edges}_{G}(v)} \mathsf{f}(e) \quad ({\text {since}}\;I\;{\text {is}}\;{\text {an}}\;{\text {Independent}}\;{\text {Set}}\;{\text {and}}\; \mathsf{Neigh}_{G}(V \backslash I) = I)\\&\quad = 1 \cdot |I| \quad ({\text {since}}\;\mathsf{f}\;{\text {is}}\;{\text {a}}\; {\text {Fractional}}\;{\text {Perfect}}\;{\text {Maching}}) \\&\quad > \frac{\textstyle |V|}{\textstyle 2}. \end{aligned}$$

So, $\sum _{u \in V } \! \sum _{e \in \mathsf{Edges}_{G}(u)} \mathsf{f}(e) \! >\! | V |$. A contradiction to that $\mathsf{f}$ is a Fractional Perfect Matching. $\square$

We proceed to explore the relation between Matching and Perfect-Matching Nash equilibria:

Proposition 9.5

In a Perfect-Matching graph G, each Matching Nash equilibrium is Perfect-Matching.

Proof

Since G is Perfect-Matching, we have that $\alpha (G) = \frac{\textstyle |V|}{\textstyle 2}$ (Theorem 9.2). Since each Perfect-Matching Nash equilibrium is also a Matching Nash equilibrium, it follows that $\alpha (G) =\beta ^{\prime }(G)$ (Theorem 8.2). Thus, $\alpha (G) = \beta ^{\prime }(G) = \frac{\textstyle |V|}{\textstyle 2}$. Assume, by way of contradiction, that G has a Matching Nash equilibrium $\varvec{\sigma }$ that is not Perfect-Matching. Since $\varvec{\sigma }$ is Matching, the support of the defender $\mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d})$ is an Edge Cover (Condition (1) in the definition of a Covering profile). Since $\varvec{\sigma }$ is not a Perfect-Matching Nash equilibrium, the Edge Cover $\mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d})$ is not a Perfect Matching. Since it is an Edge Cover, it follows that $|\mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d})|> \frac{\textstyle |V|}{\textstyle 2}$. Since a Matching Nash equilibrium is a special case of a Generalized Independent Covering profile, Proposition 7.9 yields that the Edge Cover $\mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d})$ is a Minimum Edge Cover. Thus, $|\mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d}) | = \beta ^{\prime }(G) > \frac{\textstyle |V|}{\textstyle 2}$. A contradiction. $\square$

On the other hand, we show:

Proposition 9.6

For a graph G with a Matching Nash equilibrium but without a Perfect-Matching Nash equilibrium, $\alpha (G) > \frac{\textstyle |V|}{\textstyle 2}$.

Proof

Since G has a Matching Nash equilibrium $\varvec{\sigma }$ which is a special case of a Generalized Independent Covering profile, Proposition 7.9 yields that $|\mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}}) | = |\mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d}) | = \alpha (G) = \beta ^{\prime }(G)$. Since for any graph G, $\beta ^{\prime }(G)\ge \frac{\textstyle |V|}{\textstyle 2}$, it follows that $\alpha (G) = \beta ^{\prime }(G) \ge \frac{\textstyle |V|}{\textstyle 2}$. Since the graph is not Perfect-Matching, it follows that $\beta ^{\prime }(G) > \frac{\textstyle |V|}{\textstyle 2}$. Recall that by Condition (1) in the definition of a Independent Covering profile, the set $\mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})$ is an Independent Set. So, Proposition  7.9 now yields that $|\mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}}) | = |\mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d}) | = \alpha (G) = \beta ^{\prime }(G) > \frac{\textstyle |V|}{\textstyle 2}$. The claim follows. $\square$

9.2 Complexity

The constructive parts of the sufficiency proofs of Proposition 4.14 and Theorem 9.2 yield together the polynomial time algorithm PerfectMatchingNE to decide the existence of and compute a Perfect-Matching Nash equilibrium. Since 2SAT can be solved in linear time [1], we obtain:

Algorithm PerfectMatchingNE

Input: A graph $G = \langle V, E \rangle$.

Output: The supports in a Perfect-Matching Nash equilibrium $\varvec{\sigma }$, or No if such does not exist.

• 1. Choose a Perfect Matching M, or output No if such does not exist.

• 2. Construct an instance $\phi$ of 2SAT as follows:

  • (2/a) For each edge $(u,v)\in E$, add the clause $({\bar{u}} \vee {\bar{v}})$ to $\phi$.

  • (2/b) For each edge $(u,v)\in M$, add the clause $(u \vee v)$ to $\phi$.

• 3. Compute a satisfying assignment $\chi$ of $\phi$, or output No if such does not exist.

• 4. Set $IS=\{u \mid \chi (u)=1\}$.

• 5. Set $\mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d}):= M$ and $\mathsf{Supp_{\varvec{\sigma }}}(\mathcal{A}):= IS$.

Theorem 9.7

F PERFECT-MATCHING NE is solvable in time Perfect Matching.

9.3 Defense Ratio

Recall that a Perfect-Matching Nash equilibrium is a Matching Nash equilibrium; so, Proposition 8.5, together with Theorem 9.2 imply that $\alpha (G)=\frac{\textstyle |V|}{\textstyle 2}$. Hence, we have:

Theorem 9.8

The Defense-Ratio of a Perfect-Matching Nash equilibrium is $\frac{\textstyle |V|}{\textstyle 2}$.

Theorem 9.8 immediately implies:

Proposition 9.9

Assume that G is Perfect-Matching. Then, $\mathsf{PoD}_G \ge \frac{\textstyle |V|}{\textstyle 2}$.

Proposition 9.9 implies that a Perfect-Matching graph cannot improve over an arbitrary graph with respect to Price of Defense.

10 Attacker-Symmetric&Uniform Nash Equilibria

An Attacker-Symmetric&Uniform Nash equilibrium is an Attacker-Symmetric&Uniform profile that is a Nash equilibrium. (Recall that a (Perfect-)Matching Nash equilibrium is Attacker-Symmetric&Uniform (but not vice versa).) A graph is Attacker-Symmetric&Uniform if it admits an Attacker-Symmetric&Uniform Nash equilibrium.

In Sect. 10.1, we provide a characterization of Attacker-Symmetric&Uniform graphs. In Sect. 10.2, we use the characterization to derive a polynomial time algorithm to decide the existence of and compute an Attacker-Symmetric&Uniform Nash equilibrium, if there is one. The Defense-Ratio of an Attacker-Symmetric&Uniform Nash equilibrium is derived in Sect. 10.3.

10.1 Characterization of Attacker-Symmetric&Uniform Graphs

We start with a conditional necessary condition for the support of the attackers in an Attacker-Symmetric&Uniform Nash equilibrium:

Proposition 10.1

Consider an Attacker-Symmetric&Uniform Nash equilibrium $\varvec{\sigma }$ such that $\mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})$ is not an Independent Set. Then, $\mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})=V$.

Proof

Since $\mathsf{Supp}_{\varvec{\sigma }}(\mathcal{A})$ is not an Independent Set, there are vertices $u,v \in \mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})$ such that $(u,v)\in E$. So,

$$ \begin{aligned} \mathsf{A}_{\varvec{\sigma }}(e)& = \sum _{\mathsf{a}_i\in {{\mathcal {A}}}} \sigma _i(u)+\sum _{\mathsf{a}_i\in {{\mathcal {A}}}} \sigma _i(v) \\& = \frac{\textstyle \nu }{\textstyle |\mathsf{Supp}_{\varvec{\sigma }}(\mathcal{A})| } + \frac{\textstyle \nu }{\textstyle |\mathsf{Supp}_{\varvec{\sigma }}(\mathcal{A})| } \quad ({\text {since}}\;\varvec{\sigma }\;{\text {is}}\;{\text {Attacker-Symmetric}} \& {\text {Uniform}})\\& = \frac{\textstyle 2\nu }{\textstyle |\mathsf{Supp}_{\varvec{\sigma }}(\mathcal{A})| }. \end{aligned}$$

Assume, by way of contradiction, that there is a vertex $u^{\prime } \not \in \mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})$. Recall that $\varvec{\sigma }$ is a Covering profile so that $\mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d})$ is an Edge Cover. Hence, there is an edge $e^{\prime }=(u^{\prime },v^{\prime })\in \mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d})$. Since $e^{\prime }\in \mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d})$, Condition (C.2) in the characterization of Nash equilibria (Theorem 3.2) implies that $\mathsf{A_{\varvec{\sigma }}}(e^{\prime })\ge \mathsf{A_{\varvec{\sigma }}}(e)$. Clearly,

$$ \begin{aligned} \mathsf{A}_{\varvec{\sigma }}(e^{\prime })& = \mathsf{A}_{\varvec{\sigma }}(u^{\prime })+\mathsf{A}_{\varvec{\sigma }}(v^{\prime }) \\& = \mathsf{A}_{\varvec{\sigma }}(v^{\prime }) \quad ({\text {since}}\;u^{\prime }\not \in \mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})) \\& = \sum _{\mathsf{a}_i\in {{\mathcal {A}}}} \sigma _i(v^{\prime }) \\& = \frac{\textstyle \nu }{\textstyle |\mathsf{Supp}_{\varvec{\sigma }}(\mathcal{A})| } \quad ({\text {since}}\;\varvec{\sigma }\;{\text {is}}\;{\text {Attacker-Symmetric}} \& {\text {Uniform}})\\< & {} \mathsf{A}_{\varvec{\sigma }}(e ), \end{aligned}$$

a contradiction. $\square$

We show:

Proposition 10.2

An Attacker-Symmetric&Uniform graph G is either Defense-Optimal or Matching.

Proof

By assumption, the graph G has an Attacker-Symmetric&Uniform Nash equilibrium $\varvec{\sigma }$. We proceed by case analysis on whether or not $\mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})$ is an Independent Set.

(1):

Assume first that $\mathsf{Supp}_{\varvec{\sigma }}(\mathcal{A})$ is not an Independent Set. By Proposition  10.1, it follows that $\mathsf{Supp}_{\varvec{\sigma }}(\mathcal{A}) =V$. Hence, by Condition (C.1) in the characterization of Nash equilibria (Proposition 3.2), for any vertex any $v\in \mathsf{Supp}_{\varvec{\sigma }}(\mathcal{A})$,

$$\begin{aligned} {\mathbb {P}}_{\varvec{\sigma }}(\mathsf{Hit}(v))& = \min _{v^{\prime }\in V} {\mathbb {P}}_{\varvec{\sigma }} (\mathsf{Hit}(v^{\prime })) , \end{aligned}$$

while by Lemma 3.1, $\sum _{v\in V}{{\mathbb {P}}}_{\varvec{\sigma }}(\mathsf{Hit}(v))=2$. It follows that for each vertex $v\in V$, ${{\mathbb {P}}}_{\varvec{\sigma }}(\mathsf{Hit}(v)) =\frac{\textstyle 2}{\textstyle |V|}$. Thus, Proposition 5.3 implies that $\varvec{\sigma }$ is Defense-Optimal and so is G.

(2):

Assume now that $\mathsf{Supp}_{\varvec{\sigma }}(\mathcal{A})$ is an Independent Set. By Proposition 7.11, this implies that $\mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})$ is an Expanding Independent Set. Thus, by Theorem 8.1, G is Matching. $\square$

We are now ready to show:

Theorem 10.3

(Characterization of Attacker-Symmetric&Uniform Graphs) A graph G is Attacker-Symmetric&Uniform if and only if either (1) G has a Fractional Perfect Matching, or (2) $\alpha (G)=\beta ^{\prime }(G)$.

Proof

Assume that G is Attacker-Symmetric&Uniform. So, by Proposition 10.2, (i) G is Defense-Optimal, or (ii) G is Matching. In case (i), by Proposition 6.2, G has a Fractional Perfect Matching and (1) holds. In case (ii), by Theorem 8.2, $\alpha (G) =\beta ^{\prime }(G)$ and (2) holds.

Assume now that either (1) or (2) holds. When (1) holds, Proposition 6.1 implies that G admits an Attacker-Symmetric&Uniform (and Fully-Mixed) Nash equilibrium. When (2) holds, Theorem 8.2 implies that G admits a Matching Nash equilibrium, which is Attacker-Symmetric&Uniform. $\square$

10.2 Complexity

We now establish that both Conditions (1) and (2) in the characterization of Attacker-Symmetric&Unform Nash equilbria (Theorem 10.3) are polynomial time decidable:

• The sufficiency proof for Condition (1) is constructive, establishing that an Attacker-Symmetric&Uniform Nash equilibrium is computable from a Fractional Perfect Matching, when there is one, in polynomial time. Since graphs with a Fractional Perfect Matching are polynomial time recognizable, it follows that Condition (1) is polynomial time decidable.

• The sufficiency proof for Condition (2) is constructive, establishing that a Matching Nash equilibrium is polynomial time computable from a Maximum Independent set of size $\beta ^{\prime }(G)$. Since graphs with $\alpha (G)=\beta ^{\prime }(G)$ are polynomial time recognizable, and a Maximum Independent set in such graphs is polynomial time computable (Proposition 4.12), it follows that a Matching Nash equilibrium is polynomial time computable. Since a Matching Nash equilibrium is Attacker-Symmetric&Uniform, we get a polynomial time algorithm to compute an Attacker-Symmetric&Uniform Nash equilibrium when it holds that $\alpha (G)=\beta ^{\prime }(G)$.

Hence, we obtain:

Theorem 10.4

F ATTACKER-SYMMETRIC&UNIFORM NE is solvable in time $\max \{ \mathsf{Fractional \; Perfect \; Matching}, \mathsf{Minimum \; Edge \; Cover} \}$.

10.3 Defense-Ratio

We show:

Theorem 10.5

The Defense-Ratio of an Attacker-Symmetric&Uniform Nash equilibrium $\varvec{\sigma }$ is either $\frac{\textstyle |V|}{\textstyle 2}$ or at most $\alpha (G)$.

Proof

We proceed by case analysis on whether or not $\mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})$ is an Independent Set. Assume first that $\mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})$ is not an Independent Set. For this case, we shall prove that the Defense-Ratio is $\frac{\textstyle |V|}{\textstyle 2}$. By Proposition 10.1, $\mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})= V$. Since $\varvec{\sigma }$ is Attacker-Symmetric&Uni- form, it follows that for each vertex $v \in \mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})$,

$$\begin{aligned} \mathsf{A_{\varvec{\sigma }}}(v)& = \sum _{\mathsf{a}_i\in {{\mathcal {A}}}} \frac{\textstyle 1}{\textstyle |\mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})|} \ \ = \ \ \frac{\textstyle \nu }{\textstyle |V|}. \end{aligned}$$

Since $\varvec{\sigma }$ is a Nash equilibrium, it holds that ${\mathsf {U}}_ {\mathsf{d}}(\varvec{\sigma })=\mathsf{A_{\varvec{\sigma }}}(e)$ for any arbitrary edge $e\in \mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d})$. Since $\mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})=V$ and $\varvec{\sigma }$ is Attacker-Symmetric&Uniform, it follows that ${\mathsf {U}}_{\mathsf{d}}({ \varvec{\sigma }})= \frac{\textstyle 2\nu }{\textstyle |V|}$. So,

$$\begin{aligned} \mathsf{DR}_{\varvec{\sigma }}& = \frac{\textstyle \nu }{\textstyle \frac{\textstyle 2\nu }{\textstyle |V|}} \ \ = \ \ \frac{\textstyle |V|}{\textstyle 2}, \end{aligned}$$

as needed.

Assume now that $\mathsf{Supp}(\mathcal{A})$ is an Independent Set. Thus, $|\mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})|\le \alpha (G)$. Since $\varvec{\sigma }$ is a Nash equilibrium, by the definition of a Nash equilibrium, for any edge $e=(u,v) \in \mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d})$,

$$\begin{aligned} {\mathsf {U}}_{\mathsf{d}}(\varvec{\sigma })& = {\mathsf {U}}_{\mathsf{d}}( e, \varvec{\sigma }_{- \mathsf{d}} ) \ \ = \ \ \sum _{\mathsf{a}_ i \in \mathcal{A}} \left( \sigma _i(u) + \sigma _i(v) \right) \ \ = \ \ \mathsf{A_{\varvec{\sigma }}}(u)+ \mathsf{A_{\varvec{\sigma }}}(v) \ \ =\ \ \mathsf{A_{\varvec{\sigma }}}(e). \end{aligned}$$

Since $\varvec{\sigma }$ is Attacker-Symmetric&Uniform, it follows that

$$\begin{aligned} {\mathsf {U}}_{ \mathsf{d}}(\varvec{\sigma })& = \sum _{\mathsf{a}_i\in {{\mathcal {A}}}} \frac{\textstyle 1}{\textstyle |\mathsf{Supp_{\varvec{\sigma }}}(\mathcal{A})|}\ \ = \ \ \frac{\textstyle \nu }{\textstyle |\mathsf{Supp_{\varvec{\sigma }}}(\mathcal{A})|} \ \ \ge \ \ \frac{\textstyle \nu }{\textstyle \alpha (G)}. \end{aligned}$$

So, it follows that $\mathsf{DR}_{\varvec{\sigma }}\le \alpha (G)$, as needed. $\square$

Theorem 10.5 immediately implies:

Proposition 10.6

Assume that G is Attacker-Symmetric&Uniform. Then, $\mathsf{PoD}_G \ge \max \left\{ \frac{\textstyle |V|}{\textstyle 2}, \right.$ $\lambda \cdot \alpha (G) \bigg \}$, $0\le \lambda \le 1$.

Proposition 10.6 implies that an Attacker-Symmetric&Uniform graph may be worse than an arbitrary graph with respect to the Price of Defense.

11 Defender-Uniform Nash Equilibria

A Defender-Uniform Nash equilibrium is a Defender-Uniform profile that is a Nash equilibrium. A graph is Defender-Uniform if it admits a Defender-Uniform Nash equilibrium.

In Sect. 11.1, a characterization of Defender-Uniform graphs is derived. In Sect. 11.2, we use the characterization to establish the $\mathcal{NP}$-hardness of recognizing a Defender-Uniform graph. The Defense-Ratio of a Defender-Uniform Nash equilibrium is derived in Sect. 11.3.

11.1 Characterization of Defender-Uniform Graphs

We show:

Theorem 11.1

(Characterization of Defender-Uniform Graphs) A graph G is Defender-Uniform if and only if there are non-empty sets $V^{\prime } \subseteq V$, $E^{\prime }\subseteq E$, and an integer $r\ge 1$ such that the following conditions hold:

• (1/a) For each vertex $v\in V^{\prime }$, $\mathsf{d}_{G(E^{\prime })}(v)=r$.

• (1/b) For each vertex $v\in V\backslash V^{\prime }$, $\mathsf{d}_{G(E^{\prime })}(v)\ge r$.

• (2) $V^{\prime }$ is partitionable into disjoint sets $V^{\prime }_{i}$ and $V^{\prime }_{r}$, with $V^{\prime }_{i} \cup V^{\prime }_ r=V^{\prime }$, and $E^{\prime }$ is partitionable into disjoint sets $E^{\prime }_{i}= \mathsf{Edges}_{G}(V^{\prime }_i\cup (V\backslash V^{\prime }))\cap E^{\prime }$ and $E^{\prime }_{r} = \mathsf{Edges}_{G} (V^{\prime }_r) \cap E^{\prime }$, with $E^{\prime }_{i} \cup E^{\prime }_ r= E^{\prime }$, such that:

  • (2/a) The set $V^{\prime }_{i}$ is an Independent set of G.

  • (2/b) The graph $\left\langle V^{\prime }_{r}, E^{\prime }_r \right\rangle$ is r-regular.

  • (2/c) The set $V\backslash V^{\prime }$ is an Independent set of $G(E^{\prime } )$ and the graph $\left\langle V^{\prime }_{i}\cup (V\backslash V^{\prime }), E^{\prime }_i \right\rangle$ is $(V^{\prime }_{i}, V \backslash V^{\prime } )$-bipartite.

Fig. 5

An illustration of the characterization of a Defender-Uniform Nash equilibrium for a graph G. The edges in $E^{\prime }$ are shown with dark lines; the remaining edges are shown with either dotted lines or a shadow in the corresponding subgraphs of G

An illustration of a Defender-Uniform graph appears in Fig. 5. The proof of the Theorem follows from the following two lemmas:

Lemma 11.2

Consider sets $V^{\prime } \subseteq V$ and $E^{\prime }\subseteq E$ with $G(E^{\prime }) = \langle V, E^{\prime }\rangle$, and an integer $r\ge 1$ such that Conditions (1) and (2) of Theorem 11.1hold. Then, G is Defender-Uniform and for a Defender Uniform Nash equilibrium $\varvec{\sigma }$, ${\mathsf {U}}_{\mathsf{d}} ({\varvec{\sigma }} ) = \frac{ \textstyle \nu }{\textstyle |V^{\prime }_i|+\frac{\textstyle |V^{\prime }_r|}{\textstyle 2}}$.

Proof

Construct a Defender-Uniform, Attacker-Symmetric mixed profile $\varvec{\sigma }$ with $\mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})=V^{\prime }$ and $\mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d})=E^{\prime }$ as follows. For each vertex player $\mathsf{a}_k\in {{\mathcal {A}}}$, set

$$\begin{aligned} \sigma _{k}(v):& = \left\{ \begin{array}{ll} \frac{\textstyle 2}{\textstyle 2 |V^{\prime }_i|+|V^{\prime }_r|}, &{} {\text {if}}\; v \in V^{\prime }_{i} \\ \frac{\textstyle 1}{\textstyle 2 |V^{\prime }_i|+|V^{\prime }_r|}, &{} {\text {if}}\; v \in V^{\prime }_{r} \\ 0, &{} \text { otherwise } \end{array} \right. . \end{aligned}$$

Note that for each vertex player $\mathsf{a}_k \in \mathcal{A}$, $\sum _{v\in \mathsf{Supp_{\varvec{\sigma }}}(k)} \sigma _{k}(v) = 1$. So, $\sigma _k$ is a probability distribution and $\varvec{\sigma }$ is a mixed profile.

To prove that $\varvec{\sigma }$ is a Nash equilibrium, we shall prove that $\varvec{\sigma }$ satisfies Conditions (C.1) and (C.2) in the characterization of a Nash equilibrium (Proposition 3.2). For Condition (C.1), note that for a vertex v,

$$\begin{aligned}&{\mathbb {P}}_{\varvec{\sigma }}(\mathsf{Hit}(v))\\&\quad = \frac{\textstyle | \mathsf{Edges}_{\varvec{\sigma }}(v)|}{ \textstyle |\mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d})|} \quad ({\text {since}}\; \varvec{\sigma }\;{\text {is}}\; {\text {Defender-Uniform}})\\&\quad = \frac{\textstyle \mathsf{d}_{G(\mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d}))}(v) }{\textstyle |E^{\prime }|} \quad ({\text {since}}\mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d}) =E^{\prime })\\&\quad = \left\{ \begin{array}{ll} = \frac{\textstyle r}{\textstyle |E^{\prime }|}, &{} {\text {if}}\; v\in \mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}}) \nonumber \\ \ge \frac{\textstyle r }{\textstyle |E^{\prime }|}, &{} \text { otherwise } \\ \end{array} \right. \quad ({\text {by}}\;{\text {Conditions}}\, \mathsf{(1/a)}\; {\text {and}}\; \mathsf{(1/b)},\; {\text {since}}\,\mathsf{Supp_{\varvec{\sigma }}}({{{\mathcal {A}}}}) =V^{\prime }). \end{aligned}$$

It follows that for each vertex $v\in \mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})$, ${\mathbb {P}}_{\varvec{\sigma }}(\mathsf{Hit}(v)) = \min _{v^{\prime }\in V}{\mathbb {P}}_{\varvec{\sigma }}(\mathsf{Hit}(v^{\prime }))$, and Condition (C.1) follows.

We continue with Condition (C.2). We first calculate $\mathsf{A_{\varvec{\sigma }}}(e)$ for an arbitrary edge $e=(u,v)\in E$. Note that $\mathsf{A}_{\varvec{\sigma }}(e) = \sum _{\mathsf{a}_k \in {{\mathcal {A}}}} \left( \sigma _{k}(u)+\sigma _{k}(v) \right)$, for an arbitrary edge $e= (u,v) \in \mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d})$. Note that by Condition (2/a), it is not possible that both $u,v \in V^{\prime }_i$. Since $\varvec{\sigma }$ is Attacker-Symmetric, we get that

$$\begin{aligned}&\mathsf{A}_{\varvec{\sigma }}(e)\\&\quad = \left\{ \begin{array}{ll} \sum _{\mathsf{a}_k \in {{\mathcal {A}}}} \left( \frac{\textstyle 1}{\textstyle 2 |V^{\prime }_i|+|V^{\prime }_r|} + \frac{\textstyle 1 }{\textstyle 2 |V^{\prime }_i|+|V^{\prime }_r|} \right) =\ \ \frac{\textstyle 2\nu }{\textstyle 2 |V^{\prime }_i|+|V^{\prime }_r|}, &{} {\text {if}}\;u, v \in V^{\prime }_r \\ \sum _{\mathsf{a}_k \in {{\mathcal {A}}}} \left( \frac{\textstyle 2}{\textstyle 2 |V^{\prime }_i|+|V^{\prime }_r|} +0\right) \ \ = \ \ \frac{\textstyle 2\nu }{\textstyle 2 |V^{\prime }_i|+|V^{\prime }_r|}, &{}{\text {if}}\;u\in V^{\prime }_i\;{\text {and}}\;v \in V\backslash V^{\prime } \\ \sum _{\mathsf{a}_k \in {{\mathcal {A}}}} \left( \frac{\textstyle 1}{\textstyle 2 |V^{\prime }_i|+|V^{\prime }_r|} +0\right) \ \ = \ \ \frac{\textstyle \nu }{\textstyle 2 |V^{\prime }_i|+|V^{\prime }_r|} , &{}{\text {if}}\;u \in V^{\prime }_r\;{\text {and}}\;v \in V\backslash V^{\prime } \\ \sum _{\mathsf{a}_k \in {{\mathcal {A}}}} \left( 0 + 0 \right) \ \ = \ \ 0, &{}{\text {if}}\;u,v \in V \backslash V^{\prime } \end{array}\right. . \end{aligned}$$

It follows that

$$\begin{aligned} \max _{e^{\prime }\in E} \mathsf{A}_{\varvec{\sigma }}(e^{\prime })& = \frac{\textstyle 2\nu }{\textstyle 2 |V^{\prime }_i|+|V^{\prime }_r|} . \end{aligned}$$

Consider now an arbitrary edge $e=(u,v)\in \mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d})$, and recall that $\mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d})=E^{\prime }$. To prove that $\mathsf{A_{\varvec{\sigma }}}(e) =\max _{e^{\prime }\in E} \mathsf{A}_{\varvec{\sigma }}(e^{\prime })$, it suffices to prove that cases with $u \in V^{\prime }_r$, $v \in V \backslash V^{\prime }$ and $u, v \in V \backslash V^{\prime }$ are not possible for the edge (u, v).

Recall that by Condition (2), set $E^{\prime }$ is partitionable into disjoint sets $E^{\prime }_{i} \cup E^{\prime }_ r=E^{\prime }$ with $E^{\prime }_{r} =\mathsf{Edges}_{G} (V^{\prime }_r) \cap E^{\prime }$ and $E^{\prime } _i = \mathsf{Edges}_{G}(V^{\prime }_i\cup (V\backslash V^{\prime }))\cap E^{\prime }$. It follows that for the edge $(u,v) \in E^{\prime }$, it is not possible that $u \in V^{\prime }_r$ and $v \in V \backslash V^{\prime }$ or both $u, v \in V \backslash V^{\prime }$, as claimed.

Now, since $\varvec{\sigma }$ is a Nash equilibrium, ${\mathsf {U}}_{\mathsf{d}}({\varvec{\sigma }})= \sum _{\mathsf{a}_k \in {{\mathcal {A}}}} \left( \sigma _{k}(u)+\sigma _{k}(v)\right)$, for an arbitrary edge $e=(u,v)\in \mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d})$. Since for such an edge e, $\mathsf{A}_{\varvec{\sigma }}(e) = \frac{\textstyle \nu }{\textstyle |V^{\prime }_i|+\frac{\textstyle {|V^{\prime }_r|}}{\textstyle 2}}$, it follows that

$$\begin{aligned} {\mathsf {U}}_{\mathsf{d}}({\varvec{\sigma }})& = \frac{ \textstyle \nu }{\textstyle |V^{\prime }_i|+\frac{\textstyle |V^{\prime }_r|}{\textstyle 2}} , \end{aligned}$$

as claimed. $\square$

We continue to prove:

Lemma 11.3

Consider a Defender-Uniform Nash equilibrium $\varvec{\sigma }$. Then, the choices

• $V^{\prime } := \mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})$, with

  • $V^{\prime }_i := \left\{ v\in V^{\prime } \mid \mathsf{A_{\varvec{\sigma }}}(v) = \max _{e^{\prime }\in E}\mathsf{A_{\varvec{\sigma }}}(e^{\prime }) \right\}$;

  • $V^{\prime }_r := V^{\prime } \backslash V^{\prime }_i$;

• $E^{\prime } := \mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d})$, with

  • $E^{\prime }_{r} =\mathsf{Edges}_{G} (V^{\prime }_r) \cap E^{\prime }$;

  • $E^{\prime } _i = \mathsf{Edges}_{G}(V^{\prime }_i\cup (V\backslash V^{\prime }))\cap E^{\prime }$;

• $r := \mathsf{d}_{G(\mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d}))}(v)$ for any vertex $v\in \mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})$,

fulfill Conditions (1) and (2) of Theorem11.1.

Proof

We shall later prove that r is well-defined. Note that both $V^{\prime }$ and $E^{\prime }$ are non-empty. Since $\varvec{\sigma }$ is a Nash equilibrium, Proposition 7.1 implies that $\varvec{\sigma }$ is a Covering profile. So, $\mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d})$ is an Edge Cover. Thus, in particular, for the vertex $u\in \mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})$, $\mathsf{d}_{G(\mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d}))}(u)\ge 1$. It follows that $r\ge 1$. We shall prove that $V^{\prime }$, $E^{\prime }$ and r satisfy Conditions (1) and (2). We start with Condition (1). Consider any vertex $u\in V$. Clearly,

$$\begin{aligned} {\mathbb {P}}_{\varvec{\sigma }}(\mathsf{Hit}(u))& = \sum _{e \in \mathsf{Edges}_{\varvec{\sigma }}(u)} \frac{\textstyle 1}{\textstyle |\mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d})|} \quad ({\text {since}}\; \varvec{\sigma }\;{\text {is}}\; {\text {Defender-Uniform}})\\& = \frac{\textstyle \mathsf{d}_{G(\mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d}))}(u) }{\textstyle |\mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d})|}. \end{aligned}$$

Condition (C.1) in the characterization of a Nash equilibrium (Proposition 3.2) implies that for any vertex $u \in V$,

$$\begin{aligned} {{\mathbb {P}}}_{\varvec{\sigma }}(\mathsf{Hit}(u))&\;&\left\{ \begin{array}{lll} = &{} \min _{v \in V} {{\mathbb {P}}}_{\varvec{\sigma }}(\mathsf{Hit}(v)), &{} {\text {if}}\; u\in \mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}}) \\ \ge &{} \min _{v \in V} {{\mathbb {P}}}_{\varvec{\sigma }}(\mathsf{Hit}(v)), &{} {\text {if}}\;u\not \in \mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}}) \end{array} . \right. \end{aligned}$$

Hence, it follows that

$$\begin{aligned} \mathsf{d}_{G}(\mathsf{Supp_{\varvec{\sigma }}}(u))&\;&\left\{ \begin{array}{ll} = \min _{v \in V} \mathsf{d}_{G}(\mathsf{Supp_{\varvec{\sigma }}}(v)), &{} {\text {if}}\; u\in \mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}}) \\ \ge \min _{v \in V} \mathsf{d}_{G}(\mathsf{Supp_{\varvec{\sigma }}}(v)), &{} {\text {if}}\; u\not \in \mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}}) \end{array}. \right. \end{aligned}$$

Since by construction, $r= \mathsf{d}_{G}(\mathsf{Supp_{\varvec{\sigma }}}(v))$ for any vertex $v\in \mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})$ and $\mathsf{Supp_{\varvec{\sigma }}}(e)=E^{\prime }$, Conditions (1/a) and (1/b) follow.

We now prove Condition (2). We first prove that $V^{\prime } _i$ and $V^{\prime }_r$ are vertex-disjoint with $V^{\prime } _i \cup V^{\prime }_r =V^{\prime }$, and $E^{\prime } _i$ and $E^{\prime }_r$ are vertex-disjoint with $E^{\prime } _i \cup E^{\prime }_r =E^{\prime }$, as required for Condition (2). Observe first that, by construction, $V^{\prime }_i$ and $V^{\prime }_r$ are vertex-disjoint and $V^{\prime } _i \cup V^{\prime }_r =V^{\prime }$. We now show that $E^{\prime } _i$ and $E^{\prime }_r$ are also vertex-disjoint with $E^{\prime } _i \cup E^{\prime }_r =E^{\prime }$. Since $\varvec{\sigma }$ is a Nash equilibrium, Proposition 7.1, implies that $\varvec{\sigma }$ is a Covering profile. Thus, $\mathsf{Supp_{\varvec{\sigma }}}({{{\mathcal {A}}}})$ is a Vertex Cover of $G(\mathsf{Supp_{\varvec{\sigma }}}({\mathsf{d}}) )$. So, by the construction of $V^{\prime }$ and $E^{\prime }$, for any edge $(u,v) \in E^{\prime }$, either u or $v \in V^{\prime }$ or both $u, v \in V^{\prime }$. Consider first the case where both $u , v \in V^{\prime }$. By Condition (2/a), $V^{\prime }_i \subseteq V^{\prime }$ is an Independent Set of G. Thus, both $u , v \not \in V^{\prime } _i$. Since $V^{\prime }_r = V^{\prime } \backslash V^{\prime }_i$, it follows that both $u , v \in V^{\prime }_r$. So, by the construction of $E^{\prime } _r$, the edge $(u,v) \in E^{\prime } _r$. On the other hand, if only one of u and v belongs to $V^{\prime }$, say $u \in V^{\prime }$, then it must be that $v\in V\backslash V^{\prime }$. Thus, by the construction of $E^{\prime } _i$, $(u,v) \in E^{\prime } _i$. It follows that $E^{\prime } _i$ and $E^{\prime }_r$ are vertex-disjoint and that $E^{\prime } _i \cup E^{\prime }_r =E^{\prime }$.

We now continue to prove Condition (2/a). Consider any vertex $v \in V^{\prime }_i$, and a vertex $u\in \mathsf{Neigh}_{G}(v)$. We show that $u\not \in V^{\prime }_i$, so that $V^{\prime }_i$ is an Independent Set of G. Assume, by way of contradiction, that $u\in V^{\prime }_i$. Since $V^{\prime }_i \subseteq V^{\prime } = \mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})$, it follows that $u\in \mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})$. Hence, $\mathsf{A_{\varvec{\sigma }}}(u)> 0$, so that $\mathsf{A_{\varvec{\sigma }}}(e)= \mathsf{A}_{\varvec{\sigma }}(u) +\mathsf{A}_{\varvec{\sigma }}(v) > \mathsf{A}_{\varvec{\sigma }}(v) = \max _{e^{\prime }\in E} \mathsf{A}_{\varvec{\sigma }}(e^{\prime })$. A contradiction.

We continue to prove Condition (2/b). Consider a vertex $v\in V^{\prime }_r$ and an edge $e=(u,v)\in E_r'$. By the construction of $E^{\prime }_r$, $u \in V^{\prime }_r$. By Condition (1/a), $\mathsf{d}_{G(E^{\prime })}(v) =r$. It follows that the graph $\left\langle V^{\prime }_{r}, E_r' \right\rangle$ is an r-regular graph, and Condition (2/b) follows.

We finally prove Condition (2/c). We first show that $V\backslash V^{\prime }$ is an Independent Set of the graph $G(E^{\prime })$. Take any vertex $v \in V\backslash V^{\prime }$ such that there is an edge $(u,v) \in E^{\prime }$. We show that $u\not \in V\backslash V^{\prime }$. By the construction of $E^{\prime }$ and $E^{\prime } _i$, and since $E^{\prime } = E^{\prime } _i \cup E^{\prime } _r$, it follows that $u \in V^{\prime }_i$, so that $u\not \in V\backslash V^{\prime }$. Now since $V^{\prime }_i$ is an Independent set of G and $V\backslash V^{\prime }$ is an Independent Set of the graph $G(E^{\prime })$, it follows that graph $\left\langle V^{\prime }_{i}\cup (V\backslash V^{\prime }), E^{\prime }_i \right\rangle$ is $(V^{\prime }_{i}, V \backslash V^{\prime } )$-bipartite. $\square$

Theorem 11.1 follows from Lemmas 11.2 and  11.3.

11.2 Complexity

We show:

Theorem 11.4

$\exists$ DEFENDER-UNIFORM NE is $\mathcal{NP}$-complete.

For the proof of the Theorem, we will use a strengthening of Theorem 11.1 for the particular case of odd cycle graphs.

Lemma 11.5

Fix a cycle graph $\mathcal{C}_n$ for which $n\ge 3$ is an odd integer. Then, a Defender-Uniform Nash equilibrium $\varvec{\sigma }$ is FullyMixed.

The proof of the Lemma is deferred in the Appendix.

Proof

Recall that $\exists$ DEFENDER-UNIFORM NE is an $\mathcal{NP}$-problem. To prove $\mathcal{NP}$-hardness, we reduce from UNDIRECTED PARTITION INTO HAMILTONIAN SUBGRAPHS OF SIZE AT LEAST 6.

Consider an instance $G_0= \left\langle V_0, E_0 \right\rangle$ of UNDIRECTED PARTITION INTO HAMILTONIAN SUBGRAPHS OF SIZE AT LEAST 6. We construct an instance $G = \left\langle V, E\right\rangle$ of $\exists$ DEFENDER-UNIFORM NE as follows:

• 1. Add $G_0$ to G.

• 2. Add two cycle graphs $\mathcal{C}_1=(V_{\mathcal{C}_1}, E_{\mathcal{C}_1})$ and $\mathcal{C}_2=(V_{\mathcal{C}_2},E_{\mathcal{C}_2})$, each of order 5, to G, where $V_{\mathcal{C}_1}=\{ v_{1i}\mid 1\le i \le 5\}$ and $V_{\mathcal{C}_2}=\{ v_{2i}\mid 1\le i \le 5\}$.

• 3. For each vertex $v \in V_0$, add the edge $(v,v_{11})$.

The intuition behind including $\mathcal{C}_5$ in the instance G is to enforce the graph G to have a Defender-Uniform Nash equilibrium in which the support of the defender is a 2-regular graph; in this case, G is partitionable into Hamiltonian cycles. Figure 6 illustrates the construction. We first prove:

Lemma 11.6

Assume that $G_0 = \left\langle V_0, E_0\right\rangle$ is a YES instance for UNDIRECTED PARTITION INTO HAMILTONIAN SUBGRAPHS OF SIZE AT LEAST 6. Then, $G = \left\langle V, E\right\rangle$ is a YES instance for $\exists$ DEFENDER-UNIFORM NE.

Fig. 6

An illustration of the construction of the graph G

Proof

Consider a collection $\mathcal{C}$ of Hamiltonian circuits, each of size at least 6, covering $G_0$. Denote $E_{\mathcal{C}}\subseteq E$ the edges of the Hamiltonian circuits in the collection $\mathcal{C}$. Construct a Uniform and Attacker-Symmetric&FullyMixed profile $\varvec{\sigma }$ with $\mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d}) = E_{\mathcal{C}} \cup E_{\mathcal{C}_1} \cup E_{\mathcal{C}_2}$; so, $\mathsf{Supp_{\varvec{\sigma }}}(\mathcal{A}) = V$. Note that, by construction, for each vertex $v\in V$, $\mathsf{d}_{G(\mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d}))}(v)=2$. We shall prove that $\varvec{\sigma }$ fulfills Conditions (C.1) and (C.2) in the characterization of Nash equilibria (Proposition 3.2).

For Condition (C.1), consider any vertex $v\in V$. Then,

$$\begin{aligned} {{\mathbb {P}}}_{\varvec{\sigma }}(\mathsf{Hit}(v))& = \sum _{e\in \mathsf{Edges_{\varvec{\sigma }}}(v)} \sigma _{\mathsf{d}}(e) \\& = \frac{\textstyle 2 }{\textstyle |\mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d})|} \quad ({\text {since}}\;\mathsf{d}_{G(\mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d}))}(v)=2\;{\text {and}}\;\varvec{\sigma }\;{\text {is}}\; {\text {Defender-Uniform}}), \end{aligned}$$

and Condition (C.1) follows. For Condition (C.2), consider any edge $e=(u,v)\in E$. Then,

$$ \begin{aligned}&\mathsf{A_{\varvec{\sigma }}}(e) \sum _{\mathsf{a}_i\in {{\mathcal {A}}}} \sigma _{i}(u) +\sum _{\mathsf{a}_i\in {{\mathcal {A}}}} \sigma _{i}(v) \\& = \frac{\textstyle \nu }{\textstyle |V|}+\frac{\textstyle \nu }{\textstyle |V|} \quad ({\text {since}}\;\varvec{\sigma }\;{\text {is}}\;{\text {Attacker-Symmetric}} \& {\text {Uniform}} \& {\text {FullyMixed}}) \\& = \frac{\textstyle 2 \nu }{\textstyle |V|}, \end{aligned}$$

which implies Condition (C.2). Hence $\varvec{\sigma }$ is a Nash equilibrium, as needed. $\square$

We continue to prove:

Lemma 11.7

Assume that $G = \langle V, E \rangle$ is a YES instance for $\exists$ DEFENDER-UNIFORM NE. Then, $G_0 = \langle V_0, E_0 \rangle$ is a YES instance for UNDIRECTED PARTITION INTO HAMILTONIAN SUBGRAPHS OF SIZE AT LEAST 6.

Proof

Consider a Defender-Uniform Nash equilibrium $\varvec{\sigma }$ for G. Set:

• $V^{\prime }:=\mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})$ with

  • $V^{\prime }_i = \left\{ v\in V^{\prime } \mid \mathsf{A_{\varvec{\sigma }}}(v) =\right. \left. \max _{e^{\prime }\in E}\mathsf{A_{\varvec{\sigma }}}(e^{\prime }) \right\}$, and

  • $V^{\prime }_r = V^{\prime } \backslash V^{\prime }_i$.

• $E^{\prime }: =\mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d})$.

• $r: =\mathsf{d}_{G(\mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d}))}(v)$, for any arbitrary vertex $v\in \mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})$.

Lemma 11.3 implies that $V^{\prime }$, $E^{\prime }$ and r satisfy the conditions from the definition of a Defender-Uniform Nash equilibrium. We shall then deduce some further properties of $V^{\prime }$, $E^{\prime }$ and r.

Claim 11.8

$E_{\mathcal{C}_2} \subseteq E^{\prime }$, $V_{\mathcal{C}_2}\subseteq V^{\prime }$ and $r=2$.

Proof

Note that $\mathcal{C}_2=\left\langle V_{\mathcal{C}_2}, E_{\mathcal{C}_2}\right\rangle$ is a connected component of G. Hence, Lemma  11.5 applies to yield that $E_{\mathcal{C}_2} \cap \mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d}) = E_{\mathcal{C}_2}$ and $V_{\mathcal{C}_2} \cap \mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}}) = V_{\mathcal{C}_2}$. Since $\mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d})=E^{\prime }$ and $\mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})=V^{\prime }$, it follows that $E_{\mathcal{C}_2} \subseteq E^{\prime }$ and $V_{\mathcal{C}_2}\subseteq V^{\prime }$. Since $E_{\mathcal{C}_2} \subseteq E^{\prime }=\mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d})$ and $\mathcal{C}_2$ is a connected component of G, it follows that for any vertex $v\in V_{\mathcal{C}_2}$, $\mathsf{d}_{G(E^{\prime })}(v) = 2$. Condition (1/a) in the characterization of Defender-Uniform graphs (Theorem 11.1) implies that $\mathsf{d}_{G(E^{\prime })}(v) = 2$, for all vertices $v\in V^{\prime }$. Hence, $r=2$, as needed. $\square$

We continue to prove:

Claim 11.9

$E_{\mathcal{C}_1} \subseteq E^{\prime }$.

Proof

Consider any arbitrary vertex $v\in V_{\mathcal{C}_1}$, with $v\ne v_{11}$. Note that $\mathsf{d}_{G}(v)=2$. Since $r=2$, Condition (1) in the characterization of Defender-Uniform graphs (Theorem 11.1) implies that $\mathsf{d}_{G(E^{\prime })}(v)\ge 2$. Since $\mathsf{d}_{G(E^{\prime })}(v) \le \mathsf{d}_{G}(v)$, it follows that $\mathsf{d}_{G(E^{\prime })}(v)=2$. This implies that $E_{\mathcal{C}_1} \subseteq E^{\prime }$, as needed. $\square$

We next prove:

Claim 11.10

$V_{\mathcal{C}_1}\subseteq V^{\prime }_r$

Proof

Consider any vertex $v\in V_{\mathcal{C}_1}$. We shall prove that $v\in V^{\prime }_r$. We proceed by case analysis.

• Assume first that $v=v_{11}$. We first prove that $v_{11}\in V^{\prime }$.

  • Assume, by way of contradiction, that $v_{11} \not \in V^{\prime }$. Since $V^{\prime }=\mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})$, it follows that $v_{11} \not \in \mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})$. By Proposition 7.1, $\varvec{\sigma }$ is a Covering profile, so that $\mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})$ is a Vertex Cover of the graph $G(\mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d}))$. Recall that $E_{\mathcal{C}_1} \subseteq E^{\prime } =\mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d})$ (by Claim 11.9). We conclude that (i) both vertices $v_{12}, v_{15} \in \mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})$ (so that $\mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})$ “hits” edges $(v_{11},v_{12}),\; (v_{11},v_{12}) \in \mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d})$), and (ii) either $v_{13} \in \mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})$ or $v_{14} \in \mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})$ (so that $\mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})$ “hits” edge $(v_{13},v_{14}) \in \mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d})$). Take that $v_{13} \in \mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})$. (The case where $v_{14} \in \mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})$ is identical.) Then,

    $$\begin{aligned} \mathsf{A_{\varvec{\sigma }}}( v_{12}, v_{13})& = \mathsf{A_{\varvec{\sigma }}}(v_{12}) + \mathsf{A_{\varvec{\sigma }}}(v_{13})\\> & {} \mathsf{A_{\varvec{\sigma }}}(v_{12}) \quad ({\text {since}}\;v_{13}\in \mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})) \\& = \mathsf{A_{\varvec{\sigma }}}(v_{12}) + \mathsf{A_{\varvec{\sigma }}}(v_{11}) \quad ({\text {since}}\;v_{11}\not \in \mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}}))\\& = \mathsf{A_{\varvec{\sigma }}}( v_{11},v_{12} ). \end{aligned}$$

    Since both edges $(v_{12}, v_{13}), (v_{11}, v_{12}) \in E_{\mathcal{C}_1} \subseteq E^{\prime }=\mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d})$ (by Claim 11.9), Condition (C.2) in the characterization of Nash equilibria (Proposition 3.2) implies that $\mathsf{A_{\varvec{\sigma }}}( v_{12},v_{13}) = \mathsf{A_{\varvec{\sigma }}}( v_{11},v_{12})$. A contradiction. Hence, $v_{11} \in V^{\prime }$.

• Assume now that $v\ne v_{11}$. By Proposition 7.1, $\varvec{\sigma }$ is a Covering profile, so that $\mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})$ is a Vertex Cover of the graph $G(\mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d}))$. Recall that $E_{\mathcal{C}_1} \subseteq E^{\prime } =\mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d})$ (by Claim 11.9). Hence, $\mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})$ includes at least two vertices other than $v_{11}$. There are three possible cases:

  • $\mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})\;{\textit{includes additional vertices}}\;v_{13}, v_{14}$ It remains to prove that both remaining vertices $v_{12},v_{15}\in \mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})$. So, assume that $v=v_{12}$. (The case where $v=v_{15}$ is identical.) Assume, by way of contradiction, that $v_{12}\not \in \mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})$. Then,

    $$\begin{aligned} \mathsf{A_{\varvec{\sigma }}}( v_{13}, v_{14})& = \mathsf{A_{\varvec{\sigma }}}( v_{13}) + \mathsf{A_{\varvec{\sigma }}}( v_{14})\\> & {} \mathsf{A_{\varvec{\sigma }}}(v_{13}) \quad ({\text {since}}\;v_{14} \in \mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}}))\\& = \mathsf{A_{\varvec{\sigma }}}(v_{13}) + \mathsf{A_{\varvec{\sigma }}}(v_{12}) \quad ({\text {since}}\;v_{12}\not \in \mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}}))\\& = \mathsf{A_{\varvec{\sigma }}}( v_{12},v_{13} ). \end{aligned}$$

    Since both edges $(v_{12}, v_{13}) , (v_{13}, v_{14}) \in E_{\mathcal{C}_1} \subseteq E^{\prime }= \mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d})$ (by Claim 11.9), Condition (C.2) in the characterization of Nash equilibria (Proposition 3.2) implies that $\mathsf{A_{\varvec{\sigma }}}(v_{12},v_{13}) = \mathsf{A_{\varvec{\sigma }}}((v_{13},v_{14}))$. A contradiction. Hence, $v_{12} \in \mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})$.

  • $\mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})\;{\textit{includes additional vertices }}\;v_{12}, v_{14}$ It remains to prove that both remaining vertices $v_{13},v_{15}\in \mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})$. So, assume that $v=v_{13}$. (The case where $v=v_{15}$ is symmetric.) Assume, by way of contradiction, that $v_{13}\not \in \mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})$. Then,

    $$\begin{aligned} \mathsf{A_{\varvec{\sigma }}}( v_{11}, v_{12})& = \mathsf{A_{\varvec{\sigma }}}(v_{11}) + \mathsf{A_{\varvec{\sigma }}}(v_{12})\\> & {} \mathsf{A_{\varvec{\sigma }}}(v_{12}) \quad ({\text {since}}\;v_{11} \in \mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}}))\\& = \mathsf{A_{\varvec{\sigma }}}(v_{12}) + \mathsf{A_{\varvec{\sigma }}}(v_{13}) \quad ({\text {since}}\;v_{13}\not \in \mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}}))\\& = \mathsf{A_{\varvec{\sigma }}}(v_{12},v_{13}) . \end{aligned}$$

    Since both edges $(v_{11}, v_{12}) , (v_{12}, v_{13}) \in E_{\mathcal{C}_1} \subseteq E^{\prime }= \mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d})$ (by Claim 11.9), Condition (C.2) in the characterization of Nash equilibria (Proposition 3.2) implies that $\mathsf{A_{\varvec{\sigma }}}(v_{11},v_{12})) = \mathsf{A_{\varvec{\sigma }}}((v_{12},v_{13})$. A contradiction. Hence, $v_{13} \in \mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})$.

  • $\mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})\;{\textit{includes additional vertices}}\; v_{15}, v_{23}$ This is symmetric to the second case considered.

So, we have established that $V_{\mathcal{C}_1}\subseteq \mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})=V^{\prime }$. We will prove that, in fact, $V_{\mathcal{C}_1} \subseteq V^{\prime }_r$. Assume, by way of contradiction, that there is a vertex $v\in V_{\mathcal{C}_1}$ such that $v\not \in V^{\prime }_r$. Since $V_{\mathcal{C}_1}\subseteq V^{\prime }$, this implies that $v\in V^{\prime }_i$. By Condition (2/a) in the characterization of Defender-Uniform Graphs (Theorem 11.1), for each neighbor u of v in G, $u\not \in V^{\prime }$. But $u\in V_{\mathcal{C}_1} \subseteq V^{\prime }$. A contradiction. Hence, $V_{\mathcal{C}_1} \subseteq V^{\prime }_r$, as needed. $\square$

We continue to prove:

Claim 11.11

$\mathsf{Neigh}_{G(E^{\prime })}(v_{11}) = \{v_{12} , v_{15}\}$.

Proof

By Claim 11.10, $v_{11} \in V^{\prime }_r\subseteq V^{\prime }=\mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})$. By Claim 11.8, $r=2$. Hence, by Condition (1/a) in the characterization of Defender-Uniform Graphs (Theorem 11.1), $\mathsf{d}_{G(E^{\prime })}(v)= 2$. Claim 11.8 implies that both edges $(v_{11},v_{12}) ,$ $(v_{11}, v_{15})\in E^{\prime }$. Hence, both $v_{12} , v_{15} \in \mathsf{Neigh}_{G(E^{\prime })}(v)$. It follows that $\mathsf{Neigh}_{G(E^{\prime })}(v_{11}) = \{v_{12} , v_{15}\}$, as needed. $\square$

We finally prove:

Claim 11.12

$V_0 \subseteq V^{\prime }_r$.

Proof

Consider an arbitrary vertex $v\in V_0$. We shall establish that $v\not \in V^{\prime }_i$ and $v \not \in V \backslash V^{\prime }$. These will imply that $v\in V^{\prime }_r$.

${\textit{Proof that}}\;v\not \in V^{\prime }_i$ Assume, by way of contradiction, that $v\in V^{\prime }_i$. By construction, $v_{11}\in \mathsf{Neigh}_G(v)$. Hence, Condition (1) in the characterization of a Defender-Uniform Nash equilibrium (Theorem 11.1) implies that $v_{11}\not \in V^{\prime }$. Since $v_{11}\in V_{\mathcal{C}_1}$, Claim 11.10 implies that $v_{11} \in V^{\prime }_r\subseteq V^{\prime }$. A contradiction. Hence, $v\not \in V^{\prime }_i$.

${\textit{Proof that}}\;v\not \in V \backslash V^{\prime }$ Assume, by way of contradiction, that $v\in V \backslash V^{\prime }$. Since $V^{\prime }=\mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})$, this implies that $v\not \in \mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})$. Recall that by Claim 11.11, $\mathsf{Neigh}_{G(E^{\prime })}(v_{11}) = \{v_{12} , v_{15}\}$. Thus, $v\not \in \mathsf{Neigh}_{G(E^{\prime })}(v_{11})$. By Proposition 7.1, $\varvec{\sigma }$ is a Covering profile so that $\mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d})$ is an Edge Cover. Since v is not connected to any other vertex of $\mathcal{C}_1$ other than $v_{11}$, it follows that there is an edge $(u,v)\in E_0$ such that $(u,v)\in \mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d})$.

By Proposition 7.1, $\varvec{\sigma }$ is a Covering profile, so that $\mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})$ is a Vertex Cover of $G(\mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d}))=G(E^{\prime })$. Since $(u,v)\in \mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d})$ but $v\not \in \mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})$, this implies that $u \in \mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})=V^{\prime }$. We have established that for any arbitrary vertex $v\in V_0$, $v\not \in V^{\prime }_i$. This implies that $u\not \in V^{\prime }_i$. Hence, it follows that $u \in V^{\prime } \backslash V^{\prime }_i=V^{\prime }_r$. By Claim 11.8, $r=2$. Since $u\in V^{\prime }_r\subseteq V^{\prime }$, Condition (1/a) in the characterization of Defender-Uniform Graphs (Theorem 11.1) implies that $\mathsf{d}_{G(E^{\prime })}(u)=2$. Since $u\in V^{\prime }_r$, Condition (2/b) in the characterization of Defender-Uniform Graphs (Theorem 11.1) implies that $\mathsf{d}_{\left\langle V^{\prime }_{r}, \mathsf{Edges}_{G} (V^{\prime }_r) \cap E^{\prime }\right\rangle }(u)=2$. Since $v\not \in V^{\prime }$, it follows that edge $( u,v) \not \in \mathsf{Edges}_{G} (V^{\prime }_r) \cap E^{\prime }$. However, $(u,v) \in \mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d})=E^{\prime }$. Hence,

$$\begin{aligned} \mathsf{d}_{G(E^{\prime })}(u)\ge & {} \mathsf{d}_{\left\langle V^{\prime }_{r}, \mathsf{Edges}_{G} (V^{\prime }_r) \cap E^{\prime }\right\rangle }(u)+1\\& = r+1, \end{aligned}$$

a contradiction. Hence, $v\not \in V \backslash V^{\prime }$.

Since $v\not \in V^{\prime }_i$ and $v\not \in V \backslash V^{\prime }$, it follows that $v\in V^{\prime }_r$, as needed. $\square$

Since $\mathcal{C}_1$ and $\mathcal{C}_2$ are Hamiltonian circuits, it remains to determine a collection of Hamiltonian circuits that covers $G_0$. Consider an arbitrary vertex $u\in V_0$. By Claim 11.12, $V_0\subseteq V^{\prime }_r$, so that $u\in V^{\prime }_r$. Since $r=2$ (by Claim 11.8), Condition (1/a) in the characterization of Defender-Uniform Graphs (Theorem 11.1) implies that $\mathsf{d}_{G(E^{\prime })} (u)= 2$. Since $\mathsf{Neigh}_{G(E^{\prime })}(v_{11}) = \{v_{12} , v_{15}\}$ (by Claim 11.11), the construction of G implies now that $\mathsf{d}_{G(E^{\prime }\cap E_0)}(u) = 2$. It follows that the edge set $E^{\prime }\cap E_0$ induces a collection of Hamiltonian circuits that covers $G_0$. Since each Hamiltonian circuit has size at least six, the assumption implies that this is a collection of Hamiltonian circuits, each of size of at least six, that covers $G_0$, as needed. $\square$

Lemmas 11.6 and 11.7 conclude the proof. $\square$

11.3 Defense-Ratio

We show:

Theorem 11.13

The Defense-Ratio of a Defender-Uniform Nash equilibrium is $\frac{\textstyle |V | }{\textstyle 2} + \lambda \cdot \frac{\textstyle |V | }{\textstyle 2}$, where $0\le \lambda \le 1$.

Proof

By Lemma 11.2, ${\mathsf {U}}_{\mathsf{d}}({\varvec{\sigma }}) = \frac{ \textstyle \nu }{\textstyle |V^{\prime }_i|+\frac{\textstyle |V^{\prime }_r|}{\textstyle 2}}$. Setting $|V^{\prime }_i|=\lambda \cdot |V^{\prime }|$, $0\le \lambda \le 1$, the Defense-Ratio yields that

$$\begin{aligned} \frac{\textstyle \nu }{\textstyle {\mathsf {U}}_{\mathsf{d}}({\varvec{\sigma }}) }& = |V^{\prime }_i|+ \frac{\textstyle |V^{\prime }_r|}{\textstyle 2} \\& = |V^{\prime }_i | + \frac{\textstyle |V^{\prime } |- |V^{\prime }_i |}{\textstyle 2} \quad ({\text {since}}\;V^{\prime }_r = V^{\prime } {\setminus } V^{\prime }_i )\\& = \frac{\textstyle |V^{\prime }| }{\textstyle 2} + \lambda \cdot \frac{\textstyle |V^{\prime }| }{\textstyle 2} \quad ({\text {setting}}|V^{\prime }_i|=\lambda \cdot |V^{\prime }|,{\text {with}}\; 0\le \lambda \le 1)\\\le & {} \frac{\textstyle |V | }{\textstyle 2} + \lambda \cdot \frac{\textstyle |V |}{\textstyle 2} \quad ({\text {since}}|V^{\prime }|\le |V|), \end{aligned}$$

as needed. $\square$

Theorem 11.13 immediately implies:

Corollary 11.14

Assume that G is Defender-Uniform. Then, $\mathsf{PoD}_G \ge \frac{\textstyle |V|}{\textstyle 2} + \lambda \cdot \frac{\textstyle |V|}{\textstyle 2}$, $0\le \lambda \le 1$.

Proposition 10.6 implies that an Attacker-Symmetric&Uniform graph may be worse than an arbitrary graph with respect to the Price of Defense.

By Lemma 11.2, ${\mathsf {U}}_{\mathsf{d}}({\varvec{\sigma }}) = \frac{ \textstyle \nu }{\textstyle |V^{\prime }_i|+\frac{\textstyle |V^{\prime }_r|}{\textstyle 2}}$. We go through a case analysis:

• Since $\mathsf{DR}_{\varvec{\sigma }}= \frac{\textstyle \nu }{\textstyle {\mathsf {U}}_{\mathsf{d}}({\varvec{\sigma }})}$, the worst-case of the Defense-Ratio is obtained when the set $V^{\prime }_r$ is empty. Thus, by Lemma 11.3, $V^{\prime }_i = \mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})$ is an Independent set. So, $\mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}}) \le \alpha (G)$. By Lemma 11.2, it follows that ${\mathsf {U}}_{\mathsf{d}}({\varvec{\sigma }}) = \frac{ \textstyle \nu }{\textstyle |\mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}}) } | \ge \frac{ \textstyle \nu }{\textstyle \alpha (G) }$. So, $\mathsf{DR}_{\varvec{\sigma }}= \frac{\textstyle \nu }{\textstyle {\mathsf {U}}_{\mathsf{d}}({\varvec{\sigma }})} \le \alpha (G)$.

• For the best-case of the Defense-Ratio, recall that, by Condition 2(a) in the characterization of Defender-Uniform Nash equilibria (Theorem 11.1), the graph $\left\langle V^{\prime }_{i}\cup (V\backslash V^{\prime }), \mathsf{Edges}_{G}\right.$ $\left. (V^{\prime }_i\cup \right.$ $\left. (V\backslash V^{\prime }))\cap E^{\prime }\right\rangle$ is a $(V\backslash V^{\prime })$-Expander graph: Consider the graph $G_1 = \left\langle V^{\prime }_{i}\cup (V\backslash V^{\prime }), \right.$ $\left. \mathsf{Edges}_{G}(V^{\prime }_i\cup \right.$ $\left. (V\backslash V^{\prime }))\cap E^{\prime }\right\rangle$ in Theorem  11.1. Clearly, $G_1$ is a connected component of $G(E^{\prime })$. By Condition (2/a) of Theorem 11.1), $V^{\prime }_i$ is an Independent Set. Note that by Lemma 11.3, $V^{\prime } = \mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})$ and $V^{\prime } = V^{\prime } _{i}\cup V^{\prime }_r$. So, $V^{\prime }_i$ is the restriction of $\mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})$ to the vertices of the graph $G_1$. Thus, by Proposition 7.11, $V^{\prime }_i$ is an Expanding Independent Set. Hence, by the definition of an Expanding Independent Set, the graph the $G_1$ is a $(V\backslash V^{\prime })$-Expander graph. Thus, by the definition of an Expander graph,

  $$\begin{aligned} | V\backslash V^{\prime } |\le & {} |V^{\prime }_{i}|. \end{aligned}$$

  Since $|V|=|V^{\prime }_r|+|V^{\prime }_i|+| V\backslash V^{\prime } |$, it follows that

  $$\begin{aligned} |V^{\prime }_r|+2|V^{\prime }_i|\ge & {} |V|. \end{aligned}$$

  Hence,

  $$\begin{aligned} |V^{\prime }_i|+\frac{\textstyle |V^{\prime }_r|}{\textstyle 2}\ge & {} \ \frac{\textstyle |V|}{\textstyle 2} . \end{aligned}$$

  Since, by Lemma 11.2, ${\mathsf {U}}_{\mathsf{d}}({\varvec{\sigma }}) = \frac{ \textstyle \nu }{\textstyle |V^{\prime }_i|+\frac{\textstyle |V^{\prime }_r|}{\textstyle 2}}$, it follows that ${\mathsf {U}}_{\mathsf{d}}({\varvec{\sigma }}) \le \frac{\textstyle {\nu } }{ \frac{\textstyle |V|}{\textstyle 2}}$. So, $\mathsf{DR}_{\varvec{\sigma }}= \frac{\textstyle \nu }{\textstyle {\mathsf {U}}_{\mathsf{d}}({\varvec{\sigma }})} \ge \frac{\textstyle |V|}{\textstyle 2}$.

Combining together the best and the worst case with the respect to Defense-Ratio, a Defender-Uniform Nash equilibrium $\varvec{\sigma }$ has $\frac{\textstyle |V|}{\textstyle 2} \le \mathsf{DR}_{\varvec{\sigma }}\le \alpha (G)$.

12 Epilogue

In this work, we introduced and evaluated the Price of Defense as a measure of the efficiency of software protection against viruses. We have studied six classes of Nash equilibria for the game on graphs in [28], and we have identified corresponding characterizations, efficient membership and non-emptiness algorithms and bounds for the associated Price of Defense. Some relations among the six cases are summarized in Fig. 7. We conclude with some problems left open by our work:

• 1. Provide efficient approximation algorithms for Defender-Uniform Nash equilibria.

• 2. Identify further connections of Nash equilibria for the considered network game to Fractional Graph Theory. This will provide further insights into the combinatorial structure of the associated Nash equilibria.

• 3. Investigate further measures of performance for the Price of Defense. Are there corresponding relations of optimality for such other measures to Fractional Graph Theory (cf. Sect. 5)?

• 4. Investigate further, for its Price of Defense, the alternative model in which attacks and defenses are represented by edge and vertex players, respectively.

Fig. 7

An illustration of the relation among several classes of profiles. The class of Attacker-Symmetric&Uniform profiles is indicated by a shredded area

Appendix: Proof of Lemma  11.5

Set:

• $V^{\prime }:=\mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})$,

• $E^{\prime }: =\mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d})$ and $r: =d_{G(\mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d}))}(v)$ for an arbitrary vertex $v\in \mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})$.

By Lemma 11.3, $V^{\prime }$, $E^{\prime }$ and r satisfy Conditions (1) and (2) in the characterization of Defender-Uniform Graphs (Theorem 11.1). We first prove:

Lemma A.1

$\mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d})=E$.

Proof

Assume, by way of contradiction, that $\mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d}) \subset E$. Then, there is an edge $(v_{i},v_{i+1}) \not \in \mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d})$, for some i, $1\le i \le n$. Since a Nash equilibrium is a Covering profile (Proposition 7.1), Condition (1) in the definition of a Covering profile implies that $\mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d})$ is an Edge Cover. Since n is odd, this implies that $\mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d})$ contains two adjacent edges. Assume, without loss of generality, that both edges $(v_n,v_1),(v_1,v_2)\in \mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d})$. Thus, $d_{\mathcal{C}_n(\mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d}))}(v_1)=2$. On the other hand, since $\mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d})$ is an Edge Cover and $(v_{i},v_{i+1}) \not \in \mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d})$, it follows that $d_{\mathcal{C}_n(\mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d}))}(v_i)= 1$. We continue to prove:

Claim A.2

For any vertex $v\in \mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})$, $d_{\mathcal{C}_n(\mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d}))}(v)= 1$.

Proof

Since $\mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d})$ is an Edge Cover, $d_{\mathcal{C}_n(\mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d}))}(v)\ge 1$. Assume, by way of contradiction, that $d_{\mathcal{C}_n(\mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d}))}(v)>1$. It follows that $d_{\mathcal{C}_n(\mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d}))}(v)> d_{\mathcal{C}_n(\mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d}))}(v_i)$. Conditions (1/a) and (1/b) in the characterization of Defender-Uniform Graphs (Theorem 11.1) together imply that $d_{\mathcal{C}_n(\mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d}))}(v_i)\ge d_{\mathcal{C}_n(\mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d}))}(v)$. A contradiction. $\square$

${\textit{Proof that}}\; v_1\not \in \mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})$ By Claim A.2, for any vertex $v\in \mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})$, $d_{\mathcal{C}_n(\mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d}))}(v)$ $=1$. Since $d_{\mathcal{C}_n(\mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d}))}(v_1) =2$, it follows that $v_1\not \in \mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})$.

${\textit{Proof that}}\;v_n, v_2\in \mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})$ Since a Nash equilibrium is a Covering profile (Proposition 7.1), Condition (2) in the definition of a Covering profile implies that $\mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})$ is a Vertex Cover of the graph $\mathcal{C}_n(\mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d}))$. Since $v_1 \not \in \mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})$ while both $(v_n,v_1),$ $(v_1,v_2)\in \mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d})$, this implies that both $v_n, v_2\in \mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})$.

We continue to prove:

Claim A.3

Consider any vertex $v_i$, $i\ge 2$ such that $v_i\in \mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})$, $( v_{i-1},v_i )\in \mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d})$ and $v_{i-1}\not \in \mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})$. Then, the following conditions hold: (1) $(v_i, v_{i+1})\not \in \mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d})$, (2) $v_{i+1}\not \in \mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})$, (3) $(v_{i+1}, v_{i+2})\in \mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d})$, and (4) $v_{i+2} \in \mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})$.

An illustration of Claim A.3 is shown in Fig. 8.

Fig. 8

An illustration of the sets $\mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})$ and $\mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d})$ in a Defender-Uniform Nash equilibrium for the odd cycle graph $\mathcal{C}_n$, where n is an odd integer. The edges in $\mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d})$ are shown with bold edges and the vertices in $\mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})$ are shown with surrounding circles

Proof

We separately prove each of the four claims.

(1): Since $v_i\in \mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})$, by Claim A.2, $d_{\mathcal{C}_n(\mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d}))}(v_i) =1$. Since $(v_i,v_{i-1})$ $\in \mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d})$, it follows that $(v_{i},v_{i+1})$ $\not \in \mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d})$.

(2): Assume, by way of contradiction, that $v_{i+1}\in \mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})$. Then, $\mathsf{A_{\varvec{\sigma }}}(v_{i+1})>0$, so that

$$\begin{aligned} \mathsf{A_{\varvec{\sigma }}}(v_{i},v_{i+1}) &> \mathsf{A_{\varvec{\sigma }}}(v_i) \\ &=\mathsf{A_{\varvec{\sigma }}}(v_{i-1},v_i)\quad({\text {since}}\;v_{i-1}\not \in \mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})). \end{aligned}$$

Since $(v_i,v_{i-1})\in \mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d})$, Condition (C.2) in the characterization of Nash equilibria (Proposition 3.2) implies that $\mathsf{A_{\varvec{\sigma }}}(v_{i},v_{i-1})\ge \mathsf{A_{\varvec{\sigma }}}(v_i,v_{i+1})$. A contradiction.

(3): Recall that $\mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d})$ is an Edge Cover of $\mathcal{C}_n$. Consider vertex $v_{i+1}$; since $(v_{i},v_{i+1}) \not \in \mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d})$, it follows that $(v_{i+1},v_{i+2}) \in \mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d})$.

(4): Recall that $\mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})$ is a Vertex Cover of the graph $\mathcal{C}_n(\mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d}))$. Since $(v_{i+1},v_{i+2}) \in \mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d})$ while $v_{i+1} \not \in \mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})$, it follows that $v_{i+2}\in \mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})$.

The claim follows. $\square$

Consider now vertex $v_2\in \mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})$. By Claim A.3, $(v_1,v_2) \in \mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d})$ but $v_1\not \in \mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})$. Hence, Claim A.3 applies repeatedly (in a clockwise fashion) to yield that $\mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}}) =\left\{ v_2,v_4,\right.$ $\left. \ldots , v_{n-1},v_1 \right\}$; thus, $v_1\in \mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})$. A contradiction. $\square$

We continue to prove:

Lemma A.4

$\mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})=V$.

Proof

Since a Nash equilibrium is a Covering profile (Proposition 7.1), Condition (2) in the definition of a Covering profile implies that $\mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})$ is a Vertex Cover of the graph $\mathcal{C}_n(\mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d}))$. Since n is odd, this implies that $\mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})$ contains at least two adjacent vertices of $\mathcal{C}_n$. We prove:

Claim A.5

Assume that vertices $v_{i}, v_{i+1}\in \mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})$. Then, $v_{i+2}\in \mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})$.

Proof

Assume, by way of contradiction, that $v_{i+2}\not \in \mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})$. Then,

$$\begin{aligned} \mathsf{A_{\varvec{\sigma }}}(v_i,v_{i+1})& = \mathsf{A_{\varvec{\sigma }}}(v_i) + \mathsf{A_{\varvec{\sigma }}}(v_{i+1})\\> & {} \mathsf{A_{\varvec{\sigma }}}(v_{i+1}) \quad ({\text {since}}\;v_i\in \mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}}))\\& = \mathsf{A_{\varvec{\sigma }}}(v_{i+1},v_{i+2}) \quad ({\text {since}}\;v_{i+2}\not \in \mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})) \end{aligned}$$

Lemma A.1 implies that both edges $(v_{i},v_{i+1}), (v_{i+1},v_{i+2}) \in \mathsf{Supp_{\varvec{\sigma }}}(\mathsf{d})$. Hence, by Condition (C.2) in the characterization of Nash equilibria (Proposition 3.2), $\mathsf{A_{\varvec{\sigma }}}(v_{i},v_{i+1})= \mathsf{A_{\varvec{\sigma }}}(v_{i+1},v_{i+2})$. A contradiction. $\square$

By repeated application of Claim A.5, it follows that $\mathsf{Supp_{\varvec{\sigma }}}({{\mathcal {A}}})= V$. $\square$

By Lemmas A.1 and A.4, the claim follows. $\square$