📊 statistics

Experimental Assortments for Choice Estimation and Nest Identification

本文提出了一种使用 $O(\log n)$ 个组合的结构化非自适应实验设计，该设计不仅在估计各种选择模型方面优于现有方法，还使一种能够准确识别嵌套 Logit 模型中项目嵌套的新算法成为可能，该框架已通过在 Dream11 上的大规模部署得到了成功验证，提升了样本外预测能力并提供了具有管理实践意义的见解。

原作者： Xintong Yu, Will Ma, Michael Zhao

发布于 2026-06-23

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Xintong Yu, Will Ma, Michael Zhao

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你是一位店主，正试图弄清楚顾客到底更喜欢哪些饮料。你的菜单上有 72 种不同类型的饮料。为了了解他们的选择，你需要观察从货架上撤掉一些饮料时会发生什么。

如果你只是每天随机决定撤掉哪些饮料，你可能会走运，也可能会感到困惑。例如，如果你在同一天撤掉了“苹果汁”和“橙汁”，你就无法判断是想喝苹果汁的人转向了橙汁，还是他们直接回家没买东西了。

这篇论文提出了一种聪明且在数学上近乎完美的方案，来运行这些“味觉测试”（实验），让你能以最少的实验天数获取最多的信息。

以下是他们解决方案的详细拆解：

1. “二进制代码”菜单策略

与其随机挑选要撤掉的饮料，作者建议给每种饮料一个秘密的二进制代码（就像由 0 和 1 组成的条形码）。

类比： 假设你有 8 种饮料。你给它们分配代码，如 000、001、010 直到 111。
实验： 与其测试所有可能的组合（那会耗费太长时间），你只需要进行 6 次特定的测试（外加一天提供所有饮料的情况）。
- 测试 1： 提供所有代码第一个位置为 1 的饮料。
- 测试 2： 提供所有代码第一个位置为 0 的饮料。
- 测试 3 & 4： 对第二个位置进行同样的操作。
- 测试 5 & 6： 对第三个位置进行同样的操作。

为什么这很神奇： 因为每种饮料都有唯一的代码，对于你选出的任意两种饮料，都保证至少有一次测试中，其中一种在货架上，而另一种被隐藏了。这让你能够准确观察撤掉某一种特定饮料是如何影响另一种饮料的销售额的。

论文证明，对于 $n$ 个项目，你只需要大约 $\log n$ 次测试。所以，即使你有 1,000 个项目，你也不需要 1,000 次测试；你只需要大约 10 或 11 次。这是极其高效的。

2. 寻找“秘密家族”（嵌套识别）

一旦通过这些智能测试获得了销售数据，你就会想知道：哪些饮料是“近乎替代品”？

问题： 如果撤掉了“苹果汁”，人们是转向了“橙汁”（因为它们都是果汁），还是转向了“牛奶”（因为它们都是早餐饮品）？
“提升”线索： 作者观察了一个“提升因子”（Boost Factor）。如果拿走一种饮料，其“好朋友”（即近乎替代品）的销售额会大幅跳升。而不相关的饮料销售额只会轻微跳升。
推导：
- 小幅跳升： 如果撤掉饮料 B 时，饮料 A 的销售额仅轻微上升，那么它们不属于同一个家族。
- 大幅跳升： 如果撤掉饮料 B 时，饮料 A 的销售额翻了一倍，那么它们很可能属于近乎替代品（处于同一个“嵌套”中）。

论文引入了一种像侦探一样的算法。它观察这 6 次测试中所有的“跳升”情况，并逻辑地推导出整个产品的家族树。它仅通过这 6 次测试就能理清 72 个项目的正确分组，这在理论上如果靠随机测试则需要成千上万次。

3. 现实世界测试：幻想体育巨头

作者不仅在计算机模拟中进行研究。他们与 Dream11 合作，这是一个拥有 7,000 万用户的印度大型幻想体育平台。

设定： Dream11 有数百种不同的“竞赛”（比如不同类型的游戏）供用户加入。管理者并不知道哪些竞赛是彼此互为替代品的。
行动： 他们针对“二进制代码”实验运行了 21 天。他们向不同的用户群体展示不同的竞赛组合，每次都会根据数学计算隐藏大约一半的竞赛。
结果：
- 他们成功识别出了用户视为可互换的竞赛“嵌套”。
- 这些基于数据的分组，在预测用户未来选择方面，比管理者基于简单特征（如报名费）的直觉判断做得更好。
- 这些分组在管理者看来也非常合理：例如，他们发现用户将“赢家通吃”的高额奖金竞赛视为一个家族，无论具体的报名费是多少，因为它们的结构（奖金分配方式）是相同的。

