CS Paper Radar

Cooperative Integer Programming Games: Core Stability and Optimal Coalition Structures

Hyunwoo Lee, Robert Hildebrand, I. Esra Buyuktahtakin

cs.GT math.OC ·submitted 2026-09-10 05:48 UTC · v1
benchmark

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Computing Equilibria in Integer Programming Games with Shared Constraints

cs.GT math.OC ·2026-10-03 ·Bainian Hao, Hyunwoo Lee, Robert Hildebrand, Carla Michini
similarity 0.68
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.

0.41

Stability and Perfection in Constrained Weighted Network Games

cs.GT econ.TH ·2026-11-04 ·Julien Fixary, Rémi Castera, Rida Laraki
similarity 0.63
Abstract

We introduce a general framework of constrained weighted network formation in which agents allocate resources across coalitional interactions while facing feasibility constraints. More precisely, we allow arbitrary coalitions of agents to be assigned a continuous weight, and we incorporate both coalitional capacity constraints and individual budget constraints into the model. This framework extends the weighted network formation model of Bich and Morhaim by combining continuous interaction intensities with endogenous feasibility restrictions. Within this setting, we introduce a new notion of stability -- called coalitionwise stability -- extending pairwise stability to constrained network games. Under standard continuity and componentwise quasiconcavity assumptions on payoff functions, we establish the existence of coalitionwise stable networks. We then investigate refinements of stability inspired by the notion of perfect equilibrium introduced by Selten, and by the notion of perfect pairwise stability developed by Bich and Teteryatnikova for network games. The presence of feasibility constraints fundamentally alters the geometry of the feasible set, which no longer possesses a product structure. As a consequence, trembling-hand type refinements become substantially more delicate, since perturbations of some interactions may render other interactions infeasible. Nevertheless, we introduce constrained analogues of both the trembling-hand and perturbative notions of perfect stability considered by Bich and Teteryatnikova, and study their existence and their relationship. In particular, we show the equivalence between these trembling-hand and perturbative formulations under some componentwise monotonicity assumption.

0.21

Cores of $3$-distant convex games

cs.GT econ.TH ·2026-11-05 ·Keisuke Bando, Toshiyuki Hirai, Kenzo Imamura, Ryuhei Mizutani
similarity 0.63
Abstract

Convex cooperative games have a nonempty core and admit an efficient construction of core allocations. However, economically natural local frictions may violate convexity. We study the core of $3$-distant convex games, which permit violations of convexity only between closely related coalitions. Although the core of such a game may be empty, we establish a simple necessary and sufficient condition for its nonemptiness. We also develop a strongly polynomial-time combinatorial algorithm for finding a core allocation whenever one exists. Finally, we demonstrate the applicability of the framework to oligopolistic competition with merger synergies and profit allocation of joint production with complementary inputs.

0.57

Does the grand coalition form? Persistence, arrival, and the role of the sharing rule in a dynamic process of nested binding agreements

cs.GT econ.THmath.OC ·2026-08-18 ·Jobst Heitzig
theory similarity 0.62
Abstract · Revised version, slightly changed definition of profitability, additional implementation results. 70 pages, 4 figures

We study a dynamic coalition-formation process in the tradition of Konishi and Ray (2003): players repeatedly form and dissolve binding agreements, evaluate states by discounted long-term expected payoffs, and hold self-confirming beliefs about the process. States and payoff sharing follow Heitzig and Kornek (2018): a state is a hierarchy of nested agreements, and the members of a new agreement share the surplus it generates, measured against the state without that agreement. All payoff assumptions are structural. We prove that every grand state ever reached is absorbing, and that every absorbing state is grand, for every discount factor. A grand state is actually reached, almost surely, for small discount factors, for three players, and, at every discount factor, whenever distributional stakes are smaller than each player s share of the efficiency gain. Otherwise the process can fail only by cycling for ever among non-grand states. We give exact necessary conditions on such a cycle, decidable for a fixed candidate cycle by linear programming, and exhibit, under an earlier and weaker notion of profitability, a four-player payoff structure whose only closed class is a cycle of two pairs forming and dissolving alternately. Under the present definition, and under either termination rule, no equilibrium traverses a cycle on a fixed schedule: somebody always reaches a state they would rather not leave, and the axioms give them the floor. Whether arrival can fail by cycling at random is open. The axioms are not merely postulated: we exhibit a bargaining game proposal, amendment by substitutes voted on by their own signatories, final unanimity, and an arbitrarily small delay on failure whose equilibria satisfy them as the delay vanishes, and which settles each period in its first round.

0.17

Core nonemptiness for $2/3$-convex games

cs.GT econ.TH ·2026-11-12 ·Keisuke Bando, Toshiyuki Hirai, Kenzo Imamura, Ryuhei Mizutani
similarity 0.62
Abstract

