Uri Zwick (Université de Tel Aviv), lauréat en 2018 de la Chaire d'excellence de la FSMP, donne dans le cadre de son séjour à Paris un cours intitulé Games on Graphs and Linear Programming Abstractions, en salle 3052 du bâtiment Sophie Germain de l'Université Paris Diderot (1, place Aurélie Nemours, 75013 Paris), les mercredis de 14h15 à 16h15 du 20 mars au 22 mai 2019.
Résumé des séances
Cliquez ici pour un résumé global 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 \emph{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.