Sturt

The value of robust assortment optimization under ranking-based choice models

The Value of Robust Assortment Optimization Under Ranking-based Choice Models

Bradley Sturt Department of Information and Decision Sciences
University of Illinois at Chicago<EMAIL_ADDRESS>
We study a class of robust assortment optimization problems that was proposed
by Farias, Jagabathula, and Shah (2013). The goal in this class of problems is
to find an assortment that maximizes a firm’s worst-case expected revenue
under all ranking-based choice models that are consistent with the historical
sales data generated by the firm’s past assortments. Despite its significance
in the revenue management literature, this class of robust optimization
problems is widely believed to be computationally intractable, and no
practical algorithms for solving these problems have been developed thus far.

Our main contributions in this paper are three-fold. First, we establish that
optimal assortments for these robust optimization problems have a simple
structure that is closely related to the structure of revenue-ordered
assortments. Second, we demonstrate that the class of robust optimization
problems can be solved in reasonable computation times in various settings of
practical importance. Specifically, we develop exact algorithms for solving
the robust optimization problems that run in polynomial time for any fixed
number of past assortments. Moreover, when the firm’s past assortments satisfy
a common assumption, we show that the robust optimization problem can be
reformulated as a compact mixed-integer linear optimization problem of size
that is polynomial in the number of products as well as the number of past
assortments. Third, we use our algorithms and structural results to derive a
number of managerial insights regarding the value of robust optimization and
the risks of estimate-then-optimize in the context of data-driven assortment
optimization with ranking-based choice models.

assortment planning; robust optimization; nonparametric choice modeling.

First version: December 9, 2021. This version: February 16, 2023.

“First, do no harm” - Hippocratic Oath

##  1 Introduction

The ranking-based choice model is one of the most fundamental and influential
discrete choice models in revenue management. It is used by firms in a variety
of industries (such as e-commerce and brick-and-mortar retail) to predict the
demand for the firm’s products as a function of the subset of products that
the firm offers to their customers. The popularity of the ranking-based choice
model can be attributed to its generality: it can represent _any_ random
utility maximization model, and thus encompasses many other popular discrete
choice models such as the multinomial logit model (Block and Marschak 1959,
Farias et al. 2013). The ranking-based choice model posits that customers who
visit the firm have preferences that are represented by randomly-chosen
rankings, and, based on the subset of products offered by the firm, each
customer will purchase the product that is most preferred according to their
personal ranking.

Unfortunately, estimating a ranking-based choice model from a firm’s
historical sales data is notoriously challenging. The key issue is that the
ranking-based choice model is comprised of around $n!$ parameters, where $n$
is the number of product alternatives that a firm can elect to offer to their
customers. Because the number of past subsets of products $M$ that the firm
has previously offered to their customers usually satisfies $M\ll n!$, many
selections of these parameters can yield a ranking-based choice model that is
consistent (has low or zero prediction error) with the firm’s historical sales
data. This leaves firms with the challenge of selecting _which_ ranking-based
choice model, out of all of those that are consistent with their historical
sales data, to use when making operational planning decisions.

The challenge of estimation in ranking-based choice models is particularly
acute in the context of assortment planning. Here, the typical goal of a firm
is to identify a new subset of products (referred to as an assortment) to
offer to their customers in order to increase the firm’s expected revenue.
Because the true relationship between assortments and expected revenue is
unknown, firms will typically interpret an estimated ranking-based choice
model as “ground truth” and subsequently solve an optimization problem to find
an assortment which maximizes the “predicted” expected revenue (Aouad et al.
2018, Bertsimas and Mišić 2019, Honhon et al. 2012, van Ryzin and Vulcano
2015, 2017, Feldman et al. 2019, Aouad et al. 2021, Désir et al. 2021). This
widely-used technique for identifying a new assortment is referred to in the
revenue management literature as _estimate-then-optimize_. The estimate-then-
optimize technique can be attractive from a computational standpoint, due to
its decoupling of the combinatorial problems related to estimation and
optimization. But the assortment which is optimal under one selection of a
ranking-based choice model that is consistent with the historical sales data
may be highly _suboptimal_ under another ranking-based choice model that is
also consistent with the historical sales data. This raises concerns about
whether estimate-then-optimize can be trusted to identify a new assortment for
the firm with an expected revenue that, at the very least, is no less than the
firm’s highest expected revenue from their past assortments.

###  1.1 A Robust Optimization Approach

We study a class of robust assortment optimization problems proposed by
Farias, Jagabathula, and Shah (2013, henceforth abbreviated as FJS13) that
aims to circumvent the risks from using estimate-then-optimize with ranking-
based choice models. The goal of the class of robust optimization problems,
stated succinctly, is to find an assortment that has high expected revenue
under _all_ of the ranking-based choice models that are consistent with the
historical sales data generated by the firm’s past assortments. The robust
optimization problems achieve this goal by yielding an assortment that
maximizes the predicted expected revenue under the worst-case ranking-based
choice model that is consistent with the historical sales data generated by
the firm’s past assortments. Formally, the class of robust optimization
problems can be stated as

$\displaystyle\underset{S\in\mathcal{S}}{\textnormal{max}}\min_{\lambda\in\mathcal{U}}\mathscr{R}^{\lambda}(S),$
(RO)

where $\mathcal{S}$ is the set of all assortments that can be offered by the
firm to its customers, $\mathcal{U}$ is the set of all ranking-based choice
models that are consistent with the historical sales data generated by the
firm’s past assortments, and $\mathscr{R}^{\lambda}(S)$ is the expected
revenue for a new assortment $S$ under a ranking-based choice model
$\lambda\in\mathcal{U}$.

The class of robust optimization problems (RO) can be attractive from a firm’s
perspective for a variety of reasons. Indeed, solving the robust optimization
problem (RO) enables one to find a new assortment that can be trusted to
improve the firm’s expected revenue in a way that is not exclusive to just one
of the many ranking-based choice models that are consistent with the firm’s
historical sales data. Moreover, the optimal objective value of the robust
optimization problem (RO) can provide a warning that implementing an
assortment found by an estimate-then-optimize technique can result in lower
expected revenues than maintaining the status quo. Finally, FJS13 showed using
real-world data that the worst-case expected revenue
$\min_{\lambda\in\mathcal{U}}\mathscr{R}^{\lambda}(S)$ can be a significantly
more accurate prediction of expected revenue compared to the predictions made
by parametric methods. Hence, there is empirical evidence that the assortments
obtained from solving (RO) may be desirable to firms from a revenue-improving
perspective.

Despite the appeal of the class of robust optimization problems (RO), very
limited progress has been made on solving these robust optimization problems
up to this point. As far as we can tell, the only prior work that considers
the computational tractability of (RO) is that of FJS13, which presented
algorithms for computing the worst-case expected revenue of a fixed
assortment. However, no algorithms to date have been developed in the
literature for solving this class of robust optimization problems
(Rusmevichientong and Topaloglu (2012, p.867), Jagabathula (2014, p.8)), and
“it is not clear how one may formulate the problem of optimizing the worst-
case revenue as an efficiently solvable mathematical optimization
formulation.” (Mišić 2016, p.118). This lack of progress is especially
notable, in view of the fact that algorithms and structural results have been
developed for other classes of robust assortment optimization problems
(Rusmevichientong and Topaloglu 2012, Bertsimas and Mišić 2017, Désir et al.
2023, Wang et al. 2020).

The lack of practical algorithms and structural results for (RO) has
ultimately prevented a formal assessment of the managerial value of the class
of robust optimization problems (RO). On one hand, the robust optimization
problem (RO) promises to help firms circumvent the risks of estimate-then-
optimize by searching for an assortment that performs well across all of the
ranking-based choice models that are consistent with the firm’s historical
sales data. But on the other hand, no previous work has established whether
assortments $S\in\mathcal{S}$ that have high expected revenue
$\mathscr{R}^{\lambda}(S)$ across all ranking-based choice models
$\lambda\in\mathcal{U}$ can ever _exist_. Because the question of whether (RO)
is too conservative to be practically valuable has remained open, the extent
to which robust optimization can actually overcome the concerns of the
estimate-then-optimize technique in data-driven assortment optimization with
ranking-based choice models has been unknown.

###  1.2 Contributions

In this paper, we pursue an agenda of understanding _if_ and _when_ the class
of robust optimization problems (RO) can provide value to firms as an
alternative to estimate-then-optimize. In the pursuit of this agenda, we make
three main contributions. First, we establish that optimal assortments for
these robust optimization problems have a simple structure that is closely
related to the structure of revenue-ordered assortments. Second, we show in
various settings of practical importance that the class of robust optimization
problems (RO) can either be solved in polynomial time or can be reformulated
as a compact mixed-integer linear optimization problem. Third, we use our
structural results and algorithms to derive a number of managerial insights
regarding the value of robust optimization and the risks of estimate-then-
optimize in the context of data-driven assortment optimization with ranking-
based choice models. In greater detail, our contributions in this paper can be
stated as follows:

####  1.2.1 Characterization of optimal assortments.

To facilitate the design of efficient algorithms, we establish the first
characterization of the structure of optimal assortments for robust
optimization problems of the form (RO) (Theorem 3.1 in §3). Our theorem
reveals that optimal assortments for these robust optimization problems have a
simple and interpretable structure that is similar to the structure of the
widely-studied class of revenue-ordered assortments. This structure is
important because it allows us to drastically reduce the number of candidate
assortments that need to be checked in order to solve the robust optimization
problem. Our proof of Theorem 3.1 is based on an elementary yet intricate
analysis of reachability conditions for vertices in a data-driven class of
directed acyclic graphs.

####  1.2.2 Polynomial-time algorithms.

Harnessing our characterization of the structure of optimal assortments, we
develop the first polynomial-time algorithms for solving the class of robust
optimization problems (RO). The existence of polynomial-time algorithms
resolves the open question in the literature regarding the theoretical
tractability of (RO) for various settings of practical importance, and we
provide numerical evidence that our algorithms are also practically efficient.
Our developments are summarized as follows:

  * •

Revenue-ordered past assortments: We show that the robust optimization problem
(RO) can be solved in closed form when the collection of previously-offered
assortments is equal to the widely-studied class of revenue-ordered
assortments (Theorem 4.2 in §4.1). Specifically, when the historical sales
data is generated from the revenue-ordered assortments, our structural result
reveals that the optimal assortment for the robust optimization problem is
equal to the previously-offered assortment with the highest expected revenue,
regardless of the prices of the products and the observations of the
historical sales data. Theorem 4.2 further implies that there can exist
settings in which it is impossible to identify an assortment with an expected
revenue that outperforms the expected revenue of the firm’s past assortments
over all ranking-based choice models that are consistent with firm’s
historical sales data.

  * •

Two past assortments: We use our structure of optimal assortments to develop a
strongly polynomial-time algorithm for solving the robust optimization problem
when the firm has offered two past assortments (Theorem 4.3 in §4.2). Our
algorithm reduces the robust optimization problem to a sequence of minimum-
cost network flow problems, which can be readily solved using off-the-shelf
optimization software, and our algorithm has a total running time of
$\mathcal{O}(n^{5}\log(nr_{n}))$, where $r_{n}$ is the integral price of the
most expensive product. We provide numerical experiments showing that our
algorithm can be practically tractable, running in less than 30 seconds for
problem instances with $n=100$ products.

  * •

Fixed number of past assortments: We generalize our algorithm from §4.2 to
show that the class of robust optimization problems (RO) can be solved in
weakly polynomial time for any fixed number of past assortments (Theorem 4.7
in §4.3). The algorithm provides evidence that it can be possible to develop
practical algorithms for solving the robust optimization problem (RO) for
real-world problem instances, where the composition of products in the
previously-offered assortments do not exhibit any convenient structure and
where there may be no ranking-based choice models that have zero prediction
error on the historical sales data.

####  1.2.3 Practical algorithms for nested past assortments.

We next show that our characterization of the structure of optimal assortments
can be used to develop refined algorithms in applications in which the past
assortments enjoy additional structure. Specifically, we consider a common
assumption in the revenue management literature in which the past assortments
that were offered by the firm to its customers are nested (see §5 for
details). For applications in which the past assortments are nested, we
develop the following results:

  * •

Exponential growth with number of past assortments: We provide a theoretical
analysis of the efficiency of the proposed algorithm from §4.3 in applications
where the number of past assortments is large. Indeed, the algorithm from §4.3
has running time that grows linearly in $|\widehat{\mathcal{S}}|$, where
$\widehat{\mathcal{S}}\subseteq\mathcal{S}$ is the collection of candidate
assortments identified by Theorem 3.1. To understand the worst-case
relationship between $|\widehat{\mathcal{S}}|$ and the number of past
assortments, we introduce a collection of nested assortments that we dub
_reverse revenue-ordered assortments_. When the past assortments are reverse
revenue-ordered, we show that $|\widehat{\mathcal{S}}|$ grows exponentially in
the number of past assortments, and we prove for this example that
$\widehat{\mathcal{S}}$ is an exact description of the collection of
assortments that can be optimal for the robust optimization problem (Theorem
5.3 in §5.1). This shows that the techniques used in §4.3 cannot generally
yield polynomial-time algorithms for robust optimization problems with large
numbers of past assortments, even when the past assortments satisfy common
structural assumptions such as nested.

  * •

Compact mixed-integer reformulations for nested past assortments: Despite the
seemingly negative result from Theorem 5.3, we show that our developments from
Theorem 3.1 can nonetheless be used to develop practical algorithms for
solving the robust optimization problem (RO) in settings where the number of
past assortments is reasonably large. Specifically, we show that our
structural developments from §3 can be used to develop a compact mixed-integer
linear optimization reformulation of the robust optimization problem (RO) when
the previously-offered assortments are nested (Theorem 5.8 in §5.2).
Importantly, our mixed-integer linear optimization formulation contains only
$n$ integer decision variables, and the total number of decision variables and
constraints of the mixed-integer linear optimization problem scales
polynomially in both the number of products as well as the number of past
assortments. We show using numerical experiments that our mixed-integer linear
optimization problem is practically tractable, requiring less than 30 seconds
to solve (RO) to optimality on problem instances with up to $M=20$ past
assortments.

  * •

Reducing the conservatism of robust optimization: Building upon our
algorithmic developments from §5.2, we revisit settings in which it might be
impossible to identify an assortment with an expected revenue that outperforms
the expected revenue of the firm’s past assortments over all ranking-based
choice models that are consistent with firm’s historical sales data. To
address such settings in which the robust optimization problem (RO) is overly
conservative, we consider optimization problems of the form

$\displaystyle\underset{S\in\mathcal{S}}{\textnormal{maximize}}$
$\displaystyle\max_{\lambda\in\mathcal{U}}\mathscr{R}^{\lambda}(S)$ (RO-
Pareto) subject to
$\displaystyle\min_{\lambda\in\mathcal{U}}\mathscr{R}^{\lambda}(S)\geq\theta.$

In contrast to the robust optimization problem (RO), the optimization problem
(RO-Pareto) aims to find an assortment that maximizes the best-case expected
revenue while imposing a lower bound on the worst-case expected revenue. Using
our reformulation techniques from §5.2, we show that (RO-Pareto) can be
reformulated as a mixed-integer linear optimization problem with size that is
polynomial in the number of products as well as the number of past assortments
when the past assortments are nested (Theorem 5.9 in §5.3).

####  1.2.4 Numerical Insights.

Finally, we conduct numerical experiments to investigate the managerial value
of the class of robust optimization problems (RO) and the risks of using
estimate-then-optimize in the context of assortment optimization with ranking-
based choice models.

  * •

