Experimental Design for Matching

Résumé Technique : Conception Expérimentale pour l'Appariement

Énoncé du Problème
Les mécanismes d'appariement constituent une infrastructure critique dans la gestion des opérations, s'étendant de l'éducation à la santé et aux plateformes numériques. Un défi fondamental surgit lorsque les praticiens cherchent à comparer empiriquement un nouvel algorithme d'appariement (traitement) par rapport à un statu quo (contrôle) sur une population finie. Les méthodes classiques d'inférence causale font face à un obstacle unique dans ce contexte : l'interférence d'appariement. Contraiment aux unités expérimentales indépendantes, l'assignation d'une unité à un appariement spécifique dans le plan de traitement peut empêcher son assignation dans le plan de contrôle en raison de contraintes de capacité et de compatibilité. Par conséquent, les contrefactuels au niveau individuel sont inobservables, et les décisions de randomisation sont couplées entre les unités. La littérature existante se concentre souvent sur l'atténuation du biais au sein d'un mécanisme d'appariement fixe ou suppose des modèles comportementaux spécifiques. Cet article comble la lacune concernant la comparaison expérimentale de deux plans d'appariement prédéterminés sans imposer de modèles de résultats ou de comportements, en s'appuyant uniquement sur une perspective basée sur la conception.

Méthodologie
Les auteurs proposent la Conception de Randomisation par Chemins Alternés (Conception AP), un cadre fondé sur la théorie des graphes et l'inférence basée sur la conception.

1. Ensemble de Désaccord et Décomposition :
   L'intuition structurelle centrale est la définition de l'ensemble de désaccord ($\Delta M_{(t,c)}$), comprenant les paires d'appariement présentes dans exactement l'un des deux plans (traitement ou contrôle). L'article prouve que pour les appariements un-à-un, cet ensemble admet une décomposition unique en chemins et cycles alternés disjoints. Dans ces structures, les arêtes alternent entre l'appariement de traitement ($M_t$) et l'appariement de contrôle ($M_c$). En raison des contraintes de capacité, des arêtes adjacentes dans un chemin ou un cycle alterné ne peuvent pas être réalisées simultanément.

2. Schéma de Randomisation :
   La Conception AP effectue une randomisation séquentielle le long de ces chemins et cycles.

   • Cas du Chemin : Pour un chemin ouvert, la première arête est sélectionnée avec une probabilité $p/(1+p)$. Les arêtes suivantes sont sélectionnées avec une probabilité conditionnelle $p$ si la précédente n'a pas été sélectionnée ; sinon, l'arête est déterministement ignorée (probabilité 0).
   • Cas du Cycle : Des règles séquentielles similaires s'appliquent, la dernière arête étant déterminée de manière déterministe en fonction de la réalisation de la première et de l'avant-dernière arêtes pour garantir la faisabilité.
   • Indépendance : La randomisation est effectuée indépendamment entre les différents chemins et cycles.

3. Estimation :
   Les auteurs utilisent l'estimateur de Horvitz-Thompson pour estimer l'Effet Moyen du Traitement (ATE). Ils établissent l'absence de biais de cet estimateur sous la conception AP.

4. Optimisation (Cadre Minimax) :
   Pour optimiser l'efficacité, les auteurs analysent la variance la plus défavorable de l'estimateur sous une hypothèse de résultat potentiel borné. Ils formulent un problème minimax pour trouver la probabilité de randomisation conditionnelle $p$ optimale.

   • Résultat Asymptotique : Pour les chemins et cycles longs, le $p$ optimal converge vers $\sqrt{2} - 1 \approx 0,4142$. Cette valeur est strictement inférieure à 0,5, reflétant un compromis où la réduction de la contribution de la variance de l'arête actuelle nécessite de prendre en compte l'interférence en aval.

5. Extension de Plusieurs-à-Un :
   Le cadre est étendu aux appariements de plusieurs-à-un (par exemple, l'affectation des étudiants aux écoles), où les contraintes de capacité compliquent la décomposition. Les auteurs construisent un graphe orienté auxiliaire déséquilibré pour représenter l'ensemble de désaccord. Ils réduisent le problème de la recherche d'une décomposition faisable à deux tâches de théorie des graphes :

   • La recherche de chemins augmentants dans un réseau de flux construit pour gérer les déséquilibres de degrés de nœuds.
   • La réalisation de décompositions de tours eulériens sur le graphe équilibré résiduel.
     Cela garantit que les chemins et cycles alternés résultants respectent les contraintes de capacité, permettant ainsi de transférer la conception AP et les garanties d'inférence.

Résultats Clés

• Absence de Biais : L'estimateur de Horvitz-Thompson sous la conception AP est sans biais pour l'ATE.
• Échelle de Variance : Contrairement aux conceptions naïves (qui sélectionnent l'intégralité de l'appariement de traitement ou de contrôle avec une probabilité de 0,5), où la variance ne disparaît pas lorsque la taille de la population $N \to \infty$, la variance de l'estimateur AP diminue à un taux de $O(1/N)$.
• Théorème Central Limite (TCL) : L'article établit un TCL en population finie pour l'estimateur. Ce résultat est non trivial car la décomposition de l'ensemble de désaccord peut présenter des motifs complexes, hétérogènes et potentiellement instables (mélanges de composantes courtes et longues) à mesure que la population croît. La preuve combine des arguments de Lindeberg-Feller avec des techniques de mélange-$\alpha$ et le théorème de Bolzano-Weierstrass.
• Bornes de Variance : Les auteurs dérivent une borne supérieure de variance estimable qui repose uniquement sur des quantités observables, permettant la construction d'intervalles de confiance asymptotiques.
• Validation Numérique : En utilisant un ensemble de données sur la main-d'œuvre (Revelio Labs), des expériences numériques confirment que la conception AP surpasse significativement la conception naïve en termes de réduction de la variance. La distribution empirique de l'estimateur s'aligne sur la distribution normale standard, validant le TCL. Le $p$ empiriquement optimal ($\approx 0,417$) correspond étroitement à l'optimum théorique du pire cas ($\sqrt{2}-1$).

Signification et Revendications
L'article affirme fournir un cadre basé sur la conception et sans hypothèse pour tester les mécanismes d'appariement. Sa signification réside dans :

1. Traitement de l'Interférence d'Appariement : Il offre une solution fondée sur les principes au problème spécifique d'interférence inhérent aux marchés d'appariement, où les unités ne sont pas indépendantes.
2. Innovation Structurelle : La décomposition unique de l'ensemble de désaccord en chemins et cycles alternés fournit une base structurelle rigoureuse pour gérer l'interférence.
3. Inférence Robuste : En établissant un TCL qui prend en compte des structures de composantes instables et hétérogènes, ce travail permet une inférence asymptotique valide dans des environnements d'appariement complexes sans nécessiter de modèles de résultats.
4. Applicabilité Pratique : L'extension aux appariements de plusieurs-à-un via des outils de la théorie des graphes (chemins augmentants et tours eulériens) rend la méthodologie applicable à des scénarios réels avec des contraintes de capacité, tels que l'échange d'organes ou le choix scolaire.

Les auteurs positionnent ce travail comme une perspective complémentaire à la modélisation structurelle, offrant un terrain de test empirique direct pour les nouveaux algorithmes d'appariement par rapport aux statu quo dans la gestion des opérations et la conception de plateformes.