Determined, finite games

Question

What is the simplest way to prove that each finite game is also determined? I know that a game is said to be determined if one of the players has a winning strategy. I was hoping to prove by contradiction that assuming in a finite game Player 1 does not have a winning strategy it needs to be the case that Player 2 has the winning strategy, but maybe there is an easier way.

Answer 1

There are numerous proofs of what I call the fundamental theorem of finite games.

Theorem. (Fundamental theorem of finite games) In any finite two-player game of perfect information, one of the players has a winning strategy.

Proof 1. Back-propagation through the game tree. Label the nodes with the player who has a winning strategy from that position. Every node will get a label, by recursively labeling from the terminal nodes of the tree (which amounts to working backwards from the won-game positions). What is the label on the root node? The winning strategy is to stay on the nodes with that label.QED

Proof 2. Let $W$ be the nodes in the game tree for which player I has a winning strategy in the game proceeding from that position. If this includes the top node, then I wins. Otherwise, it is not difficult to see that player II can avoid the nodes in W, and therefore win. QED

Proof 3. The theorem amounts to the de Morgan law. The assertion "player II has a winning strategy" is simply $$\forall x_1\exists x_2\dots \vec x\text{ is a win for II}.$$ So if player II does not have a winning strategy, we negate that assertion, and push the negation through all the quantifiers, by de Morgan's law, arriving at: $$\exists x_1\forall x_2\dots\vec x\text{ is a win for I}.$$ And this is what it means for player I to have a winning strategy. QED

Proof 4. First prove the Gale-Stewart theorem that every open game is determined, which itself has several classic proofs. For example, you can see some of them explained in the introduction of my recent article,

• V. Gitman, J. D. Hamkins, Open determinacy for class games, to appear.

One of these proofs involves transfinite game values, but in the case of bounded-length finite games, all the game values will be finite. Finally, note that any finite game is an open game. QED

Most of these arguments (all except the de Morgan argument) generalize to prove the determinacy of clopen games, rather than merely uniformly bounded-length finite games. A clopen game is a game whose game tree is well-founded, or in other words, every play terminates in a win for one of the players.