Synthesising Minimum Cost Dynamic Norms
Synthesising Minimum Cost Dynamic Norms
Natasha Alechina, Brian Logan, Giuseppe Perelli
Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence
Main Track. Pages 3-11.
https://doi.org/10.24963/ijcai.2025/1
A key problem in the design of normative multi-agent systems is the cost of enforcing a norm (for the system operator) or complying with the norm (for the system users). If the cost is too high, ensuring compliant behavior may be uneconomic, or users may be deterred from participating in the MAS. In this paper, we consider the problem of synthesizing minimum cost dynamic norms to satisfy a system-level objective specified in Alternating Time Temporal Logic with Strategy Contexts (ATLsc∗). We show that synthesizing a dynamic norm under a bound on the cost of any prohibited set of actions has the same complexity as synthesizing arbitrary norms. We also show that synthesizing norms that minimize the average cost of the prohibited set of actions is unsolvable; however, synthesizing ε-optimal norms is possible.
Keywords:
Agent-based and Multi-agent Systems: MAS: Formal verification, validation and synthesis
Agent-based and Multi-agent Systems: MAS: Normative systems
