Games of Limited Information (and Topology)

In its early years, the rigorous study of games (game theory) looked only upon games of so-called perfect information, in which each player knows the moves carried out by all players. Such games laid the foundation for early economic models of perfect competition, wherein consumers have full knowledge of both market conditions and each others’ consumer tendencies.

Of course, perfect competition — taken literally — cannot exist, and the failure of this model and others prompted economic theorists to study a more-general class of games, games of limited information (also known as games of imperfect information).

In this post, we’ll look at one-player games of limited information (sometimes classified as puzzles, not games) through a topological lens, and create for each game a poset of topologies under which topologically indistinguishable points correspond to outcomes that are indiscernible in a limited-information context. Expanding this dictionary, we’ll describe a topology on the outcome space under which the “safe” or “warranted” extension of one’s limited information relates to the continuity of certain maps.

— PART I (THE DICTIONARY)–

Our discussion will be modeled around Minesweeper-type games, a game archetype that includes in addition many grid-based logic puzzles. In this setting, the “limited information” is encoded in the set of revealed grid tiles, which — depending on the rules of the game — may (or may not) conform to particular patterns. In this sense, a round $\rho$ of the game $G$ is a map

$\rho: S \to X$ ,

in which $S$ is the game-space (e.g. the set of grid tiles) and $X$ is the space of outcomes (e.g. the numbers 0-9, union “the mine”), and $\rho$ is consistent with the rules of $G$ . Let

$\mathcal{G}=\{\rho: S \to X : \rho \text{ consistent with } G\}$

denote the set of valid rounds to the game $G$ . For each subset $R \subset S$ , we define an equivalence relation $\sim_R$ , such that $\rho_1 \sim_R \rho_2$ precisely when $\rho_1\vert_R = \rho_2\vert_R$ identically. Following this, we define (for fixed $R \subset S$ ) a topology $\tau_R$ on $\mathcal{G}$ , with basis the cosets of $\mathcal{G}/\sim_R$ . (In other words, the open sets are precisely the (possibly empty) unions of cosets in $\mathcal{G}$ .)

Example 1: With all notation as before, we find that $\tau_S$ forms the indiscrete (trivial) topology on $\mathcal{G}$ . In contrast, $\tau_\varnothing$ yields the discrete topology.

In general, two sets in a topological space are said to be topologically indistinguishable if they are contained in exactly the same open sets (equivalently, in the same closed sets). One motivating property of our construction is that two games are topologically indistinguishable with respect to $\tau_R$ if and only if they agree on the tiles of $R$ . (You may want to pause and verify this.)

Example 2: (A continuation of Example 1.) In the trivial topology, each pair of points is topologically indistinguishable (hence no two games are differentiated). On the other hand, all points are distinguished in the discrete topology, i.e. this space is $T_0$ . (Of course, totally disconnected spaces satisfy not just one, but all of the separation axioms.)

A second, subtler advantage to our construction is its naturality: an inclusion $A \subset B$ of sets induces an “inclusion” of topologies, in the following exact sense:

For two topologies $\tau,\tau'$ over a single topological space, we say that $\tau \subset \tau'$ if all open sets in $\tau$ are open in $\tau'$ . If so, $\tau$ is said to be coarser than $\tau'$ , while $\tau'$ is said to be finer than $\tau$ . We remark that the relation “ $\subset$ ” defines a poset on all topologies over a given space.

We have the following:

Proposition: The surjection

$\varphi: \{R \subset S\} \to \{\tau_R: R \subset S\}$

given by $R \mapsto \tau_R$ is inclusion-preserving.

Proof: If $R \subset T$ are subsets of $S$ , let $[g]_R$ denote the coset class of $g \in \mathcal{G}$ under the equivalence $\sim_R$ . To show that $\tau_R \subset \tau_T$ , it suffices to prove that $[g]_R$ can be written as a union of cosets in $\mathcal{G}/\sim_T$ . But this is clear, as

$[g]_R =\bigcup [h]_T$ ,

in which the union runs over all cosets $[h]_T$ such that $h \in [g]_R$ . $\square$

