Algorithm finds exact or approximate solutions for integer games with shared constraints
Computing Equilibria in Integer Programming Games with Shared Constraints
Computer Science and Game Theory
Summary
In some games, players choose whole-number strategies but must follow shared rules, and whether a player can change their move depends on what others do. The authors created a method that exactly describes all stable outcomes where no player wants to change their choice, even when changes might be allowed in some cases but not others. They embed this method into a process that efficiently searches for the best stable outcome or a close approximation and prove useful mathematical properties to guarantee good solutions. Their tests on thousands of examples show many can be solved exactly, a few have no stable solution, and some need near-exact ones.
What this means in practice
- •For logistics planners: Compute optimal and stable packing plans when multiple agents share limited container space to avoid conflicts and inefficiencies.
- •For network infrastructure teams: Identify stable network designs where users share limited bandwidth or connections, enabling better coordination under capacity limits.
Authors
Bainian Hao, Hyunwoo Lee, Robert Hildebrand, Carla Michini
Abstract
We develop a cutting-plane algorithm for computing pure Nash equilibria in finite integer games with shared constraints, where a deviation may be feasible against one opponent profile and infeasible against another. Conditional equilibrium inequalities capture this dependence through an explicit activation term. We give affine encodings of costs and activation conditions and prove that the resulting inequalities characterize the equilibrium set exactly. Embedded as lazy constraints in branch-and-cut, they yield the Generalized Zero-Regret algorithm for optimizing a linear objective over exact or approximate equilibria; a bisection procedure maintains certified bounds on the smallest achievable approximation factor. We also prove that, when the conditional polytopes have integral vertices, a concave cost is constant on the minimal face containing an equilibrium strategy, so strict concavity forces vertex strategies; for uniform integer-splittable bin packing, a cost-preserving transformation yields vertex equilibria even without strict concavity. We give formulations for bin packing, network formation, and knapsack games with shared capacities and evaluate the algorithm on 3,300 instances, computing a socially optimal equilibrium on all but 43, certifying nonexistence on 16, and certifying approximation factors within a few percent where no exact equilibrium exists.