Multiplicative updates outperform generic no-regret learning in congestion games

DOI10.1145/1536414.1536487zbMath1304.91017MaRDI QIDQ5172748

Georgios Piliouras, Éva Tardos, Robert D. Kleinberg

Publication date: 4 February 2015

Published in: Proceedings of the forty-first annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1536414.1536487

zbMATH Keywords

game theory; learning theory; price of anarchy

Mathematics Subject Classification ID

91A10: Noncooperative games

91A26: Rationality and learning in game theory

Related Items

Unnamed Item, Mutation, Sexual Reproduction and Survival in Dynamic Environments, Gradient Descent Only Converges to Minimizers: Non-Isolated Critical Points and Invariant Regions, Unnamed Item, Online Learning of Nash Equilibria in Congestion Games, Robustness of dynamics in games: a contraction mapping decomposition approach, Concurrent imitation dynamics in congestion games, Dynamics in atomic signaling games, Generalized mirror descents in congestion games, Reducing price of anarchy of selfish task allocation with more selfishness, Load balancing without regret in the bulletin board model, Competitive routing over time, From Darwin to Poincaré and von Neumann: recurrence and cycles in evolutionary and algorithmic game theory, The price of anarchy and stability in general noisy best-response dynamics, Bifurcation mechanism design -- from optimal flat taxes to better cancer treatments, Generalized mirror descents with non-convex potential functions in atomic congestion games: continuous time and discrete time, Sex with no regrets: how sexual reproduction uses a no regret learning algorithm for evolutionary advantage, Q-learning for Markov decision processes with a satisfiability criterion, Opinion dynamics with limited information, A unifying learning framework for building artificial game-playing agents, First-order methods almost always avoid strict saddle points, Exploration-exploitation in multi-agent learning: catastrophe theory meets game theory, On Learning Algorithms for Nash Equilibria, Oceanic Games: Centralization Risks and Incentives in Blockchain Mining