📊 statistics

Experimental Assortments for Choice Estimation and Nest Identification

Dit artikel stelt een gestructureerd, niet-adaptief experimenteel ontwerp voor met $O(\log n)$ assortimenten dat niet alleen bestaande methoden voor het schatten van diverse keuzemodellen overtreft, maar ook een nieuw algoritme mogelijk maakt om item-nesten in Nested Logit-modellen nauwkeurig te identificeren, een raamwerk dat succesvol is gevalideerd door middel van een grootschalige implementatie op Dream11 die de voorspelling buiten de steekproef verbeterde en bruikbare inzichten bood voor het management.

Oorspronkelijke auteurs: Xintong Yu, Will Ma, Michael Zhao

Gepubliceerd 2026-06-23

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Xintong Yu, Will Ma, Michael Zhao

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je een winkelier bent die probeert te achterhalen welke dranken je klanten werkelijk verkiezen. Je hebt 72 verschillende soorten dranken op je menu. Om hun keuzes te begrijpen, moet je zien wat er gebeurt als je sommige dranken uit het schap haalt.

Als je elke dag willekeurig beslist welke dranken je verwijdert, kun je geluk hebben, of je kunt in de war raken. Als je bijvoorbeeld "Appelsap" en "Orangesap" op dezelfde dag verwijdert, kun je niet zien of mensen die appelsap wilden zijn overgestapt op orangesap, of dat ze gewoon naar huis zijn gegaan zonder iets te kopen.

Dit artikel stelt een slimme, wiskundig perfecte manier voor om deze "smaaktests" (experimenten) uit te voeren, zodat je met de kleinste hoeveelheid dagen het meeste leert.

Hier is de onderverdeling van hun oplossing:

1. De "Binair Code" Menu Strategie

In plaats van willekeurig te kiezen welke dranken je verwijdert, stellen de auteurs voor om elke enkele drank een geheime binaire code te geven (zoals een streepjescode gemaakt van 0'en en 1'en).

De Analogie: Stel dat je 8 dranken hebt. Je geeft ze codes zoals 000, 001, 010, tot en met 111.
Het Experiment: In plaats van elke mogelijke combinatie te testen (wat eeuwig zou duren), hoef je slechts 6 specifieke tests uit te voeren (plus één dag waarop je alles aanbiedt).
- Test 1: Bied alle dranken aan met een 1 op de eerste plek van hun code.
- Test 2: Bied alle dranken aan met een 0 op de eerste plek.
- Test 3 & 4: Doe hetzelfde voor de tweede plek van de code.
- Test 5 & 6: Doe hetzelfde voor de derde plek van de code.

Waarom dit magisch is: Omdat elke drank een unieke code heeft, is er voor elke twee dranken die je kiest gegarandeerd minstens één test waarbij de ene op het schap ligt en de andere verborgen is. Dit stelt je in staat om precies te zien hoe het verwijderen van één specifieke drank de verkoop van een andere beïnvloedt.

Het artikel bewijst dat je voor $n$ items slechts ongeveer $\log n$ tests nodig hebt. Dus zelfs als je 1.000 items hebt, heb je niet 1.000 tests nodig; je hebt er slechts ongeveer 10 of 11 nodig. Dit is ongelooflijk efficiënt.

2. Het vinden van de "Geheime Families" (Nest Identificatie)

Zodra je de verkoopgegevens van deze slimme tests hebt, wil je weten: Welke dranken zijn "dichtbij vervangers"?

Het Problema: Als je "Appelsap" verwijdert, schakelen mensen dan over op "Orangesap" (omdat ze beide sappen zijn) of op "Melk" (omdat ze beide ontbijtdranken zijn)?
De "Boost" Aanwijzing: De auteurs kijken naar een "Boost Factor". Als je een drank verwijdert, zal de verkoop van zijn "beste vriend" (zijn nauwe substituut) aanzienlijk omhoog springen. De verkoop van ongerelateerde dranken zal slechts een beetje omhoog springen.
De Deductie:
- Kleine Sprong: Als de verkoop van Drank A een klein beetje omhoog gaat wanneer Drank B wordt verwijderd, behoren ze niet tot dezelfde familie.
- Grote Sprong: Als de verkoop van Drank A verdubbelt wanneer Drank B wordt verwijderd, zijn ze waarschijnlijk nauwe substituten (in hetzelfde "nest").

