Mechanism Design strives to engineer incentives in multiagent systems to improve equilibrium behaviour. But many mechanisms have the drawback that they require full information; in large, decentralized systems, this hampers their implementation.

I will discuss how simple mechanisms, which have access only to local information, can be applied and analyzed in the classical setting of machine scheduling. Here, jobs are selfish agents aiming to minimize their completion time. We consider a number of different “policies”; rules specifying the order in which the jobs assigned to a machine are processed. Smith’s rule, the optimal scheduling rule for a single machine, is the obvious choice. But somewhat counter-intuitively, we demonstrate other policies that perform much better than Smith’s rule and lead to substantially better equilibrium schedules.

These policies will all be analyzed using a common technique: a mapping of the strategy vectors into a carefully chosen inner product space.
Once this structure is in place, the proofs are relatively short and clean. I will also show how the game-theoretic insights translate into an outcome for the pure optimization problem of minimizing the weighted sum of completion times.