Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

1
vote
1answer
27 views

A question on repeated game theory

I recently have come across a business problem which could be convereted into a game problem as follows: Imagine an infinitely repeated game between two players in which the firts player (leader) ...
2
votes
1answer
63 views

Proof that “$\uparrow$ is the unique solution of $tiny(G) = G$”

Tiny & miny games can be defined as: $$tiny(G) = \{0||0|-G\}$$ $$miny(G) = -tiny(G) = \{G|0||0\}$$ From the Wikipedia page for tiny and miny: Similarly curious, mathematician John Horton ...
2
votes
1answer
41 views

Game Theory Reccomendation, Mean Field Theory

I'm about to do a sort of reading course with a mathematics professor wherein I read and teach him about Game Theory. He claims not to know Game Theory. After that, we aim to read about Mean Field ...
0
votes
1answer
37 views

Game theory applied to invoicing

There is a traditional practise in precuement of almost any kind of paying an invoice at l ast thirty days after it has been received. Is there any application of game theory here that can justify ...
1
vote
0answers
85 views

Determinacy of complement of set

Here I described the Gale-Stewart game on Baire space $\mathbb{N}^{\mathbb {N}}$. If the set A is determined (one of the players has a winning strategy), what can we say about the determinacy of ...
2
votes
1answer
84 views

Gale-Stewart game

Let's look at the Gale-Stewart game on $\mathbb N^{\mathbb N}$ space (it consists of infinite sequences of natural numbers). There are 2 players: $A$ and $B$. They write one natural number by turns (A ...
1
vote
1answer
102 views

A chomp game with infinite board size.

Given a chomp game with board size $ m * \infty $. So I've already understood that this game is final, and has a finite number of states. However I'm having problems with figuring out whether there ...
3
votes
0answers
358 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 stationary st.) in $BM(X)$. Then can ...
2
votes
1answer
220 views

Gale-Stewart Theorem (open games are determined) implies closed games are determined

A Gale-Stewart game $G(A)$ is played on a set $A\subseteq\mathbb N^\mathbb N$. In this game, players p0 and p1 alternately pick a natural number, forming a sequence $\alpha:=\alpha_0\alpha_1\alpha_2\...
5
votes
0answers
89 views

Reference Request: A Tychonoff space $X$ where the game $\mathrm{G}_1(\Omega,\Omega)$ is undetermined

Given a Tychonoff space $X$, let $\Omega$ be the set of all $\omega$-coverings of $X$, where by $\omega$-cover we mean a collection $\mathcal{U}$ of open sets of $X$ such that for any $F\in[X]^{<\...
4
votes
1answer
186 views

Question on proof that Gale-Stewart game is determined for open sets

An infinite game of perfect information consists of a finite set $A$ of moves, two players and a set $X \subseteq A^{\mathbb N}$ of winning conditions for player I. By convention player I makes the ...
2
votes
1answer
69 views

Dealing with an infinitely repeated game

I have been playing around with problems related to game theory, and I ran into this issue related to an infinitely repeated game. Consider this game repeated an infinite number of times: $$\begin{...
4
votes
2answers
2k views

King and knight moving on an infinite chess board

There are actually two separate problems: King problem: How many squares can a king moving on an infinite chess board reach in N moves? Knight problem: How many squares can a knight ...
2
votes
1answer
332 views

Question about probability in infinite game of chance

Imagine a game where you start with \$100 and toss a coin repeatedly. If it's heads - you lose \$1, if its tails - you double your money. Game ends when you lose all the money. Given infinite amount ...
7
votes
0answers
78 views

The principle $S_1(\mathcal O,\mathcal O)$ versus the game $G_1(\mathcal O,\mathcal O)$

Given a topological space $X$, Let $\mathcal O$, denote the set of all open covers of $X$. We say that a space $X$ satisfies $S_1(\mathcal O,\mathcal O)$, if for every sequence of open covers $\{ \...
4
votes
0answers
90 views

Strong Choquet preimage implies strong Choquet?

Recall that a strong Choquet space is one where player II has a winning strategy in the game where two players take turns: player I chooses an open set and a point inside, then player II chooses a ...
1
vote
1answer
72 views

Set of winning strategies for union of winning sets

Suppose that $G( \omega, A, X)$ denotes a sequential game of perfect information in which player I and player II play an element in $A$ in each turn with a total number of $\omega$ moves. $X$, the ...
4
votes
1answer
83 views

Is it true player II must have a winning strategy, if the winning set is a closed but not open set?

Suppose, in a Gale-Stewart game, player I and player II choose from $\omega$ in a alternating fashion. If the outcome is in the winning set $W$, then player I wins. Otherwise player II wins. If $W$ is ...
11
votes
1answer
382 views

Infinite combinatorial games

Hercules vs. Hydra: Recall the story where every time Hercules cuts of a head, two more heads grow instead. Now suppose the following: The hydra starts off with one head, but every time Hercules cuts ...
16
votes
0answers
625 views

“Infinito”, a combinatorial game with infinite width game-tree

I recently designed a combinatorial game (sequential game of perfect information) with an infinite branching factor, that is it has a game-tree of infinite width. I'm wondering how is it possible to ...
4
votes
1answer
118 views

Why the set of outcomes generated by a fixed strategy of one player in Gale-Stewart game is a perfect set?

In the proof that there is a payoff set $X$ such that the Gale-Stewart game is not determined(see here, Proposition 3.1.). I don't know why $X$, the set of all outcomes generated by a fixed strategy ...
4
votes
1answer
81 views

The difference between winning tactic and winning strategy

In the topological game, what is the difference between winning tactic and winning strategy? Why the author (in this paper: LEFT SEPARATED SPACES WITH POINT-COUNTABLE BASES) said that, the first ...
0
votes
1answer
84 views

A question on topological game

This is from the paper: LEFT SEPARATED SPACES WITH POINT-COUNTABLE BASES by WILLIAM G. FLEISSNER. It is a little difficult for me to understand that what's the meaning of $I$ wins, and $II$ wins. ...
5
votes
1answer
925 views

Math and Logic of Infinite Chess

Two players (White and Black) are playing on an infinite chess board (extending infinitely in all directions). First, White places a certain number of queens (and no other pieces) on the board. ...
19
votes
4answers
3k views

Is chess Turing-complete?

Is there a set of rules that translates any program into a configuration of finite pieces on an infinite board, such that if black and white plays only legal moves, the game ends in finite time iff ...