Finite, attained general adversary value for nonconstant Boolean functions

Let x,y have opposite outputs. Then x≠y, so there is i with x_i≠y_i. The symmetric matrix with entries 1 at (x,y),(y,x) and zero elsewhere is an admissible nonzero Γ; at least one Γ∘Δ_i has norm 1, while all have norm at most 1. Thus every nonconstant f has a positive-denominator admissible matrix.

If Γ is admissible and nonzero, some Γ_xy≠0. By Γ∘F=0 its endpoints have opposite outputs, hence differ at some coordinate i. Then |Γ_xy|=|(Γ∘Δ_i)_{xy}|≤||Γ∘Δ_i||, so max_i||Γ∘Δ_i||>0. The same argument shows that the normalization max_i||Γ∘Δ_i||≤1 forces every entry |Γ_xy|≤1.

The normalized set of real symmetric Γ with Γ∘F=0 and max_i||Γ∘Δ_i||≤1 is closed and bounded in the finite-dimensional matrix space, hence compact by [F4]. It is nonempty by step 1.1. The norm is continuous since $\mathrm{\mid }\mathrm{\parallel }\mathrm{\Gamma }\mathrm{\parallel }-\mathrm{\parallel }{\mathrm{\Gamma }}^{\mathrm{\prime }}\mathrm{\parallel }\mathrm{\mid }\le \mathrm{\parallel }\mathrm{\Gamma }-{\mathrm{\Gamma }}^{\mathrm{\prime }}\mathrm{\parallel }\le \mathrm{\parallel }\mathrm{\Gamma }-{\mathrm{\Gamma }}^{\mathrm{\prime }}{\mathrm{\parallel }}_F$, so [F5] gives a finite attained maximum; by homogeneity this maximum is exactly the ratio supremum in the definition.