앞 글의 일방 링크에서 각 행위자는 상대의 동의를 구할 필요 없이 자신의 보수를 최대화하는 전략을 선택했습니다. 이 글에서는 서로 합의해야만 링크가 생기는 쌍방 링크의 경우를 보겠습니다. 일방 링크의 경우 전략쌍이 곧바로 하나의 방향성 있는 연결망에 대응되었지만, 쌍방 링크의 경우 전략쌍은 각 행위자의 의도일 뿐, 쌍방이 모두 서로를 가리키는 경우에만 방향성 없는 링크가 형성되고 이 링크들로 이루어진 방향성 없는 연결망이 그 결과로 나옵니다.
$$g_{ij}=\min\{s_{ij},s_{ji}\}$$
이걸 풀어쓰면, i와 j가 서로를 가리킬 때에만 실제로 링크가 생긴다.는 말입니다. 또한 이 식은 전략쌍의 함수로서 연결망을 뜻하는데, 간단히 g(s)로 표현합니다.
잭슨(Jackson)과 올린스키(Wolinsky; 볼린스키?)가 제시했다는 연결모형(connections model)에서 각 행위자의 보수는 다음처럼 주어진다네요. 역시 수식을 보기 전에;; 0 이상 1 이하의 δ라는 양을 도입합니다. 이를테면 제가 갖고 있던 정보의 가치가 1이라고 하면 그게 제 이웃에게 전달되면서 그 가치는 δ가 되고, 제 이웃이 다른 이웃에게 전달할 때 또 δ가 곱해져서 δ2이 됩니다. 즉 저와 d 단계만큼 떨어져 있는 행위자는 저의 정보로부터 δd의 가치를 얻습니다. 극단적으로 δ가 0이면 정보가 저를 떠나자마자 사라지겠고, δ가 1이면 가치가 전혀 감소하지 않겠죠. 이게 가치로 인한 이득이라면, 비용은 제 이웃수에 비례하여 커집니다. 이웃 한 명마다 c만큼의 비용이 든다고 합시다. c는 양수라고 하면 행위자 i는 다음과 같은 보수를 얻습니다.
$$\Pi_i(s)=1+\sum_{j\in N_i(g(s))\backslash \{i\}}\delta^{d(i,j;g(s))}-\eta_i(g(s))c$$
이것도 역시 문제를 제시했을 뿐 풀지는 않습니다. 푸는 건 나중에 나올 듯.
이제 연결망의 내쉬균형(Nash equilibrium; NE)을 정의합니다. 어떤 전략쌍 s*가 다음을 만족시킬 때 이를 NE라고 합니다.
$$\Pi_i(g(s_i^*,s_{-i}^*))\geq \Pi_i(g(s_i,s_{-i}^*))\ \textrm{for all}\ s_i,\ i$$
즉 각 행위자가 자신의 전략을 바꿀 요인이 없는 상황의 전략쌍이 NE입니다. 이로부터 빈 연결망(empty network; 링크가 0개인 연결망)은 어떤 연결망 형성게임에 대해서도 NE가 된다고 합니다. 저를 제외한 나머지 모두가 어떤 링크도 원하지 않는다고 발표하는 상황에서 저의 최적대응은 역시 어떤 링크도 원하지 않는다고 발표하는 것이기 때문이랍니다. 그런데 어차피 아무도 링크를 원하지 않으면 제가 무슨 전략을 택하든 결과적으로 저 역시 링크를 만들지 못합니다. 하지만 그렇다고 그 상황에서 제가 어떤 링크도 원하지 않는다고 하는 게 최적대응인지 모르겠네요. 위의 연결모형에서 정의된 보수를 예로 들면, 저의 전략 si에 무관하게 g(s)는 빈 연결망이라 저의 보수도 제 전략에 무관해지거든요. 일단 패쓰.
이제 안정성 조건을 보겠습니다. 특히 어떤 연결망에 링크 한 개를 추가하거나 없애려고 할 때 관련된 행위자들 모두에게 이득이 되지 않을 때 이런 연결망을 짝으로 안정하다(pairwise stable; 짝, 즉 링크 하나의 변화에 대해 안정)고 합니다. 이 조건을 수식으로 써봅니다.
$$\textrm{(i) for every}\ g_{ij}=1,\ \Pi_i(g)\geq \Pi_i(g-g_{ij})\ \textrm{and}\ \Pi_j(g)\geq \Pi_j(g-g_{ij})$$
$$\textrm{(ii) for}\ g_{ij}=0,\ \Pi_i(g+g_{ij})> \Pi_i(g) \Rightarrow \Pi_j(g+g_{ij})< \Pi_j(g)$$
첫째 조건은 기존 링크를 하나 없애는 경우에 그 링크로 연결된 행위자 i와 j의 보수가 둘 다 그대로거나 줄어든다는 말입니다. 이러면 이 두 행위자 모두 링크를 없앨 이유가 없죠. 두번째 조건은 연결되지 않은 두 행위자 i와 j 사이에 링크를 새로 만드는 경우, 이로 인해 한 쪽은 좋아지지만 다른 쪽이 손해를 본다면 역시 '쌍방' 합의가 이루어지지 못해 링크가 생길 이유가 없습니다. 다시 말해서, 두 행위자 모두 보수가 커지는 경우만 아니면 링크를 새로 만들려고 하지 않는다는 말입니다.
다음으로 연결망의 상태공간에서 경로이되 행위자들의 보수가 나아지는 경로를 개선경로(improving path)로 정의합니다. 연결망 g에서 시작하여 유한한 개수(여기서는 k-2개)의 중간 연결망을 거쳐 최종 연결망 g'에 이르는 경로를 생각합니다.
$$g^1\to g^2\to \cdots\to g^k\ \textrm{with}\ g^1=g,\ g^k=g'$$
한 연결망에서 다음 연결망으로 넘어갈 때 다음 두 조건 중 하나를 만족하면 개선되었다고 볼 수 있습니다.
$$\textrm{(i) for some}\ g_{ij}^l=1,\ \Pi_k(g^l-g_{ij})>\Pi_k(g^l)\ \textrm{for}\ k\in\{i,j\}$$
$$\textrm{(ii) for some}\ g_{ij}^l=0,\ \Pi_i(g^l+g_{ij})>\Pi_i(g^l)\ \textrm{and}\ \Pi_j(g^l+g_{ij})\geq\Pi_j(g^l)$$
물론 (i)을 만족하는 경우, 다음 연결망은 이전 연결망에서 gij를 없앤 것이고, (ii)를 만족하는 경우, 이전 연결망에 새 링크 gij를 추가한 게 다음 연결망이 될 것입니다. 그런데 조건 (ii)에서 '크거나 같다'가 눈에 밟히죠?;;; (i)에서는 두 행위자 모두에게 같은 조건이었는데 (ii)에서는 등호가 없고 있고 차이가 있습니다. 있던 링크를 없앨 때는 당사자들 모두에게 이득이 분명해야 하지만, 없던 링크를 만들 때는 적어도 한쪽만 이득이 생겨도 문제 없다는 얘긴데... 정의야 그렇게 한다고 해도 그 맥락을 모르겠습니다.
이런 '개선경로'는 마치 통계물리의 이징모형에서 스핀 1개를 뒤집어보고 전체 에너지가 낮아질 때에만 받아들임으로써 시스템의 바닥상태를 찾는 알고리즘을 떠올리게 합니다. 여튼 더이상 개선될 여지가 없는 연결망이 '짝으로 안정한' 연결망이 되겠죠. 그리고 개선경로가 닫혀서 순환(cycle)이 될 수도 있고요.
지금까지는 링크 1개를 더하거나 뺄 때만 갖고 안정성을 정의했지만 링크 여러개를 동시에 더하거나 뺄 때에 대해서는 따로 논의되어야 합니다. 이런 맥락에서 '짝 안정성'을 확장하는데, 앞에서 소개한 내쉬균형에 어떤 행위자 사이에서도 새로운 링크를 만들려고 하지 않는다는 조건을 추가하여 '짝 균형(pairwise equilibrium)'을 정의합니다. 즉 짝 균형 연결망 g*를 만드는 NE 전략쌍 s*가 존재한다고 할 때 다음 조건을 만족시켜야 합니다.
$$\textrm{for any}\ g_{ij}(s^*)=0,$$
$$\Pi_i(g(s^*)+g_{ij})>\Pi_i(g(s^*))\Rightarrow\Pi_j(g(s^*)+g_{ij})<\Pi_j(g(s^*))$$
그러면서 나오는 예제로 아래 그림을 봅시다. 세 명의 행위자로 이루어진 연결망 게임인데요, 가능한 모든 경우에 각 행위자의 보수가 다음처럼 주어진다고 가정합니다.
맨 왼쪽의 빈 연결망에서 아무나 두 행위자를 잡아서 링크가 생기는 경우를 보면 당사자들 모두 보수가 높아지므로 링크가 생길 수 있습니다. 여기서 빈 연결망은 짝으로 안정하지 않습니다. 하지만 그 외의 경우 링크가 2개인 연결망과 3개인 완전 연결망(complete network)과 비교할텐데 이때 어떤 경우도 빈 연결망에서 행위자들의 보수보다 커지지 않습니다. 즉 빈 연결망은 완전균형(perfect equilibrium) 연결망입니다. 모르겠네요;;;