The risk of estimate-then-optimize with revenue-ordered past assortments:
Motivated by the impossibility result from Theorem 4.2, we perform numerical
experiments in §4.1 to assess the performance of assortments obtained using
estimate-then-optimize when the historical sales data is randomly generated
from revenue-ordered assortments. The results of our experiments are striking:
in more than 98% of the problem instances in which the estimate-then-optimize
technique recommended a new assortment, the worst-case decline in expected
revenue from implementing the new assortment (relative to the expected revenue
from the best past assortment) exceeded the best-case increase in expected
revenue. The difference in magnitude between the worst-case and best-case
change in expected revenue from implementing the new assortment found from
estimate-then-optimize is also significant; the average best-case improvement
of the new assortment over the best previously-offered assortment is 6.56%,
while the average worst-case improvement of the new assortment over the best
previously-offered assortment is -21.71%. Our results thus demonstrate that
estimate-then-optimize with ranking-based choice models can risk leading to
significant declines in a firm’s expected revenue, even in settings in which
the firm has implemented a celebrated and widely-recommended class of
assortments.

  * •

The value of robust optimization with small numbers of past assortments:
Equipped with our polynomial-time algorithms from §4, we conduct numerical
experiments to assess the conservatism of the robust optimization problem (RO)
in applications with small numbers of past assortments. Indeed, if the firm
has offered a small number of past assortments, then the set of ranking-based
choice models $\mathcal{U}$ that are consistent with the historical sales data
will be expansive. Hence, one might expect in such applications that the
robust optimization problem (RO) will be too conservative to be practically
valuable.

Our numerical experiments in §4.2 show that the above intuition can be
_incorrect_. Specifically, we conduct numerical experiments on randomly
generated problem instances in which the firm has offered only two past
assortments. The output of the experiments reveals that it can be possible to
identify assortments that outperform the firm’s past assortments over all
ranking-based choice models that are consistent with the firm’s historical
sales data, even in the seemingly limited case of two past assortments. We
further refine our experiments to construct a simple example with four
products in which it is possible to identify such a revenue-improving
assortment. These findings thus demonstrate that the robust optimization
problem (RO) may not be overly conservative and can yield practical value to
firms, even when a small number of assortments have been offered in the past.

  * •

A low-risk approach to experimentation: Finally, we present numerical
experiments in §5.3 that showcase the attractiveness of the optimization
problem (RO-Pareto) in offering firms a low-risk approach to experimenting
with the assortments that they offer to their customers. Indeed, by varying
the parameter $\theta$, we show that (RO-Pareto) can generate a Pareto
frontier of new assortments that a firm can offer to its customers that offer
varying degrees of possible improvements to the firm’s expected revenue while
enjoying guaranteed bounds on the worst-case declines in expected revenue that
the firm may incur. On various examples of datasets generated from nested past
assortments, we show that our algorithm for solving the optimization problem
(RO-Pareto) can (a) discover new assortments with high best-case and low
worst-case expected revenue, (b) deliver upper bounds on the expected revenue
that could be obtained if the true ranking-based choice model that generated
the historical sales data was known, and (c) provide experimentation
strategies to firms when the robust optimization problem (RO) is overly
conservative.

Our paper is organized as follows. In §2, we present our problem setting. In
§3, we develop our key structural result which characterizes the optimal
solutions for robust optimization problems under ranking-based choice models.
In §4, we develop polynomial-time algorithms for solving the robust
optimization problem. In §5, we develop refined algorithms when the past
assortments are nested. In §6, we offer concluding thoughts and directions for
future research. For brevity, all lengthy proofs of intermediary results are
found in the appendices.

##### Notation and Terminology.

We use $\mathbb{R}$ to denote the real numbers, $\mathbb{R}_{+}$ to denote the
nonnegative real numbers, and $y^{\intercal}x$ to denote the inner product of
two vectors. We use the phrase ‘collection’ to refer to a set of sets. We let
the set of all probability distributions which are supported on a finite set
$\mathscr{A}$ be denoted by
$\Delta_{\mathscr{A}}\triangleq\\{\lambda:\sum_{a\in\mathscr{A}}\lambda_{a}=1,\;\lambda_{a}\geq
0\;\forall a\in\mathscr{A}\\}$. We assume throughout that a norm $\|\cdot\|$
is either the $\ell_{1}$-norm or $\ell_{\infty}$-norm, and so it follows that
optimization problems of the form
$\min_{x,y}\\{c^{\intercal}x+d^{\intercal}y\mid Ax+By\leq
b,\;\|y\|\leq\eta\\}$ can be referred to as linear optimization problems. We
let $\mathbb{I}\\{\cdot\\}$ denote the indicator function, which equals one if
$\cdot$ is true and equals zero otherwise.

##### Code Availability.

The code for conducting the numerical experiments in this paper is freely
available and can be accessed at https://github.com/brad-
sturt/IdentificationQuestion.

##  2 Problem Setting

We adopt the perspective of a firm that must select a subset of products to
offer to their customers. Let the universe of products available to the firm
be denoted by $\mathcal{N}\triangleq\\{1,\ldots,n\\}$, where the no-purchase
option is denoted by index $0$ and
$\mathcal{N}_{0}\triangleq\mathcal{N}\cup\\{0\\}$. The revenue generated by
selling one unit of product $i\in\mathcal{N}$ is represented by $r_{i}>0$, and
the revenue associated with the no-purchase option is $r_{0}=0$. We assume
throughout the paper that the revenues of the products are unique and that
products have been sorted in ascending order by revenue,
$0<r_{1}<\cdots<r_{n}$.  An assortment is defined as any subset of products
$S\subseteq\mathcal{N}_{0}$, and we let
$\mathcal{S}\triangleq\\{S\subseteq\mathcal{N}_{0}:0\in S\\}$ denote the
collection of all assortments that include the no-purchase option.

We study a problem setting in which the underlying relationship between
assortment and customer demand is unknown, and our only information on this
relationship comes from historical sales data generated by the firm’s
previously-offered assortments. Let the previously-offered assortments be
denoted by
$\mathscr{M}\triangleq\\{S_{1},\ldots,S_{M}\\}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\subseteq\mathcal{N}_{0}},$
and let the indices of these past assortments be denoted by
$\mathcal{M}\triangleq\\{1,\ldots,M\\}$. Unless stated otherwise, we will make
no assumptions on the mechanism by which the firm selected the assortments to
offer in the past. That is, the firm could have chosen the previously-offered
assortments by drawing products randomly; alternatively, the previously-
offered assortments could have been chosen using managerial intuition or some
other systematic approach. We assume that the firm offered each past
assortment $S_{m}\in\mathscr{M}$ to their customers for a sufficient duration
to obtain an accurate estimate of the purchase frequencies, _i.e._ , the
fraction of customers $v_{m,i}\in[0,1]$ that purchase product $i\in S_{m}$
when offered assortment $S_{m}$. This historical sales data is assumed to be
normalized such that $\sum_{i\in\mathcal{N}_{0}}v_{m,i}=1$, and the purchase
frequencies for products that are not in an assortment are defined equal to
zero, that is, $v_{m,i}=0$ for all $i\notin S_{m}$ and $m\in\mathcal{M}$.

A discrete choice model is a function that predicts purchase frequencies for
the firm based on the assortment that the firm offers to their customers. A
_ranking-based choice model_ is a type of choice model which is parameterized
by a probability distribution $\lambda$ over the set of all distinct rankings
of the products, where a ranking refers to a one-to-one mapping of the form
$\sigma:\\{0,\ldots,n\\}\to\\{0,\ldots,n\\}$. Specifically, a ranking $\sigma$
encodes a preference for product $i$ over product $j$ if and only if
$\sigma(i)<\sigma(j)$. Let the set of all distinct rankings over the products
be denoted by $\Sigma$, and we readily observe that the number of distinct
rankings in this set satisfies $|\Sigma|=(n+1)!$. Given a probability
distribution over rankings $\lambda\in\Delta_{\Sigma}$ and an assortment
$S\in\mathcal{S}$, the prediction made by the ranking-based choice model for
the purchase frequency of each product $i\in\mathcal{N}_{0}$ is given by

$\displaystyle\mathscr{D}^{\lambda}_{i}(S)\triangleq\sum_{\sigma\in\Sigma}\mathbb{I}\left\\{i=\argmin_{j\in
S}\sigma(j)\right\\}\lambda_{\sigma}.$

It is straightforward to see from the above definition that a ranking-based
choice model always satisfies the equality $\mathscr{D}^{\lambda}_{i}(S)=0$
for all products $i$ that are not in the assortment $S$. The predicted
expected revenue for a firm that offers assortment $S$ under the ranking-based
choice model with parameter $\lambda$ is given by

$\displaystyle\mathscr{R}^{\lambda}(S)\triangleq\sum_{i\in\mathcal{N}_{0}}r_{i}\mathscr{D}^{\lambda}_{i}(S)=r^{\intercal}\mathscr{D}^{\lambda}(S).$

We say that a ranking-based choice model is _consistent_ with the historical
sales data generated by the firm’s previously-offered assortments if the
difference between the predicted purchase frequency
$\mathscr{D}^{\lambda}_{i}(S_{m})$ and the historical sales data $v_{m,i}$ is
small for each of the products $i\in S_{m}$ that were offered in each of the
previously-offered assortments $m\in\mathcal{M}$. We define the set of all
ranking-based choice models that are consistent with the historical sales data
as

$\displaystyle\mathcal{U}\triangleq\left\\{\lambda\in\Delta_{\Sigma}:\quad\begin{aligned}
&\textnormal{there exists a vector }\epsilon\textnormal{ such that
}\|\epsilon\|\leq\eta\textnormal{ and }\\\
&\mathscr{D}^{\lambda}_{i}(S_{m})-v_{m,i}=\epsilon_{m,i}\textnormal{ for all
}i\in S_{m}\text{ and }m\in\mathcal{M}\end{aligned}\right\\},$

where the radius $\eta\geq 0$ of the set $\mathcal{U}$ is a parameter that is
selected by the firm, and where $\|\cdot\|$ is defined at the end of §1 as
either the $\ell_{1}$ or $\ell_{\infty}$ norm.

To develop an understanding for the above set of ranking-based choice models
$\mathcal{U}$, let us consider the case in which the radius $\eta$ of the
above set is equal to zero. In that case, we observe that the above set
contains exactly the probability distributions for which the corresponding
ranking-based choice models have perfect accuracy on the historical sales data
generated by the previously-offered assortments. In other words, if $\eta=0$,
then the set $\mathcal{U}$ is comprised of all of the probability
distributions $\lambda\in\Delta_{\Sigma}$ that satisfy
$\mathscr{D}^{\lambda}_{i}(S_{m})=v_{m,i}$ for each of the products $i\in
S_{m}$ that were offered in each of the previously-offered assortments
$m\in\mathcal{M}$. From a theoretical perspective, it is known that the set
$\mathcal{U}$ with $\eta=0$ is guaranteed to be nonempty if the firm’s
customers’ behavior is captured by a random utility maximization model and if
the historical sales data has been observed without noise; see Block and
Marschak (1959). From a practical perspective, it can be reasonable to expect
that the set $\mathcal{U}$ will be nonempty with $\eta=0$ in problem instances
in which the number of previously-offered assortments $M$ is much smaller than
the number of parameters in the ranking-based choice model, $|\Sigma|=(n+1)!$.
Nonetheless, if there are no ranking-based choice models that have perfect
accuracy on the historical sales data, then the radius $\eta$ can always be
made sufficiently large to ensure that the set of ranking-based choice models
$\mathcal{U}$ is nonempty.111A sufficiently large choice of $\eta$ which
ensures that $\mathcal{U}$ is nonempty can easily be found by applying binary
search over the choice of $\eta$, provided that one has an algorithm that
either solves (RO). For simplicity, we make the standing assumption throughout
our paper that the set of ranking-based choice models $\mathcal{U}$ is
nonempty for the firm’s selection of the radius $\eta$.

We conclude the present section with a theoretical derivation of the class of
robust optimization problems (RO). Indeed, consider a firm that wishes to
identify an assortment with an expected revenue that is strictly greater than
expected revenues of the firm’s past assortments under all of the ranking-
based choice models that are consistent with firm’s historical sales data. In
this case, the firm seeks an assortment $S\in\mathcal{S}$ that satisfies

$\displaystyle\mathscr{R}^{\lambda}(S)$
$\displaystyle>\max\left\\{\mathscr{R}^{\lambda}(S_{1}),\ldots,\mathscr{R}^{\lambda}(S_{M})\right\\}\quad\forall\lambda\in\mathcal{U}.$
(IMP)

If $\eta=0$, then it follows from algebra222If $\eta=0$, then we observe for
each past assortment $m\in\mathcal{M}$ that
$\mathscr{R}^{\lambda}(S_{m})=r^{\intercal}\mathscr{D}^{\lambda}(S_{m})=r^{\intercal}v_{m}$
for all $\lambda\in\mathcal{U}$. that an assortment $S\in\mathcal{S}$
satisfies (IMP) if and only if

$\displaystyle\min_{\lambda\in\mathcal{U}}\mathscr{R}^{\lambda}(S)>\max_{m\in\mathcal{M}}r^{\intercal}v_{m}.$

The above analysis shows that there exists an assortment that satisfies (IMP)
if and only if the optimal objective value of the robust optimization problem
(RO) is strictly greater than $\max_{m\in\mathcal{M}}r^{\intercal}v_{m}$.
Moreover, if there exists an assortment that satisfies (IMP), then every
optimal solution of the robust optimization problem (RO) satisfies (IMP).
Hence, we conclude that the robust optimization problem (RO) enjoys
theoretical justification as a tool for identifying a new assortment with an
expected revenue that, at the very least, is no less than the firm’s highest
expected revenue from their past assortments.

##  3 Characterization of Optimal Assortments for (RO)

In this section, we establish the first characterization of the structure of
optimal assortments for the robust optimization problem (RO). In particular,
we show that there are optimal assortments for (RO) with a simple structure
that is closely related to the structure of revenue-ordered assortments.
Recall the following definition of the collection of revenue-ordered
assortments:

$\displaystyle\bar{\mathcal{S}}\triangleq\left\\{S\in\mathcal{S}:\;\textnormal{if
}i^{*}\in S\textnormal{ and }r_{i^{*}}<r_{i},\textnormal{ then }i\in
S\right\\}.$

A fundamental result in the theory of assortment optimization is that revenue-
ordered assortments are optimal under the multinomial logit choice model
(Talluri and Van Ryzin 2004, Gallego et al. 2004, Rusmevichientong et al.
2014). Revenue-ordered assortments also have attractive approximation
guarantees for assortment optimization problems under mixture-of-logits and
ranking-based choice models with known parameters (Rusmevichientong et al.
2014, Aouad et al. 2018, Berbeglia and Joret 2020). Due to their simplicity
and strong theoretical and empirical performance, revenue-ordered assortments
are widely recommended in the revenue management literature and used in
industry.

In view of the above background, we proceed to develop our main result
regarding the structure of optimal assortments for the robust optimization
problem (RO). To this end, we first define the following set of previously-
offered assortments for each product $i\in\mathcal{N}_{0}$:

$\displaystyle\mathcal{M}_{i}\triangleq\left\\{m\in\mathcal{M}:i\in
S_{m}\right\\}.$

In words, the above set contains all of the previously-offered assortments in
which the firm offered product $i$ to their customers. In particular, we
observe from this definition that the statement
$\mathcal{M}_{i}\subseteq\mathcal{M}_{j}$ holds if, for all of the previously-
offered assortments in which the firm offered product $i$, the firm also
offered product $j$. We now introduce the following new collection of
assortments:

$\displaystyle\widehat{\mathcal{S}}$
$\displaystyle\triangleq\left\\{S\in\mathcal{S}:\;\textnormal{if }i^{*}\in
S,\;r_{i^{*}}<r_{i},\textnormal{ and
}\mathcal{M}_{i^{*}}\subseteq\mathcal{M}_{i},\textnormal{ then }i\in
S\right\\}.$

The above collection has a natural interpretation as the collection of all
assortments which, speaking informally, can be viewed as revenue-ordered
_relative to_ the firm’s previously-offered assortments. Indeed, consider two
products $i^{*},i\in\mathcal{N}_{0}$ for which the revenue $r_{i^{*}}$ from
the first product $i^{*}$ is strictly less than the revenue $r_{i}$ from the
second product $i$. Then every assortment $S\in\widehat{\mathcal{S}}$ which
offers the first product must also offer the second product _unless_ there is
historical sales data from a previously-offered assortment in which the first
product $i^{*}$ was offered and the second product $i$ was not offered. Our
main result is the following:

