Mechanism Design for Online Real-Time SchedulingRyan Porter∗Computer Science DepartmentStanford UniversityStanford, CA [email protected] the problem of online real-time scheduling of jobs on asingle processor, previous work presents matching upper andlower bounds on the competitive ratio that can be achievedby a deterministic algorithm. However, these results onlyapply to the non-strategic setting in which the jobs are re-leased directly to the algorithm. Motivated by emergingareas such as grid computing, we instead consider this prob-lem in an economic setting, in which each job is released toa separate, self-interested agent. The agent can then delayreleasing the job to the algorithm, inflate its length, and de-clare an arbitrary value and deadline for the job, while thecenter determines not only the schedule, but the paymentof each agent. For the resulting mechanism design problem(in which we also slightly strengthen an assumption fromthe non-strategic setting), we present a mechanism that ad-dresses each incentive issue, while only increasing the com-petitive ratio by one. We then show a matching lower boundfor deterministic mechanisms that never pay the agents.Categories and Subject DescriptorsI.2.11 [Artificial Intelligence]: Distributed Artificial In-telligence—Multiagent systems;J.4[Social and Behav-ioral Sciences]: Economics; F.1.2 [Computation by Ab-stract Devices]: Modes of Computation—Online compu-tationGeneral TermsAlgorithms, Economics, Design, TheoryKeywordsMechanism Design, Game Theory, Online Algorithms,Scheduling∗The author would like to acknowledge Yoav Shoham for hisinfluential comments on drafts of the paper, and Yossi Azarfor a useful discussion. This work was supported in part byDARPA grant F30602-00-2-0598.Permission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies arenot made or distributed for profit or commercial advantage and that copiesbear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee.EC’04, May 17–20, 2004, New York, New York, USA.Copyright 2004 ACM 1-58113-711-0/04/0005 ...$5.00.1. INTRODUCTIONWe consider the problem of online scheduling of jobs ona single processor. Each job is characterized by a releasetime, a deadline, a processing time, and a value for successfulcompletion by its deadline. The objective is to maximize thesum of the values of the jobs completed by their respectivedeadlines. The key challenge in this online setting is thatthe schedule must be constructed in real-time, even thoughnothing is known about a job until its release time.Competitive analysis [6, 10], with its roots in [12], is awell-studied approach for analyzing online algorithms bycomparing them against the optimal offline algorithm, whichhas full knowledge of the input at the beginning of its exe-cution. One interpretation of this approach is as a game be-tween the designer of the online algorithm and an adversary.First, the designer selects the online algorithm. Then, theadversary observes the algorithm and selects the sequence ofjobs that maximizes the competitive ratio: the ratio of thevalue of the jobs completed by an optimal offline algorithmto the value of those completed by the online algorithm.Two papers paint a complete picture in terms of com-petitive analysis for this setting, in which the algorithm isassumed to know k, the maximum ratio between the valuedensities (value divided by processing time) of any two jobs.For k = 1, [4] presents a 4-competitive algorithm, and provesthat this is a lower bound on the competitive ratio for de-terministic algorithms. The same paper also generalizes thelower bound to (1 +√k)2for any k ≥ 1, and [15] thenpresents a matching (1 +√k)2-competitive algorithm.The setting addressed by these papers is completely non-strategic, and the algorithm is assumed to always know thetrue characteristics of each job upon its release. However,in domains such as grid computing (see, for example, [7,8]) this assumption is invalid, because “buyers” of processortime choose when and how to submit their jobs. Further-more, “sellers” not only schedule jobs but also determinethe amount that they charge buyers, an issue not addressedin the non-strategic setting.Thus, we consider an extension of the setting in whicheach job is owned by a separate, self-interested agent. In-stead of being released to the algorithm, each job is nowreleased only to its owning agent. Each agent now has fourdifferent ways in which it can manipulate the algorithm: itdecides when to submit the job to the algorithm after thetrue release time, it can artificially inflate the length of thejob, and it can declare an arbitrary value and deadline forthe job. Because the agents are self-interested, they willchoose to manipulate the algorithm if doing so will cause61their job to be completed; and, indeed, one can find ex-amples in which agents have incentive to manipulate thealgorithms presented in [4] and [15].The addition of self-interested agents moves the problemfrom the area of algorithm design to that of mechanism de-sign [17], the science of crafting protocols for self-interestedagents. Recent years have seen much activity at the inter-face of computer science and mechanism design (see, e.g.,[9, 18, 19]). In general, a mechanism defines a protocol forinteraction between the agents and the center that culmi-nates with the selection of an outcome. In our setting, amechanism will take as input a job from each agent, and re-turn a schedule for the jobs, and a payment to be made byeach agent to the center. A basic solution concept of mecha-nism design is incentive compatibility, which, in our setting,requires that it is always in each agent’s best interests toimmediately submit its job upon release, and to truthfullydeclare its value, length, and deadline.In order to evaluate a mechanism using competitive anal-ysis, the adversary model must be updated. In the newmodel, the adversary still determines the sequence of jobs,but it is the self-interested agents who determine the ob-served input of the mechanism. Thus, in order to achieve acompetitive ratio of c, an online mechanism must both beincentive compatible, and always achieve at least1cof thevalue that the optimal offline mechanism achieves on thesame