A logic of strategic ability under bounded memory


Authors
Abstract
We study the logic of strategic ability of coalitions of agents with bounded memory by introducing Alternating-time Temporal Logic with Bounded Memory (ATLBM), a variant of Alternating-time Temporal Logic (ATL). ATLBM accounts for two main consequences of the assumption that agents have bounded memory. First, an agent can only remember a strategy that specifies actions in a bounded number of different circumstances. While the ATL-formula means that coalition C has a joint strategy which will make φ true forever, the ATLBM-formula means that C has a joint strategy which for each agent in C specifies what to do in no more than n different circumstances and which will make φ true forever. Second, an agent has bounded recall—a strategy can only take the last m states of the system into account. We use the logic to study the interaction between strategic ability, bounded number of decisions, bounded recall and incomplete information. We discuss the logical properties and expressiveness of ATLBM, and its relationship to ATL. We show that ATLBM can express properties of strategic ability under bounded memory which cannot be expressed in ATL.
Keywords Alternatingtime temporal logic  Multi-agent systems  Resource-bounded reasoning  Strategic ability
Categories (categorize this paper)
Reprint years 2009
DOI 10.1007/s10849-008-9075-4
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 48,902
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

Preface.Michael Wooldridge & Wiebe van der Hoek - 2003 - Studia Logica 75 (1):3-5.

Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles

Analytics

Added to PP index
2009-01-28

Total views
60 ( #151,179 of 2,309,716 )

Recent downloads (6 months)
4 ( #266,053 of 2,309,716 )

How can I increase my downloads?

Downloads

My notes

Sign in to use this feature