Improving the H _k -bound on the price of stability in undirected Shapley network design games
From MaRDI portal
Publication:4924646
Abstract: In this paper we show that the price of stability of Shapley network design games on undirected graphs with k players is at most (k^3(k+1)/2-k^2) / (1+k^3(k+1)/2-k^2) H_k = (1 - Theta(1/k^4)) H_k, where H_k denotes the k-th harmonic number. This improves on the known upper bound of H_k, which is also valid for directed graphs but for these, in contrast, is tight. Hence, we give the first non-trivial upper bound on the price of stability for undirected Shapley network design games that is valid for an arbitrary number of players. Our bound is proved by analyzing the price of stability restricted to Nash equilibria that minimize the potential function of the game. We also present a game with k=3 players in which such a restricted price of stability is 1.634. This shows that the analysis of Bil`o and Bove (Journal of Interconnection Networks, Volume 12, 2011) is tight. In addition, we give an example for three players that improves the lower bound on the (unrestricted) price of stability to 1.571.
Recommendations
- Improving the \(H_k\)-bound on the price of stability in undirected Shapley network design games
- An \(O(\frac{\log n}{\log \log n})\) upper bound on the price of stability for undirected Shapley network design games
- An \(H _{n/2}\) upper bound on the price of stability of undirected network design games
- On the price of stability for undirected network design
- Improved lower bounds on the price of stability of undirected network design games
Cited in
(10)- Designing cost-sharing methods for Bayesian games
- Improved bounds on equilibria solutions in the network design game
- The price of stability for undirected broadcast network design with fair cost allocation is constant
- Improved lower bounds on the price of stability of undirected network design games
- An \(H _{n/2}\) upper bound on the price of stability of undirected network design games
- Improved lower bounds on the price of stability of undirected network design games
- Multicast network design game on a ring
- Improving the \(H_k\)-bound on the price of stability in undirected Shapley network design games
- Designing networks with good equilibria under uncertainty
- An \(O(\frac{\log n}{\log \log n})\) upper bound on the price of stability for undirected Shapley network design games
This page was built for publication: Improving the \(H _{k }\)-bound on the price of stability in undirected Shapley network design games
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4924646)
