Resumen Técnico: Surtidos Experimentales para la Estimación de Elecciones e Identificación de Nidos

1. Definición del Problema

El artículo aborda dos desafíos interconectados en el modelado de elección discreta:

1. Diseño de Surtidos Experimentales: Cómo diseñar deliberadamente un pequeño número de surtidos de productos (subconjuntos de artículos) para recolectar datos para estimar modelos de elección complejos sobre $n$ artículos totales. La literatura existente suele depender de datos observacionales (donde la variación del surtido no está controlada) o de la experimentación aleatoria, lo cual los autores argumentan que es ineficiente para aprender patrones de sustitución ricos.
2. Identificación de Nidos: Específicamente para los modelos de Logit Anidado (NL), que particionan los artículos en "nidos" de sustitutos cercanos, los procedimientos de estimación existentes típicamente asumen que la estructura del nido es conocida y fija. El artículo busca identificar automáticamente la partición de nidos correcta a partir de los datos recolectados sin depender de una clasificación subjetiva ex-ante.

La motivación central es que los modelos estándar como el Logit Multinomial (MNL) a menudo no logran capturar patrones de sustitución realistas (por ejemplo, clientes que cambian a sustitutos cercanos dentro de una categoría en lugar de a otros distantes). Aunque los modelos de Logit Anidado pueden capturar esto, requieren conocer la agrupación de los artículos, lo cual es difícil de determinar subjetivamente.

2. Metodología

A. Diseño de Experimentos Combinatorios

Los autores proponen un diseño de experimento estructurado y no adaptativo que requiere solo $O(\log n)$ surtidos distintos, una tasa que se ha demostrado es información-teóricamente óptima.

• Mecanismo: Cada uno de los $n$ artículos se asigna una codificación binaria única de longitud $L = \lceil \log_2 n \rceil$.
• Construcción del Surtido: Para cada posición de bit $\ell \in \{1, \dots, L\}$, se crean dos surtidos experimentales:
  1. $S_{\ell, -0}$: Contiene todos los artículos con un '0' en el $\ell$-ésimo bit.
  2. $S_{\ell, -1}$: Contiene todos los artículos con un '1' en el $\ell$-ésimo bit.
• Propiedad: Este diseño garantiza que para cualquier par de artículos distintos $(i, j)$, existe al menos un surtido experimental que contiene a $i$ pero no a $j$ (y viceversa). Esta propiedad de "separación" permite al algoritmo observar cómo la eliminación de un artículo afecta las ventas de otro, lo cual es crítico para identificar relaciones de sustitución.
• Eficiencia: El diseño utiliza aproximadamente $2 \lceil \log_2 n \rceil$ surtidos experimentales más un surtido de control (que ofrece todos los artículos), significativamente menos que los $O(n)$ o $O(n^2)$ surtidos requeridos por diseños previos (por ejemplo, "dejar uno fuera" o diseños por pares).

B. Algoritmo de Identificación de Nidos

Los autores desarrollan un algoritmo de deducción lógica que recupera la partición de nidos oculta a partir de las probabilidades de elección observadas (o datos de ventas).

• Factores de Impulso (Boost Factors): El algoritmo define un "factor de impulso" para un artículo $i$ en el surtido $S$ como la razón de su probabilidad de elección en $S$ respecto a su probabilidad de elección en el surtido de control completo $[n]$.
• Deducciones Lógicas:
  • Impulso Pequeño: Si el factor de impulso de un artículo es igual al del la opción externa (o la base), implica que su nido estaba totalmente contenido en $S$. Esto permite al algoritmo deducir que el artículo no está en el mismo nido que cualquier artículo ausente en $S$.
  • Impulso Grande: Si un artículo exhibe un factor de impulso grande y distinto, implica que su nido fue parcialmente eliminado. Los artículos que comparten el mismo factor de impulso grande dentro de un surtido se deducen como pertenecientes al mismo nido.
• Enfoque de Teoría de Grafos: El algoritmo mantiene una matriz de adyacencia que representa la membresía de nidos por pares. Itera a través de los $O(\log n)$ surtidos, actualizando la matriz basándose en las comparaciones de los factores de impulso. Emplea operaciones de "Transitividad de un Salto" (One-Hop Transitivity) e "Identificar Pares Faltantes" para resolver la partición completa.
• Robustez: Se proporcionan garantías teóricas para entornos sin ruido. Para configuraciones de muestra finita, los autores proponen un marco de pruebas estadísticas (usando pruebas $z$ de dos proporciones) y un paso de post-procesamiento de detección de comunidades (algoritmo Walktrap) para manejar el ruido y las inconsistencias en los datos.

C. Recuperación de Parámetros

Una vez identificada la partición de nidos, el artículo demuestra que los parámetros restantes del Logit Anidado (pesos de preferencia $v_i$ y parámetros de disimilitud $\lambda_N$) pueden recuperarse resolviendo un sistema lineal derivado de las probabilidades de elección observadas, siempre que se cumpla un supuesto de no degeneración.

