TY - JOUR AU - An, Bo AU - Tambe, Milind AU - Ordonez, Fernando AU - Shieh, Eric AU - Kiekintveld, Christopher PY - 2011/08/04 Y2 - 2024/03/28 TI - Refinement of Strong Stackelberg Equilibria in Security Games JF - Proceedings of the AAAI Conference on Artificial Intelligence JA - AAAI VL - 25 IS - 1 SE - AAAI Technical Track: Multiagent Systems DO - 10.1609/aaai.v25i1.7864 UR - https://ojs.aaai.org/index.php/AAAI/article/view/7864 SP - 587-593 AB - <p> Given the real-world deployments of attacker-defender Stackelberg security games, robustness to deviations from expected attacker behaviors has now emerged as a critically important issue. This paper provides four key contributions in this context. First, it identifies a fundamentally problematic aspect of current algorithms for security games. It shows that there are many situations where these algorithms face multiple equilibria, and they arbitrarily select one that may hand the defender a significant disadvantage, particularly if the attacker deviates from its equilibrium strategies due to unknown constraints. Second, for important subclasses of security games, it identifies situations where we will face such multiple equilibria. Third, to address these problematic situations, it presents two equilibrium refinement algorithms that can optimize the defender's utility if the attacker deviates from equilibrium strategies. Finally, it experimentally illustrates that the refinement approach achieved significant robustness in consideration of attackers' deviation due to unknown constraints. </p> ER -