The main post shows Adaptive Coverage Greedy (ACG) tracking the exact optimal value \(V^{*}(s_0)\) closely, while a plain greedy-by-degree rule falls further behind as \(p\) drops. That raises a fair question: why isn't "activate whichever queen currently threatens the most others" already optimal? Degree feels like the right signal to chase. Proposition 18 answers this with the smallest instance that breaks greedy: four queens, one blocked pair, and a tie in degree that greedy has no way to resolve correctly.
Place four queens at \(A=(1,1)\), \(B=(1,2)\), \(C=(3,2)\), \(D=(4,2)\). The attack graph is a path \(A - B - C - D\): three unblocked conflicts, \(\kappa(s_0) = 3\). There's a fourth pair sharing a line, \(B\) and \(D\), but \(C\) sits directly between them, so that pair is blocked for as long as \(C\) survives. Counting only unblocked kill-neighbors, \(B\) and \(C\) both have degree 2, the maximum on the board; \(A\) and \(D\) each have degree 1. Greedy-by-degree has to choose between \(B\) and \(C\), and on degree alone there's nothing to choose between them.
There should be, though. Activating \(C\) achieves the true optimum, \(V^{*}(s_0) = 3/p\). Activating \(B\) instead — an equally defensible tie-break under greedy-by-degree — commits you to \(V^{\pi_G}(s_0) = \dfrac{7-3p}{p(2-p)}\), strictly worse for every \(p \in (0,1)\), even granting optimal play from that point on. Two choices, identical under the only signal greedy consults, and one of them is a permanent mistake.
The panel below plays out both choices side by side. Drag \(p\); every number on it — the four activation costs, the branch probabilities, both running totals — is live.
Why the tie breaks the wrong way
Follow what happens after each activation. \(B\)'s two kill-neighbors are \(A\) and \(C\); \(C\)'s are \(B\) and \(D\). If \(C\) activates and kills both neighbors, the board is left with only \(A\) and \(C\) — which don't attack each other — so it clears completely, \(\kappa = 0\), done. If \(B\) activates and kills both of its neighbors instead, the board is left with \(B\) and \(D\)... and the \(B\)-\(D\) line is no longer blocked, because the queen that was blocking it, \(C\), is one of the two that just died. Even \(B\)'s best possible roll leaves one conflict standing, resurrected from a pair that used to be safely screened off.
Degree, as greedy computes it, only counts how many queens you can hit on the board right now. It has no way to see that removing \(C\) doesn't just delete two edges — it also switches a third one back on. \(C\) doesn't have this problem: nothing \(C\) can kill was ever screening off some other pair. That asymmetry, invisible to a single number, is the entire counterexample.
What to look for
- Drag \(p\) across the whole range. \(C\) stays strictly ahead of \(B\) throughout — the gap narrows as \(p \to 1\), since both policies converge toward resolving everything in one round, but it never closes.
- Compare \(B\) to \(A\) and \(D\): despite tying \(C\) on degree, activating \(B\) still beats both degree-1 options across the slider's whole range. The greedy mistake here is subtle, not catastrophic — it loses only to the one queen it couldn't distinguish itself from.
- Watch the note under \(B\)'s first row. Even the best possible outcome for \(B\) — both neighbors die — is exactly the outcome that reopens \(B\)-\(D\). There's no version of activating \(B\) that clears the board the way activating \(C\) can.
This board is small on purpose — Proposition 18 only needs the smallest instance that breaks greedy, not a realistic one. But the failure mode it exposes isn't small: any time removing one queen unblocks a line between two others, a rule that only ever looks at current degree has no way to see it coming. That's the gap the main post's Adaptive Coverage Greedy is built to close.