Note on the size of a stable matching

技術的要約：安定マッチングのサイズに関する注記

問題提起
本論文は、一対一の二部マッチング市場（労働者と単一のポジションを持つ企業）における、安定マッチングのサイズと、最大個別の合理性（最大）マッチングのサイズとの関係を調査している。ゲール＝シャプレー・フレームワークは安定マッチングの存在を保証するが、これらのマッチングが雇用される労働者数や埋められるポジション数を最大化することを保証するわけではない。著者らは以下の問いに取り組んでいる：最大個別の合理的なマッチングが $n$ 組のペアを含む市場において、あらゆる安定マッチングに含まれるペアの数の下限はいくらであるか。さらに、彼らは安定マッチングを最大値に対して可能な限り小さくさせる特定の選好構造を特徴付け、安定なペアと最大のマッチングにおけるペアの重複を分析している。

手法
著者らは、無向グラフおよび有向グラフの両方の定式化を利用して、マッチング市場をグラフ理論的にモデル化している。

1. 無向グラフ定式化： 市場は、エッジが許容されるペアを表す二部グラフ $G = (W, F; E)$ としてモデル化される。著者らは、極大マッチングおよび最大マッチングの性質を利用して境界を確立している。
2. 有向グラフ（有向グラフ）定式化： 選好構造を特徴付けるために、著者らは Maffray (1992) が提案したマッチング有向グラフ定式化を採用している。この有向グラフ $D = (V, A)$ において、頂点は許容されるペア $(w, f)$ を表し、弧は選好順位（例：$(w, f)$ から $(w, f')$ への弧は、労働者 $w$ が $f$ よりも $f'$ を好むことを示す）を表す。
3. 魅力的な代替案の反復削除 (IDUA)： 著者らは、市場を「標準形」に縮小するために IDUA 手順 (Balinski and Ratier, 1997; Gutin et al., 2023) を用いている。このプロセスは、参加者が自身の最も好むパートナーが未マッチングである一方で、より好みの低いパートナーとマッチングしている場合に、そのペアを（安定なマッチングには含まれ得ないものとして）反復的に削除するプロセスである。
4. 構成的特徴付け： 著者らは、ベースとなる市場に最大安定マッチングを拡張し、既存の安定な参加者にとって「魅力的でない」ように構造化された選好を持つ新しい参加者を加えることで、特定の市場クラス ($G_n$ および $F_n$) を定義している。

主要な貢献と結果

• 定理 1 (サイズ境界): 主要な結果は、最大の個別合理的マッチングのサイズが $n$ であるあらゆる市場において、すべての安定マッチングのサイズは少なくとも $\lceil n/2 \rceil$ であることを確立している。

  • 証明の論理： 証明は、(i) 安定マッチングは極大マッチングである（両者が未マッチングであるような許容されるペアは存在しない）、および (ii) グラフにおけるあらゆる極大マッチングは、最大マッチングのサイズの少なくとも半分である、という2つの事実に依拠している。
  • 含意： 最大のマッチングが個別的に合理的である限り、均衡雇用率は最大達成可能雇用の50%を下回ることはない。

• 定理 2 (極端な選好の特性付け): 本論文は、この下限に達する選好プロファイルのクラス ($F_n$) を特徴付けている。

  • 市場がサイズ $\lceil n/2 \rceil$（安定サイズ = $\lceil n/2 \rceil$、最大サイズ = $n$）となるのは、その市場がクラス $F_n$ に属する場合、かつその場合に限られる。
  • 構造的特性： これらの市場では、どの安定マッチングにも現れない参加者（均衡における「未マッチング」の者）は、互いに「受け入れがたい（unacceptable）」と感じている必要がある。もし彼らが互いに受け入れ可能であれば、彼らはブロッキング・ペアを形成し、安定マッチングのサイズを増加させてしまうためである。
  • トップでの一致： これらの市場の自然なサブクラスは、「トップでの一致（agreement at the top）」を示しており、そこでは参加者は、自身の最も好む安定なパートナーよりも、すべての新しい非安定な参加者を低くランク付けしている。

• 定理 3 (重複と犠牲): 著者らは、安定マッチングにおけるペアの集合 ($\mu^*$) と最大マッチング ($\mu$) の間の交差を分析している。

  • $r$ を共通のペアの数とする。定理は、$|\mu^*| \geq (|\mu| + r) / 2$ であることを述べている。
  • 含意： 安定マッチングが最小化されるとき（すなわち、$|\mu^*| = \lceil |\mu|/2 \rceil$ のとき）、重複 $r$ はゼロでなければならない。これは、市場が安定マッチングを可能な限り小さくするように構造化されている場合、安定マッチングに含まれるペアの中に、最大マッチングに含まれるものは一つも存在しないことを意味する。
  • 安定性のコスト： 雇用を最大化すること（すべての空席を埋めること）は、より小さな安定な構成に存在するであろうすべての均衡ペアを「犠牲」にすることを要求する場合がある。

意義と範囲
本論文は、その分析を「安定性のコスト」の探求として位置づけている。著者らは、安定性と効率性（マッチングのサイズによって測定される）の間のトレードオフを定量化している。著者らは、安定性はブロッキング・ペアがないことを保証する一方で、特に定理 2 で特定された選好構造を持つ市場においては、理論上の最大値と比較して、雇用される労働者数を大幅に減少させる可能性があると指摘している。

著者らは、自らの結果の範囲を一対一の二部マッチング市場に明示的に限定している。彼らは、本フレームワークが広く適用可能（例：学生と大学、医師と病院）であることを認めつつも、ここで導出された特定の境界や特性付けが、より複雑な環境（多対一のマッチング、カップルを含む市場、または一側的な「ルームメイト」問題など）に自動的に拡張されるものではないことを認めている。本論文は、新しいアルゴリズムや実験的な応用を提案するのではなく、安定均衡における雇用率のワーストケース・シナリオに対する理論的な境界と構造的な特性付けを提供している。