ゲーム理論に基づいた複雑ネットワーク形成のモデル化

https://gyazo.com/5943bf0ff4d154b34ca864289344fe71

---.icon

1　はじめに

情報通信学や社会学，生物学など多様な分野において，要素とその要素間の関係で構成されるネットワーク（以下，NW）の構造（トポロジ）が複雑 NW と呼ばれる特性を持っていることが明らかになってきている．複雑 NW は，スケールフリー性やスモールワールド性といった特徴を持つ NW である．

複雑 NW の中には，高度に自律的な判断能力を持った多数の主体によって自己組織的に構築されたものが多数ある．近年隆盛の Facebook や Instagram などに代表される SNS における友人間 NW のトポロジも，そのような NW の一つと見られている．

多数の主体が「どのように」振る舞えば複雑 NW が形成されるかを明らかにしたモデルは多くある一方で，多数の主体が「なぜ」複雑 NW を形成するのかを十分に明らかにしたモデルは，筆者らの知る限り多くない．

この問いを解決するための有望なアプローチとして，ゲーム理論の分野における NW 形成ゲームがある．

NW 形成ゲームは，このゲーム理論の枠組みを用いて，利己的な多主体によるゲーム的な状況下で構築されるトポロジを明らかにする取り組みの中で提案されたものである．ゲーム理論に基づいて複雑 NW 形成をモデル化することは，多数の主体が「なぜ」自己組織的に複雑 NW を形成するのかという問いを，NW を構成する主体の個人合理性に落とし込むことで明らかにすることを意味している．このような立場からは将来的に，個人合理性を考慮した NW を設計するための手法の確立に繋がり，それは強力で現実的に実行可能な手法となることが期待される．

---.icon

2　ネットワーク形成ゲーム

2.1　静学的モデル

静学的 NW 形成ゲームは以下のように定式化される．

$ u_i(g(\bold{s})) = \sum_{j \neq i}\delta^{d_{ij}} - \sum_{j \in \{j \mid ij \in g(\bold{s})\}} c_{ij} ~~~~~ (1)

静学的 NW 形成ゲームにおける安定性については，通常の戦略形ゲームにおけるナッシュ均衡に代わって，以下のよって定義される「対安定（pairwise stability）」の概念が提案されている．

$ \Delta u_i^g(ij) =

$ u_i(g - ij) - u_i(g), ~~~~~ \mathrm{if} ~~~ ij \in g

$ u_i(g + ij) - u_i(g), ~~~~~ \mathrm{if} ~~~ ij \notin g

$ (2)

かつ

が成り立つことを言う．この対安定性は，既に存在するリンクに対しては，両端のノードのどちらもそのリンクを切断するインセンティブ（誘因）がないこと（式 (3)），またリンクが存在しないノードペアに対しては，少なくとも一方のノードにはリンクを形成するインセンティブがないことを表している（式 (4)）．

可能なリンク変動とは，両端のプレイヤーの少なくとも一方の利得を増加させる（または一方の利得を増加させ，もう一方の利得を変化させない）ようなリンク追加のことをいう．あるトポロジが対安定であることは，全てのノードペアの間に可能なリンク変動が一つも存在しないことであると言い換えることができる

以下の 2 点について注意が必要である．一つは，ナッシュ均衡が戦略の変更に関する均衡概念であったのに対して，対安定性はリンクの有無の変更に関する安定性の概念であるという点．もう一つは，プレイヤーの戦略に確率的な混合戦略を許せば，必ずナッシュ均衡が存在することが保証されているのに対し，対安定解は存在しない場合があるという点である．

https://gyazo.com/0470284118ab7ee244df60bf11cc88d6

この結果は，対安定解と効率解がどのような NW トポロジを取るかを，リンクコストと減衰パラメータの大きさの関係に関する各ケースについて解析的に示したもので，重要な結果である．一方で，この結果はリンクコストが全て等しい場合に限定したものであることに注意が必要である．そのため，定理に現れる NW トポロジも，対称かそれに近いものになっている．言うまでもなく，現実の NW では各ノードの間のリンクコストが等しくなるという保証はないであろう．

島モデルにおける対安定なトポロジの一例を図 2 に示す．

https://gyazo.com/937f6ab20531d34c040e6e083ae85787

