离散选择模型

RUM首次由Thurstone(1927)提出的，该模型假设每个消费者心中对各个产品 i i i的效用函数都有由一个固定的效用 μ i ,   i = 1 , … , n \mu_i, \ i=1,\dots,n μi​, i=1,…,n，再加上一个扰动效用 ϵ i ,   i = 1 , … , n \epsilon_i,\ i=1,\dots,n ϵi​, i=1,…,n决定的。因此，对于每个消费者来说，每个产品对于他的实际效用就可以表示为： u i = μ i + ϵ i ,     i = 1 , … , n u_i=\mu_i+\epsilon_i,\ \ \ i=1,\dots,n ui​=μi​+ϵi​,   i=1,…,n 其中 μ = ( μ 1 , … , μ n ) T \bm{\mu}=(\mu_1,\dots,\mu_n)^T μ=(μ1​,…,μn​)T表示各产品的确定性效用向量， ϵ = ( ϵ 1 , … , ϵ n ) T \bm{\epsilon}=(\epsilon_1,\dots,\epsilon_n)^T ϵ=(ϵ1​,…,ϵn​)T表示每个产品的随机效用向量，这些随机变量服从联合概率分布 θ ( ⋅ ) \theta(\cdot) θ(⋅)。每个消费者会选择所有替代产品中对他而言效用最高的产品。假设 p = ( p 1 , … , p n ) T ,   ∑ i = 1 n p i = 1 \textbf{p}=(p_1,\dots,p_n)^T, \ \sum_{i=1}^{n}p_i=1 p=(p1​,…,pn​)T, ∑i=1n​pi​=1表示消费者对n各替代产品选择的概率，那么消费者最有可能选择的产品的选择概率为： p i = P ( i = arg ⁡ max ⁡ i ( μ i + ϵ i ) ) p_i=P(i=\arg\max_i (\mu_i+\epsilon_i)) pi​=P(i=argimax​(μi​+ϵi​))

MNL模型是RUM中一种，且运用广泛，首先被McFadden(1974)提出。MNL模型假设 ϵ \bm{\epsilon} ϵ服从独立同分布的Gumble分布。此时n各替代产品的选择概率可以写成一下形式：

p i m n l = e μ i ∑ k = 1 n e μ k ,    i = 1 , … , n p_i^{mnl}=\frac{e^{\mu_i}}{\sum_{k=1}^{n}e^{\mu_k}},\ \ i=1,\dots,n pimnl​=∑k=1n​eμk​eμi​​,  i=1,…,n

MNL模型运用广泛的原因就是不仅拥有确定的选择概率形式，同时该形式还具有很好的性质，例如该函数的对数似然函数具有凹性，这种性质有利于后续研究。但由于MNL假设了随机项是独立同分布的，也就是各产品两两之间选择概率的比值与其他产品的效用无关（Independence of Irrelevant Alternatives, IIA特性）。

p i m n l p j m n l = e μ i − μ j    ∀ i ≠ j \frac{p_i^{mnl}}{p_j^{mnl}}=e^{\mu_i-\mu_j}\ \ \forall i\not=j pjmnl​pimnl​​=eμi​−μj​  ∀i​=j

现实却存在着影响各选择效用的共同因素，组成效用项的某个因素发生变化会引发多种产品的变化，当替代产品之间存在相关关系，那么MNL模型就不能够给予一个很好的选择预测结果。 也属于GEV(Generalized Extrem Value)

