Publica
Hier finden Sie wissenschaftliche Publikationen aus den FraunhoferInstituten. Concurrent imitation dynamics in congestion games
 Association for Computing Machinery ACM, Special Interest Group on Algorithms and Computation Theory SIGACT; Association for Computing Machinery ACM, Special Interest Group on Operating Systems SIGOPS: Proceedings of the 2009 ACM Symposium on Principles of Distributed Computing : August 10  12, 2009, Calgary, Alberta, Canada New York: ACM, 2009 ISBN: 9781605583969 S.6372 
 Symposium on Principles of Distributed Computing (PODC) <28, 2009, Calgary> 

 Englisch 
 Konferenzbeitrag 
 Fraunhofer ITWM () 
Abstract
Imitating successful behavior is a natural and frequently applied approach when facing scenarios for which we have little or no experience upon which we can base our decision. In this paper, we consider such behavior in atomic congestion games. We propose to study concurrent imitation dynamics that emerge when each player samples another player and possibly imitates this agents' strategy if the anticipated latency gain is sufficiently large. Our main focus is on convergence properties. Using a potential function argument, we show that these dynamics converge in a monotonic fashion to stable states. In such a state none of the players can improve their latency by imitating others.
As our 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 fully polynomial time approximation schemes (FPTAS). Fixing all other parameters, the convergence time depends only in a logarithmic fashion on the number of agents.
Since imitation processes are not innovative they cannot discover unused strategies. Furthermore, strategies may become extinct with nonzero probability. For the case of singleton games, we show that the probability of this event occurring is negligible. Additionally, we prove that 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.
While we concentrate on the case of symmetric network congestion games, most of our results do not explicitly use the network structure. They continue to hold accordingly for general symmetric and asymmetric congestion games when each player samples within his commodity.