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
0
votes
1answer
45 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 ...
3
votes
1answer
84 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 ...
0
votes
1answer
17 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:...
3
votes
0answers
85 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 ...
1
vote
0answers
46 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 ...
1
vote
0answers
37 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 ...
0
votes
1answer
46 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^\...
2
votes
1answer
97 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 ...
0
votes
0answers
22 views

Example of a game with no forgetful winning strategy on the winning region

In the book "Automata, Logic and Infinite Games" there is the following exercise: Exercise 2.3. Give an example for a game $\mathcal{G}$ such that Player 0 wins forgetful on each $\{v\}$ ...
5
votes
3answers
125 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 ...
2
votes
0answers
80 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 ...
1
vote
1answer
55 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 ...
0
votes
1answer
31 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)&...
4
votes
1answer
154 views

Comparing the sizes of null sets

This question is about comparing the relative sizes of null sets by switching from open covers to open covering sequences (a la strong measure zero sets or microscopic sets). The main question is ...
1
vote
1answer
57 views

Banach-Mazur game and the Baire property

Given a topological space $\mathcal{X}=(X,\tau)$ and $A\subseteq X$, the Banach-Mazur game on of $A$, $G^{**}(A)$, is the game played as follows: Players $1$ and $2$ alternately play decreasing ...
4
votes
1answer
99 views

Determinacy and Choice

I know that Kechris proved $$\text{Con}(\text{ZF} + \text{AD})\Rightarrow \text{Con}(\text{ZF} + \text{AD} + \text{DC})$$ And that $\text{DC}$ and $\text{AC}_\omega$ are independent from $\text{AD}$, ...
0
votes
0answers
10 views

Conditions for optimal stationary strategies in MDPs

I have a specific markov decision process which is generated from a problem in another domain. What I would like to show is that under the limit of means criterion (no discounting) the optimal ...
3
votes
0answers
83 views

Borel hierarchy within Wadge hierarchy

I'm studying Wadge reducibility and the associated hierarchy (restricted to Borel sets) both from Kechris and more extensive papers. Now, in an exercise Kechris says: $[\emptyset]_W = \{\emptyset\}$...
1
vote
1answer
30 views

Number of solvable lights out puzzles on m x n rectangle

I'm trying to replicate the results on Dr. Brouwer website, I consulted two of the papers referenced [1] and [2] both of them make use of the same recursively defined polynomial and GCD. Let $p_n(x)$ ...
0
votes
0answers
43 views

Dice Game Involving an Increasing Pot

What is the average award of a dice game with the following rules: The pot starts at 0 at the beginning of every new game. The player begins with 3 CHANCES. A CHANCE is the rolling of both dice. ...
15
votes
1answer
301 views

Is there an undetermined Banach-Mazur game in ZF?

Given a topological space $\mathcal{X}=(X,\tau)$, the Banach-Mazur game on $\mathcal{X}$ is the (two-player, perfect information, length-$\omega$) game played as follows: Players $1$ and $2$ ...
0
votes
1answer
22 views

Probability problem in a game with equal turns

Two players play the following game with a machine: 1) Each player has 20 tickets. 2) Player One takes 1.23 Euro per ticket from the machine and also has 5% chance that the machine will return his ...
1
vote
1answer
105 views

Can the Average of an Infinite Number of Rational Numbers be Irrational? [closed]

In game theory, there is something called the Folk Theorem, which basically says that you can create a special strategy for any average of possible payoffs as long as the average payoffs are better ...
4
votes
1answer
96 views

Dice roll games - when is greedy/considering short-term gain optimal?

In this question, I refer to two separate games. The first is a game where you roll and accumulate your score until a six appears: You play a game using a standard six-sided die. You start with 0 ...
5
votes
0answers
88 views

One knight and one queen on an infinite chess-board (a simple game)

On an infinite chessboard, player A places the queen wherever they want. Then, player B places the knight wherever they want. Finally, the game starts. The main rule is that any square where player ...
7
votes
1answer
140 views

$6$ bishops and a knight on an infinite chessboard

Player $A$ places $6$ bishops wherever he/she wants on the chessboard with infinite number of rows and columns. Player $B$ places one knight wherever he/she wants. Then $A$ makes a move, then $B$, ...
4
votes
1answer
211 views

Covering game in Borel Determinacy proof

I was reading the introduction to the actual proof of Borel Determinacy in Kechris' "Classical Descriptive Set Theory". Here is an extract: What I don't get is why we define $\varphi$ in this way ...
16
votes
1answer
394 views

A simple game on infinite chessboard

Player $A$ chooses two queens and an arbitrary finite number of bishops on $\infty \times \infty$ chessboard and places them wherever he/she wants. Then player $B$ chooses one knight and places him ...
3
votes
1answer
111 views

Showing that Gale-Stewart Theorem on Determinacy of Open and Closed Games is equivalent to AC

I'm studying from Kechris' "Classical Descriptive Set Theory" and I'm trying to solve exercise 20.3, which asks to show that the Gale-Stewart theorem is equivalent to the axiom of choice AC in ZF. I'...
1
vote
1answer
74 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 ...
1
vote
0answers
59 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
33 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 ...
1
vote
2answers
150 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 ...
1
vote
1answer
237 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
75 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 ...
3
votes
1answer
38 views

Rothberger game and Meager set.

Someone know examples of topological spaces of first category and in which Player II has a winning strategy in the Rothberger game? Remember that: The Rothberger game on a topological space $X$ is ...
0
votes
1answer
170 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 he ...
0
votes
2answers
495 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
85 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
284 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
99 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
134 views

Proof that “$\uparrow$ is the unique solution of $\pmb{+}_G=G$”

Tiny & miny games can be defined as $$\pmb{+}_G = \{0||0|-G\}$$ $$\pmb{-}_G = -\pmb{+}_G = \{G|0||0\}$$ From the Wikipedia page for tiny and miny: Similarly curious, mathematician John Horton ...
3
votes
1answer
124 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
43 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
0answers
106 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
194 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
349 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
405 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 ...
3
votes
1answer
497 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
108 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]^{<\...