Questions tagged [infinite-games]

Infinite games. Combinatorial game theory for infinite two-player games of perfect information. Open games, clopen games. Determinacy. Transfinite game values. Topological games.

Filter by
Sorted by
Tagged with
26 votes
7 answers
5k views

Why is game theory formulated in terms of equilibrium instead of winning strategies?

Game theory, on the outset, seems to invite the questions, "what can I do to win" or "how do I beat my opponent?" So many people who are not familiar with game theory look to game ...
user avatar
2 votes
1 answer
113 views

Game versions of the tower number $\mathfrak t$

Let us recall that $\mathfrak t$ is the smallest cardinal $\kappa$ for which there exists a family $(T_\alpha)_{\alpha\in\kappa}$ of infinite subsets of $\omega$ such that $\bullet$ for any ordinals $\...
user avatar
  • 33.6k
6 votes
1 answer
205 views

Existence of a winning strategy in the $\boldsymbol{\Delta}_2^0$ game

Consider the following infinite perfect information game with two players (the name I gave in the title of the post it totally made up): at each round $i \in \omega$, player $\mathrm{I}$ picks a ...
user avatar
  • 927
21 votes
4 answers
2k views

The Chocolatier's game: can the Glutton win with a restricted form of strategy?

I have a question about the Chocolatier's game, which I had introduced in my recent answer to a question of Richard Stanley. To recap the game quickly, the Chocolatier offers up at each stage a finite ...
user avatar
14 votes
1 answer
1k views

An infinite game possibly due to Ernst Specker

I have a vague memory of an infinite game due to Ernst Specker with the following properties: (1) It is a two-person perfect information game, where the players move alternately. (2) The possible ...
user avatar
6 votes
1 answer
322 views

Are there "very narrow" undetermined games?

I'd like to close a gap left open in an old question of mine; I've tweaked the terminology to be a bit nicer. For a (boldface) pointclass $\Gamma$ and a payoff set $G\subseteq\omega^\omega$, say that $...
user avatar
2 votes
0 answers
130 views

Banach–Mazur game and mappings

The Banach-Mazur game on a nonempty space $X$ is defined as follows: two players, $I$ and $II$, alternately choose nonempty open sets \begin{matrix} I & U_0 && U_1 && \cdots ...
user avatar
7 votes
5 answers
562 views

Reference for graduate-level text or monograph with focus on "the continuum"

I always had the dream to design a course for my graduate students like "mathematical models of the continuum". This course should cover history of real numbers, the Measure Problem, the ...
user avatar
  • 125
4 votes
0 answers
82 views

Infinite positions in 3D chomp

I've recently come back to investigating ordinal chomp. See A winning move for the first player in $3 \times 3 \times \omega$ Ordinal Chomp for a definition. I made a new discovery, that the position \...
user avatar
  • 2,285
10 votes
0 answers
268 views

Undetermined Banach-Mazur games: beyond DC

This question is a follow-up to this one; see that question for the definition of Banach-Mazur games. There James Hanson showed that ZF+DC proves that there is an undetermined Banach-Mazur game; ...
user avatar
22 votes
1 answer
635 views

Undetermined Banach-Mazur games in ZF?

This question was previously asked and bountied on MSE, with no response. This MO question is related, but is also unanswered and the comments do not appear to address this question. Given a ...
user avatar
4 votes
1 answer
175 views

Can I win this variant of the Banach-Mazur Game?

Suppose I play the following game against the Opponent. My moves are rational numbers $p_i$ and the Opponent's moves are real numbers $\epsilon_i>0$. On turn $n+1$ the past move sequence is $...
user avatar
  • 1,606
2 votes
1 answer
147 views

Question about almost locally ccc and the Krom space

Definition 1. A family $\mathcal{B}$ of non-empty open sets in a topological space will be called $\pi$-base (or pseudo-base) if every non-empty open set contains at least one member of $\mathcal{B}$. ...
user avatar
6 votes
0 answers
176 views

Spaces where the Banach-Mazur game is undetermined

Let $X$ be a non-empty topological space. The Banach-Mazur game on $X$, $\textsf{BM}(X)$, is played as follows: Players I and II play an inning per positive integer. In the $n$-th inning Player I ...
user avatar
28 votes
2 answers
903 views

Solution to simple mathematical game

Consider the following game (that I made up). Two players each attempt to name a target number. The first player begins by naming 1. On each subsequent turn, a player can name any larger number that ...
user avatar
  • 331
5 votes
1 answer
557 views

Banach-Mazur game and infinite products

Studying the article "Games that involve set theory or topology" of Marion Scheepers, I found the following result Theorem 46 Let $\{(X_{i}, \tau_{i}) : i\in I \}$ be a family of topological spaces. ...
user avatar
1 vote
0 answers
86 views

