Adaptive Certification of Linear Decisions: A Linear Price of Ignorance and Shared-Factor Guarantees

A decision maker measures an unknown cost parameter through exact linear queries and stops when one decision is optimal throughout the remaining uncertainty set. We compare local tie dimension, clairvoyant certification, adaptive discovery, and non-adaptive measurement, proving ℓ* ≤ p* ≤ κ* ≤ d*. The price of discovering a certificate can be linear in parameter dimension, the largest possible order, even with rational polyhedral data and rational one-query certificates. A polygon-product family with a quadratic number of inequalities has ℓ* = p* = 1 and κ* ≥ (1/10 − o(1))m; polynomial-size families approach the lower constant 1/6. The upper bound is m. For each fixed polygon prototype and sufficiently shallow fixed caps, the sharp order is instead m/log m, proved using robust finite-alphabet sketches. A cube construction attains the same order with a linear-size inequality description. Packing adversaries establish these separations for arbitrary deterministic linear queries. In contrast, for product menus with r shared factors and independent errors, the additive price is at most the factor-contrast rank, and is exactly r on a bounded family. Computing the adaptive measures is NP-hard when the factor dimension varies; computing d* is NP-hard even for nondegenerate polytopes. With physical factor and item probes, a factor-first policy is two-competitive up to the factor-probe cost. Finally, we classify box-saturated matroid base polytopes and all full-dimensional polytopes in ambient dimensions at most four, and give a finite LP saturation test for rational vertex-listed polytopes. A synthetic recipe-selection study illustrates the factor bounds.