###### Theorem 3.1

There exists an assortment $S\in\widehat{\mathcal{S}}$ that is optimal for
(RO).

As a consequence of Theorem 3.1, we will be able to develop exact algorithms
for solving the robust optimization problem (RO) that consist of optimizing
over only the assortments in the collection $\widehat{\mathcal{S}}$. In §4, we
develop and analyze the tractability of such exact algorithms.

We conclude the present section by describing the proof strategy of Theorem
3.1, which is split into two steps. In the first step of the proof of Theorem
3.1, which is formalized below as Proposition 3.5, we show that computing the
worst-case expected revenue
$\min_{\lambda\in\mathcal{U}}\mathscr{R}^{\lambda}(S)$ corresponding to any
fixed assortment $S\in\mathcal{S}$ can be reformulated as a linear
optimization problem with $\mathcal{O}(n^{M})$ decision variables and
$\mathcal{O}(nM)$ constraints. Indeed, for each assortment $S\in\mathcal{S}$
and each product in the assortment $i\in S$, let the set of rankings that
prefer product $i$ to all other products in the assortment $S$ be defined as
follows:

###### Definition 3.2

$\mathcal{D}_{i}(S)\triangleq\left\\{\sigma\in\Sigma:\;i=\argmin_{j\in
S}\sigma(j)\right\\}$.

Given the past assortments $S_{1},\ldots,S_{M}$, we also define the following
set of tuples of products:

###### Definition 3.3

$\mathcal{L}\triangleq\left\\{(i_{1},\ldots,i_{M})\in S_{1}\times\cdots\times
S_{M}:\;\bigcap_{m\in\mathcal{M}}\mathcal{D}_{i_{m}}(S_{m})\neq\emptyset\right\\}$.

We readily observe from the above definitions that a tuple of products
satisfies $(i_{1},\ldots,i_{M})\in\mathcal{L}$ if and only if there exists a
ranking $\sigma\in\Sigma$ for which $i_{1}$ is the most preferred product
under that ranking in assortment $S_{1}$, $i_{2}$ is the most preferred
product under that ranking in assortment $S_{2}$, and so on and so forth. For
convenience, we henceforth say that a ranking $\sigma\in\Sigma$ corresponds to
a tuple $(i_{1},\ldots,i_{M})\in\mathcal{L}$ if and only if
$\sigma\in\bigcap_{m\in\mathcal{M}}\mathcal{D}_{i_{m}}(S_{m})$. Finally, for
each assortment $S\in\mathcal{S}$ and each tuple of products
$(i_{1},\ldots,i_{M})\in\mathcal{L}$, we let $\rho_{i_{1}\cdots i_{M}}(S)$ be
defined as the minimum revenue among the products in the assortment $S$ that
can be the most preferred product in $S$ under a ranking that corresponds to
the tuple $(i_{1},\ldots,i_{M})$.

###### Definition 3.4

$\rho_{i_{1}\cdots i_{M}}(S)\triangleq\min\limits_{i\in
S:\;\cap_{m\in\mathcal{M}}\mathcal{D}_{i_{m}}(S_{m})\cap\mathcal{D}_{i}(S)\neq\emptyset}r_{i}$.

Equipped with the above notation, the following result shows that the worst-
case expected revenue of any fixed assortment can be reformulated as a linear
optimization problem:

###### Proposition 3.5

For each $S\in\mathcal{S}$,
$\min_{\lambda\in\mathcal{U}}\mathscr{R}^{\lambda}(S)$ is equal to the optimal
objective value of the following linear optimization problem:

$\displaystyle\;\underset{\lambda,\epsilon}{\textnormal{minimize}}$
$\displaystyle\sum_{(i_{1},\ldots,i_{M})\in\mathcal{L}}\rho_{i_{1}\cdots
i_{M}}(S)\lambda_{i_{1}\cdots i_{M}}$ (1) subject to
$\displaystyle\sum_{(i_{1},\ldots,i_{M})\in\mathcal{L}:\;i_{m}=i}\lambda_{i_{1}\cdots
i_{M}}-\epsilon_{m,i}=v_{m,i}\quad\forall m\in\mathcal{M},\;i\in S_{m}$
$\displaystyle\sum_{(i_{1},\ldots,i_{M})\in\mathcal{L}}\lambda_{i_{1}\cdots
i_{M}}=1$ $\displaystyle\|\epsilon\|\leq\eta$
$\displaystyle\lambda_{i_{1}\cdots i_{M}}\geq
0\quad\forall(i_{1},\ldots,i_{M})\in\mathcal{L}.$

The decision variables $\lambda_{i_{1}\cdots i_{M}}\geq 0$ in the linear
optimization problem (1) can be interpreted as the likelihood that a randomly-
arriving customer will have preferences that follow a ranking that corresponds
to the tuple $(i_{1},\ldots,i_{M})\in\mathcal{L}$. The following two remarks
articulate the key properties of (1) that will be important to our
developments in the subsequent discussions.

###### Remark 3.6

The assortment $S$ does not appear in any of the constraints of (1).

###### Remark 3.7

(1) has $|\mathcal{L}|=\mathcal{O}(n^{M})$ decision variables and
$\mathcal{O}(nM)$ constraints.

We note that the asymptotic upper bound in Remark 3.7 on the number of
decision variables in the linear optimization problem (1) follows immediately
from the fact that the set of tuples of products $\mathcal{L}$ is a subset of
$S_{1}\times\cdots\times S_{M}$; see Definition 3.3.

The second step of the proof of Theorem 3.1, which is formalized below as
Proposition 3.8, consists of analyzing the behavior of the functions
$S\mapsto\rho_{i_{1}\cdots i_{M}}(S)$. To motivate this second step, let us
reflect on the structure of the linear optimization problem from Proposition
3.5. Indeed, we recall from Remark 3.6 that the set of feasible solutions of
the linear optimization problem (1) is independent of the assortment
$S\in\mathcal{S}$. We thus observe that if two assortments
$S,S^{\prime}\in\mathcal{S}$ satisfy $\rho_{i_{1}\cdots
i_{M}}(S)\leq\rho_{i_{1}\cdots i_{M}}(S^{\prime})$ for all tuples of products
$(i_{1},\ldots,i_{M})\in\mathcal{L}$, then Proposition 3.5 implies that the
worst-case expected revenue of the first assortment,
$\min_{\lambda\in\mathcal{U}}\mathscr{R}^{\lambda}(S),$ will be less than or
equal to the worst-case expected revenue of the second assortment,
$\min_{\lambda\in\mathcal{U}}\mathscr{R}^{\lambda}(S^{\prime})$. Against this
backdrop, the following result completes the proof of Theorem 3.1 by showing
that every assortment $S\in\mathcal{S}$ can be exchanged for an assortment
$S^{\prime}\in\widehat{\mathcal{S}}$ with the same or better worst-case
expected revenue:

###### Proposition 3.8

For each assortment $S\in\mathcal{S}$, there exists an assortment
$S^{\prime}\in\widehat{\mathcal{S}}$ which satisfies the inequality
$\rho_{i_{1}\cdots i_{M}}(S)\leq\rho_{i_{1}\cdots i_{M}}(S^{\prime})$ for each
$(i_{1},\ldots,i_{M})\in\mathcal{L}$.

Our proof of Proposition 3.8, which is found in Appendix 7, consists of
developing a graphical interpretation of the quantities $\rho_{i_{1}\cdots
i_{M}}(S)$. Specifically, we begin in Appendix 7.2 by showing that every tuple
of products $(i_{1},\ldots,i_{M})\in\mathcal{L}$ can be represented as a
directed acyclic graph in which there is a vertex for each product
$i\in\mathcal{N}_{0}$. Moreover, we show that $\rho_{i_{1}\cdots i_{M}}(S)$
can be computed by searching over the products in the directed acyclic graph
corresponding to the tuple $(i_{1},\ldots,i_{M})\in\mathcal{L}$ that do not
have a directed path to any vertices corresponding to the products in the
assortment $S$ (Proposition 7.11 in Appendix 7.2). We then exploit this
graphical interpretation of $\rho_{i_{1}\cdots i_{M}}(S)$ in Appendix 7.3 to
relate the quantities $\rho_{i_{1}\cdots i_{M}}(S)$ and $\rho_{i_{1}\cdots
i_{M}}(S\cup\\{i\\})$ and complete the proof of Proposition 3.8. The proof of
Theorem 3.1 follows immediately from Propositions 3.5 and 3.8.

##  4 Polynomial-Time Algorithms

In this section, we use Theorem 3.1 to develop the first polynomial-time
algorithms for solving the robust optimization problem (RO), both for specific
collections of previously-offered assortments (§4.1) as well as for general
classes of problems (§4.2 and §4.3). We use these findings, together with
stylized numerical experiments, to investigate the risks of using estimate-
then-optimize with ranking-based choice models (§4.1) and the managerial value
of the class of robust optimization problems (RO) in applications with small
numbers of past assortment (§4.2.2).

###### Remark 4.1

We assume throughout §4 and the subsequent §5 that every product
$i\in\mathcal{N}_{0}$ has been offered by the firm to its customers in at
least one of the past assortments, that is,
$\cup_{m\in\mathcal{M}}S_{m}=\mathcal{N}_{0}$. This assumption simplifies our
notation and can always be satisfied by redefining $\mathcal{N}_{0}$ to be
equal to $\cup_{m\in\mathcal{M}}S_{m}$. Such a redefining of $\mathcal{N}_{0}$
does not impact the optimal objective value of the robust optimization problem
(RO); see Appendix 8 for further details.

###  4.1 Closed-form Algorithm for Revenue-Ordered Assortments

We begin by returning to the widely-studied class of revenue-ordered
assortments that was discussed in the beginning of §3. Due to their simplicity
and desirable theoretical guarantees, a large body of literature has advocated
to firms for offering revenue-ordered assortments across numerous application
domains. Equipped with Theorem 3.1 we now show, surprisingly, that a firm
which has offered the revenue-ordered assortments has, in a rigorous sense,
operated under a worst-possible behavior from the perspective of finding new
assortments that are guaranteed to outperform the firm’s past assortments:

###### Theorem 4.2

If $\mathscr{M}=\bar{\mathcal{S}}$ and $\eta=0$, then
$\max\limits_{S\in\mathcal{S}}\min\limits_{\lambda\in\mathcal{U}}\mathscr{R}^{\lambda}(S)=\max\limits_{m\in\mathcal{M}}r^{\intercal}v_{m}$.

The above Theorem 4.2 shows that an optimal assortment for the robust
optimization problem (RO) can be obtained in closed form by computing
$r^{\intercal}v_{m}$ for each of the past assortments $m\in\mathcal{M}$.
Importantly, Theorem 4.2 establishes that we can never have  assortments that
satisfy (IMP) when the firm has historical sales data that is generated by the
revenue-ordered assortments. That is, it is impossible using the given
historical sales data to identify a new assortment with a predicted expected
revenue that strictly outperforms the expected revenues of the firm’s past
assortments under all of the ranking-based choice models that are consistent
with the firm’s historical sales data.

To understand the practical importance of Theorem 4.2, let us consider the
estimate-then-optimize technique discussed in §1. In other words, suppose that
one estimates a ranking-based choice model from the historical sales data
generated by the revenue-ordered assortments and then recommends that the firm
implement a new assortment which maximizes the predicted expected revenue
under the estimated ranking-based choice model. For this setting, Theorem 4.2
guarantees that this estimate-then-optimize technique will never offer
_fidelity_ to the firm, in the sense that there will always exist a ranking-
based choice model which is consistent with the historical sales data for
which the expected revenue for the new assortment will be less than or equal
to the expected revenue of the best previously-offered assortment. Moreover,
as we will further see through the following concise yet insightful numerical
experiment, the expected revenue from the assortment recommended by the
estimate-then-optimize technique can be strictly less than the expected
revenue of the best previously-offered assortment.

To perform our numerical experiment, we begin by constructing randomly-
generated problem instances. In each problem instance, the revenues for the
products are drawn from the distribution
$r_{1},\ldots,r_{n}\sim\textnormal{Uniform}[0,1]$, and a base choice for the
parameters $\lambda^{*}$ of a ranking-based choice model is drawn uniformly
over the $(n+1)!$-dimensional probability simplex.333If the rankings in
$\Sigma$ are indexed by $\\{\sigma_{1},\ldots,\sigma_{(n+1)!}\\}$, then
uniform sampling over the probability simplex is obtained by drawing
$u_{1},\ldots,u_{(n+1)!}\sim\textnormal{Uniform}[0,1]$ and setting
$\lambda_{\sigma_{k}}\leftarrow\log(u_{k})/\sum_{k^{\prime}=1}^{(n+1)!}\log(u_{k^{\prime}})$
for each $k=1,\ldots,(n+1)!$.  Using this base choice for the parameters, we
generate historical sales data of the form $v_{1},\ldots,v_{n}$, where each
$v_{m}$ is the historical sales data generated by the revenue-ordered
assortment $\\{0,m,m+1,\ldots,n-1,n\\}$ under the ranking-based choice model
with the base parameter $\lambda^{*}$.444We sort the products in ascending
order by revenue before performing our analysis, which ensures that
$\\{0,m,m+1,\ldots,n\\}$ for each $m\in\\{1,\ldots,n\\}$ is a revenue-ordered
assortment. After we compute the historical sales data, we _forget_ the base
parameters $\lambda^{*}$ of the ranking-based choice model and apply the
estimate-then-optimize technique to obtain a new assortment. Specifically, we
first estimate the parameters $\hat{\lambda}$ of a ranking-based choice model
using the historical sales data; since many selections of the parameters may
be consistent with the historical sales data, we choose our estimate
$\hat{\lambda}$ as the optimal solution to the linear optimization problem
$\min_{\lambda\in\mathcal{U}}c^{\intercal}\lambda$, where the cost vector $c$
is drawn uniformly over $[0,1]^{(n+1)!}$.555Alternative approaches for
estimating the parameters of a ranking-based choice model from historical
sales data are provided in Mišić (2016), van Ryzin and Vulcano (2015, 2017),
Désir et al. (2021). Our approach of estimating the parameters as
$\hat{\lambda}\in\argmin_{\lambda\in\mathcal{U}}c^{\intercal}\lambda$ for a
randomly-chosen cost vector $c$ is motivated by our desire to decouple any
potential biases associated with any particular estimation procedure from an
empirical assessment of the estimate-then-optimize technique. In particular,
our approach is viewed as a simple way of randomly sampling the parameters
from the set of all parameters of ranking-based choice models which are
consistent with the historical sales data. 666An obvious downside of our
simple estimation procedure for the parameters of the ranking-based choice
model is that it requires solving a linear optimization problem with
$\mathcal{O}(n!)$ decision variables, and, thus, our simple estimation
procedure does not scale efficiently to problem instances with many products.
Nonetheless, this estimation procedure is sufficiently fast for the purposes
of this numerical study, where the aim is simply to assess the performance of
assortments obtained by the estimate-then-optimize technique over revenue-
ordered assortments. In particular, we believe it is a reasonable assumption
that similar findings from our numerical experiment with $n=4$ (see Figures
4.1 and 4.1) would be found in experiments with larger values of $n$. We then
obtain a new assortment $S^{\prime}$ as any optimal solution to the
combinatorial optimization problem
$\max_{S\in\mathcal{S}}\mathscr{R}^{\hat{\lambda}}(S)$ which maximizes the
predicted expected revenue under the estimated ranking-based choice
model.777We solve this optimization problem using the mixed-integer linear
optimization formulation given by Bertsimas and Mišić (2019, §3.2), which is
implemented using the Julia programming language with JuMP and solved using
Gurobi. Finally, we evaluate the new assortment obtained using estimate-then-
optimize by computing the worst-case expected revenue of the new assortment
under all ranking-based choice models that are consistent with the historical
sales data, $\min_{\lambda\in\mathcal{U}}\mathscr{R}^{{\lambda}}(S^{\prime})$,
the best-case expected revenue of the new assortment under all ranking-based
choice models that are consistent with the historical sales data,
$\max_{\lambda\in\mathcal{U}}\mathscr{R}^{{\lambda}}(S^{\prime})$, and the
expected revenue of the best previously-offered assortment,
$\max_{m\in\mathcal{M}}r^{\intercal}v_{m}$.

