Blog Archives
Topic Archive: game theory
The theory of infinite games, with examples, including infinite chess
This will be a talk on April 30, 2013 for a joint meeting of the Yeshiva University Mathematics Club and the Yeshiva University Philosophy Club. I will give a general introduction to the theory of infinite games, suitable for mathematicians and philosophers. What does it mean to play an infinitely long game? What does it mean to have a winning strategy for such a game? Is there any reason to think that every game should have a winning strategy for one player or another? Could there be a game, such that neither player has a way to force a win? Must every computable game have a computable winning strategy? I will present several game paradoxes and example infinitary games, including an infinitary version of the game of Nim, and several examples from infinite chess.
The omega one of chess
This talk will be based on my recent paper with C. D. A. Evans, Transfinite game values in infinite chess.
Infinite chess is chess played on an infinite chessboard. Since checkmate, when it occurs, does so after finitely many moves, this is technically what is known as an open game, and is therefore subject to the theory of open games, including the theory of ordinal game values. In this talk, I will give a general introduction to the theory of ordinal game values for ordinal games, before diving into several examples illustrating high transfinite game values in infinite chess. The supremum of these values is the omega one of chess, denoted by $omega_1^{mathfrak{Ch}}$ in the context of finite positions and by $omega_1^{mathfrak{Ch}_{hskip-2ex atopsim}}$ in the context of all positions, including those with infinitely many pieces. For lower bounds, we have specific positions with transfinite game values of $omega$, $omega^2$, $omega^2cdot k$ and $omega^3$. By embedding trees into chess, we show that there is a computable infinite chess position that is a win for white if the players are required to play according to a deterministic computable strategy, but which is a draw without that restriction. Finally, we prove that every countable ordinal arises as the game value of a position in infinite three-dimensional chess, and consequently the omega one of infinite three-dimensional chess is as large as it can be, namely, true $omega_1$.
Definitive solutions of strategic games
In his dissertation of 1950, Nash based his concept of solution to a game on the principles that “a rational prediction should be unique, that the players should be able to deduce and make use of it.” In this paper, we address the issue of when Nash expectations of a definitive solution hold and whether the Nash Equilibrium (NE) solution concept is a match for such definitive solutions. We show that indeed, an existence of NE is a necessary condition for a definitive solution, and each NE σ is a definitive solution for some notion of rationality individually tuned for this σ. However, for specific notions of rationality, e.g., Aumann’s rationality, NE is not an exact match to definitive solutions, many games with NE do not have definitive solutions at all. In particular, strategic ordinal payoff games with two or more Nash equilibria, and even some games with a unique NE do not have definitive solutions. We also show that the iterated dominance approach is a better candidate for Nash’s definitive solution concept than the Nash Equilibrium.