下载链接：https://doi.org/10.1287/opre.2022.2384
01研究背景
2024 OR
用户的选择偏好会受到企业所推荐产品品类组成的影响。对于在线零售商来说，企业沉淀了数以万计的用户浏览和购买数据。因此，为了改善用户购物体验和提高企业收益，企业可以根据每个到达的顾客类型，从他们所售卖的产品中选择一个个性化的品类集合呈现给顾客。这一举措衍生出来了两个阶段的品类管理问题：
1）首先，企业需要决定他们售卖哪些“产品品类”；
2）然后，企业需要根据顾客类型，推荐“个性化的产品品类”；
基于这两个需要，本文使用MMNL模型研究了联合产品品类优化和个性化的问题。对于不同的顾客类型，他们使用MNL模型来刻画顾客在个性化品类中的选择行为。
02研究问题
2024 OR
1）MMNL模型的计算复杂度较高，那联合优化模型的复杂度如何？
2）提供“个性化品类”这一机制是否会比非个性化带来更多的收益改善？
3）该如何近似求解这个联合优化问题，同时保证近似算法的性能保障？
03研究模型
2023 OR
1）问题建立
有N个候选产品N={1,...,n}，产品i的收益为r_i；
假设这些产品的收益按降序排序：即r_1≥r_2≥…≥r_n≥0；
有M个顾客类型M={1,...,m}，类型j到达的概率为θj
假设在第一阶段品类优化中，从N中选出一个子集S作为企业售卖的产品组合。在第二阶段中，给j类顾客提供的产品品类为Sj，则顾客选择其中产品i的概率为：
则从j类顾客获取的最大期望收益表示为：
第一阶段的品类优化函数为：
Remark：若算出了S，第二阶段的优化就是一个普通的基于MMNL模型的产品品类优化问题，已经有大量的研究提出了近似算法。
2）问题复杂度
即使只有2种顾客类型，这个问题也是NP-HARD。
3）个性化的价值
去掉个性化的步骤，(CAP)会变为一个基于MMNL模型的问题：
由于CAP是MMNL的一个松弛版本，所以可以判断出来前者的最优收益至少会比后者的最优收益要多，因此有如下结论：
4）贪婪算法
将原来的优化问题重写为：
其中，f是monotone increasing的，非submodular。
贪婪算法：从集合P种找到一个size为k的子集，使得函数g最大化。基本的策略是每次迭代选择使得收益增量最大的那个产品。该算法可以得到原问题（1-1/e）的近似结果，但是它要求g满足单调和submodular。
Augmented贪婪算法：两步骤，取出收益排名前i的一个产品集合Vi,先用贪婪算法用这个集合返回一个子集，然后再用该子集去为顾客类型集C选择一个size小于k的品类集合。
该算法的bound为：
5）近似算法
上面的结论给出了关于贪婪算法自身的一个bound，接下来就是比较近似问题最优和原问题最优之间的性质。
同质到达：当每一类顾客到达概率相等时候，Augmented算法返回的结果是原问题最优解的一个近似。
异质到达：当顾客类型到达概率不同的时候，先根据顾客到达概率将顾客类型划分为几个group，每个group C都用前面的贪婪算法去求解最优的品类组合，然后使用动态规划将这些品类组合结合在一起，就是最终返回的品类组合。该算法的bound是：
04研究结论
2024 OR
本文考虑了一个联合品类优化和品类个性化的问题，通过对问题两阶段的描述和建模，分析了模型的有关性质和个性化的重要性。考虑到模型求解的困难，本文对贪婪算法进行了改进，并证明了算法的性能保证。然后，在用户到达概率同质和异质的假设下，分别分析了算法最优和原问题最优的bound。针对异质到达概率的情况，将顾客类型按到达概率分组构建成树形结构，从而在贪婪算法的基础上，加入了动态规划求解的步骤。
识别二维码关注我们
文章推荐人 | 罗陈斌
笔记审核人 | 付严亮
校对 | 罗陈斌
排版 | 赵骏明