3. Contribuciones Clave

1. Diseño de Experimentos Óptimo: El artículo introduce un diseño combinatorio utilizando $O(\log n)$ surtidos que garantiza la identificación de la estructura de nidos del Logit Anidado. Los autores demuestran un límite inferior coincidente ($\Omega(\log n)$), mostrando que incluso los diseños adaptativos no pueden superarlo.
2. Identificación de Nidos Basada en Datos: A diferencia de trabajos previos que asumen nidos fijos, este artículo proporciona un algoritmo para identificar la partición de nidos directamente de los datos. El algoritmo aprovecha la estructura específica del diseño de experimentos propuesto para realizar deducciones que son imposibles con surtidos aleatorios o de tamaño reducido.
3. Desempeño de Estimación Superior: El diseño propuesto supera consistentemente a los diseños aleatorios y heurísticos (como "dejar uno fuera") en pruebas numéricas. Reduce el error de estimación (RMSE) significativamente, particularmente en entornos con datos limitados o modelos mal especificados.
4. Implementación en el Mundo Real: La metodología se implementó en Dream11, una plataforma de deportes de fantasía de la India, involucrando a 70 millones de usuarios y 72 tipos de concursos. El experimento identificó exitosamente nidos significativos que mejoraron la predicción fuera de la muestra en comparación tanto con modelos MNL como con modelos NL con agrupamiento (clustering) basado en características ex-ante.

4. Resultados

Pruebas Numéricas (Benchmarks)

• Entornos Mal Especificados: Cuando la verdad fundamental sigue una distribución compleja (Lista Clasificada) y se estiman varios modelos (MNL, NL, Cadena de Markov), el diseño propuesto con $O(\log n)$ surtidos arroja consistentemente un RMSE menor que los diseños aleatorios con el mismo número de surtidos. Reduce el error hasta en un 5.5% en regímenes de pocos datos.
• Entornos Bien Especificados: Cuando el modelo estimado coincide con la verdad fundamental (por ejemplo, NL o Cadena de Markov reales), el diseño propuesto supera a los diseños aleatorios incluso cuando los diseños aleatorios utilizan significativamente más surtidos (hasta $T$ surtidos distintos). En configuraciones de Cadena de Markov, la reducción del RMSE alcanzó el 16.9%.
• Identificación de Nidos: El flujo completo (diseño + algoritmo de identificación) reduce el RMSE hasta en un 46% en comparación con el uso del algoritmo de identificación de nidos de Benson et al. (2016) con su diseño original. Los autores atribuyen esto al mayor contenido de información de sus surtidos de tamaño $\approx n/2$ frente a los surtidos de tamaño 2 o 3 utilizados por Benson et al.

Implementación en Dream11

• Predicción: Un modelo de Logit Anidado con nidos identificados por datos superó a un modelo MNL estándar y a un modelo NL con nidos determinados por clustering de $k$-means sobre las características de los concursos.
• Interpretabilidad: Los nidos identificados fueron económicamente interpretables. Por ejemplo, el algoritmo agrupó concursos con diferentes tarifas de entrada y premios pero con idénticos "Ratios de Ganadores" (Winner Ratios) y "Ratios de Premios" (Prize Ratios), sugiriendo que los usuarios perciben el valor a través de métricas normalizadas en lugar de atributos brutos. También agrupó concursos de "ganador único" e identificó patrones de comportamiento sutiles respecto a la salvedad del número de ganadores.

5. Significado y Reivindicaciones

El artículo sostiene que el paso de recolección de datos (diseño de experimentos) es un determinante de primer orden en el desempeño de la estimación de elección, potencialmente más impactante que la elección del modelo de estimación en sí.

• Cambio de Paradigma: Los autores argumentan que la literatura ha ignorado ampliamente el diseño de experimentos para la elección, recurriendo por defecto a datos aleatorios u observacionales. Este trabajo demuestra que un arreglo combinatorio deliberado de surtidos puede extraer significativamente más información sobre los patrones de sustitución.
• Eficiencia vs. Complejidad: El diseño logra la optimalidad de información ($\Omega(\log n)$) mientras utiliza surtidos de tamaño $\approx n/2$, lo que maximiza la información por observación. Esto contrasta con los diseños de "dejar uno fuera" (que son ineficientes en términos de datos debido a efectos pequeños) o los diseños de pares pequeños (que son sesgados o requieren $O(n^2)$ experimentos).
• Utilidad Práctica: El éxito de la implementación en una plataforma con 70 millones de usuarios demuestra que el diseño es escalable y operativamente factible (requiriendo solo 14 surtidos distintos para 72 artículos). Los nidos resultantes proporcionaron información comercial accionable que era difícil de derivar únicamente mediante el clustering basado en características.

El artículo concluye que, si bien la justificación teórica es específica para el Logit Anidado, el éxito empírico se extiende a modelos de elección generales, sugiriendo que la experimentación estructurada es una estrategia superior para aprender patrones de sustitución de elección en comparación con la aleatorización.