Elias Koutsoupias / Publications

Abstract

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 $\T t_{ij}$ for a task instead of the actual one $t_{ij}$, it will execute for time $\T t_{ij}$ if it gets the task---unless the declared value $\T t_{ij}$ is less than the actual value $t_{ij}$, in which case, it will execute for time $t_{ij}$. 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.

@string{SAGT11 = {Symposium on Algorithmic Game Theory (SAGT)}}

@inproceedings{Kou11,
  author    = {Elias Koutsoupias},
  title     = {Scheduling without payments},
  booktitle = SAGT,
  month     = {17--19 } # oct, 
  year      = {2011},
  address   = {Salerno - Amalfi Coast, Italy}
}