DMMP Seminar

Ruben Hoeksma — Price of Anarchy for Machine Scheduling with Selfish Jobs

Time: Wednesday, June 23, 2010, 12:45-13:30
Location: Room 101, Citadel

In algorithmic game theory one of the goals is to let selfishly acting agents make socially good choices. The ratio between the worst selfish solution, the Nash Equilibrium, and the socially optimal solution is called the Price of Anarchy.

For the scheduling game based on the uniformly related machine scheduling problem with average completion time objective, we have polynomial time algorithms for finding both the Nash Equilibrium and the optimal solution of any instance. But it seems to be hard to proof a constant upper bound on the Price of Anarchy. During this talk I will show some of the results we have on this problem. I hope that your input might lead to new insight on how to approach the problem.