More Web Proxy on the site http://driver.im/

Article

Stackelberg scheduling strategies

Author:

Tim RoughgardenAuthors Info & Claims

STOC '01: Proceedings of the thirty-third annual ACM symposium on Theory of computing

Pages 104 - 113

https://doi.org/10.1145/380752.380783

Published: 06 July 2001 Publication History

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.

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]

K.P.Birman.Building Secure and Reliable Network Applications .Manning,1996.]]

Digital Library

[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.]]

Digital Library

[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.]]

Digital Library

[7]

R.Cocchi,S.Shenker,D.Estrin,and L.Zhang. Pricing in computer networks:Motivation, formu ation,and examp e.IEEE/ACM Transactions on Networking,1(6):614-627,1993.]]

Digital Library

[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]

P. Dubey.Ine .ciency of Nash equilibria.Mathematics of Operations Research,11(1):1 -8,1986.]]

[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]

J.Feigenbaum,C.Papadimitriou,and S.Shenker. Sharing the cost of mu ticast transmissions.In Proceedin s of the 32nd Annual ACM Symposium on the Theory of Computing,pages 218 -227,2000.]]

Digital Library

[14]

M.R.Garey and D.S.Johnson.Computers and Intractability:A Guide to the Theory of NP-Completeness .Freeman,1979.]]

Digital Library

[15]

S.Keshav.An Engineerin Approach to Computer Networking .Addison-Wesley,1997.]]

Digital Library

[16]

Y.A.Korlis,A.A.Lazar,and A.Orda.Achieving network optima using Stacke berg routing strategies. IEEE/ACM Transactions on Networking, 5(1):161 -173,1997.]]

Digital Library

[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]

N.Nisan and A.Ronen.Algorithmic mechanism design.In Proceedin s of the 31st Annual ACM Symposium on the Theory of Computin,pages 129 -140,1999.]]

Digital Library

[22]

A.Orda,R.Rom,and N.Shimkin.Competitive routing in multi-user communication networks. IEEE/ACM Transactions on Networkin,1:510 -521, 1993.]]

Digital Library

[23]

G.Owen.Game Theory .Academic Press,1995.Third Edition.]]

[24]

A.L.Peressini,F.E.Sullivan,and J.J.Uhl.The Mathematics of Nonlinear Pro ramming . Springer-Verlag,1988.]]

Digital Library

[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 and E.Tardos.How bad is se .sh routing?In Proceedin s of the 41st Annual Symposium on Foundations of Computer Science, pages 93 -102,2000.Full version availab e at http://www.cs.cornell.edu/timr]]

Digital Library

[28]

Y.She ..Urban Transportation Networks: Equilibrium Analysis with Mathematical Programming Methods .Prentice-Hall,1985.]]

[29]

S.J.Shenker.Making greed work in networks:A game-theoretic analysis of switch service disciplines. IEEE/ACM Transactions on Networking, 3(6):819 -831,1995.]]

Digital Library

[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.]]

Cited By

Han MZhang FChen YKiyavash NMooij J(2024)No-regret learning of nash equilibrium for black-box games via Gaussian processesProceedings of the Fortieth Conference on Uncertainty in Artificial Intelligence10.5555/3702676.3702748(1541-1557)Online publication date: 15-Jul-2024
https://dl.acm.org/doi/10.5555/3702676.3702748
Brown D(2024)PhD Forum: Trust-Aware Routing of Human Drivers to Mitigate Traffic Congestion2024 IEEE International Conference on Smart Computing (SMARTCOMP)10.1109/SMARTCOMP61445.2024.00062(258-259)Online publication date: 29-Jun-2024
https://doi.org/10.1109/SMARTCOMP61445.2024.00062
Brown DNadendla VDas S(2024)TASR: A Novel Trust-Aware Stackelberg Routing Algorithm to Mitigate Traffic Congestion2024 IEEE International Conference on Smart Computing (SMARTCOMP)10.1109/SMARTCOMP61445.2024.00041(150-157)Online publication date: 29-Jun-2024
https://doi.org/10.1109/SMARTCOMP61445.2024.00041
Show More Cited By

Index Terms

Stackelberg scheduling strategies
1. Computing methodologies
  1. Artificial intelligence
    1. Planning and scheduling
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
      1. Scheduling algorithms
    2. Online algorithms
      1. Online learning algorithms
        Scheduling algorithms
  2. Theory and algorithms for application domains
    1. Machine learning theory
      1. Reinforcement learning
        Sequential decision making

Recommendations

Stackelberg Scheduling Strategies

We study the problem of optimizing the performance of a system shared by selfish, noncooperative users. We consider the concrete setting of scheduling small jobs on a set of shared machines possessing latency functions that specify the amount of time ...
Experimental results for stackelberg scheduling strategies
WEA'05: Proceedings of the 4th international conference on Experimental and Efficient Algorithms

