簡単まとめ

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

更新日:

本稿について

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

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

スポンサードサーチ

今回のまとめ

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

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

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

定理5

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

証明

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

全てのiについてεi = xi - wiとする。このとき、ε1ε2 ≤ ... ≤ εnとしても一般性を失わない。ΣiIεi = ΣiIxi - ΣiIwi = 1 - 1 = 0である点を付記しておく。C = I\{n}とする。εn ≥ 0であるから、ΣiCεi ≤ 0かつx(C) ≤ w(C)である。定理5の仮定によりwn < 1/2であるから、ΣiCwi > 1/2が言える。さらに定理5の仮定によりvは非線形であるから、vSc(C) > w(C)も言える。従って、vSc(C) > x(C)である。(証明終わり)

筆者補足:

  • 証明について少し補足します。
  • CS-コアが空集合でないとは、CS-コアの配分があるということである。これは、提携構造の構成している提携のいくつかが脱退したとしても、その脱退した提携がより大きな利得を得られることはないということである。逆にCS-コアが空集合であれば、提携構造を脱退することで大きな利得を得られることがあるということを示す。これが「vSc(C) > x(C)を満たすCIが存在する」ということ。これを証明できればよい。
  • 内容としては「全体提携の利得配分xi」と「各プレイヤーの重みベクトルwi」の「差εi」に注目し、全プレイヤーの「全体提携の利得配分の総和=1」、「全体提携の重みベクトルの総和=1」、そして「全体提携の利得配分の総和-全体提携の重みベクトルの総和=0」であることを利用して証明する。
    • まず最も「差」が大きいプレイヤー(nさんとする)は必ず「差」が0以上である。0より小さいとすると、その他全てのプレイヤーの「差」も0未満となってしまい、「全体提携の利得配分の総和-全体提携の重みベクトルの総和=0」に反するからだ。「差」が0以上であるということは、このプレイヤーの「全体提携の利得配分xn」は「各プレイヤーの重みベクトルwn」以上であるということだ。
    • ということで次にこの最も「差」が大きいプレイヤーnが抜けた場合の「残りの提携C」を考える(C = I\{n}のこと)。この提携について、nさんが抜けたので
      • nを除いた利得配分の総和-nを除いたの重みベクトルの総和」は0以下である(ΣiCεi ≤ 0)。
      • nを除いた全体提携の利得配分の総和」は「nを除いた重みベクトルの総和」以下である(x(C) ≤ w(C))(※1)。
        • さらに、定理の仮定より各プレイヤーの重みベクトルは1/2未満でなくてはならないから、「Cの重みベクトルの総和」は1/2より大きい(ΣiCwi > 1/2)。
        • また、vは非線形であることから(定義3により)「Cの利得配分の総和」は「nを除いた重みベクトルの総和」より大きい(vSc(C) > w(C))(※2)。
    • ※1、2より、x(C) ≤ w(C)かつvSc(C) > w(C)であるので、vSc(C) > x(C)である。
  • という手順で証明されます。

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

例2

wR|I|を重みベクトルとし、分割関数vS = {I}である場合にvS(C) = 2、それ以外の場合にvS(C) = ew(C)DSew(D)である提携形ゲームを考えてみよう。vwに対して非線形であるが、定和ではない。配分xi = 2wiは提携構造S = {I}に関して安定である。

筆者補足:

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

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

筆者補足:

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

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

筆者補足:

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

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

例5

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

筆者補足:

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

Lewenbergのプール分析論文を読んでみる9 ←← 前)|(次 →→ Lewenbergのプール分析論文を読んでみる11

免責

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

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

-簡単まとめ
-, , , , ,

Copyright© 暗号通貨界隈のメモ書きなど。 , 2019 All Rights Reserved Powered by STINGER.

%d人のブロガーが「いいね」をつけました。