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

本稿について

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

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

スポンサードサーチ

今回のまとめ

• 今回の範囲はモデルのうち「CS-コアが空集合であるための条件を示す定理5」を扱うものであるが、数式を用いてシンプルに記載されており、どちらかと言えばまとめるよりも補足する方が必要だと思われるので下記文中にて補足を行う。必要に応じて「筆者補足」部分を参照されたい。

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

5. 提携構造におけるマイニング（続き）

定理5

vを提携構造を持つ提携形ゲームの分割関数とする。vが∀_i ∈ I : w_i < 1/2を満たす重みベクトルwに関して定和かつ非線形ならば、全ての提携構造についてCS-コアは空集合である。

証明

vを上記の定理5と同じ分割関数、S ∈ CS(I)をIの提携構造、xをSに関連する配分であるとする。このとき、v_Sc(C) > x(C)を満たすC ⊂ Iが存在することを証明する。なお、I = {1, ..., n}とし、全てのS ∈ CS(I)についてΣ_S∈Sv_S(S) = 1としても一般性は失わない。

全てのiについてε_i = x_i - w_iとする。このとき、ε₁ ≤ ε₂ ≤ ... ≤ ε_nとしても一般性を失わない。Σ_i∈Iε_i = Σ_i∈Ix_i - Σ_i∈Iw_i = 1 - 1 = 0である点を付記しておく。C = I＼{n}とする。ε_n ≥ 0であるから、Σ_i∈Cε_i ≤ 0かつx(C) ≤ w(C)である。定理5の仮定によりw_n < 1/2であるから、Σ_i∈Cw_i > 1/2が言える。さらに定理5の仮定によりvは非線形であるから、v_Sc(C) > w(C)も言える。従って、v_Sc(C) > x(C)である。（証明終わり）

筆者補足：

• 証明について少し補足します。
• CS-コアが空集合でないとは、CS-コアの配分があるということである。これは、提携構造の構成している提携のいくつかが脱退したとしても、その脱退した提携がより大きな利得を得られることはないということである。逆にCS-コアが空集合であれば、提携構造を脱退することで大きな利得を得られることがあるということを示す。これが「v_Sc(C) > x(C)を満たすC ⊂ Iが存在する」ということ。これを証明できればよい。
  • そもそもCS-コアってなんぞ？という方は、Lewenbergのプール分析論文を読んでみる4、5を先に読んでおくとよいでしょう。
• 内容としては「全体提携の利得配分x_i」と「各プレイヤーの重みベクトルw_i」の「差ε_i」に注目し、全プレイヤーの「全体提携の利得配分の総和＝1」、「全体提携の重みベクトルの総和＝1」、そして「全体提携の利得配分の総和-全体提携の重みベクトルの総和=0」であることを利用して証明する。
  • まず最も「差」が大きいプレイヤー（nさんとする）は必ず「差」が0以上である。0より小さいとすると、その他全てのプレイヤーの「差」も0未満となってしまい、「全体提携の利得配分の総和-全体提携の重みベクトルの総和=0」に反するからだ。「差」が0以上であるということは、このプレイヤーの「全体提携の利得配分x_n」は「各プレイヤーの重みベクトルw_n」以上であるということだ。
  • ということで次にこの最も「差」が大きいプレイヤーnが抜けた場合の「残りの提携C」を考える（C = I＼{n}のこと）。この提携について、nさんが抜けたので
    • 「nを除いた利得配分の総和-nを除いたの重みベクトルの総和」は0以下である（Σ_i∈Cε_i ≤ 0）。
    • 「nを除いた全体提携の利得配分の総和」は「nを除いた重みベクトルの総和」以下である（x(C) ≤ w(C)）（※1）。
      • さらに、定理の仮定より各プレイヤーの重みベクトルは1/2未満でなくてはならないから、「Cの重みベクトルの総和」は1/2より大きい（Σ_i∈Cw_i > 1/2）。
      • また、vは非線形であることから（定義3により）「Cの利得配分の総和」は「nを除いた重みベクトルの総和」より大きい（v_Sc(C) > w(C)）（※2）。
  • ※1、2より、x(C) ≤ w(C)かつv_Sc(C) > w(C)であるので、v_Sc(C) > x(C)である。