Performance of new assortments obtained using the estimate-then-optimize
technique when $\mathscr{M}=\bar{\mathcal{S}}$. Each point corresponds to a
randomly-generated problem instance. The $x$-axis shows the expected revenue
of the best previously-offered assortment,
$\max_{m\in\mathcal{M}}r^{\intercal}v_{m}$. The $y$-axis shows the worst-case
expected revenue
$\min_{\lambda\in\mathcal{U}}\mathscr{R}^{\lambda}(S^{\prime})$ for the new
assortment $S^{\prime}$ obtained using the estimate-then-optimize technique.

Relative improvement in expected revenue of new assortments obtained using the
estimate-then-optimize technique when $\mathscr{M}=\bar{\mathcal{S}}$. Each of
the $x$-values corresponds to one of the 137 randomly-generated problem
instances from Figure 4.1 for which the expected revenue of the best
previously-offered assortment, $\max_{m\in\mathcal{M}}r^{\intercal}v_{m}$, was
strictly greater than the worst-case expected revenue
$\min_{\lambda\in\mathcal{U}}\mathscr{R}^{\lambda}(S^{\prime})$ for the new
assortment $S^{\prime}$ obtained using the estimate-then-optimize technique.
The corresponding interval of $y$-values formed by the red and blue bars is
the interval $[\Pi_{\lambda}:\lambda\in\mathcal{U}]$, where
$\Pi_{\lambda}\triangleq
100\%\times(\mathscr{R}^{\lambda}(S^{\prime})-\max_{m\in\mathcal{M}}r^{\intercal}v_{m})/(\max_{m\in\mathcal{M}}r^{\intercal}v_{m})$
is the relative percentage improvement of the expected revenue of the new
assortment obtained using estimate-then-optimize over the expected revenue of
the firm’s best previously-offered assortment for a given ranking-based choice
model $\lambda\in\mathcal{U}$. For clarity, the problem instances are sorted
along the $x$-axis by the endpoints of the red bars, and the dotted line shows
the reflection of the endpoints of red bars over the horizontal line at zero.

In Figures 4.1 and 4.1, we present the results of these numerical experiments
for the case of $n=4$ products over 1000 randomly-generated problem instances.
In Figure 4.1, we compare the expected revenue under the best previously-
offered assortment, $\max_{m\in\mathcal{M}}r^{\intercal}v_{m}$, to the
expected revenue of the new assortments obtained using estimate-then-optimize
under the worst-case ranking-based choice model that is consistent with the
historical sales data,
$\min_{\lambda\in\mathcal{U}}\mathscr{R}^{{\lambda}}(S^{\prime})$. We observe
that the results in Figure 4.1 are consistent with the impossibility result
from Theorem 4.2; indeed, the worst-case expected revenues of the new
assortments obtained using estimate-then-optimize never exceed the expected
revenues of the best previously-offered assortments. Furthermore, we observe
for many of the problem instances that there are ranking-based choice models
$\lambda\in\mathcal{U}$ that are consistent with the historical sales data for
which the resulting expected revenue of the new assortment
$\mathscr{R}^{\lambda}(S^{\prime})$ is strictly less than the expected revenue
under the best previously-offered assortment,
$\max_{m\in\mathcal{M}}r^{\intercal}v_{m}$.

To assess whether the above findings are overly conservative from a practical
standpoint, we turn to a detailed analysis of the $137$ problem instances for
which the expected revenue of the best previously-offered assortment,
$\max_{m\in\mathcal{M}}r^{\intercal}v_{m}$, is strictly greater than the
worst-case expected revenue
$\min_{\lambda\in\mathcal{U}}\mathscr{R}^{\lambda}(S^{\prime})$ for the new
assortment $S^{\prime}$ obtained using estimate-then-optimize. In Figure 4.1
we present, for each of these 137 problem instances, a visualization of the
range of relative percentage improvements of the predicted expected revenue of
the new assortment, $\mathscr{R}^{\lambda}(S^{\prime})$, over the expected
revenue of the firm’s best previously-offered assortment,
$\max_{m\in\mathcal{M}}r^{\intercal}v_{m}$, which are possible to obtain under
a ranking-based choice model which is consistent with the historical sales
data, $\lambda\in\mathcal{U}$. Stated more precisely, each of the $x$ values
in Figure 4.1 corresponds to one of these 137 problem instances, and the
corresponding interval of $y$-values formed by the red and blue bars is the
interval $[\Pi_{\lambda}:\lambda\in\mathcal{U}]$, where
$\Pi_{\lambda}\triangleq
100\%\times(\mathscr{R}^{\lambda}(S^{\prime})-\max_{m\in\mathcal{M}}r^{\intercal}v_{m})/(\max_{m\in\mathcal{M}}r^{\intercal}v_{m})$
is the relative percentage improvement of the predicted expected revenue of
the new assortment $S^{\prime}$ over the expected revenue of the firm’s best
previously-offered assortment for a given ranking-based choice model
$\lambda\in\mathcal{U}$. Hence, the red bars are the negative values of
$\Pi_{\lambda}$ that can be attained under the ranking-based choice models
$\lambda\in\mathcal{U}$, and the dotted line shows the reflection of the
endpoints of red bars over the horizontal line at zero. We do not assign any
likelihood to the values in each interval
$[\Pi_{\lambda}:\lambda\in\mathcal{U}]$, as there is no information available
for inferring which of the ranking-based choice models are more likely to be
the ‘truth’ among the ranking-based choice models $\lambda\in\mathcal{U}$ that
are consistent with the historical sales data.

The results in Figure 4.1 reveal a striking asymmetry between the downside and
upside of implementing a new assortment found by estimate-then-optimize. In
all but two of the 137 instances, the worst-case decline in expected revenue
from implementing the new assortment exceeded in magnitude the best-case
increase in expected revenue. The difference in magnitude between the downside
and upside is also found to be significant: the average best-case improvement
of the new assortment over the best previously-offered assortment (i.e., the
average of the blue endpoints) is 6.56%, while the average worst-case
improvement of the new assortment over the best previously-offered assortment
(i.e., the average of the red endpoints) is -21.71%. These numerical findings
demonstrate that the downside risks to a firm from implementing a new
assortment found by estimate-then-optimize can significantly exceed the
potential upsides.

In conclusion, our theoretical and numerical analysis in this subsection lead
to three main takeaways. The first takeaway is that there exist collections of
previously-offered assortments in which it can be impossible to identify
assortments that satisfy (IMP). This is practically useful because if such a
negative answer can be established for a problem instance (either through
impossibility results like Theorem 4.2 or via general algorithms like those
presented in §4.2 , §4.3, or §5.2), then a firm can be encouraged to pursue
additional small-scale experiments before committing to a large-scale
implementation of a new assortment or employ alternative experimentation
techniques such as those discussed in §5.3. The second takeaway is that
estimate-then-optimize can lead to a strictly worse expected revenue than
those of the previously-offered assortments. In fact, the numerical results in
Figures 4.1 and 4.1 show that this decline in expected revenue can be
significant and outweigh the potential upside for implementing the new
assortment. The third takeaway is that all of the aforementioned issues arise
when the previously-offered assortments are comprised of one of the most
celebrated and widely-used classes of assortments from the literature, namely,
the revenue-ordered assortments. All together, these takeaways raise concerns
about whether the estimate-then-optimize technique with ranking-based choice
models should be trusted to “first, do no harm” in  assortment planning
problems.

###  4.2 Polynomial-Time Algorithm for Two Assortments

In view of the impossibility result from the previous subsection, we next turn
to using Theorem 3.1 to assess whether it can ever be possible to identify
assortments that satisfy (IMP). In this subsection, we establish that the
answer to this identification question is _yes_ , and in particular, we show
that such an affirmative answer can be obtained even when the firm has only
offered two past assortments.

In order to establish these results, we begin by leveraging Theorem 3.1 to
develop the first algorithm for solving the robust optimization problem (RO)
with running time that is strongly polynomial in the number of products $n$
for two past assortments. The development of such an algorithm is important
because it will allow us to establish the existence of affirmative answers to
the aforementioned identification question through numerical experiments. Our
development in this subsection of an algorithm for the case of $M=2$ is also
important because it marks the first step towards the development of efficient
_general_ algorithms for solving the robust optimization problem (RO) in
settings with large numbers of products. We will show that the algorithms from
this subsection extend to general settings with any fixed number of past
assortments in the following §4.3. Our polynomial-time algorithm for solving
the robust optimization problem (RO) when $M=2$ is presented in §4.2.1, and
numerical experiments using this algorithm are found in §4.2.2.

####  4.2.1 A Strongly Polynomial-Time Algorithm for Two Assortments.

At a high level, our algorithm for solving the robust optimization problem
(RO) in the case of $M=2$ consists of reducing (RO) to solving a sequence of
minimum-cost network flow problems. Stated formally, the main contribution of
§4.2.1 is the following:

###### Theorem 4.3

If $M=2$ and $\eta=0$, then (RO) can be solved in
$\mathcal{O}(n^{5}\log(nr_{n}))$ computation time.

In the above theorem and throughout the rest of §4.2.1, we assume that the
revenues $r_{1},\ldots,r_{n}$ are represented as positive integers. We also
assume without any loss of generality that $n\in S_{1}\cap S_{2}$.888To see
why the assumption that $n\in S_{1}\cap S_{2}$ can be made without loss of
generality, suppose for the sake of argument that the product $n$ is not
contained in $S_{1}\cap S_{2}$. In that case, we can create a fictitious
product with index $n+1$ that is associated with any arbitrary revenue in the
range $r_{n+1}=(r_{n},\infty)$, and we can augment the historical sales data
to be $v_{1}^{\prime}\triangleq(v_{1},0)\in\mathbb{R}^{n+2}_{+}$ and
$v_{2}^{\prime}\triangleq(v_{2},0)\in\mathbb{R}^{n+2}_{+}$. It is
straightforward to see that any feasible solution to (1) with the augmented
historical sales data will satisfy $\lambda_{n+1,i_{2}}=\lambda_{i_{1},n+1}=0$
for all $i_{1}\in S_{1}$ and $i_{2}\in S_{2}$ that satisfy
$(n+1,i_{2})\in\mathcal{L}$ and $(i_{1},n+1)\in\mathcal{L}$. This implies that
the optimal objective value of (1) will be unchanged using the augmented
historical sales data for all assortments $S\in\mathcal{S}$. Hence, we have
shown that we can assume without loss of generality that the previously-
offered assortments satisfy $n\in S_{1}\cap S_{2}$.

To prove Theorem 4.3, and to develop an algorithm with the desired computation
time, we begin by establishing three intermediary results. The proofs of these
intermediary results, denoted by Lemmas 4.4-4.6, are relatively
straightforward and can be found in Appendix 10. In our first intermediary
result, denoted by Lemma 4.4, we develop a closed-form representation of the
collection of assortments $\widehat{\mathcal{S}}$. This representation will be
useful in the proof of Theorem 4.3 because it provides an efficient procedure
for iterating over the assortments in $\widehat{\mathcal{S}}$. Moreover, the
following Lemma 4.4 is useful because it immediately implies that the number
of assortments in the collection $\widehat{\mathcal{S}}$ scales quadratically
in the number of products $n$.

###### Lemma 4.4

If $M=2$, then

$\displaystyle\widehat{\mathcal{S}}=\left\\{S\in\mathcal{S}:\quad\begin{aligned}
&\textnormal{there exists }i_{1}\in(S_{1}\setminus
S_{2})\cup\\{n\\}\textnormal{ and }i_{2}\in(S_{2}\setminus
S_{1})\cup\\{n\\}\textnormal{ such that}\\\ &S=\left(S_{1}\cap
S_{2}\right)\cup\left\\{j\in S_{1}\setminus S_{2}:j\geq
i_{1}\right\\}\cup\left\\{j\in S_{2}\setminus S_{1}:j\geq
i_{2}\right\\}\end{aligned}\right\\}.$ (2)

Stated concretely, Lemma 4.4 shows that the assortments in the collection
$\widehat{\mathcal{S}}$ can be parameterized by the pairs of products from the
sets $(S_{1}\setminus S_{2})\cup\\{n\\}$ and $(S_{2}\setminus
S_{1})\cup\\{n\\}$. Hence, the number of assortments in the collection
$\widehat{\mathcal{S}}$ is at most $(|S_{1}\setminus
S_{2}|+1)\times(|S_{2}\setminus S_{1}|+1)=\mathcal{O}(n^{2})$. In our second
intermediary result, denoted by Lemma 4.5, we develop a closed-form
representation of the set of tuples of products $\mathcal{L}$. The following
representation of $\mathcal{L}$ will be useful in the proof of Theorem 4.3
because it will allow us to show that the worst-case expected revenue
$\min_{\lambda\in\mathcal{U}}\mathscr{R}^{\lambda}(S)$ for each assortment
$S\in\mathcal{S}$ can be computed by solving a minimum-cost network flow
problem.

###### Lemma 4.5

If $M=2$, then $\mathcal{L}=\left((S_{1}\setminus S_{2})\times
S_{2}\right)\cup\left(S_{1}\times(S_{2}\setminus
S_{1})\right)\cup\left\\{(i,i):i\in S_{1}\cap S_{2}\right\\}$.

In our third and final intermediary result, denoted by Lemma 4.6, we show that
the worst-case expected revenue
$\min_{\lambda\in\mathcal{U}}\mathscr{R}^{\lambda}(S)$ for each assortment
$S\in{\mathcal{S}}$ can be computed by solving a minimum-cost network flow
problem.

###### Lemma 4.6

If $M=2$ and $\eta=0$, then
$\min_{\lambda\in\mathcal{U}}\mathscr{R}^{\lambda}(S)$ can be evaluated for
each assortment $S\in\mathcal{S}$ by solving a minimum-cost network flow
problem in a tripartite directed acyclic graph with $n+1$ vertices and
$|S_{1}\setminus S_{2}|\times|S_{2}|+|S_{2}\setminus S_{1}|\times|S_{1}\cap
S_{2}|=\mathcal{O}(n^{2})$ directed edges.

Using the above three intermediary results, we now describe our algorithm for
solving the robust optimization problem (RO), which follows a brute-force
strategy. Namely, our algorithm iterates over each of the assortments
$S\in\widehat{\mathcal{S}}$, and, for each such assortment, the algorithm
computes the corresponding worst-case expected revenue
$\min_{\lambda\in\mathcal{U}}\mathscr{R}^{\lambda}(S)$ by solving a minimum-
cost network flow problem. The algorithm concludes by returning the maximum
value of $\min_{\lambda\in\mathcal{U}}\mathscr{R}^{\lambda}(S)$ across the
assortments $S\in\widehat{\mathcal{S}}$. The correctness of this algorithm for
solving the robust optimization problem (RO) follows immediately from Theorem
3.1. The proof that this algorithm achieves the desired running time of
Theorem 4.3 can be found in Appendix 10.4.

####  4.2.2 Numerical Experiments for Two Assortments.

We will now perform numerical experiments to show, using our polynomial-time
algorithm from §4.2.1, that there can exist assortments that satisfy (IMP) in
the case of $M=2$.

