Population Protocols that Correspond to Symmetric Games
Olivier Bournez, Jeremie Chalopin, Johanne Cohen, Xavier Koegler and Mikael Rabie
Population protocols have been introduced by Angluin et al. as a model of networks consisting of very limited mobile anonymous agents that interact in pairs but with no control over their own movement. The model has been considered as a computational model.
In an orthogonal way, several distributed systems have been termed in literature as being realizations of games in the sense of game theory. In this paper, we investigate under which conditions population protocols, or more generally pairwise interaction rules, can be considered as the result of a symmetric game.
We prove that not all symmetric rules can be considered as symmetric games. We prove that some basic protocols can be realized using symmetric games.
Keywords: Population protocols, computation theory, distributed computing, algorithmic game theory