gasics'10 

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.

Invited speakers

• Krishnendu Chatterjee:
  Games with Finitary Parity and Streett Objectives

  In this talk we will present games with finitary parity and Streett objectives. The class of finitary objectives is a stronger condition than classical ω-regular conditions, and we will discuss how it gets rid of certain weakness of classical infinitary formulation. In this talk we will present results related to determinacy of these games, present algorithms and complexity for solving these games, and characterize the memory requirements of winning strategies. Our algorithms can be used, for example, for synthesizing controllers that do not let the response time of a system increase without bound.
• Antonín Kučera:
  Stochastic games with time

  Stochastic turn-based games can be seen as discrete-time Markov chains extended by non-deterministic vertices where the players can make their decisions. Similarly, one can consider game-theoretic extensions of stochastic processes with continuous time, such as continuous-time Markov chains, semi-Markov processes, or even generalized semi-Markov processes. In the talk we give an overview of recent results about this type of games.

Programme

Registration

Organizers

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

Programme Committee

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