• 论文标题：Assortment Optimization Under General Choice
• 中文标题：一般选择下的产品组合优化
• 论文下载链接：SSRN，DOI

序言

本文为Srikanth Jagabathula于2014年以独立作者身份发表的论文笔注，有趣的是Srikanth Jagabathula在2011年还曾经以第二作者身份发表过标题完全相同的论文arxiv@1108.3596

该论文于2014年10月22日首次发布于SSRN，但之后经过数次修改，目前从SSRN或DOI上下载得到的论文与笔者所阅读的版本存在较大差异，本文为论文的首发版本的笔注，主要研究的是ADXOpt算法在MNL模型及其几种变体上的效果与理论证明，上面给出的下载链接中作者已经删除了对这几个模型的理论证明和研究，而是着重研究算法对最优解的近似程度以及与这几年新提出的算法的一个效果对比，应该算是完全不同的两篇文章了，看起来要内容相比首发版本深得多。

笔者摘录了原文大部分的内容与证明过程，并做相应的笔注，逻辑基本完整，但是部分太长的证明并没有摘录。事实上本文的算法并不复杂，但是在熟悉本文的内容前，需要先对MNL模型做一个大致的了解。

关于MNL模型

• 可选产品集： N = { 1 , 2 , . . . , n } N=\{1,2,...,n\} N={1,2,...,n}

• 产品$i$的实用性：${\mu }_i\in (0,1)$

• 产品$i$的利润（或价格）：$p_i\in (0,+\infty )$

