The Price of Compressing Preferences: Sharp Regret Bounds and Cycle Certificates for Mechanism-Ready Representations

Reusable representations of private preferences are central to decision systems that must operate across changing prices, menus, and mechanisms, so compression should preserve the comparisons that determine downstream choices rather than raw utility coordinates. This requires a task-specific theory because outcome-independent utility shifts are behaviorally irrelevant, while merging several valuations can create multi-outcome worst-case regret that is invisible to coordinatewise reconstruction error, unpriced rankings, or pairwise diameter alone. We develop the Price of Compressing Preferences (PCP) framework for finite-outcome quasilinear economies, which identifies the exact information a menu-independent representation must retain to control regret uniformly over future priced menus. PCP first quotients valuations by additive constants and derives an exact strategic distortion, then converts each encoder cell into a system of pairwise difference constraints whose optimal surrogate is obtained by a linear program and whose obstruction is a maximum directed cycle mean, and finally lifts these certificates to message complexity, mechanism transfer, rate–distortion, and a Strategic Minimax quantizer. The theory shows that arbitrary deterministic response rules cannot outperform a single optimal surrogate and yields sharp diameter and covering bounds; experiments verify the LP–cycle identity to $1.1\times 10^{-15}$ on 240 random cells and, at $K=16$, reduce held-out maximum strategic distortion relative to Anchored K-means by $13.7\%$ on public projects and $24.3\%$ on bundle selection.