CS Paper Radar

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

Jobst Heitzig

cs.GT econ.THmath.OC ·submitted 2026-08-18 13:30 UTC · v2
theory

Abstract

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.

Comment
Revised version, slightly changed definition of profitability, additional implementation results. 70 pages, 4 figures

Closest papers

Nearest neighbours by meaning across the whole index.

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

Cooperative Integer Programming Games: Core Stability and Optimal Coalition Structures

cs.GT math.OC ·2026-09-10 ·Hyunwoo Lee, Robert Hildebrand, I. Esra Buyuktahtakin
benchmark similarity 0.62
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.

0.28

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.62
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

Forming Alliances in the Fog of War: A General Lotto Perspective

cs.GT ·2026-09-30 ·Edik Hakobyan, Vade Shah, Jason R. Marden
similarity 0.61
Abstract

Agents competing against a common opponent can often gain an edge by forming alliances, but deciding whether to do so is difficult when they lack precise knowledge about their opponent or ally. We study how uncertainty affects opportunities for alliance formation in the coalitional General Lotto game, in which two players compete aganist a shared adversary by allocating their resource budgets over separate sets of valued contests. When all agents know one another's budgets, it is known that a budget transfer from one player to the other can benefit both players. We ask whether such alliances survive when the players know the relevant budgets only up to a multiplicative factor. Under two models, one in which the players are uncertain about the adversary's budget and one in which they are uncertain about each other's budgets, we characterize exactly which games admit a transfer that benefits both players in every game consistent with what they conjecture to be possible. In both models, we show that such robust transfers exist in a set of games of positive measure for every level of uncertainty. These results suggest that alliances can remain worthwhile even when allies are largely in the dark.

0.13

Refundable Deposits: How to Restore Cooperation in Finitely Repeated Games

cs.GT econ.TH ·2026-08-27 ·Giulio Salizzoni, Domenico Mergoni Cecchelli, Edward Plumb, Maryam Kamgarpour, Galit Ashkenazi-Golan
similarity 0.61
Abstract

While infinitely repeated games admit a rich set of Nash equilibria, finitely repeated games typically have a much smaller and often inefficient one. We show how to enlarge this set using deposits: in each period a player may place a refundable sum with a neutral intermediary, returned when the game ends and forfeited following a deviation. Paying these deposits is voluntary and incentive compatible at every stage, so no commitment by the players is assumed, the only commitment required being that of the intermediary to a refund rule fixed before play begins. The mechanism sustains payoff profiles more efficient than those of the standard equilibria, without altering the underlying game and without transfers between players. We demonstrate it on the prisoner's dilemma, a congestion game, and a public goods game, all settings where cooperation cannot emerge in the standard finitely repeated version. We also apply it to a dynamic common-pool resource, suggesting that the construction extends beyond repeated stage-games.

0.18

Dynamic Coalition Formation Under Capacity Constraints: A Regime-Switching Value-Investing Game

cs.GT cs.DC ·2026-11-02 ·Rosario Patanè
publishedbenchmark similarity 0.61
Abstract

Edge computing service deployment requires the Network Operator (NO) and Service Providers (SPs) to coordinate investment and resource allocation under uncertain demand. This paper develops an audit-based service management framework for daily coalition formation with fixed capacity and service-level agreement (SLA) reservations. A two-stage coalitional game separates infrastructure investment from operational participation. Demand follows a Geometric Random Walk (GRW), and SPs apply an ordered admission and suspension rule using reported marginal contributions. With the NO held fixed, the operational coalition value is submodular; mandatory reservations can produce negative Shapley payoffs. We derive a separable benchmark, compute operational Shapley allocations, and give a sufficient condition for convergence to an individual equilibrium. A probabilistic audit mechanism provides a conditional daily truthfulness guarantee under verified settlement and enforceable penalties. For five service classes over three years, the reference run gains 12.4% over static grand-coalition membership and recovers 94.6% of the full-information optimum. Across 30 runs, the median gain is 13.3%. Sensitivity tests examine policy parameters, capacity and alternative demand models. The gain depends on capacity and update order; abundant capacity can make the admission rule underperform static membership.

0.34

Policy Iteration Is Not Strongly Polynomial for Deterministic Markov Decision Processes: The Price of Algorithmic Anarchy

cs.LG cs.DSmath.OC ·2026-09-30 ·Han Zhong, Yinyu Ye
highly cited similarity 0.60
Abstract · Added results on average-reward MDPs and extended the discounted lower bounds to constant-bit integer rewards

We establish exponential iteration lower bounds in the number of states for Howard's policy iteration on deterministic discounted and average-reward Markov decision processes (MDPs), with a constant number of actions per state. This rules out strong polynomiality of Howard's policy iteration in both settings. We further prove that a Dantzig counterpart of Howard's policy iteration runs in strongly polynomial time on deterministic average-reward MDPs. Together with the known strongly polynomial bound for Dantzig's rule on deterministic discounted MDPs, these results establish an exponential separation between the two algorithms in both settings. This separation between Howard's decentralized and simultaneous selfish improvements and Dantzig's coordinated selection of a single action with the largest improvement across all states reveals a ``price'' of algorithmic anarchy.

0.42

Stability and Perfection in Constrained Weighted Network Games

cs.GT econ.TH ·2026-11-04 ·Julien Fixary, Rémi Castera, Rida Laraki
similarity 0.60
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