Scheduling Without Payments
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. We also study the price of anarchy of natural algorithms.
algorithmic game theory mechanism design