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.
56
questions
2
votes
0
answers
223
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 ...
- 19.1k
7
votes
0
answers
228
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^{<\...
- 19.1k
5
votes
1
answer
165
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 ...
- 963
3
votes
0
answers
82
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 ...
- 141
17
votes
5
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 ...
- 17.5k
16
votes
0
answers
547
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, ...
- 208k
2
votes
0
answers
129
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 ...
- 19.1k
3
votes
0
answers
130
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 ...
- 13.8k
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 ...
- 459
2
votes
1
answer
129
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 $\...
- 38.7k
6
votes
1
answer
228
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 ...
- 1,628
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 ...
- 208k
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 ...
- 46.8k
6
votes
1
answer
342
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 $...
- 19.1k
2
votes
0
answers
146
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 ...
- 103
7
votes
5
answers
586
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 ...
- 125
4
votes
0
answers
109
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 \...
- 2,573
10
votes
0
answers
279
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; ...
- 19.1k
22
votes
1
answer
673
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 ...
- 19.1k
4
votes
1
answer
186
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 $...
- 1,721
2
votes
1
answer
159
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}$. ...
- 541
6
votes
0
answers
181
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 ...
- 541
28
votes
2
answers
943
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 ...
- 331
5
votes
1
answer
580
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. ...
- 541
1
vote
0
answers
88
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 ...
- 11
1
vote
0
answers
164
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.
...
- 59
2
votes
0
answers
175
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: ...
- 59
1
vote
2
answers
198
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 ...
- 2,853
2
votes
1
answer
94
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 ...
- 541
1
vote
1
answer
130
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 ...
- 4,415
7
votes
0
answers
151
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 ...
- 38.7k
3
votes
0
answers
152
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 ...
- 131
2
votes
0
answers
114
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 ...
- 706
2
votes
0
answers
67
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 ...
- 1,558
1
vote
2
answers
271
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 \...
- 119
32
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 ...
- 4,415
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 ...
- 208k
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 ...
- 208k
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$ ...
- 879
11
votes
1
answer
601
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 ...
- 3,850
46
votes
3
answers
5k
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 ...
6
votes
1
answer
279
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 ...
- 1,792
3
votes
1
answer
454
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 ...
- 31
6
votes
1
answer
371
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. ...
- 2,853
12
votes
0
answers
343
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 ...
- 19.1k
9
votes
2
answers
637
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\...
- 25.9k
6
votes
2
answers
571
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) ...
- 26.4k
1
vote
0
answers
514
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 ...
9
votes
1
answer
402
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 ...
- 707
19
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 ...
- 17.5k