holds for every $(i_{1},\ldots,i_{M})\in\mathcal{L}$:

$\displaystyle\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]=\rho_{i_{1}\cdots
i_{M}}(S)\lambda_{i_{1}\cdots i_{M}}.$

It follows from the above equality that (WC-$S$-4) is equivalent to the linear
optimization problem (1), which concludes our proof of Proposition 3.5.

###  7.2 A Graphical Interpretation of Definition 3.4

In view of our overarching strategy for the proof of Proposition 3.8 that is
described at the end of §3, we now proceed to analyze the behavior of the
functions $S\mapsto\rho_{i_{1}\cdots i_{M}}(S)$. In particular, we will show
in the rest of Appendix 7.2 that $\rho_{i_{1}\cdots i_{M}}(S)$ can be computed
by analyzing the reachability of vertices in a directed acyclic graph. In the
subsequent Appendix 7.3, we will use this graphical interpretation of
Definition 3.4 to show for every arbitrary assortment $S\in\mathcal{S}$ that
we can construct an assortment ${S}^{\prime}\in\widehat{\mathcal{S}}$ that
satisfies $\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}$, thereby completing the proof of Theorem
3.1.

To develop our alternative representation of $\rho_{i_{1}\cdots i_{M}}(S)$, we
begin by showing that the set of tuples of products $\mathcal{L}$ can be
interpreted as a set of directed acyclic graphs. Indeed, consider any
selection of products from each of the previously-offered assortments,
$(i_{1},\ldots,i_{M})\in S_{1}\times\cdots\times S_{M}$. From this tuple of
products, we will construct a directed graph, denoted by
$\mathcal{G}_{i_{1}\cdots i_{M}}$, in which the set of vertices in the graph
is equal to $\mathcal{N}_{0}$, and the graph has a directed edge $(i,i_{m})$
from vertex $i$ to vertex $i_{m}$ for each previously-offered assortment
$m\in\mathcal{M}$ and each product $i\in S_{m}\setminus\\{i_{m}\\}$. In Figure
7.2, we present visualizations of the directed graphs generated by this
construction procedure. In the first intermediary result of this subsection,
presented below as Lemma 7.1, we show that the tuple of products
$(i_{1},\ldots,i_{M})$ is an element of $\mathcal{L}$ if and only if the
directed graph $\mathcal{G}_{i_{1}\cdots i_{M}}$ is acyclic.

###### Lemma 7.1

$(i_{1},\ldots,i_{M})\in\mathcal{L}$ if and only if $\mathcal{G}_{i_{1}\cdots
i_{M}}$ is acyclic.

###### Proof 7.2

Proof. Consider any tuple of products $(i_{1},\ldots,i_{M})\in
S_{1}\times\cdots\times S_{M}$. First, we recall the fundamental result in
graph theory that a directed graph is acyclic if and only if there exists a
ranking $\sigma\in\Sigma$ that satisfies $\sigma(i)<\sigma(j)$ for every
directed edge $(j,i)$ in the graph (Ahuja et al. 1988, p. 77). Second, we
recall from our construction of $\mathcal{G}_{i_{1}\cdots i_{M}}$ that the
directed edges in $\mathcal{G}_{i_{1}\cdots i_{M}}$ are exactly those of the
form $(j,i_{m})$ for each previously-offered assortment $m\in\mathcal{M}$ and
product $j\in S_{m}\setminus\\{i_{m}\\}$. Combining these two recollections,
we see that the directed graph $\mathcal{G}_{i_{1}\cdots i_{M}}$ is acyclic if
and only if there exists a ranking $\sigma\in\Sigma$ that satisfies
$\sigma(i_{m})<\sigma(j)$ for each $m\in\mathcal{M}$ and $j\in
S_{m}\setminus\\{i_{m}\\}$. Since

$\displaystyle\left[\sigma(i_{m})<\sigma(j)\textnormal{ for all
}m\in\mathcal{M}\textnormal{ and }j\in S_{m}\setminus\\{i_{m}\\}\right]$
$\displaystyle\iff\left[i_{m}=\argmin_{j\in S_{m}}\sigma(j)\textnormal{ for
all }m\in\mathcal{M}\right]$
$\displaystyle\iff\left[\sigma\in\cap_{m\in\mathcal{M}}\mathcal{D}_{i_{m}}(S_{m})\right],$

we conclude that $\mathcal{G}_{i_{1}\cdots i_{M}}$ is acyclic if and only if
$(i_{1},\ldots,i_{M})\in\mathcal{L}$.

102 (d) $(i_{1},i_{2},i_{3})=(0,0,0)$

102 (e) $(i_{1},i_{2},i_{3})=(1,1,0)$

102 (f) $(i_{1},i_{2},i_{3})=(1,1,2)$

102 (g) $(i_{1},i_{2},i_{3})=(2,0,2)$

102 (h) $(i_{1},i_{2},i_{3})=(2,1,2)$

Visualizations of directed graphs $\mathcal{G}_{i_{1}\cdots i_{M}}$
corresponding to tuples of products $(i_{1},\ldots,i_{M})\in\mathcal{L}$. Each
of the five figures presents a visualization of the directed graph
$\mathcal{G}_{i_{1}i_{2}i_{3}}$ corresponding to a tuple of products
$(i_{1},i_{2},i_{3})\in\mathcal{L}$ in the case where there are $M=3$
previously-offered assortments of the form $S_{1}=\\{0,1,2\\}$,
$S_{2}=\\{0,1\\}$, and $S_{3}=\\{0,2\\}$. We observe that there exists an
incoming edge to vertex $i$ if and only if there exists a previously-offered
assortment $m\in\\{1,2,3\\}$ that satisfies $i=i_{m}$.

We next introduce the definition of _reachability_ for vertices in the
directed graph $\mathcal{G}_{i_{1}\cdots i_{M}}$. In particular, the following
definition is standard in the study of directed graphs, and we will make
extensive use of Definition 7.3 throughout the appendices of this paper.

###### Definition 7.3

Let $(i_{1},\ldots,i_{M})\in S_{1}\times\cdots\times S_{M}$ and
$i,j\in\mathcal{N}_{0}$. We say that vertex $j$ is _reachable_ from vertex
$i$, denoted by $j\prec_{i_{1}\cdots i_{M}}i$, if there exists a directed path
in $\mathcal{G}_{i_{1}\cdots i_{M}}$ from $i$ to $j$.

We adopt the convention throughout this paper that a directed path must
contain at least one directed edge. Hence, we observe that if the directed
graph $\mathcal{G}_{i_{1}\cdots i_{M}}$ is acyclic, then it must be the case
that a vertex may never be reachable from itself, that is,
$i\nprec_{i_{1}\cdots i_{M}}i$ for all $i\in\mathcal{N}_{0}$.

We now use Definition 7.3 to develop several intermediary results regarding
the structure of the directed acyclic graph $\mathcal{G}_{i_{1}\cdots i_{M}}$
for each tuple of products $(i_{1},\ldots,i_{M})\in\mathcal{L}$. We begin with
a simple intermediary result, denoted below by Lemma 7.4, in which we
characterize the vertices in the directed acyclic graph
$\mathcal{G}_{i_{1}\cdots i_{M}}$ that can be reachable from other vertices.

###### Lemma 7.4

Let $(i_{1},\ldots,i_{M})\in\mathcal{L}$ and $i,j\in\mathcal{N}_{0}$. If
$j\prec_{i_{1}\cdots i_{M}}i$, then there exists a previously-offered
assortment $m\in\mathcal{M}$ that satisfies $j=i_{m}$.

###### Proof 7.5

Proof. Consider any tuple of products $(i_{1},\ldots,i_{M})\in\mathcal{L}$. We
recall from our construction of $\mathcal{G}_{i_{1}\cdots i_{M}}$ that
$i_{1},\ldots,i_{M}$ are the only vertices in $\mathcal{G}_{i_{1}\cdots
i_{M}}$ that have incoming edges. Since Lemma 7.1 implies that
$\mathcal{G}_{i_{1}\cdots i_{M}}$ is acyclic, we conclude that
$i_{1},\ldots,i_{M}$ are the only vertices in $\mathcal{G}_{i_{1}\cdots
i_{M}}$ that can be reachable from other vertices.

In our next intermediary result, denoted by Lemma 7.6, we relate the
reachability of vertices in a directed acyclic graph $\mathcal{G}_{i_{1}\cdots
i_{M}}$ to the set of rankings that correspond to
$(i_{1},\ldots,i_{M})\in\mathcal{L}$.

###### Lemma 7.6

Let $(i_{1},\ldots,i_{M})\in\mathcal{L}$ and $i,j\in\mathcal{N}_{0}$. Then,
there exists a ranking
$\sigma\in\cap_{m\in\mathcal{M}}\mathcal{D}_{i_{m}}(S_{m})$ that satisfies
$\sigma(i)<\sigma(j)$ if and only if $j\nprec_{i_{1}\cdots i_{M}}i$.

###### Proof 7.7

Proof. Let $i,j\in\mathcal{N}_{0}$ and $(i_{1},\ldots,i_{M})\in\mathcal{L}$,
in which case it follows from Lemma 7.1 that the directed graph
${\mathcal{G}}_{i_{1}\cdots i_{M}}$ is acyclic.

To show the first direction of the desired result, let us suppose that
$j\nprec_{i_{1}\cdots i_{M}}i$. In this case, we observe that the directed
edge $(j,i)$ can be added to $\mathcal{G}_{i_{1}\cdots i_{M}}$ without
inducing any cycles. For notational convenience, let this augmented graph with
the directed edge $(j,i)$ be denoted by $\tilde{\mathcal{G}}_{i_{1}\cdots
i_{M}}$. Since the augmented graph $\tilde{\mathcal{G}}_{i_{1}\cdots i_{M}}$
is acyclic, it follows from Ahuja et al. (1988, p. 77) that there exists a
ranking $\sigma\in\Sigma$ that satisfies
$\sigma(j^{\prime})<\sigma(i^{\prime})$ for all directed edges
$(i^{\prime},j^{\prime})$ in the augmented graph. Moreover, since the set of
directed edges in the augmented graph $\tilde{\mathcal{G}}_{i_{1}\cdots
i_{M}}$ is a superset of the set of directed edges in the original graph
$\mathcal{G}_{i_{1}\cdots i_{M}}$, it follows from the construction of the
original graph that this ranking satisfies $\sigma(i_{m})<\sigma(i^{\prime})$
for all $m\in\mathcal{M}$ and all $i^{\prime}\in S_{m}\setminus\\{i_{m}\\}$,
which implies that
$\sigma\in\cap_{m\in\mathcal{M}}\mathcal{D}_{i_{m}}(S_{m})$. Since the
augmented graph has the directed edge $(j,i)$, we observe that this ranking
satisfies $\sigma(i)<\sigma(j)$. In summary, we have shown that if
$j\nprec_{i_{1}\cdots i_{M}}i$, then there exists a ranking
$\sigma\in\cap_{m\in\mathcal{M}}\mathcal{D}_{i_{m}}(S_{m})$ that satisfies
$\sigma(i)<\sigma(j)$. This concludes our proof of the first direction of
Lemma 7.6.

To show the other direction, let us suppose that $j\prec_{i_{1}\cdots
i_{M}}i$. In this case, consider any arbitrary ranking $\sigma\in\Sigma$ that
satisfies $\sigma\in\cap_{m\in\mathcal{M}}\mathcal{D}_{i_{m}}(S_{m})$. It
follows from the fact that
$\sigma\in\cap_{m\in\mathcal{M}}\mathcal{D}_{i_{m}}(S_{m})$ and from the
construction of $\mathcal{G}_{i_{1}\cdots i_{M}}$ that the inequality
$\sigma(j^{\prime})<\sigma(i^{\prime})$ holds for each directed edge
$(i^{\prime},j^{\prime})$ in this graph. Moreover, without loss of generality,
let the directed path from vertex $i$ to vertex $j$ be denoted by the sequence
of vertices $i,j_{1},\ldots,j_{\nu},j$ which satisfies the property that
$(i,j_{1}),(j_{1},j_{2}),\ldots,(j_{\nu-1},j_{\nu}),(j_{\nu},j)$ are directed
edges in $\mathcal{G}_{i_{1}\cdots i_{M}}$. It then follows from our earlier
reasoning that $\sigma(i)>\sigma(j_{1})>\cdots>\sigma(j_{\nu})>\sigma(j)$.
Since the ranking $\sigma\in\cap_{m\in\mathcal{M}}\mathcal{D}_{i_{m}}(S_{m})$
was chosen arbitrarily, our proof of the other direction is complete.

Intuitively, Lemma 7.6 shows that the reachability of vertices in a directed
acyclic graph $\mathcal{G}_{i_{1}\cdots i_{M}}$ provides an encoding of the
rankings that correspond to a tuple of products
$(i_{1},\ldots,i_{M})\in\mathcal{L}$. Said another way, Lemma 7.6 implies that
if vertex $i$ has a directed path to vertex $j$ in a directed acyclic graph
$\mathcal{G}_{i_{1}\cdots i_{M}}$, then product $j$ is always preferred to
product $i$ under all rankings that correspond to the tuple of products
$(i_{1},\ldots,i_{M})\in\mathcal{L}$. In our final intermediary result in
Appendix 7.2, denoted below by Lemma 7.8, we develop a generalization of Lemma
7.6 that relates the reachability of vertices in a directed acyclic graph
$\mathcal{G}_{i_{1}\cdots i_{M}}$ to the most preferred products in an
assortment $S\in\mathcal{S}$.

###### Lemma 7.8

Let $(i_{1},\ldots,i_{M})\in\mathcal{L}$, $S\in\mathcal{S}$, and $i\in S$.
Then, there exists a ranking
$\sigma\in\cap_{m\in\mathcal{M}}\mathcal{D}_{i_{m}}(S_{m})$ that satisfies
$i=\argmin_{j\in S}\sigma(j)$ if and only if $j\nprec_{i_{1}\cdots i_{M}}i$
for all $j\in S$.

###### Proof 7.9

Proof.

Consider any tuple of products $(i_{1},\ldots,i_{M})\in\mathcal{L}$,
assortment $S\in\mathcal{S}$, and product $i\in S$.

To prove the first direction of Lemma 7.8, suppose there exists a product
$j\in S$ that satisfies $j\prec_{i_{1}\cdots i_{M}}i$. In this case, it
follows immediately from Lemma 7.4 that there exists a previously-offered
assortment $m\in\mathcal{M}$ that satisfies $i_{m}\in S$ and
$i_{m}\prec_{i_{1}\cdots i_{M}}i$. Therefore, for each ranking
$\sigma\in\cap_{m\in\mathcal{M}}\mathcal{D}_{i_{m}}(S_{m})$, it follows from
Lemma 7.6 that $\sigma(i_{m})<\sigma(i)$, which combined with the fact that
$i_{m}\in S$ implies that $i\neq\argmin_{j\in S}\sigma(j)$. That concludes our
proof of the first direction.

To prove the other direction, suppose that $i\neq\argmin_{j\in S}\sigma(j)$
for all rankings $\sigma\in\cap_{m\in\mathcal{M}}\mathcal{D}_{i_{m}}(S_{m})$.
In this case, it follows immediately from Definition 3.2 that
$\cap_{m\in\mathcal{M}}\mathcal{D}_{i_{m}}(S_{m})\cap\mathcal{D}_{i}(S)=\emptyset$.
Moreover, it follows from the fact that $(i_{1},\ldots,i_{M})\in\mathcal{L}$
and from Lemma 7.1 that that the directed graph $\mathcal{G}_{i_{1}\cdots
i_{M}}$ is acyclic. Therefore, we observe from the fact that
$\cap_{m\in\mathcal{M}}\mathcal{D}_{i_{m}}(S_{m})\cap\mathcal{D}_{i}(S)=\emptyset$
and from Lemma 7.1 that adding the directed edges $\\{(j,i):j\in
S\setminus\\{i\\}\\}$ to the directed acyclic graph $\mathcal{G}_{i_{1}\cdots
i_{M}}$ would result in a directed cycle. Since a cycle visits every vertex at
most once, there must exist a single vertex $j\in S\setminus\\{i\\}$ such that
adding only the directed edge $(j,i)$ to $\mathcal{G}_{i_{1}\cdots i_{M}}$
would result in a directed cycle, which implies that $j\prec_{i_{1}\cdots
i_{M}}i$. This concludes our proof of the other direction.

Lemma 7.8 establishes that a product $i\in S$ is the most preferred product
from assortment $S\in\mathcal{S}$ under a ranking that corresponds to the
tuple of products $(i_{1},\ldots,i_{M})\in\mathcal{L}$ if and only if there
does not exist a directed path in the directed acyclic graph
$\mathcal{G}_{i_{1}\cdots i_{M}}$ from vertex $i$ to any vertex $j$ that
satisfies $j\in S$. In other words, Lemma 7.8 implies that the set
$\cap_{m\in\mathcal{M}}\mathcal{D}_{i_{m}}(S_{m})\cap\mathcal{D}_{i}(S)$ is
nonempty if and only if there is no vertex $j\in S$ which is reachable from
vertex $i$.

In view of the above, we are now ready to develop our graphical interpretation
of $\rho_{i_{1}\cdots i_{M}}(S)$. This interpretation of $\rho_{i_{1}\cdots
i_{M}}(S)$, which is presented below in Proposition 7.11, will be instrumental
to our analysis in the subsequent Appendix 7.3, where we will use this
interpretation to analyze the behavior of the functions
$S\mapsto\rho_{i_{1}\cdots i_{M}}(S)$ for each tuple of products
$(i_{1},\ldots,i_{M})\in\mathcal{L}$. Our graphical representation of
$\rho_{i_{1}\cdots i_{M}}(S)$ requires the following definition of the set
$\mathcal{I}_{i_{1}\cdots i_{M}}(S)$, which can be interpreted as the set of
all vertices $i\in\mathcal{N}_{0}$ in the directed graph
$\mathcal{G}_{i_{1}\cdots i_{M}}$ that do not have a directed path to any of
the vertices $i_{1},\ldots,i_{M}$ that are elements of the assortment $S$.

###### Definition 7.10

$\mathcal{I}_{i_{1}\cdots
i_{M}}(S)\triangleq\left\\{i\in\mathcal{N}_{0}:\;\textnormal{for all
}m\in\mathcal{M},\;\textnormal{if }i_{m}\in S,\text{ then
}i_{m}\nprec_{i_{1}\cdots i_{M}}i\right\\}$.

To make sense of Definition 7.10, we recall from Lemma 7.4 that a vertex $j$
in a directed acyclic graph $\mathcal{G}_{i_{1}\cdots i_{M}}$ can be reachable
from another vertex only if $j=i_{m}$ for some previously-offered assortment
$m\in\mathcal{M}$. Therefore, it follows immediately from Lemma 7.8 that
$S\cap\mathcal{I}_{i_{1}\cdots i_{M}}(S)$ is the set of products $i$ for which
the set of rankings
$\cap_{m\in\mathcal{M}}\mathcal{D}_{i_{m}}(S_{m})\cap\mathcal{D}_{i}(S)$ is
nonempty. Combining this with Definition 3.4, we have concluded the proof of
the following Proposition 7.11, which establishes our graphical interpretation
of $\rho_{i_{1}\cdots i_{M}}(S)$.

###### Proposition 7.11

For all $S\in\mathcal{S}$ and $(i_{1},\ldots,i_{M})\in\mathcal{L}$,
$\rho_{i_{1}\cdots i_{M}}(S)=\min_{i\in S\cap\mathcal{I}_{i_{1}\cdots
i_{M}}(S)}r_{i}.$

###  7.3 Proof of Proposition 3.8

Equipped with Proposition 7.11 from Appendix 7.2, we are now ready to present
our proof of Proposition 3.8. To show this, we begin by developing an
intermediary result, denoted below by Claim 1, that will allow us to compare
the values of $\rho_{i_{1}\cdots i_{M}}(S)$ and $\rho_{i_{1}\cdots
i_{M}}(S\cup\\{i\\})$ for every assortment $S\in\mathcal{S}$ and every product
$i$ which is not in the assortment.

###### Claim 1

For all $S\in\mathcal{S}$, $(i_{1},\ldots,i_{M})\in\mathcal{L}$, and $i\notin
S$,

