CS Paper Radar

Achieving Robust Performance using Minimal Communication in Resource Allocation Games

Brandon Collins, Colton Hill, Philip N. Brown

cs.GT ·submitted 2026-09-22 16:30 UTC · v1

Abstract

Increasingly, resource allocation games are being proposed to model team coordination in denied communication environments. Of particular interest is understanding the impact of communication denial on the quality of emergent team coordination. In this work, we consider the situation with an arbitrary communication network and use the Price of Anarchy to quantify the quality of emergent behavior. Our main result is a computationally efficient algorithm that calculates a minimal communication network that has the same performance guarantee as the full information case. Additionally, we provide efficient algorithms that compute a Nash and a strict Nash equilibrium in the full information setting. Finally to support these algorithms, we provide sufficient conditions for the existence of a strict Nash equilibrium, characterize strict Nash equilibria across all communication networks, and show that each strict Nash equilibrium in the full information case has a necessary and sufficient set of communication links that induce it. We conclude by giving an execution time experiment of the proposed algorithm and examine several example games.

Closest papers

Nearest neighbours by meaning across the whole index.

Deriving the Pure Price of Anarchy for Networked Resource Allocation Games

cs.GT cs.MAeess.SYmath.OC ·2026-09-10 ·Vartika Singh, Philip N. Brown
theory similarity 0.71
Abstract

This work considers multi-agent coordination with arbitrary information networks among the agents using a game-theoretic approach. A system designer aims to assign local utility functions to the agents to guide their actions toward a desired system objective. The performance of the assigned local utilities is measured by the well known pure price of anarchy (pPoA) metric that equals the ratio of the system objective at the worst pure Nash equilibrium of the corresponding game to the optimal system objective. Our aim is to derive the utility functions which optimize the pPoA-based performance guarantees for any given information network and system objective. We develop a linear program that derives the optimal pPoA for any arbitrary information network and arbitrary system objective. Our work is the first to solve optimal utility design for arbitrary networks; our techniques generalize previous approaches which considered only the full-information setting. For supermodular objective functions, we prove that counterintuitively, a fully communication-denied utility design is optimal irrespective of the original information network. For submodular system objectives, an exhaustive numerical analysis suggests that the optimal utility design is robust to communication failures even for this case. When the system objective is weighted maximum coverage, the marginal contribution utility design provably optimizes the pPoA for a wide variety of information networks of interest.

0.34

Do LLMs Beat Nash? Testing Decentralized Coordination in Self-Play Multi-Agent Games

cs.MA cs.RO ·2026-08-12 ·Deborah Sinishaw, Qile Zhu, Edwin Meriaux, Gregory Dudek
benchmark similarity 0.64
Abstract · 5 pages, 5 figures. Submitted to the 2026 IEEE MIT Undergraduate Research Technology Conference (URTC)

Large language model agents deployed without a central controller are often assumed to require communication to coordinate their actions. We ask what remains possible without it: when independent instances of the same model cannot communicate, can they still reason about their counterparts well enough to exceed the standard game-theoretic baseline for uncoordinated play? We introduce a benchmark of one-shot, no-communication games in which each of thirteen language models is told only that its counterparts are running the same model and is evaluated against the Nash equilibrium of the underlying game. In two-player matrix games spanning seven archetypes and two to ten actions per player, two frontier-hosted models consistently exceed their Nash benchmark, approaching the optimal joint outcome in several archetypes, while most open-weight models achieve only partial gains that vary sharply by game structure. Performance degrades substantially in team-based games with four or more interchangeable agents, particularly as the action space grows, suggesting that whatever capability drives self-play gains in dyadic games does not transfer to larger multi-agent teams.

0.43

A Resource Allocation Tournament

cs.GT math.OCecon.TH ·2026-10-22 ·Adam Nathaniel, Refael Hassin
similarity 0.63
Abstract

We introduce and analyze a round-robin simultaneous resource allocation contest, motivated by sports leagues and other competitive environments where agents must distribute limited resources across multiple encounters. Players allocate resources in advance to matches against all opponents, and match outcomes are determined by relative allocations. We study two payoff schemes: total points, where players accumulate rewards for each win, and winner-takes-all, where only the tournament winner is rewarded. For three players, we provide complete equilibrium characterizations under both schemes. For four or more players, we show that the total points payoff admits Blotto-type equilibria, while the winner-takes-all payoff requires numerical and algorithmic analysis. To address this, we develop a best-response dynamics algorithm with stochastic inertia and use it to approximate equilibria in games with four and five players.

0.26

Randomization to Balance Performance under Nominal and Compromised Communication

cs.GT ·2026-10-22 ·Colton Hill, Brandon Collins, Philip N. Brown
similarity 0.62
Abstract

It is well-known that under nominal communication, where agents are able to share information with one another, game-theoretic methods provide system-level performance guarantees in multiagent cyber-physical human systems such as distributed resource allocation. However, approaches that depend on communication are frequently not robust when communication is compromised. While randomized decision-making can prevent arbitrarily poor outcomes under compromised communication, these performance guarantees often do not improve when communication abilities are restored. Thus, it remains unclear whether a single approach can perform well under nominal communication and remain robust under compromised communication. In this paper, we study whether a system operator can inform agents about how much they should randomize their choice when selecting actions in order to balance performance across both settings. We show that for any scenario (e.g., a multiagent resource allocation instance), there exists a level of randomization where nominal efficiency is near-optimal while compromised efficiency is strictly positive. We then show that this guarantee weakens as agents must choose between increasingly many resources. These results provide an initial step toward understanding randomization as a tool for robust performance across communication settings.

0.17

