New Algorithmic Method Improves Finite-Memory Strategies in Adversarial Patrolling Games

A computational research paper introduces a novel general method for optimizing finite-memory strategies in adversarial patrolling games, a subclass of security games. The work addresses a significant open problem: the manual assignment of memory size at each location, which has limited the practical application of these strategies. Finite-memory strategies, also known as regular strategies, have been shown to outperform other classes in experimental settings. These strategies function as positional strategies operating on a finite set of states, where each state combines a location with an integer memory value. While existing algorithms refine the transitional probabilities between states, they rely on a pre-determined, manually assigned memory allocation. The newly developed method proposes an iterative approach to automate and improve this memory assignment process, potentially enhancing the Defender's ability to minimize worst-case damage from an Attacker. The research is documented in the paper "Memory Assignment for Finite-Memory Strategies in Adversarial Patrolling Games," identified as arXiv:2505.14137v2, which was announced as a replacement. In these security scenarios, a Defender patrols between locations to protect vulnerable targets against an Attacker.