为多智能体系统设计最少约束的规则，避免不良结果。
A Graph-Theoretical Perspective on Law Design for Multiagent Systems
- 用图论方法建模规则约束，最小化限制条件。
- 两类规则均证明为NP难问题，复杂度高。
- 可借超图顶点覆盖近似算法高效求解，适合工程应用。
多智能体系统中的规则是一组对智能体行为的约束，用于避免不良后果。本文研究两类规则：有效规则（若遵循则完全消除不良结果）与无漏洞规则（每次发生不良结果时至少能追责一个智能体）。针对两类规则，研究在最小约束下实现目标的最小化问题。证明在单次并发交互的简单情况下，两类问题均为NP-hard。同时表明，超图顶点覆盖的近似算法可用于高效逼近最小规则，具有实际应用潜力。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。