Games Over Observation Spaces in Multi-Agent Capture the Flag

cs.GT ·2026-09-05 ·Mae Frost, Michael Amir, Shaunak D. Bopardikar
published similarity 0.62
Abstract · 21 pages, 5 figures, To be published as a conference paper in the 17th International Conference on Game Theory and AI for Security (GameSec …

We consider a multi-agent Capture the Flag (CtF) scenario in a graph-based environment, where a team of attackers seeks to reach designated flag vertices while a defending team attempts to intercept them. In our setting, both teams operate using decentralized heuristic policies. While the attacking team may choose its heuristic from a diverse library of policies, the defense is restricted to playing a single fixed policy. To overcome this limitation, a centralized defense oracle strategically restricts the portion of the graph visible to each of its agents in order to elicit a wider range of emergent behaviors from its fixed policy. We formalize this interaction as a two-player zero-sum game, where the attacker reasons over its library of heuristics and the defense reasons over the combinatorial space of visibility profiles. To solve this intractably large game, we propose a Double Oracle algorithm to find approximate empirical equilibria, and we empirically validate that observation manipulation can improve the defense's performance.

0.34

The Complexity of Multiplayer Colonel Blotto Games with Player-Specific Values

cs.GT cs.CCecon.TH ·2026-09-24 ·Martin Bichler, Abheek Ghosh
similarity 0.61
Abstract · 64 pages, 3 figures

We study equilibrium computation in discrete multiplayer Colonel Blotto games with player-specific battlefield values. In the two-player model with common battlefield values, equilibria can be computed in polynomial time. We show that this tractability breaks down in the multiplayer model with player-specific values under the standard uniform tie-breaking rule. In particular, computing a $(c/n)$-approximate Nash equilibrium is PPAD-hard for some constant $c>0$, even when every player has three resources, where $n$ is the number of players. The main technical step is PPAD-hardness for computing a constant-approximate well-supported Nash equilibrium. In contrast, under uniform tie-breaking, a pure Nash equilibrium can be computed in polynomial time when every player has one resource. We also prove PPAD membership for computing $\varepsilon$-approximate Nash equilibria for inverse-exponentially small $\varepsilon$. Finally, for non-uniform monotone tie-breaking, we show PPAD-hardness even when every player has one resource and all players have identical battlefield values.

0.25

Learning-Augmented Coordination Mechanisms

cs.GT ·2026-10-27 ·George Christodoulou, Vasilis Christoforidis, Alkmini Sgouritsa, Ioannis Vlachos
top venue similarity 0.61
Abstract · This paper has been accepted to the 40th Conference on Neural Information Processing Systems (NeurIPS 2026). Abstract abridged due to arXiv …

The inefficiency of decentralized resource allocation is classically measured by the Price of Anarchy (PoA) and the Price of Stability (PoS). The most widely studied and foundational class of these models are atomic and non-atomic congestion games, for which a robust theory quantifying the inefficiency of equilibria is well-established. To mitigate the effects of selfish behavior, we employ Coordination Mechanisms, which modify resource costs to incentivize socially improved equilibria. However, standard Coordination Mechanisms assume unknown, adversarial demand, restricting positive results mainly to specialized networks such as parallel links. We address this limitation by studying learning-augmented coordination mechanisms, where the mechanism is endowed with a potentially inaccurate prediction of the demand. We study general atomic and non-atomic congestion games with polynomial latency functions of degree $d$. Our main positive result is a learning-augmented coordination mechanism tuned by a confidence parameter $β$ which achieves a "best of both worlds" type of result: approximately optimal performance for an accurate prediction without sacrificing the worst-case guarantee of a good equilibrium (PoS). We further establish bounds on PoA-Robustness (worst equilibrium performance under cost modification). Our construction relies on transforming approximate equilibria of the original game into exact equilibria of the modified game using an approximate potential function. We complement our positive results with impossibility results. We first show that requiring all equilibria to have optimal social cost under an accurate prediction precludes bounded robustness. We also show a strong error tolerance limit in non-atomic games: even infinitesimal prediction errors can cause the performance of a mechanism with optimal consistency to revert to the original PoA.

0.30

Contention Resolution Against an Adversarial Scheduler

cs.DS ·2026-11-06 ·Michael A. Bender, Martín Farach-Colton, Andrew Krapivin, Pritom Kundu, John Kuszmaul +3 more
theory similarity 0.61
Abstract · 15 pages

In the classical contention-resolution problem, a set of players share a broadcast channel, and a player succeeds in a given time step if it is the only player to broadcast during that step. Implicit in the classical problem is the assumption that every player is free to act on every step: once a player arrives, it participates until it succeeds. We study what happens when that assumption is removed. In our model, an adversarial \emph{scheduler} decides, on each step, which subset of the players gets scheduled to participate in the step. An unscheduled player simply sleeps through the step. We measure a protocol by its \emph{efficiency}: the number of players divided by the expected number of steps in which at least one player was active. Our first result says that, so long as the players are given access to a global clock and to shared randomness, they can achieve efficiency $Ω(1/\log n)$. The players are able to achieve this bound without requiring any channel feedback, and even if the adversarial scheduler is adaptive. We also give a matching lower bound of $O(1 / \log n)$, which holds even with channel feedback, and even for an oblivious scheduler. Our upper bounds all require the players to have access to a shared global clock and to shared randomness. Our final result says that this type of implicit shared state is necessary. If the players have neither a global clock nor shared randomness, then no protocol can achieve efficiency better than $O(\log n / n)$; and this holds even if the other aspects of the problem are designed to be as favorable for the players as possible (the channel gives ternary feedback and the adversary is oblivious).

0.26