In large scale networks users often behave selfishly trying to minimize their routing cost. Modelling this as a noncooperative game, may yield a Nash equilibrium with unboundedly poor network performance. To measure this inefficacy, the Coordination ...
Stackelberg Strategies for Atomic Congestion Games
Special Section: Algorithmic Game Theory; Guest Editors: Burkhard Monien and Ulf-Peter Schroeder

We investigate the effectiveness of Stackelberg strategies for atomic congestion games with unsplittable demands. In our setting, only a fraction of the players are selfish, while the rest are willing to follow a predetermined strategy. A Stackelberg ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '01: Proceedings of the thirty-third annual ACM symposium on Theory of computing

July 2001

755 pages

ISBN:1581133499

DOI:10.1145/380752

Copyright © 2001 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 July 2001

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

STOC01

Sponsor:

SIGACT

STOC01: 33rd ACM Symposium on Theory of Computing

Hersonissos, Greece

Acceptance Rates

STOC '01 Paper Acceptance Rate 83 of 230 submissions, 36%;

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

88
Total Citations
View Citations
212
Total Downloads

Downloads (Last 12 months)102
Downloads (Last 6 weeks)10

Reflects downloads up to 13 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Han MZhang FChen YKiyavash NMooij J(2024)No-regret learning of nash equilibrium for black-box games via Gaussian processesProceedings of the Fortieth Conference on Uncertainty in Artificial Intelligence10.5555/3702676.3702748(1541-1557)Online publication date: 15-Jul-2024
https://dl.acm.org/doi/10.5555/3702676.3702748
Brown D(2024)PhD Forum: Trust-Aware Routing of Human Drivers to Mitigate Traffic Congestion2024 IEEE International Conference on Smart Computing (SMARTCOMP)10.1109/SMARTCOMP61445.2024.00062(258-259)Online publication date: 29-Jun-2024
https://doi.org/10.1109/SMARTCOMP61445.2024.00062
Brown DNadendla VDas S(2024)TASR: A Novel Trust-Aware Stackelberg Routing Algorithm to Mitigate Traffic Congestion2024 IEEE International Conference on Smart Computing (SMARTCOMP)10.1109/SMARTCOMP61445.2024.00041(150-157)Online publication date: 29-Jun-2024
https://doi.org/10.1109/SMARTCOMP61445.2024.00041
Hill CBrown P(2023)The Tradeoff Between Altruism and Anarchy in Transportation Networks2023 IEEE 26th International Conference on Intelligent Transportation Systems (ITSC)10.1109/ITSC57777.2023.10422228(1442-1447)Online publication date: 24-Sep-2023
https://doi.org/10.1109/ITSC57777.2023.10422228
Chervinsk JKreutz DYu J(2023)Towards Scalable Cross-Chain Messaging2023 IEEE International Conference on Blockchain (Blockchain)10.1109/Blockchain60715.2023.00060(348-355)Online publication date: 17-Dec-2023
https://doi.org/10.1109/Blockchain60715.2023.00060
Hara TSasabe MKasahara S(2020)Selfish Yet Optimal Routing by Adjusting Perceived Traffic Information of Road NetworksIEEE Open Journal of Intelligent Transportation Systems10.1109/OJITS.2020.30199351(120-133)Online publication date: 2020
https://doi.org/10.1109/OJITS.2020.3019935
Samaranayake SKrichene WReilly JMonache MGoatin PBayen A(2018)Discrete-Time System Optimal Dynamic Traffic Assignment SO-DTA with Partial Control for Physical Queuing NetworksTransportation Science10.1287/trsc.2017.080052:4(982-1001)Online publication date: 1-Aug-2018
https://dl.acm.org/doi/10.1287/trsc.2017.0800
Krichene WReilly JAmin SBayen A(2018)Stackelberg Routing on Parallel Transportation NetworksHandbook of Dynamic Game Theory10.1007/978-3-319-44374-4_26(1107-1141)Online publication date: 2-Jun-2018
https://doi.org/10.1007/978-3-319-44374-4_26
Basu SYang GLianeas TNikolova EChen Y(2017)Reconciling Selfish Routing with Social GoodAlgorithmic Game Theory10.1007/978-3-319-66700-3_12(147-159)Online publication date: 19-Aug-2017
https://doi.org/10.1007/978-3-319-66700-3_12
Krichene WReilly JAmin SBayen A(2017)Stackelberg Routing on Parallel Transportation NetworksHandbook of Dynamic Game Theory10.1007/978-3-319-27335-8_26-1(1-35)Online publication date: 10-Apr-2017
https://doi.org/10.1007/978-3-319-27335-8_26-1
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents