Experimental Design for Matching

Technische Samenvatting: Experimenteel Ontwerp voor Matching

Probleemstelling
Matching-mechanismen vormen een cruciale infrastructuur binnen operations management, variërend van onderwijs en gezondheidszorg tot digitale platforms. Een fundamentele uitdaging ontstaat wanneer praktijkbeoefenaars een nieuw matching-algoritme (behandeling) empirisch willen vergelijken met een status quo (controle) op een eindige populatie. Standaard causale inferentiemethoden worden in deze setting geconfronteerd met een uniek obstakel: matching-interferentie. In tegenstelling tot onafhankelijke experimentele eenheden, kan de toewijzing van een eenheid aan een specifieke match in het behandelplan de toewijzing ervan in het controleplan verhinderen vanwege capaciteits- en compatibiliteitsbeperkingen. Gevolgelijk zijn individuele-niveau contrafactuele scenario's niet observeerbaar, en zijn randomisatiebeslissingen gekoppeld over verschillende eenheden. De bestaande literatuur richt zich vaak op het mitigeren van bias binnen een vaste matching-mechanisme of gaat uit van specifieke gedragsmodellen. Dit artikel adresseert de kloof in hoe men twee vooraf bepaalde matching-plannen experimenteel kan vergelijken zonder uitkomst- of gedragsmodellen op te leggen, waarbij uitsluitend wordt vertrouwd op een design-gebaseerd perspectief.

Methodologie
De auteurs stellen het Alternating Path Randomized Design (AP Design) voor, een raamwerk geworteld in de grafentheorie en design-gebaseerde inferentie.

1. Disagreement Set en Decompositie:
   Het kerninzicht in de structuur is de definitie van de disagreement set ($\Delta M_{(t,c)}$), die bestaat uit match-paren die in precies één van de twee plannen (behandeling of controle) aanwezig zijn. Het artikel bewijst dat deze set voor één-op-één matchings een unieke decompositie bezit in disjuncte alternerende paden en cycli. In deze structuren wisselen de randen (edges) af tussen de behandeling-matching ($M_t$) en de controle-matching ($M_c$). Vanwege capaciteitsbeperkingen kunnen aangrenzende randen in een alternerend pad of een cyclus niet gelijktijdig gerealiseerd worden.

2. Randomisatieschema:
   Het AP Design voert sequentiële randomisatie uit langs deze paden en cycli.

   • Padgeval: Voor een open pad wordt de eerste rand geselecteerd met kans $p/(1+p)$. Opvolgende randen worden geselecteerd met een conditionele kans $p$ als de voorganger niet is geselecteerd; anders wordt de rand deterministisch overgeslagen (kans 0).
   • Cyclengeval: Vergelijkbare sequentiële regels zijn van toepassing, waarbij de laatste rand deterministisch wordt bepaald op basis van de realisatie van de eerste en de voorlaatste rand om haalbaarheid te garanderen.
   • Onafhankelijkheid: Randomisatie wordt onafhankelijk uitgevoerd over verschillende paden en cycli.

3. Schatting:
   De auteurs maken gebruik van de Horvitz-Thompson-schatter om het gemiddelde behandel-effect (Average Treatment Effect, ATE) te schatten. Zij stellen vast dat deze schatter onbevangen is onder het AP-design.

4. Optimalisatie (Minimax-raamwerk):
   Om de efficiëntie te optimaliseren, analyseren de auteurs de worst-case variantie van de schatter onder een aanname van een begrensde potentiële uitkomst. Zij formuleren een minimax-probleem om de optimale conditionele randomisatiekans $p$ te vinden.

   • Asymptotisch resultaat: Voor lange paden en cycli convergeert de optimale $p$ naar $\sqrt{2} - 1 \approx 0,4142$. Deze waarde is strikt kleiner dan 0,5, wat een afweging reflecteert waarbij het verminderen van de variantiebijdrage van de huidige rand rekening moet houden met de stroomafwaartse interferentie.

5. Many-to-One Extensie:
   Het raamwerk wordt uitgebreid naar many-to-one matchings (bijv. student-school toewijzingen), waarbij capaciteitsbeperkingen de decompositie bemoeilijken. De auteurs construeren een auxiliaire ongebalanceerde gerichte graaf om de disagreement set te representeren. Zij reduceren het probleem van het vinden van een haalbare decompositie tot twee grafentheoretische taken:

   • Het vinden van augmenterende paden in een geconstrueerd flow-netwerk om de onbalans in knoopgraden te behandelen.
   • Het uitvoeren van Euler-tour decomposities op de resterende gebalanceerde graaf.
     Dit zorgt ervoor dat de resulterende alternerende paden en cycli aan de capaciteitsbeperkingen voldoen, waardoor het AP-design en de inferentiegaranties kunnen worden overgenomen.

Belangrijkste Resultaten

• Onbevangenheid: De Horvitz-Thompson-schatter onder het AP-design is onbevangen voor de ATE.
• Variantie-schaalbaarheid: In tegenstelling tot naïeve designs (waarbij de gehele behandeling- of controle-matching met kans 0,5 wordt geselecteerd), waarbij de variantie niet verdwijnt naarmate de populatiegrootte $N \to \infty$, neemt de variantie van de AP-schatter af met een snelheid van $O(1/N)$.
• Centrale Limietstelling (CLT): Het artikel stelt een finite-population CLT vast voor de schatter. Dit resultaat is niet triviaal omdat de decompositie van de disagreement set complexe, heterogene en potentieel instabiele patronen (mengsels van korte en lange componenten) kan vertonen naarmate de populatie groeit. Het bewijs combineert Lindeberg-Feller argumenten met $\alpha$-mixing technieken en de Bolzano-Weierstrass stelling.
• Variantiegrenzen: De auteurs leiden een schatbare bovengrens voor de variantie af die enkel steunt op observeerbare grootheden, wat de constructie van asymptotische betrouwbaarheidsintervallen mogelijk maakt.
• Numerieke Validatie: Met behulp van een workforce-dataset (Revelio Labs) bevestigen numerieke experimenten dat het AP-design de naïeve design aanzienlijk overtreft in termen van variantiereductie. De empirische distributie van de schatter komt overeen met de standaard normale verdeling, wat de CLT valideert. De empirisch optimale $p$ ($\approx 0,417$) komt nauw overeen met het theoretische worst-case optimum ($\sqrt{2}-1$).

Betekenis en Claims
Het artikel claimt een design-gebaseerd, aannamevrij raamwerk te bieden voor het testen van matching-mechanismen. De significantie ligt in:

1. Adresseren van Matching-interferentie: Het biedt een principieel oplossing voor het specifieke probleem van interferentie in matching-markten, waar eenheden niet onafhankelijk zijn.
2. Structurele Innovatie: De unieke decompositie van de disagreement set in alternerende paden en cycli biedt een rigoureuze structurele basis voor het beheren van interferentie.
3. Robuuste Inferentie: Door een CLT vast te stellen die rekening houdt met instabiele en heterogene componentstructuren, maakt het werk geldige asymptotische inferentie mogelijk in complexe matching-omgevingen zonder dat er uitkomstmodellen vereist zijn.
4. Praktische Toepasbaarheid: De uitbreiding naar many-to-one matchings via grafentheoretische instrumenten (augmenterende paden en Euler-tours) maakt de methodologie toepasbaar op real-world scenario's met capaciteitsbeperkingen, zoals orgaantransplantatie en schoolkeuze.

De auteurs positioneren dit werk als een complementair perspectief op structurele modellering, wat een directe empirische testgrond biedt voor nieuwe matching-algoritmen tegenover de status quo in operations management en platformdesign.