Learning and Efficiency in Games with Dynamic Population
From MaRDI portal
Abstract: We study the quality of outcomes in repeated games when the population of players is dynamically changing and participants use learning algorithms to adapt to the changing environment. Game theory classically considers Nash equilibria of one-shot games, while in practice many games are played repeatedly, and in such games players often use algorithmic tools to learn to play in the given environment. Most previous work on learning in repeated games assumes that the population playing the game is static over time. We analyze the efficiency of repeated games in dynamically changing environments, motivated by application domains such as Internet ad-auctions and packet routing. We prove that, in many classes of games, if players choose their strategies in a way that guarantees low adaptive regret, then high social welfare is ensured, even under very frequent changes. In fact, in large markets learning players achieve asymptotically optimal social welfare despite high turnover. Previous work has only showed that high welfare is guaranteed for learning outcomes in static environments. Our work extends these results to more realistic settings when participation is drastically evolving over time.
Recommendations
- Stochastic Learning Dynamics and Speed of Convergence in Population Games
- Reinforcement learning in population games
- Learning in nonatomic games. I: Finite action spaces and population games
- Evolutionary game dynamics in populations with different learners
- Learning, Mutation, and Long Run Equilibria in Games
- Learning dynamics in games with stochastic perturbations
- Learning correlated equilibria in population games.
- scientific article; zbMATH DE number 1189218
- Learning efficient equilibria in repeated games
Cited in
(11)- Learning in auctions: regret is hard, envy is easy
- Population learning in a model with random payoff landscapes and endogenous networks
- Smoothness for Simultaneous Composition of Mechanisms with Admission
- Prophet inequalities made easy: stochastic optimization by pricing nonstochastic inputs
- Stochastic Learning Dynamics and Speed of Convergence in Population Games
- Learning, Mutation, and Long Run Equilibria in Games
- Small-Loss Bounds for Online Learning with Partial Information
- Differential privacy may have a potential optimization effect on some swarm intelligence algorithms besides privacy-preserving
- Trends and questions in open multi-agent systems
- An \(\alpha \)-regret analysis of adversarial bilateral trade
- The price of anarchy of strategic queuing systems
This page was built for publication: Learning and Efficiency in Games with Dynamic Population
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575584)
