タングルにおける均衡の説明(その2)

補足説明
この記事は原題『Equilibria in the Tangle: let me try to explain… (part 2)』の日本語訳です。ご参考までに公開します。必要だと思われる部分には言葉や構成を補っています。私の力不足のため、えいやで翻訳されている部分もあります。
トップ画像は『Equilibria in the Tangle: let me try to explain… (part 2)』より引用しております。

投稿者:Olivia Saa
投稿日:2017年12月27日

前回の記事で、タングルにトランザクションをアタッチするゲームにおいてナッシュ均衡を見出すことの重要性を説明しました。この論文(Equilibria in the tangle)では、ナッシュ均衡の存在を証明し、ナッシュ均衡の観点において利己的なノードが似通った戦略を選択することを示しました。しかし、私たちはまだこのナッシュ均衡がどのように見えるかをみていく必要があります。この理論は「ほぼ対称的な」ナッシュ均衡の存在を証明している一方で、その結果が戦略の性質と、その性質がタングルの全体的な機能に及ぼす影響については何も言及していません。システムの複雑さのために、これらの点を分析するためには、コンピュータシミュレーションに目を向ける必要があります。

数週間かけて、インテルXeon 12コア3.20 GHzプロセッサでシミュレーションを実行し、約50,000件のトランザクションのサンプルをテストし、新しいトランザクションの到着率 \(\lambda\)、論文中で定義されたコスト(トランザクションが承認されるのに必要な平均時間に似た変数)、デフォルトのランダムウォークチップ選択アルゴリズムの「ランダム度」\(\alpha\)、ネットワーク伝搬遅延 \(h\)、および利己的に振る舞うノードの割合 \(\gamma\)に関連するパラメータを検証しました。これらのシミュレーションを通じて、テストされた特定の種類の戦略について均衡を経験的に見つけることができました。そして、ノードの大部分が貪欲なチップ選択戦略をとったとしても、利己的になることであまり得をしないことがわかったのです。さらに、デフォルトのチップ選択戦略を使用している善良なノードは、貪欲なノードの存在によっても効率性を大幅に落とすことがないことがわかったのです。

まず、デフォルトのチップ選択戦略(論文の\(S_0\))と特定の「最適化された(optimized)」チップ選択戦略(論文中の\(S_1\))をとることができる利己的ノードの割合が固定され、その割合は\(\gamma\)によって示されると仮定します。残りのノードは戦略を選択できないため、常に戦略\(S_0\)を選択します。そのような戦略が入り混じったゲームは、貪欲なノードの一部\(\theta\)が戦略\(S_1\)を選択し、残りの利己的なノードが戦略\(S_0\)を選択する第2のゲームと言えるでしょう。単純化のために、これからはこの代わりのゲームについて検討していきましょう。これらの利己的なノードのうち、どれだけ自分の意志でデフォルトのチップ選択戦略をとるのでしょうか?その割合はもちろん、デフォルト戦略を選択するコストが最適化された戦略を選択するコストと等しいポイントになるでしょう。すなわち、自分の現在の戦略から逸脱すると、利己的なプレイヤーが何も得られないポイントです。このポイントをナッシュ均衡と呼びます。

あるシステムにとって(これは\(\lambda/ h\)と\(\alpha\)を意味します)、ノードのコストは\(p\)のみに依存します。\(p\)は戦略\(S_1\)のもとに発行されたトランザクションの割合です(システム全体において利己的なノードの割合を\(\gamma\)とし、利己的なノードが戦略\(S_1\)を選択する割合を\(\theta\)とすると、\(p =\gamma \theta\)と求めることができます)。そこで、ナッシュ均衡を見出すことについて語る際に、\(\theta\)(貪欲なノード戦略に関連する変数)の値について語ることになるのですが、\(p\)についてコストがどのように変化するかを探求し、研究しなければなりません。それから、この割合\(p\)を変数\(\theta\)に「変換(translate)」します。

考えられる結果は3つあります。

  1. 考えられる\(p\)すべての値に対して、デフォルト戦略が常に優れている場合。このケースでは全ての利己的なノードがデフォルトの戦略を選ぶでしょう(これは\(\theta = 0\)を意味します)。
  2. 考えられる\(p\)すべての値に対して、「最適化された」戦略が常に優れている場合。このケースでは全ての利己的なノードが「最適化された」戦略を選ぶでしょう(これは\(\theta = 1\)を意味します)。
  3. もし上記の2つの選択肢のどちらも当てはまらない場合、デフォルトの戦略は、特定のポイント\(p\)における「最適化された」戦略と等しくなります。この\(p\)において(実際には、この\(p\)に関係する\(\theta\)において)、システムのナッシュ均衡が認められるでしょう。

以下のグラフ(図1)において、シミュレーションで使用されたデフォルトのチップ選択戦略は、高度のランダム性(\(\alpha = 0.01\))を有していました。シミュレーションは、新たに入ってくるトランザクションの二つの比率(\(\lambda = 25\)と\(\lambda = 50\))に対して実行されました。上記の3つの考えられるシナリオのどれが正しいでしょうか?利己的なノードは常にデフォルトの戦略を選択するでしょうか?それとも、常に「最適化された」戦略を選択するでしょうか?はたまた、ある戦略を選択するノードはもう一方の戦略を選択するノードの数に比例するのでしょうか?図示されたケースにおいては、デフォルト戦略のコストが「最適化された」戦略のコストと交差します。この交点における戦略\(S_1\)を使用するノードの割合は、\(\lambda = 25\)の場合、およそ\(p = 0.07\)であり、\(\lambda = 50\)の場合、\(p = 0.12\)です。これらの割合\(p\)は、ここで\(\theta\)に変換しなければならず、\(\theta\)はナッシュ均衡点となります。そのためには、2つの異なる例を使用して\(\lambda = 25\)のデータを分析することで、この問題の2つの考えられる結果に繋がるでしょう。

