Friday, 16:15 - 16:40 h, Room: MA 043


Jasper de Jong
Decentralized mechanisms for throughput scheduling


Motivated by the organization of decentralized service systems, we study new models for throughput scheduling. In throughput scheduling, we have a set of jobs i with value wi, processing requirement pi, and deadline di, to be processed non-preemptively on a set of unrelated servers. The goal is to maximize the total value of jobs finished before their deadline. While several approximation algorithms with different performance guarantees exist for this and related models, we are interested in decentralized mechanisms where the servers act selfishly according to some given, simple protocol. We show by simple, combinatorial arguments that, when each server deploys an α-approximation locally, any Nash equilibrium still yields an (α+1)-approximation with respect to the global optimum. This bound is tight, even in the case of related machines, unit weights and unit processing times. For models with identical machines, the bound can be improved to \frac{\sqrt[α]{e}}{\sqrt[α]{e}-1}. Some of our results also extend to online models with corresponding competitive ratios.


Talk 3 of the invited session Fri.3.MA 043
"Analysis of equilibria in noncooperative games" [...]
Cluster 8
"Game theory" [...]


  Today, Ohio Loans Online are legitimate, but there are illegal transactions that are still on the rise. If you have already decided to take Levitra, be sure to consult a doctor, you don't have any contraindications and act strictly due to a prescription.