1
$\begingroup$

Consider the following game: You are given a set $S$ and a fixed list $q_1$, $q_2$, ..., $q_n$ of yes or no questions about the elements of $S$. Your opponent chooses an element of $S$ without telling you which. You then ask a series of questions taken from the list and your opponent truthfully answers "yes" or "no" to each. Your choice of each question can depend on the answer to the previously asked question. Your goal is to deduce the secret element of $S$ your opponent has chosen in as few questions as possible.

For example, $S$ might be $\\{\text{banana}, \text{orange}, \text{football}, \text{basketball}\\}$ and the list of questions might be "Is it a fruit?", "Is it spherical?", "Is it an animal?". In this case you could deduce the secret by asking just the first two.

This is a simple enough problem that I suspect a lot has been said about it in the computer science literature. I'm beginner enough that I don't even know what keywords to search to read more. So here are some questions:

  1. Does this problem go by a certain name? Or is easily it reducible to some other well-known named problem?

  2. Are there results about the number of queries necessary in various cases, say where the questions take a certain form? (For example, binary search is a special case of this problem where the allowed questions are of the form, "Is the index of the sought after value less than $i$?" The result there would be that the worst case takes $\log(|S|)$ queries.)

  3. I'm also interested in the variant of the problem where you have a set number of queries and the goal is to maximize the probability of guessing the secret after using up these queries. E.g. in the example above, with just one query you can narrow down the secret to two possibilities, giving you a 50% chance of guessing the right answer (assuming the secret is chosen uniformly at random). With two queries you can narrow it down entirely, so your probability of success is 100%.

$\endgroup$
1
  • 1
    $\begingroup$ The trick is to ask questions that cut the possibilities into as close to half as possible. That way, no matter the answer, you'll eliminate half the possibilities each time. ¶ For instance, "Is is spherical?" would be a poor first question, as the division would be 1 and 3, and you might need to ask 2 more questions to get the final answer. $\endgroup$ Commented Nov 17, 2022 at 3:57

1 Answer 1

3
$\begingroup$

This is the problem of building a decision tree of minimal depth. Each question is a feature that you can branch on in a node of the tree. The tree structure captures the adaptive nature of the queries.

See ID3 for one heuristic algorithm, and decision tree learning for the general area.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.