# Learning and Efficiency in Games with Dynamic Population

arXiv: https://arxiv.org/abs/1505.00391 · HTML: https://mlsanity.com/paper/1505.00391/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 May 2015.

## Built on by (most cited first, 9 of 9)

- [Bilateral Trade: A Regret Minimization Perspective](https://mlsanity.com/paper/2109.12974/) (2021)
- [Contracting with a Learning Agent](https://mlsanity.com/paper/2401.16198/) (2024)
- [A Regret Analysis of Bilateral Trade](https://mlsanity.com/paper/2102.08754/) (2021)
- [No-Regret Learning in Bilateral Trade via Global Budget Balance](https://mlsanity.com/paper/2310.12370/) (2023)
- [An α-regret analysis of Adversarial Bilateral Trade](https://mlsanity.com/paper/2210.06846/) (2022)
- [On the Convergence of No-Regret Learning Dynamics in Time-Varying Games](https://mlsanity.com/paper/2301.11241/) (2023)
- [Learning in Repeated Multi-Unit Pay-As-Bid Auctions](https://mlsanity.com/paper/2307.15193/) (2023)
- [Proximal Point Method for Online Saddle Point Problem](https://mlsanity.com/paper/2407.04591/) (2024)
- [Differential Privacy May Have a Potential Optimization Effect on Some Swarm Intelligence Algorithms besides Privacy-preserving](https://mlsanity.com/paper/2306.17370/) (2023)

## Abstract (arXiv)

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.