Layered Graph Security Games
<|reference_start|>Layered Graph Security Games: Security games model strategic interactions in adversarial real-world applications. Such applications often involve extremely large but highly structured strategy sets (e.g., selecting a distribution over all patrol routes in a given graph). In this paper, we represent each player's strategy space using a layered graph whose paths represent an exponentially large strategy space. Our formulation entails not only classic pursuit-evasion games, but also other security games, such as those modeling anti-terrorism and logistical interdiction. We study two-player zero-sum games under two distinct utility models: linear and binary utilities. We show that under linear utilities, Nash equilibrium can be computed in polynomial time, while binary utilities may lead to situations where even computing a best-response is computationally intractable. To this end, we propose a practical algorithm based on incremental strategy generation and mixed integer linear programs. We show through extensive experiments that our algorithm efficiently computes $\epsilon$-equilibrium for many games of interest. We find that target values and graph structure often have a larger influence on running times as compared to the size of the graph per se.<|reference_end|>
@article{černý2024layered,
    title={Layered Graph Security Games},
    author={Jakub v{C}ern'y, Chun Kai Ling, Christian Kroer, Garud Iyengar},
    journal={arXiv preprint arXiv:2405.03070},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.03070},
    primaryClass={cs.GT}
}