$\displaystyle\rho_{i_{1}\cdots
i_{M}}(S\cup\\{i\\})=\begin{cases}\rho_{i_{1}\cdots i_{M}}(S),&\textnormal{if
}i\notin\mathcal{I}_{i_{1}\cdots i_{M}}(S),\\\ \min\left\\{\min\limits_{j\in
S\cap\mathcal{I}_{i_{1}\cdots
i_{M}}(S)\cap\left\\{j^{\prime}\in\mathcal{N}_{0}:i\nprec_{i_{1}\cdots
i_{M}}j^{\prime}\right\\}}r_{j},r_{i}\right\\},&\textnormal{if
}i\in\mathcal{I}_{i_{1}\cdots i_{M}}(S).\\\ \end{cases}$

###### Proof 7.12

Proof of Claim 1. Consider any assortment $S\in\mathcal{S}$, tuple of products
$(i_{1},\ldots,i_{M})\in\mathcal{L}$, and product $i\notin S$. We first
observe that

$\displaystyle\mathcal{I}_{i_{1}\cdots i_{M}}(S\cup\\{i\\})$
$\displaystyle=\left\\{j\in\mathcal{N}_{0}:\textnormal{for all
}m\in\mathcal{M},\;\textnormal{if }i_{m}\in S\cup\\{i\\},\text{ then
}i_{m}\nprec_{i_{1}\cdots i_{M}}j\right\\}$
$\displaystyle=\left\\{j\in\mathcal{N}_{0}:\textnormal{for all
}m\in\mathcal{M},\;\textnormal{if }i_{m}\in S,\text{ then
}i_{m}\nprec_{i_{1}\cdots i_{M}}j\right\\}$
$\displaystyle\quad\cap\left\\{j\in\mathcal{N}_{0}:\textnormal{if there exists
}m\in\mathcal{M}\textnormal{ such that }i=i_{m},\textnormal{ then
}i\nprec_{i_{1}\cdots i_{M}}j\right\\}$
$\displaystyle=\mathcal{I}_{i_{1}\cdots
i_{M}}(S)\cap\left\\{j\in\mathcal{N}_{0}:\textnormal{if there exists
}m\in\mathcal{M}\textnormal{ such that }i=i_{m},\textnormal{ then
}i\nprec_{i_{1}\cdots i_{M}}j\right\\}$
$\displaystyle=\begin{cases}\mathcal{I}_{i_{1}\cdots i_{M}}(S),&\text{if
}i\notin\\{i_{1},\ldots,i_{M}\\},\\\ \mathcal{I}_{i_{1}\cdots
i_{M}}(S)\cap\left\\{j\in\mathcal{N}_{0}:i\nprec_{i_{1}\cdots
i_{M}}j\right\\},&\text{if }i\in\\{i_{1},\ldots,i_{M}\\}\end{cases}$
$\displaystyle=\mathcal{I}_{i_{1}\cdots
i_{M}}(S)\cap\left\\{j\in\mathcal{N}_{0}:i\nprec_{i_{1}\cdots
i_{M}}j\right\\}.$ (7)

Indeed, the first and third equalities follow from Definition 7.10. The second
and fourth equalities follow from algebra. The final equality follows from the
fact that if $i\notin\\{i_{1},\ldots,i_{M}\\}$, then it follows from the
construction of $\mathcal{G}_{i_{1}\cdots i_{M}}$ that there are no incoming
edges to vertex $i$, which implies that
$\left\\{j\in\mathcal{N}_{0}:i\nprec_{i_{1}\cdots
i_{M}}j\right\\}=\mathcal{N}_{0}$.

Therefore, it follows from line (7) and Proposition 7.11 that

$\displaystyle\rho_{i_{1}\cdots i_{M}}(S\cup\\{i\\})$
$\displaystyle=\min_{j\in(S\cup\\{i\\})\cap\mathcal{I}_{i_{1}\cdots
i_{M}}(S\cup\\{i\\})}r_{j}$
$\displaystyle=\min_{j\in(S\cup\\{i\\})\cap\mathcal{I}_{i_{1}\cdots
i_{M}}(S)\cap\\{j^{\prime}\in\mathcal{N}_{0}:\;i\nprec_{i_{1}\cdots
i_{M}}j^{\prime}\\}}r_{j}$ $\displaystyle=\begin{cases}\min\limits_{j\in
S\cap\mathcal{I}_{i_{1}\cdots
i_{M}}(S)\cap\\{j^{\prime}\in\mathcal{N}_{0}:i\nprec_{i_{1}\cdots
i_{M}}j^{\prime}\\}}r_{j},&\text{if }i\notin\mathcal{I}_{i_{1}\cdots
i_{M}}(S),\\\ \min\left\\{\min\limits_{j\in S\cap\mathcal{I}_{i_{1}\cdots
i_{M}}(S)\cap\\{j^{\prime}\in\mathcal{N}_{0}:i\nprec_{i_{1}\cdots
i_{M}}j^{\prime}\\}}r_{j},r_{i}\right\\},&\text{if
}i\in\mathcal{I}_{i_{1}\cdots i_{M}}(S),\end{cases}$ (8)

where the first equality follows from Proposition 7.11, the second equality
follows from line (7), and the last equality follows from algebra and the fact
that $i\nprec_{i_{1}\cdots i_{M}}i$.

We conclude the proof of Claim 1 by considering the case where
$i\notin\mathcal{I}_{i_{1}\cdots i_{M}}(S)$. For this case, suppose for the
sake of developing a contradiction that there exists $j\in
S\cap\mathcal{I}_{i_{1}\cdots i_{M}}(S)$ which satisfies $i\prec_{i_{1}\cdots
i_{M}}j$. Under that supposition, it would follow from the fact that
$i\notin\mathcal{I}_{i_{1}\cdots i_{M}}(S)$ and Definition 7.10 that there
would exist a previously-offered assortment $m\in\mathcal{M}$ that satisfies
$i_{m}\in S$ and $i_{m}\prec_{i_{1}\cdots i_{M}}i$. Thus, by the transitive
property, we have $i_{m}\prec_{i_{1}\cdots i_{M}}i\prec_{i_{1}\cdots i_{M}}j$,
which contradicts the supposition that $j\in\mathcal{I}_{i_{1}\cdots
i_{M}}(S)$. Because we have a contradiction, we have shown that
$i\nprec_{i_{1}\cdots i_{M}}j$ for all $j\in S\cap\mathcal{I}_{i_{1}\cdots
i_{M}}(S)$, and so the desired result follows immediately from line (8) and
Definition 3.4.

Using the above intermediary result, we show in the following Claim 2 that for
each assortment $S\in\mathcal{S}$, we can construct an assortment
$S^{\prime}\in\widehat{\mathcal{S}}$ that satisfies $\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}$.

###### Claim 2

Let $S\in\mathcal{S}$ and $i\notin S$. If there exists $i^{*}\in S$ which
satisfies $r_{i^{*}}<r_{i}$ and $\mathcal{M}_{i^{*}}\subseteq\mathcal{M}_{i}$,
then $\rho_{i_{1}\cdots i_{M}}(S)\leq\rho_{i_{1}\cdots i_{M}}(S\cup\\{i\\})$
for each $(i_{1},\ldots,i_{M})\in\mathcal{L}$.

###### Proof 7.13

Proof of Claim 2. Consider any assortment $S\in\mathcal{S}$ and any product
$i\notin S$. Suppose that there exists a product $i^{*}\in S$ which satisfies
$r_{i^{*}}<r_{i}$ and $\mathcal{M}_{i^{*}}\subseteq\mathcal{M}_{i}$. For each
tuple of products $(i_{1},\ldots,i_{M})\in\mathcal{L}$, we have two cases to
consider:

  * •

Case 1: Suppose that $i\notin\mathcal{I}_{i_{1}\cdots i_{M}}(S)$. In this
case, it follows immediately from Claim 1 that

$\rho_{i_{1}\cdots i_{M}}(S\cup\\{i\\})=\rho_{i_{1}\cdots i_{M}}(S),$

and so the inequality $\rho_{i_{1}\cdots i_{M}}(S)\leq\rho_{i_{1}\cdots
i_{M}}(S\cup\\{i\\})$ holds when $i\notin\mathcal{I}_{i_{1}\cdots i_{M}}(S)$.

  * •

Case 2: Suppose that $i\in\mathcal{I}_{i_{1}\cdots i_{M}}(S)$.

In this case, we begin by showing that $i_{m}\notin S$ for each
$m\in\mathcal{M}_{i}$. Indeed, consider any previously-offered assortment
$m\in\mathcal{M}_{i}$. On one hand, if $i=i_{m}$, then it follows immediately
from the fact that $i\notin S$ that $i_{m}\notin S$. On the other hand, if
$i\neq i_{m}$, then it also must be the case that $i_{m}\notin S$, else we
would have a contradiction with the fact that $i\in\mathcal{I}_{i_{1}\cdots
i_{M}}(S)$ and the fact that there is, by our construction of
$\mathcal{G}_{i_{1}\cdots i_{M}}$, a directed edge from vertex $i$ to vertex
$i_{m}$. We have thus shown that $i_{m}\notin S$ for all
$m\in\mathcal{M}_{i}$.

We next show that $i_{m}\in\mathcal{I}_{i_{1}\cdots i_{M}}(S)$ for all
$m\in\mathcal{M}_{i}$. Indeed, consider any arbitrary $m\in\mathcal{M}_{i}$.
On one hand, if $i_{m}=i$, then the statement
$i_{m}\in\mathcal{I}_{i_{1}\cdots i_{M}}(S)$ follows immediately from the fact
that $i\in\mathcal{I}_{i_{1}\cdots i_{M}}(S)$. On the other hand, if
$i_{m}\neq i$, then it follows from the fact that
$i\in\mathcal{I}_{i_{1}\cdots i_{M}}(S)$ and the fact that there is a directed
edge from vertex $i$ to vertex $i_{m}$ that there must not be a directed path
from vertex $i_{m}$ to a vertex $i_{m^{\prime}}$ that satisfies
$i_{m^{\prime}}\in S$ for any $m^{\prime}\in\mathcal{M}$. We have thus shown
that $i_{m}\in\mathcal{I}_{i_{1}\cdots i_{M}}(S)$ for all
$m\in\mathcal{M}_{i}$.

Using the above results, we now prove that $i^{*}\in\mathcal{I}_{i_{1}\cdots
i_{M}}(S)$. Indeed, we have shown in the above results that $i_{m}\notin S$
and $i_{m}\in\mathcal{I}_{i_{1}\cdots i_{M}}(S)$ for all
$m\in\mathcal{M}_{i}$. Therefore, it follows from the supposition that
$\mathcal{M}_{i^{*}}\subseteq\mathcal{M}_{i}$ that $i_{m}\notin S$ and
$i_{m}\in\mathcal{I}_{i_{1}\cdots i_{M}}(S)$ for all
$m\in\mathcal{M}_{i^{*}}$. Since we have supposed that $i^{*}\in S$, it
follows from the fact that $i_{m}\notin S$ for all $m\in\mathcal{M}_{i^{*}}$
that $i^{*}\neq i_{m}$ for all $m\in\mathcal{M}_{i^{*}}$. Moreover, it follows
from the construction of $\mathcal{G}_{i_{1}\cdots i_{M}}$ that all of the
outgoing edges from vertex $i^{*}$ are incoming edges to vertices $i_{m}$ for
$m\in\mathcal{M}_{i^{*}}$. Therefore, it follows from the fact that
$i_{m}\in\mathcal{I}_{i_{1}\cdots i_{M}}(S)$ for all $m\in\mathcal{M}_{i^{*}}$
that $i^{*}\in\mathcal{I}_{i_{1}\cdots i_{M}}(S)$.

We now prove the desired result for Case 2. First, we observe that

$\displaystyle\rho_{i_{1}\cdots i_{M}}(S)=\min_{j\in
S\cap\mathcal{I}_{i_{1}\cdots i_{M}}(S)}r_{j}\leq r_{i^{*}},$ (9)

where the equality follows from Proposition 7.11 and the inequality follows
from our supposition that $i^{*}\in S$ and because we have shown that
$i^{*}\in\mathcal{I}_{i_{1}\cdots i_{M}}(S)$. Therefore, we have that

$\displaystyle\rho_{i_{1}\cdots i_{M}}(S\cup\\{i\\})$
$\displaystyle=\min\left\\{\min\limits_{j\in S\cap\mathcal{I}_{i_{1}\cdots
i_{M}}(S)\cap\\{j^{\prime}\in\mathcal{N}_{0}:i\nprec_{i_{1}\cdots
i_{M}}j^{\prime}\\}}r_{j},r_{i}\right\\}$
$\displaystyle\geq\min\left\\{\min\limits_{j\in S\cap\mathcal{I}_{i_{1}\cdots
i_{M}}(S)}r_{j},r_{i}\right\\}$ $\displaystyle=\min\left\\{\rho_{i_{1}\cdots
i_{M}}(S),r_{i}\right\\}$ $\displaystyle=\rho_{i_{1}\cdots i_{M}}(S),$

where the first equality follows from Claim 1 and the supposition of Case 2
that $i\in\mathcal{I}_{i_{1}\cdots i_{M}}(S)$, the inequality follows algebra,
the second equality follows from Proposition 7.11, and the final equality
holds because of our supposition that $r_{i^{*}}<r_{i}$ and because of line
(9), which showed that $\rho_{i_{1}\cdots i_{M}}(S)\leq r_{i^{*}}$. This
concludes the proof of Case 2.

In both of the above two cases, we showed that $\rho_{i_{1}\cdots
i_{M}}(S)\leq\rho_{i_{1}\cdots i_{M}}(S\cup\\{i\\})$, and so our proof of
Claim 2 is complete.

We now use Claim 2 to complete our proof of Proposition 3.8. Indeed, consider
any arbitrary assortment $S\in\mathcal{S}$. For this assortment, we define a
new assortment as

$S^{\prime}\triangleq S\cup\left\\{i\in\mathcal{N}_{0}:\text{there exists
}i^{*}\in S\textnormal{ such that
}\mathcal{M}_{i^{*}}\subseteq\mathcal{M}_{i}\textnormal{ and
}r_{i^{*}}<r_{i}\right\\}.$

It follows immediately from the definition of the collection
$\widehat{\mathcal{S}}$ that this new assortment satisfies
$S^{\prime}\in\widehat{\mathcal{S}}$. Moreover, let
$\\{j_{1},\ldots,j_{\nu}\\}\triangleq S^{\prime}\setminus S$ denote the new
products that have been added into the assortment. Then we observe for each
tuple of products $(i_{1},\ldots,i_{M})\in\mathcal{L}$ that

$\displaystyle\rho_{i_{1}\cdots i_{M}}(S^{\prime})$
$\displaystyle=\rho_{i_{1}\cdots
i_{M}}(S)+\sum_{\iota=1}^{\nu}\left(\rho_{i_{1}\cdots
i_{M}}(S\cup\\{j_{1},\ldots,j_{\iota}\\})-\rho_{i_{1}\cdots
i_{M}}(S\cup\\{j_{1},\ldots,j_{\iota-1}\\})\right)\geq\rho_{i_{1}\cdots
i_{M}}(S).$

Indeed, the equality follows from algebra. The inequality follows from Claim
2, which implies that $\rho_{i_{1}\cdots
i_{M}}(S\cup\\{j_{1},\ldots,j_{\iota}\\})\geq\rho_{i_{1}\cdots
i_{M}}(S\cup\\{j_{1},\ldots,j_{\iota-1}\\})$ for each
$\iota\in\\{1,\ldots,\nu\\}$. Since the assortment $S\in\mathcal{S}$ was
chosen arbitrarily, our proof of Proposition 3.8 is complete.

##  8 Assumption that $\mathcal{N}_{0}=\cup_{m\in\mathcal{M}}S_{m}$

In Remark 4.1 of §4, we state an assumption that the universe of products
$\mathcal{N}_{0}$ is equal to $\cup_{m\in\mathcal{M}}S_{m}$, where
$S_{1},\ldots,S_{M}\subseteq\mathcal{N}_{0}$ are the assortments that the firm
has previously offered to its customers. In that remark, we claim that this
assumption can always be satisfied by redefining $\mathcal{N}_{0}$ to be equal
to $\cup_{m\in\mathcal{M}}S_{m}$. In this appendix, we argue that this
assumption is without loss of generality from the perspective of the robust
optimization problem (RO). Specifically, we formalize Remark 4.1 via the
following proposition:

###### Proposition 8.1

$\max\limits_{S\in\mathcal{S}}\min\limits_{\lambda\in\mathcal{U}}\mathscr{R}^{\lambda}(S)=\max\limits_{S\in\mathcal{S}}\min\limits_{\lambda\in\mathcal{U}}\mathscr{R}^{\lambda}\left(S\cap\left(\bigcup_{m\in\mathcal{M}}S_{m}\right)\right).$

The above proposition says that if $S^{*}\in\mathcal{S}$ is an optimal
solution of the robust optimization problem (RO), then
$S^{*}\cap\left(\bigcup_{m\in\mathcal{M}}S_{m}\right)$ is also an optimal
solution of the robust optimization problem (RO). Hence, the above proposition
implies that we can assume without loss of generality that the robust
optimization problem (RO) will only optimize over assortments $S$ in the set
$\mathcal{S}\cap\left(\bigcup_{m\in\mathcal{M}}S_{m}\right)$. The following
proof of Proposition 8.1 relies on the graphical interpretation of
$\rho_{i_{1}\cdots i_{M}}(S)$ that is developed in Appendix 7.2.

###### Proof 8.2

Proof of Proposition 8.1. We first observe that

$\displaystyle\max\limits_{S\in\mathcal{S}}\min\limits_{\lambda\in\mathcal{U}}\mathscr{R}^{\lambda}\left(S\cap\left(\bigcup_{m\in\mathcal{M}}S_{m}\right)\right)$
$\displaystyle=\max\limits_{S\in\mathcal{S}\cap\left(\bigcup_{m\in\mathcal{M}}S_{m}\right)}\min\limits_{\lambda\in\mathcal{U}}\mathscr{R}^{\lambda}\left(S\right)\leq\max\limits_{S\in\mathcal{S}}\min\limits_{\lambda\in\mathcal{U}}\mathscr{R}^{\lambda}(S),$

where the equality follows from the fact that
$\mathcal{S}\triangleq\\{S\subseteq\mathcal{N}_{0}:0\in S\\}$, and the
inequality follows from algebra. To show the other direction, consider any
arbitrary assortment $S\in\mathcal{S}$. We recall from Proposition 3.5 that
the worst-case expected revenue
$\min_{\lambda\in\mathcal{U}}\mathscr{R}^{\lambda}\left(S\cap\left(\bigcup_{m\in\mathcal{M}}S_{m}\right)\right)$
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}}\left(S\cap\left(\bigcup_{m\in\mathcal{M}}S_{m}\right)\right)\lambda_{i_{1}\cdots
i_{M}}$ (10) subject to same constraints as (1)

Moreover, we recall from Proposition 7.11 in Appendix 7.2 that the following
equality holds for each $(i_{1},\ldots,i_{M})\in\mathcal{L}$:

$\displaystyle\rho_{i_{1}\cdots
i_{M}}\left(S\cap\left(\bigcup_{m\in\mathcal{M}}S_{m}\right)\right)=\min_{i\in
S\cap\left(\bigcup_{m\in\mathcal{M}}S_{m}\right)\cap\mathcal{I}_{i_{1}\cdots
i_{M}}\left(S\cap\left(\bigcup_{m\in\mathcal{M}}S_{m}\right)\right)}r_{i}.$
(11)

In particular, we observe for each $(i_{1},\ldots,i_{M})\in\mathcal{L}$ that

$\displaystyle\mathcal{I}_{i_{1}\cdots
i_{M}}\left(S\cap\left(\bigcup_{m\in\mathcal{M}}S_{m}\right)\right)$
$\displaystyle=\left\\{i\in\mathcal{N}_{0}:\;\textnormal{for all
}m\in\mathcal{M},\;\textnormal{if }i_{m}\in
S\cap\left(\bigcup_{m\in\mathcal{M}}S_{m}\right),\text{ then
}i_{m}\nprec_{i_{1}\cdots i_{M}}i\right\\}$
$\displaystyle=\left\\{i\in\mathcal{N}_{0}:\;\textnormal{for all
}m\in\mathcal{M},\;\textnormal{if }i_{m}\in S,\text{ then
}i_{m}\nprec_{i_{1}\cdots i_{M}}i\right\\}$
$\displaystyle=\mathcal{I}_{i_{1}\cdots i_{M}}\left(S\right),$ (12)

where the first equality follows from Definition 7.10, the second equality
follows from the fact that $i_{1},\ldots,i_{M}\in\cup_{m\in\mathcal{M}}S_{m}$,
and the third equality follows from Definition 7.10. Therefore, for every
feasible solution $(\lambda,\epsilon)$ for the linear optimization problem
(1), we observe that

