Multi-Agent Integer Programming Games with Non-Cooperation and Cooperation

Abstract

This dissertation studies integer programming games (IPGs), in which each of several self-interested players solves an integer program whose payoff is coupled to the others' discrete decisions. Because feasible sets are combinatorial and best responses require integer optimization, even deciding whether a pure Nash equilibrium (PNE) exists is computationally intractable in general. The unifying thesis is that the equilibrium of such a game is a computable and leverageable object around which better system-level decisions can be built, and this idea is developed across the non-cooperative, generalized, and cooperative regimes on a common branch-and-cut foundation of globally valid inequalities and best-response oracles. First, to make equilibrium computation scale, round-based random-restart best-response dynamics (RRR-BRD) are introduced with a Las Vegas convergence guarantee and hybridized with the zero-regret cutting-plane method (BZR), lifting tractable PNE computation and sampling from a handful of players to dozens; the methods are instantiated on edge-weighted budgeted maximum coverage games, including a Minnesota aquatic invasive species (AIS) inspection game with up to 84 counties. Second, Nash-informed planning converts computed equilibria into individual-rationality floors and optimizes social welfare above them, improving system outcomes without making any player worse off; the accompanying Price of Individual Rationality is proven to be bounded by the Price of Stability, and the welfare cost of guaranteeing participation is empirically negligible. Third, for generalized IPGs with shared constraints, conditional equilibrium inequalities and a generalized zero-regret algorithm optimize over the equilibrium set, while α-approximate equilibrium certificates and structural (VEST) cuts handle cost-sharing games such as integer splittable bin packing. Fourth, cooperative IPGs define coalition values through pooled integer programs and compute optimal, Core-stable coalition structures via stability inequalities and separation. Computational studies, anchored by the AIS application, demonstrate scalability, interpretability, and concrete policy improvements.