ファイル置き場 Sendai Logic Homepage speaker18

(1)

Determinacy and Optimal Strategies of

Network Games

Ahmad Termimi Ab Ghani (jointly with K. Tanaka and K. Higuchi)

Mathematical Institute Tohoku University

JAPAN

Workshop on Proof Theory and Computability Theory 2012 - Philosophical Frontiers in Reverse Mathematics

Tokyo, JAPAN 23 Feb 2012

(2)

Outline

1 Introduction Background

2 PART 1 (Network Games)

Definitions of Network Games and Profits Properties of Pure Nash equilibria

Mixed Strategies and Expected Profits Characterizations of Mixed Nash equilibria

3 PART 2 (Asynchronous Games) Notations and Definitions One-Round Games and Profits Games with a Natural Payoff Function

(3)

Outline

(4)

Previous Work and Motivation

Let G= (V , E) be a graph with no isolated vertices.

Mavronicolas et al. (2005) presented a network game: -attackers: aim to damage by attacking avertices. -defender: aim to protect the network by select anedge. (i.e., attacker and defenders have conflicting objectives). Subsequently, MedSalem et al. (2007) generalized the model so that they have many defenders instead of a single defender.

(5)

Previous Work and Motivation

Then we introduced a new network game with the roles of players interchanged (T. and K. Tanaka, 2011).

In particular, we proposed a new network game where: -attackers: aim to damage the network by attacking anedge -defenders: aim to protect the network by choosing avertex. We obtained a graph-theoretic characterization of pure Nash equilibrium.

(6)

Previous Work and Motivation

Then, we presented mixed Nash equilibria for stochastic strategies in this new game (Akiu, 2011).

(7)

Previous Work and Motivation

In this talk, I will explain a generalization of network game (called asynchronous game), where two players repeatedly execute simultaneous games.

(8)

Outline

(9)

Network Game

Definition

Let G= (V , E) be an undirected graph with no isolated vertices. Fix integerα and δ with α, δ≥ 1. A network game Γ_α,δ(G) =hN , Si on G is defined as follows:

N = NA∪ NDis the set of players where

N^Ais a finite set ofattackersai, where 1_{≤ i ≤ α} NDis a finite set ofdefendersdj^{, where 1}≤ j ≤ δ S = E^α× V^δis the strategy set ofΓ_α,δ(G)

An element_he1, ..., e_α, v1, ..., v_δi of S is also called a profile of the game, and e_i, v_j strategies of a_i, d_j, respectively.

(10)

Profits

Now fix a profile s=_he1, ..., e_α, v1, ..., v_δi of the game Γα,δ^(G),

define the individual profit of the players as follows:

The individual profit of attacker ai, 1≤ i ≤ α, is given by

Ps(ai) =

