# A Graph-Theoretical Perspective on Law Design for Multiagent Systems

arXiv: https://arxiv.org/abs/2511.06361 · HTML: https://mlsanity.com/paper/2511.06361/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 53 references that are in the map.
- First posted on arXiv 9 Nov 2025.

## Builds on (most cited first, 4 of 4)

- [What Do We Want From Explainable Artificial Intelligence (XAI)? -- A Stakeholder Perspective on XAI and a Conceptual Model Guiding Interdisciplinary XAI Research](https://mlsanity.com/paper/2102.07817/) (2021)
- [A Game-Theoretic Account of Responsibility Allocation](https://mlsanity.com/paper/2105.09129/) (2021)
- [Blameworthiness in Strategic Games](https://mlsanity.com/paper/1809.05485/) (2018)
- [An Axiomatic Approach to Formalized Responsibility Ascription](https://mlsanity.com/paper/2111.06711/) (2021)

## Built on by (most cited first, 1 of 1)

- [Peer Oversight in Collective Decision Making](https://mlsanity.com/paper/2608.28754/) (2026)

## Abstract (arXiv)

A law in a multiagent system is a set of constraints imposed on agents' behaviours to avoid undesirable outcomes. The paper considers two types of laws: useful laws that, if followed, completely eliminate the undesirable outcomes and gap-free laws that guarantee that at least one agent can be held responsible each time an undesirable outcome occurs. In both cases, we study the problem of finding a law that achieves the desired result by imposing the minimum restrictions. We prove that, for both types of laws, the minimisation problem is NP-hard even in the simple case of one-shot concurrent interactions. We also show that the approximation algorithm for the vertex cover problem in hypergraphs could be used to efficiently approximate the minimum laws in both cases.