$\displaystyle\sum_{(i_{1},\ldots,i_{M})\in\mathcal{L}}\rho_{i_{1}\cdots
i_{M}}\left(S\cap\left(\bigcup_{m\in\mathcal{M}}S_{m}\right)\right)\lambda_{i_{1}\cdots
i_{M}}$
$\displaystyle=\sum_{(i_{1},\ldots,i_{M})\in\mathcal{L}}\left(\min_{i\in
S\cap\left(\bigcup_{m\in\mathcal{M}}S_{m}\right)\cap\mathcal{I}_{i_{1}\cdots
i_{M}}\left(S\cap\left(\bigcup_{m\in\mathcal{M}}S_{m}\right)\right)}r_{i}\right)\lambda_{i_{1}\cdots
i_{M}}$
$\displaystyle=\sum_{(i_{1},\ldots,i_{M})\in\mathcal{L}}\left(\min_{i\in
S\cap\left(\bigcup_{m\in\mathcal{M}}S_{m}\right)\cap\mathcal{I}_{i_{1}\cdots
i_{M}}\left(S\right)}r_{i}\right)\lambda_{i_{1}\cdots i_{M}}$
$\displaystyle\geq\sum_{(i_{1},\ldots,i_{M})\in\mathcal{L}}\left(\min_{i\in
S\cap\mathcal{I}_{i_{1}\cdots
i_{M}}\left(S\right)}r_{i}\right)\lambda_{i_{1}\cdots i_{M}}$
$\displaystyle=\sum_{(i_{1},\ldots,i_{M})\in\mathcal{L}}\rho_{i_{1}\cdots
i_{M}}\left(S\right)\lambda_{i_{1}\cdots i_{M}},$

where the first equality follows from (11), the second equality follows from
(12), the inequality follows from algebra, and the third equality follows from
Proposition 7.11. Since the above analysis holds for every feasible solution
$(\lambda,\epsilon)$ for the linear optimization problem (1), and since the
assortment $S\in\mathcal{S}$ was chosen arbitrarily, we conclude that

$\displaystyle\max\limits_{S\in\mathcal{S}}\min\limits_{\lambda\in\mathcal{U}}\mathscr{R}^{\lambda}\left(S\cap\left(\bigcup_{m\in\mathcal{M}}S_{m}\right)\right)$
$\displaystyle\geq\max\limits_{S\in\mathcal{S}}\min\limits_{\lambda\in\mathcal{U}}\mathscr{R}^{\lambda}(S).$

The proof of Proposition 8.1 is thus complete.

##  9 Proof of Theorem 4.2

Let $\mathscr{M}=\bar{\mathcal{S}}$, and let the previously-offered
assortments be indexed by $\mathscr{M}=\\{\bar{S}_{1},\ldots,\bar{S}_{n}\\}$,
whereby the $i$-th previously-offered assortment is
$\bar{S}_{i}\triangleq\\{0,i,i+1,\ldots,n-1,n\\}$.

Equipped with the above notation, we first prove that the equality
$\bar{\mathcal{S}}=\widehat{\mathcal{S}}$ holds. Indeed, choose any arbitrary
assortment $S\in\widehat{\mathcal{S}}$, and let $i^{*}\triangleq\argmin_{j\in
S:r_{j}>0}r_{j}$ denote the product in the chosen assortment that has the
smallest nonzero revenue. It readily follows from the facts that
$\mathscr{M}=\bar{\mathcal{S}}$ and $r_{1}<\cdots<r_{n}$ that the equalities
$\mathcal{M}_{i^{*}}=\\{m\in\mathcal{M}:m\leq i^{*}\\}$ and
$\mathcal{M}_{i}=\\{m\in\mathcal{M}:m\leq i\\}$ hold for each
$i\in\\{i^{*}+1,\ldots,n\\}$. Therefore, for each
$i\in\\{i^{*}+1,\ldots,n\\}$, it follows from the definition of the collection
$\widehat{\mathcal{S}}$, from the fact that $r_{i^{*}}<r_{i}$, and from the
fact that $\mathcal{M}_{i^{*}}\subseteq\mathcal{M}_{i}$ that $i\in S$. We have
thus shown that $S=\\{0,i^{*},i^{*}+1,\ldots,n-1,n\\}=\bar{S}_{i^{*}}$, which
implies that $S\in\bar{\mathcal{S}}$. Since the assortment
$S\in\widehat{\mathcal{S}}$ was chosen arbitrarily, we have shown that
$\widehat{\mathcal{S}}\subseteq\bar{\mathcal{S}}$. The other direction of the
proof that $\bar{\mathcal{S}}=\widehat{\mathcal{S}}$ follows from the fact
that the inclusion $\mathscr{M}\subseteq\widehat{\mathcal{S}}$ always
holds121212To see why the inclusion
$\mathscr{M}\subseteq\widehat{\mathcal{S}}$ always holds, consider any
previously-offered assortment $S\in\mathscr{M}$. For each product $i^{*}\in
S$, suppose that there exists another product $i$ which satisfies
$r_{i^{*}}<r_{i}$ and $\mathcal{M}_{i^{*}}\subseteq\mathcal{M}_{i}$. Since
$S\in\mathcal{M}_{i^{*}}\subseteq\mathcal{M}_{i}$, we conclude that $i\in S$
must hold, which proves that $S\in\widehat{\mathcal{S}}$.  and from the fact
that $\mathscr{M}=\bar{\mathcal{S}}$. Our proof that
$\bar{\mathcal{S}}=\widehat{\mathcal{S}}$ is thus complete.

Using the above result, we have

$\displaystyle\max_{S\in\mathcal{S}}\min_{\lambda\in\mathcal{U}}\mathscr{R}^{\lambda}(S)=\max_{S\in\widehat{\mathcal{S}}}\min_{\lambda\in\mathcal{U}}\mathscr{R}^{\lambda}(S)=\max_{S\in\bar{\mathcal{S}}}\min_{\lambda\in\mathcal{U}}\mathscr{R}^{\lambda}(S)=\max_{S\in\mathscr{M}}\min_{\lambda\in\mathcal{U}}\mathscr{R}^{\lambda}(S)=\max_{m\in\mathcal{M}}r^{\intercal}v_{m},$

where the first equality follows from Theorem 3.1, the second equality holds
because $\widehat{\mathcal{S}}=\bar{\mathcal{S}}$, the third equality holds
because $\mathscr{M}=\bar{\mathcal{S}}$, and the final equality follows from
the construction of the set of ranking-based choice models $\mathcal{U}$ (see
§2) and from the fact that $\eta=0$.

##  10 Proofs of Technical Results from §4.2

###  10.1 Proof of Lemma 4.4

For notational convenience, let the collection on the right side of line (2)
in Lemma 4.4 be denoted by $\widehat{\mathcal{S}}^{\prime}$. It follows
immediately from the definition of $\widehat{\mathcal{S}}$ and from the fact
that $r_{0}<r_{1}<\cdots<r_{n}$ that each assortment
$S\in\widehat{\mathcal{S}}^{\prime}$ is also an element of
$\widehat{\mathcal{S}}$. This proves that
$\widehat{\mathcal{S}}\supseteq\widehat{\mathcal{S}}^{\prime}$.

To show the other direction, consider any arbitrary assortment
$S\in\widehat{\mathcal{S}}$. We first show that $S_{1}\cap S_{2}\subseteq S$.
Indeed, it follows from the fact that $S,S_{1},S_{2}\in\mathcal{S}$ that $0\in
S\cap S_{1}\cap S_{2}$. Moreover, for each product $j\in(S_{1}\cap
S_{2})\setminus\\{0\\}$, we readily observe that the inequality $r_{j}>r_{0}$
and the equality $\mathcal{M}_{j}=\mathcal{M}_{0}$ both hold. Therefore, it
follows from the definition of $\widehat{\mathcal{S}}$ and the fact that
$S\in\widehat{\mathcal{S}}$ that each product $j\in S_{1}\cap S_{2}$ is also
an element of $S$. We have thus shown that $S_{1}\cap S_{2}\subseteq S$ for
all $S\in\widehat{\mathcal{S}}$. Next, we define the following integers:

$\displaystyle i_{1}$ $\displaystyle\triangleq\min\left\\{n,\min_{j\in
S_{1}\setminus S_{2}}j\right\\},$ $\displaystyle i_{2}$
$\displaystyle\triangleq\min\left\\{n,\min_{j\in S_{2}\setminus
S_{1}}j\right\\},$

where any minimization problem over an empty feasible set is defined equal to
$\infty$. It follows from the fact that $S\in\widehat{\mathcal{S}}$, from the
definition of $\widehat{\mathcal{S}}$, and from the assumption of
$r_{0}<r_{1}<\cdots<r_{n}$ that

$\displaystyle\left\\{j\in S_{1}\setminus S_{2}:j\geq i_{1}\right\\}\subseteq
S\text{ and }\left\\{j\in S_{2}\setminus S_{1}:j\geq i_{2}\right\\}\subseteq
S.$

Hence, it follows from the assumption that $S_{1}\cup S_{2}=\mathcal{N}_{0}$
that

$\displaystyle 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\\}.$

We have thus shown that the assortment $S$ is an element of the collection of
assortments $\widehat{\mathcal{S}}^{\prime}$. Since
$S\in\widehat{\mathcal{S}}$ was chosen arbitrarily, we have shown that
$\widehat{\mathcal{S}}\subseteq\widehat{\mathcal{S}}^{\prime}$, which
concludes our proof of Lemma 4.4.

###  10.2 Proof of Lemma 4.5

It follows from Definition 3.3 and the fact that $M=2$ that

$\displaystyle\mathcal{L}=\left\\{(i_{1},i_{2}):\mathcal{D}_{i_{1}}(S_{1})\cap\mathcal{D}_{i_{2}}(S_{2})\neq\emptyset\right\\}.$

The rest of the proof of Lemma 4.5 is split into three cases.

In the first case, consider any arbitrary pair of products
$(i_{1},i_{2})\in(S_{1}\setminus S_{2})\times S_{2}$. For this pair of
products, consider any ranking $\sigma\in\Sigma$ which satisfies the
equalities $\sigma(i_{1})=0$ and $\sigma(i_{2})=1$. It follows from the fact
that $i_{1}\in S_{1}$ that this ranking satisfies the equality $\argmin_{j\in
S_{1}}\sigma(j)=1$. Moreover, it follows from the facts that $i_{1}\notin
S_{2}$ and $i_{2}\in S_{2}$ that this ranking also satisfies the equality
$\argmin_{j\in S_{2}}\sigma(j)=2$. We have thus shown that
$\sigma\in\mathcal{D}_{1}(S_{1})\cap\mathcal{D}_{2}(S_{2})$, which proves that
$\mathcal{D}_{1}(S_{1})\cap\mathcal{D}_{2}(S_{2})\neq\emptyset$. Since the
pair of products $(i_{1},i_{2})\in(S_{1}\setminus S_{2})\times S_{2}$ was
chosen arbitrarily, we have shown that $(S_{1}\setminus S_{2})\times
S_{2}\subseteq\mathcal{L}$.

In the second case, consider any arbitrary pair of products $(i_{1},i_{2})\in
S_{1}\times(S_{2}\setminus S_{1})$. Using identical reasoning as the first
case, we observe that
$\mathcal{D}_{1}(S_{1})\cap\mathcal{D}_{2}(S_{2})\neq\emptyset$, which shows
that $S_{1}\times(S_{2}\setminus S_{1})\subseteq\mathcal{L}$.

In the third case, consider any arbitrary pair of products
$(i_{1},i_{2})\in(S_{1}\cap S_{2})\times(S_{1}\cap S_{2})$. For this pair of
products, it follows from Definition 3.2 that the inequality
$\sigma(i_{1})<\sigma(j)$ must hold for all rankings
$\sigma\in\mathcal{D}_{i_{1}}(S_{1})$ and all products $j\in(S_{1}\cap
S_{2})\setminus\\{i_{1}\\}$. It also follows from Definition 3.2 that the
inequality $\sigma(i_{2})<\sigma(j)$ must hold for all rankings
$\sigma\in\mathcal{D}_{i_{2}}(S_{2})$ and all products $j\in(S_{1}\cap
S_{2})\setminus\\{i_{2}\\}$. It follows immediately from these inequalities
that there exists a ranking that satisfies
$\sigma\in\mathcal{D}_{i_{1}}(S_{1})\cap\mathcal{D}_{i_{2}}(S_{2})$ if and
only if $i_{1}=i_{2}$, and so it follows from Definition 3.3 that
$(i_{1},i_{2})\in\mathcal{L}$ if and only if $i_{1}=i_{2}$.

Since the three cases we have considered are exhaustive, our proof of Lemma
4.5 is complete.

###  10.3 Proof of Lemma 4.6

Let $M=2$ and $\eta=0$. In the remainder of the proof of Lemma 4.6, we will
show that the following equality holds for all assortments $S\in\mathcal{S}$:

$\displaystyle\min_{\lambda\in\mathcal{U}}\mathscr{R}^{\lambda}(S)$
$\displaystyle=\sum_{i\in S_{1}\cap S_{2}}\rho_{ii}(S)v_{1,i}\;+$
$\displaystyle\quad\quad\quad\left[\begin{aligned}
&\;\underset{\lambda}{\textnormal{minimize}}&&\sum_{i_{1}\in S_{1}\setminus
S_{2}}\sum_{i_{2}\in S_{1}\cap
S_{2}}\rho_{i_{1}i_{2}}(S)\lambda_{i_{1}i_{2}}\\\ &&&+\sum_{i_{1}\in
S_{1}\setminus S_{2}}\sum_{i_{2}\in S_{2}\setminus
S_{1}}\rho_{i_{1}i_{2}}(S)\lambda_{i_{1}i_{2}}\\\ &&&+\sum_{i_{1}\in S_{1}\cap
S_{2}}\sum_{i_{2}\in S_{2}\setminus
S_{1}}(\rho_{i_{1}i_{2}}(S)-\rho_{i_{1}i_{1}}(S))\lambda_{i_{1}i_{2}}\\\
&\textnormal{subject to}&&\begin{aligned} &\sum_{i_{2}\in
S_{2}}\lambda_{i_{1}i_{2}}=v_{1,i_{1}}&&\forall i_{1}\in S_{1}\setminus
S_{2}\\\ &\sum_{i_{1}\in S_{1}}\lambda_{i_{1}i_{2}}=v_{2,i_{2}}&&\forall
i_{2}\in S_{2}\setminus S_{1}\\\ &\sum_{i_{1}\in S_{1}\setminus
S_{2}}\lambda_{i_{1}i}-\sum_{i_{2}\in S_{2}\setminus
S_{1}}\lambda_{ii_{2}}=v_{2,i}-v_{1,i}&&\forall i\in S_{1}\cap S_{2}\\\
&\lambda_{i_{1}i_{2}}\geq
0&&\forall(i_{1},i_{2})\in\mathcal{L}\end{aligned}\end{aligned}\right].$ (13)

We readily observe that the linear optimization problem on line (13) is a
minimum-cost network flow problem, where each decision variable
$\lambda_{i_{1}i_{2}}$ corresponds to the flow on a directed edge from vertex
$i_{1}$ to vertex $i_{2}$ (Ahuja et al. 1988, p. 296). In particular, we
observe that the minimum-cost network flow problem on line (13) takes place on
a complete tripartite directed acyclic graph with $|S_{1}\setminus
S_{2}|+|S_{2}\setminus S_{1}|+|S_{1}\cap S_{2}|=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. In Figure 10.3, we present a
visualization of the network corresponding to the minimum-cost network flow
problem from line (13).

105432

Visualization of minimum-cost network flow problem from line (13). The figure
shows a visualization of the minimum-cost network flow problem corresponding
to the linear optimization problem on line (13) for the case where the
previously-offered assortments are $S_{1}=\\{0,1,2,5\\}$ and
$S_{2}=\\{0,3,4,5\\}$. We see that there is a vertex in the graph for each
product $i\in\mathcal{N}_{0}\equiv\\{0,1,2,3,4,5\\}$. The graph is a complete
tripartite directed graph, where the three partitions of vertices are denoted
by the dotted ellipses and correspond to $S_{1}\setminus S_{2}=\\{1,2\\}$,
$S_{1}\cap S_{2}=\\{0,5\\}$, and $S_{2}\setminus S_{1}=\\{3,4\\}$. The flow
demands at each of the vertices and the flow cost for each of the directed
edges can be found on line (13).

We now proceed to prove that line (13) holds. Indeed, consider any arbitrary
assortment $S\in{\mathcal{S}}$. It follows from Proposition 3.5 and our
assumptions of $M=2$ and $\eta=0$ that

$\displaystyle\min_{\lambda\in\mathcal{U}}\mathscr{R}^{\lambda}(S)=\left[\begin{aligned}
&\;\underset{\lambda}{\textnormal{minimize}}&&\sum_{(i_{1},i_{2})\in\mathcal{L}}\rho_{i_{1}i_{2}}(S)\lambda_{i_{1}i_{2}}\\\
&\textnormal{subject
to}&&\sum_{(i_{1},i_{2})\in\mathcal{L}:\;i_{1}=i}\lambda_{i_{1}i_{2}}=v_{1,i}\quad\forall
i\in S_{1}\\\
&&&\sum_{(i_{1},i_{2})\in\mathcal{L}:\;i_{2}=i}\lambda_{i_{1}i_{2}}=v_{2,i}\quad\forall
i\in S_{2}\\\ &&&\sum_{(i_{1},i_{2})\in\mathcal{L}}\lambda_{i_{1}i_{2}}=1\\\
&&&\lambda_{i_{1}i_{2}}\geq
0\quad\forall(i_{1},i_{2})\in\mathcal{L}\end{aligned}\right].$

After applying Lemma 4.5 to the above optimization problem and removing the
redundant constraint
$\sum_{(i_{1},i_{2})\in\mathcal{L}}\lambda_{i_{1}i_{2}}=1$, we observe that

$\displaystyle\min_{\lambda\in\mathcal{U}}\mathscr{R}^{\lambda}(S)=\left[\begin{aligned}
&\;\underset{\lambda}{\textnormal{minimize}}&&\sum_{i_{1}\in S_{1}\setminus
S_{2}}\sum_{i_{2}\in S_{1}\cap
S_{2}}\rho_{i_{1}i_{2}}(S)\lambda_{i_{1}i_{2}}+\sum_{i_{1}\in S_{1}\setminus
S_{2}}\sum_{i_{2}\in S_{2}\setminus
S_{1}}\rho_{i_{1}i_{2}}(S)\lambda_{i_{1}i_{2}}\\\ &&&+\sum_{i_{1}\in S_{1}\cap
S_{2}}\sum_{i_{2}\in S_{2}\setminus
S_{1}}\rho_{i_{1}i_{2}}(S)\lambda_{i_{1}i_{2}}+\sum_{i\in S_{1}\cap
S_{2}}\rho_{ii}(S)\lambda_{ii}\\\ &\textnormal{subject to}&&\begin{aligned}
&\sum_{i_{2}\in S_{2}}\lambda_{i_{1}i_{2}}=v_{1,i_{1}}&&\forall i_{1}\in
S_{1}\setminus S_{2}\\\ &\sum_{i_{1}\in
S_{1}}\lambda_{i_{1}i_{2}}=v_{2,i_{2}}&&\forall i_{2}\in S_{2}\setminus
S_{1}\\\ &\lambda_{ii}+\sum_{i_{2}\in S_{2}\setminus
S_{1}}\lambda_{ii_{2}}=v_{1,i}&&\forall i\in S_{1}\cap S_{2}\\\
&\lambda_{ii}+\sum_{i_{1}\in S_{1}\setminus
S_{2}}\lambda_{i_{1}i}=v_{2,i}&&\forall i\in S_{1}\cap S_{2}\\\
&\lambda_{i_{1}i_{2}}\geq
0&&\forall(i_{1},i_{2})\in\mathcal{L}\end{aligned}\end{aligned}\right].$

Finally, for each $i\in S_{1}\cap S_{2}$, we eliminate the decision variable
$\lambda_{ii}$ from the above optimization problem by using the equality
$\lambda_{ii}=v_{1,i}-\sum_{i_{2}\in S_{2}\setminus S_{1}}\lambda_{ii_{2}}$.
With this elimination, we obtain the desired result.

###  10.4 Proof of Theorem 4.3

We first 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)$. 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.

