An $O(\frac{\log n}{\log \log n})$ Upper Bound on the Price of Stability for Undirected Shapley Network Design Games

Abstract

In this paper, we consider the Shapley network design game on undirected networks. In this game, we have an edge weighted undirected network $G(V,E)$ and $n$ selfish players where player $i$ wants to choose a path from source vertex $s_i$ to destination vertex $t_i$. The cost of each edge is equally split among players who pass it. The price of stability is defined as the ratio of the cost of the best Nash equilibrium to that of the optimal solution. We present an $O(\log n/\log \log n)$ upper bound on price of stability for the single sink case, i.e, $t_i=t$ for all $i$.

Cited by in corpus (4)

• Do Capacity Constraints Constrain Coalitions?
• Improving the H_k-Bound on the Price of Stability in Undirected Shapley Network Design Games
• Multicast Network Design Game on a Ring
• On the Price of Stability of Undirected Multicast Games