Tight Bounds for Cost-Sharing in Weighted Congestion Games
Tight Bounds for Cost-Sharing in Weighted Congestion Games
复制标题
加权拥塞博弈中成本分摊的严格界限
DOI：
10.1007/978-3-662-47666-6_50
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Grammateia Kotsialou
中科院分区：
文献类型：
--
作者：
Martin Gairing;K. Kollias;Grammateia Kotsialou
本文研究了加权拥塞博弈中费用分担方法的无政府代价和稳定代价。我们要求我们的成本分摊方法和我们的一组成本函数满足一定的自然条件，我们提出了一般紧价格的无政府状态的界限，这是强大的，适用于一般均衡的概念。然后，我们转向稳定的价格，并证明了一个上限的Shapley值的成本分摊方法，它适用于一般的成本函数集，这是紧在特殊情况下的利益，如有界度多项式。同样对于有界次数多项式，我们以一个令人惊讶的结果结束了这篇论文，表明与Shapley值的轻微偏差对稳定性的代价有巨大的影响。事实上，在这种情况下，稳定的代价变得和无政府状态的代价一样糟糕。
This work studies the price of anarchy and the price of stability of cost-sharing methods in weighted congestion games. We require that our cost-sharing method and our set of cost functions satisfy certain natural conditions and we present general tight price of anarchy bounds, which are robust and apply to general equilibrium concepts. We then turn to the price of stability and prove an upper bound for the Shapley value cost-sharing method, which holds for general sets of cost functions and which is tight in special cases of interest, such as bounded degree polynomials. Also for bounded degree polynomials, we close the paper with a somehow surprising result, showing that a slight deviation from the Shapley value has a huge impact on the price of stability. In fact, for this case, the price of stability becomes as bad as the price of anarchy.
多项式拥塞博弈中的稳定性代价
影响因子：
1.2
作者：
Christodoulou G
通讯作者：
Christodoulou G