The arithmetic progression game and its variations: can you find optimal play? Consider the arithmetic progression game, a two-player game of
perfect information, in which the players take turns playing
natural numbers, or finite sets of natural numbers, all distinct,
and the first player wins if there is a sufficiently long
arithmetic progression amongst her numbers. This question grows out
of Haoran Chen's question, A game on the
integers, and my answer
there.
We have a natural parameterized family of such games, depending on
the number of integers each player is allowed to play on each move
and the desired length of the winning arithmetic progression.
Specifically, for positive-valued functions $f,g$ on the natural
numbers and natural number $n$, let $G(f,g,n)$ be the game in which


*

*Player A is allowed to play $f(i)$ many numbers on move $i$.

*Player B is allowed to play $g(i)$ many numbers on move $i$.

*Player A wins if she can form an arithmetic progression of length $n$ using her numbers.


All the integers played must be distinct.
Generalizing, let $G(f,g,\omega)$ be the game where player A aims
in infinite play to create an infinite arithmetic progression in
her set, and let $G(f,g,{<}\omega)$ be the game in which she wins
by creating a set with arbitrarily large finite arithmetic
progressions.
The original game at the other question was $G(1,k,5)$, with $k$
constant.
It is not difficult to see that all the games $G(f,g,n)$ are
determined, meaning that one of the players has a winning strategy.
After all, for finite $n$ the game $G(f,g,n)$ is an open game and
therefore determined; and the infinitary games $G(f,g,\omega)$ and
$G(f,g,<\omega)$ have winning conditions of complexity $\Sigma^0_2$
and $\Pi^0_2$, respectively, and all such games are determined
because they are very low in the Borel hierarchy.
In my answer at the other question, I had made several
observations.


*

*Player A wins the game $G(1,k,n)$, where player A plays one
number on each move and player B plays at most
a constant $k$ many numbers. The winning
strategy for A is simply to play the smallest available number,
which will ensure that set A has positive density, with proportion $1/(k+1)$ in any initial segment,
and all such sets with positive density contain
arbitrarily long arithmetic progressions by Szemerédi's
theorem.

*Thus, actually, player A wins $G(f,k,<\omega)$ for any $f$ and any
$k$, and all with the same strategy.

*A generalization of this argument adapts to show that if $g=O(f)$, then player A wins $G(f,g,n)$ and indeed $G(f,g,<\omega)$, since this hypothesis ensures that she can play a set with positive density, which will therefore have arbitrarily long finite arithmetic progressions.

*Meanwhile, a diagonal argument shows that player B wins $G(f,1,\omega)$ for any $f$, the game where
player A is aiming to produce an infinite arithmetic progression,
since player B can block the $n^{th}$ progression with a single number at step $n$.

*Thus, player B also wins $G(f,g,\omega)$ for any functions $f$ and $g$.

*Meanwhile, player B also wins $G(1,<\omega,3)$, since at each move player B
can play all the numbers up to double the largest current number.
This will prevent A from making three numbers in arithmetic
progression.

*Indeed, a more refined version of this argument shows that
player B wins $G(1,i-1,3)$, using the function $g(i)=i-1$, since at move
$i$, player A has added one new number, which creates $i-1$ pairs
with earlier numbers, and player B can block each of those pairs from
continuing to an arithmetic progression of length $3$ by playing
$i-1$ many blocking moves.
I have a number of questions.
Question 1. How quickly can player A win the game $G(1,k,n)$,
where $k$ is constant? Is the
always-play-the-smallest-available-number strategy in any sense
close to (or far from) optimal?
Question 2. Does the game $G(1,k,n)$ have finite game value?
That is, can we bound the length of play in advance, where the
bound depends only on $k$ and $n$ and not on the particular moves
of player B?
I presume the answer is yes, but note that not every open game has
a finite game value.
Question 3. For which functions $g$ does player A win
$G(1,g,n)$?
Above I argued that player A wins $G(1,g,3)$ for constant $g$, and
player B wins for $g(i)=i-1$. For $n=3$, that bound seems likely
close to optimal, since if player B ever fails to block a number,
then player A can win. But of course, perhaps some of the numbers
to be blocked had already been blocked at earlier stages of play.
So the answer seems to be somewhere between the constant functions
and the predecessor function.
Question 4. Can one show that every unbounded function $g$
enables player B to win $G(1,g,n)$ for some sufficiently large $n$?
Question 5. How much of the analysis carries over to the
corresponding geometric progression games? That is, the games
where player A aims to create geometric integer progressions.
I don't know if there is a geometric progression analogue of
Szemerédi's theorem, but meanwhile, some of the other arguments do
generalize.
 A: For $G(1,f,3)$, a more optimal strategy for A would be to choose the next available odd power of $2$, unless player A can complete a three term arithmetic progression on this turn.
