发表在 Operations Research, 2010. DOI: https://doi.org/10.1287/opre.1100.0866.
Subject classfications: assortment optimization; multinomial logit choice model; capacity constraint.
Area of review: Revenue Management.
这篇文章讲述在有 capacity constraint 的情况下如何求解 MNL 的 optimal assortment，讨论了静态和动态的问题。
In the static problem, we assume that the parameters of the logit model are known in advance; we then develop a simple algorithm for computing a profit-maximizing assortment based on the geometry of lines in the plane and derive structural properties of the optimal assortment.
For the dynamic problem, the parameters of the logit model are unknown and must be estimated from data. By exploiting the structural properties found for the static problem, we develop an adaptive policy that learns the unknown parameters from past data and at the same time optimizes the profit.
在经典的 MNL 模型下，给定组合 $S \subseteq \{1, 2, \dots, N\}$，顾客选择商品 $i \in S$ 的概率为：
$$ \theta_{i}(S)= \begin{cases}v_{i} /\left(1+\sum_{k \in S} v_{k}\right), & \text { if } i \in S \cup\{0\} \\ 0, & \text { otherwise }\end{cases} $$
期望利润为：
$$ f(S)=\sum_{i \in S} w_{i} \theta_{i}(S)=\frac{\sum_{i \in S} w_{i} v_{i}}{1+\sum_{i \in S} v_{i}} $$
在可选商品的数量有限的条件下，利润最大化的优化问题可表达为：
$$ Z^{\ast}=\max \{f(S): S \subseteq\{1, \ldots, N\} \text { and }|S| \leqslant C\} \tag{1} $$
Static Optimization
对于静态的问题，$v_i$ 事先已知，所以这是一个组合优化问题。
文章首先给出一个反例证明 revenue-ordered assortment 不能给出最优解，然后提出了一个非递归的算法 STATICMNL。
式(1)等价于：
$$ \begin{aligned} \max_{S \subseteq N, \lambda} & \; \lambda \\ \text{s.t. } & |S| \leqslant C \\ & \frac{\sum_{i \in S} w_{i} v_{i}}{1+\sum_{i \in S} v_{i}} = \lambda \end{aligned} $$
也即：
$$ \begin{aligned} \max_{S \subseteq N, \lambda} & \; \sum_{i \in S} (w_i - \lambda) v_i \\ \text{s.t. } & |S|\leqslant C \\ \end{aligned} $$
这意味着，我们要找使得 $\lambda = \displaystyle\max_{|S| \leqslant C} \sum_{i \in S} (w_i - \lambda) v_i$ 成立的 $\lambda$。
记
$$ A(\lambda)=\underset{X:|X| \leqslant C}{\arg \max } \sum_{i \in X} v_{i}\left(w_{i}-\lambda\right) $$
那么最优值就是 $\max \{f(A(\lambda)) \mid \lambda \in \mathrm{R}\}$，但是并不需要遍历所有的实数。
记
$$ \begin{aligned} &h_{0}(\lambda)=0 \quad \text { and } \\ &h_{i}(\lambda)=v_{i}\left(w_{i}-\lambda\right), \quad \text { for } i=1, \ldots, N \end{aligned} $$
这 $N + 1$ 条直线有 $O(N^2)$ 个交点，遍历 $A(\lambda)$ 只要在这些交点中枚举即可。
THEOREM 2.4 (SENSITIVITY OF THE OPTIMAL ASSORTMENT). The output of the STATICMNL algorithm depends only on the ordering $\boldsymbol{}{\sigma}^{0}$ of the customer preference weights $v_{i}$ and the ordering $\boldsymbol{\tau}$ of the intersection points $\mathscr{I}(i, j)$.
Dynamic Optimization
文章用 regret 衡量算法的表现。记随机变量 $X_t(S)$ 和 $Y_t(S)$ 分别表示顾客的选择和利润。其中：
$$ P\left\{X_{t}(S)=i\right\}=\theta_{i}(S)=\frac{v_{i}}{1+\sum_{k \in S} v_{k}}, \quad Y_{t}(S)=w_{X_{t}(S)} $$
并且
$$ \mathrm{E}[Y_t(S)] = f(S) $$
算法：根据历史信息选取一个 assortment
$$ \psi_{t}: \mathscr{H}_{t-1} \rightarrow\{S \subseteq\{1, \ldots, N\}:|S| \leqslant C\} $$
$T$ 时刻的累积 regret 是：
$$ \operatorname{Regret}(T, \psi)=\sum_{t=1}^{T} \mathrm{E}\left[Z^{\ast}-Y_{t}\left(S_{t}\right)\right]=\sum_{t=1}^{T} \mathrm{E}\left[Z^{\ast}-f\left(S_{t}\right)\right] $$
对于动态的问题，$v_i$ 只能从 past sales and assortment decisions 推断出来。但是，根据上一部分提出的算法，真正重要的是 customer preference 和 intersection points。
文章提出了一个算法，叫做 Adaptive Assortment (AA)。算法的每个循环都包含一个 exploration phase，以及随后的 exploitation phase。
令 $\mathscr{E} = \{S \mid \{i, j\} \subseteq S, |S| = C\}$，在第 $m$ 个 exporation 阶段，可以根据顾客的选择信息得到 $\hat{\Theta}_i (m, S)$，顾客选择商品 $i$ 的近似概率，并由此估计出 customer preference 和 intersection points，文章进一步还证明了这样得到的 sequence of assortments ${\hat{\mathscr{A}}(m)}$ 与真实的 $\mathscr{A}(m)$ 有着足够高的概率是一样的。
AA 算法的 regret 是：
$$ \operatorname{Regret}(T, A A) \leqslant a_{2} N^{2} \log ^{2} T $$
Numerical Experiments
这一部分，文章以一个 DVD 零售商在 2005 年一段时间的销售数据检验了前面两个算法的有效性。分为 static optimization 和 dynamic optimization 两个部分。
Extensions and Future Work
文章指出，上面的模型没有考虑到顾客的异质性 (heterogeneity)。同时 MNL 有 IIA 的缺点。