Synthesising Minimum Cost Dynamic Norms

Alechina, Natasha; Logan, Brian; Perelli, Giuseppe

doi:10.24963/ijcai.2025/1

Synthesising Minimum Cost Dynamic Norms

Natasha Alechina, Brian Logan, Giuseppe Perelli

Download BibTeX Cite

Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence. Main Track. Pages 3-11.

https://doi.org/10.24963/ijcai.2025/1

Keywords

Agent-based and Multi-agent Systems: MAS: Formal verification, validation and synthesis
Agent-based and Multi-agent Systems: MAS: Normative systems

Abstract

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.

Natasha Alechina, Brian Logan, and Giuseppe Perelli. 2025. Synthesising Minimum Cost Dynamic Norms. In Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-25. IJCAI, 3–11. https://doi.org/10.24963/ijcai.2025/1

@inproceedings{ijcai2025p1,
  title     = {Synthesising Minimum Cost Dynamic Norms},
  author    = {Alechina, Natasha and Logan, Brian and Perelli, Giuseppe},
  booktitle = {Proceedings of the Thirty-Fourth International Joint Conference on
               Artificial Intelligence, {IJCAI-25}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {James Kwok},
  pages     = {3--11},
  year      = {2025},
  month     = {8},
  note      = {Main Track},
  doi       = {10.24963/ijcai.2025/1},
  url       = {https://doi.org/10.24963/ijcai.2025/1},
}

TY  - CPAPER
TI  - Synthesising Minimum Cost Dynamic Norms
AU  - Alechina, Natasha
AU  - Logan, Brian
AU  - Perelli, Giuseppe
T2  - Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-25
PB  - International Joint Conferences on Artificial Intelligence Organization
PY  - 2025
SP  - 3
EP  - 11
DO  - 10.24963/ijcai.2025/1
UR  - https://doi.org/10.24963/ijcai.2025/1
ER  -