Games with a hidden component

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?

dogpoker
                                                    “A Friend in Need” by C.M. Coolidge

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 A\subseteq{^\omega}\omega and define the game \mathcal G(A) as follows.

\begin{array}{ccccccccc} \text{I} & x_0 && x_1 && x_2 && \cdots\\ \text{II} && y_0 && y_1 && y_2 && \cdots \end{array}

Here x_n,y_n\in\omega and player I wins iff x*y:=\langle x_0,y_0,x_1,y_1,\hdots\rangle\in A. A strategy for player I is then a function \sigma:\bigcup_{n<\omega}{^{2n}}\omega\to\omega, where we interpret this as \sigma taking as input some partial play of \mathcal G(A) in which it’s player I’s turn, e.g.

\begin{array}{ccccccccc} \text{I} & x_0 && \cdots && x_k \\ \text{II} && y_0 && \cdots && y_k \end{array}

and then outputting player I’s response to this partial play. The resulting play in which player I follows \sigma, written \sigma*y for some y\in{^\omega}\omega, then looks like

\begin{array}{ccccccccc} \text{I} & \sigma(\langle\rangle) && \sigma(\langle\sigma(\langle\rangle),y_0\rangle) && \cdots \\ \text{II} && y_0 && y_1 && \cdots \end{array}

For player II, a strategy is a function \tau:\bigcup_{n<\omega}{^{2n+1}}\omega\to\omega, with the same intuition as above. We then say that a strategy \sigma for player I is winning if \sigma*y\in A for every y\in{^\omega}\omega, and analogously a strategy \tau for player II is winning if x*\tau\notin A for every x\in{^\omega}\omega. For this reason, we call A the payoff set. The game \mathcal G(A) 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 \hat x\in{^\omega}\omega and \hat y\in{^\omega}\omega, respectively, making our game look like

\begin{array}{ccccccccc} \text{I} & x_0[\hat x_0] && x_1[\hat x_1] && x_2[\hat x_2] && \cdots\\ \text{II} && y_0[\hat y_0] && y_1[\hat y_1] && y_2[\hat y_2] && \cdots \end{array}

In the same manner, we declare player I to be the winner iff \langle x_0,\hat x_0,y_0,\hat y_0,x_1,\hdots\rangle\in A. We still haven’t changed anything; we’ve just postulated that \hat x and \hat y are hidden, whatever that means. To model this, we redefine our notion of \sigma*y. Instead of applying \sigma to all the previous moves, we only apply it to the public ones, arriving at the play \sigma*y*\hat y:

\begin{array}{ccccccccc} \text{I} & \sigma(\langle\rangle) && \sigma(\langle\sigma(\langle\rangle),y_0\rangle) && \cdots \\ \text{II} && y_0[\hat y_0] && y_1[\hat y_1] && \cdots \end{array}

With this notion we can then redefine that \sigma is winning iff \sigma*y*\hat y\in A for every y,\hat y\in{^\omega}\omega — 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 \hat x=\hat y=0, every closed game is determined, where a game is closed if A is closed in the product topology on {^\omega}\omega, 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

A_0:=\{x*\hat x*y*\hat y\in{^\omega}\omega\mid \hat x=\hat y\}.

Since neither player can see the other player’s hidden information, they can ensure neither that \hat x=\hat y nor that \hat x\neq\hat y — in other words, this game is not determined. Note that this game is also closed, since if \hat x\neq\hat y then there will be a finite stage k<\omega such that \hat x_k\neq\hat y_k, so player I will already have lost at stage k.

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 \hat y=0? Then we’re playing a game of the form

\begin{array}{ccccccccc} \text{I} & x_0[\hat x_0] && x_1[\hat x_1] && x_2[\hat x_2] && \cdots\\ \text{II} && y_0 && y_1 && y_2 && \cdots \end{array}

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:

\{z\in{^\omega}\omega\mid\exists k<\omega:\hat x_k\neq y_k\}.

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.