Scheduling Without Payments
Scheduling Without Payments
复制标题
无需付款即可安排
DOI：
10.1007/s00224-013-9473-0
复制
发表时间：
2011
影响因子：
0.5
通讯作者：
E. Koutsoupias
中科院分区：
文献类型：
--
作者：
E. Koutsoupias
我们考虑无需付费的机制来解决调度不相关机器的问题。具体来说，我们在假设机器（玩家）受其报告约束的情况下考虑期望随机机制的真实性：当机器撒谎并报告任务的值 $\tilde{t}_{ij}$ 而不是实际的 tij 时，如果它获得任务，它将执行 $\tilde{t}_{ij}$ 时间（除非声明的值 $\tilde{t}_{ij}$ 小于实际值 tij，在这种情况下，它将执行时间 tij）。我们的主要技术成果是针对一个任务和n个参与者的最优机制，其近似比率为(n+1)/2。我们还提供了一个匹配的下界，表明没有其他真实的机制可以实现更好的近似比。对于任意数量的任务，这立即分别给出了社会成本和完工时间最小化的近似比率 (n+1)/2 和 n(n+1)/2。我们还研究自然算法无政府状态的代价。
We consider mechanisms without payments for the problem of scheduling unrelated machines. Specifically, we consider truthful in expectation randomized mechanisms under the assumption that a machine (player) is bound by its reports: when a machine lies and reports value $\tilde{t}_{ij}$ for a task instead of the actual one tij, it will execute for time $\tilde{t}_{ij}$ if it gets the task (unless the declared value $\tilde{t}_{ij}$ is less than the actual value tij, in which case, it will execute for time tij). Our main technical result is an optimal mechanism for one task and n players which has approximation ratio (n+1)/2. We also provide a matching lower bound, showing that no other truthful mechanism can achieve a better approximation ratio. This immediately gives an approximation ratio of (n+1)/2 and n(n+1)/2 for social cost and makespan minimization, respectively, for any number of tasks. We also study the price of anarchy of natural algorithms.