Learning in Graphical Congestion Games with Applications to Content Replication and Caching
György Dán, Associate Professor, KTH
Date and Time
Tuesday, May 14th, 2013 at 10:30.
Polacksbacken, room 1145
Content caching and replication are widely used in networked systems to improve performance. Examples include content distribution networks, proxy caches, and the emerging paradigm of content centric networking. In this talk we consider the problem of caching and replication of contents by autonomous, interacting agents. We model the replication problem as a player-specific congestion game played on a graph. The graph determines the influence of the players on each other. We show that replication games do not admit a potential function in general, yet pure Nash equilibria do exist for arbitrary graph topologies. We discuss the convergence properties of the better and best response dynamics under different graph topologies and for different congestion functions. We show that the problem of caching can be modeled using the game theoretical model and provide convergence results for coordinated and uncoordinated caches. We conclude with results on the stability of equilibria under noisy estimates of content popularity.