Theorem 5: a markup-ordered assortment is optimal, with long service on an adjusted markup-ordered subset

Consider the dealer's problem (13): prices $p_i$ and qualities $q_i$ are fixed, and the dealer chooses disjoint sets $S_l,S_s\subseteq\mathcal N$ of products offered with long service $t_l$ and short service $t_s$ to maximize $\Pi^s(\mathbf p,\mathbf q;S_l,S_s)$. Write $z_i=p_i-c_iq_i^2-t_s(a_i-b_iq_i)$ for the markup with short service, and $x_i=(p_i-c_iq_i^2)-A_i(a_i-b_iq_i)$ with $A_i=\frac{t_l e^{t_ls_i}-t_s e^{t_ss_i}}{e^{t_ls_i}-e^{t_ss_i}}$ for the adjusted markup. A markup-ordered assortment is a set of the form $\{i: z_i\ge\theta\}$ and an adjusted markup-ordered set one of the form $\{i: x_i\ge\theta'\}$.

Theorem 5. Assume $t_s<t_l$, and $s_i>0$ and $a_i-b_iq_i\ge0$ for every product. Then there are thresholds $\theta,\theta'$ such that, with $S_{i^*}=\{i: z_i\ge\theta\}$ and $S_{j^\natural}=\{i: x_i\ge\theta'\}$:

1. (a) $S_{i^*}$ is an optimal offer set for (13);
2. (b) $S_{j^\natural}\subseteq S_{i^*}$, and attaching the long service to $S_{j^\natural}$ and the short service to $S_{i^*}\setminus S_{j^\natural}$ is optimal:

Consequently at most $O(N^2)$ candidate pairs need to be examined, and long service goes to the products with the highest adjusted profit margins.

Formalization Note The paper relabels products by decreasing markup and calls a prefix $\{1,\dots,i\}$ a markup-ordered assortment. Here such sets are the upper level sets $\{i: z_i\ge\theta\}$ and $\{i: x_i\ge\theta'\}$; every level set is a prefix of every decreasing relabelling, so the statement holds whatever tie-break the relabelling uses. The empty set and the full set are allowed. Parts (a) and (b) share the same $S_{i^*}$: (a) is the optimality of the pair in (b), whose union is $S_{i^*}$. The hypotheses $t_s<t_l$, $s_i>0$ and $a_i-b_iq_i\ge0$ are the model's standing assumptions made explicit (shortest and longest duration, service utility, service cost); the first two make $A_i$ well defined, and without the third part (b) is false.