Nonnegative-weight adversary bound

For nonconstant $f$, choose $x,y\in D$ with $f(x)\mathrm{\ne }f(y)$ and put ${\mathrm{\Gamma }}_{xy}={\mathrm{\Gamma }}_{yx}=1$, with all other entries zero. This is a nonnegative admissible matrix; the inputs differ in some coordinate, so its mismatch denominator is exactly one. Hence the nonnegative feasible set contains a nonzero witness. Restrict the admissible matrices of [F1] to entrywise nonnegative matrices and use the same mismatch denominator; define their maximum ratio to be Adv(f), with value zero for constant f.

Let $K_{+}$ be the set of real symmetric matrices with $\mathrm{\Gamma }\circ F=0$, $\mathrm{\Gamma }\ge 0$, and $d(\mathrm{\Gamma }):={\max }_i\mathrm{\parallel }\mathrm{\Gamma }\circ {\mathrm{\Delta }}_i\mathrm{\parallel }\le 1$. It is closed because its linear and entrywise inequalities are closed and each filtered norm is continuous; the norm continuity follows from $\mathrm{\mid }\mathrm{\parallel }A\mathrm{\parallel }-\mathrm{\parallel }B\mathrm{\parallel }\mathrm{\mid }\le \mathrm{\parallel }A-B\mathrm{\parallel }$. If $\mathrm{\Gamma }\in K_{+}$ has a nonzero entry ${\mathrm{\Gamma }}_{xy}$, then $f(x)\mathrm{\ne }f(y)$ and some coordinate i differs, so $\mathrm{\mid }{\mathrm{\Gamma }}_{xy}\mathrm{\mid }=\mathrm{\mid }(\mathrm{\Gamma }\circ {\mathrm{\Delta }}_i{)}_{xy}\mathrm{\mid }\le \mathrm{\parallel }\mathrm{\Gamma }\circ {\mathrm{\Delta }}_i\mathrm{\parallel }\le 1$ by the operator-norm entry bound in [F2,F3]. Hence $K_{+}$ is bounded, and [F4] makes it compact. It is nonempty by step 1.1, so [F5] gives a finite maximum of the continuous norm on $K_{+}$. Every nonzero admissible matrix has positive denominator by [F2]; scaling identifies this normalized maximum with the ratio supremum, and a nonzero norm maximizer must have $d(\mathrm{\Gamma })=1$ because otherwise it could be scaled up in $K_{+}$. Thus the nonnegative maximum is finite and attained with the same normalization as Adv±.