参考文献：Discrete Choice Models and Applications in Operations Management. In INFORMS TutORials in Operations Research. https://doi.org/10.1287/educ.2021.0229
Discrete Choice Models
离散选择模型关注决策者如何在多个备选方案中做出选择，已成为研究消费者面对多种产品的购买行为的重要工具，并已广泛应用于经济、营销、交通和运营等多个领域。
经典的选择模型大都建立在 RUM (random utility maximization) framework 上，假设理性的消费者会选择对他来说效用最高的商品。
Luce Model
当对消费者选择进行建模时，我们往往会要求模型满足 regularity condition: The choice probability for any product in the offer set decreases as the offer set enlarges.
记 $q_i(S)$ 为选择 item $i \in S$ 的概率
Luce 引入了 choice axiom $$ q_i(S) = q_{S^\prime}(S) \cdot q_i (S^\prime) \quad \forall i \in S^\prime \subseteq S $$ 选择公理把选择一件商品分成了两步。
Luce 证明了满足 choice axiom 的 $q$ 一定有如下形式：
$$ q_{i}(S)= \frac{a_{i}}{\sum_{j \in S} a_{j}} $$
上式也满足正则性条件。
RUM framework
RUM framework 假设顾客会选择效用最高的商品，效用是随机的：
$$ U_i = u_i + \xi_i $$
其中 $u_i$ 是常数，$\xi_i$ 是 i.i.d. 参数为 $\mu$ 的 Gumbel 随机变量。
$F_{\xi_i}(x)=\mathrm{P}\left(\xi_{i} \leq x\right)=\exp (-\exp (-(x / \mu+\gamma)))$，其中 $\gamma$ 是欧拉常数。
这时候就有：
$$ q_{i}(S)=\operatorname{Pr}\left(U_{i} \geq U_{j}, \forall j \in S, j \neq i\right), \text { for any } i \in S $$
在这样一套理论框架下，Holman and Marley 给出了 multinominal logit 模型
$$ q_{i}(S)=\frac{\exp \left(u_{i} / \mu\right)}{\sum_{j \in S} \exp \left(u_{j} / \mu\right)}, \text { for any } i \in S $$
容易看出 MNL 模型和 Luce 模型的等价性。
RUM framework 下消费者剩余可以定义为最大效用的期望： $$ E\left[\max _{k \in S} U_k\right]=u(S)=\mu \log \left(\sum_{k \in S} \exp \left(u_k / \mu\right)\right) $$ 但是，MNL/Luce 模型有一个局限性，那就是不能描述具有相关性商品的选择概率。问题就出现在它满足 IIA 这个性质。
IIA: independence of irrelevant alternatives.
The basic idea of IIA is that the ratio of any two products' shares should be independent of all other products.
“red bus/blue bus” paradox
{red bus, car} vs {red bus, blue bus, car}
假设市场上有 cars 和 red buses 两种商品，各占50%市场份额，现在增加 blue buses 这种商品，它的效用跟 red buses 是一样的，MNL 模型会把 cars 的份额调低成 33%，但这很明显是不符合实际的。
定义 Substitution Effect
The choice probability decreases as any other alternative becomes more appealing.
MNL 也满足 substitution effect.
Nested Logit Model
NL 将商品的相关性加入到 MNL 中。假设所有的商品可以被分为 $m$ 组，记为 $N_i, \, (i=1, 2, \dots, m)$ 。$N_i$ 的第 $j$ 个商品的 random utility 表示为： $$ U_{ij} = u_{ij} + \xi_{ij} + \xi_{i} $$ $\xi_{ij}$ 是 i.i.d 的 Gumbel 随机变量，参数为 $\mu_{2i}$ ; $\xi_{i}$ 是 i.i.d 的随机变量，使得 $\xi_{ij} + \xi_{i}$ 服从参数为 $\mu_1\geq \mu_{2i}$ 的 Gumbel 随机变量。
对 $j\in N_{i}, \, i \in [m]$，选择的概率 $q_{ij}$ 是 $$ q_{i j}\left(\left(S_i\right)_{i \in M}\right)=\frac{\left(\sum_{j \in S_i} \exp \left(u_{i j} / \mu_{2 i}\right)\right)^{\mu_{2 i} / \mu_1}}{\sum_{i^{\prime} \in M}\left(\sum_{j^{\prime} \in S_{i^{\prime}}} \exp \left(u_{i^{\prime} j^{\prime}} / \mu_{2 i^{\prime}}\right)\right)^{\mu_{2 i^{\prime}} / \mu_1}} \cdot \frac{\exp \left(u_{i j} / \mu_{2 i}\right)}{\sum_{j^{\prime} \in S_i} \exp \left(u_{i j^{\prime}} / \mu_{2 i}\right)} . $$
MNL with Network Effects
一个人的购买行为会受到身边的人的影响；当一个产品市场份额增大的时候，可能会受到消费者更加青睐。
Other Discrete Choice Models
Markov Choice Model
Threshold Effect
Threshold Luce (T-Luce) Model: for offer set $S$, the choice probability for $i \in S$ is defined as follows: $$ q_i(S)= \begin{cases}\frac{a_i}{\sum_{j \in \Psi(S)} a_j}, & i \in \Psi(S), \\ 0, & i \notin \Psi(S),\end{cases} $$ where $\Psi(S)=\left\{j \in S:(1+\gamma) a_j \geq a_i, \forall i \in S^{+}\right\}, a_i=\exp \left(\alpha_i-\beta p_i\right)$ and $S^{+}:=S \cup\{0\}$, "0" denotes the no purchase or outside option.
Pricing Optimization
价格影响顾客选择商品的概率，假定效用关于价格是线性的： $$ u_i = \alpha_i - \beta_i p_i $$ 并令 no-purchase option $a_0=1$，这时候的选择模型： $$ q_{i}\left(S^{+}, \mathbf{p}\right)=\frac{\exp \left(\alpha_{i}-\beta_{i} p_{i}\right)}{1+\sum_{j \in S} \exp \left(\alpha_{j}-\beta_{j} p_{j}\right)}, \quad \forall i \in S, \quad (S^+ = S \cup \{0\})\quad $$ 以最大化期望收益为目标，多产品定价优化问题可表示为：
$$ \max _{\mathbf{p}} R(S, \mathbf{p}):=\sum_{i \in S}\left(p_{i}-c_{i}\right) \cdot q_{i}\left(S^{+}, \mathbf{p}\right) $$
Assortment Optimization
另一种零售策略，如果商品的价格是给定的，商家只能调整展示给顾客的商品种类。
这时候的优化目标变为： $$ \max _{S \subseteq N} R(S):=\sum_{i \in S}\left(p_{i}-c_{i}\right) \cdot q_{i}\left(S^{+}\right) $$
Revenue-Ordered Assortment
假定商品索引按利润排序，即 $p_{1}-c_{1} \geq p_{2}-c_{2} \geq \cdots \geq p_{n}-c_{n}$，则 $S_i = \{1, 2, \dots, i\}, i = 1, \dots n$ 被称为 revenue-ordered assortment
对 MNL 模型来说，最优的 assortment 在 revenue-ordered assortments 中取到。时间复杂度是 $O(n)$。
Estimation
这一部分介绍如何估计参数。
设在情景 $k$ 下，商品集为 $S_k$，对于商品 $i \in S_{k}^{+}$，它有一个向量 $\mathbf{x}_{ki}$ 来编码它的一些特征，我们引入向量 $\mathbf{v}$ 作为参数，用线性模型 $\mathbf{v}^T \mathbf{x}_{ki}$ 来表示商品 $i$ 的效用。记 $q_{ki}(\mathbf{v})$ 是选择商品 $i$ 的概率，整个模型的对数似然函数就是： $$ \mathcal{L L}\left(\mathbf{n}, \mathbf{n}_0 \mid \mathbf{v}\right)=\sum_{k=1}^K \sum_{i \in S_k^{+}} n_{k i} \cdot \log \left(q_{k i}(\mathbf{v})\right) $$ 这里把常数 $C=\sum_{k=1}^K \log \left(\left(n_k+n_{k 0}\right) !\right)-\sum_{k=1}^K \sum_{i \in S_k^{+}} \log \left(n_{k i} !\right)$ 给省略了。
Estimation of MNL Model
在 MNL 模型下，对数似然函数是： $$ \mathcal{L L}\left(\mathbf{n}, \mathbf{n}_0 \mid \mathbf{v}\right)=\sum_{k=1}^K \sum_{i \in S_k} n_{k i} \cdot\left[\mathbf{v}^T \cdot \mathbf{x}_{k i}-\log \left(\sum_{i \in S_k} \exp \left(\mathbf{v}^T \cdot \mathbf{x}_{k i}\right)\right)\right] $$ 可以证明 $\mathcal{L L}\left(\mathbf{n}, \mathbf{n}_0 \mid \mathbf{v}\right)$ 是 $\mathbf{v}$ 的凹函数。
Constrained Assortment Optimization
当可以展示的商品数量是有限的的情况下，问题变成： $$ \begin{array}{ll} \max\limits_{S \subseteq N} & R(S):=\displaystyle\sum_{i \in S}\left(p_{i}-c_{i}\right) \cdot \frac{a_{i}}{1+\sum_{j \in S} a_{j}} \\ \text { s.t. } & |S| \leq C \end{array} $$
更进一步地，如果商品种类和价格都是可以变化的，这时商家面临 Joint Assortment and Price Optimization。
Extensions
Multinomial Logit Model with Impatient Customers
这部分来自于文章《Assortment Optimization and Pricing Under the Multinomial Logit Model with Impatient Customers: Sequential Recommendation and Selection》。
…, but it is clear that, in many cases, the customers incrementally view the assortment of offered products and make a purchase decision before viewing all the offered products.
文章考虑到了一点，比方说，当消费者在浏览手机里的商品时，他可能没有耐心把平台推荐的商品全部看完，可能只刷新了两页就不看了，这就是一个 impatient customer。
在模型上，文章假设商品集 $\mathcal{N}=\{1, \dots, n\}$，阶段 $\mathcal{M} = \{1, \dots, m\}$；在第 $k \in [m]$ 阶段，顾客都能浏览到商品集 $S_k \subseteq \mathcal{N}$，且 $S_k \cap S_\ell = \emptyset \; (k \neq \ell)$。顾客的 patience level 是一个随机变量 $Y$，令 $\lambda_k =\mathbb{P}(Y \geq k)$。
商品的效用沿用 RUM，假定消费者处于阶段 $k$，如果效用最大的那件商品的效用高于商品0（outside option），那么消费者购买这件商品；否则进入阶段 $k+1$。如果 $k+1$ 超过了该消费者的 patience level，则消费者离开。
记 $\phi_i^k\left(S_1, \ldots, S_m\right)$ 为消费者选择商品 $i \in S_k$ 的概率，以 $V(S) = \sum_{i \in S} v_i$，文章的定理2.1给出了选择概率：
$$ \phi_i^k\left(S_1, \ldots, S_m\right) =\frac{\lambda_k v_i}{\left(1+\sum_{\ell=1}^{k-1} V\left(S_{\ell}\right)\right)\left(1+\sum_{\ell=1}^k V\left(S_{\ell}\right)\right)} $$
接下来文章介绍了如何对这种选择模型进行 assortment 和 pricing 的优化。
Unconstrained Assortment Optimization
记 $r_i$ 是商品 $i$ 的利润，$W(S)=\sum_{i\in S} r_i v_i$，利润函数是 $$ \begin{aligned} \Pi \left(S_1, \ldots, S_m\right) & =\sum_{k \in \mathcal{M}} \sum_{i \in S_k} \frac{\lambda_k r_i v_i}{\left(1+\sum_{\ell=1}^{k-1} V\left(S_{\ell}\right)\right)\left(1+\sum_{\ell=1}^k V\left(S_{\ell}\right)\right)} \\ & =\sum_{k \in \mathcal{M}} \frac{\lambda_k W\left(S_k\right)}{\left(1+\sum_{\ell=1}^{k-1} V\left(S_{\ell}\right)\right)\left(1+\sum_{\ell=1}^k V\left(S_{\ell}\right)\right)} \end{aligned} $$ 对于无约束的 assortment，文章证明了存在某个 revenue-ordered 解是最优的，并设计了一个动态规划算法，其复杂度为 $O(mn^2)$ .
Joint Pricing and Assortment Optimization
在经典的假设下，利润函数是 $$ \Pi(\boldsymbol{p}) =\sum_{k \in \mathcal{M}} \sum_{i \in S_k} p_i \phi_i^k(\boldsymbol{p}) =\sum_{k \in \mathcal{M}} \frac{\lambda_k \sum_{i \in S_k} p_i e^{\alpha_i-\beta p_i}}{\left(1+\sum_{\ell=1}^{k-1} V_{\ell}(\boldsymbol{p})\right)\left(1+\sum_{\ell=1}^k V_{\ell}(\boldsymbol{p})\right)} $$
Assortment Optimization Under a Space Constraint
在这一部分，文章加入了 assortment 的空间约束。
Computational Experiments
Summary
总的来说，对于 discrete choice model 的研究主要分为以下两块：
- 如何从数据中拟合出一个好的选择模型
- 给定一类选择模型，如何设计高效的算法解决 pricing / assortment 等问题
The Red-Bus/Blue-Bus Problem
While choice simulators have proven eminently useful for simulating buyer behavior, one of the most common simulation models (the Logit or Share of Preference model) has displayed a problematic result often described as the Red-Bus/Blue-Bus problem. The underlying property leading to this problem is termed IIA, which is shorthand for "Independence from Irrelevant Alternatives." The basic idea of IIA is that the ratio of any two products' shares should be independent of all other products. This sounds like a good thing, and at first, IIA was regarded as a beneficial property.
However, another way to say the same thing is that an improved product gains share from all other products in proportion to their original shares; and when a product loses share, it loses to others in proportion to their shares. Stated that way, it is easy to see that IIA implies an unrealistically simple model. In the real world, products compete unequally with one another and when an existing product is improved, it usually gains most from a subset of products with which it competes most directly.
Imagine a transportation market with two products, cars and red buses, each having a market share of 50%. Suppose we add a second bus, colored blue. An IIA simulator would predict that the blue bus would take share equally from the car and red bus, so that the total bus share would become 67%. But it's clearly more reasonable to expect that the blue bus would take share mostly from the red bus, and that total bus share would remain close to 50%.
It is important to note that some degree of IIA is appropriate and useful within market simulations. In many markets, there is some degree of randomness to buyer behavior. It is not that people are irrational, but that buyers must balance the costs of making a utility maximizing decision against the costs of taking the time to make perfect decisions. It is quite reasonable for rational buyers to make what on the surface may seem as haphazard decisions — especially for low-involvement purchases. A similar or even duplicate offering could thus be expected to capture more share in the real world than a rational simulation model might suggest.
In general, market simulation models based on disaggregate models of preference (utilities estimated at the individual level) are less subject to IIA difficulties than aggregate models of preference (aggregate logit, as offered by our CBC System). However, IIA issues are worse as more product alternatives are added to the market simulation.
In addition to modeling respondent preferences at the individual level, there are market simulation methods (such as Randomized First Choice, First Choice, and Share of Preference with Top N setting) that help deal with IIA. These are described in the next sections.
https://sawtoothsoftware.com/help/lighthouse-studio/manual/hid_thered-bus.html