Whereas $\varphi$ is by construction surjective, it will rarely inject. Minesweeper, as a typical example, yields a non-injective map $\varphi$ . (See the Exercises.) Nevertheless, we give now (for completeness) a criterion equivalent to the injectivity of $\varphi$ :

Theorem: The map $\varphi : \mathscr{P}(S) \to \{\tau_R: R \subset S\}$ is an inclusion-preserving bijection if and only if the following condition holds:

( $*$ ) For all $R \subsetneq T \subset S$ , there exists a coset $[g]_R$ that splits non-trivially (i.e. into multiple cosets) under $\sim_T$ .

Proof: Necessity of the condition ( $*$ ) is clear: if for two sets $R \subsetneq T$ this condition does not hold, then all open sets under $\tau_T$ are open under $\tau_R$ , giving $\tau_T \subset \tau_R$ . Thus $\tau_R=\tau_T$ by our Proposition, i.e. $\varphi(R)=\varphi(T)$ .

On the other hand, suppose that $\varphi$ fails to inject, and take $\varphi(A) = \varphi(B)$ for two sets $A,B \subset S$ . Then $[g]_A \in \tau_B$ , so $[g]_A$ is a non-empty union of cosets under $\sim_B$ . Any coset $[h]_B$ in this union is open in $\tau_A$ (hence a union of $\sim_A$ -cosets). But the only open set (with respect to $\tau_A$ ) contained in $[g]_A$ is $\varnothing$ , so we have $[g]_A =[h]_B =[g]_B$ for all $g \in \mathcal{G}$ . Suppose by symmetry that $B \not\subset A$ . It follows from definition alone that $[g]_A=[g]_{A \cup B}$ . Taking $R =A$ and $T =A \cup B$ , we find a contradiction to criterion ( $*$ ). $\square$

— PART II (REFINEMENT)–

In Part I, we discussed at length the ways in which an increase in limited information can be modeled by a refinement of topologies over the space of rounds $\mathcal{G}$ . In this section, we focus on the process of extending one’s limited information, in relation to the existence of continuous maps into $X$ (and its powers).

To set the stage for our work this section, suppose that a game $\rho$ has been determined mod $\sim_R$ (i.e. the outcomes of $\rho$ on $R$ are known). The simplest of all scenarios occurs when the map $\varphi$ fails to inject; specifically, when $\tau_R=\tau_T$ for some $R \subsetneq T$ . Here, it’s simple to show that $[\rho]_R = [\rho]_T$ (regardless of $\rho$ ), hence $\rho$ defines a unique function mod $\sim_T$ .

More follows if we specify $\rho$ beforehand, as would happen in practice. In this case, we obtain a unique extension of $[\rho]_R$ to $T$ containing $R$ if and only if $[\rho]_R=[\rho]_T$ ; that is, if $[\rho]_R$ forms a single coset mod $\sim_T$ . (To borrow from algebraic number theory, one might say that $[\rho]_R$ is “inert” with respect to $T$ .)

Inertness has an equivalent formulation in the continuity of certain maps. To keep things simple, let us first assume that $T \supsetneq R$ is obtained from $R$ with the inclusion one additional element $a \in S$ . If $X$ is given the discrete topology, then the map

$e_a: [\rho]_R \to X$

given by evaluation at $a$ is continuous if and only if it is constant (i.e. when $[\rho]_R =[\rho]_T$ ). In greater generality, we have $[\rho]_R = [\rho]_T$ (for $R \subset T$ ) if and only if

$e_T:=\coprod_{t \in T} e_t: [\rho]_R \to X^T$

is continuous. (Here $X^T$ is given the product topology.)

It turns out that this second formulation is more useful. To see why, let’s consider again the case of Minesweeper:

Example 3: In the familiar case of Minesweeper, our outcome set $X$ consists of the integers 0-9, as well as the mine $\mu$ . If our game $\rho$ is known on $R$ and $a \in S$ lies outside of $R$ , we need not have full knowledge of $\rho$ on $a$ to expand our limited information. Rather, it suffices to know whether or not $\rho(a)$ is a mine, i.e. which component of the partition

$\{0,1,\ldots,8,9\} \cup \{\mu\}$

