The Domain of RSD Characterization by Efficiency, Symmetry, and Strategy-Proofness

技術的要約：効率性、対称性、および戦略的真実性によるRSDの領域特性

問題提起
本論文は、個別の対象をエージェントに割り当てる文脈における、ランダム・シリアル・ディクテーターシップ（RSD）メカニズムの公理的特性化を取り扱う。RSDは、エージェントのランダムな順序を決定し、各エージェントがその時点で最も好む利用可能な対象を順次選択することで機能する。RSDは、事後効率性（ExPE）、等しい者への等しい扱い（ETE）、および戦略的真実性（SP）という3つの核心的な公理を満たすため、学校選択や住宅割り当てなどのアプリケーションで広く用いられているが、これらの公理がすべての市場規模 $(n, m)$ においてRSDを一意に決定するかどうかは未解決の問いであった。

先行研究では、均衡ケースである $n=m=3$ において、これらの公理がRSDを一意に特定することが確立されている（Bogomolnaia and Moulin [8]）。しかし、より大きな市場においては、この問題は未解決のままであった。Basteck and Ehlers [5] による最近の研究は、$n, m \ge 5$ であるすべての市場において、これらの公理はRSDを一意に決定するには不十分であることを示した。なぜなら、代替となるメカニズムが存在するためである。本研究の中心的な課題は、公理がRSDを一意に決定する $(n, m)$ のペアを完全に分類し、非一意性が発生する特定の領域を特定することである。

手法
著者らは、正の特性化証明と構成的な反例の両方を用いる厳密な公理的アプローチを採用している。

1. 一意性証明のための公理の弱体化： 特定の市場規模における一意性を証明するにあたり、著者らは、ExPEとSPの完全な強度は必要ではないことを示している。代わりに、以下の概念に依拠している：

   • サポート効率性（Support Efficiency）： エージェントがある対象を正の確率で受け取るのは、その対象があるパレート効率的な決定論的割り当てにおいてそのエージェントに割り当てられる場合のみである。
   • 完全割り当て特性（Full Assignment Property）： もしあるエージェント（または対象）がすべてのシリアル・ディクテーターシップ（SD）の結果においてマッチングされるならば、それは確率1でマッチングされなければならない。
   • 上下不変性（Upper and Lower Invariance）： これらは、選好における隣接する入れ替えに関するSPと同等の局所的な条件であり、エージェントがランキング内の2つの隣接する項目を入れ替えた際に、他の対象の確率が変化しないことを保証する。

2. 局所分析と帰納法： 一意性が成立するケースにおいて、証明は公理の「局所分析」を利用する。エージェントのランキングにおける隣接する入れ替えを検討することで、著者らは異なる選好プロファイルにわたって制約を伝播させる。主要な補題（Lemma 2.4）は、エージェントが「準一致（near-unanimity）」（すべてのエージェントが、すべてのオブジェクトのペアに対する二値選好において、最大でも1人を除いて一致している状態）を示す場合、割り当て行列が一意に決定されることを確立している。これは、プロファイルの「不一致パラメータ」に関する帰納的議論の基礎となる。

3. 構成的な反例： 一意性が成立しない領域では、著者らは明示的な代替メカニズムを構築する。これらの構築は、概して以下の戦略に従う（Basteck and Ehlers [5] に着想を得たもの）：

   • ベースとなるメカニズム（多くの場合、特定のSD順序またはRSD自体）から開始する。
   • 特定の選好プロファイルの限定的な集合を特定し、そこでExPEまたはSPを損なうことなく特定の調整が可能であることを確認する。
   • 特定のエージェントに対する効率的な割り当ての間で、微小な確率の移動（$\epsilon$ の質量転送）を行う。
   • エージェント（および時には対象）のすべての入れ替えに対して調整されたメカニズムを対称化し、これによりETE（および多くの場合、匿名性と中立性）が保持されるようにする。

4. $m=2$ のためのパラメータ化： 対象が2つの場合の特定のケースについて、著者らは、公理を満たすすべてのメカニズムを完全にパラメータ化し、それらがエージェントの部分集合から確率への特定のクラスの関数に対応することを示している。

主な貢献と結果
本論文は、RSDの一意性に関する $(n, m)$ の完全な分類を提供している：

• 一意性の領域： 公理 ExPE, ETE, SP は、以下の場合に限り、RSDを一意に特性化する：

  • $n \le 3$ かつ $m \ge 2$ （均衡ケース $n=m=3$ を含む）。
  • $n = 4$ かつ $m = 4$ （4人のエージェントによる均衡ケース）。
  • $n = 2$ かつ $m > 2$。
  • 特筆すべきは、$n=4$ の場合、一意性は $m=4$ のときにのみ保持されることである。もし $n=4$ かつ $m \ge 5$ であれば、一意性は失われる。

• 非一意性の領域： $n, m \ge 2$ であるその他のすべてのペア $(n, m)$ について、公理はRSDを一意に決定しない。具体的には：

  • $n > m \ge 3$ の場合、代替メカニズムが存在する。
  • $n = 4, m \ge 5$ の場合、代替メカニズムが存在する。
  • $n, m \ge 5$ の場合、結果は Basteck and Ehlers [5] の否定的な知見を裏付けている。

• $m=2$ のパラメータ化： 本論文は、2つの対象に対するメカニズムの空間を完全に特性化しており、$n \ge 4$ の場合は公理を満たすメカニズムの連続体が存在する一方で、$n=2, 3$ ではメカニズムが一意であることを示している。

• 強化された公理： 著者らは、より強い公理を追加することで、非一意な領域において一意性を回復できるかどうかを調査した。彼らは以下をテストした：

  • 有界不変性（Bounded Invariance, BI）： BI（および匿名性と中立性）を追加しても、$n \ge m-1 \ge 5$ において一意性は回復しないことを示している。
  • 非ボス性（Non-Bossiness, NB）および交差単調性（Cross Monotonicity, CM）： これらの公理を（匿名性、中立性、ExPE、SP、BIと共に）システムに加えても、十分に大きな市場（$n \ge m-1 \ge 7$）において一意性を回復させることはできない。

• 厚生優越性（Welfare Dominance）： 非一意な領域において、構築された代替メカニズムはしばしばRSDを**圧倒（dominate）**する。すなわち、それらはRSDと比較してすべてのエージェントの割り当てを弱く改善し、特定のプロファイルにおいて少なくとも一つのエージェントの割り当てを厳密に改善する。

意義
本論文は、RSDの公理的特性化に関する長年の未解決問題を解決し、RSDの図を完成させた。また、$n=m=4$ がなぜ解析的に解決するのが特に困難であったのか（$n=3$ や $n \ge 5$ とは異なり、一意性が保持される唯一の均衡ケースであるため）を明らかにしている。さらに、標準的な性質である有界不変性、非ボス性、および交差単調性を用いて公理系を強化しても、大きな市場における一意性の回復には失敗することを示すことで、本論文は、これらのみを通じてRSDを特性化することの根本的な限界を浮き彫りにしている。また、RSDが一意ではない領域において、それが必ずしも厚生的に最適であるとは限らず、同じ公理を満たす他のメカニズムによって優越され得ることも確立している。