gasics'11 

Scope of the workshop

GASICS is an ESF project of the EUROCORES programme LogICCC (Modelling intelligent interaction – Logic in the Humanities, Social and Computational sciences ). It studies game theoretic formalizations of interactive computational systems and algorithms for their analysis and synthesis. Our aim is to extend the existing notions of games played on graphs introduced by computer scientists. Currently, most of the games played on graphs are of the sort "two-player zero-sum", we aim to extend them to "multiple-player non-zero-sum", and show the applicability of the new theory to the analysis and synthesis of interactive computational systems.

The aim of this workshop is to bring together researchers working on game-related subjects, and to discuss on various aspects of game theory in the fields where it is applied. The workshop will be composed of two invited talks, together with contributed talks on the following (non-exhaustive) list of relevant topics:

• Adapted notions of games for synthesis of complex interactive computational systems
• Games played on complex and infinite graphs
• Games with quantitative objectives
• Game with incomplete information and over dynamic structures
• Heuristics for efficient game solving.

Previous editions of the workshop

Invited speakers

• Hugo Gimbert:
  Playing in the dark

  We consider partially observable Markov decision processes with finitely many states and actions.

  When playing in the dark, a player has no feedback about the decisions he takes: he does not know what is the state of the game or whether he has won or not.

  A classical result of Paz shows that the value of such games is not computable in general. We will survey recent negative and positive results: on one hand other similar decision problems are undecidable and on the other hand restricting the class of input games turns some of these decision problems into decidable problems.

• Marcin Jurdziński:
  What is the search complexity of computing optimal strategies?

  The problems of deciding the winner in parity, mean-payoff, discounted and other related games are known to be both in NP and co-NP, and hence unlikely to be complete for either of the two. A less-known observation is that the search problems of finding optimal strategies in such games are known to be both in PLS and PPAD, and hence unlikely to be complete for either of the two classes (PLS and PPAD are important sub-classes of TFNP—"total-function NP"—and hence also of FNP, a natural counterpart of NP in the context of search problems). This talk will survey a hierarchy of search complexity classes from FNP, to TFNP, PLS, PPAD, to other recently identified subclasses of both PLS and PPAD; some important fixed-point and equilibrium search problems that are complete for PLS and PPAD; and the relationship between the search problem of finding optimal strategies in games on graphs and the linear complementarity problem (LCP), a fundamental problem in mathematical optimization. Some open questions will be posed aimed towards establishing completeness results for the problems of finding optimal strategies in games and of solving subclasses of the LCP, akin to PPAD-completeness of computing Nash equilibria.

Programme

Organizers

• Kim G. Larsen
• Nicolas Markey
• Jean-François Raskin
• Wolfgang Thomas

Programme Committee

• Véronique Bruyère
• Kim G. Larsen
• Nicolas Markey
• Jean-François Raskin
• Pierre-Yves Schobbens
• Olivier Serre
• Wolfgang Thomas