• 则购买商品$i$的概率为：
  $$q_i=\frac{\exp ({\mu }_i)}{1+{\sum }_{j\in S}\exp ({\mu }_j)}$$
  其中$S\in N$为报价集（offer set），那么为了使得利润最大化，即需要解决以下优化问题：
  $$\underset{S\in N}{\max }\sum _{i\in S}\frac{p_i\exp ({\mu }_i)}{1+{\sum }_{j\in S}\exp ({\mu }_j)}=\underset{x_1,...,x_n}{\max }\sum _{i=1}^n\frac{x_i{p}_i\exp ({\mu }_i)}{1+{\sum }_{j=1}^n{x}_j\exp ({\mu }_j)}$$
  其中决策变量$x_i$表示商品$i$是否存在于报价集$S$中，即：
  $$x_i=\{\begin{array}{rlrl}& 0& & \text{if }i\notin S\\ & 1& & \text{if }i\in S\end{array}$$
  这是一个拟线性（quasi-linear）规划问题，因为分子分母都是关于$x=(x_1,...,x_n)$的线性函数。

• 事实上在本科高级运筹学（或研究生优化理论）课上，江波的第一次作业的最后一题就是要求证明，最优解$S^{\ast }$和最优解下的最大收益$v^{\ast }$应当具有如下形式（这个在参考文献[26]中有提及）：
  S ∗ = { i : p i ≥ v ∗ } S^*=\{i:p_i\ge v^*\} S∗={i:pi​≥v∗}
  其中利润值是降序排列，即$p_1\ge p_2\ge ...\ge p_n\ge 0$，这个其实是可以通过贪婪算法得到最优解的，因为没有容量限制，如果加上容量限制（比如$S$至多包含$n/2$个产品），根据利润从大到小取就不一定正确了。

---

---

摘要 Abstract

• 如何向客户提供产品组合（mix of products）或报价集（offer set）以最大化期望收益？
• 提供产品的预期收入取决于所提供产品的价格和需求。
• 我们关注的是产品价格具有外生性（exogenously set），产品需求遵循一般的离散选择模型（discrete choice model）。
• 基于选择的需求模型（choice-based demand models）在运营管理和收益管理中越来越流行，因为它们能够捕获替代（capture substitution）：如果首选产品（preferred product）无法获得，客户可以购买可获得的产品之一。
• 然而，这种模型的灵活性是有代价的：在一般选择模型下寻找收益最大化的产品子集的问题在求解计算上难度较大。
• 现有的工作侧重于特定的参数选择模型族，基于特定的参数结构来开发有效的优化算法。
• 然而，对于几种常用的选择结构，高效的优化算法尚无定论。
• 此外，大多数现有技术都是针对特定结构量身定制的，并且没有扩展（即使没有保证）到更一般的选择模型。
• 本文另辟蹊径提出了一种通用的局部搜索算法，通过假设只访问一个收益子程序（revenue subroutine），为每个子集提供预期收益预测，从而找到最大规模为$C$的收益最大化子集。
• 我们证明了当基本选择模型是多项逻辑（multinomial logit，下简称为MNL）模型时，本文提出的算法可以有效地找到有容量约束和无容量约束的收益最大化报价集。
• 在不存在容量约束的情况下，我们将结果推广到鲁棒多项逻辑模型（robust MNL model）。
• 最后，我们证明了对于嵌套逻辑（nested logit，下简称为NL）和混合逻辑（mixed logit，下简称为ML）模型的特定变量，当没有容量约束时，本文提出的算法可以在多项式时间内收敛到局部最优解。
• 本文的数值分析结果表明，即便算法没有收敛到最优解时，它依然可以找到了很好的近似解，且在复杂模型上得到的近似解比简单模型上得到的精确解在决策结果上会更优。
• 本文的算法可以权衡预测复杂性和优化复杂性之间。

---

1 导论 Introduction

• 传统运营管理与收益管理假设的独立需求模型（independent demand model）：

  • 客户在到达之前决定他们想要购买的产品，如果产品可用，则在到达时进行购买。
  • 否则，他们会在没有购买的情况下离开。

  缺陷：无法捕获客户常见的替代行为：如果首选产品不可用，客户可能会购买其中一种可用产品。

  参考文献[29]强调将选择纳入收益管理模型得到重要性，可以显著改善需求预测。

• 独立需求模型$\to$离散选择模型（discrete choice model）：

  在基于选择的需求模型中，假设客户根据偏好列表从选项菜单中进行选择，因此如果最喜欢的选项不可用，他们就会从列表中选择一个可用的选项，只要有至少一种比不购买效用更高的可用选项。

  需要全局搜索报价集以得到最优解。

• 在本文中，给定一个已经从数据估计得到的需求模型，我们考虑确定产品最佳子集问题（optimal subset of products）。更准确地说，我们假设每个产品都与一个价格相关联，目标是确定产品子集以最大化每个客户的预期收益最大化。这个问题在文献中被普遍称为静态产品组合优化问题（static assortment optimization）。

  难点在于子集的数量关于产品数量是指数级别，因为穷举法通常不可行。为了解决穷举的计算复杂性，通常是在底层选择模型上强加参数结构，如：

  • MNL模型：参考文献[29]

• 带有不确定参数的MNL模型：参考文献[26]

  • 嵌套逻辑（nested logit model，下简称为NL）模型：参考文献[07,10]
  • 混合逻辑（mixed logit，下简称为ML）模型的特定变体：参考文献[17]

• 上述现有方法（指在底层模型上强加参数结构）的缺陷：

  • 方法不可扩展到除上述以外的模型，因为除MNL系列的模型外，更广为使用的还有MNP模型，NL模型的广义变体，ML模型的广义变体，Mallows模型，广义Mallows模型，非参的黑盒模型（参考文献[08]），近年来也有很多新的选择模型被提出。
  • 该方法没有产生适用于具有特定情况保证的一般的选择模型的一般启发式方法（heuristics）。现有算法是专门为它们设计的结构而设计的，因此不容易推广到更一般的选择结构。

• 我们采取以下自上而下（top-down）的方法来应对上述挑战。 我们假设访问一个收益子程序（revenue subroutine），当查询每个报价集时，该子程序返回预期收益。 我们开发了一个通用的集合优化（set optimization）启发式方法，它在收益子程序（revenue subroutine）上运行，并以高效计算的方式返回收益最大化报价集的估计，可能受所提供产品数量的约束。 然后，我们为特定模型结构的一般启发式得出性能保证。

  我们需要启发式方法具有以下要求：

  • 与任何收益子程序（revenue subroutine）结合都有效，并在计算上高效地返回一个可行的解决方案；
  • 收敛到已知可有效求解的特殊情况的最优解；
  • 为更一般的选择结构提供良好的近似。

• 除了提供一种算法来进行产品组合优化之外，我们的通用技术还提供了在模型的预测准确性与我们优化模型的能力之间进行权衡的见解。 具体来说，在实践中，我们从数据而不是模型开始。 给定有关客户交易的数据，我们的目标是找到收益最大化的报价集。 典型的方法是将需求模型与数据拟合，然后精确或近似地解决决策问题。 需求模型的选择取决于模型拟合（或模型预测能力）以及我们解决最终决策问题的能力。 简单模型具有易于处理的决策问题公式，但通常对数据的拟合不佳。 复杂模型往往更适合，但具有难以处理的决策问题公式。 在一些实际设置中，通常会选择简单易处理的模型，以使决策问题更易于处理。

• 随着通用组合优化算法的可用性，我们现在可以比较两种方法之间的差异：

  • 使用一个预测能力通常较低的简单模型，其决策问题可以求解为最优。
  • 使用一个复杂的模型具有典型高预测能力的模型，其决策问题只能使用我们的通用算法来解决。

  我们的结果（见下面的讨论）表明，将复杂模型与我们的通用算法结合使用可以显著优于简单模型，即便没有求得最优解。

• 本文方法概述：给定包含$n$个产品的产品全集$N$，需要确定收益最大化的报价集，即：
  $$\underset{S\subseteq N:|S|\le C}{\max }R(S)$$
  其中$R$为收益函数，它返回报价集$S$的期望收益，$C$表示报价集的容量限制。

  我们的目标是提出一种通用集合函数（set-function）优化算法，该算法无需特定的参数结构，并且只需要访问收益函数$R$。

  因为除了收益函数，没有其他可用的信息参考，一种贪婪的想法是从空集开始每次向报价集中添加使得收益函数增长最多的产品，当再增加任意产品都无法增加收益（或$S$达到容量限制）时算法终止。

  显然这样只能得到局部最优解，且非常遗憾的是，即使在最简单的MNL模型中，上述贪婪算法也无法找到最优解，只有当最优解呈现嵌套性质（nested property）时，贪婪算法才能有效，即对任意的$C_1\le C_2$，容量为$C_1$的最优报价集都包含于容量为$C_2$的最优报价集。

  其实这个还是比较容易理解的，在参考文献[27]中的第1669页给出了一个例子（但是这篇论文似乎不太容易找得到），显然满足上述嵌套性质的问题是可以用贪婪算法得到最优解的，事实上只要找到一个不满足嵌套性质的问题就可以说明贪婪算法的不可行性。

  这里简单给一个例子：

  • N = { 1 , 2 , 3 } N=\{1,2,3\} N={1,2,3}
  • ${\mu }_1={\mu }_2=\mu ,{\mu }_3={\mu }^{\prime }$
  • $p_1=p_2=p,p_3=p^{\prime }$

  当满足如下条件：
  $$\frac{p\exp (\mu )}{1+\exp (\mu )}\le \frac{p^{\prime }\exp ({\mu }^{\prime })}{1+\exp ({\mu }^{\prime })}\le \frac{2p\exp (\mu )}{1+2\exp (\mu )}\text{and}\frac{p\exp (\mu )+p^{\prime }\exp ({\mu }^{\prime })}{1+\exp (\mu )+\exp ({\mu }^{\prime })}\le \frac{2p\exp (\mu )}{1+2\exp (\mu )}$$
  显然报价集最多包含一个产品时，最优解 S ∗ = { 3 } S^*=\{3\} S∗={3}，报价集最多包含两个产品时最优解 S ∗ = { 1 , 2 } S^*=\{1,2\} S∗={1,2}

  取了几组数据，当$p=2,p^{\prime }=1.9,\mu =0.5,{\mu }^{\prime }=0.7$时，有：
  $$1.245\le 1.270\le 1.535\text{and}1.528\le 1.535$$
  即此时不满足嵌套性质，显然无法用贪婪算法求得最多包含两个产品时的最优解。

• 为了克服朴素贪婪算法的上述挑战，我们允许算法通过将操作集从贪婪的添加扩展到贪婪的删除和交换（exchange）来探索邻域。特别是，在每次迭代中，算法可能会：

  • 添加一个尚未在候选集中的产品；

  • 从候选集中删除产品；

  • 将候选集中的产品换成不在候选集中的产品。

  在上述可行的操作中，选择使得收益增加最多的操作。该算法是局部搜索的元启发式（meta-heuristic）的一个特定实例。当算法达到局部最优时，即所有可行的操作都不会导致收益增加，算法自然终止。然而，在允许删除和交换的情况下，算法可能需要多次迭代才能达到局部最优。为了确保在多项式时间内终止，我们引入了一个控制参数来限制产品可能被移除的次数。具体而言，将每个产品的移除次数限制为$b$，则算法可以在$O(n^{2}bC)$次迭代后终止。

• 局部搜索算法的性能取决于两个因素：

  • 参数$b$的选择是否允许算法收敛到局部最优？

  • 局部最优（相对于增、删、换三个操作）是否也是全局最优？

  遗憾的是，对于一般的选择结构，算法当然可能不会收敛到局部最优，即使收敛，局部最优也可能不是全局最优。 然而，令人惊讶的是，我们表明对于上面提到的几种选择结构，算法收敛到全局最优！请注意，本文的算法是通用的，并且与特定的选择结构（choice structure）无关，因此与寻找最佳解决方案的现有算法大不相同。因此本文的结果为现有流行选择模型的结构提供了新的见解。

• 本文算法的理论保证：

  我们通过推导出几种常用选择结构的理论保证来分析局部搜索启发式方法的性能。

  首先需要定义收益排序子集（revenue-ordered subsets）的概念。收益排序子集的集合包含几个流行选择模型的最佳无容量报价集。它包括$n$个报价集：即 { 1 } , { 1 , 2 } , { 1 , 2 , 3 } , . . . , { 1 , 2 , . . . , n } \{1\},\{1,2\},\{1,2,3\},...,\{1,2,...,n\} {1},{1,2},{1,2,3},...,{1,2,...,n}，其中假设产品利润降序排列，即$p_1\ge p_2\ge ...\ge p_n\ge 0$，我们有如下结论：

  • MNL模型：对于MNL模型，本文同时考虑了问题的无容量和有容量的版本。

    在无容量情况下，$b=1$的局部搜索启发式方法收敛到$O(n^2)$次迭代的最优解（定理2）。

    在有容量的情况下， b = min ⁡ { C , n − C + 1 } b=\min\{C,n − C + 1\} b=min{C,n−C+1}的算法在$O(n^{2}bC)$次迭代中收敛到最优解（定理 3）。

    事实上在无容量限制的情况下，MNL模型的最优解必须是$n$个收益有序子集之一（见本笔注序言部分），因此找到最优解需要$O(n)$次迭代。

    对于有容量限制的情况下，参考文献[27]表明可以设计算法在$O(nC)$次迭代下获得最优解，但需要对选择结构的有特定要求。

  • 参数不确定的MNL模型：即模型参数存在不确定性时。参考文献[27]研究了这种情况，其中作者建议使用收益函数$mi{n}_{v\in \mathcal{V}}{R}_v(S)$来预测收益，其中$v$表示MNL模型的参数向量，$\mathcal{V}$表示参数空间，$R_v$表示参数向量为$v$的MNL模型下的收益函数。本文研究了上述鲁棒的（robust）收益函数的在无容量限制的产品组合问题，结果表明本文的算法与$b=1$在$O(n^2)$次迭代中收敛到最优解（定理 4）。

    作为比较，参考文献[27]表明最优解必须属于$n$个收入排序子集之一，因此找到最优报价集需要$O(n)$次迭代。？？？

  • 两级NL模型：我们考虑两级NL模型的一个特定变体：第一个嵌套中无购买替代品和第二个嵌套中包含所有其他产品。对于这个模型，我们研究了无容量限制的产品组合优化问题，并表明我们的算法如下：

    • $b=1$时，本文的算法在$O(n^2)$次迭代中收敛到局部最优

    • 局部最优是收益排序子集（定理5）。

    不幸的是，由于NL模型的块状特性，局部最优性并不能保证全局最优性（参考文献[17]）。

    但如果NL参数使得模型不会表现出块状结构，那么我们的算法就可以收敛到最优解。本文的数值分析表明块状是一种罕见的情况，因此我们的算法在绝大多数情况下都会收敛到最优解。

    作为比较，参考文献[17]表明最优解必须是收益有序子集之一，这样才能在$O(n)$次迭代中找到最优解。

  • ML模型：我们考虑ML模型的一个特定变体：不同的客户类别仅在无购买替代方案上有所不同。 对于这个模型，我们考虑无容量限制的产品组合优化问题：

    • $b=1$，本文的算法在$O(n^2)$次迭代中收敛到局部最优，

    • 局部最优是收益排序子集（定理7）

    不幸的是，局部最优并不能保证全局最优。 本文的数值分析表明本文的算法在绝大多数情况下都能找到最优解。

    作为比较，参考文献[28]证明了最优解必须是收益排序子集之一，因此可以在$O(n)$次迭代中找到最优解。

• 据作者所知，对于具有参数不确定性的MNL模型的有容量限制的产品组合优化问题，尚无定论。而NL模型和ML模型通常是NP难得。对于已知具有可有效解决的无容量限制得产品组合优化问题的NL和ML模型的变体，本文证明了在特殊情况下可以收敛到局部最优解的性质。最后，本文还为已知结果提供了新颖和简化的证明（定理6和定理8），即最优解属于我们考虑的NL和ML模型变体的收益有序子集集合。

• 数值分析：本文进行了广泛的模拟研究，以证明提出的局部搜索算法的有效性。具体来说，本文进行了两项模拟研究：

  • 第一项研究旨在证明我们的算法可以获得对各种一般选择结构的良好近似。

  • 第二项研究旨在证明在实际数据环境中，拟合复杂模型，然后使用我们的算法解得的模型最优解，要优于拟合简单模型并求解最优解。

  对于第一个模拟研究，我们考虑了以下选择结构：

  • NL2：具有两个嵌套的两级嵌套的NL模型——第一个嵌套仅包含不购买选项，第二个嵌套包含所有其他产品；

  • ML-DIS混合逻辑模型：不同类别的客户仅在无购买参数上有所不同；

  • ML：一般的混合逻辑模型。

  我们将第二个模型称为ML-DIS（其中DIS代表dis-utility），因为如果我们假设客户为每个产品添加一个（dis-）效用项——不包括 nopurchase替代——并且（非）效用项在不同客户之间是异质的。

  我们的仿真结果表明，我们的算法分别在 NL2、ML-DIS 和ML模型类的98%、99% 和 98% 的情况下找到了最优解。

  此外，在算法没有找到最优解的情况下，NL2、ML-DIS和ML模型类的平均最优差距分别为0.15%、0.005%和3.04%（8.1节表8.1） 。

  第二个模拟研究的目标是证明模型的预测准确性和我们优化模型的能力之间的权衡。具体来说，在实践中，我们从数据而不是模型开始。给定有关客户交易的数据，我们的目标是找到收入最大化的报价集。典型的方法是将需求模型与数据拟合，然后精确或近似地求解决策问题。需求模型的选择取决于模型拟合（或模型预测能力）以及我们解决最终决策问题的能力。简单模型具有易于处理的决策问题公式，但通常对数据的拟合不佳。复杂模型往往更适合，但具有难以处理的决策问题公式。在一些实际设置中，模型选择往往以决策问题的易处理性为指导，导致需求模型简单但易处理。随着通用分类优化算法的可用性，我们现在可以比较两种方法之间的差异：

  • 可以将决策问题求解到最优的简单模型。
  • 可以将决策问题求解的复杂模型（只能使用我们的通用算法来解决）。

  为了说明上述权衡，我们进行了以下实验。我们修复了具有 5 个客户类别和 15 个产品的混合 logit 模型作为真实模型并生成合成交易。然后使用交易来拟合两个模型：标准MNL模型和参考文献[08]提出的一般非参数方法。

  标准的MNL模型很简单。 参考文献[08]提出的非参数方法是复杂的，具有高预测能力，但会导致难以处理的决策问题。使用本文局部搜索算法来估计收益最大化报价集（有容量限制为10）。本文的算法在MNL模型下产生了最优解，但最优解的收益只能达到非参数方法的近似值。然后，我们通过将两个估计的真实收益与真实模型下的真实最佳收益进行比较来确定估计的质量。我们的结果表明，非参数方法在很大程度上优于MNL模型：在多77%的情况下达到最佳解决方案，而相对优化差距平均减少约72%（8.2节中的表 8.2）。

---

2 相关文献 Relevant literature

将选择纳入运营决策的问题已在运营管理（operation management，OM）和收入管理（revenue management，RM）领域得到广泛研究。传统运营模型忽略了替代，并假设了一种独立需求模型（参考文献[30]），其中每种产品的需求独立于其他产品的可用性。此后航空公司RM的多项研究显示了使用基于选择的需求模型的价值：

• 参考文献[01]：对著名的旅客始发地和目的地模拟器（Passenger Origin and Destination Simulator，PODS）进行了模拟研究，以论证修正的独立需求模型的应用价值；
• 参考文献[25,33]：使用真实的航空公司市场数据来论述使用基于MNL选择的RM方法对期望收益的改进。
• 在这些研究之后，有大量研究将选择行为纳入运营决策模型：参考文献[29,11,18,35,22,23,34,15,16,32,06]

静态分类优化是上述大部分工作中出现的关键决策问题。具体而言，参考文献[29]研究单航段航空公司座位分配问题（single-leg airline seat allocation problem），其中航空公司在有限数量的离散时间段内出售机票，因此每个时间段内最多有一个客户到达。客户在提供的多种票价等级中进行选择。航空公司必须根据可用座位容量和剩余预订时间来决定提供或开放哪一组票价等级。这个动态决策问题可以转换为一个具有一个状态变量的动态程序。他们表明动态程序可以简化为解决静态分类优化问题的变体。参考文献[29]表明，当客户根据MNL模型做出选择并且没有容量限制时，最佳收益最大化报价集必须是收益排序子集（即 { 1 } , { 1 , 2 } , . . . , { 1 , 2 , . . . , n } \{1\},\{1,2\},...,\{1,2,...,n\} {1},{1,2},...,{1,2,...,n}，产品价格降序排列）。因此，最优策略包括从按收入排序的票价等级分类开始，并在可用座位容量和剩余预订时间减少时关闭价格较低的票价等级。由此产生的嵌套策略实际上也非常有趣。

参考文献[27]考虑在报价集容量受限的情况下，在MNL选择模型下寻找收益最大化报价集的问题。作者证明在容量限制的情况下，收益最大化的报价集可能不再是收益排序子集之一。然而，能够以较为简单的计算复杂度来确定收益最大的报价集。特别地，作者专门研究了参考文献[21]的方法来解决具有合理目标函数的组合优化问题，以获得一种确定收益最大化报价集的有效算法，复杂度为$O(nC)$。

参考文献[26]考虑这样一个设定，客户根据MNL模型做出选择，但是决策者对MNL模型的参数的认知局限于一个不确定的紧集（compact uncertainty set）。决策者希望免受不确定性的影响，因此他的目标在不确定的紧集中的所有参数值上最大化最坏情况下的预期收益的报价集。作者表明，当没有容量限制时，令人惊讶的是，即使目标是防止出现最坏情况的预期收入，收益排序子集依然是最优解，该结果扩展了参考文献[29]的研究结果，并提供了一种新颖（且更简单）的证明。

参考文献[07]研究NL模型下的组合优化问题。作者表明在没有容量限制的情况下，当嵌套差异参数都小于1且在嵌套中无购买替代方案时，可以设计算法快速确定收益最大化的报价集。参考文献[09]将此结果扩展到每个嵌套有容量限制的情况。参考文献[07]还表明，放宽所有嵌套差异参数小于1的假设或在嵌套中无购买替代方案的假设，那么即便没有容量限制，问题也是NP难的。减少来自众所周知的分区问题（partition problem，参考文献[12]）。

参考文献[03]表明，当至少有$n$个客户类别时，ML模型下的无容量产品组合优化问题严格意义上（in the strong sense）属于NP难，因为他可以由最小顶点覆盖问题归约得到（参考文献[12]）。

参考文献[24]提出了一种在广义ML模型下找到最佳组合的分支和剪枝算法。参考文献[28]将NP难的结果扩展到至少有两个客户类别的情况，因为可以从分区问题归约得到（partition problem，参考文献[12]），因此证明了不严格意义上的（in the weak sense）NP难性质。参考文献[28]考虑ML模型类的两个特殊情况下，证明最优组合必须是收益排序子集之一：

• 与产品无关的价格敏感性（product-independent price sensitivity）：给出每个产品的内在平均效用通过一个非随机的特定于产品的术语，它被添加到一个依赖于价格的术语中，价格敏感度是从均匀分布中采样的
• 价值意识（value-conscious）：任意平均效用向量满足$V_1\le V_2\le ...\le V_n$和$p_1{V}_1\ge p_2{V}_2\ge ...\ge p_n{V}_n$，其中产品价格降序排列，即$p_1\ge p_2\ge ...\ge p_n$。变体与产品无关的价格敏感性可以等价地表述属于不同类别的客户的内在效用仅针对无购买替代方案而有所不同的设定下的模型。

也有学者研究组合优化的其他变体。参考文献[19]考虑了组合优化问题，其中产品既产生收益又产生运营成本。参考文献[04]将这种设定扩展到包括产品搜索成本，即客户可能决定不从商店购买可接受的产品，希望进一步搜索可能会出现更高效用的产品。

最后，本文的算法非常通用，可以适应不同于MNL、NL和ML模型类的选择模型。参考文献[31]描述了NL模型和ML模型的几个扩展情况，并且还描述了多项概率（multinomial probit，下简称为MNP）模型。参考文献[08]描述了一种选择建模的非参数方法（non-parametric method），他们允许选择模型是偏好列表上的任何分布，并设计一个收益子程序，给定数据，子程序将任何报价集的预期收益预测为所有最坏情况下收益。他们表明，虽然模型非常复杂，但该方法具有非常高的预测能力。然而，该论文没有考虑优化问题。参考文献[14]考虑了一个两阶段模型的设定，客户首先会形成一个考虑集（consideration set），然后根据选择模型进行选择。在这个模型的设定下，作者提出了半参数（semi-parametric）技术来预测收益作为价格向量和报价集的函数。

---

3 局部搜索算法：增删换优化 Local search algorithm: ADXOpt

• 问题设定与标记定义：

  • 已知产品全集 N = { 1 , 2 , . . . , n } N=\{1,2,...,n\} N={1,2,...,n}

  • 给定收益函数$R:2^N\to {\mathbb{R}}_{+}$，其中$2^N$表示所有可能的报价集数量，并定义空报价集的收益为零，即$R(\varnothing )=0$

  • 为了简化符号标记，本文将 S ∪ { j } S\cup\{j\} S∪{j}表示为$S+j$， S ∖ { j } S\setminus\{j\} S∖{j}表示为$S-j$，其中$S\subset N,j\in N$

  • 目标是求解集合优化问题：
    $${\text{argmax}}_{S\subset N:|S|\le C}R(S)\text{\hspace{1em}(1)}$$
    该问题在学术上称为有容量限制的静态产品组合优化问题（capacitated static assortment optimization problem），它的一个特殊情况无容量限制下的对应问题，即$C=n$，学术上称为无容量限制的静态产品组合优化问题（uncapacitated static assortment optimization problem），本文分别简称为有容量限制和无容量限制的问题。

• 我们的目标是设计算法以高效的方式（in a computationally efficient manner）求解式$(1)$中的集合优化问题，这里假定$R(S)$的计算是高效的，因此我们只关注如何高效搜索最优子集，难点在于无容量限制的问题中穷举的复杂度为$O(2^n)$，有容量限制的问题中穷举的复杂度为$O(n^C)$，这分别是指数级别和伪多项式级别的复杂度。因此大部分的现有工作都是假定收益$R$具有某种特殊结构，然后设计算法使得搜索复杂度降低，或是直接证明问题的NP难性并提出启发式算法求解。总之这些方法很难扩展到一般的选择模型。

• 与上述自底向上（bottom up，指根据模型参数结构设计算法）的方法不同，本文的方法是一种自顶向下的算法，本文考察的是最一般的情形，即假定只能访问收益函数$R(\cdot )$的取值，因此可以在一般的选择模型优化求解上使用。

• 因为除收益函数$R(\cdot )$外，几乎没有任何额外的参数结构可以利用，因此本文的算法是广义的贪婪启发式算法，即在局部进行贪婪式的运算操作（即增、删、换）以使得收敛到局部最优，一般来说从空集开始，直到任意运算操作都无法改进报价集的期望收益时算法终止（或达到容量限制）。

• 具体而言，算法执行过程中会生成一系列的报价集（产品组合） { S t : t = 0 , 1 , . . . } \{S^t:t=0,1,...\} {St:t=0,1,...}，其中$S^0=\varnothing$，$S^{t+1}$在$S^t$的基础上或增加一个未在$S^t$中产品，或减少一个已在$S^t$中的产品，或将一个已在$S^t$中的产品替换为未在$S^t$中的产品。

• 当然无论增删换，都要确保$S^{t+1}$满足约束（如有容量限制的情况下$|S^{t+1}|\le C$），然后我们的目的是最大化收益的增益（即$\max R(S^{t+1})-R(S^t)$），当无法提升收益时算法终止，因此得到的结果显然为局部最优。

• 增删换算法理论上需要执行指数级别的迭代次数（与$n$和$C$有关）才能抵达局部最优，因此为了确保算法能在多项式时间内收敛，我们需要对移出操作（这在删除和替换两种操作中都会出现移出操作）的次数做限制（比如不超过$b$次），当一个产品从报价集中被移除$b$次后，它就不能再被移入了（在增加操作和替换操作中会产生移入操作）。

  

• ADXOpt算法复杂度分析：显然每次迭代需要搜索$O(nC)$种产品组合（增加和删除都是$O(n)$，替换则为$O((n-C)C)=O(nC)$）以贪婪地确定下一个报价集，由于每个产品可以被移出至多$b$次，因此每个产品至多会被移出移入至多$2b$次，此外因为每次迭代涉及移出或移入至少一个产品，因此这样的迭代至多会发生$2nb$次（即每个产品的移入移出操作次数都达到上限）。因此算法会搜索超过$O(2nb\cdot nC)=O(n^{2}Cb)$种不同的产品组合。

  注意如果我们不考虑替换操作（因为替换操作事实上只会在报价集达到容量限制时才会发生，否则一定是增加或删除，而在无容量限制时是不会发生增加替换操作的），那么每次迭代会涉及搜索$O(n)$种不同的产品组合，因此算法最终会搜索$O(n\cdot 2nb)=O(n^{2}b)$种不同的产品组合。

• 算法性能：取决于两个因素：

  • $b$的取值是否容许算法找到局部最优？
  • 局部最优（相对于增删换）是否当然为全局最优？

  对于一般的选择模型，算法当然不能收敛到局部最优，即便收敛到局部最优，也不会是全局最优。事实上因为算法没有用到收益函数的底层结构，因此我们并不期望算法最终收敛到最优解，但是下面我们将证明算法可以在几种典型的选择模型上收敛到最优解。

---

4 多项逻辑模型的（最优性）保证 Guarantees for the MNL model

• MNL模型设定：$n$个产品，产品$j$的效用为$v_j$，不购买参数为$v_0$（一般为$1$），则从报价集$S$种购买产品$i$的概率为：
  $$\mathrm{Pr}(i|S)=\frac{v_i}{v_0+{\sum }_{j\in S}{v}_j}$$
  假定产品$j$价格为$p_j$，则收益函数可以写为：
  $$R(S)=\sum _{j\in S}{p}_j\mathrm{Pr}(j|S)=\frac{{\sum }_{j\in S}{p}_j{v}_j}{v_0+{\sum }_{j\in S}{v}_j}$$
  不失一般性地，我们假定$p_1\ge p_2\ge ...\ge p_n$

• 虽然无容量限制问题是有容量限制问题的特例，本文仍然将他们分开阐述。

4.1 无容量限制的产品组合优化问题 Uncapacitated assortment optimization problem

• 问题设定：$p_1>p_2>...>p_n$，即产品价格各不相同（目的是避免最优解的退化形式），目标是求解集合优化问题：
  $${\text{argmax}}_{S\subset N}\frac{{\sum }_{j\in S}{p}_j{v}_j}{v_0+{\sum }_{j\in S}{v}_j}\text{\hspace{1em}(2)}$$

• 结论：收益最大化报价集唯一，且是收益排序子集（即 { 1 } , { 1 , 2 } , { 1 , 2 , 3 } , . . . , { 1 , 2 , . . . , n } \{1\},\{1,2\},\{1,2,3\},...,\{1,2,...,n\} {1},{1,2},{1,2,3},...,{1,2,...,n}）之一，参考文献[29]中首次给出结论与证明，本文将给出一种新颖的证明方法。

• 定理1（无容量限制的MNL模型的最优解必然是收益排序子集之一）：

  当产品价格互不相同且满足$p_1>p_2>...>p_n$，式$(2)$中集合优化问题的最优解唯一，且是收益排序子集（ { 1 } , { 1 , 2 } , { 1 , 2 , 3 } , . . . , { 1 , 2 , . . . , n } \{1\},\{1,2\},\{1,2,3\},...,\{1,2,...,n\} {1},{1,2},{1,2,3},...,{1,2,...,n}）之一。

• 证明：证明思路来自MNL模型如下的性质，设$V(S)=v_0+{\sum }_{i\in S}{v}_i$，则有：
  $$R(S+j)=\frac{p_j{v}_j+{\sum }_{i\in S}{p}_i{v}_i}{v_j+v_0+{\sum }_{i\in S}{v}_i}=\frac{p_j{v}_j+{\sum }_{i\in S}{p}_i{v}_i}{v_j+V(S)}=\frac{p_j{v}_j+R(S)V(S)}{v_j+V(S)}\text{\hspace{1em}(3)}$$
  于是向报价集$S$中加入一个新产品$j$后的收益提升可以表示为$R(S)$和$p_j$的凸组合。

  反证法：设$S^{\ast }$为最优报价集，假设存在某个产品$j\notin S^{\ast }$以及$i\in S^{\ast }$满足$p_i<p_j$，那么我们说明必然有$R(S^{\ast }+j)>R(S^{\ast })$，就与$S^{\ast }$为最优报价集矛盾。

  因为$S^{\ast }$是最优报价集且$i\in S^{\ast }$，则必然有$R(S^{\ast }-i)<R(S^{\ast })$

  又因为$R(S^{\ast })$是$R(S^{\ast }-i)$与$p_i$的凸组合，则必然有$p_i>R(S^{\ast })$

  于是就有$p_j>p_i>R(S^{\ast })$，又有$R(S^{\ast }+j)$是$p_j$与$R(S^{\ast })$的凸组合，于是必然有$R(S^{\ast }+j)>R(S^{\ast })$，这就产生了矛盾，定理得证。$■$

• 参考文献[26]中给到了本笔注序言部分的性质，即若$z^{\ast }$是最优解$S^{\ast }$对应的最大收益$R(S^{\ast })$，则 S ∗ = { j ∈ N : p j > z ∗ } S^*=\{j\in N:p_j>z^*\} S∗={j∈N:pj​>z∗}，这个性质在接下来的定理证明中将会被使用到。

  接下来我们将说明$b=1$时的ADXOpt算法可以收敛到式$(2)$集合优化问题的最优解。

• 定理2（无容量限制的MNL模型最优解可以由ADXOpt算法得到）：$b=1,C=n$的ADXOpt算法收敛到式$(2)$集合优化问题的最优解。

• 证明：假设ADXOpt算法输出$\hat{S}$，利用序言部分提到的参考文献[26]中的性质，我们说明$S^{\ast }\subseteq \hat{S}$以及$\hat{S}\subseteq S^{\ast }$

  • $S^{\ast }\subseteq \hat{S}$：

    反证法，假设存在$j\in S^{\ast }\setminus \hat{S}$，由于$j\in S^{\ast }$，则必然有$p_j>Z^{\ast }$，又$Z^{\ast }>R(S)$对任意报价集$S$都成立；

    因此$R(S+j)>R(S)$（根据式$(3)$可得$R(S+j)$是$R(S)$和$p_j$的凸组合，而已知$p_j>R(S+j)$）对任意不包含$j$的报价集$S$成立；

    同理有$R(S-j)<R(S)$对任意包含$j$的报价集$S$成立；

    即移入$j$总会提升收益，移出$j$总会降低收益，因此$j$必然在算法某次迭代中移入$\hat{S}$，且不会再被移出，因此$S^{\ast }\subseteq \hat{S}$是必然成立的。

  • $\hat{S}\subseteq S^{\ast }$：

    假设$\hat{S}⊈S^{\ast }$，由于上面已经证明了$S^{\ast }\subseteq \hat{S}$，则必然可以将$\hat{S}$划分为$S^{\ast }$与$D$（$\hat{S}=S^{\ast }\cup D$，且$S^{\ast }\cap D=\varnothing ,D\ne \varnothing$）；

    设$R_D=({\sum }_{i\in D}{p}_i{v}_i)/V_D$，$V_D={\sum }_{i\in D}{v}_i$，进一步地，注意$V(S^{\ast })=v_0+{\sum }_{j\in S^{\ast }}{v}_j$，我们可以写作：
    $$R(\hat{S})=\frac{{\sum }_{i\in D}{p}_i{v}_i+{\sum }_{j\in S^{\ast }}{p}_j{v}_j}{{\sum }_{i\in D}{v}_i+v_0+{\sum }_{j\in S^{\ast }}{v}_j}=\frac{R_D{V}_D+R(S^{\ast })V(S^{\ast })}{V_D+V(S^{\ast })}$$
    因此$R(\hat{S})$是$R_D$和$R(S^{\ast })$的凸组合，由于$R(\hat{S})<R(S^{\ast })$，则必然有$R_D<R(\hat{S})$

    假设$i$是$D$中价格最低的产品，即$p_i={\min }_{j\in D}{p}_j$，而$R_D$事实上是$D$中所有产品价格的加权平均数，因此必然有$p_i<R_D<R(\hat{S})$

    又因为$R(\hat{S})$是$p_i$和$R(\hat{S}-i)$的凸组合，于是有$R(\hat{S}-i)>R(\hat{S})$，这就与$\hat{S}$是算法得出的局部最优性矛盾，定理得证。$■$

• 算法复杂度：综上所述，$b=1,C=n$的ADXOpt算法可以得到无容量限制的MNL模型最优解，算法复杂度显然为$O(n^2)$（每次迭代搜索$O(n)$种不同的组合，迭代次数$O(n)$）

4.2 有容量限制的产品组合优化问题 Capacitated assortment optimization problem

• 问题设定：假设报价集容量限制为$C$，对应集合优化问题如下所示：
  $${\text{argmax}}_{S\subset N:|S|\le C}\frac{{\sum }_{j\in S}{p}_j{v}_j}{v_0+{\sum }_{j\in S}{v}_j}\text{\hspace{1em}(4)}$$
  参考文献[27]证明了式$(4)$的优化问题可以在$O(nC)$的复杂度内求解，虽然看起来求解很高效，但是最优解的结构相较于无容量约束的情形要复杂得多，此时最优解未必是收益排序子集之一（参考文献[26]给出反例，本笔注在前文中也构造出一种反例），且最优报价集未必具有嵌套性质，即容量限制为$C_1,C_2$（$C_1\le C_2$）的最优报价集$S_1^{\ast },S_2^{\ast }$未必满足$S_1^{\ast }⊈S_2^{\ast }$

• 重要结论：参考文献[26]建立如下的结构，固定容量限制$C$，设$S^{\ast }$是式$(4)$优化问题的最优解，$z^{\ast }=R(S^{\ast })$，则参考文献[26]证明了 S ∗ ⊂ { j ∈ N : p j ≥ z ∗ } S^*\subset\{j\in N:p_j\ge z^*\} S∗⊂{j∈N:pj​≥z∗}，且$S^{\ast }$是由按照$v_j(p_j-z^{\ast })$降序排列的至多前$C$大的产品构成。因此可以通过如下的几何方法构造最优解：

  • 对每个产品$j$，做映射$h_j:x\to v_j(p_j-x)$，其中该线性函数的斜率为$-v_j$，与横轴交于$p_j$，与纵轴交于$v_j{p}_j$

  • 最优解集合$S^{\ast }$就由至多$C$个在横轴交点大于$x=z^{\ast }$的产品构成。

  • 因此可以通过搜索子集族 S = { S C ( x ) : x ∈ R + } \mathcal{S}=\{S_C(x):x\in\R_+\} S={SC​(x):x∈R+​}，其中 S C ( x ) ⊂ { j ∈ N : p j ≥ x } S_C(x)\subset\{j\in N:p_j\ge x\} SC​(x)⊂{j∈N:pj​≥x}表示根据$v_j(p_j-x)$排序得到的至多前$C$个产品构成的报价集。

  • 因为$S_C(x)$由位于横轴$x$处上方的至多前$C$条直线构成，所以$S_C(x)$在任意两条直线的交点（$h_j$对应的直线）之间的距离是常数。不懂？？？

    原文：…, the set remains constant between any two points of intersection of the collections of lines $h_j$.

  • 因为$n$条线交于$O(n^2)$个交点，所以最优解集合会在$O(n^2)$个子集中搜索得到，进一步地分析会发现子集族$\mathcal{S}$由$O(nC)$个子集构成。

• 上面的几何构造似乎有点晦涩难懂，这里笔者做一下注解：因为已知$S^{\ast }$是由按照$v_j(p_j-z^{\ast })$降序排列的至多前$C$大的产品构成，但是我们并不知道$z^{\ast }$具体是多少，所以无法直接求解$S^{\ast }$。于是想到将所有产品对应的$n$条直线$h_j$画出来，然后用一条垂直线$L$去跟它们相交，交点靠上面的$C$个产品即为所求，水平移动垂直线$L$即可得到不同的报价集（对应$S_C(x)$，$x$即为垂直线$L$与横轴的交点），然而事实上我们无需连续地移动垂直线$L$，而只需在这$n$条直线$h_j$的交点处检查即可（因为两个交点之间的部分对应的报价集完全相同），因此一共只需要检查$O(n^2)$种情况。特别地，因为直线$h_j$与横轴的交点恰好为产品$j$的价格，所以当垂直线与横轴的交点超过产品$j$的价格时，$h_j$与垂直线的交点就在横轴下方了（交点在下方就不会被选入报价集，详见$S_C$的定义，当然交点在上方的可能不足$C$个，那么就全部取到报价集作为最优解）。

• 我们利用上述最优解地结构来证明本文的算法能够收敛到最优解，在此之前我们需要先做一些假设来避免一些退化情况，这些假定在参考文献[26]中也被使用到。

• 假设1（客户偏好与交点相异）：模型参数应当满足
  • $\forall i\in N$，有$v_i>0$；$\forall i,j\in N,i\ne j$，有$v_i\ne v_j$；
  • $\mathcal{I}(i,j)\ne \mathcal{I}(s,t)$，对任意$(i,j)\ne (s,t),i\ne j,s\ne t$成立（$i,j,s,t\in N$）；其中$\mathcal{I}(i,j)=(p_i{v}_i-p_j{v}_j)/(v_i-v_j)$，即为$h_i$与$h_j$两条线的交点的横坐标。
• 假设1的第一条要求MNL模型参数各异。
• 假设1的第二条要求价格各异，且不存在三个产品对应的直线（$h_j:x\to v_j(p_j-x)$）交于同一点。

• 接下来我们来陈述ADXOpt在该情形下的最优性：

• 定理3（有容量限制的MNL模型最优解可以由ADXOpt算法得到）： b = min ⁡ { C , n − C + 1 } b=\min\{C,n-C+1\} b=min{C,n−C+1}的ADXOpt算法收敛到式$(4)$集合优化问题的最优解。

• 证明：详见附录A（证明真的好长啊），这里仅陈述证明思路。

  思路仍然借用上面提到的几何构造方法，令$S^t$表示算法第$t$次迭代后得到的产品组合，$z_t=R(S^t)$，则可以证明若产品$j$在第$t$次迭代中被移入（增加或替换），则必然有$j\in S_C(z_t)$（即垂直线位于$x=z_t$时，得到的解中必然有产品$j$）；

  同理若$j$在第$t$次迭代中被移出（删除或替换），则必然有$j\notin S_C(z_t)$；

  因此第$t$次迭代中，算法移入那些$v_j(p_j-z_t)$排名前$C$的产品，移出$v_j(p_j-z_t)$排名不在前$C$的产品，每一次迭代都是如此，直到最后一次迭代终止。则最终输出的解恰好包含至多前$C$个在横轴上方的直线对应的产品，可以证明只有满足$S_C(R(S))=S$的可行子集$S$是唯一最优解，因此算法最终得到了最优解。

  上面的论述假定$S^{\ast }$中所有还不在解集中的产品都可以在每次迭代中被移入，因此只需要设定 b = min ⁡ { C , n − C + 1 } b=\min\{C,n-C+1\} b=min{C,n−C+1}，即可确保

• 算法复杂度： O ( n 2 C b ) = O ( n 2 C min ⁡ { C , n − C + 1 } ) = O ( n 2 C 2 ) O(n^2Cb)=O(n^2C\min\{C,n-C+1\})=O(n^2C^2) O(n2Cb)=O(n2Cmin{C,n−C+1})=O(n2C2)，与现有的算法比较（$O(nC)$），在最坏情况下额外付出$O(nC)$倍的时间。

---

5 鲁棒多项逻辑模型的（最优性）保证 Guarantees for the Robust MNL model

• 鲁棒MNL模型设定：决策者只知道模型参数局限于某个不确定的集合，这种设定在实际情况中很常见，因为通常可用的数据都是不完整的。

  参考文献[26]中考察了这种带有不确定性的MNL模型设定，并提出使用鲁棒方法来解决：即选择一个报价集来最大化最坏情况下（遍历所有不确定集合中的参数情况）的收益，令人讶异的是，收益排序子集竟然仍然保持了最优性，即便模型存在不确定性且目标是优化最坏情况下的收益。

  正式的符号定义如下所示，$n$个产品按照价格降序排列（$p_1>p_2>...>p_n$），每个客户根据MNL模型来挑选产品，其中MNL模型的参数向量$\vec{v}=(v_0,v_1,...,v_n)\in {\mathbb{R}}_{++}^{n+1}$未知（${\mathbb{R}}_{++}$表示正实数），即期望收益表示为：
  $$R(S,\vec{v})=\frac{{\sum }_{i\in S}{p}_i{v}_i}{v_0+{\sum }_{i\in S}{v}_i}$$

  决策者虽然不知道$\vec{v}$具体数值，但是他会知道$\vec{v}\in \mathcal{V}$，其中$\mathcal{V}\subset {\mathbb{R}}_{++}^{n+1}$是一个已知的紧集。我们的目标是最大化最坏情况下的期望收益，即收益函数为：
  $$R(S,\mathcal{V})=\underset{\vec{v}\in \mathcal{V}}{\min }R(S,\vec{v})$$
  因为$\mathcal{V}$是一个紧集，因此这是一个完善定义的（well-defined）优化问题，但是我们并不知道对于一般的紧集$\mathcal{V}$，该优化问题能否高效求解。参考文献[26]证明了若$\mathcal{V}$是一个多面体，则$R(S,\mathcal{V})$可以看作是线性规划，本文假定$R(S,\mathcal{V})$已经能够高效求解，我们只关注产品组合优化问题，具体而言，给定$\mathcal{V}$，我们考察无容量限制的组合优化问题：
  $${\text{argmax}}_{S\subset N}R(S,\mathcal{V})={\text{argmax}}_{S\subset N}\underset{\vec{v}\in \mathcal{V}}{\min }R(S,v)\text{\hspace{1em}(5)}$$

• 重要结论：参考文献[26]中证明了式$(5)$规划的最优解$S^{\ast }(\mathcal{V})$必然属于收益排序子集（ { 1 } , { 1 , 2 } , . . . , { 1 , 2 , . . . , n } \{1\},\{1,2\},...,\{1,2,...,n\} {1},{1,2},...,{1,2,...,n}）之一，且 S ∗ ( V ) = { j ∈ N : p j ≥ Z ∗ ( V ) } S^*(\mathcal{V})=\{j\in N:p_j\ge Z^*(\mathcal{V})\} S∗(V)={j∈N:pj​≥Z∗(V)}，其中$Z^{\ast }(\mathcal{V})={\min }_{v\in \mathcal{V}}R(S^{\ast }(\mathcal{V}),\mathcal{V})$，这是非常重要的结论，对接下来的算法能够收敛到最优解的证明很有帮助。

• 定理4（无容量限制的鲁棒MNL模型最优解可以由ADXOpt算法得到）：$b=1,C=n$的ADXOpt算法收敛到式$(5)$集合优化问题的最优解。

• 证明：

  • 引理1（鲁棒MNL模型中增加一个产品对收益的影响）：考察产品组合$S\subset N$与产品$j\notin S$，则有：
    $$R(S+j,\mathcal{V})>R(S,\mathcal{V})⟺p_j>R(S,\mathcal{V})$$
    关于引理1的证明详细过程见附录B，接下来我们直接证明定理4。

  • 类似定理2的证明（几乎完全相同的证明套路），令$\hat{S}$表示算法最终得到的子集，由于产品价格互不相同，因此最优产品组合必然唯一（根据上述重要结论），因此不存在产品$j$满足$p_j=Z^{\ast }(\mathcal{V})$（否则加不加产品$j$收益相同，与唯一性矛盾），我们分两部分证明：$S^{\ast }(\mathcal{V})\subseteq \hat{S}$与$\hat{S}\subseteq S^{\ast }(\mathcal{V})$

  • $S^{\ast }(\mathcal{V})\subseteq \hat{S}$：

    考察任意产品$j\in S^{\ast }(\mathcal{V})$，由于$p_j>Z^{\ast }(V)\ge R(S,\mathcal{V})$对任意$S\subset N$成立，根据引理1可知将$j$移入到任意产品组合$S$中都会严格增加收益，反之移出则会严格减少收益，因此$j$必然在某次迭代中移入$\hat{S}$，此后不再被移出。因此$j\in \hat{S}$，则$S^{\ast }(\mathcal{V})\subseteq \hat{S}$得证。

  • $\hat{S}\subseteq S^{\ast }(\mathcal{V})$：

    反证法，由于$S^{\ast }(\mathcal{V})\subseteq \hat{S}$已证，假设$\hat{S}=S^{\ast }(\mathcal{V})\cap D$（$D\subset N$非空且$D\cap S^{\ast }(\mathcal{V})=\varnothing$），由于最优产品组合唯一，则必然有$p_j<Z^{\ast }(V)$对任意$j\in D$成立（否则根据引理1加入$j$就会更优）。

    令$R_D(\vec{v})=({\sum }_{j\in D}{p}_j{v}_j)/{\sum }_{j\in D}{v}_j$，由于$R_D(\vec{v})$是集合$D$中产品价格的加权平均，且$p_j<Z^{\ast }(V)$对任意$j\in D$成立，则必然有$R_D(\vec{v})<Z^{\ast }(\mathcal{V})$；

    进一步地，因为$Z^{\ast }(\mathcal{V})={\min }_{v\in \mathcal{V}}R(S^{\ast }(\mathcal{V}),\mathcal{V})$，则$\forall \vec{v}\in \mathcal{V}$，有$Z^{\ast }(\mathcal{V})\le R(S^{\ast }(\mathcal{V}),\vec{v})$成立；

    根据上面两个结论，可得$R_D(\vec{v})<Z^{\ast }(\mathcal{V})\le R(S^{\ast }(\mathcal{V}),\vec{v})$

    于是有$\forall \vec{v}\in \mathcal{V}$：
    $$R(\hat{S},\vec{v})=\frac{V(S^{\ast }(\mathcal{V}))R(S^{\ast }(\mathcal{V}),\vec{v})+V_D{R}_D(\vec{v})}{V(S^{\ast }(\mathcal{V}))+V_D}$$
    其中：
    $$\begin{gathered} V(S^{\ast }(\mathcal{V}))=v_0+\sum _{j\in S^{\ast }(\mathcal{V})}{v}_j \\ {V}_D=\sum _{i\in D}{v}_i \end{gathered}$$
    都是定理2证明中的标记，这样就发现$R(\hat{S},\vec{v})$是$R(S^{\ast }(\mathcal{V},\vec{v})$和$R_D(\vec{v})$的凸组合，已知$R_D(\vec{v})<R(S^{\ast }(\mathcal{V}),\vec{v})$，必然有$R_D(\vec{v})<R(\hat{S},\vec{v})$（$\forall \vec{v}\in \mathcal{V}$）

    此时令$i\in D$是$D$中价格最低的产品，即$p_i={\min }_{j\in D}{p}_j$，则$\forall \vec{v}\in \mathcal{V}$，我们有$p_i<R_D(\vec{v})<R(\hat{S},\vec{v})$（加权平均），那么对$\vec{v}$求最小值就有$p_i<{\min }_{\vec{v}\in \mathcal{V}}R(\hat{S},\vec{v})=R(\hat{S},\mathcal{V})$

    利用引理1，对于$S=\hat{S}-i$，我们有$R(\hat{S},\mathcal{V})<R(S,\mathcal{V})$，这与$\hat{S}$是局部最优解矛盾，定理得证。$■$

---

6 两级嵌套逻辑模型的保证 Guarantees for the two-level nested logit model

• NL模型设定：MNL模型的一个缺陷是无关方案的独立性（Independence of Irrelevant Alternatives，下简称为IIA），具体而言就是报价集中两个不同产品的选择概率与其他产品是独立的，即不同的产品必须对等（指在效用值的衡量上），如果主要产品与次要产品混杂，效果就会很差。

  即如果从报价集中移出产品$j$，对产品$j$的需求就会流失到其他产品中（以及不购买的概率中）。则购买产品$j$的客户就会在报价集中剩下的产品中以计算得到的概率选择产品，这往往与实际情况不符合，比如三件产品对客户的效用分别为0.99,0.005,0.005​，如果你移出第一件产品，那么客户就会在剩下两个产品中等可能的挑选吗？显然不会，因为他很可能就是只想要第一件产品，移除第一件产品会大大提高不购买的概率。

  另外笔者还查到一个经典的红蓝巴士悖论：如果某人选择小汽车和巴士（假设所有的巴士都漆成红色）的概率各为0.5，两者的选择概率之比为1:1。现在设原模型中加入一半巴士漆成蓝色的选择枝。蓝巴士和红巴士完全相同，选择他们的概率为1:1。所以加入蓝巴士后，小汽车、红巴士、蓝巴士选择的概率为1:1:1，概率值都为1/3。但通常人们在进行选择时与巴士颜色无关，小汽车、巴士的选择概率仍为0.5，红蓝巴士的选择概率各为0.25，这种模型忽略了红巴士和蓝巴士的紧密相关性。

  另一种情形就是原论文中作者提及的不购买的效用$v_0$远远大于所有产品效用$v_j$的累和，这时候任意删除一个产品后，对该产品的需求几乎全部流入到不购买的渠道中，这也不符合实际情况。

  因此我们为了避免这种情况，就对MNL模型进行扩展，做两个嵌套，第一个嵌套就是不购买选择，剩下的产品选择放到第二个嵌套中。这种变体即为NL模型，它一定程度上缓解了IIA带来的问题（因为不同嵌套间不存在IIA），同时保持MNL模型的优良性质（相对易于求解）。

  NL模型的建立来自参考文献[02]，该模型将产品空间分割为不同的嵌套（nests），每个嵌套$i$与一个相异度（dissimilarity）参数${\rho }_i\ge 0$联系。令$m$表示嵌套的数量，则每个报价集$S$可以表示为元组$(S_1,S_2,...,S_m)$，其中$S_i$表示$S$中属于嵌套$i$的产品子集。每个产品$j$的效用值为$v_j$，一般来说每个嵌套中都会有一个不购买选项，即$v_{0i}$表示嵌套$i$中的不购买效用值，同时会有一个嵌套专门存放不购买选项，该嵌套中的不购买选项的效用值为$v_0$。注意，我们允许$v_{0i}=0$。

  在这种设定下，客户首先会选择一个嵌套，然后再从该嵌套中选择产品。给定报价集$S$，定义$Q_i(S)$表示客户选择嵌套$i$的概率，则嵌套选择概率为：
  $$Q_i(S)=\frac{V_i(S_i{)}^{{\rho }_i}}{v_0+V_i(S_i{)}^{{\rho }_i}}$$

  其中：
  $$V_i(S_i)=v_{0i}+\sum _{j\in S_i}{v}_j$$
  在客户已经选定嵌套$i$的条件下，客户就会以MNL模型选择概率选择该嵌套内的产品，即：
  $$\mathrm{Pr}(j|S)=\sum _i{Q}_i(S)\frac{v_j}{v_{0i}+{\sum }_{j^{\prime }\in S_i}{v}_j}=\sum _i{Q}_i(S)\frac{v_j}{V_i(S_i)}$$
  则收益函数为：
  $$R(S)=\sum _{j\in S}{p}_j\mathrm{Pr}(j|S)$$
  目标是在无容量限制的情况下最大化期望收益。

• 参考文献[07]考察了无容量限制的NL模型，文中证明了该优化问题是多项式时间可解的，若嵌套相异度（dissimilarity）参数都比$1$小（即${\rho }_i<1$）且不购买的选项会被分割在一个单独的嵌套中（此时$v_{0i}=0$对于所有其他嵌套）。若放宽上述假设，则优化问题在弱意义（in a weak sense）上是NP难的，因为可以从分割问题（partition problem）归约得到。

  对于多项式时间可解的情形，参考文献[07]提出一种基于线性规划的解法，参考文献[17]提出另一种贪婪算法来确定收益最大化子集。基于线性规划的解法中包含$O(m)$个决策变量与$O(n)$条约束，贪婪算法运算时间复杂度为$O(n\log m)$（这里虽然没有定义$m$，但是应该是嵌套的数量）。

• 为了推导出本文算法的最优性保证，我们着重研究二级NL的一种特殊情形模型，第一个嵌套中是不购买选项，所有产品都放在另一个嵌套中（嵌套相异度参数$\rho \in [0,1]$），这种最简单的NL模型仅仅缓解相对于不购买情形的IIA问题（但也已经是比较常见的了）。具体而言，需要求解的集合优化问题如下所示：
  $${\text{argmax}}_{S\in N}R(S)={\text{argmax}}_{S\subset N}\frac{{\left({\sum }_{j\in S}{v}_j\right)}^{\rho }}{v_0+{\left({\sum }_{j\in S}{v}_j\right)}^{\rho }}\frac{{\sum }_{j\in S}{p}_j{v}_j}{{\sum }_{j\in S}{v}_j}\text{\hspace{1em}(6)}$$
  假定$p_1>p_2>...>p_n$，参考文献[07]说明式$(6)$规划的最优解必然是收益排序子集（ { 1 } , { 1 , 2 } , . . . , { 1 , 2 , . . . , n } \{1\},\{1,2\},...,\{1,2,...,n\} {1},{1,2},...,{1,2,...,n}）之一，于是我们可以得到如下定理：

• 定理5（无容量限制的NL模型的局部最优解可以由ADXOpt算法得到）：假若我们将增加操作的优先级设置得比删除操作的优先级高，即在每次迭代中，只要一个可行增加操作会提升收益，我们就增加该产品。则$b=1,C=n$的ADXOpt算法收敛到式$(6)$优化问题的局部最优（相对雨增删换），进一步地得到的局部最优解必然收益排序子集之一。

• 说明：上述定理确保了算法能够在多项式次迭代后收敛到局部最优解，然而在最坏的情况下，局部最优解未必是全局最优解，这原因是NL模型具有块状结构（lumpy structure），具体而言，参考文献[17]证明了两级NL模型表现出一种块状特征，使得某些连续索引的产品（价格降序索引）总是同时出现在最大收益子集中，因此算法每次迭代只对一个产品进行局部优化未必能够提升收益，必须同时对这一块的产品同时增删换才能提升收益。

  如果这种块的大小（块中产品的数量）可以用一个常数进行约束（比如$K$），则可以将算法推广为每次对至多$K$个产品进行优化，那么算法复杂度将会以$K$的指数级提升，但是这样可以确保算法能够收敛到全局最优。

  事实上在数值分析模拟实验中，本文证明了在绝大多数情况下（$\approx 98\%$）ADXOpt算法（每次只调整一个产品）可以收敛到最大收益子集（即全局最优解）。因此我们可以说，该算法在最坏的情况下只能收敛到局部最优解，大部分情况下都可以得到全局最优解，可以适用于大部分实际需求。

• 算法复杂度：算法复杂度与我们是否容许替换操作（因为替换操作的复杂度是最高的$O(nC)$）。若只允许增加和删除操作，则算法收敛到局部最优解（相对于增删换）只需要$O(n^2)$步，且必然是一个收益排序子集。

  原因是若某次迭代可以通过替换操作来提升收益，那么总是有一个可行的增加操作或删除操作同样可以提升收益（这个很显然吗？），因此即便不使用替换操作，也能收敛到局部最优解（相对于增删换）。于是我们有如下引理：

  • 引理2（替换操作可以从ADXOpt中移除，仅在此处的二级NL模型设定中成立）：对于任意子集$S$，若存在产品$i\in S,j/inS$使得$R(S+j-i)>R(S)$，则表达式$R(S+j)>R(S)$和$R(S-i)>R(S)$中必然有一个成立。

    引理2的证明详见附录C。

  • 引理3（NL模型中增加或减少产品对收益的影响）：对于任意产品组合$S$以及$j\notin S,i\in S$，有如下结论成立：
    $$\begin{array}{rl}R(S+j)>R(S)& ⟺p_j>R(S)Y(v_j,S)\\ R(S-i)>R(S)& ⟺p_i<R(S)Y(-v_i,S)\end{array}$$
    其中：
    $$\begin{gathered} Y(v,S)=1+v_0\frac{(V(S)+v{)}^{1-\rho }-V(S{)}^{1-\rho }}{v}\forall v>0,\forall S\subseteq N \\ V(S)=v_0+\sum _{j\in S}{v}_j \end{gathered}$$
    引理3的证明详见附录C。

  • 引理4（$Y(v,S)$的性质）：对于任意子集$S$以及任意$a<c$，有$Y(a,S)\ge Y(c,S)$，且$\forall a,S\subset S^{\prime }$，有$Y(a,S)\ge Y(a,S^{\prime })$，即函数$Y(v,S)$相对于$v$单调递减，相对于$S$也是某种意义上单调递减的。

    引理4的证明详见附录C。

    利用引理3和引理4可以得出最优解是收益排序子集的结论，即下面的定理6。

  • 定理6（最优解是收益排序子集）：式$(6)$规划的最优解是收益排序子集之一。

  • 证明（定理6）：反证法。

    假设最优产品组合$S^{\ast }$中的$l\in S^{\ast }$的价格最低，即$p_l={\min }_{l^{\prime }\in S^{\ast }}{p}_{l^{\prime }}$，假设存在一个产品$i$满足$p_i>p_l$且$i\notin S^{\ast }$。

    由于$l\in S^{\ast }$，必然有$R(S^{\ast }-l)<R(S^{\ast })$，因此根据引理3有：
    $$p_l>R(S^{\ast })Y(-v_l,S^{\ast })$$
    注意给定$p_i>p_l$的条件，以及$Y(-v_l,S^{\ast })\ge Y(v_i,S^{\ast })$（根据引理4）的事实，我们有如下一系列的不等式：
    $$p_i>p_l>Y(-v_l,S^{\ast })R(S^{\ast })\ge Y(v_i,S^{\ast })R(S^{\ast })$$
    这就推导出$p_i>Y(v_i,S^{\ast })R(S^{\ast })$（原文写的是$p_i>Y(v_i,S^{\ast })$，应该是写错了。），由于$i\notin S^{\ast }$，利用引理3，可得$R(S^{\ast }+i)>R(S^{\ast })$，与$S^{\ast }$的最优性矛盾。定理得证。$■$

• 正如前文提到的那样，参考文献[07]证明了无容量限制的NL问题（${\rho }_i<1,v_{0i}=0,\forall i$）的最优解是收益排序子集之一，定理6是该结论的另一种证明方法（但是情况是更加简单二级NL模型，只包含两个嵌套），相对来说本文的证明更简单（因为情况也更特殊）。接下来就可以最终证明定理5了。

• 证明（定理5）：证明分为两个论断构成：

  • 论断一：当$b=\infty$，ADXOpt算法的迭代流程可以分割为连续的增加操作，然后连续的删除操作，最后终止。

    证明：反证法。

    令$t_1$表示第一次删除操作发生时的迭代次数，$S_1$表示第一次删除操作前的产品组合，$i$表示第一次删除的产品。

    令$t>t_1$是第$t_1$次迭代后第一次增加操作发生的迭代，且增加的产品为$j$，令$S_2$表示这次增加操作前的产品组合。

    于是必然有（因为算法每次迭代一定使得收益提升）：
    $$R(S_1)<R(S_1-i)\le R(S_2)<R(S_2+j)$$
    进一步地，必然有$S_2\subseteq (S_1-i)$（这是显然的，因为从$S_1$到$S_2$这段过程中，算法一直在删除产品）。

    接下来分两种情况讨论（下面两种情况指的应该是在第$t$次迭代增加产品$j$前是否发生过情况中所述的事情）以说明上述这种不符合论断一的情形是不能成立的：

    • 情况一：算法迭代中产品$j$从未被增加到产品子集中。

      根据引理3，可得$R(S_2+j)>R(S_2)⟹p_j>R(S_2)Y(v_j,S_2)$。

      根据引理4，由于$S_2\subseteq S_1$，可得$R(S_2)>R(S_1)$以及$Y(v_j,S_2)\ge Y(v_j,S_1)$，于是有：
      $$p_j>R(S_2)Y(v_j,S_2)>R(S_1)Y(v_j,S_1)$$

      根据引理3，可得$R(S_1+j)>R(S_1)$，换言之，即从$S_1$开始，将产品$j$增加到$S_1$中将会提升收益。

      由于$b=\infty$，且增加$j$是可行的操作（因为提升收益），因此当我们将增加操作的优先级设置为比删除操作的优先级高的时候，产品$j$必然会在第$t_1$次迭代中被增加到产品子集中。这与产品$i$在第$t_1$次迭代被删除是矛盾的，情况一不能成立。

    • 情况二：算法迭代中产品$j$先被增加，再被删除，最后又被增加到产品子集中。

      

  <font face=times new roman>假定产品$j$在第$t_2$次迭代中被删除（$t_1<t_2<t$），设$S$表示在第$t_2$次迭代删除产品$j$前的产品子集，则必然有（从$S$到$S_2$中，收益不断提升）：</font>
  $$
  R(S)<R(S-j)\le R(S_2)<R(S_2+j)
  $$
  <font face=times new roman>进一步地，必然有$S_2\subseteq(S-j)$（因为从$S_2$到$S$一直在删除产品），因此$R(S_2)<R(S_2+j)$，根据**引理3**可得$p_j>R(S_2)Y(v_j,S_2)$。</font>

  <font face=times new roman>进一步地，已知$R(S_2)\ge R(S-j)$与$Y(v_j,S_2)\ge Y(v_j,S-j)$（由**引理4**可知，因为$S_2\subseteq(S-j)$），因此有如下结论：</font>
  $$
  p_j>R(S_2)Y(v_j,S_2)\ge R(S-j)Y(v_j,S-j)
  $$
  <font face=times new roman>于是根据**引理3**就有$R(S)>R(S-j)$，这就与$R(S)<R(S-j)$的假定矛盾。第二种情况不能成立。</font>

<font face=times new roman>至此，当$b=\infty$，ADXOpt算法的迭代流程必然可以分割为连续的增加操作，然后连续的删除操作，最后终止。论断一得证。</font>

• 论断二：当$b=1$，算法在一个收益排序子集终止，并相对于增加操作与删除操作这是一个局部最优解。

  证明：令$\hat{S}$表示算法最终输出的产品子集，首先我们说明$\hat{S}$相对于增删两个操作是局部最优的。

  显然相对于删除操作是最优的，否则算法不会终止（就把对应的产品删掉，就可以得到更高的收益）。

  类似地，对于那些在算法迭代中从未被增加到产品子集中的产品$j$，必然有$R(\hat{S}+j)\le R(\hat{S})$（否则总是可以把$j$加入到产品子集中以提升收益）。

  现在我们考察被增加后又被删除的产品$j$，根据论断一，即便$b=\infty$，一旦某个产品被删除，就不可能再有任何产品被增加到产品子集中（前面都是增加，后面都是删除），因此也必然有$R(\hat{S}+j)\le R(\hat{S})$。

  综上所述，相对于增删两个操作是局部最优的。

  最后我们说明$\hat{S}$是一个收益排序子集，反证法，假定存在$j\notin \hat{S}$与$i\in \hat{S}$满足$p_j>p_i$，由于$\hat{S}$是局部最优解，因此必然有$R(\hat{S}-i)\le R(\hat{S})$，根据引理3可得$p_i\ge R(\hat{S})Y(-v_i,\hat{S})$，再根据引理4可得$Y(-v_i,\hat{S})\ge Y(v_j,\hat{S})$，于是有：
  $$p_j>p_i\ge R(\hat{S})Y(-v_i,\hat{S})\ge R(\hat{S})Y(v_j,\hat{S})$$
  现在根据引理3可得$R(\hat{S}+j)>R(\hat{S})$，与$\hat{S}$是局部最优解（相对于增删操作）矛盾，论断二得证。

定理5得证。$■$

---

7 混合逻辑模型 Mixed logit model

• ML模型设定：又称潜在类别（latent-class）MNL模型（或离散混合MNL模型），具体而言，假定人群被划分为$K$种不同的客户类别，客户类别$k$可以用参数向量为${\vec{v}}_k=(v_{0k},v_{k1},v_{k2},...,v_{kn})$的MNL模型构成，于是选择概率为：
  $$\mathrm{Pr}(j|S)=\sum _{k=1}^K{\alpha }_k\frac{v_{kj}}{v_{0k}+{\sum }_{j^{\prime }\in S}{v}_{k{j}^{\prime }}}$$
  其中${\alpha }_k>0$表示混合比例，且${\sum }_{k=1}^K{\alpha }_k=1$，则收益函数为：
  $$R(S)=\sum _{j\in S}{p}_j\mathrm{Pr}(j|S)$$
  参考文献[20]证明了ML模型的设定是非常一般（general）的，可以用于近似任意的离散选择模型（第二节课江波有提过），那么可以预想得到的是，它的求解会非常困难。参考文献[03]证明了ML模型设定下的无容量限制的产品组合优化问题是严格意义上的NP难（当客户类别数至少为$n$，即大于产品总数），因为它可以从最小顶点覆盖（minimum vertex cover problem）归约得到。参考文献[28]将NP难（弱意义上的）的结论扩展到只有两个客户类别的情况，因为可以从分割问题（partition problem）归约得到。

• 本文考虑的ML模型变体：因为ML模型的一般情况真的很困难，本文只关注下面这种特殊的变体。假定不同的客户类仅仅在不购买的效用（即$v_{0k}$）上有所不同，所有其他产品的效用值在不同客户类中都是相同的，具体而言，令$w_k$表示$v_{0k}$，$v_j$表示$v_{kj}$，则选择概率可以改写为：
  $$\mathrm{Pr}(j|S)=\sum _{k=1}^K{\alpha }_k\frac{v_j}{w_k+{\sum }_{j^{\prime }\in S}{v}_{j^{\prime }}}$$
  目标是求解下面的集合优化问题：
  $${\text{argmax}}_{S\subseteq N}\sum _{k=1}^K{\alpha }_k\frac{{\sum }_{j\in S}{p}_j{v}_j}{w_k+{\sum }_{j\in S}{v}_j}\text{\hspace{1em}(7)}$$
  上述的ML模型变体类似参考文献[28]中提出的产品独立价格敏感度（product-independent price sensitivity），参考文献[28]中证明了最优解必然是收益排序子集之一，本文给出该结论的另一种证明，并说明ADXOpt算法（$b=1$）能够取得局部最优解。

• 定理7（无容量限制的鲁棒ML模型局部最优解可以由ADXOpt算法得到）：假定设置增加操作的优先级高于删除操作（即在每次迭代中只要增加操作能提升收益，就优先进行增加操作），则$b=1,C=n$的ADXOpt算法收敛到式$(7)$规划的局部最优（相对于增删换操作），进一步地，局部最优解是一个收益排序子集。

• 说明：定理7确保算法能够在多项式时间内收敛到局部最优，然而在最坏地情况下，局部最优并非全局最优，但是数值分析地模拟实验表明，在$99\%$的情况下，算法收敛到收益最大子集。

• 算法复杂度：取决于是否允许替换操作，如果不允许替换操作，则$O(n^2)$次迭代收敛到局部最优，且忽略替换操作依然可以得到局部最优（相对于增删换操作），因为若某次迭代中通过替换操作能够提升收益，则总是有一个可行的增加或删除操作可以提升收益（这跟NL模型中的相关论述类似）。

• 引理5（ADXOpt算法中无需考虑替换操作）：对于任意子集$S$，若存在产品$i\in S$与$j\notin S$使得$R(S+j-i)>R(S)$，则表达式$R(S+j)>R(S)$与$R(S-i)>R(S)$总有一个能成立。（证明可由引理2直接得到）

• 引理6（增加或删除产品对ML模型收益的影响）：对于任意产品组合$S$与产品$j\notin S$与$i\in S$，必然有：
  $$\begin{array}{rl}R(S+j)>R(S)& ⟺p_j>R(S)X(v_j,S)\\ R(S-i)>R(S)& ⟺p_i<R(S)X(-v_i,S)\end{array}$$
  其中有：
  $$\begin{gathered} X(v,S)=\frac{{\sum }_{k=1}^K{\alpha }_k/(W_k(S)(W_k(S)+v))}{\left({\sum }_{k=1}^K{\alpha }_k/W_k(S)\right)\left({\sum }_{k=1}^K{\alpha }_k/(W_k(S)+v)\right)}\forall v>0,S\subseteq N \\ {W}_k(S)=w_k+\sum _{j\in S}{v}_j \end{gathered}$$

• 引理7（$X(v,S)$的性质）：$\forall S\subseteq N$，若$a<c$，则$X(a,S)\ge X(c,S)$（$X$关于$v$单调递减）；$\forall a$，若$S\subset S^{\prime }$，则$X(a,S)\ge X(a,S^{\prime })$（$X$关于$S$单调递减）。

• 引理6和引理7的证明详见附录D，最后我们就可以得到最优解是收益排序子集的结论。

• 定理8（最优解是收益排序子集）：式$(7)$规划的最优解是收益排序子集。

• 定理8的证明完全类同定理6的证明（基于引理6和引理7），定理7的证明完全类同定理5的证明。$■$

---

8 数值分析 Numerical study

• 本文进行了两个模拟研究来论述ADXOpt算法的有效性：

  • 第一个研究旨在论述我们的算法可以得到许多一般的选择模型架构的很好的近似解。

  • 第尔研究旨在论述在实际设定中，使用我们的算法求解复杂模型得到的近似解要比使用简单模型求解得到的精确解更好。

8.1 增删换优化算法对于一般选择结构的表现 Performance of ADXOpt algorithm for general choice structures

• 理论部分已经证明ADXOpt算法对MNL模型以及鲁棒MNL模型能够求解全局最优，但是对于NL模型和ML模型只能求解得到局部最优。本文将说明，即便在最差的情况下只能收敛到局部最优，ADXOpt算法依然在平均意义上提供一个很好的近似解。

• 测试的几种模型：考察三个模型类：

  • NL2（即本文第6节的二级NL模型设定，两个嵌套，相异度参数$0<\rho <1$）：

• ML-DIS（即本文第7节考察的ML模型变体）：这里的DIS表示的是dis-utility，因为其实相当于对每个客户类别在每个产品上增加的一个(dis-)utility项即可忽略掉不购买效用值在不同客户类别中的区别。

• ML（最一般的ML模型）

• 模拟实验设定：对每个模型类随机生成1000个模型实例，产品数量考虑$n=10$和$n=15$两种情况，产品价格采样自区间$[100,150]$上的均匀分布，具体各个模型类的参数如下所示：

  • NL2：嵌套相异度参数取自区间$[0,1]$上的均匀分布，产品效用值$v_j$采样自$[0,10]$地均匀分布。

• ML-DIS：客户类别数$K=5$，混合权重${\alpha }_k$采样自$[0,1]$的均匀分布（归一化以确保和为1），不同客户类地不购买效用值$w_k$采样自区间$[0,10]$的均匀分布。

  • ML：客户类别数$K=5$，混合权重${\alpha }_k$采样自$[0,1]$的均匀分布（归一化以确保和为1），每个客户类中会随机挑选4个产品，产品的效用值采样自$[0,10]$的均匀分布，没有被挑选到产品的效用值就是0。

  模拟实验结果如Table 1所示：可以发现大部分情况下ADXOpt算法都收敛到最优解。

  

  表中的两个指标定义如下所示（$L=1000$，$\text{NonOpt}$是指算法未能达到最优解的模拟实验数量，$S_l^{\ast }$和${\hat{S}}_l$分别在模型实例$l$下的最优子集和算法生成的近似解）：
  $$\begin{array}{rl}\text{OptGapAll}& =\frac{1}{L}\sum _{l=1}^L\frac{R(S_l^{\ast })-R({\hat{S}}_l)}{R(S_l^{\ast })}\\ \text{GapNonOpt}& =\frac{1}{|\text{NonOpt}|}\sum _{l\in \text{NonOpt}}\frac{R(S_l^{\ast })-R({\hat{S}}_l)}{R(S_l^{\ast })}\end{array}$$
  总之算法在最坏情况下得到的近似解相对于全局最优的差距不超过$3\%$，且算法在大部分情况下都能达到全局最优（NL模型和ML模型中）。

8.2 数据到决策 Data to decision

• 本小节将论述使用ADXOpt算法求解复杂模型得到的近似解优于简单模型的精确解，具体将从实际案例对应的数据出发论述。

• 以客户交易场景为例，目标是找到收益最大子集，典型的方法是使用一个需求模型（demand model）来拟合数据，然后精确地或近似地求解决策问题，而在对需求模型的选择时通常会考虑模型的拟合程度（预测能力）以及对应的决策模型的求解能力，简单的模型通常对应易于求解的决策问题，但是往往对数据的拟合程度（预测能力）交叉，复杂的模型通常对数据拟合得更好，但是往往不易于求解。接下来我们比较两种不同方法的实际性能：

  • 简单模型对应的决策问题可以直接求解最优解。

  • 复杂模型对应的决策问题只能使用本文的算法求解近似解。

• 为了论述上述两种方法的权衡（trade-off），本文设计了如下的实验：

  • 首先给定一个ML模型（带有5个客户类别以及15个产品）作为校正模型（ground-truth model）；

  • 然后生成该模型的1000个实例，对于每个模型实例，生成人造的交易数据（20个集合，每个集合的大小为 { 1 , 2 , 3 , 4 , 5 , 6 , 7 } \{1,2,3,4,5,6,7\} {1,2,3,4,5,6,7}的离散均匀分布）；

  • 对于每个实例，交易数据用于拟合两个模型：标准的MNL模型和参考文献[08]提出的具有高预测能力的广义无参数方法（general non-parametric method）；

  • MNL模型可以直接求解决策问题的最优解，我们使用ADXOpt算法来对后一种模型进行估计得到近似解，结果如Table 2所示：

    

    这里的指标定义与上面一个模拟实验是完全相同的：
    $$\begin{array}{rl}\text{OptGapAll}& =\frac{1}{L}\sum _{l=1}^L\frac{R(S_l^{\ast })-R({\hat{S}}_l)}{R(S_l^{\ast })}\\ \text{GapNonOpt}& =\frac{1}{|\text{NonOpt}|}\sum _{l\in \text{NonOpt}}\frac{R(S_l^{\ast })-R({\hat{S}}_l)}{R(S_l^{\ast })}\end{array}$$
    $L=1000$为仿真次数，$\text{NonOpt}$是ADXOpt算法未能取得最优解的实例集合，$S_l^{\ast }$与${\hat{S}}_l$分别表示实例$l$的最优解子集和算法输出的近似解。$R(\cdot )$是校正的（ground-truth）收益函数。

    结果表明第二种复杂模型在$44\%$的情况下找到了收益最大子集（规模不超过10），而简单模型MNL只能做到$25\%$，此外无参方法与ADXOpt的结合相比于MNL模型与ADXOpt的结合能提供更好的估计。总体而言无参方法相比于MNL模型有$72\%$的提升，即便只是考察次优（sub-optimal）的实例，无参方法也要比MNL模型好$63\%$。

---

9 总结与讨论 Summary and discussion

• 总结：本文重点研究一般选择模型下的组合优化问题。假设访问收益预测子程序，我们设计了一个通用的集合优化算法，以尽可能少地调用收益子程序来估计集合元素最多为$C$的收益最大子集。

  本文提出一种局部搜索算法（ADXOpt算法），该算法通过在每次迭代中添加或删除产品或以贪婪的方式交换一对产品来迭代搜索最优子集。为了确保算法在多项式时间内收敛，我们限制了每个产品被移出候选子集的次数。与现有方法对比，后者侧重于利用假设选择模型的结构；因此，现有的算法（即使没有任何保证）也不能与一般选择模型一起使用。

  另一方面，我们的算法不适合特定的参数结构，并且只需要一个子程序来为产品组合提供收益估计。我们的算法有充分的理论保证：MNL模型的有容量限制和无容量限制的组合优化问题以及鲁棒MNL模型的无容量限制的组合优化问题都能通过ADXOpt算法收敛到最优解。此外，我们证明了NL模型和ML模型的特定变体也能收敛到局部最优。

  本文还进行了数值分析，验证了ADXOpt算法在各种模型实例中的准确性。最后，我们的算法允许在研究模型的预测准确性和优化模型的能力之间的权衡。

• 展望：首先，算法的理论分析可以扩展到一般的NL模型和ML模型的其他变体。我们推测该算法将收敛到一般NL模型的局部最优值（即存在一个只包含不购买的嵌套，然后嵌套相异度参数取值范围在$0<\rho <1$）。 此外，我们的数值研究表明，即使在算法没有收敛到最优解的情况下，它为最优决策提供了很好的近似。

  本文提出的算法可以通过允许在每个操作中添加、删除和交换多个产品来进行进一步地扩展（见NL模型地块状结构部分地论述），这种灵活性肯定会增加算法的计算复杂度，但会产生更高质量的结果，了解此类扩展的好处是未来的一个潜在方向。

  另一个方向是限制子集地可行域，本文的设定中子集仅受容量限制。然而，在实践中，有几个考虑因素限制了可行子集的类别。如果这些限制具有良好地结构性，则可以使优化问题更易于求解。

  最后，我们的分析使我们能够研究模型的预测准确性和我们优化模型的能力之间的权衡。进一步了解这种权衡将为我们指明开发预测性需求模型和相应优化方案的正确方向。

  

---

参考文献 References

[01] P P Belobaba and C Hopperstad. Boeing/MIT simulation study: PODS results update. In 1999 AGIFORS Reservations and Yield Management Study Group Symposium, April, pages 27–30, 1999.
[02] M E Ben-Akiva and S R Lerman. Discrete choice analysis: theory and application to travel demand. CMIT press, Cambridge, MA, 1985.
[03] Juan Jos´e Miranda Bront, Isabel M´endez-D´ıaz, and Gustavo Vulcano. A Column Generation Algorithm for Choice-Based Network Revenue Management. Operations Research, 57(3):769–784, June 2009.
[04] G´erard P Cachon, Christian Terwiesch, and Yi Xu. Retail Assortment Planning in the Presence of Consumer Search. Manufacturing & Service Operations Management, 7(4):330–346, October 2005.
[05] S R Chandukala, J Kim, and T Otter. Choice Models in Marketing. Now Publishers Inc, 2008.
[06] J M Chaneton and G Vulcano. Computing bid prices for revenue management under customer choice behavior. Manufacturing & Service Operations Management, 2011.
[07] James M Davis, Guillermo Gallego, and Huseyin Topaloglu. Assortment Optimization Under Variants of the Nested Logit Model. Operations Research, 62(2):250–273, April 2014.
[08] Vivek F Farias, Srikanth Jagabathula, and Devavrat Shah. A Nonparametric Approach to Modeling Choice with Limited Data. Management Science, 59(2):305–322, February 2013.
[09] Guillermo Gallego and Huseyin Topaloglu. Constrained assortment optimization for the nested logit model. Technical report, 2012a.
[10] Guillermo Gallego and Huseyin Topaloglu. Constrained assortment optimization for the nested logit model. 2012b.
[11] Guillermo Gallego, G Iyengar, R Phillips, and A Dubey. Managing flexible products on a network. 2006.
[12] Michael R Garey and D S Johnson. Computers and Intractability. A Guide to the Theory of NPCompleteness. W H Freeman & Company, January 1979.
[13] W H Greene. Econometric analysis, 2003.
[14] Srikanth Jagabathula and Paat Rusmevichientong. A Two-Stage Model of Consideration Set and Choice: Learning, Revenue Prediction, and Applications. SSRN Electronic Journal, 2013.
[15] Sumit Kunnumkal and Huseyin Topaloglu. A refined deterministic linear program for the network revenue management problem with customer choice behavior. Naval Research Logistics (NRL), 55(6):563–580, September 2008.
[16] Sumit Kunnumkal and Huseyin Topaloglu. A New Dynamic Programming Decomposition Method for the Network Revenue Management Problem with Customer Choice Behavior. Production and Operations Management, 19(5):575–590, September 2010.
[17] Guang Li and Paat Rusmevichientong. A greedy algorithm for the two-level nested logit model. Operations Research Letters, 42(5):319–324, July 2014.
[18] Qian Liu and G van Ryzin. On the choice-based linear programming model for network revenue management. Manufacturing & Service Operations Management, 2008.
[19] S Mahajan and G J van Ryzin. On the Relationship between Inventory Costs and Variety Benefits in Retail Assortments. Management Science, 45(11):1496–1509, 1999.
[20] D McFadden and K Train. Mixed MNL models for discrete response. Journal of Applied Econometrics, 15 (5):447–470, September 2000.
[21] Nimrod Megiddo. Combinatorial Optimization with Rational Objective Functions. Mathematics of Operations Research, 4(4):414–424, November 1979.
[22] Joern Meissner and Arne Strauss. Improved bid prices for choice-based network revenue management. European Journal of Operational Research, 217(2):417–427, March 2012a.
[23] Joern Meissner and Arne Strauss. Network revenue management with inventory-sensitive bid prices and customer choice. European Journal of Operational Research, 216(2):459–468, January 2012b.
[24] Isabel M´endez-D´ıaz, Juan Jos´e Miranda-Bront, Gustavo Vulcano, and Paula Zabala. A branch-and-cut algorithm for the latent-class logit assortment problem. Discrete Applied Mathematics, 2012.
[25] R M Ratliff, V Rao, C P Narayan, and K Yellepeddi. A multi-flight recapture heuristic for estimating unconstrained demand from airline bookings. Journal of Revenue and Pricing Management, 7(2): 153–171, 2008.
[26] Paat Rusmevichientong and Huseyin Topaloglu. Robust Assortment Optimization in Revenue Management Under the Multinomial Logit Choice Model. Operations Research, 60(4):865–882, August 2012.
[27] Paat Rusmevichientong, Zuo-Jun Max Shen, and David B Shmoys. Dynamic Assortment Optimization with a Multinomial Logit Choice Model and Capacity Constraint. Operations Research, 58(6):1666–1680, December 2010.
[28] Paat Rusmevichientong, David Shmoys, Chaoxu Tong, and Huseyin Topaloglu. Assortment Optimization under the Multinomial Logit Model with Random Choice Parameters. Production and Operations Management, March 2014.
[29] K Talluri and G J van Ryzin. Revenue management under a general discrete choice model of consumer behavior. Management Science, 50(1):15–33, 2004a.
[30] K T Talluri and G J van Ryzin. The Theory and Practice of Revenue Management. Springer Science+Business Media, 2004b.
[31] K E Train. Discrete choice methods with simulation, 2009.
[32] G J van Ryzin and G Vulcano. Computing Virtual Nesting Controls for Network Revenue Management Under Customer Choice Behavior. Manufacturing & Service Operations Management, 10(3):448–467, 2008.
[33] G Vulcano, G van Ryzin, and W Chaar. OM Practice—Choice-Based Revenue Management: An Empirical Study of Estimation and Optimization. Manufacturing & Service Operations Management, 12(3):371– 392, 2010.
[34] D Zhang. An improved dynamic programming decomposition approach for network revenue management. Manufacturing & Service Operations Management, 2011.
[35] Dan Zhang and Daniel Adelman. An Approximate Dynamic Programming Approach to Network Revenue Management with Customer Choice. Transportation Science, 43(3):381–394, August 2009.

---

附录 Appendix

A 第四节第二小节对于多项逻辑模型的证明 Proofs for the MNL model in Section 4.2

• 为了证明定理3，我们需要一些额外的标记：

  $\forall z\in \mathbb{R}$以及$\forall j\in N$，设$h_j(z)=v_j(p_j-z)$，进一步地，给定容量限制$0\le C\le n$，令$S^{\ast }(z)$表示根据$h_j(z)$的值，选出值最高的至多C个满足$h_j(z)>0$的产品，即：
  $$S_C^{\ast }(z)={\text{argmax}}_{S\subset N:|S|\le C}\sum _{j\in S}{h}_j(z)$$
  最后令$z_C^{\ast }$表示有容量限制的组合优化问题的最优收益值，给定这些标记，我们知道式$(4)$规划的最优解$S_C^{\ast }$满足$S_C^{\ast }=S_C^{\ast }(z_C^{\ast })$（参考文献[27]）

• 定义函数$f:{\mathbb{R}}_{+}\to \mathbb{R}$：
  $$f(z)=\{\begin{array}{rlrl}& \underset{j\in S_C^{\ast }(z)}{\min }{h}_j(z)& & \text{if }{S}_C^{\ast }(z)\ne \varnothing \\ & 0& & \text{otherwise}\end{array}$$
  由于$h_j(\cdot )$是线性函数对于任意$j\in N$，因此显然$f(\cdot )$是分段线性函数（piece-wise linear function），且每一个间断点对应两条直线$h_j(\cdot )$与$h_{j^{\prime }}(\cdot )$的交点横坐标。因此至多有$n^2$个间断点。

  我们称直线$h_j$从顶部（from top）交$f$于点$z$，当且仅当$h_j(z)=f(z),h_j(z^{-})\ge f(z^{-}),h_j(z^{+})\le (z^{+})$。

  类似地，称直线$h_j$从底部（from top）交$f$于点$z$，当且仅当$h_j(z)=f(z),h_j(z^{-})\le f(z^{-}),h_j(z^{+})\ge (z^{+})$。

  最后，称直线$h_j$从顶部交直线$h_{j^{\prime }}$于点$z$，当且仅当$h_j(z)=h_{j^{\prime }}(z),h_j(z^{+})<h_{j^{\prime }}(z^{+})$；称直线$h_j$从底部交直线$h_{j^{\prime }}$于点$z$，当且仅当$h_j(z)=h_{j^{\prime }}(z),h_j(z^{+})<h_{j^{\prime }}(z^{+})$

  为了证明有容量约束情形的定理，我们需要定义如下几个命题：

• 命题1：任意直线$h_j$从顶部交$f$于至多 min ⁡ { C , n − C + 1 } \min\{C,n-C+1\} min{C,n−C+1}个点。

• 命题2：对于任意两个产品组合$S_1$和$S_2$，必然成立：
  ∑ j ∈ S 1 h j ( z ) > ∑ j ∈ S 2 h j ( z ) ⟺ R ( S 1 ) > R ( S 2 ) , ∀ z ∈ { R ( S 1 ) , R ( S 2 ) } \sum_{j\in S_1}h_j(z)>\sum_{j\in S_2}h_j(z)\Longleftrightarrow R(S_1)>R(S_2),\forall z\in\{R(S_1),R(S_2)\} j∈S1​∑​hj​(z)>j∈S2​∑​hj​(z)⟺R(S1​)>R(S2​),∀z∈{R(S1​),R(S2​)}

• 命题3：假设产品$j$在算法第$t-1$次迭代中从产品子集中被移出（对应删除和替换操作），则必然有$h_j(z_t)<f(z_t)$，其中$z_t=R(S^t)$且$S^t$是第$t$次迭代结束的最优产品组合估计量。

• 这部分的证明实在是太长了，笔者就不做笔注了，关于上述三个命题的证明在原文附录A中有详细说明，利用这三个命题的结论可以证明定理3的结论。（本文证明中有不少地方标记都有点问题，要注意甄别）

B 第五节对于鲁棒多项逻辑模型的证明 Proofs for the Robust MNL model in Section 5

• 证明（引理1）：考察任意$\vec{v}\in \mathcal{V}$，令$V(S)=v_0+{\sum }_{i\in S}{v}_i$，观察到$R(S+j,\vec{v})$是$p_j$和$R(S,\vec{v})$的凸组合:
  $$R(S+j,\vec{v})=\frac{v_j{p}_j+V(S)R(S,\vec{v})}{v_j+V(S)}$$
  因此，若$p_j\ge R(S,v)$，则$p_j\ge R(S+j,\vec{v})\ge R(S,v)$；若$p_j<R(S,v)$，则$p_j<R(S+j,\vec{v})<R(S,v)$

  于是证明分为两步：

  • $p_j<R(S,\mathcal{V})⟹R(S+j,\mathcal{V})<R(S,\mathcal{V})$

    证明：由于$R(S,\mathcal{V})\le R(S,\vec{v}),\forall \vec{v}\in \mathcal{V}$，因此$p_j<R(S,\vec{v}),\forall \vec{v}\in \mathcal{V}$，因此$R(S+j,\vec{v})<R(S,\vec{v}),\forall \vec{v}\in \mathcal{V}$，对两边求最小值，则有${\min }_{\vec{v}\in \mathcal{V}}<{\min }_{\vec{v}\in \mathcal{V}}R(S,\vec{v})$，可得$R(S+j,\mathcal{V})<R(S,\mathcal{V})$，于是结论成立。（注意之所以两边取最小值保持严格的不等号是因为$\mathcal{V}$是紧集）

  • $p_j\ge R(S,\mathcal{V})⟹R(S+j,\mathcal{V})\ge R(S,\mathcal{V})$

    证明：令${\mathcal{V}}_1\subseteq \mathcal{V}$是使得$p_j<R(S,\vec{v}),\forall v\in {\mathcal{V}}_1$，类似地，令${\mathcal{V}}_2\subseteq \mathcal{V}$是使得$p_j\ge R(S,\vec{v}),\forall v\in {\mathcal{V}}_2$，则显然$\mathcal{V}={\mathcal{V}}_1\cup {\mathcal{V}}_2$且${\mathcal{V}}_1\cap {\mathcal{V}}_2=\varnothing$；

    由于$p_j\ge {\min }_{\vec{v}\in \mathcal{V}}R(S,\vec{v})$，可得${\mathcal{V}}_2\ne \varnothing$；

    首先注意到由于$R(S,{\vec{v}}_2)\le p_j<R(S,{\vec{v}}_1),\forall {\vec{v}}_1\in {\mathcal{V}}_1,\forall {\vec{v}}_2\in {\mathcal{V}}_2$，则立刻可得：
    R ( S , V ) = min ⁡ v ⃗ ∈ V R ( S , v ⃗ ) = min ⁡ v ⃗ 1 ∈ V 1 , v ⃗ 2 ∈ V 2 min ⁡ { R ( S , v ⃗ 1 ) , R ( S , v ⃗ 2 ) } = min ⁡ v ⃗ 1 ∈ V 1 , v ⃗ 2 ∈ V 2 R ( S , v ⃗ 2 ) = min ⁡ v ⃗ 2 ∈ V 2 R ( S , v ⃗ 2 ) (9) \begin{aligned} R(S,\mathcal{V})&=\min_{\vec v\in \mathcal{V}}R(S,\vec v)\\ &=\min_{ \vec v_1\in \mathcal{V}_1,\vec v_2\in\mathcal{V_2}}\min\{R(S,\vec v_1),R(S,\vec v_2)\}\\ &=\min_{ \vec v_1\in \mathcal{V}_1,\vec v_2\in\mathcal{V_2}} R(S,\vec v_2)\\ &=\min_{\vec v_2\in\mathcal{V_2}} R(S,\vec v_2) \end{aligned}\tag{9} R(S,V)​=v ∈Vmin​R(S,v )=v 1​∈V1​,v 2​∈V2​min​min{R(S,v 1​),R(S,v 2​)}=v 1​∈V1​,v 2​∈V2​min​R(S,v 2​)=v 2​∈V2​min​R(S,v 2​)​(9)
    其中第二个等号成立的原因是$R(S,{\vec{v}}_2)<R(S,{\vec{v}}_1),\forall {\vec{v}}_1\in {\mathcal{V}}_1,\forall {\vec{v}}_2\in {\mathcal{V}}_2$

    于是根据我们的定义，$\forall {\vec{v}}_1\in {\mathcal{V}}_1$，有$p_j<R(S+j,{\vec{v}}_1)<R(S,{\vec{v}}_1)$，类似地，对于任意${\vec{v}}_2\in {\mathcal{V}}_2$，有$p_j\ge R(S+j,{\vec{v}}_2)\ge R(S,{\vec{v}}_2)$，于是就有$R(S+j,{\vec{v}}_2)\le p_j<R(S+j,{\vec{v}}_1)$，因此有：
    R ( S + j , V ) = min ⁡ v ⃗ ∈ V R ( S + j , v ⃗ ) = min ⁡ v ⃗ 1 ∈ V 1 , v ⃗ 2 ∈ V 2 min ⁡ { R ( S + j , v ⃗ 1 ) , R ( S + j , v ⃗ 2 ) } = min ⁡ v ⃗ 1 ∈ V 1 , v ⃗ 2 ∈ V 2 R ( S + j , v ⃗ 2 ) = min ⁡ v ⃗ 2 ∈ V 2 R ( S + j , v ⃗ 2 ) ≥ min ⁡ v ⃗ 2 ∈ V 2 R ( S , v ⃗ 2 ) = R ( S , V ) \begin{aligned} R(S+j,\mathcal{V})&=\min_{\vec v\in\mathcal{V}}R(S+j,\vec v)\\ &=\min_{ \vec v_1\in \mathcal{V}_1,\vec v_2\in\mathcal{V_2}}\min\{R(S+j,\vec v_1),R(S+j,\vec v_2)\}\\ &=\min_{ \vec v_1\in \mathcal{V}_1,\vec v_2\in\mathcal{V_2}}R(S+j,\vec v_2)\\ &=\min_{\vec v_2\in\mathcal{V_2}}R(S+j,\vec v_2)\\ &\ge \min_{\vec v_2\in\mathcal{V_2}}R(S,\vec v_2)\\ &=R(S,\mathcal{V}) \end{aligned} R(S+j,V)​=v ∈Vmin​R(S+j,v )=v 1​∈V1​,v 2​∈V2​min​min{R(S+j,v 1​),R(S+j,v 2​)}=v 1​∈V1​,v 2​∈V2​min​R(S+j,v 2​)=v 2​∈V2​min​R(S+j,v 2​)≥v 2​∈V2​min​R(S,v 2​)=R(S,V)​
    其中第一个不等号来自$R(S+j,{\vec{v}}_2)\ge R(S,{\vec{v}}_2),\forall {\vec{v}}_2\in {\mathcal{V}}_2$的事实，最后一个不等号来自式$(9)$。

    注意到若$p_j=R(S,\mathcal{V})$，则$p_j=R(S,{\vec{v}}_2),\forall {\vec{v}}_2\in {\mathcal{V}}_2$，于是有$R(S+j,{\vec{v}}_2)=R(S,{\vec{v}}_2),\forall {\vec{v}}_2\in {\mathcal{V}}_2$，于是上式中唯一的不等号将在$R(S+j,\mathcal{V})=R(S,\mathcal{V})$时成立。

  综上所述，引理1得证。$■$

C 第六节对于嵌套逻辑模型的证明 Proofs for the nested logit model in Section 6

• 证明（引理2）：我们说明若$R(S+j)\le R(S)$，则$R(S+j-i)>R(S)$必然可以推出$R(S-i)>R(S)$。

  因为$R(S+j)\le R(S)$以及$R(S+j-i)>R(S)$，则有$R(S+j)<R(S+j-i)$，此处引用引理3即可得$p_j<R(S+j)Y(-v_j,S+j)$，又因为有$Y(-v_i,S+j)\le Y(-v_i,S)$（由引理4可得），以及$R(S+j)\le R(S)$，则有$p_i<R(S+j)Y(-v_i,S+j)\le R(S)Y(-v_i,S)$，根据引理3可得$R(S-i)>R(S)$。证毕。$■$

• 证明（引理3）：为了简化标记，令$r(S)={\sum }_{k\in S}{p}_k{v}_k/V(S)$，则有：
  $$\begin{array}{rl}R(S+j)-R(S)& =\frac{V(S+j{)}^{\rho }}{v_0+V(S+j{)}^{\rho }}\frac{p_j{v}_j+{\sum }_{k\in S}{p}_k{v}_k}{V(S+j)}-\frac{V(S{)}^{\rho }}{v_0+V(S{)}^{\rho }}\frac{{\sum }_{k\in S}{p}_k{v}_k}{V(S)}\\ & =\frac{V(S+j{)}^{\rho }}{v_0+V(S+j{)}^{\rho }}\left[\frac{v_j{p}_j+V(S)r(S)}{V(S+j)}-\frac{V(S{)}^{\rho }}{V(S+j{)}^{\rho }}\frac{v_0+V(S+j{)}^{\rho }}{v_0+V(S{)}^{\rho }}r(S)\right]\end{array}$$
  于是$R(S+j)-R(S)$的符号就由中括号内的符号决定，因此，我们有：
  $$\begin{array}{rl}& \frac{v_j{p}_j}{V(S+j)}+\frac{V(S{)}^{\rho }}{V(S+j{)}^{\rho }}r(S)\left(\frac{V(S{)}^{1-\rho }}{V(S+j{)}^{1-\rho }}-\frac{v_0+V(S+j{)}^{\rho }}{v_0+V(S{)}^{\rho }}\right)\\ =& \frac{v_j{p}_j}{V(S+j)}+\frac{V(S{)}^{\rho }r(S)}{V(S+j)(v_0+V(S{)}^{\rho })}((V(S{)}^{1-\rho }-V(S+j{)}^{1-\rho })v_0-v_j)\\ =& \frac{v_j{p}_j}{V(S+j)}+\frac{R(S)}{V(S+j)}((V(S{)}^{1-\rho }-V(S+j{)}^{1-\rho })v_0-v_j)\end{array}$$
  则$R(S+j)>R(S)$当且仅当：
  $$p_j>R(S)\left[1+v_0\frac{V(S+j{)}^{1-\rho }-V(S{)}^{1-\rho }}{v_j}\right]=R(S)\left[1+v_0\frac{(v_j+V(S){)}^{1-\rho }-V(S{)}^{1-\rho }}{v_j}\right]=R(S)Y(v_j,S)$$
  以类似的形式，记$r(S-i)=(V(S)r(S)-p_i{v}_i)/V(S-i)$，我们有：
  $$\begin{array}{rl}R(S-i)-R(S)& =\frac{V(S-i{)}^{\rho }}{v_0+V(S-i{)}^{\rho }}\frac{V(S)r(S)-p_i{v}_i}{V(S-i)}-\frac{V(S{)}^{\rho }}{v_0+V(S{)}^{\rho }}r(S)\\ & =\frac{V(S-i{)}^{\rho }}{v_0+V(S-i{)}^{\rho }}\left[\frac{-v_i{p}_i+V(S)r(S)}{V(S-i)}-\frac{V(S{)}^{\rho }}{V(S-i{)}^{\rho }}\frac{v_0+V(S-i{)}^{\rho }}{v_0+V(S{)}^{\rho }}r(S)\right]\end{array}$$
  这样通过类似的推导有$R(S-i)>R(S)$当且仅当：
  $$p_i<R(S)\left[1+v_0\frac{V(S{)}^{1-\rho }-V(S-i{)}^{1-\rho }}{v_i}\right]=R(S)\left[1+v_0\frac{(-v_i+V(S){)}^{1-\rho }-V(S{)}^{1-\rho }}{-v_i}\right]=R(S)Y(-v_i,S)$$
  证毕。$■$

• 证明（引理4）：固定子集$S$，令$f(a)$表示$Y(a,S)$以$a$为变元的函数，为了证明$Y(a,S)\ge Y(c,S),\forall a<c$，即证明$f(\cdot )$单调减，等价于$f^{\prime }(a)\le 0$。为了简化标记，我们令$\beta =V(S)$，于是有：
  $$f(a)=1+v_0\frac{(\beta +a{)}^{1-\rho }-{\beta }^{1-\rho }}{a}$$
  假设$a$在$f$的定义域上，且$\beta +a>0$，于是可以对$f$求导：
  $$f^{\prime }(a)=...=\frac{v_0}{a^2}(\beta +a{)}^{-\rho }\left[{\left(\frac{\beta +\alpha }{\beta }\right)}^{\rho }-\frac{a\rho +\beta }{\beta }\right]$$
  因此$f^{\prime }(a)$的符号只与中括号内的符号有关，即证明：
  $${\left(\frac{\beta +\alpha }{\beta }\right)}^{\rho }\le \frac{a\rho +\beta }{\beta }$$
  这个利用$x^{\rho }\le 1+\rho (x-1)$的结论即可轻易得证引理4的前半部分。

  类似地，固定$a$，并定义：
  $$g(\beta )=1+v_0\frac{(a+\beta {)}^{1-\rho }-{\beta }^{1-\rho }}{a}$$
  于是$Y(a,S)=g(V(S))$，因此，若证得$g(\cdot )$单调减，则有引理5的后半部分成立（$Y(S,a)\ge Y(S^{\prime },a),\forall S\subset S^{\prime }$，此时有$V(S)<V(S^{\prime })$）。

  同理对$g$求导：
  $$g^{\prime }(\beta )=...=(a+\beta {)}^{-\rho }{v}_0\frac{1-(1+a/\beta {)}^{\rho }}{a}<0$$
  于是$g$是单调减函数，引理4后半部分得证。

  证毕。$■$

D 第七节对于混合逻辑模型的证明 Proofs for the mixed logit model in Section 7

• 证明（引理6）：首先推导：
  $$R(S+j)-R(S)=...=v_j\sum _{k=1}^K{\alpha }_k\frac{p_j-R_k(S)}{w_k+v_j+{\sum }_{l\in S}{v}_l}$$
  其中$R_k(S)={\sum }_{l\in S}{p}_l{v}_l/W_k(S)$，于是$R(S+j)>R(S)$当且仅当：
  $$p_j>\frac{{\sum }_{k=1}^K{\alpha }_k{R}_k(S)/W_k(S+j)}{{\sum }_{k=1}^K{\alpha }_k/W_k(S+j)}$$
  其中$W_k(S)=w_k+{\sum }_{j\in S}{v}_j$，于是利用这些记号就可以推导：
  $$\begin{array}{rl}R(S+j)>R(S)& ⟺p_j>\frac{{\sum }_{k=1}^K{\alpha }_k{R}_k(S)/W_k(S+j)}{{\sum }_{k=1}^K{\alpha }_k/W_k(S+j)}\\ & ⟺p_j>\left(\sum _{l\in S}{p}_l{v}_l\right)\frac{{\sum }_{k=1}^K{\alpha }_k/(W_k(S)W_k(S+j))}{{\sum }_{k=1}^K{\alpha }_k/W_k(S+j)}\\ & ⟺p_j>\left(\sum _{l\in S}{p}_l{v}_l\right)\left(\sum _{k=1}^K\frac{{\alpha }_k}{W_k(S)}\right)\frac{{\sum }_{k=1}^K{\alpha }_k/(W_k(S)(W_k(S)+v_j))}{\left({\sum }_{k=1}^K{\alpha }_k)/W_k(S\right)\left({\sum }_{k=1}^K{\alpha }_k/(W_k(S)+v_j)\right)}\\ & ⟺p_j>\left(\sum _{k=1}^K{\alpha }_K\frac{{\sum }_{l\in S}{p}_l{v}_l}{W_k(S)}\right)\frac{{\sum }_{k=1}^K{\alpha }_k/(W_k(S)(W_k(S)+v_j))}{\left({\sum }_{k=1}^K{\alpha }_k)/W_k(S\right)\left({\sum }_{k=1}^K{\alpha }_k/(W_k(S)+v_j)\right)}\\ & ⟺p_j>R(S)\frac{{\sum }_{k=1}^K{\alpha }_k/(W_k(S)(W_k(S)+v_j))}{\left({\sum }_{k=1}^K{\alpha }_k)/W_k(S\right)\left({\sum }_{k=1}^K{\alpha }_k/(W_k(S)+v_j)\right)}\\ & ⟺p_j>R(S)X(v_j,S)\end{array}$$
  类似地：
  $$R(S-i)-R(S)=...=v_i\sum _{k=1}^K{\alpha }_k\frac{-p_i+R_k(S)}{w_k-v_i+{\sum }_{l\in S}{v}_l}$$
  于是$R(S-i)>R(S)$当且仅当：
  $$p_i<\frac{{\sum }_{k=1}^K{\alpha }_k{R}_k(S)/W_k(S-i)}{{\sum }_{k=1}^K{\alpha }_k/W_k(S-i)}$$
  类似地流程可得：
  $$R(S-i)>R(S)⟺p_i<R(S)X(-v_i,S)$$
  证毕。$■$

• 证明（引理7）：这个证明与引理4基本一致，还是用求导的思路证明函数单调减，前半部分完全相同，后半部分构造的$g(x)$如下所示：
  $$g(x)=\frac{{\sum }_k{\alpha }_k/((w_k+x)(w_k+x+a))}{({\sum }_k{\alpha }_k/(x+w_k))({\sum }_k{\alpha }_k/(x+w_k+a))}$$
  则有$X(S,a)=g({\sum }_{j\in S}{v}_j)$，之后的求导过程极为冗长，不作笔注。