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.
68
questions
8
votes
0
answers
148
views
Which sentences are "strategically preserved"?
Below, everything is first-order.
Say that a sentence $\varphi$ is strategically preserved iff player 2 has a winning strategy in the following game:
Players 1 and 2 alternately build a sequence of ...
10
votes
0
answers
349
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 ...
4
votes
1
answer
391
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 ...
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 ...
6
votes
2
answers
286
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-...
0
votes
0
answers
99
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 ...
6
votes
0
answers
164
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 ...
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 ...
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 ...
7
votes
0
answers
189
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 ...
4
votes
2
answers
152
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 ...
10
votes
0
answers
318
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}$, ...
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 ...
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^{<\...
5
votes
1
answer
194
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 ...