💾 Archived View for djhsu.smol.pub › 20240706-geography captured on 2024-08-18 at 18:08:30. Gemini links have been rewritten to link to archived content
⬅️ Previous capture (2024-07-08)
-=-=-=-=-=-=-
"Geography" is a two-player in which players take turn naming cities. The city that a player names must start with the last letter of the previously named city, and it cannot repeat a previously named city. For example, if Player 1 starts with "New York", Player 2 could then say "Kolkata", after which Player 1 could say "Amsterdam", etc. A player loses if they cannot name any city.
Karp generalized this game to be played on an arbitrary directed graph, where the players take turns moving a token from vertex to vertex along the directed edges, subject to the constraint that no vertex is visited more than once. Schaefer proved that deciding if the first player has a winning strategy is PSPACE-complete, so it is as hard as any other decision problem that can be solved in polynomial space.
Schaefer, "On the complexity of some two-person perfect-information games"
Now consider a variant of Geography in which the named city can either start with the last letter of the previously named city, or it can end with the first letter of the previously named city. For example, if Player 1 starts with "New York", Player 2 could still say "Kolkata", but now "Boston" is also a possibility. The generalization of this game is now just as before, except the graph is undirected. Deciding if the first player has a winning strategy can be accomplished in polynomial time! This was observed by Fraenkel, Scheinerman, and Ullman. (Hint: consider matchings...)
Fraenkel, Scheinerman, and Ullman, "Undirected edge geography"
One last variant: there are always two "current" cities (e.g., "New York, Seoul"). A player must name a new city that is a valid response to (at least) one of the current cities, which is then replaced with the newly named city. So starting with "New York, Seoul" and naming "Paris" leads to the current pair "New York, Paris". (This new game is formed by taking the "disjunctive sum" of two copies of the Undirected Geography game.) What is the complexity of this new game? It turns out it is PSPACE-complete! This is a very recent result of Burke, Ferland, and Teng.
I'm grateful to Shang-Hua Teng for teaching me about these games and results earlier this week!
Wikipedia page for "Generalized Geography"
--------------------------------------------------------------------------------