Het artikel introduceert een algoritme dat werkt als een detective. Het kijkt naar al deze "sprongen" over de 6 tests heen en leidt logischerwijs de hele familiestamboom van de producten af. Het kan de juiste groepering van 72 items bepalen met slechts die 6 tests, een prestatie die theoretisch duizenden willekeurige tests zou vereisen.

3. Real-World Test: De Fantasy Sports Gigant

De auteurs hebben dit niet alleen in een computersimulatie gehouden. Ze zijn een partnerschap aangegaan met Dream11, een enorm Indiaas fantasy sports platform met 70 miljoen gebruikers.

De Opzet: Dream11 heeft honderden verschillende "contests" (zoals verschillende soorten spellen) waar gebruikers aan kunnen deelnemen. De managers wisten niet welke contests nauwe substituten van elkaar waren.
De Actie: Ze voerden het "Binary Code" experiment uit gedurende 21 dagen. Ze toonden verschillende groepen gebruikers verschillende sets contests, waarbij ongeveer de helft van de contests telkens werd verborgen op basis van de wiskunde.
Het Resultaat:
- Ze hebben succesvol "nests" geïdentificeerd van contests die gebruikers als vervangbaar beschouwden.
- Deze op data gebaseerde groepen voorspelden beter wat gebruikers in de toekomst zouden kiezen dan de eigen vermoedens van de managers (die gebaseerd waren op eenvoudige kenmerken zoals deelnamegelden).
- De groepen waren logisch voor de managers: bijvoorbeeld ontdekten ze dat gebruikers "Winner-Take-All" contests met hoge inzetten als een familie beschouwden, ongeacht het specifieke deelnamegeld, omdat de structuur van de prijs hetzelfde was.

Samenvatting

Het artikel lost twee grote problemen op:

Hoe te testen: Gok niet willekeurig. Gebruik een binair codesysteem om een klein aantal specifieke combinaties te testen die garanderen dat je alles leert wat je moet weten.
Hoe te leren: Gebruik de resultaten van die tests om items automatisch in "families" van substituten te groeperen zonder dat je klanten hoeft te vragen of moet gokken op basis van productkenmerken.

Het is alsof je probeert uit te zoeken welke sleutels welke sloten openen in een enorme sleutelbos. In plaats van elke sleutel in elk slot te proberen (wat eeuwen duurt), gebruik je een specifiek patroon van het proberen van sleutels dat garandeert dat je de juiste matches in recordtijd vindt.

Technische Samenvatting: Experimentele Assortimenten voor Keuzeschatting en Nestidentificatie

1. Probleemdefinitie

Het artikel behandelt twee onderling verbonden uitdagingen in discrete keuzemodellering:

Experimenteel Assortimentontwerp: Hoe ontwerpt men doelbewust een klein aantal productassortimenten (subsets van items) om data te verzamelen voor het schatten van complexe keuzemodellen over $n$ totale items. Bestaande literatuur leunt vaak op observationele data (waarbij de variatie in assortiment ongecontroleerd is) of gerandomiseerde experimentatie, wat de auteurs als inefficiënt beschouwen voor het leren van rijke substitutiepatronen.
Nestidentificatie: Specifiek voor Nested Logit (NL) modellen, die items verdelen in "nesten" van nauwe substituten, gaan bestaande schattingsprocedures er doorgaans van uit dat de neststructuur bekend en vaststaand is. Dit artikel streeft ernaar om de correcte nestpartitie automatisch te identificeren uit verzamelde data, zonder te vertrouwen op een subjectieve, ex-ante classificatie.

De kernmotivatie is dat standaardmodellen zoals de Multinomial Logit (MNL) vaak niet in staat zijn om realistische substitutiepatronen te vangen (bijvoorbeeld klanten die overstappen naar nauwe substituten binnen een categorie in plaats van naar verre substituten). Hoewel Nested Logit-modellen dit wel kunnen vangen, vereisen zij kennis van de groepering van items, wat moeilijk subjectief te bepalen is.

2. Methodologie

A. Combinatorisch Experimentontwerp

De auteurs stellen een gestructureerd, niet-adaptief experimentontwerp voor dat slechts $O(\log n)$ verschillende assortimenten vereist, een snelheid die bewezen informatie-theoretisch optimaal is.

