Campus Event Calendar
Event Entry
What and Who
A Novel Approach to Improve the Quality of Equilibria of Selfish Scheduling
Weidong Ma
Chinese Academy of Sciences
AG1 Mittagsseminar (own work)
AG 1
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Tuesday, 9 August 2011
13:00
30 Minutes
Warning: Date has changed!
E1 4
024
Saarbrücken
Abstract
Scheduling problem is one of the most important and well studied combinatorial optimization problems. Some recent work studied this problem from a game theoretical point of view; It was assumed that tasks are controlled by selfish agents, i.e., each task has a selfish agent who aims at assigning the task on the machine with smallest load regardless of the overall performance of the underlying system. One of the major concerns is how large the difference in scheduling qualities between the optimal scheduling and selfish scheduling.
In this talk we will present a novel approach to improve the quality of selfish scheduling. We assume that not only are the tasks but the machines managed by selfish agents, and each machine agent could reject a job assigned on it in order to attract and serve a bigger job so that he/she could get more profit. We prove that for the objective of minimizing the makespan on identical machines the price of anarchy (PoA) is less than or equal to 3/2, which is strictly smaller than the PoA of the classical model. We also give a low bound 4/3 on the PoA of our model. In the end, we will discuss how to narrow the 1/6 gap.
Contact
Rob van Stee
--email hidden
passcode not visible
logged in users only
Rob van Stee, 08/02/2011 09:36
Rob van Stee, 07/27/2011 13:41
Rob van Stee, 07/27/2011 11:43 -- Created document.
Rob van Stee, 07/27/2011 13:41
Rob van Stee, 07/27/2011 11:43 -- Created document.