We now analyze the running time of our algorithm by using our three
intermediary results. We assume that the two assortments $S_{1}$ and $S_{2}$
are given as sorted arrays. Under this assumption, it is straightforward to
see that the sets $S_{1}\cap S_{2}$, $S_{1}\setminus S_{2}$, and
$S_{2}\setminus S_{1}$ can be computed and stored as sorted arrays in
$\mathcal{O}(n)$ computation time. We also require $\mathcal{O}(n)$
computation time to store copies of the sets $S_{1},S_{2},S_{1}\cap S_{2}$,
$S_{1}\setminus S_{2}$, and $S_{2}\setminus S_{1}$ in hash tables, which
ensures that querying whether a given product is an element of any of these
sets can be performed in $\mathcal{O}(1)$ time.

We next analyze the computation times for constructing the collection of
assortments $\widehat{\mathcal{S}}$, constructing the set of pairs of products
$\mathcal{L}$, and computing the quantities $\rho_{i_{1}i_{2}}(S)$ for each
assortment $S\in\widehat{\mathcal{S}}$ and each pair of products
$(i_{1},i_{2})\in\mathcal{L}$. Indeed, using the aforementioned data
structures, it follows readily from Lemma 4.4 that we can construct the
collection of assortments $\widehat{\mathcal{S}}$ in $\mathcal{O}(n^{3})$
computation time.131313It follows from Lemma 4.4 that we can efficiently
iterate over the assortments in $\widehat{\mathcal{S}}$ by iterating over the
pairs of products in $(S_{1}\setminus S_{2})\cup\\{n\\}$ and $(S_{2}\setminus
S_{1})\cup\\{n\\}$. Constructing the collection $\widehat{\mathcal{S}}$ thus
requires iterating over the $(|S_{1}\setminus S_{2}|+1)\times(|S_{2}\setminus
S_{1}|+1)=\mathcal{O}(n^{2})$ assortments, and each of the assortments is
comprised of at most $\mathcal{O}(n)$ products.  Moreover, it follows from
Lemma 4.5 that the set of pairs of products $\mathcal{L}$ can be computed in
$\mathcal{O}(n^{2})$ time. Finally, we analyze the computation times for
computing the quantities $\rho_{i_{1}i_{2}}(S)$ for each assortment
$S\in\widehat{\mathcal{S}}$ and each pair of products
$(i_{1},i_{2})\in\mathcal{L}$. Indeed, we recall from Lemma 4.4 that
$|\widehat{\mathcal{S}}|=\mathcal{O}(n^{2})$, and we recall from Lemma 4.5
that $|\mathcal{L}|=\mathcal{O}(n^{2})$. Therefore, there are
$|\widehat{\mathcal{S}}|\times|\mathcal{L}|=\mathcal{O}(n^{4})$ different ways
of choosing an assortment $S\in\widehat{\mathcal{S}}$ and a pair of products
$(i_{1},i_{2})\in\mathcal{L}$. For each assortment $S\in{\mathcal{S}}$ and
pair of products $(i_{1},i_{2})\in\mathcal{L}$, it follows readily from
Definition 3.4 and Lemmas 4.4 and 4.5 that

$\displaystyle\rho_{i_{1}i_{2}}(S)$
$\displaystyle=\begin{cases}r_{i_{1}},&\text{if
}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}i_{1},i_{2}\in
S_{1}\cap S_{2}},\;i_{1}=i_{2},\textnormal{ and }i_{1}\in S,\\\ 0,&\text{if
}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}i_{1},i_{2}\in
S_{1}\cap S_{2}},\;i_{1}=i_{2},\textnormal{ and }i_{1}\notin S,\\\
\\\\[-5.0pt] r_{i_{2}},&\text{if
}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}i_{1}\in
S_{1}\cap S_{2},\;i_{2}\in S_{2}\setminus S_{1}},\textnormal{ and }i_{2}\in
S,\\\ \min\left\\{r_{i_{1}},\min_{j\in S\cap S_{2}\setminus
S_{1}}r_{j}\right\\},&\text{if
}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}i_{1}\in
S_{1}\cap S_{2},\;i_{2}\in S_{2}\setminus S_{1}},\;i_{2}\notin S,\textnormal{
and }i_{1}\in S,\\\ 0,&\text{if
}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}i_{1}\in
S_{1}\cap S_{2},\;i_{2}\in S_{2}\setminus S_{1}},\;i_{2}\notin S,\textnormal{
and }i_{1}\notin S,\\\ \\\\[-5.0pt] r_{i_{1}},&\text{if
}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}i_{1}\in
S_{1}\setminus S_{2},\;i_{2}\in S_{1}\cap S_{2}},\textnormal{ and }i_{1}\in
S,\\\ \min\left\\{r_{i_{2}},\min_{j\in S\cap S_{1}\setminus
S_{2}}r_{j}\right\\},&\text{if
}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}i_{1}\in
S_{1}\setminus S_{2},\;i_{2}\in S_{1}\cap S_{2}},\;i_{1}\notin S,\textnormal{
and }i_{2}\in S,\\\ 0,&\text{if
}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}i_{1}\in
S_{1}\setminus S_{2},\;i_{2}\in S_{1}\cap S_{2}},\;i_{1}\notin S,\textnormal{
and }i_{2}\notin S,\\\ \\\\[-5.0pt]
\min\left\\{r_{i_{1}},r_{i_{2}}\right\\},&\text{if
}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}i_{1}\in
S_{1}\setminus S_{2},\;i_{2}\in S_{2}\setminus S_{1}},\;i_{1}\in S,\text{ and
}i_{2}\in S,\\\ \min\left\\{r_{i_{1}},\min_{j\in S\cap S_{2}\setminus
S_{1}}r_{j}\right\\},&\text{if
}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}i_{1}\in
S_{1}\setminus S_{2},\;i_{2}\in S_{2}\setminus S_{1}},\;i_{1}\in S,\text{ and
}i_{2}\notin S,\\\ \min\left\\{r_{i_{2}},\min_{j\in S\cap S_{1}\setminus
S_{2}}r_{j}\right\\},&\text{if
}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}i_{1}\in
S_{1}\setminus S_{2},\;i_{2}\in S_{2}\setminus S_{1}},\;i_{1}\notin S,\text{
and }i_{2}\in S,\\\ 0,&\text{if
}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}i_{1}\in
S_{1}\setminus S_{2},\;i_{2}\in S_{2}\setminus S_{1}},\;i_{1}\notin S,\text{
and }i_{2}\notin S.\end{cases}$

We observe that the quantities $\min_{j\in S\cap S_{1}\setminus S_{2}}r_{j}$
and $\min_{j\in S\cap S_{2}\setminus S_{1}}r_{j}$ appear in many of the above
cases, and we see that these quantities can be precomputed for each of the
assortments $S\in\widehat{\mathcal{S}}$ in a total of
$|\widehat{\mathcal{S}}|\times\mathcal{O}(n)=\mathcal{O}(n^{3})$ computation
time. Given that we have precomputed these quantities, and given the fact that
our data structures allow us to query whether any product is an element of the
sets $S_{1}\setminus S_{2}$, $S_{2}\setminus S_{1}$, and $S_{1}\cap S_{2}$ in
$\mathcal{O}(1)$ time, we conclude that all of the $\rho_{i_{1}i_{2}}(S)$ can
be computed in a total of $\mathcal{O}(n^{4}+n^{3})=\mathcal{O}(n^{4})$ time.
In summary, we have established that constructing the collection of
assortments $\widehat{\mathcal{S}}$, constructing the set of pairs of products
$\mathcal{L}$, and computing the quantities $\rho_{i_{1}i_{2}}(S)$ for each
assortment $S\in\widehat{\mathcal{S}}$ and each pair of products
$(i_{1},i_{2})\in\mathcal{L}$ can be performed in a total of
$\mathcal{O}(n^{4})$ computation time.

We conclude our proof of Theorem 4.3 by establishing the total computation
time of our brute-force algorithm using the information computed above. In
each iteration of our algorithm, we select an assortment
$S\in\widehat{\mathcal{S}}$ and compute the worst-case expected revenue
$\min_{\lambda\in\mathcal{U}}\mathscr{R}^{\lambda}(S)$. As shown in Lemma 4.6,
we can compute $\min_{\lambda\in\mathcal{U}}\mathscr{R}^{\lambda}(S)$ by
solving a minimum-cost network flow problem over a graph with $n+1$ vertices
and $\mathcal{O}(n^{2})$ edges. Using the minimum-cost network flow algorithm
of Orlin (1997) and Tarjan (1997), we observe that Problem (13) can be solved
in $\mathcal{O}(n^{3}\log(nr_{n}))$ computation time.141414The algorithm of
Orlin (1997) and Tarjan (1997) computes the minimum-cost network flow on a
directed graph in $\mathcal{O}((VE\log V)\min\left\\{\log(VC),E\log
V\right\\})$ running time, where $V$ is the number of vertices, $E$ is the
number of directed edges, and $C$ is the maximum absolute value of any edge
cost. The algorithm requires that $C$ is integral; for more details, see
Tarjan (1997, §3). In our case, Problem (13) is a minimum-cost network flow
problem in a directed graph where $V=n$, $E=\mathcal{O}(n^{2})$, and
$C=\max_{S\in\widehat{\mathcal{S}},(i_{1},i_{2})\in\mathcal{L}}\rho_{i_{1}i_{2}}(S)=r_{n}$.
Since the worst-case expected revenue
$\min_{\lambda\in\mathcal{U}}\mathscr{R}^{\lambda}(S)$ must be computed for
each assortment $S\in\widehat{\mathcal{S}}$, and since it follows readily from
Lemma 4.4 that $|\widehat{\mathcal{S}}|=\mathcal{O}(n^{2})$, we conclude that
our algorithm requires a total of $\mathcal{O}(n^{5}\log(nr_{n}))$ computation
time.

##  11 In-Depth Analysis of a Specific Problem Instance

In this section, we conduct an in-depth analysis of a specific problem
instance with two previously-offered assortments. Our goal here is to show
that there exist problem instances which can have affirmative answers to the
identification question, the unique assortments which answer the
identification question for the problem instances are not revenue-ordered
assortments, and the estimate-then-optimize technique can yield new
assortments for the problem instances with expected revenues that are strictly
less than the best expected revenues obtained from the firm’s previously-
offered assortments.

###  11.1 Description of Problem Instance

We begin by defining the specific problem instance that will be our focus
throughout this section. The problem instance is comprised of two previously-
offered assortments, which are denoted by $S_{1}=\\{0,2,3,4\\}$ and
$S_{2}=\\{0,1,2,4\\}$. The revenues corresponding to the four products are
$r_{1}=\$10$, $r_{2}=\$20$, $r_{3}=\$30$, and $r_{4}=\$100$. The historical
sales data for the two previously-offered assortments are the purchase
frequencies $(v_{1,0},v_{1,2},v_{1,3},v_{1,4})=(0.3,0.3,0.3,0.1)$ and
$(v_{2,0},v_{2,1},v_{2,2},v_{2,4})=(0.3,0.3,0.1,0.3)$. In the remainder of
this section, we will investigate the identification question for this problem
instance in the case of $\eta=0$.

###  11.2 Useful Facts for Problem Instance

To facilitate our analysis throughout this section, we next develop some
useful facts about the problem instance defined in §11.1. Indeed, we first
observe that the expected revenues associated with the two previously-offered
assortments $S_{1}=\\{0,2,3,4\\}$ and $S_{2}=\\{0,1,2,4\\}$ are

$\displaystyle r^{\intercal}v_{1}$ $\displaystyle=\$0\times 0.3+\$20\times
0.3+\$30\times 0.3+\$100\times 0.1=\$25,$ $\displaystyle r^{\intercal}v_{2}$
$\displaystyle=\$0\times 0.3+\$10\times 0.3+\$20\times 0.1+\$100\times
0.3=\$35.$

Hence, the best expected revenue from a previously-offered assortment is
$\max\\{\$25,\$35\\}=\$35$.

We next show that the set of ranking-based choice models $\mathcal{U}$ is
nonempty when the radius is $\eta=0$. To show this, we will construct a
ranking-based choice model $\lambda$ that has perfect accuracy on the
historical sales data. Specifically, consider the following five rankings:

$\displaystyle\sigma^{1}(0)$ $\displaystyle=0,$ $\displaystyle\sigma^{2}(1)$
$\displaystyle=0,$ $\displaystyle\sigma^{3}(1)$ $\displaystyle=0,$
$\displaystyle\sigma^{4}(2)$ $\displaystyle=0,$ $\displaystyle\sigma^{5}(3)$
$\displaystyle=0,$ $\displaystyle\sigma^{1}(\phantom{0})$ $\displaystyle=1,$
$\displaystyle\sigma^{2}(2)$ $\displaystyle=1,$ $\displaystyle\sigma^{3}(4)$
$\displaystyle=1,$ $\displaystyle\sigma^{4}(4)$ $\displaystyle=1,$
$\displaystyle\sigma^{5}(4)$ $\displaystyle=1,$
$\displaystyle\sigma^{1}(\phantom{0})$ $\displaystyle=2,$
$\displaystyle\sigma^{2}(4)$ $\displaystyle=2,$ $\displaystyle\sigma^{3}(0)$
$\displaystyle=2,$ $\displaystyle\sigma^{4}(0)$ $\displaystyle=2,$
$\displaystyle\sigma^{5}(0)$ $\displaystyle=2,$
$\displaystyle\sigma^{1}(\phantom{0})$ $\displaystyle=3,$
$\displaystyle\sigma^{2}(0)$ $\displaystyle=3,$
$\displaystyle\sigma^{3}(\phantom{0})$ $\displaystyle=3,$
$\displaystyle\sigma^{4}(\phantom{0})$ $\displaystyle=3,$
$\displaystyle\sigma^{5}(\phantom{0})$ $\displaystyle=3,$
$\displaystyle\sigma^{1}(\phantom{0})$ $\displaystyle=4,$
$\displaystyle\sigma^{2}(\phantom{0})$ $\displaystyle=4,$
$\displaystyle\sigma^{3}(\phantom{0})$ $\displaystyle=4,$
$\displaystyle\sigma^{4}(\phantom{0})$ $\displaystyle=4,$
$\displaystyle\sigma^{5}(\phantom{0})$ $\displaystyle=4.$

Indeed, we recall from §2 that a ranking $\sigma\in\Sigma$ prefers product
$i\in\mathcal{N}_{0}$ over product $j\in\mathcal{N}_{0}$ if
$\sigma(i)<\sigma(j)$. For the sake of simplicity, we have chosen without loss
of generality to not specify the preference ordering among products which are
less preferred than the no-purchase option in each ranking. We observe that
the most preferred products from the previously-offered assortments
$S_{1}=\\{0,2,3,4\\}$ and $S_{2}=\\{0,1,2,4\\}$ under each of the five
rankings are

$\displaystyle\argmin_{j\in S_{1}}\sigma^{1}(j)$ $\displaystyle=0,$
$\displaystyle\argmin_{j\in S_{1}}\sigma^{2}(j)$ $\displaystyle=2,$
$\displaystyle\argmin_{j\in S_{1}}\sigma^{3}(j)$ $\displaystyle=4,$
$\displaystyle\argmin_{j\in S_{1}}\sigma^{4}(j)$ $\displaystyle=2,$
$\displaystyle\argmin_{j\in S_{1}}\sigma^{5}(j)$ $\displaystyle=3,$
$\displaystyle\argmin_{j\in S_{2}}\sigma^{1}(j)$ $\displaystyle=0,$
$\displaystyle\argmin_{j\in S_{2}}\sigma^{2}(j)$ $\displaystyle=1,$
$\displaystyle\argmin_{j\in S_{2}}\sigma^{3}(j)$ $\displaystyle=1,$
$\displaystyle\argmin_{j\in S_{2}}\sigma^{4}(j)$ $\displaystyle=2,$
$\displaystyle\argmin_{j\in S_{2}}\sigma^{5}(j)$ $\displaystyle=4.$

It follows from the above observations that the historical sales data
$(v_{1,0},v_{1,2},v_{1,3},v_{1,4})=(0.3,0.3,0.3,0.1)$ and
$(v_{2,0},v_{2,1},v_{2,2},v_{2,4})=(0.3,0.3,0.1,0.3)$ are fit perfectly by the
ranking-based choice model $\hat{\lambda}\in\Delta_{\Sigma}$ which satisfies
the following equalities:

$\displaystyle\hat{\lambda}_{\sigma^{1}}$ $\displaystyle=0.3,$
$\displaystyle\hat{\lambda}_{\sigma^{2}}$ $\displaystyle=0.2,$
$\displaystyle\hat{\lambda}_{\sigma^{3}}$ $\displaystyle=0.1,$
$\displaystyle\hat{\lambda}_{\sigma^{4}}$ $\displaystyle=0.1,$
$\displaystyle\hat{\lambda}_{\sigma^{5}}$ $\displaystyle=0.3.$

###  11.3 Analysis of Estimate-Then-Optimize for Problem Instance

Equipped with the useful facts from §11.2, we now consider the performance of
the estimate-then-optimize technique for the problem instance defined in
§11.1. Specifically, suppose we use the estimate-then-optimize technique in
which our estimate of the ranking-based choice model is defined by the
probability distribution $\hat{\lambda}$ defined in §11.2. In that case, the
estimate-then-optimize technique will output a new assortment
$S^{\hat{\lambda}}$ which is an optimal solution to the following
combinatorial optimization problem:

$\displaystyle\begin{aligned}
&\underset{S\in\mathcal{S}}{\textnormal{maximize}}&&\mathscr{R}^{\hat{\lambda}}(S).\end{aligned}$

To determine the optimal solution to the above combinatorial optimization
problem, let us inspect the five rankings $\sigma^{1},\ldots,\sigma^{5}$ which
have nonzero probability under the estimated probability distribution. It is
easy to see that the first of these five rankings satisfies the equality
$\argmin_{j\in S}\sigma^{1}(j)=0$ for all assortments $S\in\mathcal{S}$.
Moreover, we observe that the assortment $\\{0,4\\}\in\mathcal{S}$ satisfies
the equalities
$\argmin_{j\in\\{0,4\\}}\sigma^{2}(j)=\cdots=\argmin_{j\in\\{0,4\\}}\sigma^{5}(j)=4$.
From this reasoning, we conclude that $\\{0,4\\}$ is an optimal assortment to
the above combinatorial optimization problem, and the predicted expected
revenue for this assortment is
$\mathscr{R}^{\hat{\lambda}}(S^{\hat{\lambda}})=\mathscr{R}^{\hat{\lambda}}(\\{0,4\\})=0.7\times\$100=\$70$.

We will now show that the assortment $S^{\hat{\lambda}}=\\{0,4\\}$ obtained
from estimate-then-optimize can have an expected revenue that is strictly
lower than the best expected revenue obtained from a previously-offered
assortment under a ranking-based choice model that is consistent with the
historical sales data. To show this, we consider the following seven rankings:

$\displaystyle\sigma^{6}(0)$ $\displaystyle=0,$ $\displaystyle\sigma^{7}(1)$
$\displaystyle=0,$ $\displaystyle\sigma^{8}(2)$ $\displaystyle=0,$
$\displaystyle\sigma^{9}(3)$ $\displaystyle=0,$ $\displaystyle\sigma^{10}(4)$
$\displaystyle=0,$ $\displaystyle\sigma^{11}(1)$ $\displaystyle=0,$
$\displaystyle\sigma^{12}(3)$ $\displaystyle=0,$
$\displaystyle\sigma^{6}(\phantom{0})$ $\displaystyle=1,$
$\displaystyle\sigma^{7}(0)$ $\displaystyle=1,$ $\displaystyle\sigma^{8}(0)$
$\displaystyle=1,$ $\displaystyle\sigma^{9}(0)$ $\displaystyle=1,$
$\displaystyle\sigma^{10}(0)$ $\displaystyle=1,$ $\displaystyle\sigma^{11}(2)$
$\displaystyle=1,$ $\displaystyle\sigma^{12}(4)$ $\displaystyle=1,$
$\displaystyle\sigma^{6}(\phantom{0})$ $\displaystyle=2,$
$\displaystyle\sigma^{7}(\phantom{0})$ $\displaystyle=2,$
$\displaystyle\sigma^{8}(\phantom{0})$ $\displaystyle=2,$
$\displaystyle\sigma^{9}(\phantom{0})$ $\displaystyle=2,$
$\displaystyle\sigma^{10}(\phantom{0})$ $\displaystyle=2,$
$\displaystyle\sigma^{11}(0)$ $\displaystyle=2,$ $\displaystyle\sigma^{12}(0)$
$\displaystyle=2,$ $\displaystyle\sigma^{6}(\phantom{0})$ $\displaystyle=3,$
$\displaystyle\sigma^{7}(\phantom{0})$ $\displaystyle=3,$
$\displaystyle\sigma^{8}(\phantom{0})$ $\displaystyle=3,$
$\displaystyle\sigma^{9}(\phantom{0})$ $\displaystyle=3,$
$\displaystyle\sigma^{10}(\phantom{0})$ $\displaystyle=3,$
$\displaystyle\sigma^{11}(\phantom{0})$ $\displaystyle=3,$
$\displaystyle\sigma^{12}(\phantom{0})$ $\displaystyle=3,$
$\displaystyle\sigma^{6}(\phantom{0})$ $\displaystyle=4,$
$\displaystyle\sigma^{7}(\phantom{0})$ $\displaystyle=4,$
$\displaystyle\sigma^{8}(\phantom{0})$ $\displaystyle=4,$
$\displaystyle\sigma^{9}(\phantom{0})$ $\displaystyle=4,$
$\displaystyle\sigma^{10}(\phantom{0})$ $\displaystyle=4,$
$\displaystyle\sigma^{11}(\phantom{0})$ $\displaystyle=4,$
$\displaystyle\sigma^{12}(\phantom{0})$ $\displaystyle=4.$

