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

research-article

Dynamics in congestion games

Authors:

Jinwoo ShinAuthors Info & Claims

ACM SIGMETRICS Performance Evaluation Review, Volume 38, Issue 1

Pages 107 - 118

https://doi.org/10.1145/1811099.1811052

Published: 14 June 2010 Publication History

Abstract

Game theoretic modeling and equilibrium analysis of congestion games have provided insights in the performance of Internet congestion control, road transportation networks, etc. Despite the long history, very little is known about their transient (non equilibrium) performance. In this paper, we are motivated to seek answers to questions such as how long does it take to reach equilibrium, when the system does operate near equilibrium in the presence of dynamics, e.g. nodes join or leave., or the tradeoff between performance and the rate of dynamics. In this pursuit, we provide three contributions in this paper. First, a novel probabilistic model to capture realistic behaviors of agents allowing for the possibility of arbitrariness in conjunction with rationality. Second, evaluation of (a) time to converge to equilibrium under this behavior model and (b) distance to Nash equilibrium. Finally, determination of tradeoff between the rate of dynamics and quality of performance (distance to equilibrium) which leads to an interesting uncertainty principle. The novel technical ingredients involve analysis of logarithmic Sobolov constant of Markov process with time varying state space and methodically this should be of broader interest in the context of dynamical systems.

References

[1]

C. Alos-Ferrer and N. Netzer. The logit-response dynamics. TWI Research Paper Series 28, Thurgauer Wirtschaftsinstitut, Universita"t Konstanz, 2008.

[2]

M. Beckmann, C. B. McGuire, and C. B. Winston. Studies in the Economics of Transportation. Yale University Press, 1956.

[3]

J. Bergine and B. Lipman. Evolution with state-dependent mutations. Econometrica, 64:943--956, 1996.

[4]

L. Blume. The statistical mechanics of strategic interaction. Games and Economic Behavior, 5(3):387--424, 1993.

[5]

L. Blume. Population games. Game theory and information, EconWPA, July 1996.

[6]

J. R. Correa, A. S. Schulz, and N. E. Stier-Moses. On the inefficiency of equilibria in congestion games. Lecture Notes in Computer Science, 3509:167--181, 2005.

Digital Library

[7]

A. Cournot. Recherches sur les principes mathematiques de la theories des richesse. Paris:Hachette, 1, 1838.

[8]

P. Diaconis and L. Saloff-Coste. Logarithmic Sobolev inequalities for finite Markov chains. The Annals of Applied Probability, 6(3):695--750, 1996.

[9]

G. Facchini, F. van Megen, P. Borm, and S. Tijs. Congestion models and weighted Bayesian potential games. Theory and Decision, 42(2):193--206, 1997.

[10]

A. Frieze and R. Kannan. Log-sobolev inequalities and sampling from log-concave distributions. Annals of Applied Probability, 9:14--26, 1998.

[11]

R. Johari and J. N. Tsitsiklis. Efficiency loss in a network resource allocation game. Mathematics of Operations Research, 29(3):407--435, 2004.

Digital Library

[12]

M. Kandori, G. J. Mailath, and R. Rob. Learning, mutation, and long run equilibria in games. Econometrica, 61(1):29--56, 1993.

[13]

F. P. Kelly, A. K. Maulloo, and D. K. H. Tan. Rate control for communication networks: shadow prices, proportional fairness and stability. Journal of the Operational Research Society, 49(3):237--252, March 1998.

[14]

E. Koutsoupias and C. Papadimitriou. Worst-case equilibria. In In Proc. 16th STACS, 1999.

Digital Library

[15]

A. D. Wentzell M. I. Freidlin. Random perturbations of dynamical systems. Springer, 1984.

[16]

J. R. Marden and J. S. Shamma. Revisiting log-linear learning: asynchrony, completeness, and payoff-based implementation. Submitted for journal publication, September 2008.

[17]

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

[18]

R. Montenegro and P. Tetali. Mathematical aspects of mixing times in Markov chains. Now Pub, 2006.

Digital Library

[19]

T. Roughgarden. Selfish routing and the price of anarchy. The MIT Press, 2005.

Digital Library

[20]

T. Roughgarden and E. Tardos. How bad is selfish routing? Journal of the ACM (JACM), 49(2):259, 2002.

Digital Library

[21]

M. E. Slade. What does an oligopoly maximize? Journal of Industrial Economics, 42(1):45--61, 1994.

[22]

P. Young. The evolution of conventions. Econometrica, 61(1):57--84, 1993.

Cited By

Bistritz IBambos N(2024)Gamekeeper: Online Learning for Admission Control of Networked Open Multiagent SystemsIEEE Transactions on Automatic Control10.1109/TAC.2024.339813969:11(7694-7709)Online publication date: Nov-2024
https://doi.org/10.1109/TAC.2024.3398139
Bistritz IBambos N(2023)Admission Control for Games with a Dynamic Set of Players2023 62nd IEEE Conference on Decision and Control (CDC)10.1109/CDC49753.2023.10383907(1219-1224)Online publication date: 13-Dec-2023
https://doi.org/10.1109/CDC49753.2023.10383907
Taha FRokade KParise F(2023)Gradient Dynamics in Linear Quadratic Network Games with Time-Varying Connectivity and Population Fluctuation2023 62nd IEEE Conference on Decision and Control (CDC)10.1109/CDC49753.2023.10383490(1991-1996)Online publication date: 13-Dec-2023
https://doi.org/10.1109/CDC49753.2023.10383490
Show More Cited By

