《Pricing a Finite Inventory of Substitutable Products with Show-All Constraint》
全文深度总结、模型函数解析、命题算例阐释与管理启示
| 文献属性维度 | 详细内容 |
|---|---|
| 论文原标题 | Pricing a Finite Inventory of Substitutable Products with Show-All Constraint(具有“全部展示”约束的可替代产品有限库存定价问题) |
| 作者 (Authors) | Vineet Goyal (Columbia University), Garud Iyengar (Columbia University), Rajan Udwani (University of California, Berkeley) |
| 发表期刊 (Journal) | Operations Research(运筹学顶刊,INFORMS 旗舰期刊),2026年第74卷第5期(Vol. 74, No. 5, September–October 2026, pp. 2536–2555) |
| DOI 与检索信息 | https://doi.org/10.1287/opre.2022.0479 (收稿:2022年9月16日;录用:2026年4月9日;在线发表:2026年6月3日) |
| 核心关键词 | Pricing(定价)、Choice Models(选择模型)、Substitution(需求替代)、Inventory Constraint(库存约束)、Show-All Constraint(全部展示约束)、Approximation Ratio(近似比) |
一、 全文核心脉络总结
1. 研究背景与商业痛点:在现代零售与电子商务平台(如 Amazon 等)的日常运营中,卖方需要在有限的规划期 内,对一组具有固定初始库存 的差异化但可相互替代的商品集合 进行动态定价。例如,Amazon 上销售的同款三本装笔记本(Pukka Pad 3-Pack),其纸张质量与页数完全相同,仅封面设计不同,但折后售价分别为 $29.99 与 $26.70。随着时间推移,部分商品可能因热销而售罄断货(Stock-out),原本倾向于购买断货商品的顾客会将需求转移至仍在库的替代商品上(即断货替代效应,Stock-out Substitution)。卖方的核心目标是制定一套能够响应库存消耗与需求替代的定价策略,以最大化整个规划期内的总期望收益。
2. “子集定价(SP)”与“全部展示定价(SAP)”的根本分歧:既有运筹学与收益管理文献在研究多商品有限库存定价时,绝大多数允许卖方通过隐藏部分在库商品(或赋予其无穷大价格)来仅向顾客展示在库商品的一个严格子集,这一松弛问题被称为子集定价问题(Subset Pricing, SP)。在大库存渐近条件下,SP 问题存在随机静态最优策略(即以固定概率分布独立抽样商品组合与价格),并可通过基于选择的确定性线性规划(CDLP)高效求解。然而,实证营销研究(如 Borle et al. 2005, Sethuraman et al. 2022)表明,人为隐藏在库商品会严重损害顾客信任与长期品牌忠诚度。因此,真实零售场景普遍遵循一项关键的运营准则——全部展示约束(Show-All Constraint):只要某件商品仍有库存,卖方就必须为其设定一个有限的、可行的价格并向顾客展示。作者将这一更符合商业现实的问题定义为全部展示定价问题(Show-All Pricing, SAP)。
3. 为什么自然启发式与静态策略会失效:面对 SAP 问题,一种最直观的启发式思路是:先求解无展示约束的 SP 问题(即 CDLP),然后对每个被抽中展示的商品组合进行“简单增广(Simple Augmentation)”——把所有未包含在该组合中但仍有库存的商品,以最高可行价格 强行加入展示列表。然而,作者通过反例证明,这种随机静态增广策略会导致原本应在低价售罄的商品因被高价替代品分流或因展示顺序不当而出现库存积压,从而显著偏离最优收益。事实上,SAP 的最优策略本质上是动态的(Inherently Dynamic):随着部分商品售罄下架,在库商品因承接替代需求而面临更高的购买率,最优价格必须随时间动态调整(在 MNL 模型下表现为分段常数且单调递增)。
4. 全文研究路线与三步转化框架:为了在大库存体制(Large Inventory Regime,即 )下高效求解 SAP,作者构建了一套严谨的“三步转化框架”:(1)首先利用单顾客定价算子或紧凑重构求解忽略全部展示约束的线性规划松弛 CDLP(或在异质最高价下求解混合整数规划 CDMIP);(2)设计Sequence(序列算法,Algorithm 1 & 2)与Greedy Unrolling(贪心展开算法,Algorithm 3),将 CDLP 解转化为连续时间确定性流体松弛问题(DR)的可行动态定价策略,并严格界定收益损失;(3)通过预设安全库存缓冲区的独立采样算法(Independent Sampling, Algorithm 4),将 DR 策略无损转化为离散时间随机顾客到达下的 SAP 策略。此外,文章深入探索了选择多胞形(Choice Polytope)的链凸分解(Chain Convex Decomposition, CCD)性质,从几何与对偶角度完美解释了何时“全部展示约束”不会带来任何收益损失,并将结论拓展至非平稳时变需求与异质最高价格上限场景。
二、 文章的核心贡献 (Core Contributions)
本文在动态定价、离散选择建模与在线资源分配交叉领域取得了突破性进展。在本文之前,即便对于最基础的多项式 Logit(MNL)选择模型,SAP 问题的计算复杂性以及“全部展示约束”对最优收益的定量影响仍是未解之谜。全文的核心贡献可系统归纳为以下五个方面:
贡献一:证明 MNL 模型下“全部展示约束”零收益损失,并给出多项式时间精确求解算法。在离散可行价格集且所有商品共享同一最高可行价格(,即 Assumption 1)的条件下,作者针对 MNL 选择模型提出了多项式时间的 Sequence 算法(Algorithm 1 & 2),能够将任意 CDLP 可行解完全无损(Without Any Loss in Revenue)地转化为满足全部展示约束的 DR 可行解。同时,作者证明了可变价格下的 MNL-CDLP 具备多项式规模(关于 )的紧凑线性规划重构(Lemma 3)。这意味着在 MNL 模型下,施加全部展示约束完全不会降低卖方的渐近最优期望收益,且最优策略具有极其优美的结构特征:每件商品的最优展示价格随时间推移呈分段常数且单调不减(Piecewise Constant and Monotonically Nondecreasing)。
贡献二:针对一般弱理性与单调选择模型(涵盖 RUM),确立“全部展示约束”收益损失的紧界与通用近似框架。当消费者行为遵循一般的随机效用最大化(RUM)或满足弱理性与单调性(Assumption 2)的选择模型时,作者证明了全部展示约束在最坏情况下至少会造成 14.8% 的收益损失(即 DR 最优值与 SP/CDLP 最优值之比至多为 )。为应对这一挑战,作者提出了基于在线次模福利最大化(OSW)分析技术的 Greedy Unrolling(贪心展开算法,Algorithm 3):只要给定单期定价问题的 -近似算子,即可在多项式时间内生成具有 近似保证(其中 )的动态定价策略。这一结果将一般选择模型下全部展示约束对最优收益的影响严格锁定在 之间。
贡献三:创立选择多胞形(Choice Polytope)的链凸分解(CCD)对偶理论,解决可变价格下的可分解性判定难题。为了从根本上回答“究竟什么样的选择模型在全部展示约束下没有收益损失”,作者定义了选择多胞形 并提出了链凸分解(Chain Convex Decomposition, CCD)性质——即多胞形中的每个点都能表示为一组嵌套商品集合()对应顶点的凸组合。在固定价格文献中,人们通常依赖构造基于销量的线性规划(SBLP)来证明该性质,但当价格可变时,即便底层 是 MNL 模型,修正后的选择模型 也已不再是 MNL 或马尔可夫链模型,且无法通过既有 SBLP 直接推广;更重要的是,重构法无法证伪一个模型不满足 CCD。作者另辟蹊径,利用线性规划强对偶性证明了:模型满足 CCD 当且仅当对元素全排列构成的每一组递归特征价格向量,其最优商品组合期望收益恒等于 1(Lemma 6)。借助这一充要条件,作者成功证明了可变价格下的 MNL 模型满足 CCD(Theorem 2),而可变价格下的马尔可夫链(Markov Chain)选择模型不满足 CCD(Lemma 7)——打破了固定价格下两者均满足 CCD 的传统认知。
贡献四:攻克非平稳时变偏好与异质最高价格上限两大现实扩展难题。(1)在顾客偏好随时间演化的非平稳环境(Nonstationary Customer Preferences)中,作者将贪心展开算法推广至时变选择模型 ,证明了算法可达到 的近似比,并证明没有任何算法能在最坏情况下取得严格优于 的常数近似比(Theorem 5),实现了理论上的紧界(Tight Bound)。(2)在各商品最高可行价格不同的异质价格上限环境(Heterogeneity in Highest Prices)中,作者指出 CDLP 与 DR 的最优值差距可以任意大(趋近于无穷倍)。为此,作者针对 MNL 模型引入二元决策变量 (刻画商品 要么在期末完全售罄,要么在所有正权重组合中全程展示),构建了紧凑的混合整数线性规划 CDMIP,并证明 CDMIP 与 DR 之间零间隙(Theorem 6 & Lemma 8),彻底解决了异质价格上限下的求解失真问题。
贡献五:通过库存缓冲与独立采样机制完成从确定性流体松弛(DR)到离散随机问题(SAP)的渐近无损转化。在传统无展示约束的 SP 问题中,算法可以通过以小概率 向顾客展示空集(不展示任何商品)来抑制需求,防止库存过早耗尽。然而在全部展示约束下,只要有库存就绝不允许展示空集。作者巧妙地设计了预扣安全库存缓冲(Inventory Buffer)机制(Algorithm 4),通过将初始库存缩减为 后求解 DR 并进行独立随机采样(还可利用条件期望法去随机化),证明了当 时,随机 SAP 策略的期望收益以 的收敛速率逼近 DR 基准(Theorem 4)。
| 场景与模型设定 | 最高价假设与需求特征 | 核心求解算法 | 理论性能保证 (相对 SP/CDLP) |
|---|---|---|---|
| MNL 选择模型 | 同质最高价 ,平稳需求 | 紧凑 LP + Sequence (Alg. 1 & 2) | 1 (即 100% 最优),无收益损失,价格单调不减 |
| 一般弱理性单调模型 (含 RUM) | 同质最高价 ,平稳需求 | 椭球法 CDLP + Greedy (Alg. 3) | 下界 (约 );上界 |
| Nested Logit (NL) / Markov 模型 | 同质最高价 ,平稳需求 | 单期算子 + Greedy (Alg. 3) | NL 特定子类:;Markov: |
| 非平稳一般选择模型 | 同质最高价 ,时变需求 | N-CDLP + 时变 Greedy (Alg. 5) | 紧近似比 (最坏情况上界亦为 ) |
| MNL 选择模型(异质最高价) | 异质最高价 ,平稳需求 | 紧凑 MILP (CDMIP) + Alg. 2 | 相对 CDMIP 为 (MILP 精确求解时 100% 最优) |
三、 模型中的函数与数学结构详尽解释
为了严谨刻画有限库存、离散价格集、单品单一定价限制以及“全部展示约束”,作者在传统离散选择模型的基础上引入了“产品-价格对(Product-Price Pairs)”扩展地面集与修正选择函数。以下对全文模型中出现的每一个核心函数、变量与目标泛函进行逐一拆解与物理意义阐释。
3.1 基础集合、扩展地面集与最低价格提取函数 及筛选算子
(1)产品集与可行价格集:设卖方共有 种可相互替代的产品,构成产品地面集 。每种产品 拥有初始库存 ,以及有限的离散可行价格集合 。定义所有产品可行价格的并集为 。产品 的最高可行价格记为 ,最低可行价格记为 。在核心模型(Assumption 1)中,所有产品共享统一的最高可行价格(如统一标准吊牌价),即 。
(2)扩展地面集 (产品 vs. 商品条目):为了将“定价决策”转化为“商品组合选择(Assortment Optimization)决策”,作者定义了笛卡尔积扩展地面集 。在术语上,作者严格区分了“产品(Product)” 与“商品条目(Item)” :一个商品条目 代表“以价格 售卖产品 ”。当展示组合 中存在某个价格 使得 时,称产品 在组合 中得到展示(简记为 )。
(3)最低价格提取函数 与有效最低价子集函数 :在商业现实中,同一时期一件产品只能标一个价格。但数学上任意子集 可能同时包含同一产品 的多个不同价格条目(如同时包含 和 )。为了在全集 上无约束地定义模型并自动满足“单品单一价格”性质,作者定义了组合 中产品 的最低展示价格函数 以及只保留各产品最低价格条目的筛选算子 :
函数直观解释:若组合 中同时放入了同一款产品的多档价格,理性的顾客只会关注并购买该产品最便宜的那一档价格 ,高价档位相当于自动隐身。因此,算子 的作用就是将任意原始集合 “净化”为每个在展产品仅保留最低标价的有效展示集合。若 ,则约定 。
3.2 原始选择概率函数 与修正选择概率函数
(1)原始选择模型 :表示当卖方提供商品条目子集 时,到达的顾客从中选择商品条目 的原始概率 ;顾客不购买任何商品(选择外部选项 / 离开)的概率记为 。
(2)修正选择模型 (全文核心典范模型):为了隐式强制执行“每件产品在同一时刻仅以单一(最低)价格生效”,作者基于 定义了修正选择函数 :
其中规定:若 (即价格 不是产品 在 中的最低展示价)或 ,则 。同时定义外部不购买概率为 ,从而保证概率归一性 。在此基础上,作者进一步定义了两个简写聚合概率函数——产品级选择概率函数 与组合总购买率函数 :
(3)MNL 模型下的修正选择函数实例:若底层模型 是定义在 上的多项式 Logit(MNL)模型,每个商品条目 具有吸引力权重(Attraction Weight)(外部选项权重标准化为 ),则修正选择模型 的具体函数形式为:
关键结构警示:作者特别指出,即使底层 是标准的 MNL 模型,经过最低价筛选后的修正模型 在整个 上不再是一个标准 MNL 模型(因为向组合 中加入同一个产品的更低价格条目 时,原本较高价格条目 的选择概率会直接突变为 ,违反了标准 MNL 的无关备选方案独立性 IIA 性质)。这也是为什么传统固定价格下的 MNL 性质不能直接照搬到可变价格问题中的核心原因。
(4)选择函数的基本理性假设(Assumption 2):全文假设卖方已知选择函数 ,且 满足以下两条经济学基本公理(所有基于随机效用最大化 RUM 的模型,在任意商品价格下降不会降低该商品效用的前提下,其导出的 均自动满足这两条性质):
其中,弱理性表明扩大展示集合(引入新产品或某产品的更低价格)绝不会增加原有具体条目的被选中概率(即商品之间只存在替代关系而不存在互补关系);单调性表明向展示集合中添加任何新条目(或降低某产品的价格)只会提高或保持顾客的整体购买总概率 ,绝不会把顾客“吓跑”去选择外部不购买选项。
3.3 期望收益函数 与四大核心优化模型
(1)单期商品组合期望收益函数 :当卖方向单个到达的顾客展示商品组合 时,每件在展产品 的实际成交价格为其最低展示价 ,成交概率为 。因此单期期望收益函数定义为:
(2)原问题:全部展示定价问题(SAP)的随机动态规划泛函:设顾客 到达时,当前剩余库存大于零的在库产品集合为 。历史依赖定价策略 为顾客 提供展示集合 。SAP 的优化目标与“全部展示约束”数学表述为:
(3)单顾客(单期)定价问题与 -近似算子(Single-Period Pricing Oracle):若同时去掉库存约束与全部展示约束,问题简化为单顾客静态定价问题:。在通用算法框架中,作者假设可以调用一个单期 -近似算子:对于任意给定的候选条目子集 ,该算子返回一个子集 ,满足:
(4)确定性流体松弛模型(Deterministic Relaxation, DR):将离散时间点与随机顾客选择替换为连续时间区间 上的确定性流体需求。在任意时刻 ,卖方展示集合 ,产品 以瞬时速率 被消耗。时刻 的在库产品集定义为 。DR 的优化模型为:
(5)基于选择的确定性线性规划(Choice-Based Deterministic Linear Program, CDLP):若从 DR 模型中移除“全部展示约束”,则连续时间展示轨迹可以等价地汇总为每个子集 在整个规划期内的展示时间占比(或向每位顾客展示组合 的静态概率)。这就得到了经典的 CDLP 模型:
3.4 核心转化算法与选择多胞形分析中的关键函数
(1)Sequence 算法(Algorithm 1 & 2)中的目标销量函数 与步长权重函数 :给定 CDLP 的一个有限支撑可行解 ,每个商品条目 在单位时间内的平均目标销售率函数 、第 阶段嵌套集合 的维持时间权重 以及总权重 分别为:
其中 的含义是:当展示当前所有未完成销量目标的商品条目集合 时,计算集合中每个条目按当前消耗速率 恰好耗尽其剩余目标销量 所需的时间,并取最早达到目标的那个时间点作为切换点。一旦某个低价条目达到目标销量并从 中移除,同一产品的次低价条目(或最高兜底价 )便自动接管,从而使展示价格随时间单调递增。
(2)Greedy Unrolling(贪心展开算法,Algorithm 3)中的双时间步长控制函数 :在任意时刻 ,设剩余总库存大于零的产品集为 ,剩余单品目标销量预算大于零的条目集为 。算法贪心地从 CDLP 支撑集中挑选当前期望收益最高的截断组合 ,并用最高价 补齐所有在库产品得到展示集 。该组合可持续展示的时长 由两个瓶颈时间函数决定:
其中 限制了展示时长不能超过任何在展产品的剩余物理库存 耗尽的时间(因为以最高价 增广展示的产品即便其 档位的 CDLP 预算已经用完,只要物理库存还在就会继续以 展示并被消耗);而 限制了展示时长不能超过当前选中组合 中任何条目的 CDLP 单品价格预算 耗尽的时间。
(3)选择多胞形对偶特征价格函数 :在第 4 节研究选择多胞形 的链凸分解(CCD)性质时,作者固定地面集 的任意排列 ,定义前缀嵌套子集 以及下三角选择概率矩阵 (其元素为 )。通过求解线性方程组 ,定义了递归特征价格函数 :
该特征价格向量的构造精妙之处在于:它使得嵌套链上的每一个前缀子集 的期望收益都恰好标准化为 。于是,检验模型 是否满足 CCD,就等价于检验在虚拟价格 下,是否存在某个偏离该嵌套链的子集 能够取得严格大于 的超额期望收益。
| 函数/符号名称 | 数学表达式 (Word 原生公式) | 在模型中的作用与经济含义 |
|---|---|---|
| 最低展示价格函数 | 提取组合 中产品 的最低标价,确保单品单一有效价格。 | |
| 最低价筛选子集算子 | 剔除同一产品的高价冗余条目,仅保留各在展产品的最低价格条目。 | |
| 修正选择概率函数 | 顾客在组合 下购买条目 的真实概率(非最低价时为 0)。 | |
| 组合总购买率函数 | 顾客在组合 下产生实际购买的总概率(等于 )。 | |
| 单期期望收益函数 | 向单个顾客展示组合 获得的期望销售收入。 | |
| CDLP 单位时间目标销量 | 在 CDLP 解中,条目 的单位时间期望销量目标。 | |
| Sequence 消减步长权重 | 第 个嵌套集合维持展示直至首个条目达标退出的时间比例权重。 | |
| 安全缓冲折减库存函数 | Algorithm 4 中为吸收随机需求波动、防止提前断货而预留缓冲后的库存。 | |
| 多胞形广义收益泛函 | 用于刻画选择多胞形 强对偶条件与判定 CCD 性质的线性泛函。 |
四、 全文命题、引理、定理与推论的通俗解释及算例阐释
本部分对论文中出现的全部 8 个引理(Lemma 1–8)、6 个定理(Theorem 1–6)以及 1 个推论(Corollary 1) 逐一进行解析。根据要求,我们省略繁琐的数学证明过程,聚焦于每个命题背后的直观机理,并结合论文内置算例(Example 1 & 2)及贴近商业直觉的数值算例来具象化阐释其含义。
4.0 前置基础:核心假设 (Assumption 1–2)、核心定义 (Definition 1–2) 与重要注记 (Remark 1–3) 的举例解释
【Assumption 1–2 & Definition 1–2 核心陈述】(原文第 2 节与第 4 节) Assumption 1(统一最高可行价假设):所有商品的最高可行价格相同,即存在 使得 。 Assumption 2(弱理性与单调性假设):修正选择模型 满足弱理性 与单调性 。 Definition 1(选择多胞形 Choice Polytope):选择多胞形 是所有商品组合选择概率向量 的凸包,即 当且仅当存在非负权重 (满足 )使得 。 Definition 2(链凸分解 Chain Convex Decomposition, CCD):若点 可表示为一条嵌套集合链 对应顶点的凸组合,则称 满足 CCD;若 中每个点均满足 CCD,则称选择模型 为 CCD 模型。 |
|---|
【通俗含义与举例说明】:(1)Assumption 1–2 举例:正如论文 Figure 1 展示的 Amazon 上的 Pukka Pad 三本装笔记本,不同封面花色的款式共享同一个官方标准定价上限 ,平时以不同折扣价($29.99 或 $26.70)销售,这便是 Assumption 1;而当平台多上架一款新花色或把某款花色降价时,原有花色的单品购买率可能会被分流下降(弱理性),但所有花色合在一起的总购买转化率只会提高不会降低(单调性),这便是 Assumption 2。(2)Definition 1–2 举例:假设店内有两款商品 A 和 B,单独展示 A 时销量率为 ,单独展示 B 时为 ,同时展示 时为 。那么“一半时间展示 A、一半时间展示 B”所形成的平均销量率 就是选择多胞形 中的一个点(Definition 1)。虽然 最初是由两个互不包含的单品集合 和 混合而成的,但它可以改写为嵌套集合链 的凸组合:(权重 ),因此该点满足链凸分解(Definition 2)。(3)Remark 1–3 核心要点与举例:Remark 1 指出直接对 CDLP 组合补齐最高价 并按随机静态概率或固定顺序展示会因部分商品提前断货或滞销而次优(例如在 Example 1 的 MNL 场景中,先展示 再展示 会导致产品 1 卖不完,而反过来先展示 却能达到最优,说明遍历 种排列不可行);Remark 2 强调 Sequence 算法不仅能解决本文的展示定价问题,还能广泛用于在线个性化推荐、动态随机匹配、产品退市(Product Retirement)等众多领域的分数解取整;Remark 3 说明在实际系统中,可通过蒙特卡洛模拟器估算每个候选价格组合的“未来期望收益(Revenue-to-go)”,利用条件期望法(Method of Conditional Expectations)将 Algorithm 4 的随机抽样策略转化为 100% 确定性的实时动态定价策略。
4.1 引理 1 (Lemma 1):单期定价下以最高可行价 增广展示的无损性
【Lemma 1 命题陈述】(原文第 2.1 节,第 2541 页) 给定满足 Assumption 2 的单调选择模型 ,且所有商品共享同一最高可行价格 (Assumption 1),则对于任意产品 和任意展示组合 ,均有:。 |
|---|
【核心含义解释】:在没有库存约束的单顾客(单期)定价问题中,如果某个商品组合 没有包含产品 ,卖方只需将产品 按全场最高封顶价 加入展示组合,单期期望收益只增不减(如果产品 原本已在 中以更低或相等的价格展示,根据最低价筛选规则 ,再加入 不会改变任何概率,收益保持不变)。这是因为:第一,单调性保证了加入新商品 后,顾客购买商品的总概率 只会上升而不会下降;第二,即使新加入的 分流了原本组合 中其他商品的销量(弱理性),由于 是全场最高价格,被分流出去的每一单位需求都以全场最高单价 成交,因此总期望收入必然只增不减。
【具体算例说明】:假设一家数码店销售两款无线鼠标(产品 1 为黑色款,产品 2 为白色款),可行价格集均为 ,最高可行价格统一为 。假设当只展示黑色款促销价 时,顾客有 的概率购买黑色款, 概率空手离开,此时单期期望收益为 。现在为了满足“全部展示约束”,店长把白色款以最高价 元摆上货架,形成新组合 。加入白色款后,原本买黑色款的人中有 改买白色款(黑色款购买率从 降至 ,体现弱理性),同时原本空手离开的人中也有 决定购买白色款(白色款总购买率为 ,总购买率从 升至 ,体现单调性)。此时新组合的期望收益为 。这清楚地说明:在没有库存限制的单期问题中,用最高价 补齐未展示商品不仅满足了全部展示约束,还能提升或保持当期期望收益。
4.2 引理 2 (Lemma 2):基于椭球法与单期算子的 CDLP 多项式近似求解与稀疏支撑性
【Lemma 2 命题陈述】(原文第 2.3 节,第 2542 页) 给定单期定价问题的一个 -近似算子以及精度参数 ,利用椭球法(Ellipsoid Method)仅需向单期算子进行关于 多项式次数的查询,即可求得 CDLP 的一个 -近似可行解,且所得解的支撑集大小(即正权重组合个数)至多为 。 |
|---|
【核心含义解释】:CDLP 包含指数级数量( 个)的决策变量 ,直接列出所有变量求解是不可能的。但是,CDLP 的主问题只有 个约束( 个产品的库存上限约束 + 1 个总概率不超 1 的约束)。根据线性规划对偶理论,其对偶问题只有 个变量,而对偶问题的“分离算子(Separation Oracle)”恰好等价于将每个产品的库存影子价格(Dual Variable)从实际售价中扣除后的单期定价问题。因此,只要能近似求解单期定价问题,就能在多项式时间内近似求解 CDLP;同时,因为主问题仅有 个线性约束,其基本可行解(顶点解)中非零变量 的个数最多只有 个。
【具体算例说明】:假设某服装品牌有 款夹克,每款夹克有 个可选折扣价,扩展地面集共有 个条目,理论上共有 种可能的展示子集 。Lemma 2 告诉我们:不需要遍历这三万多种组合,只要我们有一个单期定价算法(例如嵌套 Logit 模型的单期近似算法,),通过椭球法迭代调整 3 款夹克的库存影子价格,最终求出的最优(或近似最优)混合定价方案最多只需要用到 个商品组合(比如组合 的展示时间占比分别为 ),其余 个组合的权重全部为 。这一“支撑集至多为 ”的稀疏性质为后续算法在多项式时间内展开 CDLP 解奠定了基础。
4.3 引理 3 (Lemma 3):MNL 模型下可变价格 CDLP 的多项式规模紧凑线性规划重构
【Lemma 3 命题陈述】(原文第 2.3 节,第 2542 页) 如果底层选择模型 是 MNL 模型,且可行价格集合 是离散有限集,则 CDLP 存在一个规模(变量数与约束数)关于 为多项式级别的等价线性规划重构(Sales-Based LP Reformulation)。 |
|---|
【核心含义解释】:虽然椭球法(Lemma 2)在理论上具有多项式复杂度,但在实际计算中速度较慢。在固定价格(每个商品只有一个价格)的经典文献中,MNL 模型的 CDLP 可以直接改写为以“各商品期望销量 ”为决策变量的紧凑线性规划(SBLP)。然而当价格可变时,作者在附录中证明,直接照搬固定价格的 SBLP 会导致同一个产品在不同价格档位上被同时赋予正销量,不等价于 CDLP。得益于本文第 4 节证明的 MNL 可变价格模型的 CCD 性质,作者首次成功构造了可变价格下与 CDLP 完全等价的多项式规模紧凑 LP,从而可以使用标准商用求解器(如 Gurobi、CPLEX)极速精确求解 CDLP。
【具体算例说明】:假设卖方销售 种商品,每种商品有 个可选价格档位(如论文第 6 节数值实验设定)。原始 CDLP 的组合变量个数高达 个,根本无法直接建模。而利用 Lemma 3 的紧凑销量重构,决策变量直接转化为每个“商品-价格对” 的平均销售率 ,核心变量数量骤降至 个级别,普通计算机在几毫秒内即可求出全局最优解。
4.4 定理 1 (Theorem 1):Sequence 展开算法的时间复杂度与 -收益下界保证
【Theorem 1 命题陈述】(原文第 3.2 节,第 2544 页) 给定满足 Assumption 2 的选择模型 ,以及支撑集大小为 、总期望收益为 的一个 CDLP 可行解,Algorithm 2(Unrolling Sequence)的运行时间为 ,并输出一个 DR 可行解,其总收益至少为 (其中 )。 |
|---|
【核心含义解释】:Sequence 算法(Algorithm 1)的核心思想是:将 CDLP 解中所有出现过的商品条目全部汇集在一起,形成初始大集合 (由于只取最低价生效,每个产品最初都以其在 CDLP 中出现过的最低价格展示)。随着时间推移,一旦某个低价条目 的累计销量达到了它在 CDLP 中的目标销量 ,算法就将该低价条目移除,从而使该产品的展示价格跳升至下一个更高的价格档位(直至最高价 ),由此生成一串严格嵌套递减的集合链 及其对应持续时间权重 。如果总时间权重 (即 ),说明在规划期 结束前,所有条目的目标销量都能 100% 完成,收益至少为 ;如果 ,说明要在 的时间内才能卖完所有目标销量,此时 Algorithm 2 将每段展示时间按比例缩小为 并用最高价 补齐未展示产品,每个条目的销量至少完成目标的 ,从而严格保证总收益不低于 。
【具体算例说明(对应原文 Example 1 的 Scenario 1)】:考虑 3 种产品 ,初始库存分别为 ,可行价格集均为 (最高价 )。设消费者的选择遵循排名偏好模型(Scenario 1): 的顾客偏好顺序为 ;另外 的顾客偏好顺序为 ;剩余 的顾客不买任何产品。在无展示约束的 CDLP 中,最优解为:在 的时间展示 (故意隐藏产品 3,迫使第二类顾客购买 ),在 的时间展示 。此时三件产品的目标销量分别为 ,CDLP 最优总收益为 。现在运行 Sequence 算法:第 1 步展示并集 ,由于 在场,第二类顾客全部跑去买 而不买 ,导致 下只有 和 各以 的速率成交。经过 后, 达到目标销量 退出;第 2 步展示 ,此时第一、二类顾客都买 (速率为 ),需耗时 才能卖完 剩余的 销量;第 3 步展示 ,需耗时 才能卖完 的 销量。三段权重之和为 。Algorithm 2 将时间按 缩放并在缺省时补齐最高价,最终得到的 DR 可行策略保证总收益至少为 。
4.5 定理 2 (Theorem 2) 与 推论 1 (Corollary 1):MNL 模型下 及 DR 与 CDLP 的零间隙等价性
【Theorem 2 & Corollary 1 命题陈述】(原文第 3.2 节,第 2544 页;第 4.2 节,第 2549 页) Theorem 2:如果底层选择模型 是 MNL 模型,则对于 CDLP 的任意有限支撑可行解,Sequence 算法输出的权重总和恒满足 。 Corollary 1:当底层选择模型 是 MNL 模型时,确定性松弛问题(DR)可以在多项式时间内精确求解,并且 DR 的最优目标函数值与 CDLP 的最优目标函数值完全相等。 |
|---|
【核心含义解释】:Theorem 2 和 Corollary 1 是全文最核心的理论突破之一。它指出:只要消费者遵循 MNL 选择模型且各产品最高可行价一致(Assumption 1),把 CDLP 解中的全部商品放在一起从低价往高价逐步提价(Sequence 算法),永远不会出现时间不够用(即 )的情况!换句话说,在规划期 内,Sequence 算法总能把 CDLP 规划的所有商品销量一分不少地按原定价格(甚至因后期补入最高价 而以更高价格)全部卖完。由于 CDLP 是 DR 的松弛上界,而 Algorithm 2 构造的 DR 可行解又达到了至少 的收益,这就直接推导出 Corollary 1:在 MNL 模型下,“全部展示约束”不会造成任何收益损失(最优 DR 收益 = 最优 CDLP 收益),且最优动态定价策略总是将每种产品的价格随时间单调递增(从促销低价逐步上调至封顶价)。
【具体算例说明(对应原文 Example 1 的 Scenario 2)】:仍考虑上述 3 种产品 ,库存为 ,但底层模型 改为 MNL 模型,吸引力参数为 。很容易验证,这组 MNL 参数在 和 下给出的选择概率与 Scenario 1 完全一致,因此 CDLP 最优解依然是 ,目标销量依然是 ,CDLP 最优收益为 。但在 MNL 模型下运行 Sequence 算法时:第 1 阶段同时展示 ,分母总权重为 ,因此三个条目的销售速率分别为 (注意在 MNL 下 的销售速率是 ,不会被 完全吸干!)。于是只需展示时长 ,产品 1 和产品 2 就同时售罄下架!同时产品 3 在这一阶段已经卖出了 ;第 2 阶段只剩下 ,产品 3 的销售速率由于替代效应上升为 ,卖完剩余 仅需时长 。总权重 !不仅在 时就提前完成了全部库存销售,而且实现了与 CDLP 完全相同的最优收益 。
4.6 定理 3 (Theorem 3):一般选择模型下 Greedy 算法的 近似保证与 最坏情况上界
【Theorem 3 命题陈述】(原文第 3.3 节,第 2545 页) 给定满足 Assumption 2 的选择模型 以及目标函数值为 的 CDLP 可行解: (i)Algorithm 3(Greedy Unrolling)输出一个 DR 可行解,其总收益至少为 ; (ii)存在一个问题实例,使得 DR 的最优目标函数值至多为 (即全部展示约束在最坏情况下至少造成 的不可避免收益损失)。 |
|---|
【核心含义解释】:对于非 MNL 的一般选择模型(例如排名偏好模型、马尔可夫模型或混合 Logit 模型),Sequence 算法的权重和 在最坏情况下可能高达 ,导致 趋近于 0。为此,作者设计了 Greedy Unrolling(Algorithm 3):在每个时刻 ,不再把所有商品低价混在一起,而是直接从 CDLP 的支撑集组合 中(剔除已达销量预算上限的条目后)贪心地挑选当前瞬时期望收益最高的那一个组合 ,并把其余未包含的在库商品一律按最高封顶价 增广进去。Theorem 3(i) 表明,无论选择模型 内部替代关系多么复杂,这种贪心策略都能稳健地保住至少 的 CDLP 收益;而 Theorem 3(ii) 则从反面证明,当消费者偏好异质性很强时,任何满足全部展示约束的算法都不可能拿到 100% 的 CDLP 收益,最坏情况下连理论最优 DR 策略也最多只能拿到 的收益。
【具体算例说明】:为什么在一般模型下全部展示必然损失收益,且 Greedy 如何运作?我们以 Theorem 3 在 Example 1(Scenario 1 排名模型)上的运行轨迹为例:CDLP 有两个组合 (单期收益为 )和 (单期收益为 )。在 时,Greedy 比较 和 ,贪心地优先选择收益更高的 ,并用最高价 补齐产品 1 和 2,实际展示 。在 下,第一类顾客买 ,第二类顾客买 。展示到 时,产品 2 的物理库存 率先耗尽(触发 );随后在 期间继续展示 直至产品 3 的库存 耗尽;最后在剩余的 时间内展示 ,卖出 单位的产品 1。最终 Greedy 获得总收益 (远高于 的理论保底线,且在该例中恰好达到了 DR 的理论最优值)。当把这种分流效应扩展到 种级联替代产品时(原文 Online Appendix D.2 构造的实例),全部展示约束迫使高价展示的商品不断截留其他组合的计划客流,使 DR 与 CDLP 的最优值之比收敛到 。
4.7 定理 4 (Theorem 4):从确定性流体松弛 (DR) 到离散随机问题 (SAP) 的渐近无损转化
【Theorem 4 命题陈述】(原文第 3.4 节,第 2546 页) 给定满足 Assumption 2 的选择模型 ,以及针对 DR 问题的任一高效定价算法 (设 相对于 SP 具有 -近似比),则 Algorithm 4 是一个针对原随机问题 SAP 的高效定价策略,其近似比保证为:,其中 。 |
|---|
【核心含义解释】:DR 模型假设需求是像水流一样连续确定的,而在真实的 SAP 问题中,顾客一个接一个离散到达,每次购买都是一个 0-1 随机事件。如果直接按照原始库存 求解 DR 并随机抽样展示,由于随机波动,某些产品可能在销售期中途就意外提前售罄,导致后续时段无法按计划展示。在无展示约束的 SP 中,可以通过以小概率向顾客展示“空货架”来给需求降温,但 SAP 的全部展示约束严禁在有货时展示空货架!Algorithm 4 采取了“虚报缩减库存”的聪明做法:在跑 DR 算法前,先把每件产品的可用库存人为扣减掉一个安全缓冲比例 ,用缩减后的库存 求出 DR 策略,再在每个离散时间步 内按展示时长比例独立随机抽样。Theorem 4 证明:只要最小库存 足够大(远大于 ),根据霍夫丁/切尔诺夫集中不等式(Concentration Bounds),真实库存幾乎不可能在期末前被击穿,随机策略的期望收益无损收敛于 DR 策略的收益。
【具体算例说明】:假设某电商平台在大促期间销售 款可替代的家电单品,每款单品的起始库存至少为 台,预计共有 名顾客先后访问。此时安全缓冲项 (当库存增至 台时,该缓冲比例进一步降至约 )。假设计算出的 DR 策略在第 位顾客对应的单位时间区间 内,前 的时间展示价格组合 ,后 的时间展示价格组合 。那么当第 位顾客实际点击进入页面时,系统只需掷一枚以 概率正面朝上的硬币:若正面则向其展示 ,若反面则展示 (若有未包含的在库商品则标最高价 )。由于预留了安全库存垫,几乎不会发生计划外断货,每位顾客的购买概率与流体模型完全吻合。
4.8 引理 4 (Lemma 4):选择多胞形中不同嵌套链分解的权重和守恒定律
【Lemma 4 命题陈述】(原文第 4 节,第 2547 页) 如果选择多胞形中的一点 可以同时在两条不同的嵌套集合链 和 上进行线性分解,对应的分解权重分别为 和 ,则两条链的权重总和必然严格相等:。 |
|---|
【核心含义解释】:一个目标销量向量 往往来自几个非嵌套组合的凸组合(例如 CDLP 解)。当我们试图把 改写为一串“大集合包含小集合”的嵌套链(Chain)的线性组合时,可能会担心:是不是Sequence 算法选错了嵌套链的顺序,才导致权重和 ?如果换一条嵌套链,权重和会不会变小?Lemma 4 给出了一个令人惊讶的确定性答案:只要分解所用的集合族是嵌套链,无论你怎么变换链条的分解方式,所有链权重的总和都是一个绝对不变量!(事实上,由于每条链都必然以支撑集全集 为起点,结合下三角矩阵的唯一可逆性,该嵌套链分解本身就是唯一确定的)。
【具体算例说明】:设地面集有两个商品 ,当同时展示 时,选择概率向量为 ;单独展示 时为 ;单独展示 时为 。假设目标销量向量为 。在非嵌套分解下,它可以表示为 (权重和为 ,但这不是嵌套链,因为 与 互不包含)。若要求在嵌套链上分解,由于 且 ,最大的集合必须同时包含 ,唯一的正权重嵌套链就是 ,解得 ,权重总和恒为 ,不可能存在另一条嵌套链算出不同的权重总和。
4.9 引理 5 (Lemma 5):Sequence 算法输出与链凸分解 (CCD) 性质的等价判定
【Lemma 5 命题陈述】(原文第 4 节,第 2547 页) 设 ,且 为 Sequence 算法对 返回的链分解。则: (i)点 是链凸可分解的(CCD),当且仅当 ; (ii)Sequence 算法对 中的每一个点都输出链凸分解,当且仅当选择模型 是 CCD 模型。 |
|---|
【核心含义解释】:由于 Lemma 4 证明了嵌套链分解的权重总和是唯一固定的,而 Sequence 算法(Algorithm 1)构造的恰好就是非负权重的嵌套链分解,因此:判断多胞形中的任意目标销量向量 能否表示为一条嵌套链的凸组合(即非负权重之和不超过 1,剩余权重可赋给空集),完全等价于直接把 输入 Sequence 算法,看输出的 是否小于等于 1!如果一个选择模型 本身具有 CCD 性质,那么 Sequence 算法就成为了将任意 CDLP 解无损转化为 DR 解的“万能钥匙”。
【具体算例说明】:对比前文 Example 1 的两个场景:在 Scenario 1(排名偏好模型)中,CDLP 解对应的目标销量向量 经 Sequence 分解后得到 。根据 Lemma 5(i),这直接判定该点 不是 CCD 点,从而该排名偏好模型也不是 CCD 模型,无法在时间 内无损展开。而在 Scenario 2(MNL 模型)中,同一个向量 经 Sequence 分解得到 ,说明该点是 CCD 点(剩余 的权重对应空集或任意最高价兜底组合)。
4.10 引理 6 (Lemma 6):选择模型满足 CCD 性质的充要条件(强对偶商品组合优化准则)
【Lemma 6 命题陈述】(原文第 4.1 节,第 2548 页) 一个单调且弱理性的选择模型 满足链凸分解(CCD)性质,当且仅当对于地面集 的所有排列 ,在由递归方程(式 3–4)生成的特征价格向量 下,单期最优商品组合收益恒等于 1,即:。 |
|---|
【核心含义解释】:Lemma 6 是全文最具方法论创新价值的理论工具。原本要检验一个模型 是否满足 CCD,需要检验多胞形 中无穷多个点 是否都满足 。作者利用线性规划强对偶定理,将这个几何分解问题完美转化为了一个单期商品组合收益最大化(Assortment Optimization)问题:对于元素的任意排列 ,我们先按照递归公式(式 3)给每个元素定一个虚拟价格 ,使得排列的前缀集合 的期望收益全部恰好等于 。此时,如果无论怎么挑子集 ,其期望收益 都绝对不会超过 1,那么模型就一定满足 CCD;反之,只要能找到某一个排列 和某一个子集 使得 ,就立刻证伪该模型不满足 CCD!
【具体算例说明】:假设只有两个独立商品 ,考察排列 。设单独展示 时购买概率为 ;同时展示 时,,。按递归公式求特征价格:首先要求前缀集 收益为 1,即 ;接着要求前缀集 收益为 1,即 。现在检验剩下的非前缀子集 的收益 。由于任何概率都不超过 1,!同理检验排列 若也满足最大收益为 1,则由 Lemma 6 直接断定该模型满足 CCD。
4.11 引理 7 (Lemma 7):可变价格下的马尔可夫链选择模型不满足 CCD 性质
【Lemma 7 命题陈述】(原文第 4.2 节,第 2550 页) 存在一个马尔可夫链选择模型(Markov Chain Choice Model),使得其对应的可变价格修正选择模型 不满足链凸分解(CCD)性质。 |
|---|
【核心含义解释】:在固定价格的经典文献(如 Feldman and Topaloglu 2017)中,马尔可夫链选择模型(作为 MNL 的重要推广)是满足 CCD 性质的。然而 Lemma 7 揭示了一个深刻的结构性差异:一旦引入可变价格,马尔可夫链选择模型就不再满足 CCD 性质!原因在于:当某件商品降价时,原本先看其他商品未果的顾客,会有更高比例转移到这件降价商品上(即状态转移概率随价格改变而发生非对称变化),这使得利用 Lemma 6 构造的特征价格在特定低价子集上产生超过 1 的收益。
【具体算例说明(对应原文 Figure 2 反例)】:考虑两款商品 和两个价格档位 。顾客到达时,有 的初始概率先看商品 1,有 的初始概率先看商品 2。如果顾客先看商品 2 但决定不直接买(或商品 2 不合心意),他会以一定转移概率去考察商品 1:当商品 1 标高价 (即条目 )时,从商品 2 转向商品 1 的转移概率仅为 (另外 直接离开选择 0);但当商品 1 降价至 (即条目 )时,由于价格更有吸引力,从商品 2 转向商品 1 的转移概率翻倍至 !现在考察排列 :按 Lemma 6 递归定出的特征价格为 (这保证了前三个前缀集合的收益都等于 1,因为在第三个前缀集合中有 截留了 的客流,只有初始 的客流买到了 )。然而,如果我们单独拿出子集 (此时商品 2 不在组合中,原本先看商品 2 的 顾客有 的比例全部转移过来购买 !), 的总购买率飙升至 ,导致期望收益达到 !违反了 Lemma 6 的充要条件,从而彻底证明了可变价格下的马尔可夫选择模型不满足 CCD。
4.12 定理 5 (Theorem 5):非平稳时变顾客偏好下的 -紧近似比保证
【Theorem 5 命题陈述】(原文第 5.1 节,第 2550 页) 给定随时间变化的单调且弱理性选择模型序列 ,以及非平稳线性规划松弛(N-CDLP)的一个目标函数值为 的可行解,改进的贪心展开算法(Algorithm 5)输出一个 DR 可行解,其总收益至少为 。此外,在最坏情况下,没有任何算法能保证获得严格大于 的收益。 |
|---|
【核心含义解释】:在现实商业中,不同时段到达的顾客往往具有不同的偏好结构(例如工作日白领客群与周末家庭客群的价格敏感度不同,即 随 变化)。此时,平稳环境下的 近似比下降为 ,但这并不是算法设计不够好,而是问题本身在非平稳环境下的信息与约束壁垒所致:Theorem 5 同时证明了 是所有算法在最坏情况下的理论极限上界(即 是紧界,Tight Bound)。
【具体算例说明】:想象一家生鲜电商拥有 1 单位的高端牛排(产品 1,最高价 )和 1 单位的普通牛排(产品 2,促销价 元,最高价 元),分早晚两个时段()销售:早间顾客()原本只想买 元的普通牛排,但如果货架上同时摆着 元的高端牛排(全部展示约束强制要求摆出),早间顾客会有很大概率转而买走这唯一的一份高端牛排;而晚间到达的顾客()是高净值顾客,只愿意买 元的高端牛排,对普通牛排毫无兴趣。在无展示约束的 N-CDLP 中,平台可以在早间把高端牛排“藏起来”,只卖普通牛排,把高端牛排留给晚间高净值顾客,两单都成交;但在全部展示约束下,只要早间高端牛排还在库就必须以 元展示,一旦被早间顾客买走,晚间高净值顾客到达时高端牛排已断货,导致晚间销售额归零。通过这种跨期客群错配,全部展示约束在最坏情况下会腰斩一半()的收益,而贪心算法恰好能保住至少 的收益底线。
4.13 定理 6 (Theorem 6) 与 引理 8 (Lemma 8):异质最高价格上限下的 CDMIP 紧凑重构与无损转化
【Theorem 6 & Lemma 8 命题陈述】(原文第 5.2 节,第 2551 页) Theorem 6:给定 MNL 选择模型 、任意异质最高可行价格 ,以及混合整数线性规划松弛(CDMIP)的一个 -近似可行解作为输入,Algorithm 2(未包含产品赋其专属最高价 )输出 DR 的一个 -近似可行解。 Lemma 8:当底层选择模型 为 MNL、可行价格集 为离散集且外部选项权重 时,CDMIP 存在一个等价的混合整数线性规划(MILP)重构,其决策变量数与约束数关于 为多项式规模。 |
|---|
【核心含义解释】:当不同商品的最高可行价格 不相同时(例如同一品类中既有最高能卖 1000 元的旗舰机,又有最高只能卖 10 元的清仓手机壳),Lemma 1 不再成立!因为把一个最高只能卖 10 元但吸引力极高的廉价商品强行加入展示组合,会大量吸走原本要买 1000 元旗舰机的客流,导致单期收益雪崩。此时普通 CDLP 与 DR 的差距可以无穷大。为此,作者为每个产品引入 0-1 整数变量 和两条精妙的逻辑约束构建了 CDMIP:
这两条约束的含义是:对于任何一种产品 ,要么它在规划期结束前把全部库存 彻底卖光(对应 ),要么它必须在所有被展示的商品组合中 100% 全程出镜(对应 )!Theorem 6 证明:在 MNL 模型下,只要满足这一“非售罄即全程展示”的二选一条件,通过 Sequence 展开算法就能把 CDMIP 解完全无损地转化为 DR 可行解;而 Lemma 8 则进一步保证了这个含有指数级变量的 CDMIP 可以等价改写为一个只有多项式个变量和约束的紧凑 MILP,直接用现代整数规划求解器即可求出精确最优解。
【具体算例说明(对应原文 Example 2)】:考虑两款商品,各有 1 单位库存,销售期 。产品 1 的可行价格为 (),MNL 权重 ;产品 2 是一款低价引流品,最高可行价格仅为 (,其中 ),但吸引力极高,MNL 权重为 (外部选项 )。如果用传统的 CDLP 求解,CDLP 会选择只展示产品 1(隐藏产品 2),获得期望收益 。但在全部展示约束(DR)下,由于产品 2 有库存,在 内无法卖光 1 单位(最多只能卖出 单位),因此产品 2 永远在库!这就迫使卖方必须全程同时展示产品 1 和产品 2,此时几乎所有顾客都被超低价高权重的引流品 2 吸走,真实 DR 收益为 !而在 CDMIP 模型中,由于产品 2 的最大可能销量严格小于其库存 ,第一条约束 迫使二元变量必须取 ;进而第二条约束 自动强制产品 2 必须出现在每一个展示集合中!这样 CDMIP 就精确捕捉到了“无法售罄的低价品必须全程展示”的物理约束,与 DR 完全零间隙等价。
4.14 全文 15 个核心命题(Lemma 1–8, Theorem 1–6, Corollary 1)全景对照表
| 命题编号 | 所在章节与页码 | 核心数学结论 | 直观核心意思与算例要点 |
|---|---|---|---|
| Lemma 1 | Sec 2.1, p.2541 | 单期无库存限制下,以全场最高价 补齐未展示商品绝不降低当期收益。 | |
| Lemma 2 | Sec 2.3, p.2542 | 椭球法求得 解,支撑集 | 指数级变量的 CDLP 可借单期算子多项式近似求解,且最多只需 个价格组合。 |
| Lemma 3 | Sec 2.3, p.2542 | MNL 下 CDLP 存在 规模 LP | MNL 离散定价的 CDLP 可降维成紧凑销量线性规划,毫秒级精确求解。 |
| Theorem 1 | Sec 3.2, p.2544 | Alg. 2 耗时 ,DR 收益 | Sequence 按目标销量由低价向高价逐级淘汰条目,保证至少获得 比例的 CDLP 收益。 |
| Theorem 2 | Sec 3.2, p.2544 | 当 为 MNL 时,恒有 | MNL 模型下将组合并集按低价到高价展开,总能在规划期 内完成所有目标销量。 |
| Corollary 1 | Sec 3.2, p.2544 | MNL 下 | 同质最高价下,MNL 模型的全部展示约束零收益损失,且最优价格随时间单调递增。 |
| Theorem 3 | Sec 3.3, p.2545 | Greedy 收益 ;最坏上界 | 一般模型下全部展示至少损失 14.8% 收益,而 Greedy 算法稳健保底 63.2% 收益。 |
| Theorem 4 | Sec 3.4, p.2546 | SAP 近似比 | 通过预扣安全库存缓冲并独立随机抽样,在大库存下将 DR 策略无损转化为随机 SAP 策略。 |
| Lemma 4 | Sec 4.0, p.2547 | 任意两条嵌套链分解满足 | 选择多胞形中同一点在不同嵌套链下的分解权重总和是一个绝对守恒不变量。 |
| Lemma 5 | Sec 4.0, p.2547 | 是 CCD | 检验点或模型是否满足链凸分解(CCD),完全等价于检验 Sequence 输出的总权重是否 。 |
| Lemma 6 | Sec 4.1, p.2548 | 是 CCD | 强对偶定理将几何 CCD 判定转化为:递归特征价格向量下不存在期望收益大于 1 的子集。 |
| Lemma 7 | Sec 4.2, p.2550 | 存在 Markov 模型 使 非 CCD | 固定价格下满足 CCD 的马尔可夫链模型,在引入可变价格后因转移概率随价格改变而不再是 CCD。 |
| Theorem 5 | Sec 5.1, p.2550 | 时变偏好 下 Greedy 达 紧界 | 当顾客偏好随时间变化时,改进贪心算法保证 50% 收益,且任何算法在最坏情况下均无法超越 50%。 |
| Theorem 6 | Sec 5.2, p.2551 | 异质 下 CDMIP + Alg. 2 达 -近似 | 当各商品最高限价不同时,MNL 模型下用 CDMIP 替代 CDLP 可通过 Sequence 无损还原 DR 解。 |
| Lemma 8 | Sec 5.2, p.2551 | MNL 下 CDMIP 具 MILP | 引入“售罄或全程展示”二元变量 的 CDMIP 可等价重构为紧凑混合整数线性规划。 |
五、 全文结论的经济与管理学启示总结
本文不仅在运筹学算法与多胞形理论上取得了严密的数学突破,其分析框架与数值实验(第 6 节)更为零售平台、品牌商及收益管理实践者提供了极具指导价值的经济学洞察与管理学启示:
1. “全部展示”合规性与商业利润并非零和博弈——同质价格上限下的无损动态调价法则:在电子商务与实体零售管理中,运营团队常常面临“短期收益最大化”与“长期用户体验/防断货感知”之间的矛盾:算法团队往往倾向于通过隐藏部分低毛利或特定库存商品(即子集定价 SP)来引导消费者购买高溢价商品,而业务与品牌团队则坚持“只要有货就必须上架展示”(即全部展示约束 SAP)以维护搜索透明度与客户留存率。本文的 Theorem 2 与 Corollary 1 给出了一个振奋人心的管理学定论:当同品类替代商品具有相近的标准吊牌价上限()且消费者遵循经典的 MNL 选择行为时,坚持“有货必展示”的商业诚信原则完全不会牺牲任何期望总收益!实现这一双赢局面的关键在于摒弃僵化的静态定价,转而采用反应库存消耗的动态定价策略。
2. 断货替代效应驱动的“早期促销让利、后期逐步提价”单调递增价格路径:传统单商品收益管理或忽略全部展示约束的多商品流体模型往往认为“静态固定价格”在大库存下即是最优。然而本文深刻揭示了“有限库存 + 需求替代 + 全部展示约束”三者交织下的价格演化规律:在销售期初,所有替代款式库存充足、同台竞技,平台应当提供具有吸引力的折扣低价(对应 Sequence 算法的初始大集合 ),以最大化整体客流转化率;随着部分热门款式或低价配额率先售罄,原本属于这些款式的需求会因替代效应溢出到剩余在库款式上,推高在库款式的边际需求率与机会成本。此时,卖方应当顺应断货节奏,分阶段、单调递增地收回折扣、上调在库商品价格(Piecewise Constant and Monotonically Nondecreasing Prices)。数值实验(Figure 3)证实,忽略这一动态提价逻辑而采用静态增广定价(Static Pricing),在库存紧缺( 较小)且产品基础吸引力较高()时,会因大量商品过早以低价流失而造成显著的收益折损。
3. 异质价格上限下的“低价引流品蚕食效应(Cannibalization)”与货架结构治理:当同一页面或同一推荐列表中混杂着最高限价差异悬殊的可替代商品时(第 5.2 节,),本文发出了明确的管理预警:如果某款低价商品( 很低)备货量极大(无法在销售期内售罄)且对消费者极具吸引力,那么“全部展示约束”会迫使该低价品长期占据货架,持续蚕食高价高毛利主推商品的客流(如 Example 2 与数值实验 Scenario 2 中当 且平均库存 增大时,全部展示约束的成本超过 15%)。这给零售商带来两条核心品类管理启示:第一,严格控制低封顶价引流品的备货深度(对应 CDMIP 中令 ),确保低价引流品能够在促销早期快速售罄退场,从而为高价值商品腾出无干扰的溢价销售时间窗;第二,若低价配件库存极大,则在界面设计与推荐架构上不宜将其与高价核心单品置于同一直接替代比较集内,或者必须借助本文提出的 CDMIP 混合整数规划模型 统筹测算“清仓售罄”与“长期陪跑”的全局收益平衡。
4. 复杂消费者偏好与时变客流下的算法选型策略(Sequence vs. Greedy):在工程落地层面,本文提供的两套核心算法各具鲜明的管理适用边界:(1)Sequence 算法(Algorithm 1 & 2)计算极快()、调价方向单调向上(不会出现价格忽高忽低引发消费者对价格不公的反感),在顾客行为接近 MNL 模型时能够实现 100% 理论最优,是标准化零售场景的首选引擎;(2)Greedy 贪心展开算法(Algorithm 3 & 5)则在面对复杂非理性替代行为(如多级嵌套选择、马尔可夫链式比价)以及早晚客群偏好剧烈波动的非平稳场景(Theorem 3 & Theorem 5)时展现出极强的鲁棒性,不仅在理论上提供 (平稳)与 (非平稳紧界)的最坏情况兜底保障,在数值实验中也始终保持在最优解 以上的卓越表现。
5. 从流体规划到实时随机交易系统的“安全库存缓冲垫”机制:在将确定性运筹优化模型部署到真实高并发电商系统时,管理者不能直接将物理总库存 100% 投入流体规划模型。由于“全部展示约束”剥夺了系统通过临时下架在库商品来调控消耗速度的手段,一旦随机洪峰导致某款高利润商品提前断货,整个跨期替代价格链条就会失真。按照 Theorem 4(Algorithm 4)揭示的规律,在算法规划阶段预留约 比例的虚拟安全库存缓冲垫,并配合蒙特卡洛条件期望去随机化技术(Remark 3),能够确保线上实时定价系统在满足 100% 在库展示合规的同时,平稳兑现确定性优化的理论利润。
六、 参考文献 (References)
以下完整附上本文自身标准引用格式及文末引用的全部 53 篇学术文献(共计 54 篇):
[1] Goyal V, Iyengar G, Udwani R (2026) Pricing a Finite Inventory of Substitutable Products with Show-All Constraint. Operations Research 74(5):2536–2555. https://doi.org/10.1287/opre.2022.0479.
[2] Akçay Y, Natarajan HP, Xu SH (2010) Joint dynamic pricing of multiple perishable products under consumer choice. Management Sci. 56(8):1345–1361.
[3] Aouad A, Sarıtaç Ö (2022) Dynamic stochastic matching under limited time. Oper. Res. 70(4):2349–2383.
[4] Ashlagi I, Shi P (2016) Optimal allocation without money: An engineering approach. Management Sci. 62(4):1078–1097.
[5] Avadhanula V, Bhandari J, Goyal V, Zeevi A (2016) On the tightness of an LP relaxation for rational optimization and its applications. Oper. Res. Lett. 44(5):612–617.
[6] Balseiro SR, Besbes O, Pizarro D (2024) Survey of dynamic resource-constrained reward collection problems: Unified model and analysis. Oper. Res. 72(5):2168–2189.
[7] Bitran G, Caldentey R (2003) An overview of pricing models for revenue management. Manufacturing Service Oper. Management 5(3):203–229.
[8] Blanchet J, Gallego G, Goyal V (2016) A Markov chain approximation to choice modeling. Oper. Res. 64(4):886–905.
[9] Block HD, Marschak J (1959) Random orderings and stochastic theories of response. Cowles Foundation Discussion Paper No. 66, Cowles Foundation for Research in Economics, Yale University.
[10] Borle S, Boatwright P, Kadane JB, Nunes JC, Galit S (2005) The effect of product assortment changes on customer retention. Marketing Sci. 24(4):616–622.
[11] Cao Y, Kleywegt AJ, Wang H (2022) Network revenue management under a spiked multinomial logit choice model. Oper. Res. 70(4):2237–2253.
[12] Cao Y, Rusmevichientong P, Topaloglu H (2023) Revenue management under a mixture of independent demand and multinomial logit models. Oper. Res. 71(2):603–625.
[13] Chan CW, Farias VF (2009) Stochastic depletion problems: Effective myopic policies for a class of dynamic optimization problems. Math. Oper. Res. 34(2):333–350.
[14] Chen X, Ma W, Simchi-Levi D, Xin L (2024) Assortment planning for recommendations at checkout under inventory constraints. Math. Oper. Res. 49(1):297–325.
[15] Cheung WC, Simchi-Levi D (2016) Efficiency and performance guarantees for choice-based network revenue management problems with flexible products. Preprint, submitted August 15, https://doi.org/10.2139/ssrn.2823339.
[16] Dai J, Ding W, Kleywegt A, Wang X, Zhang Y (2014) Choice based revenue management for parallel flights. Preprint, submitted March 8, https://doi.org/10.2139/ssrn.2404193.
[17] Den Boer AV (2015) Dynamic pricing and learning: Historical origins, current research, and new directions. Surveys Oper. Res. Management Sci. 20(1):1–18.
[18] Dong L, Kouvelis P, Tian Z (2009) Dynamic pricing and inventory control of substitute products. Manufacturing Service Oper. Management 11(2):317–339.
[19] Dong J, Simsek AS, Topaloglu H (2019) Pricing problems under the markov chain choice model. Production Oper. Management 28(1):157–175.
[20] Elmachtoub AN, Goyal V, Lederman R, Sheth H (2022) Revenue management with product retirement and customer selection. Preprint, submitted February 16, https://doi.org/10.2139/ssrn.4033922.
[21] Feldman BJ, Topaloglu H (2017) Revenue management under the Markov chain choice model. Oper. Res. 65(5):1322–1342.
[22] Feng Y, Niazadeh R, Saberi A (2022) Near-optimal Bayesian online assortment of reusable resources. Immorlica N, Pennock D, eds. Proc. 23rd ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 964–965.
[23] Fishburn PC (1992) Induced binary probabilities and the linear ordering polytope: A status report. Math. Soc. Sci. 23(1):67–80.
[24] Gallego G, Topaloglu H (2014) Constrained assortment optimization for the nested logit model. Management Sci. 60(10):2583–2601.
[25] Gallego G, Topaloglu H (2019) Revenue Management and Pricing Analytics, International Series in Operations Research and Management Science, vol. 279 (Springer, New York).
[26] Gallego G, van Ryzin G (1994) Optimal dynamic pricing of inventories with stochastic demand over finite horizons. Management Sci. 40(8):999–1020.
[27] Gallego G, van Ryzin G (1997) A multiproduct dynamic pricing problem and its applications to network yield management. Oper. Res. 45(1):24–41.
[28] Gallego G, Ratliff R, Shebalov S (2015) A general attraction model and sales-based linear program for network revenue management under customer choice. Oper. Res. 63(1):212–232.
[29] Gallego G, Iyengar G, Phillips R, Dubey A (2020) Managing flexible products on a network. Preprint, submitted April 27, https://doi.org/10.2139/ssrn.3567371.
[30] Ganz A, Nuti P, Schwartz R (2023) A tight competitive ratio for online submodular welfare maximization. Gørtz IL, Farach-Colton M, Puglisi SJ, Herman G, eds. Proc. 31st Annual Eur. Sympos. Algorithms, vol. 274 (Schloss Dagstuhl–Leibniz-Zentrum für Informatik), 52:1–52:17.
[31] Golrezaei N, Nazerzadeh H, Rusmevichientong P (2014) Real-time optimization of personalized assortments. Management Sci. 60(6):1532–1551.
[32] Gong XY, Goyal V, Iyengar GN, Simchi-Levi D, Udwani R, Wang S (2022) Online assortment optimization with reusable resources. Management Sci. 68(7):4772–4785.
[33] Goyal V, Iyengar G, Udwani R (2025) Asymptotically optimal competitive ratio for online allocation of reusable resources. Oper. Res. 73(4):1897–1915.
[34] Kapralov M, Post I, Vondrák J (2013) Online submodular welfare maximization: Greedy is optimal. Khanna S, ed. Proc. 24th Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 1216–1225.
[35] Karp RM, Vazirani UV, Vazirani VV (1990) An optimal algorithm for on-line bipartite matching. Ortiz H, ed. Proc. 22nd Annual ACM Sympos. Theory Comput. (ACM, New York), 352–358.
[36] Kök A, Fisher M, Vaidyanathan R (2015) Assortment planning: Review of literature and industry practice. Agrawal N, Smith SA, eds. Retail Supply Chain Management, International Series in Operations Research & Management Science (Springer US), 175–236.
[37] Luce RD (1959) Individual Choice Behavior: A Theoretical Analysis (John Wiley & Sons, New York).
[38] Ma W, MacRury C, Zhang J (2024) Online contention resolution schemes for network revenue management and combinatorial auctions. Saraf S, ed. 17th Innovations Theoret. Comput. Sci. Conf. (Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Wadern, Germany), 100:1.
[39] Ma W, Simchi-Levi D, Zhao J (2021) Dynamic pricing (and assortment) under a static calendar. Management Sci. 67(4):2292–2313.
[40] Maglaras C, Meissner J (2006) Dynamic pricing strategies for multiproduct revenue management problems. Manufacturing Service Oper. Management 8(2):136–148.
[41] McFadden D (1973) Conditional logit analysis of qualitative choice behavior. Zarembka P, ed. Frontiers in Econometrics.
[42] McFadden D (1978) Modeling the choice of residential location. Transportation Res. Rec. 673.
[43] Mehta A (2013) Online matching and ad allocation. Foundations Trends Theoretical Comput. Sci. 8(4):265–368.
[44] Plackett RL (1975) The analysis of permutations. J. Roy. Statist. Soc. Ser. C (Appl. Statist.) 24(2):193–202.
[45] Raghavan P, Motwani R (1995) Randomized Algorithms (Cambridge University Press, Cambridge, UK).
[46] Sethuraman R, Gázquez-Abad JC, Martínez-López FJ (2022) The effect of retail assortment size on perceptions, choice, and sales: Review and research directions. J. Retailing 98(1):24–45.
[47] Sumida M, Gallego G, Rusmevichientong P, Topaloglu H, Davis J (2021) Revenue-utility tradeoff in assortment optimization under the multinomial logit model with totally unimodular constraints. Management Sci. 67(5):2845–2869.
[48] Sun S, Udwani R, Shen ZJM (2025) A unified algorithmic framework for dynamic assortment optimization under MNL choice. Proc. 26th ACM Conf. Econom. Comput. (ACM, New York), 789–789.
[49] Talluri K, van Ryzin G (2004) Revenue management under a general discrete choice model of consumer behavior. Management Sci. 50(1):15–33.
[50] Topaloglu H (2013) Joint stocking and product offer decisions under the multinomial logit model. Production Oper. Management 22(5):1182–1199.
[51] Udwani R (2025a) Optimality of non-adaptive algorithms in online submodular welfare maximization with stochastic outcomes. Ashlagi I, Roth A, eds. Proc. 26th ACM Conf. Econom. Comput. (ACM, New York), 1.
[52] Udwani R (2025b) Submodular order functions and assortment optimization. Management Sci. 71(1):202–218.
[53] Vera A, Banerjee S, Gurvich I (2021) Online allocation and pricing: Constant regret via bellman inequalities. Oper. Res. 69(3):821–840.
[54] Williams HC (1977) On the formation of travel demand models and economic evaluation measures of user benefit. Environment Planning A 9(3):285–344.