Cooperative integer programming games improve coalition stability and optimization
Cooperative Integer Programming Games: Core Stability and Optimal Coalition Structures
Computer Science and Game Theory
Summary
This paper looks at how groups of agents can work together to accomplish tasks that can’t be split up easily. The authors create models where agents pool resources and use integer programming—a math method for decision-making where solutions are whole numbers—to find the best ways to form teams and share rewards. They develop new mathematical tools and algorithms that ensure these teams remain stable, meaning no subgroup would want to break away. Their approach was tested on examples similar to knapsack problems and showed good results even with many agents.
What this means in practice
- •For transportation planners: Coordinate multiple agents to optimize shared resource constraints for indivisible project tasks ensuring stable cooperation.
- •For supply chain managers: Design collaboration schemes where companies pool budgets to complete joint shipments or orders efficiently with stable profit sharing.
Authors
Hyunwoo Lee, Robert Hildebrand, I. Esra Buyuktahtakin
Abstract
We introduce cooperative integer programming games (CIPGs), in which agents pool budget constraints to accomplish indivisible tasks jointly and the characteristic function maps every coalition to the optimal value of a pooled integer program. Our goal is to identify an optimal coalition structure (OCS) and a stable one (OSCS). We derive a stability inequality that keeps each formed coalition in the Core with respect to itself, and present two mixed-integer OCS formulations, aggregated and disaggregated, proving that the disaggregated formulation is integer-equivalent yet yields a tighter LP relaxation. Building on the stability inequality we develop lifted stability cuts, several separation strategies inside a cutting-plane algorithm, an SCS-feasible primal heuristic that constructs warm starts with guaranteed stability, and a payoff-refinement step computing the Shapley value and the nucleolus of every formed coalition. On benchmark cooperative knapsack games, the method certifies optimality with up to 16 players and reaches MIP gaps below 1% at 30 players while evaluating 766 of the roughly $10^9$ coalition values.