  Due to numerous applications in retail and (online) advertising the problem
of assortment selection has been widely studied under many combinations of
discrete choice models and feasibility constraints. In many situations,
however, an assortment of products has to be constructed gradually and without
accurate knowledge of all possible alternatives; in such cases, existing
offline approaches become inapplicable. We consider a stochastic variant of the
assortment selection problem, where the parameters that determine the revenue
and (relative) demand of each item are jointly drawn from some known
item-specific distribution. The items are observed sequentially in an arbitrary
and unknown order; upon observing the realized parameters of each item, the
decision-maker decides irrevocably whether to include it in the constructed
assortment, or forfeit it forever. The objective is to maximize the expected
total revenue of the constructed assortment, relative to that of an offline
algorithm which foresees all the parameter realizations and computes the
optimal assortment. We provide simple threshold-based online policies for the
unconstrained and cardinality-constrained versions of the problem under a
natural class of substitutable choice models; as we show, our policies are
(worst-case) optimal under the celebrated Multinomial Logit choice model. We
extend our results to the case of knapsack constraints and discuss interesting
connections to the Prophet Inequality problem, which is already subsumed by our
setting.
