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, α ≥ 1, 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 ≈(α+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.