Efficient computation is a spinal backbone of modern society, including communication, transportation, production as well as services. In almost all domains, computation takes place in a networked system of interacting entities. Once these entities act on their own behalf, we are faced with the challenge to model, analyze, and anticipate the phenomenon of strategic behavior. Even if an accurate model for strategic behavior of interacting entities has been obtained, the crucial challenge to actually solve the model (e.g. to compute an equilibrium) remains. Polynomial time computation of the outcome of strategic behavior and its computational complexity is the core issue addressed in the field of Algorithmic Game Theory. It builds upon the concepts and models developed at the intersection of Economics and Theoretical Computer Science and has lately become an influential field particularly in Computer Science.
In the traditional approach to network analysis and design (traffic networks, data networks, etc.), the vast majority of models has focused on two limit cases: In the static regime, the attributes of the network are assumed effectively static and the system’s analysis relies on techniques from optimization, game theory and (optimal) control. On the other hand, in the so-called stochastic regime, the network is assumed to evolve randomly following some stationary probability law, and the allocation of resources is optimized using tools from stochastic optimization and control. In modern networks, however (such as the Internet, cognitive radios and wireless networks), both assumptions fail because of factors that introduce unpredictable variability to the system (for instance, users going arbitrarily on- and off- line, non-random capacity fluctuations, etc.). As a result, existing resource allocation schemes do not – in fact, cannot – apply in this setting because “optimum” target states no longer exist, either static or in the mean. In view of the above, we envision a drastic turn towards a flexible resource allocation paradigm (i.e. without any prior system knowledge) based on game theory, machine learning and the deployment of online optimization protocols at the network’s decision-making level.
Graph games are a mathematical framework to analyze reactive systems. A reactive system interacts with an environment and it consists of several variables. Consider the example of a train-gate controller, where there is a variable for the gate position (say, open, closed, closing), and a variable to denote positions of trains (say, away, approaching, at gate, crossed, gone). A state of the system is a valuation to the variables, such as the gate being open and train being away, or a train is approaching and the gate is closing. In graph games vertices of the graph represent states of the reactive system, edges of the graph represent transition of the reactive systems, paths of the graph represent behaviors of the system, and different interacting agents represent the different players. The associated research problem is the algorithmic and computational complexity analysis of games on graphs. In deterministic reactive systems, these questions have been quite deeply studied. The significant theoretical achievements have resulted in several algorithms and satisfactory computational complexity results for deterministic graph games with respect to omega-regular objectives (omega- regular objectives can express all commonly used properties of reactive systems). These algorithms can be used in practice, such as, automatically deriving AMBA-Bus protocol, widely used in industries, and the game- theoretic algorithms are routinely used in correctness analysis of complex, safety-critical systems.
Stochastic games comprise a general model for the study and analysis of dynamic interactions in economic and technological contexts. It includes the theory of repeated games, stopping games, differential games and mean-field games. Since its beginning, the main fields where repeated games are applied are economics, finance, biology, engineering and computer science, and it is impossible to overestimate the impact that the theory of stochastic games has had in these fields – as evidenced by the many game theorists that have been awarded the Nobel memorial prize in economics for their contributions to the theory of stochastic games. Recent advances in stochastic games include new computational tools, and approaches in continuous time, which are also the main tasks of this working group. Faced by the new applications and problems described in WGs 2 and 3, the role of this WG is to support the applications in these fields, by developing the rigorous mathematical foundations for the game problems arising therein.