In this paper, we consider undirected network design games with fair cost allocation. We introduce two concepts Potential-Optimal Price of Anarchy (POPoA) and Potential-Optimal Price of Stability (POPoS), where POPoA is the ratio between the worst cost of Nash equilibria with optimal potential and the minimum social cost, and POPoS is the ratio between the best cost of Nash equilibria with optimal potential and the minimum social cost, and show that?The POPoA and POPoS for undirected broadcast games with n players are O(logn ? ? ? ? √ ) .?The POPoA and POPoS for undirected broadcast games with |V| vertices are O(log|V|).?There exists an undirected broadcast game with n players such that POPoA, POPoS=Ω(loglogn ? ? ? ? ? ? √ ) .?There exists an undirected broadcast game with |V| vertices such that POPoA,POPoS?=?Ω(log|V|).
各種検索
サポート
ヘルプ