id: 05965650
dt: a
an: 05965650
au: Koutsoupias, Elias
ti: Scheduling without payments.
so: Persiano, Giuseppe (ed.), Algorithmic game theory. 4th international
    symposium, SAGT 2011, Amalfi, Italy, October 17‒19, 2011.
    Proceedings. Berlin: Springer (ISBN 978-3-642-24828-3/pbk). Lecture
    Notes in Computer Science 6982, 143-153 (2011).
py: 2011
pu: Berlin: Springer
la: EN
cc: 
ut: 
ci: 
li: doi:10.1007/978-3-642-24829-0_14
ab: Summary: 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 $t _{ij }$, 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 $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.
rv: