I defended my PhD thesis on Thursday, March 30th, 2017.
We study games played on graphs by an arbitrary number of players with non-zero sum objectives. The players represent agents (programs, processes or devices) that can interact to achieve their own objectives as much as possible. Solution concepts, as Nash Equilibria, for such optimal plays, need not exist when restricting to pure deterministic strategies, even with simple reachability or safety objectives. The symmetry induced by deterministic behaviours motivates the studies where either the players or the environment can use randomization. In the first case, we show that classical concepts are undecidable with a fixed number of agents and propose computable approximations. In the second case, we study randomization as a reasonable policy for scheduling an arbitrary number of processes.
A preprint version of the thesis manuscript is available here.