Locally Optimal Solutions for Integer Programming Games Conference: ; ;

Pravesh Koirala, Mel Krusniak, Forrest Laine · 2025

Read Locally Optimal Solutions for Integer Programming Games Conference: ; ; by Pravesh Koirala, Mel Krusniak, Forrest Laine (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-20918.txt.

Introduction

Pravesh Koirala, Mel Krusniak, and Forrest Laine soften a hard solution idea for integer games in a 2025 paper. Integer programming games model rivals choosing whole-number strategies, from cyber defense to transport. The classic target, Nash equilibrium, is brutal to compute; even asking if one exists is deeply hard.

Their relaxed concept, locally optimal integer solutions, settles for answers no small change can improve. These are faster to find and scale to bigger games. They also allow listing many solutions and picking among them. The frame covers Stackelberg-style leader games too. In a network defense game, the new solutions beat the Nash approach on speed and scale.

Catalog record

CREATORPravesh Koirala, Mel Krusniak, Forrest Laine
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE43 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-20918

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Locally Optimal Solutions for Integer Programming Games Conference: ; ; Pravesh Koirala, Mel Krusniak, Forrest Laine Abstract . Integer programming games (IPGs) are n n -person games with integer strategy spaces. These games are used to model non-cooperative combinatorial decision-making and are used in domains such as cybersecurity and transportation. The prevalent solution concept for IPGs, Nash equilibrium, is difficult to compute and even showing whether such an equilibrium exists is known to be Σ 2 p \Sigma^{p}_{2} -complete. In this work, we introduce a class of relaxed solution concepts for IPGs called locally optimal integer solutions (LOIS) that are simpler to obtain than pure Nash equilibria. We demonstrate that LOIS are not only faster and more readily scalable in large-scale games but also support desirable features such as equilibrium enumeration and selection. We also show that these solutions can model a broader class of problems including Stackelberg, Stackelberg-Nash, and generalized IPGs. Finally, we provide initial comparative results in a cybersecurity game called the Critical Node game, showing the performance gains of LOIS in comparison to the existing Nash equilibrium solution concept. 1. Introduction Integer programs ( Wolsey 2020 ) , in isolation, model a large variety of scenarios including crew scheduling ( Ryan and Foster 1981 ) , production planning ( Pochet and Wolsey 2006 ) , radiation therapy treatment ( Lee et al. 2003 ) , kidney exchange ( Constantino et al. 2013 ) etc. Due to a combinatorial search space, they are difficult to solve, and in fact are known to be NP-hard ( Papadimitriou 1981 ) . An extension of integer programs, where we solve two or more of them together is called an integer programming game (IPG) ( Köppe et al. 2011 ) . IPGs are used to model non-cooperative strategic games with integer strategy space and are particularly useful to model scenarios where there are indivisible resources to be considered or when each player makes a combinatorial decision. They were first introduced by Köppe et al. 2011 and have been since used to model inventory management ( Lamas and Chevalier 2018 ) , facility planning ( Crönert and Minner 2024 ) , transportation games ( Sagratella et al. 2020 ) , attacker-defender-based cybersecurity scenarios ( Dragotto and Scatamacchia 2023 ) , and energy markets ( Crönert and Minner 2021 ) . Although IPGs have recent origins, works utilizing them have grown in past years and we refer interested readers to the excellent tutorial by Carvalho et al. 2023 for a comprehensive list. Very much like general games, the prevalent solution concept for an IPG is a Nash equilibrium. More specifically, IPGs admit both pure and mixed Nash equilibrium with there being theoretical guarantees for the existence of the latter for finite IPGs due to the well-known result by Nash. Since a larger focus in IPG is towards finding, enumerating, and evaluating pure Nash equilibrium due to their straightforward interpretation ( Dragotto and Scatamacchia 2023 ) , we also primarily concern ourselves with pure equilibrium solutions throughout the rest of this work. While IPGs promise substantial modeling capability for scenarios where each player has discrete decisions to make, they are notoriously difficult to solve for. In fact, it has been shown that even deciding if an IPG has a pure Nash equilibrium is \Sigma^{p}_{2} -complete ( Carvalho et al. 2018 ; Carvalho et al. 2022 ) . And, while algorithms exist to compute solutions for IPGs, as the scale of the game increases, these algorithms become intractable due to the inherent difficulty of the problem itself. Indeed, this has been acknowledged by the research community at large and there is a need for approximate solution concepts that are both reasonable and efficient to compute as demonstrated by this remark from Carvalho et al. 2023 . “In contrast, we suggest the more unconventional idea of computing different notions of equilibria, for example, approximate equilibria, when such an approximation is faster to compute. This could provide a significant speedup in the play phase and help adapt the existing algorithms to different solution concepts other than the Nash equilibrium.“ Embracing this need, we propose a class of novel solution concepts for IPGs called Locally Optimal Integer Solutions (LOIS) that are more relaxed than Nash equilibrium concept. We show that LOIS are theoretically simpler to compute than their Nash counterparts (NP-complete instead of \Sigma^{p}_{2} ). We also outline that it is possible to obtain KKT-like conditions for LOIS in the form of what we call implication constraints . For a class of IPGs with quadratic payoffs and linear constraints, these implication constraints can be encoded in the form of integer linear constraints which can be obtained for each player and solved together to get the LOI solution. We also show that these LOIS allow for equilibrium enumeration and selection based on some welfare function , which is often desirable in many economic applications ( Dragotto and Scatamacchia 2023 ) . In summary, our contributions can be listed as follows: (1) We introduce a relaxed solution concept for IPGs called LOIS that is theoretically simpler and more scalable than pure Nash solutions while allowing for equilibrium enumeration and selection based on a welfare function. (2) For a class of IPGs with quadratic payoffs and linear constraints, we show that LOIS can be obtained by solving a system of integer linear constraints. (3) We show that LOIS can be extended to solve Stackelberg, Stackelberg-Nash and generalized IPGs. The rest of the paper is organized as follows. In section 2 , we highlight existing algorithms for solving IPGs and motivate the need for local solutions. Then, in section 3 , we introduce LOIS and show how to obtain and encode the optimality constraints to get LOIS for an IPG. In section 4 , we introduce a cybersecurity game called the critical node game (CNG) . In section 5 , we make an intrinsic comparison between quality of solutions obtained for different orders of LOIS and an extrinsic comparison between existing algorithms from the literature for both simultaneous and sequential versions of the CNG with LOI solutions. Finally, in section 6 , we summarize the work and discuss different avenues for further research. 2. Related Works 2.1. Existing algorithms for IPGs The term IPG itself was first introduced by Köppe et al. 2011 who also outlined an algorithm to solve a specific type of IPG with the payoffs being differences of piecewise linear convex functions. A branching based method to enumerate the solution set of an IPG was outlined by ( Sagratella 2016 ) under convexity assumptions on the payoff. This was later refined by ( Schwarze and Stein 2023 ) where they drop the convexity assumption altogether. Carvalho et al. 2021 introduce a cut-and-play algorithm for separable games whose payoffs are linear with personal strategies but bilinear in terms of opponents. For computing mixed strategies, Carvalho et al. 2022 propose a sample generation method for separable IPGs. Crönert and Minner 2024 improve upon this method and allow for equilibrium enumeration and selection. A recent work by Dragotto and Scatamacchia 2023 introduces a zero-regret algorithm that supports enumeration and selection of pure Nash strategies based on a given welfare function. All of the

Read the complete text