Abstract
This work concerns the mechanism design for
online scheduling in a strategic setting. In this
setting, each job is owned by a self-interested agent
who may misreport the release time, deadline,
length, and value of her job, while we need to
determine not only the schedule of the jobs, but
also the payment of each agent. We focus on the
design of incentive compatible (IC) mechanisms,
and study the maximization of social welfare (i.e.,
the aggregated value of completed jobs) by competitive analysis. We first derive two lower bounds
on the competitive ratio of any deterministic IC
mechanism to characterize the landscape of our
research: one bound is 5, which holds for equallength jobs; the other bound is ?
ln ? + 1 ? o(1),
which holds for unequal-length jobs, where ? is the
maximum ratio between lengths of any two jobs.
We then propose a deterministic IC mechanism and
show that such a simple mechanism works very
well for two models: (1) In the preemption-restart
model, the mechanism can achieve the optimal
competitive ratio of 5 for equal-length jobs and
a near optimal ratio of ( 1
(1?)2 + o(1)) ?
ln ?
for
unequal-length jobs, where 0 < < 1 is a small
constant; (2) In the preemption-resume model, the
mechanism can achieve the optimal competitive
ratio of 5 for equal-length jobs and a near optimal
competitive ratio (within factor 2) for unequallength jobs