Christophe Bravard
email: christophe.bravard@univ-grenoble-alpes.fr.

Liza Charroin
email: charroin@gate.cnrs.fr.

Corinne Touati
email: corinne.touati@inria.fr.

Pascal Billand

Stéphan Hans Haller

Optimal Design and Defense of Networks Under Link Attacks

Keywords: JEL Classification: D74, D85 Attacks on links, Network defense, Network design

 with two players: a Designer and an Adversary. First, the Designer forms costly protected and non-protected links. Then, the Adversary attacks at most k links given that attacks are costly and that protected links cannot be removed by her attacks. The Adversary aims at disconnecting the network shaped by the Designer. The Designer builds a protected network that minimizes her costs given that it has to resist the attacks of the Adversary. We establish that in equilibrium the Designer forms a minimal 1-link-connected network which contains only protected links, or a minimal (k + 1, n)-link-connected network which contains only non-protected links, or a network which contains one protected link and (n -1)(k + 1)/2 non-protected links. We also examine situations where the Designer can only create a limited number of protected links and situations where protected links are imperfect, that is, protected links can be removed by attacks with some probabilities. We show that if the available number of protected links is limited, then, in equilibrium, there exists a network which contains several protected and non-protected links. In the imperfect defense framework, we provide conditions under which the results of the benchmark model are preserved.

Introduction

Networks can be seen as communication structures. They are composed of nodes and links, where links represent the flow of information. Networks represent a crucial feature in our society, and are of particular interest in different fields such as military defense, telecommunication or computer networks. Some networks can be damaged by natural disasters or intelligent attacks. Attacks can affect nodes (agents, computers, telecommunication antennas, ...) or links (roads, communications flows, ...), and may disconnect a network. 1 In this paper, we examine a model where attacks target links. To illustrate the type of situations we model, consider a firm which has several production units (nodes of the network). Each production unit produces a part of the product and the pieces are assembled by a given production unit. The links of the network allow the parts of the product to be transferred among the units. If one unit is not connected to the rest of the units, its production cannot be transferred and the production 1 has no value. Recall that during the Second World War, the production units for the weapons (nodes) were buried, so they were impossible to target, and attacks had to target the roads (links) in order to destroy the production process of the enemy. Therefore, the issue was to design a communication network between the production units that the enemy could not disconnect.

Our goal is to examine how to design and protect the network in an optimal way, such that the network remains connected after an intelligent link attack. 2 We say that a network is designed and protected in an optimal way if the costs associated with the design and the protection of the network are minimized.

We consider a two-stage game with two players: a Designer (D) and an Adversary (A).

• Stage 1. The Designer moves first and chooses both a set of protected, and a set of non-protected links. Protected links cannot be removed by the attacks of the Adversary.

• Stage 2. After observing the protected network (strategy) formed by the Designer, the Adversary attacks the network by allocating attacks to specific links. Since the attacks are costly, the Adversary has an incentive to attack at most k links.

Creating protected and non-protected links is costly for the Designer. The benefits obtained by the Designer at the end of the game depend on the connectivity of the residual network, that is, the network obtained after the attack of the Adversary. If the residual network is connected, then the Designer wins the game: her benefits are equal to 1 and the benefits of the Adversary are 0. If the residual network is not connected, then the Adversary wins the game: her benefits are equal to 1 and the benefits of the Designer are 0. The payoffs obtained by the players are equal to the difference between their benefits and the costs associated with their strategies. 3We are interested in the Sub-game Perfect Equilibrium (SPE) of the two-stage game. We assume that the cost of protected links and non-protected links are sufficiently low so that the Designer has some profitable strategies which allow the residual network to be connected. First, we provide for each number of protected links, the minimal number of non-protected links that the Designer has to form in order to prevent the Adversary from disconnecting the network as well as a method to construct a solution network. Second, we establish that only three polar non-empty networks may arise in equilibrium in the benchmark model. 1. A minimal (k + 1, n)-link-connected network which contains no protected links. 42. A minimal (1, n)-link-connected network which contains n -1 protected links.

3.

A network which contains one protected link and (n -1)(k + 1)/2 non-protected links.

The first family of networks constitutes the optimal strategy of the Designer when the cost of forming non-protected links is sufficiently low relative to that of forming protected links. The second one is the optimal strategy when the cost of forming non-protected links is sufficiently high relative to that of forming protected links. The third one is optimal for intermediate relative costs (cost of a protected link / cost of a non-protected link) when the number of nodes is odd and the number of attacks is even.

Additionally to the benchmark model described above, we study some variations of the game to develop a larger understanding of optimal design of protected networks. We take into account two types of limitations concerning protections. First, we consider that D cannot create as many protected links as in the benchmark model. 5 Then, we consider a framework where each protected link has a probability π to be removed when it is attacked by A. 6In the framework where the number of protected links available for D is limited, we show that for intermediate relative costs, the optimal strategy of D consists in designing a network which contains both protected links and non-protected links. In the framework where protected links are removed by attacks with some probabilities, we provide conditions under which the results obtained in our benchmark model are preserved.

We now relate our paper to the existing literature on networks. This literature has become broader in the recent years (Jackson [18], Goyal [START_REF] Goyal | Connections: an introduction to the economics of networks[END_REF] and Vega-Redondo [START_REF] Vega-Redondo | Complex social networks[END_REF]). The two seminal papers on the formation of social and economic networks are the paper of Jackson and Wolinsky [START_REF] Jackson | A strategic model of social and economic networks[END_REF] and the paper of Bala and Goyal [START_REF] Bala | A noncooperative model of network formation[END_REF]. Bala and Goyal [START_REF] Bala | A strategic analysis of network reliability[END_REF] and Haller and Sarangi [START_REF] Haller | Nash networks with heterogeneous links[END_REF] introduce imperfectly reliable links in the Bala and Goyal [START_REF] Bala | A noncooperative model of network formation[END_REF] model. Bala and Goyal [START_REF] Bala | A strategic analysis of network reliability[END_REF] show that, for certain ranges of linking cost and probability of failure, the equilibrium network is at least (2, n)-link-connected, i.e. any two nodes are connected by at least two paths. Haller and Sarangi [START_REF] Haller | Nash networks with heterogeneous links[END_REF] extend the model of Bala and Goyal [START_REF] Bala | A strategic analysis of network reliability[END_REF] by allowing heterogeneity in probabilities of link failure. These authors model random link failure but not an intelligent attack that seeks to interrupt the communication flow. In the present paper, we study the robustness of a network that must be designed and protected to resist an intelligent attack on links.

A growing literature on attacked networks studies the optimal strategy of a Designer whose network is under node attack. Dziubinski and Goyal [START_REF] Dziubiński | Network design and defense[END_REF](DG) study the optimal design and defense of networks under an intelligent attack. In their framework, there are two players: the Designer and the Adversary; the Designer can form links between n nodes, and protect these nodes to ensure their survival. The model we propose is close to the model of DG, with the following major differences:

• The Adversary attacks nodes in the DG's framework while she attacks links in our framework;

• In our framework, the Designer wins the game if every node is able to communicate with any other node in the residual network. In the DG's framework, the Designer wins the game if the residual network is connected regardless of the number of nodes removed by the Adversary. Thus, our setting is based on the complementarity of nodes while DG assume that nodes are substitutable.

DG show that in an SPE, the Designer protects 0 or 1 node. If the Designer protects 0 nodes, then she designs a minimal (k + 1, n)-node-connected network. 7 We obtain the same type of networks when the Designer uses no protection. At first sight, this result seems intriguing since the Adversary attacks nodes in DG's paper and links in our paper. However, a minimal (k + 1, n)-node-connected network defined in DG is also a network that contains the minimal number of links and resists the Adversary who attacks links. In DG's paper, if the Designer protects nodes, she designs a star network 8 and protects 1 node, the central node. In our framework, when D uses protections, she designs either a network which contains 1 protected link and (n -1)(k + 1)/2 non-protected links, or a network which contains n -1 protected links. The results differ because in our framework every node needs to be connected with any other node in the residual network. Moreover, we establish that if we limit the number of available protections, then there exist optimal strategies for D where she designs networks which contain several protected and non-protected links. This result follows the fact that the number of non-protected links that each protected link allows the Designer to save is not constant. DG examine imperfect defense through an example. They assume that the protections used by the Designer can fail when they are attacked by the Adversary. More precisely, an attack on an unprotected target always destroys the target, and an attack on a protected target destroys the target with a positive probability. A recent independent work of Landwehr [START_REF] Landwehr | Network design and imperfect defense[END_REF] extends the analysis of imperfect defense. It shows that for a certain range of protection cost and link formation cost, strategies that use both protections and several links are equilibria.

Hoyer and De Jaegher [START_REF] Hoyer | Strategic network disruption and defense[END_REF] consider a framework where the Designer has to shape the network and form enough links in order to resist the attacks. In this framework, the Designer cannot protect specific parts of the network. The authors study the optimal way to design a network under link or node deletion with various cost levels. They show that if the costs of forming links are low, a regular network 9 with a sufficient number of links is the optimal network for the Designer. If costs are high and links are attacked, then a star network is optimal for the Designer. The difference with our paper (except for the fact that they do not use protected links) is that in our framework, nodes are complementary and the Designer cannot sacrifice any node to minimize her costs. Haller [START_REF] Haller | Network vulnerability: a Designer-Disruptor game[END_REF] extends the model of Hoyer and De Jaegher [START_REF] Hoyer | Strategic network disruption and defense[END_REF] by adding the possibility for two nodes to be connected by more than one link. In that case, it is harder for the Adversary to disconnect the network. Allowing multiple links between nodes can be seen as a different way to protect a connection between specific nodes than ours.

A part of the literature on attacked networks examines the role played by the contagion of attacks in networks. Goyal and Vigier [START_REF] Goyal | Attack, defense, and contagion in networks[END_REF] extend the work of DG by allowing the contagion of attacks (or threats). They find that the star network with a protected central node remains an equilibrium network. Cabrales, Gottardi and Vega-Redondo [START_REF] Cabrales | Risk-sharing and contagion in networks[END_REF] and Baccara and Bar-Isaac [START_REF] Baccara | How to organize crime[END_REF] study the contagion of attacks in networks respectively in the field of financial firms where a financial risk can spread between connected firms and in the field of criminal networks where connectivity increases vulnerability because of external threats. 10 Cerdeiro, Dziubinski and Goyal [START_REF] Cerdeiro | Contagion risk and network design[END_REF] and Acemoglu, Malekian and Ozdaglar [START_REF] Acemoglu | Network security and contagion[END_REF] identify nodes to players. Specifically, Cerdeiro, Dziubinski and Goyal [START_REF] Cerdeiro | Contagion risk and network design[END_REF] propose a three-stage game. First, the Designer chooses the network. Second, each player observes the network and chooses independently and simultaneously if she invests in protection or not. Third, the Adversary observes the protected network and chooses the players to infect. In Acemoglu, Malekian and Ozdaglar [START_REF] Acemoglu | Network security and contagion[END_REF] nodes/players are connected in a random network. Players have to invest in protection to be immune. Their investment depends on their links and the probability of being infected in the random network. This model allows to examine for instance the impact of a contagious disease on the individual behavior. These papers are different from the present one for two reasons. First, we study a framework where an attack on a link can remove only this specific link. Indeed, literature on contagious attacks reflects situations such as epidemics or virus spreading while our paper is focused on the study of specific link removal (for military strategies for instance). Second, in our model nodes cannot influence the architecture of the network by their decision. 11 The rest of the paper is organized as follows. In section 2, we present the model setup. In section 3, we present our main results. In section 4, we extend our model by examining a framework where the number of protected links available for the Designer is limited, and a framework where protected links have some probabilities to be removed by an attack. In section 5, we conclude.

Model setup

To simplify the notations, we set a, b = {i ∈ N, a ≤ i ≤ b}. Moreover, x and x are respectively the largest integer smaller or equal to x and the smallest integer larger or equal to x, and abs (x) = max{-x, x}. Further, for every set X, #X is its cardinality.

Network. For any integer n > 4, let N = 1, n and L(N ) be the set of unordered pairs of N , i.e. L(N ) = {(i, j) ∈ N × N, i = j}. Throughout the paper, the elements of N are referred to as nodes while those of L(N ) are called links. An unordered pair (i, j) ∈ L(N ) is thus a link said to join nodes i and j and the link is denoted by ij. We introduce the notion of protected network as a triplet g = (N, EP , ENP ) with EP ⊆ L(N ), ENP ⊆ L(N ) and EP ∩ ENP = ∅. We call protected links the elements of EP and non-protected links the elements of ENP . Let G be the set of all protected networks. The significance of this refinement on the links will be made explicit in the two-player game formulation. To simplify the notations, we let p = #EP . In the rest of the paper, we will interchangeably use the term network or protected network. 10 McBride and Hewitt [START_REF] Mcbride | The enemy you can't see: An investigation of the disruption of dark networks[END_REF] study the best way to dismantle a criminal network with imperfect information on its architecture. There also exists a literature which examines the particular cases of terrorist attacks, transportation network security, and homeland security (see Brown, Carlyle, Salmeron and Wood [START_REF] Brown | Defending critical infrastructure[END_REF], Tambe [START_REF] Tambe | Security and game theory: Algorithms, deployed systems, lessons learned[END_REF], and Hong [START_REF] Hong | Enhancing transportation security against terrorist attacks[END_REF]).

