Skip to Content

Gale-Stewart Games

Posted on

Authors:

  • Joosten, Sebastiaan J.

Published in: Arch. Formal Proofs

Abstract:

This is a formalisation of the main result of Gale and Stewart from 1953, showing that closed finite games are determined. This property is now known as the Gale Stewart Theorem. While the original paper shows some additional theorems as well, we only formalize this main result, but do so in a somewhat general way. We formalize games of a fixed arbitrary length, including infinite length, using co-inductive lists, and show that defensive strategies exist unless the other player is winning. For closed games, defensive strategies are winning for the closed player, proving that such games are determined. For finite games, which are a special case in our formalisation, all games are closed.

BibTeX entry:

@article{Joosten21a,
 abstract = {This is a formalisation of the main result of Gale and Stewart from 1953, showing that closed finite games are determined. This property is now known as the Gale Stewart Theorem. While the original paper shows some additional theorems as well, we only formalize this main result, but do so in a somewhat general way. We formalize games of a fixed arbitrary length, including infinite length, using co-inductive lists, and show that defensive strategies exist unless the other player is winning. For closed games, defensive strategies are winning for the closed player, proving that such games are determined. For finite games, which are a special case in our formalisation, all games are closed.},
 author = {Joosten, Sebastiaan JC},
 date-added = {2021-09-18 14:47:12 -0400},
 date-modified = {2021-09-18 15:26:48 -0400},
 journal = {Arch. Formal Proofs},
 month = {4},
 title = {Gale-Stewart Games},
 volume = {2021},
 year = {2021}
}