In this thesis, we are concerned with multi-player games played on finite graphs. They are games in which the players interact trying to fulfil their own objectives which are not necessarily antagonistic to the others’. More particularly, we are interested in the study of dynamics which model the behaviour of the players when they repeatedly update their strategy in order to achieve a better outcome. A dynamics terminates when these updates converge to a state in which the players have no incentive to further update their respective strategies. We define several dynamics characterised by the type of updates made by the players.There are two types of contributions in this thesis. The first one is to draw a general framework to reason about the termination of dynamics in order to show its applicability to particular problems. In this abstract framework, we present several meta-theorems that make the links between games and dynamics explicit. For example, we introduce a notion of game minor that allows to induce simulations between the associated dynamics. The second type of contribution is the application of dynamics to a particular context, characterised by three parameters: the arena of the game, the conditions over the dynamics, and the payoff functions of the players. The first arena we deal with are sequential games (or games played on trees). Among other results, we prove that the acyclicity of the preferences is a necessary and sufficient condition to ensure the termination of dynamics that respect the Subgame Improvement Property (i.e. every update has to improve the payoff in the subgame of the change).Another studied arena is the so called One-player Games. We model BGP (Border Gateway Protocol, which is a standard interdomain routing protocol) into dynamics on graphs. We firstly revisit some classical results of network theory in our context, then we identify a theoretical and relevant framework regarding to the termination of the dynamics. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished
| Identifer | oai:union.ndltd.org:ulb.ac.be/oai:dipot.ulb.ac.be:2013/308082 |
| Date | 19 June 2020 |
| Creators | Hallet, Marion |
| Contributors | Geeraerts, Gilles, Brihaye, Thomas, Quoitin, Bruno, Raskin, Jean-François, Bouyer, Patricia, Bertrand, Nathalie |
| Publisher | Universite Libre de Bruxelles, Université de Mons, Faculté de Sciences, Département de Mathématiques - Docteur en Sciences, Université libre de Bruxelles, Faculté des Sciences – Informatique, Mons |
| Source Sets | Université libre de Bruxelles |
| Language | English |
| Detected Language | English |
| Type | info:eu-repo/semantics/doctoralThesis, info:ulb-repo/semantics/doctoralThesis, info:ulb-repo/semantics/openurl/vlink-dissertation |
| Format | 204 p., 3 full-text file(s): application/pdf | application/pdf | application/pdf |
| Rights | 3 full-text file(s): info:eu-repo/semantics/openAccess | info:eu-repo/semantics/closedAccess | info:eu-repo/semantics/restrictedAccess |
Page generated in 0.0021 seconds