11 Additionally to economics, several fields investigate problems close to the one we deal with. In an early graph theoretic work, Harary [START_REF] Harary | The maximum connectivity of a graph[END_REF] exhibits a family of (k, n)-node-connected networks with a total number of links that is minimal. This family of networks is crucial to establish our results. Groetschel, Monma and Stoer [START_REF] Groetschel | Design of survivable networks[END_REF] study a model where a firm has to prevent a communication network to be disconnected given that there exist possibilities of communication failure. As some connections may be interrupted, the firm has to design the least costly network that guarantees the best service for the consumers. Moreover, there also exists a literature on the design of survivable networks (see the survey of Kerivin and Mahjoun [START_REF] Kerivin | Design of survivable networks: A survey[END_REF]) in Computer Science. Cunningham [START_REF] Cunningham | Optimal attack and reinforcement of a network[END_REF] studies network security and considers a model where the Designer allocates a different number of defense units to each link. A defended link has a level of resistance that depends on the number of defense units the Designer has allocated to it. The Adversary allocates attack units to remove a link. A link is removed if more attack units than defense units have been allocated to this link. The author proposes an algorithm which exhibits how some links have to be reinforced in order to protect the network.

For any network g, let EP (g) (respectively ENP (g)) refer to the set of protected (respectively nonprotected) links of g, and E(g) = EP (g) ∪ ENP (g). If there exists a link between i and j in g (i.e. if ij ∈ E(g)), then i and j are called adjacent. For each node i, di(g) is its degree in g, that is the number of links incident to i in g: di(g) = #{ij ∈ E(g)}. A path between two nodes i0 and iq of a network g is a finite alternating sequence of nodes and distinct links: i0, i0i1, i1, i1i2, i2, . . . , iq-1iq, iq where i ∈ N for all ∈ 0, q and i i +1 ∈ E(g) for all ∈ 0, q -1 . A cycle is a path where i0 = iq. Finally, a network g = (N, EP , ENP ) is connected if there exists a path between any two nodes i, j ∈ N . We say that network g = (N , E P , E N P ) is a subnetwork of g = (N, EP , ENP ) if N ⊆ N , E P ⊆ EP and E N P ⊆ ENP . Subnetwork g = (N , E P , E N P ) is a component of network g if g is connected and if there is no connected subnetwork g = (N , E P , E N P ) of g, with g = g and such that N ⊆ N or E(g ) ⊆ E(g ). By convention, a node i ∈ N such that di(g) = 0 is a component.

Two-player game. The players are the Designer (D) and the Adversary (A). We consider a twostage game where D plays first and A moves at the second stage. Given N , a strategy s D for D is (identified with) a protected network (N, E D P , E D N P ). In other words, D chooses to create some links from L(N ) and to protect some of them:

s D = (N, E D P , E D N P ), E D P ⊆ L(N ), E D N P ⊆ L(N )
, and

E D P ∩ E D N P = ∅.
A strategy for the Adversary is a mapping that assigns to each protected network g a subset of links E A of E(g). In other words, A chooses to attack some links of g:

s A : G → 2 L(N ) , g → s A (g) = E A , with s A (g) ⊆ E(g).
Residual network and benefits. At the first stage D designs a protected network s D . Then, the attack of A leads to a second protected network of the form g R = (N, E D P , E D N P \ E A ), which we call residual network. Note that, by construction, g R is a subnetwork of s D . The benefits of D are given by

φ(g R ) = 1, if g R is connected, 0, otherwise. (1)
Network and costs. We assume that attacking a link has a unitary cost cA. Therefore, the cost of the Adversary associated with s

A (g) = E A is c A (E A ) = cA#E A , (2)
where cA ∈ [1/(n -3), 1). 12 Note that the cost of a strategy is less than 1 if and only if the Adversary attacks less than k = 1/cA links. Similarly, both protected and non-protected links are costly to create: each protected link has a strictly positive cost cP > 0 and each non-protected link has a strictly positive cost cL > 0. We assume that cP > cL. The cost of a strategy s D of the Designer is thus:

c D (s D ) = cP #E D P + cL #E D N P . (3)
If the cost of creating protected or non-protected links is too large, then D cannot use a strategy where she forms protected or non-protected links. Therefore, to obtain non trivial results, we assume that the costs of creating protected and non-protected links are sufficiently low: cP < 1/(n -1) and cL < 1/(n(n -1)/2). 13Payoffs. The payoff of the Designer for choosing s D when the Adversary responds with s A is:

Π D (s D , s A (s D )) = φ(g R ) -c D (s D ). (4)
Since cP < 1/(n -1), D obtains a strictly positive payoff when she designs a network with n -1 protected links and 0 non-protected links and the residual network is connected. Similarly, since cL < 1/(n(n -1)/2), D obtains a strictly positive payoff when she designs a network with 0 protected links and n(n -1)/2 non-protected links and the residual network is connected. The payoff of the Adversary is

Π A (s D , s A (s D )) = 1 -φ(g R ) -c A (s A (s D )). (5)
If there exist two strategies of A that lead to the same payoff, A chooses the one having the highest value of #E A . 14In a nutshell, in our framework the objective of the Designer is to obtain a connected residual network at a minimal cost. The objective of the Adversary is to obtain a residual network that is disconnected. Note that A does not attack strictly more than n -3 links. Indeed, A obtains Π A (s D , s A (s D )) ≤ 1 -1/cA #E A < 0, when #E A > n -3, while A obtains a payoff equal to zero when she attacks no links. We now provide some illustrations where equation (1) captures the benefits of D. Suppose that D has n production units identified to nodes. Let yi be the output of production unit i, and δi be such that δi = 1 if there is a path between i ∈ 2, n and production unit i -1, and δi = 0 otherwise. Here, production unit i -1 can be interpreted as the unique supplier of production unit i. We assume that y1 = γ, γ > 0, and yi = δiyi-1 for i ∈ 2, n . If the total output obtained by D from the production units is Y = yn, then the total output function is in line with the benefits function of D. The same conclusion occurs if we assume Y = min i∈N {yi} or Y = i∈N (yi) ρ i with ρi > 0. We now provide another example. Let nodes be identified to cities and links be identified to communication flows between cities. Public authorities may have an incentive to maintain communication between all the cities when some communication flows are broken because of a natural disaster or a strategic attack. Indeed, if some cities are isolated from the others, then it is difficult for the public authorities to rescue inhabitants of these cities.

Sub-game Perfect Equilibrium (SPE).

An SPE is a pair (s D , s A ) that prescribes the following strategic choices. At Stage 2, A plays a best response s A (s D ) to s D ∈ G:

s A (s D ) ∈ argmax X⊆E(s D ) {Π A (s D , X)}.
Note that s A (s D ) ⊆ E D N P since attacks cannot remove protected links. Let g R (s D ) be the residual network obtained when D plays strategy s D and A plays a best response to s D , that is s A (s D ). Given the best response outcome g R (s D ), D achieves payoff φ(g R (s D )) -c D (s D ) when choosing s D . At stage 1, D plays s D such that

s D ∈ argmax X∈G {Π D (X, s A (X))}.
Specific architectures. The empty network is the network which contains no links. A tree is a connected and acyclic network. A network g which contains n nodes is a (κ, n)-link-connected network if any subnetwork g obtained from g by removing κ -1 links is connected, and there exists a subnetwork g obtained from g by removing κ links that is not connected. Let G(κ, n) be the set of minimal (κ, n)-linkconnected networks with n nodes, i.e. if g ∈ G(κ, n), then there does not exist a (κ, n)-link-connected network, g , such that #E(g ) < #E(g). It is easy to see that every node i of a network g ∈ G(κ, n) satisfies di(g) ≥ κ, as otherwise it could be separated by removing all links incident to i. Consequently, the number of links in a minimal (κ, n)-link-connected network, κ ≥ 2, is at least nκ/2 . As was shown by Harary [START_REF] Harary | The maximum connectivity of a graph[END_REF], this condition is also sufficient. The proof of this result is constructive -Harary describes how to obtain a family of solution graphs when κ ≥ 2. The minimal (κ, n)-link-connected networks described by Harary are called (κ, n)-Harary-networks. To give the reader some idea of what (κ, n)-Harary-networks look like, we provide some examples in Figure 1 with 5 nodes. For full description of the construction the interested reader is referred to Harary [START_REF] Harary | The maximum connectivity of a graph[END_REF]. Specific strategies. We define specific strategies that play a crucial role in the rest of the paper.

(N, ∅, ∅) is the empty network. Let S D p,k be the set of protected networks that (i) cannot be disconnected by k attacks, (ii) contain p protected links, and (iii) contain a minimal number of non-protected links. Protected networks which belong to the same set induce the same costs for D. Protected networks associated with two specific values of p play a crucial role in our analysis.

• S D 0,k is the set of protected networks which contain no protected link, and which are minimal

(k + 1, n)-link-connected networks. For instance, (k + 1, n)-Harary-networks belong to S D 0,k . • S D n-1,k
is the set of protected networks s D = (N, EP , ENP ) which only contain protected links (ENP = ∅) and such that (N, EP , ∅) is a tree. 15

Model Analysis

Our first result provides, for any number of protected links, the minimal number of non-protected links that the Designer has to form in order to prevent the Adversary from disconnecting the network.

To establish the first result, for any pair (n, k) ∈ N × 1, n -3 , we set p1(k, n) and p2(k, n) as follows:

               ∆ = (3k + 5) 2 -8n(k + 1) p1(k, n) = 4 n -3 k -5 - √ ∆ 8 + 1 if ∆ ≥ 0, and p1(k, n) = -1 otherwise, p2(k, n) = 4 n -3 k -5 + √ ∆ 8 -1 if ∆ ≥ 0, and p2(k, n) = -1 otherwise.
When no confusion is possible, we let p1 = p1(k, n) and p2 = p2(k, n).

Proposition 1 Suppose that A attacks exactly k links in an optimal way. Let n1(p, k)

= (n-p)(k+1) 2 and n2(p, k) = (n -2p) (k + 1 + p) + (n -1)p -n(n-1) 2 . For s D ∈ S D p,k ,
15 Indeed, if the subnetwork of s D , (N, E P , ∅), is a tree and

E N P = ∅, then s D ∈ S D n-1,k cannot be disconnected by k attacks. Otherwise -that is if (N, E P , ∅) contains a cycle -the network is not connected unless #E D N P > 0.
Therefore, that network does not satisfy condition (iii) and thus is not in

S D n-1,k . #E D N P =          n1(p, k), for p ∈ 0, n -2 \ p1(k, n), p2(k, n) , n2(p, k), for p ∈ 0, n -2 ∩ p1(k, n), p2(k, n) , 0, for p = n -1. (6)
So, if D forms p protected links and A attacks k links, then the optimal cost function associated with the pair (p, k) is

C (p, k) = cL #E D N P + cP p, with s D ∈ S D p,k . (7)
Proof The proof is given in Appendix.

Let us provide the intuition of Proposition 1. If D forms n -1 protected links, then there exists a set of strategies (i.e. a set of protected networks) for D that allows to resist k attacks without nonprotected links, S D n-1,k . Otherwise, let D form p ∈ 0, n -2 protected links and build a protected network s D = (N, EP , ENP ) in S D p,k . First, (N, EP , ∅) is acyclic. Indeed, if s D contains a cycle, then there exists a protected link, say ij, that can be removed without altering the fact that s D resists k attacks. Hence, it is possible for D to remove the protected link ij and replace a non-protected link i j by the protected link i j , and so reduce the number of non-protected links.

Second, consider the following sequence of networks: g0 = (N, ∅, ∅) and for any ∈ 1, p , g = (N, EP (g -1 ) ∪ ij, ∅) for some ij ∈ EP \EP (g -1 ). Hence gp = (N, EP , ∅). Since there is no cycle in (N, EP , ∅), then, for any , the extra link of EP (g ) allows to merge two components of EP (g -1 ). Since g0 has n components, then by an immediate recurrence, (N, EP , ∅) has exactly n -p components.

Third, observe that each component of (N, EP , ∅) has to be incident to at least k + 1 non-protected links, otherwise A can disconnect the protected network s D with k attacks. Since there are n -p such components, n1(p, k) is the minimal number of non-protected links to form. In the following example, we illustrate that there exist some values of p and k for which n1(p, k) non-protected links are sufficient to resist k attacks.

