多工玩家排程賽局中的隨機本機政策

Abstract

在排程賽局中，大多數的研究是將每一個等待配置的工作隸屬於一個玩家操控(此稱單工)，每一個玩家會決定將自己的工作 j 移動到哪一個機器 i 上處理，而所有玩家追求個人的加權完工時間最小化。 並且用最壞均衡和最佳解比(the price of anarchy, PoA)衡量該賽局的奈許均衡(Nash equilibrium) 表現優異程度。而在過去的研究中，Richard Cole 已有三種排程策略(policy)的PoA結果，

在此篇研究中，延續Abed 的排程賽局架構，使用多重工作(multi-jobs)排程賽局(此稱多工)，此種架構是將一個玩家同時配屬一至多個工作，在這個架構下，每一個玩家都可以決定同時移動多個工作到新的機器上以獲取自己的完工時間最小化，在多工環境下，我們探討的均衡狀態為弱均衡(weak equilibrium)而非奈許均衡，此種均衡是保證即使在多重工作的架構，最多只會有一個工作可以移動到不同的機器上以降低該工作的完工時間。相較於之前的每個工作各擁有一個玩家的排程賽局，我們使用了多重工作架構及弱均衡設定，並提出一個隨機的排程策略，達到了小於4的最壞均衡和最佳解比。

Most research on scheduling games assumes a single-job model, where each job can be seen as a distinct player. Each 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 thesis, we study multi-job scheduling games, where each player owns several jobs and can move any subset of her jobs arbitrarily to minimize the sum of weighted completion times of her jobs. We analyze weak equilibria for multi-job scheduling games with a randomized local policy and give a price-of-anarchy upper bound less than 4.