The Price of Anarchy of the Proportional Allocation Mechanism Revisited
The Price of Anarchy of the Proportional Allocation Mechanism Revisited
复制标题
重新审视比例分配机制无政府状态的代价
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
N. Stier
中科院分区：
文献类型：
--
作者：
J. Correa;Andreas S. Schulz;N. Stier
我们考虑的比例分配机制，首先研究了凯利1997年在通信网络的拥塞控制算法的上下文中。一个单一的无限可分的资源是要有效地分配给竞争的球员，其个人的效用函数是未知的资源管理器。如果参与者预期他们的出价对资源价格的影响，并且他们的效用函数是凹的，严格增加的和连续可微的，Johari和Tsitsiklis 2004证明了无政府状态的价格是4/3。有人提出的问题是，这个结果与Roughgarden和Tardos 2002的结果之间是否存在关系，Roughgarden和Tardos在2002年的结果中，曾证明了具有仿射线性拥塞函数的非原子自私路由的完全相同的界。我们建立这样的关系，并显示，特别是，效率损失的特点是完全相同的几何量。我们还提出了一个新的变分不等式表征纳什均衡在这种情况下，这使我们能够扩展价格的无政府状态分析的重要类的效用函数，不一定是凹的。
We consider the proportional allocation mechanism first studied by Kelly 1997 in the context of congestion control algorithms for communication networks. A single infinitely divisible resource is to be allocated efficiently to competing players whose individual utility functions are unknown to the resource manager. If players anticipate the effect of their bids on the price of the resource and their utility functions are concave, strictly increasing and continuously differentiable, Johari and Tsitsiklis 2004 proved that the price of anarchy is 4/3. The question was raised whether there is a relationship between this result and that of Roughgarden and Tardos 2002, who had earlier shown exactly the same bound for nonatomic selfish routing with affine-linear congestion functions. We establish such a relationship and show, in particular, that the efficiency loss can be characterized by precisely the same geometric quantity. We also present a new variational inequality characterization of Nash equilibria in this setting, which enables us to extend the price-of-anarchy analysis to important classes of utility functions that are not necessarily concave.