Résumé technique : Assortiments expérimentaux pour l'estimation du choix et l'identification de nids

1. Définition du problème

Le document traite de deux défis interconnectés dans la modélisation du choix discret :

1. Conception d'assortiments expérimentaux : Comment concevoir délibérément un petit nombre d'assortiments de produits (sous-ensembles d'articles) pour collecter des données permettant d'estimer des modèles de choix complexes sur $n$ articles au total. La littérature existante repose souvent sur des données observationnelles (où la variation des assortiments est incontrôlée) ou sur l'expérimentation aléatoire, ce qui, selon les auteurs, est inefficace pour apprendre des schémas de substitution riches.
2. Identification de nids : Spécifiquement pour les modèles Logit à nids (Nested Logit - NL), qui partitionnent les articles en « nids » de substituts proches, les procédures d'estimation existantes supposent généralement que la structure du nid est connue et fixe. Le document cherche à identifier automatiquement la partition de nids correcte à partir des données collectées sans dépendre d'une classification subjective ex ante.

La motivation centrale est que les modèles standards comme le Logit Multinomial (MNL) échouent souvent à capturer des schémas de substitution réalistes (par exemple, les clients passant à des substituts proches au sein d'une catégorie plutôt qu'à des substituts éloignés). Bien que les modèles de Logit à nids puissent capturer cela, ils nécessitent de connaître le regroupement des articles, ce qui est difficile à déterminer de manière subjective.

2. Méthodologie

A. Conception d'expériences combinatoires

Les auteurs proposent une conception d'expérience structurée et non adaptative qui ne nécessite que $O(\log n)$ assortiments distincts, un taux qui s'avère être informationnellement optimal.

• Mécanisme : Chaque article parmi les $n$ reçoit un codage binaire unique de longueur $L = \lceil \log_2 n \rceil$.
• Construction de l'assortiment : Pour chaque position de bit $\ell \in \{1, \dots, L\}$, deux assortiments expérimentaux sont créés :
  1. $S_{\ell, -0}$ : Contient tous les articles ayant un '0' à la $\ell$-ième position.
  2. $S_{\ell, -1}$ : Contient tous les articles ayant un '1' à la $\ell$-ième position.
• Propriété : Cette conception garantit que pour toute paire d'articles distincts $(i, j)$, il existe au moins un assortiment expérimental contenant $i$ mais pas $j$ (et vice versa). Cette propriété de « séparation » permet à l'algorithme d'observer comment la suppression d'un article affecte les ventes d'un autre, ce qui est crucial pour identifier les relations de substitution.
• Efficacité : La conception utilise environ $2 \lceil \log_2 n \rceil$ assortiments expérimentaux plus un assortiment de contrôle (offrant tous les articles), soit nettement moins que les $O(n)$ ou $O(n^2)$ assortiments requis par les conceptions précédentes (par exemple, « leave-one-out » ou les conceptions par paires).

B. Algorithme d'identification de nids

Les auteurs développent un algorithme de déduction logique qui récupère la partition de nids cachée à partir des probabilités de choix observées (ou des données de ventes).

• Facteurs de boost (Boost Factors) : L'algorithme définit un « facteur de boost » pour un article $i$ dans un assortiment $S$ comme le ratio de sa probabilité de choix dans $S$ par rapport à sa probabilité de choix dans l'assortiment de contrôle complet $[n]$.
• Déductions logiques :
  • Petit boost : Si le facteur de boost d'un article est égal à celui de l'option externe (ou de la référence), cela implique que son nid était entièrement contenu dans $S$. Cela permet à l'algorithme de déduire que l'article n'est pas dans le même nid que tout article manquant de $S$.
  • Grand boost : Si un article présente un facteur de boost important et distinct, cela implique que son nid a été partiellement retiré. Les articles partageant le même grand facteur de boost au sein d'un assortiment sont déduits d'appartenir au même nid.
• Approche par la théorie des graphes : L'algorithme maintient une matrice d'adjacence représentant l'appartenance aux nids par paire. Il itère à travers les $O(\log n)$ assortiments, mettant à jour la matrice sur la base des comparaisons de facteurs de boost. Il emploie des opérations de « Transitivité à un bond » (One-Hop Transitivity) et d'« Identification des paires manquantes » (Identify Missing Pairs) pour résoudre la partition complète.
• Robustesse : Des garanties théoriques sont fournies pour les contextes sans bruit. Pour les contextes à échantillon fini, les auteurs proposent un cadre de test statistique (utilisant des tests $z$ de deux proportions) et une étape de post-traitement de détection de communauté (algorithme Walktrap) pour gérer le bruit et les incohérences des données.

C. Récupération des paramètres

Une fois la partition des nids identifiée, le document démontre que les paramètres restants du modèle Logit à nids (poids de préférence $v_i$ et paramètres de dissimilarité $\lambda_N$) peuvent être récupérés en résolvant un système linéaire dérivé des probabilités de choix observées, à condition qu'une hypothèse de non-dégénérescence soit respectée.

3. Contributions clés

1. Conception d'expérience optimale : Le document introduit une conception combinatoire utilisant $O(\log n)$ assortiments qui garantit l'identification de la structure de nid du Logit à nids. Les auteurs prouvent une borne inférieure correspondante ($\Omega(\log n)$), montrant que même les conceptions adaptatives ne peuvent faire mieux.
2. Identification de nids basée sur les données : Contra à les travaux antérieurs qui supposent des nids fixes, ce document fournit un algorithme pour identifier la partition de nids directement à partir des données. L'algorithme tire parti de la structure spécifique de la conception d'expérience proposée pour effectuer des déductions impossibles avec des assortiments aléatoires ou de petite taille.
3. Performance d'estimation supérieure : La conception proposée surpasse systématiquement les conceptions aléatoires et heuristiques (comme le « leave-one-out ») dans les tests numériques. Elle réduit l'erreur d'estimation (RMSE) de manière significative, particulièrement dans les contextes de données limitées ou de modèles mal spécifiés.
4. Déploiement en conditions réelles : La méthodologie a été déployée sur Dream11, une plateforme de fantasy sports indienne, impliquant 70 millions d'utilisateurs et 72 types de concours. L'expérience a identifié avec succès des nids significatifs qui ont amélioré la prédiction hors échantillon par rapport aux modèles MNL et aux modèles NL avec un clustering ex ante (basé sur les caractéristiques).

4. Résultats

Tests numériques

• Contextes mal spécifiés : Lorsque la vérité terrain suit une distribution complexe (Ranked List) et que divers modèles (MNL, NL, Chaîne de Markov) sont estimés, la conception proposée avec $O(\log n)$ assortiments produit systématiquement un RMSE plus faible que les conceptions aléatoires avec le même nombre d'assortiments. Elle réduit l'erreur jusqu'à 5,5 % dans les régimes de faibles données.
• Contextes bien spécifiés : Lorsque le modèle estimé correspond à la vérité terrain (par exemple, NL ou Chaîne de Markov), la conception proposée surpasse les conceptions aléatoires même lorsque les conceptions aléatoires utilisent beaucoup plus d'assortiments (jusqu'à $T$ assortiments distincts). Dans les contextes de Chaîne de Markov, la réduction du RMSE a atteint 16,9 %.
• Identification de nids : L'ensemble du pipeline (conception + algorithme d'identification) réduit le RMSE jusqu'à 46 % par rapport à l'utilisation de l'algorithme d'identification de nids de Benson et al. (2016) avec leur conception originale. Les auteurs attribuent cela à la teneur informationnelle plus élevée de leurs assortements de taille $\approx n/2$ par rapport aux assortements de taille 2 ou 3 utilisés par Benson et al.

