World Library  
Flag as Inappropriate
Email this Article

Zermelo's theorem (game theory)

Article Id: WHEBN0025046926
Reproduction Date:

Title: Zermelo's theorem (game theory)  
Author: World Heritage Encyclopedia
Language: English
Subject: Solving chess, Solved game, History of mathematics, Game theory, Chess
Collection: Game Theory, History of Mathematics, Mathematical Theorems
Publisher: World Heritage Encyclopedia
Publication
Date:
 

Zermelo's theorem (game theory)

In game theory, Zermelo’s theorem, named after Ernst Zermelo, says that in any finite two-person game of perfect information in which the players move alternatingly and in which chance does not affect the decision making process, if the game cannot end in a draw, then one of the two players must have a winning strategy.[1]

Contents

  • Formal definition 1
  • Publication history 2
  • Details 3
  • Example 4
  • Notes 5
  • External Links 6

Formal definition

Every finite extensive-form game exhibiting full information has a Nash equilibrium that is discoverable by backward induction. If every payoff is unique, for every player, this backward induction (starting from the end of the game and then working backwards to its beginning)[2] solution is unique.[3]

Publication history

Zermelo's original paper describing the theorem, Uber eine Anwendung der Mengenlehre auf die Theorie des Schachspiels, was published in German in 1913. Ulrich Schwalbe and Paul Walker translated Zermelo's paper into English in 1997 and published the translation in the appendix to Zermelo and the Early History of Game Theory.[4]

Details

Zermelo considers the class of two-person games without chance, where players have strictly opposing interests and where only a finite number of positions are possible. Although in the game only finitely many positions are possible, Zermelo allows infinite sequences of moves since he does not consider stopping rules. Thus, he allows for the possibility of infinite games. Then he addresses two problems:

  1. What does it mean for a player to be in a 'winning' position and is it possible to define this in an objective mathematical manner?
  2. If he is in a winning position, can the number of moves needed to force the win be determined?

To answer the first question, Zermelo states that a necessary and sufficient condition is the nonemptyness of a certain set, containing all possible sequences of moves such that a player wins independently of how the other player plays. But should this set be empty, the best a player could achieve would be a draw. So he defines another set containing all possible sequences of moves such that a player can postpone his loss for an infinite number of moves, which implies a draw. This set may also be empty, i. e., the player can avoid his loss for only finitely many moves if his opponent plays correctly. But this is equivalent to the opponent being able to force a win. This is the basis for all modern versions of Zermelo's theorem.

About the second question, Zermelo claimed that it will never take more moves than there are positions in the game. His proof is a proof by contradiction: Assume that a player can win in a number of moves larger than the number of positions. Of course, at least one winning position must have appeared twice. So the player could have played at the first occurrence in the same way as he does at the second and thus could have won in fewer moves than there are positions.

Example

When applied to chess, Zermelo's Theorem states "either white can force a win, or black can force a win, or both sides can force at least a draw".[5]

Notes

  1. ^ http://hkumath.hku.hk/~ntw/EMB(giftedstudents_6-April-2008).pdf
  2. ^ http://www.math.harvard.edu/~elkies/FS23j.03/zermelo.pdf
  3. ^ Mas-Colell, Whinston, Greene Microeconomic Theory
  4. ^ http://www.math.harvard.edu/~elkies/FS23j.03/zermelo.pdf
  5. ^ http://www.gap-system.org/~history/Projects/MacQuarrie/Chapters/Ch4.html

External Links

  • Original Paper (in German)
  • Zermelo and the Early History of Game Theory
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
 
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
 
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.
 


Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.