Theorem 4.2 — Augmented Greedy recovers a $(1-1/e)$ fraction of complete-type revenue

Consider CAP with positive product revenues ordered from highest to lowest, nonnegative MNL preference weights, and nonnegative type-arrival probabilities summing to one. Let $S^*$ be an optimal first-stage assortment under capacity $K$. For customer types $C$, products $P$, and any $k\ge|P\cap S^*|$, let $\Delta$ be any output of Augmented Greedy on $C,k$. A type is complete with respect to $P$ when every product of $P\cap S^*$ belongs to its threshold optimal personalized assortment. Write $C_P$ for the complete types in $C$. Then

This structural bound is the paper's guarantee for Augmented Greedy and a building block for its later CAP approximation results.

Formalization Note The theorem covers every legal Greedy run and every tie-breaking choice of Augmented Greedy. The threshold optimal assortment is $\{i\in S^*:r_i\ge f_j(S^*)\}$, as in Lemma E.1. $k$ is independent of $K$.