CS Paper Radar

Scaling Chance-Constrained Correlated Equilibrium Computation for Exclusive Resource-Assignment Games

Jaehan Im, Ufuk Topcu, David Fridovich-Keil

cs.GT ·submitted 2026-09-11 22:10 UTC · v1

Abstract

The chance-constrained correlated equilibrium concept provides a robust coordination technique for self-interested agents whose costs are uncertain to a central coordinator, but the number of joint actions considered in its computation grows exponentially with the number of agents. We propose an exact-one resource-assignment restriction for games in which agents compete for shared resources and simultaneous use of a resource is undesirable or unsafe. The restriction allows each resource to be assigned to exactly one agent, reducing the number of joint actions considered from O(2^(nr)) to O(n^r) for n agents and r resources. The resulting problem is solved over the restricted joint action set while retaining all incentive constraints associated with unilateral deviations. We show that the feasible set of the restricted problem is exactly the convex hull of the chance-constrained pure Nash equilibria contained in the exact-one assignment set, yielding a necessary and sufficient condition for nonemptiness. We further derive a sufficient condition under which all chance-constrained pure Nash equilibria of the unrestricted game are retained by the restriction. Numerical experiments in a vertiport departure-corridor coordination scenario demonstrate a 99.81% reduction in median computation time relative to the unrestricted formulation while achieving equivalent coordination performance.

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

Exact Hill Shares Are Simultaneous Guarantees

cs.GT ·2026-09-18 ·Bo Li, Hanyu Li, Chenghua Liu
benchmarktheory similarity 0.64
Abstract

Fair division of indivisible bads seeks allocations that guarantee every agent a bundle whose cost is no larger than a meaningful fairness benchmark. The canonical minimax share has widely been used; unfortunately, it is not a simultaneous guarantee. Hill (Ann. Probab., 1987) initiated a complementary approach in which the share depends only on the number of agents and the largest possible single-item value. Li et al. (ACM Trans. Econ. Comput., 2024) gave the exact Hill formula and proved that its monotone closure is a simultaneous guarantee. The closure treats the largest-item cost only as an upper bound and can be strictly larger than the share conditioned on the \emph{actual} largest item. They asked whether this smaller exact share is itself simultaneously guaranteed for three or more agents. We resolve this open question affirmatively. For any number of agents and arbitrary heterogeneous largest-item costs, there is one allocation that satisfies every agent's exact Hill's share. We further provide a polynomial-time algorithm computes such an allocation. Our algorithm combines an ordered moving knife with a tail-domination invariant, and a one-sided trimmed subset-sum routine for the two-agent endpoint without computing an exact minimax partition.

0.16

Matching Tasks to Agents: Mechanism Design for Multi-Agent Contracts

cs.GT ·2026-10-22 ·Matteo Bollini, Matteo Castiglioni, Alberto Marchesi
benchmark similarity 0.64
Abstract

We study task assignment under adverse selection and moral hazard. In the single-task setting, agents privately know their types, which determine their success probabilities and effort costs. Based on the agents' reported types, the principal selects an agent to perform the task and offers a success-contingent payment. Although optimal Bayesian contract design is generally computationally intractable and Myerson's characterization does not directly extend to settings with hidden actions and multidimensional private information, we show that the single-task problem admits a simple Myerson-style characterization. Our key insight is that incentive constraints depend only on the ratio between effort cost and success probability. We characterize an optimal mechanism and show that it can be computed in polynomial time. We also establish a tight $Θ(1/(NK))$ worst-case bound on the ratio between the optimal profit and the full-information benchmark, where $N$ is the number of agents and $K$ is the number of types per agent. We then extend our analysis to multiple tasks, showing that an optimal mechanism may not exist. Nevertheless, for a constant number of agents, we provide a polynomial-time approximation scheme for the supremum profit.

0.31

Exact Regret Frontiers and Externality Scheduling in Centralized Serial-Dictatorship Bandits

cs.GT cs.LGstat.ML ·2026-09-17 ·Lishang Xu, Guodong Ma, Pengcheng Weng, Zixuan Xia
similarity 0.63
Abstract · v3: exposition clarified; a sentence in Section 5.3 that was inaccurate for K > N removed, and the K = N condition stated in the introductio…