We study the core of $2/3$-convex games, a class of transferable-utility (TU) games that generalizes convex games, which requires at least two of any three distinct coalitions satisfy the supermodular inequality. We show that every $2/3$-convex game admits a marginal worth vector in the core, and hence has a nonempty core. Our proof is constructive and yields a linear-time algorithm for finding such a core allocation. We also show that $2/3$-convexity does not imply permutational convexity in general, while the implication holds under an additional superadditivity condition on pairs of singletons. As an application, we introduce a TU model motivated by the OSCE's consensus-minus-two procedure and show that the resulting game is $2/3$-convex but need not be convex.

0.05

A Cooperative Game Theoretic Model for Sustainable, Smallholder Carbon Farming

cs.GT ·2026-11-07 ·Geetha Charan, Thandava Sunkara, Rohit P Suresh, V. Priyanka, Manojkumar Patil +2 more
dataset similarity 0.62
Abstract

Carbon farming offers a promising path to improve farmer livelihoods, mitigate climate change, and make farming sustainable. However, smallholder farmers, who dominate agriculture in developing economies, face structural barriers to participating in carbon farming due to high certification costs, limited landholdings, and limited budgets available to them. In this paper, we develop a cooperative game-theoretic framework to study how coalition formation can enable viable and profitable participation of smallholder farmers in carbon farming. Our approach explores three components: (i) Solo Portfolio Optimization (SPO), which determines an optimal portfolio of carbon farming practices that individual farmers can adopt under budget constraints; (ii) Joint Portfolio Optimization (JPO), which computes the maximum total economic surplus achievable through the formation of farmer coalitions; and (iii) surplus allocation among participating farmers in a principled way using cooperative game-theoretic solution concepts, such as Shapley value, core, least core, and nucleolus. We show that the underlying cooperative game is superadditive under an affordability condition and non-convex in general. As part of this study, we release CarbonFARM-Bench, a carbon farming dataset constructed by experts, and conduct controlled computational experiments on this dataset. We observe that solo participation in carbon farming is largely infeasible for smallholder farmers under baseline parameters, whereas coalition formation creates substantial value driven by economies of scale. In addition, we demonstrate that stability-aware allocation mechanisms are required for sustaining cooperation. Together, our results highlight that enabling smallholder carbon farming is fundamentally a challenge of institutional design, and we offer several policy recommendations to make it attractive to smallholder farmers.

0.27

Individual Rationality in Constrained Hedonic Games: Friends, Enemies, and Neutrals

cs.GT ·2026-08-14 ·Šimon Schierreich, Ildikó Schlotter
publishedtheory similarity 0.61
Abstract

We study constrained coalition formation in games induced by friends, enemies, and neutrals, under the two standard refinements of additively separable preferences: friend-oriented and enemy-oriented. We ask for partitions that are individually rational (IR), while additionally requiring exactly $k$ non-empty coalitions, each satisfying a prescribed lower and upper bound on its size. Although IR alone is trivial to satisfy for any hedonic game, the size constraints make it computationally intractable to decide whether a feasible partition exists. The two models tell strikingly different stories. Under enemy-oriented preferences, the problem collapses to size-constrained graph coloring, and its complexity follows accordingly. Under friend-oriented preferences, however, the picture is far more intricate, and is governed by the enmity structure rather than the friendships. The complexity is further shaped by two factors: how strict the imposed size requirements are, and whether relationships are symmetric or asymmetric, with several cases turning out tractable in the symmetric setting but intractable once asymmetry is allowed. Charting this boundary in terms of both classical and parameterized complexity, we provide a complete understanding of which properties of the friend/enemy structure are responsible for hardness.

0.23

Social Optimality Does Not Imply Coalitional Stability in Unweighted Max-k-Cut Games

cs.GT math.OC ·2026-10-04 ·Hritiz Gogoi
theory similarity 0.61
Abstract · 16 pages

In Max-$k$-Cut games, optimal colorings maximize social welfare, but are they stable against coordinated deviations that strictly benefit every participating player? A recurring conjecture in the literature asserts that, for unweighted graphs, every optimal coloring has this stability property, known as strong equilibrium. We disprove the conjecture for every $k\ge3$ by exhibiting a finite, simple, connected, unweighted graph with an optimal coloring that is not a strong equilibrium. The profitable coalitional deviation leads to another optimal coloring: every coalition member gains, while players outside the coalition bear the corresponding losses and social welfare remains unchanged. We also give an exact identity relating coalitional gains, changes in cut value, and internal conflicts, recovering the known stability guarantee for optimal colorings when the maximum degree is at most $2k-1$. For strong deviations from general Nash equilibria, we establish a sharp upper bound on the number of monochromatic edges remaining within the coalition and show that this number can exceed the coalition size.

0.09