To perform our numerical experiments, we begin by constructing randomly-
generated problem instances in a manner that is similar to that taken in §4.1.
In each randomly-generated problem instance, the revenues are drawn from the
distribution $r_{1},\ldots,r_{n}\sim\textnormal{Uniform}[0,1]$, and we sort
the products such that $r_{1}<\cdots<r_{n}$. The two past assortments
$S_{1},S_{2}\in\mathcal{S}$ are also constructed randomly, whereby the two
assortments satisfy $\\{0,n\\}\subseteq S_{1}\cap S_{2}$ and, for each of the
remaining products $j\in\\{1,\ldots,n-1\\}$, we randomly assign the product to
the assortments with distribution given by $P(j\in S_{1}\cap
S_{2})=\nicefrac{{1}}{{3}}$, $P(j\in S_{1}\setminus
S_{2})=\nicefrac{{1}}{{3}}$, and $P(j\in S_{2}\setminus
S_{1})=\nicefrac{{1}}{{3}}$. In order to generate historical sales data for
these two assortments, we generate a base choice for the parameters
$\lambda^{*}$ of the ranking-based choice model. Because we will be performing
numerical experiments on problem instances with larger values of $n$ than were
considered in §4.1, it will not be viable from a computational tractability
standpoint to generate base parameters $\lambda^{*}$ that have nonzero values
for each of the $(n+1)!$ parameters of a ranking-based choice model. To get
around this, we restrict the numerical experiments to generating base
parameters $\lambda^{*}$ which are _sparse_. Specifically, we generate the
base parameters in each problem instance by first randomly selecting a subset
of rankings $\Sigma^{\prime}\subseteq\Sigma$ of length
$|\Sigma^{\prime}|=K$;999We use rejection sampling to ensure that each of the
$\binom{(n+1)!}{K}$ subsets of rankings is selected with equal probability. we
then assign $\lambda_{\sigma}^{*}\leftarrow 0$ for each ranking
$\sigma\notin\Sigma^{\prime}$, and we choose the remaining parameters
$\\{\lambda_{\sigma}:\sigma\in\Sigma^{\prime}\\}$ by drawing uniformly over
the $K$-dimensional probability simplex. Using this base choice for the
parameters, we generate historical sales data of the form $v_{1}$ and $v_{2}$
corresponding to the two assortments $S_{1}$ and $S_{2}$ under the ranking-
based choice model with the base parameters $\lambda^{*}$. After we compute
the historical sales data, we _forget_ the base parameters $\lambda^{*}$ of
the ranking-based choice model as well as the choice of $K$, and we apply the
algorithm from §4.2.1 to obtain a new assortment, denoted by $S^{\prime}$.

Performance of assortments obtained using algorithm from §4.2.1 when $M=2$,
$K=10$, and $n=10$.

Computation time for the algorithm from §4.2.1 when $M=2$ and $K=1000$.

110 Left figure: Each point corresponds to a randomly-generated problem
instance. The $x$-axis shows the expected revenue of the best previously-
offered assortment, $\max_{m\in\mathcal{M}}r^{\intercal}v_{m}$. The $y$-axis
shows the worst-case expected revenue
$\min_{\lambda\in\mathcal{U}}\mathscr{R}^{\lambda}(S^{\prime})$ for the new
assortment $S^{\prime}$ obtained by using the algorithm from §4.2.1. Right
figure: Results are averaged over 100 replications for each
$n\in\\{10,12,14,\ldots,100\\}$.

In Figures 4.2.2 and 4.2.2, we present the results of the numerical
experiments conducted as described above. In Figure 4.2.2, we present the
results of these numerical experiments in the case of $n=10$ products over
1000 randomly-generated problem instances and for $K=10$. This figure compares
the expected revenue under the best previously-offered assortment,
$\max_{m\in\mathcal{M}}r^{\intercal}v_{m}$, to the predicted expected revenue
of the new assortment under the worst-case ranking-based choice model that is
consistent with the historical sales data,
$\min_{\lambda\in\mathcal{U}}\mathscr{R}^{{\lambda}}(S^{\prime})$. These
results establish that there can be affirmative answers to the identification
question in the case of $M=2$; indeed, we observe from Figure 4.2.2 that there
are problem instances for which the predicted expected revenue of the new
assortment obtained by our algorithm from §4.2.1 is strictly greater than the
expected revenue of the best previously-offered assortment under all ranking-
based choice model that are consistent with the historical sales data. In
Figure 4.2.2, we show the average computation times for our algorithm from
§4.2.1 on problem instances in which the number of products is varied across
$n\in\\{10,12,14,\ldots,100\\}$ and $K=1000$. Here, we use the larger $K=1000$
to ensure that the sparsity of the randomly-generated base parameters
$\lambda^{*}$ does not introduce any biases on the resulting computation times
of our algorithm. The results in Figure 4.2.2 show that the computation time
of the algorithm remains under 30 seconds even when there are one hundred
products. This is viewed as promising from a practical perspective, as it
shows that a general algorithm for solving the robust optimization problem
(RO) in the case of $M=2$ can scale to problem instances with realistic
numbers of products.

Motivated by the numerical findings in Figure 4.2.2, we further conducted an
informal analysis of the randomly-generated problem instances in which the
worst-case expected revenue of the new assortment was strictly greater than
the expected revenue of the best previously-offered assortment. Our analysis
consisted of a visual examination of the assortments that were found by the
algorithm from §4.2.1, along with an exploratory analysis in which we manually
adjusted the parameters which were used to generate the problem instances to
understand their impact on the resulting assortments found by the algorithm
from §4.2.1. Our goal in conducting this informal analysis was to gain a
qualitative understanding of the types of problem instances for which the
algorithm from §4.2.1 is able to find an assortment that satisfies (IMP). We
were also interested in assessing the performance of the estimate-then-
optimize technique in problem instances in which there exist assortments that
satisfy (IMP).

The main takeaway from our informal analysis is a simple but insightful
example of a problem instance for which the identification question has an
affirmative answer. The example, which is presented in Appendix 11, is
insightful for three specific reasons. First, the example shows that there are
problem instances in which the assortment $S\in\widehat{\mathcal{S}}$ that
satisfies (IMP) is not a revenue-ordered assortment. Second, the example shows
that the estimate-then-optimize technique can perform poorly (that is, yield
an assortment with an expected revenue which is strictly less than the best
expected revenue from the previously-offered assortments) even on problem
instances for which there exist assortments that satisfy (IMP). Third, the
example shows that the aforementioned two properties can be obtained in
relatively simple problem instances which are comprised of only $n=4$ products
and in which the revenues and historical sales data have numerical values that
are relatively easy to manipulate. More broadly, this example illustrates that
assortments that satisfy (IMP) can in general have a non-trivial structure,
and discovering such assortments appears to be challenging without the aid of
algorithms like those developed in §4.2.1 and in the subsequent sections.

###  4.3 Polynomial-time Algorithm for Fixed Number of Past Assortments

We conclude §4 by developing the first polynomial-time algorithm for solving
the robust optimization problem (RO) for any fixed number of previously-
offered assortments $M$. The algorithm developed in this subsection is
particularly attractive due to its generality: it does not require any
assumptions on the composition of products in the previously-offered
assortments. Moreover, the algorithm allows for the radius $\eta$ in the set
of ranking-based choice models to be strictly positive (see §2); hence, the
algorithm can be applied in settings in which there are no ranking-based
choice models that have perfect accuracy on the firm’s historical sales data.

Our polynomial-time algorithm for solving the robust optimization problem (RO)
for any fixed number of past assortments follows the same high-level strategy
as developed in §4.2. Specifically, our algorithm reduces the robust
optimization problem (RO) to computing the worst-case expected revenue
$\min_{\lambda\in\mathcal{U}}\mathscr{R}^{\lambda}(S)$ for each candidate
assortment $S\in\widehat{\mathcal{S}}$ and outputting the assortment that has
the maximum worst-case expected revenue. The correctness of such a brute-force
algorithm for solving the robust optimization problem (RO) follows immediately
from Theorem 3.1. In the remainder of §4.3, we prove that there exists an
implementation of the aforementioned brute-force algorithm which yields the
following theoretical guarantee on its computational tractability:

###### Theorem 4.7

(RO) can be solved in weakly $\mathcal{O}(\textnormal{poly}(n))$ computation
time for every fixed $M$.

The above theorem holds for any choice of the radius $\eta\geq 0$ in the set
of ranking-based choice models and any composition of products in the
previously-offered assortments. We note that our algorithm is guaranteed to
run in weakly, as opposed to strongly, polynomial time due to its reduction to
solving linear optimization problems.

To sketch the proof of Theorem 4.7, we will make use of several intermediary
results (Lemma 4.8-4.11), the proofs of which can be found in Appendix 12. The
primary workhorse in our proof of Theorem 4.7 is contained in the proof of our
first intermediary result, denoted by Lemma 4.8, in which we develop an
algorithm for constructing the collection of assortments
$\widehat{\mathcal{S}}$ from the previously-offered assortments. The algorithm
which achieves the specified running time of the following lemma is based on
dynamic programming over a compact graphical representation of the collection
of assortments $\widehat{\mathcal{S}}$. In particular, the algorithm can be
viewed as attractive due to its mild dependence on the number of assortments
in the collection $\widehat{\mathcal{S}}$.

###### Lemma 4.8

The collection of assortments $\widehat{\mathcal{S}}$ can be constructed in
$\mathcal{O}(n^{2}(M+|\widehat{\mathcal{S}}|))$ time.

We observe that the algorithm which achieves the specified running time in
Lemma 4.8 is efficient when the number of assortments in the collection
$\widehat{\mathcal{S}}$ is small. In fact, we have seen evidence up to this
point that the number of assortments in the collection $\widehat{\mathcal{S}}$
can indeed be small in special cases of problem instances: namely, we recall
from §4.1 that $|\widehat{\mathcal{S}}|=\mathcal{O}(n)$ when the previously-
offered assortments are the revenue-ordered assortments, and we recall from
§4.2 that $|\widehat{\mathcal{S}}|=\mathcal{O}(n^{2})$ when there are two
previously-offered assortments. In the next intermediary result, denoted by
Lemma 4.9, we develop a more general result along these lines. Specifically,
the following lemma establishes that the number of assortments in the
collection $\widehat{\mathcal{S}}$ can be upper bounded by a polynomial of the
number of products $n$ for _any_ fixed number of previously-offered
assortments $M$. While the bound in the following lemma is not the tightest
possible, the bound will be sufficient for its theoretical purpose in this
subsection of proving Theorem 4.7.

###### Lemma 4.9

$|\widehat{\mathcal{S}}|\leq(n+2)^{2^{M}}$.

The remaining intermediary results will be used in our proof of Theorem 4.7 to
show that the worst-case expected revenue
$\min_{\lambda\in\mathcal{U}}\mathscr{R}^{\lambda}(S)$ can be computed for
each assortment $S\in\widehat{\mathcal{S}}$ in weakly polynomial time for
every fixed number of previously-offered assortments $M$. The following
intermediary results accomplish this by showing for every fixed $M\geq 2$ and
assortment $S\in\widehat{\mathcal{S}}$ that the worst-case expected revenue
$\min_{\lambda\in\mathcal{U}}\mathscr{R}^{\lambda}(S)$ can be computed by
solving a linear optimization problem that can be constructed in polynomial
time (Lemma 4.10-4.11) and has a polynomial number of decision variables and
constraints (see Remark 3.7 from §3).

###### Lemma 4.10

$|\mathcal{L}|=\mathcal{O}(n^{M})$, and $\mathcal{L}$ can be constructed in
$\mathcal{O}(Mn^{M+1})$ computation time.

###### Lemma 4.11

For each assortment $S\in\widehat{\mathcal{S}}$ and each tuple of products
$(i_{1},\ldots,i_{M})\in\mathcal{L}$, the quantity $\rho_{i_{1}\cdots
i_{M}}(S)$ can be computed in $\mathcal{O}(M^{2}n)$ time.

Combining the above intermediary lemmas, we obtain an algorithm that satisfies
the running time requirements of Theorem 4.7. The detailed description of the
algorithm and the proof of its running time can be found in Appendix 12.5.

##  5 Practical Algorithms for Structured Past Assortments

In §4.3, we developed a general algorithm for solving the robust optimization
problem (RO) that is theoretically efficient in applications in which the
number of past assortments is small. In this section, we extend our structural
and algorithmic developments from §3 and §4 to address applications in which
the number of past assortments is large, as well as applications in which
there do not exist any assortments that satisfy (IMP).

Our discussion in §5 will focus on applications in which the previously-
offered assortments have a widely-studied structure called _nested_. Formally,
the previously-offered assortments are nested if and only if there is an
ordering of the past assortments such as that each assortment is a subset of
the subsequent assortment: [Nested] The past assortments
$\mathscr{M}\equiv\\{S_{1},\ldots,S_{M}\\}\subseteq\mathcal{N}_{0}$ satisfy
$S_{1}\subset\cdots\subset S_{M}$. Applications in which historical sales data
is obtained from nested past assortments are “common in retail and revenue
management settings” (Jagabathula and Rusmevichientong 2019, p.2202). For
example, the past assortments will be nested if a retailer initially offers a
large assortment of products to its customers and does not replenish
inventory, in which the case the initial assortment will dwindle to smaller
and smaller assortments as products run out of inventory. Nested past
assortments also arise as new products become available in the marketplace, as
well as in online retail as customers scroll through products across multiple
pages of a website (Davis et al. 2015). Finally, nested assortments are a
generalization of revenue-ordered assortments, and thus arise in any
situations in which a firm has only offered revenue-ordered assortments.

This section is organized as follows. In §5.1, we show that the cardinality of
the collection of assortments $\widehat{\mathcal{S}}$ can grow exponentially
in the number of previously-offered assortments when the past assortments are
nested. In §5.2, we show that our technical developments behind Theorem 3.1
can be extended to develop compact mixed-integer linear optimization
reformulations in the case of nested past assortments. In §5.3, we apply our
reformulation techniques to offer a low-risk approach to experimentation in
applications in which there do not exist any assortments that satisfy (IMP).

###  5.1 Exponential Growth of $\widehat{\mathcal{S}}$ for Nested Past
Assortments

The efficiency of the proposed algorithm from §4.3 is the result of two key
factors. First, when the number of past assortments is fixed, the cardinality
of the collection of assortments $\widehat{\mathcal{S}}$ scales as a
polynomial in the number of products (Lemma 4.9 in §4.3). Second, when the
number of past assortments is fixed, the worst-case expected revenue
$\min_{\lambda\in\mathcal{U}}\mathscr{R}^{\lambda}(S)$ for each fixed
assortment $S\in\widehat{\mathcal{S}}$ can be evaluated by solving a linear
optimization problem with size that scales as a polynomial in the number of
products (Proposition 3.5 in §3). In the present §5.1, motivated by
applications in which the number of past assortments is large, we investigate
the relationship between the cardinality of the collection of assortments
$\widehat{\mathcal{S}}$ and the number of past assortments $M$ in applications
when the past assortments are nested (but not necessarily revenue-ordered).

Our discussion in the present §5.1 will focus on a specific example of past
assortments:

###### Definition 5.1

We say that the firm’s past assortments are _reverse revenue-ordered_ if
$S_{1}\triangleq\\{0,n\\}$, $S_{m}\triangleq\left\\{0,1,\ldots,m-1,n\right\\}$
for each $m\in\\{2,\ldots,n\\}$, and
$\mathscr{M}=\tilde{\mathcal{S}}\triangleq\left\\{S_{1},\ldots,S_{n}\right\\}$.

We readily observe from the above definition that the reverse revenue-ordered
assortments are nested, in the sense that $S_{1}\subset\cdots\subset S_{n}$.
Moreover, we observe that the following lemma follows immediately from the
definition of the collection of assortments $\widehat{S}$ from §3.

###### Lemma 5.2

If $\mathscr{M}=\tilde{\mathcal{S}}$, then
$\widehat{\mathcal{S}}=\left\\{S\subseteq\mathcal{N}_{0}:\\{0,n\\}\subseteq
S\right\\}$.

The above lemma shows that if the past assortments $\mathscr{M}$ are the
reverse revenue-ordered assortments, then the corresponding collection of
assortments $\widehat{\mathcal{S}}$ is the collection of all subsets of
products that include the most expensive product $n$ and the no-purchase
option $0$. It follows immediately from Lemma 5.2 and from the fact that $M=n$
that $|\widehat{\mathcal{S}}|=2^{M-2}$ when the past assortments are the
reversed revenue-ordered assortments. Since the reverse revenue-ordered
assortments are nested, we have thus shown that the cardinality of the
collection of assortments $\widehat{\mathcal{S}}$ can grow exponentially in
the number of past assortments when the past assortments are nested.

