The Worst-Case Efficiency of Cost Sharing Methods in Resource Allocation Games
The Worst-Case Efficiency of Cost Sharing Methods in Resource Allocation Games
复制标题
资源分配博弈中成本分摊方法的最坏情况效率
作者：
T. Harks;K. Miller
资源分配问题在交通网络、电信网络和经济等许多应用中发挥着关键作用。在大多数应用中，资源的分配是由有限数量的独立参与者决定的，每个参与者优化一个单独的目标函数。在所有这些应用程序中的一个重要问题是自私的资源分配所造成的次优程度。我们考虑了资源分配博弈中成本分担方法的最坏情况下的效率，即纳什均衡的最小保证盈余与最大盈余之比。我们的主要技术成果是效率损失的上限，这取决于类的允许成本函数和类的允许成本分摊方法。我们通过评估三种著名的成本分摊方法（增量成本分摊、边际成本定价和平均成本分摊）在最坏情况下的效率损失来证明这一界限的威力。
Resource allocation problems play a key role in many applications, including traffic networks, telecommunication networks, and economics. In most applications, the allocation of resources is determined by a finite number of independent players, each optimizing an individual objective function. An important question in all these applications is the degree of suboptimality caused by selfish resource allocation. We consider the worst-case efficiency of cost sharing methods in resource allocation games in terms of the ratio of the minimum guaranteed surplus of a Nash equilibrium and the maximal surplus. Our main technical result is an upper bound on the efficiency loss that depends on the class of allowable cost functions and the class of allowable cost sharing methods. We demonstrate the power of this bound by evaluating the worst-case efficiency loss for three well-known cost sharing methods: incremental cost sharing, marginal cost pricing, and average cost sharing.