The 19th Annual Conference of the Japanese Society for Artificial Intelligence, 2005

3E3-04

集団分割による協調の安定
The Stability of Cooperation by Dividing a Group
千葉 一博
Kazuhiro Chiba

東京家政学院大学情報処理センター
Information Processing Center, Tokyo Kasei Gakuin University

In this research, first, in a social dilemma game we show a condition on the cost that the player may bear individing the group. Next, we clarify that a Tit for Tat strategy is stable by dividing the group.

1.

式 (1) (3) (4) より，0 < f (x + 1) − f (x) < N b の条件で，資源提供ゲームは社会的ジレンマゲームである．以降，この条件が成り立つとする．

はじめに従来より，いたるところで大小様々な集団が社会的ジレンマに直面している．社会的ジレンマとは，他者の意思決定の如何に関わらず社会的に協調するよりも裏切るほうが個々にとっては良いが，全員が裏切るより全員が協調するほうが全員にとって良いという状況のことである．このような状況で協調が実現されるのは困難である．本研究の目的は，社会的ジレンマにおいて，集団を分割することによって協調が安定となることを明らかにすることである．集団のメンバーについては，単純な意
思決定ができるソフトウェアでもよいと考えるので，ここではエージェントということばを用いる．

2.

3.

今，社会的ジレンマゲームを繰り返し行う場合を考える．このとき，しっぺ返し戦略を以下のように定義する．
定義 3 N 人社会的ジレンマゲームにおいて，次のような戦略
をしっぺ返し戦略（TFT: Tit for Tat）という．

• 一回目は C をとる．
• 二回目以降は，前回，D をとったプレイヤが存在すればD をとり存在しなければ C をとる．

社会的ジレンマゲーム

N 個のエージェントからなる集団を考える．本研究では，
エージェントを N 人ゲームのプレイヤとみなす．はじめに，
社会的ジレンマゲームを以下のように定義する [Dawes 80]．

また，AllD という戦略を毎回 D をとる戦略と定義する．
戦 略 X1 , . . . , X N を そ れ ぞ れ と る プ レ イ ヤ の 集 団 を{X1 , . . . , XN } とする．X1 , . . . , XN がすべて同じ戦略 Y のとき，その集団を {Y N } と表す．また，{X1 , . . . , XN } における Xi の各回の利得の和を累積利得 V (Xi |{X1 , . . . , XN })とする．
ところで，戦略 X ，Y の二人ゲームにおける X の累積利
得を V (X|Y ) とするとき，V (X|Y ) > V (Y |Y ) ならば X は
Y に侵入することができる [Axelrod 84]．本研究では，N 人
ゲームにおける戦略の侵入について以下のように定義する．

定義 1 N 人ゲームにおける各プレイヤが，協調を意味する C
または裏切りを意味する D という手をとる．C をとるプレイ
ヤの数を x とするとき，C をとるプレイヤの利得を C(x)，Dをとるプレイヤの利得を D(x) とする．ここで，式 (1) (2) を満たすゲームを社会的ジレンマゲームという．

D(x) > C(x + 1)

(1)

D(0) < C(N )(2)

定義 4 {X} ∪ {Y N −1 } において，V (X|{X} ∪ {Y N −1 }) >V (Y |{X} ∪ {Y N −1 }) ならば X は Y に侵入することができる．

次に，資源提供ゲームを以下のように定義する [小山 04]．
定義 2 N 人ゲームにおける各プレイヤが，b の価値をもつ資源を集団に提供するかしないかを決定する．ただし b > 0 とする．資源を提供するプレイヤの数を x とするとき，資源を提供するプレイヤの利得を C(x)，提供しないプレイヤの利得
を D(x) とする．ここで，式 (3) (4) を満たすゲームを資源提供ゲームという．
f (x)(3)C(x) =
N

D(x) =f (x)+bN

しっぺ返し戦略は侵入される

資源提供ゲームを繰り返し T 回行う場合，次式のようになる．

