Best-Response Dynamics for Large-Scale Integer Programming Games with Applications to Aquatic Invasive Species Prevention

Abstract

This paper presents a scalable algorithm for computing the best pure Nash equilibrium (PNE) in large-scale integer programming games (IPGs). While recent advances in IPG algorithms are extensive, existing methods are limited to a small number of players, typically 𝑛 = 2, 3. Motivated by a county-level aquatic invasive species (AIS) prevention problem involving 84 players, we develop efficient and scalable algorithms that significantly extend the applicability of IPGs. Specifically, we propose the best-response dynamics incorporated zero-regret (BZR) algorithm, which leverages best-response dynamics (BRD) for rapid PNE identification and integrates BRD as a primal heuristic within the zero-regret (ZR) framework. This approach dramatically improves the scalability of IPG algorithms, allowing us to solve IPGs with up to 30 players in random datasets and the 84-player AIS prevention problem with Minnesota data. To model the AIS prevention problem, we introduce the edge-weighted budgeted maximum coverage (EBMC) game, a newclass of IPG that has not been previously studied. We establish theoretical conditions for the existence of a PNE under both selfish and locally altruistic utility functions. Experimental results in EBMC games and knapsack problem games demonstrate that BZR significantly enhances ZR in both finding a PNE and identifying the best PNE, particularly in games with many players.