Coverage Games

Orna Kupferman ORCID:0000-0003-4699-6117, Noam Shenwald ORCID:0000-0003-1994-6835 · 2026

Read Coverage Games by Orna Kupferman ORCID:0000-0003-4699-6117, Noam Shenwald ORCID:0000-0003-1994-6835 (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-20398.txt.

Introduction

Kupferman and Shenwald introduce coverage games, a new framework for multi-agent planning. A coverer runs several agents toward a set of objectives. A disruptor acts against them inside the same setting. The coverer wins when each objective is met by at least one agent. The setup extends classic two-player games by letting objectives split among agents. Uses include multi-robot surveillance and guarding shared resources from exhaustion. The authors study determinacy and the cost of deciding who wins.

Catalog record

CREATOROrna Kupferman ORCID:0000-0003-4699-6117, Noam Shenwald ORCID:0000-0003-1994-6835
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE134280
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.20398

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Coverage Games Thanks: Research supported by European Research Council, Advanced Grant ADVANSYNT Orna Kupferman ORCID:0000-0003-4699-6117, Noam Shenwald ORCID:0000-0003-1994-6835 Abstract . We introduce and study coverage games – a novel framework for multi-agent planning in settings in which a system operates several agents but do not have full control on them, or interacts with an environment that consists of several agents. The game is played between a coverer, who has a set of objectives, and a disruptor. The coverer operates several agents that interact with the adversarial disruptor. The coverer wins if every objective is satisfied by at least one agent. Otherwise, the disruptor wins. Coverage games thus extend traditional two-player games with multiple objectives by allowing a (possibly dynamic) decomposition of the objectives among the different agents. They have many applications, both in settings where the system is the coverer (e.g., multi-robot surveillance, coverage in multi-threaded systems) and settings where it is the disruptor (e.g., prevention of resource exhaustion, ensuring non-congestion). We first study the theoretical properties of coverage games, including determinacy, and the ability to a priori decompose the objectives among the agents. We then study the problems of deciding whether the coverer or the disruptor wins. Besides a comprehensive analysis of the tight complexity of the problems, we consider interesting special cases, such as the one-player cases and settings with a fixed number of agents or objectives. \titlecomment \lsuper *A preliminary version appeared in the proceedings of CONCUR 2025, the 36th International Conference on Concurrency Theory. Introduction Synthesis is the automated construction of a system from its specification [ 34 ] . A reactive system interacts with its environment and has to satisfy its specification in all environments [ 21 ] . A useful way to approach synthesis of reactive systems is to consider the situation as a two-player game between the system and the environment [ 3 ] . The game is played on a graph whose vertices are partitioned between the players. Starting from an initial vertex, the players jointly move a token and generate a play , namely a path in the graph, with each player deciding the successor vertex when the token reaches a vertex she owns. The system wins if it has a strategy to ensure that no matter how the environment moves the token, the generated play satisfies an objective induced by the specification. For example, in Büchi games, the objective is given by a set \alpha of vertices, and a play satisfies the objective if it visits \alpha infinitely often. Synthesis is closely related to automated planning in AI [ 37 ] . Indeed, in both settings, the goal is to realize a sequence of actions in order to accomplish a desired task, often under uncertainty or adversarial conditions. For example, in pursuit-evasion [ 25 ] , a robot aims to complete a task while avoiding collisions with an adversarial robot. This setting naturally corresponds to a game between the robot and its environment, and extensive work from the synthesis community has been lifted to planning, for both finite- and infinite-horizon tasks [ 26 , 18 , 16 , 35 , 15 , 24 , 29 , 5 , 32 , 14 , 20 ] . The game setting enables the modeling of uncertainty or adversarial environments, dealing with unknown terrains, partial observability, or limited sensing capabilities. Both synthesis and planning often involve multiple objectives . For example, in synthesis, generalized objectives such as generalized Büchi [ 7 ] , generalized parity [ 8 ] , generalized reachability [ 17 ] , and generalized reactivity (GR(1)) [ 33 , 7 ] specify conjunctions of underlying objectives that the system must satisfy. Research on multi-objective games studies the impact of this conjunction on memory requirements, algorithmic complexity, and strategy construction. Such objectives have also been studied in a variety of game models, including concurrent, stochastic, energy, and weighted games [ 4 , 9 , 6 , 41 , 28 ] . In planning, multiple objectives also naturally arise, especially in multi-agent systems [ 37 ] . The agents typically represent robots, drones, or autonomous vehicles that perform tasks such as terrain exploration or handling of requests at various locations [ 11 , 37 , 10 , 36 , 38 ] . For example, in adversarial patrolling [ 30 ] , a team of robots must detect intrusions into a guarded area, and in the offline-coverage problem [ 1 ] , robots must visit every point in a work area — typically within minimal time [ 9 , 37 , 10 ] . In the context of planning from temporal specifications, researchers have studied settings in which several robots or components act cooperatively toward a shared objective [ 32 , 20 , 16 ] . For example, in [ 32 ] , decentralized synthesis methods are used to coordinate a robot swarm so as to satisfy a global LTL specification, assuming full control and a static environment. Similarly, [ 20 ] considers multi-robot synthesis from Signal Temporal Logic specifications using event-triggered control. Each robot is assigned its own task, and thus there is no strategic cooperation among the robots. We introduce and study coverage games – a framework for reasoning about planning tasks in which the system does not have full control over the agents. Formally, a coverage game is a two-player game with a set \beta=\{\alpha_{1},\ldots,\alpha_{m}\} of objectives, in which one player – the covering player (named Coverer ) operates a number k of agents that together aim to cover all the objectives in \beta . In the beginning of the game, k tokens are placed on the initial vertex. Each agent is responsible for one token, and as in standard two-player games, the interaction of each agent with the second player – the disrupting player (named Disruptor ) generates a play in the graph. The outcome of the game is then a set of k plays — one for each agent. The goal of Coverer is for these plays to cover all the objectives in \beta . That is, for all 1\leq l\leq m , there is an agent 1\leq i\leq k such that \alpha_{l} is satisfied in the play generated by the interaction of Agent i with Disruptor . A covering strategy for Coverer is a vector of strategies, one for each agent, that ensures that no matter how Disruptor behaves, each objective is satisfied in at least one play in the outcome. In the coverage problem , we are given a game graph G , a set \beta of objectives, and a number k\geq 1 of agents, and we have to decide whether Coverer has a covering strategy. Note that when k=1 , a coverage game coincides with a standard two-player game with multiple objectives. Also, it is not hard to see that when k\geq m , namely there are more agents than objectives, then a dominant strategy (in the game-theoretic sense) for Coverer allocates each objective in \beta to a different agent. The interesting cases are when 1<k<m , in which case the objectives in \beta need to be partitioned, possibly dynamically, among the agents. Coverage games significantly extend the settings addressed in current studies of planning. Indeed,

Read the complete text