Two classes of infinite duration games

János Flesch
Maastricht University
Friday, 6 June, 2014 - 02:00
NO Building, room 2NO9.06

During this talk, I discuss two classes of infinite duration games that are related to each other. I give an overview of the main questions and results, recent developments, and also a bit of the underlying techniques. I devote special attention to the zero-sum case (i.e. when there are only two players and they have completely opposite interests).

I consider games that are played on a state space (think of positions) by a number of players. At time period 1, the play of the game is in an initial state, where each player has to choose an action from a given action set. These choices are made simultaneously and independently. Then, according to a probability distribution that depends on the chosen actions and the state, the play moves to a new state. At time period 2, in the new state, the players choose actions again, and so on. This is repeated infinitely long.

In the first class of games, the players receive an instantaneous reward at every time period, as a function of the actions and the current state at that time period. Each player's goal is then to maximize his/her long-term average reward. 

In the second class of games, it is assumed that in every state, only one player has more than one action (the interpretation is that this player controls the state). But the evaluation of the play is very general, that is, each player is given a payoff function that assigns a real number to each infinite sequence of states and actions that can arise by playing the game. Then, his/her goal is to maximize this payoff function. 

During this talk, we are mainly interested in the following solution concepts: (approximately) optimal strategies in the zero-sum case, and (approximate) Nash or subgame-perfect equilibria in the general case (so the non-zero-sum case).