Summary of Equilibria in the Tangle: let me try to explain…

Reference

Equilibria in the Tangle: let me try to explain…

這是 IOTA 白皮書的作者 Serguei Popov 對於其論文：Equilibria in the tangle. 的第一篇解釋，日後會有更多篇的文章來慢慢導讀該篇論文 … …。

Summary

IOTA 目前預設的 tips selection 演算法並非是強制的。也就是說，wallet 端在每一次的交易中，可以總是刻意選擇固定的 tips，而非透過 IRI 的 MCMC (Markov chain Monte Carlo) 演算法。這會造成新進的 tips 很不容易被驗證，而一直處於 pending 的狀態，且自私的節點也容易促成：垃圾郵件攻擊，“分裂”，雙重支出 … …等等的攻擊。其 Tangle 模型如下圖1.所示：

圖1. 這是一種我們必須要避免的狀態，中間黑色的部份為一個幾乎像是區塊鏈的塊狀，大部分的綠色交易選擇 confirm 黑色塊，而且成為孤兒（因為沒有新的交易 confirm 他們），而新進的藍色 tips 也面臨一樣的命運。

所以有些自私的節點會採取這種「貪婪」的策略來加速交易的產生，最終就會產生如同圖1.的狀態，而導致系統失敗。我們如何探討這個問題？看看是否真的會發生？首先讓我們先看理論。

當一個由兩個或多個玩家組成的非合作博奕遊戲中，如果某情況下無一參與者可以通過獨自行動而增加收益，則此策略組合被稱為奈許均衡點，如同著名的囚徒困境博奕般。而奈許均衡點只會發生在 Pareto-optimal 的結果上。在沒有其他可能的結果的情況下，如果沒有讓至少一名玩家變壞，任何玩家都會變得更好。

由於IOTA是一個分散的、無權限的節點網絡，因此必須假設這個系統中的一部分節點將被視為一個非合作博弈，只選擇對自己自身利益最大化的情況。因此，在這種「貪婪」的節點劑定會發生的條件下，理解這個博奕遊戲中可能的平衡狀況是很重要的。它會變成系統崩潰的悲劇嗎？或者奈許均衡點會出現 Pareto-efficient 嗎？ 在這種情況下，奈許均衡是否會存在？

大概在 70 年前 John Nash 證明在有限數的玩家，且選擇決定（即非隨機）的情況下，平衡點是存在的。然而這個條件並不適用於 Tangle，因為在交易被發布之後，我們不知道該交易何時會被確認 (confirm)。因此，在Equilibria in the tangle 這篇論文中，我們提出了非合作博弈中存在奈許均衡的嚴格證明，其中一部分節點選擇了一個「貪婪」的 tips 的演算法，來最小化他們的交易成本（例如，時間， 交易需要自己的交易被批准）。 我們還證明了，給定一個有大量節點的網路，所有的奈許均衡“幾乎是對稱的”，所有節點的成本大致相同，這又使我們可以假設 所有節點都可以採取相同的策略。 我們需要進行模擬，因為試圖用許多不同的策略來模擬許多節點將是不可行的。

但是，所有上述理論都不能回答我們之前提出的問題：**自私的節點會“毀掉”網絡嗎？**要回答這個問題，我們需要看看奈許均衡看起來是怎樣的。但由於系統的整體複雜性，要獲得純粹的分析解決方案似乎太困難了，當一些自私的節點在某種機率下以取巧的方式選擇 tips 時。然而，仍然有可能理解為什麼在「貪婪」節點之間發生的非合作博弈中，仍不會形成奈許均衡。

圖2. 為什麼「貪婪」的 tips selection 不會起作用。(圖中的藍色圈為兩個最好的 tips) 許多自私的節點將他們的交易附加到兩個“最好”的 tips 上，認為通過選擇這些 tips，他們的交易將更有可能被隨後的交易選擇。結果，這兩個 tips 的“鄰居”變得“擁擠”：自私節點之間的交易競爭如此之多，以至於後來交易選擇審批的機會實際上減少了，並全部損失。

模擬是為了驗證上述的直覺，而且他們證明這是正確的（在隨後的 blog 文章中，我們將以更詳細的方式描述這些模擬）。 而且，在奈許均衡中，系統幾乎與“完全合作”的製度（沒有自私的節點）一樣有效，這可能暗示了 Pareto-efficient 奈許均衡。 作為結束語，我們觀察到，鑑於自私的節點仍然有一些額外的成本（例如，他們需要計算一個馬爾可夫鏈在一個非常大的狀態空間的出口分佈，這可能在計算上是昂貴的），他們將很少或根本沒有動機去使用任何奇特的 tips selection 策略，而不是預設的 MCMC 策略。

奈許均衡點：

奈許均衡點 又稱為非合作賽局博弈，是在非合作博弈（Non-cooperative game）狀況下的一個概念解，在博弈論中有重要地位，以約翰·奈許命名。

簡單的解釋為：
如果某情況下無一參與者可以通過獨自行動而增加收益，則此策略組合被稱為奈許均衡點。例如註明的博奕理論：囚徒困境 便是奈許均衡點的理論應用。

以電影中的奈許均衡點來解釋為何貪婪的節點不會起作用？
如果每個人都去泡房間裡最 hot 的女孩（「最好」的 tips），每個人都會失敗，且都得一個人回家（也就是本文中的「永遠是孤兒」）。
而如果每個人都遵循正常的參與規則（預設的 tips selection 演算法：MCMC） 所有的男孩和女孩（ transaction 和 tips）都會得到一些動作（奈許均衡），即使是房間裡最炙手可熱的女孩。

如果太多自私的節點選擇一個貪婪的策略。 他們將不得不付出更多的努力來爭奪他們的 tips，就像多個追求者一樣為了同一個女人：沒有帕累托最優的結果。