论文标题
镜子游戏与开放式书籍玩家
Mirror Games Against an Open Book Player
论文作者
论文摘要
镜像游戏是由Garg and Schnieder发明的（ITCS 2019）。爱丽丝（Alice）和鲍勃（Bob）在{1,2，... 2n}的声明数字中轮流（爱丽丝（Alice）首次演奏）。如果玩家选择了以前玩过的数字，那个球员就输了，另一个球员获胜。如果所有数字都没有重复声明，则结果是抽奖。鲍勃（Bob）有一个简单的镜子策略，可以确保他不会失去，并且不需要任何记忆。另一方面，Garg和Schenier表明，每个确定性的爱丽丝都需要在$ n $中对尺寸线性的记忆，以确保平局。 关于概率策略，以前的工作表明，爱丽丝可以访问{1,2，... 2n}的秘密随机完美匹配的模型使她能够在游戏W.P.中获得平局。至少1-1/n，仅使用一个记忆的多个位置。 我们表明，对秘密碎屑的要求至关重要：对于一本“开放书”的爱丽丝，没有秘密（鲍勃都知道她的记忆，但对未来的硬币翻转）和对任何C> 2的N/4C位最多都记忆，鲍勃赢得了W.P. W.P.接近1-2^{ - C/2}。
Mirror games were invented by Garg and Schnieder (ITCS 2019). Alice and Bob take turns (with Alice playing first) in declaring numbers from the set {1,2, ...2n}. If a player picks a number that was previously played, that player loses and the other player wins. If all numbers are declared without repetition, the result is a draw. Bob has a simple mirror strategy that assures he won't lose and requires no memory. On the other hand, Garg and Schenier showed that every deterministic Alice needs memory of size linear in $n$ in order to secure a draw. Regarding probabilistic strategies, previous work showed that a model where Alice has access to a secret random perfect matching over {1,2, ...2n} allows her to achieve a draw in the game w.p. a least 1-1/n and using only polylog bits of memory. We show that the requirement for secret bits is crucial: for an `open book' Alice with no secrets (Bob knows her memory but not future coin flips) and memory of at most n/4c bits for any c>2, there is a Bob that wins w.p. close to 1-2^{-c/2}.
