Resumo Técnico: Sortimentos Experimentais para Estimativa de Escolha e Identificação de Ninhos

1. Definição do Problema

O artigo aborda dois desafios interconectados na modelagem de escolha discreta:

1. Design de Sortimento Experimental: Como projetar deliberadamente um pequeno número de sortimentos de produtos (subconjuntos de itens) para coletar dados para estimar modelos de escolha complexos sobre $n$ itens totais. A literatura existente frequentemente recorre a dados observacionais (onde a variação do sortimento é não controlada) ou experimentação aleatória, o que os autores argumentam ser ineficiente para aprender padrões de substituição ricos.
2. Identificação de Ninhos: Especificamente para modelos de Logit Aninhado (Nested Logit - NL), que particionam itens em "ninhos" de substitutos próximos, os procedimentos de estimação existentes tipicamente assumem que a estrutura do ninho é conhecida e fixa. O artigo busca identificar automaticamente a partição de ninhos correta a partir dos dados coletados, sem depender de uma classificação subjetiva ex-ante.

A motivação central é que modelos padrão como o Logit Multinomial (MNL) frequentemente falham em capturar padrões de substituição realistas (por exemplo, clientes mudando para substitutos próximos dentro de uma categoria em vez de distantes). Embora os modelos de Logit Aninhado possam capturar isso, eles exigem saber o agrupamento de itens, o que é difícil de determinar subjetivamente.

2. Metodologia

A. Design de Experimento Combinatório

Os autores propõem um design de experimento estruturado e não adaptativo que requer apenas $O(\log n)$ sortimentos distintos, uma taxa mostrada como sendo informação-teoricamente ótima.

• Mecanismo: Cada um dos $n$ itens recebe uma codificação binária única de comprimento $L = \lceil \log_2 n \rceil$.
• Construção do Sortimento: Para cada posição de bit $\ell \in \{1, \dots, L\}$, dois sortimentos experimentais são criados:
  1. $S_{\ell, -0}$: Contém todos os itens com um '0' no $\ell$-ésimo bit.
  2. $S_{\ell, -1}$: Contém todos os itens com um '1' no $\ell$-ésimo bit.
• Propriedade: Este design garante que, para qualquer par de itens distintos $(i, j)$, exista pelo menos um sortimento experimental contendo $i$ mas não $j$ (e vice-versa). Esta propriedade de "separação" permite ao algoritmo observar como a remoção de um item afeta as vendas de outro, o que é crítico para identificar relações de substituição.
• Eficiência: O design utiliza aproximadamente $2 \lceil \log_2 n \rceil$ sortimentos experimentais mais um sortimento de controle (oferecendo todos os itens), significativamente menos do que os $O(n)$ ou $O(n^2)$ sortimentos exigidos por designs anteriores (ex: "deixar um fora" ou designs pareados).

B. Algoritmo de Identificação de Ninhos

Os autores desenvolvem um algoritmo de dedução lógica que recupera a partição de ninhos oculta a partir das probabilidades de escolha observadas (ou dados de vendas).

• Fatores de Impulso (Boost Factors): O algoritmo define um "fator de impulso" para um item $i$ no sortimento $S$ como a razão entre sua probabilidade de escolha em $S$ e sua probabilidade de escolha no sortimento de controle total $[n]$.
• Deduções Lógicas:
  • Baixo Impulso: Se o fator de impulso de um item for igual ao do item externo (ou da linha de base), isso implica que o ninho do item estava totalmente contido em $S$. Isso permite que o algoritmo deduza que o item não está no mesmo ninho que qualquer item ausente de $S$.
  • Alto Impulso: Se um item exibe um fator de impulso alto e distinto, isso implica que seu ninho foi parcialmente removido. Itens que compartilham o mesmo fator de impulso alto dentro de um sortimento são deduzidos como estando no mesmo ninho.
• Abordagem Teoria-dos-Grafos: O algoritmo mantém uma matriz de adjacência representando a pertinência ao ninho por pares. Ele itera através dos $O(\log n)$ sortimentos, atualizando a matriz com base nas comparações de fatores de impulso. Ele emprega operações de "Transitividade de Um Salto" (One-Hop Transitivity) e "Identificar Pares Ausentes" para resolver a partição completa.
• Robustez: Garantias teóricas são fornecidas para configurações sem ruído. Para configurações de amostra finita, os autores propõem um framework de teste estatístico (usando testes $z$ de duas proporções) e uma etapa de pós-processamento de detecção de comunidades (algoritmo Walktrap) para lidar com ruídos e inconsistências nos dados.

C. Recuperação de Parâmetros

Uma vez identificada a partição de ninhos, o artigo demonstra que os parâmetros restantes do Logit Aninhado (pesos de preferência $v_i$ e parâmetros de dissimilaridade $\lambda_N$) podem ser recuperados resolvendo um sistema linear derivado das probabilidades de escolha observadas, desde que uma suposição de não-degenerescência seja mantida.

