Tight bounds on the weak price of anarchy for the randomized externality policy in scheduling games with multi-job players
研究了多作业玩家调度博弈中的弱均衡，提出随机外部性策略，并给出该策略下弱无政府价格的紧上界为1+黄金比例，证明该界是最优的。
Most research on scheduling games assumes a single-job model, where each job can be seen as a distinct player. Every player decides to assign her job to a machine to minimize her own completion time according to a local policy for ordering jobs on a machine. The price of anarchy as a measure of the overall performance is defined as the ratio between the social cost of the worst equilibrium and the optimal social cost. A common social cost is the sum of all weighted completion times. In this article, we study multi-job scheduling games, where each player owns several jobs and aims to minimize the sum of weighted completion times of her jobs. We focus on weak equilibria for multi-job scheduling games, where each player has no incentive to move any single job from its set of jobs, with the randomized externality policy that we propose and give the tight (pure, mixed, correlated, and coarse) weak price-of-anarchy upper bound of 1+ϕ, where ϕ is the golden ratio. Note that this bound is the best possible given the lower bound of 1+ϕ for “prompt policies” in the previous work of Abed et al., which include preemptive policies and randomized policies. Finally, we supplement the main result with the existence and implementation of such a policy on each machine.