We provide a logical investigation of a simple case of communication in a network of agents called the gossip problem. Its classical version is: given n agents each of which has a secret – a fact not known to anybody else –, how many calls does it take to achieve shared knowledge of all secrets, i.e., to reach a state where every agent knows every secret? Several protocols achieving shared knowledge in calls exist and were proved to be optimal: no shorter sequence of calls exists. We generalize that problem and focus on higher-order shared knowledge: how many calls does it take to obtain that everybody knows that everybody knows all secrets? More generally, how many calls does it take to obtain shared knowledge of order k? This cannot be achieved simply by communicating facts: the agents also have to communicate higher-order knowledge of facts. We give an algorithm that works in calls. We analyse its properties in a logic that we have investigated in previous work and that is based on the concept of observability of propositional variables by agents: Dynamic Epistemic Logic of Propositional Assignment and Observation DEL-PAO. This enables us in particular to give a formal proof of correctness of the algorithm.
E.A.Akkoyunlu, K.Ekanadham and R.V.Hubert, Some constraints and tradeoffs in the design of network communications, in: Proceedings of the 5th ACM Symposium on Operating Systems Principles, ACM Press, 1975, pp. 67–74.
2.
R.Alur, T.A.Henzinger, F.Y.C.Mang, S.Qadeer, S.K.Rajamani and S.Tasiran, MOCHA: Modularity in model checking, in: Computer Aided Verification, 10th International Conference, CAV ’98, Proceedings, Vancouver, BC, Canada, June 28–July 2, 1998, A.J.Hu and M.Y.Vardi, eds, Lecture Notes in Computer Science, Vol. 1427, Springer, 1998, pp. 521–525. doi:10.1007/BFb0028774.
3.
K.R.Apt, D.Grossi and W.van der Hoek, Epistemic protocols for distributed gossiping, in: Proceedings Fifteenth Conference on Theoretical Aspects of Rationality and Knowledge, TARK 2015, Carnegie Mellon University, Pittsburgh, USA, June 4–6, 2015, R.Ramanujam, ed., EPTCS, Vol. 215, 2015, pp. 51–66.
4.
M.Attamah, H.van Ditmarsch, D.Grossi and W.van der Hoek, A framework for epistemic gossip protocols, in: Multi-Agent Systems – 12th European Conference, EUMAS 2014, Prague, Czech Republic, December 18–19, 2014, Revised Selected Papers, N.Bulling, ed., Lecture Notes in Computer Science, Vol. 8953, Springer, 2014, pp. 193–209.
5.
M.Attamah, H.van Ditmarsch, D.Grossi and W.van der Hoek, Knowledge and gossip, in: Proceedings of 21st ECAI, 2014, pp. 21–26.
6.
M.Attamah, H.van Ditmarsch, D.Grossi and W.van der Hoek, The pleasure of gossip, in: Rohit Parikh on Logic, Language and Society, L.M.C. Baskent and R. Ramanujam, eds, Springer, to appear.
7.
G.Aucher and T.Bolander, Undecidability in epistemic planning, in: IJCAI 2013, Proceedings of the 23rd International Joint Conference on Artificial Intelligence, Beijing, China, August 3–9, 2013, F.Rossi, ed., IJCAI/AAAI, 2013, pp. 27–33.
8.
B.Baker and R.Shostak, Gossips and telephones, Discrete Mathematics2(3) (1972), 191–193. doi:10.1016/0012-365X(72)90001-5.
9.
P.Balbiani, O.Gasquet and F.Schwarzentruber, Agents that look at one another, Logic Journal of the IGPL21(3) (2013), 438–467. doi:10.1093/jigpal/jzs052.
A.Baltag, L.S.Moss and S.Solecki, The logic of public announcements, common knowledge, and private suspicions, in: Proc. TARK’98, Morgan Kaufmann, 1998, pp. 43–56.
12.
T.Bolander, Seeing is believing: Formalising false-belief tasks in dynamic epistemic logic, in: Proceedings of the European Conference on Social Intelligence (ECSI-2014), Barcelona, Spain, November 3–5, 2014, A.Herzig and E.Lorini, eds, CEUR Workshop Proceedings, Vol. 1283, 2014, pp. 87–107, CEUR-WS.org.
13.
T.Bolander and M.B.Andersen, Epistemic planning for single and multi-agent systems, Journal of Applied Non-Classical Logics21(1) (2011), 9–34. doi:10.3166/jancl.21.9-34.
14.
T.Charrier, A.Herzig, E.Lorini and F.Schwarzentruber, Building epistemic logic from observations and public announcements, in: International Conference on Principles of Knowledge Representation and Reasoning (KR), Cape Town, AAAI Press, 2016, pp. 268–277, http://www.aaai.org/Press/press.php.
15.
T.Charrier, B.Maubert and F.Schwarzentruber, On the impact of modal depth in epistemic planning, in: Kambhampati [28], pp. 1030–1036.
16.
T.Charrier and F.Schwarzentruber, Arbitrary public announcement logic with mental programs, in: Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2015, Istanbul, Turkey, May 4–8, 2015, G.Weiss, P.Yolum, R.H.Bordini and E.Elkind, eds, ACM, 2015, pp. 1471–1479.
17.
M.C.Cooper, A.Herzig, F.Maffre, F.Maris and P.Régnier, A simple account of multi-agent epistemic planning, in: Proceedings of the 22nd European Conference on Artificial Intelligence (ECAI 2016), 2016, pp. 193–201.
18.
M.C.Cooper, A.Herzig, F.Maffre, F.Maris and P.Régnier, Simple epistemic planning: Generalised gossiping, in: Proceedings of the 22nd European Conference on Artificial Intelligence (ECAI 2016), 2016, pp. 1563–1564.
19.
R.Fagin, J.Y.Halpern, Y.Moses and M.Y.Vardi, Reasoning About Knowledge, MIT Press, 1995.
20.
O.Gasquet, V.Goranko and F.Schwarzentruber, Big brother logic: Logical modeling and reasoning about agents equipped with surveillance cameras in the plane, in: Proceedings of the 10th International Conference on Autonomous Agents and Multi-Agent Systems, AAMAS ’14, A.L.C.Bazzan, M.N.Huhns, A.Lomuscio and P.Scerri, eds, IFAAMAS/ACM, 2014, pp. 325–332.
21.
J.Gerbrandy, Bisimulations on Planet Kripke, PhD thesis, University of Amsterdam, 1999.
22.
J.Gerbrandy and W.Groeneveld, Reasoning about information change, J. of Logic, Language and Information6(2) (1997). doi:10.1023/A:1008222603071.
23.
S.Ghosh, T.Halder, K.Sharma and R.Verbrugge, Human strategic reasoning in dynamic games: Experiments, logics, cognitive models, in: van der Hoek et al. [34], pp. 116–128.
24.
A.Hajnal, E.C.B.Milner and E.Szemerédi, A cure for the telephone disease, Canadian Mathematical Bulletin15(3) (1972), 447–450. doi:10.4153/CMB-1972-081-0.
25.
A.Herzig, E.Lorini and F.Maffre, A poor man’s epistemic logic based on propositional assignment and higher-order observation, in: International Conference on Logic, Rationality and Interaction (LORI), Taipei, October 28–31, 2015, LNCS, Vol. 9394, Springer Verlag, 2015, pp. 156–168. doi:10.1007/978-3-662-48561-3_13.
26.
A.Herzig, E.Lorini, F.Maffre and F.Schwarzentruber, Epistemic boolean games based on a logic of visibility and control, in: Kambhampati [28], pp. 1116–1122.
27.
C.A.J.Hurkens, Spreading gossip efficiently, Nieuw Archief voor Wiskunde5/1(2) (2000), 208–210.
28.
S.Kambhampati (ed.), Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI 2016, New York, NY, USA, 9–15 July 2016, IJCAI/AAAI Press, 2016.
29.
F.Maffre, Ignorance is bliss: observability-based dynamic epistemic logics and their applications, PhD thesis, Ecole doctorale Math., Info. et Télécom. de Toulouse, 2016.
30.
K.Su, A.Sattar and X.Luo, Model checking temporal logics of knowledge via OBDDs, Comput. J.50(4) (2007), 403–420. doi:10.1093/comjnl/bxm009.
31.
R.Tijdeman, On a telephone problem, Nieuw Archief voor Wiskunde19(3) (1971), 188–192.
32.
H.van Ditmarsch, D.Grossi, A.Herzig, W.van der Hoek and L.B.Kuijer, Parameters for epistemic gossip problems, in: Proc. LOFT 2016, 2016.
33.
J.van Benthem, J.van Eijck, M.Gattinger and K.Su, Symbolic model checking for dynamic epistemic logic, in: van der Hoek et al. [34], pp. 366–378.
34.
W.van der Hoek, W.H.Holliday and W.Wang (eds), Logic, Rationality, and Interaction – 5th International Workshop, LORI 2015, Proceedings, Taipei, Taiwan, October 28–31, 2015, Lecture Notes in Computer Science, Vol. 9394, Springer, 2015.
35.
W.van der Hoek, P.Iliev and M.Wooldridge, A logic of revelation and concealment, in: Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems, W.van der Hoek, L.Padgham, V.Conitzer and M.Winikoff, eds, IFAAMAS, 2012, pp. 1115–1122.
36.
W.van der Hoek, N.Troquard and M.Wooldridge, Knowledge and control, in: Proceedings of the 10th International Conference on Autonomous Agents and Multiagent Systems, L.Sonenberg, P.Stone, K.Tumer and P.Yolum, eds, IFAAMAS, 2011, pp. 719–726.
37.
H.van Ditmarsch, W.van der Hoek and B.Kooi, Dynamic Epistemic Logic, 1st edn, Springer Publishing Company, Incorporated, 2007.
