Theorem 4 — under constraint uncertainty, 𝒫_K can be strictly worse than 𝒫 for every K < |𝒴|

Theorem 4. The K-adaptability problem $\mathcal P_K$ may attain a strictly higher optimal value than the two-stage robust binary program $\mathcal P$ for any number of policies $K<|\mathcal Y|$.

Precisely: for every $Q\in\mathbb N$, let (EC.4) be the instance of $\mathcal P$ with no first-stage decision, second-stage feasible set $\mathcal Y=\{0,1\}^Q$ (so $|\mathcal Y|=2^Q$), zero objective, second-stage constraints $y_q-\xi_q\le\frac12$, $\xi_q-y_q\le\frac12$ ($q=1,\dots,Q$), and uncertainty set $[0,1]^Q$. Then for every $K<|\mathcal Y|$,

Contrast Theorem 1 of the same paper: when $\xi$ enters only the objective, $\min\{\dim\mathcal Y,\operatorname{rk}Q\}+1$ policies already attain the optimal value of $\mathcal P$. Theorem 4 shows that when $\xi$ enters the constraints, every feasible policy $y\in\mathcal Y$ may be required.

Formalization Note $\mathcal P$ and $\mathcal P_K$ are the general problems of KAdaptability.ConstrGap.Values (any dimensions, any data), evaluated at the instance inst Q of KAdaptability.ConstrGap.Instance; the affine right-hand side of (EC.4) is encoded with an auxiliary parameter $\xi_{Q+1}=1$, as the paper prescribes on p. 6. The instance is fixed before $K$ is chosen, so a single instance works for all $K<|\mathcal Y|$. Values are in EReal.