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

research-article

Best-response dynamics out of sync: complexity and characterization

Authors:

Roee Engelberg,

Alex Fabrikant,

Michael Schapira,

David WajcAuthors Info & Claims

EC '13: Proceedings of the fourteenth ACM conference on Electronic commerce

Pages 379 - 396

https://doi.org/10.1145/2492002.2482609

Published: 16 June 2013 Publication History

Abstract

In many computational and economic models of multi-agent interaction, each participant repeatedly "best-responds" to the others' actions. Game theory research on the prominent "best-response dynamics" model typically relies on the premise that the interaction between agents is somehow synchronized. However, in many real-life settings, e.g., internet protocols and large-scale markets, the interaction between participants is asynchronous. We tackle the following important questions: (1) When are best-response dynamics guaranteed to converge to an equilibrium even under asynchrony? (2) What is the (computational and communication) complexity of verifying guaranteed convergence? We show that, in general, verifying guaranteed convergence is intractable. In fact, our main negative result establishes that this task is undecidable. We exhibit, in contrast, positive results for several environments of interest, including complete, computationally-tractable, characterizations of convergent systems. We discuss the algorithmic implications of our results, which extend beyond best-response dynamics to applications such as asynchronous Boolean circuits.

References

[1]

Alon, N., Matias, Y., and Szegedy, M. 1996. The space complexity of approximating the frequency moments. In Proc. of STOC.

Digital Library

[2]

Aspnes, J. and Ruppert, E. 2007. An introduction to population protocols. Bulletin of the EATCS 93, 98--117.

[3]

Davis, A. and Nowick, S. M. 1996. An introduction to asynchronous circuit design. Tech. Rep. UUCS-97-013, CS Dept., U. of Utah.

[4]

Dolev, S. 2000. Self stabilization. MIT Press.

Digital Library

[5]

Fabrikant, A., Jaggard, A., and Schapira, M. 2010. On the structure of weakly acyclic games. In Proc. of SAGT.

Digital Library

[6]

Fabrikant, A. and Papadimitriou, C. H. 2008. The complexity of game dynamics: BGP oscillations, sink equilibria, and beyond. In Proc. of SODA. 844--853.

Digital Library

[7]

Fich, F. and Ruppert, E. 2003. Hundreds of impossibility results for distributed computing. Distributed Computing 16, 2--3, 121--163.

Digital Library

[8]

Gao, L. and Rexford, J. 2002. Stable internet routing without global coordination. IEEE/ACM Trans. Netw. 9, 6, 681--692.

Digital Library

[9]

Godfrey, P. B., Schapira, M., Zohar, A., and Shenker, S. 2010. Incentive compatibility and dynamics of congestion control. In Proc. SIGMETRICS. 95--106.

Digital Library

[10]

Griffin, T. G., Shepherd, F. B., and Wilfong, G. 2002. The stable paths problem and interdomain routing. IEEE/ACM Trans. Netw. 10, 2, 232--243.

Digital Library

[11]

Hart, S. 2005. Adaptive heuristics. Econometrica 73, 1401--1430.

[12]

Hart, S. and Mansour, Y. 2010. How long to equilibrium? the communication complexity of uncoupled equilibrium procedures. GEB 69, 1, 107--126.

[13]

Jaggard, A. D., Schapira, M., and Wright, R. N. 2011. Distributed computing with adaptive heuristics. In Proc. ICS. 417--443.

[14]

Lehrer, E. and Lagziel, D. 2012. No regret with delayed information. Tech. rep., Tel-Aviv Univ. Working paper, Google Electronic Markets and Auctions initiative.

[15]

Levin, H., Schapira, M., and Zohar, A. 2008. Interdomain routing and games. In Proc. of STOC. 57--66.

Digital Library

[16]

Lynch, N. 1989. A hundred impossibility proofs for distributed computing. In Proc. ACM PODC. 1--28.

Digital Library

[17]

Mirrokni, V. S. and Skopalik, A. 2009. On the complexity of Nash dynamics and sink equilibria. In Proc. EC. 1--10.

Digital Library

[18]

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

[19]

Nisan, N. 2002. The communication complexity of approximate set packing and covering. In Proc. of ICALP.

Digital Library

[20]

Nisan, N., Schapira, M., and Zohar, A. 2008. Asynchronous best-reply dynamics. In Proc. WINE '08. 531--538.

Digital Library

[21]

Osborne, M. J. and Rubinstein, A. 1994. A Course in Game Theory. MIT Press.

[22]

Rosenthal, R. W. 1973. A class of games possessing pure-strategy Nash equilibria. Int. J. Game Theory 2, 65--67.

Digital Library

[23]

Sami, R., Schapira, M., and Zohar, A. 2009. Searching for stability in interdomain routing. In Proc. of INFOCOM.

[24]

Suchara, M., Fabrikant, A., and Rexford, J. 2011. BGP safety with spurious updates. In Proc. of INFOCOM.

[25]

Young, H. P. 1993. The evolution of conventions. Econometrica 61, 1, 57--84.

Cited By