of $X$ that $\rho(a)$ lies in. If this component is fixed as $\rho$ varies over $[\rho]_R$ , then we are justified in expanding our limited information to include the value of $\rho$ on $a$ . But this happens precisely when the map $e_a : [\rho]_R \to X$ is continuous with respect to the partition topology on $X$ .

All together, we’ve stumbled upon an “algorithm” for justifiable and/or safe play:

Partition $X$ into the minimal number of components required to inform safe play under general conditions.
Given knowledge of $\rho$ on $R$ , let $T \subset S$ be maximal such that $e_T: [\rho]_R \to X^T$ is continuous with respect to the partition topology on $X$ (whence the product topology on $X^T$ ).
This justifies knowledge of $\rho$ on $T$ ; now repeat step 2.

If $S$ is finite, the procedure above will terminate (in finite time) with knowledge of $\rho$ on some subset $R' \subset S$ . Dependent on $R'$ we have two cases (here, we assume $X$ finite):

$R'=S$ , in which case we have won our game.
$R' \subsetneq S$ , in which case we reveal some $t \in S \smallsetminus R'$ such that the Bayesian probability of winning (given knowledge of $\rho$ on $R' \cup\{t\}$ weighed against the risk of guessing $\rho$ ) is maximized.

Combined with our earlier procedure, this gives an optimal (probabilistic) strategy for $G$ , which need not be a winning strategy. (This result, we remind the reader, relies upon the finiteness of $S$ .)

— PART III (GENERALIZATIONS) —

If our game space $S$ is infinite, far less can be said. For instance, it could very well be that our “algorithm” above may never terminate (although these “infinitely long games still hold interest for certain game theorists; see determinacy).

A second means of generalization comes from relaxing our assumptions on $X$ (while keeping $S$ finite). Here, our algorithm for careful play proceeds without a hitch, while admitting the novel possibility of an infinite number of different rounds $\mathcal{G}$ . Indeed, the only sticking point in this more general setting is our reliance upon Bayesian probability.

Working over a finite set of rounds allows us to (implicitly in the previous) make use of a uniform distribution on $\mathcal{G}$ . Without this standard, invocation of Bayesian probability requires a priori knowledge of the distribution of rounds in $\mathcal{G}$ . Alternatively — if the distribution of rounds is not known — we could employ a frequentist approach, hopefully converging upon optimal play (using a machine-learning algorithm, say).

Simple examples of this more general behavior are included in the Exercises.

— EXERCISES —

Exercise: Show that the function $\varphi$ given by $R \mapsto \tau_R$ associated to the game of Minesweeper is not injective. (Hint: consider at which point the round $\rho \in \mathcal{G}$ is determined.)

Exercise: If the space $S$ is infinite, is there any difference (as regards the continuity of our maps $e_T$ ) between the product topology and the box topology on $X^T$ ?

Exercise: Let $S \subset \mathbb{R}^n$ be a region, and let $A \subset S$ be a closed, measurable set with finitely many components. We define

$\delta(x,r):= \displaystyle\frac{1}{m(B(r,x))} \int_{B(r,x)} \chi_A(t) dt$ ,

in which $m(B(r,x))$ is the volume of the $n$ -dimensional unit ball and $\chi_A$ is the indicator function of $A$ . Fix some $\theta \in (0,1)$ . We define a game of limited information as follows: the player chooses $(x,r)$ such that $B(r,x) \subset S$ . If $\delta(x,r)>\theta$ , the player loses (immediately). Otherwise, play continues until the player can ascertain the number of connected components of $A$ . Prove that this game has a winning strategy if and only if

We do not lose on the first turn.
$S$ is pre-compact (equivalently, totally bounded).
The connected components of $A$ are simply connected.

Prove that (2) can be dropped if we are allowed to take countably many turns. (This might be called a “ $\sigma$ -winning strategy.)

Exercise (The Secretary Problem): Let $L=\{\alpha_1,\ldots,\alpha_n\}$ be a list of $n$ real numbers (unknown to the player). We define a game of limited information as follows: the player views the elements of $L$ sequentially, and may stop at any point. If the player stops at $\alpha_j$ , the round ends and the player wins if and only if $\alpha_j = \max L$ . What is the optimal (probabilistic) strategy, as $n \to \infty$ ? How does this problem change if $L$ is known to be sampled from a given distribution?