Fast Convergence of Best-Reply Dynamics in Aggregative Games

References

• Alos-Ferrer C, Ania AB (2005) The evolutionary stability of perfectly competitive behavior. Econom. Theory 26(3):497–516.Crossref, Google Scholar
• Arieli I, Young HP (2016) Stochastic learning dynamics and speed of convergence in population games. Econometrica 84(2):627–676.Crossref, Google Scholar
• Awerbuch B, Azar Y, Epstein A, Mirrokni VS, Skopalik A (2008) Fast convergence to nearly optimal solutions in potential games. Fortnow L, Riedl J, Sandholm T, eds. Proc. 9th ACM Conf. Electronic Commerce, EC ’08 (ACM, New York), 264–273.Crossref, Google Scholar
• Azrieli Y, Shmaya E (2013) Lipschitz games. Math. Oper. Res. 38(2):350–357.Link, Google Scholar
• Babichenko Y (2013) Best-reply dynamics in large binary-choice anonymous games. Games Econom. Behav. 81:130–144.Crossref, Google Scholar
• Chien S, Sinclair A (2011) Convergence to approximate Nash equilibria in congestion games. Games Econom. Behav. 71(2):315–327.Crossref, Google Scholar
• Daskalakis C, Papadimitriou C (2007) Computing equilibria in anonymous games. Proc. 48th Annual IEEE Sympos. Foundations Comput. Sci., FOCS’07 (IEEE Computer Society, Washington, DC), 83–93.Crossref, Google Scholar
• Dindoš M, Mezzetti C (2006) Better-reply dynamics and global convergence to Nash equilibrium in aggregative games. Games Econom. Behav. 54(2):261–292.Crossref, Google Scholar
• Dubey P, Haimanko O, Zapechelnyuk A (2006) Strategic complements and substitutes, and potential games. Games Econom. Behav. 54(1):77–94.Crossref, Google Scholar
• Fabrikant A, Papadimitriou C, Talwar K (2004) The complexity of pure Nash equilibria. Proc. 36th Annual ACM Sympos. Theory Comput., STOC ’04 (ACM, New York), 604–612.Crossref, Google Scholar
• Feller W (1974) Introduction to probability theory and its applications (John Wiley & Sons, New York).Google Scholar
• Gorodeisky Z (2003) Evolutionary stability for large populations. Technical report, The Hebrew University of Jerusalem, Israel.Google Scholar
• Hart S, Mansour Y (2010) How long to equilibrium? The communication complexity of uncoupled equilibrium procedures. Games Econom. Behav. 69(1):107–126.Crossref, Google Scholar
• Jensen MK (2010) Aggregative games and best-reply potentials. Econom. Theory 43(1):45–66.Crossref, Google Scholar
• Kearns M, Mansour Y (2002) Efficient Nash computation in large population games with bounded influence. Proc. 18th Conf. Uncertainty in Artificial Intelligence, UAI ’02 (Morgan Kaufmann Publishers, San Francisco), 259–266.Google Scholar
• Kukushkin NS (2004) Best response dynamics in finite games with additive aggregation. Games Econom. Behav. 48(1):94–110.Crossref, Google Scholar
• Kukushkin NS (2005) Strategic supplements in games with polylinear interactions. EconWPA Paper 411008.Google Scholar
• Monderer D, Shapley LS (1996) Potential games. Games Econom. Behav. 14(1):124–143.Crossref, Google Scholar
• Pradelski BS (2014) Evolutionary dynamics and fast convergence in the assignment game. Technical report, University of Oxford.Google Scholar
• Selten R (1970) Preispolitik der Mehrproduktenunternehmung in der statischen Theorie, Vol. 16 (Springer, Berlin).Crossref, Google Scholar
• Serfling RJ (1974) Probability inequalities for the sum in sampling without replacement. Ann. Statist. 2(1):39–48.Crossref, Google Scholar
• Shah D, Shin J (2010) Dynamics in congestion games. ACM SIGMETRICS Performance Evaluation Review, Vol. 38 (ACM, New York), 107–118.Crossref, Google Scholar
• Skopalik A, Vöcking B (2008) Inapproximability of pure Nash equilibria. Dwork C, ed. Proc. 40th Annual ACM Sympos. Theory Comput., STOC ’08 (ACM, New York), 355–364.Crossref, Google Scholar
• Takács L (1962) Ballot problems. Probab. Theory and Related Fields 1(2):154–158.Google Scholar