Publication Type

Conference Proceeding Article

Version

acceptedVersion

Publication Date

8-2024

Abstract

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.

Keywords

Noncooperative games; Mixed discrete and continuous optimization

Discipline

Artificial Intelligence and Robotics | Computer Sciences

Research Areas

Data Science and Engineering; Intelligent Systems and Optimization

Areas of Excellence

Digital transformation

Publication

Proceedings of the 33rd International Joint Conference on Artificial Intelligence (IJCAI 2024) : Jeju, South Korea, August 3-9

First Page

2913

Last Page

2921

Identifier

10.24963/ijcai.2024/323

Publisher

International Joint Conferences on Artificial Intelligence

City or Country

Jeju, South Korea

Additional URL

https://doi.org/10.24963/ijcai.2024/323

Download

Share

COinS