Experimental Design for Matching

技術要約：マッチングのための実験設計

問題提起
マッチング・メカニズムは、教育、ヘルスケア、デジタル・プラットフォームにわたるオペレーションズ・マネジメントにおける重要なインフラである。実務家が、有限の集団に対して新しいマッチング・アルゴリズム（処置）を現状（対照）と比較しようとする際、根本的な課題が生じる。それは、**マッチング干渉（matching interference）**である。独立した実験単位とは異なり、あるユニットを特定の処置プランのペアに割り当てると、容量および適合性の制約により、そのユニットを対照プランに割り当てることが不可能になる場合がある。その結果、個別のレベルでの反事実（counterfactual）は観測不可能となり、ランダム化の決定はユニット間で結合される。既存の文献は、固定されたマッチング・メカニズム内でのバイアスの軽減に焦点を当てるか、あるいは特定の行動モデルを仮定することが多い。本論文は、成果や行動のモデルを課すことなく、デザインベースの視点のみに基づき、二つの既定のマッチング・プランを実験的に比較する方法という空白を埋めるものである。

手法
著者らは、グラフ理論とデザインベースの推論に基づいたフレームワークである**交互パス・ランダム化デザイン（AP Design）**を提案する。

1. 不一致集合と分解：
   核心となる構造的洞察は、二つのプラン（処置または対照）のいずれか一方にのみ存在するマッチング・ペアからなる不一致集合（disagreement set） ($\Delta M_{(t,c)}$) の定義である。本論文では、一対一のマッチングにおいて、この集合が互いに素な交互パス（alternating paths）とサイクル（cycles）へと一意に分解されることを証明している。これらの構造において、エッジは処置のマッチング ($M_t$) と対照のマッチング ($M_c$) を交互に辿る。容量制約のため、交互パスまたはサイクル内の隣接するエッジを同時に実現することはできない。

2. ランダム化スキーム：
   APデザインは、これらのパスおよびサイクルに沿って逐次的なランダム化を行う。

   • パスの場合： 開いたパス（open path）については、最初のエッジが確率 $p/(1+p)$ で選択される。後続のエッジは、前方のエッジが選択されなかった場合に条件付き確率 $p$ で選択され、前方のエッジが選択された場合には、そのエッジは決定論的にスキップ（確率0）される。
   • サイクルの場合： 同様の逐次的ルールが適用される。最終的なエッジは、実現可能性を確保するために、最初のエッジと最後から二番目のエッジの実現状況に基づいて決定論的に決まる。
   • 独立性： ランダム化は、異なるパスおよびサイクル間で独立して行われる。

3. 推定：
   著者らは、平均処置効果（ATE）を推定するために**ホーブ・トンプソン推定量（Horvitz-Thompson estimator）**を利用する。彼らは、APデザインの下でこの推定量の不偏性を確立している。

4. 最適化（ミニマックス・フレームワーク）：
   効率性を最適化するために、著者らは有界な潜在的結果の仮定の下で、推定量の最悪ケースの分散を分析する。彼らは、最適な条件付きランダム化確率 $p$ を求めるためのミニマックス問題を定式化する。

   • 漸近的結果： 長いパスおよびサイクルにおいて、最適な $p$ は $\sqrt{2} - 1 \approx 0.4142$ に収束する。この値は0.5よりも厳密に小さく、これは現在のエッジの分散への寄与を減らすために、ダウンストリームの干渉を考慮する必要があるというトレードオフを反映している。

5. 多対一への拡張：
   本フレームワークは、容量制約によって分解が複雑になる多対一のマッチング（例：学生と学校の割り当て）へと拡張される。著者らは、不一致集合を表現するために、**補助的な不均衡有向グラフ（auxiliary unbalanced directed graph）を構築する。彼らは、不均衡なノード次数を処理するための構築されたフローネットワークにおける増大パス（augmenting paths）の探索と、残余の均衡グラフに対するオイラー・ツアー分解（Euler-tour decompositions）**という二つのグラフ理論的タスクに、実現可能な分解を見出す問題を還元する。これにより、生成される交互パスおよびサイクルが容量制約を満たすことが保証され、APデザインと推論の保証が継承される。

主な結果

• 不偏性： APデザインの下でのホーブ・トンプソン推定量は、ATEに対して不偏である。
• 分散のスケーリング： 素朴なデザイン（全処置または全対照のマッチングを確率0.5で選択するもの）では、集団サイズ $N \to \infty$ としても分散が消失しないが、AP推定量の分散は $O(1/N)$ の速度で減少する。
• 中心極限定理 (CLT)： 著者らは、推定量の有限集団における中心極限定理を確立している。この結果は非自明である。なぜなら、不一致集合の分解は、集団が増大するにつれて、複雑で不均一かつ、潜在的に不安定なパターン（短・長成分の混合）を示す可能性があるからである。証明には、リンデベルグ・フェラーの議論と $\alpha$-ミキシングの手法、およびボルツァーノ・ワイエルシュトラスの定理を組み合わせている。
• 分散境界： 著者らは、観測可能な量のみに依存する推定可能な分散の上限を導出し、これにより漸近的な信頼区間の構築を可能にしている。
• 数値的検証： 労働力データセット（Revelio Labs）を用いた数値実験により、APデザインが素朴なデザインと比較して分散減少の面で大幅に優れていることが確認された。推定量の経験的分布は標準正規分布と一致しており、CLTが妥当であることを示している。経験的に得られた最適な $p$ ($\approx 0.417$) は、理論的な最悪ケースの最適値 ($\sqrt{2}-1$) と密接に一致している。

意義および主張
本論文は、マッチング・メカニズムをテストするためのデザインベースの、仮定のないフレームワークを提供すると主張している。その意義は以下の点にある：

1. マッチング干渉への対処： ユニットが独立していないという、マッチング市場に固有の特定の干渉問題に対する、原理的な解決策を提供する。
2. 構造的革新： 不一致集合を交互パスとサイクルへと一意に分解することで、干渉を管理するための厳密な構造的基礎を提供する。
3. ロバストな推論： 不安定で不均一な成分構造をも許容するCLTを確立することで、成果モデルを必要とせずに、複雑なマッチング環境における有効な漸近的推論を可能にする。
4. 実用的な適用可能性： 増大パスやオイラー・ツアーといったグラフ理論的ツールを用いた多対一マッチングへの拡張により、臓器交換や学校選択といった、容量制約を伴う現実世界のシナリオへの適用を可能にしている。

著者らは、本研究を構造モデルに対する補完的な視点として位置づけており、オペレーションズ・マネジメントやプラットフォーム・デザインにおける新しいマッチング・アルゴリズムを、現状と比較するための直接的な経験的テストの場を提供している。