Technical Summary: Experimental Assortments for Choice Estimation and Nest Identification

1. Problem Definition

The paper addresses two interconnected challenges in discrete choice modeling:

1. Experimental Assortment Design: How to deliberately design a small number of product assortments (subsets of items) to collect data for estimating complex choice models over $n$ total items. Existing literature often relies on observational data (where assortment variation is uncontrolled) or randomized experimentation, which the authors argue is inefficient for learning rich substitution patterns.
2. Nest Identification: Specifically for Nested Logit (NL) models, which partition items into "nests" of close substitutes, existing estimation procedures typically assume the nest structure is known and fixed. The paper seeks to automatically identify the correct nest partition from collected data without relying on subjective, ex-ante classification.

The core motivation is that standard models like the Multinomial Logit (MNL) often fail to capture realistic substitution patterns (e.g., customers switching to close substitutes within a category rather than distant ones). While Nested Logit models can capture this, they require knowing the grouping of items, which is difficult to determine subjectively.

2. Methodology

A. Combinatorial Experiment Design

The authors propose a structured, non-adaptive experiment design that requires only $O(\log n)$ distinct assortments, a rate shown to be information-theoretically optimal.

• Mechanism: Each of the $n$ items is assigned a unique binary encoding of length $L = \lceil \log_2 n \rceil$.
• Assortment Construction: For each bit position $\ell \in \{1, \dots, L\}$, two experimental assortments are created:
  1. $S_{\ell, -0}$: Contains all items with a '0' in the $\ell$-th bit.
  2. $S_{\ell, -1}$: Contains all items with a '1' in the $\ell$-th bit.
• Property: This design guarantees that for any pair of distinct items $(i, j)$, there exists at least one experimental assortment containing $i$ but not $j$ (and vice versa). This "separation" property allows the algorithm to observe how the removal of one item affects the sales of another, which is critical for identifying substitution relationships.
• Efficiency: The design uses approximately $2 \lceil \log_2 n \rceil$ experimental assortments plus one control assortment (offering all items), significantly fewer than the $O(n)$ or $O(n^2)$ assortments required by previous designs (e.g., "leave-one-out" or pairwise designs).

B. Nest Identification Algorithm

The authors develop a logical deduction algorithm that recovers the hidden nest partition from the observed choice probabilities (or sales data).

• Boost Factors: The algorithm defines a "boost factor" for an item $i$ in assortment $S$ as the ratio of its choice probability in $S$ to its choice probability in the full control assortment $[n]$.
• Logical Deductions:
  • Small Boost: If an item's boost factor equals that of the outside option (or the baseline), it implies the item's nest was fully contained in $S$. This allows the algorithm to deduce that the item is not in the same nest as any item missing from $S$.
  • Large Boost: If an item exhibits a large, distinct boost factor, it implies its nest was partially removed. Items sharing the same large boost factor within an assortment are deduced to be in the same nest.
• Graph-Theoretic Approach: The algorithm maintains an adjacency matrix representing pairwise nest membership. It iterates through the $O(\log n)$ assortments, updating the matrix based on the boost factor comparisons. It employs "One-Hop Transitivity" and "Identify Missing Pairs" operations to resolve the full partition.
• Robustness: Theoretical guarantees are provided for noiseless settings. For finite-sample settings, the authors propose a statistical testing framework (using two-proportion $z$-tests) and a community detection post-processing step (Walktrap algorithm) to handle noise and inconsistencies in the data.

C. Parameter Recovery

Once the nest partition is identified, the paper demonstrates that the remaining Nested Logit parameters (preference weights $v_i$ and dissimilarity parameters $\lambda_N$) can be recovered by solving a linear system derived from the observed choice probabilities, provided a non-degeneracy assumption holds.

3. Key Contributions

1. Optimal Experiment Design: The paper introduces a combinatorial design using $O(\log n)$ assortments that guarantees the identification of the Nested Logit nest structure. The authors prove a matching lower bound ($\Omega(\log n)$), showing that even adaptive designs cannot do better.
2. Data-Driven Nest Identification: Unlike prior work that assumes fixed nests, this paper provides an algorithm to identify the nest partition directly from data. The algorithm leverages the specific structure of the proposed experiment design to make deductions that are impossible with random or small-sized assortments.
3. Superior Estimation Performance: The proposed design consistently outperforms randomized and heuristic designs (like "leave-one-out") in numerical benchmarks. It reduces estimation error (RMSE) significantly, particularly in settings with limited data or mis-specified models.
4. Real-World Deployment: The methodology was deployed on Dream11, an Indian fantasy sports platform, involving 70 million users and 72 contest types. The experiment successfully identified meaningful nests that improved out-of-sample prediction compared to both MNL models and NL models with ex-ante (feature-based) clustering.

4. Results

Numerical Benchmarks

• Mis-specified Settings: When the ground truth follows a complex distribution (Ranked List) and various models (MNL, NL, Markov Chain) are estimated, the proposed design with $O(\log n)$ assortments consistently yields lower RMSE than randomized designs with the same number of assortments. It reduces error by up to 5.5% in small data regimes.
• Well-Specified Settings: When the estimated model matches the ground truth (e.g., true NL or Markov Chain), the proposed design outperforms randomized designs even when the randomized designs use significantly more assortments (up to $T$ distinct assortments). In Markov Chain settings, the reduction in RMSE reached 16.9%.
• Nest Identification: The full pipeline (design + identification algorithm) reduces RMSE by up to 46% compared to using the nest identification algorithm of Benson et al. (2016) with their original design. The authors attribute this to the higher information content of their $O(n/2)$-sized assortments versus the size-2 or size-3 assortments used by Benson et al.

Dream11 Deployment

• Prediction: A Nested Logit model with data-driven nests (identified by the algorithm) outperformed a standard MNL model and an NL model with nests determined by $k$-means clustering on contest features.
• Interpretability: The identified nests were economically interpretable. For example, the algorithm grouped contests with different entry fees and prize pools but identical "Winner Ratios" and "Prize Ratios," suggesting users perceive value through normalized metrics rather than raw attributes. It also grouped "winner-take-all" contests and identified subtle behavioral patterns regarding the salience of the number of winners.

5. Significance and Claims

The paper claims that the data collection step (experiment design) is a first-order determinant of choice estimation performance, potentially more impactful than the choice of the estimation model itself.

• Shift in Paradigm: The authors argue that the literature has largely ignored experiment design for choice estimation, often defaulting to randomized or observational data. This work demonstrates that a deliberate, combinatorial arrangement of assortments can extract significantly more information about substitution patterns.
• Efficiency vs. Complexity: The design achieves information-theoretic optimality ($O(\log n)$) while using assortments of size $\approx n/2$, which maximizes the information per observation. This contrasts with "leave-one-out" designs (which are data-inefficient due to small effects) and small-pair designs (which are biased or require $O(n^2)$ experiments).
• Practical Utility: The successful deployment on a platform with 70 million users demonstrates that the design is scalable and operationally feasible (requiring only 14 distinct assortments for 72 items). The resulting nests provided actionable business insights that were difficult to derive from feature-based clustering alone.

The paper concludes that while the theoretical justification is specific to Nested Logit, the empirical success extends to general choice models, suggesting that structured experimentation is a superior strategy for learning choice substitution patterns compared to randomization.