A Graph-Theoretical Perspective on Law Design for Multiagent Systems
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Event-Triggered Distributed Stabilization of Interconnected Multiagent Systems with Abnormal Agent and Control Layers: Theoretical Analysis
A graph theoretic framework recently has been proposed to stabilize interconnected multiagent systems in a distributed fashion, while systematically capturing the architectural aspect of cyber-physical systems with separ…
Duality and Stability in Complex Multiagent State-Dependent Network Dynamics
Despite significant progress on stability analysis of conventional multiagent networked systems with weakly coupled state-network dynamics, most of the existing results have shortcomings in addressing multiagent systems …
Learning in Multiagent Systems: An Introduction from a Game-Theoretic Perspective
We introduce the topic of learning in multiagent systems. We first provide a quick introduction to the field of game theory, focusing on the equilibrium concepts of iterated dominance, and Nash equilibrium. We show some …
Robust consensus control of second-order uncertain multiagent systems with velocity and input constraints (extended version)
In this paper, we investigate the consensus problem of second-order multiagent systems under directed graphs. Simple yet robust consensus algorithms that advance existing achievements in accounting for velocity and input…
Game-Theoretical Perspectives on Active Equilibria: A Preferred Solution Concept over Nash Equilibria
Multiagent learning settings are inherently more difficult than single-agent learning because each agent interacts with other simultaneously learning agents in a shared environment. An effective approach in multiagent re…