Exploration in centralized serial-dictatorship matching bandits must use complete matchings, so learning one player-arm pair can impose regret on others. We study this externality under a known common priority order and Gaussian rewards with unit variance. We show that the matching-level Graves-Lai constraints reduce to finitely many pairwise exploration quotas and, at top-choice-separated instances, yield a polynomial-size marginal linear program. At these instances, the exact attainable set of expected logarithmic regret coefficients is $G(θ)\mathcal{X}(θ)$, where $\mathcal{X}$ is the feasible matching-allocation set and $G$ maps allocations to player regret. The usual upper-closed Graves-Lai region can be strictly larger despite having the same Pareto-minimal boundary. We further show that identical exploration quotas can induce very different regret through their scheduling. Finally, we construct estimate-solve-track policies, uniformly good on the full row-strict class, that attain every fixed positively weighted optimum without assuming optimizer uniqueness. Every Pareto-minimal point is pointwise attainable, possibly through an instance-calibrated target.

0.19

Equilibria of Round-Robin: Computational Hardness and Fairness for Few Subadditive Agents

cs.GT cs.CCcs.DS ·2026-09-16 ·Paul W. Goldberg, Alexandros Hollender, Giannis Tyrovolas
theory similarity 0.63
Abstract

The round-robin procedure is a simple and well-studied fair division mechanism where agents pick goods in turns. Motivated by draft mechanisms in sports leagues, we investigate strategic behaviour in online round-robin for subadditive agents. This gives rise to an extensive-form game, and we study the computational problem of computing a subgame perfect Nash equilibrium (SPNE). We show that for just two submodular agents, computing an SPNE is $\mathsf{PSPACE}$-hard. Even for the class of $\mathit{OXS}$ utilities, which are a special case of submodular utilities, computing an SPNE remains $\mathsf{NP}$-hard for a small number of agents. We complement our computational results with normative results. We show that for just three additive agents, there exist instances where every equilibrium violates EF1. This separates the online and the direct revelation games. On the positive side, we show that for additive agents every equilibrium allocation is proportional up to one good (PROP1) and for two additive agents it is also EF1. Finally, by showing that round-robin is bossy at equilibrium, we prove that the number of equilibrium allocations can be exponential even if agents have lexicographic preferences.

0.19

Learning to Harvest Without Collapse in a Regenerative Commons: A Lagrangian Framework

cs.AI cs.GT ·2026-09-29 ·Jose Tupayachi, Xueping Li, Soham Das
theory similarity 0.63
Abstract

The tragedy of the commons poses a multi-agent safety problem: reward-seeking agents can deplete a shared resource, and cooperation among its users does not itself specify how much must be preserved. We make preservation an explicit requirement by formulating a regenerative commons as a constrained Markov game or a constrained multi-agent MDP with a designer-specified depletion budget. We develop a nonstationary Lagrangian framework that constructs a policy sequence from solutions of unconstrained games or cooperative control problems. Extending earlier time-average constructions, we introduce average-epoch solution concepts for reset episodes with discounted rewards and terminal costs. We prove a reward-independent feasibility certificate, cooperative feasibility and approximate optimality against feasible policy mixtures, and an extension to unbiased sampled costs. For self-interested agents, a constrained Nash certificate quantifies the price-dispersion term introduced by deviations that redistribute budget across epochs. Under the stated assumptions on solver accuracy and multiplier updates, these results give constrained policy-sequence guarantees using solutions of unconstrained problems. Experiments with constrained IPPO and MAPPO in a Gordon-Schaefer fishery examine how depletion budgets shape stock retention, harvest rewards, and price adaptation.

0.18

Incentive Mechanisms for Welfare Maximization Under Individual Rationality in Noncooperative Dynamical Systems

eess.SY ·2026-10-22 ·Yuyue Yan, Maojiao Ye, Hideaki Ishii, Tomohisa Hayakawa
similarity 0.62
Abstract · 16 pages, 10 figures

Human societies are shaped by strategic interactions among self-interested decision-makers, where conflicts between individual and social interests naturally arise. This paper investigates the design of incentive mechanism for multi-agent game systems to reconcile social welfare maximization with individual benefits under economic constraints. We develop a linear-quadratic incentive framework to reshape Nash equilibria while reconciling the constraints of Pareto efficiency, individual rationality, and budget balance. The optimal target state is identified as the solution of a constrained optimization problem associated with the social welfare and aggregated payoff functions. Our theoretical analysis characterizes the conditions of incentive functions that steer self-interested agents towards the optimal target state as a Pareto-efficient Nash equilibrium for achieving the maximum attainable social welfare. We further characterize how the choice of social welfare function constrains achievable individual outcomes, revealing a structural paradox associated with priority weighting under individual rationality. Several numerical examples are presented to demonstrate the efficacy of our results.

0.17