Games and mechanism design in machine scheduling - an introduction

Birgit Heydenreich, Rudolf Müller, Marc Jochen Uetz

Research output: Contribution to journalArticleAcademicpeer-review

55 Citations (Scopus)


We survey different models, techniques, and some recent results to tackle machine scheduling problems within a distributed setting. In traditional optimization, a central authority is asked to solve a (computationally hard) optimization problem. In contrast, in distributed settings there are several agents, possibly equipped with private information that is not publicly known, and these agents must interact to derive a solution to the problem. Usually the agents have their individual preferences, which induces them to behave strategically to manipulate the resulting solution. Nevertheless, one is often interested in the global performance of such systems. The analysis of such distributed settings requires techniques from classical optimization, game theory, and economic theory. The paper therefore briefly introduces the most important of the underlying concepts and gives a selection of typical research questions and recent results, focusing on applications to machine scheduling problems. This includes the study of the so-called price of anarchy for settings where the agents do not possess private information, as well as the design and analysis of (truthful) mechanisms in settings where the agents do possess private information.
Original languageUndefined
Pages (from-to)437-454
Number of pages18
JournalProduction and operations management
Issue number4
Publication statusPublished - Aug 2007


  • EWI-11571
  • IR-62055
  • METIS-247087

Cite this