Tackling Stackelberg network interdiction against a boundedly rational adversary

• Main Authors: MAI, Tien, BOSE, Avinandan, SINHA, Arunesh, NGUYEN, Thanh, SINGH, Ayushman Kumar
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2024
• Subjects: Noncooperative games; Mixed discrete and continuous optimization; Artificial Intelligence and Robotics; Computer Sciences
• Online Access: https://ink.library.smu.edu.sg/sis_research/9690; https://ink.library.smu.edu.sg/context/sis_research/article/10690/viewcontent/2301.12232v1.pdf
• Institution: Singapore Management University

This work studies Stackelberg network interdiction games --- an important class of games in which a defender first allocates (randomized) defense resources to a set of critical nodes on a graph while an adversary chooses its path to attack these nodes accordingly. We consider a boundedly rational adversary in which the adversary's response model is based on a dynamic form of classic logit-based (quantal response) discrete choice models. The resulting optimization is non-convex and additionally, involves complex terms that sum over exponentially many paths. We tackle these computational challenges by presenting new efficient algorithms with solution guarantees. First, we present a near optimal solution method based on path sampling, piece-wise linear approximation and mixed-integer linear programming (MILP) reformulation. Second, we explore a dynamic programming based method, addressing the exponentially-many-path challenge. We then show that the gradient of the non-convex objective can also be computed in polynomial time, which allows us to use a gradient-based method to solve the problem efficiently. Experiments based on instances of different sizes demonstrate the efficiency of our approach in achieving near-optimal solutions.