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

本稿について

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

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

スポンサードサーチ

今回のまとめ

• 今回の範囲は3人以上のソロマイナーがいる譲渡可能効用協力ゲームの場合にコアが存在しないことを証明するものであるが、数式を用いてシンプルに記載されており、どちらかと言えばまとめるよりも補足する方が必要だと思われるので下記文中にて補足を行う。必要に応じて「筆者補足」部分を参照されたい。

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

6. 協力ゲームとしてのマイニング（続き）

さて、これでdに対するいくつかの条件の下、n > 2の同一とみなせるマイナーについて、このゲームのコアが空であることを示す準備が整った。dに対する制約は実際のところこれらの結果を得るのに必須である点を付け加えておく。もしdが任意に大きければこのプールは非常に非効率的であり最長チェーンのブロックがこのプールのものである確率は任意に低くなり、マイナーがこのプールのために働くインセンティブは何も残らない。|M| = 3の場合から始めよう。定理に先立って補題を示すが、証明はここでは省く。

筆者補足：

• 今回は前回主張した「Bitcoinネットワークをソロマイナーだけから成る譲渡可能効用の協力ゲームとみなしてこれまでの結果を適用すると、3人以上のソロマイナーがいるマイナーネットワークの場合、コアが存在しない」を証明する内容です。前稿Lewenbergのプール分析論文を読んでみる13が証明の準備にあたるため、先に読まれることをお勧めします。

補題11

Γ = <{1, 2}, ∅, {p, 1 - p}, D, λ>をマイナーネットワークとする。f_2/3(Dλ) = p ⇔ γ(Γ)₁ = 2/3で定義される関数f_2/3：R⁺ → (1/2, 2/3)は単調減少関数である。

定理12

C = <M, P, D, d, β>を|M| = 3であるマイナーのゲームとする。dについて次の条件が成り立つならば、Cのコアは空である。

証明

コアが空ではないと仮定し、xをそのコアの配分とする。C = {1, 2}について、x(C) ≤ 2/3と仮定しても一般性を失わない。すると、次を証明すればよい。

Γ₂ = <{C, S}, {p_C, p_S}, D, λ₂>をv(C)の見積もりに用いるソロマイナーが2人のマイナーネットワークとする。α_C = 2λ/(3+4dλ)、α_S = λ/3をΓ₂の各マイナーがブロックを生成する確率とする。p_C ∝ α_C、p_S ∝ α_Sであり、λはα_C + α_S = λ₂を満たし、λ(Γ₂) = βを満たすものとする。

さて、p_C = (2/(3+4dλ))/λ₂ = 6/(9+4dλ) > 2/(3+4dβ)である。最後の不等式部分はβ > λ/3であるため成り立つ。dについて、

を仮定しているので、f_2/3(Dβ) ≤ 2/(3+4dβ)が成り立つ。f_2/3は単調減少かつβ ≤ λ₂であるから、f_2/3(Dβ) ≤ f_2/3(Dλ₂)が成り立つ。従って、p_C > f_2/3(Dβ)（筆者注：論文ではp_C > f_2/3(Dλ₂)となっているがp_C > f_2/3(Dβ)の誤植と思われる）と言える。f_2/3の定義によりγ(Γ₂)_C = γ_C > 2/3が成り立つ。すなわちv(C) > x(C)であり、xがコアであることに矛盾する。よって題意は示された。（証明終わり）

筆者補足：

• 3人のマイナーネットワークにおいてコアがないことを背理法を使って証明するものです。当然コアの配分があるならば、選んだ2人だけで提携する方が利益が得られることはあってはいけませんが、実際は存在してしまうことからコアの配分はない...という具合に証明します。
  • 「C = {1, 2}について、x(C) ≤ 2/3と仮定しても一般性を失わない」というのは、3人から好きに2人を選ぶとすると全体提携の利得の2/3であるような選び方が必ず存在するから。
