Markov decision processes (MDPs) are a standard model for dynamic systems that exhibit both stochastic and nondeterministic behavior. For MDPs with finite state space it is known that for a wide range of objectives there exist optimal strategies that are memoryless and deterministic. In contrast, if the state space is infinite, optimal strategies may not exist, and optimal or ε-optimal strategies may require (possibly infinite) memory. In this talk we consider qualitative objectives: reachability, safety, (co-)Büchi, and other parity objectives. The aim is to give an introduction to a collection of techniques that allow for the construction of strategies with little or no memory in countably infinite MDPs. Joint work with Richard Mayr, Mahsa Shirmohammadi, Patrick Totzke, Dominik Wojtczak.

I will talk about countably infinite Markov decision processes with Büchi objectives, which ask to visit a given subset F of states infinitely often. This talk is based on a collaboration with Stefan Kiefer, Patrick Totzke and Richard Mayr, with the full version here.

A question left open by T.P. Hill in 1979 is whether there always exist epsilon-optimal Markov strategies, i.e., strategies that base decisions only on the current state and the number of steps taken so far. I will talk about the negative answer we provided to this question, and give intuitions on why Markov strategies with only 1 bit of extra memory are sufficient.

We consider both concurrent and turn-based 2-player stochastic games on countably infinite game graphs. The reachability objective is arguably one of the most basic objectives in graph games: A play satisfies the objective iff it ever visits a given set of target states. The Maximizer (resp. Minimizer) player aims to maximize (resp. minimize) the probability of the objective, i.e., the probability of visiting the set of target states. We give an overview about how much memory is required for good Maximizer (resp. Minimizer) strategies in different variants of reachability games, where "good" means epsilon-optimal or optimal, respectively. The full version is here.

We study Markov Decision Processes with stage payofss. In the litterature, many different ways to aggregate these stage payoffs have been introduced: finite average, discounted average, weighted average, inferior limit of the mean average,... I will present several recent results obtained in a series of papers proving links between these notions for MDP with finite state space and finite actions spaces.

We consider matrix games from the dynamic perspective where players move in turns and actions chosen remain fixed for two stages. So, for a game based on matrix \(A\), player 1 initiates play by choosing row \(i_1\), next player 2 chooses column \(j_1\) and player 1 receives \(A(i_1,j_1)\) by player 2, next player 1 chooses row i_2 and receives \(A(i_2,j_1)\), next player 2 chooses \(j_2\) and player 1 receives \(A(i_2,j_2)\), and so on. We assume that player 1 wants to maximize the long run average of \(A(i_1,j_1), A(i_2,j_1), A(i_2,j_2), A(i_3,j_2), A(i_3,j_3), A(i_4,j_3), ...\), while player 2 wants to minimize that number. We show that this cycle value exists and can be achieved by pure strategies. However, it is not immediately obvious how to explicitly find these.

In adversarial patrolling, a mobile Defender strives to discover possible ongoing intrusions at vulnerable targets initiated by the Attacker. The task of constructing an optimal Defender's strategy achieving the optimal protection can be formalized as a graph game of two players. In the talk, we overview the basic solution concepts, strategy synthesis techniques, and discuss the role of randomization.

In this talk I will present two results: first, an explicit formula for their value, second, an algorithm that is derived from it and which is "as efficient as it can be".

References

• Luc Attia and Miquel Oliu-Barton -- A formula for the value of a stochastic game, PNAS 2019
• Miquel Oliu-Barton -- New Algorithms for Solving Zero-Sum Stochastic Games, Mathematics of Operations Research, Vol 46, No 1, 2020

We analyze an asynchronous variation of the DeGroot dynamics. In this model, we study the convergence of opinions, the consensus of the limiting opinions, and the ability to aggregate information (``wisdom of the crowd''). The results are obtained for both finite and infinite networks. We provide estimates of the speed of convergence in finite networks. A fragmentation process of independent interest is found to be closely related to the asynchronous DeGroot, and this relation is the basis of our analysis.
Joint with Galit Ashkenazi-Golan, Dor Elboim, and Yuval Peres.

In this talk, we will present the notion of adversarial Stackelberg value for two-player non-zero sum games played on bi-weighted graphs with the mean-payoff and the discounted sum functions. The adversarial Stackelberg value of Player 0 is the largest value that Player 0 can obtain when announcing her strategy to Player 1 which in turn responds with any of his best response. For the mean-payoff function, we show that the adversarial Stackelberg value is not always achievable but ε-optimal strategies exist. We show how to compute this value and prove that the associated threshold problem is in NP. For the discounted sum payoff function, we draw a link with the target discounted sum problem which explains why the problem is difficult to solve for this payoff function. We also provide solutions to related gap problems.

