2026-07-25T03:14:34Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15990 2024-03-06T10:57:01Z ddc:004 open_access

Mirror Games Against an Open Book Player Magen, Roey Naor, Moni Mirror Games Space Complexity Eventown-Oddtown 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}}. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Roey Magen and Moni Naor 2022 Is Part Of LIPIcs, Volume 226, 11th International Conference on Fun with Algorithms (FUN 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FUN.2022.20 urn:nbn:de:0030-drops-159900 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.20 eng https://creativecommons.org/licenses/by/4.0/legalcode