Example 1 Suppose N = 1, 10 , k = 6 and p = 5. We describe a strategy s D where #E D N P = n1 [START_REF] Brown | Defending critical infrastructure[END_REF][START_REF] Cabrales | Risk-sharing and contagion in networks[END_REF]. Consider the networks of Figure 2 and s D the protected network such that g , g , g are all subnetworks of s D , with E D P = EP (g ) and E D N P = ENP (g ) ∪ ENP (g ). Note that subnetwork g is a complete network and g is a (3, 5)-Harary-network. Finally, we observe that each component in (N, EP , ∅) is incident to at least 7 non-protected links and there is no possibility for A to disconnect s D with 6 attacks.

E N P = E N P (g ) ∪ E N P (g ).
Recall that each component of (N, EP , ∅) has to be incident to at least k + 1 non-protected links in order to resist k attacks. This fact implies that for some parameters p and k, networks in S D p,k contains n2(p, k) non-protected links. We illustrate these cases through the following example.

Example 2 Suppose N = 1, 10 , k = 7, and p = 2. We assume that D forms a protected network s D in S D p,k , with a protected link between nodes 1 and 2 and between nodes 3 and 4. Then s D contains 8 components. We denote by C the component which contains nodes 1 and 2, and by C the component which contains nodes 3 and 4. Each of these components has to be incident to 8 non-protected links. Networks g and g given in Figure 3 are subnetworks of s D , with E D P = EP (g ) and E D N P = ENP (g ) ∪ ENP (g ). Each node a ∈ 5, 10 can form at most 5 non-protected links with each other. Hence each of them has to form at least 3 non-protected links with nodes in 1, 4 . Altogether, nodes 5, 6, 7, 8, 9 and 10 have to form a total of 3 × 6 = 18 non-protected links with nodes 1, 2, 3 and 4. As for components C and C , they should be incident to a total of 16 non-protected links. Hence, D cannot form a protected network with n1(2, 7) protected links that resists k attacks. More precisely, a network that cannot be disconnected by A with 7 attacks has to contain 18 + (5 × 6)/2 = 33 non-protected links while n1(2, 7) = 32. In Example 2, we have assumed that D uses protected links to form two components of size two in (N, EP , ∅). Now, assume instead that (N, EP , ∅) has a unique component of size strictly greater than 1. For instance, D forms protected links between nodes 1 and 2 and between nodes 2 and 3. Then, each node a ∈ 4, 10 can form at most 6 non-protected links with other nodes in 4, 10 . Consequently, since k = 7 each node a ∈ 4, 10 has to form at least 2 non-protected links with nodes in 1, 3 . The component which contains nodes 1, 2 and 3 is incident to at least 14 non-protected links. It follows that D forms 21 + 14 = 35 non-protected links instead of 33 links in Example 2. This example illustrates how D designs (N, EP , ∅) in order to minimize the costs of forming links.

We now generalize Example 2 to provide some intuition for p1(k, n) and p2(k, n). Consider a protected network in S D p,k where each component of (N, EP , ∅) contains either one or two nodes. There are thus n -2p components of size 1 and p components of size 2. We observe that components of size 1 need to be incident to at least k+1 non-protected links. Since the number of links between a component of size 1 and other components of size 1 is at most (n-2p-1), the total number of non-protected links between components of size 1 and those of size 2 is at least equal to (n-2p)((k +1)-(n-2p-1)). Moreover, to minimize the number of links, the total number of the non-protected links incident to components of size 2 should be equal to (k+1)p. Let x1 and x2 be the roots (when they exist) of (n-2x)((k+1)-(n-2x-1)) = (k+1)x. Since p1(k, n) = x1 + 1 and p2(k, n) = x2 -1, the number of non-protected links required to resist k attacks is given by n2(p, k)

when p ∈ 0, n -2 ∩ p1(k, n), p2(k, n) .
We now characterize the SPE according to the costs of forming protected and non-protected links.

Proposition 2 Let the payoff functions be given by equations (4) and (5), and let (s D , s A ) be an SPE. 16 1. Suppose that n(k + 1) mod 2 = 0. 16 The case of equality follows the same pattern, that is:

1. If n(k + 1) mod 2 = 0 and c P c L = n n-1 k+1 2 , then s D ∈ S D n-1,k ∪ S D 0,k and s A (s D ) = ∅. 2. Suppose that n(k + 1) mod 2 = 1. (a) If c P c L = n-1 n-2 k+1 2 , then s D ∈ S D n-1,k ∪ S D 1,k and s A (s D ) = ∅. (b) If k+2 2 = c P c L , then s D ∈ S D 0,k ∪ S D 1,k and s A (s D ) = ∅. (a) If c P c L < n n-1 k+1 2 , then s D ∈ S D n-1,k and s A (s D ) = ∅. (b) If n n-1 k+1 2 < c P c L , then s D ∈ S D 0,k and s A (s D ) = ∅.
2. Suppose that n(k + 1) mod 2 = 1.

(a) If c P c L < n-1 n-2 k+1 2 , then s D ∈ S D n-1,k and s A (s D ) = ∅. (b) If n-1 n-2 k+1 2 < c P c L < k+2 2 , then s D ∈ S D 1,k and s A (s D ) = ∅. (c) If k+2 2 < c P c L , then s D ∈ S D 0,k and s A (s D ) = ∅.
Proof Let ∆ = (3k + 5) 2 -8n(k + 1), by straightforward calculations, we have 4 n-3 k-5-

√ ∆ 8 ≥ 0. Hence, we have either p1(k, n) = p2(k, n) = -1, or p1(k, n) ≥ 1. Therefore, from Proposition 1, if D builds a protected network in S D 0,k , then her cost equals C (0, k) = n1(0, k)cL. Similarly, by Proposition 1, C (n -1, k) = (n -1)cP . Moreover, by Lemma 3, we know that n2(p, k) ≥ n1(p, k) when p ∈ p1(k, n), p2(k, n) . Hence by Proposition 1, for all p ∈ 1, n -2 , C (p, k) ≥ n1(p, k)cL + pcP .
We prove successively the two parts of the proposition.

1. Let n(k + 1) mod 2 = 0. For p ∈ 1, n -2 , C (p, k) -C (0, k) ≥ p(cP -cL(k + 1)/2) > 0, if cP /cL > (k + 1)/2. Moreover, C (n -1, k) -C (0, k) > 0 if cP /cL > n n-1 k+1 2 . Assume that cP /cL > n n-1 k+1 2
. Then, cP /cL > (k + 1)/2 and s D ∈ S D 0,k .

For p ∈ 1, n -2 , C (p, k) -C (n -1, k) > 0 if cP /cL < n-p n-p-1 k+1 2 . Assume that cP /cL < n n-1 k+1 2 . Then, cP /cL < n-p n-p-1 k+1 2 for all p ∈ 1, n -2 . Consequently, s D ∈ S D n-1,k . By assumption, C (0, k) < 1 and C (n -1, k) < 1. It follows that D has an incentive to build a protected network in S D 0,k or S D n-1,k since she obtains benefits equal to 1. Hence, A cannot disconnect s D with k attacks. Consequently, s A (s D ) = ∅.
2. Let n(k + 1) mod 2 = 1. By Proposition 1, we know that:

C (0, k) -C (1, k) > 0 if cP /cL < (k + 2)/2, C (1, k) -C (n -1, k) > 0 if cP /cL < n-1 n-2 k+1 2
, and

C (0, k) -C (n -1, k) > 0 if cP /cL < 1 n-1 n(k+1) 2
.

By using the same argument as in the previous point, we establish that for p ∈ 2, n -2 , if s D ∈ S D p,k , then s D is not an optimal strategy for D. Assume that cP /cL < n-1 n-2 k+1 2

. Then

cP /cL < n n-1 k+1 2 and s D ∈ S D n-1,k . Assume that cP /cL > n-1 n-2 k+1 2
. There are two

possible cases. If cP /cL < (k + 2)/2, then C (1, k) -C (n -1, k) < 0 and C (1, k) -C (0, k) < 0, and s D ∈ S D 1,k . If cP /cL > (k + 2)/2, then C (0, k) -C (n -1, k) < 0 and C (0, k) -C (1, k) < 0, and s D ∈ S D 0,k . Since D has an incentive to build a network s D in S D 0,k , S D 1,k or S D n-1,k , A cannot disconnect s D with k attacks. Consequently, s A (s D ) = ∅.
Let us provide the intuition of Proposition 2. Note that if D builds a protected network that A cannot disconnect with k attacks (which is the maximal number of attacks that A has an incentive to choose), then A attacks no link in an SPE since each attack is costly. Also, due to the costs of forming protected and non-protected links, in an SPE D always has an incentive to build a protected network that A cannot disconnect.

We now compare the costs of protected networks that belong to different sets S D p,k , p ∈ 0, n -1 , with respect to the values of cL and cP . First, we consider point 1 of Proposition 2: n(k + 1) mod 2 = 0. In Figure 4, we draw lines (d p,p ) whose slopes σ p,p can be interpreted as the average number of non-protected links that each protected link allows to save between a protected network in S D p,k , p ∈ 0, n -1 , and a protected network that belongs to S D p ,k , p = p. We draw four such lines:

• Line (d 0,p ) whose slope σ 0,p shows the average saving of non-protected link per protected link between networks in S D 0,k and those of S D p ,k , for p ∈ 1, n -2 \ p1, p2 , and similarly: • Line (d0,p) of slope σ0,p between networks in S D 0,k and in S D p,k , with p ∈ 0, n -2 ∩ p1, p2 • Line (d0,n-1) of slope σ0,n-1 between networks in S D 0,k and in

S D n-1,k . • Line (d n-1,p ) of slope σ n-1,p between networks in S D n-1,k and in S D p ,k , with p ∈ 1, n -2 .
Observe that for any p ∈ 1, n -2 \ p1, p2 and any p ∈ 0, n -2 ∩ p1, p2 , abs(σ0,p) < abs(σ 0,p ). Similarly, for any p ∈ 1, n -2 \ p1, p2 , abs(σ 0,p ) < abs(σ0,n-1). Moreover, for any p ∈ 1, n -2 , abs(σ0,n-1) < abs(σ n-1,p ).

Suppose cP /cL > abs(σ0,n-1). Then, costs of forming links with a strategy in S D 0,k are lower than the costs of forming links with a strategy in S D n-1,k . Moreover, cP /cL > abs(σ0,n-1) > abs(σ 0,p ) > abs(σ0,p), with p ∈ 1, n -2 \ p1, p2 and p ∈ 0, n -2 ∩ p1, p2 . It follows that the costs of forming links are minimized for strategies in S D 0,k . Conversely, suppose cP /cL < abs(σ0,n-1). Then cP /cL < abs(σ n-1,p ), for p ∈ 1, n -2 . It follows that the costs of forming links are minimized for strategies in

S D n-1,k . Finally, note that abs(σ0,n-1) = n n-1 k+1 2
.

Average number of non-protected links We now consider the second part of Proposition 2: n(k + 1) mod 2 = 1. The intuition is similar to the case where n(k + 1) mod 2 = 0 except for protected networks which belong to S D 0,k and S D 1,k . Consequently, we focus only on three sets of protected networks: S D 0,k , S D 1,k and S D n-1,k . In Figure 5, the slope σ0,1 of (d0,1), can be interpreted as the number of non-protected links that the protected link allows to save between a protected network in S D 0,k and a protected network in S D 1,k . The same interpretation is valid for the slope σ1,n-1 of (d1,n-1), which relates a protected network in S D 1,k and a protected network in S D n-1,k , and for the slope σ0,n-1 of the line (d0,n-1), which relates a protected network in S D 0,k and a protected network in S D n-1,k . Suppose that cP /cL < abs(σ1,n-1). Then, cP /cL < abs(σ0,n-1), and networks in S D n-1,k have a minimal link formation cost. Conversely, suppose that cP /cL > abs(σ1,n-1). If k < n -3, 17 then there

p p 1 p p 2 (d 0,p ) (d 0,p ) (d 0,n-1 ) (d n-1,p ) p n -2 n -1
17 For k = n -3, k+2 2 = n-1 n-2 k+1 2
, and thus the case 2.(b) of Proposition 2 never occurs.

are two possibilities. If cP /cL > abs(σ0,1), then protected networks in S D 0,k minimize the cost of forming links. If cP /cL < abs(σ0,1), then protected networks in S D 1,k minimize the cost of forming links. Finally, note that abs(σ0,1) = (k + 2)/2, and abs(σ1,n-1) = n-1 n-2 k+1 2

.

Average number of non-protected links

p 1 n -1 (d 1,n-1 ) (d 0,1 ) 0 (d 0,n-1 )
Figure 5: Intuition of Proposition 2 when n(k + 1) mod 2 = 1 and k < n -3.

We now compare the results obtained in our framework where A attacks links and the results obtained in DG's framework where A attacks nodes (Proposition 1 in [START_REF] Dziubiński | Network design and defense[END_REF]). Recall that in DG's paper, the nonempty networks formed by D at equilibrium are either a star network with a protected central node, or a minimal (k + 1, n)-node-connected network without any protection. Hence, (s D , ∅), with s D ∈ S D 0,k , is an SPE when the cost of links (non-protected links in our case) is sufficiently low relatively to the cost of protection in both frameworks.

