DMMP Seminar

Jasper de Jong — Decentralized Throughput Scheduling

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_ij on machine i, release dates r_j and deadlines d_j, 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 [r_j,d_j]. 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.