Mechanisme: Elk van de $n$ items krijgt een unieke binaire codering van lengte $L = \lceil \log_2 n \rceil$ .
Assortimentconstructie: Voor elke bitpositie $\ell \in \{1, \dots, L\}$ $ℓ \in {1, \dots, L}$ worden twee experimentele assortimenten gecreëerd:
1. $S_{\ell, -0}$ : Bevat alle items met een '0' op de $\ell$ -de bit.
2. $S_{\ell, -1}$ : Bevat alle items met een '1' op de $\ell$ -de bit.
Eigenschap: Dit ontwerp garandeert dat voor elk paar verschillende items $(i, j)$ er ten minste één experimenteel assortiment bestaat dat $i$ bevat maar niet $j$ (en vice versa). Deze "scheidings"-eigenschap stelt het algoritme in staat om te observeren hoe het verwijderen van één item de verkoop van een ander item beïnvloedt, wat cruciaal is voor het identificeren van substitutierelaties.
Efficiëntie: Het ontwerp gebruikt ongeveer $2 \lceil \log_2 n \rceil$ experimentele assortimenten plus één controle-assortiment (dat alle items biedt), aanzienlijk minder dan de $O(n)$ of $O(n^2)$ assortimenten die vereist zijn door eerdere ontwerpen (bijv. "leave-one-out" of paarvormige ontwerpen).

B. Nestidentificatiealgoritme

De auteurs ontwikkelen een logisch deductie-algoritme dat de verborgen nestpartitie herstelt uit de geobserveerde keuzekansen (of verkoopdata).

Boostfactoren: Het algoritme definieert een "boostfactor" voor een item $i$ in assortiment $S$ als de ratio van zijn keuzekans in $S$ tot zijn keuzekans in het volledige controle-assortiment $[n]$ .
Logische Deducties:
- Kleine Boost: Als de boostfactor van een item gelijk is aan die van de buitenoptie (of de baseline), impliceert dit dat het nest van het item volledig aanwezig was in $S$ . Dit stelt het algoritme in staat om te deduceren dat het item niet in hetzelfde nest zit als een item dat ontbreekt in $S$ .
- Grote Boost: Als een item een grote, onderscheidende boostfactor vertoont, impliceert dit dat zijn nest gedeeltelijk is verwijderd. Items die binnen een assortiment dezelfde grote boostfactor delen, worden geduceerd als behorend tot hetzelfde nest.
Graaf-theoretische Aanpak: Het algoritme onderhoudt een nabijheidsmatrix die de paarvormige nestlidmaatschap representeert. Het iterereert door de $O(\log n)$ assortimenten en werkt de matrix bij op basis van de vergelijking van boostfactoren. Het maakt gebruik van "One-Hop Transitivity" en "Identify Missing Pairs" operaties om de volledige partitie op te lossen.
Robuustheid: Er worden theoretische garanties gegeven voor ruisloze settings. Voor eindige steekproeven stellen de auteurs een statistisch testframework voor (met behulp van twee-proportie $z$ -toetsen) en een community detection post-processing stap (Walktrap-algoritme) om ruis en inconsistenties in de data op te vangen.

C. Parameterherstel

Zodra de nestpartitie is geïdentificeerd, demonstreren de auteurs dat de resterende Nested Logit-parameters (voorkeursgewichten $v_i$ en dissimilariteitsparameters $\lambda_N$ ) kunnen worden hersteld door een lineair systeem op te lossen dat is afgeleid van de geobserveerde keuzekansen, mits een niet-degeneratiediscrepantie geldt.

3. Belangrijkste Bijdragen

Optimaal Experimentontwerp: Het artikel introduceert een combinatorisch ontwerp met gebruik van $O(\log n)$ assortimenten dat de identificatie van de Nested Logit-neststructuur garandeert. De auteurs bewijzen een bijbehorende ondergrens ( $\Omega(\log n)$ ), waarmee zij aantonen dat zelfs adaptieve ontwerpen niet beter kunnen presteren.
Data-gedreven Nestidentificatie: In tegenstelling tot eerder werk dat vaste nesten veronderstelt, biedt dit artikel een algoritme om de nestpartitie direct uit data te identificeren. Het algoritme maakt gebruik van de specifieke structuur van het voorgestelde experimentontwerp om deducties te maken die onmogelijk zijn met willekeurige of kleine assortimenten.
Superieure Schattingsprestaties: Het voorgestelde ontwerp presteert consequent beter dan gerandomiseerde en heuristische ontwerpen (zoals "leave-one-out") in numerieke benchmarks. Het vermindert de schattingsfout (RMSE) aanzienlijk, met name in settings met beperkte data of mis-gespecificeerde modellen.
Reële Implementatie: De methodologie werd ingezet bij Dream11, een Indiaans fantasy sports platform, waarbij 70 miljoen gebruikers en 72 wedstrijdtypen betrokken waren. Het experiment identificeerde succesvol betekenisvolle nesten die de out-of-sample voorspelling verbeterden vergeleken met zowel MNL-modellen als NL-modellen met ex-ante (feature-gebaseerde) clustering.

