Skip to main content

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
10 votes
0 answers
338 views

Connection properties of a single stone on an infinite Hex board

This includes a series of questions. One of the most typical examples is shown as the picture below. An half-infinite Hex board with an one row of black stones. Black stones are separated by one ...
hzy's user avatar
  • 151
4 votes
1 answer
383 views

"Infinity": A card game based on prime factorization and a question

I have been developing a card game called "Infinity", which involves a unique play mechanic based on card interactions. In this game, each card displays a set of symbols, and players match ...
mathoverflowUser's user avatar
14 votes
3 answers
1k views

Examples of concrete games to apply Borel determinacy to

I'm teaching a course on various mathematical aspects of games, and I'd like to find some examples to illustrate Borel determinacy. Open or closed determinacy is easy to motivate because it proves ...
Gro-Tsen's user avatar
  • 30.6k
6 votes
2 answers
285 views

Embeds in a topological W-group, or a W-space that embeds in a topological group?

In Theorem 3.11 of Tkachuk - A compact space $K$ is Corson compact if and only if $C_p(K)$ has a dense lc-scattered subspace it's shown that if a compact Hausdorff space embeds in a topological W-...
Steven Clontz's user avatar
0 votes
0 answers
91 views

Are gaps and loopy games interchangeable in the Surreal Numbers?

The class of surreal numbers (commonly called $No$) is not complete: it contains gaps. Some people have studied the "Dedekind completion" of the surreal numbers in order to do limits and ...
Farran Khawaja's user avatar
6 votes
0 answers
161 views

Complexity of transfinite 5-in-a-row and other games

Suppose that 5-in-a-row is played on an infinite board, and after an infinite number of moves, if no one won yet and there is an empty square, the game just continues. At limit steps, it is the first ...
Dmytro Taranovsky's user avatar
18 votes
1 answer
1k views

Let $R, S$ be infinite sets. Alice and Bob will play a game over $R\times S$

Let $R, S$ be infinite sets. Alice and Bob will play a game over $R\times S$. Alice's color is red and Bob's color is blue. In each step, for each $s\in S$, a player will choose finitely many ...
Alma Arjuna's user avatar
1 vote
0 answers
71 views

EF-games with scrambling

This question is motivated both by the notion of zero-knowledge proofs and by general curiosity about versions of the infinitely-long Ehrenfeucht-Fraisse game which don't trivialize (= Duplicator win ...
Noah Schweber's user avatar
7 votes
0 answers
186 views

Strengthening Determinacy in constructive set theory?

Recall how games work. Let $X$ be a set (the "game space") and $\alpha$ an ordinal (the "game clock"). Alice and Bob take turns naming elements of $X$. We write them down in order ...
Tim Campion's user avatar
  • 62.2k
4 votes
2 answers
151 views

Does there exist a non-hemicompact regular space for which the 2nd player in the $K$-Rothberger game has a winning Markov strategy?

