1

研究会論文

Technical Report

不均質な環境における拡張協調期待戦略の効率と特性
大塚 知亮
Tomoaki Otsuka

早稲田大学基幹理工学研究科情報理工・情報通信専攻
Department of Computer Science and Communications Engineering, Waseda University

oh-tsuka.21@suou.waseda.jp

菅原 俊治

（同

上）

Toshiharu Sugawara

sugawara@waseda.jp

keywords: 囚人のジレンマ, 複雑ネットワーク, 強化学習, マルチエージェントシステム
Summary
本論文では, 複雑ネットワーク上での繰り返し囚人のジレンマゲームにおいて, 協調をネットワーク上に拡散させる協調期待戦略に裏切りエージェントの判定を追加した, 拡張協調期待戦略を提案する. 協調期待戦略は裏切り行動がナッシュ均衡である囚人のジレンマゲームにおいて, インタラクションによって相互協調が成立した際に, 周囲に協調が拡散したことを期待して, 一定回数連続して協調行動を行う手法である. この手法は相互評価や罰則などの本来のゲームに不要なインタラクションを発生させずに, 比較的簡単なアルゴリズムでネットワーク上に協調行動を拡散させることが可能な手法である. しかし, これまでの研究ではネットワーク上の全てのエージェン
トがこの協調期待戦略をとるエージェントと仮定しており, 単純な強化学習により裏切り行動に収束するエージェ
ントが混在することで協調を維持できずに, 徐々に崩壊することがわかっている. そこで協調期待戦略に比較的簡単なアルゴリズムでインタラクションのみから裏切りエージェントと一時的に判定し, 裏切りエージェントに対して協調期間の協調を行わない拡張協調期待戦略を導入した. 実験から本戦略が頑健であり, 広く協調を拡散できることを示す.

1. は じ め に
近年のテクノロジーの発展により, コンピュータシス

15][Walker 95]. これらの研究では, 利用者間の関係をエー
ジェントのネットワークで, インタラクションにおける利得構造をゲームでそれぞれをモデル化し, その環境下でテムは様々な用途で用いられるようになった. 特に, ス

エージェントが過去のインタラクションを強化学習によっ

マート端末や小型で高性能なコンピュータの普及と各種て最適な戦略を決定するアルゴリズムを提案している. しのサービスサーバとの連携により人間の代理として働く

かし, これらの研究の多くは協調ゲームなどナッシュ均衡

エージェントを様々な電子機器に搭載する技術が注目さが社会全体においても最適解である問題を仮定している

れている. こうしたエージェントはユーザの代理としてものが多い.

情報の収集や共有, ユーザ間での交渉や調整を自動化す

エージェント間においても現実の人間社会と同様に, そることを目的としている. このとき, エージェントはエー

れぞれの利益を優先して行動することでエージェント間

ジェント間のインタラクションにおいて, 各ユーザにとっでの競合が強くなり, 社会全体で利益を下げ合うジレンて適切な動作と行動戦略を取ることが求められる. 従っ

マ的状況が存在する. これは, 例えば, エージェントが個て, 協調・調整・競争などを通じて, 個々の条件を考慮し人や組織の代理として動作することや, エージェント自体つつシステムが構成する社会全体のバランスをとった行の活動が共有するサーバや通信帯域を計算資源とするこ動選択ができるように, エージェントが学習する機能がとに起因する. こうした社会的ジレンマをモデル化した必要となる.

ゲームの 1 つが囚人のジレンマゲームである. 囚人のジこのような状況に対し, マルチエージェントシステム

レンマゲームでは, 「裏切り (D)」行動がナッシュ均衡と(MAS) の分野において, エージェント間の社会的協調
や調整・取引を効率的に実現するために, 社会全体で整なるが, この状況はパレート効率的ではなく, 全員が「協合性のある戦略や行動規範（ノルム）を周囲のエージェ

こうした社会的ジレンマの状況は低価格競争や公共財にントとのインタラクションから学習する手法が提案さ対する行動戦略など様々な現実世界の事象があてはまり,