V (AllD|{AllD} ∪ {TFTN −1 }) =f (N − 1)+ b + (T − 1)bN

V (TFT|{AllD} ∪ {TFTN −1 }) =f (N − 1)+ (T − 1)bN

よって，V (AllD|{AllD} ∪ {TFTN −1 }) > V (TFT|{AllD} ∪{TFTN −1 }) より AllD は TFT に侵入することができる．

(4)

4.

ただし，f (x) は x の増加関数であり，f (0) = 0，f (N ) > N b
である．

集団の分割

今，集団を m 個の小集団に分割する．簡単のため，各小集団におけるプレイヤの数をいずれも n とする．すなわち，
N = nm，n ≥ 2，m ≥ 2 である．また，f (n) > nb，0 <f (x + 1) − f (x) < nb とする．

連 絡 先: 千 葉 一 博 ，東 京 家 政 学 院 大 学 ，町 田 市 相 原 町
2600，Tel: 042-782-9811，Fax: 042-782-9880，E-mail:chiba@kasei-gakuin.ac.jp1

The 19th Annual Conference of the Japanese Society for Artificial Intelligence, 2005

4.1

式 (6) (9) より，T が次式を満たすとき TFT は AllD に侵入されない．

繰り返し回数に基づく解析

集団を分割するためには，各プレイヤが等しくコストを負うべきだと考える．このコストを δ とする．ただし δ ≥ 0 である．分割することによって “最悪の場合でも得られる累積利得” が小さくなってしまうと分割の意義がない．よって，資源提供ゲームを繰り返し T 回行う場合，式 (5) が成り立たなけ
ればならない．
f (1)
f (1)
−δ ≥T
(5)
T
n
N

T >

例えば，n = 4，m = 4，f (x) = 40x，b = 20 のとき，T >
7/4，すなわち繰り返し 2 回以上行う場合，TFT は AllD に侵入されない．

4.2

ゆえに，δ に関する条件は次式のようになる．

0 ≤ δ ≤ (m − 1)T

f (1)
N

ゆえに，δ に関する条件は次式のようになる．

0 ≤ δ ≤ (m − 1)

定義 5 {X} ∪ {Y
} に お い て ，小 集 団 {X} ∪{Y n−1 }, {Y n }m−1に 分 割 す る と き ，V (X|{X} ∪{Y n−1 }, {Y n }m−1 ) > V (Y |{X} ∪ {Y n−1 }, {Y n }m−1 )ならば X は Y に侵入することができる．

V (AllD|{AllD} ∪ {TFTn−1 }, {TFTn }m−1 )=資源提供ゲームを繰り返し T 回行う場合，式 (6) のようになる．

V (TFT|{AllD}∪{TFTn−1 }) =(6)

V (TFT|{TFTn }) =f (n − 1)+(T −1)b−δ (7)
n
f (n)
−δ
n

=

(8)

w>

(n − 1)f (n − 1)
n−1
m−1
+
(T − 1)b +T f (n)(N − 1)n
N −1
N −1

5.

