Originator(s): F. Harary, B. Sagan, D[avid] West (presented by Yancey - REGS 2009)
Rules to the game: Fix a poset P and natural numbers a and d prior to play. In the game (P,a,b), Players A and B take turns selecting an element of P to append to a growing sequence of elements. The game ends when all of P has been selected or the sequence has a subsequence that is an ascending chain of length a or a descending chain of length d. In the "normal" form of the game, a player who ends the game by creating such a chain wins. In the "misere" form of the game, such a player loses. If neither player wins (and the poset is exhausted), then the game is a draw.
Background: The game was originally proposed in [HSW] for the special case where P is a finite chain; let n denote the chain with n elements. The general form was proposed in [AAAHHMS], with special attention to the case where P is the set of rationals under the usual ordering. The papers present computational results giving the outcome under optimal play for various fixed values of a and d and fixed P. They also prove the outcomes for some fixed d and P with arbitrary a.
Note that when P has a chain with more than (a-1)(d-1) elements, every play of the game has a winner. Except in very special cases, it seems that Player A generally wins the normal form of (P,a,d) when P has a sufficiently long chain.
Problem 1: Extend the computational results about which player wins (n,a,d) to larger values of a and d, perhaps by designing a more complex algorithm that encorporates theoretical results from [AAAHHMS].
Problem 2: Determine asymptotically in relation to a and d the smallest n such that (n,a,d) is not a draw.
Conjecture 3: When P is the usual linear order on the rational numbers and a,d>3, Player A has a winning strategy.
Problem 4: Find the answers to analogous questions on more general posets, such as products of finite chains.
Comment: Another version of monotone sequence games on such posets was suggested in REGS 2008.
References:
[HSW] Frank Harary, Bruce Sagan, and David West,
Computer-aided analysis of monotonic sequence games,
Atti Accad. Peloritana Pericolanti Cl. Sci. Fis. Mat. Natur., 61 (1983), 67-78.
[AAAHHMS] Michael Albert, Robert Aldred, Mike Atkinson, Chris Handley,
Derek Holton, Dennis McCaughan, and Bruce Sagan;
Monotonic Sequence Games, Games of No Chance 3 (2009), 309-327; preprint
on Sagan's website at http://www.mth.msu.edu/~sagan/Papers/Old/list.html .