Coordination mechanisms for selfish scheduling
Coordination mechanisms for selfish scheduling
复制标题
DOI：
10.1016/j.tcs.2008.12.032
复制
发表时间：
2005-12
期刊：
影响因子：
--
通讯作者：
Nicole Immorlica;Erran L. Li;V. Mirrokni;Andreas S. Schulz
中科院分区：
文献类型：
--
作者：
Nicole Immorlica;Erran L. Li;V. Mirrokni;Andreas S. Schulz
在机器调度中，必须在一组机器上调度一组作业，以使某些全局目标函数（如最大完工时间）最小化。在实践中，作业通常由独立的、自私的代理控制，每个代理选择一台机器进行处理，以最小化（预期的）完成时间。这个场景可以形式化为一个博弈，其中参与者是作业所有者，策略是机器，参与者的负效用是其作业在相应计划中的完成时间。这些博弈的均衡可能导致大于最优的总体完工时间。无政府状态的代价是最坏情况下的均衡最大完工时间与最优最大完工时间之比。在本文中，我们设计和分析调度策略，或协调机制，为机器的目标是最小化相应博弈的无政府状态的代价。研究了四类多处理机调度问题的协调机制，并给出了这些机制的无政府代价的上界和下界。对于所提出的几种机制，我们还证明了系统在线性轮数下收敛到纯策略纳什均衡。最后，我们注意到我们的结果适用于通信网络中出现的几个实际问题。
In machine scheduling, a set of jobs must be scheduled on a set of machines so as to minimize some global objective function, such as the makespan, which we consider in this paper. In practice, jobs are often controlled by independent, selfishly acting agents, which each select a machine for processing that minimizes the (expected) completion time. This scenario can be formalized as a game in which the players are job owners, the strategies are machines, and a player’s disutility is the completion time of its jobs in the corresponding schedule. The equilibria of these games may result in larger-than-optimal overall makespan. The price of anarchy is the ratio of the worst-case equilibrium makespan to the optimal makespan. In this paper, we design and analyze scheduling policies, or coordination mechanisms, for machines which aim to minimize the price of anarchy of the corresponding game. We study coordination mechanisms for four classes of multiprocessor machine scheduling problems and derive upper and lower bounds on the price of anarchy of these mechanisms. For several of the proposed mechanisms, we also prove that the system converges to a pure-strategy Nash equilibrium in a linear number of rounds. Finally, we note that our results are applicable to several practical problems arising in communication networks.