Multiplicative updates outperform generic no-regret learning in congestion games

DOI10.1145/1536414.1536487zbMath1304.91017OpenAlexW2083562271MaRDI 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 theorylearning theoryprice of anarchy

Mathematics Subject Classification ID

Noncooperative games (91A10) Rationality and learning in game theory (91A26)

Related Items (25)

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

This page was built for publication: Multiplicative updates outperform generic no-regret learning in congestion games