TY - GEN

T1 - Quantifying network topology robustness under budget constraints

T2 - 4th International Conference on Decision and Game Theory for Security, GameSec 2013

AU - Laszka, Aron

AU - Gueye, Assane

PY - 2013

Y1 - 2013

N2 - Recently, network blocking game (NBG) models have been introduced and utilized to quantify the vulnerability of network topologies in adversarial environments. In NBG models, the payoff matrix of the game is only "implicitly " given. As a consequence, computing a Nash equilibrium in these games is expected to be harder than in more conventional models, where the payoff matrix is "explicitly " given. In this paper, we first show that computing a Nash equilibrium of a NBG is in general NP-hard. Surprisingly, however, there are particular interesting cases for which the game can be solved in polynomial time. We revisit these cases in a framework where the network is to be operated under budget constraints, which previous models did not consider. We generalize previous blocking games by introducing a budget limit on the operator and consider two constraint formulations: the maximum and the expected cost constraints. For practical applications, the greatest challenge posed by blocking games is their computational complexity. Therefore, we show that the maximum cost constraint leads to NP-hard problems, even for games that were shown to be efficiently solvable in the unconstrained case. On the other hand, we show that the expected cost constraint formulation leads to games that can be solved efficiently.

AB - Recently, network blocking game (NBG) models have been introduced and utilized to quantify the vulnerability of network topologies in adversarial environments. In NBG models, the payoff matrix of the game is only "implicitly " given. As a consequence, computing a Nash equilibrium in these games is expected to be harder than in more conventional models, where the payoff matrix is "explicitly " given. In this paper, we first show that computing a Nash equilibrium of a NBG is in general NP-hard. Surprisingly, however, there are particular interesting cases for which the game can be solved in polynomial time. We revisit these cases in a framework where the network is to be operated under budget constraints, which previous models did not consider. We generalize previous blocking games by introducing a budget limit on the operator and consider two constraint formulations: the maximum and the expected cost constraints. For practical applications, the greatest challenge posed by blocking games is their computational complexity. Therefore, we show that the maximum cost constraint leads to NP-hard problems, even for games that were shown to be efficiently solvable in the unconstrained case. On the other hand, we show that the expected cost constraint formulation leads to games that can be solved efficiently.

UR - http://www.scopus.com/inward/record.url?scp=84893384904&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84893384904&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-02786-9_10

DO - 10.1007/978-3-319-02786-9_10

M3 - Conference contribution

AN - SCOPUS:84893384904

SN - 9783319027852

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 154

EP - 174

BT - Decision and Game Theory for Security - 4th International Conference, GameSec 2013, Proceedings

PB - Springer Verlag

Y2 - 11 November 2013 through 12 November 2013

ER -