发表在 Operations Research, 2016. DOI: https://doi.org/10.1287/opre.2016.1505.
Keywords: choice modeling; assortment optimization; model selection.
Subject classifications: probability: stochastic model applications; queues: Markovian.
Area of review: Operations and Supply Chain.
选择模型 (customer choice model) 是一个在经济学和管理学很重要的一个理论。围绕它有两个研究主题：
- 如何建立一个恰当的模型来刻画人们的选择行为
- 在给出模型时，如何有效地计算和优化 (如，assortment)
这篇文章提出了一个用 Markov chain 对顾客的选择行为进行建模的方式，并给出了一个多项式时间内解决 assortment optimization 的方法。
Markov Chain based Choice Model
记商品集 $\mathcal{N} = \{1, 2, \dots, N\}, \mathcal{N}_{+} = \mathcal{N} \cup \{0\}$.
$S_+ = S \cup \{0\}, S \subseteq \mathcal{N}$，$\pi(i, S)$ 表示在 $S_+$ 中选择商品 $i$ 的概率。
考虑用 Markov chain $\mathcal{M}$ 来模拟顾客选择的行为。$\mathcal{M}$ 有 $N + 1$ 个状态，分别对应 $\mathcal{N}_{+}$，初始的概率分布为 $\vec{\lambda} = (\pi(0, \mathcal{N}), \dots, \pi(N, \mathcal{N}))$ .
给定组合 $S$ ，customer 的选择过程如下：
首先，一个顾客以 $\vec{\lambda}$ 为概率分布选择一个商品 $i$，如果 $i \in S$，那么顾客选择它。否则以概率 $\rho_{ij}$ 转移到另一个状态 $j \neq i$，转移概率如下：
$$ \rho_{i j}= \begin{cases}1, & \text { if } i=0, j=0 \\ \displaystyle\frac{\pi(j, \mathcal{N} \backslash\{i\})-\pi(j, \mathcal{N})}{\pi(i, \mathcal{N})}, & \text { if } i \in \mathcal{N}, j \in \mathcal{N}_{+}, i \neq j \\ 0, & \text { otherwise }\end{cases} $$
文章接下来列举了一些选择模型的 Markov 近似。
Multinomial logit (MNL) model
对于参数为 $u_0, \dots, u_N\; (\sum u_i = 1)$ 的 MNL 模型，初始状态分布和转移概率是：
$$ \begin{aligned} \lambda_{i} &=\pi(i, \mathcal{N})=u_{i} \\ \rho_{i j} &=\frac{\pi(j, \mathcal{N} \backslash\{i\})-\pi(j, \mathcal{N})}{\pi(i, \mathcal{N})}=\frac{u_{j}}{1-u_{i}} \end{aligned} $$
Generalized attraction model (GAM)
$$ \pi(j, S)=\frac{u_{j}}{u_{0}+\sum_{i \notin S} v_{i}+\sum_{i \in S} u_{i}} $$
文章后面证明了这种近似对于 MNL 和 GAM 是精确的。
接着，文章说明了如何从 Markov chain 中解构出一个选择模型。
文章的第三章证明了 GAM 可以被 Markov chain 精确表示，并揭示了这类转移概率矩阵是秩1的。
The proof of Theorem 3.1 shows that GAM can be represented exactly by a Markov chain where the transition submatrix over states $\mathcal{N}$ is a rank one matrix.
在第四章，文章给出了 Markov chain 近似任意一个选择模型的 bound。
$$ \left(1-\alpha(\bar{S})^{2}\right) \cdot \pi(j, S) \leqslant \hat{\pi}(j, S) \leqslant\left(1+\frac{\tau(\bar{S}) \cdot \alpha(\bar{S})}{1-\alpha(\bar{S})}\right) \cdot \pi(j, S) $$
Assortment Optimization for Markov Chain Model
在第五章，文章考虑如何对 Markov chain discrete choice model 做 assortment optimization，即，研究以下的优化问题：
$$ \max _{S \subseteq \mathcal{N}} \sum_{j \in S}\left(r_{j} \cdot \hat{\pi}(j, S)\right) $$
当然，从 Markov chain 反推 $\hat{\pi}(j, S)$ 是困难的。但是，并不需要这样做。
Let $g_i(S)$ denote the expected revenue from a customer that arrives in state $i$. According to the transitions in the Markov chain
$$ g_{i}(S)=\sum_{j \in \mathcal{N}} P_{i j} g_{j}(S) $$
Reformulate as follows
$$ \max _{S \subseteq \mathcal{N}} \sum_{j \in \mathcal{N}} \lambda_{j} \cdot g_{j}(S) $$
This optimization problem is equivalent to selecting an optimal set of stopping (or absorbing) states in the Markov chain, and is related to the classical optimal stopping time problem.
Since the Markov chain model provides a good approximation of most discrete choice models and the corresponding assortment optimization problem can be solved efficiently, it can be useful to use the Markov chain model instead of the known true choice model.
【未完待续】