Metagame Paradox: what is wrong with this explanation?

Question

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:

1. 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".
2. I don't know what is a formal word for "not defined properly"
3. Assumption A1 may also be undecidable, but I believe it should not change the argument..

Answer 1

The flaw is that your definition of "game" is deficient and does not correspond to our intuition. We also need a restriction on the number of moves that are possible at any position in the game. It doesn't really have anything to do about computability, so much as about the notion of what it means for a game to be finite.

---

Usually we define a game as something where at each step there are only finitely many moves that can be played, and where the game is guaranteed to end after finitely many moves (there is no infinite sequence of moves in the game). You forgot to specify the "at each position, there are only finitely many moves possible from that position" in your definition of a game.

If you add that to the definition, then you'll find that the metagame does not meet the definition: the metagame is not a game. In particular, there are infinitely many possible games, so at the beginning of your metagame, there are infinitely many possible moves -- thus the metagame does not qualify as a game. There is no paradox.

---

You could have an alternative definition of a game where you say that at each step the number of moves is either finite or countably infinite. This is a bit different from what our intuition would suggest, but let's explore the consequences of defining a game this way.

In particular, the set of all games would now be uncountably infinite.

As a result, the metagame is still not a game: at the beginning of your metagame, there are uncountably infinitely many possible moves -- so does not qualify as a game.

In particular, "pick a game" is not meaningful: Player 1 has to select a game and describe it to Player 2, but there are uncountably infinitely many possible games, so Player 1 cannot describe his choice in any finite amount of time. In particular, you cannot specify a game with a finite string (more precisely: no matter what candidate encoding of games you come up with, there will exist some games that cannot be specified by any finite string). The description of the game is an infinite-length string.

If you like to think of it intuitively: in this case it wouldn't really be fair to think of the metagame as "finite" (even though it only lasts for a finite number of moves, if the first move takes infinitely long to complete, the metagame cannot be considered finite).

In any case, if you define a game this way, there is still no paradox.

(Why is the set of games uncountably infinite, if this is how we defined a game? Well, I'll show an injective map $f$ that maps from a real number $x \in [0,1]$ to a game $G_x$. In the first move of $G_x$, player 1 chooses a natural number $n \in \mathbb{N}$. After that, there are $n$ more moves, then the game ends. At the $i+1$th move (for $1 \le i \le n$), there are $x_i$ different moves available to the player whose turn it is to move, where $x_i$ denotes the $i$th digit after the decimal point in the decimal expansion of $x$. Notice that $G_x$ qualifies as a game: there are two players, the players alternate, there are finitely or countably infinitely many moves at each possible position of the game, and the game is guaranteed to end after finitely many steps -- there is no infinite sequence of valid moves. But the set $[0,1]$ of real numbers is uncountably infinite, and we have an injective map from an uncountably infinite set to a subset of the set of games. Therefore, the set of all games is uncountably infinite, under this definition.)

---

Finally, the last alternative would be to define "game" so there is no restriction on the number of possible moves at each position.

However, this definition of a "game" would no longer correspond to our usual intuition for what a game should involve. In particular, it may not be possible for a player to describe his/her move to the other player in any finite amount of time (since he/she may be choosing from among uncountably infinitely many possibilities). That just ain't right. In particular, such a process can't reasonably be considered finite: it would not complete in any finite amount of time.

---

Intuitively, why does it make sense that our definition of game ought to restrict the number of possible moves at each position to be finite, or at most countably infinite? Because we need the player to be able to select a move and describe it to the other player. If there is no finite encoding of the set of possible moves (at a given position), then the player whose turn it is to move has no way to describe the move he chose to his opponent. If there is a finite encoding of the set of possible moves (at each possible position), then the number of possible moves must always be finite or countably infinite, by the definition of countability.

Answer 2

This is a set theory paradox, rather than a computability paradox. Let us define: a game is any set $X$. The initial game state of game $X$ is the set $X$ itself; taking a move means moving from a set $Y$ (the current game state) to one of its elements; if the current game state is the empty set, then the game ends (and the player whose turn is to move loses). The set $X$ is well-founded, if it doesn't have an infinite downwards chain of the $\in$ relation - there doesn't exist such an infinite sequence of sets $A$, $B$, $C$, $D$, ... that $B \in A$, $C \in B$, $D \in C$, ... and so on, where $A=X$. (This means that the game is guaranteed to end in finitely many moves.) From axiom of regularity it follows that every set is well-founded; so let's assume that we are working in ZF with the axiom of regularity omitted.

The question whether or not metagame is a finite game becomes: is the set of all well-founded sets itself well-founded? First, observe that a well-founded set can't contain itself. (Otherwise, we could have picked an infinite sequence $X$, $X$, $X$, ...) Now a set which only contains well-founded sets is itself well-founded. (We see that every downwards chain of all the elements of $A$ is finite; the downwards chains of the set $A$ itself are just one element longer, with set $A$ added to its front. We could have run in trouble if the set $A$ contained itself as an element - but in this case the set $A$ is not well-founded and so it doesn't only contain well-founded sets.) Now to the set of all well-founded sets: If the set doesn't contain itself, then it is well-founded, and therefore it isn't the set of all well founded sets (it misses one well-founded set, namely itself). On the other hand, if the set contains itself, then it is not well-founded, and therefore it contains a set which is not well-founded. Either way, we have reached a paradox, so the conclusion is that the "metagame" (set of all well-founded sets) cannot exist - the class of all well-founded sets is a proper class.

(We can prove the result from the other side: Again, observe that 1) a well-founded set can't contain itself; and 2) a set is well-founded if and only if all its elements are well-founded. But this means that any well-founded set necessarily doesn't contain some well-founded set - namely, itself - and therefore there can't exist a set of all well-founded sets.)

Answer 3

Let me to rephrase the answer by D.W. and give my understanding (all credit goes to D.W.!)

We need to formalize what is a game, and D.W. showed different possibilities. All formalizations lead to "meta-game is not a game" (and no paradox!).

One of the possibilities is:

Smth is a game iff: 
1) two players
2) alternate
3) in each position in the game there is a countable number of possible moves
4) game ends (infinite game-play is forbidden).

We need (3) otherwise player1 will not be able to communicate its answer to player2 (the answer becomes an infinite string).

Even for this definition D.W. shows that meta-game is not a game (and no paradox), because in meta-game item (3) is violated. See D.W. answer for explanation.

In the above definition a game description can be an infinite string (and is indeed, see D.W. answer). One of "natural" requirements on the game is to require:

5) a game description should be a finite string

Is there a paradox now? Not really: now comes into play the meta-game item which says pick a game. How to implement it? If meta-game stores all possible games inside and picks one of them, then meta-game description is not finite and so it is not a game (and no paradox). If assume that meta-game just generates some string and then passes it to decider that says 'yes, it is a game, you can pick it', then we get contradictions (just like in paradox), and so the assumption is wrong -- there is no such decider.