Our main contribution of §5.1, which is presented below as Theorem 5.3,
consists of establishing that the characterization of optimal assortments from
Theorem 3.1 cannot be refined for reverse revenue-ordered assortments. More
precisely, Theorem 5.3 shows that $\widehat{\mathcal{S}}$ is exactly the
collection of assortments that can be optimal for the robust optimization
problem (RO) when the previously-offered assortments are reverse revenue-
ordered. This theorem is significant because it proves that the collection of
assortments $\widehat{\mathcal{S}}$ that is developed in §3 is an accurate
description of the range of possible optimal solutions for the robust
optimization problem (RO), at least for the case when the previously-offered
assortments are reverse revenue-ordered. It also is significant because it
implies that the exponential growth of the cardinality of the collection of
assortments $\widehat{\mathcal{S}}$ that is established in Lemma 5.2 is not
the result of constructing an overly-conservative collection of assortments
$\widehat{\mathcal{S}}$.

###### Theorem 5.3

Suppose that $\mathscr{M}=\tilde{\mathcal{S}}$, that $\eta=0$, and that the
revenues $r_{1}<\cdots<r_{n}$ are fixed. Then for every assortment
$\bar{S}\in\widehat{\mathcal{S}}$, there exists a realization of the
historical data $v\equiv(v_{m,i}:m\in\mathcal{M},i\in S_{m})$ such that
$\bar{S}$ is the unique optimal solution of the robust optimization problem
(RO).

To summarize, Lemma 5.2 shows that the proposed algorithm from §4.3 may not be
practically efficient in applications in which the past assortments are nested
and in which the number of past assortments is large. Indeed, the algorithms
from §4 consist of evaluating the worst-case expected revenue
$\min_{\lambda\in\mathcal{U}}\mathscr{R}^{\lambda}(S)$ for each assortment
$S\in\widehat{\mathcal{S}}$, and Lemma 5.2 and Theorem 5.3 together show that
there exist examples of past assortments that are nested in which the number
of possible optimal solutions for the robust optimization problem (RO) grows
exponentially in the number of past assortments. Therefore, except in settings
in which the past assortments are close to being revenue-ordered (see Theorem
4.2), we conclude that algorithms that are meaningfully different from the
algorithm in §4.3 will be needed to solve the robust optimization problem (RO)
in practical computation times when the number of past assortments is large.

###  5.2 Mixed-Integer Linear Optimization Formulation for Nested Past
Assortments

In the present §5.2, we show that our technical developments behind Theorem
3.1 can be used to obtain a compact mixed-integer linear optimization
reformulation of the robust optimization problem (RO) when the past
assortments are nested. This reformulation can offer significant value
compared to the algorithm from §4.3 when the number of past assortments as
large; indeed, the number of decision variables and constraints of the mixed-
integer linear optimization reformulation scale as a polynomial in the number
of past assortments as well as the number of products. As a result, we show
through numerical experiments at the end of §5.2 that our mixed-integer linear
optimization problem can solve the robust optimization problem (RO) in less
than 30 seconds in applications with as many as $M=20$ past assortments. More
generally, this subsection shows that our technical developments behind
Theorem 3.1 can be combined with structural assumptions on past assortments to
develop practical algorithms for solving (RO) when $|\widehat{\mathcal{S}}|$
is large.

To motivate our construction of the mixed-integer linear optimization
reformulation of the robust optimization problem (RO), we begin by showing for
the case of nested past assortments that the linear optimization problem (1)
has a number of decision variables that grows exponentially in the number of
past assortments. Indeed, for each $m\in\mathcal{M}$, let the set of products
that appear in the previously-offered assortment $S_{m}$ and do not appear in
any preceding previously-offered assortments be denoted by

$\displaystyle\mathcal{B}_{m}\triangleq
S_{m}\setminus\left(\bigcup_{m^{\prime}=1}^{m-1}S_{m^{\prime}}\right)=\begin{cases}S_{1},&\text{if
}m=1,\\\ S_{m}\setminus S_{m-1},&\text{otherwise},\end{cases}$ (3)

where the right-most equality follows from algebra and from the fact that the
previously-offered assortments are nested. We observe from the above
definition that the sets $\mathcal{B}_{1},\ldots,\mathcal{B}_{M}$ are
disjoint. In view of this notation, the following lemma and its corollary show
that the number of decision variables in the linear optimization problem (1)
grows exponentially with respect to the number of past assortments $M$ when
the past assortments are nested.

###### Lemma 5.4

If Assumption 5 holds, then

$\mathcal{L}=\left\\{(i_{1},\ldots,i_{M})\in S_{1}\times\cdots\times
S_{M}:\textnormal{ for each
}m\in\\{1,\ldots,M-1\\},\;i_{m+1}\in\\{i_{m}\\}\cup\mathcal{B}_{m+1}\right\\}.$

###### Corollary 5.5

If Assumption 5 holds, then $|\mathcal{L}|\geq 2^{M-1}$.

With the above motivation, we now demonstrate that our technical developments
behind Theorem 3.1 can be used to reformulate (1) as linear optimization
problem with a polynomial number of decision variables and constraints. To
explain our reformulation strategy, we observe in the case of $\eta=0$ that
the linear optimization problem (1) can be rewritten equivalently as

$\displaystyle\begin{aligned}
&\;\underset{y\in\mathcal{Y}(S)}{\textnormal{minimize}}&&\sum_{i\in\mathcal{N}_{0}}r_{i}y_{i},\end{aligned}$
(4)

where

$\displaystyle\mathcal{Y}(S)\triangleq\left\\{y\in\mathbb{R}^{\mathcal{N}_{0}}:\begin{gathered}\textnormal{there
exists a vector }\lambda\equiv(\lambda_{i_{1}\cdots
i_{M}}:(i_{1},\ldots,i_{M})\in\mathcal{L})\geq 0\textnormal{ such
that:}\\\\[5.0pt] \begin{aligned}
\sum_{(i_{1},\ldots,i_{M})\in\mathcal{L}:\rho_{i_{1}\cdots
i_{M}}(S)=r_{i}}\lambda_{i_{1}\cdots i_{M}}&=y_{i}&&\textnormal{for all }i\in
S\\\\[5.0pt]
\sum_{(i_{1},\ldots,i_{M})\in\mathcal{L}:i_{m}=i}\lambda_{i_{1}\cdots
i_{M}}&=v_{m,i}&&\textnormal{for all }m\in\mathcal{M},\;i\in S_{m}\\\\[5.0pt]
\sum_{(i_{1},\ldots,i_{M})\in\mathcal{L}}\lambda_{i_{1}\cdots
i_{M}}&=1\end{aligned}\end{gathered}\right\\}.$

The number of decision variables in the linear optimization problem (4) is
equal to $|\mathcal{N}_{0}|=n+1$. Hence, we observe that the computational
tractability of the linear optimization problem (1) depends on our ability to
develop a compact representation of the set $\mathcal{Y}(S)$.101010A linear
optimization problem over the feasible set $\mathcal{Y}(S)$ bears resemblance
to the RankAggregationLP optimization problem that is studied by Jagabathula
and Rusmevichientong (2019). In contrast, our set $\mathcal{Y}(S)$ requires an
aggregation of the decision variables $\lambda_{i_{1}\cdots i_{M}}$ in such a
way that preserves the quantity $\rho_{i_{1}\cdots i_{M}}(S)$, where we recall
from §3 that $\rho_{i_{1}\cdots i_{M}}(S)$ can be interpreted as the worst-
case revenue that is earned by the firm when assortment $S$ is offered to a
customer whose preferences are represented by a ranking that corresponds to
the tuple of products $(i_{1},\ldots,i_{M})\in\mathcal{L}$. Because of this
difference, the reformulations developed by Jagabathula and Rusmevichientong
(2019, §4 and §5) are not readily applicable to the set $\mathcal{Y}(S)$. In
view of this observation, we proceed to show that the constraints on the
decision variables $y\in\mathbb{R}^{\mathcal{N}_{0}}$ can be represented
compactly when the past assortments are nested. The key insight that will
enable the compact reformulation of the constraints on the decision variables
$y\in\mathbb{R}^{\mathcal{N}_{0}}$ is the following Lemma 5.6, which shows
that the quantities $\rho_{i_{1}\cdots i_{M}}(S\cap S_{m})$ can be written
_recursively_. Similarly to the proof of Theorem 3.1, the proof of the
following Lemma 5.6 is based on the graphical interpretation of
$\rho_{i_{1}\cdots i_{M}}(S)$ that is developed in Appendix 7.2.

###### Lemma 5.6

If Assumption 5 holds and the assortment $S\subseteq\mathcal{N}_{0}$ satisfies
$S\cap S_{1}\neq\emptyset$,111111The condition that $S\cap S_{1}\neq\emptyset$
in Lemma 5.6 is satisfied, for example, when $S,S_{1}\in\mathcal{S}$. then the
following equality holds for each tuple $(i_{1},\ldots,i_{M})\in\mathcal{L}$
and $m\in\mathcal{M}$:

$\displaystyle\rho_{i_{1}\cdots i_{M}}(S\cap S_{m})$
$\displaystyle=\begin{cases}r_{i_{m}},&\textnormal{if }i_{m}\in S,\\\
\min\limits_{i\in\mathcal{B}_{m}\cap S}r_{i},&\textnormal{if }i_{m}\notin
S\textnormal{ and }m=1,\\\ \min\left\\{\min\limits_{i\in\mathcal{B}_{m}\cap
S}r_{i},\rho_{i_{1}\cdots i_{M}}\left(S\cap
S_{m-1}\right)\right\\},&\textnormal{if }i_{m}\notin S\textnormal{ and }m\geq
2.\end{cases}$ (5)

Equipped with the observation that the quantities $\rho_{i_{1}\cdots
i_{M}}(S\cap S_{m})$ can be written recursively, we now introduce a directed
acyclic graph that will serve as a low-dimensional network representation of
the decision variables of the linear optimization problem (1). Indeed, we
define the vertices and directed edges of the graph as follows:

$\displaystyle\mathfrak{V}$
$\displaystyle\triangleq\left\\{(m,i,\kappa):\;m\in\mathcal{M},\;i\in
S_{m},\;\kappa\in\\{r_{j}:j\in S_{m}\\}\right\\};$ $\displaystyle\mathfrak{E}$
$\displaystyle\triangleq\left\\{((m,i,\kappa),(m^{\prime},i^{\prime},\kappa^{\prime}))\in\mathfrak{V}\times\mathfrak{V}:\;m^{\prime}=m+1,\;i^{\prime}\in\\{i\\}\cup\mathcal{B}_{m+1},\;\kappa^{\prime}\in\\{\kappa\\}\cup\left\\{r_{j}:j\in\mathcal{B}_{m+1}\right\\}\right\\}.$

We observe that each of the directed edges in the graph
$\mathfrak{G}\equiv(\mathfrak{V},\mathfrak{E})$ is of the form
$((m,i,\kappa),(m+1,i^{\prime},\kappa^{\prime}))$, which readily implies that
the directed graph $\mathfrak{G}\equiv(\mathfrak{V},\mathfrak{E})$ is acyclic.
Moreover, the number of vertices $|\mathfrak{V}|$ and the number of directed
edges $|\mathfrak{E}|$ clearly scale as a polynomial with respect to both the
number of products $n$ as well as the number of past assortments $M$. Using
this directed acyclic graph, we now state our compact reformulation of the
linear optimization problem (1).

###### Proposition 5.7

Let Assumption 5 hold. Then for each $S\subseteq\mathcal{N}_{0}$ that
satisfies $S\cap S_{1}\neq\emptyset$,
$\min_{\lambda\in\mathcal{U}}\mathscr{R}^{\lambda}(S)$ is equal to the optimal
objective value of the following linear optimization problem:

$\displaystyle\;\underset{f,g,\epsilon}{\textnormal{minimize}}$
$\displaystyle\sum_{i,\kappa:(M,i,\kappa)\in\mathfrak{V}}\kappa
g_{M,i,\kappa}$ (6) subject to
$\displaystyle\sum_{\kappa:(m,i,\kappa)\in\mathfrak{V}}g_{m,i,\kappa}-\epsilon_{m,i}=v_{m,i}$
$\displaystyle\forall m\in\mathcal{M},\;i\in S_{m}$
$\displaystyle\sum_{i^{\prime},\kappa^{\prime}:((m,i,\kappa),(m+1,i^{\prime},\kappa^{\prime}))\in\mathfrak{E}}f_{m,i,\kappa,i^{\prime},\kappa^{\prime}}=g_{m,i,\kappa}$
$\displaystyle\forall(m,i,\kappa)\in\mathfrak{V}:m\in\\{1,\ldots,M-1\\}$
$\displaystyle\sum_{i^{\prime},\kappa^{\prime}:((m-1,i^{\prime},\kappa^{\prime}),(m,i,\kappa))\in\mathfrak{E}}f_{m-1,i^{\prime},\kappa^{\prime},i,\kappa}=g_{m,i,\kappa}$
$\displaystyle\forall(m,i,\kappa)\in\mathfrak{V}:m\in\\{2,\ldots,M\\}$
$\displaystyle g_{m,i,\kappa}=0$
$\displaystyle\forall(m,i,\kappa)\in\mathfrak{V}:i\in
S,\;i\in\mathcal{B}_{m},\;\kappa\neq r_{i}$ $\displaystyle g_{m,i,\kappa}=0$
$\displaystyle\forall(m,i,\kappa)\in\mathfrak{V}:i\in
S,\;i\notin\mathcal{B}_{m},\;\kappa\in\\{r_{j}:j\in\mathcal{B}_{m}\\}$
$\displaystyle g_{m,i,\kappa}=0$
$\displaystyle\forall(m,i,\kappa)\in\mathfrak{V}:\kappa\in\\{r_{j}:j\in\mathcal{B}_{m}\setminus
S\\}$
$\displaystyle\sum_{i,\kappa:(M,i,\kappa)\in\mathfrak{V}}g_{M,i,\kappa}=1$
$\displaystyle\|\epsilon\|\leq\eta$ $\displaystyle
f_{m,i,\kappa,i^{\prime},\kappa^{\prime}}\geq 0$
$\displaystyle\forall((m,i,\kappa),(m+1,i^{\prime},\kappa^{\prime}))\in\mathfrak{E}$
$\displaystyle g_{m,i,\kappa}\geq 0$
$\displaystyle\forall(m,i,\kappa)\in\mathfrak{V}.$

Let us make several remarks about the linear optimization problem (6). First,
we remark that the decision variables $f,g$ can be interpreted as a network
flow through the directed acyclic graph
$\mathfrak{G}\equiv(\mathfrak{V},\mathfrak{E})$. Indeed, the decision variable
$g_{m,i,\kappa}$ represents the amount of flow that passes through each vertex
$(m,i,\kappa)\in\mathfrak{V}$, the decision variable
$f_{m,i,\kappa,i^{\prime},\kappa^{\prime}}$ represents the amount of flow
through the directed edge from vertex $(m,i,\kappa)\in\mathfrak{V}$ to vertex
$(m+1,i^{\prime},\kappa^{\prime})\in\mathfrak{V}$, and the constraints of the
form
$\sum_{i^{\prime},\kappa^{\prime}:((m,i,\kappa),(m+1,i^{\prime},\kappa^{\prime}))\in\mathfrak{E}}f_{m,i,\kappa,i^{\prime},\kappa^{\prime}}=g_{m,i,\kappa}$
and
$\sum_{i^{\prime},\kappa^{\prime}:((m-1,i^{\prime},\kappa^{\prime}),(m,i,\kappa))\in\mathfrak{E}}f_{m-1,i^{\prime},\kappa^{\prime},i,\kappa}=g_{m,i,\kappa}$
ensure that flow is conserved through each vertex
$(m,i,\kappa)\in\mathfrak{V}$ with $m\in\\{2,\ldots,M-1\\}$. Second, we show
in the proof of Proposition 5.7 that the decision variables in the linear
optimization problem (6) can be interpreted as an aggregation of the decision
variables in the linear optimization problem (1). In particular, we show in
Appendices 14.4 and 14.5 that each decision variable $\lambda_{i_{1}\cdots
i_{M}}$ can be interpreted as flow through the path
$(1,i_{1},\rho_{i_{1}\cdots i_{M}}(S\cap
S_{1})),\ldots,(M,i_{M},\rho_{i_{1}\cdots i_{M}}(S\cap S_{M}))$ in the
directed acyclic graph $\mathfrak{G}\equiv(\mathfrak{V},\mathfrak{E})$. Hence,
any optimal solution for the linear optimization problem (6) can be
transformed back into the decision variables of the linear optimization
problem (1) by applying the flow decomposition theorem (Ahuja et al. 1988,
Theorem 3.5).