TFT が AllD に侵入されないためには，式 (10) が成り立たなければならない．
V (AllD|{AllD} ∪ {TFT
<

n m−1

}, {TFT }V (TFT|{AllD} ∪ {TFT

n−1

(13)

(n − 1)f (n − 1)(n − 1)wb+(N − 1)n(N − 1)(1 − w)
m−1
f (n) − δ+(N − 1)(1 − w)

(14)(m − 1)(f (n − 1) − (f (n) − nb)) + (n − 1)b(m − 1)f (n − 1) + (n − 1)b(15)

例えば，n = 4，m = 4，f (x) = 40x，b = 20 のとき，w > 3/7
で繰り返し行う場合，TFT は AllD に侵入されない．

(9)

n−1

f (n)
−δ
(1 − w)n

TFT が AllD に侵入されないためには，式 (10) が成り立たなければならない．式 (11) (14) より，w が式 (15) を満たす
とき TFT は AllD に侵入されない．

V (TFT|{AllD} ∪ {TFTn−1 }, {TFTn }m−1 )1=((n − 1)V (TFT|{AllD} ∪ {TFTn−1 })N −1+ n(m − 1)V (TFT|{TFTn }))−δf (n − 1)wb+−δ (12)n
1−w

V (TFT|{AllD} ∪ {TFTn−1 }, {TFTn }m−1 )式 (7) (8) より，TFT の累積利得の平均は式 (9) のように
なる．

=

(11)

式 (12) (13) より，TFT の累積利得の平均は式 (14) のようになる．

また，TFT の累積利得は小集団によって以下のように異なる．

V (TFT|{TFTn }) = T

f (n − 1)
b
+
−δ
n
1−w

また，TFT の累積利得は小集団によって以下のように異なる．

V (AllD|{AllD} ∪ {TFTn−1 }, {TFTn }m−1 )V (TFT|{AllD}∪{TFTn−1 }) =f (1)(1 − w)N

資源提供ゲームを割引率 w で繰り返し行う場合，式 (11) のようになる．

N −1

f (n − 1)+ b + (T − 1)b − δn割引率に基づく解析

一回のゲームのたびごとにさらにゲームを続けるかどうかを表す確率（割引率）を w とする．ただし 0 ≤ w < 1 である．
このとき，ゲームの繰り返し回数は 1/(1 − w) になる．分割することによって “最悪の場合でも得られる累積利得” が小さくならないためには，式 (5) より次式が成り立たなければな
らない．
f (1)
f (1)
−δ ≥
(1 − w)n(1 − w)N

例えば，N = 16，m = 4，f (x) = 40x のとき，0 ≤ δ ≤ 15T /2となる．
小 集 団 {X11 , . . . , X1n }, . . . , {Xm1 , . . . , Xmn } が す べて 同 じ 小 集 団 {Y1 , . . . , Yn } の と き {Y1 , . . . , Yn }m と
表 す．集 団 を 分 割 す る 場 合 ，同 じ 戦 略 で も 小 集 団 が 異な れ ば 累 積 利 得 が 異 な る こ と が あ る ．そ こ で ，小 集 団{X11 , . . . , X1n }, . . . , {Xm1 , . . . , Xmn } における Xij の累積利得の平均を V (Xij |{X11 , . . . , X1n }, . . . , {Xm1 , . . . , Xmn })とし，戦略の侵入について以下のように再定義する．

=(m − 1)f (n − 1) + (n − 1)b(m − 1)(f (n) − nb)

集団的に安定な戦略

ところで，戦略 X ，Y の二人ゲームにおいて，Y と異なる
任意の X に対して Y が X に侵入されないならば Y は集団的に安定な戦略（CSS: Collectively Stable Strategy）である[Axelrod 84]．本研究では，N 人ゲームにおける CSS について同様に定義する．

)}, {TFTn }m−1 ) (10)2The 19th Annual Conference of the Japanese Society for Artificial Intelligence, 2005
戦略 \ 回目
X
TFT

1
C
C

···
···
···

k−1
C
C

k
D
C

k+1
D
D

···
···
···

戦略 \ 回目
X
γ-TFT

1
C
C

···
···
···

k−1
C
C

k
D
C

k+1
D
C

···
···
···

図 1: X と TFT がとる手の列

図 2: X と γ-TFT がとる手の列

定義 6 Y と異なる任意の X に対して，Y が X に侵入されないならば Y は CSS である．

定理 1 集団を分割する場合，式 (15) を満たすとき TFT は
CSS である．

また，便宜上，ユニフォームゲームを以下のように定義する[Dawes 80]．

証明: 集団を分割する場合，式 (15) を満たすとき TFT は
AllD に侵入されない．AllD は TFT に対して最適だから，
TFT は AllD に侵入されないならば他の任意の戦略にも侵入されない．ゆえに，定義 6 より，集団を分割する場合，式 (15)を満たすとき TFT は CSS である．
（証明終）

定義 7 式 (16) (17) を満たす社会的ジレンマゲームをユニフォームゲームという．

