## Jasper de Jong — *Decentralized Throughput Scheduling*

Time: | Wednesday, May 15, 2013, 12:45-13:30 |

Location: | Room 311, Citadel |

Motivated by the organization of distributed service systems, we study models for throughput scheduling in a decentralized setting.
In throughput scheduling, a set of jobs *j* with values *w _{j}*, processing times

*p*on machine

_{ij}*i*, release dates

*r*and deadlines

_{j}*d*, is to be processed non-preemptively on a set of unrelated machines. The goal is to maximize the total value of jobs scheduled within their time window [

_{j}*r*]. While approximation algorithms with different performance guarantees exist for this and related models, we are interested in the situation where subsets of machines are governed by selfish players. We give a universal result that bounds the price of decentralization: Any local α-approximation algorithm, yields Nash equilibria that are at most a factor α+1 away from the global optimum, and this bound is tight. For identical machines, we improve this bound to approximately α+1/2, which is shown to be tight, too. The latter result is obtained by considering subgame perfect equilibria of a corresponding sequential game. We also address some variations of the problem.

_{j},d_{j}