01.02.15 - 06.02.15, Seminar 15061

Non-Zero-Sum-Games and Control

Diese Seminarbeschreibung wurde vor dem Seminar auf unseren Webseiten veröffentlicht und bei der Einladung zum Seminar verwendet.

Motivation

Non-zero-sum games with quantitative objectives constitute a field of growing attraction that is of central interest in all scenarios of computer science where multi-agent reactive systems are studied. The purpose of the seminar is to push forward and integrate the rapidly developing research on non-zero-sum games in its many facets (e.g., timed games, priced timed games, stochastic games, energy games, games with multidimensional optimization criteria, etc.), and to build bridges to related fields, in particular to control engineering.

The interactions in such games are not purely antagonistic as in two-person games but mix collaboration, hostility and optimization. Let us mention questions to be pursued in this context:

Games with quantitative objectives. A starting point is the study of mean-payoff games, a class of games that is still closely related to the classical two-player setting of parity games. The solvability of these games in polynomial time is a long-standing open problem. A great number of variants have been proposed with very interesting applications, for instance energy games that involve the objective to keep values of prefixes of plays within certain bounds; other examples are stochastic games and timed (priced) games. Many promising results have been obtained, e.g. on the computability of optimal or near-optimal strategies in such games. But often the computational complexity involved is open, as is the question how to reconcile multiple (and possibly conflicting) quantitative objectives.

Equilibria in multiplayer games. In multiplayer games, aspects of partial information (or "concurrency") enter, and "winning objectives" are replaced in terms of diverse notions of equilibria that capture an "optimal" behavior of the participating players. There is a host of open questions in this field, not only concerning the existence of equilibria, but more so the computational complexity of finding – and ensuring – such equilibria, and the choice of "good" equilibria.

Controller synthesis, supervisory control. In the field of control engineering, the work on supervisory control of discrete event systems has shifted towards problems of distributed or decentralized control, where a set of controllers cooperate as a team in order to achieve a specification (possibly in the form of a quantitative objective) on the entire system behavior, in the presence of a reactive environment. For instance, costly sensors and actuators, as well as costly communication, lead to challenging synthesis problems, both conceptually (e.g., characterization of the information structure) and computationally.

Tools for Synthesis. While tools for automatic program verification ("model-checkers") are well established both in academic research and in industry, tools supporting synthesis even in restricted scenarios are still in the beginning.

A first goal is the assessment of the extremely rich landscape of current work in the fields outlined above. A second goal is to work out essentials in the fields mentioned, as an attempt to shape the state-of-the-art (say in survey articles). We think of having an invited talk for each of the topics mentioned above to support this aim. The last and (maybe self-evident) goal is of course to detect problems and approaches where the represented communities from automata theory, logic, formal methods, game theory, and supervisory control can join their forces.