However, when A attacks nodes, D uses at most one protected node at equilibrium. The role played by the protections is different since in DG, if D builds a star network, one protection is sufficient to protect the network and resist any attack of A. By contrast, in our framework, D may use more than one protected link in an SPE: indeed, when the cost of protected links is sufficiently low relative to the cost of non-protected links, D designs a (1, n)-link-connected network which contains n -1 protected links. Protecting a network under link-attack is thus more costly than protecting a network under nodeattack. This is because our framework calls for the survival of every node, a requirement which does not hold in the DG's framework.

Limited number of protected links and imperfectly protected links

In this section, we consider two potential types of restrictions on the protection of the network for the Designer. First, we consider the case where D can only use a limited number of protected links and we focus on situations where this number is smaller than p2(k, n). Then, we consider a framework where links are imperfectly protected and can be removed by the Adversary with some a priori known probability π ∈ (0, 1).

Limited number of protected links

We examine a framework where the maximal number of protected links, p, that D can form is strictly smaller than n -1. More precisely, we are interested in the case where p ∈ p1(k, n), p2(k, n) . 18Proposition 2 establishes that for n(k + 1) mod 2 = 0, there exists no SPE in which D uses both protected and non-protected links. In contrast, when p ∈ p1, p2 , there exist values where the SPEs are of the form (s D , ∅) with s D ∈ S D p 1 -1,k . Note that networks in S D p 1 -1,k contain both protected and nonprotected links when p1 > 1. 19 The following proposition gives a condition on the values of the parameters upon which such situations arise. To simplify the analysis, we assume that (k + 1) mod 2 = 0. Proposition 3 Assume that (k + 1) mod 2 = 0 and n < (3k + 5) 2 /(8(k + 1)). Assume further that p1 > 1, p2 -p1 ≥ 2 and that the maximal number of protected links is p ∈ p1, p2 . Let (s D , s A ) be an SPE. There exists ε > 0 such that if

(k + 1)/2 -ε < cP /cL < (k + 1)/2, then s D ∈ S D p 1 -1,k and s A (s D ) = ∅. Proof If p1 > 1, for all p ∈ 1, p1 -1 , C (0, k) -C (p, k) = p( k+1 2 cL -cP ). If cP /cL < (k + 1)/2, then C (0, k) -C (p, k) > 0. Therefore, if cP /cL < (k + 1)/2, then arg min p∈ 0,p 1 -1 {C (p, k)} = p1 -1. Now, let p ∈ p1, p . We have C (p, k) -C (p1 -1, k) = (p -p1 + 1)cP + n2(p, k) -n1(p1 -1, k) cL. Consider ε = k+1 2 -max p∈ p 1 , p { n 1 (p 1 -1,k)-n 2 (p,k) p-p 1 +1
}. Since p1 -1, p is a discrete non-empty set, then

ε is well defined. If (k + 1)/2 -ε < cP /cL, then C (p, k) -C (p1 -1, k) > (p -p1 + 1)((k + 1)/2 - ε) + n2(p, k) -n1(p1 -1, k) cL ≥ (p -p1 + 1) n 1 (p 1 -1,k)-n 2 (p,k) p-p 1 +1 + n2(p, k) -n1(p1 -1, k) cL = 0. Thus, arg min p∈ p 1 -1, p {C (p, k)} = p1 -1. It remains to show that ε > 0. If p ∈ p1 -1, p , then (n -2p)((k + 1) -(n -2p -1)) > (k + 1)p. Moreover, by straightforward calculations if (k+1) mod 2 = 1 and (n-2p)((k+1)-(n-2p-1)) > (k+1)p, then n2(p, k) > n1(p, k). Thus n1(p1 -1, k) -n2(p, k) p -p1 + 1 < n1(p1 -1, k) -n1(p, k) p -p1 + 1 ≤ (k + 1)(n -p1 + 1 -n + p) 2(p -p1 + 1) = k + 1 2 .
Since this holds for any p ∈ p1, p , then ε > 0.

Finally, since (i) s D ∈ S D p 1 -1,k , (ii) any network in S D p 1 -1,k cannot be disconnected with k attacks and (iii) attacks are costly for A, then s A (s D ) = ∅. 19 Indeed, note that p 1 ≤ 4n 8 + 1 ≤ n -1 since n ≥ 4 and therefore S D p 1 -1,k always contains non-protected links.

p 1 p p 2 x → n 1 (x, k) x → n 2 (x, k) c P /c L = 18 c P /c L = 12 c P /c L = 8

13

We illustrate this result with an example:

Example 3 Suppose that n = 31 and k = 27. Then, p1 = 3 and p2 = 7. Let p = 6. Figure 6 shows the number of non-protected links in networks of S D p,k as a function of the number of protected links (large dots in red).

Let us consider the following function:

ENP : x →      n1(x) = (n -x)(k + 1) 2 if x ∈ [0, p1) ∪ (p2, n -2], n2(x) = (n -2x) k + 1 - n -2x -1 2 otherwise.
Note that since (k+1) mod 2 = 0, then for any p ∈ 1, n-2 we have n1(p) = n1(p, k), n2(p) = n2(p, k) and ENP (p) = #ENP (s D ) for any s D ∈ S D p,k . Therefore the functions n1, n2 and ENP can be interpreted as the natural continuous extensions of p → n1(p, k), p → n2(p, k) and p → #ENP (s D ), s D ∈ S D p,k , respectively. The functions n1 and n2 are plotted in green and blue plain lines respectively in Figure 6.

Let us consider a value of cP and cL. The lines of equal costs (isocost lines) have slope -cP /cL, thus have equations of the type

y = c cL -p cP , (Iso)
with c cL being the y-coordinate of the y-intercept. The value of c corresponds to the associated cost for the Designer normalized by cL.

The optimal cost for D corresponds to the smallest value c such that the associated element of (Iso) intersects with the plot of ENP for some integer value p. Then, the optimal strategies of D belong to S D p,k .

Figure 6 shows the optimal strategies of D for three different values of cP /cL, namely 18, 12 and 8 (in dashed lines):

For large values of cP /cL (value 18 in Figure 6) the slope of the line of (Iso) is larger (in absolute value) than that of n1 and thus the optimal strategy for D is obtained with p = 0 protected links.

In other words, if cP /cL > k+1 2 , then the optimal strategies for D belong to S D 0,k . For small values of cP /cL (value 8 in Figure 6) the slope of the line (Iso) is low, hence favoring strategies with maximal values of p. In Figure 6, one can see that for cP /cL = 8, the optimal strategy for the Designer is obtained for p = p protected links.

For intermediate values of cP /cL (value 12 in Figure 6) the optimal strategy for the Designer is obtained when using p1 -1 protected links, which is the inflection point of ENP .

DG [START_REF] Dziubiński | Network design and defense[END_REF] show that when A attacks nodes, there exist situations where the optimal strategy of D is a star network with a protected central node. In this case, D uses both node protections and link creations to protect her network. In our framework, D may use both protected and non-protected links to protect her network if the number of protected links available to D belongs to p1, p2 . This result is a consequence of the discontinuity in the number of non-protected links that each protected link allows the Designer to save (given that D builds a network that resists k attacks).

Imperfectly protected links

We now assume that each protected link has a probability π ∈ (0, 1) to be removed when it is attacked by A. Let g = (N, EP , ENP ) be an (imperfectly) protected network, and E A an attack over the links of g. In the benchmark model, g R is obtained by removing the links of ENP that are targeted by A, i.e. g R = (N, EP , ENP \E A ). Now, a realization of the attack, g , is a subnetwork of g R of the form g = (N, E , ENP \E A ) with E ⊆ EP \E A . We illustrate these networks in the following example.

Example 4 Suppose N = 1, 5 , ENP (g) = {13, 15, 25, 34, 35, 45}, EP (g) = {12, 24} and E A = {12, 34} (see Figure 4). The subnetwork g R obtained when removing the non-protected links that are attacked (i.e. E A ∩ ENP ), is drawn in Figure 7(ii). The two possible realizations are drawn in Figures 7(iii) and 7(iv). Note that g 1 occurs with probability 1 -π, and g 2 occurs with probability π. (iv) The other realization g 2 Let g be a realization and λ(g |g R , E A ) be the probability that g is realized given g R and E A . We have

λ(g |g R , E A ) = ij∈E P (g ), ij∈E D P ∩E A (1 -π) ij / ∈E P (g ), ij∈E D P ∩E A π.
The expected benefits obtained by D, Eφ(g R , E A ), when she builds a protected network g and A chooses

E A is Eφ(g R , E A ) = g =(N,E ,E D N P \E A ) E ⊆E D P λ(g |g R , E A )φ(g ).
We assume that the costs incurred by D when she chooses a strategy are given by equation ( 3), the costs incurred by A when she chooses a strategy are given by equation [START_REF] Baccara | How to organize crime[END_REF]. The expected payoffs obtained by D, EΠ D , is the difference between the expected benefits and the costs of forming protected and non-protected links:

EΠ D (s D , s A (s D )) = Eφ(g R , E A ) -c D (s D ). (8)
Finally, the expected payoffs obtained by A are

EΠ A (s D , s A (s D )) = 1 -Eφ(g R , E A ) -c A (s A (s D )). ( 9
)
Recall that cA ≥ 1/(n -3).

Proposition 4 Let the payoff functions be given by equations [START_REF] Cunningham | Optimal attack and reinforcement of a network[END_REF] and [START_REF] Dziubiński | Network design and defense[END_REF]. Suppose that π < cA. Then, results provided in Proposition 2 are preserved.

Proof Let s D = (N, EP , ENP ) and let s A (s D ) = E A with E A = (E A P , E A N P ), where E A P ⊆ EP and E A N P ⊆ ENP . If A can disconnect the protected network s D with E A = (∅, E A N P ), then her best response is to not attack any protected links, i.e. E A P = ∅, since attacks are costly. If A cannot disconnect the protected network s D with (∅, E A N P ), then (E A P , E A N P ) should disconnect the network with a strictly positive probability (otherwise A would not be playing a best response). The highest probability to disconnect network (N, EP , ENP ) occurs when the deletion of any protected link implies that (N, EP , ENP ) is disconnected. This probability is 1

-(1 -π) #E A P . Since 1 -π ∈ (0, 1), by Taylor's expansion 1 -(1 -π) #E A P = ∞ =0 #E A P (-1) +1 π .
Then by Leibniz's rule on alternating series 1 -(1 -π) #E A P ≤ π#E A P . Hence, A disconnects the network with a probability lower or equal to π#E A P when she attacks the links in E A . So, the expected benefits associated with E A are at most π#E A P with a cost of at least cA#E A P . Hence, if E A P = ∅ and π < cA, then the expected payoff associated to E A is (strictly) negative and thus A does not play a best response. Therefore E A P = ∅. Since no optimal strategy of A targets any protected link, the situation is equivalent to the one examined in Proposition 2. Proposition 4 examines situations where probability π is low relative to cA, the cost of attacking links. We now examine other situations through an example. Example 5 Suppose that N = 1, 5 and k = 2, thus the maximum number of attacks that A has an incentive to do is 2. To simplify the analysis, we assume that cP > (3/2)cL. Figure 8 shows the networks that maximize the expected payoff of D for different numbers of protected links p = 1, . . . , 5 and all of A potential best response attacks. As in the previous figures, the protected links are represented by thick lines and dashed lines identify the links potentially attacked by A. The captions represent the Designer's expected benefit. Depending on the value of cA, the Adversary may attack 0, 1 or 2 links leading to different values of D's expected benefit.

(i) 1 -8c L (ii) 1 -6c L -c P if π < 2c A 1 -π -6c L -c P otherwise. (iii) 1-5c L -2c P if π 2 < 2c A 1 -π 2 -5c L -2c P otherwise. (iv) 1 -3c L -3c P if π < 2c A 1 -π -3c L -3c P otherwise. (v) 1 -4c P if π(1 -π/2) < c A 1 -π -4c P if π(1 -π) < c A ≤ π(1 -π/2) (1 -π) 2 -4c P if c A ≤ π(1 -π) (vi) 1 -c L -4c P if π < 2c A 1 -π -c L -4c P otherwise. (vii) 1 -5c P if π 2 < 2c A 1 -π 2 -5c P otherwise.
Note that the (3,5)-Harary-network (in S D 0,k represented in Figure 8(i)) contains 0 protected links and 8 non-protected links and is fully protected against any attack of 2 links. Therefore, all other strategies that can be optimal for D induce networks which contain at most 7 links, which in turn implies that there exists at least one node of degree lower or equal to 2. Further, the expected benefit associated to any network for the Designer is always bounded by the probability of its weakest node to be disconnected. Hence, the expected benefits of any protected network not in S D 0,k are lower or equal to 1-π 2 . Figure 8(vii) shows a network with such expected benefits and 5 protected links. Since cP > cL, D has no incentive to form networks which contains 6 protected links or more. Based on these observations, Figure 8 contains all potential optimal strategies of D under imperfectly protected links.

