Equilibrium strategies for multiple interdictors on a common network

Harikrishnan Sreekumaran, Ashish R. Hota, Andrew L. Liu, Nelson A. Uhan and Shreyas Sundaram

European Journal of Operational Research, 2021, vol. 288, issue 2, 523-538

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: Multi-agent systems; Interdiction; Game theory; Nash equilibrium; Price of anarchy (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221720305415
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:288:y:2021:i:2:p:523-538

DOI: 10.1016/j.ejor.2020.06.002

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().