Convergence in Player-Specific Graphical Resource Allocation Games
2012 (English)In: IEEE Journal on Selected Areas in Communications, ISSN 0733-8716, E-ISSN 1558-0008, Vol. 30, no 11, 2190-2199 p.Article in journal (Refereed) Published
As a model of distributed resource allocation in networked systems, we consider resource allocation games played over a influence graph. The influence graph models limited interaction between the players due to, e. g., the network topology: the payoff that an allocated resource yields to a player depends only on the resources allocated by her neighbors on the graph. We prove that pure strategy Nash equilibria (NE) always exist in graphical resource allocation games and we provide a linear time algorithm to compute equilibria. We show that these games do not admit a potential function: if there are closed paths in the influence graph then there can be best reply cycles. Nevertheless, we show that from any initial allocation of a resource allocation game it is possible to reach a NE by playing best replies and we provide a bound on the maximal number of update steps required. Furthermore we give sufficient conditions in terms of the influence graph topology and the utility structure under which best reply cycles do not exist. Finally we propose an efficient distributed algorithm to reach an equilibrium over an arbitrary graph and we illustrate its performance on different random graph topologies.
Place, publisher, year, edition, pages
2012. Vol. 30, no 11, 2190-2199 p.
resource allocation, graphical games, player-specific congestion games, best reply dynamics
Electrical Engineering, Electronic Engineering, Information Engineering
IdentifiersURN: urn:nbn:se:kth:diva-109783DOI: 10.1109/JSAC.2012.121211ISI: 000311673200011ScopusID: 2-s2.0-84870277594OAI: oai:DiVA.org:kth-109783DiVA: diva2:584224
FunderSwedish Research Council, 2010-5812ICT - The Next Generation
QC 201301092013-01-082013-01-082016-01-11Bibliographically approved