# 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.

35 questions
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 ...
569 views

### Good text to start studying topological games?

Topological games and some similar infinite games seem to be often used used as a tool in some areas of general topology, but also some other areas, such as Ramsey theory, filters, etc. Probably the ...
677 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 ...
411 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 ...
217 views

### A two player game on compact topological spaces

I've though of an infinite game that two players may play on a given topological space $(X,\tau)$. It goes like this. On turn $n$ Player I selects a point $x_n\in X$ and Player II selects a ...
93 views

3k 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 ...
84 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 ...
121 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 ...
196 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 ...
88 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 ...
94 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 ...
300 views

94 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 ...
109 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 ...
98 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{...
64 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 ...
107 views

### The Connect Infinity game

Recently Joel David Hamkins posted an entry on the Connect Infinity game. Connect-$\omega$ is Connect Four but played on an $\omega\times n$ grid ($n$ finite)! The above shows $n=6$. The difference ...
45 views

### Mixed strategy equilibrium in Cournot Duopoly

This maybe a trivial question to most. I am fairly new to game theory. The usual cournot duopoly (same constant marginal cost for both players) is solved using pure strategies. Are there mixed ...
63 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) ...
156 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 ...
79 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 ...
91 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 ...
85 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. ...
34 views

### A question on gaming theory with variables [closed]

We have two stacks of coins, each with a and b coins respectively. On each step, the player is allowed to remove as many coins as they want(but at least one) from either of the two stacks he wants to (...
53 views

### Probability of winning a Craps game

A Craps game consists of throwing 2 dices. If the sum is either 7 or 11, you win. Else, if the sum is either 2,3 or 12, then you loose. If the sum is either 4, 5, 6, 8, 9 or 10, then let's call the ...
31 views

### Who has a winning strategy in Choquet game on rational numbers?

I know that in a real-numbers-variant of Choquet game, the player aiming for non-empty intersection has a winning strategy. Is the same true for rational numbers?
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 ...
### Explanation for Oxtoby's proof: a nonempty topological space $X$ is Baire iff player (I) has no winning strategy in the Choquet game
A nonempty topological space $X$ is a Baire space iff player I has no winning strategy in the Choquet game $G_X$. Oxtoby's proof I have several questions about this proof. $(\Leftarrow)$ How can ...
I'm having some trouble showing that the following zero-sum game with 2 players has a value (and in consequence, computing it's value). The strategies of both players are in $\mathbb{N}-\{0\}$ and ...