Epistemic Logic - Common Knowledge & Public Announcements

COMP304 Lectures 2022-11-03

Common knowledge relates to multiple agents knowing the same thing about each-other:

• People drive on the left because we know that other people know to drive on the left.

Definition of Common Knowledge

We can use $E$ to denote that “everybody knows”:

• $E\varphi$ means $K_a\varphi \wedge K_b\varphi \wedge \dots$

Fixed Point Definition

A formula $\varphi$ is common knowledge, denoted by $C\varphi$, if and only if:

• Everybody knows $\varphi$ (so $E\varphi$)
• Everybody knows that $\varphi$ is common knowledge (so $EC\varphi$).

This definition is circular, so can’t be proven.

Transitive Closure Definition

A formula $\varphi$ is common knowledge, denoted by $C\varphi$, if and only if:

• Everybody knows $\varphi$ (so $E\varphi$)
• Everybody knows that everybody knows $\varphi$ (so $EE\varphi$)
• Everybody knows that everybody knows that everybody knows $\varphi$ (so $EEE\varphi$)
• $⋮$

This one is linear to can be determined.

Semantics of “Everybody Knows”

• $M,w\models E\varphi$ if and only if every successor of $w$ satisfies $\varphi$ (regardless of which agent defines the successor)

• Additionally:

  $$M,w\models E\varphi ⟺M,w\models K_a\varphi \wedge K_b\varphi \wedge \dots$$

Semantics of Common Knowledge

• A world $w_2$ is reachable from $w_1$ if $w_2$ is a successor of a successor of $\dots$ a successor of $w_1$.
• $M,w_1\models C\varphi$ if $\varphi$ holds on every world that is reachable from $w_1$.

• $M,w_1⊭C\mathrm{\neg }p$, since $w_3$ and $w_5$ satisfy $p$ and are reachable from $w_1$.
• $M,w_1\models C(p⟹K_{a}p)$, since every reachable world satisfies $p⟹K_{a}p$.
• $M,w_7\models C\mathrm{\neg }p$, since every world reachable from $w_7$ (namely $w_7$ and $w_8$) satisfy $\mathrm{\neg }p$.

Public Announcements

You can never gain common knowledge by using imperfect communication channels.

A public announcement is an event that provides new information to the agents in such a way that:

• All the agents receive the same information.
• The received information is true.

• It is clear to all the agents that everyone receives the information without error.

  Other agents should observe other agents observing.

Notation: $[\varphi ]\psi$ meaning “after $\varphi$ has been publicly announced, $\psi$ is true.”

Semantics of Public Announcements

• The public announcement operator $[\varphi ]$ is a dynamic operator:
  • This means that to determine whether $M,w\models [\varphi ]\psi$ we have to look at a different model $M\ast \varphi$

1. This model $M\ast \varphi$ is obtained by removing all $\mathrm{\neg }\varphi$ worlds from $M$.
2. All arrows to and from removed worlds are simply deleted.

A public announcement has to be true. If $\varphi$ is false we consider $[\varphi ]\psi$ to be trivially true.

We define public announcements like so:

Let $M=(W,\mathbf{R},V)$ be a model and let $w\in W$. Then $M,w\models [\varphi ]\psi$ if and only if either $M,w⊭\varphi$ or $M\ast \varphi ,w\models \varphi$ where:

$$\begin{array}{rl}M\ast \varphi & =(W\ast \varphi ,\mathbf{R}\ast \varphi ,V\ast \varphi )\\ \mathbf{R}\ast \varphi & =\{R_a\ast \varphi ,R_b\ast \varphi ,\dots \}\\ W\ast \varphi & =\{w_1\in W\mid M,w_1\models \varphi \}\\ R_a\varphi & =R_a\cap (W\ast \varphi \times W\ast \varphi )\\ V\ast \varphi (p)& =V(p)\cap W\ast \varphi \end{array}$$

There are many examples of public announcment models starting at slide 12