License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2022.107
URN: urn:nbn:de:0030-drops-157039
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/15703/
Menuhin, Boaz ;
Naor, Moni
Keep That Card in Mind: Card Guessing with Limited Memory
Abstract
A card guessing game is played between two players, Guesser and Dealer. At the beginning of the game, the Dealer holds a deck of n cards (labeled 1, ..., n). For n turns, the Dealer draws a card from the deck, the Guesser guesses which card was drawn, and then the card is discarded from the deck. The Guesser receives a point for each correctly guessed card.
With perfect memory, a Guesser can keep track of all cards that were played so far and pick at random a card that has not appeared so far, yielding in expectation ln n correct guesses, regardless of how the Dealer arranges the deck. With no memory, the best a Guesser can do will result in a single guess in expectation.
We consider the case of a memory bounded Guesser that has m < n memory bits. We show that the performance of such a memory bounded Guesser depends much on the behavior of the Dealer. In more detail, we show that there is a gap between the static case, where the Dealer draws cards from a properly shuffled deck or a prearranged one, and the adaptive case, where the Dealer draws cards thoughtfully, in an adversarial manner. Specifically:
1) We show a Guesser with O(log² n) memory bits that scores a near optimal result against any static Dealer.
2) We show that no Guesser with m bits of memory can score better than O(√m) correct guesses against a random Dealer, thus, no Guesser can score better than min {√m, ln n}, i.e., the above Guesser is optimal.
3) We show an efficient adaptive Dealer against which no Guesser with m memory bits can make more than ln m + 2 ln log n + O(1) correct guesses in expectation.
These results are (almost) tight, and we prove them using compression arguments that harness the guessing strategy for encoding.
BibTeX - Entry
@InProceedings{menuhin_et_al:LIPIcs.ITCS.2022.107,
author = {Menuhin, Boaz and Naor, Moni},
title = {{Keep That Card in Mind: Card Guessing with Limited Memory}},
booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
pages = {107:1--107:28},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-217-4},
ISSN = {1868-8969},
year = {2022},
volume = {215},
editor = {Braverman, Mark},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/15703},
URN = {urn:nbn:de:0030-drops-157039},
doi = {10.4230/LIPIcs.ITCS.2022.107},
annote = {Keywords: Adaptivity vs Non-adaptivity, Adversarial Robustness, Card Guessing, Compression Argument, Information Theory, Streaming Algorithms, Two Player Game}
}
|
Keywords: |
|
Adaptivity vs Non-adaptivity, Adversarial Robustness, Card Guessing, Compression Argument, Information Theory, Streaming Algorithms, Two Player Game |
|
Collection: |
|
13th Innovations in Theoretical Computer Science Conference (ITCS 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
25.01.2022 |
