This work focuses on the study of concurrent and timed games. These two classes of games have been useful models in controller synthesis. In situations where several agents interact, the notion of winning strategies used so far is not adapted and it is necessary to adopt concepts from game theory. The main concept considered in this area is that of Nash equilibrium. For concurrent games, we propose a transformation which draw a parallel between equilibria and winning strategies. Many works have focused on the computation of winning strategies and we can take advantage of the available algorithms. To compute equilibria in timed games we show that it is possible to reduce them to concurrent games. We propose algorithms for the computation of equilibria, first with classical objectives. Then, we propose a more general framework, in which more quantitative preferences can be described. We also study the theoretical complexity of the associated decision problems. Finally, we present a tool that implements one of the algorithms that we developed.
| Identifer | oai:union.ndltd.org:CCSD/oai:tel.archives-ouvertes.fr:tel-00827027 |
| Date | 29 November 2012 |
| Creators | Brenguier, Romain |
| Publisher | École normale supérieure de Cachan - ENS Cachan |
| Source Sets | CCSD theses-EN-ligne, France |
| Language | French |
| Detected Language | English |
| Type | PhD thesis |
Page generated in 0.0037 seconds