Experimental Design for Matching

Technisches Resümee: Experimentelles Design für Matching-Verfahren

Problemstellung
Matching-Mechanismen sind kritische Infrastrukturen im Operations Management, die Bereiche wie Bildung, Gesundheitswesen und digitale Plattformen umspannen. Eine grundlegende Herausforderung entsteht, wenn Praktiker einen neuen Matching-Algorithmus (Behandlung) gegen einen Status Quo (Kontrolle) auf einer endlichen Population empirisch vergleichen wollen. Standardmethoden der kausalen Inferenz stehen in diesem Setting vor einem einzigartigen Hindernis: der Matching-Interferenz. Im Gegensatz zu unabhängigen experimentellen Einheiten kann die Zuweisung einer Einheit zu einem bestimmten Match im Behandlungsplan die Zuweisung zu einem Kontrollplan ausschließen, da Kapazitäts- und Kompatibilitätsbeschränkungen bestehen. Folglich sind individuelle Gegenfaktuale nicht beobachtbar, und die Randomisierungsentscheidungen sind über die Einheiten hinweg gekoppelt. Die bestehende Literatur konzentriert sich oft darauf, Bias innerhalb eines festen Matching-Mechanismus zu mildern oder setzt spezifische Verhaltensmodelle voraus. Diese Arbeit adressiert die Lücke bei der Frage, wie zwei vordefinierte Matching-Pläne experimentell zu vergleichen sind, ohne Outcome- oder Verhaltensmodelle aufzuerlegen, und stützt sich dabei rein auf eine designbasierte Perspektive.

Methodik
Die Autoren schlagen das Alternating Path Randomized Design (AP Design) vor, ein Framework, das auf Graphentheorie und designbasierter Inferenz basiert.

1. Disagreement Set und Zerlegung:
   Die zentrale strukturelle Erkenntnis ist die Definition des Disagreement Sets ($\Delta M_{(t,c)}$), der jene Match-Paare umfasst, die in genau einem der beiden Pläne (Behandlung oder Kontrolle) vorhanden sind. Das Paper beweist, dass dieser Satz für Eins-zu-eins-Matchings eine eindeutige Zerlegung in disjunkte alternierende Pfade und Zyklen zulägt. In diesen Strukturen alternieren die Kanten zwischen dem Behandlungs-Matching ($M_t$) und dem Kontroll-Matching ($M_c$). Aufgrund von Kapazitätsbeschränkungen können benachbarte Kanten in einem alternierenden Pfad oder Zyklus nicht gleichzeitig realisiert werden.

2. Randomisierungsschema:
   Das AP Design führt eine sequentielle Randomisierung entlang dieser Pfade und Zyklen durch.

   • Pfad-Fall: Für einen offenen Pfad wird die erste Kante mit der Wahrscheinlichkeit $p/(1+p)$ ausgewählt. Nachfolgende Kanten werden mit der bedingten Wahrscheinlichkeit $p$ ausgewählt, falls der Vorgänger nicht ausgewählt wurde; andernfalls wird die Kante deterministisch übersprungen (Wahrscheinlichkeit 0).
   • Zyklus-Fall: Ähnliche sequentielle Regeln gelten hier, wobei die letzte Kante deterministisch basierend auf der Realisierung der ersten und vorletzten Kante festgelegt wird, um die Durchführbarkeit zu gewährleisten.
   • Unabhängigkeit: Die Randomisierung erfolgt unabhängig über verschiedene Pfade und Zyklen hinweg.

3. Schätzung:
   Die Autoren verwenden den Horvitz-Thompson-Schätzer, um den durchschnittlichen Behandlungseffekt (Average Treatment Effect, ATE) zu schätzen. Sie weisen die Unverzerrtheit dieses Schätzers unter dem AP Design nach.

4. Optimierung (Minimax-Framework):
   Um die Effizienz zu optimieren, analysieren die Autoren die Worst-Case-Varianz des Schätzers unter einer beschränkten Annahme potenzieller Outcomes. Sie formulieren ein Minimax-Problem, um die optimale bedingte Randomisierungswahrscheinlichkeit $p$ zu finden.

   • Asymptotisches Ergebnis: Für lange Pfade und Zyklen konvergiert das optimale $p$ gegen $\sqrt{2} - 1 \approx 0,4142$. Dieser Wert liegt strikt unter 0,5, was einen Trade-off widerspiegelt, bei dem die Reduzierung des Varianzbeitrags der aktuellen Kante die Berücksichtigung der nachfolgenden Interferenz erfordert.

