Article

Alternating-time temporal logics with irrevocable strategies

Authors:

Thomas Ågotnes,

Valentin Goranko,

Wojciech JamrogaAuthors Info & Claims

TARK '07: Proceedings of the 11th conference on Theoretical aspects of rationality and knowledge

Pages 15 - 24

https://doi.org/10.1145/1324249.1324256

Published: 25 June 2007 Publication History

Get Access

Abstract

In Alternating-time Temporal Logic (ATL), one can express statements about the strategic ability of an agent (or a coalition of agents) to achieve a goal ϕ such as: "agent i can choose a strategy such that, if i follows this strategy then, no matter what other agents do, ϕ will always be true". However, strategies in ATL are revocable in the sense that in the evaluation of the goal ϕ the agent i is no longer restricted by the strategy she has chosen in order to reach the state where the goal is evaluated. In this paper we consider alternative variants of ATL where strategies, on the contrary, are irrevocable. The difference between revocable and irrevocable strategies shows up when we consider the ability to achieve a goal which, again, involves (nested) strategic ability. Furthermore, unlike in the standard semantics of ATL, memory plays an essential role in the semantics based on irrevocable strategies.

References

[1]

R. Alur, T. A. Henzinger, and O. Kupferman. Alternating-time Temporal Logic. Journal of the ACM, 49:672--713, 2002.

Digital Library

Google Scholar

[2]

E. A. Emerson. Temporal and modal logic. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science, volume B, pages 995--1072. Elsevier Science Publishers, 1990.

Digital Library

Google Scholar

[3]

V. Goranko and W. Jamroga. Comparing semantics of logics for multi-agent systems. Synthese, 139(2):241--280, 2004.

Crossref

Google Scholar

[4]

V. Goranko and G. van Drimmelen. Complete axiomatization and decidability of the Alternating-time Temporal Logic. Theoretical Computer Science, 353:93--117, 2006.

Digital Library

Google Scholar

[5]

M. Pauly. A modal logic for coalitional power in games. Journal of Logic and Computation, 12(1):149--166, 2002.

Crossref

Google Scholar

[6]

P. Y. Schobbens. Alternating-time logic with imperfect recall. Electronic Notes in Theoretical Computer Science, 85(2), 2004.

Google Scholar

[7]

W. van der Hoek, W. Jamroga, and M. Wooldridge. A logic for strategic reasoning. In Proceedings of AAMAS'05, pages 157--164, 2005.

Digital Library

Google Scholar

[8]

W. van der Hoek and M. Pauly. Modal logic for games and information. In Johan van Benthem, Patrick Blackburn, and Frank Wolter, editors, Handbook of Modal Logic, pages 1077--1148. Elsevier, 2006.

Google Scholar

[9]

W. van der Hoek, M. Roberts, and M. Wooldridge. Social laws in alternating time: Effectiveness, feasibility and synthesis. Synthese, 2005.

Google Scholar

Cited By

View all

Niewiadomski ANazarczuk MPrzychodzki MKacprzak MPenczek WZbrzezny ADastani MSichman JAlechina NDignum V(2024)SMT4SMTL: A Tool for SMT-Based Satisfiability Checking of SMTLProceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems10.5555/3635637.3663297(2815-2817)Online publication date: 6-May-2024
https://dl.acm.org/doi/10.5555/3635637.3663297
Galimullin RKuijer LDastani MSichman JAlechina NDignum V(2024)Synthesizing Social Laws with ATL ConditionsProceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems10.5555/3635637.3663130(2270-2272)Online publication date: 6-May-2024
https://dl.acm.org/doi/10.5555/3635637.3663130
Ballot GMalvone VLeneutre JLaarouchi YDastani MSichman JAlechina NDignum V(2024)Strategic Reasoning under Capacity-constrained AgentsProceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems10.5555/3635637.3662859(123-131)Online publication date: 6-May-2024
https://dl.acm.org/doi/10.5555/3635637.3662859
Show More Cited By

Alternating-time temporal logics with irrevocable strategies
1. Theory of computation
  1. Logic

Recommendations

Alternating-time temporal announcement logic
CLIMA'11: Proceedings of the 12th international conference on Computational logic in multi-agent systems