We observe that the most preferred products from the first previously-offered
assortment $S_{1}=\\{0,2,3,4\\}$ are

$\displaystyle\argmin_{j\in S_{1}}\sigma^{6}(j)=0,\quad\argmin_{j\in
S_{1}}\sigma^{7}(j)=0,\quad\argmin_{j\in
S_{1}}\sigma^{8}(j)=2,\quad\argmin_{j\in
S_{1}}\sigma^{9}(j)=3,\quad\argmin_{j\in S_{1}}\sigma^{10}(j)=4,$
$\displaystyle\argmin_{j\in S_{1}}\sigma^{11}(j)=2,\quad\argmin_{j\in
S_{1}}\sigma^{12}(j)=3,$

the most preferred products from the second previously-offered assortment
$S_{2}=\\{0,1,2,4\\}$ are

$\displaystyle\argmin_{j\in S_{2}}\sigma^{6}(j)=0,\quad\argmin_{j\in
S_{2}}\sigma^{7}(j)=1,\quad\argmin_{j\in
S_{2}}\sigma^{8}(j)=2,\quad\argmin_{j\in
S_{2}}\sigma^{9}(j)=0,\quad\argmin_{j\in S_{2}}\sigma^{10}(j)=4,$
$\displaystyle\argmin_{j\in S_{2}}\sigma^{11}(j)=1,\quad\argmin_{j\in
S_{2}}\sigma^{12}(j)=4,$

and the most preferred products from the new assortment
$S^{\hat{\lambda}}=\\{0,4\\}$ from estimate-then-optimize are

$\displaystyle\argmin_{j\in
S^{\hat{\lambda}}}\sigma^{6}(j)=0,\quad\argmin_{j\in
S^{\hat{\lambda}}}\sigma^{7}(j)=0,\quad\argmin_{j\in
S^{\hat{\lambda}}}\sigma^{8}(j)=0,\quad\argmin_{j\in
S^{\hat{\lambda}}}\sigma^{9}(j)=0,\quad\argmin_{j\in
S^{\hat{\lambda}}}\sigma^{10}(j)=4,$ $\displaystyle\argmin_{j\in
S^{\hat{\lambda}}}\sigma^{11}(j)=0,\quad\argmin_{j\in
S^{\hat{\lambda}}}\sigma^{12}(j)=4.$

It follows from the above observations that the historical sales data
$(v_{1,0},v_{1,2},v_{1,3},v_{1,4})=(0.3,0.3,0.3,0.1)$ and
$(v_{2,0},v_{2,1},v_{2,2},v_{2,4})=(0.3,0.3,0.1,0.3)$ are fit perfectly by the
ranking-based choice model $\bar{\lambda}\in\Delta_{\Sigma}$ which satisfies
the following equalities:

$\displaystyle\bar{\lambda}_{\sigma^{6}}$ $\displaystyle=0.2,$
$\displaystyle\bar{\lambda}_{\sigma^{7}}$ $\displaystyle=0.1,$
$\displaystyle\bar{\lambda}_{\sigma^{8}}$ $\displaystyle=0.1,$
$\displaystyle\bar{\lambda}_{\sigma^{9}}$ $\displaystyle=0.1,$
$\displaystyle\bar{\lambda}_{\sigma^{10}}$ $\displaystyle=0.1,$
$\displaystyle\bar{\lambda}_{\sigma^{11}}$ $\displaystyle=0.2,$
$\displaystyle\bar{\lambda}_{\sigma^{12}}$ $\displaystyle=0.2.$

However, we observe that the expected revenue for the assortment
$S^{\hat{\lambda}}$ under the ranking-based choice model with parameters
$\bar{\lambda}$ is
$\mathscr{R}^{\bar{\lambda}}(S^{\hat{\lambda}})=\mathscr{R}^{\bar{\lambda}}(\\{0,4\\})=0.3\times\$100=\$30$.
Since this is strictly less than the best expected revenue from a previously-
offered assortment, $\$35$, we have thus shown that the estimate-then-optimize
technique can yield an assortment for the problem instance defined in §11.1
with an expected revenue that is strictly worse than the best expected revenue
obtained from a previously-offered assortment under a ranking-based choice
model that is consistent with the historical sales data.

###  11.4 Affirmative Answer to Identification Question for Problem Instance

We next show that there are affirmative answers to the identification question
for the problem instance defined in §11.1. From this point forward, our
analysis will closely follow the algorithm for answering the identification
question which was developed in §4.2.1. We begin by constructing the
collection of assortments $\widehat{\mathcal{S}}$ corresponding to the
previously-offered assortments $S_{1}=\\{0,2,3,4\\}$ and
$S_{2}=\\{0,1,2,4\\}$. Indeed, we observe that $S_{1}\cap S_{2}=\\{0,2,4\\}$,
$S_{1}\setminus S_{2}=\\{3\\}$, and $S_{2}\setminus S_{1}=\\{1\\}$, and so it
follows from Lemma 4.4 that

$\displaystyle\widehat{\mathcal{S}}$
$\displaystyle=\left\\{S\in\mathcal{S}:\quad\begin{aligned} &\textnormal{there
exists }i_{1}\in\\{3,4\\}\textnormal{ and }i_{2}\in\\{1,4\\}\textnormal{ such
that}\\\ &S=\\{0,2,4\\}\cup\left\\{j\in\\{3\\}:j\geq
i_{1}\right\\}\cup\left\\{j\in\\{1\\}:j\geq
i_{2}\right\\}\end{aligned}\right\\}=\left\\{\begin{gathered}\\{0,1,2,3,4\\},\\\
\\{0,1,2,4\\},\\\ \\{0,2,3,4\\},\\\ \\{0,2,4\\}\end{gathered}\right\\}.$

Under the assumption that $\eta=0$ from §11.1, it follows from our
implementation of the algorithm from §4.2.1 that

$\displaystyle\begin{aligned}
&\min_{\lambda\in\mathcal{U}}\mathscr{R}^{\lambda}\left(\\{0,1,2,3,4\\}\right)&=\$14,\\\
&\min_{\lambda\in\mathcal{U}}\mathscr{R}^{\lambda}\left(\\{0,1,2,4\\}\right)&=\$35,\\\
&\min_{\lambda\in\mathcal{U}}\mathscr{R}^{\lambda}\left(\\{0,2,3,4\\}\right)&=\$25,\\\
&\min_{\lambda\in\mathcal{U}}\mathscr{R}^{\lambda}\left(\\{0,2,4\\}\right)&=\$36.\end{aligned}$

Hence, we observe that there is an affirmative answer to the identification
question associated with the assortment $\\{0,2,4\\}$, since this assortment
satisfies $\mathscr{R}^{\lambda}(\\{0,2,4\\})\geq\$36>\$35$ for all ranking-
based choice models $\lambda\in\mathcal{U}$. In particular, we note that
$\\{0,2,4\\}$ is not a revenue-ordered assortment. We remark that the
correctness of the above equalities
$\min_{\lambda\in\mathcal{U}}\mathscr{R}^{\lambda}\left(\\{0,1,2,4\\}\right)=\$35$
and
$\min_{\lambda\in\mathcal{U}}\mathscr{R}^{\lambda}\left(\\{0,2,3,4\\}\right)=\$25$
for the two previously-offered assortments follows immediately from the fact
that $\eta=0$, which implies that $\mathscr{D}^{\lambda}(S_{m})=v_{m}$ for all
$m\in\\{1,2\\}$ and all $\lambda\in\mathcal{U}$.

We conclude this section by showing that $\\{0,2,4\\}$ is the unique
assortment that answers the identification question for our specific problem
instance. To show this, we present below an exhaustive list of the worst-case
expected revenues $\min_{\lambda\in\mathcal{U}}\mathscr{R}^{\lambda}(S)$ for
all assortments $S\in\mathcal{S}$ which satisfy $4\in S$. We compute the
following list by using our implementation of the algorithm from §4.2.1. The
following list shows that $\\{0,2,4\\}$ is the unique assortment which leads
to an affirmative answer to the identification question for our specific
problem instance.

$\displaystyle\begin{aligned}
&\min_{\lambda\in\mathcal{U}}\mathscr{R}^{\lambda}\left(\\{0,4\\}\right)&=\$30,\\\
&\min_{\lambda\in\mathcal{U}}\mathscr{R}^{\lambda}\left(\\{0,1,4\\}\right)&=\$33,\\\
&\min_{\lambda\in\mathcal{U}}\mathscr{R}^{\lambda}\left(\\{0,2,4\\}\right)&=\$36,\\\
&\min_{\lambda\in\mathcal{U}}\mathscr{R}^{\lambda}\left(\\{0,3,4\\}\right)&=\$19,\\\
&\min_{\lambda\in\mathcal{U}}\mathscr{R}^{\lambda}\left(\\{0,1,2,4\\}\right)&=\$35,\\\
&\min_{\lambda\in\mathcal{U}}\mathscr{R}^{\lambda}\left(\\{0,1,3,4\\}\right)&=\$12,\\\
&\min_{\lambda\in\mathcal{U}}\mathscr{R}^{\lambda}\left(\\{0,2,3,4\\}\right)&=\$25,\\\
&\min_{\lambda\in\mathcal{U}}\mathscr{R}^{\lambda}\left(\\{0,1,2,3,4\\}\right)&=\$14.\end{aligned}$

##  12 Proofs of Intermediary Technical Results from §4.3

###  12.1 Proof of Lemma 4.8

As the first step in our proof of Lemma 4.8, we develop an algorithm for
constructing a directed graph, denoted by
$\mathscr{G}\equiv(\mathscr{V},\mathscr{E})$, in which the set of vertices in
the directed graph is defined as $\mathscr{V}\triangleq\mathcal{N}_{0}$ and
the set of directed edges is defined as
$\mathscr{E}\triangleq\\{(i^{*},i)\in\mathcal{N}_{0}\times\mathcal{N}_{0}:\;r_{i^{*}}<r_{i}\textnormal{
and }\mathcal{M}_{i^{*}}\subseteq\mathcal{M}_{i}\\}$. This directed graph has
a natural correspondence with the collection of assortments
$\widehat{\mathcal{S}}$, as we readily observe that an assortment satisfies
$S\in\widehat{\mathcal{S}}$ if and only if [$0\in S$] and [we have that $i\in
S$ whenever there exists a product $i^{*}\in S$ and a directed edge
$(i^{*},i)\in\mathscr{E}$]. It is easy to see that this directed graph is
acyclic and has the property that a vertex $j\in\mathscr{V}$ is reachable from
a vertex $i\in\mathscr{V}$ if and only if there is a directed edge
$(i,j)\in\mathscr{E}$ from vertex $i$ to vertex $j$. A directed acyclic graph
which has the aforementioned property for each pair of vertices is referred to
as a _transitive closure_ (Ahuja et al. 1988, p.90).

Our algorithm for constructing the directed acyclic graph $\mathscr{G}$ that
is a transitive closure is presented in Algorithm 1. In the algorithm, we
first iterate over each product $i\in\mathcal{N}_{0}$ and construct the
corresponding set $\mathcal{M}_{i}$ of previously-offered assortments which
offered that product. It is easy to see that each of the sets
$\mathcal{M}_{i}$ can be constructed in $\mathcal{O}(M)$ computation time by
checking whether the product satisfies $i\in S_{m}$ for each previously-
offered assortment $m\in\mathcal{M}$; hence, we observe that all of the sets
$\mathcal{M}_{0},\ldots,\mathcal{M}_{n}$ can be constructed in a total of
$\mathcal{O}(Mn)$ computation time. Assume that we store the sets
$\mathcal{M}_{0},\ldots,\mathcal{M}_{n}$ as unsorted arrays as well as hash
tables. Given these data structures for
$\mathcal{M}_{0},\ldots,\mathcal{M}_{n}$, we then iterate over each pair of
products $(i,i^{*})\in\mathcal{N}_{0}\times\mathcal{N}_{0}$ and check in
$\mathcal{O}(M)$ computation time whether $r_{i^{*}}<r_{i}$ and
$\mathcal{M}_{i^{*}}\subseteq\mathcal{M}_{i}$. Since there are
$\mathcal{O}(n^{2})$ pairs of products in
$\mathcal{N}_{0}\times\mathcal{N}_{0}$, we conclude that the set of directed
edges $\mathscr{E}$ can be constructed in a total of $\mathcal{O}(n^{2}M)$
computation time. Combining all of the steps, and since it takes
$\mathcal{O}(n)$ computation time to construct the set of vertices
$\mathscr{V}$, we have shown that the total computation time for Algorithm 1
is $\mathcal{O}(n+Mn+n^{2}M)=\mathcal{O}(n^{2}M)$.

Construct-${\mathscr{G}}(\mathscr{M},r)$ Inputs: • The collection of
previously-offered assortments, $\mathscr{M}\equiv\\{S_{1},\ldots,S_{M}\\}$. •
The revenues of the products, $r\equiv(r_{0},r_{1},\ldots,r_{n})$. Output: •
$\mathscr{G}\equiv(\mathscr{V},\mathscr{E})$, where
$\mathscr{V}\equiv\mathcal{N}_{0}$ and
$\mathscr{E}\equiv\\{(i^{*},i)\in\mathcal{N}_{0}\times\mathcal{N}_{0}:\;r_{i^{*}}<r_{i}\textnormal{
and }\mathcal{M}_{i^{*}}\subseteq\mathcal{M}_{i}\\}$. Procedure: 1. Initialize
the vertex set $\mathscr{V}\leftarrow\emptyset$ and edge set
$\mathscr{E}\leftarrow\emptyset$. 2. For each product $i\in\mathcal{N}_{0}$:
(a) Update $\mathscr{V}\leftarrow\mathscr{V}\cup\\{i\\}$. (b) Construct the
set $\mathcal{M}_{i}$ of previously-offered assortments which offered product
$i$. 3. For each pair of products
$(i^{*},i)\in\mathcal{N}_{0}\times\mathcal{N}_{0}$: (a) If $r_{i^{*}}<r_{i}$
and $\mathcal{M}_{i^{*}}\subseteq\mathcal{M}_{i}$: i. Update
$\mathscr{E}\leftarrow\mathscr{E}\cup\\{(i^{*},i)\\}$ 4. Output
$\mathscr{G}\equiv(\mathscr{V},\mathscr{E})$ and terminate.

Algorithm 1:  A procedure for constructing the directed acyclic graph
$\mathscr{G}$.

We next describe our algorithm for constructing the collection of assortments
$\widehat{\mathcal{S}}$ from the directed graph $\mathscr{G}$. This algorithm
is denoted by Construct-$\widehat{\mathcal{S}}(\mathscr{M},r)$ and is found in
Algorithm 2. In this algorithm, we first use Algorithm 1 to construct the
directed acyclic graph $\mathscr{G}\equiv(\mathscr{V},\mathscr{E})$ which is a
transitive closure, and then we invoke a recursive subroutine denoted by
RecursiveStep$(\mathscr{G})$ in Algorithm 3. The goal of the recursive
subroutine is to take as an input a generic directed acyclic graph
$\mathcal{G}\equiv(\mathcal{V},\mathcal{E})$ which is a transitive closure,
and for that graph, output the collection of subsets of vertices
$\mathcal{A}\equiv\\{S\subseteq\mathcal{V}:\text{ if $i\in S$ and
$(i,j)\in\mathcal{E}$, then $j\in S$}\\}$. Algorithm 2 concludes by removing
the subsets of vertices from $\mathcal{A}$ which do not include the no-
purchase option $0$, and then outputs the remaining subsets of vertices from
$\mathcal{A}$. The correctness of Algorithm 2 follows immediately from our
earlier observation that an assortment satisfies $S\in\widehat{\mathcal{S}}$
if and only if [$0\in S$] and [we have that $i\in S$ whenever there exists a
product $i^{*}\in S$ and a directed edge $(i^{*},i)\in\mathscr{E}$].

At a high level, the recursive subroutine in Algorithm 3 is comprised of two
cases. The base case of the subroutine is when the graph has no vertices, in
which case it is clear that $\mathcal{A}=\\{\emptyset\\}$. If we are not in
the base case, then the aim of the recusive subroutine is to construct the
collections $\left\\{S\in\mathcal{A}:i\notin S\right\\}$ and
$\left\\{S\in\mathcal{A}:i\in S\right\\}$ for a chosen vertex
$i\in\mathcal{V}$ and output the union of these two collections. The
construction of the collection $\left\\{S\in\mathcal{A}:i\notin S\right\\}$
takes place on lines (2b)-(2c) of Algorithm 3, and the construction of the
collection $\left\\{S\in\mathcal{A}:i\in S\right\\}$ takes place on lines
(2d)-(2f) of Algorithm 3.

Up to this point, we have established that Algorithm 1 is correct (that is, it
delivers the desired output for any valid input), and we have established that
Algorithm 2 is correct under the assumption that Algorithm 3 is correct.
Therefore, it remains for us to prove that the recursive subroutine in
Algorithm 3 is correct. To prove the correctness of the recursive subroutine,
we will make use of four intermediary claims, which are denoted below by
Claims 3-6. The purpose of the first two intermediary claims, denoted by
Claims 3 and 4, is to show that the graphs
$\mathcal{G}^{\prime}\equiv(\mathcal{V}^{\prime},\mathcal{E}^{\prime})$ and
$\mathcal{G}^{\prime\prime}\equiv(\mathcal{V}^{\prime\prime},\mathcal{E}^{\prime\prime})$
constructed on lines (2b) and (2d) of Algorithm 3 are directed acyclic graphs
that are transitive closures, which implies that $\mathcal{G}^{\prime}$ and
$\mathcal{G}^{\prime\prime}$ are valid inputs on lines (2c) and (2e) of
Algorithm 3. The purpose of the second two intermediary claims, denoted by
Claims 5 and 6, is to show that the union of the two collections
$\mathcal{A}^{\prime}$ and $\mathcal{A}^{\prime\prime\prime}$ constructed on
lines (2c) and (2f) of Algorithm 3 provides the desired output on line (2g) of
Algorithm 3.

Construct-$\widehat{\mathcal{S}}(\mathscr{M},r)$ Inputs: • The collection of
previously-offered assortments, $\mathscr{M}\equiv\\{S_{1},\ldots,S_{M}\\}$. •
The revenues of the products, $r\equiv(r_{0},r_{1},\ldots,r_{n})$. Output: •
The collection of assortments $\widehat{\mathcal{S}}$ corresponding to the
collection of previously-offered assortments $\mathscr{M}$ and the revenues
$r$. Procedure: 1. Construct the directed acyclic graph
$\mathscr{G}\leftarrow\textsc{Construct-${\mathscr{G}}(\mathscr{M},r)$}$. 2.
Compute the collection of assortments
$\widehat{\mathcal{S}}\leftarrow\textsc{RecursiveStep$(\mathscr{G})$}$. 3. For
each $S\in\widehat{\mathcal{S}}$: (a) If $0\notin S$: i. Update
$\widehat{\mathcal{S}}\leftarrow\widehat{\mathcal{S}}\setminus\\{S\\}$. 4.
Output $\widehat{\mathcal{S}}$ and terminate.

Algorithm 2:  A procedure for constructing $\widehat{\mathcal{S}}$.

