When studying games in a set-theoretical context, we’re mostly interested in the existence of winning strategies — that the given game is determined. Underlying the game-theoretic framework however, there’s an assumption which usually is assumed without much thought: that both players have perfect information. There’s nothing hidden, like what you got on your hand in poker or which routes you’re trying to build in Ticket to Ride. What happens to our determinacy questions if we allow hidden information?
Let’s first of all recall the basic game-theoretic components, so that we’ll be able to model the hidden information by tweaking those components. For simplicity we’ll be focusing on the “standard integer games”, but the same components and tweaks apply to other games as well. Let and define the game as follows.
Here and player I wins iff . A strategy for player I is then a function , where we interpret this as taking as input some partial play of in which it’s player I’s turn, e.g.
and then outputting player I’s response to this partial play. The resulting play in which player I follows , written for some , then looks like
For player II, a strategy is a function , with the same intuition as above. We then say that a strategy for player I is winning if for every , and analogously a strategy for player II is winning if for every . For this reason, we call the payoff set. The game is determined if one of the two players has a winning strategy (they can’t both have one).
Okay, that was the classical set-up. How can we tweak that to include hidden information? Say that player I and player II has some hidden information and , respectively, making our game look like
In the same manner, we declare player I to be the winner iff . We still haven’t changed anything; we’ve just postulated that and are hidden, whatever that means. To model this, we redefine our notion of . Instead of applying to all the previous moves, we only apply it to the public ones, arriving at the play :
With this notion we can then redefine that is winning iff for every — so the main difference here is that we’ve made it harder for player I to win. Everything is completely analogous for player II.
Now, what can we say about the existence of winning strategies in these games with hidden information? In the classical perfect information case, i.e. when , every closed game is determined, where a game is closed if is closed in the product topology on , or alternatively, that if player I loses then he will have lost at a finite stage. In contrast, consider a general game with hidden information with payoff set
Since neither player can see the other player’s hidden information, they can ensure neither that nor that — in other words, this game is not determined. Note that this game is also closed, since if then there will be a finite stage such that , so player I will already have lost at stage .
This example shows that our usual notion of determinacy is not really useful when both players have something hidden. Instead, one proceeds to talk about a probabilistic version of determinacy called Blackwell determinacy; for more information see e.g. chapter 4 in my determinacy project. But what if only one player has a secret, say if ? Then we’re playing a game of the form
If this game is closed, in the same sense as above, then it is determined! The proof is exactly the same as in the classical case: we assume player II has no winning strategy and define a winning strategy for player I consisting of all the “non-losing moves” (again, see section 2.1 in my determinacy project for more details). The important bit here is that, from the point of view of player I, the game is a perfect information game.
This is as far as we can go however, since even open games with hidden information aren’t in general determined. Consider for instance the following payoff set:
This is easily seen to be an open set, but the players can neither ensure that this condition is true nor false, so it’s an open game which isn’t determined. But even though we only get determinacy for a rather small class of games with hidden information, namely the closed ones where the closed player has perfect information, this can still be a useful tool when dealing with determinacy questions.