Generalized mirror descents in congestion games
From MaRDI portal
(Redirected from Publication:334813)
Abstract: Different types of dynamics have been studied in repeated game play, and one of them which has received much attention recently consists of those based on "no-regret" algorithms from the area of machine learning. It is known that dynamics based on generic no-regret algorithms may not converge to Nash equilibria in general, but to a larger set of outcomes, namely coarse correlated equilibria. Moreover, convergence results based on generic no-regret algorithms typically use a weaker notion of convergence: the convergence of the average plays instead of the actual plays. Some work has been done showing that when using a specific no-regret algorithm, the well-known multiplicative updates algorithm, convergence of actual plays to equilibria can be shown and better quality of outcomes in terms of the price of anarchy can be reached for atomic congestion games and load balancing games. Are there more cases of natural no-regret dynamics that perform well in suitable classes of games in terms of convergence and quality of outcomes that the dynamics converge to? We answer this question positively in the bulletin-board model by showing that when employing the mirror-descent algorithm, a well-known generic no-regret algorithm, the actual plays converge quickly to equilibria in nonatomic congestion games. Furthermore, the bandit model considers a probably more realistic and prevalent setting with only partial information, in which at each time step each player only knows the cost of her own currently played strategy, but not any costs of unplayed strategies. For the class of atomic congestion games, we propose a family of bandit algorithms based on the mirror-descent algorithms previously presented, and show that when each player individually adopts such a bandit algorithm, their joint (mixed) strategy profile quickly converges with implications.
Recommendations
- Multiplicative updates outperform generic no-regret learning in congestion games (extended abstract)
- Online learning of Nash equilibria in congestion games
- Routing without regret, on convergence to Nash equilibria of regret-minimizing algorithms in routing games
- Generalized mirror descents with non-convex potential functions in atomic congestion games: continuous time and discrete time
- Learning, regret minimization, and equilibria
Cites work
- scientific article; zbMATH DE number 5485547 (Why is no real title available?)
- scientific article; zbMATH DE number 5485549 (Why is no real title available?)
- scientific article; zbMATH DE number 2107836 (Why is no real title available?)
- scientific article; zbMATH DE number 903638 (Why is no real title available?)
- Adaptive game playing using multiplicative weights
- Adaptive subgradient methods for online learning and stochastic optimization
- Algorithmic Game Theory
- Circumventing the price of anarchy: leading dynamics to good behavior
- Concurrent imitation dynamics in congestion games
- Convergence to approximate Nash equilibria in congestion games
- Convergence to equilibrium of logit dynamics for strategic games
- Fast convergence to Wardrop equilibria by adaptive sampling methods
- Interior-Point Methods for Full-Information and Bandit Online Learning
- Intrinsic robustness of the price of anarchy
- Introductory lectures on convex optimization. A basic course.
- Learning equilibria of games via payoff queries
- Load balancing without regret in the bulletin board model
- Mirror descent and nonlinear projected subgradient methods for convex optimization.
- Multiplicative updates outperform generic no-regret learning in congestion games (extended abstract)
- Near-optimal no-regret algorithms for zero-sum games
- On the convergence of regret minimization dynamics in concave games
- Online convex optimization in the bandit setting: gradient descent without a gradient
- Routing without regret, on convergence to Nash equilibria of regret-minimizing algorithms in routing games
- Tatonnement beyond gross substitutes? Gradient descent to the rescue
- The Nonstochastic Multiarmed Bandit Problem
- The complexity of pure Nash equilibria
- The weighted majority algorithm
Cited in
(11)- No-regret learning for repeated non-cooperative games with lossy bandits
- Leadership in singleton congestion games: what is hard and what is easy
- Online learning of Nash equilibria in congestion games
- On the convergence of regret minimization dynamics in concave games
- Continuous-Time Discounted Mirror Descent Dynamics in Monotone Concave Games
- Multiplicative updates outperform generic no-regret learning in congestion games (extended abstract)
- Generalized mirror descents with non-convex potential functions in atomic congestion games: continuous time and discrete time
- An alternating algorithm for finding linear Arrow-Debreu market equilibria
- A reinforcement learning scheme for the equilibrium of the in-vehicle route choice problem based on congestion game
- Routing without regret, on convergence to Nash equilibria of regret-minimizing algorithms in routing games
- Memory loss can prevent chaos in games dynamics
This page was built for publication: Generalized mirror descents in congestion games
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q334813)