RecursiveStep$(\mathcal{G})$ Inputs: • A directed acyclic graph
$\mathcal{G}\equiv(\mathcal{V},\mathcal{E})$ which is a transitive closure.
Output: • The collection $\mathcal{A}\equiv\\{S\subseteq\mathcal{V}:\text{ if
$i\in S$ and $(i,j)\in\mathcal{E}$, then $j\in S$}\\}$. Procedure: 1. If
$\mathcal{V}=\emptyset$: (a) Output the collection
$\mathcal{A}\equiv\\{\emptyset\\}$ and terminate. 2. Otherwise: (a) Choose any
vertex $i\in\mathcal{V}$. (b) Create a copy of
$\mathcal{G}\equiv(\mathcal{V},\mathcal{E})$ in which the vertices
$\\{i\\}\cup\\{\ell:(\ell,i)\in\mathcal{E}\\}$ and the incoming and outgoing
edges of these vertices are removed. Denote this new graph by
$\mathcal{G}^{\prime}\equiv(\mathcal{V}^{\prime},\mathcal{E}^{\prime})$. (c)
Compute the collection
$\mathcal{A}^{\prime}\leftarrow\textsc{RecursiveStep$(\mathcal{G}^{\prime})$}$.
(d) Create a copy of $\mathcal{G}\equiv(\mathcal{V},\mathcal{E})$ in which the
vertices $\\{i\\}\cup\\{\ell:(i,\ell)\in\mathcal{E}\\}$ and the incoming and
outgoing edges of these vertices are removed. Denote this new graph by
$\mathcal{G}^{\prime\prime}\equiv(\mathcal{V}^{\prime\prime},\mathcal{E}^{\prime\prime})$.
(e) Compute the collection
$\mathcal{A}^{\prime\prime}\leftarrow\textsc{RecursiveStep$(\mathcal{G}^{\prime\prime})$}$.
(f) Compute the collection
$\mathcal{A}^{\prime\prime\prime}\leftarrow\\{S\cup\\{i\\}\cup\\{\ell:(i,\ell)\in\mathcal{E}\\}:S\in\mathcal{A}^{\prime\prime}\\}$.
(g) Output the collection
$\mathcal{A}\equiv\mathcal{A}^{\prime}\cup\mathcal{A}^{\prime\prime\prime}$
and terminate.

Algorithm 3:  A recursive subroutine which is used in Algorithm 2.

###### Claim 3

Let $\mathcal{G}\equiv(\mathcal{V},\mathcal{E})$ be a directed acyclic graph
that is a transitive closure. For notational convenience, let
$\mathcal{E}_{i}$ denote the set of incoming and outgoing edges from each
vertex $i\in\mathcal{V}$. Then for each vertex $i\in\mathcal{V}$, we have that
$\tilde{\mathcal{G}}\equiv(\mathcal{V}\setminus\\{i\\},\mathcal{E}\setminus\mathcal{E}_{i})$
is a directed acyclic graph that is a transitive closure.

###### Proof 12.1

Proof of Claim 3. Let $\mathcal{G}\equiv(\mathcal{V},\mathcal{E})$ be a
directed acyclic graph that is a transitive closure, and let $i\in\mathcal{V}$
be any chosen vertex. It is clear that removing a vertex and its associated
incoming and outgoing edges from a directed acyclic graph will not induce any
cycles. Therefore, it follows from the fact that the original graph
$\mathcal{G}\equiv(\mathcal{V},\mathcal{E})$ is a directed acyclic graph that
the new graph
$\tilde{\mathcal{G}}\equiv(\mathcal{V}\setminus\\{i\\},\mathcal{E}\setminus\mathcal{E}_{i})$
is also a directed acyclic graph. Moreover, consider any two arbitrary
vertices $j,k\in\mathcal{V}\setminus\\{i\\}$ which satisfy the property that
vertex $k$ is reachable from vertex $j$ in the new graph
$\tilde{\mathcal{G}}\equiv(\mathcal{V}\setminus\\{i\\},\mathcal{E}\setminus\mathcal{E}_{i})$.
Then it follows immediately from the construction of the new graph that vertex
$k$ is reachable from vertex $j$ in the original graph
$\mathcal{G}\equiv(\mathcal{V},\mathcal{E})$. Since the original graph
$\mathcal{G}\equiv(\mathcal{V},\mathcal{E})$ is a transitive closure, there
must exist a directed edge from vertex $j$ to vertex $k$ in the original
graph. Since neither $j$ nor $k$ are equal to $i$, we have thus shown that
there is a directed edge $(j,k)\in\mathcal{E}\setminus\mathcal{E}_{i}$. Since
the two vertices $j,k\in\mathcal{V}\setminus\\{i\\}$ were chosen arbitrarily,
we have shown that the new graph is also a transitive closure. Our proof of
Claim 3 is thus complete.

###### Claim 4

Let $\mathcal{G}\equiv(\mathcal{V},\mathcal{E})$ be a directed acyclic graph
that is a transitive closure. For notational convenience, let
$\mathcal{E}_{i}$ denote the set of incoming and outgoing edges from each
vertex $i\in\mathcal{V}$. Then for each subset of vertices
$\mathcal{B}\subseteq\mathcal{V}$, we have that
$\tilde{\mathcal{G}}\equiv(\mathcal{V}\setminus\mathcal{B},\mathcal{E}\setminus(\cup_{i\in\mathcal{B}}\mathcal{E}_{i}))$
is a directed acyclic graph that is a transitive closure.

###### Proof 12.2

Proof of Claim 4. Let $\mathcal{G}\equiv(\mathcal{V},\mathcal{E})$ be a
directed acyclic graph that is a transitive closure, let
$\mathcal{B}\subseteq\mathcal{V}$ be a subset of vertices, and define the
directed graph
$\tilde{\mathcal{G}}\equiv(\mathcal{V}\setminus\mathcal{B},\mathcal{E}\setminus(\cup_{i\in\mathcal{B}}\mathcal{E}_{i}))$.
The rest of the proof follows a straightforward induction argument. Indeed,
let the vertices of $\mathcal{B}$ be indexed by
$\mathcal{B}\equiv\\{i^{\mathcal{B}}_{1},\ldots,i^{\mathcal{B}}_{|\mathcal{B}|}\\}$.
For each $j\in\\{0,1,\ldots,|\mathcal{B}|\\}$, we define the following
directed graph:

$\displaystyle{\mathcal{G}}^{\mathcal{B}}_{j}\equiv(\underbrace{\mathcal{V}\setminus\\{i^{\mathcal{B}}_{1},\ldots,i^{\mathcal{B}}_{j}\\}}_{\mathcal{V}^{\mathcal{B}}_{j}},\;\underbrace{\mathcal{E}\setminus\left\\{(k,\ell)\in\mathcal{E}:k\in\\{i^{\mathcal{B}}_{1},\ldots,i^{\mathcal{B}}_{j}\\}\textnormal{
or
}\ell\in\\{i^{\mathcal{B}}_{1},\ldots,i^{\mathcal{B}}_{j}\\}\right\\}}_{\mathcal{E}^{\mathcal{B}}_{j}}).$

We readily observe from the above definition that
${\mathcal{G}}^{\mathcal{B}}_{0}=\mathcal{G}$ and that
${\mathcal{G}}^{\mathcal{B}}_{|\mathcal{B}|}=\tilde{\mathcal{G}}$. In the
remainder, we will prove by induction that each
$\tilde{\mathcal{G}}^{\mathcal{B}}_{0},\ldots,\tilde{\mathcal{G}}^{\mathcal{B}}_{|\mathcal{B}|}$
is a directed acyclic graph that is a transitive closure. Our induction proof
proceeds as follows. In the base case, it follows from the equality
${\mathcal{G}}^{\mathcal{B}}_{0}=\mathcal{G}$ that
${\mathcal{G}}^{\mathcal{B}}_{0}$ is a directed acyclic graph that is a
transitive closure. Next, assume by induction that
$\tilde{\mathcal{G}}^{\mathcal{B}}_{0},\ldots,\tilde{\mathcal{G}}^{\mathcal{B}}_{j-1}$
are directed acyclic graphs that are transitive closures for any
$j\in\\{1,\ldots,|\mathcal{B}|\\}$. Then we readily observe from the
definition of the directed graph
$\mathcal{G}^{\mathcal{B}}_{j}\equiv(\mathcal{V}^{\mathcal{B}}_{j},\mathcal{E}^{\mathcal{B}}_{j})$
that the following equalities hold:

$\displaystyle\mathcal{V}^{\mathcal{B}}_{j}$
$\displaystyle=\mathcal{V}^{\mathcal{B}}_{j-1}\setminus\\{i^{\mathcal{B}}_{j}\\};$
$\displaystyle\mathcal{E}^{\mathcal{B}}_{j}$
$\displaystyle=\mathcal{E}^{\mathcal{B}}_{j-1}\setminus\left\\{(k,\ell)\in\mathcal{E}^{\mathcal{B}}_{j-1}:\;k=i^{\mathcal{B}}_{j}\textnormal{
or }\ell=i^{\mathcal{B}}_{j}\right\\}.$

Using the above equalities, it follows immediately from Claim 3 and the
induction hypothesis that $\mathcal{G}^{\mathcal{B}}_{j}$ is a directed
acyclic graph that is a transitive closure. This concludes our induction
proof, and since the equality
${\mathcal{G}}^{\mathcal{B}}_{|\mathcal{B}|}=\tilde{\mathcal{G}}$ holds, our
proof of Claim 4 is complete.

###### Claim 5

Let $\mathcal{G}\equiv(\mathcal{V},\mathcal{E})$ be a directed acyclic graph
that is a transitive closure. For notational convenience, let
$\mathcal{E}_{i}$ denote the set of incoming and outgoing edges from each
vertex $i\in\mathcal{V}$. For each vertex $i\in\mathcal{V}$,

$\displaystyle\left\\{S\subseteq\mathcal{V}\setminus\\{i\\}:\textnormal{ if
$k\in S$ and $(k,j)\in\mathcal{E}$, then $j\in S$}\right\\}$
$\displaystyle=\left\\{S\subseteq\mathcal{V}\setminus(\\{i\\}\cup\\{\ell:(\ell,i)\in\mathcal{E}\\}):\textnormal{if
}k\in S\textnormal{ and
}(k,j)\in\mathcal{E}\setminus\left(\mathcal{E}_{i}\cup\bigcup_{\ell:(\ell,i)\in\mathcal{E}}\mathcal{E}_{\ell}\right),\textnormal{
then }j\in S\right\\}.$ (14)

###### Proof 12.3

Proof of Claim 5. Let $\mathcal{G}\equiv(\mathcal{V},\mathcal{E})$ be a
directed acyclic graph that is a transitive closure, and let $i\in\mathcal{V}$
be any chosen vertex from this graph. We first observe that

$\displaystyle\left\\{S\subseteq\mathcal{V}\setminus\\{i\\}:\text{ if $k\in S$
and $(k,j)\in\mathcal{E}$, then $j\in S$}\right\\}$ (15)
$\displaystyle=\left\\{S\subseteq\mathcal{V}\setminus(\\{i\\}\cup\\{\ell:(\ell,i)\in\mathcal{E}\\}):\textnormal{if
}k\in S\textnormal{ and }(k,j)\in\mathcal{E},\textnormal{ then }j\in
S\right\\},$ (16)

where the above equality follows from the fact that any subset of vertices $S$
from the collection on line (15) must not contain any vertices in the graph
that have an outgoing edge to vertex $i$. For notational convenience, let the
collection of subsets of vertices on line (14) be denoted by
$\tilde{\mathcal{A}}$, and let the collection of subsets of vertices on line
(16) be denoted by $\tilde{\mathcal{A}}^{\prime}$. In other words, let

$\displaystyle\tilde{\mathcal{A}}^{\prime}$
$\displaystyle\triangleq\left\\{S\subseteq\mathcal{V}\setminus(\\{i\\}\cup\\{\ell:(\ell,i)\in\mathcal{E}\\}):\textnormal{if
}k\in S\textnormal{ and }(k,j)\in\mathcal{E},\textnormal{ then }j\in
S\right\\}$ $\displaystyle\tilde{\mathcal{A}}$
$\displaystyle\triangleq\left\\{S\subseteq\mathcal{V}\setminus(\\{i\\}\cup\\{\ell:(\ell,i)\in\mathcal{E}\\}):\textnormal{if
}k\in S\textnormal{ and
}(k,j)\in\mathcal{E}\setminus\left(\mathcal{E}_{i}\cup\bigcup_{\ell:(\ell,i)\in\mathcal{E}}\mathcal{E}_{\ell}\right),\textnormal{
then }j\in S\right\\}.$

In the remainder of the proof, we will show that
$\tilde{\mathcal{A}}=\tilde{\mathcal{A}}^{\prime}$.

To show the first direction, consider any arbitrary subset of vertices
$S\in\tilde{\mathcal{A}}^{\prime}$. For this subset of vertices, consider any
two arbitrary vertices
$k,j\in\mathcal{V}\setminus(\\{i\\}\cup\\{\ell:(\ell,i)\in\mathcal{E}\\})$
which satisfy the conditions [$k\in S$] and
[$(k,j)\in\mathcal{E}\setminus(\mathcal{E}_{i}\cup\bigcup_{\ell:(\ell,i)\in\mathcal{E}}\mathcal{E}_{\ell})$].
In this case, it follows immediately from the fact that
$\mathcal{E}\setminus(\mathcal{E}_{i}\cup\bigcup_{\ell:(\ell,i)\in\mathcal{E}}\mathcal{E}_{\ell})\subseteq\mathcal{E}$
that the condition [$(k,j)\in\mathcal{E}$] holds. Therefore, it follows
immediately from the definition of $\tilde{\mathcal{A}}^{\prime}$ that $j\in
S$. Since the two vertices
$k,j\in\mathcal{V}\setminus(\\{i\\}\cup\\{\ell:(\ell,i)\in\mathcal{E}\\})$
which satisfy the conditions [$k\in S$] and
[$(k,j)\in\mathcal{E}\setminus(\mathcal{E}_{i}\cup\bigcup_{\ell:(\ell,i)\in\mathcal{E}}\mathcal{E}_{\ell})$]
were chosen arbitrarily, we have shown that $S\in\tilde{\mathcal{A}}$, and
since the subset of vertices $S\in\tilde{\mathcal{A}}^{\prime}$ was chosen
arbitrarily, we have shown that
$\tilde{\mathcal{A}}^{\prime}\subseteq\tilde{\mathcal{A}}$. Our proof of the
first direction is thus complete.

To show the other direction, consider any arbitrary subset of vertices
$S\in\tilde{\mathcal{A}}$. For this subset of vertices, consider any two
arbitrary vertices
$k,j\in\mathcal{V}\setminus(\\{i\\}\cup\\{\ell:(\ell,i)\in\mathcal{E}\\})$
which satisfy the conditions [$k\in S$] and [$(k,j)\in\mathcal{E}$]. We now
suppose, for the sake of developing a contradiction, that the directed edge
from vertex $k$ to vertex $j$ satisfies
$(k,j)\in\mathcal{E}_{i}\cup\bigcup_{\ell:(\ell,i)\in\mathcal{E}}\mathcal{E}_{\ell}$.
Under this supposition, we have two cases to consider. In the first case, the
directed edge satisfies $(k,j)\in\mathcal{E}_{i}$. However, that would imply
that either $j=i$ or $k=i$, and those equalities contradict the facts that
$k\in S$ and
$S\subseteq\mathcal{V}\setminus(\\{i\\}\cup\\{\ell:(\ell,i)\in\mathcal{E}\\})$.
In the second case, the directed edge satisfies
$(k,j)\in\bigcup_{\ell:(\ell,i)\in\mathcal{E}}\mathcal{E}_{\ell}$, which
implies that there are directed edges $(k,j)\in\mathcal{E}$ and
$(j,i)\in\mathcal{E}$ in the graph $\mathcal{G}$. Since the graph is a
transitive closure, the existence of directed edges $(k,j)\in\mathcal{E}$ and
$(j,i)\in\mathcal{E}$ implies that there must exist a directed edge
$(k,i)\in\mathcal{E}$. However, the existence of a directed edge
$(k,i)\in\mathcal{E}$ contradicts the facts that $k\in S$ and
$S\subseteq\mathcal{V}\setminus(\\{i\\}\cup\\{\ell:(\ell,i)\in\mathcal{E}\\})$.
In all cases, we have proved by contradiction that the vertices $k$ and $j$
must satisfy the condition
[$(k,j)\in\mathcal{E}\setminus(\mathcal{E}_{i}\cup\bigcup_{\ell:(\ell,i)\in\mathcal{E}}\mathcal{E}_{\ell})$].
Since the two vertices
$k,j\in\mathcal{V}\setminus(\\{i\\}\cup\\{\ell:(\ell,i)\in\mathcal{E}\\})$
which satisfy the conditions [$k\in S$] and [$(k,j)\in\mathcal{E}$] were
chosen arbitrarily, we have shown that $S\in\tilde{\mathcal{A}}^{\prime}$, and
since the subset of vertices $S\in\tilde{\mathcal{A}}$ was chosen arbitrarily,
we have shown that $\tilde{\mathcal{A}}\subseteq\tilde{\mathcal{A}}^{\prime}$.
Our proof of the second direction is thus complete.

We have thus shown that $\tilde{\mathcal{A}}=\tilde{\mathcal{A}}^{\prime}$,
which concludes our proof of Claim 5.

###### Claim 6

Let $\mathcal{G}\equiv(\mathcal{V},\mathcal{E})$ be a directed acyclic graph
that is a transitive closure. For notational convenience, let
$\mathcal{E}_{i}$ denote the set of incoming and outgoing edges from each
vertex $i\in\mathcal{V}$. For each vertex $i\in\mathcal{V}$,

$\displaystyle\left\\{S\subseteq\mathcal{V}:\left[i\in S\right]\textnormal{
and }\left[\textnormal{if $k\in S$ and $(k,j)\in\mathcal{E}$, then $j\in
S$}\right]\right\\}$ $\displaystyle=\left\\{\begin{aligned}
&S^{\prime}\cup\\{i\\}\cup\left\\{\ell:(i,\ell)\in\mathcal{E}\right\\}:\\\
&\quad
S^{\prime}\in\left\\{S\subseteq\mathcal{V}\setminus\left(\\{i\\}\cup\left\\{\ell:(i,\ell)\in\mathcal{E}\right\\}\right):\textnormal{if
}k\in S\textnormal{ and
}(k,j)\in\mathcal{E}\setminus\left(\mathcal{E}_{i}\cup\bigcup_{\ell:(i,\ell)\in\mathcal{E}}\mathcal{E}_{\ell}\right),\textnormal{
then }j\in S\right\\}\end{aligned}\right\\}.$ (17)

###### Proof 12.4

Proof of Claim 6. Let $\mathcal{G}\equiv(\mathcal{V},\mathcal{E})$ be a
directed acyclic graph that is a transitive closure, and let $i\in\mathcal{V}$
be any chosen vertex from this graph. Then we observe that

$\displaystyle\left\\{S\subseteq\mathcal{V}:\left[i\in S\right]\textnormal{
and }\left[\textnormal{if $k\in S$ and $(k,j)\in\mathcal{E}$, then $j\in
S$}\right]\right\\}$ (18)
$\displaystyle=\left\\{S\subseteq\mathcal{V}:\left[\\{i\\}\cup\\{\ell:(i,\ell)\in\mathcal{E}\\}\subseteq
S\right]\textnormal{ and }\left[\textnormal{if $k\in S$ and
$(k,j)\in\mathcal{E}$, then $j\in S$}\right]\right\\}$ (19)
$\displaystyle=\left\\{S\subseteq\mathcal{V}:\left[\\{i\\}\cup\left\\{\ell:(i,\ell)\in\mathcal{E}\right\\}\subseteq
S\right]\textnormal{ and }\left[\textnormal{if }k\in S\textnormal{ and
}(k,j)\in\mathcal{E}\setminus\left(\mathcal{E}_{i}\cup\bigcup_{\ell:(i,\ell)\in\mathcal{E}}\mathcal{E}_{\ell}\right),\textnormal{
then }j\in S\right]\right\\}.$ (20)

