02/02/2021

Coalition Formation in Multi-defender Security Games

Dolev Mutzari, Jiarui Gan, Sarit Kraus

Keywords:

Abstract Paper Similar Papers

Abstract: We study Stackelberg security game (SSG) with multiple defenders, where heterogeneous defenders need to allocate security resources to protect a set of targets against a strategic attacker. In such games, coordination and cooperation between the defenders can increase their ability to protect their assets, but the heterogeneous preferences of the self-interested defenders often make such cooperation very difficult. In this paper, we approach the problem from the perspective of cooperative game theory and study coalition formation among the defenders. Our main contribution is a number of algorithmic results for the computation problems that arise in this model. We provide a poly-time algorithm for computing a solution in the core of the game and show that all of the elements in the core are Pareto efficient. We show that the problem of computing the entire core is NP-hard and then delve into a special setting where the size of a coalition is limited up to some threshold. We analyse the parameterized complexity of deciding if a coalition structure is in the core under this special setting, and provide a poly-time algorithm for computing successful deviation strategies for a given coalition.

The video of this talk cannot be embedded. You can watch it here:
https://slideslive.com/38948071
(Link will open in new window)
 0
 0
 0
 0
  Share    
This is an embedded video. Talk and the respective paper are published at AAAI 2021 virtual conference. If you are one of the authors of the paper and want to manage your upload, see the question "My papertalk has been externally embedded..." in the FAQ section.

Comments

Post Comment
no comments yet
code of conduct: tbd Characters remaining: 140

Similar Papers

 0
 0
 0
 0
 14:02 
 0
 0
 0
 0
 4:52 
 0
 0
 0
 0
 5:21 
 0
 0
 0
 0
 17:06 
 0
 0
 0
 0
 16:35 
 0
 0
 0
 0
 3:32 
 0
 0
 0
 0
 14:59 
 0
 0
 0
 0
 12:30 
 0
 0
 0
 0
 11:52 
 0
 0
 0
 0
 10:33 
 0
 0
 0
 0
 15:01 
 0
 0
 0
 0
 20:14 
 0
 0
 0
 0
 15:01 
 0
 0
 0
 0
 16:33 
 0
 0
 0
 0
 3:32 
 0
 0
 0
 0
 15:02 
 0
 0
 0
 0
 15:35 
 0
 0
 0
 0
 3:15 
 0
 0
 0
 0
 15:07 
 0
 0
 0
 0
 20:10 
 0
 0
 0
 0
 15:46 
 0
 0
 0
 0
 16:54 
 0
 0
 0
 0
 15:20 
 0
 0
 0
 0
 14:42 
 0
 0
 0
 0
 18:49 
 0
 0
 0
 0
 14:35 
 0
 0
 0
 0
 11:20 
 0
 0
 0
 0
 15:03 
 0
 0
 0
 0
 12:59 
 0
 0
 0
 0
 4:38 
 0
 0
 0
 0
 15:35 
 0
 0
 0
 0
 3:11 
 0
 0
 0
 0
 2:53 
 0
 0
 0
 0
 13:17 
 0
 0
 0
 0
 17:04 
 0
 0
 0
 0
 13:19 
 0
 0
 0
 0
 3:23 
 0
 0
 0
 0
 3:00 
 0
 0
 0
 0
 12:14 
 0
 0
 0
 0
 5:30