Towards a Theory for the Design of Rules in Multi-Agent Systems: the case of Homogeneous Fleets
cs.MA
Submitted: 2026-11-01
Updated: 2026-11-01
Comments: 30 pages; A first version of the RDP
License: http://creativecommons.org/licenses/by-nc-sa/4.0/
The gist: The regulation of systems composed of many interacting decentralised agents is a long-standing problem.
Terminology
Abstract
The regulation of systems composed of many interacting decentralised agents is a long-standing problem. This problem has typically been resolved by the imposition of rules. Rules resolve the limitations of sub-optimal agents whilst simultaneously aligning the behaviour of the agents with the demands of society. Traffic laws, for example, let a driver cross a junction without seeing around the corner, and transport protocols such as TCP let applications share a network without knowing of one another. The problem is more pressing today, as autonomous systems are deployed in society. In this work, we establish the basis of a system-agnostic theory of rule design for multi-agent systems. We first state the rule design problem (RDP) in its generality. It relates a rule to the set of system performances, defined by the regulator, that the agents deployed under it can attain. However, it is not yet possible to solve the RDP in full generality. As such, we introduce the homogeneous rule design problem (HRDP), in which the agents in each environment are identical, and among other interesting properties, show that under worst-case aggregation the two problems have the same solution, bypassing the combinatorial complexity of the RDP. To solve the RDP under worst-case aggregation we propose Rule Branch and Bound (RuleBnB), an anytime branch-and-bound algorithm. Finally, we illustrate the value of solving the RDP on an autonomous driving case study.
Sources
- Minimum-violation LTL Planning with Conflicting Specifications
- Liability, Ethics, and Culture-Aware Behavior Specification using Rulebooks
- Receding Horizon Planning with Rule Hierarchies for Autonomous Vehicles
- On a Formal Model of Safe and Scalable Self-driving Cars
- Lexicographic Descent: A Gradient-Based Approach to Optimize Totally Ordered Rulebooks via Parametric Scalarization
- Compatibility and future-proof testing for multi-agent systems
Related papers
- MultiAgentBench: Evaluating the Collaboration and Competition of LLM agents
- Iterative Negotiation and Oversight: A Case Study in Decentralized Air Traffic Management
- Towards using Large Language Models for Risk Negotiation and Consensus-building in One Health contexts
- A-MapReduce: Executing Wide Search via Agentic MapReduce
- AgentCue: Statistical Summaries for Guiding Decentralized Multi-Agent Self-Organization
- Events as Triggers for Behavioral Diversity in Multi-Agent Reinforcement Learning