Advertisement
Published in:
2012 | OriginalPaper | Chapter
Mechanisms for Scheduling with Single-Bit Private Values
Authors : Vincenzo Auletta, George Christodoulou, Paolo Penna
Published in: Algorithmic Game Theory
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We consider randomized mechanisms for multi-dimensional scheduling. Following Lavi and Swamy [10], we study a setting with restrictions on the domain, while still preserving multi-dimensionality. In a sense, our setting is the simplest multi-dimensional setting, where each machine holds privately only a single-bit of information.
We prove a separation between truthful-in-expectation and universally truthful mechanisms for makespan minimization: We first show how to design an optimal truthful-in-expectation mechanism, and then prove lower bounds on the approximation guarantee of universally truthful mechanisms.