(0 if vj ∈ ei for some j, 1_{≤ j ≤ δ} 1 if vj _{∈ e}/ i for all j, 1_{≤ j ≤ δ}

where v ∈ e denote the node v is adjacent to an edge e. In other words, attacker ai receives 0 if it is caught by a defender dj, and 1 otherwise.

(11)

Profits

Now fix a profile s=_he1, ..., e_α, v1, ..., v_δi of the game Γα,δ^(G),

define the individual profit of the players as follows:

The individual profit of attacker ai, 1≤ i ≤ α, is given by

Ps(ai) =

(0 if vj ∈ ei for some j, 1_{≤ j ≤ δ} 1 if vj _{∈ e}/ i for all j, 1_{≤ j ≤ δ}

where v ∈ e denote the node v is adjacent to an edge e. In other words, attacker ai receives 0 if it is caught by a defender dj, and 1 otherwise.

(12)

Profits

The individual profit of defender d_j, 1≤ j ≤ δ, is given by Ps(dj) =|{i : 1 ≤ i ≤ α, v^j ∈ eⁱ}|

representing the number of attackers captured by dj.

(13)

An illustration of the game

(14)

Basic Notions of Graph Theory

We consider an undirected graph G= (V , E). A vertex cover of G is a vertex set CV ⊆ V s.t.

∀e ∈ E, ∃v ∈ C^V ^{where v} ∈ e.

An edge cover of G is an edge set CE ⊆ E s.t.

∀v ∈ V , ∃e ∈ C^E^{, v} ∈ e.

A matching M of G is a subset of E such that no vertex is incident to more than one edge in M.

A vertex set IV ⊆ V is an independent set of G if for all pairs of vertices u, v _{∈ I}_V, (u, v ) /_{∈ E.}

nV and nE denote the number of vertices and edges in G.

(15)

Basic Notions of Graph Theory

∀e ∈ E, ∃v ∈ C^V ^{where v} ∈ e.

∀v ∈ V , ∃e ∈ C^E^{, v} ∈ e.

(16)

Basic Notions of Graph Theory

∀e ∈ E, ∃v ∈ C^V ^{where v} ∈ e.

∀v ∈ V , ∃e ∈ C^E^{, v} ∈ e.

(17)

Basic Notions of Graph Theory

∀e ∈ E, ∃v ∈ C^V ^{where v} ∈ e.

∀v ∈ V , ∃e ∈ C^E^{, v} ∈ e.

(18)

Basic Notions of Graph Theory

∀e ∈ E, ∃v ∈ C^V ^{where v} ∈ e.

∀v ∈ V , ∃e ∈ C^E^{, v} ∈ e.

(19)

Outline

(20)

Nash equilibrium

Definition

A profile s is a Nash equilibrium if for any player r _{∈ {a}i, dj}, Ps(r )_{≥ P}_¯s(r ) for any profiles ¯s which differs from s only on the strategy of r .

In other words, in a Nash equilibrium no player can improve his individual profit by changing his strategy unilaterally.

(21)

Firstly, we define a set

As={e ∈ E : ∃i, 1 ≤ i ≤ α, where e = ei} Ds ={v ∈ V : ∃j, 1 ≤ j ≤ δ such that v = v^j} where s=_he1, ..., e_α, v1, ..., v_δ_i.

Theorem

The gameΓ_α,δ(G) has a (pure) Nash equilibrium if and only if there exist D⊂ V and A ⊂ E such that

(1)|D| ≤ δ and |A| ≤ α (2) D is a vertex cover of G

(3)∀v ∈ D, |A ∩ E(v)| = max¯v∈V|A ∩ E(¯v)|

(22)

Firstly, we define a set

As={e ∈ E : ∃i, 1 ≤ i ≤ α, where e = ei} Ds ={v ∈ V : ∃j, 1 ≤ j ≤ δ such that v = v^j} where s=_he1, ..., e_α, v1, ..., v_δ_i.

Theorem

The gameΓ_α,δ(G) has a (pure) Nash equilibrium if and only if there exist D⊂ V and A ⊂ E such that

(1)|D| ≤ δ and |A| ≤ α (2) D is a vertex cover of G

(3)∀v ∈ D, |A ∩ E(v)| = max¯v∈V|A ∩ E(¯v)|

(23)

Definition

The graph G is bipartite if V = V0_{∪ V}1for some disjoint vertex sets V₀,V₁⊆ V so that for each edge (u, v) ∈ E, u ∈ V0^and

v _{∈ V}1(or u _{∈ V}1and v _{∈ V}0). Theorem

For a bipartite graph G, a gameΓ_α,δ(G) has a (pure) Nash equilibrium if and only ifα, δ ≥ m, where m is the size of a maximum matching in G.

(24)

Definition

The graph G is bipartite if V = V0_{∪ V}1for some disjoint vertex sets V₀,V₁⊆ V so that for each edge (u, v) ∈ E, u ∈ V0^and

v _{∈ V}1(or u _{∈ V}1and v _{∈ V}0). Theorem

For a bipartite graph G, a gameΓ_α,δ(G) has a (pure) Nash equilibrium if and only ifα, δ ≥ m, where m is the size of a maximum matching in G.

(25)

Outline

(26)

Mixed Strategies

A mixed strategy for an attacker (resp. defender) is a probability distribution over edges (resp. vertices) of G.

A mixed profile s=_hσ1, ..., σ_α, τ1, ..., τ_δi is a collection of mixed strategies, one for each player.

σi(e) : the probability that attacker ai chooses edge e τ_j(v ) : the probability that defender d_j chooses vertex v .

(27)

Mixed Strategies

Thus, for each i _{≤ α,}

σi : E → [0, 1] satisfies ^X

e∈E

σi(e) = 1,

and for each j_{≤ δ,}

τ_j : V → [0, 1] satisfies ^X

v∈V

τ_j(v ) = 1.

(28)

Support

The support of a player r ∈ N in a profile s (denoted by S^s^{(r )),} is the set of edges or vertices to which r assigns positive probability in s.

Let

Ss(A) = ^[

a_i∈N_A

Ss(ai) and

Ss(D) = ^[

d_j∈N_D

Ss(dj).

(29)

LetSave(e):= the event that at least one end v _{∈ e is} protected by a defender.

Letπs(Save(e))be the probability of the event Save(e) with respect to s.

(30)

Expected Profits

For a defender dj∈ ND, Ps(d_j) = ^X

v∈Vi≤α e∈E(v )

τ_j(v )σ_i(e) = ^X

v∈V

τ_j(v ) ^X

e∈E(v )i

σ_i(e)

For an attacker a_i _{∈ N}_A, Ps(ai) =^X

e∈E

σi(e)_{· (1 − π}s(Save(e)))

(31)

Expected Profits

For a defender dj∈ ND, Ps(d_j) = ^X

v∈Vi≤α e∈E(v )

τ_j(v )σ_i(e) = ^X

v∈V

τ_j(v ) ^X

e∈E(v )i

σ_i(e)

For an attacker a_i _{∈ N}_A, Ps(ai) =^X

e∈E

σi(e)_{· (1 − π}s(Save(e)))

(32)

Mixed Nash equilibria

Definition

A mixed profile s is a mixed Nash equilibrium if for each player r ∈ N , it maximizes Psover all profiles ¯s that differ from s only with respect to the mixed strategy of player r .

Intuitively, no player can gain more by a unilateral change of his strategy.

(33)

Outline

(34)

Theorem

In any mixed Nash equilibrium s ofΓ_α,δ(G), Ss(D) is a vertex cover of G.

Theorem

In any mixed Nash equilibrium s ofΓ_α,δ(G), Ss(A) is an edge cover of the subgraph of G obtained by restricting to Ss(D).

(35)

Theorem

In any mixed Nash equilibrium s ofΓ_α,δ(G), Ss(D) is a vertex cover of G.

Theorem

In any mixed Nash equilibrium s ofΓ_α,δ(G), Ss(A) is an edge cover of the subgraph of G obtained by restricting to Ss(D).

(36)

The following characterization is useful for checking whether or not it is a mixed Nash equilibrium.

Proposition

Given a graph G, a mixed profile s is a Nash equilibrium iff:

1 ∀j ≤ δ, ∀v ∈ Ss^(dj⁾

X

e∈E(v)i

σi(e) = max

¯ v∈V

X

e∈E(¯i v)

σi(e)

2 ∀i ≤ α, ∀e ∈ Ss(ai)

πs(Save(e)) = min

¯

e∈E^π^s^(Save(¯^e))

(37)

The following characterization is useful for checking whether or not it is a mixed Nash equilibrium.

Proposition

Given a graph G, a mixed profile s is a Nash equilibrium iff:

1 ∀j ≤ δ, ∀v ∈ Ss^(dj⁾

X

e∈E(v)i

σi(e) = max

¯ v∈V

X

e∈E(¯i v)

σi(e)

2 ∀i ≤ α, ∀e ∈ Ss(ai)

πs(Save(e)) = min

¯

e∈E^π^s^(Save(¯^e))

(38)

Remark

Given a profile s, the condition that Ss(A) and Ss(D) are an edge cover and vertex cover respectively, does not necessarily imply that s is a Nash equilibrium.

Example

For example, let G=_{{v₀, v₁, v₂_{}, {e}₀, e₁_{}} where e}₀= (v₀, v₁) and e1= (v1, v2). Let α = δ = 1, and also s =_hσ1, τ1i such that σ1(e0) = 0.9, σ1(e1) = 0.1 and τ1(v0) = 0.9, τ1(v1) = 0,

τ₁(v₂) = 0.1.

(39)

Remark

Given a profile s, the condition that Ss(A) and Ss(D) are an edge cover and vertex cover respectively, does not necessarily imply that s is a Nash equilibrium.

Example

For example, let G=_{{v₀, v₁, v₂_{}, {e}₀, e₁_{}} where e}₀= (v₀, v₁) and e1= (v1, v2). Let α = δ = 1, and also s =_hσ1, τ1i such that σ1(e0) = 0.9, σ1(e1) = 0.1 and τ1(v0) = 0.9, τ1(v1) = 0,

τ₁(v₂) = 0.1.

(40)

Example (con’t)

the attacker

the defender

v

0

^e

⁰

v

1

^e

¹

v

2

0_.9 0_.1

0_.9 0 0_.1

Figure:An illustration of the example

(41)

Example (con’t)

Then, clearly Ss(A) =_{e₀, e₁_{} and S}s(D) =_{v₀, v₂_{} are an} edge cover and vertex cover, respectively.

However, X

e∈E(vi ₀)

σi(e) = 0.9_{6= max}

v∈V¯

X

e∈E(¯i v)

σi(e) = 1

Hence, s is not a Nash equilibrium by Proposition.

(42)

Perfect Covering Profiles

Now we introduce a new notion, called a perfect covering profile, and show it is a sufficient condition for the existence of a Nash equilibrium in a bipartite graph.

(43)

Definition

A mixed profile s= (σ1, ..., σα, τ1, ..., τ_δ) is said to be a perfect covering profile if it is uniform and satisfies the following conditions.

1 _S_s(D) is an independent vertex cover.

2 _S_s(A) is a perfect matching. Lemma

In a bipartite graph, a perfect covering profile is a mixed Nash equilibrium.

(44)

Definition

A mixed profile s= (σ1, ..., σα, τ1, ..., τ_δ) is said to be a perfect covering profile if it is uniform and satisfies the following conditions.

1 _S_s(D) is an independent vertex cover.

2 _S_s(A) is a perfect matching. Lemma

In a bipartite graph, a perfect covering profile is a mixed Nash equilibrium.

(45)

The following theorem provides necessary and sufficient conditions forΓ_α,δ(G) to have a perfect Nash equilibrium. Remark

If G has a perfect matching and no odd cycle, then G has an independent vertex cover.

Theorem

The gameΓ_α,δ(G) has a perfect Nash equilibria if and only if G has a perfect matching and no odd cycle.

(46)

Theorem

(47)

Theorem

(48)

Proof

Suppose first thatΓ_α,δ(G) has a perfect Nash equilibrium, say s. By definition, Ss(D) is an independent vertex cover, which imply V_{\ S}s(D) is independent as well. Suppose that G had an odd cycle_Codd. Then, there would be an edge e contained in C^odd with endpoints both in Ss(D) or both in V _{\ S}s(D), which is a contradiction. By definition, G has a perfect matching.

Conversely, assume G has a perfect matching and no odd cycle. By Remark 3, G has an independent vertex cover.

(49)

con’t.

Since now we have a perfect matching M and an independent vertex cover I_C_V, we construct a perfect covering profile s= (...σ_i..., ...τ_j...) as follows:

σi(e) = ( ₁

|M| ^{if e}^{∈ M}

0 if otherwise and

τj(v ) = ( ₁

|I_CV| ^{if v} ^{∈ I}^CV

0 if otherwise

where M:= Ss(A) and IC_V := Ss(D). Clearly, a perfect covering profile s is a mixed Nash equilibrium, as needed. Therefore, the gameΓ_α,δ(G) has a perfect Nash equilibrium.

(50)

Computing a Perfect Nash Equilibrium

Theorem

For a bipartite graph G, it can be computed in O(^√nVnE) whether or notΓ_α,δ(G) has a perfect Nash equilibrium, and if any, one can obtain in O(^√n_Vn_E).

Proof.

Find a maximum matching M by reducing to finding an augmenting path which can be compute in O(^√nVnE).

(51)

Computing a Perfect Nash Equilibrium

Theorem

For a bipartite graph G, it can be computed in O(^√nVnE) whether or notΓ_α,δ(G) has a perfect Nash equilibrium, and if any, one can obtain in O(^√n_Vn_E).

Proof.

Find a maximum matching M by reducing to finding an augmenting path which can be compute in O(^√nVnE).

(52)

Outline

(53)

An illustration of the game

(54)

Notations and Definitions

First of all, we define partial plays and corresponding sequences of subgraphs.

Let G= (V , E) be an undirected graph.

The setP ⊂ (E × V )^<^Nof partial plays is defined recursively as follows:

Put the empty sequenceλ_{∈ P and E}_λ = E and V_λ= V . Now assume thatη_{∈ P, and E}_η _{⊂ E and V}_η _{⊂ V have} been defined.

We putρ := η^⌢h(e, v)i into P, if e ∈ Eη and v _{∈ V}η.

(55)

Notations and Definitions

(56)

Notations and Definitions

(57)

Notations and Definitions

(58)

Notations and Definitions

(59)

Notations and Definitions

(60)

Notations and Definitions

Then, we define Eρ^:=

(E_η if v _{∈ e} Eη− {e} if v /∈ e V_ρ:= V (E_ρ).

Finally, let[P] = {w ∈ (E × V )^N^:

each finite initial segment of w belongs to_P}.

(61)

Notations and Definitions

Then, we define Eρ^:=

(E_η if v _{∈ e} Eη− {e} if v /∈ e V_ρ:= V (E_ρ).

Finally, let[P] = {w ∈ (E × V )^N^:

each finite initial segment of w belongs to_P}.

(62)

Mixed Strategy

A mixed strategy in an asynchronous game is defined as follows.

Definition

A mixed strategy for attacker a is defined by σ^∗ :_{P → [0, 1]}^E satisfying ^X

e∈Eρ

σ^∗(ρ)(e) = 1.

Similarly, a mixed strategy for defender d is given by τ^∗ :_{P → [0, 1]}^V such that ^X

v∈Vρ

τ^∗(ρ)(v ) = 1.

(63)

Mixed Strategy

A mixed strategy in an asynchronous game is defined as follows.

Definition

A mixed strategy for attacker a is defined by σ^∗ :_{P → [0, 1]}^E satisfying ^X

e∈Eρ

σ^∗(ρ)(e) = 1.

Similarly, a mixed strategy for defender d is given by τ^∗ :_{P → [0, 1]}^V such that ^X

v∈Vρ

τ^∗(ρ)(v ) = 1.

(64)

Outline

(65)

Solving One-Round Games

Given G: a finite graph and

f :_{G^′ : G^′ is a proper subgraph of G} → R, a state evaluation, We define a function h: E× V → {subgraphs of G} by

h(e, v ) :=

(G if v _{∈ e}

G(E \ {e}) if v /∈ e

(66)

Solving One-Round Games

Given G: a finite graph and

f :_{G^′ : G^′ is a proper subgraph of G} → R, a state evaluation, We define a function h: E× V → {subgraphs of G} by

h(e, v ) :=

(G if v _{∈ e}

G(E \ {e}) if v /∈ e

(67)

Expected Profit of One-Round Game

Definition

Let s= (σ, τ ) be a pair of mixed strategies. The expected profit of the attacker with the delay constant c is given by

Ps(Γ(G; f )) :=^X

v∈e/

σ(e)τ (v ){1 + f (h(e, v))}

+^X

v∈e

σ(e)τ (v )cPs(Γ(G; f )),

(68)

Now we see the existence of a mixed Nash equilibria in the one-round game.

Theorem

Given G and function f :_{G^′ _{$ G : G}^′ a subgraph_{} → R.} Then, the one-round gameΓ(G; f ) is determined with a stable solution.

Proof (Idea)

The proof follows from a combination of the mini-max theorem and Brouwer’s fixed point theorem.

(69)

Theorem

Proof (Idea)

(70)

Theorem

Proof (Idea)

(71)

Proof

Suppose f :_{G^′ $ G} → R, and f (G) = x ∈ R (for the next round with the same G) are given.

The expected profit according to a profile(σ, τ ) is following:

P(σ, τ, x) :=^X

v∈e/

σ(e)τ (v ){1 + f (h(e, v))} +^X

v∈e

σ(e)τ (v )¹ 2^x.

By the mini-max theorem, we have maxσ ^minτ P(σ, τ, x) = min

τ ^maxσ ^{P(σ, τ, x)}

for all x _{∈ R.}

(72)

Proof

The expected profit according to a profile(σ, τ ) is following: P(σ, τ, x) :=^X

v∈e/

σ(e)τ (v ){1 + f (h(e, v))} +^X

v∈e

σ(e)τ (v )¹ 2^x. By the mini-max theorem, we have

maxσ ^minτ P(σ, τ, x) = min

for all x _{∈ R.}

(73)

Proof

The expected profit according to a profile(σ, τ ) is following: P(σ, τ, x) :=^X

v∈e/

σ(e)τ (v ){1 + f (h(e, v))} +^X

v∈e

σ(e)τ (v )¹ 2^x. By the mini-max theorem, we have

maxσ ^minτ P(σ, τ, x) = min

for all x _{∈ R.}

(74)

con’t.

Note that the set of strategyσ’s (similar for τ ’s) is bounded closed convex, and so it is easy to see that

M(x) = max

σ ^minτ ^{P(σ, τ, x)}

is a continuous function. Now put m= 1 + max f .

Clearly, M : [0, m]→ [0, m]. So it has a fixed point ˆx. Then M(ˆx) serves as a stable solution.

(75)

con’t.

Note that the set of strategyσ’s (similar for τ ’s) is bounded closed convex, and so it is easy to see that

M(x) = max

σ ^minτ ^{P(σ, τ, x)}

is a continuous function. Now put m= 1 + max f .

Clearly, M : [0, m]→ [0, m]. So it has a fixed point ˆx. Then M(ˆx) serves as a stable solution.

(76)

Outline

(77)

Payoff Function

Now, we define a function f : W → R, which plays the role of a natural payoff for the attacker of our asynchronous game. For w = ((e¹, v¹), (e², v²), (e³, v³), ...)∈ [P], we set

bi(w) :=

(0 if vⁱ _{∈ e}ⁱ, 1 if vⁱ _{∈ e}/ ⁱ. Then we define

f(w) =^X

i>0

bi^(w)

2ⁱ

Thus f(w) does not only evaluate the number of damaged edges through w , but also evaluate the promptness of attacks.

(78)

Payoff Function

bi(w) :=

f(w) =^X

i>0

bi^(w)

2ⁱ

(79)

Payoff Function

bi(w) :=

f(w) =^X

i>0

bi^(w)

2ⁱ

(80)

Determinacy of Asynchronous Game

Theorem

The asynchronous gameΓ(G; f ) is determined. Proof (idea)

We show the existence of a stable solution in the game without referring to the Blackwell determinacy.

We reduced the infinite gameΓ(G; f ) to a finite-round game.

(81)

Determinacy of Asynchronous Game

Theorem

The asynchronous gameΓ(G; f ) is determined. Proof (idea)

We show the existence of a stable solution in the game without referring to the Blackwell determinacy.

We reduced the infinite gameΓ(G; f ) to a finite-round game.

(82)

Infinite game Γ(G; f )

(83)

Finite-round game (or finite transition system)

(84)

Concluding Remarks

We have considered various conditions for computing mixed Nash equilibria for this game.

Then, we generalized it to an asynchronous game, which may be viewed as a special Blackwell game.

We have shown that an asynchronous game can be constructively reduced to a finite-round game.

(85)

ThankYou

(86)

References I

A. Termimi, A.G. and Tanaka, K.:

Network Games with Many Attackers and Defenders. Proceedings of Research Institute for Mathematical Sciences (RIMS) Kôkyûroku Kyoto University. 1729, 146–151, 2011.

Blackwell. D.:

Infinite G_δgames with imperfect information.

Zastosowania Matematyki Applicationes Mathematicae, Hugo Steinhaus Jubilee Volume X, p. 99-101, 1969.

(87)

References II

Gelastou, M., Mavronicholas, M., Papadopoulou, V.G., Philippou, A. and Spirakis, P.:

The Power of the Defender.

CD-ROM Proceedings of the 2nd International Workshop on Incentive-Based Computing, July 2006.

Hall, P.:

On representatives of subsets

J. London Math. Soc..10, 26–30, 1935. Martin, D.A.:

The determinacy of Blackwell games.

Journal Symbolic Logic. 63(4), 1565–1581, 1998.

(88)

References III

Mavronicholas, M., Papadopoulou, V.G., Philippou, A., Spirakis, P.G.:

A Network Game with Attacker and Protector Entities. Proceedings of the 16th Annual International Symposium on Algorithms and Computation,. 3827, 288–297, 2005. Mavronicholas, M., Papadopoulou, V.G., Philippou, A., Spirakis, P.G.:

A Graph-Theoretic Network Security Game.

Proceedings of the 1st International Workshop on Internet and Network Economics. 3828, 969–978, LNCS, 2005.

(89)

References IV

Mavronicholas, M., Michael, L., Papadopoulou, V.G., Philippou, A., Spirakis, P.G.:

The Price of Defense.

Proceedings of the 31st International Symposium on Mathematical Foundations of Computer Science. 4162, 717–728, LNCS, 2006.

MedYahya Ould-MedSalem., Manoussakis, Y.,Tanaka, K.: A Game on Graphs with Many non-Centralized Defenders. (EURO XXII) 22nd European Conference on Operations Research. July 8–11, Prague, 2007.

(90)

References V

Nash, J.F:

Equilibrium Points in n-Person Games.

Proceedings of the National Academy of Sciences, 36, 48–49, 1950.

Nash, J.F.:

Noncooperative Games.

Annals of Maths, 54, 286–295, 1951. West, D.B.:

Introduction to Graph Theory. Prentice Hall. 2nd edition, 2001.

(91)

References VI

A. Termimi, A.G. and Tanaka, K.:

Network Games with and without Synchroneity.

In: Baras J.S., Katz, J., Altman, E. (eds.) GAMESEC 2011. LNCS, vol. 7037, pp.87-103. Springer, Heidelberg (2011)