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

本稿について

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

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

スポンサードサーチ

今回のまとめ

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

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

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

次の定理はD_MS-CSコアが空であることの十分条件を与えるものである。

定理6

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

筆者補足：

• 定理5の条件に「単調」であることが加わったものが定理6です。定理5はこちらを参照。

証明

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

|S| ≥ 3の場合、v_S(C₁) ≤  ... ≤ v_S(C_m)であるようなSをS = {C₁, ..., C_m}と表記する。C = C₁ ∪ C₂とする。配分xはx(C) = x(C₁) + x(C₂) = v_S(C₁) + v_S(C₂)を満たす。CはSにおける2つの提携を結合したものであるので、C ∈ D_MS(S)が言える。さらにvは単調関数であるからv_Sc(C) > v_S(C₁) + v_S(C₂)である。ゆえに、v_Sc(C) > x(C)が成り立つ。

|S| ≤ 2の場合、（定理5と同様に）ε_i = x_i - w_iとし、ε₁ ≤ ε₂ ≤ ... ≤ ε_nを仮定する。すると、C = I＼{n}についてv_Sc(C) > x(C)である。|S| = 1ならばCは全体提携から分離した提携であり、|S| = 2ならば2つの提携を結合したものである。ゆえにどちらの場合においてもC ∈ D_MS(S)である。（証明終わり）

筆者補足：

• 証明について少し補足します。
• D_MS-CSコアが空集合でないとは、D_MS-CSコアの配分があるということである。これは、提携構造の構成している提携のいくつかが結合・分離したとしても、その結合・分離した提携がより大きな利得を得られることはないということである。逆にD_MS-CSコアが空集合であれば、提携構造から結合・分離することで大きな利得を得られることがあるということを示す。これが「v_Sc(C) > x(C)を満たすC ∈ D_MS(S)が存在する」ということ。これを証明できればよい。
  • そもそもD_MS-CSコアってなんぞ？という方は、Lewenbergのプール分析論文を読んでみる4、5、6を先に読んでおくとよいでしょう。
• |S|が3以上の場合について
  • C = C₁ ∪ C₂とすると、提携構造SでCが得られる利得は、C₁とC₂が得られる利得の和である。これがx(C) = x(C₁) + x(C₂) = v_S(C₁) + v_S(C₂)ということ。（※1）
  • また、C = C₁ ∪ C₂と置いたので、必然的にC ∈ D_MS(S)である。
  • 定理の仮定よりこの分割関数は「単調関数」であるから、定義3によりv_S(C₁) + v_S(C₂) < v_Sc(C)（※2）
  • ※1、2より、v_Sc(C) > x(C)が成り立つ。
• |S|が2以下の場合については定理5の証明をなぞっている。直観的にSが2より小さいとすれば、2つの提携が一緒になっているか、あるいは提携1つずつ（全体提携から分離したか）のどちらかしかない。どちらの場合でもそのような提携構造をとっていることがそのままC ∈ D_MS(S)であることを示す。
  • |S|が2以下であればvが「単調」かに関わらず、D_MS-CSコアは空集合であるともいえる(定理5のみで証明可能なため)。

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

免責

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

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