不完美監督賽局之分析

Abstract

由具有決策性的人所形成的網路被廣泛運用在經濟學和電腦科學， 其中一個在電腦科學中最熱門的網路拓墣模型由 Febrikant [6] 等人提 出。之後，Mcbride [11] 基於沒有人可以知道整個網路結構的想法，提 出了一個框架去研究在一個網路中，不正確的看法導致的平衡。然 而，不正確的看法如何影響效能目前並沒有人研究。在本篇論文中， 我們考慮 n 位自私的人，每個人建造連結的花費是 α，對於 u 和 v 這 兩個人來說，這彼此的距離為 dist(u, v)，每個人最多可以看到的範圍 是 x。對於每個人來說，他的花費是所有他建造的連結乘上 α 加上他 與其他所有人的距離總和。我們便利用 conjectural PoA 和 conjectural PoS 去分析一個不完美監督賽局的效能。 我們根據不同的 x 和 α，給出了 conjectural PoA/PoS 的範圍。在conjectural PoA 上界的部分，在 x ≥ 2 時，conjectural PoA 是 O(√α);在 conjectural PoA 下界的部分，得到了 x = 1 時，conjectural PoA 是Ω(α);如果 x ≥ 2, α = Θ(n)，可以得到 conjectural PoA 是 Ω(√x n)。而當 x > ⌊2√α⌋ + 1 時，conjectural PoA 會等價於 PoA。我們也得到了當 k ∈ N, k ≥ 5,α <√(k−4)n/2 , 且 x ≥ k + 3 時，conjectural PoA 最大是 k+1。另一方面，除了在 1 < α < 2, x = 1 的情況下，conjectural PoS 會等價於 Fabricant [6] 得到的 PoS。而在 1 < α < 2, x = 1 的情況下， conjectural PoS 會是 1。