4.4-common-knowledge.md

4.4 Common Knowledge

binary mask $$\mu^a$$에 대한 중요한 특성은 agent$$a$$가 entity $$e$$를 볼 수 있느냐에만 달려 있다는 점입니다. 그렇기 때문에 만약 agent $$a$$의 모든 mask $$\mu^a$$가 common knowledge라면, 다른 agent $$ b$$가 $$ a$$를 볼 수 있다면 $$ a$$와 그가 볼 수 있는 entities $$ e$$에 대해 $$ a,e \in \mathcal{M}^b_s$$임을 알 수 있습니다.

한 그룹이 알고있는 Mutual knowledge $$\mathcal{M}^\mathcal{G}_s ,\mathcal{G}\subseteq \mathcal{A}$$라고 정의할 때 이는 다음과 같이 표현할 수 있습니다.

                                                                       $$ \mathcal{M}^\mathcal{G}_s = \cap_{a \in \mathcal{G}} \mathcal{M}^\mathcal{a}_s$$

그러나 이러한 mutual knowledge는 common knowledge를 뜻하지 않습니다. 그저 다같이 알고있는 entities이기 때문입니다. 대신 한 group의 common knowledge는 $$\mathcal{L}^\mathcal{G}_s$$로 표현하는데, 이는 정의대로 group $$ \mathcal{G}$$가 $$\mathcal{L}^\mathcal{G}_s$$를 알고, $$ \mathcal{G}$$모두가 $$\mathcal{L}^\mathcal{G}_s$$를 안다는 사실을 아는 정보입니다.

agent $$a$$가 다른 agent $$ b$$도 $$e \in\xi $$를 보고있는지 알기 위해선, agent $$ a$$도 $$ b$$를 봐야하고 $$ b$$가 $$e$$를 보고있는지 알아야하는데 이는 다음과 같이 표기할 수 있습니다.

                                                          $$ \mu^a(s^a,s^b) \wedge \mu^b(s^b,s^e)= \top$$

$$\mathcal{L}^\mathcal{G}_s$$는 다음과 같이 재귀적인 형태로 표현도 가능합니다. 모든 agent $$ a $$가 그룹 $$\mathcal{G}$$에 속한다면, 다음과 같이 표현 가능합니다.

                                                 $$ \mathcal{L}^{\mathcal{G}}_s = \lim_{m\rightarrow \infty}{\mathcal{L}^{a,m}_s}, \mathcal{L}^{a,0}_s = \mathcal{M}^a_s$$

                                              $$ $$$$ \mathcal{L}^{a,m}_s =\bigcap_{b\in\mathcal{G}}\{e\in \mathcal{L}^{b,m-1}_s|\mu^a(s^a,s^b)\} \cdots (4.4.2)$$

 이는 iteration m=0일 때, agent $$a $$에 대한 mutual knowledge $$\mathcal{M}^a_s$$는 $$ \mathcal{L}^{a,0}_s$$와 같습니다. 스스로 가지고 있는 mutual knowledge는 스스로의 common knowledge가 됩니다. 

m = 1로 iteration을 진행해보겠습니다.

                                              $$ $$$$ \mathcal{L}^{a,1}_s =\bigcap_{b\in\mathcal{G}}\{e\in \mathcal{L}^{b,0}_s|\mu^a(s^a,s^b)\}$$

                                                        $$ $$$$  =\bigcap_{b\in\mathcal{G}}\{e\in \mathcal{M}^{b}_s|\mu^a(s^a,s^b)\}$$

이를 해석하면, a가 observe할 때, a가 보는 b에 관한 entities에 대해 mutual knowledge$$\mathcal{M}^b_s$$에 포함되고, 이것에 대한 그룹 전체의 교집합을 하게 되면, $$\mathcal{L}^{a,1}_s$$는 그룹 내 전체가 아는 entities라는 것을 알 수 있습니다.

m = 2로 iteration을 더 진행해 보겠습니다.

                                              $$ $$$$ \mathcal{L}^{a,2}_s =\bigcap_{b\in\mathcal{G}}\{e\in \mathcal{L}^{b,1}_s|\mu^a(s^a,s^b)\}$$

결국, agent가 a가 봤을 때, 모든 agent가 $$\mathcal{L}^{a,1}_s$$를 알고 있다는 사실은 상대방이 알고있다는걸 알고있는 상태를 의미합니다. 이를 무한대로 보내는 행위는 위의 행위를 반복하는 것은 mutual knowledge$$\mathcal{M}^b_s$$가 common knowledge$$\mathcal{L}^\mathcal{G}_s$$가 된다는 것을 알 수 있습니다.

