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

本稿について

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

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

スポンサードサーチ

今回のまとめ

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

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

2. 準備（続き）

D安定性（D-Stability）（※Dは裏切り関数のこと）

チームを脱退して新たなチームを作ることで利得を得ることのできるエージェントの部分集合が存在しないという条件が必須であることは非常に強い要求である。いくつかの状況では全てのエージェントの部分集合が協力して新しいチームを作れるわけではない。これに対応するため、「裏切り関数（defection function）」[2]を定義する。裏切り関数は、提携の集合であるCS(I)の各提携構造と関連する関数D：CS(I) → 2^Iである。直観的に提携構造Sと提携C ∈ Iについて、CのエージェントはC ∈ D(S)である場合に限りSを脱退できる。全てのC ∈ D(S)についてx(C) ≥ v_Sc(C)であるならば、Sと関連する配分は「D安定（D-stable）」である。さらに、Sと関連する全てのD安定な配分の集合としてSの「D-CSコア（D-CS-core）」を定義する。

本論文では、1つの提携が別の提携の部分集合と「結合する（merge）」のを可能にしたり、提携の部分集合がその提携を「分離（split）する」のを可能にしたりする裏切り関数D_MSに焦点を当てる。

ある提携構造S ∈ CS(I)について、D_MS(S) := D_M(S) ∪ D_S(S)を定義する。ここで、D_M(S)はある提携と（恐らく自明な）別の部分集合とがとりうる全ての結合の集合であり、D_S(S)はある提携を（恐らく自明な）2つの部分集合に分ける取りうる全ての分離の集合である。形式的には、D_M(S) := {C|D₁ ⊂ C ⊂ D₁ ∪ D₂, D₁, D₂ ∈ S}、D_S(S) := {C|C ⊂ D, D ∈ S}で定義する。

筆者補足：

• 前項と関連しますので、まだお読みでない方はまずLewenbergのプール分析論文を読んでみる4、Lewenbergのプール分析論文を読んでみる5をお読みください。
• ここまで協力することを前提として提携の利得を見てきたが、必ずしもすべてのエージェントが協力して提携を維持できるわけではない、という現実的な条件を加味しているのが本項。従ってここでは提携を構成しているエージェント（やその部分集合）が提携から抜けてしまったり（＝「分離」）別の提携に参加したしてしまったり（＝「結合」）という状況を考えます。このように取りうる提携構造を破壊してエージェント（の部分集合の集合）に戻してしまう関数が「裏切り関数D」です。「関数D：CS(I) → 2^Iである」というのはちょうどこれを表しています。
• しかし、このような提携構造を壊してしまう場合を考えてもやっぱり提携している方がwin-winを維持できるような利得の分配方法があるかもしれません。このような分配方法を「D安定」な配分といいます。そしてD安定な配分を集めたものが「D-CSコア」と本論文で定義されているものです。前項までで述べた「コアの配分」や「CSコアの配分」よりも厳しい条件になります。
• D_M(S) := {C|D₁ ⊂ C ⊂ D₁ ∪ D₂, D₁, D₂ ∈ S}は「結合」を表すものです。2つのグループA、Bがあったとして、片方のグループAがもう一方のBから何人が人員を引き抜いてしまうイメージです。意味合いとしては、「D_M(S)を次の条件を満たす集合Cであると定義する。その条件は『集合Cは集合D₁よりは大きく、集合D₁と集合D₂を合わせたものよりは小さい。ここで集合D₁とD₂は集合Sに含まれるものとする』である」となります。
• D_S(S) := {C|C ⊂ D, D ∈ S}は「分離」を表すものです。グループAがあったとして、グループAから一部の人員がいなくなってさらに小さくなってしまうイメージです。意味合いとしては、「D_S(S)を次の条件を満たす集合Cであると定義する。その条件は『集合Cは集合Dより小さい。ここで集合Dは集合Sに含まれるものとする』である」となります。

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

免責

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

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