TY - GEN

T1 - Linear loss function for the network blocking game

T2 - 3rd International Conference on Decision and Game Theory for Security, GameSec 2012

AU - Laszka, Aron

AU - Szeszlér, Dávid

AU - Buttyán, Levente

PY - 2012

Y1 - 2012

N2 - In order to design robust networks, first, one has to be able to measure robustness of network topologies. In [1], a game-theoretic model, the network blocking game, was proposed for this purpose, where a network operator and an attacker interact in a zero-sum game played on a network topology, and the value of the equilibrium payoff in this game is interpreted as a measure of robustness of that topology. The payoff for a given pair of pure strategies is based on a loss-in-value function. Besides measuring the robustness of network topologies, the model can be also used to identify critical edges that are likely to be attacked. Unfortunately, previously proposed loss-in-value functions are either too simplistic or lead to a game whose equilibrium is not known to be computable in polynomial time. In this paper, we propose a new, linear loss-in-value function, which is meaningful and leads to a game whose equilibrium is efficiently computable. Furthermore, we show that the resulting game-theoretic robustness metric is related to the Cheeger constant of the topology graph, which is a well-known metric in graph theory.

AB - In order to design robust networks, first, one has to be able to measure robustness of network topologies. In [1], a game-theoretic model, the network blocking game, was proposed for this purpose, where a network operator and an attacker interact in a zero-sum game played on a network topology, and the value of the equilibrium payoff in this game is interpreted as a measure of robustness of that topology. The payoff for a given pair of pure strategies is based on a loss-in-value function. Besides measuring the robustness of network topologies, the model can be also used to identify critical edges that are likely to be attacked. Unfortunately, previously proposed loss-in-value functions are either too simplistic or lead to a game whose equilibrium is not known to be computable in polynomial time. In this paper, we propose a new, linear loss-in-value function, which is meaningful and leads to a game whose equilibrium is efficiently computable. Furthermore, we show that the resulting game-theoretic robustness metric is related to the Cheeger constant of the topology graph, which is a well-known metric in graph theory.

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

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

U2 - 10.1007/978-3-642-34266-0_9

DO - 10.1007/978-3-642-34266-0_9

M3 - Conference contribution

AN - SCOPUS:84869464435

SN - 9783642342653

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

SP - 152

EP - 170

BT - Decision and Game Theory for Security - Third International Conference, GameSec 2012, Proceedings

Y2 - 5 November 2012 through 6 November 2012

ER -