Prisoners dilemma games on graphs

Abstract

다양한 분야에서 협력이 일어나는 기제를 이해하기 위한 도구로 죄수의 딜레마 게임을 사용해왔다. 수많은 연구에서 협력을 설명하기 위한 다양한 가설들이 제시되었다. 성공적이라 평가되는 가설 중 하나는 진화 과정과 공간 구조의 조합이다. 첫 번째 장에서 공간 구조 위의 진화적 죄수의 딜레마 게임을 간단히 살펴보겠다. 그 다음 두 파트에서 두 가지 세부적인 측면에서 공간 구조 위의 진화적 죄수의 딜레마 게임을 연구한 결과를 제시하였다.

두 번째 장은 큰 세상 네트워크에서 작은 세상 네트워크로 변화가 가능한 네트워크 위에서 진행되는 죄수의 딜레마 게임에 대한 연구이다. 이 연구에서는 특히 협력 전략을 유지하는 행위자들이 이루는 집단에 대해 살펴보았다. 허브들 간의 연결이 많은 작은 세상 네트워크에서는 단 하나의 협력자 집단이 생성되며 전체적인 협력 수준도 높다. 반면, 큰 세상 네트워크에서는 다양한 크기를 갖는 수많은 협력자 집단이 형성되며, 협력자 비율은 상대적으로 높지 않다. 큰 세상 네트워크에서 작은 세상 네트워크로 네트워크를 변화시키면서 협력자 집단의 크기 분포를 조사하였고, 전이점에서는 크기 분포가 멱함수 꼴을 따른다는 점을 확인하였다.

세 번째 장에서는 진화적 죄수의 딜레마 게임에 혼합 전략을 도입했다. 죄수의 딜레마 게임에서 혼합 전략은 행위자의 협력 확률로써 표현 가능하다. 적용 사례로서, 레귤러 그래프 위에서 두 가지 혼합 전략만으로 진행되는 죄수의 딜레마 게임에서 진화적 안정성을 조사했다. 다른 전략의 침입을 허용하지 않는 전략을 진화적으로 안정한 전략이라고 한다. 결정론적인 게임 법칙 하에서는 항상 진화적으로 안정한 전략이 존재한다는 점을 확인했다. 이러한 전략을 가진 집단은 다른 전략의 침입 시도에도 불구하고 본래의 협력 수준을 유지할 수 있다. 죄수의 딜레마 게임에 혼합 전략을 도입한 이 연구는 보다 현실에 가까운 게임의 기초가 될 수 있을 것이다.

Prisoner's dilemma(PD) game has been used widely in various disciplines as a tool to understand the mechanisms to evoke the cooperation although a player's favorable choice is not cooperative. Among a variety of explanations for the emergence of cooperation, the combination of evolutionary process and spatial structure is one of the successful hypotheses. In the first chapter, we review the spatial evolutionary PD games shortly. In the next two parts, we study the spatial evolutionary PD games in two detailed aspects.

In the second chapter, we study the PD games on several scale-free networks bridging between large-world and small-world types. Especially, we focus on the clusters of permanent cooperators. In small-world networks where the hubs are interconnected, one cooperator cluster is formed, and overall cooperation level is relatively high. On the other hand, in large-world networks where the hubs are separated, the clusters of cooperators with diverse sizes are formed, and the fraction of cooperators is not high. We investigate the cluster size distribution, changing networks from large-world ones to small-world ones, and find that the cluster size follows a power law at the transition point.

In the third chapter, we introduce mixed strategies into spatial evolutionary PD games. The probability of cooperation is used to represent the mixed strategies. As an application, we investigate the evolutionary stability in PD games with two mixed strategies on several types of regular graphs. A strategy which doesn't allow the invasion of other strategy is called an evolutionarily stable strategy. We find that under the deterministic game rules, there always exist evolutionarily stable strategies. These strategies can maintain the cooperation level against the invasion of other strategies. The introduction of mixed strategies in PD games can be the basis of more realistic PD games.