Suppose that we have a formula A which is valid in all states of Kripke structure and some transition relations. Is it generally possible to derive if formula A is common knowledge between particular agents directly from the structure?

  • $\begingroup$ Welcome to CS.SE! Can you expand the question to define what "common knowledge between particular agents" means? Can that be formalized or defined precisely? $\endgroup$ – D.W. Jun 5 '17 at 22:49
  • $\begingroup$ Hi! I think this description in wikipedia is explanatory: There is common knowledge of p in a group of agents G when all the agents in G know p, they all know that they know p, they all know that they all know that they know p, and so on ad infinitum. More precisely, Kip means Agent i knows formula p, Ep means All agents know p and common knowledge Cp is E applied on E applied on E ........ applied on Ep, where E is applied infinite times. I only know how to see Kip for agent i in Kripke structure. $\endgroup$ – DevM Jun 5 '17 at 23:56
  • $\begingroup$ I doubt that this is what you really wanted to ask because all universally valid formulas are common knowledge. That's called the logical omniscience problem. $\endgroup$ – Kai Jun 7 '17 at 22:29
  • $\begingroup$ @D.W. the standard reference would be Knowledge and Common Knowledge in a Distributed Environment, JY Halpern & Y Moses, jacm 37(3), 1990 $\endgroup$ – Kai Jun 7 '17 at 22:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.