Big, but not unruly: Tractable norms for anonymous game structures

Autor:	Pedersen, Truls, Dyrkolbotn, Sjur, Kaźmierczak, Piotr
Rok vydání:	2014
Předmět:	Computer Science - Multiagent Systems Computer Science - Logic in Computer Science 68T27 68T42 I.2.11
Druh dokumentu:	Working Paper
Popis:	We present a new strategic logic NCHATL that allows for reasoning about norm compliance on concurrent game structures that satisfy anonymity. We represent such game structures compactly, avoiding models that have exponential size in the number of agents. Then we show that model checking can be done in polynomial time with respect to this compact representation, even for normative systems that are not anonymous. That is, as long as the underlying game structures are anonymous, model checking normative formulas is tractable even if norms can prescribe different sets of forbidden actions to different agents. Comment: Accepted at COIN@PRIMA 2013 workshop and presented on December 3rd, 2013 in Dunedin, New Zealand. http://coin2013-prima.tudelft.nl/
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1405.6899 Zobrazit plný text záznamu View this record from Arxiv