Is there a well-posed definition of game on a graph? Or a well defined category of games on graphs?

All I ever found about this were natural language rules à la Asimov's three laws of robotics. The questions are straightforward questions: 1) Is there a well-posed mathematical definition of game on ...
user avatar
1 vote
0 answers
159 views

Winning strategies for a game on the natural numbers

Define $$F=\{(l_n, k_n)_{n=1}^t: t,l_n, k_n \in \mathbb{N}, l_1<\ldots <l_t, m_1<\ldots <m_t\}.$$ Suppose that I have a collection $G\subset F$, which is a set of ''good'' sequences. ...
user avatar
  • 59
2 votes
0 answers
169 views

An analytic game and Ramsey's theorem

Let $$P=\{(l_n, m_n)_{n=1}^t: l_n, m_n,t\in\mathbb{N}, l_1<\ldots <l_t, m_1<\ldots <m_t\}$$ and suppose that $T$ is some subset of $P$. Suppose that $T$ also has the following properties: ...
user avatar
  • 59
1 vote
2 answers
194 views

Convergence and winning strategies

Suppose we have a set $B\subseteq 2^\omega\times\omega^\omega$ and a sequence $(x_n)$ in $2^\omega$ such that for each $n$, Player I (the one trying to get into the payoff set) has a winning strategy ...
user avatar
  • 2,709
2 votes
1 answer
87 views

Rothberger game and Meager in itself sets

