簡単まとめ

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

投稿日:

本稿について

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

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

スポンサードサーチ

今回のまとめ

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

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

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

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

定理6

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

筆者補足:

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

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

|S| ≥ 3の場合、vS(C1) ≤  ... ≤ vS(Cm)であるようなSS = {C1, ..., Cm}と表記する。C = C1C2とする。配分xx(C) = x(C1) + x(C2) = vS(C1) + vS(C2)を満たす。CSにおける2つの提携を結合したものであるので、CDMS(S)が言える。さらにvは単調関数であるからvSc(C) > vS(C1) + vS(C2)である。ゆえに、vSc(C) > x(C)が成り立つ。

|S| ≤ 2の場合、(定理5と同様に)εi = xi - wiとし、ε1ε2 ≤ ... ≤ εnを仮定する。すると、C = I\{n}についてvSc(C) > x(C)である。|S| = 1ならばCは全体提携から分離した提携であり、|S| = 2ならば2つの提携を結合したものである。ゆえにどちらの場合においてもCDMS(S)である。(証明終わり)

筆者補足:

  • 証明について少し補足します。
  • DMS-CSコアが空集合でないとは、DMS-CSコアの配分があるということである。これは、提携構造の構成している提携のいくつかが結合・分離したとしても、その結合・分離した提携がより大きな利得を得られることはないということである。逆にDMS-CSコアが空集合であれば、提携構造から結合・分離することで大きな利得を得られることがあるということを示す。これが「vSc(C) > x(C)を満たすCDMS(S)が存在する」ということ。これを証明できればよい。
  • |S|が3以上の場合について
    • C = C1C2とすると、提携構造SCが得られる利得は、C1C2が得られる利得の和である。これがx(C) = x(C1) + x(C2) = vS(C1) + vS(C2)ということ。(※1)
    • また、C = C1C2と置いたので、必然的にCDMS(S)である。
    • 定理の仮定よりこの分割関数は「単調関数」であるから、定義3によりvS(C1) + vS(C2) < vSc(C)(※2)
    • ※1、2より、vSc(C) > x(C)が成り立つ。
  • |S|が2以下の場合については定理5の証明をなぞっている。直観的にSが2より小さいとすれば、2つの提携が一緒になっているか、あるいは提携1つずつ(全体提携から分離したか)のどちらかしかない。どちらの場合でもそのような提携構造をとっていることがそのままCDMS(S)であることを示す。
    • |S|が2以下であればvが「単調」かに関わらず、DMS-CSコアは空集合であるともいえる(定理5のみで証明可能なため)。

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

免責

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

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

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

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

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