Theorem 1 — min{dim 𝒴, rk Q} + 1 policies attain the optimal value of 𝒫𝒪

Consider a two-stage robust binary program $\mathcal{PO}$ with objective uncertainty: a nonempty bounded polyhedral uncertainty set $\Xi$, first-stage set $\mathcal X\subseteq\mathbb R^N_+$ and finite second-stage set $\mathcal Y\subseteq\{0,1\}^M$. Let $\dim\mathcal Y$ be the affine dimension of $\mathcal Y$ and $\operatorname{rk}Q$ the rank of the second-stage cost matrix $Q$. Then for every number of policies

the K-adaptability problem $\mathcal{PO}_K$ has the same optimal value as $\mathcal{PO}$:

Under objective uncertainty, a number of here-and-now policies that is at most linear in the dimension of the second-stage decisions, or in the rank of the cost matrix, therefore loses nothing compared with full second-stage adaptability, although $\mathcal Y$ may have exponentially many elements.

Formalization Note Optimal values are in EReal (infeasibility gives $+\infty$). The theorem is stated for every $K$ at or above the threshold. Matrix.rank equals the row rank. For $\mathcal Y=\emptyset$ the Lean affine dimension is $0$; both optimal values are then $+\infty$.