总结

这篇论文解决了两个大问题：

如何测试： 不要靠猜测。使用二进制代码系统来测试少量的特定组合，这些组合能保证你学到所需的一切。
如何学习： 利用这些测试的结果，自动将项目归类为“家族”（替代品），而无需询问客户或根据产品特征进行猜测。

这就像是在尝试弄清楚巨大的钥匙串中哪些钥匙能打开哪些锁。你不需要尝试每一把钥匙去开每一个锁（那太慢了），而是使用一种特定的尝试模式，保证能以最短的时间找到匹配项。

技术摘要：用于选择估计与嵌套识别的实验性品类组合设计

1. 问题定义

本文探讨了离散选择建模中两个相互关联的挑战：

实验性品类组合设计（Experimental Assortment Design）： 如何有目的地设计少量的产品组合（即项的子集），以便为估计包含 $n$ 个总项的复杂选择模型收集数据。现有文献通常依赖于观测数据（其中品类组合的变化是不可控的）或随机化实验，作者认为这些方法在学习丰富的替代模式方面效率较低。
嵌套识别（Nest Identification）： 特别是针对嵌套 Logit（NL）模型，该模型将各项划分为“嵌套”以表示紧密的替代品。现有的估计程序通常假设嵌套结构是已知且固定的。本文旨在通过收集到的数据自动识别正确的嵌套划分，而不依赖于主观的、先验的分类。

核心动机在于，标准的多元 Logit（MNL）模型往往无法捕捉真实的替代模式（例如，客户会转向同一类别内的紧密替代品，而非远距离的替代品）。虽然嵌套 Logit 模型可以捕捉这一点，但它需要预先知道项的分组方式，而这在主观判断上是非常困难的。

2. 方法论

A. 组合实验设计

作者提出了一种结构化的非自适应实验设计，仅需 $O(\log n)$ 个不同的品类组合，这一速率被证明在信息论上是最优的。

机制： 每个项 $n$ 被分配一个长度为 $L = \lceil \log_2 n \rceil$ 的唯一二进制编码。
品类组合构建： 对于每个位位置 $\ell \in \{1, \dots, L\}$ $ℓ \in {1, \dots, L}$ ，创建两个实验性品类组合：
1. $S_{\ell, -0}$ ：包含第 $\ell$ 位为 '0' 的所有项。
2. $S_{\ell, -1}$ ：包含第 $\ell$ 位为 '1' 的所有项。
属性： 该设计保证对于任何一对不同的项 $(i, j)$ ，都至少存在一个实验性品类组合包含 $i$ 但不包含 $j$ （反之亦然）。这种“分离”属性允许算法观察移除一个项如何影响另一个项的销售情况，这对于识别替代关系至关重要。
效率： 该设计使用大约 $2 \lceil \log_2 n \rceil$ 个实验性品类组合加上一个控制组合（提供所有项），显著少于以往设计（如“留一法”或成对设计）所需的 $O(n)$ 或 $O(n^2)$ 个组合。

B. 嵌套识别算法

作者开发了一种逻辑演绎算法，从观测到的选择概率（或销售数据）中恢复隐藏的嵌套划分。

提升因子（Boost Factors）： 算法将组合 $S$ 中某项 $i$ 的“提升因子”定义为其在 $S$ 中的选择概率与在全量控制组合 $[n]$ 中的选择概率之比。
逻辑演绎：
- 小提升： 如果一个项的提升因子等于外部选项（或基准项）的提升因子，这意味着该项所属的嵌套被完全包含在 $S$ 中。这使得算法可以推断出该项并不与 $S$ 中缺失的任何项属于同一个嵌套。
- 大提升： 如果一个项表现出较大的、独特的提升因子，这意味着其所属的嵌套被部分移除了。在同一个组合内共享相同的大提升因子的项，被推断为属于同一个嵌套。
图论方法： 算法维护一个代表成对嵌套成员关系的邻接矩阵。它遍历 $O(\log n)$ 个组合，并根据提升因子的比较来更新矩阵。它采用“一跳传递性（One-Hop Transitivity）”和“识别缺失对（Identify Missing Pairs）”操作来解决完整的划分问题。
鲁棒性： 论文为无噪声设置提供了理论保证。对于有限样本设置，作者提出了一个统计测试框架（使用两比例 $z$ 检验）和一个社区检测后处理步骤（Walktrap 算法），以处理数据中的噪声和不一致性。