In summary, we have shown in Proposition 5.7 that the worst-case expected
revenue $\min_{\lambda\in\mathcal{U}}\mathscr{R}^{\lambda}(S)$ in the case of
nested past assortments can be evaluated by solving a linear optimization
problem with size that is polynomial in the number of products $n$ and the
number of past assortments $M$. The key step behind developing the compact
reformulation is exploiting the graphical interpretation of the quantities
$\rho_{i_{1}\cdots i_{M}}(S)$ that is developed in Appendix 7.2 to design a
low-dimensional network representation of the decision variables in the linear
optimization problem (1). By applying strong duality to the linear
optimization problem from Proposition 5.7 and introducing binary decision
variables to represent the assortment $S$, we readily obtain a mixed-integer
linear optimization formulation of the robust optimization problem (RO):

###### Theorem 5.8

Let Assumption 5 hold and $S_{1},\ldots,S_{M}\in\mathcal{S}$. Then the robust
optimization problem (RO) can be reformulated as a mixed-integer linear
optimization problem with $n$ binary decision variables,
$\mathcal{O}(\textnormal{poly}(n,M))$ continuous decision variables, and
$\mathcal{O}(\textnormal{poly}(n,M))$ constraints.

The description of the mixed-integer linear optimization reformulation from
Theorem 5.8 is found at the end of Appendix 14.6.

We conclude §5.2 by showing that the mixed-integer linear optimization problem
from Theorem 5.8 can be solved in reasonable computation times in applications
with realistic numbers of past assortments and numbers of products. To show
this, we conduct numerical experiments on randomly-generated problem instances
with nested past assortments that are constructed in a manner that is similar
to §4. Specifically, in each problem instance, we generate a sparse base
parameter vector $\lambda^{*}$ by drawing a subset of rankings
$\Sigma^{\prime}\subseteq\Sigma$ of length $|\Sigma^{\prime}|=80$ uniformly at
random, and then choosing the values of the nonzero base parameters
$\\{\lambda_{\sigma}^{*}:\sigma\in\Sigma^{\prime}\\}$ by drawing uniformly
over the $80$-dimensional probability simplex. The revenues of the products
are drawn from the distribution
$r_{1},\ldots,r_{n}\sim\textnormal{Uniform}\\{1,\ldots,10000\\}$, and we sort
the products such that $r_{1}<\cdots<r_{n}$. To construct a random collection
of nested past assortments of length $M$, we draw a permutation of products
$\sigma:\mathcal{N}\to\mathcal{N}$ uniformly at random, draw a subset of
distinct integers $1\leq q_{1}<\cdots<q_{M-1}\leq n-1$ uniformly at random,
and define the past assortments as
$S_{m}\triangleq\\{0\\}\cup\\{\sigma(i):i\in\\{1,\ldots,q_{m}\\}\\}$ for each
$m\in\\{1,\ldots,M-1\\}$ and $S_{M}\triangleq\mathcal{N}_{0}$. We generate the
historical sales data for each of the past assortments under the ranking-based
choice model with the base parameters $\lambda^{*}$, and we then use the
algorithm from Theorem 5.8 to solve the robust optimization problem (RO) in
the case of $\eta=0$.

Computation time for solving mixed-integer linear optimization problem from
Theorem 5.8 with $n=20$ products and $M\in\\{2,\ldots,20\\}$ nested past
assortments. Results are averaged over 10 replications for each
$M\in\\{2,\ldots,20\\}$.

In Figure 5.2, we present the computation times of our numerical experiments
averaged over ten replications for each selection of $M\in\\{2,\ldots,20\\}$
and $n=20$. To appreciate the computation times in Figure 5.2, let us recall
the algorithm from §4.3 for solving the robust optimization problem (RO). In
the case of $M=20$ past assortments, it follows from Lemma 5.2 that our
algorithm from §4.3 would require iterating over as many as $2^{20-2}\approx
260000$ assortments, and each iteration would have required solving a linear
optimization problem with more than $2^{20-1}\approx 520000$ decision
variables (see Corollary 5.5 and Proposition 3.5). In contrast, we observe
from Figure 5.2 that the computation time of our mixed-integer linear
optimization problem remained below 30 seconds on average. More generally, we
conclude from Figure 5.2 that our mixed-integer linear optimization
reformulation of the robust optimization problem (RO) from Theorem 5.8 can
scale to applications with realistic numbers of products and past assortments.

###  5.3 A Low-Risk Approach to Experimentation

In §4.1, we showed that there exist settings in which the robust optimization
problem (RO) is overly conservative, in the sense that there do not exist any
assortments that satisfy condition (IMP) from §2. While we showed through
numerical experiments in §4.2.2 that the robust optimization problem is not
_always_ conservative, we nonetheless face a fundamental question: what
assortment should a risk-averse firm offer to its customers when there do not
exist assortments that satisfy (IMP)? We conclude §5 by answering this
question in the case of nested past assortments by considering the following
alternative optimization problem:

$\displaystyle\underset{S\in\mathcal{S}}{\textnormal{maximize}}$
$\displaystyle\max_{\lambda\in\mathcal{U}}\mathscr{R}^{\lambda}(S)$ (RO-
Pareto) subject to
$\displaystyle\min_{\lambda\in\mathcal{U}}\mathscr{R}^{\lambda}(S)\geq\theta.$

In contrast to the robust optimization problem (RO), the optimization problem
(RO-Pareto) aims to find an assortment that maximizes the best-case expected
revenue while imposing a lower bound on the worst-case expected revenue. By
varying the lower bound $\theta$, the above optimization problem thus leads to
a _Pareto frontier_ of new assortments that a firm can offer to its customers
that offer varying degrees of possible improvement to the firm’s expected
revenue while enjoying guarantees on the decrease in expected revenue that the
firm might incur by experimenting with the new assortment. Such a Pareto
frontier of new assortments provided by (RO-Pareto) is especially attractive
to risk-averse firms in situations in which there do not exist any assortments
that satisfy (IMP), as there may exist optimal assortments for the
optimization problem (RO-Pareto) that are different from the firm’s past
assortments when choosing the parameter $\theta$ to be slightly less than the
expected revenue of the firm’s best past assortment. Moreover, in the case of
nested past assortments, we can use the same reformulation techniques from
§5.2 to reformulate (RO-Pareto) as a mixed-integer linear optimization
problem:

###### Theorem 5.9

Let Assumption 5 hold and $S_{1},\ldots,S_{M}\in\mathcal{S}$. Then the
optimization problem (RO-Pareto) can be reformulated as a mixed-integer linear
optimization problem with $n$ binary decision variables,
$\mathcal{O}(\textnormal{poly}(n,M))$ continuous decision variables, and
$\mathcal{O}(\textnormal{poly}(n,M))$ constraints.

We conclude with numerical experiments that showcase the managerial value of
(RO-Pareto) in applications in which it may be impossible to identify
assortments that satisfy (IMP). To perform our numerical experiments, we begin
by constructing randomly-generated problem instances in a manner that is
similar to that taken in §4. Specifically, in each problem instance, we
generate a sparse base parameter vector $\lambda^{*}$ by randomly selecting a
subset of rankings $\Sigma^{\prime}\subseteq\Sigma$ of length
$|\Sigma^{\prime}|=80$ and assigning the parameters
$\\{\lambda_{\sigma}:\sigma\in\Sigma^{\prime}\\}$ by drawing uniformly over
the $80$-dimensional probability simplex. Using this base choice for the
parameters, we then generate historical sales data for each of the past
assortments under the ranking-based choice model with the base parameters
$\lambda^{*}$, after which we forget the base parameters $\lambda^{*}$. In
each randomly-generated problem instance, the revenues are drawn from the
distribution $r_{1},\ldots,r_{n}\sim\textnormal{Uniform}\\{1,\ldots,10000\\}$,
and we sort the products such that $r_{1}<\cdots<r_{n}$. Finally, we use the
algorithm from Theorem 5.8 to compute the optimal objective value of the
robust optimization problem (RO), and we then use the algorithm from Theorem
5.9 to solve the optimization problem (RO-Pareto) for each parameter
$\theta\in\\{q\times\eqref{prob:robust}:q\in\\{0,0.01,\ldots,0.99,1.00\\}\\}$
to obtain a new assortment, denoted by $S^{\prime}$.

Figure 1: Pareto frontiers of new assortments from different collections of
past assortments

(a)
$\mathscr{M}=\left\\{\\{0,10\\},\\{0,9,10\\},\\{0,8,9,10\\},\ldots,\\{0,1,\ldots,9,10\\}\right\\}$

(b)
$\mathscr{M}=\left\\{\\{0,10\\},\\{0,1,10\\},\\{0,1,2,10\\},\ldots,\\{0,1,\ldots,9,10\\}\right\\}$

(c)
$\mathscr{M}=\\{\\{0,3,8,13\\},\\{0,3,5,8,10,13,15\\},\\{0,1,3,5,6,8,10,11,13,15\\},\\{0,1,3,4,5,6,8,9,10,11,13,14,15\\},\\{0,\ldots,15\\}\\}$

110 Each of the $x$-values in each problem instance corresponds to one of the
unique assortments obtained from solving the optimization problem (RO-Pareto)
across the choices of parameters
$\theta\in\\{q\times\eqref{prob:robust}:q\in\\{0,0.01,\ldots,0.99,1.00\\}\\}$.
The corresponding interval of $y$-values formed by the red and blue bars is
the interval $[\Pi_{\lambda}:\lambda\in\mathcal{U}]$, where
$\Pi_{\lambda}\triangleq
100\%\times(\mathscr{R}^{\lambda}(S^{\prime})-\max_{m\in\mathcal{M}}r^{\intercal}v_{m})/(\max_{m\in\mathcal{M}}r^{\intercal}v_{m})$
is the relative percentage improvement of the expected revenue of the new
assortment over the expected revenue of the firm’s best previously-offered
assortment for a given ranking-based choice model $\lambda\in\mathcal{U}$. The
top figure shows problem instances in which the past assortments are the
revenue-ordered assortments with $n=10$ products; the middle figure shows
problem instances in which the past assortments are the reverse revenue-
ordered assortments with $n=10$ products; the bottom figure shows problem
instances with a collection of nested past assortments with a complicated and
more realistic structure, $n=15$ products, and $M=5$ past assortments.

In Figure 1, we show the results of our experiments in cases where the
collection of past assortments is the revenue-ordered assortments, the reverse
revenue-ordered assortments, and neither revenue-ordered nor reverse revenue-
ordered. In each of these experiments, we visualize the Pareto frontier of new
assortments generated under ten randomly-generated instances of the specified
collections of past assortments. We elaborate on the key managerial insights
from these experiments below.

  * •

Compared to new assortments found using estimate-then-optimize, the Pareto
frontier of new assortments found from solving (RO-Pareto) enables firms to
select a new assortment that maximizes their best-case improvement in expected
revenue for any guaranteed level of risk that a firm is willing to incur. This
distinction is particularly salient in the case where the past assortments are
the revenue-ordered assortments (top of Figure 1). Indeed, we recall from §4.1
that the assortments found using estimate-then-optimize can have significant
declines in expected revenue compared to the best expected revenue from the
firm’s past assortments. In contrast, we observe from Figure 1a that nine out
of the ten problem instances yielded new assortments that firms can offer to
their customers that, under any ranking-based choice model that is consistent
with the firm’s historical sales data, will cause the firm’s expected revenue
to decline by no more than 12%. Hence, the results from Figure 1 show that our
algorithms can offer firms a low-risk way to experiment with the assortments
that they offer to their customers.

  * •

For the more realistic example in Figure 1c, we observe that the Pareto
frontier of new assortments found from solving (RO-Pareto) includes new
assortments that offer very high best-case increases in expected revenue
(20%-60%) while enjoying very low worst-case decreases in expected revenues
(1%-10%). In fact, several of the problem instances shown in Figure 6c
(instances 1, 9, and 10) show that there exist new assortments in which the
worst-case change in expected revenue is strictly positive, that is, there
exist assortments that satisfy (IMP).

  * •

As an auxiliary benefit, we observe in the case of $\theta=0$ that the optimal
objective value of the optimization problem (RO-Pareto) serves as an upper
bound on the expected revenue that could be obtained if the true ranking-based
choice model that generated the historical sales data was known. From this
perspective, we observe from Figure 1a that revenue-ordered assortments are
within 10% of optimal for the ten randomly-generated problem instances.

The results shown in Figure 1 are presented for cases in which the firm does
not have any business constraints on the assortments $S\in\mathcal{S}$. In
many applications of assortment optimization, firms can also have additional
business constraints (e.g., due to limited shelf space or bundling
requirements) that limit the space of possible new assortments; see Mišić
(2016, p.113). Because our algorithm from Theorem 5.9 consists of solving a
mixed-integer linear optimization problem with a binary decision variable
$x_{i}\in\\{0,1\\}$ for each product $i\in\mathcal{N}_{0}$ that satisfies
$x_{i}=1$ if and only if product $i$ is included in the assortment $S$, such
business constraints can be easily integrated directly into our mixed-integer
linear optimization problem. In particular, as long as the number of such
business constraints is not exponential in $n$ or $M$, the size of our mixed-
integer linear optimization reformulation of (RO-Pareto) will remain
polynomial in the number of products and number of past assortments.

##  6 Conclusion and Future Research

In this work, we investigated a popular class of high-dimensional discrete
choice models, known as ranking-based choice models, in the context of
assortment planning problems. Motivated by the fact that many ranking-based
choice models can be consistent with a firm’s historical sales data, we
considered a class of robust optimization problems in which the goal is find
an assortment that has high expected revenue across all of the ranking-based
choice models that are consistent with the firm’s historical sales data. By
developing the first structural results and practical algorithms for solving
these robust optimization problems, our paper showed in a variety of
applications that these robust optimization problems can be solved in
reasonable computation times and offer significant value to firms in
comparison to estimate-then-optimize in the context of data-driven assortment
optimization with ranking-based choice models.

We believe this work opens up a number of promising directions for future
research. First, our work showed for the first time that  the question of
whether it can be possible to identify assortments that satisfy condition
(IMP) can be answered for one popular class of high-dimensional discrete
choice models. Yet there are many other high-dimensional discrete choice
models beyond the ranking-based choice model for which this identification
question can be asked, such as models for capturing irrational customer choice
(Berbeglia 2018, Chen and Mišić 2022, Jena et al. 2022). Second, our work
showed that polynomial-time algorithms can be developed for solving the robust
optimization problem (RO) for ranking-based choice models. However, it may be
possible in certain settings that existing algorithms for estimating high-
dimensional discrete choice models such as expectation-maximization (Talluri
and Van Ryzin 2004, van Ryzin and Vulcano 2017, Şimşek and Topaloglu 2018), in
combination with algorithms for finding assortments that maximize the
predicted expected revenue, can lead to assortments with provable performance
guarantees with respect to the identification question. Establishing such
guarantees would provide new assurances to firms for using estimate-then-
optimize in high-stakes assortment planning problems. Finally, we believe that
the present and related work (e.g., Kallus and Zhou (2018), Sturt (2021))
provide a starting point for using robust optimization to develop efficient
algorithms that are valuable for operations management problems in which good
_average_ performance is paramount. In particular, future work may extend the
algorithms developed in the present paper to numerous other revenue management
problems, ranging from multi-product pricing to dynamic assortment planning.

