Games and mechanism design in machine scheduling - an introduction

Heydenreich, B. and Müller, R. and Uetz, M.J. (2007) Games and mechanism design in machine scheduling - an introduction. Production and Operations Management, 16 (4). pp. 437-454. ISSN 1059-1478

PDF
Restricted to UT campus only: Request a copy
320Kb

Abstract:	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.
Item Type:	Article
Faculty:	Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:	Discrete Mathematics and Mathematical Programming (DMMP)
Link to this item:	http://purl.utwente.nl/publications/62055
Official URL:	http://www.atypon-link.com/POMS/loi/ijop
Export this item as:	BibTeX EndNote HTML Citation Reference Manager

Show download statistics for this publication

Repository Staff Only: item control page

Metis ID: 247087