💻 computer science

Coverage Games

This paper introduces "coverage games," a novel multi-agent planning framework where a coverer operating multiple agents competes against a disruptor to satisfy a set of objectives, providing a comprehensive theoretical analysis of their determinacy, objective decomposition, and computational complexity.

Original authors: Orna Kupferman (The Hebrew University, School of Computer Science and Engineering, Jerusalem, Israel), Noam Shenwald (The Hebrew University, School of Computer Science and Engineering, Jerusalem, Isra

Published 2026-03-24

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Orna Kupferman (The Hebrew University, School of Computer Science and Engineering, Jerusalem, Israel), Noam Shenwald (The Hebrew University, School of Computer Science and Engineering, Jerusalem, Israel)

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: A Game of "Covering All Bases"

Imagine you are the manager of a team of security guards (the Coverer) trying to protect a museum. Your goal is to make sure every single exhibit (the Objectives) is watched over infinitely often. However, you don't have total control. There is a mischievous saboteur (the Disruptor) who can move the guards around, block hallways, or create distractions.

In a standard security game, you usually have just one guard trying to watch one thing, or maybe one guard trying to watch everything at once.

Coverage Games are different. Here, you have multiple guards (agents), but you don't know in advance which guard should watch which exhibit. You have a list of 10 exhibits to watch, but only 3 guards.

The Challenge: You need to figure out a plan where, no matter how the saboteur tries to mess things up, every single exhibit gets watched by at least one of your guards.
The Twist: You don't have to assign Guard A to Exhibit 1 and Guard B to Exhibit 2 forever. The assignment can change dynamically. Maybe Guard A watches Exhibit 1 for a while, then switches to Exhibit 2, while Guard B takes over Exhibit 1. As long as someone is watching everything at all times, you win.

The Two Main Questions

The paper asks two big questions about this game:

The Coverage Problem: Can the Manager (Coverer) come up with a strategy to win? (i.e., Can we guarantee that every exhibit is watched, no matter what the saboteur does?)
The Disruption Problem: Can the Saboteur (Disruptor) come up with a strategy to win? (i.e., Can the saboteur force a situation where at least one exhibit is left unwatched, no matter how the Manager moves the guards?)

Key Discoveries (The "Aha!" Moments)

1. The Game Isn't Always "Fair" (Undetermined)

In many classic games (like Chess), one side is guaranteed to have a winning strategy. If you play perfectly, you will win.

In Coverage Games: This isn't always true. Sometimes, the Manager cannot guarantee a win, but the Saboteur also cannot guarantee a win. It's a "stalemate" where the outcome depends on the specific moves made in real-time, not just a pre-planned strategy.
Analogy: Imagine a game of tag in a foggy forest. The tagger (Saboteur) can't guarantee catching the runner (Manager) because the runner might dodge perfectly. But the runner can't guarantee escaping forever because the tagger might get lucky. Neither has a "perfect" plan that works 100% of the time.

2. The "Splitting" Problem

The hardest part for the Manager is deciding how to split the work.

The Metaphor: Imagine you have 10 chores (Objectives) and 2 kids (Agents). You can't just say "Kid 1 does chores 1-5 and Kid 2 does 6-10" because the Saboteur might make Kid 1 get stuck doing only chore 1.
The Insight: The paper shows that you often can't decide the split before the game starts. The Manager must be flexible. If the Saboteur pushes the guards toward a specific hallway, the Manager must instantly re-assign who watches what. The paper calls these decision points "Forks." A winning strategy involves reaching a Fork and then dynamically splitting the tasks based on where the Saboteur sends the guards.

3. Complexity: How Hard is it to Solve?

The authors calculated how difficult it is for a computer to solve these games.

General Case: It is very hard (PSPACE-complete). It's like solving a massive maze where you have to think many steps ahead, and the number of possibilities explodes.
Fixed Number of Guards: If you only have a small, fixed number of guards (e.g., always 2 guards), the problem becomes easier (NP-complete), but still tricky.
Fixed Number of Tasks: If you only have a small, fixed number of exhibits to watch, the problem becomes very easy (Polynomial Time). The computer can solve it quickly.

The Surprise:
Usually, in computer science, "Co-Büchi" objectives (which mean "avoid these bad things forever") are easier to handle than "Büchi" objectives (which mean "visit these good things forever").

In this paper: For the Disruptor (the Saboteur), Co-Büchi games are actually harder to solve than Büchi games when the number of guards is fixed. It's like the Saboteur finds it harder to block a "visit" goal than an "avoid" goal when there are only a few guards.

Real-World Applications

Why does this matter? The paper suggests this framework helps in:

Robot Swarms: Imagine a fleet of drones patrolling a city. You want to ensure every neighborhood is checked. The "Saboteur" could be bad weather, traffic, or a hacker. The system needs to know if the drones can cover the whole city despite the chaos.
Cybersecurity: You have several firewalls (agents) trying to block different types of hacker attacks (objectives). The hacker (Disruptor) tries to find a way to slip through. Can your system guarantee that every type of attack is blocked by at least one firewall?
Traffic Management: You want to ensure that at least one route out of a city is never jammed. The "agents" are the traffic lights, and the "Disruptor" is the flow of cars. Can the traffic lights coordinate to keep a path open?

Summary in a Nutshell

Coverage Games are a new way to think about teamwork in chaotic environments. Instead of assigning one person to one job, it asks: "Can a team of flexible workers cover all the necessary tasks, even if a troublemaker tries to confuse them?"

The paper proves that while this is a powerful way to model real-world problems, it is mathematically complex. The key to winning isn't a rigid plan, but a flexible strategy that knows how to split the team's efforts at the right moment (the "Forks") to ensure nothing gets left behind.

1. Problem Definition

The paper introduces Coverage Games (CGs), a novel framework for multi-agent planning in adversarial environments where a system (the Coverer) operates multiple agents ( $k$ ) but lacks full control over their behavior or interacts with an environment containing multiple agents.

The Players:
- Coverer: Operates $k$ agents. The goal is to ensure that a set of objectives $\beta = \{\alpha_1, \dots, \alpha_m\}$ is covered. An objective is covered if it is satisfied by at least one of the $k$ agents' plays.
- Disruptor: An adversarial player who interacts with all $k$ agents simultaneously using a single strategy. The goal is to prevent the Coverer from covering all objectives (i.e., ensure at least one objective remains unsatisfied in all $k$ plays).
The Game Structure:
- Played on a game graph $G = \langle V_1, V_2, v_0, E \rangle$ .
- $k$ tokens start at $v_0$ . Each agent controls one token.
- The outcome is a tuple of $k$ plays (paths).
- Winning Condition: Coverer wins if $\bigcup_{i=1}^k \text{sat}(\rho_i, \beta) = \beta$ , where $\text{sat}(\rho, \beta)$ is the set of objectives satisfied by play $\rho$ .
Key Distinction: Unlike standard multi-objective games (where one agent must satisfy all objectives) or standard multi-agent planning (where agents are fully controlled), CGs involve partial control (adversarial environment) and decomposition (objectives can be split among agents dynamically).
Determinacy: A crucial theoretical finding is that CGs are not necessarily determined. It is possible that neither the Coverer has a winning covering strategy nor the Disruptor has a winning disrupting strategy.

2. Methodology and Theoretical Framework

The authors analyze the problem using game theory, automata theory, and computational complexity.

Objective Types: The study focuses on Büchi (visit a set infinitely often) and co-Büchi (visit a set finitely often) objectives.
Decomposability: A central concept is whether the set of objectives $\beta$ can be a-priori decomposed among the $k$ agents. The authors prove that in general, Coverer cannot commit to a static partition of objectives; the decomposition must be dynamic, depending on the Disruptor's moves.
Forks and $V_{avoid}$ :
- A fork is a vertex where Coverer can split agents to different successors to cover different subsets of objectives.
- The authors define $V_{avoid}$ as the set of vertices from which Disruptor can force the game to stay without reaching any fork.
- Theorem 3.5 establishes a recursive characterization: Coverer wins from $v$ if $v \notin V_{avoid}$ (can reach a fork) OR if $v \in V_{avoid}$ and Coverer can win a single-agent game on the subgraph $G_{avoid}$ .
Symbolic Strategies: For the Disruption problem (especially with co-Büchi objectives), the authors utilize fairness requirements and superset objectives to describe disrupting strategies symbolically, avoiding the need to guess explicit infinite strategies.

3. Key Contributions and Results

A. Theoretical Properties

Undeterminacy: CGs are not determined. There exist games where neither player has a winning strategy. This holds even for small instances ( $k=2$ agents, $|\beta|=3$ objectives).
Non-Decomposability: Coverer generally cannot partition objectives statically. A winning strategy often requires reacting to the Disruptor's moves to decide how to split objectives among agents.
Special Cases:
- If $k=1$ , the problem reduces to standard multi-objective two-player games.
- If $k \ge |\beta|$ , the problem decomposes into $|\beta|$ independent single-objective games (Coverer wins iff they win each individually).

B. Complexity Analysis

The paper provides a comprehensive analysis of the Coverage and Disruption problems. The complexity depends on the objective type (Büchi vs. co-Büchi) and whether parameters ( $k$ or $|\beta|$ ) are fixed.

Table 1 Summary of Complexity (Joint Complexity):

Problem	Büchi Objectives	co-Büchi Objectives
Coverage	PSPACE-complete	PSPACE-complete
Disruption	$\Sigma_2^P$ -complete	$\Sigma_2^P$ -complete

Coverage Problem: Solvable in PSPACE. Hardness is proven via reduction from QBF (Quantified Boolean Formulas).
Disruption Problem: Solvable in $\Sigma_2^P$ $Σ_{2}^{P}$ (NP with a co-NP oracle). This is strictly easier than Coverage. Hardness is proven via reduction from 2QBF.
- Note: For Büchi, Disruptor has a memoryless disrupting strategy. For co-Büchi, strategies may require memory, but can be described symbolically.

C. Parameterized Complexity

The authors analyze the complexity when the game graph $G$ is large, but $k$ (agents) or $|\beta|$ (objectives) are fixed.

Fixed Parameter	Coverage (Büchi/co-Büchi)	Disruption (Büchi)	Disruption (co-Büchi)
Fixed $k$	NP-complete	NP-complete	$\Sigma_2^P$ -complete
Fixed $\|\beta\|$	PTIME	PTIME	PTIME

Significance of Fixed $k$ :
- For Coverage, fixing $k$ reduces complexity from PSPACE to NP.
- For Disruption (Büchi), fixing $k$ reduces complexity from $\Sigma_2^P$ to NP.
- For Disruption (co-Büchi), fixing $k$ does not reduce complexity; it remains $\Sigma_2^P$ -complete even for $k=2$ . This highlights a fundamental asymmetry: co-Büchi objectives are harder to disrupt with a fixed number of agents due to the difficulty of finding maximal sets of objectives an agent can satisfy.
Significance of Fixed $|\beta|$ : Fixing the number of objectives makes both problems PTIME-complete for all cases, as the number of possible partitions becomes constant.

4. Significance and Applications

Multi-Robot Surveillance: Ensuring that critical locations are visited infinitely often by at least one robot in a team, even if the environment (Disruptor) can block paths or create obstacles.
Cyber-Security: Ensuring that every set of potential attack vectors is mitigated by at least one defense mechanism, countering an adversarial hacker.
Multi-threaded Systems: Ensuring that critical resources are accessed infinitely often by at least one process, regardless of the scheduler's (Disruptor) behavior.
Traffic Management: Ensuring at least one route remains uncongested despite the actions of multiple vehicles.

5. Conclusion

The paper establishes Coverage Games as a rigorous framework for reasoning about multi-agent systems with shared goals and adversarial environments. The primary contribution is the identification of the decomposition challenge: the need to dynamically split objectives among agents. The authors provide tight complexity bounds, showing that while the general problem is PSPACE-complete, it becomes tractable (PTIME) if the number of objectives is fixed, and NP-complete if the number of agents is fixed (for Büchi). The distinction between Büchi and co-Büchi objectives in the disruption problem (specifically the persistence of $\Sigma_2^P$ hardness for co-Büchi with fixed agents) is a novel and significant theoretical insight.