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.
展开▼
机译：我们考虑在通信网络的拥塞控制算法的背景下，首先由Kelly（1997）研究的比例分配机制。单个无限可分割的资源将有效地分配给资源管理器未知其效用函数的竞争参与者。如果参与者期望出价对资源价格的影响并且其效用函数是凹的，严格增加的并且是连续可区分的，则Johari和Tsitsiklis（2004）证明无政府状态的价格为4/3。有人提出了这个结果与Roughgarden and Tardos（2002）的关系之间是否存在关系，Roughgarden和Tardos先前已经证明了具有仿射线性拥塞函数的非原子自私路由的界线完全相同。我们建立了这样的关系，并特别表明，效率损失可以由完全相同的几何量来表征。在这种情况下，我们还提出了纳什均衡的新的变分不等式刻画，这使我们能够将无政府状态分析扩展到不一定是凹形的重要效用函数类别。
展开▼
