OATAO - Open Archive Toulouse Archive Ouverte Open Access Week

Temporal Epistemic Gossip Problems

Cooper, Martin and Herzig, Andreas and Maris, Frédéric and Vianey, Julien Temporal Epistemic Gossip Problems. (2019) In: 16th European Conference on Multi-Agent Systems (EUMAS 2018), 6 December 2018 - 7 December 2018 (Bergen, Norway).

(Document in English)

PDF (Author's version) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader

Official URL: https://doi.org/10.1007/978-3-030-14174-5_1


Gossip problems are planning problems where several agents have to share information (`secrets') by means of phone calls between two agents. In epistemic gossip problems the goal can be to achieve higher-order knowledge, i.e., knowledge about other agents' knowledge; to that end, in a call agents communicate not only secrets, but also agents' knowledge of secrets, agents' knowledge about other agents' knowledge about secrets, etc. Temporal epistemic gossip problems moreover impose constraints on the times of calls. These constraints are of two kinds: either they stipulate that a call between two agents must necessarily be made at some time point, or they stipulate that a call can be made within some possible (set of) interval(s). In the non-temporal version, calls between two agents are either always possible or always impossible. We investigate the complexity of the plan existence problem in this general setting. Concerning the upper bound, we prove that it is in NP in the general case, and that it is in P when the problem is non-temporal and the goal is a positive epistemic formula. As for the lower bound, we prove NP-completeness for two fragments: problems with possibly negative goals even in the non-temporal case, and problems with temporal constraints even if the goal is a set of positive atoms.

Item Type:Conference or Workshop Item (Paper)
Additional Information:Thanks to Springer editor. This papers appears in volume 11450 of Lecture Notes in Computer Science ISSN : 0302-9743 ISBN 978-3-030-14173-8 The original PDF is available at: https://link.springer.com/chapter/10.1007/978-3-030-14174-5_1
HAL Id:hal-02378391
Audience (conference):International conference proceedings
Uncontrolled Keywords:
Institution:Université de Toulouse > Institut National Polytechnique de Toulouse - Toulouse INP (FRANCE)
French research institutions > Centre National de la Recherche Scientifique - CNRS (FRANCE)
Université de Toulouse > Université Toulouse III - Paul Sabatier - UT3 (FRANCE)
Université de Toulouse > Université Toulouse - Jean Jaurès - UT2J (FRANCE)
Université de Toulouse > Université Toulouse 1 Capitole - UT1 (FRANCE)
Laboratory name:
Deposited On:20 Nov 2019 10:57

Repository Staff Only: item control page