Mechanism Design for Decentralized Online Machine Scheduling

Heydenreich, Birgit and Müller, Rudolf and Uetz, Marc (2010) Mechanism Design for Decentralized Online Machine Scheduling. Operations Research, 58 (2). pp. 445-457. ISSN 0167-6377

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

Abstract:	Traditional optimization models assume a central decision maker who optimizes a global system performance measure. However, problem data is often distributed among several agents, and agents make autonomous decisions. This gives incentives for strategic behavior of agents, possibly leading to suboptimal system performance. Furthermore, in dynamic environments, machines are locally dispersed and administratively independent. Examples are found both in business and engineering applications. We investigate such issues for a parallel machine scheduling model where jobs arrive online over time. Instead of centrally assigning jobs to machines, each machine implements a local sequencing rule and jobs decide for machines themselves. In this context, we introduce the concept of a myopic best-response equilibrium, a concept weaker than the classical dominant strategy equilibrium, but appropriate for online problems. Our main result is a polynomial time, online mechanism that—assuming rational behavior of jobs—results in an equilibrium schedule that is 3.281-competitive with respect to the maximal social welfare. This is only slightly worse than state-of-the-art algorithms with central coordination.
Item Type:	Article
Copyright:	© 2010 INFORMS
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/71282
Official URL:	http://dx.doi.org/10.1287/opre.1090.0732
Export this item as:	BibTeX EndNote HTML Citation Reference Manager

Show download statistics for this publication

Repository Staff Only: item control page