I presented my paper The determinacy of infinite games with eventual perfect monitoring in the theory bag lunch a couple of weeks ago, and I promised some open problems, which I didn’t deliver yet. Well, we have a blog now, so here goes:
I consider in this paper an infinite general two-player zero-sum game with imperfect monitoring. These games are generalizations of Gale-Stewart games to the case in which players don’t observe opponent’s past actions immediately after they are played.
More formally, a game is given by a finite set of actions, a subset of , the winning set of player 1, and a monitoring structure which I will describe in a moment. The game is played in stages: First player 1 picks an action ; Then, player 2 picks an action ; Then player 1 picks ; then player 2 picks and so on, ad inifinitum. By the time infinitum arrives, the players have created an infinite play path . If the play path is in , player 1 wins. Otherwise, player 2 wins.
The last piece in the description of the game is the monitoring structure. Monitoring is the term game theorists use to describe observation of opponent’s actions. In the original Gale-Stewart setup, each player observed the actions of the opponent immediately after they were played. So before the player that plays at stage picks , he knows the partial history . In my setup this is not necessarily the case. The players might know something about the partial history that was already played before they pick their action, but not necessarily everything. More formally, for every there is an equivalence relation over partial histories of length and the player that plays at stage can’t distinguish between -equivalent histories.
Now that the game is well defined, you know what strategy is, and if you know something about zero-sum games you might ask yourself the million dollar question — Does the game admit a value ?
Well, the answer is not necessarily. However, I prove that if the monitoring structure satisfies a condition I call `eventual perfect monitoring’ then the game has a value. What this condition means is that, regardless of the play path, every player knows all the previous actions of the opponent. Not necessarily immediately, it may take some delay, and the delay may depend on the actual play path, but at the day of reckoning (aka infinity) every action is known and all secrets are resolved:
Theorem An infinite zero-sum game with Borel winning set and eventual perfect monitoring admits a value
(Don’t bother about the Borel thing now, it’s not the issue)
Question 1 — Suppose that the monitoring structure is such that not all actions are revealed, but still every player knows the identity of the winner at infinity for every play path. Does the game still admit a value ?
Question 2 — What about general payoff function ? suppose that at infinity player 2 pays player 1 an amount where is a Borel function. Under eventual perfect monitoring, does the game still admits a value ?
Btw, I could also combine the two questions — what if the payoff is given by an arbitrary Borel function, and the monitoring structure is such that at infinity every player knows the payoff in the game ? To this question I actually know the answer already. Which means you know it too, given what I already said about what I know. But maybe you don’t see the proof. Well, I might write about some other time. Meanwhile, if you are curious, then this paper (jstor) by Dinah and Nicolas might be helpful..