MNP模型是随即效用模型的随机项服从均值为零，任意方差-协方差矩阵的多元联合高斯分布。因此，与MNL不同，在MNP模型中，随机项的方差可以不同，且各随机项之间可以相关。然而，MNP模型只有在仅存在两个可选择产品时存在显示解。 当只有两个替代产品可供选择时 p 1 = P r ( v 1 + ϵ 1 > v 2 + ϵ 2 ) = P r ( ϵ 2 − ϵ 1 < v 1 − v 2 ) \begin{aligned} p_1&=Pr(v_1+\epsilon_1>v_2+\epsilon_2)\\ &=Pr(\epsilon_2-\epsilon_1v2​+ϵ2​)=Pr(ϵ2​−ϵ1​1,2,…,n},其中只有 S ⊆ N \mathcal{S}\subseteq\mathcal{N} S⊆N可以选择的商品，其他商品皆不可选。此外，消费者还有选择不买的权利，因此 S + = S ∪ { 0 } \mathcal{S}_+=\mathcal{S}\cup\left\lbrace0\right\rbrace S+​=S∪{0}为消费者的可选空间，当消费者选择的商品 j ∉ S + j\not\in\mathcal{S}_+ j​∈S+​就会转移到其他选择，直到买到或者离开停止。对任意 j ∈ S + j\in\mathcal{S}_+ j∈S+​， π ( j , S ) \pi(j,S) π(j,S)表示每个商品被选择的概率。

假设一个最希望购买 i ∈ N ⊆ { 0 } i\in\mathcal{N}\subseteq\left\lbrace0\right\rbrace i∈N⊆{0}的消费者到达的概率为 λ i = π ( i , N ) \lambda_i=\pi(i,\mathcal{N}) λi​=π(i,N)并购买商品 i i i。如果 i i i不可购买，用 ρ i j ,   i ≠ j , i ∈ N , j ∈ N ∪ { 0 } \rho_{ij},\ i\not=j, i\in\mathcal{N},j\in\mathcal{N}\cup\left\lbrace0\right\rbrace ρij​, i​=j,i∈N,j∈N∪{0}表示从商品 i i i转移到商品 j j j的概率，其中 i i i是更希望的得到的产品但 i ∉ S + i\not\in\mathcal{S}_+ i​∈S+​。该转移概率可以从数据模拟中获得，一旦转移至商品 j j j，那消费者的行为和那些一开始就选择商品 j j j的人一致。这样只要有消费者到达概率和转移矩阵，我们就可以近似估计出消费者行为。

