Game theory is a well-developed branch of mathematics that is applied to various domains like economics, biology, computer science, etc. It is the study of mathematical models of interaction and conflict between individuals and the understanding of their decisions assuming that they are rational [11, 13].The last decades have seen a lot of research on the automatic synthesis of reliable and efficient systems by using the mathematical framework of game theory. One important line of research is concerned with reactive systems that must continuously react to the uncontrollable events produced by the environment in which they evolve. A controller of a reactive system indicates which actions it has to perform to satisfy a certain objective against any behavior of the environment. An example in air traffic management is the autopilot that controls the trajectory of the plane to guarantee a safe landing without any control on the weather conditions. Such a situation can be modeled by a two-player game played on a finite directed graph: the system and the environment arc the two players, the vertices of the graph model the possible configurations of the system and the environment, and the infinite paths in the graph model the continuous interactions between them. As we cannot assume the cooperation of the environment, its objective is the negation of the objective of the system and we speak of zero-sum games. In this framework, checking whether the system is able to achieve its objective reduces to the existence of a winning strategy in the corresponding game, and building a controller reduces to computing such a strategy [8]. Whether such a controller can be automatically designed from the objective is known as the synthesis problem.In this talk, we consider another, more recent, line of research concerned with the modelization and the study of complex systems. Instead of the simple situation of a system embedded in a hostile environment, we are now faced with systems/environments formed of several components each of them with their own objectives that are not necessarily conflicting. An example is a communication network composed of several nodes, each of them aiming at sending a message to some other nodes by using a certain frequency range. These objectives are conflicting or not, depending on the used frequencies. We model such complex systems by multi-player non zero-sum games played on graphs: the components of the complex system are the different players, each of them aiming at satisfying his own objective. In this context, the synthesis problem is a little different: winning strategies are no longer appropriate and are replaced by the concept of equilibrium, that is, a profile of strategies, one for each player, such that no player has an incentive to deviate from the play consistent with this profile [9]. Different kinds of relevant equilibria have been investigated among which the famous notions of Nash equilibrium [10] and subgame perfect equilibrium [12].In the setting of multi-player non zero-sum games, classical questions are the following ones. What are the objectives for which there always exists an equilibrium of a certain given type? When the existence is not guaranteed, can we decide whether such an equilibrium exists or not. When the latter problem is decidable, what is its complexity class? Many results were first obtained for Boolean objectives, and in particular for ω-regular objectives like avoiding a deadlock, always granting a request, etc [8, 9]. In this context, an infinite path in the game graph is either winning or losing w.r.t. a player depending on whether his objective is satisfied or not. More recent results were then obtained for quantitative objectives such as minimizing the energy consumption or guaranteeing a limited response time to a request [6]. To allow such richer objectives, the game graph is augmented with weights and a payoff (or a cost) is then associated with each of its infinite paths [7]. When solving the above mentioned questions, for practical applicability of the studied models, it is also important to know how complex the strategies composing the equilibrium are. Given past interactions between the players, a strategy for a player indicates the next action he has to perform. The amount of memory on those past interactions is one of the ways to express the complexity of the strategy, the simplest strategies being those requiring no memory at all [8].In this talk, we focus on reachability objectives: each player wants to reach a given subset of vertices (qualitative objective) or to reach it as soon as possible (quantitative objective). We also restrict the discussion to turn-based games (the players choose their actions in a turn-based way, and not concurrently) and to pure strategies (the next action is chosen in a deterministic way, and not according to a probability distribution). For those games, we explain the different techniques developed and the results obtained for both notions of Nash equilibrium and subgame perfect equilibrium [1-5]. The talk is made accessible to a large audience through illustrative examples.
展开▼