この結果により，切り捨てありの連結モデルにおいては，リンクコストに関する少しのバリエーションを許すことによって，あるパラメータセットにおいて短い平均最短経路長と高いクラスタリング係数をもつスモールワールド NW が対安定なトポロジとして現れることが示された．これは，現実の様々な場面で現れる複雑 NW の形成の仕組みが，NW 形成ゲームの枠組みで表現される可能性があることを示唆したものである．

では，大規模なノード数を持ち，不均一な分布を持つコストパラメータに対して，このモデルで予測される帰結はどういったものになるだろうか？現実に観測される，スケールフリー性やスモールワールド性を備えた NW は，このモデルから生成されるのだろうか？この問いに答えるには，静学的 NW 形成ゲームの枠組みでは十分ではない．具体的には，以下の 3 つの問題点が挙げられる．

1.　対安定解の探索が困難

2.　ゲームのプレイヤーに過大な能力を仮定している

3.　対安定解同士の比較ができない

2.2　動学的モデル

動学的 NW 形成ゲームモデルの基本的なアイデアは，以下の通りである．

・各離散時間で静学的 NW 形成ゲームを実施し，各ノードの戦略を決定する．

$ ij \in \mathrm{argmax}_{ij \in L_{PLC}}(\max{\{\Delta u_i^g(ij), \Delta u_j^g(ij)\}})

を満たす．このようなリンクが複数存在する場合は，何らかの決定論的な方法（ノード ID が若い方を優先する，など）によって決定する．

・各プレイヤー（＝ ノード）は，各時刻においてリンクが 1 本しか変動しないことを知っており，また近視眼的に戦略を決定するものとする．すなわち，次時刻の自身の利得のみを考え，最終的な NW トポロジにおける利得が最適かどうかを考えない．

任意の初期状態が最終的に到達する状態は，対安定解と周期解の 2 種類に分かれる．状態空間のサイズは有限であり，周期の長さも有限となるため，無限の周期長を持つカオス解は存在しない．

---.icon

3　計算機シミュレーション

3.1　シミュレーション実行

3.2　結果と考察

https://gyazo.com/1d84db7ec5d4020d3d136733bf4abcd8

(a) の次数分布から分かるように，スケールフリー性の特徴であるベキ分布よりも，ランダムグラフの次数分布の特徴であるポアソン分布に近い．ここでは C = 140 の例のみを示しているが，C の値を変化させてみても，この傾向は変わらなかった．この原因として，(c) の最大次数の値 (11.86) に示されているように，大きな規模のハブが形成されにくくなっていることが挙げられる．

本モデルでは，リンクの形成に際して両端のノードの合意が必要であった．つまり，双方にとって利得をもたらすような潜在リンクに対してのみ，実際のリンク形成が成立する．他のノードから見ると，ハブが成長するにつれて，ハブノードにリンクを張るメリットはどんどん増加していく一方で，ハブノードにとっては，次数の少ないノードにわざわざリンクを張るメリットは変わらないために，リンク形成の合意が成立せず，結果としてハブノードの次数は極端に大きくならない．これが，動学的 NW 形成ゲームモデルの基本モデルにおいて，巨大なハブが形成されない理由である．

トランスファーとは，ゲームのプレイヤー間で行われる財の交換のことである．財のトランスファーの導入によって，取引に参加する全てのプレイヤーの利得を増加させるような合意を取り付けることができるようになる場合がある．本モデルにおけるトランスファーとは，リンクの変化に際し，利得を増加させるプレイヤーから利得を減少させるプレイヤーにその減少分を補填させることとする．この仕組みを導入することによって，他のノードがハブとのリンクを形成することによって十分な（ハブに対する補填分を差し引いてもまだ利得の増加をもたらすような）場合，ハブに対してその利得の減少を補填することができ，結果として新たな（特にハブに関係する）リンク形成を促進させることができる．

---.icon

4　ダイナミクス解析

4.1　動学的 NW 形成ゲームモデルのダイナミクスの特徴

https://gyazo.com/cbbf62fd32e38f87efabe5c9b7d862c8

それぞれの解は，最終的にその解へ到達する状態の集合を持ち，それを引き込み領域と呼ぶ．状態空間全体は，各解に対応する引き込み領域に分割される．

4.2　ダイナミクス解析の応用：解の非効率性の評価

