An O (log n/log log n) upper bound on the price of stability for undirected Shapley network design games

被引：31
|
作者：
Li, Jian [1 ]
机构：
[1] Univ Maryland, Dept Comp Sci, College Pk, MD 20742 USA
来源：
INFORMATION PROCESSING LETTERS | 2009年 / 109卷 / 15期
基金：
美国国家科学基金会;
关键词：
Algorithms; Price of stability; Shapley network design game;
D O I：
10.1016/j.ipl.2009.04.015
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
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 low cost 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. (C) 2009 Elsevier B.V. All rights reserved.
引用
收藏
页码：876 / 878
页数：3
相关论文
共 50 条
  • [1] An O(log n log log n) space algorithm for undirected st-connectivity
    Trifonov, Vladimir
    SIAM JOURNAL ON COMPUTING, 2008, 38 (02) : 449 - 483
  • [2] Tree Evaluation Is in Space O(log n• log log n)
    Cook, James
    Mertz, Ian
    PROCEEDINGS OF THE 56TH ANNUAL ACM SYMPOSIUM ON THEORY OF COMPUTING, STOC 2024, 2024, : 1268 - 1278
  • [3] Randomized Mutual Exclusion in O(log N/log log N) RMRs
    Hendler, Danny
    Woelfel, Philipp
    PODC'09: PROCEEDINGS OF THE 2009 ACM SYMPOSIUM ON PRINCIPLES OF DISTRIBUTED COMPUTING, 2009, : 26 - 35
  • [4] Improving the Hk-bound on the price of stability in undirected Shapley network design games
    Disser, Yann
    Feldmann, Andreas Emil
    Klimm, Max
    Mihalak, Matus
    THEORETICAL COMPUTER SCIENCE, 2015, 562 : 557 - 564
  • [5] A Deterministic Construction of Normal Bases With Complexity O(n3 + n log n log(log n) log q)
    Poli, A.
    Journal of Symbolic Computation, 19 (04):
  • [6] ASPACE(O(LOG LOG N)) IS REGULAR
    IWAMA, K
    SIAM JOURNAL ON COMPUTING, 1993, 22 (01) : 136 - 146
  • [7] AN O(N LOG N LOG LOG N) PARALLEL MAXIMUM MATCHING ALGORITHM FOR BIPARTITE GRAPHS
    KIM, T
    CHWA, KY
    INFORMATION PROCESSING LETTERS, 1987, 24 (01) : 15 - 17
  • [8] An O(log n/log log n)-Approximation Algorithm for the Asymmetric Traveling Salesman Problem
    Asadpour, Arash
    Goemans, Michel X.
    Madry, Aleksander
    Gharan, Shayan Oveis
    Saberi, Amin
    OPERATIONS RESEARCH, 2017, 65 (04) : 1043 - 1061
  • [9] An O(log n/log log n)-approximation Algorithm for the Asymmetric Traveling Salesman Problem
    Asadpour, Arash
    Goemans, Michel X.
    Madry, Aleksander
    Gharan, Shayan Oveis
    Saberi, Amin
    PROCEEDINGS OF THE TWENTY-FIRST ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 2010, 135 : 379 - +
  • [10] An Ω(√log log n) lower bound for routing in optical networks
    Goldberg, LA
    Jerrum, M
    Mackenzie, PD
    SIAM JOURNAL ON COMPUTING, 1998, 27 (04) : 1083 - 1098
12345