Mechanisms for scheduling games with selfish players

R.P. Hoeksma

Research output: ThesisPhD Thesis - Research UT, graduation UTAcademic

73 Downloads (Pure)

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 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.
Original languageUndefined
Awarding Institution
  • University of Twente
Supervisors/Advisors
  • Uetz, Marc Jochen, Supervisor
Award date30 Jan 2015
Place of PublicationEnschede
Publisher
Print ISBNs978-90-365-3827-5
DOIs
Publication statusPublished - 30 Jan 2015

Keywords

  • IR-94264
  • EWI-25795
  • METIS-308991

Cite this

Hoeksma, R.P.. / Mechanisms for scheduling games with selfish players. Enschede : University of Twente, 2015. 94 p.
@phdthesis{913576bea0064658bd41d5c01a7cd679,
title = "Mechanisms for scheduling games with selfish players",
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 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.",
keywords = "IR-94264, EWI-25795, METIS-308991",
author = "R.P. Hoeksma",
year = "2015",
month = "1",
day = "30",
doi = "10.3990/1.9789036538275",
language = "Undefined",
isbn = "978-90-365-3827-5",
publisher = "University of Twente",
address = "Netherlands",
school = "University of Twente",

}

Mechanisms for scheduling games with selfish players. / Hoeksma, R.P.

Enschede : University of Twente, 2015. 94 p.

Research output: ThesisPhD Thesis - Research UT, graduation UTAcademic

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 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.

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 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.

KW - IR-94264

KW - EWI-25795

KW - METIS-308991

U2 - 10.3990/1.9789036538275

DO - 10.3990/1.9789036538275

M3 - PhD Thesis - Research UT, graduation UT

SN - 978-90-365-3827-5

PB - University of Twente

CY - Enschede

ER -