Index Terms

Dynamics in congestion games

Recommendations

Dynamics in congestion games
SIGMETRICS '10: Proceedings of the ACM SIGMETRICS international conference on Measurement and modeling of computer systems

Game theoretic modeling and equilibrium analysis of congestion games have provided insights in the performance of Internet congestion control, road transportation networks, etc. Despite the long history, very little is known about their transient (non ...
Cost-Balancing Tolls for Atomic Network Congestion Games
Internet and Network Economics
Abstract
We investigate the existence of optimal tolls for atomic symmetric network congestion games with unsplittable traffic and arbitrary non-negative and non-decreasing latency functions. We focus on pure Nash equilibria and a natural toll mechanism, ...
Congestion Games with Variable Demands

We initiate the study of congestion games with variable demands in which the players strategically choose both a nonnegative demand and a subset of resources. The players’ incentives to use higher demands are stimulated by nondecreasing and concave ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGMETRICS Performance Evaluation Review

ACM SIGMETRICS Performance Evaluation Review Volume 38, Issue 1

Performance evaluation review

June 2010

382 pages

ISSN:0163-5999

DOI:10.1145/1811099

Issue’s Table of Contents

SIGMETRICS '10: Proceedings of the ACM SIGMETRICS international conference on Measurement and modeling of computer systems
June 2010
398 pages
ISBN:9781450300384
DOI:10.1145/1811039
General Chair:
Vishal Misra
Columbia University, USA
,
Program Chairs:
Paul Barford
University of Wisconsin-Madison, USA
,
Mark Squillante
IBM T.J. Watson Research Center, USA

Copyright © 2010 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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 14 June 2010

Published in SIGMETRICS Volume 38, Issue 1

Check for updates

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

64
Total Citations
View Citations
501
Total Downloads

Downloads (Last 12 months)57
Downloads (Last 6 weeks)5

Reflects downloads up to 19 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Bistritz IBambos N(2024)Gamekeeper: Online Learning for Admission Control of Networked Open Multiagent SystemsIEEE Transactions on Automatic Control10.1109/TAC.2024.339813969:11(7694-7709)Online publication date: Nov-2024
https://doi.org/10.1109/TAC.2024.3398139
Bistritz IBambos N(2023)Admission Control for Games with a Dynamic Set of Players2023 62nd IEEE Conference on Decision and Control (CDC)10.1109/CDC49753.2023.10383907(1219-1224)Online publication date: 13-Dec-2023
https://doi.org/10.1109/CDC49753.2023.10383907
Taha FRokade KParise F(2023)Gradient Dynamics in Linear Quadratic Network Games with Time-Varying Connectivity and Population Fluctuation2023 62nd IEEE Conference on Decision and Control (CDC)10.1109/CDC49753.2023.10383490(1991-1996)Online publication date: 13-Dec-2023
https://doi.org/10.1109/CDC49753.2023.10383490
Bu ZZhang SCao SJiang JJiang Y(2023)Community-aware empathetic social choice for social network group decision makingInformation Sciences10.1016/j.ins.2023.119248644(119248)Online publication date: Oct-2023
https://doi.org/10.1016/j.ins.2023.119248
Avni GGuha SKupferman O(2023)Timed network gamesInformation and Computation10.1016/j.ic.2022.104996290(104996)Online publication date: Jan-2023
https://doi.org/10.1016/j.ic.2022.104996
Paarporn KCanty BBrown PAlizadeh MMarden J(2021)The Impact of Complex and Informed Adversarial Behavior in Graphical Coordination GamesIEEE Transactions on Control of Network Systems10.1109/TCNS.2020.30388428:1(200-211)Online publication date: Mar-2021
https://doi.org/10.1109/TCNS.2020.3038842
Jaleel HShamma J(2021)Path to Stochastic Stability: Comparative Analysis of Stochastic Learning Dynamics in GamesIEEE Transactions on Automatic Control10.1109/TAC.2020.303948566:11(5253-5268)Online publication date: Nov-2021
https://doi.org/10.1109/TAC.2020.3039485
Franceschelli MFrasca P(2021)Stability of Open Multiagent Systems and Applications to Dynamic ConsensusIEEE Transactions on Automatic Control10.1109/TAC.2020.300936466:5(2326-2331)Online publication date: May-2021
https://doi.org/10.1109/TAC.2020.3009364
Hammouti HHamza DShihada BAlouini MShamma J(2021)The Optimal and the Greedy: Drone Association and Positioning Schemes for Internet of UAVsIEEE Internet of Things Journal10.1109/JIOT.2021.30702098:18(14066-14079)Online publication date: 15-Sep-2021
https://doi.org/10.1109/JIOT.2021.3070209
Yazıcıoğlu YBhat RAksaray D(2021)Distributed Planning for Serving Cooperative Tasks with Time Windows: A Game Theoretic ApproachJournal of Intelligent and Robotic Systems10.1007/s10846-021-01477-0103:2Online publication date: 1-Oct-2021
https://dl.acm.org/doi/10.1007/s10846-021-01477-0
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 Issue’s Table of Contents