Games of Limited Information (and Topology)

minesweeper

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 inclusionA \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:

  1. Partition X into the minimal number of components required to inform safe play under general conditions.
  2. 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).
  3. 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):

  1. R'=S, in which case we have won our game.
  2. 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

  1. We do not lose on the first turn.
  2. S is pre-compact (equivalently, totally bounded).
  3. 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 nreal 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?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s