Guessing secrets (Q5925762)

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.