LewenbergのBitcoinマイニングプールにおける協力ゲーム理論分析論文を読んでみる5

本稿について

Bitcoinマイニングプールのインセンティブ設計について協力ゲーム理論の観点から分析したLewenbergらの論文を見ていきます。本稿では「2. Preliminaries」の「Cooperative Games with Coalition Structure」を見ます。

原文はこちらになります。

スポンサードサーチ

今回のまとめ

• 今回の範囲は本論文にて分析のベースとなる「提携構造の協力ゲーム理論」のモデルについて述べたものであるが、数式を用いてシンプルに記載されており、どちらかと言えばまとめるよりも補足する方が必要だと思われるので下記文中にて補足を行う。必要に応じて「筆者補足」部分を参照されたい。

※以下、今回まとめた範囲の論文和訳になりますので詳細をご覧になりたい方は読み進めてください。

2. 準備（続き）

提携構造の協力ゲーム（Cooperative Games with Coalition Structures）

多くの領域で「いくつかの（several）」チームが連なって提携構造を成す場合がある。「提携構造（Coalition Structures）」の協力ゲームは人工知能研究でエージェントの協働とチームの形成をモデル化するために用いられている[21, 39, 40, 42]。提携構造はエージェントの集合Iをチームというばらばらな集合に分割する。つまり、S = {C₁, ..., C_m}は、∪^m_i=1C_i = Iかつ全てのi ≠ jについてC_i∩C_j = ∅を必要十分条件としてIに対する提携構造である。Iに対して取りうる全ての提携構造の集合をCS(I)と表す。いくつかの設定では、提携の値は他の提携構造に依存する。提携構造のある協力ゲームは「分割関数（partition function）」[33]により定義される。分割関数はインプットとして提携構造S ∈ CS(I)と提携C ∈ Sをとり、値v(S, C) = v_S(C)をアウトプットする。つまり、Sにより与えられる他エージェントの分割の下における提携Cの利得を決定する。譲渡可能な利得のある提携形ゲームと同様に、エージェントはその提携構造内で各チームの利得を分割する必要がある。Sと関連する配分は、全てのi ∈ Iについてx_i ≥ 0、かつ、全てのC ∈ Sについてx(C) = v_S(C)であることを満たすベクトルx ∈ R^|I|である。全てのC ⊂ Iについてx(C) ≥ v_Sc(C)（ここで、S_C = {C} ∪ {{D＼C} : D ∈ S, D＼C ≠ ∅}である）であるならば、Sと関連する配分はSの「CSコア（CS-core）」の配分である。直観的に、チームを脱退して新たなチームを作ることで利得を得ることのできるエージェントの部分集合が存在しないならば、配分はSのCSコアの配分である。

筆者補足：

• 前項と関連しますので、まだお読みでない方はまずLewenbergのプール分析論文を読んでみる4をお読みください。
• 提携構造を持つ協力ゲームは必ずしも全員が協力することを前提としない協力ゲームです。特に、ある提携の組み方次第で別の提携の利得に影響が出るようなモデルは分割関数型のゲームといいます。
• 「S = {C₁, ..., C_m}は、∪^m_i=1C_i = Iかつ全てのi ≠ jについてC_i∩C_j = ∅を必要十分条件としてIに対する提携構造」というのは提携構造の定義ですが、簡単に言ってしまえばある集団の中からグループに入っていない人がいないように、かつ、2つ以上のグループに所属する人がいないようにグループを作るような操作といえます。
  • 簡単な例を考えてみましょう。A~Eさんの5人がいるとします。例えば（Aさん、Bさん）と（Cさん、Dさん、Eさん）のグループ分け、あるいは（Aさん）と（Bさん、Cさん）と（Dさん、Eさん）などといったグループ分けはOKです。しかし、（Aさん、Bさん、Cさん）と（Aさん、Dさん、Eさん）といった分け方はNGです。これはAさんが重複しているのでC_i∩C_j = ∅（重複する人がいてはダメに反します。また（Bさん、Cさん）と（Dさん、Eさん）という分け方もNGです。これはAさんが抜けているので∪^m_i=1C_i = I（グループに入っていない人がいてはダメ）に反します。
• 「Iに対して取りうる全ての提携構造の集合をCS(I)と表す」というのは上記の例で言えば（Aさん、Bさん）と（Cさん、Dさん、Eさん）のグループ分け、あるいは（Aさん）と（Bさん、Cさん）と（Dさん、Eさん）のグループ分けなど、条件に反しない分け方を全て網羅したものになります。
• さて、このように様々な提携の仕方が存在する中で、どんな提携構造をもってしても誰も得することができない...そのような全員協力による利得の分配の方法があるとすると（もっとざっくり言うと全員がwin-winな）、そういった分配の方法を集めたものがいわゆる「コア」となります。本論文では「CSコア」と表現されているものです。そういった分配方法の一つ一つが「CSコアの配分」です。「全てのC ⊂ Iについてx(C) ≥ v_Sc(C)（ここで、S_C = {C} ∪ {{D＼C} : D ∈ S, D＼C ≠ ∅}である）であるならば、Sと関連する配分はSの「CSコア（CS-core）」の配分である」という数式はちょうどこれを数学的に表現したものです。

（Lewenbergのプール分析論文を読んでみる4　←←　前）｜（次　→→　Lewenbergのプール分析論文を読んでみる6）

免責

邦訳には誤りがある場合がございます。予めご承知おき下さい。

確実な情報を知るためには冒頭に示した原文をご参照くださいますようお願いいたします。