article
How many attackers can selfish defenders catch?
Marios
Mavronicolas
author
Burkhard
Monien
author
Vicky
Papadopoulou Lesta
author
SFB 901
project
SFB 901 - Subprojekt A3
project
SFB 901 - Project Area A
project
In a distributed system with attacks and defenses, both attackers and defenders are self-interested entities. We assume a reward-sharing scheme among interdependent defenders; each defender wishes to (locally) maximize her own total fair share to the attackers extinguished due to her involvement (and possibly due to those of others). What is the maximum amount of protection achievable by a number of such defenders against a number of attackers while the system is in a Nash equilibrium? As a measure of system protection, we adopt the Defense-Ratio (Mavronicolas et al., 2008)[20], which provides the expected (inverse) proportion of attackers caught by the defenders. In a Defense-Optimal Nash equilibrium, the Defense-Ratio matches a simple lower bound.We discover that the existence of Defense-Optimal Nash equilibria depends in a subtle way on how the number of defenders compares to two natural graph-theoretic thresholds we identify. In this vein, we obtain, through a combinatorial analysis of Nash equilibria, a collection of trade-off results:• When the number of defenders is either sufficiently small or sufficiently large, Defense-Optimal Nash equilibria may exist. The corresponding decision problem is computationally tractable for a large number of defenders; the problem becomes NPNP-complete for a small number of defenders and the intractability is inherited from a previously unconsidered combinatorial problem in Fractional Graph Theory.• Perhaps paradoxically, there is a middle range of values for the number of defenders where Defense-Optimal Nash equilibria do not exist.
https://ris.uni-paderborn.de/download/523/1297/523-MMP13.pdf
application/pdf
Elsevier2013
eng
Discrete Applied Mathematics10.1016/j.dam.2013.05.022
16116-172563-2586
Mavronicolas, M., Monien, B., & Papadopoulou Lesta, V. (2013). How many attackers can selfish defenders catch? <i>Discrete Applied Mathematics</i>, <i>161</i>(16–17), 2563–2586. <a href="https://doi.org/10.1016/j.dam.2013.05.022">https://doi.org/10.1016/j.dam.2013.05.022</a>
M. Mavronicolas, B. Monien, and V. Papadopoulou Lesta, “How many attackers can selfish defenders catch?,” <i>Discrete Applied Mathematics</i>, vol. 161, no. 16–17, pp. 2563–2586, 2013.
Mavronicolas, Marios, Burkhard Monien, and Vicky Papadopoulou Lesta. “How Many Attackers Can Selfish Defenders Catch?” <i>Discrete Applied Mathematics</i> 161, no. 16–17 (2013): 2563–86. <a href="https://doi.org/10.1016/j.dam.2013.05.022">https://doi.org/10.1016/j.dam.2013.05.022</a>.
M. Mavronicolas, B. Monien, V. Papadopoulou Lesta, Discrete Applied Mathematics 161 (2013) 2563–2586.
@article{Mavronicolas_Monien_Papadopoulou Lesta_2013, title={How many attackers can selfish defenders catch?}, volume={161}, DOI={<a href="https://doi.org/10.1016/j.dam.2013.05.022">10.1016/j.dam.2013.05.022</a>}, number={16–17}, journal={Discrete Applied Mathematics}, publisher={Elsevier}, author={Mavronicolas, Marios and Monien, Burkhard and Papadopoulou Lesta, Vicky}, year={2013}, pages={2563–2586} }
Mavronicolas, Marios, et al. “How Many Attackers Can Selfish Defenders Catch?” <i>Discrete Applied Mathematics</i>, vol. 161, no. 16–17, Elsevier, 2013, pp. 2563–86, doi:<a href="https://doi.org/10.1016/j.dam.2013.05.022">10.1016/j.dam.2013.05.022</a>.
Mavronicolas M, Monien B, Papadopoulou Lesta V. How many attackers can selfish defenders catch? <i>Discrete Applied Mathematics</i>. 2013;161(16-17):2563-2586. doi:<a href="https://doi.org/10.1016/j.dam.2013.05.022">10.1016/j.dam.2013.05.022</a>
5232017-10-17T12:42:34Z2019-01-03T13:16:53Z