How to Use Prices for Efficient Online Matching

1. 問題設定 (Problem)

本研究は、**「オンラインマッチング」**の文脈における特定の制約条件下での資源配分問題を扱います。

• 文脈: 虐待された子供を里親に割り当てる、救急患者を病室に割り当てる、ホームレスをシェルターに収容するなど、エージェント（需要側）が確率的かつ動的に到着し、到着時に即時にマッチングしなければならない（Greedy Allocation）状況。
• 制約条件:
  1. Greedy Allocation（貪欲な配分）: エージェントが到着した時点で、可能な限り最善のオブジェクト（供給側）に即座に割り当てなければならない。遅延や破棄は許されない。
  2. 粗い順序付けされた選好（Coarse, Ordinal Preferences）: エージェントの選好は数値的な効用ではなく、順序付け（Ordinal）であり、特に**無差別（Indifference）**を含む場合がある（例：2 つの里親家庭が同等に適切である）。
• 課題: 従来のオンラインマッチング理論では、貪欲な制約と順序付けされた選好（特に無差別を含む場合）を同時に満たし、かつパレート効率性（Pareto efficiency）や公平性を達成するメカニズムの存在は不可能であることが示されています（例 1 を参照）。特に、有限市場において「貪欲かつ順序効率的（Ordinal Efficient）」なメカニズムを設計することは不可能です。

2. 手法と提案メカニズム (Methodology & Proposed Mechanism)

著者は、**逐次均衡メカニズム（Sequential Equilibrium Mechanism: SEM）**という新しいランダム化オンラインマッチングメカニズムを提案しています。このメカニズムは、大規模市場の競争均衡の概念をオンライン設定に適用するものです。

• 基本アイデア:

  1. 偽市場（Pseudomarket）の活用: エージェントにトークン金（Fake money）を割り当て、競争均衡（Competitive Equilibrium）を解くことで、確率的な配分（ロトリー）を導出します。
  2. ランダム価格（Random Prices）: 価格ベクトルにランダムなノイズ（$\xi$）を加えることで、需要対応（Demand Correspondence）の連続性を確保し、均衡の存在を証明します。これにより、無差別が生じた際の「同点処理（Tie-breaking）」を確率的に処理します。
  3. 非対称な予算（Asymmetric Budgets）: 早期到着のエージェントに高い予算を割り当てることで、貪欲な制約（到着順に最善のものを優先する）を満たしつつ、将来の需要を価格に反映させます。

• SEM のアルゴリズムの概要:

  1. 各時点 $t$ において、現在の実現された到着と将来の期待到着分布に基づき、大規模市場の価格均衡 $p_t$ を計算します。
  2. 到着したエージェントに対して、その均衡に基づく確率的配分（ロトリー）を割り当てます。
  3. 各期間の終わりにロトリーを確定（Ex-post realization）させ、残存供給を更新して次の期間へ進みます。

• 理論的基盤:

  • 均衡の存在: Aumann 積分（対応上の積分）とカクタニの不動点定理を用いて、ランダム価格下での均衡存在を証明しています。
  • 効率性の条件: 「同点処理なし（No Tie-Breaking）」または「適切なランダム同点処理（Random Tie-Breaking）」の仮定の下で、均衡配分が順序効率的（Ordinal Efficient）であることを示しています。

3. 主要な貢献と理論的結果 (Key Contributions & Results)

SEM は以下の性質をほぼ確率 1（with probability one）で満たすことが証明されています。

1. 漸近的効率性（Asymptotic Efficiency）:
   • 市場規模（1 期間あたりの到着数 $n$）が無限大に発散する際、SEM の実現配分は順序効率的な配分に収束します。
   • 有限市場では不可能な「貪欲かつ順序効率的」な達成を、大規模市場の近似として実現します。
2. 貪欲性（Greediness）:
   • エージェントが到着した時点で、利用可能な最善のオブジェクトが含まれるロトリーを割り当てます。
3. 公平性（Fairness）:
   • 同タイプ・エントロピーフリー（Equal-type Envy-Free）: 同じ時期に到着したエージェント同士は互いのロトリーを羨ましく思いません。
4. 戦略的耐性（Strategyproofness）:
   • 市場規模が大きくなるにつれ、エージェントが嘘をついて利益を得るインセンティブは消失します（確率 1 で戦略的耐性を満たす）。

文献への貢献:

• 疑似市場（Pseudomarkets）: Hylland-Zeckhauser (1979) や Budish (2011) の研究を拡張し、無差別を含む順序付けされた選好とオンライン（動的）な到着を同時に扱えるようにしました。
• オンラインマッチング: 従来の競合比（Competitive Ratio）や機能的な効用最大化ではなく、**確率的支配（Stochastic Dominance）**に基づく福利厚生を最適化するアプローチを提示しました。
• 大規模市場分析: 大規模市場均衡が有限市場のオンライン制約下でどのように機能するかを理論的に解明しました。

4. 実証シミュレーションと結果 (Simulations & Results)

著者は、米国の非営利団体（The Firm）が運営する「子供と里親のマッチング」という実社会の問題をモデル化し、シミュレーションを行いました。

• 比較対象:
  • SEM: 提案メカニズム。
  • SD-RTB (Serial Dictatorship with Random Tie-Breaking): 現在のプロセスを簡略化したモデル（到着順にランダムに優先順位をつけ、選好リストからランダムに割り当てる）。
• 設定: 2 つの里親ホーム、2 種類の子供（選択的か否か）、4 期間。1 期間あたりの到着数 $n$ を 1, 5, 10, 25 と変化させます。
• 結果:
  • 配置率（Placement Rates）: SEM は SD-RTB に比べて、すべての市場規模で約10% 高い配置率を達成しました。
  • 市場規模の影響: $n=1$ の場合でも SEM は優位であり、$n$ が大きくなるにつれて両者の分散は減少しますが、SEM の優位性は維持されます。
  • 解釈: SEM は大規模市場均衡を利用することで、将来の到着を内部化し、限られたリソースをより効率的に配分できるため、小規模市場であっても SD-RTB のような近視眼的な割り当てよりも優れた結果をもたらします。

5. 意義と結論 (Significance & Conclusion)

• 実務的意義: 子供保護、医療、住宅支援など、即時のマッチングが求められる社会的な課題において、単なるランダム割り当てや直感的なルールよりも、理論的に裏付けられた価格メカニズムを用いることで、社会的福利を大幅に向上させる可能性があります。
• 理論的意義: 「貪欲性」と「順序効率性」の両立という長年の不可能性を、大規模市場の近似とランダム価格というアプローチによって克服しました。
• 今後の展望: 実社会でのフィールド実験（ラボ・イン・ザ・フィールド）の実施、および完全オンラインマッチング（供給側も確率的に到着する場合）への拡張が予定されています。

総じて、この論文は、オンライン環境における複雑な制約下での資源配分問題に対し、価格メカニズムと大規模市場均衡の概念を融合させることで、理論的に堅牢かつ実用的に優れた解決策を提示した画期的な研究です。