C. 参数恢复

一旦识别出嵌套划分，本文展示了可以通过求解由观测选择概率导出的线性方程组来恢复剩余的嵌套 Logit 参数（偏好权重 $v_i$ 和差异参数 $\lambda_N$ ），前提是满足非退化假设。

3. 核心贡献

最优实验设计： 本文引入了一种使用 $O(\log n)$ 个组合的组合设计，该设计保证了能够识别嵌套 Logit 的嵌套结构。作者证明了与之匹配的下界（ $\Omega(\log n)$ ），表明即使是自适应设计也无法做得更好。
数据驱动的嵌套识别： 不同于以往假设固定嵌套的工作，本文提供了一种直接从数据中识别嵌套划分的算法。该算法利用了所提实验设计的特定结构，从而实现了在随机或小规模组合下无法实现的演绎。
卓越的估计性能： 在数值基准测试中，所提设计在面对误设模型时，表现优于随机化设计和启发式设计（如“留一法”）。它显著降低了估计误差（RMSE），特别是在数据有限或模型误设的情况下。
实际部署： 该方法已部署在印度幻想体育平台 Dream11 上，涉及 7000 万用户和 72 种竞赛类型。实验成功识别了具有意义的嵌套，相比于 MNL 模型和基于先验特征聚类的 NL 模型，提升了样本外预测能力。

4. 结果

数值基准测试

误设设置： 当真实分布遵循复杂的分布（排序列表）且估计各种模型（MNL、NL、马尔可夫链）时，所提 $O(\log n)$ 组合的设计在 RMSE 上始终低于具有相同组合数量的随机化设计。在小数据量级下，它能减少高达 5.5% 的误差。
设定正确设置： 当估计模型与真实模型匹配时（例如真实的 NL 或马尔可夫链），所提设计即使在随机化设计使用更多组合（高达 $T$ 个不同组合）的情况下也表现更优。在马尔可夫链设置中，RMSE 的降幅达到了 16.9%。
嵌套识别： 完整的流水线（设计 + 识别算法）相比于使用 Benson 等人 (2016) 原有设计的嵌套识别算法，可降低高达 46% 的 RMSE。作者将其归功于其 $O(n/2)$ 规模组合比 Benson 等人使用的规模为 2 或 3 的组合具有更高的信息含量。

Dream11 部署

预测： 使用数据驱动嵌套（由算法识别）的嵌套 Logit 模型，优于标准的 MNL 模型以及使用 $k$ -means 聚类竞赛特征确定的 NL 模型。
可解释性： 识别出的嵌套具有经济学上的可解释性。例如，算法将具有不同报名费和奖金池、但“胜率（Winner Ratios）”和“奖金率（Prize Ratios）”相同的竞赛归为一类，这表明用户是通过标准化指标而非原始属性来感知价值的。它还对“赢家通吃”类型的竞赛进行了分组，并识别了关于获胜人数显著性的微妙行为模式。

5. 重要性与主张

本文声称，数据收集步骤（实验设计）是决定选择估计性能的首要因素，其影响力可能超过了选择估计模型本身。

范式转移： 作者认为，文献在很大程度上忽略了选择估计中的实验设计，通常默认使用随机化或观测数据。这项工作证明，一种刻意的、组合式的品类组合排列可以提取更多关于替代模式的信息。
效率与复杂性： 该设计在实现信息论最优性（ $O(\log n)$ ）的同时，使用了规模约为 $n/2$ 的组合，从而最大化了单次观测的信息量。这与“留一法”设计（由于效应微弱而数据效率低下）以及小规模成对设计（容易产生偏差或需要 $O(n^2)$ 次实验）形成了对比。
实用价值： 在拥有 7000 万用户的平台上成功部署，证明了该设计的可扩展性和操作可行性（对于 72 个项目仅需 14 个不同组合）。由此产生的嵌套提供了难以通过基于特征的聚类获得的、具有行动力的商业洞察。

本文得出结论：虽然其理论依据是针对嵌套 Logit 的，但其在经验上的成功可以推广到一般的选择模型，这表明结构化实验是比随机化更优的学习选择替代模式的策略。