Let us now focus on the optimal strategies of A. Networks 8(ii)-8(iv) and 8(vi)-8(vii) can only be disconnected if at least two links fail. Therefore the Adversary has no incentive to attack only 1 link in these networks. Further, since cP > (3/2)cL, we have 3cL + 3cP > 6cL + cP , and thus the strategy depicted in 8(iv) is never an optimal strategy for D. Further, suppose that for some value of π, the strategy of D depicted in Figure 8(iii) is optimal for D, then it has a greater or equal expected payoff than that of Figure 8(vii) and thus 5cL ≤ 3cP . But, then its expected payoff is no more than 1 -5cL -10cL/3 < 1 -8cL and thus is strictly dominated by strategy depicted in Figure 8(i) which is a contradiction. Thus, building the network of Figure 8(iii) is never an optimal strategy. It follows that only strategies depicted in Figures 8(i), 8(ii), 8(v), 8(vi) 8(vii) are candidate to be optimal for D.

Let us now compare these strategies with that of the case of perfectly protected links. From Proposition 2, since n(k+1) mod 2 = 1, three potential SPEs could occur, resulting in the networks of Figure 8(i), 8(ii) and 8(v). However, as in this case k = n -3, then protected networks in S D 1,k (depicted in Figure 8(ii)) are never optimal when π = 0 (as explained in Footnote 17). For small values of π, the networks of Figure 8(i) and 8(v) can occur. For instance for π = cA = 0.1 and cP = 0.2 and cL = 0.075, then the networks of S D 0,k are optimal, while for cP = 0.12 and cL = 0.075 the networks of S D n-1,k are optimal.

Note that in that cases, A does not attack any link in SPEs. Suppose that cP /cL > (k + 2)/2, then for perfectly protected links (i.e. π = 0), building the network of Figure 8(i) is an equilibrium strategy for D and an equilibrium strategy for A is to attack no link. Observe now that the expected payoff of D associated with this network is not modified when π changes, while her expected payoff associated with all other networks drawn in Figure 8(v) decreases with π and reaches negative values. Consequently, given cP and cL there exists a probability π such that for π > π strategies in S D 0,k are optimal for D. Moreover, for π = 0.45, cP = 0.113, and cL = 0.075 and cA = 0.2, the network of Figure 8(vii) is induced by an optimal strategy for D given that A chooses an optimal attack. Further, for cP = 0.12, cL = 0.075, π = 0.3 and cA = 0.2, the network of Figure 8(vi) is induced by an optimal strategy for D given that A plays an optimal strategy. Note that D never builds these protected networks in our benchmark model. 20Example 5 establishes three main insights. First, S D 0,k are the unique optimal strategies when π is sufficiently high. Second, there exist situations where the Designer's best strategy is to build a network where each node is incident to m protected links, with m = k. Note that since cP > cL, D has no incentive to form a protected network where each node is incident to k + 1 protected links. Third, there exist optimal strategies for D where nodes which belong to the same component in (N, EP , ∅) are linked with a non-protected link (see Figure 8(vi)) in an optimal strategy for D.

DG [START_REF] Dziubiński | Network design and defense[END_REF] examine the impact of imperfect defense in a framework where D protects nodes instead of links. They use an example and provide two insights. First, there exist parameters such that the SPEs obtained in the perfect defense model remain equilibria in the imperfect defense model, namely the empty network, the center protected star, and the minimal (k + 1, n)-node-connected networks. Second, they establish that richer strategies than those played by D in the perfect defense model may appear in equilibrium. In particular, for some parameters an optimal strategy for D is to protect several nodes and create a network which generalizes the center protected star network, or to design a (2, n)-node-connected network and to protect all the nodes.

It is worth noting that imperfect defense has the same type of impact in the framework of DG and in our framework. First, if the probability of successful attacks π is sufficiently high and the cost of forming non-protected links is sufficiently low, then strategies in S D 0,k are the unique optimal strategies for D. Second, the set of strategies candidate to be an equilibrium is larger in the imperfect defense framework than in the perfect defense framework. In particular, for sufficiently high π, D has an incentive to use more protections than in a situation where π = 0: there exist parameters where D protects all the nodes in DG's framework, and there exist parameters where D designs a network where each node is incident to k protected links in our framework. Third, in both frameworks it is difficult to obtain general results when imperfect defense is introduced. However, Landwehr [START_REF] Landwehr | Network design and imperfect defense[END_REF] provides equilibrium strategies for D when the number of attacks is very small. In particular, he establishes that if k = 2, then there exist 6 types of strategies that D may play in equilibrium according to the value of π, cP , and cL.

Conclusion

In this paper, we have studied the optimal way to design and protect a network under strategic link attacks. In our benchmark model, the number of protected links available for the Designer is not bounded, and protected links cannot be removed by the Adversary. Our main findings in this model are the following. In equilibrium, three types of networks may arise according to the value of the parameters of the model (which are the number of nodes and the costs of link creation and attack). First, if the relative cost of protections (cost of a protected link/cost of a non-protected link) is low comparatively to the number of attacks, then D forms a (1, n)-link-connected network which contains only protected links. Second, if the relative cost of protection is high in regards to the number of attacks, then the Designer forms a minimal (k + 1, n)-connected network which contains only non-protected links. Third, for intermediate relative costs of protection, there exist situations where the Designer forms a network which contains one protected link and (n -1)(k + 1)/2 non-protected links. To sum up, in this paper we provide the minimal costs that D incurs to protect her network against an intelligent attack (i.e. the worst attack).

We have also examined a framework where the number of protected links available for the Designer is limited. In that case, we have established that for intermediate relative costs, the Designer forms a network which contains several protected and non-protected links. Finally, we have discussed the case of imperfectly protected links. We cannot provide a full characterization of the SPEs in the imperfect defense model, but we have given conditions under which results obtained in the framework with perfect defense are preserved. Moreover, we have established through an example that the set of equilibria is larger in the framework with imperfect defense links than in the framework with perfect defense.

In this paper, we have assumed that the Designer incurs the same costs if she forms protected links that are adjacent and if they are not adjacent. It would be interesting to examine a situation where it is more costly for the Designer to form protected links that are not adjacent. As we explained after Example 2, if D protects adjacent links, it can lead her to form strictly more non-protected links than in the optimal strategies described in Proposition 1.

Adding constraints on the location of protected links can be applied in different contexts. Indeed, it is more costly for a company to protect some cables (by reinforcing them or replacing them with new equipments) in different locations. For instance, the company has to send several teams of workers to protect cables which are far from each other instead of a single team when they are close to each other.

We define the adjacency matrix M(ĝ) of a multigraph ĝ = ( N , Ê, ψ) as ∀(a, b) ∈ Ê2 , M a,b (ĝ) = #{e ∈ Ê : ψ(e) = (a, b)}, i.e. the number of links between nodes a and b in ĝ. Note that the adjacency matrix of an undirected multigraph is symmetric. We note | • | the sum of elements of a matrix or a vector, that is, for any matrix A ∈ 1, a × 1, b , |A| = i∈ 1,a ,j∈ 1,b Ai,j.

Contractions of networks.

Let g be a network. Given a link ij ∈ E(g), the network g ij is obtained by contracting the link ij; that is, by merging the two nodes i and j into a single node {i, j}, and making any node a adjacent to the (new) node {i, j} in g ij if and only if a is adjacent to i or j in the network g. In other words, all links, other than those incident to neither i nor j, are included in E(g ij) if and only if they are included in E(g). For any set F ⊆ E(g), we define the F -contraction of network g and denote by ĝF the network obtained from g by sequences of link contractions for all links in F . Note that the resulting network does not depend on the order of links contractions. In particular, we are interested in the case where F = EP (g), that is the contraction over all protected links of the network. We illustrate the EP -contraction of a network g in Figure 9. Multigraphs and E P -contractions of networks. Let g = (N, EP , ENP ) be a protected network and Γ1(g), . . . , Γ (g), . . . , Γν (g) be the components of the subnetwork (N, EP , ∅) with γ (g) the number of nodes of the component Γ (g). When no confusion is possible, we simplify notations by removing (g). By construction, the EP -contraction of g is ĝE P = ( 1, ν , Êg, ψg) with Êg = {eij : ij ∈ ENP (g)} and

∀(a, b) ∈ 1, ν 2 , ∀i ∈ Γa(g), ∀j ∈ Γ b (g), ψg(eij) = (a, b).
Note that a protected network g induces one and only one EP -contraction ĝE P (up to ordering). However the converse is not true: a multigraph can be the EP -contraction of two (or more) distinct protected networks. However, these graphs have the same number of non-protected links (which is given by a,b∈ 1,ν 2 M a,b (ĝ E P )), and the same minimum number of protected links (which is equal 22 to n-ν). Therefore, all protected networks resulting in a given EP -contraction have the same minimal cost.

An optimal strategy for the Designer is the choice of vector (Γ (g)) 1≤ ≤ν and matrix M(g), that is the number and size of the components and the number of non-protected links, under some constraints, which we develop below: Lemma 2 For a given number of components ν, an optimal strategy for D is a solution of the following optimization problem:

min γ∈N ν , M∈N ν×ν 1 2 i∈ 1,ν j∈ 1,ν Mi,j s.t.                                        ∀(i, j) ∈ 1, ν 2 , Mi,j = Mj,i, ∀(i, j) ∈ 1, ν 2 , Mi,j ≤ γiγj, ∀i ∈ 1, ν , Mi,i ≤ γi(γi -1)/2 -(γi -1), ∀I ⊆ 1, ν , i∈I j∈ 1,ν \I Mi,j ≥ k + 1, n = i∈ 1,ν γi. (CS-1) (CS-2) (CS-3) (CS-4) (CS-5) Proof Consider any matrix M = (Mi,j) i∈ 1,ν , j∈ 1,ν . Build N = 1, ν , Ê = ∪ (i,j)∈ N × N Êij, with Êij = {e 1 ij , . . . , e M i,j ij
}, and ψ(e) = (i, j) if and only if e ∈ Êij. The triplet ( N , Ê, ψ) is an (undirected) multigraph if and only if the links are undirected (constraint (CS-1)).

In turns, this multigraph is the EP -contraction of a protected network g = (N, EP , ENP ), such that (N, EP , ∅) has ν components of size γ1, γ2, . . . , γν , if and only if all nodes of g belong to exactly one component (constraint (CS-5)), if each node in one component is connected to any other node in a different component by at most one link (constraint (CS-2)), and if the network does not contain any loop. The latter requires that each node in a component Γi is linked with at most γi -1 nodes which belong to Γi. From Lemma 1, each component of size γi contains exactly γi -1 protected links (since it is connected and does not contain any loops). This is reflected in constraint (CS-3).

The goal of the Designer is to minimize her number of non-protected links, which are given by

1 2 i∈ 1,ν j∈ 1,
ν Mi,j. Finally, no component of (N, EP , ∅) should be vulnerable to an attack of A, that is, every component of (N, EP , ∅) should be incident to at least k + 1 non-protected links in g: this means that ∀i ∈ 1, ν , j∈ 1,ν \{i} Mi,j ≥ k + 1. This should also hold for any group of components, as reflected by constraint (CS-4).

This formulation allows us to directly derive a lower bound on the number of (non-protected) links that are necessary in the construction of a network that resists k attacks. We will show in the subsequent paragraphs that this bound can be reached under some assumptions on n, ν and k (Lemmas 5 and 9).

Lemma 3

The number of non-protected links induced by any strategy is at least

n 1 = ν(k + 1) 2 .
Proof This is a direct consequence of constraint (CS-4). Indeed, for any i, eq. (CS-4) implies that

j∈ 1,ν ,j =i Mi,j ≥ k + 1. Therefore, i∈ 1,ν j∈ 1,ν Mi,j ≥ i∈ 1,ν (k + 1) = ν(k + 1).
In the rest of the proof, we provide, for each number of components ν, the optimal value of the optimization problem given in Lemma 2 as well as the corresponding optimal vector γ and matrix M. The constructions will rely heavily on the following definitions:

α1 = n ν , α2 = n mod ν, β1 = k + 1 ν -1 , and β2 = (k + 1) mod (ν -1). (11)
Note that by construction n = α1ν +α2 and k +1 = β1(ν -1)+β2. Also, one specific vector of component sizes, γ = (γ 1 , . . . , γ ν ), will come in handy in the proofs. Consider

γ i = α1 if i ≤ ν -α2, and α1 + 1 otherwise. ( 12
)
Then i∈ 1,ν γ i = α1(ν -α2) + (α1 + 1)α2 = α1ν + α2 = n, which satisfies constraint (CS-5).

Roughly speaking, if we create ν almost equally sized components over n nodes, then there will be ν -α2 components of size α1 = n ν and α2 components of size α1 + 1 (this is reflected in the definition of γ). Consider one of the ν components. Recall that we have to satisfy (CS-4). If we distribute k + 1 links between this component and the (ν -1) others in a way as balanced as possible, then ν -1 -β2 components will be incident to β1 = k+1 ν-1 links and β2 components will be incident to β1 + 1 links to the considered component.

