On the Efficiency of the Proportional Allocation Mechanism for Divisible Resources
On the Efficiency of the Proportional Allocation Mechanism for Divisible Resources
复制标题
论可分割资源比例分配机制的效率
DOI：
10.1007/s00224-016-9701-5
复制
发表时间：
2016
影响因子：
0.5
通讯作者：
Christodoulou G
中科院分区：
文献类型：
--
作者：
Christodoulou G
我们研究了广泛用于分配可分割资源的比例分配机制的效率。每个代理针对每个可分割资源提交出价，并收到与她的出价成比例的分数。我们通过研究完全和不完全信息下诱导博弈的无政府价格（PoA）来量化纳什均衡的低效率。当代理人的估值是凹的时，我们表明贝叶斯纳什均衡可能是任意低效的，这与众所周知的纯均衡 Johari 和 Tsitsiklis 的 4/3 界限形成鲜明对比（Math. Oper. Res.29(3), 407–435 2004）。接下来，当代理人的估值具有次可加性时，我们将 PoA 相对于贝叶斯均衡的上限提高 2，从而概括并加强了格子模估值的先前界限。此外，我们表明这个界限是严格的，不能通过任何简单或无标度机制来改进。然后我们切换到具有预算约束的设置，并且我们显示了相对于粗相关均衡的 PoA 上限的改进。最后，我们证明在多面体环境中，对于纯平衡，PoA 恰好为 2。
We study the efficiency of theproportional allocation mechanismthat is widely used to allocate divisible resources. Each agent submits a bid for each divisible resource and receives a fraction proportional to her bids. We quantify the inefficiency of Nash equilibria by studying the Price of Anarchy (PoA) of the induced game under complete and incomplete information. When agents’ valuations are concave, we show that the Bayesian Nash equilibria can be arbitrarily inefficient, in contrast to the well-known 4/3 bound for pure equilibria Johari and Tsitsiklis (Math. Oper. Res.29(3), 407–435 2004). Next, we upper bound the PoA over Bayesian equilibria by 2 when agents’ valuations are subadditive, generalizing and strengthening previous bounds on lattice submodular valuations. Furthermore, we show that this bound is tight and cannot be improved by anysimpleorscale-freemechanism. Then we switch to settings with budget constraints, and we show an improved upper bound on the PoA over coarse-correlated equilibria. Finally, we prove that the PoA is exactly 2 for pure equilibria in the polyhedral environment.
登录
查看更多内容
DOI：
--
发表时间：
2007
期刊：
ACM Conference on Economics and Computation
影响因子：
--
作者：
T. Nguyen;É. Tardos
通讯作者：
É. Tardos
DOI：
10.1145/2847520
发表时间：
2013-12
期刊：
ACM Trans. Economics and Comput.
影响因子：
--
作者：
G. Christodoulou;Annamária Kovács;A. Sgouritsa;Bo Tang
通讯作者：
G. Christodoulou;Annamária Kovács;A. Sgouritsa;Bo Tang
影响因子：
8.2
作者：
N. Nisan
通讯作者：
N. Nisan
子加法函数
DOI：
--
发表时间：
1950
期刊：
影响因子：
--
作者：
R. Rosenbaum
通讯作者：
R. Rosenbaum
重新审视比例分配机制无政府状态的代价
DOI：
--
发表时间：
2013
期刊：
Workshop on Internet and Network Economics
影响因子：
--
作者：
J. Correa;Andreas S. Schulz;N. Stier
通讯作者：
N. Stier