Assume spaces are regular. A space is $\sigma$-compact if and only if the second player in the Menger game has a winning Markov strategy (relying on only the most recent move of the opponent and the ...
Steven Clontz's user avatar
10 votes
0 answers
316 views

Determinacy coincidence at $\omega_1$: is CH needed?

This is a follow-up to the last part of an old MSE answer of mine. Briefly, an analogue at $\omega_1$ of Steel's equivalence between clopen and open determinacy can be proved assuming $\mathsf{CH}$, ...
Noah Schweber's user avatar
2 votes
0 answers
260 views

Is determinacy of (some) very long open games consistent?

For $\varphi$ a first-order sentence in the language of set theory and $\kappa$ an ordinal, let $G_\varphi^{\kappa}$ be the game of length $\kappa$ in which players $1$ and $2$ alternately play ...
Noah Schweber's user avatar
7 votes
0 answers
248 views

Is this determinacy principle consistent?

Let $\mathsf{ODet}_{\omega_1}(L(\mathbb{R}))$ be the following principle ("determinacy for simple open length-$\omega_1$ games"): If $\kappa$ is any ordinal and $X\subseteq \kappa^{<\...
Noah Schweber's user avatar
5 votes
1 answer
193 views

Are the completeness Games $G_{\lambda+1}(P)$ and $G_{\lambda^+}(P)$ equivalent for INC?

The completeness game $G_{\gamma}(P)$ for a partial order $P$ has players COM and INC play alternatingly and descendingly elements of $P$ with player INC playing first and player COM playing at limit ...
Hannes Jakob's user avatar
  • 1,632
3 votes
0 answers
134 views

Poker with infinite stack size

In two-player No Limit Texas Hold 'Em (NLHE), the optimal strategy depends on the "effective stack size," that is maximum amount of money held by one of the players (in the sequel I'll just ...
Davis Yoshida's user avatar
17 votes
6 answers
1k views

Strategic vs. tactical closure

The Banach-Mazur game on a poset $\mathbb P$ is the $\omega$-length game where the players alternate choosing a descending sequence $a_0 \geq b_0 \geq a_1 \geq b_1 \geq \dots$. Player II wins when ...
Monroe Eskew's user avatar
  • 17.9k
24 votes
2 answers
1k views

What is the complexity of the winning condition in infinite Hex? In particular, is infinite Hex a Borel game?

Consider the game of infinite Hex, where two players Red and Blue alternately place their stones on the infinite hex grid, each aiming to create a winning configuration. Red wins after infinite play, ...
Joel David Hamkins's user avatar
2 votes
0 answers
139 views

Weakening of open determinacy for uncountably long games

For a cardinal $\kappa$ I'll use the phrase "$(\kappa,\kappa)$-game" to mean "two-player, perfect-information, deterministic game on $\kappa$ of length $\kappa$." Say that a ...
Noah Schweber's user avatar
3 votes
0 answers
150 views

A p-point game with infinitely many ultrafilters

The following game-theoretic characterization of p-points is well known: Theorem A. An ultrafilter $D$ on the set $\omega$ of natural numbers is a p-point if and only if player I does not have a ...
Goldstern's user avatar
  • 14k
28 votes
7 answers
6k 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 ...
Sin Nombre's user avatar
2 votes
1 answer
149 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 $\...
Taras Banakh's user avatar
  • 41.1k
6 votes
1 answer
251 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 ...
Lorenzo's user avatar
  • 2,236
25 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 ...
Joel David Hamkins's user avatar
15 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 ...
Richard Stanley's user avatar
6 votes
1 answer
364 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 $...
Noah Schweber's user avatar
2 votes
0 answers
161 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 ...
Smolin Vlad's user avatar
7 votes
5 answers
649 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 ...
Ruth-NO's user avatar
  • 125
4 votes
0 answers
154 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 \...
Thomas's user avatar
  • 2,751
10 votes
0 answers
288 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; ...
Noah Schweber's user avatar
22 votes
1 answer
730 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 ...
Noah Schweber's user avatar
4 votes
1 answer
203 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 $...
Daron's user avatar
  • 1,915
2 votes
1 answer
167 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}$. ...
Gabriel Medina's user avatar
6 votes
0 answers
194 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 ...
Gabriel Medina's user avatar
28 votes
2 answers
1k 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 ...
cbmanica's user avatar
  • 331
5 votes
1 answer
596 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. ...
Gabriel Medina's user avatar
1 vote
0 answers
93 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 ...
IpsumPanEst's user avatar
1 vote
0 answers
171 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-1's user avatar
  • 59
2 votes
0 answers
194 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-1's user avatar
  • 59
1 vote
2 answers
212 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 ...
Iian Smythe's user avatar
  • 2,981
2 votes
1 answer
101 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 ...
Gabriel Medina's user avatar
2 votes
1 answer
144 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 ...
Christopher King's user avatar
7 votes
0 answers
163 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 ...
Taras Banakh's user avatar
  • 41.1k
3 votes
0 answers
156 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 ...
Henry Story's user avatar
2 votes
0 answers
122 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 ...
Eilon's user avatar
  • 745
2 votes
0 answers
86 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 ...
Geoffrey Irving's user avatar
2 votes
2 answers
308 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 \...
DukeZhou's user avatar
  • 129
33 votes
1 answer
3k 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 ...
Christopher King's user avatar
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 ...
Joel David Hamkins's user avatar
19 votes
3 answers
1k 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 ...
Joel David Hamkins's user avatar
41 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$ ...
Haoran Chen's user avatar