Abstract
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
}
Mechanisms for scheduling games with selfish players. / Hoeksma, R.P.
Enschede : University of Twente, 2015. 94 p.Research output: Thesis › PhD Thesis  Research UT, graduation UT
TY  THES
T1  Mechanisms for scheduling games with selfish players
AU  Hoeksma, R.P.
PY  2015/1/30
Y1  2015/1/30
N2  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.
AB  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.
KW  IR94264
KW  EWI25795
KW  METIS308991
U2  10.3990/1.9789036538275
DO  10.3990/1.9789036538275
M3  PhD Thesis  Research UT, graduation UT
SN  9789036538275
PB  University of Twente
CY  Enschede
ER 