Multi-defender Security Games with Schedules

• URL: http://arxiv.org/abs/2311.16392v1
• Date: Tue, 28 Nov 2023 00:39:02 GMT
• Title: Multi-defender Security Games with Schedules
• Authors: Zimeng Song, Chun Kai Ling, Fei Fang
• Abstract summary: Security games are often used to model strategic interactions in high-stakes security settings. Many realistic scenarios feature multiple heterogeneous defenders with their own interests and priorities embedded in a more complex system. We show that unlike prior work on multi-defender security games, the introduction of schedules can cause non-existence of equilibrium.
• Score: 42.32444288821052
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Stackelberg Security Games are often used to model strategic interactions in high-stakes security settings. The majority of existing models focus on single-defender settings where a single entity assumes command of all security assets. However, many realistic scenarios feature multiple heterogeneous defenders with their own interests and priorities embedded in a more complex system. Furthermore, defenders rarely choose targets to protect. Instead, they have a multitude of defensive resources or schedules at its disposal, each with different protective capabilities. In this paper, we study security games featuring multiple defenders and schedules simultaneously. We show that unlike prior work on multi-defender security games, the introduction of schedules can cause non-existence of equilibrium even under rather restricted environments. We prove that under the mild restriction that any subset of a schedule is also a schedule, non-existence of equilibrium is not only avoided, but can be computed in polynomial time in games with two defenders. Under additional assumptions, our algorithm can be extended to games with more than two defenders and its computation scaled up in special classes of games with compactly represented schedules such as those used in patrolling applications. Experimental results suggest that our methods scale gracefully with game size, making our algorithms amongst the few that can tackle multiple heterogeneous defenders.

Related papers

• Patrol Security Game: Defending Against Adversary with Freedom in Attack Timing, Location, and Duration [4.765278970103286]
  Patrol Security Game (PSG) is a robotic patrolling problem modeled as an extensive-form deterministic Stackelberg problem. Our objective is to devise a synthetic schedule that minimizes the attacker's time horizon.
  arXiv  Detail & Related papers  (2024-10-21T02:53:18Z)
• Securing Equal Share: A Principled Approach for Learning Multiplayer Symmetric Games [21.168085154982712]
  equilibria in multiplayer games are neither unique nor non-exploitable. This paper takes an initial step towards addressing these challenges by focusing on the natural objective of equal share. We design a series of efficient algorithms, inspired by no-regret learning, that provably attain approximate equal share across various settings.
  arXiv  Detail & Related papers  (2024-06-06T15:59:17Z)
• Optimistic Policy Gradient in Multi-Player Markov Games with a Single Controller: Convergence Beyond the Minty Property [89.96815099996132]
  We develop a new framework to characterize optimistic policy gradient methods in multi-player games with a single controller. Our approach relies on a natural generalization of the classical Minty property that we introduce, which we anticipate to have further applications beyond Markov games.
  arXiv  Detail & Related papers  (2023-12-19T11:34:10Z)
• Cooperation or Competition: Avoiding Player Domination for Multi-Target Robustness via Adaptive Budgets [76.20705291443208]
  We view adversarial attacks as a bargaining game in which different players negotiate to reach an agreement on a joint direction of parameter updating. We design a novel framework that adjusts the budgets of different adversaries to avoid any player dominance. Experiments on standard benchmarks show that employing the proposed framework to the existing approaches significantly advances multi-target robustness.
  arXiv  Detail & Related papers  (2023-06-27T14:02:10Z)
• Finding mixed-strategy equilibria of continuous-action games without gradients using randomized policy networks [83.28949556413717]
  We study the problem of computing an approximate Nash equilibrium of continuous-action game without access to gradients. We model players' strategies using artificial neural networks. This paper is the first to solve general continuous-action games with unrestricted mixed strategies and without any gradient information.
  arXiv  Detail & Related papers  (2022-11-29T05:16:41Z)
• Rigidity for Monogamy-of-Entanglement Games [0.6091702876917281]
  We study the prototypical example of a game where the referee measures in either the computational or Hadamard basis. We show that this game satisfies a rigidity property similar to what is known for some nonlocal games. We also show rigidity for multiple copies of the game played in parallel.
  arXiv  Detail & Related papers  (2021-11-15T20:59:17Z)
• Adversarial Online Learning with Variable Plays in the Pursuit-Evasion Game: Theoretical Foundations and Application in Connected and Automated Vehicle Cybersecurity [5.9774834479750805]
  We extend the adversarial/non-stochastic multi-play multi-armed bandit (MPMAB) to the case where the number of arms to play is variable. The work is motivated by the fact that the resources allocated to scan different critical locations in an interconnected transportation system change dynamically over time and depending on the environment.
  arXiv  Detail & Related papers  (2021-10-26T23:09:42Z)
• "What's in the box?!": Deflecting Adversarial Attacks by Randomly Deploying Adversarially-Disjoint Models [71.91835408379602]
  adversarial examples have been long considered a real threat to machine learning models. We propose an alternative deployment-based defense paradigm that goes beyond the traditional white-box and black-box threat models.
  arXiv  Detail & Related papers  (2021-02-09T20:07:13Z)
• Algorithm for Computing Approximate Nash Equilibrium in Continuous Games with Application to Continuous Blotto [1.7132914341329848]
  We present a new algorithm for approximating Nash equilibrium strategies in continuous games. In addition to two-player zero-sum games, our algorithm also applies to multiplayer games and games with imperfect information.
  arXiv  Detail & Related papers  (2020-06-12T19:53:18Z)
• Block Switching: A Stochastic Approach for Deep Learning Security [75.92824098268471]
  Recent study of adversarial attacks has revealed the vulnerability of modern deep learning models. In this paper, we introduce Block Switching (BS), a defense strategy against adversarial attacks based on onity.
  arXiv  Detail & Related papers  (2020-02-18T23:14:25Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.