Introduction
The product line design (PLD) problem concerns the selection of a limited subset of related product variants from a large candidate set to serve a heterogeneous market [10 ] (Zufryden 1977).
A key factor in the success of PLD is understanding heterogeneous customer preferences and predicting choice behavior across alternative product lines. Random utility maximization (RUM) models provide a standard framework to analyze this choice behavior. Specifically, it assumes that a random customer assigns a utility for every available alternative and selects the alternative with the highest realized utility. Therefore, the utility distribution over the population determines the choice probability of each alternative—the probability that it realizes the highest utility—which in turn allows the firm to evaluate the expected revenue of a product line.
A central challenge in constructing an RUM model is the inevitable uncertainty in customer utilities. This is because neither realized utilities nor their underlying distribution is directly observable and therefore both must be inferred from data such as transactions or conjoint surveys. More specifically, the error jointly reflects the inconsistency in respondents’ choices and the limited number of observations for each customer, leading to substantial estimation error in the inferred utilities [1 ] (Toubia et al. 2007).
As such, it is essential to design product lines that remain robust to uncertainty in the utility distribution. In this paper, we study the robust revenue-maximizing PLD problem under a general RUM framework. Specifically, we propose a distributionally robust optimization (DRO) model that maximizes the worst-case expected revenue over an ℓ 1 \ell_1 ℓ 1 -Wasserstein ball centered at the nominal utility distribution. Analysis of the dual reformulation reveals a general mechanism for robust PLD: protecting revenue against customer preference uncertainty creates an endogenous incentive to increase buyers’ welfare, defined as the expected utility customers obtain from their chosen alternatives. This finding is surprising because revenue and buyers’ welfare are typically viewed as competing objectives: revenue-oriented designs may favor higher-priced or less-preferred variants, thereby reducing customer welfare [19 ] . In contrast, our results show that, under preference uncertainty, buyers’ welfare serves not as a competing objective but as an insurance of revenue against customer preference uncertainty.
Two representative implementations are then considered. We first study the problem when the random utilities follows independent Gumbel shocks, yielding a closed-form robust multinomial logit (MNL) model. We show that in the unconstrained MNL setting, this structure further preserves the revenue-order property: an optimal robust product line can be found within the class of revenue-ordered assortments, substantially simplifying the resulting optimization problem. We quantify the optimality gap when the parameters are estimated from finitely many full-assortment choices. To accommodate more general choice behaviors, we then present a nonparametric implementation that represents the distribution of the complete utility vector directly by its empirical distribution. Its objective can be evaluated from sampled utility vectors and therefore can approximate any general RUM models, including those for which choice probabilities do not admit a closed-form expression. We establish a finite-sample bound linking this empirical first-choice formulation to the product line design problem under oracle distribution following arbitrary RUM.
The two implementations translate the general welfare mechanism into distinct operational principles. In the unconstrained MNL setting, the DRO model admits an optimal revenue-ordered product line that expands as the extent of distributional uncertainty increases. Under the empirical first-choice representation, robustness favors a more cost-effective product line that delivers greater customer utility relative to the revenue extracted.
Main Contributions
Our main contributions are summarized as follows.
perturb only a prespecified set of parameters or scenarios, our framework operates directly on the utility distribution of general RUM models. Performance guarantee of two specific implementations are established. Extensive numerical experiments demonstrate the superior performance of the proposed DRO model.
An endogenous alignment between revenue robustness and buyers’ welfare. Analysis of the dual reformulation reveals that protecting revenue against adverse utility shifts creates an endogenous incentive to increase buyers’ welfare. Specifically, greater aversion to distributional uncertainty raises the guaranteed lower bound on the buyers’ welfare delivered by the selected product line, thereby making higher-welfare product lines increasingly attractive as the extent of robustness increases. Under specific RUM specifications, this general mechanism translates into distinct operational principles that benefits customers. In the unconstrained MNL setting, robustness favors larger assortments; with an empirical nominal distribution, it favors more cost-effective product lines composed of products with lower prices and greater marginal utility relative to the outside option. Our numerical results on a semi-synthetic case study shows that the “goodness” to benefit more to the customer eventually pays back in the way of better out-of-sample revenue and buyers’ welfare, and therefore, yields a “doing well by doing good” effect in the robust PLD problem.
A certified solution method for empirical DRO. When the joint utility distribution is unknown, we use the empirical distribution of sampled utility vectors as the nominal. For the resulting cardinality-constrained problem, we develop Adaptive Parametric Search (APS). Given a prescribed tolerance δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) , APS certifies that the returned product line attains at least a ( 1 − δ ) (1-\delta) ( 1 − δ ) fraction of the empirical robust optimum. Across 360 synthetic instances, APS meets its prescribed tolerance in every run and, at δ = 0.05 \delta= 0.05 δ = 0.05 , is 70.7× faster on average and up to 662.4× faster than a direct mixed-integer linear reformulation.
Related Literature
Our work is most closely related to the literature on robust product line design and robust assortment planning. Because these two problems share closely related mathematical structures in our setting, we discuss them jointly and use the term product line design throughout for consistency.
Existing robust PLD models differ primarily in their assumptions about customer choice and the structure of the uncertainty set. Although a growing literature studies robust PLD under emerging choice models, such as ranking-based choice ([22 ] ) and Markov chain choice ([5 ] ), we focus on RUM-based models. RUMs offer a clear economic interpretation of customer choice and allow the outcomes of product-line decisions to be evaluated from both the seller’s perspective, through revenue, and the customer’s perspective, through buyers’ welfare.
Within the RUM framework, most studies focus on either the first-choice model or the multinomial logit (MNL) model. For the first-choice model, Wang and Curry (2012) allow each respondent’s estimated partworth utilities to vary within a box uncertainty set and maximize the resulting worst-case market share. Liu et al. [14 ] propose a related formulation in which each respondent’s utility vector varies within a more general polyhedral uncertainty set constructed from conjoint-analysis responses. Wang and Gutierrez (2022) adopt a scenario-based framework in which each scenario represents a possible first-choice model and optimize worst-case market share or expected revenue across scenarios. Liu et al. [15 ] introduce a Wasserstein DRO framework for the first-choice model, but focus on single-product design and share-of-choice maximization. For the MNL model, Rusmevichientong and Topaloglu [21 ] study robust assortment optimization when the attraction parameters are allowed to vary within a prescribed uncertainty set. Jin et al. [12 ] instead adopt a distributionally robust approach by placing a Kullback–Leibler divergence ball around a nominal MNL model. Moreover, Bertsimas and Mišić [1 ] jointly address parameter and model uncertainty. They construct multiple uncertainty sets around different nominal choice models, including first-choice and mixture-logit specifications, and maximize worst-case revenue over their union.
Most of these studies focus on improving performance under uncertainty but provide limited insight into the economic mechanisms through which robustness reshapes product-line decisions. Although Rusmevichientong and Topaloglu [21 ] ; Jin et al. [12 ] show that revenue-ordered assortments remain optimal and that greater uncertainty aversion leads to larger assortments, these results are specific to MNL-based models. Appendix EC.§ 3 shows that these properties need not survive a cardinality constraint, and that they do not extend to a general RUM. In contrast, our analysis shows that the underlying driver is an endogenous emphasis on buyers’ welfare induced by revenue robustness, which not only explain why a larger assortment is required for a more robust product line but also persists under a general RUM framework and cardinality constraints.
Liu et al. [15 ] is the most closely related study. From the perspective of share-of-choice maximization, they show that a Wasserstein DRO model under the first-choice framework also places an endogenous emphasis on buyers’ welfare. Our work differs from theirs in four respects. First, they maximize share-of-choice, the fraction of customers who select any of the offered products rather than the outside option. Product prices are therefore ignored or treated as identical, and the objective only requires knowing whether a customer prefers some offered product to the outside option. We maximize worst-case expected revenue. Because products earn different revenues, the firm must identify the product each customer chooses and balance higher-priced products chosen by fewer customers against lower-priced products chosen by more customers. Revenue maximization therefore creates a sharper conflict with buyers’ welfare: a larger share of customers who buy is only sometimes consistent with higher buyers’ welfare. The resulting price–utility trade-off yields a further implication of the welfare mechanism. Under the empirical model, greater robustness favors products that deliver more utility per unit of revenue. Second, Liu et al. [15 ] design a single product, whereas we select a product line from a candidate set. The number of feasible lines grows exponentially with the cardinality of the line, a computational difficulty that their analysis leaves unaddressed. We develop a set-branching procedure with modular bounds and an adaptive parametric search that returns a feasible line whose value is at least ( 1 − δ ) (1-\delta) ( 1 − δ ) times the empirical optimum. Across 360 instances with up to several hundred products and customers, the algorithm certifies every solution and, at δ = 0.05 \delta= 0.05 δ = 0.05 , is 70.7 × 70.7 \times 70.7 × faster on average than the mixed-integer formulation. Third, their nominal distribution is the empirical distribution of sampled utilities. We formulate the DRO model for an arbitrary RUM nominal, which covers standard parametric specifications and broadens the scope of the structural results. Under an MNL nominal, the robust objective has a closed form, an optimal product line is revenue-ordered, and, without a cardinality constraint, that line expands as the robustness radius increases. Fourth, we provide finite-sample guarantees for the revenue loss when the nominal distribution is estimated from data, which is not investigated by Liu et al. [15 ] .
The literature on semiparametric choice models also addresses uncertainty in the utility distribution ([20 , 18 , 9 ] ). These studies share our motivation that the joint distribution of customer utilities may be imperfectly known. However, they address this uncertainty by selecting the distribution that maximizes the expected utility of the customer’s chosen alternative. This optimization is embedded in the construction of the choice model and is therefore independent of the firm’s downstream objective. In contrast, our model selects the worst-case utility distribution according to the firm’s revenue objective, so the effect of distributional uncertainty depends explicitly on both product revenues and the product-line decision.
Finally, another relevant stream of literature incorporates buyers’ welfare into product line design. Buyers’ welfare has long been considered as an explicit objective, dating back at least to Kohli and Sukumar [13 ] . For a recent review of this literature, we refer readers to Sumida et al. [23 ] . In these studies, revenue and buyers’ welfare are typically viewed as conflicting objectives, and the resulting models are designed to balance the trade-off between them. In contrast, our model begins from a purely revenue-maximization perspective and shows that robustness can endogenously align the firm’s revenue objective with buyers’ welfare.
Organization
§ 2 establishes the classical product line design problem under a general random utility model. § 3 derives the Wasserstein robust model for a general nominal and specializes it to the multinomial logit, including the expected revenue loss when the logit parameters are estimated from choice data. § 4 develop a tractable implementation of any RUM based on approximating the nominal utility distribution with its empirical counterpart and derives the corresponding expected revenue guarantee. § 5 presents the certified algorithm for the empirical problem. § 6 evaluates the algorithm against the mixed-integer benchmark, and § 7 reports the conjoint case study. § 8 concludes the paper and proposes further research directions. Proofs and supporting formulations appear in the appendices.
The Classical Model
In this section, we introduce the classical non-robust PLD model as a benchmark for the analysis that follows. Throughout the paper, sets are denoted by calligraphic letters and their cardinalities by the corresponding uppercase letters (e.g., ∣ A ∣ = A |\mathcal{A}| = A ∣ A ∣ = A ). The symbol ≔ \coloneqq : = indicates a definition. Vectors and matrices are written in boldface, and I { ⋅ } \mathbb{I}\{\cdot\} I { ⋅ } denotes the indicator function.
Following a large body of prior work (e.g., Green and Krieger, [10 ] ; Chen and Hausman, [4 ] ; Bertsimas and Mišić, [2 ] ), we formulate the PLD problem as the selection of a product line S ⊆ A S \subseteq\mathcal{A} S ⊆ A from a set of candidate products A = { 1 , 2 , … , A } \mathcal{A} = \{1,2,\ldots,A\} A = { 1 , 2 , … , A } . Each product i ∈ A i \in\mathcal{A} i ∈ A generates revenue r i > 0 r_i > 0 r i > 0 , and we write r ˉ = max i ∈ A r i \bar{r} = \max_{i\in\mathcal{A}} r_i r ˉ = max i ∈ A r i . The outside option is indexed by 0 0 0 and yields zero revenue, i.e., r 0 = 0 r_0 = 0 r 0 = 0 . Let L \mathcal{L} L denote the family of feasible product lines that satisfy the firm’s structural or managerial constraints. For example, if the firm may offer at most p p p products, then L = { S ⊆ A : ∣ S ∣ ≤ p } \mathcal{L} = \{S \subseteq\mathcal{A}: |S| \leq p\} L = { S ⊆ A : ∣ S ∣ ≤ p } .
The choice model describes how customers select among the offered products and the outside option and therefore forms the basis for evaluating a product line. We adopt the random utility maximization framework. Under this framework, each customer is associated with a random utility vector U = ( U 0 , U 1 , … , U A ) \mathbf{U} = (U_0,U_1,\ldots,U_A) U = ( U 0 , U 1 , … , U A ) , where the randomness captures preference heterogeneity across customers. Given a product line S S S , the customer chooses the alternative with the highest utility from S ∪ { 0 } S \cup\{0\} S ∪ { 0 } . Let Q Q Q denote the population distribution of U U U . For any i ∈ S ∪ { 0 } i \in S \cup\{0\} i ∈ S ∪ { 0 } , the choice probability of alternative i i i under product line S S S is q i ( S ; Q ) = P Q ( U i ≥ U j , ∀ j ∈ S ∪ { 0 } ) q_i(S;Q) = \mathbb{P}_Q(U_i \geq U_j,\ \forall j \in S \cup\{0\}) q i ( S ; Q ) = P Q ( U i ≥ U j , ∀ j ∈ S ∪ { 0 }) . For i ∈ S i \in S i ∈ S , this probability represents the expected market share for product i i i .1 Therefore, the expected revenue of product line S S S under the population distribution Q Q Q is R ( S ; Q ) = ∑ i ∈ S r i q i ( S ; Q ) R(S;Q) = \sum_{i\in S} r_i q_i(S;Q) R ( S ; Q ) = ∑ i ∈ S r i q i ( S ; Q ) , and the population PLD problem is
max S ∈ L R ( S ; Q ) . (1) \max_{S\in\mathcal{L}} R(S;Q). \tag*{(1)} S ∈ L max R ( S ; Q ) . (1)
The choice probabilities and the resulting expected revenue depend critically on the underlying distribution of the utility vector U U U . Different distributional assumptions give rise to different random utility choice models. For example, if the utility shocks are independently and identically distributed according to a type-I extreme value distribution, the RUM reduces to the multinomial logit (MNL) model; if they follow a multivariate normal distribution, the resulting model is the multinomial probit model.
However, the population distribution Q Q Q is not directly observable and must be inferred from limited data, yielding a proxy distribution Q ^ \widehat{Q} Q for optimization. A parametric approach, such as the MNL model, imposes a distributional structure and estimates its parameters, gaining parsimony at the risk of model misspecification. In contrast, a nonparametric approach, such as an empirical approximation based on i.i.d. samples, avoids imposing a specific distributional form but may require a large sample to accurately approximate the population distribution and is therefore susceptible to sampling error when data are limited. In either case, the proxy Q ^ \widehat{Q} Q used for optimization may differ from the true population distribution Q Q Q . This discrepancy motivates a robust formulation that accommodates both representations while protecting product-line decisions against ambiguity in the underlying customer preference distribution.
The Distributionally Robust Optimization Model and Analysis
We now replace the population objective in Problem (1) with a distributionally robust counterpart centered at a nominal utility distribution. Section 3.1 develops the general model and its dual reformulation without imposing a parametric structure on the nominal. Section 3.2 specializes the nominal to the multinomial logit.
The DRO Model with a General RUM Nominal Distribution
As discussed above, the proxy distribution Q ^ \widehat{Q} Q may differ from the population distribution Q Q Q because of sampling and estimation errors. We account for this discrepancy by evaluating each product line over a Wasserstein neighborhood centered at a nominal distribution Q Q Q . In the implementations below, this nominal is the proxy Q ^ \widehat{Q} Q or an empirical distribution constructed from it. The Wasserstein distance between two distributions measures the minimum transportation cost required to move probability mass from one distribution to the other.
Definition 1 (Wasserstein Metric, Esfahani and Kuhn, 2018). Let M ( u ) \mathcal{M}(u) M ( u ) be the set of probability measures supported on u u u , and let Π ( P , Q ) \Pi(P,Q) Π ( P , Q ) collect their joint distributions with marginals P P P and Q Q Q . The Wasserstein distance is
d W ( P , Q ) = inf Π ∈ Π ( P , Q ) ∫ U 2 ∥ U − U ~ ∥ Π ( d U , d U ~ ) , d_W(P,Q)=\inf_{\Pi\in\Pi(P,Q)}\int_{\mathcal{U}^2}\lVert U-\widetilde{U}\rVert\Pi(dU,d\widetilde{U}), d W ( P , Q ) = Π ∈ Π ( P , Q ) inf ∫ U 2 ∥ U − U ∥ Π ( d U , d U ) , where ∥ ⋅ ∥ \lVert\cdot\rVert ∥ ⋅ ∥ is the chosen ground norm.
Unless stated otherwise, the ground norm is ℓ 1 \ell_1 ℓ 1 . For a radius ϵ ≥ 0 \epsilon\ge0 ϵ ≥ 0 , define the ambiguity set centered at Q Q Q as U ϵ ( Q ) = { P ∈ M ( u ) : d W ( P , Q ) ≤ ϵ } \mathcal{U}_{\epsilon}(Q)=\{P\in\mathcal{M}(u):d_W(P,Q)\le\epsilon\} U ϵ ( Q ) = { P ∈ M ( u ) : d W ( P , Q ) ≤ ϵ } . The radius ϵ \epsilon ϵ controls the extent of distributional protection. Increasing ϵ \epsilon ϵ enlarges the ambiguity set, whereas ϵ = 0 \epsilon=0 ϵ = 0 gives U 0 ( Q ) = { Q } \mathcal{U}_0(Q)=\{Q\} U 0 ( Q ) = { Q } and recovers the nominal model.
For a product line S S S , define its worst-case expected revenue over this ambiguity set as R ϵ ( S ; Q ) = inf P ∈ U ϵ ( Q ) R ( S ; P ) R_{\epsilon}(S;Q)=\inf_{P\in\mathcal{U}_{\epsilon}(Q)}R(S;P) R ϵ ( S ; Q ) = inf P ∈ U ϵ ( Q ) R ( S ; P ) . The corresponding Wasserstein DRO problem is max S ∈ S R ϵ ( S ; Q ) \max_{S\in\mathcal{S}}R_{\epsilon}(S;Q) max S ∈ S R ϵ ( S ; Q ) .
Direct evaluation of the inner problem requires optimization over probability distributions. For a fixed product line and ϵ > 0 \epsilon>0 ϵ > 0 , this infinite-dimensional problem admits the following one-dimensional dual reformulation.
Proposition 1 (Dual reformulation of the worst-case revenue). Fix a product line S ∈ L S \in\mathcal{L} S ∈ L , and suppose that the Wasserstein distance is induced by the ℓ 1 \ell_1 ℓ 1 -norm. If the nominal distribution Q Q Q has a finite first moment, then, for any ϵ > 0 \epsilon> 0 ϵ > 0 , the worst-case expected revenue satisfies
R ϵ ( S ; Q ) = max λ ≥ 0 { − λ ϵ + λ E U ∼ Q [ max i ∈ S ∪ { 0 } U i ] − λ E U ∼ Q [ max i ∈ S ∪ { 0 } { U i − r i λ } ] } (2) R_{\epsilon}(S; Q) = \max_{\lambda\ge0} \left\{ -\lambda\epsilon+ \lambda\mathbb{E}_{U \sim Q}\left[\max_{i \in S \cup\{0\}} U_i\right] - \lambda\mathbb{E}_{U \sim Q}\left[\max_{i \in S \cup\{0\}}\left\{U_i - \frac{r_i}{\lambda}\right\}\right] \right\} \tag*{(2)} R ϵ ( S ; Q ) = λ ≥ 0 max { − λ ϵ + λ E U ∼ Q [ i ∈ S ∪ { 0 } max U i ] − λ E U ∼ Q [ i ∈ S ∪ { 0 } max { U i − λ r i } ] } (2) = max λ ≥ 0 { − λ ϵ + E U ∼ Q [ min i ∈ S ∪ { 0 } { r i + λ ( max j ∈ S ∪ { 0 } U j − U i ) } ] } . = \max_{\lambda\ge0} \left\{ -\lambda\epsilon+ \mathbb{E}_{U \sim Q}\left[\min_{i \in S \cup\{0\}}\left\{r_i + \lambda\left(\max_{j \in S \cup\{0\}} U_j - U_i\right)\right\}\right] \right\}. = λ ≥ 0 max { − λ ϵ + E U ∼ Q [ i ∈ S ∪ { 0 } min { r i + λ ( j ∈ S ∪ { 0 } max U j − U i ) } ] } .
Proposition 1 replaces the search over distributions with an optimization over the scalar dual variable λ \lambda λ . Both expectations are taken under Q Q Q , so the least favorable distribution need not be constructed explicitly. The reformulation can also be combined with the outer problem, yielding a joint optimization over ( S , λ ) (S,\lambda) ( S , λ ) . The DRO problem for PLD is
max S ∈ L R ϵ ( S ; Q ) (3) \max_{S \in\mathcal{L}} R_{\epsilon}(S; Q) \tag*{(3)} S ∈ L max R ϵ ( S ; Q ) (3)
The dual reveals that the first expectation in (2) is the utility customers obtain from their chosen alternatives, which is the standard buyers’ welfare measure in product-line design [11 , 13 , 15 ] . We denote this expectation by W ( S ; Q ) W(S; Q) W ( S ; Q ) . Because λ ≥ 0 \lambda\ge0 λ ≥ 0 , welfare enters the dual objective through the nonnegative term λ W ( S ; Q ) \lambda W(S; Q) λW ( S ; Q ) , which creates an endogenous incentive to offer product lines that deliver greater customer value.
Moreover, observe that, the final term in (2) satisfies
λ max i ∈ S ∪ { 0 } { U i − r i λ } = max i ∈ S ∪ { 0 } { λ U i − r i } . \lambda\max_{i \in S \cup\{0\}} \left\{U_i - \frac{r_i}{\lambda}\right\} = \max_{i \in S \cup\{0\}} \{\lambda U_i - r_i\}. λ i ∈ S ∪ { 0 } max { U i − λ r i } = i ∈ S ∪ { 0 } max { λ U i − r i } .
Therefore, the right-hand side is piecewise linear and convex in λ \lambda λ , as it is the pointwise maximum of affine functions. Since expectations preserve convexity, λ E U ∼ Q [ max i ∈ S ∪ { 0 } { U i − r i / λ } ] \lambda\mathbb{E}_{U \sim Q}\left[\max_{i \in S \cup\{0\}}\left\{U_i - r_i/\lambda\right\}\right] λ E U ∼ Q [ max i ∈ S ∪ { 0 } { U i − r i / λ } ] is also convex in λ \lambda λ . It follows that the objective in (2) is concave in λ \lambda λ . This concavity further reveals the welfare incentive induced by the DRO model. Because r 0 = 0 r_0 = 0 r 0 = 0 and r i > 0 r_i > 0 r i > 0 for every i ∈ S i \in S i ∈ S , the outside option becomes the maximizer of λ U i − r i \lambda U_i - r_i λ U i − r i as λ → 0 + \lambda\to0^+ λ → 0 + . Consequently, the right derivative of the dual objective at λ = 0 \lambda= 0 λ = 0 is W ( S ; Q ) − E Q [ U 0 ] − ϵ W(S; Q) - \mathbb{E}_Q[U_0] - \epsilon W ( S ; Q ) − E Q [ U 0 ] − ϵ . By concavity, λ = 0 \lambda= 0 λ = 0 is optimal if and only if W ( S ; Q ) − E Q [ U 0 ] ≤ ϵ W(S; Q) - \mathbb{E}_Q[U_0] \le\epsilon W ( S ; Q ) − E Q [ U 0 ] ≤ ϵ . When λ ∗ = 0 \lambda^* = 0 λ ∗ = 0 , the robust revenue equals zero, the smallest attainable revenue level. Hence, such a product line cannot be robust optimal whenever another feasible product line attains strictly positive robust revenue. This observation imposes a welfare requirement on any robust-optimal product line.
Corollary 1 (Lower Bound on Buyers’ Welfare). Let W ∗ ( Q ) = max S ∈ L W ( S ; Q ) W^*(Q) = \max_{S \in\mathcal{L}} W(S; Q) W ∗ ( Q ) = max S ∈ L W ( S ; Q ) be the maximum buyers’ welfare over all feasible product lines under Q Q Q , and define the critical radius as ϵ † ( Q ) = W ∗ ( Q ) − E Q [ U 0 ] \epsilon^\dagger(Q) = W^*(Q) - \mathbb{E}_Q[U_0] ϵ † ( Q ) = W ∗ ( Q ) − E Q [ U 0 ] . Then, for any 0 ≤ ϵ < ϵ † ( Q ) 0 \le\epsilon< \epsilon^\dagger(Q) 0 ≤ ϵ < ϵ † ( Q ) , every optimal solution S ϵ ∗ ( Q ) S^*_\epsilon(Q) S ϵ ∗ ( Q ) satisfies
W ( S ϵ ∗ ( Q ) ; Q ) − E Q [ U 0 ] ≥ ϵ . W(S^*_\epsilon(Q); Q) - \mathbb{E}_Q[U_0] \ge\epsilon. W ( S ϵ ∗ ( Q ) ; Q ) − E Q [ U 0 ] ≥ ϵ .
In the corollary above, W ( S ; Q ) − E Q [ U 0 ] W(S; Q) - \mathbb{E}_Q[U_0] W ( S ; Q ) − E Q [ U 0 ] measures the incremental welfare generated by offering S S S relative to offering only the outside option. Corollary 1 therefore shows that robustness imposes an implicit welfare requirement, and that this requirement becomes more stringent as ϵ \epsilon ϵ increases.
Without further structure on the nominal distribution, the expectations in the general reformulation may not be directly computable, and the form of the welfare requirement depends on both the nominal and the feasible family. The next subsection specializes the nominal to the multinomial logit, for which these expectations are available in closed form.
DRO Model with MNL Nominal Distribution
We first specialize the DRO model to an MNL nominal distribution. Let Q M N L Q^{\mathrm{MNL}} Q MNL denote the distribution induced by utilities U i = μ i + ε i U_i=\mu_i+\varepsilon_i U i = μ i + ε i , i ∈ A ∪ { 0 } i\in\mathcal{A}\cup\{0\} i ∈ A ∪ { 0 } , where the shocks ε i \varepsilon_i ε i are i.i.d. standard Gumbel random variables. Writing v i = exp ( μ i ) v_i=\exp(\mu_i) v i = exp ( μ i ) , the two expectations in Proposition 1 are θ + log ∑ j ∈ S ∪ { 0 } v j \theta+\log\sum_{j\in S\cup\{0\}}v_j θ + log ∑ j ∈ S ∪ { 0 } v j and θ + log ∑ i ∈ S ∪ { 0 } v i e − r i / λ \theta+\log\sum_{i\in S\cup\{0\}}v_i e^{-r_i/\lambda} θ + log ∑ i ∈ S ∪ { 0 } v i e − r i / λ , respectively [23 ] , where θ \theta θ is the Euler–Mascheroni constant. The robust model is therefore fully determined by the nominal attraction vector v = ( v 0 , v 1 , … , v A ) \boldsymbol{v}=(v_0,v_1,\ldots,v_A) v = ( v 0 , v 1 , … , v A ) and radius ϵ > 0 \epsilon>0 ϵ > 0 . The robust MNL revenue of S ∈ L S\in\mathcal{L} S ∈ L is given by
R ϵ ( S ; Q M N L ) = sup λ ≥ 0 [ − ϵ + log ( v 0 + ∑ j ∈ S v j v 0 + ∑ i ∈ S v i e − r i / λ ) ] (4) R_{\epsilon}(S;Q^{\mathrm{MNL}})=\sup_{\lambda\geq0}\left[-\epsilon+\log\left(\frac{v_0+\sum_{j\in S}v_j}{v_0+\sum_{i\in S}v_i e^{-r_i/\lambda}}\right)\right] \tag*{(4)} R ϵ ( S ; Q MNL ) = λ ≥ 0 sup [ − ϵ + log ( v 0 + ∑ i ∈ S v i e − r i / λ v 0 + ∑ j ∈ S v j ) ] (4)
with the value at λ = 0 \lambda=0 λ = 0 defined by continuity. Therefore, the product-line design problem is [DRO-MNL] max S ∈ L R ϵ ( S ; Q M N L ) \max_{S\in\mathcal{L}}R_{\epsilon}(S;Q^{\mathrm{MNL}}) max S ∈ L R ϵ ( S ; Q MNL ) .
Without a cardinality constraint, the next proposition establishes that [DRO-MNL] preserves the revenue-ordered structure of its nominal counterpart.
Proposition 2 (Revenue-Ordered Structure under MNL). Suppose the nominal utility distribution follows the MNL model, ϵ > 0 \epsilon>0 ϵ > 0 , and there is no cardinality constraint on the offered product line. Relabel the products such that r 1 ≥ r 2 ≥ ⋯ ≥ r A > 0 r_1\geq r_2\geq\cdots\geq r_A>0 r 1 ≥ r 2 ≥ ⋯ ≥ r A > 0 . Then there exists an optimal product line of the form S k = { 1 , … , k } S_k=\{1,\ldots,k\} S k = { 1 , … , k } for some k ∈ { 1 , … , A } k\in\{1,\ldots,A\} k ∈ { 1 , … , A } . Consequently, the robust product line design problem reduces to
max k = 1 , … , A max λ ≥ 0 [ − ϵ + log ( v 0 + ∑ i = 1 k v i v 0 + ∑ i = 1 k v i e − r i / λ ) ] . \max_{k=1,\ldots,A}\max_{\lambda\geq0}\left[-\epsilon+\log\left(\frac{v_0+\sum_{i=1}^{k}v_i}{v_0+\sum_{i=1}^{k}v_i e^{-r_i/\lambda}}\right)\right]. k = 1 , … , A max λ ≥ 0 max [ − ϵ + log ( v 0 + ∑ i = 1 k v i e − r i / λ v 0 + ∑ i = 1 k v i ) ] .
We next characterize how the optimal prefix changes with the robustness radius. The following proposition implies that the optimal product line expands as the robustness radius increases, thereby raising buyers’ welfare.
Proposition 3 (Expansion of the Optimal Product Line). Suppose the nominal utility distribution follows the MNL model and there is no cardinality constraint. Relabel the products such that r 1 ≥ r 2 ≥ ⋯ ≥ r A > 0 r_1\geq r_2\geq\cdots\geq r_A>0 r 1 ≥ r 2 ≥ ⋯ ≥ r A > 0 . For each robustness radius ϵ > 0 \epsilon>0 ϵ > 0 , let ( S ∗ ( ϵ ) , λ ϵ ∗ ) (S^*(\epsilon),\lambda^*_\epsilon) ( S ∗ ( ϵ ) , λ ϵ ∗ ) be an optimal pair for [DRO-MNL], where S ∗ ( ϵ ) = { 1 , … , k ∗ ( ϵ ) } S^*(\epsilon)=\{1,\ldots,k^*(\epsilon)\} S ∗ ( ϵ ) = { 1 , … , k ∗ ( ϵ )} , with ties among optimal prefixes resolved by selecting the largest prefix. Then k ∗ ( ϵ ) k^*(\epsilon) k ∗ ( ϵ ) is weakly increasing in ϵ \epsilon ϵ . Equivalently, if 0 < ϵ 1 ≤ ϵ 2 0<\epsilon_1\leq\epsilon_2 0 < ϵ 1 ≤ ϵ 2 , then
∣ S ∗ ( ϵ 1 ) ∣ ≤ ∣ S ∗ ( ϵ 2 ) ∣ . \lvert S^*(\epsilon_1)\rvert\leq\lvert S^*(\epsilon_2)\rvert. ∣ S ∗ ( ϵ 1 )∣ ≤ ∣ S ∗ ( ϵ 2 )∣ .
Because buyers’ welfare under the MNL model is monotone with respect to set inclusion, the product-line expansion established in Proposition 3 directly translates into a welfare improvement. Thus, a greater degree of robustness induces the firm to offer a product line delivering weakly greater buyers’ welfare.
Data-driven Implementation with Finite Consumer Choice Data.
When the parameters of the nominal MNL model are not known a priori , we should first estimate them using the observed choice data. In this case, we consider a case where the nominal MNL distribution using N N N choices observed when the offered product line is the candidate set A \mathcal{A} A . Specifically, the observed choice data Y 1 , … , Y N Y_1,\ldots,Y_N Y 1 , … , Y N are i.i.d. samples denoting the customer choice when offering the full assortment, where Y t = 0 Y_t=0 Y t = 0 denotes no purchase which is assumed to be also observed. Under the MNL assumption and observation of the full product line, the maximum-likelihood estimator of the attraction parameters admits the closed form in the following proposition.
Proposition 4 (MNL maximum-likelihood estimator). Denote the choice counts and empirical shares as n ^ i : = ∑ t = 1 N I { Y t = i } \hat{n}_i := \sum_{t=1}^{N} \mathbb{I}\{Y_t=i\} n ^ i := ∑ t = 1 N I { Y t = i } , p ^ i : = n ^ i / N \hat{p}_i := \hat{n}_i/N p ^ i := n ^ i / N , i = 0 , 1 , … , A i=0,1,\ldots,A i = 0 , 1 , … , A , and write p ^ = ( p ^ 0 , p ^ 1 , … , p ^ A ) \hat{\mathbf{p}}=(\hat{p}_0,\hat{p}_1,\ldots,\hat{p}_A) p ^ = ( p ^ 0 , p ^ 1 , … , p ^ A ) . If n ^ 0 > 0 \hat{n}_0>0 n ^ 0 > 0 , the extended MLE of v i v_i v i is
v ^ i = n ^ i / n ^ 0 = p ^ i / p ^ 0 , i = 0 , 1 , … , A . (5) \hat{v}_i=\hat{n}_i/\hat{n}_0=\hat{p}_i/\hat{p}_0,\qquad i=0,1,\ldots,A. \tag*{(5)} v ^ i = n ^ i / n ^ 0 = p ^ i / p ^ 0 , i = 0 , 1 , … , A . (5) It is an interior finite MLE if and only if every n ^ i > 0 \hat{n}_i>0 n ^ i > 0 , including n ^ 0 > 0 \hat{n}_0>0 n ^ 0 > 0 .
We estimate the choice probability of alternative i i i on a product line S S S by
q ^ i ( S ) : = v ^ i 1 + ∑ j ∈ S v ^ j = p ^ i p ^ 0 + ∑ j ∈ S p ^ j , (6) \hat{q}_i(S):=\frac{\hat{v}_i}{1+\sum_{j\in S}\hat{v}_j}=\frac{\hat{p}_i}{\hat{p}_0+\sum_{j\in S}\hat{p}_j}, \tag*{(6)} q ^ i ( S ) := 1 + ∑ j ∈ S v ^ j v ^ i = p ^ 0 + ∑ j ∈ S p ^ j p ^ i , (6) where the second equality uses v ^ i = p ^ i / p ^ 0 \hat{v}_i=\hat{p}_i/\hat{p}_0 v ^ i = p ^ i / p ^ 0 for i ≥ 1 i\ge1 i ≥ 1 .
Lemma 1 (Uniform choice-probability error). Suppose the true model is MNL with attractions v = ( v 0 , v 1 , … , v A ) \mathbf{v}=(v_0,v_1,\ldots,v_A) v = ( v 0 , v 1 , … , v A ) , normalized by v 0 = 1 v_0=1 v 0 = 1 , and write Q Q Q for the induced distribution. Denote the choice probabilities on A \mathcal{A} A by
p 0 = Q ( A ; Q ) = 1 1 + ∑ j = 1 A v j , p i = q i ( A ; Q ) = v i 1 + ∑ j = 1 A v j , i = 1 , … , A , (7) p_0=Q(\mathcal{A};Q)=\frac{1}{1+\sum_{j=1}^{A}v_j},\qquad p_i=q_i(\mathcal{A};Q)=\frac{v_i}{1+\sum_{j=1}^{A}v_j},\qquad i=1,\ldots,A, \tag*{(7)} p 0 = Q ( A ; Q ) = 1 + ∑ j = 1 A v j 1 , p i = q i ( A ; Q ) = 1 + ∑ j = 1 A v j v i , i = 1 , … , A , (7) and
q i ( S ; Q ) = p i p 0 + ∑ j ∈ S p j . q_i(S;Q)=\frac{p_i}{p_0+\sum_{j\in S}p_j}. q i ( S ; Q ) = p 0 + ∑ j ∈ S p j p i . If p 0 ≥ κ > 0 p_0\ge\kappa>0 p 0 ≥ κ > 0 , and p ^ 0 > 0 \hat{p}_0>0 p ^ 0 > 0 , we have
E ( sup S ⊆ A ∑ i ∈ S ∪ { 0 } ∣ q ^ i ( S ) − q i ( S ; Q ) ∣ ) ≤ 2 κ A N . (8) \mathbb{E}\left(\sup_{S\subseteq\mathcal{A}}\sum_{i\in S\cup\{0\}}\left|\hat{q}_i(S)-q_i(S;Q)\right|\right)\le\frac{2}{\kappa}\sqrt{\frac{A}{N}}. \tag*{(8)} E S ⊆ A sup i ∈ S ∪ { 0 } ∑ ∣ q ^ i ( S ) − q i ( S ; Q ) ∣ ≤ κ 2 N A . (8)
The estimated nominal yields a guarantee for the robust objective under the true distribution. Let
S ^ N ∈ arg max S ∈ L R ^ ϵ ( S ) \hat{S}_N\in\arg\max_{S\in\mathcal{L}}\hat{R}_{\epsilon}(S) S ^ N ∈ arg S ∈ L max R ^ ϵ ( S )
denote an optimal product line of [DRO-MNL] under the estimated DRO objective function. Then, we have the following result.
Proposition 5 (Expected robust revenue loss). Under the assumptions of Lemma 1, suppose p ^ 0 > 0 \hat{p}_0>0 p ^ 0 > 0 . Then, the expected loss of from the data-driven approach is
E [ max S ∈ L R ϵ ( S ; Q ) − R ϵ ( S ^ N ; Q ) ] ≤ 4 r ˉ κ A N + r ˉ exp ( − N κ 8 ) = O ( N − 1 / 2 ) . (9) \mathbb{E}\left[\max_{S\in\mathcal{L}}R_{\epsilon}(S;Q)-R_{\epsilon}(\hat{S}_N;Q)\right]\le\frac{4\bar{r}}{\kappa}\sqrt{\frac{A}{N}}+\bar{r}\exp\left(-\frac{N\kappa}{8}\right)=O(N^{-1/2}). \tag*{(9)} E [ S ∈ L max R ϵ ( S ; Q ) − R ϵ ( S ^ N ; Q ) ] ≤ κ 4 r ˉ N A + r ˉ exp ( − 8 N κ ) = O ( N − 1/2 ) . (9)
The loss bound in Lemma 5 immediately gives the sample size needed to achieve certain prescribed tolerance level.
Corollary 2 (Sample size for a prescribed expected robust loss). Fix ϵ ≥ 0 \epsilon\ge0 ϵ ≥ 0 and η > 0 \eta>0 η > 0 . Under the assumptions of Proposition 5, if
N ≥ max { 64 A r ˉ 2 κ 2 η 2 , 8 κ max { 0 , log 2 r ˉ η } } , (10) N\ge\max\left\{\frac{64A\bar{r}^{2}}{\kappa^{2}\eta^{2}},\frac{8}{\kappa}\max\left\{0,\log\frac{2\bar{r}}{\eta}\right\}\right\}, \tag*{(10)} N ≥ max { κ 2 η 2 64 A r ˉ 2 , κ 8 max { 0 , log η 2 r ˉ } } , (10) then
E [ max S ∈ L R ϵ ( S ; Q ) − R ϵ ( S ^ N ; Q ) ] ≤ η . \mathbb{E}\left[\max_{S\in\mathcal{L}}R_{\epsilon}(S;Q)-R_{\epsilon}(\hat{S}_N;Q)\right]\le\eta. E [ S ∈ L max R ϵ ( S ; Q ) − R ϵ ( S ^ N ; Q ) ] ≤ η .
DRO with Empirical Approximation
The MNL specification yields sharp structural results but imposes restrictive substitution model, and the preceding assortment-expansion result relies on an unconstrained product line. In many applications, the type of choice model may also be unknown. We therefore develop a nonparametric data-driven formulation based on an empirical nominal distribution, which is also known as the first-choice model [1 , 15 ] .
To construct a sample average for the DRO, we define for convenience, for U = ( U 0 , U 1 , … , U A ) U=(U_0,U_1,\ldots,U_A) U = ( U 0 , U 1 , … , U A ) ,
ϕ S , λ ( U ) = min i ∈ S ∪ { 0 } { r i + λ ( max j ∈ S ∪ { 0 } U j − U i ) } . (11) \phi_{S,\lambda}(U)=\min_{i\in S\cup\{0\}}\left\{r_i+\lambda\left(\max_{j\in S\cup\{0\}}U_j-U_i\right)\right\}. \tag*{(11)} ϕ S , λ ( U ) = i ∈ S ∪ { 0 } min { r i + λ ( j ∈ S ∪ { 0 } max U j − U i ) } . (11)
Thus, the outside option is included in both the maximum and the minimum, with r 0 = 0 r_0=0 r 0 = 0 . This is essential: the first term represents the utility of the customer’s preferred available alternative, which may be the outside option, while the second term allows the adversarially induced choice to be the outside option. Restricting either index set to S S S alone would define a different objective and would incorrectly rule out no purchase. In terms of this function, we have
R ϵ ( S ; Q ) = max λ ≥ 0 { − λ ϵ + E U ∼ Q [ ϕ S , λ ( U ) ] } . (12) R_\epsilon(S;Q)=\max_{\lambda\ge0}\left\{-\lambda\epsilon+\mathbb{E}_{U\sim Q}[\phi_{S,\lambda}(U)]\right\}. \tag*{(12)} R ϵ ( S ; Q ) = λ ≥ 0 max { − λ ϵ + E U ∼ Q [ ϕ S , λ ( U )] } . (12)
Collect N N N independent full utility samples u ^ n = ( u ^ n 0 , u ^ n 1 , … , u ^ n A ) \hat{u}_n=(\hat{u}_{n0},\hat{u}_{n1},\ldots,\hat{u}_{nA}) u ^ n = ( u ^ n 0 , u ^ n 1 , … , u ^ n A ) that are i.i.d. with distribution Q Q Q . These utility-vector samples can be obtained through, for example, repeated choice experiments used to survey the customer preference such as those used in conjoint-analysis settings, individual-level utility vectors can be estimated from respondents’ stated preferences and treated as sampled realizations of heterogeneous customer utilities. See e.g., the discussions in Toubia et al. (2003); Evgeniou et al. [8 ] .
The sample-average approximation (SAA) of the DRO objective function is
R ^ ϵ ( S ) : = sup λ ≥ 0 { − λ ϵ + 1 N ∑ n = 1 N ϕ S , λ ( u ^ n ) } . (13) \widehat{R}_\epsilon(S):=\sup_{\lambda\ge0}\left\{-\lambda\epsilon+\frac{1}{N}\sum_{n=1}^{N}\phi_{S,\lambda}(\hat{u}_n)\right\}. \tag*{(13)} R ϵ ( S ) := λ ≥ 0 sup { − λ ϵ + N 1 n = 1 ∑ N ϕ S , λ ( u ^ n ) } . (13)
The resulting first-choice product-line design problem, denoted by [DRO-FC], is
[DRO-FC] S ^ N ∈ arg max S ∈ L R ^ ϵ ( S ) . (14) \text{[DRO-FC]}\qquad\widehat{S}_N\in\arg\max_{S\in\mathcal{L}}\widehat{R}_\epsilon(S). \tag*{(14)} [DRO-FC] S N ∈ arg S ∈ L max R ϵ ( S ) . (14)
Beyond its implementability, the empirical formulation permits a sample-level characterization of worst-case selection.
Proposition 6 (Worst-case Selection of Customer n n n ). Given a fixed product line S S S and dual multiplier λ \lambda λ , let k n ∈ arg min i ∈ S ∪ { 0 } { r i − λ u ^ n i } k_n\in\arg\min_{i\in S\cup\{0\}}\{r_i-\lambda\hat{u}_{ni}\} k n ∈ arg min i ∈ S ∪ { 0 } { r i − λ u ^ ni } . Then, k n k_n k n satisfies the following conditions:
The dominance condition states that the worst-case choice k n k_n k n is Pareto-undominated under the adversary’s revenue–utility ordering: no available alternative can generate strictly lower revenue while delivering weakly higher utility.
The two margin conditions provide a consumer-value interpretation of λ \lambda λ . Relative to the worst-case choice k n k_n k n , a higher-revenue alternative cannot offer enough extra utility per unit of additional revenue to justify moving upward; equivalently, its utility gain per unit of revenue premium is at most 1 / λ 1/\lambda 1/ λ . Conversely, a lower-revenue alternative must sacrifice sufficiently much utility per unit of revenue saved, so moving downward is not attractive from the consumer’s perspective. Thus, 1 / λ 1/\lambda 1/ λ acts as a utility-per-revenue benchmark for comparing products around k n k_n k n .
If k n ≠ 0 k_n \ne0 k n = 0 , dominance exclusion implies u ^ n k n > u ^ n 0 \hat{u}_{nk_n} > \hat{u}_{n0} u ^ n k n > u ^ n 0 . Applying the lower-margin condition to the outside option then gives r k n / ( u ^ n k n − u ^ n 0 ) ≤ λ r_{k_n}/(\hat{u}_{nk_n} - \hat{u}_{n0}) \le\lambda r k n / ( u ^ n k n − u ^ n 0 ) ≤ λ . Summing over customers, and noting that both sides contribute zero when k n = 0 k_n = 0 k n = 0 , gives
∑ n ∈ N r k n ≤ λ ∑ n ∈ N ( u ^ n k n − u ^ n 0 ) . \sum_{n\in\mathcal{N}} r_{k_n} \le\lambda\sum_{n\in\mathcal{N}}(\hat{u}_{nk_n} - \hat{u}_{n0}). n ∈ N ∑ r k n ≤ λ n ∈ N ∑ ( u ^ n k n − u ^ n 0 ) .
The left-hand side is the aggregate revenue generated by the worst-case choices, and the right-hand sum is their aggregate utility gain relative to the outside option. Thus, the inequality indicates that there must exists an alternative for each sample such that these alternatives must deliver at least 1 / λ 1/\lambda 1/ λ units of incremental utility per unit of revenue on average.
A smaller λ \lambda λ tightens this requirement and forces the worst-case demand realization to place weight only on products with greater consumer value per unit of revenue. The next result links this interpretation to the robustness radius.
Proposition 7 (Monotonicity of λ ϵ ∗ \lambda^{*}_{\epsilon} λ ϵ ∗ ). For [ D R O - F C ] [DRO\text{-}FC] [ D R O - F C ] , let ( S j , λ j ) (S_j,\lambda_j) ( S j , λ j ) be any joint optimizer at robustness level ϵ j \epsilon_j ϵ j , j = 1 , 2 j = 1, 2 j = 1 , 2 . If 0 < ϵ 1 < ϵ 2 0 < \epsilon_1 < \epsilon_2 0 < ϵ 1 < ϵ 2 , then λ 1 ≥ λ 2 \lambda_1 \ge\lambda_2 λ 1 ≥ λ 2 .
As ϵ \epsilon ϵ increases, Proposition 7 implies that the upper bound on revenue per unit of incremental utility becomes tighter for products selected under the worst-case demand realization. Accordingly, under a greater degree of uncertainty aversion, the firm should offer products that deliver higher consumer value per unit of revenue.
There are two questions that need to be addressed: 1) How good is the data-driven solution of (14) compared with that of the origin PLD problem? and 2) how to compute the optimal solution for (14)? In the rest of this section we address the first question, and in the next section, we discuss the second.
Statistical Guarantees of the Empirical DRO Model
We quantify the statistical loss from replacing the population DRO problem with its sample-average approximation. Let S ^ N \hat{S}_N S ^ N be an exact optimizer of the empirical problem (14). We evaluate this product line under the population distribution Q Q Q and compare it with the optimum under the same distribution:
L N = max S ∈ S R ϵ ( S ; Q ) − R ϵ ( S ^ N ; Q ) . L_N = \max_{S\in\mathcal{S}} R_{\epsilon}(S;Q) - R_{\epsilon}(\hat{S}_N;Q). L N = S ∈ S max R ϵ ( S ; Q ) − R ϵ ( S ^ N ; Q ) .
The finite-sample analysis uses the following bound on the dual integrand, where r ˉ = max i ∈ A r i \bar{r} = \max_{i\in\mathcal{A}} r_i r ˉ = max i ∈ A r i is the largest product revenue.
Lemma 2. For every product line S S S , every λ ≥ 0 \lambda\ge0 λ ≥ 0 , and every utility vector U U U ,
0 ≤ ϕ S , λ ( U ) ≤ r ˉ . 0 \le\phi_{S,\lambda}(U) \le\bar{r}. 0 ≤ ϕ S , λ ( U ) ≤ r ˉ . Moreover, the supremum over λ \lambda λ in both the population objective and the empirical objective can be restricted to [ 0 , r ˉ / ϵ ] [0,\bar{r}/\epsilon] [ 0 , r ˉ / ϵ ] .
:::`
For S ∈ L \mathcal{S} \in\mathcal{L} S ∈ L and λ ≥ 0 \lambda\ge0 λ ≥ 0 , write μ S ( λ ) = E Q [ φ S , λ ( U ) ] \mu_{\mathcal{S}}(\lambda) = \mathbb{E}_{Q}[\varphi_{\mathcal{S},\lambda}(U)] μ S ( λ ) = E Q [ φ S , λ ( U )] and let μ ^ S ( λ ) \widehat{\mu}_{\mathcal{S}}(\lambda) μ S ( λ ) denote the corresponding sample average. Define the uniform dual deviation
Z N : = sup S ∈ L sup λ ≥ 0 ∣ μ ^ S ( λ ) − μ S ( λ ) ∣ . (15) Z_N := \sup_{\mathcal{S}\in\mathcal{L}}\sup_{\lambda\ge0}\left|\widehat{\mu}_{\mathcal{S}}(\lambda)-\mu_{\mathcal{S}}(\lambda)\right|. \tag*{(15)} Z N := S ∈ L sup λ ≥ 0 sup ∣ μ S ( λ ) − μ S ( λ ) ∣ . (15)
Lemma 2 implies Z N ≤ r ˉ Z_N \le\bar{r} Z N ≤ r ˉ . For every ϵ > 0 \epsilon> 0 ϵ > 0 , the penalty − λ ϵ -\lambda\epsilon − λ ϵ cancels in the comparison of the two dual objectives, so
sup S ∈ L ∣ R ϵ ( S ; Q ) − R ^ ϵ ( S ) ∣ ≤ Z N . \sup_{\mathcal{S}\in\mathcal{L}}\left|R_{\epsilon}(\mathcal{S};Q)-\widehat{R}_{\epsilon}(\mathcal{S})\right|\le Z_N. S ∈ L sup R ϵ ( S ; Q ) − R ϵ ( S ) ≤ Z N .
For α ∈ ( 0 , 1 ) \alpha\in(0,1) α ∈ ( 0 , 1 ) , define
b N ( α ) = r ˉ min { 1 , π + log ( ∣ L ∣ / α ) 2 N } . (16) b_N(\alpha)=\bar{r}\min\left\{1,\frac{\sqrt{\pi}+\sqrt{\log(|\mathcal{L}|/\alpha)}}{\sqrt{2N}}\right\}. \tag*{(16)} b N ( α ) = r ˉ min { 1 , 2 N π + log ( ∣ L ∣/ α ) } . (16)
Theorem 1 (Finite-sample accuracy). Suppose the N N N utility vectors are drawn independently from Q Q Q , and let α ∈ ( 0 , 1 ) \alpha\in(0,1) α ∈ ( 0 , 1 ) . With probability at least 1 − α 1-\alpha 1 − α ,
Z N ≤ b N ( α ) . (17) Z_N \le b_N(\alpha). \tag*{(17)} Z N ≤ b N ( α ) . (17) The same event yields, for every ϵ > 0 \epsilon> 0 ϵ > 0 ,
∣ V N , ϵ ∗ − V ϵ ∗ ( Q ) ∣ ≤ b N ( α ) , (18) \left|V^{*}_{N,\epsilon}-V^{*}_{\epsilon}(Q)\right|\le b_N(\alpha), \tag*{(18)} V N , ϵ ∗ − V ϵ ∗ ( Q ) ≤ b N ( α ) , (18) 0 ≤ L N ≤ 2 b N ( α ) , (19) 0\le L_N\le2b_N(\alpha), \tag*{(19)} 0 ≤ L N ≤ 2 b N ( α ) , (19) where V ϵ ∗ ( Q ) = max S ∈ L R ϵ ( S ; Q ) V^{*}_{\epsilon}(Q)=\max_{\mathcal{S}\in\mathcal{L}}R_{\epsilon}(\mathcal{S};Q) V ϵ ∗ ( Q ) = max S ∈ L R ϵ ( S ; Q ) and V N , ϵ ∗ = max S ∈ L R ^ ϵ ( S ) V^{*}_{N,\epsilon}=\max_{\mathcal{S}\in\mathcal{L}}\widehat{R}_{\epsilon}(\mathcal{S}) V N , ϵ ∗ = max S ∈ L R ϵ ( S ) . The expected loss satisfies
E [ L N ] ≤ 2 r ˉ 2 N ( π + 1 2 + 1 + log ∣ L ∣ ) . (20) \mathbb{E}[L_N]\le\frac{2\bar{r}}{\sqrt{2N}}\left(\sqrt{\pi}+\frac{1}{2}+\sqrt{1+\log|\mathcal{L}|}\right). \tag*{(20)} E [ L N ] ≤ 2 N 2 r ˉ ( π + 2 1 + 1 + log ∣ L ∣ ) . (20)
Since ∣ L ∣ ≤ 2 A |\mathcal{L}|\le2^A ∣ L ∣ ≤ 2 A , both bounds remain valid when ∣ L ∣ |\mathcal{L}| ∣ L ∣ is replaced by 2 A 2^A 2 A .
The bound in (20) gives a sufficient sample size for a target expected loss due to sampling. The next section accounts for the additional optimization error when the empirical problem is solved to a prescribed tolerance.
Computational Algorithm
Although the empirical approximation error deminishes as N N N increases, [DRO-FC] with a large sample size is computationally challenging. Even its nominal counterpart, obtained by setting ϵ = 0 \epsilon=0 ϵ = 0 , is NP-hard, and robustness couples the continuous multiplier with the combinatorial product-line decision. McCormick envelopes and big-M M M bounds yield the exact formulation [DRO-MILP] in Section EC.1 of the online supplement. Its weak linear programming relaxation, however, makes [DRO-MILP] impractical beyond relatively small instances. We therefore develop a certified approximation framework for [DRO-FC] that returns a ( 1 − δ ) (1-\delta) ( 1 − δ ) -optimal solution. Throughout this section, we consider the cardinality-constrained feasible family L = { S : ∣ S ∣ ≤ p } \mathcal{L}=\{\mathcal{S}:|\mathcal{S}|\le p\} L = { S : ∣ S ∣ ≤ p } . We write S ˉ = S ∪ { 0 } \bar{\mathcal{S}}=\mathcal{S}\cup\{0\} S ˉ = S ∪ { 0 } for the offered alternatives including the outside option. For the empirical distribution, we write ϵ † = ϵ † ( Q ^ N ) = max S ∈ L W N ( S ) − N − 1 ∑ n ∈ N u ^ n 0 \epsilon^{\dagger}=\epsilon^{\dagger}(\widehat{Q}_N)=\max_{\mathcal{S}\in\mathcal{L}}W_N(\mathcal{S})-N^{-1}\sum_{n\in\mathcal{N}}\widehat{u}_{n0} ϵ † = ϵ † ( Q N ) = max S ∈ L W N ( S ) − N − 1 ∑ n ∈ N u n 0 for the critical radius in Corollary 1. We maintain 0 ≤ ϵ < ϵ † 0\le\epsilon<\epsilon^{\dagger} 0 ≤ ϵ < ϵ † , so [DRO-FC] has a positive optimal value.
To expose the two-level structure of the problem, define the functions C ( ⋅ , ⋅ ) , G ( ⋅ , ⋅ ) : L × R + → R C(\cdot,\cdot),G(\cdot,\cdot):\mathcal{L}\times\mathbb{R}_{+}\to\mathbb{R} C ( ⋅ , ⋅ ) , G ( ⋅ , ⋅ ) : L × R + → R by
C ( S , λ ) = 1 N ∑ n ∈ N min i ∈ S ˉ ( r i − λ u ^ n i ) C(\mathcal{S},\lambda)=\frac{1}{N}\sum_{n\in\mathcal{N}}\min_{i\in\bar{\mathcal{S}}}(r_i-\lambda\widehat{u}_{ni}) C ( S , λ ) = N 1 n ∈ N ∑ i ∈ S ˉ min ( r i − λ u ni )
and G ( S , λ ) = λ W N ( S ) + C ( S , λ ) G(S,\lambda) = \lambda W_N(S) + C(S,\lambda) G ( S , λ ) = λ W N ( S ) + C ( S , λ ) . Here, C ( S , λ ) C(S,\lambda) C ( S , λ ) is the average of the customer-level minima min i ∈ S ˉ ( r i − λ u ^ n i ) \min_{i\in\bar{\mathcal{S}}}(r_i-\lambda\hat{u}_{ni}) min i ∈ S ˉ ( r i − λ u ^ ni ) obtained by separating λ max j ∈ S ˉ u ^ n j \lambda\max_{j\in\bar{\mathcal{S}}}\hat{u}_{nj} λ max j ∈ S ˉ u ^ nj from the minimum in (11) , and G ( S , λ ) G(S,\lambda) G ( S , λ ) is the sample average of ϕ S , λ \phi_{S,\lambda} ϕ S , λ in (13) before the ambiguity penalty − λ ϵ -\lambda\epsilon − λ ϵ . For a fixed λ \lambda λ , let
f ( λ ) = max S ∈ L G ( S , λ ) (21) f(\lambda)=\max_{S\in\mathcal{L}}G(S,\lambda) \tag*{(21)} f ( λ ) = S ∈ L max G ( S , λ ) (21)
denote the optimal value of the product-line subproblem at multiplier λ \lambda λ . For a fixed product line S S S , write h S ( λ ) = − λ ϵ + G ( S , λ ) h_S(\lambda)=-\lambda\epsilon+G(S,\lambda) h S ( λ ) = − λ ϵ + G ( S , λ ) . By (13) , R ^ ϵ ( S ) = sup λ ≥ 0 h S ( λ ) \widehat{R}_{\epsilon}(S)=\sup_{\lambda\geq0}h_S(\lambda) R ϵ ( S ) = sup λ ≥ 0 h S ( λ ) . Write R N , ϵ F C ( S ) : = R ^ ϵ ( S ) R^{\mathrm{FC}}_{N,\epsilon}(S):=\widehat{R}_{\epsilon}(S) R N , ϵ FC ( S ) := R ϵ ( S ) and V N , ϵ ⋆ : = max S ∈ L R ^ ϵ ( S ) V^\star_{N,\epsilon}:=\max_{S\in\mathcal{L}}\widehat{R}_{\epsilon}(S) V N , ϵ ⋆ := max S ∈ L R ϵ ( S ) . It follows that h ( λ ) = − λ ϵ + f ( λ ) = max S ∈ L h S ( λ ) h(\lambda)=-\lambda\epsilon+f(\lambda)=\max_{S\in\mathcal{L}}h_S(\lambda) h ( λ ) = − λ ϵ + f ( λ ) = max S ∈ L h S ( λ ) .
Before constructing either level of the algorithm, we restrict the multiplier to a finite, data-dependent interval. For customer n n n , consider an ordered pair ( i , j ) (i,j) ( i , j ) for which product i i i has both higher revenue and higher utility than product j j j . This pair can affect the right slope of h h h at λ \lambda λ only when its revenue-to-utility ratio is strictly greater than λ \lambda λ . Accordingly, define
D n ( λ ) = max { u ^ n i − u ^ n j : i ∈ A , j ∈ A ∪ { 0 } , r i > r j , u ^ n i > u ^ n j , r i − r j u ^ n i − u ^ n j > λ } . (22) D_n(\lambda)=\max\left\{\hat{u}_{ni}-\hat{u}_{nj}:i\in\mathcal{A},\ j\in\mathcal{A}\cup\{0\},\ r_i>r_j,\ \hat{u}_{ni}>\hat{u}_{nj},\ \frac{r_i-r_j}{\hat{u}_{ni}-\hat{u}_{nj}}>\lambda\right\}. \tag*{(22)} D n ( λ ) = max { u ^ ni − u ^ nj : i ∈ A , j ∈ A ∪ { 0 } , r i > r j , u ^ ni > u ^ nj , u ^ ni − u ^ nj r i − r j > λ } . (22)
If the set in (22) is empty, we set D n ( λ ) = 0 D_n(\lambda)=0 D n ( λ ) = 0 . Averaging these customer-level bounds gives
Φ ( λ ) = 1 N ∑ n ∈ N D n ( λ ) . (23) \Phi(\lambda)=\frac{1}{N}\sum_{n\in\mathcal{N}}D_n(\lambda). \tag*{(23)} Φ ( λ ) = N 1 n ∈ N ∑ D n ( λ ) . (23)
Lemma 3 (Valid Upper Bound on λ \lambda λ ). The envelope Φ ( λ ) \Phi(\lambda) Φ ( λ ) is nonincreasing, right-continuous, and piecewise constant in λ \lambda λ . Moreover, for every S ∈ L S\in\mathcal{L} S ∈ L ,
R N , ϵ F C ( S ) = max 0 ≤ λ ≤ λ u h S ( λ ) , λ u : = min { λ ≥ 0 : Φ ( λ ) ≤ ϵ } . (24) R^{\mathrm{FC}}_{N,\epsilon}(S)=\max_{0\leq\lambda\leq\lambda^u}h_S(\lambda),\qquad\lambda^u:=\min\{\lambda\geq0:\Phi(\lambda)\leq\epsilon\}. \tag*{(24)} R N , ϵ FC ( S ) = 0 ≤ λ ≤ λ u max h S ( λ ) , λ u := min { λ ≥ 0 : Φ ( λ ) ≤ ϵ } . (24) Consequently, [DRO-FC] admits an optimal multiplier λ ⋆ ∈ [ 0 , λ u ] \lambda^\star\in[0,\lambda^u] λ ⋆ ∈ [ 0 , λ u ] .
The only breakpoints of Φ \Phi Φ are the O ( N ∣ A ∣ 2 ) O(N|\mathcal{A}|^2) O ( N ∣ A ∣ 2 ) ratios in (22) . Thus, λ u \lambda^u λ u is obtained by sorting these ratios and scanning the value immediately after each breakpoint until Φ ( λ ) ≤ ϵ \Phi(\lambda)\leq\epsilon Φ ( λ ) ≤ ϵ ; the implementation uses the next representable floating-point value to perform this right-hand scan.
The [DRO-FC] problem is therefore equivalent to
h ⋆ = max λ ∈ [ 0 , λ u ] h ( λ ) , (25) h^\star=\max_{\lambda\in[0,\lambda^u]}h(\lambda), \tag*{(25)} h ⋆ = λ ∈ [ 0 , λ u ] max h ( λ ) , (25)
where h ⋆ = V N , ϵ ⋆ h^\star=V^\star_{N,\epsilon} h ⋆ = V N , ϵ ⋆ . Our method separates the two decisions in (25) . § 5.1 first constructs an exact combinatorial solver for f ( λ ) f(\lambda) f ( λ ) at a fixed multiplier. § 5.2 then uses this solver as an oracle in a certified search over [ 0 , λ u ] [0,\lambda^u] [ 0 , λ u ] .
Set-Branching with Modular Bounds (SBMB)
Fix λ ∈ [ 0 , λ u ] \lambda\in[0,\lambda^u] λ ∈ [ 0 , λ u ] . The inner problem (21) remains difficult even though the multiplier is no longer a decision variable. A direct MILP formulation of this fixed-λ \lambda λ problem retains N ( ∣ A ∣ + 1 ) N(\lvert\mathcal{A}\rvert+1) N (∣ A ∣ + 1 ) assignment variables, N N N epigraph variables, and O ( N ∣ A ∣ ) O(N\lvert\mathcal{A}\rvert) O ( N ∣ A ∣) big-M M M and linking constraints. SBMB avoids this overhead by branching directly on product sets and bounding each node in closed form, without solving a continuous relaxation. The fixed-λ \lambda λ problem is nevertheless NP-hard: for sufficiently large λ \lambda λ , it reduces to nominal first-choice product-line design [13 ] .
SBMB keeps a feasible incumbent ( S , G b e s t ) (\mathcal{S},\mathcal{G}_{\mathrm{best}}) ( S , G best ) and a collection Q \mathcal{Q} Q of open nodes. A node is a pair ( I , F ) (\mathcal{I},\mathcal{F}) ( I , F ) of disjoint subsets of A \mathcal{A} A . Products in I \mathcal{I} I have been included, and those in F \mathcal{F} F have not yet been decided. The remaining products are excluded, so E = A ∖ ( I ∪ F ) \mathcal{E} = \mathcal{A} \setminus(\mathcal{I} \cup\mathcal{F}) E = A ∖ ( I ∪ F ) need not be stored. The root is ( I 0 , F 0 ) = ( ∅ , A ) (\mathcal{I}_0,\mathcal{F}_0) = (\varnothing,\mathcal{A}) ( I 0 , F 0 ) = ( ∅ , A ) . At any node, the residual capacity is k = p − ∣ I ∣ k = p - |\mathcal{I}| k = p − ∣ I ∣ , and its feasible descendants are I ∪ T \mathcal{I} \cup\mathcal{T} I ∪ T , where T ⊆ F \mathcal{T} \subseteq\mathcal{F} T ⊆ F and ∣ T ∣ ≤ k |\mathcal{T}| \leq k ∣ T ∣ ≤ k .
The outside option is always available, but it is not a member of I \mathcal{I} I , F \mathcal{F} F , or E \mathcal{E} E . In the code, index 0 is retained in the internal included-set array, which therefore has p + 1 p + 1 p + 1 slots. Our notation counts candidate products only and hence has ∣ I ∣ ≤ p |\mathcal{I}| \leq p ∣ I ∣ ≤ p . For any product line,
G ( S , λ ) = 1 N ∑ n ∈ N min i ∈ S ‾ { r i + λ ( max j ∈ S ‾ u ^ n j − u ^ n i ) } ≥ 0. G(\mathcal{S},\lambda) = \frac{1}{N}\sum_{n\in\mathcal{N}}\min_{i\in\overline{\mathcal{S}}}\left\{r_i+\lambda\left(\max_{j\in\overline{\mathcal{S}}}\widehat{u}_{nj}-\widehat{u}_{ni}\right)\right\}\geq0. G ( S , λ ) = N 1 n ∈ N ∑ i ∈ S min { r i + λ ( j ∈ S max u nj − u ni ) } ≥ 0.
Thus, the best singleton weakly dominates the empty line, whose value is zero. The code omits t = 0 t = 0 t = 0 whenever I = ∅ \mathcal{I} = \varnothing I = ∅ ; we retain it in (28) to state one bound for every node.
After a node is bounded, it is stored in Q Q Q as ( I , F , U ) (\mathcal{I},\mathcal{F},U) ( I , F , U ) , where U = UB n o d e ( I , F ) U = \operatorname{UB}_{\mathrm{node}}(\mathcal{I},\mathcal{F}) U = UB node ( I , F ) . The pair ( I , F ) (\mathcal{I},\mathcal{F}) ( I , F ) identifies the subproblem, and U U U determines its priority in the queue. The multiplier is fixed during an SBMB call and is therefore suppressed in the notation for UB n o d e \operatorname{UB}_{\mathrm{node}} UB node .
The bound rests on two diminishing-returns properties. Adding a product increases W N ( ⋅ ) W_N(\cdot) W N ( ⋅ ) , with smaller marginal gains for larger product lines. It decreases C ( ⋅ , λ ) C(\cdot,\lambda) C ( ⋅ , λ ) , and the magnitude of this decrease also becomes smaller as the product line grows. Lemma 4 records these properties.
Lemma 4 (Submodularity and Supermodularity). Given a fixed λ ≥ 0 \lambda\geq0 λ ≥ 0 , W N ( ⋅ ) W_N(\cdot) W N ( ⋅ ) is monotone nondecreasing and submodular , and C ( ⋅ , λ ) C(\cdot,\lambda) C ( ⋅ , λ ) is monotone nonincreasing and supermodular . That is, for every S 1 ⊆ S 2 ⊆ A \mathcal{S}_1 \subseteq\mathcal{S}_2 \subseteq\mathcal{A} S 1 ⊆ S 2 ⊆ A and j ∉ S 2 j \notin\mathcal{S}_2 j ∈ / S 2 ,
W N ( S 1 ) ≤ W N ( S 2 ) , W N ( S 1 ∪ { j } ) − W N ( S 1 ) ≥ W N ( S 2 ∪ { j } ) − W N ( S 2 ) , C ( S 1 , λ ) ≥ C ( S 2 , λ ) , C ( S 1 ∪ { j } , λ ) − C ( S 1 , λ ) ≤ C ( S 2 ∪ { j } , λ ) − C ( S 2 , λ ) . \begin{aligned}
W_N(\mathcal{S}_1) &\leq W_N(\mathcal{S}_2), \\
W_N(\mathcal{S}_1\cup\{j\})-W_N(\mathcal{S}_1) &\geq W_N(\mathcal{S}_2\cup\{j\})-W_N(\mathcal{S}_2), \\
C(\mathcal{S}_1,\lambda) &\geq C(\mathcal{S}_2,\lambda), \\
C(\mathcal{S}_1\cup\{j\},\lambda)-C(\mathcal{S}_1,\lambda) &\leq C(\mathcal{S}_2\cup\{j\},\lambda)-C(\mathcal{S}_2,\lambda).
\end{aligned} W N ( S 1 ) W N ( S 1 ∪ { j }) − W N ( S 1 ) C ( S 1 , λ ) C ( S 1 ∪ { j } , λ ) − C ( S 1 , λ ) ≤ W N ( S 2 ) , ≥ W N ( S 2 ∪ { j }) − W N ( S 2 ) , ≥ C ( S 2 , λ ) , ≤ C ( S 2 ∪ { j } , λ ) − C ( S 2 , λ ) .
At a node ( I , F ) (\mathcal{I},\mathcal{F}) ( I , F ) , the included products determine the customer-level values
u ‾ n ( I ) = max i ∈ I ∪ { 0 } u ^ n i , c ‾ n ( I , λ ) = min i ∈ I ∪ { 0 } ( r i − λ u ^ n i ) . (26) \overline{u}_n(\mathcal{I}) = \max_{i\in\mathcal{I}\cup\{0\}}\widehat{u}_{ni}, \qquad\overline{c}_n(\mathcal{I},\lambda) = \min_{i\in\mathcal{I}\cup\{0\}}(r_i-\lambda\widehat{u}_{ni}). \tag*{(26)} u n ( I ) = i ∈ I ∪ { 0 } max u ni , c n ( I , λ ) = i ∈ I ∪ { 0 } min ( r i − λ u ni ) . (26)
Thus, W N ( I ) = N − 1 ∑ n u ‾ n ( I ) W_N(\mathcal{I}) = N^{-1}\sum_n \overline{u}_n(\mathcal{I}) W N ( I ) = N − 1 ∑ n u n ( I ) and C ( I , λ ) = N − 1 ∑ n c ‾ n ( I , λ ) C(\mathcal{I},\lambda) = N^{-1}\sum_n \overline{c}_n(\mathcal{I},\lambda) C ( I , λ ) = N − 1 ∑ n c n ( I , λ ) . For each free product j ∈ F j \in\mathcal{F} j ∈ F , let m j W ( I ) m_j^W(\mathcal{I}) m j W ( I ) be its welfare gain and m j C ( I , λ ) m_j^C(\mathcal{I},\lambda) m j C ( I , λ ) its decrease in C ( ⋅ , λ ) C(\cdot,\lambda) C ( ⋅ , λ ) when added alone:
m j W ( I ) = W N ( I ∪ { j } ) − W N ( I ) = 1 N ∑ n ∈ N [ u ^ n j − u ‾ n ( I ) ] + , m j C ( I , λ ) = C ( I , λ ) − C ( I ∪ { j } , λ ) = 1 N ∑ n ∈ N [ c ‾ n ( I , λ ) − ( r j − λ u ^ n j ) ] + . (27) \begin{aligned}
m_j^W(\mathcal{I}) &= W_N(\mathcal{I}\cup\{j\})-W_N(\mathcal{I}) \\
&= \frac{1}{N}\sum_{n\in\mathcal{N}}[\widehat{u}_{nj}-\overline{u}_n(\mathcal{I})]_+, \\
m_j^C(\mathcal{I},\lambda) &= C(\mathcal{I},\lambda)-C(\mathcal{I}\cup\{j\},\lambda) \\
&= \frac{1}{N}\sum_{n\in\mathcal{N}}[\overline{c}_n(\mathcal{I},\lambda)-(r_j-\lambda\widehat{u}_{nj})]_+. \tag*{(27)}
\end{aligned} m j W ( I ) m j C ( I , λ ) = W N ( I ∪ { j }) − W N ( I ) = N 1 n ∈ N ∑ [ u nj − u n ( I ) ] + , = C ( I , λ ) − C ( I ∪ { j } , λ ) = N 1 n ∈ N ∑ [ c n ( I , λ ) − ( r j − λ u nj ) ] + . (27)
All marginals can be computed in O ( N ∣ F ∣ ) O(N|\mathcal{F}|) O ( N ∣ F ∣ ) operations. The modular component of the node bound uses only the k k k largest welfare gains and the k k k smallest decreases in C ( ⋅ , λ ) C(\cdot,\lambda) C ( ⋅ , λ ) . The code maintains these order statistics in O ( k ∣ F ∣ ) O(k|\mathcal{F}|) O ( k ∣ F ∣ ) time instead of sorting all of F \mathcal{F} F .
Consider a completion T ⊆ F \mathcal{T}\subseteq\mathcal{F} T ⊆ F with ∣ T ∣ = t |\mathcal{T}|=t ∣ T ∣ = t . By submodularity, its total welfare gain is at most the sum of the t t t largest values of m j W ( I ) m_j^W(\mathcal{I}) m j W ( I ) . For the C ( ⋅ , λ ) C(\cdot,\lambda) C ( ⋅ , λ ) term, any t t t chosen products must include one whose one-product decrease is at least the t t t -th smallest value of m j C ( I , λ ) m_j^C(\mathcal{I},\lambda) m j C ( I , λ ) . Hence, C ( I ∪ T , λ ) C(\mathcal{I}\cup\mathcal{T},\lambda) C ( I ∪ T , λ ) is at most C ( I , λ ) C(\mathcal{I},\lambda) C ( I , λ ) minus that order statistic. Proposition 8 combines the two bounds.
Proposition 8 (Node Upper Bound). At a node ( I , F ) (\mathcal{I},\mathcal{F}) ( I , F ) with residual capacity k = p − ∣ I ∣ k=p-|\mathcal{I}| k = p − ∣ I ∣ , let m [ 1 ] W ≥ m [ 2 ] W ≥ ⋯ m^{W}_{[1]} \ge m^{W}_{[2]} \ge\cdots m [ 1 ] W ≥ m [ 2 ] W ≥ ⋯ denote the values m j W ( I ) m^{W}_{j}(\mathcal{I}) m j W ( I ) , j ∈ F j \in\mathcal{F} j ∈ F , in decreasing order and m ( 1 ) C ≤ m ( 2 ) C ≤ ⋯ m^{C}_{(1)} \le m^{C}_{(2)} \le\cdots m ( 1 ) C ≤ m ( 2 ) C ≤ ⋯ the values m j C ( I , λ ) m^{C}_{j}(\mathcal{I},\lambda) m j C ( I , λ ) , j ∈ F j \in\mathcal{F} j ∈ F , in increasing order, with m ( 0 ) C = 0 m^{C}_{(0)}=0 m ( 0 ) C = 0 . For t = 0 , … , min { k , ∣ F ∣ } t=0,\ldots,\min\{k,|\mathcal{F}|\} t = 0 , … , min { k , ∣ F ∣ } , define
UB ( t ∣ I , F ) = λ ( W N ( I ) + ∑ q = 1 t m [ q ] W ) + C ( I , λ ) − m ( t ) C , \operatorname{UB}(t \mid\mathcal{I},\mathcal{F})=\lambda\left(W_N(\mathcal{I})+\sum_{q=1}^{t}m^{W}_{[q]}\right)+C(\mathcal{I},\lambda)-m^{C}_{(t)}, UB ( t ∣ I , F ) = λ ( W N ( I ) + q = 1 ∑ t m [ q ] W ) + C ( I , λ ) − m ( t ) C , UB m o d ( I , F ) = max 0 ≤ t ≤ min { k , ∣ F ∣ } UB ( t ∣ I , F ) . (28) \operatorname{UB}_{\mathrm{mod}}(\mathcal{I},\mathcal{F})=\max_{0\le t\le\min\{k,|\mathcal{F}|\}}\operatorname{UB}(t\mid\mathcal{I},\mathcal{F}). \tag*{(28)} UB mod ( I , F ) = 0 ≤ t ≤ m i n { k , ∣ F ∣ } max UB ( t ∣ I , F ) . (28) For n ∈ N n\in\mathcal{N} n ∈ N and j ∈ F j\in\mathcal{F} j ∈ F , define the customer-level net gain
η n j ( I , λ ) = λ [ u ^ n j − u ˉ n ( I ) ] + − [ c ˉ n ( I , λ ) − ( r j − λ u ^ n j ) ] + , \eta_{nj}(\mathcal{I},\lambda)=\lambda[\hat{u}_{nj}-\bar{u}_{n}(\mathcal{I})]_{+}-[\bar{c}_{n}(\mathcal{I},\lambda)-(r_j-\lambda\hat{u}_{nj})]_{+}, η nj ( I , λ ) = λ [ u ^ nj − u ˉ n ( I ) ] + − [ c ˉ n ( I , λ ) − ( r j − λ u ^ nj ) ] + , and let
UB s e p ( I , F ) = G ( I , λ ) + 1 N ∑ n ∈ N [ max j ∈ F η n j ( I , λ ) ] + , \operatorname{UB}_{\mathrm{sep}}(\mathcal{I},\mathcal{F})=G(\mathcal{I},\lambda)+\frac{1}{N}\sum_{n\in\mathcal{N}}\left[\max_{j\in\mathcal{F}}\eta_{nj}(\mathcal{I},\lambda)\right]_{+}, UB sep ( I , F ) = G ( I , λ ) + N 1 n ∈ N ∑ [ j ∈ F max η nj ( I , λ ) ] + , UB n o d e ( I , F ) = min { UB m o d ( I , F ) , UB s e p ( I , F ) } . (29) \operatorname{UB}_{\mathrm{node}}(\mathcal{I},\mathcal{F})=\min\{\operatorname{UB}_{\mathrm{mod}}(\mathcal{I},\mathcal{F}),\operatorname{UB}_{\mathrm{sep}}(\mathcal{I},\mathcal{F})\}. \tag*{(29)} UB node ( I , F ) = min { UB mod ( I , F ) , UB sep ( I , F )} . (29) The inner maximum in (29) is defined as zero when F = ∅ \mathcal{F}=\varnothing F = ∅ . Then max T ⊆ F , ∣ T ∣ ≤ k G ( I ∪ T , λ ) ≤ UB n o d e ( I , F ) \max_{\mathcal{T}\subseteq\mathcal{F},|\mathcal{T}|\le k}G(\mathcal{I}\cup\mathcal{T},\lambda)\le\operatorname{UB}_{\mathrm{node}}(\mathcal{I},\mathcal{F}) max T ⊆ F , ∣ T ∣ ≤ k G ( I ∪ T , λ ) ≤ UB node ( I , F ) .
The separable component couples the utility improvement and cost decrease at the customer–product level before maximizing over free products. It requires the same O ( N ∣ F ∣ ) O(N|\mathcal{F}|) O ( N ∣ F ∣ ) pass used to compute the marginals and is particularly effective when the two terms in G ( ⋅ , λ ) G(\cdot,\lambda) G ( ⋅ , λ ) are individually large but offset one another.
SBMB begins with a greedy incumbent. Starting from the best singleton, it repeatedly adds the product with the largest positive increment in G ( ⋅ , λ ) G(\cdot,\lambda) G ( ⋅ , λ ) until no positive increment remains or the line contains p p p products. The root triple ( I 0 , F 0 , U 0 ) (\mathcal{I}_0,\mathcal{F}_0,U_0) ( I 0 , F 0 , U 0 ) is then inserted into Q Q Q .
The search processes open nodes in decreasing order of U U U . Suppose ( I , F , U ) (\mathcal{I},\mathcal{F},U) ( I , F , U ) has the largest bound in Q Q Q . If U ≤ G b e s t U\le G_{\mathrm{best}} U ≤ G best , neither this node nor any other open node can improve the incumbent, so the algorithm terminates. Otherwise, I \mathcal{I} I is itself a feasible product line. It replaces the incumbent if I ≠ ∅ \mathcal{I}\ne\varnothing I = ∅ and G ( I , λ ) > G b e s t G(\mathcal{I},\lambda)>G_{\mathrm{best}} G ( I , λ ) > G best .
If ∣ I ∣ < p |\mathcal{I}|<p ∣ I ∣ < p and F ≠ ∅ \mathcal{F}\ne\varnothing F = ∅ , the node is not a leaf. SBMB chooses j ∗ ∈ arg max j ∈ F m j W ( I ) j^{*}\in\arg\max_{j\in\mathcal{F}}m^{W}_{j}(\mathcal{I}) j ∗ ∈ arg max j ∈ F m j W ( I ) and forms two children:
( I i n , F i n ) = ( I ∪ { j ∗ } , F ∖ { j ∗ } ) , ( I o u t , F o u t ) = ( I , F ∖ { j ∗ } ) . (\mathcal{I}^{\mathrm{in}},\mathcal{F}^{\mathrm{in}})=(\mathcal{I}\cup\{j^{*}\},\mathcal{F}\setminus\{j^{*}\}),\qquad
(\mathcal{I}^{\mathrm{out}},\mathcal{F}^{\mathrm{out}})=(\mathcal{I},\mathcal{F}\setminus\{j^{*}\}). ( I in , F in ) = ( I ∪ { j ∗ } , F ∖ { j ∗ }) , ( I out , F out ) = ( I , F ∖ { j ∗ }) .
The include child fixes j ∗ j^{*} j ∗ in the line, while the exclude child removes it from further consideration. For each child b ∈ { i n , o u t } b\in\{\mathrm{in},\mathrm{out}\} b ∈ { in , out } , SBMB recomputes U b = UB n o d e ( I b , F b ) U^{b}=\operatorname{UB}_{\mathrm{node}}(\mathcal{I}^{b},\mathcal{F}^{b}) U b = UB node ( I b , F b ) and inserts ( I b , F b , U b ) (\mathcal{I}^{b},\mathcal{F}^{b},U^{b}) ( I b , F b , U b ) into Q Q Q only if U b > G b e s t U^{b}>G_{\mathrm{best}} U b > G best . A leaf has no children. The greedy start and the choice of branching product affect runtime, but not the validity of the bounds.
Algorithm 1 Set-Branching with Modular Bounds (SBMB)
Require: Instance parameters $(r, \hat{u}, N, \mathcal{A}, p)$ with $1 \le p \le |\mathcal{A}|$ and fixed $\lambda \ge 0$
Ensure: An optimal product line $S_\lambda$ and $f(\lambda)=G(S_\lambda,\lambda)$
1: Construct the greedy feasible line described above; set $(S_\lambda,G_{\mathrm{best}})$ to this line and its value
2: Set $(\mathcal{I}_0,\mathcal{F}_0)\leftarrow(\varnothing,\mathcal{A})$ and $U_0\leftarrow \operatorname{UB}_{\mathrm{node}}(\mathcal{I}_0,\mathcal{F}_0)$; initialize $\mathcal{Q}\leftarrow\{(\mathcal{I}_0,\mathcal{F}_0,U_0)\}$
3: while $\mathcal{Q}\ne\varnothing$ do
4: Select $(\mathcal{I},\mathcal{F},U)\in\mathcal{Q}$ with maximal $U$; set $\mathcal{Q}\leftarrow\mathcal{Q}\setminus\{(\mathcal{I},\mathcal{F},U)\}$
5: if $U\le G_{\mathrm{best}}$ then
6: return $(S_\lambda,G_{\mathrm{best}})$
7: If $\mathcal{I}\ne\varnothing$ and $G(\mathcal{I},\lambda)>G_{\mathrm{best}}$, set $(S_\lambda,G_{\mathrm{best}})\leftarrow(\mathcal{I},G(\mathcal{I},\lambda))$
8: if $|\mathcal{I}|<p$ and $\mathcal{F}\ne\varnothing$ then ▷ a nonleaf node
9: Compute $m_j^W(\mathcal{I}),m_j^C(\mathcal{I},\lambda)$ for $j\in\mathcal{F}$ via {xref}`(27)`; select $j^*\leftarrow\arg\max_{j\in\mathcal{F}}m_j^W(\mathcal{I})$
10: Set the include child $(\mathcal{I}^{\mathrm{in}},\mathcal{F}^{\mathrm{in}})\leftarrow(\mathcal{I}\cup\{j^*\},\mathcal{F}\setminus\{j^*\})$
11: $U^{\mathrm{in}}\leftarrow\operatorname{UB}_{\mathrm{node}}(\mathcal{I}^{\mathrm{in}},\mathcal{F}^{\mathrm{in}})$
12: if $U^{\mathrm{in}}>G_{\mathrm{best}}$ then $\mathcal{Q}\leftarrow\mathcal{Q}\cup\{(\mathcal{I}^{\mathrm{in}},\mathcal{F}^{\mathrm{in}},U^{\mathrm{in}})\}$
13: Set the exclude child $(\mathcal{I}^{\mathrm{out}},\mathcal{F}^{\mathrm{out}})\leftarrow(\mathcal{I},\mathcal{F}\setminus\{j^*\})$
14: $U^{\mathrm{out}}\leftarrow\operatorname{UB}_{\mathrm{node}}(\mathcal{I}^{\mathrm{out}},\mathcal{F}^{\mathrm{out}})$
15: if $U^{\mathrm{out}}>G_{\mathrm{best}}$ then $\mathcal{Q}\leftarrow\mathcal{Q}\cup\{(\mathcal{I}^{\mathrm{out}},\mathcal{F}^{\mathrm{out}},U^{\mathrm{out}})\}$
16: return $(S_\lambda,G_{\mathrm{best}})$
Proposition 8 makes every pruning step valid, and each branch removes one product from F \mathcal{F} F , so the search tree is finite. When SBMB terminates, every unexplored node has an upper bound no larger than G b e s t G_{\mathrm{best}} G best ; Algorithm 1 therefore returns the exact value f ( λ ) f(\lambda) f ( λ ) .
Adaptive Parametric Search (APS)
With the exact fixed-λ \lambda λ oracle in place, it remains to maximize h h h over [ 0 , λ u ] [0,\lambda^u] [ 0 , λ u ] . For a fixed product line S S S , G ( S , ⋅ ) G(S,\cdot) G ( S , ⋅ ) is concave and piecewise linear. Its pointwise maximum over L \mathcal{L} L , however, need not be concave or convex. APS therefore does not rely on the global shape of h h h . Instead, it combines exact endpoint values with the uniform slope bounds in Lemma 5.
Lemma 5 (Slope Bounds). The function h ( λ ) = − λ ϵ + f ( λ ) h(\lambda)=-\lambda\epsilon+f(\lambda) h ( λ ) = − λ ϵ + f ( λ ) satisfies, for all 0 ≤ λ 1 < λ 2 ≤ λ u 0\le\lambda_1<\lambda_2\le\lambda^u 0 ≤ λ 1 < λ 2 ≤ λ u ,
− L − ≤ h ( λ 2 ) − h ( λ 1 ) λ 2 − λ 1 ≤ L + , (30) -L^- \le\frac{h(\lambda_2)-h(\lambda_1)}{\lambda_2-\lambda_1}\le L^+, \tag*{(30)} − L − ≤ λ 2 − λ 1 h ( λ 2 ) − h ( λ 1 ) ≤ L + , (30) where L − = ϵ L^-=\epsilon L − = ϵ , L + = N − 1 ∑ n ∈ N Δ n − ϵ L^+=N^{-1}\sum_{n\in\mathcal{N}}\Delta_n-\epsilon L + = N − 1 ∑ n ∈ N Δ n − ϵ , and Δ n = max i ∈ A ∪ { 0 } u ^ n i − u ^ n 0 \Delta_n=\max_{i\in\mathcal{A}\cup\{0\}}\hat{u}_{ni}-\hat{u}_{n0} Δ n = max i ∈ A ∪ { 0 } u ^ ni − u ^ n 0 .
If L + > 0 L^+>0 L + > 0 , fix any interval [ a , b ] ⊆ [ 0 , λ u ] [a,b]\subseteq[0,\lambda^u] [ a , b ] ⊆ [ 0 , λ u ] and define x a b = [ h ( b ) − h ( a ) + L − ( b − a ) ] / ( L + + L − ) . x_{ab}=[h(b)-h(a)+L^-(b-a)]/(L^++L^-). x ab = [ h ( b ) − h ( a ) + L − ( b − a )] / ( L + + L − ) . Then x a b ∈ [ 0 , b − a ] x_{ab}\in[0,b-a] x ab ∈ [ 0 , b − a ] and
max λ ∈ [ a , b ] h ( λ ) ≤ UB ∗ ( [ a , b ] ) : = h ( a ) + L + x a b \max_{\lambda\in[a,b]}h(\lambda)\le\operatorname{UB}^*([a,b]):=h(a)+L^+x_{ab} λ ∈ [ a , b ] max h ( λ ) ≤ UB ∗ ([ a , b ]) := h ( a ) + L + x ab = h ( b ) + L − ( b − a − x a b ) = L − h ( a ) + L + h ( b ) + L + L − ( b − a ) L + + L − . (31) =h(b)+L^-(b-a-x_{ab})=\frac{L^-h(a)+L^+h(b)+L^+L^-(b-a)}{L^++L^-}. \tag*{(31)} = h ( b ) + L − ( b − a − x ab ) = L + + L − L − h ( a ) + L + h ( b ) + L + L − ( b − a ) . (31)
The maintained condition ϵ < ϵ † \epsilon<\epsilon^\dagger ϵ < ϵ † implies L + > 0 L^+>0 L + > 0 , so the first case of Lemma 5 applies throughout Algorithm 2; the second case is included for completeness. On an interval [ a , b ] [a,b] [ a , b ] , the slope bounds give h ( λ ) ≤ h ( a ) + L + ( λ − a ) h(\lambda)\le h(a)+L^+(\lambda-a) h ( λ ) ≤ h ( a ) + L + ( λ − a ) and h ( λ ) ≤ h ( b ) + L − ( b − λ ) h(\lambda)\le h(b)+L^-(b-\lambda) h ( λ ) ≤ h ( b ) + L − ( b − λ ) . The pointwise minimum of these affine functions is a tent-shaped upper bound on h h h , whose maximum occurs at their intersection a + x a b a+x_{ab} a + x ab . APS initially calls SBMB at 0 0 0 and λ u \lambda^{u} λ u and sets I λ = { [ 0 , λ u ] } \mathcal{I}_{\lambda}=\{[0,\lambda^{u}]\} I λ = {[ 0 , λ u ]} . Every interval in I λ \mathcal{I}_{\lambda} I λ stores its exact endpoint values and carries the bound in (31) . Let ub max = max [ a , b ] ∈ I λ UB ∗ ( [ a , b ] ) \operatorname{ub}_{\max}=\max_{[a,b]\in\mathcal{I}_{\lambda}}\operatorname{UB}^{*}([a,b]) ub m a x = max [ a , b ] ∈ I λ UB ∗ ([ a , b ]) denote the largest active bound. The incumbent ( S ^ , λ ^ ) (\widehat{S},\widehat{\lambda}) ( S , λ ) provides the lower bound h b e s t = h S ^ ( λ ^ ) h_{\mathrm{best}}=h_{\widehat{S}}(\widehat{\lambda}) h best = h S ( λ ) . An interval is pruned only when its upper bound does not exceed the incumbent; hence, whenever I λ ≠ ∅ \mathcal{I}_{\lambda}\ne\varnothing I λ = ∅ , h b e s t ≤ h ⋆ ≤ ub max h_{\mathrm{best}}\le h^{\star}\le\operatorname{ub}_{\max} h best ≤ h ⋆ ≤ ub m a x . The certificate gap is therefore Γ : = ub max − h b e s t ≥ 0 \Gamma:=\operatorname{ub}_{\max}-h_{\mathrm{best}}\ge0 Γ := ub m a x − h best ≥ 0 , and APS stops once Γ ≤ δ ub max \Gamma\le\delta\operatorname{ub}_{\max} Γ ≤ δ ub m a x . If the certificate is not yet satisfied, APS selects [ a , b ] ∈ arg max [ c , d ] ∈ I λ UB ∗ ( [ c , d ] ) [a,b]\in\arg\max_{[c,d]\in\mathcal{I}_{\lambda}}\operatorname{UB}^{*}([c,d]) [ a , b ] ∈ arg max [ c , d ] ∈ I λ UB ∗ ([ c , d ]) and calls SBMB at λ n e w = ( a + b ) / 2 \lambda_{\mathrm{new}}=(a+b)/2 λ new = ( a + b ) /2 . The exact value h ( λ n e w ) h(\lambda_{\mathrm{new}}) h ( λ new ) becomes the common endpoint of the two child intervals, while the returned product line is processed through the solution pool described below. APS then replaces [ a , b ] [a,b] [ a , b ] by its two children and prunes every interval whose upper bound does not exceed h b e s t h_{\mathrm{best}} h best :
I λ ← ( I λ ∖ { [ a , b ] } ) ∪ { [ a , λ n e w ] , [ λ n e w , b ] } , I λ ← { [ c , d ] ∈ I λ : UB ∗ ( [ c , d ] ) > h b e s t } . \mathcal{I}_{\lambda}\leftarrow\left(\mathcal{I}_{\lambda}\setminus\{[a,b]\}\right)\cup\{[a,\lambda_{\mathrm{new}}],[\lambda_{\mathrm{new}},b]\},\qquad\mathcal{I}_{\lambda}\leftarrow\{[c,d]\in\mathcal{I}_{\lambda}:\operatorname{UB}^{*}([c,d])>h_{\mathrm{best}}\}. I λ ← ( I λ ∖ {[ a , b ]} ) ∪ {[ a , λ new ] , [ λ new , b ]} , I λ ← {[ c , d ] ∈ I λ : UB ∗ ([ c , d ]) > h best } .
Both children are created and assessed independently; APS does not impose unimodality on h h h .
The endpoint values support the certificate; the product lines returned by SBMB strengthen the incumbent. Once a product line is fixed, its multiplier can be optimized exactly without another combinatorial search. Although this fixed-line problem can be written as a linear program, APS does not call an LP solver. Proposition 6 identifies every value of λ \lambda λ at which a customer’s worst-case selection can change. APS therefore enumerates these breakpoints and evaluates the objective directly. For S ∈ L S\in\mathcal{L} S ∈ L , define
B S = { 0 , λ u } ∪ { r i − r j u ^ n i − u ^ n j : n ∈ N , { i , j } ⊆ S ‾ , u ^ n i ≠ u ^ n j , 0 ≤ r i − r j u ^ n i − u ^ n j ≤ λ u } , B_{S}=\{0,\lambda^{u}\}\cup\left\{\frac{r_{i}-r_{j}}{\widehat{u}_{ni}-\widehat{u}_{nj}}:n\in\mathcal{N},\ \{i,j\}\subseteq\overline{S},\ \widehat{u}_{ni}\ne\widehat{u}_{nj},\ 0\le\frac{r_{i}-r_{j}}{\widehat{u}_{ni}-\widehat{u}_{nj}}\le\lambda^{u}\right\}, B S = { 0 , λ u } ∪ { u ni − u nj r i − r j : n ∈ N , { i , j } ⊆ S , u ni = u nj , 0 ≤ u ni − u nj r i − r j ≤ λ u } ,
[ P o o l - B P ( S ) ] H S = max λ ∈ B S h S ( λ ) , λ S ∈ arg max λ ∈ B S h S ( λ ) . (32) \begin{aligned}
[\mathrm{Pool\text{-}BP}(S)]\qquad H_{S}&=\max_{\lambda\in B_{S}}h_{S}(\lambda),\qquad\lambda_{S}\in\arg\max_{\lambda\in B_{S}}h_{S}(\lambda). \tag*{(32)}
\end{aligned} [ Pool - BP ( S )] H S = λ ∈ B S max h S ( λ ) , λ S ∈ arg λ ∈ B S max h S ( λ ) . (32)
For fixed S S S , the worst-case alternative of customer n n n can change only when two terms r i − λ u ^ n i r_{i}-\lambda\widehat{u}_{ni} r i − λ u ni intersect. Because h S ( ⋅ ) h_{S}(\cdot) h S ( ⋅ ) is concave and piecewise linear, an optimum on [ 0 , λ u ] [0,\lambda^{u}] [ 0 , λ u ] is attained at one of these intersections or at an endpoint. Lemma 3 therefore gives H S = h S ( λ S ) = R N , ϵ F C ( S ) H_{S}=h_{S}(\lambda_{S})=R^{\mathrm{FC}}_{N,\epsilon}(S) H S = h S ( λ S ) = R N , ϵ FC ( S ) . Thus, [ P o o l - B P ( S ) ] [\mathrm{Pool\text{-}BP}(S)] [ Pool - BP ( S )] is an exact finite enumeration, not a solver-based subproblem. The candidate set has at most 2 + N ( ∣ S ‾ ∣ 2 ) 2+N\binom{|\overline{S}|}{2} 2 + N ( 2 ∣ S ∣ ) elements. The implementation evaluates these candidates in vectorized, bounded-memory batches and caches the exact pair ( λ S , H S ) (\lambda_{S},H_{S}) ( λ S , H S ) when a product line first enters the solution pool P \mathcal{P} P . The incumbent is S ^ ∈ arg max S ∈ P H S \widehat{S}\in\arg\max_{S\in\mathcal{P}}H_{S} S ∈ arg max S ∈ P H S , with λ ^ = λ S ^ \widehat{\lambda}=\lambda_{\widehat{S}} λ = λ S and h b e s t = H S ^ h_{\mathrm{best}}=H_{\widehat{S}} h best = H S . Algorithm 2 summarizes the complete outer procedure. A call to SBMB solves (21) exactly and returns an optimal product line at the evaluated multiplier; [ P o o l - B P ( S ) ] [\mathrm{Pool\text{-}BP}(S)] [ Pool - BP ( S )] then optimizes that line exactly over the multiplier.
Algorithm 2 Adaptive Parametric Search (APS)
Require: Instance $(r,\tilde{u},N,\mathcal{A},p)$, ambiguity radius $\epsilon \in [0,\epsilon^\dagger)$, and outer tolerance $\delta \in (0,1)$
Ensure: Incumbent pair $(\widehat{S},\widehat{\lambda})$, its value $h_{\mathrm{best}}=h_{\widehat{S}}(\widehat{\lambda})$, and absolute certificate gap $\Gamma$ satisfying $R_{N,\epsilon}^{\mathrm{FC}}(\widehat{S})=h_{\mathrm{best}}\ge (1-\delta)V_{N,\epsilon}^{\star}$
1: Compute $L^{-}\leftarrow\epsilon$, $L^{+}\leftarrow\frac{1}{N}\sum_{n\in\mathbb{N}}\Delta_n-\epsilon$, and $\lambda^{u}$ by the ratio scan over (22)–(23)
2: $(S_0,f(0))\leftarrow\operatorname{SBMB}(0)$ and $(S_u,f(\lambda^{u}))\leftarrow\operatorname{SBMB}(\lambda^{u})$
3: Record $h(0)\leftarrow f(0)$ and $h(\lambda^{u})\leftarrow-\lambda^{u}\epsilon+f(\lambda^{u})$
4: $\mathcal{P}\leftarrow\operatorname{distinct}\{S_0,S_u\}$; evaluate [Pool-BP$(S)$] once for each $S\in\mathcal{P}$
5: Choose $\widehat{S}\in\arg\max_{S\in\mathcal{P}}H_S$ and set $(\widehat{\lambda},h_{\mathrm{best}})\leftarrow(\lambda_{\widehat{S}},H_{\widehat{S}})$
6: Set $\mathcal{I}_{\lambda}\leftarrow\{[0,\lambda^{u}]\}$
7: while $\mathcal{I}_{\lambda}\ne\varnothing$ do
8: $[a,b]\leftarrow\arg\max_{[c,d]\in\mathcal{I}_{\lambda}}\operatorname{UB}^{\ast}([c,d])$
9: $\mathrm{ub}_{\max}\leftarrow\operatorname{UB}^{\ast}([a,b])$ and $\Gamma\leftarrow\mathrm{ub}_{\max}-h_{\mathrm{best}}$
10: if $\Gamma\le\delta\,\mathrm{ub}_{\max}$ then
11: return $(\widehat{S},\widehat{\lambda},h_{\mathrm{best}},\Gamma)$
12: $\lambda_{\mathrm{new}}\leftarrow(a+b)/2$ and $(S_{\mathrm{new}},f(\lambda_{\mathrm{new}}))\leftarrow\operatorname{SBMB}(\lambda_{\mathrm{new}})$
13: Record $h(\lambda_{\mathrm{new}})\leftarrow-\lambda_{\mathrm{new}}\epsilon+f(\lambda_{\mathrm{new}})$
14: if $S_{\mathrm{new}}\notin\mathcal{P}$ then
15: Evaluate [Pool-BP$(S_{\mathrm{new}})$] and set $\mathcal{P}\leftarrow\mathcal{P}\cup\{S_{\mathrm{new}}\}$
16: if $H_{S_{\mathrm{new}}}>h_{\mathrm{best}}$ then
17: $(\widehat{S},\widehat{\lambda},h_{\mathrm{best}})\leftarrow(S_{\mathrm{new}},\lambda_{S_{\mathrm{new}}},H_{S_{\mathrm{new}}})$
18: $\mathcal{I}_{\lambda}\leftarrow(\mathcal{I}_{\lambda}\setminus\{[a,b]\})\cup\{[a,\lambda_{\mathrm{new}}],[\lambda_{\mathrm{new}},b]\}$
19: $\mathcal{I}_{\lambda}\leftarrow\{[c,d]\in\mathcal{I}_{\lambda}:\operatorname{UB}^{\ast}([c,d])>h_{\mathrm{best}}\}$
20: return $(\widehat{S},\widehat{\lambda},h_{\mathrm{best}},0)$ $\triangleright$ all remaining intervals have been pruned
Each product line enters P \mathcal{P} P at most once, so its breakpoint set is evaluated once. The resulting value is the exact robust revenue of that line and hence a valid lower bound on V N , ϵ ⋆ V_{N,\epsilon}^{\star} V N , ϵ ⋆ , but it need not equal h ( λ S ) h(\lambda_S) h ( λ S ) , which also optimizes over product lines outside the pool. These fixed-line values update h b e s t h_{\mathrm{best}} h best and strengthen pruning; the exact SBMB values enter (31).
The following result establishes the end-to-end approximation guarantee and bounds the number of SBMB calls.
Theorem 2 (Optimality Guarantee). Suppose 0 < ϵ < ϵ † 0<\epsilon<\epsilon^\dagger 0 < ϵ < ϵ † and δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) . Algorithm 2 returns a feasible pair ( S ^ , λ ^ ) (\widehat{S},\widehat{\lambda}) ( S , λ ) satisfying
R N , ϵ F C ( S ^ ) = h b e s t ≥ ( 1 − δ ) V N , ϵ ⋆ R_{N,\epsilon}^{\mathrm{FC}}(\widehat{S})=h_{\mathrm{best}}\ge(1-\delta)V_{N,\epsilon}^{\star} R N , ϵ FC ( S ) = h best ≥ ( 1 − δ ) V N , ϵ ⋆ Let K = L + L − / ( L + + L − ) K=L^{+}L^{-}/(L^{+}+L^{-}) K = L + L − / ( L + + L − ) and let B B B denote the total number of SBMB calls, including the two endpoint calls. Then
B < 2 max { 1 , K λ u δ V N , ϵ ⋆ } + 1. B<2\max\left\{1,\frac{K\lambda^{u}}{\delta V_{N,\epsilon}^{\star}}\right\}+1. B < 2 max { 1 , δ V N , ϵ ⋆ K λ u } + 1.
The maximum covers the possibility that the initial interval already satisfies the stopping condition, in which case B = 2 B=2 B = 2 . For fixed instance-dependent quantities, the bound grows at rate 1 / δ 1/\delta 1/ δ . It depends on the unknown value V N , ϵ ⋆ V_{N,\epsilon}^{\star} V N , ϵ ⋆ , but the algorithm itself does not: APS stops using the observable certificate gap Γ \Gamma Γ . Section 6 reports the observed B B B for δ ∈ { 0.01 , 0.05 } \delta\in\{0.01,0.05\} δ ∈ { 0.01 , 0.05 } .
The next corollary combines this computational certificate with the finite-sample guarantee in Theorem 1.
Corollary 3 (Population Performance of APS). Under the sampling conditions of Theorem 1, fix ϵ > 0 \epsilon> 0 ϵ > 0 and δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) . If ϵ < ϵ † ( Q ^ N ) \epsilon< \epsilon^{\dagger}(\widehat{Q}_N) ϵ < ϵ † ( Q N ) , let S ^ \widehat{S} S be the product line returned by Algorithm 2; otherwise, set S ^ = ∅ \widehat{S} = \varnothing S = ∅ . Let V ϵ ⋆ ( Q ) = max S ∈ L R ϵ ( S ; Q ) V_{\epsilon}^{\star}(Q) = \max_{S \in\mathcal{L}} R_{\epsilon}(S;Q) V ϵ ⋆ ( Q ) = max S ∈ L R ϵ ( S ; Q ) . Then
E [ R ϵ ( S ^ ; Q ) ] ≥ ( 1 − δ ) V ϵ ⋆ ( Q ) − ( 2 − δ ) r ˉ 2 N ( π + 1 2 + 1 + log ∣ L ∣ ) (33) \mathbb{E}\left[R_{\epsilon}(\widehat{S};Q)\right] \ge(1-\delta)V_{\epsilon}^{\star}(Q) - (2-\delta)\frac{\bar{r}}{\sqrt{2N}}\left(\sqrt{\pi}+\frac{1}{2}+\sqrt{1+\log|\mathcal{L}|}\right) \tag*{(33)} E [ R ϵ ( S ; Q ) ] ≥ ( 1 − δ ) V ϵ ⋆ ( Q ) − ( 2 − δ ) 2 N r ˉ ( π + 2 1 + 1 + log ∣ L ∣ ) (33) where the expectation is over the N N N sampled utility vectors.
Thus, δ \delta δ controls optimization error on the empirical problem, while the expected loss in (20) controls the error from replacing the population utility distribution by the empirical sample.
Computational Experiments
Section 5 develops APS and its finite-termination certificate. We now examine the computational cost of that certificate and compare the resulting solutions with those of the direct formulation [DRO-MILP]. The experiments vary the candidate set, customer sample, cardinality bound, and ambiguity radius to identify where the two approaches begin to separate.
Experimental Design
Each product i i i has a distinct profile z i z_i z i , sampled without replacement from { 0 , 1 } 10 ∖ { 0 } \{0,1\}^{10} \setminus\{0\} { 0 , 1 } 10 ∖ { 0 } , and a price r i ∼ Uniform ( 1 , 3 ) r_i \sim\operatorname{Uniform}(1,3) r i ∼ Uniform ( 1 , 3 ) that also serves as unit revenue. We first draw a common partworth vector θ ˉ \bar{\theta} θ ˉ with independent Uniform ( − 0.75 , 0.75 ) \operatorname{Uniform}(-0.75,0.75) Uniform ( − 0.75 , 0.75 ) coordinates. Customer n n n has θ n = θ ˉ + ξ n \theta_n = \bar{\theta} + \xi_n θ n = θ ˉ + ξ n , where the coordinates of ξ n \xi_n ξ n are independently drawn from Uniform ( − 0.70 , 0.70 ) \operatorname{Uniform}(-0.70,0.70) Uniform ( − 0.70 , 0.70 ) . Normalizing the magnitude of the price coefficient to one gives u ^ n i = θ n T z i − r i \widehat{u}_{ni} = \theta_n^{\mathsf{T}}z_i-r_i u ni = θ n T z i − r i . The outside option has zero utility and revenue. The common partworths induce correlation across product utilities, while the continuous draws make utility ties a zero-probability event.
For each of 10 seeds, we generate a master instance with A = N = 200 A=N=200 A = N = 200 ; smaller instances retain the first A A A products and first N N N customers. This nesting preserves paired comparisons as the problem grows. We vary A , N ∈ { 50 , 100 , 200 } A,N \in\{50,100,200\} A , N ∈ { 50 , 100 , 200 } , p ∈ { 5 , 10 } p \in\{5,10\} p ∈ { 5 , 10 } , and ϵ ∈ { 0.25 ϵ † , 0.75 ϵ † } \epsilon\in\{0.25\epsilon^{\dagger},0.75\epsilon^{\dagger}\} ϵ ∈ { 0.25 ϵ † , 0.75 ϵ † } , where ϵ † \epsilon^{\dagger} ϵ † is the critical radius in Corollary 1. We refer to these radii as low (L) and high (H), respectively. The design contains 36 configurations and 360 instances.
We compare APS at δ ∈ { 0.01 , 0.05 } \delta\in\{0.01,0.05\} δ ∈ { 0.01 , 0.05 } with [DRO-MILP] from Section EC.1. We solve [DRO-MILP] with Gurobi 11.0.3 using one thread and a relative gap tolerance of 10 − 4 10^{-4} 1 0 − 4 . Each SBMB call uses the same relative gap tolerance. APS uses the upper bounds returned by SBMB to construct its interval bounds. The outer tolerance δ \delta δ applies to the resulting global certificate for the empirical problem. Each end-to-end run has a one-hour limit. All experiments use a Windows 10 workstation with an Intel Xeon W-2245 CPU (3.90 GHz) and 64 GB RAM. Reported times cover the complete optimization routine: [DRO-MILP] includes model construction, while APS includes computation of λ u \lambda^u λ u and all SBMB calls. Instance generation, calibration of ϵ † \epsilon^{\dagger} ϵ † , and one-time compilation are excluded.
Computational Performance
Each row of Table 1 summarizes the 10 replications of one configuration. Time and B B B , the total number of SBMB calls, are reported as arithmetic means. Solved counts the [DRO-MILP] runs that reach the prescribed 10 − 4 10^{-4} 1 0 − 4 relative gap tolerance within one hour. A time-limited run contributes 3600 seconds to the mean time. We compare the returned objective values using Δ = ( h A P S − h M I L P ) / ∣ h M I L P ∣ × 100 % \Delta= (h_{\mathrm{APS} - h_{\mathrm{MILP}})/|h_{\mathrm{MILP}}| \times100\%} Δ = ( h APS − h MILP ) /∣ h MILP ∣ × 100% , where h A P S h_{\mathrm{APS}} h APS is the objective value returned by APS and h M I L P h_{\mathrm{MILP}} h MILP is the final [DRO-MILP] incumbent objective. A positive Δ \Delta Δ favors APS.
Table 1. End-to-end comparison of APS and [DRO-MILP].
APS meets its prescribed relative tolerance on all 360 instances at both δ = 0.01 \delta= 0.01 δ = 0.01 and δ = 0.05 \delta= 0.05 δ = 0.05 , as certified by its own global bounds. [DRO-MILP] reaches its 10 − 4 10^{-4} 1 0 − 4 relative gap tolerance on 352 instances within one hour. On those instances, the objective values returned by APS and [DRO-MILP] agree to numerical precision. Among the eight time-limited [DRO-MILP] runs, APS matches the final incumbent in six and improves on it by 0.18% and 1.19% in the other two.
APS is faster in every paired run, including those in which [DRO-MILP] reaches its prescribed tolerance. The mean paired speedups are 52.9 × 52.9\times 52.9 × for δ = 0.01 \delta= 0.01 δ = 0.01 and 70.7 × 70.7\times 70.7 × for δ = 0.05 \delta= 0.05 δ = 0.05 ; the corresponding maxima are 508.0 × 508.0 \times 508.0 × and 662.4 × 662.4 \times 662.4 × . The advantage is therefore not driven by the eight time-limited benchmark runs.
Scale separates the methods most sharply. With p = 10 p = 10 p = 10 , N = 200 N = 200 N = 200 , and the low radius, the mean [DRO-MILP] times at A = 50 , 100 , 200 A = 50, 100, 200 A = 50 , 100 , 200 are 13.1, 205.6, and 2372.8 seconds, compared with 0.44, 2.1, and 160.6 seconds for APS at δ = 0.05 \delta= 0.05 δ = 0.05 . All eight [DRO-MILP] time limits occur at A = 200 A = 200 A = 200 . On the largest configuration, the mean paired objective improvement over the final [DRO-MILP] incumbent is 0.14%.
Both tolerances return the same product line, multiplier, and objective value on every instance. Reducing δ \delta δ from 0.05 to 0.01 raises the mean number of SBMB calls from 15.5 to 34.0 and increases the mean paired runtime by a factor of 1.38, tightening the certificate without changing the solution.
Remark 2 (Decomposing the Computational Gain). Table 1 reports the end-to-end performance of APS. Section EC.§ 2 of the online supplement fixes λ \lambda λ and compares SBMB with [MILP], thereby isolating the contribution of the inner solver.
Case Study on Conjoint Data
Section 6 establishes the computational performance of the proposed algorithms on synthetic instances. We now turn to two empirical questions: how the proposed model performs with new customers, and how robustness reshapes the product line and thereby produces those outcomes. The application concerns a smart vending machine whose limited capacity requires the seller to choose a small menu of meal boxes from a large collection of feasible configurations.
Data and Experimental Protocol
The data come from a choice-based conjoint survey of 45 students. Each respondent completed 10 tasks involving three meal profiles and a no-purchase option. Table 2 lists the five meal attributes. We estimate respondent-level partworths using the generalized robust conjoint method of Evgeniou et al. [8 ] . After normalizing the magnitude of the price coefficient to one, a meal’s utility equals the sum of its four non-price partworths minus its price. The estimates form a 45 × 16 45 \times16 45 × 16 matrix of non-price partworths; price enters utility directly. The survey design, raw responses, and estimated partworths are available at https://github.com/mogoooojay/Robust-PLD.git .
Table 2. Meal attributes and level indices.
We fit a kernel density estimate with bandwidth 0.5 to the respondent-level partworth vectors and use it to generate repeated instances. In each replication, we draw A + 20 A + 20 A + 20 distinct non-price profiles from the 4 4 = 256 4^4 = 256 4 4 = 256 possible combinations and independently assign each a price drawn uniformly from {¥8, ¥10, ¥12, ¥15}. The first A A A meals form the seller’s candidate set. The remaining 20 are competing alternatives, and their maximum utility defines each customer’s outside option.
For each ( A , p , N ) (A,p,N) ( A , p , N ) configuration, we conduct 100 replications. A replication uses N N N training customers and 100 independently drawn validation customers. For testing, we draw an independent sample of 10,000 partworth vectors once and hold it fixed across replications. Within each replication, all methods face the same products and customer samples. The validation sample is used only for model selection, and the test sample only for evaluation, so all reported method comparisons are paired.
We measure utility relative to the competing alternatives. For each customer, we normalize utilities as u ~ n i = u n i − u n 0 \tilde{u}_{ni}=u_{ni}-u_{n0} u ~ ni = u ni − u n 0 and set u ~ n 0 = 0 \tilde{u}_{n0}=0 u ~ n 0 = 0 . This normalization preserves within-customer utility differences and first choices. All optimization and evaluation use these normalized utilities. For any customer sample D \mathcal{D} D , buyers’ welfare is W ( S ; D ) = ∣ D ∣ − 1 ∑ n ∈ D max i ∈ S ∪ { 0 } u ~ n i W(S;\mathcal{D})=|\mathcal{D}|^{-1}\sum_{n\in\mathcal{D}}\max_{i\in S\cup\{0\}}\tilde{u}_{ni} W ( S ; D ) = ∣ D ∣ − 1 ∑ n ∈ D max i ∈ S ∪ { 0 } u ~ ni . With unit price sensitivity, W ( S ; D ) W(S;\mathcal{D}) W ( S ; D ) has a money-metric interpretation. Revenue is reported per customer, in the same monetary units as price.
The MNL-based benchmarks use a representative-consumer model constructed from the same training sample. Its attraction parameters are v ˉ i = exp ( N − 1 ∑ n = 1 N u ~ n i ) \bar{v}_i=\exp(N^{-1}\sum_{n=1}^{N}\tilde{u}_{ni}) v ˉ i = exp ( N − 1 ∑ n = 1 N u ~ ni ) , so v ˉ 0 = 1 \bar{v}_0=1 v ˉ 0 = 1 . For a product line S S S , its nominal revenue and welfare are
R M N L ( S ) = ∑ i ∈ S r i v ˉ i 1 + ∑ i ∈ S v ˉ i , U M N L ( S ) = log ( 1 + ∑ i ∈ S v ˉ i ) . R_{\mathrm{MNL}}(S)=\frac{\sum_{i\in S}r_i\bar{v}_i}{1+\sum_{i\in S}\bar{v}_i},\qquad U_{\mathrm{MNL}}(S)=\log\left(1+\sum_{i\in S}\bar{v}_i\right). R MNL ( S ) = 1 + ∑ i ∈ S v ˉ i ∑ i ∈ S r i v ˉ i , U MNL ( S ) = log ( 1 + i ∈ S ∑ v ˉ i ) .
We compare five methods under the common cardinality constraint ∣ S ∣ ≤ p |S|\le p ∣ S ∣ ≤ p :
R&T 2012 is the robust MNL model of Rusmevichientong and Topaloglu [21 ] . We use their rectangular attraction set V = ∏ i ∈ A + [ ( 1 − κ ) v ˉ i , ( 1 + κ ) v ˉ i ] \mathcal{V}=\prod_{i\in A^+}[(1-\kappa)\bar{v}_i,(1+\kappa)\bar{v}_i] V = ∏ i ∈ A + [( 1 − κ ) v ˉ i , ( 1 + κ ) v ˉ i ] , which includes the outside-option attraction.
B&M 2017 uses the robust product-line design framework of Bertsimas and Mišić [1 ] , which covers parameter uncertainty within a choice model as well as structural uncertainty across choice models. We adopt their first-choice box specification from Section 4.2 because it is the closest counterpart to our empirical first-choice model. It retains the sampled utility vectors and choice rule but allows the population weights of the sampled customer types to vary according to max { 0 , ( 1 − η ) / N } ≤ π k ≤ ( 1 + η ) / N \max\{0,(1-\eta)/N\}\le\pi^k\le(1+\eta)/N max { 0 , ( 1 − η ) / N } ≤ π k ≤ ( 1 + η ) / N , with ∑ k π k = 1 \sum_k\pi^k=1 ∑ k π k = 1 .
Nominal-FC requires no calibration. The next subsection specifies how the remaining methods are calibrated and then compares the resulting product lines on a common test market.
The ``Doing Well by Doing Good'' Mechanism
We first validate the “doing good” incentive in the robust product line design across all robust models, including R&T, B&M, and Ours, and then show that the resulting gain in buyers’ welfare is repaid in out-of-sample revenue, so that the model also “does well.” We fix ( A , p , N ) = ( 200 , 10 , 30 ) (A,p,N)=(200,10,30) ( A , p , N ) = ( 200 , 10 , 30 ) and use Figure 1 to trace each robust model across its uncertainty-parameter grid. The resulting paths connect changes in product-line composition to revenue and buyers’ welfare. Our model moves utility vectors, R&T bounds aggregate MNL attractions, and B&M reweights sampled customer types. Because ϵ / ϵ † \epsilon/\epsilon^\dagger ϵ / ϵ † , κ \kappa κ , and η \eta η measure different forms of uncertainty, their magnitudes and slopes are meaningful within a row, not across rows.
Figure 1. Revenue, welfare, and offered-product composition along the uncertainty paths.
Panel (a) evaluates each line under the nominal model from which it was constructed: first-choice for our model and B&M, and MNL for R&T. These are nominal in-sample outcomes, not robust objective values. Panel (b) evaluates every line on the common first-choice test population. Panel (c) reports the mean price of the offered products and mean utility across all offered products and test customers, measured relative to the outside option. These composition measures describe the line itself, not the products eventually purchased. The zero endpoint is added for our model and R&T. Each point is a mean over 100 replications; the bands in panels (a) and (b) are 95% percentile-bootstrap confidence intervals.
Along all three paths, stronger protection shifts the selected product line toward lower prices and higher utility relative to the outside option. The broader appeal raises purchase incidence, and by the upper end of each grid the additional purchases more than offset the decline in revenue per purchase: both out-of-sample revenue and welfare exceed their low-protection levels. The adjustment need not be monotone at every grid point, and its source differs across models.
The top row traces the proposed model. As ϵ / ϵ † \epsilon/\epsilon^\dagger ϵ / ϵ † increases from 0 to 0.85, nominal in-sample revenue falls from 7.463 to 7.227, while welfare rises from 0.914 to 1.444. Mean offered price falls from ¥8.57 to ¥8.01, and mean utility rises from −1.49 to −0.70. On the test population, purchase incidence increases from 0.809 to 0.865, more than offsetting the decline in revenue per purchase from 8.214 to 8.003. Out-of-sample revenue consequently rises from 6.647 to 6.925, alongside a welfare increase from 0.889 to 1.370. Most of the revenue gain appears at the first positive radius, whereas welfare continues to improve along the path. The dual representation in Proposition 1 explains why this movement arises naturally under [DRO-FC]: robust revenue contains the term λ W N ( S ) \lambda W_N(S) λ W N ( S ) . Thus, buyers’ welfare enters the seller’s primary robust-revenue objective rather than serving only as an ex post performance measure.
For R&T, the adjustment originates in aggregate-attraction protection. At the relevant vertex of its uncertainty set, the product-to-outside attraction ratio is scaled by ( 1 − κ ) / ( 1 + κ ) (1-\kappa)/(1+\kappa) ( 1 − κ ) / ( 1 + κ ) . Increasing κ \kappa κ therefore favors lines that retain more aggregate attraction under the adverse model. From κ = 0 \kappa=0 κ = 0 to 0.5 0.5 0.5 , mean offered price falls from ¥8.61 to ¥8.19, and mean utility rises from − 0.66 -0.66 − 0.66 to − 0.36 -0.36 − 0.36 . In the representative-consumer MNL model, in-sample revenue decreases slightly from 7.133 to 7.095, while welfare increases from 2.139 to 2.275. On the common first-choice test population, purchase incidence rises from 0.816 to 0.845 and revenue per purchase falls from 8.088 to 8.004. The increase in purchases dominates: out-of-sample revenue rises from 6.589 to 6.759, together with a welfare increase from 1.233 to 1.330. The capacity bound is binding throughout, so the change comes from product replacement rather than line expansion; Section EC.§ 3 discusses this distinction.
B&M acts instead on customer-type weights. For a fixed line, its adversary shifts probability toward sampled types that generate lower revenue, penalizing lines whose performance relies on favorable population weights. Within each B&M solve, the in-sample tie rule specified in § 7.3 invokes welfare only when robust revenue is unchanged. From η = 0.1 \eta=0.1 η = 0.1 to 4, nominal in-sample revenue falls from 7.463 to 7.239, while welfare rises from 1.013 to 1.445. Over the same path, mean offered price falls from ¥8.62 to ¥8.30, and mean utility rises from − 1.60 -1.60 − 1.60 to − 1.14 -1.14 − 1.14 . Test-market purchase incidence increases from 0.831 to 0.866, offsetting a decrease in revenue per purchase from 8.188 to 8.002. Out-of-sample revenue reaches 6.938 at η = 1 \eta=1 η = 1 and remains near 6.93 thereafter; welfare rises from 0.976 at η = 0.1 \eta=0.1 η = 0.1 to 1.372 at η = 4 \eta=4 η = 4 . Most of the adjustment occurs between η = 0.5 \eta=0.5 η = 0.5 and 1.
The three rows show that the “doing well by doing good” mechanism extends beyond a single ambiguity set. In this application, utility perturbations, aggregate-attraction protection, and customer-type reweighting all shift the selected product line toward broader appeal, although through different channels. [DRO-FC] is distinctive because its robust-revenue representation contains the explicit term λ W N ( S ) \lambda W_N(S) λ W N ( S ) , so buyers’ welfare enters the seller’s primary objective. Proposition 1 identifies this link, and Corollary 1 converts it into a formal welfare guarantee.
Out-of-Sample Comparison
We then compare the out-of-sample performance of our model against the benchmarks across varying settings. R&T, B&M, and Sumida et al., which select their uncertainty levels on the independent validation sample. Regardless of the model used to construct a product line, we score it by first-choice validation revenue and welfare. For each method, we solve the full parameter grid and retain the line with the highest validation revenue; exact revenue ties are broken by higher validation welfare and then by the larger uncertainty parameter.
We use the grids κ ∈ { 0.05 , 0.10 , 0.20 , 0.30 , 0.50 } \kappa\in\{0.05, 0.10, 0.20, 0.30, 0.50\} κ ∈ { 0.05 , 0.10 , 0.20 , 0.30 , 0.50 } , η ∈ { 0.10 , 0.20 , 0.50 , 1 , 2 , 3 , 4 } \eta\in\{0.10, 0.20, 0.50, 1, 2, 3, 4\} η ∈ { 0.10 , 0.20 , 0.50 , 1 , 2 , 3 , 4 } , and ϵ / ϵ † ∈ { 0.05 , 0.10 , 0.15 , 0.25 , 0.40 , 0.55 , 0.70 , 0.85 } \epsilon/\epsilon^{\dagger} \in\{0.05, 0.10, 0.15, 0.25, 0.40, 0.55, 0.70, 0.85\} ϵ / ϵ † ∈ { 0.05 , 0.10 , 0.15 , 0.25 , 0.40 , 0.55 , 0.70 , 0.85 } , where ϵ † \epsilon^{\dagger} ϵ † is the critical radius in Corollary 1. We exclude zero because it reproduces Nominal-FC for our model and B&M, and the nominal MNL endpoint for R&T. The B&M grid follows the positive values in Section 4.2 of their paper. At each value of η \eta η , we run the B&M local search from 50 random starts, add the exact Nominal-FC line and the line from the preceding value of η \eta η as warm starts, and retain the solution with the highest robust objective. To accommodate the common constraint ∣ S ∣ ≤ p |S| \le p ∣ S ∣ ≤ p , its one-product neighborhood allows additions and deletions as well as swaps. Exact robust-objective ties are resolved by higher in-sample buyers’ welfare and then by higher nominal in-sample revenue; this comparison uses neither validation nor test outcomes. Nominal-FC and R&T are solved exactly. At each value of ϵ \epsilon ϵ , our model is solved by APS (§ 5 ) with relative tolerance δ = 0.01 \delta= 0.01 δ = 0.01 .
The Sumida et al. benchmark is calibrated by a revenue-loss allowance rather than validation. On the supported frontier generated by R M N L ( S ) + λ U M N L ( S ) R_{\mathrm{MNL}}(S) + \lambda U_{\mathrm{MNL}}(S) R MNL ( S ) + λ U MNL ( S ) , we select the highest-utility point satisfying R M N L ( S ) ≥ 0.99 R M N L ⋆ R_{\mathrm{MNL}}(S) \ge0.99R_{\mathrm{MNL}}^{\star} R MNL ( S ) ≥ 0.99 R MNL ⋆ , where R M N L ⋆ R_{\mathrm{MNL}}^{\star} R MNL ⋆ is the exact revenue optimum under that MNL model. Thus, 1% is the permitted revenue loss under the model, not a fixed value of λ \lambda λ . The supported frontier and its revenue benchmark are computed exactly.
After calibration, we evaluate every selected product line on the common 10,000-customer first-choice test sample. The test sample plays no role in model selection.
We vary N N N , p p p , and A A A one at a time around the default setting ( A , p , N ) = ( 200 , 10 , 30 ) (A,p,N) = (200, 10, 30) ( A , p , N ) = ( 200 , 10 , 30 ) . Thus, ( A , p ) = ( 200 , 10 ) (A,p) = (200, 10) ( A , p ) = ( 200 , 10 ) when N N N varies, ( A , N ) = ( 200 , 30 ) (A,N) = (200, 30) ( A , N ) = ( 200 , 30 ) when p p p varies, and ( p , N ) = ( 10 , 30 ) (p,N) = (10, 30) ( p , N ) = ( 10 , 30 ) when A A A varies. Figure 2 reports outcome levels for all five methods. Each marker is the mean over 100 replications, and the shaded bands are 95% percentile-bootstrap confidence intervals for the mean.
Figure 2. Out-of-sample revenue and buyers’ welfare after model calibration.
Across the nine distinct configurations, our model’s mean revenue and welfare both exceed Nominal-FC in every case. It attains the highest mean revenue in six configurations and ranks first or second in mean welfare in all nine. At the default setting, its mean revenue is 6.951, narrowly above B&M at 6.947. Mean welfare is 1.304, 0.022 below R&T and above the other three methods.
The amount of training data changes the ranking. At N = 10 N = 10 N = 10 , all four alternatives to Nominal-FC yield higher revenue. R&T leads with a gain of 0.799, followed by B&M at 0.745; Sumida et al. and our model are close behind, at 0.727 and 0.725. Our model moves into first place at N = 30 N = 30 N = 30 and remains there at N = 50 N = 50 N = 50 and 100, although B&M is close at each of these sample sizes. Its gain over Nominal-FC narrows from 0.725 at N = 10 N = 10 N = 10 to 0.074 at N = 100 N = 100 N = 100 as the empirical distribution becomes more informative. The two MNL-based benchmarks benefit most from the smallest sample, but their revenue gaps turn negative at N = 50 N = 50 N = 50 and 100. Thus, the aggregate MNL approach is most competitive with limited data, whereas the individual-level utility information becomes more valuable as N N N grows.
The apparent drop in B&M welfare is a calibration effect. From N = 30 N = 30 N = 30 to N = 50 N = 50 N = 50 , validation selects η = 4 \eta= 4 η = 4 less often (79 versus 63 replications), and mean welfare falls from 1.258 to 1.175 while mean revenue rises from 6.947 to 7.017. At every fixed η \eta η , welfare instead increases. Figure 2 therefore reports calibrated, rather than fixed-parameter, performance.
Our model’s advantage over Nominal-FC also grows with the size of the feasible design space. Its revenue gain rises from 0.025 at p = 1 p = 1 p = 1 to 0.304 at p = 10 p = 10 p = 10 , and from 0.163 at A = 50 A = 50 A = 50 to 0.304 at A = 200 A = 200 A = 200 . Sumida et al. leads at A = 50 A = 50 A = 50 , B&M leads narrowly at A = 100 A = 100 A = 100 , and our model leads at A = 200 A = 200 A = 200 . Larger values of p p p and A A A give the seller more scope to fit a nominal line to sample-specific preferences and, correspondingly, create more value from distributional protection. The revenue gains are accompanied by strong welfare performance: our model leads both measures at N = 100 N = 100 N = 100 and at p = 1 , 2 , 5 p = 1, 2, 5 p = 1 , 2 , 5 , and ranks first or second in welfare elsewhere. Section 7.2 next examines how the joint improvement arises.
The outperformance of Sumida et al. over Nominal-FC provides further support for the revenue–welfare alignment. Their model places greater weight on buyers’ welfare than Nominal-FC does when selecting the product line, which is the “doing good” incentive. That emphasis improves both out-of-sample revenue and buyers’ welfare, which is the “doing well” payoff in market performance.
Conclusion
This paper studies product line design when customer utilities are uncertain. A DRO model is formulated to maximize worst-case expected revenue over an ℓ 1 \ell_1 ℓ 1 -Wasserstein ball around a nominal utility distribution. The analysis of the dual reveals a “doing well by doing good” mechanism: protecting revenue against utility uncertainty raises buyers’ welfare, and that welfare in turn supports revenue. Under the MNL nominal with no cardinality constraint, the higher welfare is achieved by expanding the revenue-ordered assortment as the robustness radius grows. Under the empirical nominal, robustness shifts the line toward lower-priced products with greater utility relative to the outside option. We also provide statistical guarantees on the revenue loss incurred when the model is applied to estimated or sampled utilities. The conjoint study shows the mechanism in the data: the robust line improves both out-of-sample revenue and buyers’ welfare over the nominal benchmark in every configuration. Our adaptive parametric search algorithm certifies that the returned product line attains at least a ( 1 − δ ) (1 - \delta) ( 1 − δ ) fraction of the empirical robust optimum. We separately bound its expected robust-revenue loss relative to the population optimum, accounting for both sampling error and the optimization tolerance. On 360 instances it is 70.7× faster on average and up to 662.4× faster than the mixed-integer formulation.
Three directions remain open. The first is a DRO formulation for choice models beyond random utility maximization. The second is attribute-level product line design, in which the decision is the attribute profile of each variant rather than a subset of a candidate list. The third is whether the “doing well by doing good” mechanism extends to other applications of robust models.
Appendix
We derive [DRO-MILP], an exact mixed-integer linear reformulation of [DRO-FC]. Let binary decision variables x ∈ B A + 1 \boldsymbol{x} \in\mathbb{B}^{A+1} x ∈ B A + 1 represent the product line, where x i = 1 x_i = 1 x i = 1 if alternative i ∈ A + i \in A^+ i ∈ A + is offered and x i = 0 x_i = 0 x i = 0 otherwise. The feasible region of x \boldsymbol{x} x , denoted by X \mathcal{X} X , is in one-to-one correspondence with the feasible family L \mathcal{L} L . Under the cardinality restriction used in § 5 , L = { S ⊆ A : ∣ S ∣ ≤ p } \mathcal{L} = \{S \subseteq A : |S| \le p\} L = { S ⊆ A : ∣ S ∣ ≤ p } , and the corresponding decision space is
X = { x ∈ B A + 1 : x 0 = 1 , ∑ i ∈ A + x i ≤ p + 1 } . \mathcal{X} = \left\{ \boldsymbol{x} \in\mathbb{B}^{A+1} : x_0 = 1,\ \sum_{i \in A^+} x_i \le p + 1 \right\}. X = { x ∈ B A + 1 : x 0 = 1 , i ∈ A + ∑ x i ≤ p + 1 } .
With these definitions, the robust PLD problem can be reformulated as the following MIP:
max λ ≥ 0 , x ∈ X − λ ϵ + 1 N ( ∑ n ∈ N s n + λ ∑ n ∈ N ∑ i ∈ A + u ^ n i y n i ) s.t. s n ≤ r i − λ u ^ n i + C ‾ n ( 1 − x i ) , ∀ n ∈ N , ∀ i ∈ A + , ∑ i ∈ A + y n i = 1 , ∀ n ∈ N , y n i ≤ x i , ∀ n ∈ N , ∀ i ∈ A + , y ≥ 0. (34) \begin{aligned}
\max_{\lambda\ge0,\ \boldsymbol{x} \in\mathcal{X}}\quad&-\lambda\epsilon+ \frac{1}{N}\left(\sum_{n \in\mathcal{N}} s_n + \lambda\sum_{n \in\mathcal{N}}\sum_{i \in A^+} \hat{u}_{ni}y_{ni}\right) \\
\text{s.t.}\quad&s_n \le r_i - \lambda\hat{u}_{ni} + \overline{C}_n(1-x_i), &&\forall n \in\mathcal{N},\ \forall i \in A^+,\\
&\sum_{i \in A^+} y_{ni} = 1, &&\forall n \in\mathcal{N},\\
&y_{ni} \le x_i, &&\forall n \in\mathcal{N},\ \forall i \in A^+,\\
&\boldsymbol{y} \ge0. \tag*{(34)}
\end{aligned} λ ≥ 0 , x ∈ X max s.t. − λ ϵ + N 1 ( n ∈ N ∑ s n + λ n ∈ N ∑ i ∈ A + ∑ u ^ ni y ni ) s n ≤ r i − λ u ^ ni + C n ( 1 − x i ) , i ∈ A + ∑ y ni = 1 , y ni ≤ x i , y ≥ 0. ∀ n ∈ N , ∀ i ∈ A + , ∀ n ∈ N , ∀ n ∈ N , ∀ i ∈ A + , (34)
Constraint (EC.2) enforces that s n = min i ∈ S ˉ { r i − λ u ^ n i } s_n = \min_{i \in\bar{S}}\{r_i-\lambda\hat{u}_{ni}\} s n = min i ∈ S ˉ { r i − λ u ^ ni } at optimality, where C ‾ n \overline{C}_n C n is a constant large enough to deactivate the constraint for products that are not offered. The variables y ∈ R N × ( A + 1 ) \boldsymbol{y} \in\mathbb{R}^{N \times(A+1)} y ∈ R N × ( A + 1 ) represent customer choice across N N N samples. Constraints (EC.3) and (EC.4) ensure that each customer allocates one unit of choice among the offered alternatives (including the outside option). Although y \boldsymbol{y} y is declared continuous, the formulation is exact in value: for fixed ( x , λ ) (\boldsymbol{x}, \lambda) ( x , λ ) , the welfare term λ ∑ i ∈ A + u ^ n i y n i \lambda\sum_{i \in A^+}\hat{u}_{ni}y_{ni} λ ∑ i ∈ A + u ^ ni y ni is a linear function maximized over the polytope { y n ≥ 0 : ∑ i ∈ A + y n i = 1 , y n i ≤ x i } \{y_n \ge0 : \sum_{i \in A^+} y_{ni} = 1, y_{ni} \le x_i\} { y n ≥ 0 : ∑ i ∈ A + y ni = 1 , y ni ≤ x i } , whose vertices are integral; its maximum equals λ max i ∈ S ˉ u ^ n i \lambda\max_{i \in\bar{S}}\hat{u}_{ni} λ max i ∈ S ˉ u ^ ni and is attained by placing all mass of y n y_n y n on a utility-maximizing offered alternative. Utility ties leave the optimal value unchanged. because tied alternatives carry the same coefficient u ^ n i \hat{u}_{ni} u ^ ni . Averaging over customers, the optimal value of the MIP equals the [DRO-FC] value V N , ϵ ⋆ V^{\star}_{N,\epsilon} V N , ϵ ⋆ .
Next, we apply a standard linearization technique to the bilinear term λ y n i \lambda y_{ni} λ y ni . By Lemma 3, [DRO-FC] admits an optimal multiplier in [ 0 , λ u ] [0,\lambda^{u}] [ 0 , λ u ] , which we use as the McCormick range. Introducing auxiliary variables ρ n i \rho_{ni} ρ ni in place of λ y n i \lambda y_{ni} λ y ni yields the following mixed-integer linear program:
\begin{aligned}
\text{\[DRO-MILP\]}\qquad\max_{\lambda\in[0,\lambda^{u}],\,x\in\mathcal{X}} \quad&-\lambda\epsilon+\frac{1}{N}\sum_{n\in\mathcal{N}}\left(s_n+\sum_{i\in A^{+}}\hat{u}_{ni}\rho_{ni}\right)\\
\text{s.t.}\quad&\text{\{xref\}`(EC.2)`--\{xref\}`(EC.4)`},\\
&0\leq\rho_{ni}\leq\lambda^{u}y_{ni}, &&\forall n\in\mathcal{N},\ \forall i\in A^{+},\\
&\lambda^{u}(y_{ni}-1)+\lambda\leq\rho_{ni}\leq\lambda, &&\forall n\in\mathcal{N},\ \forall i\in A^{+},\\
&\sum_{i\in A^{+}}\rho_{ni}=\lambda, &&\forall n\in\mathcal{N}. \tag*{(35)}
\end{aligned}
Constraints (EC.7)--(EC.8) are the McCormick envelope of ρ n i = λ y n i \rho_{ni}=\lambda y_{ni} ρ ni = λ y ni over λ ∈ [ 0 , λ u ] \lambda\in[0,\lambda^{u}] λ ∈ [ 0 , λ u ] , y n i ∈ [ 0 , 1 ] y_{ni}\in[0,1] y ni ∈ [ 0 , 1 ] . Constraint (EC.9) is obtained by multiplying the assignment constraint (EC.3) by λ \lambda λ ; it is not implied by the McCormick system alone and serves two purposes. First, it strengthens the LP relaxation by linking the auxiliary variables ρ n i \rho_{ni} ρ ni across products for each customer. Second, it makes the linearization exact in value: because continuous y y y admits fractional points at which the McCormick system alone permits ∑ i ∈ A + u ^ n i ρ n i \sum_{i\in A^{+}}\hat{u}_{ni}\rho_{ni} ∑ i ∈ A + u ^ ni ρ ni to exceed the bilinear value, [DRO-MILP] without (EC.9) is a strict relaxation in general.
We now verify that [DRO-MILP] is exact. Fix any feasible solution of [DRO-MILP] with product line S = { i ∈ A : x i = 1 } S=\{i\in A:x_i=1\} S = { i ∈ A : x i = 1 } . Constraints (EC.7) and (EC.4) give ρ n i ≤ λ u y n i ≤ λ u x i \rho_{ni}\leq\lambda^{u}y_{ni}\leq\lambda^{u}x_i ρ ni ≤ λ u y ni ≤ λ u x i , so ρ n i = 0 \rho_{ni}=0 ρ ni = 0 whenever x i = 0 x_i=0 x i = 0 . If λ > 0 \lambda>0 λ > 0 , constraint (EC.9) makes { ρ n i / λ } i \{\rho_{ni}/\lambda\}_i { ρ ni / λ } i a convex-combination weight vector supported on S ˉ \bar{S} S ˉ , whence
∑ i ∈ A + u ^ n i ρ n i ≤ λ max i ∈ S ˉ u ^ n i . \sum_{i\in A^{+}}\hat{u}_{ni}\rho_{ni}\leq\lambda\max_{i\in\bar{S}}\hat{u}_{ni}. i ∈ A + ∑ u ^ ni ρ ni ≤ λ i ∈ S ˉ max u ^ ni .
if λ = 0 \lambda=0 λ = 0 , (EC.9) forces ρ n = 0 \boldsymbol{\rho}_n=\boldsymbol{0} ρ n = 0 and the same bound holds trivially. Combined with s n ≤ min i ∈ S ˉ ( r i − λ u ^ n i ) s_n\leq\min_{i\in\bar{S}}(r_i-\lambda\hat{u}_{ni}) s n ≤ min i ∈ S ˉ ( r i − λ u ^ ni ) from (EC.2), every feasible objective value is at most max S ∈ L , λ ∈ [ 0 , λ u ] { − λ ϵ + λ W N ( S ) + C ( S , λ ) } = V N , ϵ ⋆ \max_{S\in\mathcal{L},\,\lambda\in[0,\lambda^{u}]}\{-\lambda\epsilon+\lambda W_N(S)+C(S,\lambda)\}=V^{\star}_{N,\epsilon} max S ∈ L , λ ∈ [ 0 , λ u ] { − λ ϵ + λ W N ( S ) + C ( S , λ )} = V N , ϵ ⋆ , using Lemma 3 for the restriction of λ \lambda λ to [ 0 , λ u ] [0,\lambda^{u}] [ 0 , λ u ] . Conversely, the value V N , ϵ ⋆ V^{\star}_{N,\epsilon} V N , ϵ ⋆ is attained by taking an optimal ( S ⋆ , λ ⋆ ) (S^{\star},\lambda^{\star}) ( S ⋆ , λ ⋆ ) , setting binary y n i y_{ni} y ni to select a utility-maximizing alternative in S ⋆ ∪ { 0 } S^{\star}\cup\{0\} S ⋆ ∪ { 0 } for each n n n , and setting ρ n i = λ ⋆ y n i \rho_{ni}=\lambda^{\star}y_{ni} ρ ni = λ ⋆ y ni , which satisfies (EC.7)--(EC.9). Hence the optimal value of [DRO-MILP] equals V N , ϵ ⋆ V^{\star}_{N,\epsilon} V N , ϵ ⋆ .
With the λ \lambda λ range from Lemma 3, the Big-M constants can be set as
C ˉ n = max 0 ≤ λ ≤ λ u { max i ∈ A + { r i − λ u ^ n i } − min j ∈ A + { r j − λ u ^ n j } } \bar{C}_n=\max_{0\leq\lambda\leq\lambda^{u}}\left\{\max_{i\in A^{+}}\{r_i-\lambda\hat{u}_{ni}\}-\min_{j\in A^{+}}\{r_j-\lambda\hat{u}_{nj}\}\right\} C ˉ n = 0 ≤ λ ≤ λ u max { i ∈ A + max { r i − λ u ^ ni } − j ∈ A + min { r j − λ u ^ nj } }
for each n ∈ N n\in\mathcal{N} n ∈ N .
The benchmark implementation used to generate Table 1 solves an algebraically equivalent variant that folds the welfare term into the epigraph constraints, replacing (EC.2) by s n ≤ r i + ∑ j ∈ A + u ^ n j ρ n j − λ u ^ n i + C ˉ n ( 1 − x i ) s_n\leq r_i+\sum_{j\in A^{+}}\hat{u}_{nj}\rho_{nj}-\lambda\hat{u}_{ni}+\bar{C}_n(1-x_i) s n ≤ r i + ∑ j ∈ A + u ^ nj ρ nj − λ u ^ ni + C ˉ n ( 1 − x i ) so that the objective carries only 1 N ∑ n s n \frac{1}{N}\sum_n s_n N 1 ∑ n s n . The epigraph variables remain free. Apart from this algebraic rearrangement, the implementation uses the continuous assignment variables, the McCormick system (EC.7)--(EC.8), and the aggregation constraint (EC.9) exactly as displayed above. No first-choice ordering inequalities or nonempty-line restriction are imposed.
To isolate the contribution of SBMB to the speedup in Table 1 , we fix λ \lambda λ and compare SBMB with a direct mixed-integer linear formulation of the same subproblem. We use the product-line variables x ∈ X x \in\mathcal{X} x ∈ X from Section EC.§ 1 , continuous assignment variables y \mathbf{y} y , and free epigraph variables s \mathbf{s} s :
[ M I L P ] max x ∈ X , y ≥ 0 , s ∈ R N 1 N ∑ n ∈ N ( s n + λ ∑ i ∈ A + u ^ n i y n i ) s.t. s n ≤ r i − λ u ^ n i + C ‾ n ( λ ) ( 1 − x i ) , ∀ n ∈ N , i ∈ A + , ∑ i ∈ A + y n i = 1 , ∀ n ∈ N , y n i ≤ x i , ∀ n ∈ N , i ∈ A + . (36) \begin{aligned}
[\mathrm{MILP}]\quad&\max_{x\in\mathcal{X},\,y\geq0,\,s\in\mathbb{R}^{N}} \frac{1}{N}\sum_{n\in\mathcal{N}}\left(s_n+\lambda\sum_{i\in\mathcal{A}^{+}}\hat{u}_{ni}y_{ni}\right) \\
\text{s.t.}\quad&s_n\leq r_i-\lambda\hat{u}_{ni}+\overline{C}_n(\lambda)(1-x_i), &&\forall n\in\mathcal{N},\ i\in\mathcal{A}^{+},\\
&\sum_{i\in\mathcal{A}^{+}}y_{ni}=1, &&\forall n\in\mathcal{N},\\
&y_{ni}\leq x_i, &&\forall n\in\mathcal{N},\ i\in\mathcal{A}^{+}. \tag*{(36)}
\end{aligned} [ MILP ] s.t. x ∈ X , y ≥ 0 , s ∈ R N max N 1 n ∈ N ∑ ( s n + λ i ∈ A + ∑ u ^ ni y ni ) s n ≤ r i − λ u ^ ni + C n ( λ ) ( 1 − x i ) , i ∈ A + ∑ y ni = 1 , y ni ≤ x i , ∀ n ∈ N , i ∈ A + , ∀ n ∈ N , ∀ n ∈ N , i ∈ A + . (36)
Here, C ‾ n ( λ ) \overline{C}_n(\lambda) C n ( λ ) deactivates (EC.11) for alternatives outside the product line; the implementation uses
C ‾ n ( λ ) = 1 + max i ∈ A + { r i − λ u ^ n i } − min i ∈ A + { r i − λ u ^ n i } . \overline{C}_n(\lambda)=1+\max_{i\in\mathcal{A}^{+}}\{r_i-\lambda\hat{u}_{ni}\}-\min_{i\in\mathcal{A}^{+}}\{r_i-\lambda\hat{u}_{ni}\}. C n ( λ ) = 1 + i ∈ A + max { r i − λ u ^ ni } − i ∈ A + min { r i − λ u ^ ni } .
At optimality, (EC.11) recovers the customer-level minimum in C ( S , λ ) C(S,\lambda) C ( S , λ ) and (EC.12)–(EC.13) recover the maximum in W N ( S ) W_N(S) W N ( S ) . Thus [\mathrm{MILP}] and SBMB both compute f ( λ ) = max S ∈ L G ( S , λ ) f(\lambda)=\max_{S\in\mathcal{L}}G(S,\lambda) f ( λ ) = max S ∈ L G ( S , λ ) . Fixing λ \lambda λ makes − λ ϵ -\lambda\epsilon − λ ϵ constant and eliminates the need for McCormick variables.
We use the complete grid and all 10 seeds from § 6.1 : A , N ∈ { 50 , 100 , 200 } A,N\in\{50,100,200\} A , N ∈ { 50 , 100 , 200 } , p ∈ { 5 , 10 } p\in\{5,10\} p ∈ { 5 , 10 } , and ϵ ∈ { 0.25 ϵ † , 0.75 ϵ † } \epsilon\in\{0.25\epsilon^{\dagger},0.75\epsilon^{\dagger}\} ϵ ∈ { 0.25 ϵ † , 0.75 ϵ † } . We solve each instance at λ / λ u ∈ { 0.25 , 0.50 , 1.00 } \lambda/\lambda^{u}\in\{0.25,0.50,1.00\} λ / λ u ∈ { 0.25 , 0.50 , 1.00 } , for 1,080 paired problems.
[\mathrm{MILP}] uses Gurobi 11.0.3 with one thread. Both methods use a relative optimality tolerance of 10 − 4 10^{-4} 1 0 − 4 and no time limit. The timing includes [\mathrm{MILP}] model construction, which would recur at every call within a parametric search, but excludes shared preprocessing and one-time compilation. Table EC.Table 1 reports mean times over the 10 seeds.
[\mathrm{MILP}] and SBMB reach the tolerance on all 1,080 problems with identical objective values. SBMB is faster in 1,065 paired runs and in 107 of the 108 comparisons of configuration means. The exception is A = N = 200 A=N=200 A = N = 200 , p = 10 p=10 p = 10 , ϵ = 0.25 ϵ † \epsilon=0.25\epsilon^{\dagger} ϵ = 0.25 ϵ † , and λ / λ u = 0.50 \lambda/\lambda^{u}=0.50 λ / λ u = 0.50 : 22.60 seconds for SBMB versus 20.57 seconds for [\mathrm{MILP}]. The ratios of total [\mathrm{MILP}] time to total SBMB time are 12.70, 2.25, and 3.42 at λ / λ u = 0.25 \lambda/\lambda^{u}=0.25 λ / λ u = 0.25 , 0.50, and 1.00, respectively.
Nestedness and Welfare–Revenue Alignment under Capacity Constraints
A cardinality constraint can overturn assortment nestedness, but it does not remove the welfare term from the robust revenue of a fixed product line in [\mathrm{DRO\text{-}FC}].
Nestedness Need Not Survive a Cardinality Constraint
Corollary 3.3 of Rusmevichientong and Topaloglu [21 ] and Proposition 6 of Désir et al. [6 ] guarantee nested unconstrained optimizers for nested uncertainty sets. The following examples show why neither conclusion extends to L p = { S ⊆ A : ∣ S ∣ ≤ p } \mathcal{L}_p=\{S\subseteq\mathcal{A}:|S|\leq p\} L p = { S ⊆ A : ∣ S ∣ ≤ p } .
Table EC.1. Mean solution times (seconds) for the fixed-λ \lambda λ subproblem.
Robust MNL
In the model of Rusmevichientong and Topaloglu [21 ] , v 0 = 1 v_0 = 1 v 0 = 1 is the no-purchase attraction and
R ( S , v ) = ∑ i ∈ S r i v i v 0 + ∑ i ∈ S v i . R(S,v) = \frac{\sum_{i \in S} r_i v_i}{v_0 + \sum_{i \in S} v_i}. R ( S , v ) = v 0 + ∑ i ∈ S v i ∑ i ∈ S r i v i .
For a box V V V , let S p ∗ ( V ) S_p^*(V) S p ∗ ( V ) maximize min v ∈ V R ( S , v ) \min_{v \in V} R(S,v) min v ∈ V R ( S , v ) over L p \mathcal{L}_p L p . We take A = 4 A = 4 A = 4 , p = 2 p = 2 p = 2 , r = ( 10 , 8 , 6 , 5 ) r = (10, 8, 6, 5) r = ( 10 , 8 , 6 , 5 ) , and the two boxes in Table EC.Table 2 . The inclusion V ′ ⊂ V V' \subset V V ′ ⊂ V is strict.
Table EC.2. Nested rectangular uncertainty sets in the robust-MNL counterexample.
By Lemma 3.7 of Rusmevichientong and Topaloglu [21 ] , it suffices to evaluate the extreme points of each box. Table EC.3 reports the resulting worst-case revenue for every nonempty line in L 2 \mathcal{L}_2 L 2 .
Table EC.3. Worst-case MNL revenue for every nonempty line with ∣ S ∣ ≤ 2 |S| \le2 ∣ S ∣ ≤ 2 ; bold starred entries are optimal.
The unique constrained optima S p ∗ ( V ) = { 3 , 4 } S_p^*(V)=\{3,4\} S p ∗ ( V ) = { 3 , 4 } and S p ∗ ( V ′ ) = { 1 , 2 } S_p^*(V')=\{1,2\} S p ∗ ( V ′ ) = { 1 , 2 } are disjoint. Without the capacity limit, the optima are { 1 , 2 , 3 , 4 } \{1,2,3,4\} { 1 , 2 , 3 , 4 } under V V V and { 1 , 2 } \{1,2\} { 1 , 2 } under V ′ V' V ′ , consistent with Corollary 3.3.
Robust Markov Chain
In the model of Désir et al. [6 ] , α i > 0 \alpha_i>0 α i > 0 is the arrival probability at product i i i , and ρ i j \rho_{ij} ρ ij is the probability of moving from an unavailable product i i i to product j j j . We use α \alpha α for the arrival vector, which they denote by λ \lambda λ , to distinguish it from our dual multiplier. For a fixed line S S S ,
R M C ( S ; α , ρ ) = α ⊤ v ( ρ ) , v i ( ρ ) = { r i , i ∈ S , ∑ j ∈ A ρ i j v j ( ρ ) , i ∉ S . R^{\mathrm{MC}}(S;\alpha,\rho)=\alpha^\top v(\rho), \qquad v_i(\rho)=\begin{cases}r_i, & i\in S,\\ \sum_{j\in A}\rho_{ij}v_j(\rho), & i\notin S.\end{cases} R MC ( S ; α , ρ ) = α ⊤ v ( ρ ) , v i ( ρ ) = { r i , ∑ j ∈ A ρ ij v j ( ρ ) , i ∈ S , i ∈ / S .
The outside transition is ρ i 0 = 1 − ∑ j ∈ A ρ i j \rho_{i0}=1-\sum_{j\in A}\rho_{ij} ρ i 0 = 1 − ∑ j ∈ A ρ ij . We impose ρ i i = 0 \rho_{ii}=0 ρ ii = 0 and ∑ j ρ i j ≤ 0.99 \sum_j\rho_{ij}\le0.99 ∑ j ρ ij ≤ 0.99 , so every admissible row satisfies the strict condition in Assumption 2 of Désir et al. [6 ] .
Again take A = 4 A=4 A = 4 , p = 2 p=2 p = 2 , and r = ( 10 , 8 , 6 , 5 ) r=(10,8,6,5) r = ( 10 , 8 , 6 , 5 ) . Table EC.4 defines two row-wise uncertainty sets. The arrival coordinates lie in the displayed intervals and satisfy ∑ i α i ≤ 1 \sum_i\alpha_i\le1 ∑ i α i ≤ 1 . Transition rows vary independently; each off-diagonal coordinate has upper bound one, subject to the common row-mass bound 0.99. We write l i l_i l i for the lower-bound vector of row i i i . The smaller set raises selected arrival and transition lower bounds, so U M C ′ ⊂ U M C U^{\mathrm{MC}'}\subset U^{\mathrm{MC}} U MC ′ ⊂ U MC .
Table EC.4. Nested row-wise uncertainty sets in the robust Markov-chain counterexample. Transition lower bounds are listed in product order ( 1 , 2 , 3 , 4 ) (1,2,3,4) ( 1 , 2 , 3 , 4 ) .
Lemma EC.1 (Lower-Bound Worst Case). For either uncertainty set in Table EC.4 and any fixed S S S , the balance equations have a unique nonnegative solution, and
min ( α , ρ ) R M C ( S ; α , ρ ) = ( α l ) ⊤ v ( l ) , \min_{(\alpha,\rho)}R^{\mathrm{MC}}(S;\alpha,\rho)=(\alpha^l)^\top v(l), ( α , ρ ) min R MC ( S ; α , ρ ) = ( α l ) ⊤ v ( l ) ,
where α l \alpha^{l} α l and l l l are the corresponding arrival and transition lower bounds.
Proof. For fixed ρ \rho ρ , let T ρ T_{\rho} T ρ denote the mapping on the right-hand side of the balance equations. Its contraction modulus under the sup norm is at most 0.99, so v ( ρ ) v(\rho) v ( ρ ) is unique and nonnegative. The mapping is coordinatewise nondecreasing in both its argument and ρ \rho ρ . Iteration from 0 \mathbf{0} 0 therefore gives v ( l ) ≤ v ( ρ ) v(l) \le v(\rho) v ( l ) ≤ v ( ρ ) . Since α ≥ α l \alpha\ge\alpha^{l} α ≥ α l and v ( ρ ) ≥ 0 v(\rho) \ge0 v ( ρ ) ≥ 0 ,
α ⊤ v ( ρ ) ≥ ( α l ) ⊤ v ( ρ ) ≥ ( α l ) ⊤ v ( l ) . \alpha^{\top}v(\rho) \ge(\alpha^{l})^{\top}v(\rho) \ge(\alpha^{l})^{\top}v(l). α ⊤ v ( ρ ) ≥ ( α l ) ⊤ v ( ρ ) ≥ ( α l ) ⊤ v ( l ) .
The lower bounds are feasible, so equality is attained at ( α l , l ) (\alpha^{l},l) ( α l , l ) . □
Table EC.5 reports these exact worst-case values for every nonempty line in L 2 \mathcal{L}_2 L 2 .
Table EC.5. Worst-case Markov-chain revenue for every nonempty line with ∣ S ∣ ≤ 2 |S| \le2 ∣ S ∣ ≤ 2 ; bold starred entries are optimal.
The unique constrained optima are { 3 , 4 } \{3,4\} { 3 , 4 } under U M C U^{\mathrm{MC}} U MC and { 1 , 2 } \{1,2\} { 1 , 2 } under U M C ′ U^{\mathrm{MC}'} U MC ′ . Under U M C U^{\mathrm{MC}} U MC , zero product-to-product transitions are feasible, so the two lines earn 0.30 ( 6 ) + 0.30 ( 5 ) = 3.30 0.30(6) + 0.30(5) = 3.30 0.30 ( 6 ) + 0.30 ( 5 ) = 3.30 and 0.05 ( 10 ) + 0.05 ( 8 ) = 0.90 0.05(10) + 0.05(8) = 0.90 0.05 ( 10 ) + 0.05 ( 8 ) = 0.90 , respectively. Under U M C ′ U^{\mathrm{MC}'} U MC ′ , higher arrival floors at products 1 and 2 and positive transition floors from products 3 and 4 raise the value of { 1 , 2 } \{1,2\} { 1 , 2 } to 7.3872; { 3 , 4 } \{3,4\} { 3 , 4 } still earns 3.30. The optima are thus disjoint, whereas the unconstrained optima { 1 , 2 , 3 , 4 } \{1,2,3,4\} { 1 , 2 , 3 , 4 } and { 1 , 2 } \{1,2\} { 1 , 2 } are nested, consistent with Proposition 6 of Désir et al. [6 ] .
In both examples, capacity forces a change in the optimal line to take the form of replacement rather than expansion. A change in the uncertainty set can reverse the ranking of the feasible pairs.
The Welfare Term under Capacity Constraints
In [DRO-FC], welfare enters the robust objective before product lines are compared. Proposition 1, specialized to the empirical distribution, gives, for every fixed S S S ,
R N , ϵ F C ( S ) = max λ ≥ 0 { − λ ϵ + λ W N ( S ) + 1 N ∑ n ∈ N min i ∈ S ( r i − λ u ^ n i ) } . R_{N,\epsilon}^{\mathrm{FC}}(S) = \max_{\lambda\ge0} \left\{-\lambda\epsilon+ \lambda W_N(S) + \frac{1}{N}\sum_{n \in\mathcal{N}} \min_{i \in S} (r_i - \lambda\hat{u}_{ni})\right\}. R N , ϵ FC ( S ) = λ ≥ 0 max { − λ ϵ + λ W N ( S ) + N 1 n ∈ N ∑ i ∈ S min ( r i − λ u ^ ni ) } .
This identity is established before optimizing over the feasible family. Replacing an unconstrained family by L p \mathcal{L}_p L p , or by any other operationally constrained family, changes which product lines are compared but not the term + λ W N ( S ) +\lambda W_N(S) + λ W N ( S ) for any retained line. The critical radius ϵ † ( Q ^ N ) \epsilon^{\dagger}(\widehat{Q}_N) ϵ † ( Q N ) is then computed over that family, and Corollary 1 continues to provide the corresponding welfare guarantee.
The last term in the display also varies with S S S , so the strength of the revenue–welfare association may differ across instances. Figure EC.Figure 1 shows this association on a common four-product instance with r = ( 10 , 8 , 6 , 5 ) r=(10,8,6,5) r = ( 10 , 8 , 6 , 5 ) , N = 15 N=15 N = 15 , and ∣ S ∣ ≤ 2 |S| \le2 ∣ S ∣ ≤ 2 . Product and outside-option utilities are drawn independently with standard deviation 0.5 around ( 1.0 , 1.5 , 3.0 , 3.5 ) (1.0,1.5,3.0,3.5) ( 1.0 , 1.5 , 3.0 , 3.5 ) and 1.0, respectively, using seed 20250501. We evaluate all ten nonempty feasible lines and order them by W N ( S ) W_N(S) W N ( S ) .
For the robust-MNL benchmark, v ˉ i = exp ( N − 1 ∑ n u ^ n i ) \bar{v}_i=\exp(N^{-1}\sum_n \hat{u}_{ni}) v ˉ i = exp ( N − 1 ∑ n u ^ ni ) , v ˉ 0 \bar{v}_0 v ˉ 0 is fixed, and v i ∈ [ v ˉ i − t , v ˉ i + t ] v_i \in[\bar{v}_i-t,\bar{v}_i+t] v i ∈ [ v ˉ i − t , v ˉ i + t ] with t = 1.338 t=1.338 t = 1.338 . For the robust Markov-chain benchmark, modal arrival and transition probabilities are obtained from the same mean utilities, including the outside option in each normalization; Equation (17) of Désir et al. [6 ] is then applied with ϵ M C = 0.50 \epsilon_{\mathrm{MC}} = 0.50 ϵ MC = 0.50 . We evaluate [DRO-FC] at ϵ = 0.996 = 0.40 ϵ † \epsilon= 0.996 = 0.40\epsilon^{\dagger} ϵ = 0.996 = 0.40 ϵ † .
Figure EC.1. Welfare and robust revenue across the ten nonempty lines with ∣ S ∣ ≤ 2 |S| \le2 ∣ S ∣ ≤ 2 , ordered by W N ( S ) W_N(S) W N ( S ) . Values are min–max normalized within each panel; panel annotations report the ambiguity level and Spearman rank correlation.
At these ambiguity levels, robust-MNL and robust Markov-chain revenues are nonmonotone in the welfare ordering, with Spearman correlations of 0.18. [DRO-FC] tracks the ordering closely (correlation 0.99) and selects the welfare-maximizing line { 3 , 4 } \{3, 4\} { 3 , 4 } .
Proofs
Proof of Proposition 1
For a fixed product line S S S , let g S ( ξ ) = min { r i : i ∈ arg max j ∈ S ˉ U j } g_S(\xi) = \min\{r_i: i \in\arg\max_{j\in\bar{S}} U_j\} g S ( ξ ) = min { r i : i ∈ arg max j ∈ S ˉ U j } be its realized revenue under the lower-revenue tie rule in § 2 . This bounded, lower-semicontinuous function satisfies the conditions for Wasserstein strong duality (Esfahani and Kuhn [7 ] ; Blanchet and Murthy [3 ] ):
R ϵ ( S ; Q ) = sup λ ≥ 0 { − λ ϵ + E Q [ inf ξ ∈ R A + 1 { g S ( ξ ) + λ ∥ ξ − ξ ′ ∥ 1 } ] } . (37) R_{\epsilon}(S; Q) = \sup_{\lambda\ge0} \left\{-\lambda\epsilon+ \mathbb{E}_Q\left[\inf_{\xi\in\mathbb{R}^{A+1}}\left\{g_S(\xi) + \lambda\lVert\xi-\xi'\rVert_1\right\}\right]\right\}. \tag*{(37)} R ϵ ( S ; Q ) = λ ≥ 0 sup { − λ ϵ + E Q [ ξ ∈ R A + 1 inf { g S ( ξ ) + λ ∥ ξ − ξ ′ ∥ 1 } ] } . (37)
where ξ ′ \xi' ξ ′ is distributed according to Q Q Q .
For i ∈ S ˉ i \in\bar{S} i ∈ S ˉ , the closure of its choice region is C i ( S ) = { ξ ∈ R A + 1 : U i ≥ U j ∀ j ∈ S ˉ } C_i(S) = \{\xi\in\mathbb{R}^{A+1}: U_i \ge U_j\ \forall j \in\bar{S}\} C i ( S ) = { ξ ∈ R A + 1 : U i ≥ U j ∀ j ∈ S ˉ } . These cells cover R A + 1 \mathbb{R}^{A+1} R A + 1 ; on overlaps the tie rule takes the lowest revenue. Let m = max j ∈ S ˉ U j ′ m = \max_{j\in\bar{S}} U'_j m = max j ∈ S ˉ U j ′ . Raising coordinate i i i to m m m reaches C i ( S ) C_i(S) C i ( S ) at ℓ 1 \ell_1 ℓ 1 distance m − U i ′ m-U'_i m − U i ′ . For the reverse bound, fix ξ ∈ C i ( S ) \xi\in C_i(S) ξ ∈ C i ( S ) and choose j ⋆ ∈ arg max j ∈ S ˉ U j ′ j^\star\in\arg\max_{j\in\bar{S}} U'_j j ⋆ ∈ arg max j ∈ S ˉ U j ′ . If j ⋆ = i j^\star=i j ⋆ = i , the bound is immediate. Otherwise, U i ≥ U j ⋆ U_i \ge U_{j^\star} U i ≥ U j ⋆ implies
m − U i ′ = U j ⋆ ′ − U i ′ ≤ ∣ U j ⋆ ′ − U j ⋆ ∣ + ∣ U i − U i ′ ∣ ≤ ∥ ξ − ξ ′ ∥ 1 . m-U'_i=U'_{j^\star}-U'_i\le\lvert U'_{j^\star}-U_{j^\star}\rvert+\lvert U_i-U'_i\rvert\le\lVert\xi-\xi'\rVert_1. m − U i ′ = U j ⋆ ′ − U i ′ ≤ ∣ U j ⋆ ′ − U j ⋆ ∣ + ∣ U i − U i ′ ∣ ≤ ∥ ξ − ξ ′ ∥ 1 .
Taking the infimum over ξ ∈ C i ( S ) \xi\in C_i(S) ξ ∈ C i ( S ) gives the distance. Therefore
inf ξ ∈ R A + 1 { g S ( ξ ) + λ ∥ ξ − ξ ′ ∥ 1 } = min i ∈ S ˉ { r i + λ ( max j ∈ S ˉ U j ′ − U i ′ ) } = λ max j ∈ S ˉ U j ′ + min i ∈ S ˉ { r i − λ U i ′ } . \begin{aligned}
\inf_{\xi\in\mathbb{R}^{A+1}}\{g_S(\xi)+\lambda\lVert\xi-\xi'\rVert_1\}
=
\min_{i\in\bar{S}}\left\{r_i+\lambda\left(\max_{j\in\bar{S}}U'_j-U'_i\right)\right\} \\
&=\lambda\max_{j\in\bar{S}}U'_j+\min_{i\in\bar{S}}\{r_i-\lambda U'_i\}.
\end{aligned} ξ ∈ R A + 1 inf { g S ( ξ ) + λ ∥ ξ − ξ ′ ∥ 1 } = i ∈ S ˉ min { r i + λ ( j ∈ S ˉ max U j ′ − U i ′ ) } = λ j ∈ S ˉ max U j ′ + i ∈ S ˉ min { r i − λ U i ′ } .
Substituting this identity into (EC.14) and using min i { r i − λ U i } = − λ max i { U i − r i / λ } \min_i\{r_i-\lambda U_i\}=-\lambda\max_i\{U_i-r_i/\lambda\} min i { r i − λ U i } = − λ max i { U i − r i / λ } for λ > 0 \lambda>0 λ > 0 gives (2). The expression at λ = 0 \lambda=0 λ = 0 equals zero because r 0 = 0 r_0=0 r 0 = 0 and is obtained as the continuous boundary value. The combined integrand is continuous in λ \lambda λ and lies in [ 0 , r ˉ ] [0,\bar r] [ 0 , r ˉ ] : choosing a utility-maximizing alternative in the inner minimum gives the upper bound. Dominated convergence therefore gives continuity of the dual objective on [ 0 , ∞ ) [0,\infty) [ 0 , ∞ ) , while the term − λ ϵ -\lambda\epsilon − λ ϵ forces it to − ∞ -\infty − ∞ as λ → ∞ \lambda\to\infty λ → ∞ for ϵ > 0 \epsilon>0 ϵ > 0 . Hence, the supremum is attained.
Proof of Corollary 1
For fixed S S S , write the objective in (2) as
ψ S ( λ ; ϵ , Q ) = − λ ϵ + λ W ( S ; Q ) + E Q [ min i ∈ S ˉ { r i − λ U i } ] . \psi_S(\lambda;\epsilon,Q)=-\lambda\epsilon+\lambda W(S;Q)+\mathbb{E}_Q\left[\min_{i\in\bar S}\{r_i-\lambda U_i\}\right]. ψ S ( λ ; ϵ , Q ) = − λ ϵ + λW ( S ; Q ) + E Q [ i ∈ S ˉ min { r i − λ U i } ] .
This objective is concave and equals zero at λ = 0 \lambda=0 λ = 0 . Since the outside option uniquely minimizes r i r_i r i , dominated convergence gives ∂ + ψ S ( 0 ; ϵ , Q ) = W ( S ; Q ) − E Q [ U 0 ] − ϵ \partial_+\psi_S(0;\epsilon,Q)=W(S;Q)-\mathbb{E}_Q[U_0]-\epsilon ∂ + ψ S ( 0 ; ϵ , Q ) = W ( S ; Q ) − E Q [ U 0 ] − ϵ . If the derivative is nonpositive, concavity implies that the maximum is zero; if it is positive, the objective increases to the right of zero and the maximum is positive.
Because ϵ < ϵ † ( Q ) \epsilon<\epsilon^\dagger(Q) ϵ < ϵ † ( Q ) , a welfare-maximizing product line has incremental welfare strictly greater than ϵ \epsilon ϵ and hence positive robust revenue. Every robust-optimal product line must therefore have positive robust revenue, which requires W ( S ϵ ∗ ( Q ) ; Q ) − E Q [ U 0 ] > ϵ W(S^*_\epsilon(Q);Q)-\mathbb{E}_Q[U_0]>\epsilon W ( S ϵ ∗ ( Q ) ; Q ) − E Q [ U 0 ] > ϵ . The weak inequality stated in the corollary follows.
Proof of Proposition 2
Fix λ > 0 \lambda>0 λ > 0 . The fixed-λ \lambda λ expression for [DRO-MNL] is maximized by maximizing
F λ ( S ) = v 0 + ∑ i ∈ S v i v 0 + ∑ i ∈ S v i e − r i / λ . F_\lambda(S)=\frac{v_0+\sum_{i\in S}v_i}{v_0+\sum_{i\in S}v_i e^{-r_i/\lambda}}. F λ ( S ) = v 0 + ∑ i ∈ S v i e − r i / λ v 0 + ∑ i ∈ S v i .
Let S λ S_\lambda S λ be optimal and denote its numerator and denominator by A λ A_\lambda A λ and B λ B_\lambda B λ . Adding an excluded product i i i cannot improve the ratio, which implies e − r i / λ ≥ B λ / A λ e^{-r_i/\lambda}\ge B_\lambda/A_\lambda e − r i / λ ≥ B λ / A λ . Removing an included product cannot improve it, which implies e − r i / λ ≤ B λ / A λ e^{-r_i/\lambda}\le B_\lambda/A_\lambda e − r i / λ ≤ B λ / A λ . Since e − r / λ e^{-r/\lambda} e − r / λ decreases in r r r , an optimal product line can be chosen as a revenue-ordered prefix for every fixed λ > 0 \lambda>0 λ > 0 . At λ = 0 \lambda=0 λ = 0 , the continuous boundary value is zero for every product line, so a prefix can again be selected. Maximizing jointly over the finite set of prefixes and λ \lambda λ proves the result.
Proof of Proposition 3
Fix λ > 0 \lambda>0 λ > 0 and write t = 1 / λ t=1/\lambda t = 1/ λ . For the prefix S k = { 1 , … , k } S_k=\{1,\ldots,k\} S k = { 1 , … , k } , define
ρ i ( t ) = 1 − e − t r i , A k = v 0 + ∑ i = 1 k v i , Ψ k ( t ) = ∑ i = 1 k v i ρ i ( t ) A k , \rho_i(t)=1-e^{-tr_i},\qquad A_k=v_0+\sum_{i=1}^{k}v_i,\qquad\Psi_k(t)=\frac{\sum_{i=1}^{k}v_i\rho_i(t)}{A_k}, ρ i ( t ) = 1 − e − t r i , A k = v 0 + i = 1 ∑ k v i , Ψ k ( t ) = A k ∑ i = 1 k v i ρ i ( t ) ,
with Ψ 0 ( t ) = 0 \Psi_0(t)=0 Ψ 0 ( t ) = 0 . Maximizing the fixed-λ \lambda λ [DRO-MNL] objective over prefixes is equivalent to maximizing Ψ k ( t ) \Psi_k(t) Ψ k ( t ) .
The sequence { Ψ k ( t ) } k = 0 A \{\Psi_k(t)\}_{k=0}^{A} { Ψ k ( t ) } k = 0 A is single-peaked in k k k . Indeed,
Ψ k + 1 ( t ) ≥ Ψ k ( t ) ⟺ ρ k + 1 ( t ) ≥ Ψ k ( t ) . (38) \Psi_{k+1}(t)\ge\Psi_k(t)\quad\Longleftrightarrow\quad\rho_{k+1}(t)\ge\Psi_k(t). \tag*{(38)} Ψ k + 1 ( t ) ≥ Ψ k ( t ) ⟺ ρ k + 1 ( t ) ≥ Ψ k ( t ) . (38)
If the inequality fails at k k k , then Ψ k + 1 ( t ) \Psi_{k+1}(t) Ψ k + 1 ( t ) is a strict weighted average of Ψ k ( t ) \Psi_k(t) Ψ k ( t ) and ρ k + 1 ( t ) \rho_{k+1}(t) ρ k + 1 ( t ) . Since r k + 2 ≤ r k + 1 r_{k+2}\le r_{k+1} r k + 2 ≤ r k + 1 , we have ρ k + 2 ( t ) ≤ ρ k + 1 ( t ) < Ψ k + 1 ( t ) \rho_{k+2}(t)\le\rho_{k+1}(t)<\Psi_{k+1}(t) ρ k + 2 ( t ) ≤ ρ k + 1 ( t ) < Ψ k + 1 ( t ) , so the next addition also fails; the same argument applies inductively. The largest maximizing prefix is therefore the last index whose adjacent addition is weakly beneficial.
Each adjacent addition also has a single-crossing property in t t t . Rearranging (EC.15) gives
H k ( t ) : = v 0 e t r k + 1 + ∑ i = 1 k v i e − t ( r i − r k + 1 ) A k ≥ 1. H_k(t) := \frac{v_0 e^{t r_{k+1}} + \sum_{i=1}^{k} v_i e^{-t(r_i-r_{k+1})}}{A_k} \ge1. H k ( t ) := A k v 0 e t r k + 1 + ∑ i = 1 k v i e − t ( r i − r k + 1 ) ≥ 1.
The function H k H_k H k is strictly convex, H k ( 0 ) = 1 H_k(0) = 1 H k ( 0 ) = 1 , and H k ( t ) → ∞ H_k(t) \to\infty H k ( t ) → ∞ as t → ∞ t \to\infty t → ∞ . It follows that { t > 0 : H k ( t ) ≥ 1 } \{t > 0 : H_k(t) \ge1\} { t > 0 : H k ( t ) ≥ 1 } is an upper interval. Combined with single-peakedness, the largest fixed-λ \lambda λ optimal prefix is nondecreasing in t = 1 / λ t = 1/\lambda t = 1/ λ ; the conclusion extends to λ = 0 \lambda= 0 λ = 0 by selecting the largest prefix.
It remains to establish the monotonicity of the optimal multiplier. Let
J k ( λ ) = λ log v 0 + ∑ i = 1 k v i v 0 + ∑ i = 1 k v i e − r i / λ . J_k(\lambda) = \lambda\log\frac{v_0 + \sum_{i=1}^{k} v_i}{v_0 + \sum_{i=1}^{k} v_i e^{-r_i/\lambda}}. J k ( λ ) = λ log v 0 + ∑ i = 1 k v i e − r i / λ v 0 + ∑ i = 1 k v i .
with its continuous boundary value at λ = 0 \lambda= 0 λ = 0 , so the objective associated with pair ( k , λ ) (k,\lambda) ( k , λ ) is J k ( λ ) − ϵ λ J_k(\lambda)-\epsilon\lambda J k ( λ ) − ϵ λ . Fix ϵ 1 < ϵ 2 \epsilon_1 < \epsilon_2 ϵ 1 < ϵ 2 and write ( k q , λ q ) = ( k ∗ ( ϵ q ) , λ ϵ q ∗ ) (k_q,\lambda_q) = (k^*(\epsilon_q),\lambda^*_{\epsilon_q}) ( k q , λ q ) = ( k ∗ ( ϵ q ) , λ ϵ q ∗ ) for q = 1 , 2 q = 1, 2 q = 1 , 2 . Optimality at the two radii gives
J k 1 ( λ 1 ) − ϵ 1 λ 1 ≥ J k 2 ( λ 2 ) − ϵ 1 λ 2 , J_{k_1}(\lambda_1) - \epsilon_1\lambda_1 \ge J_{k_2}(\lambda_2) - \epsilon_1\lambda_2, J k 1 ( λ 1 ) − ϵ 1 λ 1 ≥ J k 2 ( λ 2 ) − ϵ 1 λ 2 ,
J k 2 ( λ 2 ) − ϵ 2 λ 2 ≥ J k 1 ( λ 1 ) − ϵ 2 λ 1 . J_{k_2}(\lambda_2) - \epsilon_2\lambda_2 \ge J_{k_1}(\lambda_1) - \epsilon_2\lambda_1. J k 2 ( λ 2 ) − ϵ 2 λ 2 ≥ J k 1 ( λ 1 ) − ϵ 2 λ 1 .
Adding these inequalities yields ( ϵ 2 − ϵ 1 ) ( λ 1 − λ 2 ) ≥ 0 (\epsilon_2-\epsilon_1)(\lambda_1-\lambda_2) \ge0 ( ϵ 2 − ϵ 1 ) ( λ 1 − λ 2 ) ≥ 0 , and hence λ 1 ≥ λ 2 \lambda_1 \ge\lambda_2 λ 1 ≥ λ 2 . Thus, λ ∗ \lambda^* λ ∗ is nonincreasing in ϵ \epsilon ϵ , so 1 / λ ∗ 1/\lambda^* 1/ λ ∗ is nondecreasing, with 1 / 0 1/0 1/0 interpreted as + ∞ +\infty + ∞ . Applying the fixed-multiplier result and the stated largest-prefix tie rule gives k ∗ ( ϵ 1 ) ≤ k ∗ ( ϵ 2 ) k^*(\epsilon_1) \le k^*(\epsilon_2) k ∗ ( ϵ 1 ) ≤ k ∗ ( ϵ 2 ) whenever ϵ 1 ≤ ϵ 2 \epsilon_1 \le\epsilon_2 ϵ 1 ≤ ϵ 2 .
Proof of Proposition 4
With v 0 = 1 v_0 = 1 v 0 = 1 , the multinomial log-likelihood is ℓ T ( v ) = ∑ i = 1 A T ^ i log v i − T log ( 1 + ∑ i = 1 A v i ) \ell_T(v) = \sum_{i=1}^{A} \widehat{T}_i \log v_i - T \log(1 + \sum_{i=1}^{A} v_i) ℓ T ( v ) = ∑ i = 1 A T i log v i − T log ( 1 + ∑ i = 1 A v i ) for v ∈ ( 0 , ∞ ) A v \in(0,\infty)^A v ∈ ( 0 , ∞ ) A . It extends continuously to v i = 0 v_i = 0 v i = 0 when T ^ i = 0 \widehat{T}_i = 0 T i = 0 . If T ^ 0 > 0 \widehat{T}_0 > 0 T 0 > 0 , an interior critical point satisfies T ^ k / v k = T / ( 1 + ∑ i = 1 A v i ) \widehat{T}_k/v_k = T/(1 + \sum_{i=1}^{A} v_i) T k / v k = T / ( 1 + ∑ i = 1 A v i ) for each k = 1 , … , A k = 1,\ldots,A k = 1 , … , A . Summing T ^ k = v k T / ( 1 + ∑ i v i ) \widehat{T}_k = v_k T/(1 + \sum_i v_i) T k = v k T / ( 1 + ∑ i v i ) over k ≥ 1 k \ge1 k ≥ 1 and using ∑ k ≥ 1 T ^ k = T − T ^ 0 \sum_{k\ge1} \widehat{T}_k = T-\widehat{T}_0 ∑ k ≥ 1 T k = T − T 0 gives ∑ k ≥ 1 v k = ( T − T ^ 0 ) / T ^ 0 \sum_{k\ge1} v_k = (T-\widehat{T}_0)/\widehat{T}_0 ∑ k ≥ 1 v k = ( T − T 0 ) / T 0 . Substituting back yields v k = T ^ k / T ^ 0 = p ^ k / p ^ 0 v_k = \widehat{T}_k/\widehat{T}_0 = \widehat{p}_k/\widehat{p}_0 v k = T k / T 0 = p k / p 0 . The Hessian of ℓ T \ell_T ℓ T is negative definite on ( 0 , ∞ ) A (0,\infty)^A ( 0 , ∞ ) A whenever T ^ 0 > 0 \widehat{T}_0 > 0 T 0 > 0 , so this critical point is the unique maximizer. Coordinates with T ^ k = 0 \widehat{T}_k = 0 T k = 0 are maximized at v k = 0 v_k = 0 v k = 0 , which is the extended MLE on [ 0 , ∞ ) A [0,\infty)^A [ 0 , ∞ ) A . Every coordinate is strictly positive if and only if T ^ i > 0 \widehat{T}_i > 0 T i > 0 for all i = 0 , 1 , … , A i = 0,1,\ldots,A i = 0 , 1 , … , A , and only then is the maximizer interior.
If T ^ 0 = 0 \widehat{T}_0 = 0 T 0 = 0 , write v = t u v = tu v = t u with t > 0 t > 0 t > 0 and ∑ i = 1 A u i = 1 \sum_{i=1}^{A} u_i = 1 ∑ i = 1 A u i = 1 . Since ∑ i = 1 A T ^ i = T \sum_{i=1}^{A} \widehat{T}_i = T ∑ i = 1 A T i = T , we have ℓ T ( t u ) = ∑ i = 1 A T ^ i log u i + T log ( t / ( 1 + t ) ) \ell_T(tu) = \sum_{i=1}^{A} \widehat{T}_i \log u_i + T \log(t/(1+t)) ℓ T ( t u ) = ∑ i = 1 A T i log u i + T log ( t / ( 1 + t )) . The last term is strictly increasing in t t t and converges to zero, so the finite supremum is not attained.
Proof of Lemma 1
The multinomial counts give E [ ∥ p ^ − p ∗ ∥ 2 2 ] = T − 1 ( 1 − ∑ i = 0 A ( p i ∗ ) 2 ) \mathbb{E}[\lVert\widehat{p}-p^*\rVert_2^2] = T^{-1}(1-\sum_{i=0}^{A}(p_i^*)^2) E [∥ p − p ∗ ∥ 2 2 ] = T − 1 ( 1 − ∑ i = 0 A ( p i ∗ ) 2 ) . Since ∑ i = 0 A ( p i ∗ ) 2 ≥ 1 / ( A + 1 ) \sum_{i=0}^{A}(p_i^*)^2 \ge1/(A+1) ∑ i = 0 A ( p i ∗ ) 2 ≥ 1/ ( A + 1 ) , this is at most A / ( ( A + 1 ) T ) A/((A+1)T) A / (( A + 1 ) T ) . Cauchy–Schwarz therefore gives
E [ ∥ p ^ − p ∗ ∥ 1 ] ≤ A + 1 E [ ∥ p ^ − p ∗ ∥ 2 2 ] ≤ A T . \mathbb{E}[\lVert\widehat{p}-p^*\rVert_1] \le\sqrt{A+1}\sqrt{\mathbb{E}[\lVert\widehat{p}-p^*\rVert_2^2]} \le\sqrt{\frac{A}{T}}. E [∥ p − p ∗ ∥ 1 ] ≤ A + 1 E [∥ p − p ∗ ∥ 2 2 ] ≤ T A .
On { p ^ 0 > 0 } \{\widehat{p}_0 > 0\} { p 0 > 0 } , fix S ⊆ A S \subseteq\mathcal{A} S ⊆ A and write a i = p i ∗ a_i = p_i^* a i = p i ∗ , a ^ i = p ^ i \widehat{a}_i = \widehat{p}_i a i = p i for i ∈ S ∪ { 0 } i \in S \cup\{0\} i ∈ S ∪ { 0 } , with sums A S A_S A S and A ^ S \widehat{A}_S A S . Then
∑ i ∈ S ∪ { 0 } ∣ q i ( S ; Q ^ ) − q i ( S ; Q 0 ) ∣ ≤ 2 ∥ a ^ − a ∥ 1 A S ≤ 2 κ ∥ p ^ − p ∗ ∥ 1 . \sum_{i\in S\cup\{0\}} \left|q_i(S;\widehat{Q})-q_i(S;Q_0)\right| \le\frac{2\lVert\widehat{a}-a\rVert_1}{A_S} \le\frac{2}{\kappa}\lVert\widehat{p}-p^*\rVert_1. i ∈ S ∪ { 0 } ∑ q i ( S ; Q ) − q i ( S ; Q 0 ) ≤ A S 2 ∥ a − a ∥ 1 ≤ κ 2 ∥ p − p ∗ ∥ 1 .
because A S ≥ p 0 ∗ ≥ κ A_S \ge p_0^* \ge\kappa A S ≥ p 0 ∗ ≥ κ . The same bound holds for the supremum over S S S , so
E [ sup S ⊆ A ∑ i ∈ S ∪ { 0 } ∣ q i ( S ; Q ^ ) − q i ( S ; Q 0 ) ∣ ⋅ 1 { p ^ 0 > 0 } ] ≤ 2 κ A T . \mathbb{E}\left[\sup_{S\subseteq\mathcal{A}}\sum_{i\in S\cup\{0\}}\left|q_i(S;\widehat{Q})-q_i(S;Q_0)\right|\cdot\mathbf{1}\{\widehat{p}_0>0\}\right]\leq\frac{2}{\kappa}\sqrt{\frac{A}{T}}. E S ⊆ A sup i ∈ S ∪ { 0 } ∑ q i ( S ; Q ) − q i ( S ; Q 0 ) ⋅ 1 { p 0 > 0 } ≤ κ 2 T A .
On { p ^ 0 = 0 } \{\widehat{p}_0=0\} { p 0 = 0 } the error is 2 2 2 , and P ( p ^ 0 = 0 ) = ( 1 − p 0 ∗ ) T ≤ exp ( − κ T ) \mathbb{P}(\widehat{p}_0=0)=(1-p_0^*)^T\leq\exp(-\kappa T) P ( p 0 = 0 ) = ( 1 − p 0 ∗ ) T ≤ exp ( − κ T ) . Adding these contributions yields (8).
Proof of Proposition 5
We first bound the effects of estimation and robustness separately.
Lemma EC.2 (Nominal Revenue and Choice Probabilities). Let Q Q Q and Q ′ Q' Q ′ be two utility distributions. For every product line S S S ,
∣ R ( S ; Q ) − R ( S ; Q ′ ) ∣ ≤ r ˉ 2 ∑ i ∈ S ∪ { 0 } ∣ q i ( S ; Q ) − q i ( S ; Q ′ ) ∣ . \left|R(S;Q)-R(S;Q')\right|\leq\frac{\bar{r}}{2}\sum_{i\in S\cup\{0\}}\left|q_i(S;Q)-q_i(S;Q')\right|. ∣ R ( S ; Q ) − R ( S ; Q ′ ) ∣ ≤ 2 r ˉ i ∈ S ∪ { 0 } ∑ ∣ q i ( S ; Q ) − q i ( S ; Q ′ ) ∣ .
Proof of Lemma EC.2. Let d i = q i ( S ; Q ) − q i ( S ; Q ′ ) d_i=q_i(S;Q)-q_i(S;Q') d i = q i ( S ; Q ) − q i ( S ; Q ′ ) for i ∈ S ˉ i\in\bar{S} i ∈ S ˉ . The outside option can be included in the revenue sum because r 0 = 0 r_0=0 r 0 = 0 . Since both choice vectors sum to one, ∑ i ∈ S ˉ d i = 0 \sum_{i\in\bar{S}}d_i=0 ∑ i ∈ S ˉ d i = 0 . Subtracting r ˉ / 2 \bar{r}/2 r ˉ /2 from each revenue coefficient therefore leaves the difference unchanged:
∣ R ( S ; Q ) − R ( S ; Q ′ ) ∣ = ∣ ∑ i ∈ S ˉ ( r i − r ˉ / 2 ) d i ∣ ≤ r ˉ 2 ∑ i ∈ S ˉ ∣ d i ∣ , \left|R(S;Q)-R(S;Q')\right|=\left|\sum_{i\in\bar{S}}(r_i-\bar{r}/2)d_i\right|\leq\frac{\bar{r}}{2}\sum_{i\in\bar{S}}|d_i|, ∣ R ( S ; Q ) − R ( S ; Q ′ ) ∣ = i ∈ S ˉ ∑ ( r i − r ˉ /2 ) d i ≤ 2 r ˉ i ∈ S ˉ ∑ ∣ d i ∣ ,
where the inequality uses 0 ≤ r i ≤ r ˉ 0\leq r_i\leq\bar{r} 0 ≤ r i ≤ r ˉ .
Lemma EC.3 (Robustness Penalty for an MNL Nominal). Let Q Q Q be any MNL distribution. Then, for every ϵ ≥ 0 \epsilon\geq0 ϵ ≥ 0 ,
V 0 ∗ ( Q ) − V ϵ ∗ ( Q ) ≤ r ˉ ϵ 2 . (39) V_0^*(Q)-V_\epsilon^*(Q)\leq\bar{r}\sqrt{\frac{\epsilon}{2}}. \tag*{(39)} V 0 ∗ ( Q ) − V ϵ ∗ ( Q ) ≤ r ˉ 2 ϵ . (39)
Proof of Lemma EC.3. The claim is immediate when ϵ = 0 \epsilon=0 ϵ = 0 . Fix ϵ > 0 \epsilon>0 ϵ > 0 and a product line S S S . Let X X X be the nominal revenue of the alternative chosen from S ∪ { 0 } S\cup\{0\} S ∪ { 0 } , so X ∈ [ 0 , r ˉ ] X\in[0,\bar{r}] X ∈ [ 0 , r ˉ ] and E [ X ] = R ( S ; Q ) \mathbb{E}[X]=R(S;Q) E [ X ] = R ( S ; Q ) . The Gumbel calculation in (4) gives
R ϵ ( S ; Q ) = sup λ > 0 { − λ ϵ − λ log E [ e − X / λ ] } . R_\epsilon(S;Q)=\sup_{\lambda>0}\left\{-\lambda\epsilon-\lambda\log\mathbb{E}\left[e^{-X/\lambda}\right]\right\}. R ϵ ( S ; Q ) = λ > 0 sup { − λ ϵ − λ log E [ e − X / λ ] } .
Hoeffding’s lemma gives log E [ e − X / λ ] ≤ − R ( S ; Q ) / λ + r ˉ 2 / ( 8 λ 2 ) \log\mathbb{E}[e^{-X/\lambda}]\leq-R(S;Q)/\lambda+\bar{r}^2/(8\lambda^2) log E [ e − X / λ ] ≤ − R ( S ; Q ) / λ + r ˉ 2 / ( 8 λ 2 ) for every λ > 0 \lambda>0 λ > 0 . Multiplying by − λ -\lambda − λ and substituting yields
R ϵ ( S ; Q ) ≥ R ( S ; Q ) − inf λ > 0 { λ ϵ + r ˉ 2 8 λ } = R ( S ; Q ) − r ˉ ϵ 2 . R_\epsilon(S;Q)\geq R(S;Q)-\inf_{\lambda>0}\left\{\lambda\epsilon+\frac{\bar{r}^2}{8\lambda}\right\}=R(S;Q)-\bar{r}\sqrt{\frac{\epsilon}{2}}. R ϵ ( S ; Q ) ≥ R ( S ; Q ) − λ > 0 inf { λ ϵ + 8 λ r ˉ 2 } = R ( S ; Q ) − r ˉ 2 ϵ .
The infimum equals r ˉ ϵ / 2 \bar{r}\sqrt{\epsilon/2} r ˉ ϵ /2 at λ = r ˉ / 8 ϵ \lambda=\bar{r}/\sqrt{8\epsilon} λ = r ˉ / 8 ϵ . Evaluating the inequality at a nominal optimizer gives (EC.16).
Let S ^ = S ^ T , ϵ \widehat{S}=\widehat{S}_{T,\epsilon} S = S T , ϵ . On { p ^ 0 = 0 } \{\widehat{p}_0=0\} { p 0 = 0 } the maximum-likelihood estimator is undefined and the loss is at most r ˉ \bar{r} r ˉ . On { p ^ 0 > 0 } \{\widehat{p}_0>0\} { p 0 > 0 } , decompose the loss as
V 0 ⋆ − R ( S ^ ; Q 0 ) = ( V 0 ⋆ ( Q 0 ) − V 0 ⋆ ( Q ^ ) ) + ( V 0 ⋆ ( Q ^ ) − V ϵ ⋆ ( Q ^ ) ) + ( V ϵ ⋆ ( Q ^ ) − R ( S ^ ; Q 0 ) ) . V_0^\star-R(\widehat{S};Q_0)=\left(V_0^\star(Q_0)-V_0^\star(\widehat{Q})\right)+\left(V_0^\star(\widehat{Q})-V_\epsilon^\star(\widehat{Q})\right)+\left(V_\epsilon^\star(\widehat{Q})-R(\widehat{S};Q_0)\right). V 0 ⋆ − R ( S ; Q 0 ) = ( V 0 ⋆ ( Q 0 ) − V 0 ⋆ ( Q ) ) + ( V 0 ⋆ ( Q ) − V ϵ ⋆ ( Q ) ) + ( V ϵ ⋆ ( Q ) − R ( S ; Q 0 ) ) .
Lemma EC.3 bounds the second term by r ˉ ϵ / 2 \bar{r}\sqrt{\epsilon}/2 r ˉ ϵ /2 .
For the first term, let S ⋆ S^\star S ⋆ be optimal for R ( ⋅ ; Q 0 ) R(\cdot;Q_0) R ( ⋅ ; Q 0 ) . Lemma EC.2 gives
V 0 ⋆ ( Q 0 ) − V 0 ⋆ ( Q ^ ) ≤ R ( S ⋆ ; Q 0 ) − R ( S ⋆ ; Q ^ ) ≤ r ˉ 2 ∑ i ∈ S ⋆ ∪ { 0 } ∣ q i ( S ⋆ ; Q ^ ) − q i ( S ⋆ ; Q 0 ) ∣ . V_0^\star(Q_0)-V_0^\star(\widehat{Q})\le R(S^\star;Q_0)-R(S^\star;\widehat{Q})\le\frac{\bar{r}}{2}\sum_{i\in S^\star\cup\{0\}}\left|q_i(S^\star;\widehat{Q})-q_i(S^\star;Q_0)\right|. V 0 ⋆ ( Q 0 ) − V 0 ⋆ ( Q ) ≤ R ( S ⋆ ; Q 0 ) − R ( S ⋆ ; Q ) ≤ 2 r ˉ i ∈ S ⋆ ∪ { 0 } ∑ q i ( S ⋆ ; Q ) − q i ( S ⋆ ; Q 0 ) .
For the third term, optimality of S ^ \widehat{S} S for the robust objective and the inequality R ϵ ≤ R R_\epsilon\le R R ϵ ≤ R give V ϵ ⋆ ( Q ^ ) = R ϵ ( S ^ ; Q ^ ) ≤ R ( S ^ ; Q ^ ) V_\epsilon^\star(\widehat{Q})=R_\epsilon(\widehat{S};\widehat{Q})\le R(\widehat{S};\widehat{Q}) V ϵ ⋆ ( Q ) = R ϵ ( S ; Q ) ≤ R ( S ; Q ) . Lemma EC.2 therefore yields
V ϵ ⋆ ( Q ^ ) − R ( S ^ ; Q 0 ) ≤ r ˉ 2 ∑ i ∈ S ^ ∪ { 0 } ∣ q i ( S ^ ; Q ^ ) − q i ( S ^ ; Q 0 ) ∣ . V_\epsilon^\star(\widehat{Q})-R(\widehat{S};Q_0)\le\frac{\bar{r}}{2}\sum_{i\in\widehat{S}\cup\{0\}}\left|q_i(\widehat{S};\widehat{Q})-q_i(\widehat{S};Q_0)\right|. V ϵ ⋆ ( Q ) − R ( S ; Q 0 ) ≤ 2 r ˉ i ∈ S ∪ { 0 } ∑ q i ( S ; Q ) − q i ( S ; Q 0 ) .
The two sums are each at most the supremum in Lemma 1, so together they contribute at most r ˉ \bar{r} r ˉ times that choice-probability error. On { p ^ 0 > 0 } \{\widehat{p}_0>0\} { p 0 > 0 } ,
V 0 ⋆ − R ( S ^ ; Q 0 ) ≤ r ˉ ϵ 2 + r ˉ sup S ⊆ A ∑ i ∈ S ∪ { 0 } ∣ q i ( S ; Q ^ ) − q i ( S ; Q 0 ) ∣ . V_0^\star-R(\widehat{S};Q_0)\le\bar{r}\sqrt{\frac{\epsilon}{2}}+\bar{r}\sup_{S\subseteq\mathcal{A}}\sum_{i\in S\cup\{0\}}\left|q_i(S;\widehat{Q})-q_i(S;Q_0)\right|. V 0 ⋆ − R ( S ; Q 0 ) ≤ r ˉ 2 ϵ + r ˉ S ⊆ A sup i ∈ S ∪ { 0 } ∑ q i ( S ; Q ) − q i ( S ; Q 0 ) .
On { p ^ 0 = 0 } \{\widehat{p}_0=0\} { p 0 = 0 } the loss is at most r ˉ \bar{r} r ˉ , and P ( p 0 = 0 ) ≤ exp ( − κ T ) \mathbb{P}(p_0=0)\le\exp(-\kappa T) P ( p 0 = 0 ) ≤ exp ( − κ T ) . Therefore
E [ V 0 ⋆ − R ( S ^ ; Q 0 ) ] ≤ r ˉ ϵ 2 + r ˉ E [ sup S ⊆ A ∑ i ∈ S ∪ { 0 } ∣ q i ( S ; Q ^ ) − q i ( S ; Q 0 ) ∣ ⋅ 1 { p ^ 0 > 0 } ] + r ˉ exp ( − κ T ) . \mathbb{E}\left[V_0^\star-R(\widehat{S};Q_0)\right]\le\bar{r}\sqrt{\frac{\epsilon}{2}}+\bar{r}\mathbb{E}\left[\sup_{S\subseteq\mathcal{A}}\sum_{i\in S\cup\{0\}}\left|q_i(S;\widehat{Q})-q_i(S;Q_0)\right|\cdot\mathbf{1}\{\widehat{p}_0>0\}\right]+\bar{r}\exp(-\kappa T). E [ V 0 ⋆ − R ( S ; Q 0 ) ] ≤ r ˉ 2 ϵ + r ˉ E S ⊆ A sup i ∈ S ∪ { 0 } ∑ q i ( S ; Q ) − q i ( S ; Q 0 ) ⋅ 1 { p 0 > 0 } + r ˉ exp ( − κ T ) .
The proof of Lemma 1 bounds the expectation on { p ^ 0 > 0 } \{\widehat{p}_0>0\} { p 0 > 0 } by ( 2 / κ ) A / T (2/\kappa)\sqrt{A/T} ( 2/ κ ) A / T . Substituting that bound gives (9) . The displayed expectation in the lemma is larger by the additional 2 exp ( − κ T ) 2\exp(-\kappa T) 2 exp ( − κ T ) coming from the convention that the error equals 2 on { p ^ 0 = 0 } \{\widehat{p}_0=0\} { p 0 = 0 } ; the argument above charges that event only r ˉ \bar{r} r ˉ .
Proof of Corollary 2
The threshold 16 A r ˉ 2 / ( κ 2 η 2 ) 16A\bar{r}^{2}/(\kappa^{2}\eta^{2}) 16 A r ˉ 2 / ( κ 2 η 2 ) makes ( 2 r ˉ / κ ) A / T ≤ η / 2 (2\bar{r}/\kappa)\sqrt{A/T}\le\eta/2 ( 2 r ˉ / κ ) A / T ≤ η /2 . The threshold κ − 1 log ( 2 r ˉ / η ) \kappa^{-1}\log(2\bar{r}/\eta) κ − 1 log ( 2 r ˉ / η ) makes r ˉ exp ( − κ T ) ≤ η / 2 \bar{r}\exp(-\kappa T)\le\eta/2 r ˉ exp ( − κ T ) ≤ η /2 when 2 r ˉ > η 2\bar{r}>\eta 2 r ˉ > η . When η ≥ 2 r ˉ \eta\ge2\bar{r} η ≥ 2 r ˉ , one has log ( 2 r ˉ / η ) ≤ 0 \log(2\bar{r}/\eta)\le0 log ( 2 r ˉ / η ) ≤ 0 , so (10) imposes no further restriction from this term, and r ˉ exp ( − κ T ) ≤ r ˉ ≤ η / 2 \bar{r}\exp(-\kappa T)\le\bar{r}\le\eta/2 r ˉ exp ( − κ T ) ≤ r ˉ ≤ η /2 for every T ≥ 0 T\ge0 T ≥ 0 . Adding these estimation terms to the robustness penalty gives the claim.
Proof of Proposition 6
The minimizing property of k n k_n k n gives
r k n − λ u ^ n k n ≤ r i − λ u ^ n i , i ∈ S ∪ { 0 } . (40) r_{k_n}-\lambda\widehat{u}_{nk_n}\le r_i-\lambda\widehat{u}_{ni},\qquad i\in S\cup\{0\}. \tag*{(40)} r k n − λ u n k n ≤ r i − λ u ni , i ∈ S ∪ { 0 } . (40)
If r i < r k n r_i<r_{k_n} r i < r k n and u ^ n i ≥ u ^ n k n \widehat{u}_{ni}\ge\widehat{u}_{nk_n} u ni ≥ u n k n , the right-hand side of (EC.17) is strictly smaller than the left-hand side, a contradiction. This proves dominance exclusion.
If r i > r k n r_i>r_{k_n} r i > r k n and u ^ n i > u ^ n k n \widehat{u}_{ni}>\widehat{u}_{nk_n} u ni > u n k n , rearranging (EC.17) gives the upper-margin condition ( r i − r k n ) / ( u ^ n i − u ^ n k n ) ≥ λ (r_i-r_{k_n})/(\widehat{u}_{ni}-\widehat{u}_{nk_n})\ge\lambda ( r i − r k n ) / ( u ni − u n k n ) ≥ λ . If r i < r k n r_i<r_{k_n} r i < r k n and u ^ n i < u ^ n k n \widehat{u}_{ni}<\widehat{u}_{nk_n} u ni < u n k n , it gives the lower-margin condition $(r_{k_n}-r_i)/(\widehat{u}_{nk_n}-\widehat{u}_{ni})\le\lambda.
Proof of Proposition 7
Let
F ( S , λ ) = λ W N ( S ) + 1 N ∑ n ∈ N min i ∈ S ˉ { r i − λ u ^ n i } F(S,\lambda)=\lambda W_N(S)+\frac{1}{N}\sum_{n\in\mathcal{N}}\min_{i\in\bar{S}}\{r_i-\lambda\hat{u}_{ni}\} F ( S , λ ) = λ W N ( S ) + N 1 n ∈ N ∑ i ∈ S ˉ min { r i − λ u ^ ni }
denote the part of the [DRO-FC] objective that does not contain ϵ \epsilon ϵ . For ϵ 1 < ϵ 2 \epsilon_1<\epsilon_2 ϵ 1 < ϵ 2 , let ( S 1 , λ 1 ) (S_1,\lambda_1) ( S 1 , λ 1 ) and ( S 2 , λ 2 ) (S_2,\lambda_2) ( S 2 , λ 2 ) be joint optimizers. Their optimality gives
F ( S 1 , λ 1 ) − ϵ 1 λ 1 ≥ F ( S 2 , λ 2 ) − ϵ 1 λ 2 , F(S_1,\lambda_1)-\epsilon_1\lambda_1\ge F(S_2,\lambda_2)-\epsilon_1\lambda_2, F ( S 1 , λ 1 ) − ϵ 1 λ 1 ≥ F ( S 2 , λ 2 ) − ϵ 1 λ 2 ,
F ( S 2 , λ 2 ) − ϵ 2 λ 2 ≥ F ( S 1 , λ 1 ) − ϵ 2 λ 1 . F(S_2,\lambda_2)-\epsilon_2\lambda_2\ge F(S_1,\lambda_1)-\epsilon_2\lambda_1. F ( S 2 , λ 2 ) − ϵ 2 λ 2 ≥ F ( S 1 , λ 1 ) − ϵ 2 λ 1 .
Adding the inequalities yields ( ϵ 2 − ϵ 1 ) ( λ 1 − λ 2 ) ≥ 0 (\epsilon_2-\epsilon_1)(\lambda_1-\lambda_2)\ge0 ( ϵ 2 − ϵ 1 ) ( λ 1 − λ 2 ) ≥ 0 , and therefore λ 1 ≥ λ 2 \lambda_1\ge\lambda_2 λ 1 ≥ λ 2 .
Proof of Lemma 2
For convenience let S ˉ = S ∪ { 0 } \bar{S}=S\cup\{0\} S ˉ = S ∪ { 0 } . For every i ∈ S ˉ i\in\bar{S} i ∈ S ˉ , max j ∈ S ˉ U j − U i ≥ 0 \max_{j\in\bar{S}}U_j-U_i\ge0 max j ∈ S ˉ U j − U i ≥ 0 , so the second expression in (11) is nonnegative. Choosing an index i i i that maximizes utility gives ϕ S , λ ( U ) ≤ r i ≤ r ˉ \phi_{S,\lambda}(U)\le r_i\le\bar{r} ϕ S , λ ( U ) ≤ r i ≤ r ˉ . Consequently, for λ > r ˉ / ϵ \lambda>\bar{r}/\epsilon λ > r ˉ / ϵ the dual criterion is at most − λ ϵ + r ˉ < 0 -\lambda\epsilon+\bar{r}<0 − λ ϵ + r ˉ < 0 . Since λ = 0 \lambda=0 λ = 0 attains the nonnegative continuous-extension value, no optimizer lies beyond r ˉ / ϵ \bar{r}/\epsilon r ˉ / ϵ .
Proof of Theorem 1
For S ∈ L S\in\mathcal{L} S ∈ L , let Z N , S = sup λ ≥ 0 ∣ μ ^ S ( λ ) − μ S ( λ ) ∣ Z_{N,S}=\sup_{\lambda\ge0}|\hat{\mu}_S(\lambda)-\mu_S(\lambda)| Z N , S = sup λ ≥ 0 ∣ μ ^ S ( λ ) − μ S ( λ ) ∣ , so Z N = max S ∈ L Z N , S Z_N=\max_{S\in\mathcal{L}}Z_{N,S} Z N = max S ∈ L Z N , S . The inequality sup λ a ( λ ) − sup λ b ( λ ) ≤ sup λ ∣ a ( λ ) − b ( λ ) ∣ \sup_\lambda a(\lambda)-\sup_\lambda b(\lambda)\le\sup_\lambda|a(\lambda)-b(\lambda)| sup λ a ( λ ) − sup λ b ( λ ) ≤ sup λ ∣ a ( λ ) − b ( λ ) ∣ gives, for every ϵ > 0 \epsilon>0 ϵ > 0 and every S ∈ L S\in\mathcal{L} S ∈ L ,
∣ R ϵ ( S ; Q ) − R ^ ϵ ( S ) ∣ ≤ Z N , S ≤ Z N . |R_\epsilon(S;Q)-\hat{R}_\epsilon(S)|\le Z_{N,S}\le Z_N. ∣ R ϵ ( S ; Q ) − R ^ ϵ ( S ) ∣ ≤ Z N , S ≤ Z N .
The penalty − λ ϵ -\lambda\epsilon − λ ϵ does not appear in Z N Z_N Z N , so this comparison is uniform in ϵ \epsilon ϵ . Let S ∗ S^* S ∗ maximize R ϵ ( ⋅ ; Q ) R_\epsilon(\cdot;Q) R ϵ ( ⋅ ; Q ) and recall that S ^ N \hat{S}_N S ^ N maximizes R ^ ϵ \hat{R}_\epsilon R ^ ϵ over L \mathcal{L} L . Then
L N = [ R ϵ ( S ∗ ; Q ) − R ^ ϵ ( S ∗ ) ] + [ R ^ ϵ ( S ∗ ) − R ^ ϵ ( S ^ N ) ] + [ R ^ ϵ ( S ^ N ) − R ϵ ( S ^ N ; Q ) ] ≤ Z N + 0 + Z N = 2 Z N . \begin{aligned}
L_N=[R_\epsilon(S^*;Q)-\hat{R}_\epsilon(S^*)]+[\hat{R}_\epsilon(S^*)-\hat{R}_\epsilon(\hat{S}_N)]+[\hat{R}_\epsilon(\hat{S}_N)-R_\epsilon(\hat{S}_N;Q)] \\
&\le Z_N+0+Z_N=2Z_N.
\end{aligned} L N = [ R ϵ ( S ∗ ; Q ) − R ^ ϵ ( S ∗ )] + [ R ^ ϵ ( S ∗ ) − R ^ ϵ ( S ^ N )] + [ R ^ ϵ ( S ^ N ) − R ϵ ( S ^ N ; Q )] ≤ Z N + 0 + Z N = 2 Z N .
The same comparison of maxima gives ∣ V N , ϵ ∗ − V ϵ ∗ ( Q ) ∣ ≤ Z N |V^*_{N,\epsilon}-V^*_\epsilon(Q)|\le Z_N ∣ V N , ϵ ∗ − V ϵ ∗ ( Q ) ∣ ≤ Z N . Thus (18) and (19) follow from (17) .
It remains to control Z N Z_N Z N . Let Q ^ N \hat{Q}_N Q ^ N denote the empirical distribution of the N N N utility vectors. Fix S S S and set f λ = ϕ S , λ / r ˉ f_\lambda=\phi_{S,\lambda}/\bar{r} f λ = ϕ S , λ / r ˉ . By Lemma 2, f λ f_\lambda f λ takes values in [ 0 , 1 ] [0,1] [ 0 , 1 ] . Each term in the minimum (11) is affine in λ \lambda λ with nonnegative slope, so f λ f_\lambda f λ is continuous and nondecreasing in λ \lambda λ . For t ∈ [ 0 , 1 ] t\in[0,1] t ∈ [ 0 , 1 ] define
τ t ( U ) = inf { λ ≥ 0 : f λ ( U ) > t } , \tau_t(U)=\inf\{\lambda\ge0:f_\lambda(U)>t\}, τ t ( U ) = inf { λ ≥ 0 : f λ ( U ) > t } ,
with the infimum of the empty set equal to + ∞ +\infty + ∞ . The level sets
E λ , t = { U : f λ ( U ) > t } = { U : τ t ( U ) < λ } E_{\lambda,t}=\{U:f_\lambda(U)>t\}=\{U:\tau_t(U)<\lambda\} E λ , t = { U : f λ ( U ) > t } = { U : τ t ( U ) < λ }
are thresholds of the scalar random variable τ t \tau_t τ t . The Dvoretzky–Kiefer–Wolfowitz inequality with Massart’s constant ([16 ] ) therefore yields, for every x > 0 x>0 x > 0 ,
P { sup λ ≥ 0 ∣ Q ^ N ( E λ , t ) − Q ( E λ , t ) ∣ > x } ≤ 2 exp ( − 2 N x 2 ) . \mathbb{P}\left\{\sup_{\lambda\ge0}|\hat{Q}_N(E_{\lambda,t})-Q(E_{\lambda,t})|>x\right\}\le2\exp(-2Nx^2). P { λ ≥ 0 sup ∣ Q ^ N ( E λ , t ) − Q ( E λ , t ) ∣ > x } ≤ 2 exp ( − 2 N x 2 ) .
The layer-cake representation gives
Z N , S r ˉ ≤ ∫ 0 1 sup λ ≥ 0 ∣ Q ^ N ( E λ , t ) − Q ( E λ , t ) ∣ d t . \frac{Z_{N,S}}{\bar{r}}\le\int_0^1\sup_{\lambda\ge0}|\hat{Q}_N(E_{\lambda,t})-Q(E_{\lambda,t})|\,dt. r ˉ Z N , S ≤ ∫ 0 1 λ ≥ 0 sup ∣ Q ^ N ( E λ , t ) − Q ( E λ , t ) ∣ d t .
Taking expectations and applying Tonelli’s theorem,
E [ Z N , S ] r ˉ ≤ ∫ 0 1 ∫ 0 ∞ 2 e − 2 N x 2 d x d t = π 2 N . \frac{\mathbb{E}[Z_{N,S}]}{\bar r} \le\int_0^1 \int_0^\infty2e^{-2Nx^2}\,dx\,dt = \sqrt{\frac{\pi}{2N}}. r ˉ E [ Z N , S ] ≤ ∫ 0 1 ∫ 0 ∞ 2 e − 2 N x 2 d x d t = 2 N π .
Replacing one sampled utility vector changes μ ^ S ( λ ) \hat{\mu}_S(\lambda) μ ^ S ( λ ) by at most r ˉ / N \bar r/N r ˉ / N for every λ \lambda λ , and hence changes Z N , S Z_{N,S} Z N , S by at most r ˉ / N \bar r/N r ˉ / N . Since E [ Z N , S ] ≤ r ˉ π / ( 2 N ) \mathbb{E}[Z_{N,S}] \le\bar r\sqrt{\pi/(2N)} E [ Z N , S ] ≤ r ˉ π / ( 2 N ) , the bounded-difference inequality ([17 ] ) gives
P { Z N , S > r ˉ π 2 N + x } ≤ exp ( − 2 N x 2 r ˉ 2 ) . \mathbb{P}\left\{Z_{N,S} > \bar r\sqrt{\frac{\pi}{2N}}+x\right\} \le\exp\left(-\frac{2Nx^2}{\bar r^2}\right). P { Z N , S > r ˉ 2 N π + x } ≤ exp ( − r ˉ 2 2 N x 2 ) .
Write M = ∣ L ∣ M=|\mathcal{L}| M = ∣ L ∣ , μ = r ˉ π / ( 2 N ) \mu=\bar r\sqrt{\pi/(2N)} μ = r ˉ π / ( 2 N ) , and a = 2 N / r ˉ 2 a=2N/\bar r^2 a = 2 N / r ˉ 2 . A union bound gives P ( Z N > μ + x ) ≤ M exp ( − a x 2 ) \mathbb{P}(Z_N>\mu+x)\le M\exp(-ax^2) P ( Z N > μ + x ) ≤ M exp ( − a x 2 ) for x > 0 x>0 x > 0 . Taking x = log ( M / α ) / a x=\sqrt{\log(M/\alpha)/a} x = log ( M / α ) / a and using Z N ≤ r ˉ Z_N\le\bar r Z N ≤ r ˉ proves (17) .
To bound the expectation, set t 0 = log ( e M ) / a t_0=\sqrt{\log(eM)/a} t 0 = log ( e M ) / a , so M exp ( − a t 0 2 ) = 1 / e M\exp(-at_0^2)=1/e M exp ( − a t 0 2 ) = 1/ e . Integrating the tail gives
E [ Z N ] ≤ μ + t 0 + ∫ t 0 ∞ M exp ( − a x 2 ) d x ≤ μ + t 0 + 1 2 a t 0 . \begin{aligned}
\mathbb{E}[Z_N]\le\mu+t_0+\int_{t_0}^{\infty}M\exp(-ax^2)\,dx \\
&\le\mu+t_0+\frac{1}{2at_0}.
\end{aligned} E [ Z N ] ≤ μ + t 0 + ∫ t 0 ∞ M exp ( − a x 2 ) d x ≤ μ + t 0 + 2 a t 0 1 .
The integral bound uses ∫ t 0 ∞ exp ( − a x 2 ) d x ≤ exp ( − a t 0 2 ) / ( 2 a t 0 ) \int_{t_0}^{\infty}\exp(-ax^2)\,dx\le\exp(-at_0^2)/(2at_0) ∫ t 0 ∞ exp ( − a x 2 ) d x ≤ exp ( − a t 0 2 ) / ( 2 a t 0 ) . Since log ( e M ) ≥ 1 \log(eM)\ge1 log ( e M ) ≥ 1 , one has 1 / ( 2 a t 0 ) ≤ r ˉ / 8 N 1/(2at_0)\le\bar r/\sqrt{8N} 1/ ( 2 a t 0 ) ≤ r ˉ / 8 N . Substituting t 0 = r ˉ log ( e M ) / ( 2 N ) t_0=\bar r\sqrt{\log(eM)/(2N)} t 0 = r ˉ log ( e M ) / ( 2 N ) therefore yields
E [ Z N ] ≤ r ˉ 2 N ( π + 1 2 + 1 + log ∣ L ∣ ) . \mathbb{E}[Z_N]\le\frac{\bar r}{\sqrt{2N}}\left(\sqrt{\pi}+\frac{1}{2}+\sqrt{1+\log|\mathcal{L}|}\right). E [ Z N ] ≤ 2 N r ˉ ( π + 2 1 + 1 + log ∣ L ∣ ) .
Multiplying by two and using L N ≤ 2 Z N L_N\le2Z_N L N ≤ 2 Z N gives (20) .
Proof of Lemma 3
Since λ ≥ 0 \lambda\ge0 λ ≥ 0 in the dual reformulation of Proposition 1, only the upper bound requires proof. We establish it via the exact right-derivative envelope of h h h .
Right-derivative envelope. Recall that h ( λ ) = − λ ϵ + f ( λ ) = − λ ϵ + max S ∈ L G ( S , λ ) h(\lambda)=-\lambda\epsilon+f(\lambda)=-\lambda\epsilon+\max_{S\in\mathcal{L}}G(S,\lambda) h ( λ ) = − λ ϵ + f ( λ ) = − λ ϵ + max S ∈ L G ( S , λ ) . For each fixed S ∈ L S\in\mathcal{L} S ∈ L , G ( S , ⋅ ) G(S,\cdot) G ( S , ⋅ ) is concave and piecewise linear, being an average of pointwise minima of affine functions, and the customer-wise worst-case selection k n ( λ ) ∈ arg min i ∈ S ˉ ( r i − λ u ^ n i ) k_n(\lambda)\in\arg\min_{i\in\bar S}(r_i-\lambda\hat u_{ni}) k n ( λ ) ∈ arg min i ∈ S ˉ ( r i − λ u ^ ni ) is well defined (breaking ties toward the utility-maximizer). Consequently
h S ′ ( λ + ) = − ϵ + 1 N ∑ n ∈ N [ u ^ n , i n ⋆ ( S ) − u ^ n , k n ( S , λ ) ] , h'_S(\lambda^+)=-\epsilon+\frac{1}{N}\sum_{n\in\mathcal{N}}\left[\hat u_{n,i_n^\star(S)}-\hat u_{n,k_n(S,\lambda)}\right], h S ′ ( λ + ) = − ϵ + N 1 n ∈ N ∑ [ u ^ n , i n ⋆ ( S ) − u ^ n , k n ( S , λ ) ] ,
where i n ⋆ ( S ) ∈ arg max i ∈ S ˉ u ^ n i i_n^\star(S)\in\arg\max_{i\in\bar S}\hat u_{ni} i n ⋆ ( S ) ∈ arg max i ∈ S ˉ u ^ ni realizes W N ( S ) W_N(S) W N ( S ) .
Customer-separable bound on the envelope. Fix S S S and n n n . If i n ⋆ ( S ) = 0 i_n^\star(S)=0 i n ⋆ ( S ) = 0 , then u ^ n 0 ≥ u ^ n i \hat u_{n0}\ge\hat u_{ni} u ^ n 0 ≥ u ^ ni for all i ∈ S i\in S i ∈ S and r 0 = 0 ≤ r i r_0=0\le r_i r 0 = 0 ≤ r i , so r 0 − λ u ^ n 0 ≤ r i − λ u ^ n i r_0-\lambda\hat u_{n0}\le r_i-\lambda\hat u_{ni} r 0 − λ u ^ n 0 ≤ r i − λ u ^ ni for all i ∈ S i\in S i ∈ S ; hence the outside option is itself a worst-case minimizer and u ^ n , i n ⋆ ( S ) − u ^ n , k n ( S , λ ) = 0 ≤ D n ( λ ) \hat u_{n,i_n^\star(S)}-\hat u_{n,k_n(S,\lambda)}=0\le D_n(\lambda) u ^ n , i n ⋆ ( S ) − u ^ n , k n ( S , λ ) = 0 ≤ D n ( λ ) . Otherwise, i n ⋆ ( S ) ∈ A i_n^\star(S)\in A i n ⋆ ( S ) ∈ A and, by the minimality of k n ( S , λ ) k_n(S,\lambda) k n ( S , λ ) ,
r k n − λ u ^ n , k n ≤ r i n ⋆ − λ u ^ n , i n ⋆ . r_{k_n}-\lambda\hat u_{n,k_n}\le r_{i_n^\star}-\lambda\hat u_{n,i_n^\star}. r k n − λ u ^ n , k n ≤ r i n ⋆ − λ u ^ n , i n ⋆ .
Rearranging gives r i n ⋆ − r k n ≥ λ ( u ^ n , i n ⋆ − u ^ n , k n ) r_{i_n^\star}-r_{k_n}\ge\lambda(\hat u_{n,i_n^\star}-\hat u_{n,k_n}) r i n ⋆ − r k n ≥ λ ( u ^ n , i n ⋆ − u ^ n , k n ) . The utility gap u ^ n , i n ⋆ − u ^ n , k n \hat u_{n,i_n^\star}-\hat u_{n,k_n} u ^ n , i n ⋆ − u ^ n , k n is non-negative by construction; if it vanishes, the bound 0 ≤ D n ( λ ) 0\le D_n(\lambda) 0 ≤ D n ( λ ) is trivial. If it is strictly positive, then r i n ⋆ > r k n r_{i_n^\star}>r_{k_n} r i n ⋆ > r k n (immediate from the display for λ > 0 \lambda>0 λ > 0 ; at λ = 0 \lambda=0 λ = 0 the minimizer is the outside option, so r k n = 0 < r i n ⋆ r_{k_n}=0<r_{i_n^\star} r k n = 0 < r i n ⋆ ). Moreover, equality in the ratio would make i n ⋆ i_n^\star i n ⋆ and k n k_n k n simultaneous minimizers, in which case the right-derivative tie rule selects the higher-utility alternative i n ⋆ i_n^\star i n ⋆ and the utility gap would be zero. Thus u ^ n , i n ⋆ > u ^ n , k n \hat{u}_{n,i_n^\star} > \hat{u}_{n,k_n} u ^ n , i n ⋆ > u ^ n , k n and ( r i n ⋆ − r k n ) / ( u ^ n , i n ⋆ − u ^ n , k n ) > λ (r_{i_n^\star} - r_{k_n})/(\hat{u}_{n,i_n^\star} - \hat{u}_{n,k_n}) > \lambda ( r i n ⋆ − r k n ) / ( u ^ n , i n ⋆ − u ^ n , k n ) > λ , so the pair ( i n ⋆ , k n ) (i_n^\star, k_n) ( i n ⋆ , k n ) is feasible for the maximization defining D n ( λ ) D_n(\lambda) D n ( λ ) and therefore
u ^ n , i n ⋆ ( S ) − u ^ n , k n ( S , λ ) ≤ D n ( λ ) . \hat{u}_{n,i_n^\star}(S) - \hat{u}_{n,k_n}(S,\lambda) \le D_n(\lambda). u ^ n , i n ⋆ ( S ) − u ^ n , k n ( S , λ ) ≤ D n ( λ ) .
Averaging the bound u ^ n , i n ⋆ − u ^ n , k n ≤ D n ( λ ) \hat{u}_{n,i_n^\star} - \hat{u}_{n,k_n} \le D_n(\lambda) u ^ n , i n ⋆ − u ^ n , k n ≤ D n ( λ ) over n n n and taking the supremum over S ∈ L \mathcal{S} \in\mathcal{L} S ∈ L yields, uniformly in S \mathcal{S} S ,
sup S ∈ L h S ′ ( λ + ) ≤ Φ ( λ ) − ϵ . (41) \sup_{\mathcal{S}\in\mathcal{L}} h_{\mathcal{S}}'(\lambda^+) \le\Phi(\lambda) - \epsilon. \tag*{(41)} S ∈ L sup h S ′ ( λ + ) ≤ Φ ( λ ) − ϵ . (41)
Monotonicity of Φ \Phi Φ . As λ \lambda λ increases, the feasibility set { ( i , j , n ) : ( r i − r j ) / ( u ^ n i − u ^ n j ) > λ } \{(i,j,n) : (r_i-r_j)/(\hat{u}_{ni}-\hat{u}_{nj}) > \lambda\} {( i , j , n ) : ( r i − r j ) / ( u ^ ni − u ^ nj ) > λ } underlying (22) shrinks; hence each D n ( ⋅ ) D_n(\cdot) D n ( ⋅ ) is non-increasing and so is Φ \Phi Φ . At a ratio breakpoint, the corresponding pairs are excluded at the breakpoint itself. Thus Φ \Phi Φ is right-continuous and piecewise constant.
Upper bound on λ ⋆ \lambda^\star λ ⋆ . Let λ u = min { λ ≥ 0 : Φ ( λ ) ≤ ϵ } \lambda^u = \min\{\lambda\ge0 : \Phi(\lambda) \le\epsilon\} λ u = min { λ ≥ 0 : Φ ( λ ) ≤ ϵ } , which is well defined because Φ \Phi Φ is right-continuous, piecewise constant, and eventually zero. By monotonicity, Φ ( λ ) ≤ ϵ \Phi(\lambda) \le\epsilon Φ ( λ ) ≤ ϵ for every λ ≥ λ u \lambda\ge\lambda^u λ ≥ λ u . Equation (EC.18) therefore gives h S ′ ( λ + ) ≤ 0 h_{\mathcal{S}}'(\lambda^+) \le0 h S ′ ( λ + ) ≤ 0 for every S \mathcal{S} S and every λ ≥ λ u \lambda\ge\lambda^u λ ≥ λ u . Hence each h S h_{\mathcal{S}} h S is non-increasing on [ λ u , ∞ ) [\lambda^u,\infty) [ λ u , ∞ ) and attains its maximum over [ 0 , λ u ] [0,\lambda^u] [ 0 , λ u ] . This proves (24) for every product line. Taking the maximum over S ∈ L \mathcal{S} \in\mathcal{L} S ∈ L then yields a joint optimal multiplier in [ 0 , λ u ] [0,\lambda^u] [ 0 , λ u ] . □
Proof of Lemma 4
Monotonicity of W N ( ⋅ ) W_N(\cdot) W N ( ⋅ ) (resp. reverse-monotonicity of C ( ⋅ , λ ) C(\cdot,\lambda) C ( ⋅ , λ ) ) is immediate: max i ∈ S ˉ u ^ n i \max_{i\in\bar{S}}\hat{u}_{ni} max i ∈ S ˉ u ^ ni is non-decreasing and min i ∈ S ˉ ( r i − λ u ^ n i ) \min_{i\in\bar{S}}(r_i-\lambda\hat{u}_{ni}) min i ∈ S ˉ ( r i − λ u ^ ni ) is non-increasing in S S S ; averaging preserves the direction.
Submodularity of W N ( ⋅ ) W_N(\cdot) W N ( ⋅ ) . Fix S 1 ⊆ S 2 ⊆ A S_1 \subseteq S_2 \subseteq\mathcal{A} S 1 ⊆ S 2 ⊆ A and j ∉ S 2 j \notin S_2 j ∈ / S 2 . For every customer n n n ,
max i ∈ S k ∪ { j , 0 } u ^ n i − max i ∈ S k ∪ { 0 } u ^ n i = [ u ^ n j − max i ∈ S k ∪ { 0 } u ^ n i ] + ( k = 1 , 2 ) . \max_{i\in S_k\cup\{j,0\}}\hat{u}_{ni}-\max_{i\in S_k\cup\{0\}}\hat{u}_{ni}
=\left[\hat{u}_{nj}-\max_{i\in S_k\cup\{0\}}\hat{u}_{ni}\right]_+
\qquad(k=1,2). i ∈ S k ∪ { j , 0 } max u ^ ni − i ∈ S k ∪ { 0 } max u ^ ni = [ u ^ nj − i ∈ S k ∪ { 0 } max u ^ ni ] + ( k = 1 , 2 ) .
Because max i ∈ S 1 ∪ { 0 } u ^ n i ≤ max i ∈ S 2 ∪ { 0 } u ^ n i \max_{i\in S_1\cup\{0\}}\hat{u}_{ni} \le\max_{i\in S_2\cup\{0\}}\hat{u}_{ni} max i ∈ S 1 ∪ { 0 } u ^ ni ≤ max i ∈ S 2 ∪ { 0 } u ^ ni , the positive-part expression is non-increasing in S S S . Averaging over n n n and taking the difference gives
W N ( S 1 ∪ { j } ) − W N ( S 1 ) ≥ W N ( S 2 ∪ { j } ) − W N ( S 2 ) , W_N(S_1\cup\{j\})-W_N(S_1) \ge W_N(S_2\cup\{j\})-W_N(S_2), W N ( S 1 ∪ { j }) − W N ( S 1 ) ≥ W N ( S 2 ∪ { j }) − W N ( S 2 ) ,
which is the submodularity of W N ( ⋅ ) W_N(\cdot) W N ( ⋅ ) .
Supermodularity of C ( ⋅ , λ ) C(\cdot,\lambda) C ( ⋅ , λ ) . By the same argument applied to the minimum, for every n n n ,
min i ∈ S k ∪ { 0 } ( r i − λ u ^ n i ) − min i ∈ S k ∪ { j , 0 } ( r i − λ u ^ n i ) = [ min i ∈ S k ∪ { 0 } ( r i − λ u ^ n i ) − ( r j − λ u ^ n j ) ] + . \min_{i\in S_k\cup\{0\}}(r_i-\lambda\hat{u}_{ni})-\min_{i\in S_k\cup\{j,0\}}(r_i-\lambda\hat{u}_{ni})
=\left[\min_{i\in S_k\cup\{0\}}(r_i-\lambda\hat{u}_{ni})-(r_j-\lambda\hat{u}_{nj})\right]_+. i ∈ S k ∪ { 0 } min ( r i − λ u ^ ni ) − i ∈ S k ∪ { j , 0 } min ( r i − λ u ^ ni ) = [ i ∈ S k ∪ { 0 } min ( r i − λ u ^ ni ) − ( r j − λ u ^ nj ) ] + .
Because min i ∈ S 1 ∪ { 0 } ( r i − λ u ^ n i ) ≥ min i ∈ S 2 ∪ { 0 } ( r i − λ u ^ n i ) \min_{i\in S_1\cup\{0\}}(r_i-\lambda\hat{u}_{ni}) \ge\min_{i\in S_2\cup\{0\}}(r_i-\lambda\hat{u}_{ni}) min i ∈ S 1 ∪ { 0 } ( r i − λ u ^ ni ) ≥ min i ∈ S 2 ∪ { 0 } ( r i − λ u ^ ni ) , this positive part is again non-increasing in S S S . Averaging and rearranging yields
C ( S 1 , λ ) − C ( S 1 ∪ { j } , λ ) ≥ C ( S 2 , λ ) − C ( S 2 ∪ { j } , λ ) , C(S_1,\lambda)-C(S_1\cup\{j\},\lambda) \ge C(S_2,\lambda)-C(S_2\cup\{j\},\lambda), C ( S 1 , λ ) − C ( S 1 ∪ { j } , λ ) ≥ C ( S 2 , λ ) − C ( S 2 ∪ { j } , λ ) ,
i.e., − C ( ⋅ , λ ) -C(\cdot,\lambda) − C ( ⋅ , λ ) is submodular, so C ( ⋅ , λ ) C(\cdot,\lambda) C ( ⋅ , λ ) is supermodular. □
Proof of Proposition 8
Fix a completion T ⊆ F \mathcal{T} \subseteq\mathcal{F} T ⊆ F of size t ≤ k t \le k t ≤ k . By submodularity of W N ( ⋅ ) W_N(\cdot) W N ( ⋅ ) ,
W N ( I ∪ T ) − W N ( I ) ≤ ∑ j ∈ T ( W N ( I ∪ { j } ) − W N ( I ) ) = ∑ j ∈ T m j W ( I ) ≤ ∑ q = 1 t m [ q ] W . W_N(\mathcal{I}\cup\mathcal{T})-W_N(\mathcal{I}) \le\sum_{j\in\mathcal{T}}\left(W_N(\mathcal{I}\cup\{j\})-W_N(\mathcal{I})\right)=\sum_{j\in\mathcal{T}}m_j^W(\mathcal{I})\le\sum_{q=1}^{t}m_{[q]}^W. W N ( I ∪ T ) − W N ( I ) ≤ j ∈ T ∑ ( W N ( I ∪ { j }) − W N ( I ) ) = j ∈ T ∑ m j W ( I ) ≤ q = 1 ∑ t m [ q ] W .
For the C ( I , λ ) C(\mathcal{I},\lambda) C ( I , λ ) term, direct calculation gives C ( I , λ ) − C ( I ∪ { j } , λ ) = m j C ( I , λ ) C(\mathcal{I},\lambda)-C(\mathcal{I}\cup\{j\},\lambda)=m_j^C(\mathcal{I},\lambda) C ( I , λ ) − C ( I ∪ { j } , λ ) = m j C ( I , λ ) . If t ≥ 1 t\ge1 t ≥ 1 , monotonicity then gives, for every j ∈ T j\in\mathcal{T} j ∈ T ,
C ( I ∪ T , λ ) ≤ C ( I ∪ { j } , λ ) = C ( I , λ ) − m j C ( I , λ ) . C(\mathcal{I}\cup\mathcal{T},\lambda)\le C(\mathcal{I}\cup\{j\},\lambda)=C(\mathcal{I},\lambda)-m_j^C(\mathcal{I},\lambda). C ( I ∪ T , λ ) ≤ C ( I ∪ { j } , λ ) = C ( I , λ ) − m j C ( I , λ ) .
Thus
C ( I ∪ T , λ ) ≤ C ( I , λ ) − max j ∈ T m j C ( I , λ ) ≤ C ( I , λ ) − m ( t ) C . C(\mathcal{I}\cup\mathcal{T},\lambda)\le C(\mathcal{I},\lambda)-\max_{j\in\mathcal{T}}m_j^C(\mathcal{I},\lambda)\le C(\mathcal{I},\lambda)-m_{(t)}^C. C ( I ∪ T , λ ) ≤ C ( I , λ ) − j ∈ T max m j C ( I , λ ) ≤ C ( I , λ ) − m ( t ) C .
The last inequality follows because a set of t t t free products must contain a product whose decrease in the C ( ⋅ , λ ) C(\cdot,\lambda) C ( ⋅ , λ ) term is at least the t t t -th smallest free-product decrease. For t = 0 t=0 t = 0 , the same expression holds under the convention m ( 0 ) C = 0 m_{(0)}^C=0 m ( 0 ) C = 0 .
Combining the welfare and cost bounds yields
G ( I ∪ T , λ ) ≤ UB ( t ∣ I , F ) ≤ UB m o d ( I , F ) . G(\mathcal{I}\cup\mathcal{T},\lambda)\le\operatorname{UB}(t\mid\mathcal{I},\mathcal{F})\le\operatorname{UB}_{\mathrm{mod}}(\mathcal{I},\mathcal{F}). G ( I ∪ T , λ ) ≤ UB ( t ∣ I , F ) ≤ UB mod ( I , F ) .
Since every admissible completion has some size t ∈ { 0 , … , min ( k , ∣ F ∣ ) } t\in\{0,\ldots,\min(k,|\mathcal{F}|)\} t ∈ { 0 , … , min ( k , ∣ F ∣ )} , the modular component is valid for the at-most-p p p model.
It remains to verify the separable component. For customer n n n , write
d n j u = [ u ^ n j − u ˉ n ( I ) ] + , d n j c = [ c ˉ n ( I , λ ) − ( r j − λ u ^ n j ) ] + . d_{nj}^{u}=[\hat{u}_{nj}-\bar{u}_{n}(\mathcal{I})]_{+},\qquad d_{nj}^{c}=[\bar{c}_{n}(\mathcal{I},\lambda)-(r_{j}-\lambda\hat{u}_{nj})]_{+}. d nj u = [ u ^ nj − u ˉ n ( I ) ] + , d nj c = [ c ˉ n ( I , λ ) − ( r j − λ u ^ nj ) ] + .
For a nonempty completion T \mathcal{T} T , take j n j_{n} j n maximizing d n j u d_{nj}^{u} d nj u over T \mathcal{T} T . The change in customer n n n ’s contribution satisfies
λ max j ∈ T d n j u − max j ∈ T d n j c ≤ λ d n j n u − d n j n c ≤ max j ∈ T η n j ( I , λ ) ≤ [ max j ∈ F η n j ( I , λ ) ] + . \lambda\max_{j\in\mathcal{T}}d_{nj}^{u}-\max_{j\in\mathcal{T}}d_{nj}^{c}\le\lambda d_{nj_n}^{u}-d_{nj_n}^{c}\le\max_{j\in\mathcal{T}}\eta_{nj}(\mathcal{I},\lambda)\le\left[\max_{j\in\mathcal{F}}\eta_{nj}(\mathcal{I},\lambda)\right]_{+}. λ j ∈ T max d nj u − j ∈ T max d nj c ≤ λ d n j n u − d n j n c ≤ j ∈ T max η nj ( I , λ ) ≤ [ j ∈ F max η nj ( I , λ ) ] + .
The last positive part also covers the empty completion. Summing over customers and dividing by N N N proves that UB s e p ( I , F ) \operatorname{UB}_{\mathrm{sep}}(\mathcal{I},\mathcal{F}) UB sep ( I , F ) is valid. The minimum of two valid upper bounds is valid, establishing (29) and the proposition.
Finally, SBMB evaluates G ( I , λ ) G(\mathcal{I},\lambda) G ( I , λ ) at every visited node with I ≠ ∅ \mathcal{I}\ne\varnothing I = ∅ , so nonempty feasible product lines of all cardinalities can update the incumbent. The empty root need not be evaluated because G ( ∅ , λ ) = 0 G(\varnothing,\lambda)=0 G ( ∅ , λ ) = 0 and the best-singleton initialization is nonnegative. Every child preserves ∣ I ∣ ≤ p |\mathcal{I}|\le p ∣ I ∣ ≤ p , and the include/exclude branching tree is finite. A node is discarded only when its valid upper bound does not exceed the incumbent. Because SBMB processes nodes in decreasing order of their bounds, it terminates only when the queue is empty or its largest bound does not exceed the incumbent. No unexplored descendant can then improve the incumbent, so the returned value equals f ( λ ) f(\lambda) f ( λ ) . □
Proof of Lemma 5
Consider any feasible S ∈ L S\in\mathcal{L} S ∈ L . For each n ∈ N n\in\mathcal{N} n ∈ N , min i ∈ S ˉ ( r i − λ u ^ n i ) \min_{i\in\bar{S}}(r_i-\lambda\hat{u}_{ni}) min i ∈ S ˉ ( r i − λ u ^ ni ) is the pointwise minimum of finitely many affine functions of λ \lambda λ and is therefore concave and piecewise linear, so G ( S , ⋅ ) G(S,\cdot) G ( S , ⋅ ) is concave in λ \lambda λ . Except on a finite set of breakpoints where the argmin is set-valued, the right derivative equals
G ′ ( S , λ + ) = W N ( S ) − 1 N ∑ n ∈ N u ^ n , k n ( λ ) , G'(S,\lambda^{+})=W_N(S)-\frac{1}{N}\sum_{n\in\mathcal{N}}\hat{u}_{n,k_n(\lambda)}, G ′ ( S , λ + ) = W N ( S ) − N 1 n ∈ N ∑ u ^ n , k n ( λ ) ,
where k n ( λ ) ∈ arg min i ∈ S ˉ ( r i − λ u ^ n i ) k_n(\lambda)\in\arg\min_{i\in\bar{S}}(r_i-\lambda\hat{u}_{ni}) k n ( λ ) ∈ arg min i ∈ S ˉ ( r i − λ u ^ ni ) is a worst-case product for customer n n n . Since k n ( λ ) ∈ S ˉ k_n(\lambda)\in\bar{S} k n ( λ ) ∈ S ˉ , we have u ^ n , k n ( λ ) ≤ max i ∈ S ˉ u ^ n i \hat{u}_{n,k_n(\lambda)}\le\max_{i\in\bar{S}}\hat{u}_{ni} u ^ n , k n ( λ ) ≤ max i ∈ S ˉ u ^ ni and hence G ′ ( S , λ + ) ≥ 0 G'(S,\lambda^{+})\ge0 G ′ ( S , λ + ) ≥ 0 . Comparing the minimizing product with the outside option gives r k n ( λ ) − λ u ^ n , k n ( λ ) ≤ − λ u ^ n 0 r_{k_n}(\lambda)-\lambda\hat{u}_{n,k_n(\lambda)}\leq-\lambda\hat{u}_{n0} r k n ( λ ) − λ u ^ n , k n ( λ ) ≤ − λ u ^ n 0 . If k n ( λ ) ≠ 0 k_n(\lambda)\neq0 k n ( λ ) = 0 , then r k n ( λ ) > 0 r_{k_n}(\lambda)>0 r k n ( λ ) > 0 , which requires λ > 0 \lambda>0 λ > 0 and u ^ n , k n ( λ ) > u ^ n 0 \hat{u}_{n,k_n(\lambda)}>\hat{u}_{n0} u ^ n , k n ( λ ) > u ^ n 0 . The utilities are equal if k n ( λ ) = 0 k_n(\lambda)=0 k n ( λ ) = 0 . Together with W N ( S ) ≤ N − 1 ∑ n max i ∈ A + u ^ n i W_N(S)\leq N^{-1}\sum_n\max_{i\in A^+}\hat{u}_{ni} W N ( S ) ≤ N − 1 ∑ n max i ∈ A + u ^ ni , this gives
0 ≤ G ′ ( S , λ + ) ≤ 1 N ∑ n ( max i ∈ A + u ^ n i − u ^ n 0 ) = 1 N ∑ n Δ n . 0\leq G'(S,\lambda^+)\leq\frac{1}{N}\sum_n\left(\max_{i\in A^+}\hat{u}_{ni}-\hat{u}_{n0}\right)=\frac{1}{N}\sum_n\Delta_n. 0 ≤ G ′ ( S , λ + ) ≤ N 1 n ∑ ( i ∈ A + max u ^ ni − u ^ n 0 ) = N 1 n ∑ Δ n .
For λ 1 < λ 2 \lambda_1<\lambda_2 λ 1 < λ 2 we therefore have 0 ≤ G ( S , λ 2 ) − G ( S , λ 1 ) ≤ ( 1 N ∑ n Δ n ) ( λ 2 − λ 1 ) 0\leq G(S,\lambda_2)-G(S,\lambda_1)\leq\left(\frac{1}{N}\sum_n\Delta_n\right)(\lambda_2-\lambda_1) 0 ≤ G ( S , λ 2 ) − G ( S , λ 1 ) ≤ ( N 1 ∑ n Δ n ) ( λ 2 − λ 1 ) . Taking the pointwise maximum over S ∈ L S\in\mathcal{L} S ∈ L preserves both the non-negative lower bound and the Lipschitz upper bound: for any S 1 ⋆ ∈ arg max S G ( S , λ 1 ) S_1^\star\in\arg\max_S G(S,\lambda_1) S 1 ⋆ ∈ arg max S G ( S , λ 1 ) ,
f ( λ 2 ) − f ( λ 1 ) ≥ G ( S 1 ⋆ , λ 2 ) − G ( S 1 ⋆ , λ 1 ) ≥ 0 , f(\lambda_2)-f(\lambda_1)\geq G(S_1^\star,\lambda_2)-G(S_1^\star,\lambda_1)\geq0, f ( λ 2 ) − f ( λ 1 ) ≥ G ( S 1 ⋆ , λ 2 ) − G ( S 1 ⋆ , λ 1 ) ≥ 0 ,
and
f ( λ 2 ) − f ( λ 1 ) ≤ max S ∈ L [ G ( S , λ 2 ) − G ( S , λ 1 ) ] ≤ 1 N ∑ n Δ n ⋅ ( λ 2 − λ 1 ) . f(\lambda_2)-f(\lambda_1)\leq\max_{S\in\mathcal{L}}\left[G(S,\lambda_2)-G(S,\lambda_1)\right]\leq\frac{1}{N}\sum_n\Delta_n\cdot(\lambda_2-\lambda_1). f ( λ 2 ) − f ( λ 1 ) ≤ S ∈ L max [ G ( S , λ 2 ) − G ( S , λ 1 ) ] ≤ N 1 n ∑ Δ n ⋅ ( λ 2 − λ 1 ) .
Hence h ′ ( λ + ) = − ϵ + f ′ ( λ + ) ∈ [ − ϵ , 1 N ∑ n Δ n − ϵ ] h'(\lambda^+)=-\epsilon+f'(\lambda^+)\in\left[-\epsilon,\frac{1}{N}\sum_n\Delta_n-\epsilon\right] h ′ ( λ + ) = − ϵ + f ′ ( λ + ) ∈ [ − ϵ , N 1 ∑ n Δ n − ϵ ] wherever it exists; the same bounds extend to the finite difference quotient on the entire interval, which proves (30) .
For λ ∈ [ a , b ] \lambda\in[a,b] λ ∈ [ a , b ] , the slope bounds give h ( λ ) ≤ h ( a ) + L + ( λ − a ) h(\lambda)\leq h(a)+L^+(\lambda-a) h ( λ ) ≤ h ( a ) + L + ( λ − a ) and h ( λ ) ≤ h ( b ) + L − ( b − λ ) h(\lambda)\leq h(b)+L^-(b-\lambda) h ( λ ) ≤ h ( b ) + L − ( b − λ ) . Thus h h h lies below the pointwise minimum of an increasing and a decreasing affine function. Their intersection is a + x a b a+x_{ab} a + x ab ; Equation (30) places it in [ a , b ] [a,b] [ a , b ] . Substitution gives the closed form in (31) . If L + ≤ 0 L^+\leq0 L + ≤ 0 , h h h is non-increasing and λ = 0 \lambda=0 λ = 0 is optimal. □
Proof of Theorem 2
Every product line entering the solution pool is feasible. The affine pieces of h S ( ⋅ ) h_S(\cdot) h S ( ⋅ ) can change only at the pairwise intersections collected in B S B_S B S , and a concave piecewise-linear function attains its maximum over a compact interval at an endpoint or a breakpoint. Lemma 3 shows that [ 0 , λ u ] [0,\lambda^u] [ 0 , λ u ] contains an optimal multiplier for every fixed product line. Consequently, [Pool-BP( S ) (S) ( S ) ] is exact and APS retains a line S ^ \hat{S} S ^ satisfying
R N , ϵ F C ( S ^ ) = max λ ≥ 0 h S ^ ( λ ) = H S ^ = h b e s t , R_{N,\epsilon}^{\mathrm{FC}}(\hat{S})=\max_{\lambda\geq0}h_{\hat{S}}(\lambda)=H_{\hat{S}}=h_{\mathrm{best}}, R N , ϵ FC ( S ^ ) = λ ≥ 0 max h S ^ ( λ ) = H S ^ = h best ,
so h b e s t h_{\mathrm{best}} h best is a valid lower bound on V N , ϵ ⋆ V_{N,\epsilon}^\star V N , ϵ ⋆ . Every SBMB call returns the exact value h ( λ ) h(\lambda) h ( λ ) , so Lemma 5 makes UB ∗ ( [ a , b ] ) \operatorname{UB}^{\ast}([a,b]) UB ∗ ([ a , b ]) a valid upper bound for every active interval.
Let λ ⋆ \lambda^\star λ ⋆ maximize h h h on [ 0 , λ u ] [0,\lambda^u] [ 0 , λ u ] . If the active interval containing λ ⋆ \lambda^\star λ ⋆ has not been pruned, then
V N , ϵ ⋆ = h ( λ ⋆ ) ≤ max [ a , b ] ∈ I λ UB ∗ ( [ a , b ] ) = : u b max . V_{N,\epsilon}^\star=h(\lambda^\star)\leq\max_{[a,b]\in\mathcal{I}_\lambda}\operatorname{UB}^{\ast}([a,b])=:ub_{\max}. V N , ϵ ⋆ = h ( λ ⋆ ) ≤ [ a , b ] ∈ I λ max UB ∗ ([ a , b ]) =: u b m a x .
If that interval was pruned earlier, its upper bound did not exceed the incumbent at that time, so the current incumbent already satisfies h b e s t ≥ V N , ϵ ⋆ ≥ ( 1 − δ ) V N , ϵ ⋆ h_{\mathrm{best}}\geq V_{N,\epsilon}^\star\geq(1-\delta)V_{N,\epsilon}^\star h best ≥ V N , ϵ ⋆ ≥ ( 1 − δ ) V N , ϵ ⋆ . In the unpruned case, the termination test u b max − h b e s t ≤ δ u b max ub_{\max}-h_{\mathrm{best}}\leq\delta\,ub_{\max} u b m a x − h best ≤ δ u b m a x implies
h b e s t ≥ ( 1 − δ ) u b max ≥ ( 1 − δ ) V N , ϵ ⋆ . h_{\mathrm{best}}\geq(1-\delta)ub_{\max}\geq(1-\delta)V_{N,\epsilon}^\star. h best ≥ ( 1 − δ ) u b m a x ≥ ( 1 − δ ) V N , ϵ ⋆ .
It remains to prove the stated evaluation bound. Let S W ∈ arg max S ∈ L W N ( S ) S^{\mathrm{W}}\in\arg\max_{S\in\mathcal{L}}W_N(S) S W ∈ arg max S ∈ L W N ( S ) . Under the empirical distribution, Corollary 1 gives
ϵ † = W N ( S W ) − 1 N ∑ n ∈ N u ^ n 0 ≤ 1 N ∑ n ∈ N Δ n . \epsilon^\dagger=W_N(S^{\mathrm{W}})-\frac{1}{N}\sum_{n\in\mathcal{N}}\hat{u}_{n0}\leq\frac{1}{N}\sum_{n\in\mathcal{N}}\Delta_n. ϵ † = W N ( S W ) − N 1 n ∈ N ∑ u ^ n 0 ≤ N 1 n ∈ N ∑ Δ n .
Thus ϵ < ϵ † \epsilon< \epsilon^\dagger ϵ < ϵ † implies L + > 0 L^+ > 0 L + > 0 , while the assumption ϵ > 0 \epsilon> 0 ϵ > 0 gives L − = ϵ > 0 L^- = \epsilon> 0 L − = ϵ > 0 . First note that V N , ϵ ⋆ > 0 V^\star_{N,\epsilon} > 0 V N , ϵ ⋆ > 0 . Indeed, h S W ( 0 ) = 0 h_{\mathrm{SW}}(0) = 0 h SW ( 0 ) = 0 , and because r 0 = 0 < r i r_0 = 0 < r_i r 0 = 0 < r i for i ∈ A i \in\mathcal{A} i ∈ A , its right derivative at zero is
h S W ′ ( 0 + ) = − ϵ + W N ( S W ) − 1 N ∑ n ∈ N u ^ n 0 = ϵ † − ϵ > 0. h'_{\mathrm{SW}}(0^+) = -\epsilon+ W_N(\mathcal{S}^{\mathrm{W}}) - \frac{1}{N}\sum_{n\in\mathcal{N}}\hat{u}_{n0} = \epsilon^\dagger- \epsilon> 0. h SW ′ ( 0 + ) = − ϵ + W N ( S W ) − N 1 n ∈ N ∑ u ^ n 0 = ϵ † − ϵ > 0.
A direct calculation from (31) gives, for every active interval [ a , b ] [a,b] [ a , b ] ,
UB ∗ ( [ a , b ] ) − max { h ( a ) , h ( b ) } ≤ K ( b − a ) , K = L + L − L + + L − . \operatorname{UB}^\ast([a,b]) - \max\{h(a),h(b)\} \le K(b-a), \qquad K = \frac{L^+L^-}{L^+ + L^-}. UB ∗ ([ a , b ]) − max { h ( a ) , h ( b )} ≤ K ( b − a ) , K = L + + L − L + L − .
APS always selects an interval with the largest active upper bound, and both endpoints of that interval have already been evaluated. Hence, if the selected interval has width b − a b-a b − a ,
ub max − h b e s t ≤ UB ∗ ( [ a , b ] ) − max { h ( a ) , h ( b ) } ≤ K ( b − a ) . \operatorname{ub}_{\max} - h_{\mathrm{best}} \le\operatorname{UB}^\ast([a,b]) - \max\{h(a),h(b)\} \le K(b-a). ub m a x − h best ≤ UB ∗ ([ a , b ]) − max { h ( a ) , h ( b )} ≤ K ( b − a ) .
Define
x δ = K λ ν δ V N , ϵ ⋆ ≥ 0 , d δ = ⌈ log 2 max { 1 , x δ } ⌉ . x_\delta= \frac{K\lambda^\nu}{\delta V^\star_{N,\epsilon}} \ge0, \qquad d_\delta= \left\lceil\log_2\max\{1,x_\delta\}\right\rceil. x δ = δ V N , ϵ ⋆ K λ ν ≥ 0 , d δ = ⌈ log 2 max { 1 , x δ } ⌉ .
An interval at depth q q q in the midpoint-bisection tree has width λ ν / 2 q \lambda^\nu/2^q λ ν / 2 q . By the definition of d δ d_\delta d δ , every interval at depth q ≥ d δ q \ge d_\delta q ≥ d δ satisfies
K ( b − a ) ≤ K λ ν 2 d δ ≤ δ V N , ϵ ⋆ . K(b-a) \le\frac{K\lambda^\nu}{2^{d_\delta}} \le\delta V^\star_{N,\epsilon}. K ( b − a ) ≤ 2 d δ K λ ν ≤ δ V N , ϵ ⋆ .
If such an interval were selected, either the interval containing an optimizer had already been pruned, in which case the incumbent is optimal, or ub max ≥ V N , ϵ ⋆ \operatorname{ub}_{\max} \ge V^\star_{N,\epsilon} ub m a x ≥ V N , ϵ ⋆ . In the latter case,
ub max − h b e s t ≤ δ V N , ϵ ⋆ ≤ δ ub max , \operatorname{ub}_{\max} - h_{\mathrm{best}} \le\delta V^\star_{N,\epsilon} \le\delta\operatorname{ub}_{\max}, ub m a x − h best ≤ δ V N , ϵ ⋆ ≤ δ ub m a x ,
so APS would stop before bisecting that interval. Consequently, APS can bisect only nodes at depths q < d δ q < d_\delta q < d δ . The complete binary tree contains 2 d δ − 1 2^{d_\delta}-1 2 d δ − 1 such nodes; this quantity is zero when d δ = 0 d_\delta= 0 d δ = 0 . Pruning can only reduce this count. Each bisection requires one new exact fixed-λ \lambda λ evaluation, in addition to the two initial endpoint evaluations, yielding B ≤ 2 d δ + 1 B \le2^{d_\delta}+1 B ≤ 2 d δ + 1 . Since d δ = ⌈ log 2 max { 1 , x δ } ⌉ d_\delta= \left\lceil\log_2\max\{1,x_\delta\}\right\rceil d δ = ⌈ log 2 max { 1 , x δ } ⌉ , we have 2 d δ < 2 max { 1 , x δ } 2^{d_\delta} < 2\max\{1,x_\delta\} 2 d δ < 2 max { 1 , x δ } . Thus, on every empirical sample,
V N , ϵ ⋆ − h b e s t ≤ δ V N , ϵ ⋆ , B < 2 max { 1 , K λ ν δ V N , ϵ ⋆ } + 1. V^\star_{N,\epsilon} - h_{\mathrm{best}} \le\delta V^\star_{N,\epsilon}, \qquad B < 2\max\left\{1,\frac{K\lambda^\nu}{\delta V^\star_{N,\epsilon}}\right\}+1. V N , ϵ ⋆ − h best ≤ δ V N , ϵ ⋆ , B < 2 max { 1 , δ V N , ϵ ⋆ K λ ν } + 1.
Proof of Corollary 3
If ϵ < ϵ † ( Q ^ N ) \epsilon< \epsilon^\dagger(\widehat{Q}_N) ϵ < ϵ † ( Q N ) , Theorem 2 gives R N , ϵ F C ( S ^ ) ≥ ( 1 − δ ) V N , ϵ ⋆ R^{\mathrm{FC}}_{N,\epsilon}(\widehat{S}) \ge(1-\delta)V^\star_{N,\epsilon} R N , ϵ FC ( S ) ≥ ( 1 − δ ) V N , ϵ ⋆ . Otherwise, taking the outside option in each minimum in C ( S , λ ) C(S,\lambda) C ( S , λ ) gives
h S ( λ ) ≤ λ ( W N ( S ) − N − 1 ∑ n ∈ N u ^ n 0 − ϵ ) ≤ 0 ( S ∈ L , λ ≥ 0 ) , h_S(\lambda) \le\lambda\left(W_N(S)-N^{-1}\sum_{n\in\mathcal{N}}\hat{u}_{n0}-\epsilon\right)\le0 \qquad(S\in\mathcal{L},\ \lambda\ge0), h S ( λ ) ≤ λ ( W N ( S ) − N − 1 n ∈ N ∑ u ^ n 0 − ϵ ) ≤ 0 ( S ∈ L , λ ≥ 0 ) ,
where the last inequality uses the definition of ϵ † ( Q ^ N ) \epsilon^\dagger(\widehat{Q}_N) ϵ † ( Q N ) . Since h S ( 0 ) = 0 h_S(0)=0 h S ( 0 ) = 0 , the empty line is optimal in this case, so the same bound holds for every sample. By the uniform comparison following (15) , R ϵ ( S ^ ; Q ) ≥ R N , ϵ F C ( S ^ ) − Z N R_\epsilon(\widehat{S};Q)\ge R^{\mathrm{FC}}_{N,\epsilon}(\widehat{S})-Z_N R ϵ ( S ; Q ) ≥ R N , ϵ FC ( S ) − Z N and V N , ϵ ⋆ ≥ V ϵ ⋆ ( Q ) − Z N V^\star_{N,\epsilon}\ge V^\star_\epsilon(Q)-Z_N V N , ϵ ⋆ ≥ V ϵ ⋆ ( Q ) − Z N . Combining these inequalities gives
R ϵ ( S ^ ; Q ) ≥ ( 1 − δ ) V N , ϵ ⋆ − Z N ≥ ( 1 − δ ) V ϵ ⋆ ( Q ) − ( 2 − δ ) Z N . R_\epsilon(\widehat{S};Q)\ge(1-\delta)V^\star_{N,\epsilon}-Z_N\ge(1-\delta)V^\star_\epsilon(Q)-(2-\delta)Z_N. R ϵ ( S ; Q ) ≥ ( 1 − δ ) V N , ϵ ⋆ − Z N ≥ ( 1 − δ ) V ϵ ⋆ ( Q ) − ( 2 − δ ) Z N .
Taking expectations and using the bound on E [ Z N ] \mathbb{E}[Z_N] E [ Z N ] from the proof of Theorem 1 yields (33) .