## References

  * Ahuja et al. (1988) Ahuja RK, Magnanti TL, Orlin JB (1988) Network flows .
  * Aouad et al. (2021) Aouad A, Farias V, Levi R (2021) Assortment optimization under consider-then-choose choice models. _Management Science_ 67(6):3368–3386.
  * Aouad et al. (2018) Aouad A, Farias V, Levi R, Segev D (2018) The approximability of assortment optimization under ranking preferences. _Operations Research_ 66(6):1661–1669.
  * Berbeglia (2018) Berbeglia G (2018) The generalized stochastic preference choice model. _arXiv preprint arXiv:1803.04244_ .
  * Berbeglia and Joret (2020) Berbeglia G, Joret G (2020) Assortment optimisation under a general discrete choice model: A tight analysis of revenue-ordered assortments. _Algorithmica_ 82(4):681–720.
  * Bertsimas and Mišić (2017) Bertsimas D, Mišić VV (2017) Robust product line design. _Operations Research_ 65(1):19–37.
  * Bertsimas and Mišić (2019) Bertsimas D, Mišić VV (2019) Exact first-choice product line optimization. _Operations Research_ 67(3):651–670.
  * Block and Marschak (1959) Block H, Marschak J (1959) Random orderings and stochastic theories of response. Cowles Foundation Discussion Papers 66, Cowles Foundation for Research in Economics, Yale University, URL https://EconPapers.repec.org/RePEc:cwl:cwldpp:66.
  * Chen and Mišić (2022) Chen YC, Mišić VV (2022) Decision forest: A nonparametric approach to modeling irrational choice. _Management Science_ 68(10):7090–7111.
  * Davis et al. (2015) Davis JM, Topaloglu H, Williamson DP (2015) Assortment optimization over time. _Operations Research Letters_ 43(6):608–611.
  * Désir et al. (2021) Désir A, Goyal V, Jagabathula S, Segev D (2021) Mallows-smoothed distribution over rankings approach for modeling choice. _Operations Research_ 69(4):1206–1227.
  * Désir et al. (2023) Désir A, Goyal V, Jiang B, Xie T, Zhang J (2023) Robust assortment optimization under the markov chain choice model. _Operations Research_ .
  * Farias et al. (2013) Farias VF, Jagabathula S, Shah D (2013) A nonparametric approach to modeling choice with limited data. _Management Science_ 59(2):305–322.
  * Feldman et al. (2019) Feldman J, Paul A, Topaloglu H (2019) Assortment optimization with small consideration sets. _Operations Research_ 67(5):1283–1299.
  * Gallego et al. (2004) Gallego G, Iyengar G, Phillips R, Dubey A (2004) Managing flexible products on a network. _Available at SSRN 3567371_ .
  * Honhon et al. (2012) Honhon D, Jonnalagedda S, Pan XA (2012) Optimal algorithms for assortment selection under ranking-based consumer choice models. _Manufacturing & Service Operations Management_ 14(2):279–289.
  * Jagabathula (2014) Jagabathula S (2014) Assortment optimization under general choice. _Available at SSRN 2512831_ .
  * Jagabathula and Rusmevichientong (2019) Jagabathula S, Rusmevichientong P (2019) The limit of rationality in choice modeling: Formulation, computation, and implications. _Management Science_ 65(5):2196–2215.
  * Jena et al. (2022) Jena SD, Lodi A, Sole C (2022) On the estimation of discrete choice models to capture irrational customer behaviors. _INFORMS Journal on Computing_ 34(3):1606–1625.
  * Kallus and Zhou (2018) Kallus N, Zhou A (2018) Confounding-robust policy improvement. _Advances in Neural Information Processing Systems_ 31\.
  * Mišić (2016) Mišić VV (2016) _Data, models and decisions for large-scale stochastic optimization problems_. Ph.D. thesis, Massachusetts Institute of Technology.
  * Orlin (1997) Orlin JB (1997) A polynomial time primal network simplex algorithm for minimum cost flows. _Mathematical Programming_ 78(2):109–129.
  * Rusmevichientong et al. (2014) Rusmevichientong P, Shmoys D, Tong C, Topaloglu H (2014) Assortment optimization under the multinomial logit model with random choice parameters. _Production and Operations Management_ 23(11):2023–2039.
  * Rusmevichientong and Topaloglu (2012) Rusmevichientong P, Topaloglu H (2012) Robust assortment optimization in revenue management under the multinomial logit choice model. _Operations Research_ 60(4):865–882.
  * Şimşek and Topaloglu (2018) Şimşek AS, Topaloglu H (2018) An expectation-maximization algorithm to estimate the parameters of the markov chain choice model. _Operations Research_ 66(3):748–760.
  * Sturt (2021) Sturt B (2021) A nonparametric algorithm for optimal stopping based on robust optimization. _arXiv preprint arXiv:2103.03300_ .
  * Talluri and Van Ryzin (2004) Talluri K, Van Ryzin G (2004) Revenue management under a general discrete choice model of consumer behavior. _Management Science_ 50(1):15–33.
  * Tarjan (1997) Tarjan RE (1997) Dynamic trees as search trees via euler tours, applied to the network simplex algorithm. _Mathematical Programming_ 78(2):169–177.
  * van Ryzin and Vulcano (2015) van Ryzin G, Vulcano G (2015) A market discovery algorithm to estimate a general class of nonparametric choice models. _Management Science_ 61(2):281–300.
  * van Ryzin and Vulcano (2017) van Ryzin G, Vulcano G (2017) An expectation-maximization method to estimate a rank-based choice model of demand. _Operations Research_ 65(2):396–407.
  * Wang et al. (2020) Wang Z, Peura H, Wiesemann W (2020) Randomized assortment optimization. _Available at SSRN 3685695_ .

Technical Proofs and Additional Results

##  7 Proofs of Technical Results from §3

###  7.1 Proof of Proposition 3.5

Following the notation from §2, we readily observe that the worst-case
expected revenue for the fixed assortment $S\in\mathcal{S}$ is equal to the
optimal objective value of the following linear optimization problem:

$\displaystyle\begin{aligned}
&\;\underset{\lambda,\epsilon}{\textnormal{minimize}}&&\sum_{\sigma\in\Sigma}\sum_{i\in
S}r_{i}\mathbb{I}\left\\{i=\argmin_{j\in
S}\sigma(j)\right\\}\lambda_{\sigma}\\\ &\textnormal{subject
to}&&\sum_{\sigma\in\Sigma}\mathbb{I}\left\\{i=\argmin_{j\in
S_{m}}\sigma(j)\right\\}\lambda_{\sigma}-\epsilon_{m,i}=v_{m,i}\quad\forall
m\in\mathcal{M}\text{ and }i\in S_{m}\\\
&&&\sum_{\sigma\in\Sigma}\lambda_{\sigma}=1\\\ &&&\|\epsilon\|\leq\eta\\\
&&&\lambda_{\sigma}\geq 0\quad\forall\sigma\in\Sigma.\end{aligned}$ (WC-$S$)

For every assortment $S^{\prime}\in\mathcal{S}$, product in the assortment
$i\in S^{\prime}$, and ranking $\sigma\in\Sigma$, it follows immediately from
Definition 3.2 that the equality $\mathbb{I}\left\\{i=\argmin_{j\in
S^{\prime}}\sigma(j)\right\\}=1$ is satisfied if and only if
$\sigma\in\mathcal{D}_{i}(S^{\prime})$. Therefore, for every assortment
$S\in\mathcal{S}$, we observe that the linear optimization problem (WC-$S$) is
equivalent to

$\displaystyle\begin{aligned}
&\;\underset{\lambda,\epsilon}{\textnormal{minimize}}&&\sum_{i\in
S}\left(\sum_{\sigma\in\mathcal{D}_{i}(S)}\lambda_{\sigma}\right)r_{i}\\\
&\textnormal{subject
to}&&\sum_{\sigma\in\mathcal{D}_{i}(S_{m})}\lambda_{\sigma}-\epsilon_{m,i}=v_{m,i}&&\forall
m\in\mathcal{M}\text{ and }i\in S_{m}\\\
&&&\sum_{\sigma\in\Sigma}\lambda_{\sigma}=1\\\ &&&\|\epsilon\|\leq\eta\\\
&&&\lambda_{\sigma}\geq 0\quad\forall\sigma\in\Sigma.\end{aligned}$ (WC-$S$-1)

Moreover, we recall from Definitions 3.2 and 3.3 that there is a unique tuple
of products $(i_{1},\ldots,i_{M})\in\mathcal{L}$ corresponding to each ranking
$\sigma\in\Sigma$ that satisfies
$\sigma\in\cap_{m\in\mathcal{M}}\mathcal{D}_{i_{m}}(S_{m})$. Therefore, it
follows immediately from Definitions 3.2 and 3.3 that the linear optimization
problem (WC-$S$-1) is equivalent to

$\displaystyle\begin{aligned}
&\;\underset{\lambda,\epsilon}{\textnormal{minimize}}&&\sum_{(i_{1},\ldots,i_{M})\in\mathcal{L}}\sum_{i\in
S}r_{i}\left(\sum_{\sigma\in\cap_{m\in\mathcal{M}}\mathcal{D}_{i_{m}}(S_{m})\cap\mathcal{D}_{i}(S)}\lambda_{\sigma}\right)\\\
&\textnormal{subject
to}&&\sum_{(i_{1},\ldots,i_{M})\in\mathcal{L}:\;i_{m}=i}\left(\sum_{\sigma\in\cap_{m\in\mathcal{M}}\mathcal{D}_{i_{m}}(S_{m})}\lambda_{\sigma}\right)-\epsilon_{m,i}=v_{m,i}&&\forall
m\in\mathcal{M}\text{ and }i\in S_{m}\\\
&&&\sum_{(i_{1},\ldots,i_{M})\in\mathcal{L}}\left(\sum_{\sigma\in\cap_{m\in\mathcal{M}}\mathcal{D}_{i_{m}}(S_{m})}\lambda_{\sigma}\right)=1\\\
&&&\|\epsilon\|\leq\eta\\\ &&&\lambda_{\sigma}\geq
0\quad\forall\sigma\in\Sigma.\end{aligned}$ (WC-$S$-2)

We now simplify the linear optimization problem (WC-$S$-2) by performing a
transformation on its decision variables. Specifically, we transform
(WC-$S$-2) by creating the following new decision variables for each tuple of
products $(i_{1},\ldots,i_{M})\in\mathcal{L}$ and each product $i\in S$:

$\displaystyle\lambda_{i_{1}\cdots i_{M}}$
$\displaystyle\leftarrow\sum_{\sigma\in\cap_{m\in\mathcal{M}}\mathcal{D}_{i_{m}}(S_{m})}\lambda_{\sigma};$
$\displaystyle\omega_{i,i_{1}\cdots i_{M}}$
$\displaystyle\leftarrow\sum_{\sigma\in\cap_{m\in\mathcal{M}}\mathcal{D}_{i_{m}}(S_{m})\cap\mathcal{D}_{i}(S)}\lambda_{\sigma}.$

Let us make three observations about the new decision variables defined above.
First, we observe immediately from the definition of the new decision
variables $\omega_{i,i_{1}\cdots i_{M}}$ that the equality
$\omega_{i,i_{1}\cdots i_{M}}=0$ must hold for each tuple of products
$(i_{1},\ldots,i_{M})\in\mathcal{L}$ and product $i\in S$ that satisfy
$\cap_{m\in\mathcal{M}}\mathcal{D}_{i_{m}}(S_{m})\cap\mathcal{D}_{i}(S)=\emptyset$.
Second, we observe that the nonnegativity constraints $\lambda_{\sigma}\geq 0$
in the linear optimization problem (WC-$S$-2) imply that the new decision
variables must also satisfy the nonnegativity constraints
$\lambda_{i_{1}\cdots i_{M}}\geq 0$ and $\omega_{i,i_{1}\cdots i_{M}}\geq 0$.
Third, we observe from the definitions of the new decision variables that the
equality $\sum_{i\in S}\omega_{i,i_{1}\cdots i_{M}}=\lambda_{i_{1}\cdots
i_{M}}$ must hold for every tuple of products
$(i_{1},\ldots,i_{M})\in\mathcal{L}$. Based on the definitions of the new
decision variables and by applying the aforementioned three observations, we
have shown that the linear optimization problem (WC-$S$-2) is equivalent to

$\displaystyle\begin{aligned}
&\;\underset{\lambda,\epsilon,\omega}{\textnormal{minimize}}&&\sum_{(i_{1},\ldots,i_{M})\in\mathcal{L}}\sum_{i\in
S}r_{i}\omega_{i,i_{1}\cdots i_{M}}\\\ &\textnormal{subject
to}&&\begin{aligned} &\sum_{i\in S}\omega_{i,i_{1}\cdots
i_{M}}=\lambda_{i_{1}\cdots
i_{M}}&&\forall(i_{1},\ldots,i_{M})\in\mathcal{L}\\\
&\sum_{(i_{1},\ldots,i_{M})\in\mathcal{L}:\;i_{m}=i}\lambda_{i_{1}\cdots
i_{M}}-\epsilon_{m,i}=v_{m,i}&&\forall m\in\mathcal{M}\text{ and }i\in
S_{m}\\\ &\sum_{(i_{1},\ldots,i_{M})\in\mathcal{L}}\lambda_{i_{1}\cdots
i_{M}}=1\\\ \end{aligned}\\\ &&&\begin{aligned} &\|\epsilon\|\leq\eta\\\
&\lambda_{i_{1}\cdots i_{M}}\geq
0&&\forall(i_{1},\ldots,i_{M})\in\mathcal{L}\\\ &\omega_{i,i_{1}\cdots
i_{M}}\geq 0&&\forall i\in S\text{ and }(i_{1},\ldots,i_{M})\in\mathcal{L}\\\
&\omega_{i,i_{1}\cdots i_{M}}=0&&\forall i\in S\text{ and
}(i_{1},\ldots,i_{M})\in\mathcal{L}\textnormal{ such that
}\cap_{m\in\mathcal{M}}\mathcal{D}_{i_{m}}(S_{m})\cap\mathcal{D}_{i}(S)=\emptyset.\end{aligned}\end{aligned}$
(WC-$S$-3)

After rearranging terms, we observe that the linear optimization problem
(WC-$S$-3) is equivalent to

$\displaystyle\begin{aligned}
&\;\underset{\lambda,\epsilon}{\textnormal{minimize}}&&\sum_{(i_{1},\ldots,i_{M})\in\mathcal{L}}\left[\begin{aligned}
&\underset{\omega}{\textnormal{minimize}}&&\sum_{i\in
S}r_{i}\omega_{i,i_{1}\cdots i_{M}}\\\ &\textnormal{subject to}&&\sum_{i\in
S}\omega_{i,i_{1}\cdots i_{M}}=\lambda_{i_{1}\cdots i_{M}}\\\
&&&\omega_{i,i_{1}\cdots i_{M}}\geq 0\quad\forall i\in S\\\
&&&\omega_{i,i_{1}\cdots i_{M}}=0\quad\forall i\in S\textnormal{ such
that}\cap_{m\in\mathcal{M}}\mathcal{D}_{i_{m}}(S_{m})\cap\mathcal{D}_{i}(S)=\emptyset\end{aligned}\right]\\\
&\textnormal{subject to}&&\begin{aligned}
&\sum_{(i_{1},\ldots,i_{M})\in\mathcal{L}:\;i_{m}=i}\lambda_{i_{1}\cdots
i_{M}}-\epsilon_{m,i}=v_{m,i}\quad\forall m\in\mathcal{M}\text{ and }i\in
S_{m}\\\ &\sum_{(i_{1},\ldots,i_{M})\in\mathcal{L}}\lambda_{i_{1}\cdots
i_{M}}=1\\\ &\|\epsilon\|\leq\eta\\\ &\lambda_{i_{1}\cdots i_{M}}\geq
0\quad\forall(i_{1},\ldots,i_{M})\in\mathcal{L}.\end{aligned}\end{aligned}$
(WC-$S$-4)

Finally, we readily observe from Definition 3.4 that the following equality