Games and mechanism design in machine scheduling - an introduction


Heydenreich, Birgit and Müller, Rudolf and Uetz, Marc (2007) Games and mechanism design in machine scheduling - an introduction. Production and operations management, 16 (4). pp. 437-454. ISSN 1059-1478

[img] PDF
Restricted to UT campus only
: Request a copy
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
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:
Official URL:
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page

Metis ID: 247087