Déploiement sur Dream11

• Prédiction : Un modèle Logit à nids avec des nids dérivés des données (identifiés par l'algorithme) a surpassé un modèle MNL standard et un modèle NL avec des nids déterminés par un clustering k-means sur les caractéristiques des concours.
• Interprétabilité : Les nids identifiés étaient économiquement interprétables. Par exemple, l'algorithme a regroupé des concours avec des frais d'entrée et des pools de prix différents mais des « Ratios de Gagnants » et des « Ratios de Prix » identiques, suggérant que les utilisateurs perçoivent la valeur via des métriques normalisées plutôt que par des attributs bruts. Il a également regroupé les concours de type « winner-take-all » et a identifié des schémas comportementaux subtils concernant la saillance du nombre de gagnants.

5. Signification et affirmations

Le document affirme que la étape de collecte de données (conception d'expérience) est un déterminant de premier ordre de la performance d'estimation du choix, potentiellement plus impactant que le choix du modèle d'estimation lui-même.

• Changement de paradigme : Les auteurs soutiennent que la littérature a largement ignoré la conception d'expériences pour l'estimation du choix, se contentant souvent de données aléatoires ou observationnelles. Ce travail démontre qu'un arrangement combinatoire délibéré d'assortiments peut extraire beaucoup plus d'informations sur les schémas de substitution.
• Efficacité vs Complexité : La conception atteint l'optimalité informationnelle ($O(\log n)$) tout en utilisant des assortements de taille $\approx n/2$, ce qui maximise l'information par observation. Cela contraste avec les conceptions « leave-one-out » (peu efficaces en données en raison des effets de faible ampleur) ou les conceptions par petites paires (biaisées ou nécessitant $O(n^2)$ expériences).
• Utilité pratique : Le succès du déploiement sur une plateforme de 70 millions d'utilisateurs démontre que la conception est scalable et opérationnellement réalisable (nécessitant seulement 14 assortiments distincts pour 72 articles). Les nids résultants ont fourni des informations commerciales exploitables qui étaient difficiles à dériver d'un clustering basé sur les caractéristiques seul.

Le document conclut que bien que la justification théorique soit spécifique au Logit à nids, le succès empirique s'étend aux modèles de choix généraux, suggérant que l'expérimentation structurée est une stratégie supérieure pour apprendre les schémas de substitution de choix par rapport à la randomisation.