Résumé du cours

Séance 1 : Two‑player Turn‑based Stochastic Games
In the first lecture we define the two‑player Turn‑Based Stochastic Games (TBSGs), the most general games considered in this lecture series. We define the objectives of the two players, the strategies that they can use, and define the values of the games. We then consider algorithms for finding the values and optimal strategies, first in one‑player games and then in two‑player games. While for one‑player games polynomial time algorithms are known, for most two‑player games no polynomial time algorithms are currently known.

Séance 2 : Mean Payoff games and Energy Games
In this talk we consider non‑stochastic versions of the games introduced in the first lecture, namely Mean Payoff Games (MPGs) and Energy Games (EGs). We show reductions between these two games. We then describe a pseudo‑polynomial time algorithm of Brim et al. for EGs, and hence also MPGs.

Séance 3 : Randomized sub‑exponential time algorithm
In this talk we present an elegant randomized algorithm that solves all the games we consider in sub‑exponential time. This is currently the fastest known algorithm for TBSGs, and also for MPGs and EGs, when there is no restriction on the edge costs. The algorithm is an adaptation of a randomized algorithms of Kalai and Matousek, Sharir and Welzl for solving linear programs. We also mention relations to abstractions of Linear Programming abstractions.

Séance 4 : Parity Games
In this lecture we consider Parity Games (PGs), a very special case of MPGs, with many relations to automata on infinite words and to automatic verification. In a recent breakthrough Calude et al. recently obtained a quasi‑polynomial time algorithm for solving PGs. We will describe one of the existing variants of their algorithm.

Séance 5 : Acyclic Unique Sink Orientations (AUSOs)
In this lecture we consider Acyclic Unique Sink Orientations (AUSOs) an abstraction related to linear programming that also captures the games we are interested in. We present algorithms for finding the sink of an AUSOs, which directly translate to algorithms for solving games.

Séance 6 : Lower bounds for Policy Iteration
Policy Iteration, introduced in the first lecture, is a very natural class of algorithms for solving TBSGs. Policy Iteration algorithms work very well in practice. However, we now know that their worst‑case complexity is exponential. We will present such lower bounds.

Séance 7 : Lower bounds for Random‑Facet and Random‑Edge
In this lecture we present sub‑exponential lower bounds for Random‑Facet (the randomized algorithm considered in Lecture 3) and Random‑Edge.

Télécharger l'affiche