Groups Versus Coalitions: On the Relative Expressivity of GAL and CAL

French, Tim; Galimullin, Rustam; Van Ditmarsch, Hans; Alechina, Natasha

Abstract

Group Announcement Logic (GAL) and Coalition Announcement Logic (CAL) were proposed to study effects of public announcements by groups of agents on knowledge in multiagent systems. Both logics have operators that quantify over such announcements. In GAL, it is possible to express that 'a group of agents G has a (truthful) announcement such that after this announcement, some property A holds'; for example, A may involve some agents in G gaining additional knowledge, while agents outside G remain ignorant. In CAL, the meaning of the coalition announcement operator is subtly different: it says that 'G has an announcement such that, whatever else the agents outside G announce simultaneously, some property A is guaranteed to hold after the joint announcement'. It has been open for some time whether GAL and CAL are equally expressive. We show that this is not the case: there is a property expressible in GAL that is not expressible in CAL. It is still an open question whether CAL is subsumed by GAL, or whether the two logics have incomparable expressive power.

Citation

French, T., Galimullin, R., Van Ditmarsch, H., & Alechina, N. (2019, June). Groups Versus Coalitions: On the Relative Expressivity of GAL and CAL. Presented at 18th International Conference on Autonomous Agent and MultiAgent Systems, AAMAS '19, Montreal, QC, Canada

• Presentation Conference Type: Edited Proceedings
• Conference Name: 18th International Conference on Autonomous Agent and MultiAgent Systems, AAMAS '19
• Start Date: Jun 13, 2019
• End Date: Jun 17, 2019
• Acceptance Date: Jan 23, 2019
• Publication Date: May 13, 2019
• Deposit Date: Jun 14, 2019
• Publisher: Association for Computing Machinery (ACM)
• Peer Reviewed: Peer Reviewed
• Pages: 953-961
• Book Title: AAMAS: '19 Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems
• ISBN: 978-1-4503-6309-9
• Public URL: https://nottingham-repository.worktribe.com/output/2189470
• Publisher URL: https://dl.acm.org/citation.cfm?id=3331790