We distinguish two cases depending on the values of α1 and β1, that lead to different constructions and optimal numbers of non-protected links. These two cases depend on the average size of the components relatively to the number of required links.

B Solution of the case where

α 2 1 ≥ β 1 + 1.
Intuitively, in this case, the average size of the components is high enough compared to the number of required links. Thus, we are able to form a sufficient number of links incident to each component without contradicting constraint (CS-2). In this case, an optimal matrix M that reaches the lower bound given by Lemma 3 can be built. It relies on the matrices of (a, b)-Harary-networks H(a, b) (for any a < b). In the following paragraph, we give the general formula of the adjacency matrices obtained by the construction of Harary [START_REF] Harary | The maximum connectivity of a graph[END_REF]. Consider the squared matrices D(b) of size b which are defined by D(b)i,j = 1 if (j -i) mod b = 1 and 0 otherwise. Similarly, the squared matrices E(b) of size b which are defined by E(b)i,j = 1 if j -i = 1 and 0 otherwise. That is, Then, following the processes provided by Harary [START_REF] Harary | The maximum connectivity of a graph[END_REF], when a ∈ 2, b-1 , a matrix of a (a, b)-Hararynetwork is given by:

D(b) =         0 1 0 1 0 . . . . . . 0 0 1 1 0         and E(b) =         0 1 0 1 0 . . . . . . 0 0 1 0         .
H(a, b) =            a/2 i=1 F(i, b) if a mod 2 = 0, a/2 i=1 F(i, b) + G b 2 , b if a mod 2 = 1.
We also consider the situation where a = 1, and we assume that matrix H(1, b) is given by the previous formula, i.e.

H(1, b) = G b 2 , b .
We have the following important lemma which is a very slight extension of Harary [START_REF] Harary | The maximum connectivity of a graph[END_REF]. Lemma 4 If ab mod 2 = 0 then each node of the network whose adjacency matrix is H(a, b) has a degree of a. Otherwise, all nodes have a degree of a except for the node b/2 + 1, that has a degree of a + 1. Consequently, for any a and b, we have

|H(a, b)| = ab if ab mod 2 = 0, ab + 1 if ab mod 2 = 1.
Lemma 6 If 2ν ≤ n, then α 2 1 ≥ β1 + 1. Thus, if 2ν ≤ n, then any optimal strategy has exactly n 1 non-protected links.

Proof Indeed, 2ν ≤ n ⇒ ν(2ν -n) ≤ 2(2ν -n) ⇒ 2ν 2 + 2n ≤ nν + 4ν ⇒ νn -2ν ≤ 2nν -2n -2ν 2 + 2ν ⇒ ν(n -2) ≤ 2(n -ν)(ν -1) ⇒ n -2 ν -1 ≤ 2(n -ν) ν . Hence k + 1 ν -1 ≤ n -2 ν -1 ≤ 2 n ν -2. Thus, if 2ν ≤ n, then n ν ≥ 2 and hence n ν 2 ≥ 2 n ν > 2 n ν -1 ≥ k+1 ν-1 . Finally n ν 2 ≥ k+1 ν-1 + 1.
C Solution of the case where α 2 1 < β 1 + 1.

Intuitively, in this case, the average size of the components is low compared to the number of required links. However, small sized components cannot bear too many multiple links. Thus, the constraint (CS-2) may be harder to satisfy. More precisely, with the condition that α 2 1 < β1 + 1, the construction based on Harary networks of Lemma 5 is no longer valid (it violates constraint (CS-2)).

By Lemma 6, when α 2 1 < β1 + 1, we have 2ν > n and thus α1 = 1 and α2 = n -ν. To provide a lower bound on the minimal number of links required for the network to resist k attacks, we need to establish bounds concerning δ, the number of components of size 1 in a network at equilibrium. More precisely, we successively establish that δ ≥ 2ν -n and δ ≤ k + 1.

Let γ = (γ1, . . . , γν ) be any (non-decreasing) vector satisfying constraint (CS-5). Then, γ1 = 1, otherwise we would have i∈ 1,ν γi ≥ 2ν > n = i∈ 1,ν γi which is impossible. Let δ be such that for all i ≤ δ, γi = 1 and for all i > δ, γi > 1. Hence, δ is the maximal number such that γ δ = 1. Note that n = i∈ 1,ν γi = δ + i∈ δ+1,ν γi ≥ δ + 2(ν -δ). We have δ < ν since ν < n as there exists at least one protected link. Hence, δ ≥ 2ν -n. Finally, α 2 1 < β1 + 1 gives β1 ≥ 1 and thus k + 1 ≥ ν -1 which implies k + 1 ≥ δ by definition of δ as soon as ν < n (that is, there exists at least 1 protected link).

Up to a reordering of the nodes, any solution matrix M has the following form:

M =      δ A ν -δ B B C      δ ν -δ . ( 13
)
Note that adjacency matrix A captures links between nodes in 1, δ , that is components of size 1. Adjacency matrix B captures links between nodes in 1, δ and nodes in δ + 1, ν (we will see below that nodes in δ + 1, ν are identified with components of size 2). Finally, adjacency matrix C captures links between nodes in δ + 1, ν .

In the next lemma, we establish that if α 2 1 < β1 + 1, then the number of non-protected links may be strictly higher than n 1 .

Lemma 7 If α 2 1 < β1 + 1 then the required number of non-protected links is at least:

• n 2 = (2ν -n)(k + 1) -(2ν-n)(2ν-n-1) 2 if (3ν -2n)(k + 1) > (2ν -n)(2ν -n -1).
• n 1 otherwise.

Proof The bound n 1 has been established in Lemma 3. Further, in the case of α 2 1 ≥ β1 + 1, the optimal bound of n 1 can be achieved (Lemma 5) because the elements of each row of M add up to k + 1 with at most one row whose elements add up to k + 2.

From eq. ( 13), constraint (CS-2) imposes that each row of A adds up to at most δ-1. Thus, to comply with constraint (CS-4), the elements of each row of B need to add up to at least k + 1 -(δ -1). Thus, the total sum of elements of matrix B, that is, |B| is at least δ(k + 1 -(δ -1)). Thus, the total number of

links required is |M| 2 ≥ (|A|+|B|)+|B | 2 ≥ δ(k+1)+|B| 2 ≥ δ(k+1)+δ(k+1-(δ-1)) 2 = δ(k + 1) -δ(δ-1) 2 .
The function δ → δ(k + 1) -δ(δ-1) 2 is concave, quadratic and its maximum is obtained at k + 3/2; so this function is increasing in the interval [2ν -n, k

+ 3/2]. Since 2ν -n ≤ δ ≤ k + 3/2, then |M| 2 ≥ (2ν -n)(k + 1) -(2ν-n)(2ν-n-1) 2 = n 2 .
This bound is attained when the sum of elements of each row of B is larger than or equal to k + 1 (hence leading to a zero matrix C). This happens necessarily when |B| ≥ (k + 1)(ν -δ), that is δ(k + 1 -(δ -1)) ≥ (k + 1)(ν -δ), i.e. (2δ -ν)(k + 1) ≥ δ(δ -1). Since δ ≥ 2ν -n, this implies that (3ν -2n)(k + 1) ≥ (2ν -n)(2ν -n -1). We now establish that n 1 occurs when (3ν -2n)(k + 1) = (2νn)(2ν -n-1). Suppose ν(k +1) mod 2 = 1 and (3ν -2n)(k +1) = (2ν -n)(2ν -n-1), by straightforward calculations we have n 2 < n 1 , a contradiction since by definition n 2 ≥ n 1 . Moreover, if ν(k+1) mod 2 = 0 and (3ν -2n)(k + 1) = (2ν -n)(2ν -n -1), then by straightforward calculations we have n 2 = n 1 . Finally, by straightforward calculations we have n 2 ≥ n 1 when (3ν -2n)(k + 1) > (2ν -n)(2ν -n -1). The result follows.

We now introduce the last two lemmas. In Lemma 8, we provide a construction that allows us to build exactly n 2 non-protected links for resisting k attacks when (2ν -n)(2ν -n -1) < (3ν -2n)(k + 1). Similarly, in Lemma 9 we provide a construction that allows us to build exactly n 1 links for resisting k attacks when (2ν -n)(2ν -n -1) ≥ (3ν -2n)(k + 1). The proofs of these lemmas rely on the properties of a type of matrices which we denote as Z ∈ N δ×(ν-δ) , Zi,j ∈ {0, 1}, that are such that:

∀i ∈ 1, δ , j∈ 1,ν-δ
Zi,j = (k + 1) -(ν -1), and ( 14)

∀d ∈ 1, δ , ∀x, y ∈ 1, ν -δ , i∈ 1,d Zi,x - i∈ 1,d Zi,y ≤ 1. ( 15
)
In other words, these matrices have δ rows and ν -δ columns and elements in {0, 1}. The sum of elements of each row is equal to (k + 1) -(ν -1) (eq. 14) while the partial sums of the columns are balanced, i.e. their values differ by at most 1 (eq. 15). Z is well defined as (k + 1) -(ν -1) ≥ 0 (since β1 > 0 from α 2 1 < β1 + 1) and (k + 1)

-(ν -1) ≤ ν -δ (since k + 1 ≤ n -1)
. Also, note that the size of Z complies with that of B as defined in eq. ( 13). We have | Z| = δ((k + 1) -(ν -1)). Matrix Z captures the links formed by the following process. At step 0 there is no link between nodes in 1, δ and nodes in δ + 1, ν . At each step t = 1, . . . , τ , we consider the set of nodes in 1, δ which are involved in the lowest number of links formed during the process (links formed at steps 1, . . . , t -1), and we pick the node, say it, with the lowest index in this set. Similarly, we consider the subsets of δ + 1, ν whose size is equal to k + 1 -(ν -1) and such that the sum of links incident to the nodes of these subsets is minimal. We pick one of this subset and call it Wt (for instance the one such that the sum of indices of nodes is minimal). Then we form a link between it and each node in Wt. The process stops after each node in 1, δ is involved in k + 1 -(ν -1) links, i.e. τ = δ. 24In Lemmas 8 and 9, Z allow us to capture some of the links between nodes in 1, δ and nodes in δ + 1, ν . Roughly speaking, these links allow us to ensure that nodes in 1, δ have a degree equal to k + 1 and these links are distributed in a way as balanced as possible between nodes in δ + 1, ν .

In the following lemma, we form links for satisfying the condition that each node in 1, δ has a degree equal to k + 1; these links are captured by adjacency matrices A and B. When these links are formed, nodes in δ + 1, ν have degrees strictly higher than k + 1. Hence we do not form any links between nodes in δ + 1, ν , and C is the zero matrix. Moreover, the number of links required to ensure that each node has a degree at least equal to k + 1 is strictly higher than n 1 . We provide a construction that leads to a network that resists k attacks and contains n 2 non-protected links.

Lemma 8 If α 2 1 < β1 + 1 and (2ν -n)(2ν -n -1) < (3ν -2n)(k + 1
) then, optimal strategies require exactly n 2 non-protected links.

Proof We have already shown in Lemma 7 that n 2 is a lower bound on the required number of links. We now show that this bound can be reached by providing a solution adjacency matrix.

Consider the following construction: let γ be as in eq. ( 12), that is, the nodes are ordered such that the δ = 2ν -n components are of size 1 and the others are of size 2. Moreover, let (i) all components of size 1 be connected to all the other components (i.e. both the components of size 1 and 2), (ii) no component of size 2 be connected to any other component of size 2 and (iii) some components of size 2 have two links with a component of size 1. More precisely, we consider a solution matrix M of the shape given by eq. ( 13) with:

                                         A = H(δ -1, δ), B =   1 ν-δ      δ + Z, and C =   0 ν-δ      ν -δ (i.e. C is the zero matrix). (16)
It is important to note that the assumption of Lemma 8 imposes that 3ν -2n > 0. Hence, in this construction, δ > ν -δ. Let us show that this construction satisfies the problem constraints altogether with the desired value of |M|/2 . CS-1 is verified, since by construction A and C are symmetric.

CS-2 ∀i, j ∈ 1, δ , Ai,j ≤ 1 = γiγj, ∀i ∈ 1, δ , j ∈ 1, ν -δ Bi,j ≤ 2 and ∀i, j ∈ 1, ν -δ , Ci,j = 0 ≤ 4
and thus constraint (CS-2) is satisfied.

CS-3 is verified by construction since ∀i, Ai,i = Ci,i = 0.

CS-4 Let

I ⊆ 1, ν . • If I is a singleton {i} ⊆ 1, δ , then j =i Mi,j = (δ -1) + (ν -δ) + ((k + 1) -(ν -1)) = k + 1. • If I is a singleton {i} ⊆ δ + 1, ν , then j =i Mi,j ≥ δ + δ((k+1)-(ν-1)) ν-δ = (2ν -n) + (2ν-n)((k+1)-(ν-1)) n-ν = (2ν -n) (k+1)-(2ν-1-n) n-ν > (2ν-n)(k+1)-(k+1)(3ν-2n) n-ν
by the lemma's assumption. Hence j =i Mi,j > (-ν+n)(k+1)

