Computing Equilibria in Integer Programming Games with Shared Constraints
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.
Related
- Integer linear programming based methods for computing the maximum chordal subgraph of an arbitrary graph
- Computing Approximate Solutions of Inconsistent Max-Min Fuzzy Relational Equations by Mixed-Integer Programming
- Computing Multi-Slot First-Price Pacing Equilibria at Scale via Entropic Smoothing
- Hidden Convexity via Symmetric Displacement Covers: Mixed-Integer Quadratic Programming and Integer Cubic Programming in Fixed Dimension
- Computing Stationary Equilibria in Measure-Dependent Markov Systems
BibTeX
@misc{hao2026computing,
title = {{Computing Equilibria in Integer Programming Games with Shared Constraints}},
author = {Bainian Hao and Hyunwoo Lee and Robert Hildebrand and Carla Michini},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.04279},
eprint = {2610.04279},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.04279},
}
RIS
TY - UNPB
TI - Computing Equilibria in Integer Programming Games with Shared Constraints
AU - Bainian Hao
AU - Hyunwoo Lee
AU - Robert Hildebrand
AU - Carla Michini
PY - 2026
DA - 2026/10/03
PB - arXiv
DO - 10.48550/arxiv.2610.04279
UR - https://arxiv.org/abs/2610.04279
AB - 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.
ER -