Article

Convergence time to Nash equilibria

Authors:

Alex Kesselman,

Yishay MansourAuthors Info & Claims

ICALP'03: Proceedings of the 30th international conference on Automata, languages and programming

Pages 502 - 513

Published: 30 June 2003 Publication History

Abstract

We study the number of steps required to reach a pure Nash Equilibrium in a load balancing scenario where each job behaves selfishly and attempts to migrate to a machine which will minimize its cost. We consider a variety of load balancing models, including identical, restricted, related and unrelated machines. Our results have a crucial dependence on the weights assigned to jobs. We consider arbitrary weights, integer weights, K distinct weights and identical (unit) weights. We look both at an arbitrary schedule (where the only restriction is that a job migrates to a machine which lowers its cost) and specific efficient schedulers (such as allowing the largest weight job to move first).

References

[1]

E. Altman, T. Basar, T. Jimenez and N. Shimkin, "Routing into two parallel links: Game-Theoretic Distributed Algorithms," Journal of Parallel and Distributed Computing, pp. 1367-1381, Vol. 61, No. 9, 2001.

Digital Library

[2]

B. Awerbuh, Y. Azar, and Y. Richter, "Analysis of worse case Nash equilibria for restricted assignment," unpublished manuscript.

[3]

Y. Azar, "On-line Load Balancing Online Algorithms - The State of the Art," chapter 8, 178-195, Springer, 1998.

Digital Library

[4]

T. Boulogne, E. Altman and O. Pourtallier, "On the convergence to Nash equilibrium in problems of distributed computing," Annals of Operation research, 2002.

[5]

P. Brucker, J. Hurink, and F. Werner, "Improving Local Search Heuristics for Some Scheduling Problems, Part I," Discrete Applied Mathematics, 65, pp. 97-122, 1996.

Digital Library

[6]

P. Brucker, J. Hurink, and F. Werner, "Improving Local Search Heuristics for Some Scheduling Problems, Part II," Discrete Applied Mathematics, 72, pp. 47-69, 1997.

Digital Library

[7]

A. Czumaj, P. Krysta and B. Vocking, "Selfish traffic allocation for server farms," STOC 2002.

Digital Library

[8]

A. Czumaj and B. Vocking, "Tight bounds on worse case equilibria," SODA 2002.

Digital Library

[9]

E. Even-Dar, A. Kesselman and Y. Mansour, "Convergence Time To Nash Equilibria", Technical Report, available at http://www.cs.tau.ac.il/~evend/papers.html

[10]

G. Finn and E. Horowitz, "Linear Time Approximation Algorithm for Multiprocessor Scheduling," BIT, vol. 19, no. 3, 1979, pp. 312-320.

[11]

Florian, M. and D. Hearn, "Network Equilibrium Models and Algorithms", Network Routing. Handbooks in RO and MS, M.O. Ball et al. Editors, Elsevier, pp. 485-550. 1995.

[12]

D. Fudenberg and D. Levine, "The theory of learning in games," MIT Press, 1998.

[13]

D. Fotakis, S. Kontogiannis, E. Koutsoupias, M. Mavronicolas, and P. Spirakis, "The Structure and Complexity of Nash Equilibria for a Selfish Routing Game," In Proceedings of the 29th ICALP, Malaga, Spain, July 2002.

Digital Library

[14]

M. Kearns and Y. Mansour, "Efficient Nash Computation in Large Population Games with Bounded Influence," In Proceedings of UAI, 2002.

Digital Library

[15]

Y. A. Korilis and A. A. Lazar, "On the Existence of Equilibria in Noncooperative Optimal Flow Control," Journal of the ACM, Vol. 42, pp. 584-613, 1995.

Digital Library

[16]

Y.A. Korilis, A.A. Lazar, and A. Orda. Architecting Noncooperative Networks. IEEE J. on Selected Areas in Communications, Vol. 13, pp. 1241-1251, 1995.

Digital Library

[17]