D(x + 1) > D(x)(16)

C(x + 1) > C(x)(17)

今，しっぺ返し戦略を以下のように一般化する．
定義 8 N 人社会的ジレンマゲームにおいて，次のような戦略を一般的しっぺ返し戦略（γ-TFT）という．

たいていの社会的ジレンマゲームはユニフォームゲームである．資源提供ゲームもユニフォームゲームである．
今，{X} ∪ {TFTN −1 } において X と TFT がとる手の列について考える．X が C をとり続ける限り TFT も C をとり続ける．X が決して D をとらない場合，V (X|{X}∪{TFTN −1 }) =V (TFT|{X} ∪ {TFTN −1 }) である．この場合，定義 4 より
TFT は X に侵入されない．一方，図 1 のように，k 回目に Xが D をとる場合，k + 1 回目に TFT は D をとる．k ≥ 1 とする．このときどの TFT も D をとるから，k + 2 回目以降もX がとる手に関わらず TFT は D をとる．TFT の k + 1 回目
以降の手の列に対して X が最適な手をとるとすれば，式 (1)より，それは D をとり続けることである．すなわち，k 回目にX が D をとる場合，それより前までは X と TFT は互いに Cをとり続け，k + 1 回目以降は X が D をとり続けるのが最適反応になる．この場合，k 回目における X の D による利得とTFT の C による利得の差が繰り返しゲームの累積利得の差になる．k 回目における X の D による利得は wk−1 D(N − 1)，
TFT の C による利得は wk−1 C(N − 1) である．式 (1) より，
wk−1 D(N − 2) > wk−1 C(N − 1) である．また，ユニフォーム
ゲームならば式 (16) より wk−1 D(N −1) > wk−1 D(N −2) である．よって，wk−1 D(N − 1) > wk−1 C(N − 1) である．ゆえに，k 回目に X が D をとる場合，V (X|{X}∪{TFTN −1 }) >V (TFT|{X} ∪ {TFTN −1 }) である．この場合，定義 4 より
X は TFT に侵入することができる．したがって，TFT は
CSS ではない．
ところで，0 ≤ w < 1 より k = 1 のとき V (X|{X} ∪{TFTN −1 }) と V (TFT|{X} ∪ {TFTN −1 }) の差が最大になる．よって，TFT に対する最適な X は AllD である．これと同様なことは，集団を分割する場合の小集団 {X}∪{TFTn−1 }にもいえる．また，それ以外の小集団 {TFTn }m−1 におけるTFT の累積利得は X によらず一定である．ゆえに，累積利得の平均の差，すなわち V (X|{X} ∪ {TFTn−1 }, {TFTn }m−1 )と V (TFT|{X} ∪ {TFTn−1 }, {TFTn }m−1 ) の差が最大になるのは，累積利得の差，すなわち V (X|{X} ∪ {TFTn−1 }) とV (TFT|{X} ∪ {TFTn−1 }) の差が最大になる場合である．したがって，集団を分割する場合も，TFT に対する最適な X はAllD である．
さて，資源提供ゲームを割引率 w で繰り返し行う場合，次の定理が成り立つ．

• 一回目は C をとる．
• 二回目以降は，特定の γ に対して，前回，x/N < γ ならば D をとり x/N ≥ γ ならば C をとる．ここで，0 < γ ≤ 1 とする．
定義 8 より，定義 3 の TFT は 1-TFT と表すことができる．
また，(N − 1)/N < γ ≤ 1 のときは，1-TFT，すなわち TFTに対する議論と同じである．
ここでは，0 < γ ≤ (N −1)/N のとき，{X}∪{γ-TFTN −1 }において X と γ-TFT がとる手の列について考える．X が Cをとり続ける限り γ-TFT も C をとり続ける．X が決して D をとらない場合，V (X|{X}∪{γ-TFTN −1 }) = V (γ-TFT|{X}∪{γ-TFTN −1 }) である．この場合，定義 4 より γ-TFT は X に侵入されない．一方，k 回目に X が D をとる場合，x = N −1
だから x/N ≥ γ である．k ≥ 1 とする．よって，図 2 のように，k + 1 回目に γ-TFT は C をとる．同様に，k + 2 回目以降も X がとる手に関わらず γ-TFT は C をとる．γ-TFT の
k +1 回目以降の手の列に対して X が最適な手をとるとすれば，
式 (1) より，それは D をとり続けることである．すなわち，k
回目に X が D をとる場合，それより前までは X と γ-TFT
は互いに C をとり続け，k + 1 回目以降は X が D をとり続けるのが最適反応になる．この場合，k 回目以降における X のD による利得と γ-TFT の C による利得の差が繰り返しゲー
ムの累積利得の差になる．k 回目以降における X の D によ
P∞ i−1る利得は
w D(N − 1)，γ-TFT の C による利得は
i=kP∞

