Synthesizing Social Laws with ATL Conditions
Pages 2270 - 2272
Abstract
We introduce a formalism called SLAM (Social Laws on ATL Models) for defining social laws. Such social laws can constrain the behaviour of a multi-agent system. Importantly, these social laws can use any ATL formula as the condition under which an action is allowed. We show that the synthesis problem for these social laws is NP-complete. This generalizes a known result that synthesis of social laws that use only Boolean conditions is NP-complete.
References
[1]
Thomas Ågotnes, Valentin Goranko, and Wojciech Jamroga. 2007 a. Alternating-time temporal logics with irrevocable strategies. In Proceedings of the 11th TARK, Dov Samet (Ed.). 15--24. https://doi.org/10.1145/1324249.1324256
[2]
Thomas Ågotnes, Wiebe van der Hoek, Juan A. Rodríguez-Aguilar, Carles Sierra, and Michael Wooldridge. 2007 b. On the logic of normative systems. In Proceedings of the 20th IJCAI. 1175--1180.
[3]
Thomas Ågotnes, Wiebe van der Hoek, and Michael J. Wooldridge. 2010. Robust normative systems and a logic of norm compliance. Logic Journal of the IGPL, Vol. 18, 1 (2010), 4--30. https://doi.org/10.1093/jigpal/jzp070
[4]
Thomas Ågotnes and Michael J. Wooldridge. 2010. Optimal social laws. In Proceedings of the 9th AAMAS, Wiebe van der Hoek, Gal A. Kaminka, Yves Lespérance, Michael Luck, and Sandip Sen (Eds.). IFAAMAS, 667--674.
[5]
Natasha Alechina, Mehdi Dastani, and Brian Logan. 2013. Reasoning about Normative Update. In Proceedings of the 23rd IJCAI, Francesca Rossi (Ed.). 20--26.
[6]
Natasha Alechina, Mehdi Dastani, and Brian Logan. 2018. Norm Specification and Verification in Multi-agent Systems. Journal of Applied Logics, Vol. 5, 2 (2018), 457--491.
[7]
Rajeev Alur, Thomas A. Henzinger, and Orna Kupferman. 2002. Alternating-time temporal logic. J. ACM, Vol. 49 (2002), 672--713. https://doi.org/10.1145/585265.585270
[8]
Stéphane Demri, Valentin Goranko, and Martin Lange. 2016. Temporal Logics in Computer Science: Finite-State Systems. Cambridge Tracts in Theoretical Computer Science, Vol. 58. CUP. https://doi.org/10.1017/CBO9781139236119
[9]
Robert Paige and Robert E. Tarjan. 1987. Three Partition Refinement Algorithms. SIAM J. Comput., Vol. 16, 6 (1987), 973--989. https://doi.org/10.1137/0216062
[10]
Yoav Shoham and Moshe Tennenholtz. 1995. On social laws for artificial agent societies: off-line design. Artificial Intelligence, Vol. 73, 1 (1995), 231--252. https://doi.org/10.1016/0004--3702(94)00007-N
[11]
Wiebe van der Hoek, Mark Roberts, and Michael Wooldridge. 2007. Social laws in alternating time: effectivenss, feasibility and synthesis. Synthese, Vol. 156 (2007), 1--19.
[12]
Michael Wooldridge and Wiebe van der Hoek. 2005. On obligations and normative ability. Journal of Applied Logic, Vol. 4 (2005), 396--420. io
Index Terms
- Synthesizing Social Laws with ATL Conditions
Recommendations
Optimal social laws
AAMAS '10: Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems: volume 1 - Volume 1Social laws have proved to be a powerful and theoretically elegant framework for coordination in multi-agent systems. Most existing models of social laws assume that a designer is attempting to produce a set of constraints on agent behaviour which will ...
Enforceable social laws
AAMAS '05: Proceedings of the fourth international joint conference on Autonomous agents and multiagent systemsIn this paper we study the enforcement of social laws in artificial social systems using a control system. We define the enforceable social law problem as an extension of Tennenholtz' stable social law problem. We distinguish the choice of social laws ...
Synthesizing Efficient Social Laws based on Algorithmic Mechanism Design
ACAI '23: Proceedings of the 2023 6th International Conference on Algorithms, Computing and Artificial IntelligenceMinimality is usually a desired property of social laws. From the perspective of game theory, minimality closely relates to the concept of maximum social welfare and synthesizing a minimal social law can be modeled as an efficient mechanism design ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
May 2024
2898 pages
ISBN:9798400704864
- General Chairs:
- Mehdi Dastani,
- Jaime Simão Sichman,
- Program Chairs:
- Natasha Alechina,
- Virginia Dignum
Sponsors
Publisher
International Foundation for Autonomous Agents and Multiagent Systems
Richland, SC
Publication History
Published: 06 May 2024
Check for updates
Author Tags
Qualifiers
- Extended-abstract
Conference
AAMAS '24
Sponsor:
AAMAS '24: International Conference on Autonomous Agents and Multiagent Systems
May 6 - 10, 2024
Auckland, New Zealand
Acceptance Rates
Overall Acceptance Rate 1,155 of 5,036 submissions, 23%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 6Total Downloads
- Downloads (Last 12 months)6
- Downloads (Last 6 weeks)2
Reflects downloads up to 14 Jan 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in