例如，如果对于 S = { N ∖ { i } ∣ i = 1 , … , n } \mathcal{S}=\left\lbrace\mathcal{N}\setminus\left\lbrace i\right\rbrace|i=1,\dots,n\right\rbrace S={N∖{i}∣i=1,…,n},我们可以通过下式估计出到达到达概率和转移矩阵： λ i = π ( i , N ) \lambda_i=\pi(i,\mathcal{N}) λi​=π(i,N) ρ i j = { 1 , if  i = 0 , j = 0 ; π ( j , N ∖ { i } ) − π ( j , N ) π ( j , N ) , if  i ∈ N , j ∈ N ∪ { 0 } ,   i ≠ j ; 0 , otherwise . \rho_{ij}=\begin{cases} 1,&\text{if}\ i=0,j=0;\\ \frac{\pi(j,\mathcal{N}\setminus\left\lbrace i\right\rbrace)-\pi(j,\mathcal{N})}{\pi(j,\mathcal{N})},&\text{if}\ i\in\mathcal{N},j\in\mathcal{N}\cup\left\lbrace0\right\rbrace,\ i\not=j;\\ 0,&\text{otherwise}. \end{cases} ρij​=⎩⎪⎨⎪⎧​1,π(j,N)π(j,N∖{i})−π(j,N)​,0,​if i=0,j=0;if i∈N,j∈N∪{0}, i​=j;otherwise.​ 其中 π ( j , N ∖ { i } ) − π ( j , N ) \pi(j,\mathcal{N}\setminus\left\lbrace i\right\rbrace)-\pi(j,\mathcal{N}) π(j,N∖{i})−π(j,N)表示由于商品 i i i不可得之后商品 j j j增加得概率。在实际模型中， ρ i j \rho_{ij} ρij​与设定得集合 S \mathcal{S} S有关，如果我们已经有数据直到在集合 S \mathcal{S} S和 S ∖ { i } \mathcal{S}\setminus\left\lbrace i\right\rbrace S∖{i}下的选择概率，那么就可以估计转移概率： ρ i j = τ ⋅ π ( j , S ∖ { i } ) − π ( j , S ) π ( j , S ) \rho_{ij}=\tau\cdot\frac{\pi(j,\mathcal{S}\setminus\left\lbrace i\right\rbrace)-\pi(j,\mathcal{S})}{\pi(j,\mathcal{S})} ρij​=τ⋅π(j,S)π(j,S∖{i})−π(j,S)​ 实际上基于Markov chain的选择模型经常用于选品优化，并且能在多项式时间内求解。在选品优化问题中目标函数就是最大化期望收益： max ⁡ S ⊆ { 1 , … , n } r ( S ) = ∑ j ∈ S r j ⋅ π ( j , S ) \max_{\mathcal{S}\subseteq\left\lbrace1,\dots,n\right\rbrace}r(\mathcal{S})=\sum_{j\in\mathcal{S}}r_j\cdot\pi(j,\mathcal{S}) S⊆{1,…,n}max​r(S)=j∈S∑​rj​⋅π(j,S) 其中 r j r_j rj​是商品 j j j单位收益， π ( j , S ) \pi(j,\mathcal{S}) π(j,S)是在集合 S \mathcal{S} S下购买商品 j j j的概率。很显然该目标函数很难求解，但可以在 O ( log ⁡ 1 / ϵ ) \mathcal{O}(\log1/\epsilon) O(log1/ϵ)迭代下得到一个收益在最优收益 ϵ \epsilon ϵ内的产品组合，只要选取足够小的 ϵ \epsilon ϵ就可以在多项式时间内逼近最优决策。

Jagabathula(2013)提出了两阶段选择模型，第一阶段消费者考虑与价格（或其他因素）无关，对所有产品（包括选择‘不买’）进行排序，得到基础偏好集合；第二阶段消费者在基础偏好集合中再根据与价格（或其他因素）和潜在消费者偏好相关进行挑选，得到一个更小的集合。例如，可以将第一阶段当作是消费者在不考虑价格的情况下，对所有产品的排序，很显然质量高的产品排在质量低的产品前面。但当考虑价格时，由于消费者预算问题、打折或者其他与价格相关的事件，消费者会排除一些产品（如价格高的产品），得到一个更小的选择集合，一旦这个集合确定，消费者只需要选择质量最高的产品即可，当外界因素不断变化，消费者对产品偏好排序不会变化，但根据外界因素“修剪”过的集合会发生变化。

假设按照商品价格进行排序 p 1 ≤ p 1 ≤ ⋯ ≤ p n ≤ p n + 1 p_1\leq p_1\leq \cdots\leq p_n\leq p_{n+1} p1​≤p1​≤⋯≤pn​≤pn+1​,以此为基础设定消费者的WTP(willing to pay) g [ p i , p i + 1 ) g\left[p_i,p_{i+1}\right) g[pi​,pi+1​),表示消费者的WTP落在 [ p i , p i + 1 ) \left[p_i,p_{i+1}\right) [pi​,pi+1​)区间内。 S i \mathcal{S}_i Si​表示在该WTP下可以购买的商品集合 { 1 , 2 , … , i } \left\lbrace1,2,\dots,i\right\rbrace {1,2,…,i},那么消费者选择商品 i i i的概率为 p i = ∑ j = i n g [ p j , p j + 1 ) P λ ( i ∣ S j ) p_i=\sum_{j=i}^ng\left[p_j,p_{j+1}\right)P_\lambda(i|\mathcal{S}_j) pi​=j=i∑n​g[pj​,pj+1​)Pλ​(i∣Sj​) 其中， λ \lambda λ表示偏好排序的分布， P λ ( i ∣ S j ) P_\lambda(i|\mathcal{S}_j) Pλ​(i∣Sj​)表示在 λ \lambda λ规则下，在 S j \mathcal{S}_j Sj​的可选集合中选择购买商品 i i i的概率。很显然需要消费者预算大于商品 i i i的价格，才有可能购买商品 i i i

研究选品优化或者收益管理一个很大问题就是选择离散选择模型。具体使用哪个模型才能刻画需要的行为，可能存在适用的模型并不能进行有效的处理，能进行有效处理的模型不能很好的解释现实意义。因此研究各模型在数学形式上的关系非常重要。

Andreson(1988)等证明一个参数为 η \eta η的MNL模型的选择概率与正则项 V ( x ) = η ∑ i = 1 n x i log ⁡ x i V(\bm{x})=\eta\sum_{i=1}^nx_i\log x_i V(x)=η∑i=1n​xi​logxi​的代表性代理人模型选择概率相同，也就是我们可以将MNL模型的选择概率写成： p i = arg ⁡ max ⁡ { μ T x − η ∑ i = 1 n x i log ⁡ x i ∣ ∑ i = 1 n x i = 1 } p_i=\arg\max\left\lbrace\bm{\mu}^T\bm{x}-\eta\sum_{i=1}^nx_i\log x_i\bigg|\sum_{i=1}^nx_i=1\right\rbrace pi​=argmax{μTx−ηi=1∑n​xi​logxi​∣∣∣∣​i=1∑n​xi​=1} Hofbauer和Sandholm(2002)将这个结论扩展至整个随机效用模型。他们证明任意随机项是连续分布的随即效用模型，都能够用一个代表性代理人模型给出相同的选择概率。但是反过来就不一定能实现，他们证明了，当可选择商品数量 n ≥ 4 n\geq4 n≥4时，不存在一个随机效用函数的选择概率与正则项为 V ( x ) = − ∑ i = 1 n log ⁡ x i V(\bm{x})=-\sum_{i=1}^n\log x_i V(x)=−∑i=1n​logxi​的代表性代理人模型的选择概率相同。也就是，RAM模型完全包含RUM模型。

Natarajan(2009)等证明MDM模型可以与一个RAM模型等价。假设 Θ = { θ ∣ ϵ i ∼ F i ( ⋅ ) , ∀ i } \Theta=\left\lbrace\theta|\epsilon_i\sim F_i(\cdot),\forall i\right\rbrace Θ={θ∣ϵi​∼Fi​(⋅),∀i},其中 F i ( ⋅ ) F_i(\cdot) Fi​(⋅)是一直连续分布，那么其选择概率除了用MDM形式表示，还能够写成 p i = arg ⁡ max ⁡ x { μ T x + ∑ i = 1 n ∫ 1 − x i 1 F i − 1 ( t ) d t ∣ ∑ i = 1 n x i = 1 } p_i=\arg\max_x\left\lbrace\bm{\mu}^T\bm{x}+\sum_{i=1}^n\int_{1-x_i}^1F_i^{-1}(t)dt\bigg|\sum_{i=1}^nx_i=1\right\rbrace pi​=argxmax​{μTx+i=1∑n​∫1−xi​1​Fi−1​(t)dt∣∣∣∣​i=1∑n​xi​=1} 同时他们也证明了，MMM模型也能够用一个RAM模型表示。不失一般性地，假设所有随机项的边际期望都为0，那么假设随机项 ϵ i \epsilon_i ϵi​的方差为 σ i \sigma_i σi​，那么选择概率可以写为 p i = arg ⁡ max ⁡ x { μ T x + ∑ i = 1 n σ i x i ( 1 − x i ) ∣ ∑ i = 1 n x i = 1 } p_i=\arg\max_x\left\lbrace\bm{\mu}^T\bm{x}+\sum_{i=1}^n\sigma_i\sqrt{x_i(1-x_i)}\bigg|\sum_{i=1}^nx_i=1\right\rbrace pi​=argxmax​{μTx+i=1∑n​σi​xi​(1−xi​) ​∣∣∣∣​i=1∑n​xi​=1} 之后Ahipasaoglu(2013)等证明了CMM也可以用一个RAM表示。至此，所有已经研究过的半参数模型都被证明可以用RAM描述。

Feng(2015)等提出了一个新的选择模型框架，称为welfare-based选择模型。一个拥有单调性、转移不变性以及凸性的函数 w ( μ ) w(\bm{\mu}) w(μ)，就被称为一个选择模型的收益函数。如果这个函数可微，那么选择模型的概率可以表示为 p = ∇ w ( μ ) \bm{p}=\nabla w(\bm{\mu}) p=∇w(μ)。用这种方式定义的离散选择模型可以证明与RAM和半参数选择模型之间两两等价，且完全包含RUM模型。与RUM模型之间的区别仅是收益函数各阶偏微分的差别，welfare-based选择模型仅对一、二阶偏导有要求，而RUM要求所有高阶偏导符号不断交换。由此将离散选择模型大的分类整合在一起，研究清楚了各选择模型之间的关系。

另外，Blanchet(2013)等证明基于Markov chain的离散选择模型在数据上是任一随机效用模型真实选择概率的逼近。Jagabathula(2013)等证明两阶段选择模型包含随即效用模型。

[1] Ahipasaoglu S D, Li X, Natarajan K. A convex optimization approach for computing correlated choice probabilities with many alternatives[J]. IEEE Transactions on Automatic Control, 2018, 64(1): 190-205. [2] Alptekinoglu, A., J. Temple. 2013. The exponomial choice model: A new alternative for assortment and price optimization. Working paper. [3] Anderson S P, De Palma A, Thisse J F. A representative consumer theory of the logit model[J]. International Economic Review, 1988: 461-466. [4] Blanchet, J., G. Gallego, V. Goyal. 2013. A Markov chain approximation to choice modeling. Working paper. [5] Daganzo C. Multinomial probit: the theory and its application to demand forecasting[M]. Elsevier, 2014. [6] Feng G, Li X, Wang Z. Analysis of discrete choice models: A welfare-based framework[J]. arXiv preprint arXiv:1503.01854, 2015. [7] Gallego, G., R. Ratliff, S. Shebalov. 2014. A general attraction model and sales-based linear program for network revenue management under customer choice. Operations Research. [8] Heiss, F. Specification(s) of Nested Logit Models. Mannheimer Forschungsinstitut Okonomie und Demographischer Wandel, Mannheim, Germany, 2002 [9] Kirman A P. Whom or what does the representative individual represent?[J]. Journal of economic perspectives, 1992, 6(2): 117-136. [10] McFadden, D. 1974. Conditional logit analysis of qualitative choice behavior. P. Zarembka, ed., Frontiers in Econometrics. Academic Press, 105-142. [11] McFadden, Daniel, et al. 1978. Modelling the choice of residential location. Institute of Transportation Studies, University of California. [12] McFadden, D. 1980. Econometric models for probabilistic choice among products. The Journal of Business 53(3) 13-29 [13] McFadden, D., K. Train. 2000. Mixed MNL models for discrete responses. Journal of Applied Econometrics 15 447-470. [14] Mishra V K, Natarajan K, Tao H, et al. Choice prediction with semidefinite optimization when utilities are correlated[J]. IEEE Transactions on Automatic Control, 2012, 57(10): 2450-2463. [15] Natarajan, K., M. Song, C.-P. Teo. 2009. Persistency model and its applications in choice modeling. Management Science 55(3) 453-469. [16] Small K A. A discrete choice model for ordered alternatives[J]. Econometrica: Journal of the Econometric Society, 1987: 409-424. [17] Thurstone, L. 1927. A law of comparative judgment. Psychological Review 34(4) 273-286. [18] Train, K. E. 2009. Discrete Choice Methods with Simulation. Cambridge University Press.