Jasper de Jong— Decentralized Mechanisms for Throughput Scheduling: Subgame Perfect Equilibria and Deal-Proof Equilibria
|Time:||Wednesday, November 14, 2012, 12:45-13:30|
|Location:||Room 311, Citadel|
We study models for throughput scheduling in a decentralized setting. In throughput scheduling, we have a set of jobs j with values wj, processing times pij on machine i, release dates rj and deadlines dj, 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 [rj,dj]. 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.