Tangleにおける均衡の説明

この記事は原題『Equilibria in the Tangle: let me try to explain…』の翻訳です。
ご参考までに公開します。必要だと思われる部分には言葉や構成を補っています。私の力不足のため、えいやで翻訳されている部分もあります。

Tangleにおける均衡の説明

投稿者:Serguei Popov
投稿日:2017年12月18日

IOTAの初期から、デフォルトのチップ選択アルゴリズムが強制されていないという事実について疑問がいくつか提起されました。つまり、あるノードが実際にチップを選択するために推奨されるMCMC法を使用しているかどうかや、自己利益を得るためにチップ選択の方法に何らかの調整を施しているかどうか、を確認する手段がないという疑問です。確かに、ホワイトペーパーで説明したように、システムが良好に機能するためには、チップの選択が十分にランダムであることが不可欠です。 ノードがそのトランザクションをどこにアタッチするかを選択するとき、多くのチップの中から等しい確率で選ばれるべきです。このランダム性がなぜ重要であるかを知るために、ノードが常に(いくつかの基準に照らして)最良の2つのチップを選択しようとしていると仮定してください。多くの数のノードが存在し、またトランザクション数も多いため、「最良(best)」とみなされた2つのチップを選んだ者の間で「競争(competition)」が起こります。競合者の中で幸運を勝ち得る者は少なく(そのチップは「最良」とみなされます)、敗者は忘れ去られます。

ここで避けたい状況を説明します。中央に薄い「ほぼブロックチェーン(almost blockchain)」があり、永遠に孤立する可能性の高いトランザクション(緑色)がたくさんあります。青い「直近の(recent)」チップの中で、多くはおそらく不運なことになり、緑の友人たちと運命を共にします。『Equilibria in the Tangle: let me try to explain…』より引用

したがって、利己的なノードは「貪欲な(greedy)」戦略を選択することが非常に懸念され、その戦略は最終的に上記の状況を引き起こします。そして、これがシステムの失敗に繋がるのです。このようなことが起り得るのかどうかという疑問を、どうしたら紐解くことがができるでしょうか。まずはいくつかの理論を見てみましょう。

2人以上のプレイヤー間の非協力ゲームにおいては、ナッシュ均衡に達します。ナッシュ均衡は、他のプレイヤーの戦略が与えられた上で、各プレイヤーが自分の現在の戦略を変更しても得しない状況のことです。場合によっては、そのようなナッシュ均衡は、よく知られている囚人のジレンマゲームのような協力ゲームの結果と比較して、プレーヤーの一部または全部が悪くなっているところで発生する可能性があります。他のケースでは、少なくとも1人のプレーヤーを損させることなく、他の可能な結果が得られないパレート最適の形で、ナッシュ均衡が生じることがあります。IOTAは非中央集権で、分散型で、パーミッションレスなシステムであるので、このシステムのノードの一定割合は非協調的なゲームを行い、自分自身の利益を最大化しようとすると仮定すべきです。したがって、利己的な(または「貪欲な」)ノードの存在を考慮して、この特定のゲームで均衡が起こる場所を理解することが重要です。コモンズの悲劇に陥るのでしょうか。パレート最適でナッシュ均衡が起こるのでしょうか。この状況でナッシュ均衡は本当に起こり得るのでしょうか。

約70年前、John Nashは、結果がプレイヤーの選択によって決定される状況(すなわち非ランダム)において、有限個の可能な選択肢を有する有限の数のプレイヤーの場合における均衡の存在を証明しました。しかし、結果がプレイヤーの選択によって決定される状況(すなわち非ランダム)はTangleにとってはあてはまりません。トランザクションが発行された時点で、それがいつ承認されるか(もっといえば承認されるかどうか自体)分からないからです。そこで、Tangleにおける均衡についての論文中で、私たちは非協調ゲームにおいてナッシュ均衡の存在を厳密に証明していますが、ノードの一部がコストを最小限に抑えるために貪欲なチップ選択戦略を取っています(たとえば、自分のトランザクションが承認されるまでの時間)。また私たちはネットワーク内のノード数が多い場合に、すべてのナッシュ均衡が「ほぼ対称(almost symmetric)」であることも証明しました。ここで言う対称とは、すべてのノードのコストがほぼ同じであるという意味です。ここから、すべてのノードが同じ戦略を採用し得ると仮定することができます。シミュレーションには後者を選択すべきでしょう。過度に異なる戦略を用いて多くのノードをシミュレートしようとするのは、実現不可能であろうからです。

しかし、上記の理論は全て、私たちが以前に提起した疑問に答えるものではありません。つまり、利己的なノードはネットワークを 「破壊(destroy)」するだろうか、という疑問です。この疑問に答えるためには、ナッシュ均衡をどのように捉えるべきかを知る必要があります。しかし、システムの全体的な複雑さのために、純粋に分析的な解を得ることは難しそうですし、また(相対的に)シンプルな、利己的なノードは(ある確率で)上記の「最良の」チップを承認する「貪欲な」戦略をとるという状況でさえも、解を得ることは難しそうです。しかし、貪欲なノード間で行われる非協調的ゲームにおいて、「単純な(naive)」貪欲なチップ選択戦略がナッシュ均衡ではない理由を理解することは可能です。

なぜ「欲張りな」チップ選択戦略は機能しないのでしょうか(2つの「最良」のチップは大きな青い円で表されます)。多くの利己的なノードは、これらの「最良の」チップを選択することによって、つまり、彼らのトランザクションが後続のトランザクションに選択して貰える可能性が高いと思われる2つのチップを選択し、トランザクションをアタッチします。その結果、これらの2つのチップの「近傍(neighborhood)」は「過密(overcrowded)」になります。つまり、利己的なノードによって発行されるトランザクション間の競争が激しくなり、後続のトランザクションによる承認のために選択される可能性が実際には低下し、利己的なノードのインセンティブはすべて失われるのです。『Equilibria in the Tangle: let me try to explain…』より引用

上記の直感を検証するためにシミュレーションが実行され、確かに正しいことが示されました(後続のブログ記事では、これらのシミュレーションをより詳細な方法で説明します)。さらに、ナッシュ均衡では、システムはパレート最適ナッシュ均衡を示すことができる「完全協調(fully cooperative)」型(利己的なノードなし)とほぼ同じくらい効率的でした。結論として、利己的なノードにはまだ余計なコストがかかっていて(たとえば、非常に大きな状態空間上のマルコフ連鎖の出口分布を計算する必要があるなど、計算コストが高く)、デフォルトの戦略の代わりにわざわざ奇妙なチップ選択戦略をとるインセンティブが、殆どあるいは全くありません。

コメントを残す

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