Games and mechanism design in machine scheduling – an introduction

Games and mechanism design in machine scheduling – an introduction

0.00 Avg rating0 Votes
Article ID: iaor20082360
Country: United States
Volume: 16
Issue: 4
Start Page Number: 437
End Page Number: 454
Publication Date: Jan 2007
Journal: Production and Operations Management
Authors: , ,
Keywords: scheduling, game theory
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.

Reviews

Required fields are marked *. Your email address will not be published.