Indeed, the equality of the collections of subsets of vertices on lines (18)
and (19) follows from the fact that any subset of vertices $S$ in the
collection on line (18) satisfies $i\in S$, and so it must contain all of the
vertices in the graph which have an incoming edge from vertex $i$. For
notational convenience, let the collections of subsets of vertices on lines
(19) and (20) be denoted by $\bar{\mathcal{A}}^{\prime}$ and
$\bar{\mathcal{A}}$, respectively. To show that line (19) is equal to line
(20), we first observe that the inclusion
$\bar{\mathcal{A}}^{\prime}\subseteq\bar{\mathcal{A}}$ follows immediately
from the definitions of the collections $\bar{\mathcal{A}}^{\prime}$ and
$\bar{\mathcal{A}}$. To show the other direction, consider any subset of
vertices $S\in\bar{\mathcal{A}}$ and consider any vertex $k\in S$. If there
exists a directed edge $(k,j)\in\mathcal{E}$ which satisfies
$(k,j)\in\mathcal{E}_{i}\cup\bigcup_{\ell:(i,\ell)\in\mathcal{E}}\mathcal{E}_{\ell}$,
then we observe that the vertex $j$ must satisfy
$j\in\\{i\\}\cup\\{\ell:(i,\ell)\in\mathcal{E}\\}$. Since it follows from
$S\in\bar{\mathcal{A}}$ that the inclusion
$\\{i\\}\cup\\{\ell:(i,\ell)\in\mathcal{E}\\}\subseteq S$ holds, we conclude
that $S\in\bar{\mathcal{A}}^{\prime}$. We have thus shown that line (19) is
equal to line (20). Since the equivalence of lines (20) and (17) follows
readily from algebra, our proof of Claim 6 is complete.

Using the above intermediary claims, we now prove the correctness of the
recursive subroutine in Algorithm 3. Indeed, it is clear that the recursive
subroutine yields the correct output in the base case where
$\mathcal{V}=\emptyset$. Next, let us assume by induction that the recursive
subroutine yields the correct output for all valid input graphs with up to
$p-1$ vertices, and consider any valid input
$\mathcal{G}\equiv(\mathcal{V},\mathcal{E})$ for which the number of vertices
is $|\mathcal{V}|=p$. Let $i\in\mathcal{V}$ denote the vertex from this graph
which is chosen in line (2a) of Algorithm 3, where the existence of such a
vertex follows from the fact that we are in the case where
$\mathcal{V}\neq\emptyset$. It follows immediately from Claim 4 that the
graphs $\mathcal{G}^{\prime}\equiv(\mathcal{V}^{\prime},\mathcal{E}^{\prime})$
and
$\mathcal{G}^{\prime\prime}\equiv(\mathcal{V}^{\prime\prime},\mathcal{E}^{\prime\prime})$
constructed on lines (2b) and (2d) of Algorithm 3 are directed acyclic graphs
which are transitive closures, which implies that these graphs are valid
inputs to Algorithm 3 in lines (2c) and (2e). Therefore, it follows from the
induction hypothesis and lines (2c), (2e), and (2f) of Algorithm 3 that

$\displaystyle\mathcal{A}^{\prime}$
$\displaystyle=\left\\{S\subseteq\mathcal{V}\setminus(\\{i\\}\cup\\{\ell:(\ell,i)\in\mathcal{E}\\}):\textnormal{if
}k\in S\textnormal{ and
}(k,j)\in\mathcal{E}\setminus\left(\mathcal{E}_{i}\cup\bigcup_{\ell:(\ell,i)\in\mathcal{E}}\mathcal{E}_{\ell}\right),\textnormal{
then }j\in S\right\\}$ $\displaystyle\mathcal{A}^{\prime\prime}$
$\displaystyle=\left\\{S\subseteq\mathcal{V}\setminus(\\{i\\}\cup\\{\ell:(i,\ell)\in\mathcal{E}\\}):\textnormal{if
}k\in S\textnormal{ and
}(k,j)\in\mathcal{E}\setminus\left(\mathcal{E}_{i}\cup\bigcup_{\ell:(i,\ell)\in\mathcal{E}}\mathcal{E}_{\ell}\right),\textnormal{
then }j\in S\right\\}$ $\displaystyle\mathcal{A}^{\prime\prime\prime}$
$\displaystyle=\left\\{S\cup\\{i\\}\cup\left\\{\ell:(i,\ell)\in\mathcal{E}\right\\}:S\in\mathcal{A}^{\prime\prime}\right\\},$

where the induction hypothesis can be applied because
$\mathcal{G}^{\prime}\equiv(\mathcal{V}^{\prime},\mathcal{E}^{\prime})$ and
$\mathcal{G}^{\prime\prime}\equiv(\mathcal{V}^{\prime\prime},\mathcal{E}^{\prime\prime})$
are valid inputs to Algorithm 3 and because $|\mathcal{V}^{\prime}|\leq p-1$
and $|\mathcal{V}^{\prime\prime}|\leq p-1$. Therefore, it follows from Claims
5 and 6 that

$\displaystyle\mathcal{A}^{\prime}$
$\displaystyle=\left\\{S\subseteq\mathcal{V}\setminus\\{i\\}:\textnormal{ if
$k\in S$ and $(k,j)\in\mathcal{E}$, then $j\in S$}\right\\}$
$\displaystyle\mathcal{A}^{\prime\prime\prime}$
$\displaystyle=\left\\{S\subseteq\mathcal{V}:\left[i\in S\right]\textnormal{
and }\left[\textnormal{if $k\in S$ and $(k,j)\in\mathcal{E}$, then $j\in
S$}\right]\right\\},$

which proves that the output of Algorithm 3 is

$\displaystyle\mathcal{A}^{\prime}\cup\mathcal{A}^{\prime\prime\prime}=\left\\{S\subseteq\mathcal{V}:\textnormal{
if $k\in S$ and $(k,j)\in\mathcal{E}$, then $j\in S$}\right\\}.$

This completes our proof of the correctness of Algorithm 3.

To conclude our proof of Lemma 4.8, we analyze the computation time of
Algorithm 2. Indeed, we recall that the computation time required for line (1)
in Algorithm 2 is $\mathcal{O}(n^{2}M)$. In what follows, we assume that all
directed graphs are stored as adjacency lists. Under this assumption, our
analysis of the computation time for line (2) in Algorithm 3 is split into the
following two intermediary claims, denoted by Claim 7 and 8. In our first
intermediary claim, presented below as Claim 7, we establish the computation
time required for lines (2b), (2d), (2f), and (2g) of Algorithm 3.

###### Claim 7

If $\mathcal{G}\equiv(\mathcal{V},\mathcal{E})$ is a directed acyclic graph
that is a transitive closure with $|\mathcal{V}|\geq 1$, then lines (2b),
(2d), (2f), and (2g) of Algorithm 3 can be performed in
$\mathcal{O}\left(|\mathcal{V}|\times\left|\textsc{RecursiveStep}(\mathcal{G})\right|\right)$
time.

###### Proof 12.5

Proof. We observe that the set of vertices
$\\{i\\}\cup\\{\ell:(\ell,i)\in\mathcal{E}\\}$ in line (2b) of Algorithm 3 can
be queried and stored as a hash table in
$\mathcal{O}(|\\{i\\}\cup\\{\ell:(\ell,i)\in\mathcal{E}\\}|)=\mathcal{O}(|\mathcal{V}|)$
computation time. Therefore, the directed graph
$\mathcal{G}^{\prime}\equiv(\mathcal{V}^{\prime},\mathcal{E}^{\prime})$ in
line (2b) of Algorithm 3 can be constructed from scratch in
$\mathcal{O}(|\mathcal{V}|+|\mathcal{E}|)$ computation time. By identical
reasoning, we observe that the directed graph
$\mathcal{G}^{\prime\prime}\equiv(\mathcal{V}^{\prime\prime},\mathcal{E}^{\prime\prime})$
in line (2d) of Algorithm 3 can be constructed in
$\mathcal{O}(|\mathcal{V}|+|\mathcal{E}|)$ computation time. It is easy to see
for each $S\in\mathcal{A}^{\prime\prime}$ that
$S\cup\\{i\\}\cup\\{\ell:(i,\ell)\in\mathcal{E}\\}$ is the union of three
disjoint sets, which implies that the collection on line (2f) of Algorithm 3
can be constructed in a total of
$\mathcal{O}\left(\sum_{S\in\mathcal{A}^{\prime\prime}}(|S|+|\\{\ell:(i,\ell)\in\mathcal{E}\\}|)\right)=\mathcal{O}\left(\sum_{S\in\mathcal{A}^{\prime\prime\prime}}|S|\right)$
computation time. It is similarly easy to see that
$\mathcal{A}\equiv\mathcal{A}^{\prime}\cup\mathcal{A}^{\prime\prime\prime}$ is
the union of two disjoint collections, which implies that line (2g) of
Algorithm 3 can be performed in
$\mathcal{O}\left(\sum_{S\in\mathcal{A}^{\prime}}|S|+\sum_{S\in\mathcal{A}^{\prime\prime\prime}}|S|\right)=\mathcal{O}\left(\sum_{S\in\mathcal{A}}|S|\right)$
computation time. All combined, we have shown that the computation time
required for lines (2b), (2d), (2f), and (2g) of Algorithm 3 is

$\displaystyle\underbrace{\mathcal{O}(|\mathcal{V}|+|\mathcal{E}|)}_{\eqref{step:construct_A1:1}}+\underbrace{\mathcal{O}(|\mathcal{V}|+|\mathcal{E}|)}_{\eqref{step:construct_A2:1}}+\underbrace{\mathcal{O}\left(\sum_{S\in\mathcal{A}^{\prime\prime\prime}}|S|\right)}_{\eqref{step:construct_A2:3}}+\underbrace{\mathcal{O}\left(\sum_{S\in\mathcal{A}}|S|\right)}_{\eqref{step:construct_A}}=\mathcal{O}\left(|\mathcal{V}|+|\mathcal{E}|+\sum_{S\in\mathcal{A}}|S|\right).$

Using the fact that graphs always satisfy the inequality
$|\mathcal{E}|\leq|\mathcal{V}|^{2}$ and the fact that $|S|\leq|\mathcal{V}|$
for all $S\in\mathcal{A}$, the above computation time simplifies to
$\mathcal{O}\left(|\mathcal{V}|^{2}+\left|\mathcal{V}\right|\times\left|\mathcal{A}\right|\right).$
Since $\mathcal{A}\equiv\textsc{RecursiveStep}(\mathcal{G})$ is the output of
Algorithm 3, and since it is easy to see that
$|\mathcal{A}|\geq|\mathcal{V}|$, our proof of Claim 7 is complete.

In our second intermediary claim, presented below as Claim 8, we use Claim 7
to establish the computation time for Algorithm 3 for any valid input.

###### Claim 8

If $\mathcal{G}\equiv(\mathcal{V},\mathcal{E})$ is a directed acyclic graph
that is a transitive closure with $|\mathcal{V}|\geq 1$, then the computation
time for Algorithm 3 is
$\mathcal{O}(|\mathcal{V}|^{2}\times\left|\textsc{RecursiveStep}(\mathcal{G})\right|)$.

###### Proof 12.6

Proof. Let $T(\mathcal{G})$ denote the computation time required to run
Algorithm 3 for any valid input $\mathcal{G}\equiv(\mathcal{V},\mathcal{E})$.
It follows from Claim 7 that $T(\mathcal{G})$ can be represented by an
asymptotic recurrence of the form

$\displaystyle T(\mathcal{G})$
$\displaystyle=\begin{cases}|\mathcal{V}|\times\left|\textsc{RecursiveStep}(\mathcal{G})\right|+T(\mathcal{G}^{\prime})+T(\mathcal{G}^{\prime\prime}),&\text{if
}\mathcal{V}\neq\emptyset,\\\ 1,&\text{if }\mathcal{V}=\emptyset,\end{cases}$
(21)

where $\mathcal{G}^{\prime}$ and $\mathcal{G}^{\prime\prime}$ are the
subgraphs constructed in Algorithm 3 on lines (2b) and (2d). We will now prove
that the above recurrence satisfies the following inequality:

$\displaystyle
T(\mathcal{G})\leq(|\mathcal{V}|+1)^{2}\times\left|\textsc{RecursiveStep}(\mathcal{G})\right|.$

Indeed, the above inequality clearly holds in the base case. Now assume by
induction that the above inequality holds for all valid inputs graphs to
Algorithm 3 with up to $p-1$ vertices, and consider any valid input
$\mathcal{G}\equiv(\mathcal{V},\mathcal{E})$ to Algorithm 3 for which the
number of vertices is $|\mathcal{V}|=p$. For this input, we have

$\displaystyle T(\mathcal{G})$
$\displaystyle=|\mathcal{V}|\times\left|\textsc{RecursiveStep}(\mathcal{G})\right|+T(\mathcal{G}^{\prime})+T(\mathcal{G}^{\prime\prime})$
$\displaystyle\leq|\mathcal{V}|\times\left|\textsc{RecursiveStep}(\mathcal{G})\right|+(|\mathcal{V}^{\prime}|+1)^{2}\times\left|\textsc{RecursiveStep}(\mathcal{G}^{\prime})\right|+(|\mathcal{V}^{\prime\prime}|+1)^{2}\times\left|\textsc{RecursiveStep}(\mathcal{G}^{\prime\prime})\right|$
$\displaystyle\leq|\mathcal{V}|\times\left|\textsc{RecursiveStep}(\mathcal{G})\right|+|\mathcal{V}|^{2}\times\left|\textsc{RecursiveStep}(\mathcal{G}^{\prime})\right|+|\mathcal{V}|^{2}\times\left|\textsc{RecursiveStep}(\mathcal{G}^{\prime\prime})\right|$
$\displaystyle=|\mathcal{V}|\times\left|\textsc{RecursiveStep}(\mathcal{G})\right|+|\mathcal{V}|^{2}\times\left|\textsc{RecursiveStep}(\mathcal{G})\right|$
$\displaystyle\leq(|\mathcal{V}|+1)^{2}\times\left|\textsc{RecursiveStep}(\mathcal{G})\right|,$

where the first line follows from (21) and from the fact that
$\mathcal{V}\neq\emptyset$, the second line follows from the induction
hypothesis, the third line follows from the facts that
$|\mathcal{V}^{\prime}|<|\mathcal{V}|$ and
$|\mathcal{V}^{\prime\prime}|<|\mathcal{V}|$, the fourth line follows from the
fact that
$\left|\textsc{RecursiveStep}(\mathcal{G})\right|=\left|\textsc{RecursiveStep}(\mathcal{G}^{\prime})\right|+\left|\textsc{RecursiveStep}(\mathcal{G}^{\prime\prime})\right|$,
and the final line follows from algebra. This concludes our proof of Claim 8.

Our analysis of the computation time for line (2) of Algorithm 2 follows
readily from Claim 8. Indeed, we observe that the graph
$\mathscr{G}\equiv(\mathscr{V},\mathscr{E})$ that was constructed on line (1)
of Algorithm 2 satisfies $|\mathscr{V}|=n+1$ and $|\mathscr{E}|\leq(n+1)^{2}$.
Therefore, it follows from Claim 8 that line (2) of Algorithm 2 requires
$\mathcal{O}((n+1)^{2}\times\left|\textsc{RecursiveStep}(\mathscr{G})\right|)=\mathcal{O}(n^{2}|\widehat{\mathcal{S}}|)$
computation time. Since the loop on line (3) of Algorithm 2 can be performed
in
$\mathcal{O}(\sum_{S\in\widehat{\mathcal{S}}}|S|)=\mathcal{O}(n|\widehat{\mathcal{S}}|)$
computation time, we have shown that the total computation time for Algorithm
2 is

$\displaystyle\underbrace{\mathcal{O}(n^{2}M)}_{\eqref{step:construct_S:1}}+\underbrace{\mathcal{O}(n^{2}|\widehat{\mathcal{S}}|)}_{\eqref{step:construct_S:2}}+\underbrace{\mathcal{O}(n|\widehat{\mathcal{S}}|)}_{\eqref{step:construct_S:3}}=\mathcal{O}\left(n^{2}(M+|\widehat{\mathcal{S}}|)\right).$

This concludes our proof of Lemma 4.8.

###  12.2 Proof of Lemma 4.9

We readily observe that the collection of assortments $\widehat{\mathcal{S}}$
is a subset of

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

where we recall from the beginning of §3 that $\mathcal{M}_{i}$ is defined as
the subset of the previously-offered assortments
$\mathcal{M}\equiv\\{1,\ldots,M\\}$ that offered product $i$. For each subset
of previously-offered assortments $\mathcal{C}\subseteq\mathcal{M}$, let the
products which are offered only in the assortments in $\mathcal{C}$ be denoted
by

$\displaystyle\mathcal{N}(\mathcal{C})$
$\displaystyle\triangleq\left\\{i\in\mathcal{N}_{0}:\mathcal{M}_{i}=\mathcal{C}\right\\}.$

Equipped with the above definitions, we observe that
$\\{\mathcal{N}(\mathcal{C}):\mathcal{C}\subseteq\mathcal{M}\\}$ is the
collection of subsets of products which always appear together in the
previously-offered assortments, and we readily observe that
$|\\{\mathcal{N}(\mathcal{C}):\mathcal{C}\subseteq\mathcal{M}\\}|=2^{M}$.
Therefore,

$\displaystyle|\widehat{\mathcal{S}}|$
$\displaystyle\leq|\widetilde{\mathcal{S}}|\leq\prod_{\mathcal{C}\subseteq\mathcal{M}}\left(\left|\mathcal{N}(\mathcal{C})\right|+1\right)\leq(n+2)^{2^{M}}.$
(22)

Indeed, the first inequality on line (22) holds because the collection of
assortments $\widehat{\mathcal{S}}$ is a subset of the collection of
assortments $\widetilde{\mathcal{S}}$. To see why the second inequality on
line (22) holds, consider any arbitrary subset of previously-offered
assortments $\mathcal{C}\subseteq\mathcal{M}$, and let the products in
$\mathcal{N}(\mathcal{C})$ be indexed in ascending order by revenue; that is,
let the products that comprise $\mathcal{N}(\mathcal{C})$ be denoted by
$i_{1}^{\mathcal{C}},\ldots,i_{|\mathcal{N}(\mathcal{C})|}^{\mathcal{C}}$,
where
$r_{i_{1}^{\mathcal{C}}}<\cdots<r_{i_{|\mathcal{N}(\mathcal{C})|}^{\mathcal{C}}}$.
Then, we observe from the definition of the collection
$\widetilde{\mathcal{S}}$ that every assortment $S\in\widetilde{\mathcal{S}}$
must satisfy the condition
[$\\{i_{j+1}^{\mathcal{C}},\ldots,i_{|\mathcal{N}(\mathcal{C})|}^{\mathcal{C}}\\}\subseteq
S$ and $i_{1}^{\mathcal{C}},\ldots,i_{j}^{\mathcal{C}}\notin S$] for some
$j\in\\{0,\ldots,|\mathcal{N}(\mathcal{C})|\\}$. Since
$\mathcal{C}\subseteq\mathcal{M}$ was chosen arbitrarily, we have shown that

$\widetilde{\mathcal{S}}\subseteq\left\\{\bigcup_{\mathcal{C}\subseteq\mathcal{M}}\mathcal{F}^{\mathcal{C}}:\;\mathcal{F}^{\mathcal{C}}\in\left\\{\emptyset,\left\\{i_{|\mathcal{N}(\mathcal{C})|}^{\mathcal{C}}\right\\},\left\\{i_{|\mathcal{N}(\mathcal{C})|-1}^{\mathcal{C}},i_{|\mathcal{N}(\mathcal{C})|}^{\mathcal{C}}\right\\},\ldots,\left\\{i_{1}^{\mathcal{C}},\ldots,i_{|\mathcal{N}(\mathcal{C})|}^{\mathcal{C}}\right\\}\right\\}\right\\},$

which proves that the second inequality on line (22) holds. The third
inequality on line (22) follows from the fact that
$|\\{\mathcal{N}(\mathcal{C}):\mathcal{C}\subseteq\mathcal{M}\\}|=2^{M}$ and
from the fact that $|\mathcal{N}(\mathcal{C})|\leq n+1$ for every
$\mathcal{C}\subseteq\mathcal{M}$. We have thus proven that
$|\widehat{\mathcal{S}}|$ is at most $(n+2)^{2^{M}}$, which concludes our
proof of Lemma 4.9.

###  12.3 Proof of Lemma 4.10

To construct the set of tuples of products $\mathcal{L}$, we iterate over each
tuple of products $(i_{1},\ldots,i_{M})\in S_{1}\times\cdots\times S_{M}$. For
each such tuple of products, we can construct the corresponding directed graph
$\mathcal{G}_{i_{1}\cdots i_{M}}$ that is described in the beginning of
Appendix 7.2. According to Lemma 7.1 in Appendix 7.2, the tuple of products
$(i_{1},\ldots,i_{M})$ satisfies $(i_{1},\ldots,i_{M})\in\mathcal{L}$ if and
only if the directed graph $\mathcal{G}_{i_{1}\cdots i_{M}}$ is acyclic. We
can check whether a directed graph is acyclic by using the well-known
topological sorting algorithm (Ahuja et al. 1988, p.79). Therefore, our
algorithm for constructing the set of tuples of products $\mathcal{L}$ is to
iterate over each tuple of products $(i_{1},\ldots,i_{M})\in
S_{1}\times\cdots\times S_{M}$ and, for each such tuple of products, to check
whether the tuple of products satisfies $(i_{1},\ldots,i_{M})\in\mathcal{L}$
by performing the topological sorting algorithm on the directed graph
$\mathcal{G}_{i_{1}\cdots i_{M}}$.