図1: \(S_0\) はデフォルトの戦略であり、 \(S_1\) は「最適化された」戦略です。\(p\)は、デフォルトの戦略よりも最適化戦略を選択する利己的なノードの割合です。ナッシュ均衡は(2つのそれぞれのトランザクションの割合\(\lambda\))ラインが交差するところです。
Equilibria in the Tangle: let me try to explain… (part 2)』より引用

1.\(\gamma = 0.5%\)のノードが利己的に振る舞うと仮定します。戦略\(S_1\)の下で発行されるトランザクションの考えられる最大の割合はどうなるでしょうか?それは明らかに\(0.5\)です。善良なノードは戦略\(S_1\)を選択することができないからです。したがって、考えられる\(p\)は\(0 \leq p \leq 0.5\)になります。今、\(p = 0.07\)の戦略\(S_1\)の下で発行されるトランザクションの割合を得るためには、\(\theta= 0.14\)でなければいけません。そして、これがナッシュ均衡になるでしょう。

2.次に、\(\gamma = 0.05%\)のノードが利己的に振る舞うと仮定します。戦略\(S_1\)の下で発行されるトランザクションの考えられる最大の割合はどうなるでしょうか?それは明らかに\(0.05\)です。上の例と同じ理由です。したがって、考えられる\(p\)は\(0 \leq p \leq 0.05\)になります。この場合、考えられる全ての\(p\)の値に対して、最適化された戦略が常により小さいコストを得られることを意味します。したがって、すべての利己的なノードは、「最適化された」戦略(これは\(\theta = 1\)を意味します)を選択します。

要約すると、戦略\(S_1\)でのノードのコストが、戦略\(S_0\)でのノードのコストと\(p = p\)で等しい場合、ナッシュ均衡は\(\theta = \min(1, p /\gamma)\)になります。この情報の1つの考えられる直接的な応用は、デフォルトのチップ選択アルゴリズムの改良(ゲーム理論的な側面で)でしょう。現在のデフォルトのチップ選択アルゴリズムを、時間の割合\(p\)で\(S_1\)を使用し、残りは\(S_0\)を使用するアルゴリズムに変更すると、利己的なノードも均衡状態にあるポイントに向かうため、利己的なノードはデフォルトの戦略から逸脱するインセンティブがなくなるでしょう。

私たちは既にナッシュ均衡を見出しましたが、まだ疑問に答えられていません。すなわち、利己的な戦略の存在は、システムの全体的な機能にどのようなコストを課すのか?という疑問です。善良なノードが(利己的なノードがまったくない状況と比較して)深刻な悪影響を被るのでしょうか?

次のグラフ(図2)は、デフォルトの戦略に従った利己的なノードに課せられた平均コストの増加を示しています。\(W(p)\)を図1に示す善良なノードのコストとします。コストの増加は、\((W(p)-W(0)) / W(0)\)として計算されるので、コストの増加は、利己的なトランザクションの割合\(p\)の存在下での善良なノードのコストと、利己的なトランザクションが全くないときの善良なノードのコストの(割合における)差となります。グラフに示されているように、発見された善良なノードに課せられた平均コスト増加は実際には負であり、平均して利己的なノードの存在が、\(\alpha\)の値が低い時には他のノードに害を為さないことを意味します。

図2 – いくつかの\(\alpha\)と\(\lambda\)に対する、利己的なノードの存在によって誘発された善良なノードコストの増加
Equilibria in the Tangle: let me try to explain… (part 2)』より引用

上記の結果が必ずしも高い\(\alpha\)で保持されるとは限らないことに注意してください。また、ここでは、利己的なノードが常に善良なノードを助けると主張しているわけではありません。なぜなら、全てのノードのコストの分布ではなく、単に平均を分析しているからです。例えば、広範な分布(いくつかのノードが非常に低いコストを有し、他のノードが非常に高いコストを有すなど)がシステムの機能を妨害する可能性があります。したがって、今後の研究では、このテーマについてより深い分析を行う必要があります。

さらに、善良なノードに対する貪欲なノードの利得は経済的に魅力的ではないことを示しています(図3では、この場合最大利得は計算上10%強です)。計算コストのいくつかの本質的な増大について比較した際に、善良なノードがデフォルトのチップ選択アルゴリズムに単に従う場合と比較して、利己的に振る舞うことで得られる利益は小さい(またはおそらく負でさえある)です。また、我々は、貪欲であるという社会的コストを考慮に入れていません。つまり、ノードが利己的であると見なされると、そのノードは他のノードによって避けられる可能性があるのです。つまり、長期的には、利己的なノードは誰も他のノードに避けることを強いていない状況下でさえ、ネットワークから「出禁(banned)されて」いるのです。

図3:\(\alpha = 0.01\)の割合におけるデフォルト戦略\(S_0\)に対する貪欲な戦略\(S_1\)の利得。ナッシュ均衡は\(\delta = 0\)です。
Equilibria in the Tangle: let me try to explain… (part 2)』より引用

要約すると、この研究の予備的な結果は、欲張りなノードの存在下でタングルがどのように進化するかについての著者の直観のいくつかを確認しました。さらなる研究では、考えられる貪欲なチップ選択戦略の広がり、ML(機械学習)およびAI技術によるシミュレーションの実行、およびデフォルトのチップ選択アルゴリズムを利己的、善良なノードのどちらにとっても最適な戦略とするべく改善し続けることが含まれます。

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です