3. Principais Contribuições

1. Design de Experimento Ótimo: O artigo introduz um design combinatório usando $O(\log n)$ sortimentos que garante a identificação da estrutura de ninhos do Logit Aninhado. Os autores provam um limite inferior correspondente ($\Omega(\log n)$), mostrando que mesmo designs adaptativos não podem fazer melhor.
2. Identificação de Ninhos Baseada em Dados: Ao contrário de trabalhos anteriores que assumem ninhos fixos, este artigo fornece um algoritmo para identificar a partição de ninhos diretamente dos dados. O algoritmo aproveita a estrutura específica do design de experimento proposto para realizar deduções que são impossíveis com sortimentos aleatórios ou de tamanho reduzido.
3. Desempenho de Estimação Superior: O design proposto supera consistentemente designs aleatórios e heurísticos (como o "deixar um fora") em benchmarks numéricos. Ele reduz o erro de estimação (RMSE) significativamente, particularmente em cenários com poucos dados ou modelos mal especificados.
4. Implementação no Mundo Real: A metodologia foi implementada no Dream11, uma plataforma de esportes de fantasia indiana, envolvendo 70 milhões de usuários e 72 tipos de concursos. O experimento identificou com sucesso ninhos significativos que melhoraram a previsão fora da amostra em comparação tanto com modelos MNL quanto com modelos NL com agrupamento (clustering) ex-ante baseado em atributos.

4. Resultados

Benchmarks Numéricos

• Cenários de Má Especificação: Quando a verdade fundamental segue uma distribuição complexa (Lista Ranqueada) e vários modelos (MNL, NL, Cadeia de Markov) são estimados, o design proposto com $O(\log n)$ sortimentos produz consistentemente um RMSE menor do que designs aleatórios com o mesmo número de sortimentos. Ele reduz o erro em até 5,5% em regimes de pequenos dados.
• Cenários Bem Especificados: Quando o modelo estimado coincide com a verdade fundamental (ex: NL ou Cadeia de Markov reais), o design proposto supera os designs aleatórios mesmo quando os designs aleatórios utilizam significativamente mais sortimentos (até $T$ sortimentos distintos). Em configurações de Cadeia de Markov, a redução no RMSE atingiu 16,9%.
• Identificação de Ninhos: O pipeline completo (design + algoritmo de identificação) reduz o RMSE em até 46% em comparação ao uso do algoritmo de identificação de ninhos de Benson et al. (2016) com seu design original. Os autores atribuem isso ao maior conteúdo de informação de seus sortimentos de tamanho $\approx n/2$ em comparação aos sortimentos de tamanho 2 ou 3 usados por Benson et al.

Implementação no Dream11

• Previsão: Um modelo de Logit Aninhado com ninhos identificados pelos dados (identificados pelo algoritmo) superou um modelo MNL padrão e um modelo NL com ninhos determinados por agrupamento $k$-means em atributos de concursos.
• Interpretabilidade: Os ninhos identificados foram economicamente interpretáveis. Por exemplo, o algoritmo agrupou concursos com diferentes taxas de entrada e prêmios, mas com "Ratios de Vencedores" e "Ratios de Prêmios" idênticos, sugerindo que os usuários percebem o valor através de métricas normalizadas em vez de atributos brutos. Também agrupou concursos do tipo "vencedor leva tudo" e identificou padrões comportamentais sutis em relação à saliência do número de vencedores.

5. Significância e Alegações

O artigo afirma que o passo de coleta de dados (design de experimento) é um determinante de primeira ordem para o desempenho da estimação de escolha, potencialmente mais impactante do que a escolha do próprio modelo de estimação.

• Mudança de Paradigma: Os autores argumentam que a literatura tem amplamente ignorado o design de experimentos para escolha, recorrendo por padrão a dados observacionais ou aleatórios. Este trabalho demonstra que um arranjo combinatório deliberado de sortimentos pode extrair significativamente mais informações sobre padrões de substituição.
• Eficiência vs. Complexidade: O design alcança a otimalidade da informação ($\text{O}(\log n)$) enquanto utiliza sortimentos de tamanho $\approx n/2$, o que maximiza a informação por observação. Isso contrasta com designs de "deixar um fora" (que são ineficientes em termos de dados devido aos pequenos efeitos) e designs de pares pequenos (que são enviesados ou exigem $O(n^2)$ experimentos).
• Utilidade Prática: O sucesso da implementação em uma plataforma com 70 milhões de usuários demonstra que o design é escalável e operacionalmente viável (exigindo apenas 14 sortimentos distintos para 72 itens). Os ninhos resultantes forneceram insights de negócios acionáveis que eram difíceis de derivar apenas por meio de agrupamento baseado em atributos.

O artigo conclui que, embora a justificativa teórica seja específica para o Logit Aninhado, o sucesso empírico se estende a modelos de escolha gerais, sugerindo que a experimentação estruturada é uma estratégia superior para aprender padrões de substituição de escolha em comparação com a randomização.