Mechanisms for scheduling games with selfish players

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 worst-case 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 two-dimensional scheduling mechanism design problem is treated. While for single-dimensional mechanism design it is well known that optimal solutions can be found efficiently for most settings, the knowledge of optimal mechanism design for multi-dimensional problems is limited. The results from this thesis show that for the scheduling problem with two-dimensional private types, the optimal, randomized mechanism can in fact be found efficiently with the use of LP-techniques. 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 so-called type graph is a promising approach toward applying simple, efficient mechanisms.