Skip to main content

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.

Filter by
Sorted by
Tagged with
1 vote
0 answers
57 views

Family of graphs characterized by their eigenvalues

Studying the convergence/divergence of certain processes on simple graphs (processes similar to Kostant games on graphs), I'm confronted with the task of characterizing graphs whose spectra must ...
Gianfranco's user avatar
2 votes
3 answers
84 views

Topological game on $(0,1)$

I consider a « game » on a topological space with $2$ players. I will describe the game and tried to prove that one of the player has no winning strategy in the sense that the other player can always «...
G2MWF's user avatar
  • 1,391
1 vote
2 answers
94 views

Existence of Nash Equilibrium in a Game with Mixed Strategy Spaces

I am considering formulating an applied research problem as a simultaneous zero-sum game with two players. The first player's set of actions is an infinite and compact subset of $\mathbb{R}^n$, while ...
graphtheory123's user avatar
2 votes
1 answer
114 views

How is the set $C(f)\cap V$ of second category in $V$?

I am reading the paper "P. S. Kenderov, I. S. Kortezov and W. B. Moors, Continuity points of quasi-continuous mappings, Topology Appl. 109 (2001), 321–346." Just before Theorem 2 of the ...
Ghosh Da's user avatar
1 vote
1 answer
70 views

Mathematically prove whether it's possible to survive indefinitely in an unbounded tag game

Suppose we have a tag game, with an unbounded (2D) map, where the player possesses a character in the map represented by it's (x,y) position, that can, at any frame, move 1 unit left, right, up or ...
Clovergheister's user avatar
13 votes
2 answers
827 views

Infinite wacky race

Dick Dastardly is taking part in an infinite wacky race. What is infinite about it, you ask? Well, just everything! There are infinitely many racers, every one of which can run infinitely fast and the ...
Alma Arjuna's user avatar
  • 3,901
0 votes
0 answers
49 views

Axiom of Choice and Borel determinacy for Polish space

Given a set $A$, Borel determinacy for $A$ is the theorem (of $\mathsf{ZFC}$) asserting that every Borel subset of $A^\omega$ is determined. That is, if I and II take turns playing members of $A$, and ...
Clement Yung's user avatar
  • 8,387
3 votes
1 answer
174 views

Infinite game of an unfair coin toss

Following game between person A and B is proposed: Person A has an unfair coin with probability $p \in (\frac{1}{3},\frac{1}{2})$ of heads. Person B starts with a captial of 100€. For each time B ...
tychonovs-scholar's user avatar
0 votes
2 answers
73 views

Finite Games winning strategy exercises

I'm currently studying finite games from the textbook "Automata Theory and its Applications" by Bakhadyr Khoussainov and Anil Nerode and am having trouble with this exercise with the ...
Noah R's user avatar
  • 1
1 vote
0 answers
33 views

Finite Games winning strategy exercises [duplicate]

I'm currently studying finite games from the textbook "Automata Theory and its Applications" by Bakhadyr Khoussainov and Anil Nerode and am having trouble with this exercise with the ...
user avatar
1 vote
1 answer
121 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 ...
Clement Yung's user avatar
  • 8,387
1 vote
1 answer
105 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 ...
lis's user avatar
  • 13
3 votes
2 answers
108 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 ...
Steven Clontz's user avatar
2 votes
2 answers
74 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$...
Steven Clontz's user avatar
3 votes
2 answers
85 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 ...
Steven Clontz's user avatar
1 vote
2 answers
115 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\...
Steven Clontz's user avatar
6 votes
2 answers
211 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/...
C. Caruvana's user avatar
  • 1,179
2 votes
1 answer
184 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 ...
student's user avatar
  • 21
2 votes
0 answers
70 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 ...
Mathathon's user avatar
0 votes
2 answers
127 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 ...
Philipp's user avatar
  • 4,584
7 votes
3 answers
334 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 ...
Philipp's user avatar
  • 4,584
2 votes
0 answers
73 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 ...
Foster Boondoggle's user avatar
1 vote
1 answer
170 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 ...
Dylan Rollins's user avatar
3 votes
0 answers
78 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 ...
Ynir Paz's user avatar
  • 607
1 vote
1 answer
184 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.sstatic.net/wvccF.jpg "I’m ...
Gtcarozzi's user avatar
32 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 ...
mathlander's user avatar
  • 4,057
1 vote
1 answer
149 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 ...
SP SINGH's user avatar
5 votes
1 answer
167 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....
mathlearner98's user avatar
8 votes
0 answers
189 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 ...
Mathemagician314's user avatar
0 votes
1 answer
53 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 ...
user122424's user avatar
  • 3,978
1 vote
0 answers
50 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 ...
jfab's user avatar
  • 25
7 votes
0 answers
96 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$ ...
Noah Schweber's user avatar
1 vote
0 answers
62 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 ...
Roy's user avatar
  • 95
1 vote
1 answer
115 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$...
Ollie Garland's user avatar
11 votes
0 answers
227 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$ (...
Ris's user avatar
  • 1,292
0 votes
0 answers
116 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 ...
Pathfinder's user avatar
1 vote
1 answer
160 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 ...
Nameless Guy's user avatar
0 votes
3 answers
44 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 ...
user avatar
1 vote
0 answers
36 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 ...
Moni145's user avatar
  • 2,162
2 votes
1 answer
139 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 ...
Moni145's user avatar
  • 2,162
0 votes
1 answer
45 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 ...
Yonatan's user avatar
  • 35
1 vote
0 answers
43 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 ...
quanticbolt's user avatar
  • 1,776
2 votes
0 answers
74 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 ...
Zach466920's user avatar
  • 8,361
2 votes
1 answer
135 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 ...
Mara's user avatar
  • 155
1 vote
0 answers
45 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 ...
Theo Deep's user avatar
  • 247
3 votes
1 answer
91 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 ...
Matteo Casarosa's user avatar
2 votes
0 answers
46 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', ...
WALTER ANGELO ROJAS GUTIERREZ's user avatar
0 votes
1 answer
92 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 ...
Ma Joad's user avatar
  • 7,544
0 votes
1 answer
87 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 ...
I.Kiaan's user avatar
  • 41
3 votes
1 answer
117 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 ...
Maurice Dekker's user avatar