# Summary of Equilibria in the Tangle: let me try to explain… (part 2)

## Reference
[Equilibria in the Tangle: let me try to explain… (part 2)](https://blog.iota.org/equilibria-in-the-tangle-let-me-try-to-explain-part-2-6dcc8e7c0ad8)

[Part 1 (原文) ...](https://blog.iota.org/equilibria-in-the-tangle-let-me-try-to-explain-b22ad6f00c13)

[Part 1 (中文 summary) ...](/s/rkltQhPzf)

本篇 (part 2) 的作者為 Olivia Saa，為 [Equilibria in the Tangle](https://arxiv.org/abs/1712.05385) 論文的第二作者。

在[第一篇](https://blog.iota.org/equilibria-in-the-tangle-let-me-try-to-explain-b22ad6f00c13)文章中，Serguei Popov 告訴我們其 Equilibria 指的就是 Nash Equilibrium，在本篇 Olivia Saa 的目標為證明 Nash Equilibrium 是存在的。

本篇重點在於以一台 Intel Xeon 12 core 3.20 Ghz 的處理器上，及測試的樣本大約為 50,000 個交易 (transactions)，模擬與證明使用預設 tip selection 策略的奈許平衡存在！

即使大部分節點選擇了「貪婪」的 tip selection 策略，他們也沒有因為「自私」而獲得更多的利益。此外也呈現，非「自私」的節點，使用預設的 tip selection 策略，不會因「貪婪節點」的存在而顯著地損失效率。

## Summary
在 [前一篇的文章](https://blog.iota.org/equilibria-in-the-tangle-let-me-try-to-explain-b22ad6f00c13)中，我們解釋了尋奈許平衡的重要性。而在 [Equilibria in the Tangle](https://arxiv.org/abs/1712.05385) 論文中，我們也證明了它的存在，並且表明在這一點上，所有的「自私節點」都會選擇一個類似的「策略」。然而，我們仍需要看看這個奈許平衡是怎樣的。雖然這個理論證明了「幾乎是對稱的」奈許平衡存在，但是這個結果並沒有說明「策略」本質以及它會對 Tangle 的整體運作產生什麼樣的影響。由於系統的複雜性，我們必須轉向計算機模擬來分析這些重點。

在幾個星期的時間裡，Tangle 的模擬運行在一台 Intel Xeon 12 core 3.20 Ghz 的處理器上，測試的樣本大約為 50,000 個交易 (transactions)。**參數的變化與新交易的到達率 λ 有關，成本 (cost)（類似於交易確認所需的平均時間的變量）。該交易的「隨機性」α 為預設的隨機遊走 (random walks) tip selection 演算法。網路傳播延遲 h，自私節點的百分比 γ .** 通過這些模擬，我們能夠憑經驗找到特定「策略」的平衡點，測試驗證並公開他們，即使大部分節點選擇了「貪婪」的 tip selection 策略，他們也沒有因為「自私」而獲得更多的利益。此外，我們也呈現，非「自私」的節點，使用預設的 tip selection 策略，不會因「貪婪節點」的存在而顯著地損失效率。

首先，我們假設「自私節點」選擇介於「預設」的 tip selection 策略 (論文中的 S₀)，與特定「優化」的策略(論文中的 S₁)的比例是固定的 γ. 其餘節點將無法選擇策略，他們將永遠採用策略S₀. 這樣的混合策略遊戲將相當於第二種遊戲規則，其中「貪婪節點」的一部分θ將選擇策略S₁，其餘的「自私節點」將選擇策略S₀。為了簡化，從現在開始，我們正在考慮這個替代遊戲。那麼，我們想問：在這些「自私節點」中，有多少人會根據自己的意願選擇預設的 tip selection 策略？**那麼這個比例當然是在選擇預設策略的「成本」等於選擇優化策略的成本的時候，也就是說，沒有自私的玩家可以通過偏離他自己的策略來獲得任何東西。 我們把這一點稱為奈許平衡。**

在一個給定的系統中（這意味著，給定的λ/h和α），節點的成本將僅取決於 p：基於 S₁ tip selection 策略下發起的交易比例。（注意，如果我們在系統中有自私節點的百分比γ，並且這些節點的百分比θ選擇策略 S₁，我們將具有p =γθ）。所以，當我們談論找到奈許平衡時，即使我們談論的是θ的值 - 也就是與「貪婪節點」策略有關的變量 - 我們必須探索和研究「成本」在p上的變化。 然後，我們將這個百分比 p「轉化」為變量θ。

有三種可能的結果：

1. 對於 p 所有可能的值，「預設的策略」總是比較好的，在這種情況下，所有「自私的節點」都會選擇預設策略（即θ= 0）。
2. 對於 p 所有可能的值，「優化的策略」總是比較好的，在這種情況下，所有「自私的節點」都會選擇優化策略（即θ= 1）。
3. 如果以上兩個選項均不成立，**則「預設策略」將等於特定點 p 處的「優化策略」。** 在這個 p（實際上，與這個p相關的θ），系統的奈許平衡將被找到。

對於以下圖形（圖1），預設的 tip selection 策略在模擬中具有高度的隨機性（α= 0.01）。此模擬運行兩個新交易的到達率（λ= 25和λ= 50）。現在我們試問：上述的三種可能的情況，何者為真？「自私節點」總是選擇預設的策略嗎？或者他們總是選擇「優化策略」？還是只有一部分的節點選擇一個策略而不是另一個呢？在這個描述的情況下，「預設策略」的「成本」與「優化策略」的「成本」相交。比例上使用策略 S₁ 的節點，交點大概在：對於λ= 25 大致為 p = 0.07，對於λ= 50 大約為 p = 0.12。現在這些百分比必須轉化為θ，那裡將是奈許平衡點。 為此，我們將使用兩個不同的例子來分析λ= 25 的數據，這將導致我們得到這個問題的兩個可能的結果。

圖1：S₀ 是「預設策略」，S₁ 是「優化策略」。 p 是選擇「優化策略」的「自私節點」的比例。 奈許平衡（Nash Equilibrium）是線（兩個交易匯率λ）相交的地方。

1. 假設我們有一個百分比γ= 0.5 的節點表現自私。 根據策略 S₁，已發行交易的最大可能百分比是多少？ 顯然，它是 0.5，因為「非貪婪節點」不能選擇策略 S₁。 所以，可能的 p 將是 0≤p≤0.5。 現在，為了在 P = 0.07 的策略 S₁ 下獲得已發行交易的百分比，我們必須有θ= 0.14。 所以，這將是奈許平衡。

2. 現在假設我們有一個百分比 γ= 0.05 的「表現自私的節點」。 根據策略 S₁，已發行交易的最高百分比是多少？ 顯然，由於另一個例子的相同原因，它是0.05。 因此，可能的 p 將是0≤p≤0.05，這意味著在這種情況下，對於所有可能的 p 值，我們總是會有一個「優化的策略」，其成本較小。 所以，所有自私的節點都會選擇「優化策略」（即θ= 1）。

總結一下，如果策略 S₁ 下節點的成本等於策略 S₀ 下 p = p 時的節點成本，則奈許均衡將在 θ= min（1，p /γ）。這個應用的訊息透露出可能應用預設的策略（在賽局理論中）的算法改進。如果我們將當前預設的 tip selection 算法改變為使用 S₁ 時間百分比為 P 的算法，而將剩餘時間改為 S₀，由於「自私節點」也趨於平衡時的那個點，所以「自私節點」在一切都偏離了預設的策略。

**既然我們已經找到了慨許均衡，那麼問題仍然沒有得到解答：「自私策略」的存在會給整個系統的整體運作帶來多大的代價？ 「非自私的節點」是否會以一種有意義的方式受到損害（與沒有自私的節點相比）**

下圖（圖2）顯示了「自私節點」在「預設策略」之後對節點施加的平均成本增加。設 W（p）為圖1所示的「非貪婪節點成本」。成本增加按（W（p）-W（0））/ W（0）計算，所以成本增加的百分比 p 在「自私交易」中的「非自私節點交易」，還有當「沒有自私的交易」時，一個「非自私的節點的成本」，是不同的。如圖所示，對所發現的「非貪婪節點」施加的平均「成本」增加實際上是負的，**意味著平均而言，「自私節點」的存在不會對低α狀態的其他節點造成傷害。**

圖2 - 由於存在「自私節點」而導致的「非自私節點成本增加」，對於幾個α和λ

請注意，上述結果不一定適用於更高的α。 此外，我們並不是在這裡聲稱，「自私的節點」總是幫助「非自私的節點」，因為我們只是分析平均數，而不是節點成本的所有分佈。例如，廣泛的分佈（意味著一些節點「成本」很低，其他節點「成本」很高）可能會擾亂系統的功能。 因此，在進一步的研究中應該對這個問題進行更深入的分析。

此外，我們證明了「貪婪節點」在「非貪婪節點」上的收益在經濟上不具有經濟吸引力（注意在圖3中，在這種情況下，最大可能獲得的收益有點超過10％） 成本，這意味著與簡單地遵循非自私節點的預設選擇算法相比，自私行為的收益是小的（或者甚至是負的）。另外，我們沒有考慮到貪婪的「社會成本」，因為當一個節點被看作自私的時候，其他節點可以避開他，這意謂著，長遠看來，這樣的節點有可能會被 Tangle 網路屏蔽 (banned)，即使沒有人強迫其他節點這樣做。

圖3：貪婪策略 S₁ 對預設策略 S₀ 的增益，對於α= 0.01，以百分比表示。 奈許均衡是 δ= 0 的地方。

綜上所述，本研究的初步結果證實了作者在「貪婪節點」的存在下如何演化的一些直覺。進一步的研究將包含貪婪的 tip selection 策略可能擴大的空間，運行 ML 和 AI 技術的模擬，並繼續優化預設的 tip selection 演算法，使其成為自私和非自私節點的最佳策略。