On $(\mathbb{R}, \tau)$ the euclidean space of real numbers, we define a new topology by letting $\tau^{*}=\{X\subseteq \mathbb{R}: X=\emptyset \hspace{0.1cm}\mbox{or}\hspace{0.1cm}\mathbb{R}\setminus ...
user avatar
2 votes
1 answer
117 views

Is there a three valued logic whose game semantics corresponds to potentially infinite games?

Consider game trees with the following properties: Each node in the tree is one of the following: Verifier Choice: Has one or more children Falsifier Choice: Has one or more children No Choice: Has ...
user avatar
  • 4,160
7 votes
0 answers
140 views

Is each Choquet topological group strong Choquet?

A topological space $X$ is called (strong) Choquet if the player II has a winning strategy in the (strong) Choquet game. It is known that a metrizable space $X$ is $\bullet$ Choquet if and only if it ...
user avatar
  • 33.6k
3 votes
0 answers
143 views

final coalgebra of the 𝓟${_{<κ}}$(A×X) endo-functor in $Set^*$?

In the paper Coalgebraic Games and Strategies F. Honsell, M. Lenisa, and R. Redamalla use the functor $F_A$(X) = ${\mathscr{P}_{<κ}}$(A×X) to define games coalgebraically. This is a functor from ...
user avatar
2 votes
0 answers
108 views

A community effort: equilibrium in quitting games [closed]

This thread is in the spirit of the polymath project: a combined effort of the community to solve a difficult open problem. It is an activity of the European Network for Game Theory whose goal is to ...
user avatar
  • 676
1 vote
0 answers
60 views

Continuous limits of Hex on larger and larger boards

Consider the game of Hex on a variable sized $n \times n$ board. Remap each board to be a discrete subset of the unit square $[0,1]^2$. Optimal games are now finite sequences on the unit square. We ...
user avatar
1 vote
2 answers
261 views

How to describe the common boundaries between regions in a infinite Sudoku?

This relates to the answer to a question "Who wins two player sudoku?" and this awesome blog. A Sudoku can be $N \times N$ where $\sqrt{N}$ is a natural number because $N \times N / \sqrt{N} \times \...
user avatar
  • 119
32 votes
1 answer
2k views

Is there a position in infinite Go for which the life of a particular stone has transfinite game value?

As follow up to Checkmate in $\omega$ moves?, we can ask the same question about go. Is there a position on a $\mathbb Z \times \mathbb Z$ goban such that either black can kill a white group, but ...
user avatar
  • 4,160
9 votes
3 answers
1k views

The Sudoku game: Solver-Spoiler variation

Consider the Sudoku Solver-Spoiler game, a natural variation of the Sudoku game recently appearing in the question Who wins two-player Sudoku? posted by user PyRulez. In that game, the players attempt ...
user avatar
19 votes
3 answers
972 views

The arithmetic progression game and its variations: can you find optimal play?

Consider the arithmetic progression game, a two-player game of perfect information, in which the players take turns playing natural numbers, or finite sets of natural numbers, all distinct, and the ...
user avatar
37 votes
3 answers
4k views

A game on integers

$A$ and $B$ take turns to pick integers: $A$ picks one integer and then $B$ picks $k > 1$ integers ($k$ being fixed). A player cannot pick a number that his opponent has picked. If $A$ has $5$ ...
user avatar
11 votes
1 answer
548 views

The Axiom of Determinacy and the Banach-Mazur game

The Wikipedia article on the Axiom of Determinacy (AD) claims: Equivalent to the axiom of determinacy is the statement that for every subspace X of the real numbers, the Banach–Mazur game BM(X) is ...
user avatar
46 votes
3 answers
4k views

Does knight behave like a king in his infinite odyssey?

The Knight's Tour is a well-known mathematical chess problem. There is an extensive amount of research concerning this question in two/higher dimensional finite boards. Here, I would like to tackle ...
user avatar
6 votes
1 answer
265 views

On the topological complexity of the set of winning strategies for Gale-Stewart Games

Given a set $A \subseteq \omega^\omega$, let $G_A$ denote the Gale-Stewart game with payoff set $A$ (so player $I$ wants the real built over the course of play to be in $A$ and player $II$ wants it ...
user avatar
3 votes
1 answer
447 views

If non-empty player has a winning strategy in Banach-Mazur game BM(X), then it also has in BM(Y)?

Let $f:X\rightarrow Y$ be a continuous, open, surjection function and second player (non-empty) has a winning strategy (not important which one, say for simplicity stationery st.) in $BM(X)$. Then can ...
user avatar
6 votes
1 answer
352 views

Products and Gale-Stewart games

For the purpose of this post, I will say that the Gale-Stewart game is the infinite two-player game of perfect information where players I and II alternate playing natural numbers, with I going first. ...
user avatar
  • 2,709
12 votes
0 answers
335 views

Undetermined copy/diagonalize games without CH

This question was the motivation behind an earlier question of mine; having thought about it some more, that question seems nontrivial and the connection is actually pretty tenuous anyways, so I've ...
user avatar
9 votes
2 answers
624 views

Choosing subsets of $\mathbb R$ of cardinality $\frak c$, who wins?

Consider the following infinite game: two players, I and II, are alternating and choosing a descending sequence of subsets of $\mathbb R$ of cardinality $\frak c$, so I chooses a set $A_1\subseteq\...
user avatar
  • 23.7k
6 votes
2 answers
532 views

Determinacy of (infinite, possibly loopy) combinatorial games

I am looking for references and hopefully enlightening proofs of the following statement(s) concerning the determinacy of not-necessarily-well-founded (i.e., possibly infinite, possibly loopy) ...
user avatar
  • 22.1k
1 vote
0 answers
511 views

On the Theory of Infinite Step Processes of Sequential Decision Making

On the border of Set Theory and Game Theory there is a broad class of Infinite Step Processes of Sequential Decision Making that can be characterized by the main following property: a Future ...
user avatar
9 votes
1 answer
355 views

Infinite-dimensional hex

Suppose $n$ players take turns selecting vertices of the grid $[k]^n = \left\{0, 1, 2, \ldots, k-1\right\}^n$. Each player is assigned a pair of opposite faces of the grid, and wins the game if they ...
user avatar
18 votes
1 answer
1k views

A game on sets of reals

A 2 player game on $\mathcal{P}(\mathbb{R})$: Players take turns playing uncountable sets of reals. Each play must be a subset of the previously played set. Player 1 wins if the intersection of all ...
user avatar
  • 16.4k
0 votes
1 answer
417 views

Infinite board games: sentences about

As a unified approach if we have an ( read any) infinite board game described as $\mathcal{G}$ using a particular axiom set A.. can a sentence be devised in A which automatically answers the basic ...
user avatar
  • 831
13 votes
1 answer
2k views

The infinite X in Conway's game of life

In Conway's game of life, take the initial position to be two infinite diagonal lines of live cells, with a single cell in common. Does this thing converge to a stable configuration? I.e., is the ...
user avatar
103 votes
11 answers
14k views

Checkmate in $\omega$ moves?

Is there a chess position with a finite number of pieces on the infinite chess board $\mathbb{Z}^2$ such that White to move has a forced win, but Black can stave off mate for at least $n$ moves for ...
user avatar
8 votes
4 answers
2k views

Infinite games: are they well defined?

It is just my curiosity about this question where we have an infinite game and (according to the answers) winning strategies for both players. I am familiar with terminating games only, and I am ...
59 votes
5 answers
8k views

Decidability of chess on an infinite board

The recent question Do there exist chess positions that require exponentially many moves to reach? of Tim Chow reminds me of a problem I have been interested in. Is chess with finitely many men on an ...
user avatar
6 votes
2 answers
954 views

Is perfect play possible in continuous rock-paper-scissors? game "step size" vs. "acceleration"

The first part of my question is simple: Is every game continuous in time and strategy-space also a game of perfect information with a good equilibrium? For example, consider rock-paper-scissors. The ...
user avatar
  • 2,303