$ (\mathrm{PoA}) = \frac{f(\hat{s})}{\displaystyle \min_i{f(s_i)}} ~~~~~ (7)

$ (\mathrm{PoS}) = \frac{f(\hat{s})}{\displaystyle \max_i{f(s_i)}} ~~~~~ (8)

定義から明らかなように，PoA も PoS も 1 以上の値を取る．PoA が 1 であることは，システムが必ず効率解をもたらすことを表し，PoS が 1 であることは，システムがもたらす解のいずれかが効率解となることを表す．

PoA も PoS も，システムがもたらす解が最適効率解に対してどれくらい非効率であるかの評価を，多数の解の中の最悪値・最良値を使って評価するものであった．システムとしての非効率性を評価するためには，このやり方はやや極端なものであり，「平均的な」あるいは「典型的な」非効率性を測りたい場合もあるが，これは一般には難しい．なぜなら，非協力ゲームにおける代表的な解概念であるナッシュ均衡解は一般に複数存在し，またそれらの間は無差別的で，解が多数あった場合にそれらの解の間に優劣を付けることができない．そのために「起こりやすい」ナッシュ均衡であるとか，「典型的な」ナッシュ均衡を見いだすことは難しい．ゲームのプレイヤーの分散的・利己的な振る舞いがもたらすシステムの社会的非効率性を評価するための方法として，多数の解の中の最悪値と最良値を用いたものが使われてきたのはそのためであり，これは解概念の本質的な特性に起因するものである．

$ (期待~\mathrm{PoA}) = \frac{f(\hat{s})}{\displaystyle \sum_i \frac{|A_i|}{|S|}f(s_i)} ~~~~~ (9)

https://gyazo.com/8ea88524778ed47d2c8f29ae9c9a4377

---.icon

5　今後に向けて

既に述べたように，ゲーム理論に基づいたモデル化が有望な技術的・社会的 NW は多く存在する．例えば，インターネットにおける AS（Autonomous-System）間 NW や，ファイル交換のための非構造型 P2P（Peer to Peer）NW，あるいは Facebook の友人間 NW などである．これらの NW のトポロジと動学的 NW 形成ゲームモデルがもたらす NW トポロジの詳細な特性の比較を行い，モデルがどの程度現象を表現できているのかを明らかにし，必要であればモデルの精緻化を行っていくことも必要であろう．それは単に利得関数を適切に設定するだけかもしれないし，もっとモデルの根幹の部分を変えていく必要があるかもしれない．

モデルの精緻化に関する一つの例として，プレイヤーの限定合理性（bounded rationality）および非合理性（irrationality）のモデル化というアプローチが挙げられる．本稿で取り扱ったプレイヤーは，全て完全合理的であることを仮定している．すなわち，現在の状況は全て観測可能であるし，取得した状況の下で自身にとって最適な戦略をいつでも選び取ることができる．この仮定は不自然で，現実に意思決定をするプレイヤーは通常，観測能力にも最適化能力にも限界がある（限定合理性）．

ゲーム理論では，メカニズムデザインと呼ばれる研究分野がある．これは，ゲームの結果を社会的に望ましいものに制御するための方法論であり，既にオークションの設計などで成果を挙げている．近年では，計算科学者とゲーム理論学者らの尽力によって，多人数ゲームにおけるプレイヤーの限定合理性や情報の非対称性を扱った計算論的メカニズムデザインという分野も勃興しつつある．これらの成果を動学的 NW 形成ゲームモデルによる NW 形成の問題に援用することによって，将来的に NW トポロジを最適化するための方法論が確立されることが期待できる．

図 4 の例を使って「望ましい」NW トポロジ形成を促す 2 つのアプローチを紹介する．

https://gyazo.com/4da3e3cb5da33e40177a6f4b2a3787e4

---.icon

6　終わりに

ゲーム論的 NW 形成の研究には大きな魅力がある．本稿で述べてきたように，ゲーム論的 NW 形成の枠組みは，多主体によって構成される NW 形成の仕組みを，NW 構成に参加する主体の個人合理性に基づいて明らかにしようとする取り組みである．このような立場からの研究は，残念ながら未だ大きな注目を集めてはいないものの，特に多主体による NW 形成を望ましい方向へ制御しようとしたときには，このような視点からの研究は本質的で，避けて通れないものとなろう．