Yan RDuan XShi ZZhong YMarden JBullo F(2022)Policy Evaluation and Seeking for Multiagent Reinforcement Learning via Best ResponseIEEE Transactions on Automatic Control10.1109/TAC.2021.308517167:4(1898-1913)Online publication date: Apr-2022
https://doi.org/10.1109/TAC.2021.3085171
Khan ZLehtomaki J(2019)Interactive Trial and Error Learning Method for Distributed Channel Bonding: Model, Prototype Implementation, and EvaluationIEEE Transactions on Cognitive Communications and Networking10.1109/TCCN.2019.28976955:2(206-223)Online publication date: Jun-2019
https://doi.org/10.1109/TCCN.2019.2897695
Palaiopanos GPanageas IPiliouras G(2017)Multiplicative weights update with constant step-size in congestion gamesProceedings of the 31st International Conference on Neural Information Processing Systems10.5555/3295222.3295337(5874-5884)Online publication date: 4-Dec-2017
https://dl.acm.org/doi/10.5555/3295222.3295337
Show More Cited By

Index Terms

Best-response dynamics out of sync: complexity and characterization
1. Theory of computation
  1. Randomness, geometry and discrete structures

Recommendations

Best-response dynamics out of sync: complexity and characterization
EC '13: Proceedings of the fourteenth ACM conference on Electronic commerce

In many computational and economic models of multi-agent interaction, each participant repeatedly "best-responds" to the others' actions. Game theory research on the prominent "best-response dynamics" model typically relies on the premise that the ...
Best-response auctions
EC '11: Proceedings of the 12th ACM conference on Electronic commerce

We present a new framework for auction design and analysis that we term "best-response auctions". We use this framework to show that the simple and myopic best-response dynamics converge to the VCG outcome and are incentive compatible in several well-...
Price Competition, Fluctuations and Welfare Guarantees
EC '15: Proceedings of the Sixteenth ACM Conference on Economics and Computation

In various markets where sellers compete in price, price oscillations are observed rather than convergence to equilibrium. Such fluctuations have been empirically observed in the retail market for gasoline, in airline pricing and in the online sale of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

EC '13: Proceedings of the fourteenth ACM conference on Electronic commerce

June 2013

924 pages

ISBN:9781450319621

DOI:10.1145/2492002

General Chair:
Michael Kearns
University of Pennsylvania., USA
,
Program Chairs:
Preston McAfee
Google, USA
,
Éva Tardos
Cornell University, USA

Copyright © 2013 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

SIGecom: Special Interest Group on Economics and Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 16 June 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

EC '13

Sponsor:

SIGecom

EC '13: ACM Conference on Electronic Commerce

June 16 - 20, 2013

Pennsylvania, Philadelphia, USA

Acceptance Rates

EC '13 Paper Acceptance Rate 72 of 223 submissions, 32%;

Overall Acceptance Rate 664 of 2,389 submissions, 28%

Upcoming Conference

EC '25

Sponsor:
sigecom

The 25th ACM Conference on Economics and Computation

July 7 - 11, 2025

Stanford , CA , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
121
Total Downloads

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

Reflects downloads up to 09 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Yan RDuan XShi ZZhong YMarden JBullo F(2022)Policy Evaluation and Seeking for Multiagent Reinforcement Learning via Best ResponseIEEE Transactions on Automatic Control10.1109/TAC.2021.308517167:4(1898-1913)Online publication date: Apr-2022
https://doi.org/10.1109/TAC.2021.3085171
Khan ZLehtomaki J(2019)Interactive Trial and Error Learning Method for Distributed Channel Bonding: Model, Prototype Implementation, and EvaluationIEEE Transactions on Cognitive Communications and Networking10.1109/TCCN.2019.28976955:2(206-223)Online publication date: Jun-2019
https://doi.org/10.1109/TCCN.2019.2897695
Palaiopanos GPanageas IPiliouras G(2017)Multiplicative weights update with constant step-size in congestion gamesProceedings of the 31st International Conference on Neural Information Processing Systems10.5555/3295222.3295337(5874-5884)Online publication date: 4-Dec-2017
https://dl.acm.org/doi/10.5555/3295222.3295337
Dvijotham KRabani YSchulman LKlein P(2017)Convergence of incentive-driven dynamics in fisher marketsProceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3039686.3039721(554-567)Online publication date: 16-Jan-2017
https://dl.acm.org/doi/10.5555/3039686.3039721
Jaggard ALutz NSchapira MWright R(2017)Dynamics at the Boundary of Game Theory and Distributed ComputingACM Transactions on Economics and Computation10.1145/31071825:3(1-20)Online publication date: 9-Aug-2017
https://dl.acm.org/doi/10.1145/3107182
Dolev DErdmann MLutz NSchapira MZair ASchiller ESchwarzmann A(2017)Stateless ComputationProceedings of the ACM Symposium on Principles of Distributed Computing10.1145/3087801.3087854(419-421)Online publication date: 25-Jul-2017
https://dl.acm.org/doi/10.1145/3087801.3087854
Sobrinho J(2017)Correctness of Routing Vector Protocols as a Property of Network CyclesIEEE/ACM Transactions on Networking10.1109/TNET.2016.256760025:1(150-163)Online publication date: 1-Feb-2017
https://dl.acm.org/doi/10.1109/TNET.2016.2567600
Babaioff MPaes Leme RSivan BRoughgarden TFeldman MSchwarz M(2015)Price Competition, Fluctuations and Welfare GuaranteesProceedings of the Sixteenth ACM Conference on Economics and Computation10.1145/2764468.2764493(759-776)Online publication date: 15-Jun-2015
https://dl.acm.org/doi/10.1145/2764468.2764493

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.

Figures

Tables

Media

View Table of Conten