Questions tagged [infinite-games]
Infinite games. Combinatorial game theory for infinite two-player games of perfect information. Infinitary aspects of common recreational games. Open games, clopen games. Determinacy. Transfinite game values. Topological games.
101
questions
1
vote
1
answer
107
views
"Explicit" undetermined set of reals
Recall that a set $X \subseteq \omega^\omega$ is determined if the Gale-Stewart game for $X$ is determined. It's well-known that the axiom of choice implies the existence of an undetermined set. The ...
- 8,245
1
vote
1
answer
42
views
(Combinatorial) Game Theory: Determinacy and Determinism
I am struggling with the concepts of Determinacy and Determinism.
Are the following statements correct(for 2-player, zero-sum games)?
Or am I getting something mixed up in my head?
A game has the ...
- 13
3
votes
2
answers
89
views
Why can't a Lusin set be sigma-compact?
In A Direct Proof of a Theorem of Telgársky, Scheepers asserts that the Menger game is indeteremined for a Lusin (aka Luzin) subset of the reals. That is, the first player lacks a winning strategy in ...
- 4,299
2
votes
2
answers
65
views
Can P1 improve an open cover to an omega-cover in the finite-open game?
Definitions/terms taken from https://www.sciencedirect.com/science/article/abs/pii/S016686411830470X (https://arxiv.org/abs/1806.06001).
In the finite-open game $FO(X)$, during each round $n<\omega$...
- 4,299
3
votes
2
answers
78
views
Do uncountable spaces admit Markov strategies in Rothberger-style games?
Consider the selection game $G_1(\mathcal C,\mathcal C)$ where $\mathcal C$ is associated with a class of open covers. Considering various possibilities for $\mathcal C$, do uncountable spaces admit ...
- 4,299
1
vote
2
answers
106
views
How are the Menger and $\Omega$-Menger games related?
Let $G_{fin}(\mathcal A,\mathcal B)$ be a selection game taking place over $\omega$ rounds. In round $n<\omega$, P1 chooses some $A_n\in\mathcal A$, then P2 chooses some finite subcollection $B_n\...
- 4,299
6
votes
2
answers
192
views
What kinds of selection principles hold for Fortissimo space?
Note: This question is being posted primarily as a reference to include for https://topology.pi-base.org/ following the guidelines for references as spelled out at https://github.com/pi-base/data/blob/...
- 1,144
2
votes
1
answer
120
views
Why restricted removal Nim games with 1 pile has pattern (cycle in states)?
I working on solution of NIM-like game, where players take from one piece from 1 to k and players can't repeat previous turn (only the opponent's previous move). Total n stones in beginning. Winner is ...
- 21
2
votes
0
answers
67
views
Elegantly solvable game always ends in finite number of steps
The problem I'll describe below looks very difficult to me when trying to approach it with common mathematical processes (I'm not very skilled), but I've noted a good relation with physics which ...
- 21
0
votes
2
answers
79
views
How does recursion work in stochastics?
How do I justify recursive equations when it comes to solving basic probability/stochastic questions?
(I am attending a basic stochastic/probability class so we can't use measure theory or advanced ...
- 4,278
7
votes
3
answers
309
views
Game: $\frac{1}{3}$ winning probability vs. $\frac{2}{3}$ winning probability
$A$ and $B$ play a round-based game. Each round $A$ wins with probability $\frac{1}{3}$ and $B$ with probability $\frac{2}{3}$. The loser of a round pays $1$ USD to the winner. The winner of the whole ...
- 4,278
2
votes
0
answers
70
views
Searching for Martin Gardner / Dr. Matrix reference
In a recent interview on Robinson's Podcast, Joel David Hamkins described an infinite game he called "The chocolatier and the glutton" (also at this link). The 2 player alternate-move game ...
0
votes
1
answer
132
views
Can a game of chess go on forever?
Is there non-terminating game of chess? I ran into this problem while designing a machine learning model to estimate the probability that a given chess player wins. If we ignore the 50-move-rule and ...
3
votes
0
answers
66
views
Game of placing lines on the plane, trying to create $n$-gon
Given a natural number $n$, consider the following 2-player game:
at each turn, a player places an (infinite) line on the plane (that wasn't already placed). The first player wins if at any point in ...
- 423
1
vote
1
answer
156
views
A Pocket Frog collection problem (spend minimum money to collect all frogs) [closed]
This is a problem I've been thinking about for a few months. It was created by Kyle Hess, inspired from playing the game Pocket Frogs.
OP's PROBLEM STATEMENT:
https://i.stack.imgur.com/wvccF.jpg
"...
- 19
30
votes
1
answer
1k
views
In the game of Repeat-a-Number, who wins?
I devised a game recently. There is a string of numbers, and each player extends the string by appending a number to the end based on the current last number of the string. The string starts as the ...
- 3,905
1
vote
1
answer
95
views
Infinite two players zero sum game and Nash equilibrium
Consider a two player zero sum game (finite strategy space) with mixed strategies. Let the game value is $v$ which is obtained at a Nash equilibrium say $(p,q)$ where $p$ and $p$ are probability law ...
- 61
5
votes
1
answer
130
views
Question on Gale-Stewart Theorem and Axiom of Choice
I am reading Kechris' descriptive set theory text book, and there is this Theorem regarding infinite games:
Gale-Stewart: Let $T$ be a non-empty pruned tree on $A$. Let $X\subset[T]$ be closed or open....
- 762
8
votes
0
answers
141
views
Can War be Infinite?
War is a card game played by two players, each of which has half of a deck of cards. At the same time, the players take the top card from their deck, and place it face up in front of them. The player ...
- 806
0
votes
1
answer
52
views
game of 2 players on an ultrafilter $\cal U$ on $\omega$ in which neither player has a winning strategy
There is a game of 2 players (I and II) with an ultrafilter $\cal U$ on $\omega$ such that neither player has a winning strategy. I would like to understand in this game where in which part of the ...
- 3,872
1
vote
0
answers
46
views
Empty intersection of uncountable sets game
We define a two player game in $\mathbb{R}$. Player 1 chooses an uncountable set $X_1 \subseteq \mathbb{R}$. Player 2 chooses some uncountable subset $X_2 \subseteq X_1$. The game continues and a ...
- 25
7
votes
0
answers
93
views
Is this cardinal characteristic trivial? (Number of strategies needed to guarantee at least one win)
(Now asked at MO.)
Let the determinacy number, $\mathfrak{g}$ (for "game"), be the smallest cardinal such that for every (two-player, perfect-information, length-$\omega$) game on $\omega$ ...
- 240k
1
vote
0
answers
53
views
Minimax over long term, one player plays first for a long time -> converges to single player game optimum
Suppose there is a game with two players involving probability. There are finitely many game states, and associated with each state is a set of moves available to the current player, and each move ...
- 85
1
vote
1
answer
90
views
What is the winning strategy for this deterministic game?
I was trying to solve one of the questions in Herrlich's book "The Axiom of Choice" and got stuck on the second part of this problem. The game in question as described by Herrlich is:
Let $X$...
11
votes
0
answers
216
views
Is mate-in-$n$ problem for Trappist-1 undecidable?
Trappist-1 is a variant of infinite chess that has a piece called huygens which leaps any prime number of squares orthogonally. To actually implement this game, it should have decidable mate-in-$0$ (...
- 1,252
0
votes
0
answers
87
views
Is the Game of Life predictable?
I played the Game of Life intensively for a while. I tried to keep things alive from all kinds of initial configurations and succeeded up to about 1000 iterations maximally. Everything died all the ...
1
vote
1
answer
125
views
A possible easy proof of Borel determinacy?
I was initially trying to prove determinacy of $\mathbf{\Sigma}^0_2$ games, but surprisingly the proof I came up with seems to generalise all the way to Borel determinacy. Obviously this sounds a ...
- 11
0
votes
3
answers
43
views
Average coinflips to reach the 6 (Custom game)
a friend of mine asked me about a certain game mechanic in a videogame and how many tries it would take for him (on average) to reach his goal. In abstract form, it can be explained as follows:
You ...
user984645
1
vote
0
answers
33
views
Where do winning strategies occur for Player II in the Determinacy of Computable Open Games relative to a parameter?
Moschovakis goes over various theorems proving the Determinacy of closed/open games, and I am reading into various papers regarding the characterization of ordinals where winning strategies for the ...
- 2,104
2
votes
1
answer
111
views
Overall confusion in Moschovakis' Proof that $\Sigma_2 ^0$ games are determined (Page 221)
I'm reading through Moschovaki's proof that all $\Sigma_2^0$ games are determined, and the second part of the proof is confusing me. I follow up to the point where they prove $u\in W^{\xi}\implies $ I ...
- 2,104
0
votes
1
answer
43
views
Formulating stochastic sequential or discrete time games
I am trying to formulate a stochastic sequential game in discrete time, and was trying to do so as is common in the literature but couldn't find the appropriate setting anywhere.
I'm sure that it ...
- 15
1
vote
0
answers
41
views
Argument for cardinality of all possible strategies for a two-player game
If I understand correctly, a strategy for a two-player game (for either player) is a function from $\omega^{<\omega}$ (i.e. the set of all finite sequences of natural numbers) to $\omega$. Jech ...
- 1,714
2
votes
0
answers
70
views
Are Banach-Mazur Games related to filter Convergence?
Is there a way to connect filter convergence to the condition for player 1/2 to win a Banach-Mazur game in an if (and only if) fashion? Thanks! Details below...
A Banach-Mazur game is defined as ...
- 8,281
2
votes
1
answer
116
views
Why are Bernstein sets not determined?
I've been reading Oxtoby's Measure and Category and in chapter 6 he discusses the game of Banach-Mazur for two players $A$ and $B$ on the unit interval $I_0 \subset \mathbb{R}$. Towards the end of the ...
- 155
1
vote
0
answers
40
views
Infinite game (Ehrenfeucht-Fraïssé?) for Linear Temporal Logics
Imagine we have two LTL formulae: A and B. I would like to prove whether they are equivalent or not (the formulae can have the "Globally" operator, so the game is infinite).
To do so I have ...
- 247
3
votes
1
answer
89
views
Presentation on game theory and determinacy
I have to write a short paper(about 20 pages) and prepare a presentation (about 1 hour) for an exam on Game Theory (it is a general, introductory course). I've looked up some things on the internet ...
- 546
2
votes
0
answers
45
views
Is there a paper or book about countable-open game?
I am studying about topological game, and I found the progression:
Point-Open(X)>> Finite-Open(X)>>Compact-Open(X).
I understand that a natural way to extend 'be finite' is 'be compact', ...
0
votes
1
answer
78
views
"Playable" games on an uncountable set
Almost all games in real life are based on a finite set of integers (for example, we can index each possible movement in chess by an integer). But it is still pretty interesting to think about games ...
- 7,158
0
votes
1
answer
80
views
Game on $[0;1]$ about repeating decimal
Two players play the following game. Before the beginning $"0."$ is written on the board. The first player writes any (finite) sequence of digits. The second one then writes only one digit. Then the ...
- 41
3
votes
1
answer
114
views
history-based strategy versus position-based strategy
SUMMARY: suppose a game is played that is a walk on an infinite directed graph without blind points, where the two players each make one step alternatingly.
Suppose that the pay-off of a play is ...
- 436
0
votes
1
answer
40
views
Can you help me find an optimal mixed strategy for this simple 2-person allocation game?
Consider the following simple 2-person game. Players 1 and 2 each have 100 dollar coins, with a barrier between them, hiding each other's moves. Each player must allocates his 100 coins into 3 piles:...
- 1
3
votes
1
answer
128
views
How to win when placing colored dots on a plane against one opponent?
A‘s color is purple, B‘s color is green.
They alternately set a dot in their color on a set 2D-plane.
Whoever manages to
construct a triangle in their own color without a dot in the other color ...
- 65
2
votes
1
answer
77
views
Do hybrid games exist?
I'm new to game theory. So far, I know that we have games with finite strategy sets and games with continuous strategy sets. I was wondering if there are any games in which some players have finite ...
- 21
1
vote
0
answers
91
views
Coin Flipping Game -- St. Petersburg Variant?
Suppose Alice and Bob are playing a game with a fair coin. Every time the coin comes up heads, the score (initially 0) increases by 1. If the coin comes up tails, the score decreases by 1. If the ...
- 212
0
votes
1
answer
116
views
Definition of a drawing strategy
Given the following definition:
Let $M$ be a move set and $A,B \subset M^\omega$ are disjoint, we define the winning
conditions for the game $G(A,B)$ as follows: if the play of the game is
$x \in M^\...
- 1,668
2
votes
1
answer
124
views
Intuition behind equivalence of infinite games
In my lecture notes we denote with $S_I^T$ and $S_{II}^T$ the sets of all strategies for player I and II for a game in (a tree) $T$. Then follows a definition:
Say that the game $G(T; A)$ dominates ...
- 1,668
6
votes
4
answers
293
views
Why can't you lose a chess game in which you can make $2$ legal moves at once?
So here is the Problem :-
Consider a normal chess game in an $8*8$ chessboard such that every player makes $2$ legal moves at once alternatively . Now imagine that you was asked to play with Magnus ...
- 4,157
2
votes
0
answers
501
views
How to mathematically explain why the median kill/death ratio is always lower than the mean in battle royale games?
Firstly this is a theory that I'm pretty certain must be true at least under certain conditions, but I don't know how to explain it mathematically. I understand there are many variables I'm not ...
- 21
1
vote
1
answer
68
views
Coin Tossing Game Optimal Stragegy [closed]
A and B are playing coin toss game with a fair coin as a team, both of them have to be correct in a game to be able to gain one point, no communications will be allowed after the game starts.
Assuming ...
- 87
0
votes
1
answer
288
views
Infinite Prisoners dilemma
Please help me understand the idea of solving this problem.
There are infinitely repeated game $G( \infty, \sigma)$.
$$\begin{array}{|c|c|c|}
\hline
&c&d \\
\hline
c&(0,0)&...
- 47