れている [Shibusawa 14][Sen 10][Yu 13a][Yu 15][Jianye

このゲーム構造において, エージェントが社会全体とし

調 (C)」行動をとることがパレート効率的な戦略である.

2て協調を促進できるメカニズムの解明や実装は非常に重2. 準備と協調期待戦略

要である.

2·1 囚人のジレンマゲーム
そこで我々は大規模なエージェントネットワークにおい

囚人のジレンマゲームは 2 人ゲームで, プレイヤーは 2て, 無期限繰り返しの囚人のジレンマゲームを行い, エー

種類の行動 S = {C(協調), D(裏切り)} を取る. 本研究でジェントがアルゴリズムとして単純な戦略の学習をする

は現実社会での継続的な利用を想定し, エージェントがことで, ネットワーク全体に協調を促進させる協調期待戦

ゲームの試行回数を知らない, 無期限繰り返しの囚人の略を提案してきた [渋澤 15]. ここでは, エージェントがジレンマゲームを行う. また, 囚人のジレンマゲームにお自身のおかれた環境は社会的ジレンマ構造であると推定

ける 2 種類の行動 C, D に対し, 以下の利得行列を定義す

し, 協調行動がパレート効率的であると認識している状

る. 例えば, 2 プレイヤーがそれぞれ C,D の行動を選択

況を想定している. また, エージェントはネットワーク全体の状態（他のエージェントの戦略）を観測できず, 局所C
D

的なエージェントの行動のみを観測可能としている. そこで, エージェントは最近のインタラクションで相互に協調行動が成立した場合に, 周囲で協調行動が拡散していることを期待し, 一定期間 (協調期間と呼ぶ), 協調行動

図1

C
R, R
T, S

D
S, T
P, P

囚人のジレンマゲームの利得行列を試行する. この戦略の下, 我々は協調期間を 3 とすることで, 完全グラフ, Barabasi-Albert モデルによって構築した場合, C を選択したプレイヤーは利得 S を, D を選択

したネットワーク (以降, BA ネットワーク), Connectng

したプレイヤーは利得 T を得る. 囚人のジレンマゲーム

Nearest Neighbor モデルによって構築したネットワーク(以降, CNN ネットワーク) などで協調行動が全体に広がることを示した.

の利得行列では以下の関係が成り立つ. T > R > P > S
かつ 2R > T + S. この条件により相手の行動にかかわらず, ナッシュ均衡は両者の行動が D となる. このとき両プレイヤーは利得 P を得るが, パレート効率的な状況は

一方 [渋澤 15] では, 全てのエージェントが協調期待戦
略を取ることを想定していたため, 協調期待戦略のエー
ジェントとインタラクションの結果を Q 学習する (通常は均衡点 (D, D) を学習) ことで利得を最大化する Q 学習

2 プレイヤーが互いに C を選択した場合である. また, 本
研究ではこれまでの研究 [渋澤 15] と同様に, 囚人のジレ
ンマゲームの利得行列は R = 3, S = 0, T = 5, P = 1 とする.

エージェントを一定数混在させ, 協調期待戦略の頑健性を調査した [大塚 16]. その結果, 協調期間 3 において, 完全グラフでは Q 学習エージェントが約 5%以上混在すると

2·2 ネットワークモデル
本節では本稿の実験で用いるネットワークと, それらがネットワーク全体での協調が維持できず, さらに正規ネッ持つ特徴を説明する.

トワークでは Q 学習エージェントが存在しない状態でも§ 1 完全グラフ

長期間にわたる協調は維持できないことがわかった.
そこで本論文では, この問題の解決方法として, 自分の協調期間において連続して裏切り行動を行うエージェン
トを裏切りエージェントと判定し, 協調期待戦略による強制的な協調を行わず, 裏切りエージェントの戦略変化に対応して協調に切り替える, 拡張協調期待戦略を提案する. 本戦略は単純ながらも裏切り行動中心のエージェン
トとは協調せず, 他方, 提案戦略同士の間では協調を続け,これがネットワーク全体に広がることを実験により示す.
またその拡張期待戦略の特性と限界についても議論する.

完全グラフはネットワーク内の全ノード間にリンクが貼られたネットワークである. n 個の頂点からなる完全グラフのリンク数は n C 2 = n(n − 1)/2 であり, 平均次数は n − 1 である.

§ 2 正規ネットワーク
正規ネットワークは全てのノードが同じ数の隣接エー
ジェントを持つネットワークである. ここでは正規ネット
ワークはノードを円周上に並べ, 各ノードからその両隣 m
個先のノードまでリンクを貼ることで正規ネットワークを構築した. そこで, n 個の頂点からなる正規ネットワー
クのリンク数は nm であり, 平均次数は 2m である.

本書の構成は以下のとおりである. まず, 次節で準備として囚人のジレンマゲームとネットワークモデル, エー

2·3 エージェントの行動決定

ジェントの行動決定手法について説明する. 第 3 節では

本研究では, 以下の状況を想定する. まず, 協調期待戦

拡張協調期待戦略を提案する. 第 4 節では完全グラフと略をとるエージェントは自己の利得行列のみを知る. さ

正規ネットワークを用いて評価実験を行い, 拡張協調期らに, 他のエージェントの利得行列は知らないが, 周囲も待戦略の影響を調査する. 第 5 節では実験結果の考察を同じ行列を持つと仮定し, 自身のおかれた環境が社会的述べ, 第 6 節で結論と今後の課題を述べる.

ジレンマ構造であり, 協調行動がパレート効率的である

3と推定している. そのため周囲とともに協調し合うことが最善だが, 自分だけが協調すると損をする環境であることを知っている. また, どのエージェントもネットワー
ク全体の状態を観測できず, 隣接するエージェントとのインタラクションの結果のみを観測可能とする. このようなゲームで利得を最大化しようと行動するエージェン
トは実験の初期に拡張協調期待戦略によって行動する協調期待戦略エージェントか, 本節で述べる統合法によって行動する Q 学習エージェントかを決定し, 実験中に戦略の変更は行わない. どちらの戦略で行動を決定する場合
も各エージェントはその隣接エージェントごとに, 強化
学習によりこれまでのインタラクションの結果を学習し,

図 2 Q 学習エージェントによる繰り返し囚人のジレンマゲーム

行動を決定する. また, 行動にランダム性を取り入れるた
めにインタラクションごとに ε-greedy による戦略の変更行った結果の協調成立率を図 2 に示す. 協調成立率は 1

も行う.

ラウンドに行われる全インタラクションのうち, エージェ

§ 1 統合法による行動決定
統合法は, エージェント i が各隣接エージェント j に対する行動 sij から自らの行動 si を決定するための手法である. また, エージェント i の隣接エージェントを Niとする. エージェント i はラウンド t において, 以下に示
す優先度 pi (s) の値が最大となる行動 si ∈ S を選択する.
各行動で優先度が同値の場合はランダムに行動 si を選択する.

ント間のインタラクションで両エージェントが協調行動

si (t) = arg max pi (s)

(1)

s∈S

∑

δ(s, sij (t − 1))

定されるため, 相互協調が成り立つ 25%程度のインタラ
クションが協調になり, それを学習したエージェントが協調を維持しようとするが, 初期に裏切りを学習したエー
ジェントによって, ネットワーク全体に裏切りが広がることがわかる.

§ 3 協調期待戦略

協調期間にあるとする. また, 1 実験を通して変動しない
協調期間定数 L を導入する. エージェントは最近のインsij (t − 1) = arg max Qit−1 (s, j)

(3)

s∈S

と定義する. なお, 関数 δ は任意の戦略 s1 , s2 についてδ(s1 , s2 ) =なっている. 初期の段階では最初の行動がランダムに決行期間を表現するパラメータ Li を導入し, Li > 0 の時に

(2)

j∈Ni

{

トワークの両方でネットワーク全体で協調成立率が 0 に

協調期待戦略 [大塚 16] をとるエージェント i に協調試

ここでは優先度 pi (s) を

pi (s) =をとった割合である. 図 2 を見ると完全グラフと正規ネッ

タラクションから互いに協調行動が成立した場合に, 周囲で協調行動が促進されていることを期待して Li = L とし, Li > 0 の期間, 協調行動を試行する. ここで Li は正の整数とする. エージェント i は Li > 0 のとき次の隣接

1 if s1 = s20 otherwise(4)

エージェントのインタラクションで協調行動をとり, Liの値を 1 減少させる. 協調期間であっても, 隣接エージェとなるデルタ関数である. 従って, この場合, 統合法は多ントと相互に協調行動をとった場合には Li = L と再設

数決による決定となる.

定し, 協調期間を延長する. この期間中は ε-greedy によ§ 2 Q 学習エージェント
Q 学習エージェントは隣接するエージェントへの行動
決定に Q 学習のみを用い, 協調期待戦略をとるエージェン

るランダムな行動決定をせず, 協調行動を選択する. 協調

トと同様に統合法による行動決定を行い基本的な行動をジェントへの戦略を決定する.

期待戦略をとるエージェントも協調期間にない場合は Q
学習エージェントと同様に, 統合法に基づいて隣接エー決定する. ラウンド t において, エージェント i は隣接エー
ジェント j に対して行動 s をとる時の Q 値 Qit (s, j) を以

3. 提 案 手 法

下の式に従って更新する. このとき, 前ラウンド (t − 1)iにおけるその戦略での利得を rj,t−1とする.
i
Qit (s, j) = (1 − αi ) · Qit−1 (s, j) + αi · rj,t−1(5)

協調期待戦略では協調期間中に一度でも他のエージェ
ントと相互協調が成立すると協調期間を協調期間定数に再設定し, 本来の Q 学習の結果を学習した統合法によるエージェント数 300 の完全グラフとエージェント数

行動が裏切り行動であっても協調を持続する. そのため,

1000, 平均次数 10 の正規ネットワークにおいて, Q 学習

裏切り行動に収束した Q 学習エージェントが混在するとエージェントのみで, 繰り返し囚人のジレンマゲームを

協調期待戦略エージェントの協調行動の Q 値が下がり, さ4らに協調期間が途切れると協調期待戦略エージェントもとにそれぞれのエージェントごとに学習した Q 値を元に,裏切り行動に収束する. そこで, 本節では裏切りエージェ

統合法によって基本行動を決定する. ここで決定した基ントを判定し, 裏切りエージェントと判定したエージェン

本行動を元にそれぞれのエージェントは隣接エージェン

トに対する行動を変化させる手法を提案する. ここで述トとランダムな順番で 2 人ゲームの囚人のジレンマゲー

べる手法による戦略を拡張協調期待戦略とする.

ム（インタラクション）を 1 回ずつ行う. またその結果に応じた報酬を受け取り, Q 値を逐次更新する. 全てのエー

3·1 裏切りエージェントの判定
拡張協調期待戦略エージェント i は裏切り判定閾値 M ≥0 を導入し, その隣接エージェント j に対して裏切り行動のカウンター dcij を持つ. dcij は実験初期に全て 0 で初期化する. エージェント i が協調期間中 (Li > 0) にのみ
隣接エージェント j に裏切られた場合このカウンターに1 を加算し, dcij ≥ M のときエージェント i はエージェ
ント j を裏切りエージェントと判定する. しかし, エー
ジェント i は協調期間中かどうかによらず, エージェント
j が協調行動を選択した場合に dcij を 0 に初期化する.

ジェントが隣接エージェントと 1 回ずつインタラクションを行うまでを 1 ラウンドとし, 協調成立率の変化を調査する. すべての実験を通して完全グラフにおけるエー
ジェント数は 300, 正規ネットワークにおけるエージェン
ト数は 1000, 正規ネットワークにおける平均次数は 10 とし, Q 学習の学習率 α = 0.1, 裏切りエージェントの判定閾値 M = 2, 学習行動戦略として ε-greedy (ε = 0.05) を採用した. また, [Yu 13b] にならい, 90%以上のエージェ
ントが協調を維持した場合に協調の拡散に成功したと判断する. しかし, Q 学習エージェントは Q 学習の結果のみを元に行動するため, 実験中裏切り行動に収束する. そ3·2 裏切りエージェントへの行動決定
拡張期待戦略エージェント i は裏切りエージェントに対して, 統合法による基本行動の決定に考慮せず, 協調期
間中でも協調を行わないという 2 つの異なる行動を行う.
§ 1 統合法による基本行動の決定に考慮しない
統合法の行動決定のセクションの式 (2) に以下の式に再定義する. エージェント i が裏切りエージェントと判定していない隣接エージェントの集合を jc とし, この jc に対し優先度 pi (s) を以下とする. に対する行動 sij から自らの行動 si を決定するための手法である.
pi (s) =∑のため, 本論文では（拡張）協調期待戦略のエージェント
間でのインタラクションにおいて 90%以上で協調が成立した場合に協調の拡散に成功したとする. 以下の実験結
果は全て 30 回の試行に基づく平均である.

4·2 評 価 実 験
拡張協調期待戦略との比較として, 協調期待戦略のエー
ジェントネットワークに Q 学習エージェントを混在させ, 協調期待戦略の頑健性を調査する. この結果, 完全グ
ラフにおいては協調期間が 3 のとき, 10%以上の Q 学習
エージェントが混在すると協調を促進できないことがわδ(s, sijc (t − 1))

(6)

j∈Ni

§ 2 協調期間中であっても強制的な協調を行わない
エージェント i が裏切りエージェントと判定した (dcij >0) エージェント j に対してはインタラクションの際にエー
ジェント i が協調期間中であるかによらず, エージェント
i は統合法による基本行動でエージェント j とインタラクションを行う. そのため, このインタラクションによってエージェント i の協調施行期間 Li は減少させない. 一
方インタラクションによって協調が成立した場合は協調試行期間の再設定は行う.

かった. ここでは分かりやすさのため, 完全グラフ上で Q
学習エージェントを 20%混在させた場合の協調期待戦略
エージェント間の協調成立率を図 3 に示す. L = 3 の場
合, 1300 ラウンドあたりから協調成立率が一定になっているが, より長く実験を続けると段階的に協調成立率は下がることを確認している.
次に正規ネットワークにおいて協調期待戦略エージェ
ントのみで実験を行った結果を図 4 に示す. 図 4 からもわかるように, L = 3 でも協調成立率が徐々に下がり, さらに長いラウンド数実験を続けると協調成立率は 0 になる. このことから, 協調期待戦略では正規ネットワークにおいては Q 学習エージェントが混在しない状況であって

4. 実

験

も L = 3 では協調を促進できないことがわかる. これらの結果は [大塚 16] の結果と一致する.

4·1 実 験 内 容
協調期待戦略及び拡張協調期待戦略を取るエージェン

4·3 完 全 グ ラ フトのネットワークに一定比率で Q 学習エージェントを混完全グラフにおいて拡張協調期待戦略の Q 学習エー

在させることで, ネットワーク上での囚人のジレンマゲー

ジェントに対する限界を調査する. エージェント数を 300

ムを通して協調をどの程度拡散させ, 維持できるかを調査とし, 協調期間定数 L = 3 において, Q 学習エージェント

する. 各エージェントはあらかじめ協調期待戦略によりの割合を 50%から 90%に変化させたときの拡張協調期待

行動するか, 合理的に行動するかを決定し, 戦略は変更し

戦略エージェント間の協調成立率を図 5 に, このときのないものとする. 各エージェントはそれぞれのゲームご

全エージェント間での協調成立率を図 6 に示す. また表5

図320%の Q 学習エージェントを含む完全グラフ上における協調
期待戦略エージェント間での協調成立率

図5

L = 3 における完全グラフ上における拡張協調期待戦略エージェント間での協調成立率

一方, 図 6 を見ると拡張協調期待戦略エージェントが高い協調成立率を維持している場合であっても Q 学習エー
ジェントが裏切りに収束しているため, ネットワーク全体では協調が促進されていないことがわかる. 例えば Q
学習エージェントの割合が 50%であっても, Q 学習エー
ジェントが関わるインタラクションは 75%程度ある.
表 1 から協調の維持に成功した Q 学習エージェントがジェント間で協調が維持されることがわかった. Q 学習

60%以下では Q 学習エージェントの判定率も 90%以上の高い判定率となった. Q 学習エージェントは 5%の確率でε-greedy によるランダムな行動選択をしており, 裏切り
エージェントの判定閾値が 2 のため, 95%の判定率は全ての Q 学習エージェントを同定している.
次に協調期間定数 L = 2 において, Q 学習エージェン
トの割合を 10%から 40%に変化させた場合の拡張協調期
待戦略エージェント間の協調成立率を図 7 に示す. この
結果 L = 2 では Q 学習エージェントが 10%でも協調を促進できないことがわかる. 図 7 を見ると L = 2 では図
5 の L = 3 の初期に見られた協調成立の急激な上昇がな
いため, 裏切りエージェントの割合よりも協調期間定数
L 及び初期の Q 学習の初期値の設定に依存すると考えられる. 協調期間定数の値によらず, 拡張協調期待戦略エージェント間での協調成立率は 30%程度で安定しているが,エージェントの割合が 70%のときであっても 80%程度の本稿の実験からはこの理由を推測できる結果は得られな

協調成立率を維持しているが, ラウンド数を伸ばすと, 緩かった.

図 4 協調期待戦略エージェントのみの正規ネットワーク上における協調成立率1 に協調期間定数 L = 3 のとき, 5000 ラウンド時点で, Q
学習エージェントを裏切りエージェントと判定した割合
及び拡張協調期待戦略エージェントを裏切りエージェン
トと誤判定していた割合を示す.
協調期間定数 L = 3 の拡張協調期待戦略では Q 学習
エージェントの割合が 10%のときはもとより, 60%存在
しても協調成立率は 90%であり, 拡張協調期待戦略エー

やかに協調成立率は落ちる. また, Q 学習エージェントが90%混在するときでも初期 100 ラウンド程度では拡張協調期待戦略エージェント間では協調成立率がほぼ 100%に達し, その後 Q 学習エージェントの割合によって協調成立率が変動している. これは実験の初期の状態ではエー
ジェントの Q 値が初期値 (0) で, 協調か裏切りがランダムの確率で選択されることに起因している. しかし, 図 6
からもわかるように Q 学習エージェントの大半が裏切り行動に収束しており, さらに 150 ラウンド程度でほぼ全ての Q 学習エージェントが裏切り行動に収束する. その結果, 拡張協調期待戦略エージェントの協調期間が途切
れ, 協調の Q 値が低いと裏切りに収束したと考えられる.

4·4 正規ネットワーク
エージェント数 1000 の正規ネットワークにおける拡張
協調期待戦略の Q 学習エージェントに対する限界を調査する. 正規ネットワークでは円周上に並べたエージェント
それぞれで m 個隣のエージェントまでリンクを貼ることでネットワークを作るが, ここでは m = 5 とし, それぞれの隣接するエージェント数, つまり平均次数は 2m = 10である. まず, 図 8 に拡張協調期待戦略エージェントのみで, 協調期間定数 L を 2 と 3 に設定した場合の協調成立率を示す. この結果, 拡張協調期待戦略によって協調期待
戦略で協調の収束に失敗した L = 3 さらに L = 2 におい6
表1

完全グラフにおける裏切りエージェントの判定率 (L = 3)

ネットワーク中の Q 学習エージェントの割合

Q 学習エージェントの判定率
拡張協調期待戦略エージェント間の誤判定率

10%
95.0
0

図6

L = 3 における完全グラフ上における全エージェント間での
協調成立率

図7

L = 2 における完全グラフ上における全エージェント間での
協調成立率

20%
95.1
0

30%
95.1
0

40%
95.1
0

50%
95.0
0

60%
91.0
3.43

70%
88.2
4.64

80%
65.6
16.5

90%
2.38
1.29

図8

拡張協調期待戦略エージェントのみの正規ネットワーク上における協調成立率

図9

正規ネットワーク上における拡張協調期待戦略エージェント間の協調成立率ても協調の収束に成功した. これは, これまでの協調期待戦略と比較して, 大きく異る結果となった. この要因として, Q 学習エージェントが混在しない状況であっても裏切
りエージェントの判定を行うことで, 初期にランダムで
裏切り行動をとる半数程度のエージェントを裏切りエー
ジェントとすることで, 協調期待戦略による協調が広がるまでの間, 一時的に裏切り行動を学習しているエージェ
ントに協調期間を消費しなくなったためと考えられる.
次に, 協調期間定数 L = 3 において, Q 学習エージェン
トの割合を 30%から 60%に変化させた場合の拡張協調期
待戦略エージェント間の協調成立率を図 9 に, 表 2 に協上となったが, ラウンド数を増やして行くと徐々に協調成
立率が下がり収束に失敗した. 表 2 から, 協調の収束に成功した Q 学習エージェントの割合が 40%以下では, Q 学
習エージェントの判定率が 90%以上となった. また, Q 学
習エージェントの割合が 10%程度であっても拡張協調期
待戦略エージェント間の誤判定が発生した. これは平均次数が 10 である正規ネットワーク上において局所的な裏切りの輪が発生し, その輪に含まれる拡張協調期待戦
略エージェントが裏切りに収束したためである.

調期間定数 L = 3 のとき, 5000 ラウンド時点で, Q 学習

次に, 協調期間定数 L = 2 において, Q 学習エージェン

エージェントを裏切りエージェントと判定した割合及びトの割合を 10%から 50%に変化させた場合の拡張協調期

拡張協調期待戦略エージェントを裏切りエージェントと待戦略エージェント間の協調成立率を図 10 に示す. 協調

誤判定していた割合を示す. 協調期間定数 L = 3 では Q

期間定数 L = 2 では Q 学習エージェントが 10%以下で学習エージェントが 40%程度混在しても協調が維持されは協調の収束に成功し, 20%程度においても協調成立率が90%には及ばないが僅かな増加傾向にある状態となった.

た. 50%でも 5000 ラウンド目では協調成立率は 90%以7
表2

正規ネットワークにおける裏切りエージェントの判定率 (L = 3)

ネットワーク中の Q 学習エージェントの割合

Q 学習エージェントの判定率
拡張協調期待戦略エージェント間の誤判定率

10%
95.3
0.003

20%
95.1
0.02

30%
94.2
0.16

40%
91.5
0.50

50%
84.4
1.66

60%
71.8
3.25

70%
54.8
4.79

80%
34.4
5.47

90%
14.4
3.34

正規ネットではインタラクションの順序はランダムだが,ネットワーク上に Q 学習エージェントもしくは拡張協調
期待戦略エージェントが偏って存在することで, 協調, 裏切りの広がり方が局所的に緩やかになる. その為, 正規
ネットワークではランダムな順序でインタラクションが行われるときに L = 2 でも拡張協調期待戦略による協調がある程度維持でき, Q 学習エージェントが 10%程度混在してもそれが保てる. これは局所的な協調への収束があれば, そこに徐々に協調が広がり, 一時的に裏切りを選択していた拡張協調期待戦略エージェントも協調の輪に
図 10 L = 2 における正規ネットワーク上における拡張協調期待
戦略エージェント間での協調成立率

含まれるようになる. これは社会的ジレンマ構造を背後に持つマルチエージェントシステムを構築するときに重要な要素である.

5. 考

察

以上の実験結果から裏切りが適切と学習する Q 学習
エージェントを導入しても, 拡張協調期待戦略はそれを同定し, 拡張協調期待戦略をもつエージェント同士での協調が広がることがわかった. つぎに実験の結果から, 完
全グラフと正規ネットワークの違い及び今日長期間の違いによる拡張協調期待戦略の特徴および裏切りエージェ
ントの判定閾値について考察する.
図 5, 図 9 から, 協調期間定数 L = 3 のとき, 完全グラ
フではの Q 学習エージェントの割合が 60%でも協調を維持できたが, 正規ネットワークでは 40%となった. 一方
図 7, 図 10 から, L = 2 のときでは, 完全グラフでは Q 学
習エージェントの割合によらず協調成立率を維持できなかったが, 正規ネットワークでは Q 学習エージェントが10%程度混在しても協調が維持された. この違いは完全グラフと正規ネットの局所性の差, とインタラクションの順序をランダムに決定していることに起因すると考えられる. 本実験では実験の最初では, ランダムに行動を決定している. そのため, 任意の 2 エージェントで協調が成立する確率は 4 分の 1 であり協調期待戦略では, 協調の広がりが遅くなるが, 拡張協調期待戦略では裏切りエージェ
ントの判定によりそれらを区別でき, 図 5 や図 6 で顕著なように初期段階での拡張協調期待戦略間での高い協調成立が実現されている. さらに, 裏切りエージェントと一時的に判定されても戦略の寛容性から相互協調に入ることが出来る. しかし, Q 学習エージェントが裏切りに収束するため, これにより拡張協調期待戦略間での協調期間
中の協調行動が途切れるかどうかが, 協調を維持できるかの境界となる.
完全グラフでは, 全てのエージェントがランダムに相手を決めるため, 一定の間隔で協調が成立する. 一方で,また, 表 1, 表 2 から拡張協調期待戦略中での裏切りに収束するエージェントが増えるに従って誤判定も増加す
る. 裏切りエージェントを 90%以上判定できているときに収束に成功しているようにも読み取れるが, これは裏切りエージェントの判定方法が, 自身が協調期間中に裏切り行動を 2 回連続して取られたときとしているため, 周
囲に Q 学習エージェントが多数いると拡張協調期待戦略
エージェントも協調期間から出て裏切り行動を取ることがあり, これが誤判定に繋がったと考えられる.
本実験では裏切り判定閾値を M = 2 として実験をした. 本論文では示さなかったが, 裏切り判定閾値を変動させる実験も行い, M = 1 で一部の環境では M = 2 よりも協調性効率を高めることが出来たが, 同時に拡張協調期
待戦略エージェント間での裏切り判定率を高めてしまい,

M ≥ 3 では殆どの場合で M = 2 より協調成立率が下がる結果であった.

6. 結論と今後の課題
本論文では, 協調期待戦略に裏切りに収束したエージェ
ントを同定し, 協調期間による協調を行わない拡張協調
期待戦略を提案し裏切り行動に収束する Q 学習エージェ
ントが混在する環境においても拡張協調期待戦略に比べ高い確率で協調を拡散できることを示した. 一方で, 今回の実験では完全グラフ, 正規ネットしか考慮しておらず,
より現実に近い, Watts-Strogatz(WS) モデルや Barabasi-

Arbert(BA) モデルのネットワーク上での調査や拡張協調
期待戦略によるネットワーク全体での利得への影響の調査が考えられる.

8♢ 参 考 文 献 ♢[Jianye 15] Jianye, H., Sun, J., Huang, D., Cai, Y., and Yu, C.: Heuristic Collective Learning for Efficient and Robust Emergence of Social Norms, in Proceedings of the 2015 International Conference
on Autonomous Agents and Multiagent Systems, AAMAS ’15, pp.
1647–1648, Richland, SC (2015), International Foundation for Autonomous Agents and Multiagent Systems[Sen 10] Sen, O. and Sen, S.: Effects of Social Network Topology and
Options on Norm Emergence, Vol. 67, No. 5, p. 056194 (2010)[Shibusawa 14] Shibusawa, R. and Sugawara, T.: Norm Emergence
via Influential Weight Propagation in Complex Networks, in 2014
European Network Intelligence Conference, ENIC 2014, pp. 30–37(IEEE Xplane, 2014)[Walker 95] Walker, A. and Wooldridge, M.: Understanding theEmergence of Conventions in Multi-Agent Systems, in Proceedingsof the First International Conference on Multiagent Systems, pp.
384–389, The MIT Press (1995)[Yu 13a] Yu, C., Zhang, M., Ren, F., and Luo, X.: Emergence of Social Norms Through Collective Learning in Networked Agent Societies, AAMAS ’13, pp. 475–482 (2013)[Yu 13b] Yu, C., Zhang, M., Ren, F., and Luo, X.: Emergence of Social Norms Through Collective Learning in Networked Agent Societies, in Proceedings of the 2013 International Conference on Autonomous Agents and Multi-agent Systems, AAMAS ’13, pp. 475–
482, Richland, SC (2013), International Foundation for Autonomous
Agents and Multiagent Systems[Yu 15] Yu, C., Lv, H., Bao, H., and Li, Y.: Emergence of Social
Norms through Collective Learning and Information Diffusion inComplex Relationship Networks, International Joint Agents Workshop and Symposium(IJAWS2015) (2015)[渋澤 15] 渋澤 亮介, 菅原 俊治：複雑ネットワーク上での囚人のジレンマゲームにおける協調の促進について, Joint Agent Workshops& Symposium (2015)[大塚 16] 大塚 知亮, 菅原 俊治：協調期待戦略による協調促進の
頑健性について, Joint Agent Workshops & Symposium (2016)