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

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

2008-12-13

arxiv.org/abs/0812.2567v1

Computer Science

Computer Science and Game Theory

Scientific paper

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$.

Affiliated with

Also associated with

No associations

Rating

An $O({\log n\over \log\log n})$ Upper Bound on the Price of Stability for Undirected Shapley Network Design Games does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with An $O({\log n\over \log\log n})$ Upper Bound on the Price of Stability for Undirected Shapley Network Design Games, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An $O({\log n\over \log\log n})$ Upper Bound on the Price of Stability for Undirected Shapley Network Design Games will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-193908