Mechanism design for online real-time scheduling

ABSTRACT

For the problem of online real-time scheduling of jobs on a single processor, previous work presents matching upper and lower bounds on the competitive ratio that can be achieved by a deterministic algorithm. However, these results only apply to the non-strategic setting in which the jobs are released directly to the algorithm. Motivated by emerging areas such as grid computing, we instead consider this problem in an economic setting, in which each job is released to a separate, self-interested agent. The agent can then delay releasing the job to the algorithm, inflate its length, and declare an arbitrary value and deadline for the job, while the center determines not only the schedule, but the payment of each agent. For the resulting mechanism design problem (in which we also slightly strengthen an assumption from the non-strategic setting), we present a mechanism that addresses each incentive issue, while only increasing the competitive ratio by one. We then show a matching lower bound for deterministic mechanisms that never pay the agents.

REFERENCES

• 1: A. Archer, J. Feigenbaum, A. Krishnamurthy, R. Sami, and S. Shenker, Approximation and collusion in multicast cost sharing, Games and Economic Behavior (to appear).
• 2: Baruch Awerbuch , Yossi Azar , Adam Meyerson, Reducing truth-telling online mechanisms to online optimization, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780616]
• 3: Ziv Bar-Yossef , Kirsten Hildrum , Felix Wu, Incentive-compatible online auctions for digital goods, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.964-970, January 06-08, 2002, San Francisco, California
• 4: S. Baruah , G. Koren , D. Mao , B. Mishra , A. Raghunathan , L. Rosier , D. Shasha , F. Wang, On the competitiveness of on-line real-time task scheduling, Real-Time Systems, v.4 n.2, p.125-144, May 1992 [doi>10.1007/BF00365406]
• 5: Avrim Blum , Tuomas Sandholm , Martin Zinkevich, Online algorithms for market clearing, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.971-980, January 06-08, 2002, San Francisco, California
• 6: Allan Borodin , Ran El-Yaniv, Online computation and competitive analysis, Cambridge University Press, New York, NY, 1998
• 7: R. Buyya, D. Abramson, J. Giddy, and H. Stockinger, Economic models for resource management and scheduling in grid computing, The Journal of Concurrency and Computation: Practice and Experience 14 (2002), 1507----1542.
• 8: N. Camiel, S. London, N. Nisan, and O. Regev, The popcorn project: Distributed computation over the internet in java, 6th International World Wide Web Conference, 1997.
• 9: Joan Feigenbaum , Scott Shenker, Distributed algorithmic mechanism design: recent results and future directions, Proceedings of the 6th international workshop on Discrete algorithms and methods for mobile computing and communications, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570810.570812]
• 10: Developments from a June 1996 seminar on Online algorithms: the state of the art, January 1998
• 11: Eric J. Friedman , David C. Parkes, Pricing WiFi at Starbucks: issues in online mechanism design, Proceedings of the 4th ACM conference on Electronic commerce, June 09-12, 2003, San Diego, CA, USA [doi>10.1145/779928.779978]
• 12: R. L. Graham, Bounds for certain multiprocessor anomalies, Bell System Technical Journal 45 (1966), 1563--1581.
• 13: Bala Kalyanasundaram , Kirk Pruhs, Speed is as powerful as clairvoyance, Journal of the ACM (JACM), v.47 n.4, p.617-643, July 2000 [doi>10.1145/347476.347479]
• 14: Chiu-Yuen Koo , Tak-Wah Lam , Tsuen-Wan Ngan , Kunihiko Sadakane , Kar-Keung To, On-line scheduling with tight deadlines, Theoretical Computer Science, v.295 n.1-3, p.251-261, 24 February 2003 [doi>10.1016/S0304-3975(02)00407-3]
• 15: Gilad Koren , Dennis Shasha, D^over: An Optimal On-Line Scheduling Algorithm for Overloaded Uniprocessor Real-Time Systems, SIAM Journal on Computing, v.24 n.2, p.318-339, April 1995 [doi>10.1137/S0097539792236882]
• 16: Ron Lavi , Noam Nisan, Competitive analysis of incentive compatible on-line auctions, Proceedings of the 2nd ACM conference on Electronic commerce, p.233-241, October 17-20, 2000, Minneapolis, Minnesota, United States [doi>10.1145/352871.352897]
• 17: A. Mas-Colell, M. Whinston, and J. Green, Microeconomic theory, Oxford University Press, 1995.
• 18: N. Nisan and A. Ronen, Algorithmic mechanism design, Games and Economic Behavior 35 (2001), 166--196.
• 19: Christos Papadimitriou, Algorithms, games, and the internet, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.749-753, July 2001, Hersonissos, Greece [doi>10.1145/380752.380883]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Multiagent systems

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Online computation

  J. Computer Applications
  J.4 SOCIAL AND BEHAVIORAL SCIENCES
      Subjects: Economics

General Terms:
Algorithms, Design, Economics, Theory

Keywords:
game theory, mechanism design, online algorithms, scheduling