Mirror games against an open book player
From MaRDI portal
(Redirected from Publication:6077070)
Mirror games against an open book player (scientific article; zbMATH DE number 7751503)
Mirror games against an open book player (scientific article; zbMATH DE number 7751503)
Abstract: 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 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}.
Cites work
- A Framework for Adversarially Robust Streaming Algorithms
- A new approach to fair distribution of welfare
- Fault-tolerant Computation in the Full Information Model
- scientific article; zbMATH DE number 7489400 (Why is no real title available?)
- On complexity as bounded rationality (extended abstract)
- Separating adaptive streaming from oblivious streaming using the bounded storage model
- The space complexity of mirror games
This page was built for publication: Mirror games against an open book player
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6077070)
