Truth and Regret in Online Scheduling
Truth and Regret in Online Scheduling
复制标题
网上排班的真相与遗憾
DOI：
10.1145/3033274.3085119
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Rad Niazadeh
中科院分区：
文献类型：
--
作者：
Shuchi Chawla;Nikhil R. Devanur;Janardhan Kulkarni;Rad Niazadeh
我们考虑一个调度问题，云服务提供商有多个单位的资源随着时间的推移。自私的客户端提交作业，每个作业都有到达时间、截止日期、长度和价值。服务提供商的目标是实现一个真实的在线调度机制，以最大限度地提高社会福利的时间表。最近的工作表明，在随机假设下，就业到达，有一个单参数家庭的机制，实现接近最优的社会福利。我们表明，任何这样的家庭接近最优的在线机制，存在一个在线机制，在最坏的情况下，执行以及最好的给定的机制。我们的机制是真实的，只要在给定的家庭中的机制是真实的和及时的，并实现最佳（在恒定因素）的遗憾。我们模拟的问题，对一个家庭的在线调度机制的学习专家的意见。一个主要的挑战是，我们所做的任何调度决策不仅会影响当前步骤的收益，还会影响未来步骤的资源可用性和收益。此外，从一个算法（a.k.a.专家）到另一个算法是具有挑战性的，因为它需要与后者算法的状态同步，也因为它影响算法的激励结构。我们进一步展示了如何使我们的算法适应非透视设置，其中在作业运行完成之前作业长度是未知的。再一次，在这种情况下，我们获得了真实性沿着渐进最优后悔（在多对数因子内）。
We consider a scheduling problem where a cloud service provider has multiple units of a resource available over time. Selfish clients submit jobs, each with an arrival time, deadline, length, and value. The service provider's goal is to implement a truthful online mechanism for scheduling jobs so as to maximize the social welfare of the schedule. Recent work shows that under a stochastic assumption on job arrivals, there is a single-parameter family of mechanisms that achieves near-optimal social welfare. We show that given any such family of near-optimal online mechanisms, there exists an online mechanism that in the worst case performs nearly as well as the best of the given mechanisms. Our mechanism is truthful whenever the mechanisms in the given family are truthful and prompt, and achieves optimal (within constant factors) regret. We model the problem of competing against a family of online scheduling mechanisms as one of learning from expert advice. A primary challenge is that any scheduling decisions we make affect not only the payoff at the current step, but also the resource availability and payoffs in future steps. Furthermore, switching from one algorithm (a.k.a. expert) to another in an online fashion is challenging both because it requires synchronization with the state of the latter algorithm as well as because it affects the incentive structure of the algorithms. We further show how to adapt our algorithm to a non-clairvoyant setting where job lengths are unknown until jobs are run to completion. Once again, in this setting, we obtain truthfulness along with asymptotically optimal regret (within polylogarithmic factors).