Finite game

Last updated

A finite game (sometimes called a founded game [1] or a well-founded game [2] ) is a two-player game which is assured to end after a finite number of moves. Finite games may have an infinite number of possibilities or even an unbounded number of moves, so long as they are guaranteed to end in a finite number of turns. [3]

Contents

Formal definition

William Zwicker defined a game, G, to be totally finite if it met the following five conditions: [4]

  1. Two players, I and II, move alternately, I going first. Each has complete knowledge of the other's moves.
  2. There is no chance involved.
  3. There are no ties (when a play of G is complete, there is one winner).
  4. Every play ends after finitely many moves.
  5. At any point in a play of G, there are but finitely many legal possibilities for the next move.

Examples

Supergame

A supergame is a variant of the finite game invented by William Zwicker. Zwicker defined a supergame to have the following rules:

"On the first move, I name any totally finite game G (called the subgame). The players then proceed to play G, with II playing the role of I while G is being played. The winner of the play of the subgame is declared to be the winner of the play of the supergame." [4]

Zwicker notes that a supergame satisfies properties 1-4 of a totally finite game, but not property 5. He defines games of this type to be somewhat finite. [4]

Hypergame paradox

A hypergame has the same rules as a super game except that I may name any somewhat finite game on the first move. The hypergame is closely related to the "hypergame paradox" a self-referential, set-theoretic paradox like Russell's paradox and Cantor's paradox. [2]

The hypergame paradox arises from trying to answer the question "Is a hypergame somewhat finite?" The paradox, as Zwicker note, satisfies conditions 1- 4 making it somewhat finite in the same way a supergame was. [2] However, if hypergame is a somewhat finite game, then play can proceed infinitely with both players choosing hypergame as their subgame forever. This infinite would appear to violate property 4, making the hypergame not somewhat finite. Thus, the paradox. [1]

Related Research Articles

<span class="mw-page-title-main">Cardinal number</span> Size of a possibly infinite set

In mathematics, a cardinal number, or cardinal for short, is what is commonly called the number of elements of a set. In the case of a finite set, its cardinal number, or cardinality is therefore a natural number. For dealing with the case of infinite sets, the infinite cardinal numbers have been introduced, which are often denoted with the Hebrew letter (aleph) marked with subscript indicating their rank among the infinite cardinals.

In game theory, the Nash equilibrium, named after the mathematician John Nash, is the most common way to define the solution of a non-cooperative game involving two or more players. In a Nash equilibrium, each player is assumed to know the equilibrium strategies of the other players, and no one has anything to gain by changing only one's own strategy. The principle of Nash equilibrium dates back to the time of Cournot, who in 1838 applied it to competing firms choosing outputs.

<span class="mw-page-title-main">Surreal number</span> Generalization of the real numbers

In mathematics, the surreal number system is a totally ordered proper class containing not only the real numbers but also infinite and infinitesimal numbers, respectively larger or smaller in absolute value than any positive real number. Research on the Go endgame by John Horton Conway led to the original definition and construction of surreal numbers. Conway's construction was introduced in Donald Knuth's 1974 book Surreal Numbers: How Two Ex-Students Turned On to Pure Mathematics and Found Total Happiness.

<span class="mw-page-title-main">St. Petersburg paradox</span> Paradox involving a game with repeated coin flipping

The St. Petersburg paradox or St. Petersburg lottery is a paradox involving the game of flipping a coin where the expected payoff of the theoretical lottery game approaches infinity but nevertheless seems to be worth only a very small amount to the participants. The St. Petersburg paradox is a situation where a naïve decision criterion that takes only the expected value into account predicts a course of action that presumably no actual person would be willing to take. Several resolutions to the paradox have been proposed.

In game theory, a cooperative game is a game with competition between groups of players ("coalitions") due to the possibility of external enforcement of cooperative behavior. Those are opposed to non-cooperative games in which there is either no possibility to forge alliances or all agreements need to be self-enforcing.

In mathematics, a set A is Dedekind-infinite if some proper subset B of A is equinumerous to A. Explicitly, this means that there exists a bijective function from A onto some proper subset B of A. A set is Dedekind-finite if it is not Dedekind-infinite. Proposed by Dedekind in 1888, Dedekind-infiniteness was the first definition of "infinite" that did not rely on the definition of the natural numbers.

<span class="mw-page-title-main">Solution concept</span> Formal rule for predicting how a game will be played

In game theory, a solution concept is a formal rule for predicting how a game will be played. These predictions are called "solutions", and describe which strategies will be adopted by players and, therefore, the result of the game. The most commonly used solution concepts are equilibrium concepts, most famously Nash equilibrium.

In game theory, an extensive-form game is a specification of a game allowing for the explicit representation of a number of key aspects, like the sequencing of players' possible moves, their choices at every decision point, the information each player has about the other player's moves when they make a decision, and their payoffs for all possible game outcomes. Extensive-form games also allow for the representation of incomplete information in the form of chance events modeled as "moves by nature". Extensive-form representations differ from normal-form in that they provide a more complete description of the game in question, whereas normal-form simply boils down the game into a payoff matrix.

