Algorithms for Finding the Best Pure Nash Equilibrium in Edge-weighted Budgeted Maximum Coverage Games
<|reference_start|>Algorithms for Finding the Best Pure Nash Equilibrium in Edge-weighted Budgeted Maximum Coverage Games: This paper introduces a new integer programming game (IPG) named the Edge-weighted Budgeted Maximum Coverage (EBMC) game and proposes a new algorithm, the Best Response Plus (BR-plus) algorithm, for finding the best Pure Nash Equilibrium (PNE). We demonstrate this methodology by optimizing county-level decisions to prevent aquatic invasive species (AIS) in Minnesota lakes, where each county-level decision makers has self-serving objectives while AIS is an interconnected issue that crosses county borders. Specifically, we develop EBMC games to model the strategic interactions among county-level decision-makers with two variations in utility functions. We also study and prove the existence of a PNE in these models under specified conditions. We advance the current state-of-the-art, which is limited to only a few players, by presenting the BR-plus algorithm that can handle a large set of players via utilizing the best response dynamics for finding PNE in normal-form games. Experimental results show that our BR-plus algorithm offers computational advantages over the ZR algorithm, especially in larger games, on both random and real-world networks.<|reference_end|>
@article{lee2024algorithms,
    title={Algorithms for Finding the Best Pure Nash Equilibrium in Edge-weighted
  Budgeted Maximum Coverage Games},
    author={Hyunwoo Lee, Robert Hildebrand, Wenbo Cai, .I. Esra
  B"uy"uktahtak{i}n},
    journal={arXiv preprint arXiv:2409.04078},
    year={2024},
    archivePrefix={arXiv},
    eprint={2409.04078},
    primaryClass={cs.GT math.OC}
}