wi−1 C(N −1) である．式 (1) より，i = k, k+1, . . . に対して wi−1 D(N −2) > wi−1 C(N −1) である．また，ユニフォー
ムゲームならば式 (16) より wi−1 D(N − 1) > wi−1 D(N − 2)P∞
P∞ i−1
である．よって， i=k wi−1 D(N −1) >w C(N −1)i=kである．ゆえに，k 回目に X が D をとる場合，V (X|{X} ∪{γ-TFTN −1 }) > V (γ-TFT|{X} ∪ {γ-TFTN −1 }) である．この場合，定義 4 より X は γ-TFT に侵入することができる．
したがって，γ-TFT は CSS ではない．
ところで，0 ≤ w < 1 より k = 1 のとき V (X|{X} ∪{γ-TFTN −1 }) と V (γ-TFT|{X} ∪ {γ-TFTN −1 }) の差が最大になる．よって，γ-TFT に対する最適な X は AllD である．
集団を分割する場合も，TFT に対する議論と同じく，γ-TFT
に対する最適な X は AllD である．
i=k3

The 19th Annual Conference of the Japanese Society for Artificial Intelligence, 2005
さて，集団を分割する場合，AllD が γ-TFT に侵入することができるか考える．(n − 1)/n < γ ≤ 1 のときは，1TFT，すなわち TFT に対する議論と同じである．ここでは，
0 < γ ≤ (n − 1)/n のときについて考える．資源提供ゲームを
割引率 w で繰り返し行う場合，次の定理が成り立つ．

う概念を導入している．この概念のもと，予備的解析として資源提供ゲームにおいて TFT が侵入されることを示した．
TFT に内在する協調が安定となるために有効な社会的制御を設計することは，エージェント社会にとって有意義である．
[小山 03, 小山 04] では，社会的ジレンマゲームを繰り返し行
う場合にプレイヤが集団を移動することの有効性を議論している．これは，集団の外側に協調を求めてゲームの構造を変えているとみなすことができる．一方，本研究では，集団の内側に協調を求めて集団を分割することを考えた．はじめに，資源提供ゲームを繰り返し T 回行う場合，集団を分割するために負ってもよいコストに関する条件を示した．集団を多数に分割
し T を大きくするほど，コストの上限は高くなる．次に，集団を分割するときに対して戦略の侵入という概念を再定義している．これは戦略の累積利得の平均に基づいているが，ゲームは各小集団で行われ，戦略の侵入の評価は集団全体に対してなされる．すなわち，局所的な相互作用の平均的な結果によって大域的な評価基準を定義しているといえる．これは，戦略の侵入という概念が進化に関する議論を背景としていることからも自然であると考える．さて，この再定義された戦略の侵入という概念のもと，T が十分大きいとき TFT が AllD に侵入されないことを示した．ゲームの繰り返しを割引率 w で一般的に表現した場合についても，同様な解析を行った．結果として，
w が十分大きいとき TFT が AllD に侵入されないことを示した．
最後に，戦略の侵入という概念に基づいて N 人ゲームにおける CSS を定義している．また，たいていの社会的ジレ
ンマゲームとしてユニフォームゲームを定義している．なお，[Dawes 80] ではより強い条件でユニフォームゲームを定義しているが本研究では議論の必要に応じて弱い条件で定義している．はじめに，ユニフォームゲームにおいて TFT が CSS ではないことを示した．次に，資源提供ゲームにおいて集団を分割する場合，w が十分大きいとき TFT は CSS であることを証明した．TFT を一般化した γ-TFT に対しても同様な議論を展開したが，結果として，1-TFT，すなわち TFT が CSSであることを証明できた．

