Population protocols, games, and large populations

Abstract : Population protocols were introduced to capture the specifics of opportunistic networks of tny mobile agents with limited memory and capable of wireless communication in pairs. This thesis aims at extending the understanding and analysis of population protocols as well as their links to other models of population dynamics including ones from game theory. The first contribution of this thesis is to translate in terms of population protocols the dynamics of a population of agents playing a game repeatedly against each-other and adapting their strategy according to the PAVLOV behaviour. We show that protocols born from games are exactly as powerful as general population protocols. The second contribution consists in the study of the impact of symmetry on games and in the transitions of a population protocol to show that, if symmetric population protocols are equivalent to general protocols, symmetric games are significantly less powerful. The third contribution is to show how the dynamic of a population protocol can be approximated by an ordinary differential equation when the population grows to infinity. We then define a computation by a large population to be the convergence of this differential equation to a stable equilibrium. The fourth and final contribution of this thesis is the characterisation of the numbers computable in the above sense as exactly the algebraic real numbers in [0; 1].
Complete list of metadatas

Cited literature [48 references]  Display  Hide  Download

https://hal.inria.fr/tel-01274140
Contributor : Laurent Viennot <>
Submitted on : Monday, February 15, 2016 - 2:38:48 PM
Last modification on : Thursday, April 4, 2019 - 1:15:03 AM
Long-term archiving on: Monday, May 16, 2016 - 10:15:12 AM

Identifiers

  • HAL Id : tel-01274140, version 1

Collections

Citation

Xavier Koegler. Population protocols, games, and large populations. Networking and Internet Architecture [cs.NI]. Paris Diderot Unviersity, 2012. English. ⟨tel-01274140⟩

Share

Metrics

Record views

277

Files downloads

196