TOP
Search the Dagstuhl Website
Looking for information on the websites of the individual seminars? - Then please:
Not found what you are looking for? - Some of our services have separate websites, each with its own search option. Please check the following list:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Seminars
Within this website:
External resources:
  • DOOR (for registering your stay at Dagstuhl)
  • DOSA (for proposing future Dagstuhl Seminars or Dagstuhl Perspectives Workshops)
Publishing
Within this website:
External resources:
dblp
Within this website:
External resources:
  • the dblp Computer Science Bibliography


Dagstuhl Seminar 17111

Game Theory in AI, Logic, and Algorithms

( Mar 12 – Mar 17, 2017 )


Permalink
Please use the following short url to reference this page: https://www.dagstuhl.de/17111

Organizers

Contact


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.
Copyright Swarat Chaudhuri, Julian Gutierrez, Sampath Kannan, Rupak Majumdar, and Michael J. Wooldridge

Summary

The Dagstuhl Seminar 17111: Game Theory in AI, Logic, and Algorithms was held from March 12--17, 2017. The seminar explored research challenges at the interface of computing and game theory. This area has seen fervent research activity in recent times. 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; in formal methods, model checking and synthesis problems have been studied using game-theoretic concepts; and in artificial intelligence, game theory has come to provide the fundamental conceptual vocabulary for the field of multi-agent systems. Despite this manifest common interest, there is surprisingly little trade between game-theoretic approaches in these different subfields of computer science. Our aim in this seminar was to start to build some bridges between these three areas.

Copyright Swarat Chaudhuri, Sampath Kannan, Rupak Majumdar, and Michael J. Wooldridge

Participants
  • Natasha Alechina (University of Nottingham, GB) [dblp]
  • Eric Balkanski (Harvard University - Cambridge, US) [dblp]
  • Suguman Bansal (Rice University - Houston, US) [dblp]
  • Patricia Bouyer-Decitre (ENS - Cachan, FR) [dblp]
  • Tomáš Brázdil (Masaryk University - Brno, CZ) [dblp]
  • Véronique Bruyère (University of Mons, BE) [dblp]
  • Swarat Chaudhuri (Rice University - Houston, US) [dblp]
  • Yiling Chen (Harvard University - Cambridge, US) [dblp]
  • Yuan Deng (Duke University - Durham, US) [dblp]
  • Rayna Dimitrova (MPI-SWS - Kaiserslautern, DE) [dblp]
  • Rüdiger Ehlers (Universität Bremen, DE) [dblp]
  • Kousha Etessami (University of Edinburgh, GB) [dblp]
  • Bernd Finkbeiner (Universität des Saarlandes, DE) [dblp]
  • Valentin Goranko (University of Stockholm, SE) [dblp]
  • Julian Gutierrez (University of Oxford, GB) [dblp]
  • Paul Harrenstein (University of Oxford, GB) [dblp]
  • Hanno Hildmann (Univ. Carlos III - Madrid, ES) [dblp]
  • Justin Hsu (University of Pennsylvania - Philadelphia, US) [dblp]
  • Rasmus Ibsen-Jensen (IST Austria - Klosterneuburg, AT) [dblp]
  • Nicole Immorlica (Microsoft New England R&D Center - Cambridge, US) [dblp]
  • Wojtek Jamroga (Polish Academy of Sciences - Warsaw, PL) [dblp]
  • Sampath Kannan (University of Pennsylvania - Philadelphia, US) [dblp]
  • Jan Kretinsky (TU München, DE) [dblp]
  • Antonin Kucera (Masaryk University - Brno, CZ) [dblp]
  • Orna Kupferman (Hebrew University - Jerusalem, IL) [dblp]
  • Martin Lange (Universität Kassel, DE) [dblp]
  • Kim Guldstrand Larsen (Aalborg University, DK) [dblp]
  • Rupak Majumdar (MPI-SWS - Kaiserslautern, DE) [dblp]
  • Nicolas Markey (IRISA - Rennes, FR) [dblp]
  • Daniel Neider (MPI-SWS - Kaiserslautern, DE) [dblp]
  • Evdokia Nikolova (University of Texas - Austin, US) [dblp]
  • Doron A. Peled (Bar-Ilan University - Ramat Gan, IL) [dblp]
  • Sophie Pinchinat (IRISA - Rennes, FR) [dblp]
  • Maria Polukarov (University of Southampton, GB) [dblp]
  • Jean-Francois Raskin (Free University of Brussels, BE) [dblp]
  • Sanjit A. Seshia (University of California - Berkeley, US) [dblp]
  • Arunesh Sinha (University of Michigan - Ann Arbor, US) [dblp]
  • Tami Tamir (The Interdisciplinary Center - Herzliya, IL) [dblp]
  • Moshe Y. Vardi (Rice University - Houston, US) [dblp]
  • Igor Walukiewicz (University of Bordeaux, FR) [dblp]
  • Michael J. Wooldridge (University of Oxford, GB) [dblp]
  • Mihalis Yannakakis (Columbia University - New York, US) [dblp]

Classification
  • artificial intelligence / robotics
  • data structures / algorithms / complexity
  • verification / logic

Keywords
  • game theory
  • verification
  • algorithms
  • logic