Artículo de revista
Adaptivity in Network Interdiction
Fecha
2017Registro en:
Lecture Notes in Computer Science, LNCS, Volumen 10575, 2017
16113349
03029743
10.1007/978-3-319-68711-7_3
Autor
Bahamondes, Bastián
Correa Haeussler, José
Matuschke, Jannik
Oriolo, Gianpaolo
Institución
Resumen
We study a network security game arising in the interdiction of fare evasion or smuggling. A defender places a security checkpoint in the network according to a chosen probability distribution over the links of the network. An intruder, knowing this distribution, wants to travel from her initial location to a target node. For every traversed link she incurs a cost equal to the transit time of that link. Furthermore, if she encounters the checkpoint, she has to pay a fine.
The intruder may adapt her path online, exploiting additional knowledge gained along the way. We investigate the complexity of computing optimal strategies for intruder and defender. We give a concise encoding of the intruders optimal strategy and present an approximation scheme to compute it. For the defender, we consider two different objectives: (i) maximizing the intruder’s cost, for which we give an approximation scheme, and (ii) maximizing the collected fine, which we show to be strongly NP-hard. We also give a paramterized bound on the worst-case ratio of the intruders best adaptive strategy to the best non-adaptive strategy, i.e., when she fixes the complete route at the start.