Today I’ve heard about fascinating metagame paradox. I tried to come up with an explanation via Turing Machines formalization (below). Do you know what is the solution to the paradox? (the post content: definition – proposed solution – conclusion)

Something is a game iff:

`G1. Two players G2. Players alternate G3. The game finally ends. `

The metagame is:

`M1. First player picks a game M2. Second player starts the game M3. The winner is the winner of the game at step 2. `

Example of a metagame:

`1) I pick tic-tac-toe 2) OK, I put X here .. .. so they play .. 3) .. and let player 2 wins in the tic-tac-toe => player 2 wins the metagame. `

**Paradox: Is metagame a game?**

If metagame is a game, then at point (M1) both players can always pick a metagame, so the metagame will never end => (G3) is violated => metagame is not a game => contradiction.

(also contradiction for case “metagame is not a game” — metagame will satisfy the definition of a game)

(see also http://www.math.cornell.edu/~mec/2006-2007/Games/hypergame.html)

**What is the solution to the paradox?**

*UPDATE:* You may want to skip this explanation and go directly to D.W. answer.

I came up with the following explanation:

Lets formalize the problem using Turing Machines notations. Let a game be a finite binary string that describes “somehow” game rules. Let a game simulator be a non-deterministic TM that reads a description from the input (without any sanity checks, so the TM doesn’t know if the game finally ends), and then makes non-deterministic moves for the first and second player. Here we assume (A1) that the game-simulator can decide valid next moves.

Now have a look at the description of a meta-game:

`M1. First player picks a game `

This sentence means that we can “pick a game”, i.e. in the definition we assume (A2) that whether an arbitrarily binary string is a game (satisfies G1,G2,G3) is decidable. (see also note (n1) )

M2 and M3 look decidable.

So, **my suggestion is that metagame is not “defined properly”**, since its definition assumes the existence of a decider “if a given binary string is a game”. And then we derive a contradiction, so this assumption is wrong.

**Does it make sense? Is this related with other explanations of the paradox?** (intuitive answers would be great!)

Notes:

- Assuming “whether an arbitrarily binary string is a game” may be too much. But we need some computable procedure “pick a game” and one that came into mind is “generate random string, check if it is a game”.
- I don’t know what is a formal word for “not defined properly”
- Assumption A1 may also be undecidable, but I believe it should not change the argument..