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

本稿について

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

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

スポンサードサーチ

今回のまとめ

• 今回の範囲は本論文にて分析のベースとなる「協力ゲーム理論」のモデルについて述べたものであるが、数式を用いてシンプルに記載されており、どちらかと言えばまとめるよりも補足する方が必要だと思われるので下記文中にて補足を行う。必要に応じて「筆者補足」部分を参照されたい。

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

2. 準備（続き）

協力ゲーム（Cooperative Games）

協力ゲーム理論を使ってプールにおけるエージェントのインタラクションを分析する。（譲渡可能効用のある）協力ゲーム[29]は、プレイヤーの集合I（|I| = n）、あらゆる提携（チームとして働くエージェントの部分集合）が協力することで達成できる金銭的価値を定める「特性関数（characteristic function）」であるv：2^I → Rからなる。直観的にv(C)はC ⊆ I内のメンバが協力することで獲得できる合計利得である。この特性関数は提携ごとの合計報酬を説明するものの、提携内のエージェント間での報酬の「分配（distributing）」を定めるわけではない。このような分割は「配分（imputation）」という。配分とは全エージェントの「全員提携（grand coalition）」であるIの利得を分割するベクトルx ∈ R^|I|である。ここでΣ_i∈Ix_i = v(I)であり、x_i ≥ 0はプレイヤーiの利得である。提携形ゲームにおいて安定性を説明する最も主要な解概念は「コア（core）」である。ある提携B ⊆ Iのメンバは全体提携により自らが得られる利得よりも大きな利得を自らグループとして動くことで得ることが可能、すなわちv(B) > Σ_i∈Bx_iであって、なおかつ全体提携を破棄できる場合、全体提携による配分xは提携Bにより「拒否（block）」される。どんな提携をもってしても拒否されない場合、つまり、あらゆる提携C ⊂ Iについてx(C) > v(C)（ここでx(C) = Σ_i∈Cx_i）がある場合、その配分xはコアの配分である。

筆者補足：

• 協力ゲーム理論はゲーム理論の一分野で、プレイヤーの協力が前提にあります。プレイヤー単体がどう動くか？ではなく、協力して得た利得をどう分配するか？が主な関心領域です。
• 実はマイニングプールの仕組みは協力ゲーム理論に似ています。構造を簡単に説明すると、「ブロックチェーンは複数のマイニングプールで維持されている。マイニングプールは個人マイナーが集まって協力しあうものであるが脱退もできる。マイニングプールが獲得した報酬は分割可能である」となるでしょう。これを協力ゲーム理論風に言い換えると、「ブロックチェーンは複数の提携で維持されている。マイニングプールはプレイヤーの提携であるがプレイヤーは提携を破棄することもできる。マインイングプールが獲得した利得は譲渡可能な効用である」...となります。このように、協力ゲーム理論のモデルで説明・分析できそうという見立てをLewenbergらは立てています。（※利得の譲渡不可能性を考慮する協力ゲームもありますが、ここでは割愛します。）
• 本論文で頻繁に出てくる「提携」というのは協力ゲーム理論における標準的なモデルです。提携は本論文にあるようにチームとして働くエージェントの部分集合、もう少し噛み砕けば、全プレイヤーのうちの一部が協力関係を結んだものです。表記的には提携を"S"で表現します。提携S単独で獲得できる利得を表すのが特性関数です。表記的には特性関数をvとして、提携Sの利得はv(S)で表現します。このモデルに基づく協力ゲームを「提携形ゲーム」や「特性関数形ゲーム」といいます。従って、本論文は提携形ゲームのモデルに基づいた分析であると言えるでしょう。
• v(S)は協力した結果どれだけ利得が得られるかを表しますが、それを提携しているプレイヤー間でどう分割するかについては何も定めていません。この分割する行為を協力ゲーム理論では「配分」といいます（正確には全体合理性（Σ_i∈Ix_i = v(I)のこと。要は各プレイヤーに分配された利得を全て足すと、協力して得た利得に一致するという当たり前のこと）と個人合理性（一人で動くより協力する方が高い利得を得られること）を満たす場合を特に配分というのですが、分配やら配分やらで混乱しがちになるので、簡明のためまとめて配分とします）。この配分をベクトルで表現し、xと表記します。ベクトルというと難しそうですが、要は提携Sに参加しているプレイヤーに分け与えられる報酬額を並べたものです。全部でa, b, cさんの3人のプレイヤーがおり提携S（特にこの全プレイヤーの提携を「全体提携」といいます）参加していてそれぞれに10円、20円、30円が与えられるならば(10, 20, 30)がベクトルxである...といったイメージです。
• 全体提携したとしても、提携を解消されてしまう場合があります。当然それは提携を解消する者にとって利得が生じる場合です。最もシンプルなのは単独で動く方が高い利得を得られる場合（個人合理的である場合）です。上記の例の場合であれば、aさん単独で動いたときに15円もらえるならば、aさんはわざわざ提携を組もうとは思わないわけです。これはbさんも単独で21円、cさんも単独で32円もらえるとすれば同様です。複雑にはなりますが、これとは別にaさんとbさんで部分的な提携を組んだ場合にaさんが20円、bさんが25円もらえるとすれば、両者ともに全体提携するよりも、単独で動くよりもたくさん利得をもらえるわけですからaさんとbさんだけで提携するでしょう。プレイヤーが増えてくるにつれて提携の組合せも爆発的に増えてきます。しかし、単独を含めてどのような提携をもってしても全体提携する方が全プレイヤーが得をする場合があります。このような配分をコアといいます。配分の仕方は全く存在しないこともあれば複数通り存在することもあるため、コアというのはそのような配分の仕方を集めた概念です。（※コア以外にも解の概念がありますが（仁、シャープレイ値）、ここでは割愛します。）

以下は概要を掴むのに参考になると思います。

協力ゲーム理論入門：http://www.orsj.or.jp/archive2/or60-6/or60_6_343.pdf, 岸本信
協力ゲームとその応用：https://jsai.ixsq.nii.ac.jp/ej/?action=repository_uri&item_id=7493&file_id=22&file_no=1, 松林伸生

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

免責

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

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