E. Koutsoupias, C. H. Papadimitriou, "Worst-case equilibria," STACS 99.

Digital Library

[18]

R. J. La and V. Anantharam, "Optimal Routing Control: Game Theoretic Approach," Proceedings of the 36rd IEEE Conference on Decision and Control, San Diego, CA, pp. 2910-2915, Dec. 1997.

[19]

M. Littman, M. Kearns, and S. Singh, "An efficient exact algorithm for singly connected graphical games," In Proceedings of NIPS, 2002.

[20]

I. Milchtaich, "Congestion Games with Player-Specific Payoff Functions," Games and Economic Behavior, vol. 13, pp. 111-124, 1996.

[21]

D. Monderer and L. S. Shapley, "Potential games," Games and Economic Behavior, 14, pp. 124-143, 1996.

[22]

J. F. Nash, "Non-cooperative games," Annals of Mathematics, Vol. 54, pp. 286- 295, 1951.

[23]

A. Orda, N. Rom and N. Shimkin, "Competitive routing in multi-user communication networks," IEEE/ACM Transaction on Networking, Vol 1, pp. 614-627, 1993.

Digital Library

[24]

R. W. Rosenthal, "A class of games possessing pure-strategy Nash equilibria," International Journal of Game Theory, 2, pp. 65-67, 1973.

Digital Library

[25]

T. Roughgarden and E. Tardos, "How Bad is Selfish Routing?," In the Proceedings of the 41st Annual IEEE Symposium on the Foundations of Computer Science, 2000.

Digital Library

[26]

P. Schuurman and T. Vredeveld, "Performance guarantees of local search for multiprocessor scheduling," Proceedings IPCO, pp. 370-382, 2001.

Digital Library

[27]

S. Shenker, "Making greed work in networks a game-theoretic analysis of switch service disciplines," IEEE/ACM Transactions on Networking, Vol. 3, pp. 819-831, 1995.

Digital Library

Cited By

Ayala DWolfson ODasgupta BLin JXu B(2018)Spatio-Temporal Matching for Urban Transportation ApplicationsACM Transactions on Spatial Algorithms and Systems10.1145/31833443:4(1-39)Online publication date: 4-May-2018
https://dl.acm.org/doi/10.1145/3183344
Brunsch TEtscheid MRöglin H(2016)Bounds for the Convergence Time of Local Search in Scheduling ProblemsProceedings of the 12th International Conference on Web and Internet Economics - Volume 1012310.1007/978-3-662-54110-4_24(339-353)Online publication date: 11-Dec-2016
https://dl.acm.org/doi/10.1007/978-3-662-54110-4_24
Fearnley JGairing MGoldberg PSavani R(2015)Learning equilibria of games via payoff queriesThe Journal of Machine Learning Research10.5555/2789272.288679216:1(1305-1344)Online publication date: 1-Jan-2015
https://dl.acm.org/doi/10.5555/2789272.2886792
Show More Cited By

Index Terms

Convergence time to Nash equilibria
1. 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

Index terms have been assigned to the content through auto-classification.

Recommendations

Convergence time to Nash equilibrium in load balancing

We study the number of steps required to reach a pure Nash equilibrium in a load balancing scenario where each job behaves selfishly and attempts to migrate to a machine which will minimize its cost. We consider a variety of load balancing models, ...
Pure Nash equilibria in restricted budget games

In budget games, players compete over resources with finite budgets. For every resource, a player has a specific demand and as a strategy, he chooses a subset of resources. If the total demand on a resource does not exceed its budget, the utility of ...
Nash equilibria in fisher market
SAGT'10: Proceedings of the Third international conference on Algorithmic game theory

Much work has been done on the computation of market equilibria. However due to strategic play by buyers, it is not clear whether these are actually observed in the market. Motivated by the observation that a buyer may derive a better payoff by feigning ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

ICALP'03: Proceedings of the 30th international conference on Automata, languages and programming

June 2003

1199 pages

ISBN:3540404937

