Game Theory in AI, Logic, and Algorithms

Motivation

One of the most striking growth areas in computer science over the past two decades has been research at the intersection of computing and game theory. On the one hand, game-theoretic ideas have found applications in many areas of computer science, while on the other, computer science has provided powerful tools with which to tackle game-theoretic problems. Specifically, game-theoretic ideas have found currency in three key areas of computer science:

• in the algorithms community algorithmic game theory is now a well-established sub-field, opening up a computational view on problems of social behavior in rational agents;

• in logic and formal methods, game-theoretic models and algorithms are critical tools in many important problems, including automated verification of multi-component systems and automated synthesis;

• in artificial intelligence, the field of multi-agent systems has found in game theory an appropriate vocabulary with which to understand the behaviour of interacting self-interested, semi-autonomous software agents.

Despite this manifest common interest, there is surprisingly little trade between these different sub-fields of computer science. Our aim in this Dagstuhl Seminar is to build bridges between these three areas. In particular, we aim to identify problems, themes, and models that occur across these three areas: both game theoretic questions that are relevant across the broad spectrum of computer science, and computational questions of relevance in game theory. Examples of topics that might be of interest include, but are certainly not restricted to, the following:

• Simple Stochastic Games: These are 2-player games played between a Max-player and a Min-player on a directed graph with 3 types of nodes – Max nodes, Min nodes, and average nodes. There is a distinguished start node and sink nodes labeled 1 or 0. The game starts with a token at the start node; If the token is at a Max (min) node, the Max (min) player respectively moves it to an out-neighbor of her choice, while if it is at an average node, it is moved to a random out neighbor. The game stops when a sink is reached – and the value of the game is the value at that sink. The Max (min) player seeks to maximize (minimize) the expected value of the game and it can be shown that both players have memoryless strategies that are optimal. The problem is to determine whether the game has a value strictly greater than 1/2. While much is known about the complexity of this problem, the question of whether it has a polynomial-time algorithm remains tantalizingly open. Of note for this seminar, this problem is of great interest to formal methods researchers as well, since it is closely tied to the problem of model-checking mu-calculus.

• Network Formation Games and Network Games: Typical formulations of network formation games assume that each agent is a node in a graph (to be formed). Agents may pay to form links/edges with other agents; they may also pay to give their nodes certain attributes. The payoff to each agent is a function of the attributes of the agent's node as well as the links he has bought. Equilibria, the price of stability, etc. in such games can be studied not only from a theoretical perspective, but also from an experimental one. In network games, the network is assumed to exist, but agents can only interact with their neighbors. There may no longer be one prevailing equilibrium, but local equilibria in each neighborhood, and the goal is to understand how these equilibria vary as a function of the network structure and the attributes of nodes. Games combining both of the above have also been considered by both AGT researchers and researchers in AI.

• Games against Nature, Multi Armed Bandits, and Markov Decision Processes: All of these problem areas feature decision-making under uncertainty and can be viewed as games against an opponent who plays stochastically (sometimes thought of as “nature”). The multi-armed bandit problem (named for slot machines with many arms that one could pull to receive varying rewards) has many variants – the rewards of each arm are chosen from unknown distributions, chosen adversarially, and chosen in a Markovian manner – where each pull of an arm moves the system to a different state. This last model has similarities with Markov Decision Processes that are studied both by AI researchers and more recently by researchers in formal methods.