8장의 제목은 '일방 링크형성'입니다. 이제 본격적으로 문제 풀이에 들어갑니다. 행위자들의 전략쌍에 대응되는 방향성 있는 연결망 g가 얻어졌을 때 행위자 i의 보수는 다음처럼 주어진다고 가정합니다. 첫번째 인수는 자신을 포함하여 자신으로부터 (링크의 방향성을 고려하지 않고) 도달가능한 노드의 개수이고, 두번째 인수는 i로부터 나가는 이웃수입니다.
$$\Pi_i(g)=\phi(\hat n_i(g),\eta_i^d(g))$$
φ의 두 인수를 순서대로 x와 y라고 하면 φ는 x에 대한 순증가(strictly increasing)함수, y에 대한 순감소(strictly decreasing)함수라고 가정합니다. 위 보수에 관한 식을 식8.1로 부르고, φ에 대한 가정을 가정8.1로 부르겠습니다. 이로부터 정리8.1이 제시됩니다.
정리8.1 보수가 식8.1처럼 주어지고 그게 가정8.1을 만족한다면, 내쉬연결망(Nash network)은 최소로 연결되어 있거나 비어있다.
책에 나온대로 가장 간단한 예인 선형 모형을 통해 정리8.1을 음미해보겠습니다.
$$\Pi_i(g)=\hat n_i(g)-\eta_i^d(g)c$$
여기서 c는 양수인데 0<c<1인 영역과 1<c<n-1인 영역으로 나누어서 생각합니다. c=1인 경우는 언급되지 않네요.;;; 보수가 이렇게 주어졌을 때 i가 링크를 하나 더한다고 생각해보면, ηi가 1 늘어나겠죠. (윗첨자 귀찮아서 뺍니다;;) 도달가능하지 않았던 노드에 연결하는 경우 ni도 최소 1만큼 커집니다. (역시 모자 표시 귀찮아서 뺍니다;;;) 이때 c가 1보다 작다면 링크를 함으로써 보수가 증가하겠죠. 즉 도달가능하지 않았던 노드에 연결할 동기가 주어집니다. 하지만 모든 노드가 일단 다 연결되어 있다면 '도달가능하지 않았던 노드'가 남아있질 않으므로 거기서 멈추겠죠. 이미 ni=n이므로 링크를 더해봐야 ni가 더 커질 수는 없습니다. 이런 상태에서 링크를 새로 만들면, 다시 말해서 고리(loop)를 만들면 이득 없이 비용만 발생하므로 아무도 하려고 하지 않겠죠. 고리 없이 모든 노드가 연결된 걸 가리켜 걸침나무(spanning tree)라고 부르기도 합니다.
다음으로 c가 n-1보다 크다면 링크를 하나 새로 만드는데 드는 비용이 n-1보다 커집니다. 새로운 링크를 만들어서 얻을 수 있는 이득의 최대값이 n-1이므로 100% 손해보는 장사겠죠. 아무도 링크를 만들지 않을테니 내쉬연결망은 빈 연결망이 됩니다. c가 1보다 크고 n-1보다 작을 때는 링크를 만드는 비용이 꽤 크긴 하지만 이 비용을 상쇄할만큼 새로 연결된 노드로부터 얻을 수 있는 이득이 더 크다면 연결하려 하겠죠. 이 부분에 대해서는 나중에 또 얘기가 나올 것 같습니다.
책 내용을 전달하는데 중점을 두다보니 제 생각을 잘 정리하는 것도 아니고 이도저도 아닌 것 같네요. 여튼 '최소로 연결된 상태'를 다시 설명해보겠습니다. 일단 모든 노드가 연결되어 있으면 ni=n로 최대값이 됩니다. 그런데 고리가 있다면 그 고리를 이루는 링크를 지움으로써 이득은 그대로인데 비용이 줄어들게 됩니다. 당연히 지우려고 하겠죠. 또한 두 노드 사이의 링크가 있을 때 한쪽에서만 가리켜도 충분하므로 두 노드가 서로를 가리키면 전체적으로 불필요한 비용이 드는 경우가 됩니다. 결론적으로 n-1개의 방향성 있는 링크로 n개의 노드가 모두 연결된 걸침나무가 최적의 결과입니다. 그럼 이 n-1개의 방향성 있는 링크, 즉 시스템 전체적으로 (n-1)c 만큼의 비용이 드는데 이걸 누가 부담하느냐 하는 문제로 볼 수 있습니다. 이때 가능한 경우의 수가 많을텐데 그중에서도 행위자 수준에서 보수를 최대화하는 결과가 나올 겁니다.
그런 흐름에서 강내쉬균형(strict NE)을 정의하는데요, 모든 행위자가 다른 전략에서 얻는 보수보다 명백히(strictly) 더 높은 보수를 주는 전략을 이용하는 경우를 가리킵니다.
정리8.2 보수가 식8.1처럼 주어지고 그게 가정8.1을 만족한다면, 강내쉬연결망(strict Nash network)은 중심이 이끄는 별(center-sponsored star) 또는 빈 연결망이다.
'중심이 이끄는 별'은 제멋대로 한국어로 옮긴 겁니다;;; 이건 1개의 노드(중심 노드)가 다른 n-1개의 노드(주변 노드)를 가리키고, n-1개의 노드들은 아무도 가리키지 않는 방향성 있는 연결망을 뜻합니다. 즉 중심 노드가 링크의 모든 비용을 부담하겠다는 거죠. 이 정리8.2를 증명하는 내용은 봐도 모르겠네요;;; 위에도 썼듯이 빈 연결망이 아니라면 걸침나무 모양일테고, 결국 n-1개의 링크에 대한 비용을 나누어 부담하는 문제입니다. 이렇게만 보면 일종의 제로섬 게임이라 한쪽 보수가 높아지면 다른쪽 보수는 줄어들기 마련이죠. 그러므로 이들 중 하나에 있다면 다른 연결망으로 바꿀 이유가 없으며, 그래서 결론적으로 정리8.1과 정리8.2가 실질적으로 어떻게 다른지 이해할 수 없습니다;;;
이 차이를 설명할 하나의 가능성은 보수가 나가는 이웃수(ηi)의 선형함수가 아닌 경우입니다. 지금까지 편의상 위에 말한 선형 모형으로 생각해왔는데, 그렇지 않다면, 즉 보수가 나가는 이웃수의 비선형 함수라면 제가 생각한 '단순한 제로섬'은 아닐 것이고 그러면 문제가 해결될 가능성이 있습니다. 이건 제 추측이고 책에 있는 내용을 제대로 이해하지 못했기에 이러는 거죠.
정리8.3 보수가 식8.1처럼 주어지고 그게 가정8.1을 만족한다고 하자. 만일 0 이상 n-2 이하의 모든 정수 y와 y+1 이상 n-1 이하의 모든 정수 x에 대해 φ(x+1,y+1)>φ(x,y)라면 연결망의 동역학적 과정은 1의 확률로 유한한 시간 안에 중심이 이끄는 별로 수렴한다. 같은 조건에서 φ(x+1,y+1)<φ(x,y)라면 빈 연결망으로 수렴한다.
역시 위의 선형 모형으로 생각하면, 0<c<1일 때 중심이 이끄는 별이 되고, c>1일 때 빈 연결망이 됩니다. 증명은 세 가지 일반적인 논의를 이용한다는데, 첫째 어쨌든 빈 연결망 아니면 최소로 연결된 연결망으로 수렴한다. 둘째, 주변 행위자는 먼 행위자 대신 중심 행위자를 선호하여 평균경로를 줄인다. 이 둘째 논의가 정리8.2에도 반영되어 있지 않나 하는 생각이 드네요. 문제는 지금까지 세팅에서 '평균경로'는 전혀 중요한 요인이 아니라는데 있습니다. 평균경로가 중요해지려면 이전 글에서 소개된 연결 모형처럼 정보가 전달될 때마다 정보의 가치가 감소하는 요인이 있어야 합니다. 셋째, 행위자 사이의 조정실패를 회복하는 과정이 고려됩니다. i랑 j가 모두 k를 가리키고 있다가 서로 가리키면서 k와의 연결을 끊는 조정실패의 경우 k가 i나 j를 가리킬 거랍니다. 뭐 그럴 일이 없진 않겠지만 이로부터 중심이 이끄는 별이 될 이유는 모르겠네요. 이글은 여기까지.
