Stackelberg scheduling strategies

ABSTRACT

We study the problem of optimizing the performance of a system shared by selfish, noncooperative users. We consider the concrete setting of scheduling jobs on a set of shared machines with load-dependent latency functions specifying the length of time necessary to complete a job; we measure system performance by the total latency of the system.Assigning jobs according to the selfish interests of individual users (who wish to minimize only the latency that their own jobs experience) typically results in suboptimal system performance. However, in many systems of this type there is a mixture of “selfishly controlled” and “centrally controlled” jobs; as the assignment of centrally controlled jobs will influence the subsequent actions by selfish users, we aspire to contain the degradation in system performance due to selfish behavior by scheduling the centrally controlled jobs in the best possible way.We formulate this goal as an optimization problem via Stackelberg games, games in which one player acts a leader (here, the centralized authority interested in optimizing system performance) and the rest as followers (the selfish users). The problem is then to compute a strategy for the leader (a em Stackelberg strategy) that induces the followers to react in a way that (at least approximately) minimizes the total latency in the system.In this paper, we prove that it is NP-hard to compute the optimal Stackelberg strategy and present simple strategies with provable performance guarantees. More precisely, we give a simple algorithm that computes a strategy inducing a job assignment with total latency no more than a constant times that of the optimal assignment of all of the jobs; in the absence of centrally controlled jobs and a Stackelberg strategy, no result of this type is possible. We also prove stronger performance guarantees in the

REFERENCES

• 1: A.Bagchi.Stackelber Di .erential Games in Economic Models .Springer-Verlag,1984.
• 2: T.Basar and G.J.O sder.Dynamic Noncooperative Game Theory .SIAM,1999.
• 3: M.Beckmann,C.B.McGuire,and C.B.Winsten. Studies in the Economics of Transportation .Yae University Press,1956.
• 4: Kenneth P. Birman, Building secure and reliable network applications, Manning Publications Co., Greenwich, CT, 1997
• 5: B.Braden,D.C ark,J.Crowcroft,B.Davie, S.Deering,D.Estrin,S.Floyd,V.Jacobson, G.Minsha ,C.Partridge,L.Peterson, K.Ramakrishnan,S.Shenker,J.Wroc awski,and L.Zhang.Recommendations on queue management and congestion avoidance in the Internet.Network Working Group Request for Comments 2309,April 1998.
• 6: J.Case,M.Fedor,M.Scho .stall,and J.Davin.A simple network management protocol.Network Working Group Request for Comments 1067,August 1988.
• 7: Ron Cocchi , Scott Shenker , Deborah Estrin , Lixia Zhang, Pricing in computer networks: motivation, formulation, and example, IEEE/ACM Transactions on Networking (TON), v.1 n.6, p.614-627, Dec. 1993 [doi>10.1109/90.266050]
• 8: S.C.Dafermos and F.T.Sparrow.The tra .c assignment problem for a general network.Journal of Research of the National Bureau of Standards,Series B ,73B(2):91 -118,1969.
• 9: C.Douligeris and R.Mazumdar.Multileve .ow contro of queues.In Proceedin s of the Johns Hopkins Conference on Information Sciences and Systems , page 21,1989.
• 10: C.Douligeris and R.Mazumdar.A game theoretic perspective to .ow control in telecommunication networks.Journal of the Franklin Institute , 329:383 -402,1992.
• 11: Pradeep Dubey, Inefficiency of Nash equilibria, Mathematics of Operations Research, v.11 n.1, p.1-8, Feb. 1986 [doi>10.1287/moor.11.1.1]
• 12: A.A.Economides and J.A.Silvester.Priority load sharing:An approach using Stackelberg games.In Proceedin s of the 28th Annual Al l erton Conference on Communications,Control,and Computing ,pages 674 -683,1990.
• 13: Joan Feigenbaum , Christos Papadimitriou , Scott Shenker, Sharing the cost of muliticast transmissions (preliminary version), Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.218-227, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335332]
• 14: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 15: S. Keshav, An engineering approach to computer networking: ATM networks, the Internet, and the telephone network, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 16: Yannis A. Korilis , Aurel A. Lazar , Ariel Orda, Achieving network optima using Stackelberg routing strategies, IEEE/ACM Transactions on Networking (TON), v.5 n.1, p.161-173, Feb. 1997 [doi>10.1109/90.554730]
• 17: Y.A.Korlis,A.A.Lazar,and A.Orda.Capacity a ocation under noncooperative routing.IEEE Transactions on Automatic Control ,42(3):309 -325, 1997.
• 18: Y.A.Korlis,A.A.Lazar,and A.Orda.Avoiding the Braess paradoxin noncooperative networks.Journal of Applied Probability ,36(1):211 -222,1999.
• 19: E.Koutsoupias and C.Papadimitriou.Worst-case equilibria.In Proceedin s of the 16th Annual Symposium on Theoretical Aspects of Computer Science ,pages 404 -413,1999.
• 20: N.Nisan.A gorithms for sel .sh agents:Mechanism design for distributed computation.In Proceedin s of the 16th Annual Symposium on Theoretical Aspects of Computer Science ,pages 1 -15,1999.
• 21: Noam Nisan , Amir Ronen, Algorithmic mechanism design (extended abstract), Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.129-140, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301287]
• 22: Ariel Orda , Raphael Rom , Nahum Shimkin, Competitive routing in multiuser communication networks, IEEE/ACM Transactions on Networking (TON), v.1 n.5, p.510-521, Oct. 1993 [doi>10.1109/90.251910]
• 23: G.Owen.Game Theory .Academic Press,1995.Third Edition.
• 24: A. L. Peressini , Francis E. Sullivan , J. J. Uhl, Jr., The mathematics of nonlinear programming, Springer-Verlag New York, Inc., New York, NY, 1988
• 25: C.ReVelle and D.Serra.The maximum capture prob em inc uding re ocation.INFOR ,29:130 -138, 1991.
• 26: A.Ronen.Solvin Optimization Problems amon Sel .sh Agents .PhD thesis,Hebrew University of Jerusalem,2000.
• 27: T. Roughgarden , E. Tardos, How bad is selfish routing?, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.93, November 12-14, 2000
• 28: Y.She ..Urban Transportation Networks: Equilibrium Analysis with Mathematical Programming Methods .Prentice-Hall,1985.
• 29: Scott J. Shenker, Making greed work in networks: a game-theoretic analysis of switch service disciplines, IEEE/ACM Transactions on Networking (TON), v.3 n.6, p.819-831, Dec. 1995 [doi>10.1109/90.477727]
• 30: H.von Stackelberg.Marktform und Gleichgewicht . Springer-Verlag,1934.English translation,entitled The Theory of the Market Economy ,published in 1952 by Oxford University Press.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Scheduling

General Terms:
Design, Performance, Theory, Verification