14.5. Generalized Geography

Geography

---

Geography is a children's game. Although it can be played by several players, let's restrict it to two players, called A and B, where A moves first.

The players start by selecting a category of places, such as countries or cities. Let's choose countries.

A chooses a country name, say France.

Next, B must choose a country whose name begins with e, the last letter of France. Suppose B chooses Ethiopa.

Now A must choose a country name that begins with a, the last letter of Ethiopa.

Play continues like that with the requirement that, once a country has been chosen, it cannot be chosen again.

The player who cannot name a country loses.

Generalized Geography

---

Imagine a directed graph with a vertex for each country and an edge from u to v if u ends on the letter on which v starts.

Then geography amounts to a game on that directed graph. Player A selects a vertex v₁ and puts a token on it.

Then player B must select a vertex v₂ so that there is an edge from v₁ to v₂, and he puts a token on v₂.

Play continues until a player cannot make a move to a vertex that does not have a token on it.

Generalized Geography is a game on a given directed graph. It differs a little from the geography game in that there is a designated start vertex s that already has a token on it, and player A is required to begin by choosing a vertex v so that there is an edge from s to v.

The Generalized Geography Problem (GG) is as follows.

Input. A directed graph G and a start vertex s of G.

Question. Does the first player have a winning strategy in the Generalized Geography game on graph G with start s?

Generalized geography is PSPACE-complete

---

Proof. It suffices to show: (1) GG ∈ PSPACE and (2) TQBF ≤_p GG.

GG ∈ PSPACE

The algorithm is similar to the one for TQBF.

Keep track of the graph G with tokens on it from prior moves. If G₀ is the initial graph (with just a token on s), just call gg(G₀, A, s).

  gg(G, mover, u)
  L = the set of all v such that (u,v)
      is an edge and v has no token on it.
  if mover = A
    if L = {}
      return false
    else
      for each v in L
        G′ = G with a token added on v.
        if gg(G′, B, v) then
          return true
        end if
      end for
      return false
    end if

  else // mover = B
    if L = {}
      return true
    else
      for each v in L
        G′ = G with a token added on v.
        if not(gg(G′, A, v)) then
          return false
        end if
      end for
      return true
    end if
  end if

Alternating quantifiers

Given any quantified boolean formula φ, we can modify it, creating a new quantified boolean formula φ′ that is in standard form, where

• The first and last quantifiers in φ are ∃.

• The quantifiers strictly alternate between ∃ and ∀.

∀x∀y∃z((x ∨ ¬y) ∧ (y ∨ z))

∃u∀x∃w∀y∃z((x ∨ ¬y) ∧ (y ∨ z))

TQBF ≤_p GG

We can assume that the quantified boolean formula is in standard form.

The reduction relies on some gadgets. The first is a diamond gadget. All of the edges point downward.

         O
        / \
    x  O   O  x
        \ /
         O

Suppose that it is player A's turn at the top vertex of the diamond. Player A has two moves, one to select x to be true, the other to select x to be false.

Then it is player B's turn. B must select the bottom vertex of the diamond.

Assume that the quantifiers are ∃x∀y∃z∀u∃v. We create a diamond gadget for each variable and hook them together as follows.

         O  ← start
        / \
    x  O   O  x
        \ /
         O
         |
         O
        / \
    y  O   O  y
        \ /
         O
         |
         O
        / \
    z  O   O  z
        \ /
         O
         |
         O
        / \
    u  O   O  u
        \ /
         O
         |
         O
        / \
    v  O   O  v
        \ /
         O

Notice that

1. A chooses the value of x,
2. B chooses the value of y,
3. A chooses the value of z,
4. B chooses the value of u,
5. A chooses the value of v.

So A makes the existential choices (∃) and B makes the universal choices (∀).

Now we add vertices that are used to test whether the clausal formula is true. Imagine that it is

((¬x ∨ y) ∧ (y ∨ z ∨ u) ∧ (¬v ∨ ¬ y)

             O
            / \
        v  O   O  v
            \ /
             O
             |
        _____O_____ ← B's move:
       /     |     \  select a clause
      /      |      \
     O       O       O ← A's move:
    / \     /|\     / \  select a literal
   /   \   / | \   /   \
  x    y  y  z  u v     y             

There are 3 clause nodes because φ has 3 clauses.

The nodes in the bottom row are nodes in the diamond gadgets that have those names beside them.

The first clause has two literals, ¬ x and y. Notice that the literals in the bottom row are the negations of those.

Having selected the variables, we find that player A has a winning strategy if

∃x∀y∃z∀u∃v∀(clause c)∃(literal ℓ in c)(ℓ is true)

The truth of literal ℓ is because the opposite value was selected, leaving ¬ℓ open for A to move to.