In this talk, we present the framework of two-player Stackelberg games played on graphs in which Player 0 announces a strategy and Player 1 responds rationally with a strategy that is an optimal response. While it is usually assumed that Player 1 has a single objective, we consider here the new setting where he has several. In this context, after responding with his strategy, Player 1 gets a payoff in the form of a vector of Booleans corresponding to his satisfied objectives. Rationality of Player 1 is encoded by the fact that his response must produce a Pareto-optimal payoff given the strategy of Player 0. We study the Stackelberg-Pareto Synthesis problem which asks whether Player 0 can announce a strategy which satisfies his objective, whatever the rational response of Player 1. We solve this problem for several types of omega-regular objectives. In particular, for games with parity objectives, we show that this problem is fixed-parameter tractable and NEXPTIME-complete. We also discuss the related Stackelberg-Pareto Verification problem which asks whether a given finite-memory strategy announced by Player 0 satisfies his objective, whatever the rational response of Player 1.

Percolation games is a new class of zero-sum stochastic games, where two players move in turn a ball on the vertices of \(\mathbb{Z}^d\). The stage payoff is stochastic and its distribution depends on the position of the ball. Conditions are provided under which the \(n\)-stage game value has a limit. Connections to first-passage percolation and homogenization of Hamilton-Jacobi equations are discussed. This talk is based on several works with Guillaume Garnier, Luc Attia and Raimundo Saona.

This talk will consider a special case of two-player zero-sum concurrent stochastic mean-payoff games, called absorbing games, where only one state can be left once entered. It will show that such games have epsilon-optimal strategies that uses a clock (=knowledge of how many rounds into the game we are) and 2 bits of memory. In contrast, it is known that in concurrent stochastic mean payoff games (or absorbing games for that matter), in general, a strategy that uses finite memory without a clock or a clock and deterministically updated finite memory cannot ensure anything.

We consider asymptotics of finite zero-sum stochastic games. Bewley and Kohlberg established in 1976 that the discounted value converges when players fully observe the state ; in 2016 Ziliotto constructed an example in which the state is not observed at all and the value oscillates. We investigate the middle ground in which the state is publicly observed at some stages, chosen either deterministically or randomly.

We introduce a discrete-time search game, in which two players compete to find an invisible object first. The object moves according to a time-varying Markov chain on finitely many states.The players are active in turns. At each period, the active player chooses a state. If the object is there then he finds the object and wins. Otherwise the object moves and the game enters thenext period.

We show that this game admits a value, and for any error-term \(\varepsilon > 0\), each player has a pure (subgame-perfect) \(\varepsilon\)-optimal strategy. Interestingly, a 0-optimal strategy does not always exist. We derive results on the analytic and structural properties of the value and the \(\varepsilon\)-optimal strategies. We devote special attention to the important time-homogeneous case, where additionalresults hold.

This talk focuses on the population control problem. In this setting, an arbitrarily large yet finite population of agents is controlled in a dynamic way, in an infinite sequence of steps. Each agent is modelled as a copy of a finite-state system. At each step, a controller applies the same action to every agent, and every agent performs a local transition.

This setting is inspired by the control of a biological system, namely a population of yeasts, where the controller may only change the environment common to all cells.

We review some recent decidability and complexity results in two cases: when agents are adversarially strategic (zero-sum game) and when they behave randomly (Markov Decision Process). We also present some open questions.

References

• Nathalie Bertrand, Miheer Dewaskar, Blaise Genest, Hugo Gimbert, and Adwait Amit Godbole. Controlling a population. Logical Methods in Computer Science, 2019
• Corto Mascle, Mahsa Shirmohammadi, Patrick Totzke: Controlling a Random Population is EXPTIME-hard. Arxiv 2019
• Ohlmann, Pierre, Nathanaël Fijalkow, and Thomas Colcombet. “Controlling a random population.” Logical Methods in Computer Science 17 (2021)

We study infinitely repeated games where each player has to pay a certain (switching) cost each time she changes her action. We show that whenever the players are patient enough, the Folk Theorem holds. Moreover, we show that if the switching costs are symmetric, the set of equilibrium payoffs is obtained by considering the payoffs of a simple one-shot auxiliary game. This generalizes previous studies of the equilibrium payoffs in limit cases and under the assumption that switching costs are independent of the actions being switched. Finally, we show that the introduction of switching costs have a negative impact on a player in the infinitely repeated game but can be beneficial for him in a finitely repeated game.