Ahuva Mu'alem

Gaps and Augmentations in Bayesian Scheduling

The recent resolution of the Nisan--Ronen conjecture~\cite{NR,CKK} establishes that the optimal worst-case approximation ratio of deterministic truthful mechanisms for makespan on m unrelated machines is exactly m. We ask how prior information, Bayesian incentive compatibility (BIC), randomization, and machine-side res...