2013/05/02 by Shuchi Chawla, Chawla, Shuchi, Jason D. Hartline +5
Computer Science · Decision Sciences · #Auction Theory and Applications #Blockchain Technology Applications and Security #Computer Science and Game Theory (cs.GT) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1305.0597
openalex publication_date 2013/05/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the makespan minimization problem with unrelated selfish machines under the assumption that job sizes are stochastic. We design simple truthful mechanisms that under various distributional assumptions provide constant and sublogarithmic approximations to expected makespan. Our mechanisms are prior-independent in that they do not rely on knowledge of the job size distributions. Prior-independent approximation mechanisms have been previously studied for the objective of revenue maximization [Dhangwatnotai, Roughgarden and Yan'10, Devanur, Hartline, Karlin and Nguyen'11, Roughgarden, Talgam-Cohen and Yan'12]. In contrast to our results, in prior-free settings no truthful anonymous deterministic mechanism for the makespan objective can provide a sublinear approximation [Ashlagi, Dobzinski and Lavi'09].