A randomized strategy in the mirror game
share
Alice and Bob take turns (with Alice playing first) in declaring numbers from the set [1,2N]. If a player declares a number that was previously declared, that player looses and the other player wins. If all numbers are declared without repetition, the outcome is a tie. If both players have unbounded memory and play optimally, then the game will be tied. Garg and Schneider [ITCS 2019] showed that if Alice has unbounded memory, then Bob can secure a tie with N memory, whereas if Bob has unbounded memory, then Alice needs memory linear in N in order to secure a tie. Garg and Schneider also considered an auxiliary matching model in which Alice gets as an additional input a random matching M over the numbers [1,2N], and storing this input does not count towards the memory used by Alice. They showed that is this model there is a strategy for Alice that ties with probability at least 1 - 1/N, and uses only O(√(N) ( N)^2) memory. We show how to modify Alice's strategy so that it uses only O(( N)^3) space.
READ FULL TEXT