A proof of the Nisan-Ronen conjecture

The Nisan-Ronen conjecture, a central problem in algorithmic game theory, states that no truthful mechanism for makespan minimization can achieve an approximation ratio less than n when allocating a set of tasks to n unrelated machines. In this talk, I will discuss a recent proof of this conjecture. The result is based on studying an interesting special class of instances that can be represented by multi-graphs, where vertices represent machines, edges represent tasks, and each task must be allocated to one of its two incident machines.