5. Erweiterung auf Viele-zu-eins-Matching:
   Das Framework wird auf Viele-zu-eins-Matchings (z. B. die Zuweisung von Schülern zu Schulen) erweitert, bei denen Kapazitätsbeschränkungen die Zerlegung erschweren. Die Autoren konstruieren einen hilfsweisen, unbalancierten gerichteten Graphen, um das Disagreement Set darzustellen. Sie reduzieren das Problem der Suche nach einer durchführbaren Zerlegung auf zwei graphentheoretische Aufgaben:

   • Das Finden von Augmentierungspfaden in einem konstruierten Flussnetzwerk, um Ungleichgewichte in den Knotengraden zu handhaben.
   • Durchführung von Euler-Tour-Zerlegungen auf dem verbleibenden balancierten Graphen.
     Dies stellt sicher, dass die resultierenden alternierenden Pfade und Zyklen die Kapazitätsbeschränkungen erfüllen, sodass das AP Design und die Inferenzgarantien übertragen werden können.

Wichtigste Ergebnisse

• Unverzerrtheit: Der Horvitz-Thompson-Schätzer unter dem AP Design ist ein unverzerrter Schätzer für den ATE.
• Varianzskalierung: Im Gegensatz zu naiven Designs (bei denen die gesamte Behandlungs- oder Kontroll-Matching mit einer Wahrscheinlichkeit von 0,5 ausgewählt wird), bei denen die Varianz nicht gegen Null geht, wenn die Populationsgröße $N \to \infty$, sinkt die Varianz des AP-Schätzers mit einer Rate von $O(1/N)$.
• Zentraler Grenzwertsatz (CLT): Das Paper etabliert einen Finite-Population-CLT für den Schätzer. Dieses Ergebnis ist nicht trivial, da die Zerlegung des Disagreement Sets komplexe, heterogene und potenziell instabile Muster (Mischungen aus kurzen und langen Komponenten) aufweisen kann, während die Population wächst. Der Beweis kombiniert Lindeberg-Feller-Argumente mit $\alpha$-Mixing-Techniken und dem Satz von Bolzano-Weierstraß.
• Varianzgrenzen: Die Autoren leiten eine schätzbare obere Grenze für die Varianz ab, die nur auf beobachtbaren Größen basiert, was die Konstruktion asymptotischer Konfidenzintervalle ermöglicht.
• Numerische Validierung: Unter Verwendung eines Workforce-Datensatzes (Revelio Labs) bestätigen numerische Experimente, dass das AP Design das naive Design in Bezug auf die Varianzreduktion signifikant übertrifft. Die empirische Verteilung des Schätzers stimmt mit der Standardnormalverteilung überein, was den CLT validiert. Das empirisch optimale $p$ ($\approx 0,417$) liegt nahe am theoretischen Worst-Case-Optimum ($\sqrt{2}-1$).

Bedeutung und Ansprüche
Das Paper beansprucht, ein designbasiertes, assumptionsfreies Framework für das Testen von Matching-Mechanismen bereitzustellen. Seine Bedeutung liegt in:

1. Adressierung der Matching-Interferenz: Es bietet eine fundierte Lösung für das spezifische Interferenzproblem in Matching-Märkten, in denen Einheiten nicht unabhängig sind.
2. Strukturelle Innovation: Die einzigartige Zerlegung des Disagreement Sets in alternierende Pfade und Zyklen liefert eine rigorose strukturelle Basis für das Management von Interferenz.
3. Robuste Inferenz: Durch die Etablierung eines CLT, das instabile und heterogene Komponentenstrukturen berücksichtigt, ermöglicht die Arbeit eine valide asymptotische Inferenz in komplexen Matching-Umgebungen, ohne dass Outcome-Modelle erforderlich sind.
4. Praktische Anwendbarkeit: Die Erweiterung auf Viele-zu-eins-Matchings mittels graphentheoretischer Werkzeuge (Augmentierungspfade und Euler-Touren) macht die Methodik anwendbar auf reale Szenarien mit Kapazitätsbeschränkungen, wie etwa Organaustausch oder Schulwahl.

Die Autoren positionieren diese Arbeit als komplementäre Perspektive zur strukturellen Modellierung und bieten damit ein direktes empirisches Testfeld für neue Matching-Algorithmen gegenüber dem Status Quo im Operations Management und im Plattformdesign.