Blog Archives

Topic Archive: game theory

Tuesday, April 30, 20134:00 pmYeshiva UniversityFurst Hall, Amsterdam Ave. & 185th Street.

Joel David Hamkins

The theory of infinite games, with examples, including infinite chess

The City University of New York

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.

Set theory seminarFriday, March 1, 201312:00 amGC 5383

Joel David Hamkins

The omega one of chess

The City University of New York

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$.

Computational Logic SeminarTuesday, January 29, 20132:00 pmGC 3209

Sergei Artemov

Definitive solutions of strategic games

The CUNY Graduate Center

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.