定理 2 集団を分割する場合，0 < γ ≤ (n − 1)/n のとき γTFT は CSS ではない．
証明: 資源提供ゲームを割引率 w で繰り返し行う場合，次式のようになる．

V (AllD|{AllD} ∪ {γ-TFTn−1 }, {γ-TFTn }m−1 )
=

1
1−w

µ

f (n − 1)
+b
n

¶

−δ

(18)

また，γ-TFT の累積利得は小集団によって以下のように異なる．

V (γ-TFT|{AllD} ∪ {γ-TFTn−1 }) =V (γ-TFT|{γ-TFTn }) =f (n − 1)−δ(1 − w)nf (n)−δ(1 − w)n

(19)

(20)

式 (19) (20) より，γ-TFT の累積利得の平均は次式のようになる．

V (γ-TFT|{AllD} ∪ {γ-TFTn−1 }, {γ-TFTn }m−1 )=(n − 1)f (n − 1)
m−1+
f (n) − δ(21)(N − 1)n(1 − w)
(N − 1)(1 − w)

γ-TFT が AllD に侵入されないためには，次式が成り立たな
ければならない．
V (AllD|{AllD} ∪ {γ-TFTn−1 }, {γ-TFTn }m−1 )<V (γ-TFT|{AllD} ∪ {γ-TFTn−1 }, {γ-TFTn }m−1 )式 (18) (21) より，次式を満たすとき γ-TFT は AllD に侵入
されない．
N −1
f (n) − f (n − 1) >
b
(22)
m−1

7.

おわりに

本研究では，はじめに，社会的ジレンマゲームにおいて，集団を分割するために負ってもよいコストに関する条件を示した．次に，集団を分割することによって，しっぺ返し戦略が安定となることを明らかにした．

しかし，f (n) − f (n − 1) < nb だから式 (22) は成り立たな
い．よって，AllD は γ-TFT に侵入することができる．ゆえに，集団を分割する場合，γ-TFT は CSS ではない．
（証明終）

参考文献
整理すると，ユニフォームゲームにおいて γ-TFT は CSS
ではないが，資源提供ゲームにおいて集団を分割する場合，式(15) を満たすとき，1-TFT，すなわち TFT は CSS である．

6.

[Axelrod 84] Axelrod, R.: The Evolution of Cooperation,
Basic Books (1984)[Dawes 80] Dawes, R. M.: Social Dilemmas, Annual Review of Psychology, Vol.31, pp.169-193 (1980)

考察[小山 03] 小山 友介, 大浦 宏邦: 所属集団を変更できる社会的ジレンマモデルの計算機実験, シミュレーション＆ゲーミ
ング, Vol.13, No.2, pp.169-178 (2003)

社会的ジレンマにおける協調を考えるために，はじめにその状況をゲームとして形式化している．また，以降の解析のためにそのゲームの例として資源提供ゲームを定義している．
社会的ジレンマゲームでは，協調が実現されるのは困難である．そこで，TFT に内在するような相互利益的な効果が事態を変えうる [Axelrod 84] ことよりゲームを繰り返し行う場
合を考えている．この場合に，TFT に内在する協調が安定となるかを解析するために N 人ゲームにおける戦略の侵入とい[小山 04] 小山 友介, 小林 盾, 藤山 英樹, 針原 素子, 谷口 尚子,
大浦 宏邦: 社会的ジレンマ問題への学際的接近, オペレー
ションズ・リサーチ, Vol.49, No.12, pp.733-740 (2004)

4