• 「α_C = 2λ/(3+4dλ)、α_S = λ/3」というのはLewenbergのプール分析論文を読んでみる13で示したα_Cとα_Sそれぞれにn = 3、|C| = 2を代入すれば出てきます（n = 3なのはマイナーネットワークが3人で構成されているからで、|C| = 2はソロマイナーが2人のマイナーネットワークを考えているから）。
• 「p_C = (2/(3+4dλ))/λ₂ = 6/(9+4dλ) > 2/(3+4dβ)」も同じく前稿の「p₁ = α_C/(α_C+α_S)であり...」から。（※1）
  • 左辺はα_C = 2λ/(3+4dλ)とα_C + α_S = λ₂をp₁ = α_C/(α_C+α_S)に代入してやればよい。中辺はα_C = 2λ/(3+4dλ)、α_S = λ/3をp₁ = α_C/(α_C+α_S)に代入してやればよい。右辺の不等式は真ん中の6/(9+4dλ)にβ > λ/3を代入してやれば成り立つ。
• 「f_2/3(Dβ) ≤ 2/(3+4dβ)」はdの仮定の式をf_2/3(Dβ)について変形しただけ。（※2）
• 「f_2/3は単調減少かつβ ≤ λ₂であるから、f_2/3(Dβ) ≤ f_2/3(Dλ₂)が成り立つ」はそのままの意味。（※3）
• ※1、2、3を合わせることにより、f_2/3(Dλ₂) = p_C > 2/(3+4dβ) ≥ f_2/3(Dβ)となるので、「p_C > f_2/3(Dβ)」が言える。
• f_2/3(Dλ₂) = p_C > 2/(3+4dβ)について、右辺が取りうる最大の値は2/3であるから、p_C > 2/3。f_2/3の定義より、γ(Γ₂)_C > 2/3となるので、コアの配分のはずだったx(C)（2/3以下）を超えてしまい、矛盾が生じる。...ということでコアの配分はありません。（ここの証明は次の定理13でも用いられているように系1を利用する方が自然かもしれません。）

次の定理は|M| > 3の場合について同様の結果を示すものである。

定理13

Cを|M| > 3であるマイナーのゲームであるとする。d ≤ D(n - 3)/2(n + 1)(1 + Dβ)ならば、Cのコアは空である。

証明

証明は定理12と同様である。まずコアが空ではないと仮定し、xをそのコアの配分とする。C = {1, ..., m}かつm = ⌈n/2⌉としたとき、x(C) ≤ m/nと仮定しても一般性を失わない。さて、α_Cとα_Sそれぞれについて次の値を得るマイナーネットワークΓ₂を用いる。

β > λ/n、m ≤ (n+1)/2であるから、dの上限はd < Dn(n - m -1)/2m(n + Dλ)であり、ゆえにp_C > m/n。系1よりγ(Γ₂)_C = γ_C > p_Cが得られるので、v(C) > x(C)であり、xがコアであることに矛盾する。よって題意は示された。（証明終わり）

少なくともマイナーが3人いるケースとは対照的に、|M| = 2の場合にはこのゲームのコアは空ではなくただ一つの元が存在する。

筆者補足：

• 証明は論文で述べられている通り定理12とほぼ同様なので省略しますが、定理12と13を合わせて、3人以上のソロマイナーがいる譲渡可能効用協力ゲーム（とBitcoinネットワークをみなした）の場合に必ず"割を食う"マイナーが存在するので安定しないことが分かります。

定理14

C = <M, P, D, d, β>を|M| = 2であるマイナーのゲームとする。Cのコアはただ一つの元を持つ。

証明

Γ = <{1, 2}, ∅, P, D, d, λ>をβ(Γ) = βである2人のソロマイナーのネットワークとする。γ = (γ₁, γ₂)は最長チェーンにおけるマイナーの比例利得であるとする。ソロマイナーとして動く場合に全体提携から唯一マイナーが逸脱できるのは、v({i}) = γ_iの利得を得られるときだけである。全てのコアの配分x = (x₁, x₂)について、x_i ≥ 0かつx₁ + x₂ = 1かつx_i ≥ γ_iが存在しなければならない。従って、x_i = γ_iだけが唯一解であり、コアはただ一つの元を持つ。（証明終わり）

筆者補足：

• 2人のソロマイナーネットワークの場合、どちらか片方に計算パワーに比例する分以上の利得を与えたらもう一方は必ず計算パワーに見合わない利得になるので全体提携が成り立ちません。これを成り立たせるには両方に計算パワーに比例した配分とする以外にないということです。

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

免責

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

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