THE PRICE OF STABILITY FOR NETWORK DESIGN WITH FAIR COST ALLOCATION

THE PRICE OF STABILITY FOR NETWORK DESIGN WITH FAIR COST ALLOCATION

2004 | ELLIOT ANSHELEVICH, ANIRBAN DASGUPTA, JON KLEINBERG, ÉVA TARDOS, TOM WEXLER, TIM ROUGHGARDEN
The paper "The Price of Stability for Network Design with Fair Cost Allocation" by Elliot Anshelevich, Anirban Dasgupta, Jon Kleinberg, Éva Tardos, Tom Wexler, and Tim Roughgarden explores the quality of Nash equilibria in network design problems, focusing on the ratio of their cost to the optimal network cost, known as the price of stability. The authors study a widely-studied protocol for network cost allocation where each edge's cost is divided equally among users whose connections use it, a scheme derived from the Shapley value. They show that the price of stability for this fair cost allocation is \(O(\log k)\), where \(k\) is the number of users. This means that the best Nash equilibrium solution is within a logarithmic factor of the optimal solution. The paper also discusses the convergence of best-response dynamics, which can take exponential time in the worst case, and provides bounds on the convergence time. Additionally, the authors extend their results to more general settings, such as when users aim to balance network design costs with latencies, and when there are weighted games where user weights are considered. The paper concludes with a discussion on related work and extensions to atomic and non-atomic games.The paper "The Price of Stability for Network Design with Fair Cost Allocation" by Elliot Anshelevich, Anirban Dasgupta, Jon Kleinberg, Éva Tardos, Tom Wexler, and Tim Roughgarden explores the quality of Nash equilibria in network design problems, focusing on the ratio of their cost to the optimal network cost, known as the price of stability. The authors study a widely-studied protocol for network cost allocation where each edge's cost is divided equally among users whose connections use it, a scheme derived from the Shapley value. They show that the price of stability for this fair cost allocation is \(O(\log k)\), where \(k\) is the number of users. This means that the best Nash equilibrium solution is within a logarithmic factor of the optimal solution. The paper also discusses the convergence of best-response dynamics, which can take exponential time in the worst case, and provides bounds on the convergence time. Additionally, the authors extend their results to more general settings, such as when users aim to balance network design costs with latencies, and when there are weighted games where user weights are considered. The paper concludes with a discussion on related work and extensions to atomic and non-atomic games.
Reach us at info@study.space
Understanding The price of stability for network design with fair cost allocation