Mechanism design for machine scheduling problems: classification and literature overview

Dominik Kress (), Sebastian Meiswinkel () and Erwin Pesch ()
Additional contact information
Dominik Kress: University of Siegen
Sebastian Meiswinkel: University of Siegen
Erwin Pesch: University of Siegen

OR Spectrum: Quantitative Approaches in Management, 2018, vol. 40, issue 3, No 1, 583-611

Abstract: Abstract This paper provides a literature overview on (direct revelation) algorithmic mechanism design in the context of machine scheduling problems. Here, one takes a game-theoretic perspective and assumes that part of the relevant data of the machine scheduling problem is private information of selfish players (usually machines or jobs) who may try to influence the solution determined by the scheduling algorithm by submitting false data. A central planner is in charge of controlling and designing the algorithm and a rewarding scheme that defines payments among planner and players based on the submitted data. The planner may, for example, want to design algorithm and payments such that reporting the true data always maximizes the utility functions of rationally acting players, because this enables the planner to generate fair solutions with respect to some social criterion that considers the interests of all players. We review the categories and characterizing problem features of machine scheduling settings in the algorithmic mechanism design literature and extend the widely accepted classification scheme of Graham et al. (Ann Discrete Math 5:287–326, 1979) for scheduling problems to include aspects relating to mechanism design. Based on this hierarchical scheme, we give a systematic overview of recent contributions in this field of research.

Keywords: Algorithmic mechanism design; Machine scheduling; Game theory; Incentive compatibility (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
http://link.springer.com/10.1007/s00291-018-0512-8 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:orspec:v:40:y:2018:i:3:d:10.1007_s00291-018-0512-8

Ordering information: This journal article can be ordered from
http://www.springer. ... research/journal/291

DOI: 10.1007/s00291-018-0512-8

Access Statistics for this article

OR Spectrum: Quantitative Approaches in Management is currently edited by Rainer Kolisch

More articles in OR Spectrum: Quantitative Approaches in Management from Springer, Gesellschaft für Operations Research e.V.
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().