Invited speakers
The morning sessions will be devoted to tutorials on topics closely related to strategic reasoning:- Edith Elkind (U. Oxford):
"Strategic behavior in social choice".
Abstract: applications of voting systems range from political elections to ranking universities and making funding decisions. In this tutorial, we will discuss various aspects of strategic behavior in voting, with a focus on the analysis of voting equilibria. - Marcin Jurdziński (U. Warwick):
"Quasi-polynomial algorithms for solving parity games".
Abstract: Parity games have played a fundamental role in automata theory, logic, and their applications to verification and synthesis since early 1990's. Solving parity games is polynomial-time equivalent to checking emptiness of tree automata and to the modal mu-calculus model checking. It is a long-standing open question whether there is a polynomial-time algorithm for solving parity games. The~quest for a polynomial-time algorithm has not only brought diverse algorithmic techniques to the theory and practice of verification and synthesis, but it has also significantly contributed to resolving long-standing open problems in other research areas, such as Markov Decision Processes and Linear Programming.In the first part of this course, I will survey some of the algorithmic techniques that have been developed for solving parity games until 2016, such as recursive divide-and-conquer algorithms, progress measures, and strategy improvement. In the second part, I will present new algorithmic techniques that have sprung after the first quasi-polynomial-time algorithm for solving parity games was developed by Calude et~al. in~2017, such as ordered tree coding, universal trees, succinct progress measures, and separating automata, and I will discuss their provable limitations in the ongoing quest for a polynomial-time algorithm.