Editors:
Jos C. M. Baeten
Technische Universiteit Eindhoven, Dept. of Mathematics and Computer Science, Eindhoven, The Netherlands
,
Jan Karel Lenstra
Georgia Institute of Technology, School of Industrial and Systems Engineering, Atlanta, GA
,
Joachim Parrow
Uppsala University, Department of Information Technology, Uppsala, Sweden
,
Gerhard J. Woeginger
University of Twente, Faculty of Electrical Engineering, Mathematics and Computer Science, Enschede, The Netherlands

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 30 June 2003

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

56
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 04 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ayala DWolfson ODasgupta BLin JXu B(2018)Spatio-Temporal Matching for Urban Transportation ApplicationsACM Transactions on Spatial Algorithms and Systems10.1145/31833443:4(1-39)Online publication date: 4-May-2018
https://dl.acm.org/doi/10.1145/3183344
Brunsch TEtscheid MRöglin H(2016)Bounds for the Convergence Time of Local Search in Scheduling ProblemsProceedings of the 12th International Conference on Web and Internet Economics - Volume 1012310.1007/978-3-662-54110-4_24(339-353)Online publication date: 11-Dec-2016
https://dl.acm.org/doi/10.1007/978-3-662-54110-4_24
Fearnley JGairing MGoldberg PSavani R(2015)Learning equilibria of games via payoff queriesThe Journal of Machine Learning Research10.5555/2789272.288679216:1(1305-1344)Online publication date: 1-Jan-2015
https://dl.acm.org/doi/10.5555/2789272.2886792
Feldman MTamir T(2015)Convergence of best-response dynamics in games with conflicting congestion effectsInformation Processing Letters10.1016/j.ipl.2014.07.012115:2(112-118)Online publication date: 1-Feb-2015
https://dl.acm.org/doi/10.1016/j.ipl.2014.07.012
Berenbrink PBrinkmann AFriedetzky TNagel L(2014)Balls into non-uniform binsJournal of Parallel and Distributed Computing10.1016/j.jpdc.2013.10.00874:2(2065-2076)Online publication date: 1-Feb-2014
https://dl.acm.org/doi/10.1016/j.jpdc.2013.10.008
Brun OPrabhu BSeregina THorvath ABuchholz PCortellessa VMuscariello LSquillante M(2013)On the convergence of the best-response algorithm in routing gamesProceedings of the 7th International Conference on Performance Evaluation Methodologies and Tools10.4108/icst.valuetools.2013.254405(136-144)Online publication date: 10-Dec-2013
https://dl.acm.org/doi/10.4108/icst.valuetools.2013.254405
Fearnley JGairing MGoldberg PSavani RKearns MMcAfee PTardos É(2013)Learning equilibria of games via payoff queriesProceedings of the fourteenth ACM conference on Electronic commerce10.1145/2492002.2482558(397-414)Online publication date: 16-Jun-2013
https://dl.acm.org/doi/10.1145/2492002.2482558
Fearnley JGairing MGoldberg PSavani RKearns MMcAfee PTardos É(2013)Learning equilibria of games via payoff queriesProceedings of the fourteenth ACM conference on Electronic commerce10.1145/2482540.2482558(397-414)Online publication date: 16-Jun-2013
https://dl.acm.org/doi/10.1145/2482540.2482558
Shah SKothari R(2013)Convergence of the dynamic load balancing problem to Nash equilibrium using distributed local interactionsInformation Sciences: an International Journal10.1016/j.ins.2012.09.004221(297-305)Online publication date: 1-Feb-2013
https://dl.acm.org/doi/10.1016/j.ins.2012.09.004
Feldman MRon T(2012)Capacitated Network Design GamesProceedings of the 5th International Symposium on Algorithmic Game Theory - Volume 761510.5555/2954155.2954167(132-143)Online publication date: 22-Oct-2012
https://dl.acm.org/doi/10.5555/2954155.2954167
Show More Cited By

View Options

View options

Get Access

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

Media

Figures

Other

Tables

View Table of Contents