Stackelberg scheduling strategies
Stackelberg scheduling strategies
复制标题
DOI：
10.1145/380752.380783
复制
发表时间：
2001-07
期刊：
影响因子：
--
通讯作者：
Tim Roughgarden
中科院分区：
文献类型：
--
作者：
Tim Roughgarden
我们研究了自私的非合作用户共享的系统的问题，我们考虑了在一组共享机器上的调整作业的具体设置，该机器具有负载依赖的延迟功能，以指定完成工作所需的时间系统绩效按系统的延迟进行，根据个人用户的自私兴趣（他们希望最大程度地减少他们自己的工作经历的延迟），通常会导致次优的系统性能。是“自私控制”和“集中控制”的工作的混合物；我们以最好的方式来制定这一目标，作为一个优化的问题，其中一个玩家在这里（在这里，有兴趣优化系统绩效的集中权威）和其余的是追随者（自私的用户）然后，问题是为领导者（EM Stackelberg策略）计算一种策略，该策略以（至少）（至少）最小化系统中的总延迟，我们证明它是NP - 是NP - 很难计算最佳的Stackelberg策略，并更准确地提供可证明的性能的简单策略。工作；在没有中央控制的工作和Stackelberg的策略的情况下，我们也没有结果。
We study the problem of optimizing the performance of a system shared by selfish, noncooperative users. We consider the concrete setting of scheduling jobs on a set of shared machines with load-dependent latency functions specifying the length of time necessary to complete a job; we measure system performance by the total latency of the system. Assigning jobs according to the selfish interests of individual users (who wish to minimize only the latency that their own jobs experience) typically results in suboptimal system performance. However, in many systems of this type there is a mixture of “selfishly controlled” and “centrally controlled” jobs; as the assignment of centrally controlled jobs will influence the subsequent actions by selfish users, we aspire to contain the degradation in system performance due to selfish behavior by scheduling the centrally controlled jobs in the best possible way. We formulate this goal as an optimization problem via Stackelberg games, games in which one player acts a leader (here, the centralized authority interested in optimizing system performance) and the rest as followers (the selfish users). The problem is then to compute a strategy for the leader (a em Stackelberg strategy) that induces the followers to react in a way that (at least approximately) minimizes the total latency in the system. In this paper, we prove that it is NP-hard to compute the optimal Stackelberg strategy and present simple strategies with provable performance guarantees. More precisely, we give a simple algorithm that computes a strategy inducing a job assignment with total latency no more than a constant times that of the optimal assignment of all of the jobs; in the absence of centrally controlled jobs and a Stackelberg strategy, no result of this type is possible. We also prove stronger performance guarantees in the