Can generalized twenty questions be solved by a greedy algorithm?

Question

The game of twenty questions can be generalized in the following way.

Let $\Omega$ be a finite set and $\mathcal Q$ a collection of subsets of $\Omega$, called the questions. A point $x\in\Omega$ is chosen unknown to the player, who then has the ability to iteratively choose a set $Q\in\mathcal Q$ and be told whether or not $x\in Q$. The player's goal is to determine $x$.

In order for the game to be solvable, $\mathcal Q$ is assumed to have the property that every $x\in\Omega$ can be realized as the intersection of some collection of elements of $\mathcal Q$ or their complements.

What we want is a strategy to solve this game with optimal worst-case running time.

At any point in the game, we can assign to each question a pair of integers - the number of possibilities that will remain depending on whether the answer is yes or no. Assign to each question a score which is the larger of these two integers, and always pick the question with minimal score. This is the "greedy" strategy.

Does the greedy strategy always have optimal worst-case running time?

Answer 1

No. There's a huge literature on the topic, called combinatorial search theory, you can read more about these types of questions there. The simplest example that I could think of is the following.

Suppose that you want to find an edge of a graph, and you can ask whether a given vertex is incident to the hidden edge, or not. Now take the following bipartite graph. It contains a perfect matching on $100+100$ vertices. Moreover, it also contains $10$ degree $10$ vertices that are connected to $10$ different vertices each, all on the same side. So one side of the graph has $100$ vertices, all degree $2$, the other $110$, of which $100$ have degree $1$, the other $10$ degree $10$.

In this case, the greedy algorithm would first query the degree $10$ vertices, and then the rest, taking about $110$ steps. If instead it started with querying the $100$ vertices of degree $2$, it would be done in $101$ steps.

Answer 2

Your question is not very different from set cover (it would be exactly set cover if you stopped as soon as you found a set containing $x$ rather than keeping going until you have determined $x$) and it's easy to adapt bad instances to set cover to show that the greedy algorithm can ask more questions than optimal by a logarithmic factor.

To see this, suppose that you have $n$ points in the plane, placed at the intersections of $k$ horizontal lines and a larger collection of vertical segments: $\lfloor k/3 \rfloor$ segments through triples of points on disjoint horizontal lines, $\lfloor k/4\rfloor$ segments through quadruples of points on, $\lfloor k/5\rfloor$ segments through five points, etc. Let $Q$ be the sets of points on each of these segments.

The greedy algorithm will begin by querying the vertical segments, in order from longest to shortest, because at each step this choice eliminates more points than taking any horizontal segment. Therefore, it uses a total of $(1-o(1))k\ln k$ tests in the worst case to find $x$. The optimal algorithm will take the horizontal segments first, taking $k$ steps to find a segment containing $x$ and at most $2k$ total to identify $x$. Since $n\approx k^2$, the factor $\tfrac{1}{2}\ln k$ by which greedy is bigger than optimal is $\Theta(\log n).$

(This is a standard counterexample for set cover. Its geometric realization, and the figure, are taken from my manuscript "Forbidden Configurations in Discrete Geometry". Probably you could get the inapproximability ratio up to $\ln n$ by using hard instances for set cover but I think the geometry of this example makes it easier to understand.)

On the other hand, suppose that the optimal strategy for your problem takes $k$ questions in the worst case, and consider the specific sequence of at most $k$ questions that this strategy would follow against a greedy adversary (one that always chooses the answer that leaves the most remaining elements). One of these questions must eliminate at least $n/k$ elements at the time it is asked by the optimal strategy, and would eliminate at least as many elements if it is asked immediately, as the first question. So, at each step, the greedy algorithm also eliminates at least $n'/k$ elements, where $n'$ is the number of remaining elements. Therefore, its total number of steps is $\bigl(1+o(1)\bigr)k\ln k$. That is, the $\ln k$ approximation ratio that one could presumably prove by using worst-case set cover instances in place of the geometric example above is tight.