Approximation algorithms reading group

http://www.math.uwaterloo.ca/~cswamy/papers/scheduling-journ.pdf

Title: Truthful Mechanism Design for Multi-Dimensional Scheduling via Cycle Monotonicity
Authors: Ron Lavi and Chaitanya Swamy

EC07

Abstract (of the paper):

We consider the problem of makespan minimization on m unrelated machines in the con-
text of algorithmic mechanism design, where the machines are the strategic players. This is a
multidimensional scheduling domain, and the only known positive results for makespan mini-
mization in such a domain are O(m)-approximation truthful mechanisms [30, 28]. We study a
well-motivated special case of this problem, where the processing time of a job on each machine
may either be low or high, and the low and high values are public and job-dependent. This
preserves the multidimensionality of the domain, and generalizes the restricted-machines (i.e.,
{pj ,
}) setting in scheduling. We give a general technique to convert any c-approximation al-
gorithm to a 3c-approximation truthful-in-expectation mechanism. This is one of the few known
results that shows how to export approximation algorithms for a multidimensional problem into
truthful mechanisms in a black-box fashion. When the low and high values are the same for all
jobs, we devise a deterministic 2-approximation truthful mechanism. These are the first truthful
mechanisms with non-trivial performance guarantees for a multidimensional scheduling domain.
Our constructions are novel in two respects. First, we do not utilize or rely on explicit
price definitions to prove truthfulness; instead we design algorithms that satisfy cycle mono-
tonicity. Cycle monotonicity [31] is a necessary and sufficient condition for truthfulness that is
a generalization of value monotonicity for multidimensional domains. However, whereas value
monotonicity has been used extensively and successfully to design truthful mechanisms in single-
dimensional domains, ours is the first work that leverages cycle monotonicity in the multidi-
mensional setting. Second, our randomized mechanisms are obtained by first constructing a
fractional truthful mechanism for a fractional relaxation of the problem, and then converting it
into a truthful-in-expectation mechanism. This builds upon a technique of [23], and shows the
usefulness of fractional mechanisms in truthful mechanism design.