Assortment Planning with Sponsored Products

技术摘要：包含赞助产品的品类规划

问题陈述
本文研究了电子商务和推荐系统中的品类规划问题，特别地，将研究范围从传统的有机产品（organic products）扩展到了包含赞助产品（sponsored products）的情况。以往的研究（例如 Talluri 和 Van Ryzin 2004）主要侧重于有机产品，而赞助位置（例如在亚马逊、Facebook、Google 上）的兴起引入了一个复杂的优化挑战。平台必须选择并排列一组 $k$ 个产品，以在遵守广告主特定约束的同时，实现预期收入的最大化。

核心难点在于如何平衡平台的收入目标与赞助产品的强制性要求。与可以放置在任意位置的有机产品不同，赞助产品通常带有由拍卖机制（例如，广告主竞标“前-$m$”个位置或基于质量得分的特定插槽）产生的严格位置约束。该问题被建模为一个组合优化任务，其目标是在 多元逻辑回归（MNL） 选择模型下，寻找一个能够使预期收入最大化的可行序列。

方法论
作者使用 MNL 模型对消费者选择行为进行建模，其中消费者选择产品 $i$ 的概率取决于该产品在特定位置的内在效用以及所有展示产品的效用。由于选择概率的分母包含所有被选中项目的效用之和，因此收入函数是非线性的。

针对不同的约束条件，作者提出了两种算法路径：

1. 基础约束下的精确解：
   当约束仅为必须放置赞助产品（即每个赞助产品 $i$ 必须被分配到一个有效的有效位置 $t \in R_i$）时，该问题被建模为一个指派问题（assignment problem）。作者证明了该约束矩阵是**全单模（totally unimodular）**的。因此，通过将整数约束放宽为线性规划（LP）形式，可以获得最优解，且保证能得到整数解。

2. 扩展约束下的近似算法：
   本文将问题扩展到包含对有机产品选择的额外约束，例如容量（背包）约束（总成本 $\le C$）或划分拟阵（partition matroid）约束（限制来自特定组的物品数量）。

   • 分解策略： 最优解被分解为两个部分：赞助产品的收入和有机产品的收入。作者构建了两个候选品类：
     • 候选方案 I： 仅考虑赞档产品（忽略有机产品）来优化收入。
     • 候选方案 II： 首先最小化赞助产品的总权重（效用），从而为有机产品的选择“节省”出效用，然后在固定赞助产品选择的前提下，优化有机产品的品类。
   • 随机选择： 最终方案会选择这两个候选方案中较优的一个。理论分析表明，如果有机子问题（P.5）能在 $\beta$ 的比例内得到近似，则整体算法实现的近似比为 $\frac{\beta}{\beta+1}$。
   • 次模优化： 为了在复杂约束下解决有机子问题（P.5），作者将排序问题转化为针对产品-位置对集合的子集选择问题。他们证明了所得的效用函数是**单调且次模（monotone and submodular）**的。这使得应用最先进的次模最大化算法成为可能：
     • 对于背包约束，他们使用的算法实现的比例为 $\beta = 1/(1+\epsilon)^3$。
     • 对于划分拟阵约束，他们使用的算法实现的比例为 $\beta = 1/(2+\epsilon)$。

核心贡献

• 问题建模： 本文正式定义了存在具有位置特定约束的赞助产品的品类规划问题，填补了现有文献中的空白，因为现有文献通常假设所有产品都是有机的，或者忽略了赞助产品的整合。
• 理论保证： 不同于依赖深度学习启发式方法且缺乏理论边界的现有工作（例如 Liao 等人 2022），本文提供了严谨的近似保证。
• 算法框架： 作者开发了一个桥接平台收入最大化与广告主约束之间的框架。他们证明了基础问题可以通过线性规划在多项式时间内求解，并为涉及有机产品容量或多样性约束的更复杂变体提供了常数因子近似算法。
• 次模性证明： 一个重要的技术贡献是证明了用于有机产品选择的转换后的效用函数具有次模性，从而能够使用高效的近似算法来处理 NP-hard 约束。

结果
本文确立了以下理论结果：

• 对于基础问题（仅限赞助产品约束），可以高效地计算出最优解。
• 对于扩展问题（赞助产品约束 + 有机产品容量/拟阵约束），所提出的算法实现的近似比为：
  • 对于背包约束，为 $\frac{1}{(1+\epsilon)^3 + 1}$。
  • 对于划分拟阵约束，为 $\frac{1}{(2+\epsilon) + 1}$。
  • （注：论文推导出的最终比例为 $\frac{\beta}{\beta+1}$，其中 $\beta$ 是子问题的近似比）。

意义与主张
作者声称，这项研究通过显式建模赞助产品的整合，解决了品类规划文献中的一个关键空白。这项工作的意义在于提供了一种能够平衡平台（收入最大化）与广告主（特定投放要求）之间往往冲突的目标的理论保证。论文断言，其方法为企业提供了一种在不损害整体收入策略或用户体验的前提下，无缝集成赞助产品的方法，且该方法是基于可证明的数学边界而非启发式性能。该工作被视为在这一不断发展的电子商务推荐系统领域开展未来研究的基础性步骤。