4. Resultaten

Numerieke Benchmarks

Mis-gespecificeerde Settings: Wanneer de grondwaarheid een complexe distributie volgt (Ranked List) en diverse modellen (MNL, NL, Markov Chain) worden geschat, levert het voorgestelde ontwerp met $O(\log n)$ assortimenten consistent lagere RMSE op dan gerandomiseerde ontwerpen met hetzelfde aantal assortimenten. Het vermindert de fout met tot wel 5,5% in kleine data-regimes.
Goed-gespecificeerde Settings: Wanneer het geschatte model overeenkomt met de grondwaarheid (bijv. ware NL of Markov Chain), presteert het voorgestelde ontwerp beter dan gerandomiseerde ontwerpen, zelfs wanneer de gerandomiseerde ontwerpen aanzienlijk meer assortimenten gebruiken (tot $T$ verschillende assortimenten). In Markov Chain settings bereikte de reductie in RMSE 16,9%.
Nestidentificatie: De volledige pijplijn (ontwerp + identificatiealgoritme) vermindert de RMSE met tot wel 46% vergeleken met het gebruik van het nestidentificatiealgoritme van Benson et al. (2016) met hun oorspronkelijke ontwerp. De auteurs schrijven dit toe aan de hogere informatiewaarde van hun $O(n/2)$ -grootte assortimenten versus de grootte-2 of grootte-3 assortimenten van Benson et al.

Dream11 Implementatie

Voorspelling: Een Nested Logit-model met data-gedreven nesten (geïdentificeerd door het algoritme) presteerde beter dan een standaard MNL-model en een NL-model met nesten bepaald door $k$ -means clustering op wedstrijdkenmerken.
Interpreteerbaarheid: De geïdentificeerde nesten waren economisch interpreteerbaar. Zo groepeerde het algoritme wedstrijden met verschillende instapkosten en prijzenpotten maar identieke "Winner Ratios" en "Prize Ratios", wat suggereert dat gebruikers waarde waarnemen via genormaliseerde metrieken in plaats van ruwe attributen. Het groepeerde ook "winner-take-all" wedstrijden en identificeerde subtiele gedragspatronen met betrekking tot de salientie van het aantal winnaars.

5. Betekenis en Claims

Het artikel claimt dat de dataverzamelingstap (experimentontwerp) een eerste-orde determinant is van de prestaties van de keuzeschatting, potentieel zelfs impactvoller dan de keuze van het schattingsmodel zelf.

Paradigmaverschuiving: De auteurs stellen dat de literatuur het experimentontwerp grotendeels heeft genegeerd voor keuzeschatting, waarbij vaak wordt teruggevallen op gerandomiseerde of observationele data. Dit werk toont aan dat een doelbewuste, combinatorische arrangement van assortimenten aanzienlijk meer informatie over substitutiepatronen kan extraheren.
Efficiëntie vs. Complexiteit: Het ontwerp bereikt informatie-theoretische optimaliteit ( $O(\log n)$ ) terwijl het assortimenten van grootte $\approx n/2$ gebruikt, wat de informatie per observatie maximaliseert. Dit contrasteert met "leave-one-out" ontwerpen (die data-inefficiënt zijn door kleine effecten) of kleine paar-ontwerpen (die biased zijn of $O(n^2)$ experimenten vereisen).
Praktisch Nut: De succesvolle implementatie op een platform met 70 miljoen gebruikers toont aan dat het ontwerp schaalbaar en operationeel haalbaar is (het vereist slechts 14 verschillende assortimenten voor 72 items). De resulterende nesten boden actieven zakelijke inzichten die moeilijk te verkrijgen waren via feature-gebaseerde clustering alleen.

Het artikel concludeert dat hoewel de theoretische rechtvaardiging specif kind aan Nested Logit, het empirische succes zich uitstrekt naar algemene keuzemodellen, wat suggereert dat gestructureerde experimentatie een superieure strategie is voor het leren van keuzesubstitutiepatronen vergeleken met randomisatie.