n-ν = k + 1.
• Otherwise, note that since i∈I j∈ 1,ν \I Mi,j = j∈ 1,ν \I i∈I Mi,j, wlog we can suppose that #I ≤ ν/2 . (Indeed, if #I ≥ ν/2 , then consider

J = 1, ν \I. By construc- tion, #J = ν -#I ≤ ν/2 . Then i∈J j∈ 1,ν \J Mi,j = i∈ 1,ν \I j∈I Mi,j. Thus i∈J j∈ 1,ν \J Mi,j ≥ k + 1 ⇒ i∈I j∈ 1,ν \I Mi,j ≥ k + 1.) Further, since k + 1 ≥ ν -1, then we can suppose that #I ≤ k 2 + 1.
Then, note that for all i, j ∈ 1, ν , we have Mi,j ≤ 2. Then, i∈I j∈ 1,ν \I Mi,j ≥ #I((k + 1) -(#I -1) maxi,j Mi,j). Consider function x → x((k + 3) -2x). It is concave quadratic and attains its maximum at (k + 3)/4. Therefore, its minimum in [

1, k 2 + 1] is 1(k + 3 -2) = k + 1. Hence i∈I j∈ 1,ν \I Mi,j ≥ k + 1. Hence constraint (CS-4) is satisfied. Finally, |M| = |A| + 2|B| + |C| = (δ -1)δ + 2δ((ν -δ) + (k + 1) -(ν -1)) = (δ -1)δ + 2δ(1 -δ + (k + 1)) = δ(1 -δ + 2(k + 1)
) which leads to the result by substituting δ = 2ν -n.

In the following lemma, first we form links for satisfying the condition that nodes in 1, δ have a degree exactly equal to k + 1; these links are captured by adjacency matrices A and B. When these links are formed, nodes in δ + 1, ν have a degree strictly lower than k + 1. Hence we add links between nodes in δ + 1, ν . These links are captured by adjacency matrix C which is a non zero matrix. In the proof of Lemma 9, we describe a specific way to form links between nodes in δ + 1, ν , and so a way to build adjacency matrix C. This construction leads to a network that resists k attacks and contains n 1 non-protected links.

Lemma 9 If α 2 1 < β1 + 1 and (2ν -n)(2ν -n -1) ≥ (3ν -2n)(k + 1), then optimal strategies have exactly n 1 non-protected links.

Proof Consider γ as in eq. ( 12). We construct a solution matrix M of the shape of eq. ( 13) with δ = 2ν -n, and A and B defined as in eq. ( 16). Recall that adjacency matrix A captures links between nodes in 1, δ , i.e. links between components of size 1, and adjacency matrix B captures links between nodes in 1, δ and nodes in δ + 1, ν , i.e. links between components of size 1 and components of size 2. We now build matrix C, which captures the links formed between nodes in δ + 1, ν .

Recall that the matrix Z has the property that the sum of elements between two columns should differ by at most 1 (from eq. ( 15)). Thus, by construction each column of matrix B has a sum of either |Z| ν-δ + δ, or |Z| ν-δ + δ + 1. Let us denote by K the corresponding set of columns of the first kind:

K =    j, i∈ 1,δ Bi,j = |Z| ν -δ + δ    .
Note that by construction of Z, we have #K = (ν -δ) -|Z| mod (ν -δ). Thus, intuitively, so as to resist k attacks, we need to construct matrix C in such a way that:

• C is symmetric, all diagonal elements are either 0 or 1, all other elements are 0, 1 or 2,

• the sum of elements of each row in K should be (at least) equal to k + 1 -|Z| ν-δ -δ while the sum of elements of each other row should be (at least) equal to k -|Z| ν-δ -δ. For ease of notations, let us introduce

f = k - |Z| ν -δ -δ.
Thus C is a matrix with minimal value |C| for which: (i) the sum of elements of each row in K is (at least) equal to f + 1 and (ii) the sum of elements of each row not in K is (at least) equal to f , so that each node i ∈ δ + 1, ν has a degree of k + 1.

We construct C as the sum of 2 matrices, C 1 and C 2 , which we define below. So, we have C = C 1 + C 2 . In the first one, C 1 , the sum of elements of each row associated with nodes in K is equal to 1 (except possibly for one node in K, for this node, this sum is equal to 0 or 2) while the sum of elements of other rows is equal to zero. In other words, adjacency matrix C 1 captures the fact that we add a degree to each node in K (except possibly one). So if we restrict our attention to adjacency matrices B and C 1 each node in δ + 1, ν has the same degree, equal to |Z| ν-δ + δ + 1 (except possibly for one node which has a degree equal to |Z| ν-δ + δ). In the second one, C 2 each row adds up to f (except possibly one which adds up to f + 1). Let us now explain the role played by the adjacency matrix C 2 . Due to the construction of adjacency matrices B and C 1 , we know that we have to add f degrees to each node in δ + 1, ν (except possibly for one). For these nodes, we use the same method as in Lemma 5: we overlap some cliques and a Harary network. Matrix C 2 captures this building process.

Construction of C 1 : Matrix C 1 is a symmetric matrix which satisfies the following conditions (i) all elements are either 0 or 1: C 1 i,j ∈ {0, 1}; (ii) each row (resp. column) whose index is not in the set K contains only elements equal to zero: ∀i, j, C 1 i,j = 1 ⇒ (i ∈ K and j ∈ K); (iii) each row whose index is in K admits at most one non-zero element;

(iv) there exists at most one column with two elements which are not equal to zero.

