Mechanism Design for Decentralized Online Machine Scheduling

Birgit Heydenreich (), Rudolf Müller and Marc Uetz ()
Additional contact information
Birgit Heydenreich: Department of Quantitative Economics, Maastricht University, 6200 MD Maastricht, The Netherlands
Marc Uetz: Department of Applied Mathematics, University of Twente, 7500 AE Enschede, The Netherlands

Operations Research, 2010, vol. 58, issue 2, 445-457

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.

Keywords: online machine scheduling; total weighted completion time; decentralization; mechanism design; competitive equilibrium (search for similar items in EconPapers)
Date: 2010
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1090.0732 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:58:y:2010:i:2:p:445-457

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().