Abstract
Many challenges in operations research involve optimization. In particular, scheduling treats the optimal planning of tasks. This thesis focuses on machine scheduling models, where a number of tasks, called jobs, need to be scheduled on one or more machines. The outcome is determined by which job is scheduled on which machine and in what order the jobs will be processed by those machines.
Classic optimization models often assume the availability of perfect information and the possibility of centralized control. Algorithmic game theory deals with optimization models, where such assumptions are dropped. This leads to settings where jobs are considered players of a game, that is designed by the optimizer. The rules of such a game, called the mechanism, are sometimes fixed in which case a worstcase analysis of the system performance, called price of anarchy, can be done. If such a mechanism is not fixed, a mechanism can be designed to perform optimally.
This thesis treats several classic scheduling models in different game theoretic settings. First is an analysis of the price of anarchy for the related machines scheduling model with sum of completion times objective and selfish jobs. Both an upper bound and a lower bound are given, as well as a new characterization of optimal solutions.
Second, the optimal mechanism design for the twodimensional scheduling mechanism design problem is treated. While for singledimensional mechanism design it is well known that optimal solutions can be found efficiently for most settings, the knowledge of optimal mechanism design for multidimensional problems is limited. The results from this thesis show that for the scheduling problem with twodimensional private types, the optimal, randomized mechanism can in fact be found efficiently with the use of LPtechniques. Furthermore, the resulting interim allocations can be decomposed into a lottery over deterministic schedules.
While randomized mechanisms can be found efficiently, finding deterministic mechanisms still remains a challenge. This thesis also shows that the use of heuristics based on the socalled type graph is a promising approach toward applying simple, efficient mechanisms.
Original language  Undefined 

Awarding Institution 

Supervisors/Advisors 

Award date  30 Jan 2015 
Place of Publication  Enschede 
Publisher  
Print ISBNs  9789036538275 
DOIs  
Publication status  Published  30 Jan 2015 
Keywords
 IR94264
 EWI25795
 METIS308991
Cite this
Hoeksma, R. P. (2015). Mechanisms for scheduling games with selfish players. Enschede: University of Twente. https://doi.org/10.3990/1.9789036538275