Coverage Games

Computer scientists Orna Kupferman and Noam Shenwald from The Hebrew University of Jerusalem have introduced a new theoretical framework called 'Coverage Games,' detailed in a paper published at the CONCUR 2025 conference and on arXiv. This framework provides a formal model for multi-agent planning in complex, adversarial environments where a system does not have full control over all agents or interacts with an external environment containing multiple agents. The core game is played between two players: a 'coverer,' who operates several agents to achieve a set of objectives, and an adversarial 'disruptor.' The coverer wins if every objective is satisfied by at least one of its agents, otherwise the disruptor prevails.

Coverage Games extend traditional two-player game theory by allowing a dynamic decomposition of objectives among different agents, making it highly applicable to real-world AI and robotics challenges. The researchers conducted a comprehensive theoretical analysis, studying properties like determinacy and the feasibility of pre-decomposing objectives. They also tackled the computational problem of deciding which player has a winning strategy, providing a tight complexity analysis for various special cases, including scenarios with a fixed number of agents or objectives.

The framework has dual applications. It can model systems acting as the 'coverer,' such as in multi-robot surveillance missions or ensuring coverage in multi-threaded software systems. Conversely, it can model systems as the 'disruptor' in scenarios like preventing resource exhaustion attacks or managing network congestion. This mathematical formalism gives engineers and AI researchers a powerful tool to reason about and design robust, coordinated multi-agent systems that must operate reliably despite adversarial interference or incomplete control.