Price of Stability in Polynomial Congestion Games
Price of Stability in Polynomial Congestion Games
复制标题
多项式拥塞博弈中的稳定性代价
DOI：
10.1145/2841229
复制
发表时间：
2015
影响因子：
1.2
通讯作者：
Christodoulou G
中科院分区：
文献类型：
--
作者：
Christodoulou G
在过去的十年里，拥堵游戏中的无政府状态(POA)的价格吸引了大量的研究。这导致了对这一概念的透彻理解。相比之下，稳定代价(Pos)是一个同样有趣的概念，但人们对它的理解要少得多。在本文中，我们考虑了具有非负系数和最大度的多项式代价函数的拥堵对策。我们给出了这类对策中POS的匹配界--也就是说，我们的技术提供了任何程度的精确值。对于线性拥塞对策，紧界是已知的。这些界限甚至适用于更严格的支配均衡情况，这种情况可能并不存在。我们给出的分离结果表明，对于具有二次代价函数的拥塞对策，这是不可能的--换句话说，允许存在主导策略均衡的对策子类的POA严格小于一般类的POA。
The price of anarchy (PoA) in congestion games has attracted a lot of research over the past decade. This has resulted in a thorough understanding of this concept. In contrast, the price of stability (PoS), which is an equally interesting concept, is much less understood.In this article, we consider congestion games with polynomial cost functions with nonnegative coefficients and maximum degreed. We give matching bounds for the PoS in such games—that is, our technique provides the exact value for any degreed.For linear congestion games, tight bounds were previously known. Those bounds hold even for the more restricted case of dominant equilibria, which may not exist. We give a separation result showing that this is not possible for congestion games with quadratic cost functions—in other words, the PoA for the subclass of games that admit a dominant strategy equilibrium is strictly smaller than the PoS for the general class.
登录
查看更多内容
提高无向 Shapley 网络设计博弈稳定性价格的 Hk-bound
DOI：
10.1016/j.tcs.2014.10.037
发表时间：
2012
期刊：
Theor. Comput. Sci.
影响因子：
--
作者：
Y. Disser;A. Feldmann;Max Klimm;Matús Mihalák
通讯作者：
Matús Mihalák
无向 Shapley 网络设计游戏稳定性代价的 O(log(n)/log(log(n))) 上限
DOI：
10.1016/j.ipl.2009.04.015
发表时间：
2008
期刊：
ArXiv
影响因子：
--
作者：
Jian Li
通讯作者：
Jian Li
DOI：
10.1007/11786986_53
发表时间：
2006-01-01
期刊：
AUTOMATA, LANGUAGES AND PROGRAMMING, PT 1
影响因子：
--
作者：
Fiat, Amos;Kaplan, Haim;Shabo, Ronen
通讯作者：
Shabo, Ronen
DOI：
10.1007/11561071_8
发表时间：
2005-10
期刊：
--
影响因子：
--
作者：
G. Christodoulou;E. Koutsoupias
通讯作者：
G. Christodoulou;E. Koutsoupias
自私和贪婪负载平衡的严格界限
影响因子：
1.1
作者：
I. Caragiannis;M. Flammini;C. Kaklamanis;P. Kanellopoulos;L. Moscardelli
通讯作者：
L. Moscardelli