Generalized mirror descents in congestion games
From MaRDI portal
Publication:334813
DOI10.1016/J.ARTINT.2016.09.002zbMATH Open1406.91069arXiv1605.07774OpenAlexW2398693750MaRDI QIDQ334813FDOQ334813
Authors: Po-An Chen, Chi-Jen Lu 
Publication date: 1 November 2016
Published in: Artificial Intelligence (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1605.07774
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
- Adaptive subgradient methods for online learning and stochastic optimization
- Title not available (Why is that?)
- Introductory lectures on convex optimization. A basic course.
- Algorithmic Game Theory
- Mirror descent and nonlinear projected subgradient methods for convex optimization.
- The Nonstochastic Multiarmed Bandit Problem
- Title not available (Why is that?)
- The weighted majority algorithm
- Online convex optimization in the bandit setting: gradient descent without a gradient
- Interior-Point Methods for Full-Information and Bandit Online Learning
- Adaptive game playing using multiplicative weights
- Convergence to equilibrium of logit dynamics for strategic games
- Title not available (Why is that?)
- The complexity of pure Nash equilibria
- Intrinsic robustness of the price of anarchy
- Multiplicative updates outperform generic no-regret learning in congestion games (extended abstract)
- Fast convergence to Wardrop equilibria by adaptive sampling methods
- Load balancing without regret in the bulletin board model
- Circumventing the price of anarchy: leading dynamics to good behavior
- Convergence to approximate Nash equilibria in congestion games
- Title not available (Why is that?)
- Concurrent imitation dynamics in congestion games
- On the convergence of regret minimization dynamics in concave games
- Routing without regret, on convergence to Nash equilibria of regret-minimizing algorithms in routing games
- Near-optimal no-regret algorithms for zero-sum games
- Tatonnement beyond gross substitutes? Gradient descent to the rescue
- Learning equilibria of games via payoff queries
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
- Multiplicative updates outperform generic no-regret learning in congestion games (extended abstract)
- Continuous-Time Discounted Mirror Descent Dynamics in Monotone Concave Games
- 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
Uses Software
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)
