Title: Concurrent Imitation Dynamics in Congestion Games
Martin Hoefer
RWTH Aachen University
Abstract:
Imitating successful behavior is a natural and frequently applied approach when making decisions in various scenarios. In this talk, we consider such behavior in atomic congestion games. Our concurrent imitation dynamics emerge when each player samples another player and possibly imitates this agents' strategy if the anticipated latency gain is sufficiently large. These dynamics converge in a monotonic fashion to stable states, in which none of the players can improve its latency by imitating somebody else. As the main result, we show rapid convergence to approximate equilibria. At an approximate equilibrium only a small fraction of agents sustains a latency significantly above or below
average. In particular, imitation dynamics behave like an FPTAS, and fixing all other parameters, the convergence time depends only in a logarithmic fashion on the number of agents. Additionally, the social cost of a stable state reached by our dynamics is not much worse than an optimal state in singleton congestion games with linear latency functions. Finally, we outline extensions such that, in the long run, dynamics converge to a Nash equilibrium.
This is joint work with Heiner Ackermann, Petra Berenbrink, and Simon Fischer.