Solving a Stackelberg Game on Transportation Networks in a Dynamic Crime Scenario: A Mixed Approach on Multi-Layer Networks

• URL: http://arxiv.org/abs/2406.14514v2
• Date: Wed, 23 Oct 2024 07:05:18 GMT
• Title: Solving a Stackelberg Game on Transportation Networks in a Dynamic Crime Scenario: A Mixed Approach on Multi-Layer Networks
• Authors: Sukanya Samanta, Kei Kimura, Makoto Yokoo,
• Abstract summary: Interdicting a criminal with limited police resources is a challenging task as the criminal changes location over time. We consider the concept of a layered graph to track the movements of both players, the attacker and the defenders. We develop an approximation algorithm on the layered networks to find near-optimal strategy for defenders.
• Score: 7.717719152704306
• License:
• Abstract: Interdicting a criminal with limited police resources is a challenging task as the criminal changes location over time. The size of the large transportation network further adds to the difficulty of this scenario. To tackle this issue, we consider the concept of a layered graph. At each time stamp, we create a copy of the entire transportation network to track the possible movements of both players, the attacker and the defenders. We consider a Stackelberg game in a dynamic crime scenario where the attacker changes location over time while the defenders attempt to interdict the attacker on his escape route. Given a set of defender strategies, the optimal attacker strategy is determined by applying Dijkstra's algorithm on the layered networks. Here, the attacker aims to minimize while the defenders aim to maximize the probability of interdiction. We develop an approximation algorithm on the layered networks to find near-optimal strategy for defenders. The efficacy of the developed approach is compared with the adopted MILP approach. We compare the results in terms of computational time and solution quality. The quality of the results demonstrates the need for the developed approach, as it effectively solves the complex problem within a short amount of time.

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)
• Graph Neural Networks for Decentralized Multi-Agent Perimeter Defense [111.9039128130633]
  We develop an imitation learning framework that learns a mapping from defenders' local perceptions and their communication graph to their actions. We run perimeter defense games in scenarios with different team sizes and configurations to demonstrate the performance of the learned network.
  arXiv  Detail & Related papers  (2023-01-23T19:35:59Z)
• Learning Decentralized Strategies for a Perimeter Defense Game with Graph Neural Networks [111.9039128130633]
  We design a graph neural network-based learning framework to learn a mapping from defenders' local perceptions and the communication graph to defenders' actions. We demonstrate that our proposed networks stay closer to the expert policy and are superior to other baseline algorithms by capturing more intruders.
  arXiv  Detail & Related papers  (2022-09-24T22:48:51Z)
• Distributed Task Management in Fog Computing: A Socially Concave Bandit Game [7.708904950194129]
  Fog computing leverages the task offloading capabilities at the network's edge to improve efficiency and enable swift responses to application demands. We formulate the distributed task allocation problem as a social-concave game with bandit feedback. We develop two no-regret online decision-making strategies.
  arXiv  Detail & Related papers  (2022-03-28T08:26:14Z)
• Projective Ranking-based GNN Evasion Attacks [52.85890533994233]
  Graph neural networks (GNNs) offer promising learning methods for graph-related tasks. GNNs are at risk of adversarial attacks.
  arXiv  Detail & Related papers  (2022-02-25T21:52:09Z)
• Fixed Points in Cyber Space: Rethinking Optimal Evasion Attacks in the Age of AI-NIDS [70.60975663021952]
  We study blackbox adversarial attacks on network classifiers. We argue that attacker-defender fixed points are themselves general-sum games with complex phase transitions. We show that a continual learning approach is required to study attacker-defender dynamics.
  arXiv  Detail & Related papers  (2021-11-23T23:42:16Z)
• Game Theory for Adversarial Attacks and Defenses [0.0]
  Adrial attacks can generate adversarial inputs by applying small but intentionally worst-case perturbations to samples from the dataset. Some adversarial defense techniques are developed to improve the security and robustness of the models and avoid them being attacked.
  arXiv  Detail & Related papers  (2021-10-08T07:38:33Z)
• Learning Generative Deception Strategies in Combinatorial Masking Games [27.2744631811653]
  One way deception can be employed is through obscuring, or masking, some of the information about how systems are configured. We present a novel game-theoretic model of the resulting defender-attacker interaction, where the defender chooses a subset of attributes to mask, while the attacker responds by choosing an exploit to execute. We present a novel highly scalable approach for approximately solving such games by representing the strategies of both players as neural networks.
  arXiv  Detail & Related papers  (2021-09-23T20:42:44Z)
• Sparse and Imperceptible Adversarial Attack via a Homotopy Algorithm [93.80082636284922]
  Sparse adversarial attacks can fool deep networks (DNNs) by only perturbing a few pixels. Recent efforts combine it with another l_infty perturbation on magnitudes. We propose a homotopy algorithm to tackle the sparsity and neural perturbation framework.
  arXiv  Detail & Related papers  (2021-06-10T20:11:36Z)
• RayS: A Ray Searching Method for Hard-label Adversarial Attack [99.72117609513589]
  We present the Ray Searching attack (RayS), which greatly improves the hard-label attack effectiveness as well as efficiency. RayS attack can also be used as a sanity check for possible "falsely robust" models.
  arXiv  Detail & Related papers  (2020-06-23T07:01:50Z)

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.