Title: Randomized Truthful Mechanisms for Scheduling Unrelated Machines
Speaker:  Pin Yan LU
Tsinghua University


Date: Friday, May 2, 2008
Time 11:00-12:00PM
Venue: Room 3501, HKUST

Abstract:
In this talk, we consider randomized truthful mechanisms for scheduling
tasks to unrelated machines, where each machine is controlled by a selfish
player. Most previous work on this topic focused on a special case,
scheduling two machines, for which the best approximation ratio is 1.75 and
the best lower bound is 1.5. For this case, we give a unified
framework for designing universally truthful mechanisms, which includes all
the known mechanisms, and also a tight analysis method of their
approximation ratios. Based on this, we give an improved randomized truthful
mechanism, whose approximation ratio is 1.5963. For the general case, when
there are m machines, the only known technique is to obtain a 
$\frac {\gammam}{2}$-approximation truthful mechanism by generalizing a
$\gamma$-approximation truthful mechanism for two machines. There is a
barrier of 0.75m for this technique due to the lower bound of 1.5 for two
machines. We break this 0.75m barrier by a new designing! technique,
rounding a fractional solution. We propose a randomized
truthful-in-expectation mechanism that achieves approximation of (m+5)/2,
for m machines.

For the lower bound side, we focus on an interesting family of mechanisms,
task independent truthful mechanisms. We prove a lower bound of 11/7 for two
machines and a lower bound of (m+1)/2 for m machines with respect to this
family. They almost match our upper bounds in both cases.

This talk is based on joint work with Changyuan Yu.