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
0answers
33 views

Mixed strategies as best responses in continuous games

I understand that in any finite two-person game, if I's mixed strategy $\sigma$ is a best response to one of II's (pure or mixed) strategies, then any pure strategy that is in the support of $\sigma$ ...
0
votes
3answers
37 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 ...
1
vote
0answers
12 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 ...
2
votes
1answer
73 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 ...
1
vote
0answers
44 views

In terms of binary games, what is meant by a "$\Sigma_2 ^{0}$ game"?

I am reading some articles on Determinacy and winning strategies in binary games, and there seems to be several notions of a "$\Sigma_{m}^{n}$ game." The ones I'm looking at in particular ...
0
votes
1answer
36 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 ...
2
votes
0answers
38 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 ...
3
votes
0answers
57 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 ...
2
votes
1answer
62 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 ...
1
vote
0answers
32 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 ...
3
votes
1answer
64 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 ...
2
votes
0answers
32 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', ...
0
votes
1answer
50 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 ...
0
votes
0answers
37 views

What is the most accurate scoring system between 2 players?

Considering each player has 3 attempts to score, which of the following methodologies is the most accurate to determine a players score: Highest Score of 3: 123, 456, 789 Total Score of 3: = 123, 456, ...
0
votes
1answer
61 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
102 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
22 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
1answer
94 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 ...
2
votes
0answers
53 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
51 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
76 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
108 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 ...
6
votes
4answers
207 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
354 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
61 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
71 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
159 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
99 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
123 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}$, ...
3
votes
0answers
92 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
48 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)$ ...
15
votes
1answer
324 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
23 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
216 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 ...
3
votes
1answer
155 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
103 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
166 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
228 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 ...
17
votes
1answer
415 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
173 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
98 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 ...
2
votes
0answers
88 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
38 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
198 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
485 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
81 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
42 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
254 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
1k 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
126 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?