To construct C 1 , let σ be an ordering of the elements of K, that is K = {σ1, σ2, ..., σ #K }, with σ1 < σ2 < • • • < σ #K . Let J (i, j, b) be the squared matrix of size b whose elements are all zero except for the one at row i and column j and its symmetric element (at row j and column i) whose value is 1. We set:

C 1 = i∈ 0, #K 2 -1
J (σ2i+1, σ2i+2, ν -δ)+ 0 if #K mod 2 = 0 or (ν -δ)f mod 2 = 1, J (σ #K , σ1, ν -δ) otherwise.

C 1 is symmetric as a sum of symmetric matrices. Note that in the case where #K mod 2 = 1 and f (ν -δ) mod 2 = 0, the column of index σ1 adds up to 2: node σ1 is incident to 2 links while other nodes in K are incident to 1 link.

Let us briefly comment on the special status of J (σ #K , σ1, ν -δ). In the case where #K mod 2 = 1, there exists no network such that each node in K has a degree of 1 while each node not in K has a degree of 0 (since in any network the sum of degrees is always even). In other words, there exists no adjacency matrix such that all rows (resp. columns) in the set K add up to 1 and all rows (resp. columns) out of the set K add up to 0. Therefore, to ensure that each row (resp. column) in K adds up to 1, an additional degree is required. However, in the case where (ν -δ)f mod 2 = 1, we will see below that the matrix C 2 , whose construction is based on Harary networks contains exactly one node whose degree is f + 1. Therefore, in that case, we construct C 2 in such a way that this extra link is incident to node σ #K .

Construction of C 2 : Matrix C 2 can be constructed in an analogous way as M in Lemma 5. Indeed, C 2 is analogous to the adjacency matrix of a multigraph in which each node (among ν -δ nodes) should be incident to f links. Since it may be that f ≥ ν -δ -1, then multiple links may be required. Therefore, we introduce f1 and f2 such that f = (ν -δ -1)f1 + f2 and f2 < ν -δ -1, i.e. f1 = f /(ν -δ -1) , and f2 = f mod (ν -δ -1).

Let us give some intuitions for f1 and f2. Consider one component in δ + 1, ν . If we distribute f links between this component and the (ν -δ -1) others in a way as balanced as possible, then (ν -δ -1) -f2 components will be incident to f1 links and f2 components will be incident to f1 +1 links to the considered component. Consider now the adjacency matrix, X , which is the sum of the adjacency matrices of f1 cliques (i.e. (ν -δ -1, ν -δ)-Harary networks) and one (f2, ν -δ)-Harary network, that is:

X = f1H(ν -δ -1, ν -δ) + H(f2, ν -δ).
Recall that in the case where both #K mod 2 = 1 and (ν -δ)f mod 2 = 0, an extra link is required that is adjacent to node σ #K . Due to this link, σ1 has a degree equal to 2 in C 1 . In M, σ1 has a degree equal to k + 2. Note that (ν -δ)f mod 2 = 1 ⇔ (ν -δ)f2 mod 2 = 1. Hence, in the case where #K mod 2 = 0 and (ν -δ)f mod 2 = 1, in the network whose adjacency matrix is H(f2, ν -δ), the node of index ν-δ 2 + 1 has a degree equal to f2 + 1 (from Lemma 4). In M, this node has a degree equal to k + 2. Moreover, in the case where #K mod 2 = 1 and (ν -δ)f mod 2 = 0, node σ #K has a degree equal to 0 in C 1 and in the network whose adjacency matrix is H(f2, ν -δ), the node of index ν-δ 2 + 1 has a degree equal to f2 + 1. Therefore, when #K mod 2 = 1, consider as matrix C 2 the matrix obtained from X by interchanging indices σ #K and ν-δ 2 + 1 when #K mod 2 = 1. 25 Note that, by construction and the permutation of indices, if #K mod 2 = 1 and (ν -δ)f2 mod 2 = 1, then node σ #K has the same degree as the other nodes.

Let us now show that this construction satisfies the optimization problem's constraints:

CS-1 is satisfied, since by construction A and C are both symmetric.

25 Let us define formally the required permutation:

∀i, σi =              i if i = σ #K and i = ν-δ 2 + 1 σ #K if i = ν-δ 2 + 1 ν-δ 2 + 1 if i = σ #K
and ∀i, j, C 2 i,j = X σi ,σ j CS-2 Recall that ν -δ = n -ν and 2ν -n = δ. From the choice of γ, the constraint (CS-2) translates into: ∀i, j ∈ 1, 2ν -n , Ai,j ≤ γiγj = 1, ∀i ∈ 1, 2ν -n , j ∈ 2ν -n + 1, ν , Bi,j ≤ γiγj ≤ 2 and ∀i, j ∈ 2ν -n + 1, ν , Ci,j ≤ γiγj ≤ 4. The construction of M induces that ∀i, j Ai,j ≤ 1, Bi,j ≤ 2 and Ci,j ≤ f1 + 1 + 1. Then,

f1 ≤ (k + 1) -|Z| n-ν -(2ν -n) n -ν -1 ≤ (k + 1)(n -ν) -(2ν -n)((k + 1) -(ν -1)) -(2ν -n)(n -ν) (n -ν -1)(n -ν) = (k + 1)(2n -3ν) + (2ν -n)(2ν -n -1) (n -ν -1)(n -ν) ≤ (n -2)(2n -3ν) + (2ν -n)(2ν -n -1) (n -ν -1)(n -ν) = 4 - n n -ν < 3. ( 17
)
Since f1 is an integer, then f1 ≤ 2 and thus Ci,j ≤ 4, hence, satisfying constraint (CS-2).

CS-3 A and C 2 have a zero diagonal as they are sums of matrices with zero diagonals. Since σ1 < σ2 < • • • < σ #K then all J matrices involved in the construction of C 1 have zero diagonals. Therefore ∀i, Mi,i = 0 and constraint (CS-3) is satisfied.

CS-4 Finally, let I ⊆ 1, ν .

• If I is a singleton, then by construction j =i Mi,j = k + 1.

• Otherwise, note that from eq. 17 ∀i, j, Mi,j ≤ 2. Therefore, the proof is similar to that of Lemma 8:

i∈I j /
∈I Mi,j ≥ #I(k + 1 -(#I -1)(maxi,j Mi,j)) ≥ 1((k + 1) -0) = k + 1. Hence, constraint (CS-4) is satisfied.

We now compute the number of links induced by M. By construction, all nodes in 1, δ have a degree equal to k + 1. Similarly, all nodes in δ + 1, ν , except possibly one, say i, have a degree equal to k + 1. We now examine situations where node i has a degree strictly higher than k + 1. If #K mod 2 = 1 and (ν -δ)f mod 2 = 0, then node i is identified with node σ1 defined in C 1 and has a degree equal to k + 2. Similarly, if #K mod 2 = 0, i.e. all nodes in K have exactly one degree due to the construction of C 1 , and if f2(ν -δ) mod 2 = 1, then node i is identified with node ν-δ 2 + 1. In that case, node i has a degree equal to k + 2. It remains to establish that the degree of i is equal to k + 2 if and only if ν(k + 1) mod 2 = 1. We have to examine the different possibilities associated with ν(k + 1) mod 2 = 0 or ν(k + 1) mod 2 = 1, and δ mod 2 = 0 or δ mod 2 = 1. Suppose that ν(k + 1)δ mod 2 = 1. By construction of set K, we have | Z| = x(ν -δ) + ((ν -δ) -#K), with x ∈ N, that is δ((k + 1) -(δ -1) -(ν -δ)) = x(ν -δ) + ((ν -δ) -#K), with x ∈ N. We have δ((k + 1) -(δ -1) -(ν -δ)) mod 2 = 1, so ((ν -δ) -#K) mod 2 = 1 since (ν -δ) mod 2 = 0. Moreover, since (ν -δ) mod 2 = 0, we have #K mod 2 = 1. Therefore, the degree of node i is equal to k + 2 since #K mod 2 = 1 and f (ν -δ) mod 2 = 0. The examination of the different other possibilities associated with ν(k + 1) mod 2 = 0 or ν(k + 1) mod 2 = 1, and δ mod 2 = 0 or δ mod 2 = 1 is done by using the same arguments as in the case where ν(k + 1)δ mod 2 = 1. This fastidious examination allows us to conclude that the degree of node i is k + 2 if and only if ν(k + 1) mod 2 = 1. We now conclude the proof of Proposition 1. First, let us observe the conditions of Lemma 8. These are: n ν

It follows that

2 < k + 1 ν -1 + 1 (2ν -n)(2ν -n -1) < (3ν -2n)(k + 1) (18a) (18b)
Suppose that eq. ( 18b) is satisfied and n > ν. Then:

1. Consider the quadratic x → (2ν -x)(2ν -x -1). It is always non negative except in the (open) interval (2ν -1, 2ν). Since n is an integer, for any n and ν, we have (2ν -n)(2ν -n -1) ≥ 0.

Figure 1 :

 1 Figure 1: Examples of (κ, n)-Harary-networks.

10 (Figure 2 :

 102 Figure 2: Subnetworks associated with Example 1: the solution network is (N, E P , E N P ) with E N P = E N P (g ) ∪ E N P (g ).

(Figure 3 :

 3 Figure 3: Subnetworks associated with Example 2. The solution is (N, E P , E N P ) with E N P (g) = E N P ∪E N P .

Figure 4 :

 4 Figure 4: Intuition of Proposition 2 when n(k + 1) mod 2 = 0.

Figure 6 :

 6 Figure 6: Example with n = 31, k = 27. The optimal strategy for D depends on the value of c P /c L .

Figure 7 :

 7 Figure 7: Networks of Example 4. Thick lines represent protected links and dashed lines represent links that are targetted by A.

Figure 8 :

 8 Figure 8: Networks of Example 5: n = 5, k = 2. Optimal strategies for D for different numbers of protected links and when A attacks (up to) 2 links. The captions of the figures give the Designer's expected benefit.

(Figure 9 :

 9 Figure 9: Illustration of the E P -contraction: the links 12 and 34 are contracted.

  Note that the powers of D(b) and E(b) have a specific structure. They satisfy, for any a ∈ N, D(b) (a) i,j = 1 if (j -i) mod b = a and 0 otherwise and similarly E(b) (a) i,j = 1 if j -i = a and 0 otherwise. Let us also define the matrix F(a, b) = D(b) (a) + (D(b) (a) ) (with . the transpose operator). Note that if 0 < 2a < b, then F(a, b) is an adjacency matrix of a network. 23 Finally, G(a, b) = E(b) (a) + (E(b) (a) ) is also the adjacency matrix of a network for any a, b > 0.

|M| 2 = ν(k+1) 2 , i.e |M| 2 =

 22 n 1 .

Note that an intelligent attack can also be seen as the worst case scenario.

If we take again our military example, and assume that node i -1 is the supplier of node i, then the Designer has to maintain a path between each pair of nodes i -1 and i to obtain some end products. In other words, the residual network has to be connected to allow some production.

A network g, which contains n nodes, is a minimal (k + 1, n)-link-connected network, if it is not possible to disconnect it by removing k links, and such that there is no network which cannot be disconnected by removing k links and contains a smaller number of links.

If we take again our military example, the Designer may not have enough resources to protect the whole network.

Despite the effort of the Designer (of the army) to protect the communication flow, the Adversary (the enemy) may still be able to succeed in destroying protected links with some probabilities.

A minimal (k+1, n)-node-connected network is a network, which contains n nodes, that cannot be disconnected by removing k nodes, and such that there is no network which cannot be disconnected by removing k nodes and contains a smaller number of links.

A star network is a network where one node, the central one, is linked with all other nodes, and other nodes are only linked with the central node.

A network where all nodes have the same number of links.

It will be clear in the following that if c A < 1/(n -3), then A may attack at least n -2 links. Due to our assumptions on the cost of protected and non-protected links and on the payoff function of D, if A can attack n -2 links, then in equilibrium, the only protected network without protected links that D may design is the complete network. Moreover, if A can attack strictly more than n -2 links, then in equilibrium D cannot design any protected network without protected links.

It will be clear in the following that when c P < 1/(n -1) and c L < 1/(n(n -1)/2), then D builds a non-empty protected network in equilibrium.

In particular, note that the strategy ∅ for the Adversary leads to a payoff that equals zero. If 1/c A is an integer, then there may exist a strategy such that #E A = 1/c A = k that disconnect the network. That strategy also has a payoff that equals zero and is chosen by the Adversary according to the tie-breaking rule (if no strategy with #E A < k can disconnect the network).

This interval is non empty if p 2 > p 1 which implies that ∆ > 0, that is n < (3k+5) 2 8(k+1) .

Note that in Figure8(vii), each node is incident to 2 protected links and k = 2. Interestingly, DG[START_REF] Dziubiński | Network design and defense[END_REF] and Landwehr[START_REF] Landwehr | Network design and imperfect defense[END_REF] establish that in models with imperfect defense, there exist parameters where D designs a (2, n)-Harary-networks in equilibrium.

By definition a simple graph does not contain a loop, that is a link joining a node to itself; neither does it contain multiple links, that is, several links joining the same two nodes. Therefore, it is a multigraph for which ψ is injective and for which there is no e ∈ E such that ψ(e) = (i, i) with i ∈ N .

Since ĝE P results of the contraction of p links, then ν ≥ n -p. The equality is attained when the subnetwork (N, E P , ∅) contains no cycle.

Indeed, F is symmetric by construction and F (a, b) i,j ∈ {0, 1}. Suppose F (a, b) i,j = 2. Then, by construction (ji) mod b = a and (i -j) mod b = a. It follows that ((j -i) + (i -j)) mod b = 2a mod b. Hence, 2a mod b = 0, a contradiction since 0 < 2a < b.

We present a formal construction of Z in Appendix II.

This research has been supported by a grant of the French National Research Agency (ANR, FELIS Grant, ANR-14-CE28-0010-01). It was performed within the framework of the LABEX CORTEX (ANR-11-LABX-0042) of Université de Lyon, within the program Investissements d'Avenir (ANR-11-IDEX-007) operated by the French National Research Agency (ANR). Funding for this project was provided by a grant from Région Rhône-Alpes.

Appendix I: Proof of Proposition 1

The proof of Proposition 1 is organized in the following way. We first establish that the subnetwork (N, EP , ∅) of s D ∈ S D p,k is acyclic (Lemma 1). In Appendix A, first given a number of nodes and a number of components, we provide an alternative optimization problem whose optimum corresponds to the optimal Designer's strategy (Lemma 2). Second, we provide a lower bound on the number of nonprotected links in a protected network s D ∈ S D p,k (Lemma 3). In Appendices B and C, we provide the solutions of the optimization problem, both in terms of value (i.e. the minimum number of non-protected links) as well as a constructive method for the Designer to obtain an optimal set of non-protected links according to the number of protected links and the number of attacks.

The following lemma will allow us to establish that if D forms p protected links in s D ∈ S D p,k , then s D contains n -p components. Proof If p = n -1, the result holds from Footnote 15. Otherwise, to introduce a contradiction, suppose that the subnetwork (N, EP , ∅) of s D ∈ S D p,k contains a cycle. Then, there exists a link ij ∈ EP such that (N, EP \ {ij}, ENP ) cannot be disconnected by an optimal attack of A. Moreover, since p ∈ 1, n -2 and g R cannot be disconnected by an optimal attack of A, we have ENP = ∅. Let i j ∈ ENP . Network (N, EP \ {ij} ∪ {i j }, ENP \ {i j }) contains p protected links and #ENP -1 non-protected links, a contradiction.

A An equivalent optimization formulation

The equivalent problem formulation relies on the concept of multigraph and contraction of networks which we now develop.

Multigraphs.

A multigraph is a graph where multiple links and loops are allowed. Formally, an (undirected) multigraph ĝ is an ordered triplet ( N , Ê, ψ) consisting of a non-empty set of nodes, N , a set of links, Ê, disjoint with N , and an incidence function ψ : Ê → N 2 that associates to each link an unordered pair of nodes of ĝ. If e is a link and i and j are nodes such that ψ(e) = (i, j), then e is said to join i and j. 21 Proof For a > 1, the result follows from Harary [START_REF] Harary | The maximum connectivity of a graph[END_REF]. For a = 1, the result follows from the construction of G b 2 , b : a link is formed between i and j if and only if (

is the adjacency matrix of a clique.

We can now describe the optimal strategy when α 2 1 ≥ β1 + 1. An optimal strategy consists in overlapping cliques and a Harary-network.

Lemma 5 Suppose that α 2 1 ≥ β1 + 1. Then, any optimal strategy has exactly n 1 non-protected links.

Proof Consider vector γ as defined in eq. ( 12), so (CS-5) is satisfied. Intuitively, each node should be incident to k + 1 links. If k + 1 ≥ ν -1, multi-links are needed. Since k + 1 = β1(ν -1) + β2, we consider the matrix M which is the sum of the adjacency matrices of β1 cliques (i.e. (ν -1, ν)-Harary-networks) and one (β2, ν)-Harary-network. More precisely, let M be given by:

Let us first check that M is an admissible matrix (i.e. that it satisfies the constraints (CS-1)-(CS-4)):

CS-1 is satisfied by construction.

CS-2 Further, ∀i, j, Mi,j ≤ β1 + 1 ≤ α 2 1 ≤ γi γj, which complies with constraint (CS-2). CS-3 By construction Harary-networks do not contain loops. Hence ∀i, Mi,i = 0 which satisfies constraint (CS-3).

CS-4 Finally, let I ⊆ 1, ν :

• Finally, suppose that 2 ≤ #I ≤ ν -2. Note that if 2 ≤ #I ≤ ν -2, then ν > 3. By construction, we have j∈ 1,ν M1,j = k + 1. We establish that I resists a number of attacks greater or equal to the number of attacks node 1 resists. By definition of an (a, ν)-Hararynetwork, for a ∈ 2, ν -1 and I ⊂ 1, ν , #I ∈ 2, ν -2 , we have i∈I j∈ 1,ν \I H(a, ν)i,j ≥ a = j∈ 1,ν H(a, ν)1,j and for ν > 3,

We now deal with H(a, ν) for a = 1. We have for

Hence constraint (CS-4) is satisfied.

Let us now compute the number of links induced by this strategy. We have:

2

. Therefore, in all cases, the number of links is n 1 , which is optimal from Lemma 3.

Hence, when α 2 1 ≥ β1 + 1, the lower bound on the number of links is attained. An important special case is when 2ν ≤ n, that is when the number of protections is large. In that case, γ i > 1, and the components we consider in our construction have a size strictly higher than 1.

Therefore, 3ν -2n > 0. Thus 2ν + ν > 2n, and hence ν > 2(n -ν) > n -ν (since ν < n). Thus 2ν > n > ν, or in other words n ν = 1. 2. Since ν > n -ν and n > ν, we have ν > 1.

Now, suppose that

then eq. (18b) implies that n(n -1) < n(k + 1). Since n > 0, this implies that ν -1 < k + 1, that is k+1 ν-1 ≥ 1. We have shown that for all n ≥ ν, any solution of eq. (18b) satisfies n ν 2 = 1 < 1 + 1 ≤ 1 + k+1 ν-1 . Therefore, constraint (18a) is implied by constraint (18b) and can thus be omitted.

Second, we have

, and so n 2 = n2(p, k). Finally, note that equation (n -2p)((k + 1) -(n -2p -1)/2) = (k + 1)p is quadratic in p. Let x1 and x2 be the two real roots of the polynomial when they exist (which occurs when n ≤

Appendix II: A construction for Matrix Z

A possible construction for matrix Z is to proceed according to the following process:

Input: Number of rows δ, columns ν -δ and value of row sum (k + 1) -(ν -1) Output: A possible matrix Z 1 Initialize matrix Z to the zero matrix 2 Set Z 1,j = 1 for all j ≤ (k + 1) -(ν -1) 3 for each row r from 2 to δ do 4 for each column q from 1 to ν -δ do 5 Compute the partial sum w q = i∈ 1,r Z i,q 6 Select exactly (k + 1) -(ν -1) columns among the ν -δ columns having the lowest sum of w q , i.e. Set these elements to one: Z r,j = 1 with j ∈ W r