What is the minimum worst-case length of an element removal game?

Question

A game is played as follows. There is a set $X = \{1, \ldots, n\}$. Player 1 is trying to find a "locally minimal subset" $M \subseteq X$ - that is, player 2 has said that $M$ is good, and also that every subset $M - \{x\}$ for $x \in M$ is bad.

Formally, play proceeds as follows: A move from player $1$ is any subset $S \subseteq X$ that is has not previously played. Its first move is always to play $X$.

Player 2 then moves by providing an answer $A_S \in \{0, 1\}$. $A_X = 1$ but may otherwise be chosen arbitrarily.

Play alternates between players one and two, terminating when there is some set $M$ such that player 1 has played all of $M$ and $M - \{x\}$ for all $x \in M$, and in response player 2 has played $A_M = 1$ and $A_{M - \{x\}} = 0$.

Player 1 is trying to finish in as few moves as possible. Clearly it can terminate play (just enumerate every subset in size-increasing order until player 2 says yes - the first such value will be a suitable $M$).

A naive greedy algorithm gives player 1 a winning strategy in $O(n^2)$ moves: At each stage, try removing one element at a time from your current best answer. If player 2 says yes, use that as your new current best answer. If it says no for all subsets with an element removed, the game is over.

Given any such greedy strategy that tries removing only one element at a time, player 2 can clearly force player 1 to play $O(n^2)$ moves by always saying yes to the last subset tried of the current set.

Is it true that any strategy for player 1 can similarly be forced to play $O(n^2)$ moves to win?

I conjecture (and am pretty confident in this conjecture) that it is, but the details keep escaping me. Essentially the idea should be to just force the algorithm to decay to the greedy case by blocking off all attempts, but I keep getting lost in the details - for example, you can't do it naively because player 2 could have already blocked off some paths with its previous moves.

Some Things I've Tried

(Updated to elaborate on what doesn't and might work)

The strategy that blocks the greedy algorithm from completing in fewer than $O(n^2)$ steps is to simply return $A_S = 0$ whenever $|S| \leq 1$ or when $S$ is not the last set of size $|S|$ that is a subset of the current smallest good set. This does not work for non-greedy algorithms because you can play the following moves:

• $X - \{i\}$ for $i \in \{1, \ldots, n - 2\}$
• $X - \{n - 1, i\}$ for $i \in \{1, \ldots, n - 2\}$
• $X - \{n\}$
• $X - \{n - 1\}$

When player 1 plays the greedy-blocking strategy and player 2 plays as above, the set $X - \{n - 1\}$ is a suitable minimal set.

I believe something like the following might work:

Let $\pi$ be a permutation of $X$. The $\pi$ strategy for player 1 is that $A_S = 1$ if and only if $|S| > 1$ and $S = \{\pi_1, \ldots, \pi_{|S|}\}$.

When player 1 plays the $\pi$ strategy the final answer must be $\{\pi_{n - 1}, \pi_n\}$.

I believe the following strategy works for player 1: Maintain a set of permutations $P$. Initially $P$ is the set of all permutations. Whenever player 2 plays $S$, if the $A_S = 1$ if and only if it would be $1$ when playing any $\pi \in P$. Otherwise $A_S = 0$ and we update $P$ to remove all $\pi$ which would not give that answer.

The thing I haven't been able to prove is that player 1 can continue this strategy for long enough. Intuitively the argument that it should be is as follows:

1. If you pick a $\pi$ uniformly at random, then any greedy algorithm will play expected $O(n^2)$ moves.
2. Any attempt to reduce the size by more than one step at a time succeeds with very low probability. In particular if you have $U_1, \ldots, U_{k}$ with $k < \frac{n(n - 1)}{2}$ and $|U_i| < n - 1$ then the expected number of $U_i$ with $A_{U_i} = 1$ for the randomly chosen $\pi$ is $< 1$ and in particular the probability that none of them succeed is $> 0$. This suggests that the non-greedy algorithm is dominated for this permutation by some "greedy core".

But at this point I'm handwaving wildly and again haven't been able to make the details of this intuition work out.

Answer 1

I think that there's a simple adversary strategy:

Answer 0 unless it would block all paths from $X$ to the second level from below, i.e., to the $2$-element sets. (So for $\le 1$ element sets we always answer 0.)

Such a game can end only by receiving a 1 answer on the second level for some $(a,b)$. But since this secures the path from $X$ to the second level, there is a path from $X$ to $(a,b)$. Without loss of generality, we can suppose that $a=1$, $b=1$ and the elements of the path are $(1,\ldots, i)$. Since $(1,2)$ was the last chance to reach the second level, every other path from each of $(1,\ldots, i)$ to the second level must be blocked. For $(1,\ldots, n)$, there are $n-1$ disjoint paths that end, respectively, in $(j,n)$; we need at least $n-1$ zeros to block these and they cannot block any other path from an $(1,\ldots, i)$ to the second level. Similarly, we need further $n-2$ zeros to block the paths from $(1,\ldots, n-1)$ to the second level etc, in total $n^2/2+\Theta(n)$, which matches the trivial upper bound. (Possibly with a little more care even the exact value can be determined.)