Stack Exchange Network

Stack Exchange network consists of 175 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
56 views

Three-player duel of complete information. Optimal strategy and Nash equilibrium

I have a three-player duel in which players A,B and C pick a time t in the interval [0,1] to fire at a common target and they can only fire once. When player A fires at time t, he will hit with ...
0
votes
1answer
57 views

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 ...
0
votes
0answers
23 views

Product of Paracompact spaces being Paracompact

I'm interested in the game-characterization proposed by Telgarsky (paper) of the class of paracompact spaces that preserve paracompactness under cartesian product with another paracompact space. He ...
0
votes
1answer
26 views

Play Cards Game Tournament Algorithm

I am currently trying to find algorithm to minimize the total time of a tournament. The game requires $2$ teams of $2$ players in each team (total $4$ players). Then, the perfect number of ...
18
votes
1answer
577 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 ...
1
vote
2answers
113 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 ...
7
votes
1answer
96 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 $\{ \...
1
vote
1answer
58 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 ...
2
votes
1answer
58 views

Compact complement topology and Rothberger game.

On $(\mathbb{R}, \tau)$ the euclidean space of real numbers, we define a new topology by letting $\tau^{*}=\{X\subseteq \mathbb{R}: X=\emptyset \hspace{0.1cm}\mbox{or}\hspace{0.1cm}\mathbb{R}\setminus ...
0
votes
1answer
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 (...
0
votes
0answers
29 views

Value of an infinite game

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 ...
0
votes
2answers
75 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 ...
0
votes
1answer
35 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?
7
votes
2answers
236 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 ...
1
vote
1answer
64 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
96 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
65 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 ...
4
votes
1answer
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 ...
4
votes
1answer
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 ...
0
votes
1answer
86 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. ...
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 ...
2
votes
1answer
424 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 ...
11
votes
1answer
413 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 ...
4
votes
1answer
122 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
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 ...
5
votes
0answers
95 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]^{<\...
3
votes
1answer
309 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\...
1
vote
0answers
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 ...
1
vote
1answer
161 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 ...
2
votes
1answer
112 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 ...
4
votes
0answers
96 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 ...
3
votes
0answers
389 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 ...
1
vote
1answer
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 ...
2
votes
1answer
103 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{...
17
votes
0answers
683 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 ...
20
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 ...
4
votes
2answers
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 ...
5
votes
1answer
978 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. ...