7
$\begingroup$

In Epistemic Logic, the Fixed-Point Axiom says that $\varphi$ is common knowledge among the group $G$ if and only if all the members of $G$ know that $\varphi$ is true and is common knowledge: $$\vDash C_G\varphi \Leftrightarrow E_G(\varphi \land C_G\varphi)$$ Thus, the Fixed-Point Axiom says that $C_G\varphi$ can be viewed as a fixed point of the function $f(x) = E_G (\varphi\land x)$, which maps a formula $x$ to the formula $E_G (\varphi\land x)$.


Here, $G$ is a group of agents, $C_G\varphi$ means that "group $G$ has common knowledge of $\varphi$" and $E_G\varphi$ means that "everyone in the group $G$ knows $\varphi$". For those who are not familiar with these technical differences, $E_G\varphi$ is straightforward, but $C_G\varphi$ means $E_G^k\varphi$ for every $k\in\mathbb N$. In other words, if a group $G$ has common knowledge of $\varphi$, then everyone knows $\varphi$, everyone knows that everyone knows $\varphi$, everyone knows that everyone knows that everyone knows $\varphi$ and so on ad infinitum. Common knowledge is a much stronger condition!

Why should the Fixed-Point Axiom hold? I am unable to understand the intuition behind it. Could someone explain this perhaps with the help of an example?

$\endgroup$
4
  • 1
    $\begingroup$ For those who don't know the notation, please explain it. Like what are $C_G$ and $E_G$ for one. $\endgroup$
    – coffeemath
    Apr 13, 2021 at 10:27
  • $\begingroup$ @coffeemath I did explain that towards the end. Let me know if you've other specific questions. $\endgroup$ Apr 13, 2021 at 10:30
  • $\begingroup$ epsilon: In a common sense way, saying that a group of agents has common knowledge of $\varphi$ is the same as saying that everyone in the group of agents knows $\varphi$. Is there some philosophical way these differ? $\endgroup$
    – coffeemath
    Apr 13, 2021 at 11:55
  • 3
    $\begingroup$ @coffeemath The two are not the same. If a group $G$ has common knowledge of $\varphi$, then everyone knows $\varphi$, everyone knows that everyone knows $\varphi$, everyone knows that everyone knows that everyone knows $\varphi$ and so on ad infinitum. Common knowledge is a much stronger condition, you see. $\endgroup$ Apr 13, 2021 at 12:02

3 Answers 3

6
$\begingroup$

The fixed-point treatment of common knowledge is not very intuitive. However, I will try to provide some explanation why it captures the properties of operators $C_G \varphi$.

First, recall that intuitively $C_G \varphi := \bigwedge_{n \in \mathbb{N}} E_G^n \varphi$, where $E_G^0 \varphi:= \varphi$ and $E_G^{n+1}:= E_G E_G^n \varphi$. This is your definition of the fact that $\varphi$ is common knowledge if everyone knows $\varphi$, everyone knows that everyone knows $\varphi$, and so on. We cannot have this formula in the language as the conjunction is infinite.

Second, since common knowledge is a type of knowledge, it is veridical, i.e. if $\varphi$ is common knowledge, then $\varphi$ is true.

Now, let's have a look at the axiom: $C_G \varphi \leftrightarrow E_G (\varphi \land C_G \varphi)$. The first conjunct on the right corresponds to common knowledge being veridical. In particular, $E_G \varphi$ implies $\varphi$. The second conjunct, $E_G C_G \varphi$, allows to generate $E_G^n \varphi$ for any finite $n$.

For example, let $C_G \varphi$. This is equivalent to $E_G (\varphi \land C_G \varphi)$, which in turn is equivalent to $E_G \varphi \land E_G C_G \varphi$. From $E_G \varphi$ we can imply $\varphi$ (the 'being veridical' part). In the second conjunct we can make a substitution according to the axiom: $E_G E_G (\varphi \land C_G \varphi)$. Again it can be broken down to $E_G E_G \varphi \land E_G E_G C_G \varphi$. So we get 'everyone knows that everyone knows $\varphi$'. By the same reasoning we can get an arbitrary long (and finite) stack of $E_G$'s that corresponds to $\varphi$ being a common knowledge.

$\endgroup$
3
  • $\begingroup$ I have a question! What would have gone wrong if we had $$ \vDash C_G\varphi \Leftrightarrow E_GC_G\varphi$$ in place of $$ \vDash C_G\varphi \Leftrightarrow E_G(\varphi\land C_G\varphi)$$ Even using $ \vDash C_G\varphi \Leftrightarrow E_GC_G\varphi$, we can generate $E_G^n\varphi$ for any finite $n$, using the exact same procedure you did. What's wrong? Thank you! $\endgroup$ Apr 15, 2021 at 3:36
  • 2
    $\begingroup$ Good question! Note that in $E^n_G \varphi$ there is no common knowledge operator. Hence we need $\varphi$ without $C_G$ in the right-hand side to achieve this. If we take your validity, we can only get $E^n_G C_G \varphi$ for any $n$. Hence, we cannot get rid of the operator $C_G$, and this does not capture the semantical intuition that $C_G \varphi$ implies $E^n_G \varphi$ for any $n$. $\endgroup$ Apr 15, 2021 at 8:41
  • $\begingroup$ Thanks for the clarification. I think the reason for this becomes more apparent in the formal proof I've posted (as a separate answer). Let me know your thoughts! $\endgroup$ Apr 17, 2021 at 6:09
4
$\begingroup$

The definition seems to be trying to capture exactly the recursive definition of "common knowledge" that you describe in your post. Using the axiom repeatedly, we would be able to reason that $$C_G\varphi \implies E_G(\varphi \wedge C_G(\varphi)) \implies E_G(C_G(\varphi))\\ \implies E_G(E_G(\varphi \wedge C_G\varphi)) \implies E_G(E_G(\varphi)),$$ for example -- so that common knowledge of $\varphi$ implies that "everyone knows everyone knows $\varphi$", as it should.

$\endgroup$
0
$\begingroup$

The existing answers are flawless, but I was able to gain some more intuition after writing down a formal proof. I decided to post it as an answer in case anyone's interested:

$[\Rightarrow]$: Suppose $(M,s)\vDash C_G\varphi$. Thus, $(M,t)\vDash\varphi$ for all states $t$ that are $G$-reachable from $s$. In particular, if $u$ is $G$-reachable from $s$ in 1 step, then $(M,u)\vDash\varphi$ and $(M,t)\vDash\varphi$ for all $t$ that are $G$-reachable from $u$. Then, $(M,u)\vDash \varphi \land C_G\varphi$ for all $u$ that are $G$-reachable from $s$ in 1 step, so $(M,s)\vDash E_G(\varphi \land C_G\varphi)$.

$[\Leftarrow]$: Suppose $(M,s)\vDash E_G(\varphi \land C_G\varphi)$. Suppose $t$ is $G$-reachable from $s$, and $s'$ is the first node after $s$ on a path from $s$ to $t$ whose edges are labeled by members of $G$. Since $(M,s)\vDash E_G(\varphi \land C_G\varphi)$, it follows that $(M,s')\vDash \varphi \land C_G\varphi$. Two cases arise: either $s' = t$ or $t$ is $G$-reachable from $s'$. If $s' = t$, we get $(M,t)\vDash\varphi$ due to $(M,s')\vDash\varphi$. If $t$ is $G$-reachable from $s'$, we get $(M,t)\vDash\phi$ since $(M,s')\vDash C_G\varphi$. Since $(M,t)\vDash\varphi$ for all $t$ that are $G$-reachable from $s$, it follows that $(M,s)\vDash C_G\varphi$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .