Equilibrium strategies for multiple interdictors on a common network |
| |
| Authors: | Harikrishnan Sreekumaran Ashish R. Hota Andrew L. Liu Nelson A. Uhan Shreyas Sundaram |
| |
| Affiliation: | 1. Amazon, Seattle, WA, USA;2. Department of Electrical Engineering, Indian Institute of Technology (IIT), Kharagpur, India;3. School of Industrial Engineering, Purdue University, West Lafayette, IN, USA;4. Mathematics Department, United States Naval Academy, Annapolis, MD, USA;5. School of Electrical and Computer Engineering, Purdue University, West Lafayette, IN, USA;1. Department of Economics, Universidad Pablo de Olavide, Spain;2. Department of Statistics and Operations ResearchUniversidade de Vigo, Spain;1. Department of Econometrics and Operations Research, Tinbergen Institute, VU University, De Boelelaan 1105, Amsterdam 1081 HV, the Netherlands;2. Paris School of Economics, Centre d’Economie de la Sorbonne, CNRS, Université Paris 1, 106-112 Bd de l’Hôpital, Paris Cedex 13 75647, France;1. East China University of Science and Technology, 130 Meilong Rd, Xuhui Qu, Shanghai 200237,China;2. University of Missouri-St. Louis, 1 University Blvd., St. Louis, MO 63139 USA;3. University of Southern California, 650 Childs Way, Los Angeles, CA 90089, USA;1. Department of Management Science, University of Strathclyde, Glasgow, UK;2. Department of Mathematics and CIDMA, University of Aveiro, Aveiro, Portugal;1. Department of Industrial Engineering, School of Management, Hangzhou Dianzi University, Hangzhou, 310018, China;2. Department of Industrial Engineering, School of Management, Xi''an Jiaotong University, Xi''an, 710049, China |
| |
| Abstract: | In this work, we introduce multi-interdictor games, which model interactions among multiple interdictors with differing objectives operating on a common network. As a starting point, we focus on shortest path multi-interdictor (SPMI) games, where multiple interdictors try to increase the shortest path lengths of their own adversaries attempting to traverse a common network. We first establish results regarding the existence of equilibria for SPMI games under both discrete and continuous interdiction strategies. To compute such an equilibrium, we present a reformulation of the SPMI game, which leads to a generalized Nash equilibrium problem (GNEP) with non-shared constraints. While such a problem is computationally challenging in general, we show that under continuous interdiction actions, an SPMI game can be formulated as a linear complementarity problem and solved by Lemke’s algorithm. In addition, we present decentralized heuristic algorithms based on best response dynamics for games under both continuous and discrete interdiction strategies. Finally, we establish theoretical lower bounds on the worst-case efficiency loss of equilibria in SPMI games, with such loss caused by the lack of coordination among noncooperative interdictors, and use the decentralized algorithms to numerically study the average-case efficiency loss. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
