Abstracts


Roderick Bloem: "Property synthesis"

Property Synthesis is the problem of generating a correct system from its specification. Long thought completely intractable, this problem has received significant attention in recent years. The synthesis problem is typically solved using games, and an efficient solution requires both an appropriate formalisation of requirements and efficient algorithms to solve the associated games. Practical implementations of these algorithms quickly raise new questions: Some requirements are hard to express in logics like Linear Temporal Logic. One example is robustness (the system behaves ``reasonably even if the environment does not). Another example concerns higher level properties such as ``the grant signal is raised as soon as possible. These questions in turn lead to new game-theoretic questions that we will adress in this talk.


Thomas Colcombet: "An introduction to distance automata"

Distance automata (also called min-plus automata) are finite state automata with some counting capabilities. They form the particular case of weighted automata over the tropical semiring (i.e., the semiring (N,min,+) of non-negative integers equipped with the sum as product, and minimum as addition).

This model of automata is of interest both for its applications, such as in speech recognition, and its theoretical use, for instance in the resolution difficult language theoretic problems such as the star height-problem.

This tutorial is an overview of some aspects of this rich theory.

Slides (Adobe Flash)


Paul Goldberg: "Nash equilibrium and computational complexity"

Nash equilibrium computation is an unusual problem, due to two features: it seems to be computationally hard in the worst case, but also we have, due to Nash's theorem, that an equilibrium is guaranteed to exist for any game. Recent results that Nash equilibrium and market price equilibrium are characterised by the complexity class PPAD have called attention to this topic.

In the talk I will explain PPAD and what it means for the problem to be PPAD-complete. I will also give a brief introduction to recent work on the PSPACE-completeness of solutions obtained by "path-following" algorithms. These new results show an even closer relationship between games, and the "end-of-line" search problem on large graphs that chararcterises PPAD.

Slides (PDF)


Tristran Tomala: "Secure Communication in Networks: Mechanism Design, Games and Cryptography"

This lecture combines two approaches to secure communication. Mechanism design theory studies which decisions can be implemented by an equilibrium of a communication game between players who are informed of their characteristics and a designer who chooses an outcome. The well-known revelation principle states that for every such game, its equilibria can be implemented by direct and private communication between the players and the designer. On another hand, computer science often models communication possibilities by means of communication networks where agents are linked when they have the ability to communicate privately. Our aim is to characterize the communication networks which are as good as direct and private communication. Namely, those networks for which any equilibrium outcome of a direct communication game can be replicated by an equilibrium of the game of communication within the network.

We will first review some results from the cryptography literature for secure communication on 2-way networks (undirected graphs) and show a form of equivalence between the concepts from cryptography and those from mechanism design.

Secondly, we study 1-way networks (directed graphs). A common assumption in mechanism design is the existence of a worst outcome (i.e. a bad decision). We will characterize the directed networks for which secure communication is possible in environments with a worst outcome and study the corresponding cryptographic concepts.

Slides (PDF)


Wieslaw Zielonka: "Infinite perfect information games"

We consider two player infinite games where at each moment both players have all information concerning the past, they know the sequence of visited states and the actions up the the current moment. We are interested in the question when the players have optimal memoryless deterministic strategies. A precise response can be given for finite state deterministic games. No such exact characterization is known for stochastic games, but the problem of the existence of optimal memoryless deterministic strategies for two player games can be reduced to the same problem for one player games where a convenient sufficient condition is known.

These general results will be applied to parity games. This allows to show that parity games are closely related to stopping games where for each state there is a positive probability that the game stops visiting the state.

Slides Part 1 (PDF) Slides Part 2 (PDF)


Fedor Fomin: "Graph searching"

In graph searching a set of searchers (pursuers) is trying to capture a fugitive (evader) residing in a graph. The usual task of graph searching is to find the minimum number of searchers sufficient to catch the fugitive. There are many different models of graph searching which depend on the dynamics of searchers and fugitives, phase restrictions, conditions of captures, global restrictions, visibility, etc. In this tutorial we discuss several classical models and relations of searching to different ``width" parameters like pathwidth and treewidth.