{"ID":2844355,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.06361","arxiv_id":"2511.06361","title":"A Graph-Theoretical Perspective on Law Design for Multiagent Systems","abstract":"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.","short_abstract":"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...","url_abs":"https://arxiv.org/abs/2511.06361","url_pdf":"https://arxiv.org/pdf/2511.06361v2","authors":"[\"Qi Shi\",\"Pavel Naumov\"]","published":"2025-11-09T12:46:29Z","proceeding":"cs.MA","tasks":"[\"cs.MA\",\"cs.AI\",\"cs.GT\"]","methods":"[]","has_code":false}