• という手順で証明されます。

以下の例は定理5の仮定が全て必要であることを示している。

例2

w ∈ R^|I|を重みベクトルとし、分割関数vがS = {I}である場合にv_S(C) = 2、それ以外の場合にv_S(C) = e^w(C)/Σ_D∈Se^w(D)である提携形ゲームを考えてみよう。vはwに対して非線形であるが、定和ではない。配分x_i = 2w_iは提携構造S = {I}に関して安定である。

筆者補足：

• 例2は定和でないが非線形である場合の例。このケースだとCS-コアの配分が存在するため、定理5は言えない。

例3

プレイヤーが|I| = nで、分割関数vが全てのS ∈ CS(I)とC ∈ Sについてv_S(C) = |C|/nである提携形ゲームを考えてみよう。vは定和であるが、非線形ではない。なぜなら、全ての重みベクトルについて|C| = ⌈(n+1)/2⌉かつw(C) ≥ |C|/nであるようなC ⊂ Iが必ず存在し、なおもC ∈ Sであるような全てのS ∈ CS(I)についてv_S(C) ≤ w(C)が成り立つからである。配分x_i = 1/nは全ての提携構造に関して安定である。

筆者補足：

• 例3は定和であるが非線形でない場合の例。このケースもCS-コアの配分が存在するため、定理5は言えない。

例4

プレイヤーが|I| = nで、分割関数vが1 ∈ Cである場合にv_S(C) = 1、それ以外の場合にv_S(C) = 0である提携形ゲームを考えてみよう。vは重みベクトルw₁ = 0.6とw_i = 0.4/(n-1)（i ≠ 1とする）に対してして定和かつ非線形である。配分x₁ = 1とx_i = 0（i ≠ 1とする）は全ての提携構造に関して安定である。

筆者補足：

• 例4は定和かつ非線形であるが、重みベクトルが1/2より大きいプレイヤーが存在する場合の例。このケースもCS-コアの配分が存在するため、定理5は言えない。
• 以上例2～4より、「vが∀_i ∈ I : w_i < 1/2を満たす重みベクトルwに関して定和かつ非線形」という仮定が全て必要であると言える。

定理5はCS-コアが空であることの十分条件であるが、D_MS-CSコアが空であることを表すわけではない。実際にいくつかの場合に、提携構造に関連する配分はCS-コアの配分ではないがD_MS安定な配分であることがある。

例5

表1に示す提携形ゲームを考えてみよう。このゲームには3タイプの8人のプレイヤーがいる。右列における各提携の報酬は、左列の提携構造の順序に従う。このゲームは全てのS ∈ CS(I)についてΣ_C∈Sv_S(C) = 100であるから定和である。また、例えばw_a = 1/20、w_b = 1/10、w_c = 3/10などとしてみれば分かるように、重みベクトルに関して非線形である。S₁に関して配分(3, 3, 3, 3, 10, 34, 10, 34)はD_MS安定な配分である。すなわち、提携を2つ結合した場合でも分離した場合でもそういったことをした者にとってより良い結果が得られることはない。

筆者補足：

• 例5はCS-コアの配分がなくてもD_MS安定な配分がある場合の例。確かに上の例は「vが∀_i ∈ I : w_i < 1/2を満たす重みベクトルwに関して定和かつ非線形」の条件を満たし、CS-コアの配分は存在しないがD_MS安定な配分が存在する。
• この例5は「D_MS-CSコアが空集合であるにはさらに強い条件が必要」であることを示し、次稿で示す定理6への橋渡し役をしている。

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

免責

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

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