The reason to choose odd powers of $2$ is that this prevents any "collisions" in the sense that on any round $n$ of the game the set of midpoints between two of A's choices has maximal size $\binom{n}{2}$, and the third elements of an arithmetic progression starting with two of A's choices has maximal size $\binom{n}{2}$. Furthermore, the odd power requirement ensures that these two sets don't overlap. 
[Details: If $2^x < 2^y$ are two of player A's choices, the two arithmetic progressions are $2^x,2^{x-1}+2^{y-1},2^y$ and $2^x,2^y,2^{y+1}-2^x$. In either case, it's easy to recover $x$ and $y$ from the third element, whether $2^{x-1}+2^{y-1}$ or $2^{y+1}-2^x$. The restriction to odd $x$ ensures that the binary representation of $2^{x-1}+2^{y-1}$ never has consecutive set bits. On the other hand, the set bits of the binary representation of $2^{y+1}-2^x$ are all contiguous.]
In order for B to win against this strategy, player B must cover all of these third elements at each round. This is only possible if $\sum_{i=1}^n f(i) \geq 2\binom{n}{2}$ for each $n$. Otherwise player A's power of $2$ strategy will necessarily win as soon as B's choices fail to cover all of A's $2\binom{n}{2}$ ways to complete a three element arithmetic progression. 
By skipping some odd powers of $2$ so that B cannot preemptively cover any of A's ways to finish a three term arithmetic progression, we see that A can win $G(1,f,3)$ unless $f(n) \geq 2n-2$ for every $n$.
This strategy doesn't require A to know anything about $f$. If A can additionally use information about $f$ then one can devise a winning strategy for A in $G(1,f,3)$ unless $f(n) \geq 3n-3$ for every $n$. The idea is to first choose an astronomical number $\omega$ and rather than playing odd powers of $2$, A chooses numbers of the form $\omega + 2^x$ where $x$ is odd. This way, because $\omega$ is very large, three term arithmetic progressions can also be completed below $\omega$ in addition to the two ways to complete them above $\omega$. Then there are the maximum $3\binom{n}{2}$ ways for player A to complete a three term at round $n$. Note that this requires that $\omega$ to be very large, but a suitable $\omega$ can be calculated using $f$ in such a way that $A$ wins on the first round where $f(n) < 3n-3$.
This is optimal. If $f(n)\geq 3n-3$ for every $n$, then B has a winning strategy by covering all of A's possible ways to complete a three term arithmetic progression at each step.

The games $G(r-2,f,r)$ admit a similar analysis. This time, player A's strategy is to pick sufficiently spread out powers of $(r-1)!$ shifted by an astronomical number $\omega$, unless player A can grab the remaining $r-2$ elements of an arithmetic progression containing two previous picks. 
Let's look at $r=4$ for a concrete example. Then all of A's picks are powers of $6$. Given two such numbers $\omega+6^i < \omega+6^j$ there are $6 = \binom{4}{2}$ ways to fit these numbers in a four term arithmetic progression: 


*

*$\omega+6^i,\omega+6^j,\omega+2\cdot6^j-6^i,\omega+3\cdot6^j-3\cdot6^i$

*$\omega+2\cdot6^i-6^j,\omega+6^i,\omega+6^j,\omega+2\cdot6^j-6^i$

*$\omega+3\cdot6^i-2\cdot6^j,\omega+2\cdot6^i-6^j,\omega+6^i,\omega+6^j$

*$\omega+6^i,\omega+6^i/2+6^j/2,\omega+6^j,\omega-6^i/2+3\cdot6^j/2$

*$\omega+3\cdot6^i/2-6^j/2,\omega+6^i,\omega+6^i/2+6^j/2,\omega+6^j$

*$\omega+6^i,\omega+2\cdot6^i/3+6^j/3,\omega+6^i/3+2\cdot6^j/3,\omega+6^j$


Excluding $\omega+6^i,\omega+6^j$, the union of these arithmetic progressions consists of the nine numbers $$F(i,j) = \left\{
\begin{split}
&\omega+3\cdot6^i-2\cdot6^j,\quad &
&\omega+2\cdot6^i-6^j,\quad &
&\omega+3\cdot6^i/2-6^j/2, \\
&\omega+2\cdot6^i/3+6^j/3,\quad&
&\omega+6^i/2+6^j/2,\quad&
&\omega+6^i/3+2\cdot6^j/3, \\
&\omega-6^i/2+3\cdot6^j/2,\quad&
&\omega+2\cdot6^j-6^i,\quad&
&\omega+3\cdot6^j-2\cdot6^i
\end{split}\right\}.$$ The "spread" requirements on picks by A should be that any two such sets are disjoint from each other, and disjoint from B's previous picks.
By inspection, in order to block all six arithmetic progressions containing $\omega+6^i$ and $\omega+6^j$, player B must pick at least four of the nine numbers from $F(i,j)$. This means that at round $n$, we must have $\sum_{i=1}^n f(i) \geq 4\binom{2n}{2}$. In fact, we must have $f(n) \geq 16n-12$ for every $n$ or else A's strategy will win at the first $n\geq1$ such that $f(n)<16n-12$.
Similar calculations for $r>4$ show that there is always a linear function $an+b$, where $a$ and $b$ depend on $r$, such that player A's strategy will win at the first $n$ such that $f(n)<an+b$, and player B has a winning strategy so long as $f(n) \geq an+b$ for all $n$.
A: The search term here is "Maker-Breaker arithmetic progression" or "Maker-Breaker van der Waerden".  Maker is trying to build arithmetic progressions and Breaker is trying to stop them, without caring about building arithmetic progressions themself.
For every $n \in \mathbb N$ and every $0 < \delta \leq 1$ there is a finite $N = N(n,\delta)$ such that every subset of $[N]$ of size $\delta N$ contains an arithmetic progression of length $n$.  Hence for question 2 the "take least unoccupied" strategy should be a win for Maker in at most $N(n,1/(k+1))$ steps.
Maker-Breaker games are often studied from the point of view of what bias (your $k$) allows Breaker to win.  In view of Szemerédi's theorem that means "when played on a finite interval", but the literature on that problem might shed some light on questions 3 and 4.
By factorising each integer, question 5 is equivalent to looking at arithmetic progressions in the direct sum of countably many copies of $\mathbb N$.  Only finitely many of the copies will be useful in an optimal (game length minimising) strategy for Maker.
