title: Statics and Dynamics of Selfish Interactions in Distributed Service Systems.
abstract: We study a class of games which models the competition among agents to access some service provided by distributed service units and which exhibits congestion and frustration phenomena when service units have limited capacity. We propose a technique, based on the cavity method of statistical physics, to characterize the full spectrum of Nash equilibria of the game. The analysis reveals a large variety of equilibria, with very different statistical properties. Natural selfish dynamics, such as best-response, usually tend to large-utility equilibria, even though those of smaller utility are exponentially more numerous. Interestingly, the latter actually can be reached by selecting the initial conditions of the best-response dynamics close to the saturation limit of the service unit capacities. We also study a more realistic stochastic variant of the game by means of a simple and effective approximation of the average over the random parameters, showing that the properties of the average-case Nash equilibria are qualitatively similar to the deterministic ones.
authors.affiliation: Department of Applied Science and Technology and Center for Computational Sciences, Politecnico di Torino, Torino, Italy; Collegio Carlo Alberto, Moncalieri, Italy.
authors.forename: Fabrizio
authors.initials: F
authors.lastname: Altarelli
authors.affiliation: Department of Applied Science and Technology and Center for Computational Sciences, Politecnico di Torino, Torino, Italy; Human Genetics Foundation, Torino, Italy; Collegio Carlo Alberto, Moncalieri, Italy.
authors.forename: Alfredo
authors.initials: A
authors.lastname: Braunstein
authors.affiliation: Department of Applied Science and Technology and Center for Computational Sciences, Politecnico di Torino, Torino, Italy; Collegio Carlo Alberto, Moncalieri, Italy.
authors.forename: Luca
authors.initials: L
authors.lastname: Dall'Asta
mesh_terms: D019277:Entropy; D005716:Game Theory; D008962:Models, Theoretical; D013269:Stochastic Processes