Guessing secrets
The authors consider a new game of two players stemming from a recent connection with certain Internet traffic routing applications. The game is played by two players, ``Seeker and ``Adversary, with the Adversary choosing an arbitrary \(k\)-element subset \(X\) of an \(n\)-element set \(\Omega\), and the Seeker trying to determine the secret set by a series of questions answered by the Adversary. Each of the Seeker's questions is a subset \(S\) of \( \Omega \) to which the Adversary is obliged to respond by either ``yes or ``no depending on whether \( S \) does or does not contain a vertex \(x\) of the secret set \(X\), where the vertex \(x\) is upto the Adversary to choose, may change after each question, and is not revealed to the Seeker. The goal of the game for the Seeker is to determine all the elements of \(X\), and the Adversary (while potentially trying to protect the secret set) must respond truthfully. Due to the restricted amount of information obtained, the Seeker may never be able to determine \(X\) fully. The authors define the concept of an intersecting set -- the set that contains as much information on the elements of \(X\) as possible -- and investigate the complexity of Seeker's strategies aimed at obtaining an intersecting set. The complexity of a strategy is defined to be the maximal number of questions necessary to determine an intersecting set with respect to all possible sequences of answers of the Adversary (i.e., the depth of the binary tree of the strategy). Two kinds of strategies are considered. In the adaptive strategy, the Seeker is allowed to take into account all of the information obtained and adjust the questions accordingly. The oblivious strategy is a series of questions provided to the Adversary all at once. Most of the results involve the smallest interesting case for the size of \(X\), namely the case when the secret is a two-element set. Denoting by \(f(n)\) the shortest length of an adaptive strategy bound to determine an intersecting set for a game with \(\Omega\) of size \(n\) and the secret \(X\) of size \(2\), the authors show that \(3\log_2 n - 5 \leq f(n) \leq 4 \log_2(n) + 3\), with the lower bound obtained by a simple counting argument, and the upper bound being the length of a specific strategy. Denoting the length of the shortest oblivious algorithm for a game with the same parameters by \( f_0(n) \), we learn that \(f_0(n) \leq (c +o(1))\log_2 n\), where \(c = 3/\log_2(8/7) \). Further algorithms with a restricted size of a question, as well as algorithms for the case \(|X|= k > 2\), are considered; with the results much more limited for the latter. The article also contains several connections to other problems in combinatorics and great many unanswered interesting questions.
- Finding hidden independent sets in interval graphs
- European tenure games
- Continuous guessing games with two secret numbers
- Guessing secrets. (Extended abstract)
- Efficient online algorithmic strategies for several two-player games with different or identical player roles
- Finding hidden independent sets in interval graphs
- A variant of the guessing secrets game
- Threshold Group Testing
- Guessing Secrets with Inner Product Questions
- scientific article; zbMATH DE number 2119668 (Why is no real title available?)
- Threshold and Majority Group Testing
- Guessing Secrecy
- Guessing Games
- Guessing More Secrets via List Decoding
- Separating codes and a new combinatorial search model
- The VC dimension of quadratic residues in finite fields
- Two cooperative versions of the guessing secrets problem
This page was built for publication: Guessing secrets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5925762)
