8
$\begingroup$

Given $n$. Two players in turn write different real numbers $x_1,x_2,x_3,\dots$ The player after whose turn there is a monotone subsequence of length $n$ loses. I guess that the question 'who wins' may be hopeless (nice if not so), but possibly there exists a better estimate of the number of turns than Erdős–Szekeres bound $(n-1)^2+1$ (which works not only for optimal, but for all strategies)?

$\endgroup$
  • $\begingroup$ For $n=3$, it is a first player win in four steps instead of five, so it is already better than Erdős-Szekeres. WLOG we can assume that the first palyer plays $1$, and the second player plays $3$. then the first player plays $2$ and wins. I am not sure what is the exact question. You would like a better bound than the Erdős-Szekeres, for all $n$ for optimal players? $\endgroup$ – Daniel Soltész Mar 9 '15 at 15:59
  • $\begingroup$ In a sense this is also a similar question: mathoverflow.net/questions/143547/a-ramsey-avoidance-game As there is a game, and a Ramsey-type result, that guarantees that the game ends in a finite number of steps, but it turned out that the game with optimal play "ends earlier". $\endgroup$ – Daniel Soltész Mar 9 '15 at 16:11
  • 1
    $\begingroup$ Well, let the exact question be "does number of turns grow as $\Omega(n^2)$ for large $n$"? $\endgroup$ – Fedor Petrov Mar 9 '15 at 16:17
  • 1
    $\begingroup$ You may be interested in Harary, Sagan, and West, Computer-aided analysis of monotonic sequence games, Atti Accad. Peloritana Pericoanti Cl. Sci. Fis. Mat. Natur. 61 (1983) 67-78, MR1006269 (90d:90100). $\endgroup$ – Gerry Myerson Mar 9 '15 at 22:43
  • 1
    $\begingroup$ @GerryMyerson wow, they claim that in this game the first player wins for any $n\geq 4$ by some clever reason! researchgate.net/publication/2126205_Monotonic_Sequence_Games (Theorem 10) $\endgroup$ – Fedor Petrov Mar 9 '15 at 23:32
8
$\begingroup$

As noted in the comments (but with not quite the right reference) the game is a first player win for $n \geq 4$. The question here is about the misere form, so this is a combination of Proposition 7, Theorem 10 and a bit of Proposition 9 in the paper Monotonic Sequence Games by Albert (who he?), Aldred, Atkinson, Handley, Holton, McCaughan and Sagan. This also appeared in Games of no chance 3. We did not address the question of the length of the game when one player is playing using a winning strategy, and the other to lose as slowly as possible (obviously, if the players cooperate to lengthen the game then it reaches the Erdos-Szekeres bound). The proof uses a "strategy stealing" argument, but one which is not entirely clear cut. In common with most such arguments it does not actually yield a strategy for the first player to win, only a proof that such a strategy exists.

$\endgroup$
  • $\begingroup$ Thank you, this stealing argument is amazing. Have you try similar tricks for other Ramsey type games, like, say, forbidden convex $n$-gon on the plane? $\endgroup$ – Fedor Petrov Mar 10 '15 at 17:40
  • $\begingroup$ No, we didn't really consider such games. As the heart of the argument is a symbolic representation of a game state based on encoding the "bumping" algorithms for finding longest increasing and decreasing subsequences, it's not clear to me how one would emulate it. Of course the general idea of looking for a strategy stealing argument would certainly be a line to pursue. $\endgroup$ – Michael Albert Mar 10 '15 at 18:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.