We propose a formalism that we call Alternating-time Temporal Announcement Logic (ATAL). It can be seen as an extension of the Coalition Announcement Logic (CAL) proposed by Ågotnes et al. As well as CAL, ATAL has modal operators enabling to express ...
Robust Alternating-Time Temporal Logic
Logics in Artificial Intelligence
Abstract
In multi-agent system design, a crucial aspect is to ensure robustness, meaning that for a coalition of agents A, small violations of adversarial assumptions only lead to small violations of A’s goals. In this paper we introduce a logical ... $^{}$ $^{}$ $^{}$ $^{}$
Reified Temporal Logics: An Overview

There are three main approaches to the representation of temporal information in AI literature: the so-called method of temporal arguments that simply extends functions and predicates of first-order language to include time as the additional argument; modal ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

TARK '07: Proceedings of the 11th conference on Theoretical aspects of rationality and knowledge

June 2007

296 pages

ISBN:9781450378413

DOI:10.1145/1324249

Program Chair:
Dov Samet

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 25 June 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Acceptance Rates

TARK '07 Paper Acceptance Rate 32 of 100 submissions, 32%;

Overall Acceptance Rate 61 of 177 submissions, 34%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

65
Total Citations
View Citations
196
Total Downloads

Downloads (Last 12 months)11
Downloads (Last 6 weeks)6

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Niewiadomski ANazarczuk MPrzychodzki MKacprzak MPenczek WZbrzezny ADastani MSichman JAlechina NDignum V(2024)SMT4SMTL: A Tool for SMT-Based Satisfiability Checking of SMTLProceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems10.5555/3635637.3663297(2815-2817)Online publication date: 6-May-2024
https://dl.acm.org/doi/10.5555/3635637.3663297
Galimullin RKuijer LDastani MSichman JAlechina NDignum V(2024)Synthesizing Social Laws with ATL ConditionsProceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems10.5555/3635637.3663130(2270-2272)Online publication date: 6-May-2024
https://dl.acm.org/doi/10.5555/3635637.3663130
Ballot GMalvone VLeneutre JLaarouchi YDastani MSichman JAlechina NDignum V(2024)Strategic Reasoning under Capacity-constrained AgentsProceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems10.5555/3635637.3662859(123-131)Online publication date: 6-May-2024
https://dl.acm.org/doi/10.5555/3635637.3662859
Li YWang Y(2024)Knowing How to Plan about Planning: Higher-order and Meta-level Epistemic PlanningArtificial Intelligence10.1016/j.artint.2024.104233(104233)Online publication date: Oct-2024
https://doi.org/10.1016/j.artint.2024.104233
Galimullin RÅgotnes T(2023)Action Models for Coalition LogicDynamic Logic. New Trends and Applications10.1007/978-3-031-26622-5_5(73-89)Online publication date: 14-Feb-2023
https://doi.org/10.1007/978-3-031-26622-5_5
Enqvist SGoranko V(2022)The Temporal Logic of Coalitional Goal Assignments in Concurrent Multiplayer GamesACM Transactions on Computational Logic10.1145/351712823:4(1-58)Online publication date: 20-Oct-2022
https://dl.acm.org/doi/10.1145/3517128
Goranko VJu F(2022)A Logic for Conditional Local Strategic ReasoningJournal of Logic, Language and Information10.1007/s10849-022-09357-y31:2(167-188)Online publication date: 1-Jun-2022
https://dl.acm.org/doi/10.1007/s10849-022-09357-y
Li YWang Y(2021)Knowing How to PlanElectronic Proceedings in Theoretical Computer Science10.4204/EPTCS.335.22335(233-247)Online publication date: 22-Jun-2021
https://doi.org/10.4204/EPTCS.335.22
Galimullin RÅgotnes T(2021)Dynamic Coalition Logic: Granting and Revoking Dictatorial PowersLogic, Rationality, and Interaction10.1007/978-3-030-88708-7_7(88-101)Online publication date: 4-Oct-2021
https://doi.org/10.1007/978-3-030-88708-7_7
Bozzelli LMurano ASorrentino L(2020)Alternating-time temporal logics with linear pastTheoretical Computer Science10.1016/j.tcs.2019.11.028813:C(199-217)Online publication date: 12-Apr-2020
https://dl.acm.org/doi/10.1016/j.tcs.2019.11.028
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Recommendations

Alternating-time temporal announcement logic

Robust Alternating-Time Temporal Logic

Reified Temporal Logics: An Overview