---
_id: '523'
abstract:
- lang: eng
text: 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.
accept: '1'
author:
- first_name: Marios
full_name: Mavronicolas, Marios
last_name: Mavronicolas
- first_name: Burkhard
full_name: Monien, Burkhard
last_name: Monien
- first_name: Vicky
full_name: Papadopoulou Lesta, Vicky
last_name: Papadopoulou Lesta
citation:
ama: Mavronicolas M, Monien B, Papadopoulou Lesta V. How many attackers can selfish
defenders catch? *Discrete Applied Mathematics*. 2013;161(16-17):2563-2586.
doi:10.1016/j.dam.2013.05.022
apa: Mavronicolas, M., Monien, B., & Papadopoulou Lesta, V. (2013). How many
attackers can selfish defenders catch? *Discrete Applied Mathematics*, *161*(16–17),
2563–2586. https://doi.org/10.1016/j.dam.2013.05.022
bibtex: '@article{Mavronicolas_Monien_Papadopoulou Lesta_2013, title={How many attackers
can selfish defenders catch?}, volume={161}, DOI={10.1016/j.dam.2013.05.022},
number={16–17}, journal={Discrete Applied Mathematics}, publisher={Elsevier},
author={Mavronicolas, Marios and Monien, Burkhard and Papadopoulou Lesta, Vicky},
year={2013}, pages={2563–2586} }'
chicago: 'Mavronicolas, Marios, Burkhard Monien, and Vicky Papadopoulou Lesta. “How
Many Attackers Can Selfish Defenders Catch?” *Discrete Applied Mathematics*
161, no. 16–17 (2013): 2563–86. https://doi.org/10.1016/j.dam.2013.05.022.'
ieee: M. Mavronicolas, B. Monien, and V. Papadopoulou Lesta, “How many attackers
can selfish defenders catch?,” *Discrete Applied Mathematics*, vol. 161,
no. 16–17, pp. 2563–2586, 2013.
mla: Mavronicolas, Marios, et al. “How Many Attackers Can Selfish Defenders Catch?”
*Discrete Applied Mathematics*, vol. 161, no. 16–17, Elsevier, 2013, pp.
2563–86, doi:10.1016/j.dam.2013.05.022.
short: M. Mavronicolas, B. Monien, V. Papadopoulou Lesta, Discrete Applied Mathematics
161 (2013) 2563–2586.
date_created: 2017-10-17T12:42:34Z
date_updated: 2019-01-03T13:16:53Z
ddc:
- '040'
doi: 10.1016/j.dam.2013.05.022
file:
- access_level: closed
content_type: application/pdf
creator: florida
date_created: 2018-03-15T10:37:35Z
date_updated: 2018-03-15T10:37:35Z
file_id: '1297'
file_name: 523-MMP13.pdf
file_size: 1127543
open_access: 1
relation: main_file
success: 1
file_date_updated: 2018-03-15T10:37:35Z
intvolume: ' 161'
issue: 16-17
language:
- iso: eng
page: 2563-2586
project:
- _id: '1'
name: SFB 901
- _id: '7'
name: SFB 901 - Subprojekt A3
- _id: '2'
name: SFB 901 - Project Area A
publication: Discrete Applied Mathematics
publisher: Elsevier
status: public
title: How many attackers can selfish defenders catch?
type: journal_article
user_id: '42447'
volume: 161
year: '2013'
...