Elias Koutsoupias:

**Scheduling without payments.** In

*SAGT* 2011. To appear.

### 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.
### Bib

@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}
}