Lemma 4.4.1

만약 모든 mask $$\mu$$가 모든 agent에게 알려져있다면, common knowledge $$\mathcal{L}^\mathcal{G}_s$$는 다음과 같이 정의할 수 있습니다.

                                                   $$\mathcal{L}^\mathcal{G}_s= \left\{\begin{matrix} \mathcal{M}^\mathcal{G}_s,\mathrm{if} \wedge_{a,b\in \mathcal{G}}\mu^a(s^a,s^b)\\   \emptyset\ \ \ ,\ \ \ \ \ \ \ \ \ \ \ \ \mathrm{otherwise}  \end{matrix}\right.$$

이를 해석해보면, 각 agent가 다른 모든 agent를 관찰했을 때에 공통적으로 아는 mutual knowledge$$\mathcal{M}^b_s$$에 대해 common knowledge $$\mathcal{L}^\mathcal{G}_s$$로 표현할 수 있다는 뜻입니다.

위의 재귀적인 표현에서는 공집합에대해 rough하게 보여줬지만 여기서는 좀 더 엄격하게 나타내었다고 볼 수 있습니다.

이를 정의하기 위해 (4.4.2)를 보겠습니다. 이는 재귀의 $$\mathcal{L}^{a,0}_s = \mathcal{M}^a_s$$부터 시작한다면, 아래와 같음을 알 수 있습니다.

                                              $$\mathcal{L}^{a,1}_s= \left\{\begin{matrix} \mathcal{M}^\mathcal{G}_s,\mathrm{if} \wedge_{b\in \mathcal{G}}\mu^a(s^a,s^b)\\   \emptyset,\mathrm{otherwise}  \end{matrix}\right.$$

이 때, 그룹내의 mutual knowledge$$\mathcal{M}^{\mathcal{G}}_s$$는 귀납적으로 몇번의 iteration 후에 $$ \mathcal{L}^{c,m}_s = \mathcal{M}^{\mathcal{G}}_s$$이 됨을 볼건데, 이전에 mutual knowledge가 common knowledge가 되는 것은 2번임을 보았습니다. 이는 다음을 통해 수식화 가능합니다.

             $$ \mathcal{L}^{a,m+2}_s = \{e\in\xi|\bigwedge_{b\in\mathcal{G}}(\mu^a(s^a,s^b)\wedge \bigwedge_{c\in\mathcal{G}}(\mu^b(s^b,s^c)\wedge e\in \mathcal{L}^{c,m}_s))\}$$

                             $$ = \{ e \in \mathcal{M}^\mathcal{G}_s|  \wedge_{b,c\in\mathcal{G}}\mu^b(s^b,s^c)\} = \mathcal{L}^\mathcal{G}_s$$

그러므로 그룹내의 어느 agent의 knowledge로 부터 시작하던지, agent는 모든 agent는 서로를 볼 수 있습니다.

Common Knowledge는 그룹 내의 모든 agent에 대해 오직 볼 수 있는 mutual knowledge에서만 계산되어 얻어질 수 있습니다. policy에 의해 선택된 action은 그 자체로 Common knowledge로 볼 수 있는데, 이는 오직 common knowledge와 그를 랜덤으로 선택할때의 seed에 대한 rule common knowledge에만 의존합니다.

그룹 내에서 시간에 따른 common knowledge는 이전의 trajectories $$ \tau_0$$부터 최근 관측한 trajectory $$\tau^\mathcal{G}_t = (\tau_0,o^\mathcal{G}_1,\bold{u}^\mathcal{G}_1,...,o^\mathcal{G}_t,\bold{u}^\mathcal{G}_t)$$와 $$o^\mathcal{G}k = {s^e_k | e \in \mathcal{L}^{\mathcal{G}}{s_k}}$$가 있습니다. 모든 masks $$\mu^a$$를 아는 것은 $$\tau^{\mathcal{G}}_t = \mathcal{L}^\mathcal{G}(\tau^a_t)$$를 $$\tau^a_t = (\tau_0,o^a_1,...,o^a_t)$$를 통해 도출할 수 있는 것을 의미합니다. 그렇기 때문에$$\tau^{\mathcal{G}}$$에 의해 조건화되는 모든 함수는 그룹내의 agent에 의해 독립적으로 계산될 수 있습니다.