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:

- If you pick a $\pi$ uniformly at random, then any greedy algorithm will play expected $O(n^2)$ moves.
- 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.