The computation time of the above algorithm for constructing $\mathcal{L}$ can
be analyzed as follows. The number of iterations in the algorithm is equal to
$|S_{1}\times\cdots\times S_{M}|=\mathcal{O}(n^{M})$, where we observe that it
is trivial from a computation time analysis to enumerate and iterate over the
tuples of products in $S_{1}\times\cdots\times S_{M}$. For each iteration, we
must construct a directed graph $\mathcal{G}_{i_{1}\cdots i_{M}}$ that has
$n+1=\mathcal{O}(n)$ vertices and
$\sum_{m\in\mathcal{M}}(|S_{m}|+1)=\mathcal{O}(Mn)$ directed edges.
Constructing this directed graph requires examining each product in each of
the assortments $S_{1},\ldots,S_{M}$, and so we can construct
$\mathcal{G}_{i_{1}\cdots i_{M}}$ in $\mathcal{O}(Mn)$ computation time. The
computation time for the topological sort algorithm on a directed graph is
equal to the number of vertices plus the number of directed edges in the
directed graph, and so we can check whether $\mathcal{G}_{i_{1}\cdots i_{M}}$
is acyclic in $\mathcal{O}(n+Mn)=\mathcal{O}(Mn)$ computation time. Therefore,
we have shown that our algorithm for constructing the set of tuples of
products $\mathcal{L}$ requires
$\mathcal{O}\left(n^{M}\times\left(Mn+Mn\right)\right)=\mathcal{O}(Mn^{M+1})$
computation time. We also observe from the inequality
$|\mathcal{L}|\leq|S_{1}\times\cdots\times S_{M}|$ that
$|\mathcal{L}|=\mathcal{O}(n^{M})$, which concludes our proof of Lemma 4.10.

###  12.4 Proof of Lemma 4.11

Consider any assortment $S\in\widehat{\mathcal{S}}$ and any tuple of products
$(i_{1},\ldots,i_{M})\in\mathcal{L}$. To motivate our algorithm for computing
$\rho_{i_{1}\cdots i_{M}}(S)$, we begin by recalling the directed graph
$\mathcal{G}_{i_{1}\cdots i_{M}}$ corresponding to the tuple of products
$(i_{1},\ldots,i_{M})$ that is described in the beginning of Appendix 7.2.
According to Lemma 7.1 in Appendix 7.2, it follows from the fact that
$(i_{1},\ldots,i_{M})\in\mathcal{L}$ that $\mathcal{G}_{i_{1}\cdots i_{M}}$ is
a directed acyclic graph. Moreover, we recall that

$\displaystyle\rho_{i_{1}\cdots i_{M}}(S)$ $\displaystyle=\min_{i\in
S\cap\mathcal{I}_{i_{1}\cdots i_{M}}(S)}r_{i}=\min_{i\in
S:\;i_{m}\nprec_{i_{1}\cdots i_{M}}i\textnormal{ for all }i_{m}\in S}r_{i},$
(23)

where the first equality follows from Proposition 7.11 in Appendix 7.2 and the
second equality follows from Definition 7.10 in Appendix 7.2. We recall from
Definition 7.3 in Appendix 7.2 that the notation $i\nprec_{i_{1}\cdots
i_{M}}j$ means that there is no directed path from vertex $j$ to vertex $i$ in
the graph $\mathcal{G}_{i_{1}\cdots i_{M}}$. Stated in words, line (23) shows
that $\rho_{i_{1}\cdots i_{M}}(S)$ is equal to the minimum revenue $r_{i}$
among all of the vertices $i$ in the directed acyclic graph
$\mathcal{G}_{i_{1}\cdots i_{M}}$ which do not have a directed path to a
vertex $i_{m}$ for any previously-offered assortment $m\in\mathcal{M}$ which
satisfies $i_{m}\in S$.

Based on the above observations, we arrive at the following straightforward
algorithm (presented as Algorithm 4) for computing $\rho_{i_{1}\cdots
i_{M}}(S)$. The algorithm begins on line (1) of Algorithm 4 by constructing
the directed acyclic graph $\mathcal{G}_{i_{1}\cdots i_{M}}$. In particular,
it follows from identical reasoning as in the proof of Lemma 4.10 that
$\mathcal{G}_{i_{1}\cdots i_{M}}$ can be constructed in $\mathcal{O}(Mn)$
computation time and that this graph is comprised of $\mathcal{O}(n)$ vertices
and $\mathcal{O}(Mn)$ directed edges. In line (2) of Algorithm 4, we iterate
over each of the previously offered assortments $m\in\mathcal{M}$ which
satisfy $i_{m}\in S$. For each such previously-offered assortment $m$, we mark
all of the vertices in the graph which have a directed path to vertex $i_{m}$.
Since the graph has $\mathcal{O}(Mn)$ directed edges, and assuming henceforth
that $\mathcal{G}_{i_{1}\cdots i_{M}}$ is stored in memory as an adjacency
list, it is easy to see using a standard graph traversal algorithm like depth-
first search that the loop in line (2) of Algorithm 4 can be performed in a
total of $\mathcal{O}(M\times Mn)=\mathcal{O}(M^{2}n)$ computation time.
Finally, line (3) of Algorithm 4 iterates over all of the vertices in at most
$\mathcal{O}(Mn)$ computation time and outputs the minimum $r_{i}$ among all
of the vertices $i$ which are unmarked. The correctness of Algorithm 4 follows
immediately from our earlier reasoning on line (23), and the total computation
time required for Algorithm 4 is

$\displaystyle\underbrace{\mathcal{O}\left(Mn\right)}_{\eqref{step:construct_rho:1}}+\underbrace{\mathcal{O}\left(M^{2}n\right)}_{\eqref{step:construct_rho:2}}+\underbrace{\mathcal{O}\left(n\right)}_{\eqref{step:construct_rho:3}}=\mathcal{O}(M^{2}n).$

This concludes our proof of Lemma 4.11.

Construct-${{\rho}}(S,(i_{1},\ldots,i_{M}),\mathscr{M},r)$ Inputs: • An
assortment, $S\in\mathcal{S}$. • A tuple of products,
$(i_{1},\ldots,i_{M})\in\mathcal{L}$. • The collection of previously-offered
assortments, $\mathscr{M}\equiv\\{S_{1},\ldots,S_{M}\\}$. • The revenues of
the products, $r\equiv(r_{0},r_{1},\ldots,r_{n})$. Output: • The quantity
$\rho_{i_{1}\cdots i_{M}}(S)$. Procedure: 1. Construct the directed acyclic
graph $\mathcal{G}_{i_{1}\cdots i_{M}}$. 2. For each previously-offered
assortment $m\in\mathcal{M}$: (a) If $i_{m}\in S$: i. Mark each unmarked
vertex in $\mathcal{G}_{i_{1}\cdots i_{M}}$ that has a directed path to vertex
$i_{m}$. 3. Output the minimum $r_{i}$ among all unmarked vertices $i$ in
$\mathcal{G}_{i_{1}\cdots i_{M}}$ and terminate.

Algorithm 4:  A procedure for computing $\rho_{i_{1}\cdots i_{M}}(S)$.

###  12.5 Proof of Theorem 4.7

As described at the beginning of §4.3, we consider a brute-force algorithm for
solving the robust optimization problem (RO) that consists of 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 computation time of this brute-
force algorithm is analyzed as follows. In Lemmas 4.8 and 4.9, we established
that the collection of assortments $\widehat{\mathcal{S}}$ can be constructed
in
$\mathcal{O}(n^{2}(M+|\widehat{\mathcal{S}}|))=\mathcal{O}(n^{2}(M+(n+2)^{2^{M}}))=\mathcal{O}(\textnormal{poly}(n))$
computation time, where the last equality holds for any fixed $M$. In Lemma
4.10, we established that the set of tuples of products $\mathcal{L}$ can be
constructed in $\mathcal{O}(Mn^{M+1})=\mathcal{O}(\textnormal{poly}(n))$
computation time, where the equality holds for any fixed $M$. Our algorithm
performs an iteration for each assortment $S\in\widehat{\mathcal{S}}$, and
thus our algorithm will perform
$|\widehat{\mathcal{S}}|\leq(n+2)^{2^{M}}=\mathcal{O}(\textnormal{poly}(n))$
iterations for any fixed $M$. Given any assortment
$S\in\widehat{\mathcal{S}}$, we established in Lemma 4.11 that the quantities
$\rho_{i_{1}\cdots i_{M}}(S)$ for each $(i_{1},\ldots,i_{M})\in\mathcal{L}$
can all be computed in a total of $\mathcal{O}(|\mathcal{L}|\times
M^{2}n)=\mathcal{O}(n^{M}\times M^{2}n)=\mathcal{O}(\textnormal{poly}(n))$
computation time, where the last equality holds for any fixed $M$. Given the
set of tuples of products $\mathcal{L}$ and the quantities $\rho_{i_{1}\cdots
i_{M}}(S)$ for each $(i_{1},\ldots,i_{M})\in\mathcal{L}$, we established in
Remark 3.7 that we can compute the worst-case expected revenue
$\min_{\lambda\in\mathcal{U}}\mathscr{R}^{\lambda}(S)$ by constructing and
solving a linear optimization problem with
$\mathcal{O}(n^{M})=\mathcal{O}(\textnormal{poly}(n))$ decision variables and
$\mathcal{O}(nM)=\mathcal{O}(\textnormal{poly}(n))$ constraints for any fixed
$M$. Since linear optimization can be solved in weakly polynomial time via the
ellipsoid algorithm, we conclude that each iteration of our algorithm requires
$\mathcal{O}(\textnormal{poly}(n))$ time for any fixed $M$. Our proof of
Theorem 4.7 is thus complete.

##  13 Proof of Theorem 5.3

Our proof of Theorem 5.3 is split into several steps. We will begin by
choosing any arbitrary $\bar{S}\in\widehat{\mathcal{S}}$ and, for that
assortment, we will define a particular realization of the historical data
$v\equiv(v_{m,i}:m\in\mathcal{M},i\in S_{m})$. We will then prove in Lemma
13.1 in Appendix 13.2 for that realization of the historical data that the
corresponding set of feasible solutions for the linear optimization problem
(1) is a singleton. By showing that the realization of the historical data
generates a unique feasible solution for the linear optimization problem (1),
we conclude in Appendix 13.3 by showing that $\bar{S}$ is the unique optimal
solution of the robust optimization problem (RO).

###  13.1 Assumptions and Notation

Following the statement of Theorem 5.3, we will assume throughout Appendix 13
that $\mathscr{M}=\tilde{\mathcal{S}}$, that $\eta=0$, and that the revenues
$r_{1}<\cdots<r_{n}$ are fixed. We observe that Theorem 5.3 trivially holds in
the case where $n=1$; therefore, we assume throughout the rest of Appendix 13
that the number of products satisfies $n\geq 2$.151515Suppose the number of
products satisfies $n=1$. In that case, we observe that
$\tilde{\mathcal{S}}=\\{\\{0,1\\}\\}$. Since $\tilde{\mathcal{S}}$ is a
singleton, Theorem 5.3 follows immediately from Theorem 3.1.

We will make use of the following notation and preliminary results throughout
Appendix 13. First, it follows from the fact that
$\mathscr{M}=\tilde{\mathcal{S}}$ and from Definition 3.3 that the set of
tuples $\mathcal{L}$ can be represented compactly as161616A formal proof of
the equality on line (24) can be found as Lemma 5.4 in §5.2.

$\displaystyle\mathcal{L}=\left\\{(i_{1},\ldots,i_{n}):i_{1}\in\\{0,n\\}\text{
and }i_{j+1}\in\\{j,i_{j}\\}\text{ for all }j\in\\{1,\ldots,n-1\\}\right\\}.$
(24)

Second, for each $j\in\\{1,\ldots,n-1\\}$, we define the indices

$\displaystyle\text{\@text@baccent{$i$}}^{j}_{1}=\cdots=\text{\@text@baccent{$i$}}^{j}_{j}=0,\quad\text{\@text@baccent{$i$}}^{j}_{j+1}=\cdots=\text{\@text@baccent{$i$}}^{j}_{n}=j,$
$\displaystyle\bar{i}^{j}_{1}=\cdots=\bar{i}^{j}_{j}=n,\quad\bar{i}^{j}_{j+1}=\cdots=\bar{i}^{j}_{n}=j,$

and we denote the tuples constructed from those indices by

$\displaystyle\left(\text{\@text@baccent{$i$}}^{j}_{1},\ldots,\text{\@text@baccent{$i$}}^{j}_{n}\right)\triangleq(0,\ldots,0,j,\ldots,j)\textnormal{
and
}\left(\bar{i}^{j}_{1},\ldots,\bar{i}^{j}_{n}\right)\triangleq(n,\ldots,n,j,\ldots,j).$

Finally, it follows from the fact that $\eta=0$ that the constraints of the
linear optimization problem (1) can be written compactly as

$\displaystyle\sum_{(i_{1},\ldots,i_{n})\in\mathcal{L}:i_{m}=i}\lambda_{i_{1}\cdots
i_{n}}=v_{m,i}$ $\displaystyle\forall m\in\mathcal{M},\;i\in S_{m}$ (25)
$\displaystyle\sum_{(i_{1},\ldots,i_{n})\in\mathcal{L}}\lambda_{i_{1}\cdots
i_{n}}=1$ $\displaystyle\lambda_{i_{1}\cdots i_{n}}\geq 0$
$\displaystyle\forall(i_{1},\ldots,i_{n})\in\mathcal{L},$

where we restate for the sake of convenience that
$S_{m}\equiv\\{0,1,\ldots,m-1,n\\}$ and $\mathcal{M}\equiv\\{1,\ldots,n\\}$.

###  13.2 Construction of historical data for any given
$\bar{S}\in\widehat{\mathcal{S}}$, and proof that the corresponding system
(25) has a unique solution

In view of the strategy outlined at the beginning of Appendix 13, we now
present the details of the proof of Theorem 5.3. Indeed, consider any
arbitrary assortment $\bar{S}\in\widehat{\mathcal{S}}$. For that assortment,
we define the realization of the historical data $v_{m,i}$ for each past
assortment $m\in\mathcal{M}\equiv\\{1,\ldots,n\\}$ and each product $i\in
S_{m}$ as follows:

$\displaystyle
v_{m,i}\triangleq\begin{cases}\frac{1}{n}\left(1+\left|\left\\{m,\ldots,n-1\right\\}\setminus\bar{S}\right|\right),&\text{if
}i=n,\\\
\frac{1}{n}\left|\left\\{m,\ldots,n-1\right\\}\cap\bar{S}\right|,&\text{if
}i=0,\\\ \frac{1}{n},&\text{otherwise}.\end{cases}$ (26)

With the realization of the historical data from line (26) corresponding to
the assortment $\bar{S}$, the remainder of Appendix 13.2 is dedicated to
proving the following lemma:

###### Lemma 13.1

The system (25) is nonempty and has a unique solution $\lambda$ which
satisfies the following equality for each
$(i_{1},\ldots,i_{n})\in\mathcal{L}$:

$\displaystyle\lambda_{i_{1}\cdots i_{n}}$
$\displaystyle=\begin{cases}\frac{1}{n},&\textnormal{if there exists
}j\in\bar{S}\setminus\\{0,n\\}\textnormal{ such that
}(i_{1},\ldots,i_{n})=\left(\text{\@text@baccent{$i$}}^{j}_{1},\ldots,\text{\@text@baccent{$i$}}^{j}_{n}\right),\\\
\frac{1}{n},&\textnormal{if there exists
}j\in\mathcal{N}\setminus\bar{S}\textnormal{ such that
}(i_{1},\ldots,i_{n})=\left(\bar{i}^{j}_{1},\ldots,\bar{i}^{j}_{n}\right),\\\
\frac{1}{n},&\textnormal{if }(i_{1},\ldots,i_{n})=(n,\ldots,n),\\\
0,&\textnormal{otherwise}.\end{cases}$ (27)

Stated in words, the above Lemma 13.1 establishes that the vector $\lambda$
defined by line (27) is the unique feasible solution for the linear
optimization problem (1) under the assumptions that the previously-offered
assortments are $\mathscr{M}=\tilde{\mathcal{S}}$, that $\eta=0$, and that the
realization of the historical data satisfies (26).

Let us provide an interpretation of the vector $\lambda$ defined by line (27).
Speaking informally, the vector $\lambda$ is comprised of three types of
customers. The first type of customers are denoted by the tuples
$\left(\text{\@text@baccent{$i$}}^{j}_{1},\ldots,\text{\@text@baccent{$i$}}^{j}_{n}\right)$
for each $j\in\bar{S}\setminus\\{0,n\\}$, and these are customers that prefer
product $j$ and, if that product is unavailable, will not make a purchase. The
second type of customers are denoted by the tuples
$\left(\bar{i}^{j}_{1},\ldots,\bar{i}^{j}_{n}\right)$ for each
$j\in\mathcal{N}\setminus\bar{S}$, and these are customers whose most
preferred product is $j$, whose second-most preferred product is $n$, and will
not purchase a product if neither $j$ nor $n$ are available. The third type of
customers are denoted by the tuple $(n,\ldots,n)$, and these are customers
that will purchase product $n$ if it is available, and will otherwise not make
a purchase. In Appendix 13.3, we will use Lemma 13.1 to prove Theorem 5.3.

Our proof of Lemma 13.1 makes use of two intermediary claims, denoted below as
Claims 9 and 10. These intermediary claims establish that any feasible
solution of the system (25) must satisfy certain structural properties. We
first present these two intermediary claims, followed by the proof of Lemma
13.1.

###### Claim 9

Suppose that $\lambda$ is a feasible solution of the system (25), and let
$(i_{1},\ldots,i_{n})\in\mathcal{L}$. If $\lambda_{i_{1}\cdots i_{n}}>0$, then
either $(i_{1},\ldots,i_{n})=(n,\ldots,n)$ or there exists
$j\in\\{1,\ldots,n-1\\}$ such that $i_{j+1}=j$.

###### Proof 13.2

Proof of Claim 9. Suppose that $\lambda$ is a solution of the system (25), and
let $(i_{1},\ldots,i_{n})\in\mathcal{L}$.

We begin by showing that if $\lambda_{i_{1}\cdots i_{n}}>0$, then either
$(i_{1},\ldots,i_{n})=(n,\ldots,n)$ or there exists $m\in\\{1,\ldots,n\\}$
such that $i_{m}\notin\\{0,n\\}$. We will show this claim by proving its
contraposition. Indeed, suppose that $i_{m}\in\\{0,n\\}$ for all
$m\in\\{1,\ldots,n\\}$ and that there exists $\bar{m}\in\\{1,\ldots,n\\}$ such
that $i_{\bar{m}}=0$. In this case, it follows from (24) and from the fact
that $i_{m}\in\\{0,n\\}$ for all $m\in\\{1,\ldots,n\\}$ that
$i_{1}=\cdots=i_{n}=0$. If $i_{1}=\cdots=i_{n}=0$, then

$\displaystyle\lambda_{i_{1}\cdots
i_{n}}=\sum_{(i_{1}^{\prime},\ldots,i_{n}^{\prime})\in\mathcal{L}:i_{n}^{\prime}=0}\lambda_{i_{1}^{\prime}\cdots
i_{n}^{\prime}}=v_{n,0}=0,$

where the first equality follows from (24), the second equality follows from
the fact that $\lambda$ is a feasible solution of the system (25), and the
third equality follows from (26). We have thus shown that if
$i_{m}\in\\{0,n\\}$ for all $m\in\\{1,\ldots,n\\}$ and if there exists
$m\in\\{1,\ldots,n\\}$ such that $i_{m}=0$, then $\lambda_{i_{1}\cdots
i_{n}}=0$. Note that the contrapositive of this statement is that if
$\lambda_{i_{1}\cdots i_{n}}>0$, then either
$(i_{1},\ldots,i_{n})=(n,\ldots,n)$ or there exists $m\in\\{1,\ldots,n\\}$
such that $i_{m}\notin\\{0,n\\}$.

We conclude the proof of Claim 9 by showing that if there exists
$m\in\\{1,\ldots,n\\}$ such that $i_{m}\notin\\{0,n\\}$, then there exists