DMMP Seminar

Jasper de Jong— Decentralized Mechanisms for Throughput Scheduling: Subgame Perfect Equilibria and Deal-Proof Equilibria

We study models for throughput scheduling in a decentralized setting. In throughput scheduling, we have a set of jobs j with values w_j, processing times p_ij on machine i, release dates r_j and deadlines d_j, to be processed non-preemptively on a set of unrelated machines. The goal is to maximize the total value of jobs finished within their time window [r_j,d_j]. We are interested in decentralized mechanisms where the servers act selfishly according to some given, simple protocol. We show that restricting our attention to subgame perfect equilibria (as opposed to Nash equilibria) decreases the price of decentralization. Also, we show that allowing players to trade jobs for utility improves the price of anarchy only marginally.