Determinacy is a subfield of set theory, a branch of mathematics, that examines the conditions under which one or the other player of a game has a winning strategy, and the consequences of the existence of such strategies. Alternatively and similarly, "determinacy" is the property of a game whereby such a strategy exists. Determinacy was introduced by Gale and Stewart in 1950, under the name "determinateness".

In game theory, folk theorems are a class of theorems describing an abundance of Nash equilibrium payoff profiles in repeated games. The original Folk Theorem concerned the payoffs of all the Nash equilibria of an infinitely repeated game. This result was called the Folk Theorem because it was widely known among game theorists in the 1950s, even though no one had published it. Friedman's (1971) Theorem concerns the payoffs of certain subgame-perfect Nash equilibria (SPE) of an infinitely repeated game, and so strengthens the original Folk Theorem by using a stronger equilibrium concept: subgame-perfect Nash equilibria rather than Nash equilibria.

In game theory, a repeated game is an extensive form game that consists of a number of repetitions of some base game. The stage game is usually one of the well-studied 2-person games. Repeated games capture the idea that a player will have to take into account the impact of his or her current action on the future actions of other players; this impact is sometimes called his or her reputation. Single stage game or single shot game are names for non-repeated games.

In game theory, a subgame perfect equilibrium is a refinement of a Nash equilibrium used in dynamic games. A strategy profile is a subgame perfect equilibrium if it represents a Nash equilibrium of every subgame of the original game. Informally, this means that at any point in the game, the players' behavior from that point onward should represent a Nash equilibrium of the continuation game, no matter what happened before. Every finite extensive game with perfect recall has a subgame perfect equilibrium. Perfect recall is a term introduced by Harold W. Kuhn in 1953 and "equivalent to the assertion that each player is allowed by the rules of the game to remember everything he knew at previous moves and all of his choices at those moves".

In mathematics, a topological game is an infinite game of perfect information played between two players on a topological space. Players choose objects with topological properties such as points, open sets, closed sets and open coverings. Time is generally discrete, but the plays may have transfinite lengths, and extensions to continuum time have been put forth. The conditions for a player to win can involve notions like topological closure and convergence.

In descriptive set theory, the Borel determinacy theorem states that any Gale–Stewart game whose payoff set is a Borel set is determined, meaning that one of the two players will have a winning strategy for the game. A Gale-Stewart game is a possibly infinite two-player game, where both players have perfect information and no randomness is involved.

<span class="mw-page-title-main">Infinity</span> Mathematical concept

Infinity is that which is boundless, endless, or larger than any natural number. It is often denoted by the infinity symbol .

In game theory, Zermelo's theorem is a theorem about finite two-person games of perfect information in which the players move alternately and in which chance does not affect the decision making process. It says that if the game cannot end in a draw, then one of the two players must have a winning strategy. An alternate statement is that for a game meeting all of these conditions except the condition that a draw is now possible, then either the first-player can force a win, or the second-player can force a win, or both players can at least force a draw. The theorem is named after Ernst Zermelo, a German mathematician and logician, who proved the theorem for the example game of chess in 1913.

<span class="mw-page-title-main">Jean-François Mertens</span> Belgian game theorist (1946–2012)

Jean-François Mertens was a Belgian game theorist and mathematical economist.

The one-shot deviation principle is the principle of optimality of dynamic programming applied to game theory. It says that a strategy profile of a finite multi-stage extensive-form game with observed actions is a subgame perfect equilibrium (SPE) if and only if there exist no profitable single deviation for each subgame and every player. In simpler terms, if no player can increase their expected payoff by deviating from their original strategy via a single action, then the strategy profile is an SPE. In other words, no player can profit by deviating from the strategy in one period and then reverting to the strategy.

This is a glossary of set theory.

<span class="mw-page-title-main">Infinite chess</span> Variation of chess

Infinite chess is any variation of the game of chess played on an unbounded chessboard. Versions of infinite chess have been introduced independently by multiple players, chess theorists, and mathematicians, both as a playable game and as a model for theoretical study. It has been found that even though the board is unbounded, there are ways in which a player can win the game in a finite number of moves.

References

  1. 1 2 Bernardi, Claudio; d'Agostino, Giovanna (October 1996). "Translating the hypergame paradox: Remarks on the set of founded elements of a relation". Journal of Philosophical Logic. 25 (5): 545–557. doi:10.1007/BF00257385. S2CID   12745108.
  2. 1 2 3 "Self-Reference". Stanford Encyclopedia of Philosophy. Stanford University. Aug 31, 2017. Retrieved 2 March 2020.
  3. 1 2 3 "Hypergame". Cornell University. Retrieved 2 March 2020.
  4. 1 2 3 Zwicker, William (July 1987). "Playing Games with Games: The Hypergame Paradox". The American Mathematical Monthly. Mathematical Association of America. 94 (6): 507–514. doi:10.2307/2322840. JSTOR   2322840.
  5. ↑ "Game theory". Encyclopedia Britannica.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.