Selfish Load Balancing
Stub. Price of anarchy for scheduling jobs on selfish machines: pure and mixed equilibria on identical and uniformly related machines. (AGT ch. 20)
Load balancing as a special (finite, atomic) case of congestion games: jobs choose machines selfishly to minimize their own completion time. Covers pure-equilibrium existence and quality on identical and uniformly related machines, and the harder mixed-equilibrium analysis on both.
Outline (TODO — flesh out each)
- Pure equilibria for identical machines
- Pure equilibria for uniformly related machines
- Mixed equilibria on identical machines
- Mixed equilibria on uniformly related machines
- Summary and discussion