📈 economics

The Distribution of Envy in Matching Markets

この論文は、確率的マッチング市場における遅延受諾法（DA）とランダム直列独裁（RSD）を比較し、両アルゴリズムにおいて誰も羨まれない提案者の期待数がともに調和数 $H_n$ に等しくなることを示す一方、その割合は市場規模に対して漸近的にゼロに収束することを明らかにしています。

原著者： Josué Ortega, Gabriel Ziegler, R. Pablo Arribillaga, Geng Zhao

公開日 2026-03-25

📖 1 分で読めます☕ さくっと読める

CC BY 4.0

原著者： Josué Ortega, Gabriel Ziegler, R. Pablo Arribillaga, Geng Zhao

原論文は CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) でライセンスされています。 ✨ これは以下の論文のAI生成解説です。著者が執筆または承認したものではありません。技術的な正確性については原論文を参照してください。免責事項の全文を読む

🎒 物語の舞台：学校と生徒の「運命のマッチング」

想像してください。1 万人の生徒がいて、同じく 1 万人の学校があります。
みんな「一番行きたい学校」から順に希望を出します。
ここで使われるのが、**「遅延受容（DA）」**という有名なルールです。
（これは、生徒が学校に申し込んで、学校が「保留」したり「却下」したりしながら、最終的に安定したペアを作る仕組みです。アメリカの公立学校や日本の大学入試などで使われている、非常に公平で有名なルールです。）

この論文は、このルールで決まった結果について、2 つの不思議な質問をしました。

「誰もに妬まれない生徒」は何人いる？
- 例：A さんが学校 X に入った。他の誰かが「A さんが入った学校 X に行けばよかった！」と悔しがっていない状態。
「誰かを妬まない生徒」は何人いる？
- 例：B さんが学校 Y に入った。B さんは「自分の学校 Y が一番好きだ！」と満足している状態（つまり、自分の希望通りに入れた人）。

🔍 発見その 1：「誰もに妬まれない人」は、驚くほど少ない！

【結論】
市場が大きくなればなるほど、「誰もに妬まれない人」の割合はゼロに近づいてしまいます。

【イメージ：お菓子当てゲーム】
この現象を理解するには、**「クッキーの箱」**を想像してください。
100 種類のクッキーが入った箱から、ランダムにクッキーを引いていきます。
「すべての種類のクッキーを 1 回ずつ引く」ためには、何回引く必要があるでしょうか？（これを「クーポンコレクター問題」と呼びます）

100 種類なら、引く回数は約 500 回くらい必要になります。
この論文は、**「たった 1 回だけ引かれたクッキー（＝誰もに妬まれない学校）」**が、最終的に何個残っているかを計算しました。

【結果】
1 万人の市場でも、「誰もに妬まれない人」は約 10 人しかいません！
（10,000 人中 10 人なので、0.1% 以下です）。
つまり、**「99.9% の人は、誰かが『あいつの学校に行けばよかった』と少しは悔しがっている」**という、少し寂しい（でも現実的な）結果が出ました。

🔍 発見その 2：「誰かを妬まない人」も少ないが、前者よりは多い

【結論】
「自分の希望通りに入れた人（誰かを妬まない人）」は、先ほどの「誰もに妬まれない人」よりは多いですが、それでも全体の小さな一部しかいません。

【イメージ：抽選の順番】
DA というルールでは、みんなが順番に学校を選びますが、人気校はすぐに埋まってしまいます。

1 万人の市場では、約 1,100 人くらいが「自分の 1 位希望」に入れる計算になります。
1,000 人なら約 130 人。
100 人なら約 19 人。

「誰もに妬まれない人（10 人）」よりは多いですが、**「1 万人の 1 割もいない」**というのが現実です。

⚖️ 驚きの比較：別のルール（RSD）でも同じ？

研究者たちは、**「ランダム・シリアル・ディクテーターシップ（RSD）」**という、もっと単純なルール（順番にクジを引いて、好きな学校を 1 個ずつ取るルール）と比較しました。

RSD の場合： 順番が良ければ、**約半分（50%）**の人が「1 位希望」に入れる！
- DA（約 11%）に比べると、RSD の方が「希望通り」に入れる人は圧倒的に多いです。
しかし、意外な事実：
- 「誰もに妬まれない人」の数は、DA でも RSD でも、全く同じ（約 10 人）でした！

【なぜ？】
これは不思議な一致です。

RSD は「希望通り」に入れる人が圧倒的に多いのに、
DA は「希望通り」に入れる人が少ないのに、
「誰もに妬まれない人（＝誰も文句を言わない人）」の数は、ルールに関係なく同じなのです。

これは、「市場の大きさ」や「ランダムさ」そのものが、この数を決定づけていることを示唆しています。どんなに良いルールを作っても、この「誰もに妬まれない人」の数は、市場が大きくなれば自然と消えていく運命にあるようです。

💡 この研究が教えてくれること（まとめ）

完全な満足は難しい：
どんなに公平なルール（DA）を使っても、「誰もに妬まれない人」や「誰かを妬まない人」は、市場が大きくなればなるほど、ごく少数しか現れません。 1 万人いれば、その 99% 以上は「誰かが悔しがっている」か「誰かを悔しがっている」状態になります。
改善の余地は限られている：
「誰もに妬まれない人」や「誰かを妬まない人」は、**「これ以上、誰とも交換して良くならない人（改善不可能な人）」です。この数が少ないということは、「DA の結果から、もっと良い状態に改善できる余地（パレート改善）が、実はかなり残っている」**ことを意味します。
ルールの違いより「市場の性質」：
「希望通りに入れる人」の数はルールで大きく変わりますが、「誰もに妬まれない人」の数は、どんなルールでも同じ傾向を示します。これは、「ランダムな市場」という環境そのものが持つ性質なのかもしれません。

一言で言うと：
「学校選びのような大きな市場では、『誰も文句を言わない完璧な結果』や『全員が最高に満足する結果』は、数学的にほぼ不可能です。でも、その『改善の余地』こそが、私たちがより良い仕組みを探し続ける理由なのです。」

📝 用語の補足（簡単版）

DA（遅延受容）： 学校と生徒が、お互いの希望をすり合わせながら、最終的に安定したペアを作る仕組み。
RSD（ランダム・シリアル・ディクテーターシップ）： ランダムに順番を決めて、前から順に好きな学校を 1 個取る仕組み。
ハーモニック数（Hn）： 数学的な計算で出てくる数値。1 + 1/2 + 1/3 + ... + 1/n の合計。1 万人なら約 10 くらいになります。これが「誰もに妬まれない人」の人数の目安になります。

論文「The Distribution of Envy in Matching Markets」の技術的サマリー

本論文は、ランダムなマッチング市場における「遅延受諾（Deferred Acceptance: DA）アルゴリズム」の下での「嫉妬（Envy）」の分布を解析するものである。特に、**「誰も嫉妬しない学生」と「誰も嫉妬しない学生」**の期待数を定量化し、ランダム直列独裁制（Random Serial Dictatorship: RSD）との比較を通じて、市場の規模が大きくなる際のこれらの集団の振る舞いを明らかにしている。

以下に、問題設定、手法、主要な貢献、結果、および意義について詳述する。

1. 問題設定と背景

学校選択問題（School Choice）における安定マッチングは、「正当化された嫉妬（justified envy）」の不在によって定義される。しかし、正当化の有無にかかわらず「嫉妬そのものを避けること」も公平性の重要な指標である。
本論文は、DA アルゴリズムによって生成されるマッチングにおいて、以下の 2 つのカテゴリに属する学生の数を研究対象とする。

誰も嫉妬しない学生（Students whom nobody envies）: 割り当てられた学校が、他の誰からも「自分の方がその学校に行きたい」と思われていない学生。
誰も嫉妬しない学生（Students who envy nobody）: 自分自身で「他の誰かの学校の方が良い」と思っていない学生（すなわち、最優先の学校に割り当てられた学生）。

これらの数を理解することは、以下の理由から重要である。

DA はパレート効率的ではないため、効率的なメカニズムで成り立つ性質（例：必ず 1 人は嫉妬せず、1 人は誰も嫉妬しない）が DA でも成り立つかは不明である。
「誰も嫉妬しない学生」の数は、最優先の学校に割り当てられる学生の割合（トップチョイス・シェア）と密接に関連し、政策評価の指標となる。
これらの学生は「改善不可能（unimprovable）」であり、DA 結果から出発する交換によってさらに良くすることはできない。したがって、これらは改善不可能な学生の数の下限を与える。

2. 手法とモデル

モデル: 学生と学校がそれぞれ $n$ 人存在する両側マッチング市場。すべてのエージェントは他方のすべてのエージェントに対して厳密な選好（完全な選好リスト）を持つ。
確率モデル: 学生と学校の選好・優先順位は、互いに独立かつ一様ランダムに生成される（i.i.d. ランダム市場）。
解析手法:
- 応用確率論のツール: 確率過程と漸近解析。
- クーポンコレクター問題（Coupon Collector Problem）: DA の逐次実行（McVitie and Wilson, 1971）とクーポンコレクター問題の間の深い関連性を活用。
- 決定の遅延の原理（Principle of Deferred Decisions）: 学生が提案を行うたびに、その選好リストをその場で生成するアプローチ。

3. 主要な結果

3.1. 「誰も嫉妬しない学生」の数（ $NE_n$ ）

命題 1: ランダムな学校選択問題において、誰も嫉妬しない学生の期待数は $n$ 番目の調和数 $H_n = \sum_{k=1}^n \frac{1}{k}$ に等しい。
$NE_n = H_n$

導出の鍵: DA の逐次実装において、学校が「提案」を受けるプロセスは、クーポンコレクター問題における「すべてのクーポンタイプが少なくとも 1 回集まるまでの時間」と一致する。
解釈: 学校が「需要が低い（under-demanded）」、すなわち誰も嫉妬しない学校であるための必要十分条件は、DA 実行中にちょうど 1 人の異なる学生から提案を受けることである。これは、クーポンコレクター問題の停止時刻における「単一のクーポンタイプ（singleton coupon）」の数に一致する。
漸近挙動: $H_n \approx \log n + \gamma$ $H_{n} \approx lo g n + γ$ であるため、誰も嫉妬しない学生の数は市場規模 $n$ $n$ に対して対数的にしか成長しない。したがって、その割合 $H_n/n$ $H_{n} / n$ は $n \to \infty$ $n \to \infty$ で 0 に収束する（消滅する）。
- 例： $n=10,000$ の場合、誰も嫉妬しない学生は 10 人未満と予想される。

3.2. 「誰も嫉妬しない学生」の数（ $EN_n$ ）

命題 2: 学生が $k$ 番目の選好に割り当てられる確率は、パラメータ $1/H_n$ の幾何分布で近似される。
$\text{Pr}(\text{rank} = k) \approx \frac{1}{H_n} \left(1 - \frac{1}{H_n}\right)^{k-1}$
系 1: 誰も嫉妬しない学生（最優先の学校に割り当てられる学生）の期待数は以下のようになる。
$EN_n \approx \frac{n}{H_n}$

解釈: 学生が $H_n$ 回程度の提案を行うため、1 回の提案で受理される確率は $1/H_n$ 程度となる。
漸近挙動: $n/H_n$ $n / H_{n}$ は $n$ $n$ に比例して増加するため、誰も嫉妬しない学生の絶対数は増加するが、市場全体に対する割合 $1/H_n$ $1/ H_{n}$ は 0 に収束する（ただし、 $H_n/n$ $H_{n} / n$ に比べるとはるかに大きい）。
- 例： $n=10,000$ の場合、約 1,100 人の学生が誰も嫉妬しない（最優先の学校に行く）。

3.3. ランダム直列独裁制（RSD）との比較

RSD（学生をランダムに順序付け、順に最優先の空いている学校を選ぶメカニズム）との比較を行った。

誰も嫉妬しない学生（RSD）: 期待数は $(n+1)/2$ 。つまり、学生の約半分が最優先の学校を得る。
誰も嫉妬しない学生（RSD）: 驚くべきことに、DA と同じく $H_n$ $H_{n}$ である（命題 3）。
- 証明の要点：位置 $k$ の学生が嫉妬されない確率は、 $k$ より後のすべての学生が $k$ の学校を最優先しない確率の積となり、これは telescoping product（項消去積）となり、結果として $1/(n-k+1)$ となる。これを $k$ について和をとると $H_n$ になる。

表 1: DA と RSD の比較

指標	DA	RSD
誰も嫉妬しない学生	$\approx n/H_n$	$(n+1)/2$
誰も嫉妬しない学生	$H_n$	$H_n$

4. 結論と意義

DA の非効率性と嫉妬の分布: DA はパレート効率的ではないため、多くの学生が改善可能な状態にある。しかし、本研究は「改善不可能な学生」の下限となる 2 つのグループ（誰も嫉妬しない、誰も嫉妬しない）が、市場規模が大きくなるにつれて相対的に**消滅（vanishing fraction）**することを示した。
メカニズムに依存しない普遍性: DA と全く異なる構造を持つ RSD においても、「誰も嫉妬しない学生」の期待数が $H_n$ で一致することは驚くべき結果である。これは、ランダム市場における $H_n$ という値が、特定のメカニズムの欠陥ではなく、市場構造そのものの根本的な性質を反映している可能性を示唆している。
実用的な洞察: 現実的な市場規模（例： $n=10,000$ ）において、誰も嫉妬しない学生は極めて少数（10 人未満）であり、誰も嫉妬しない学生も市場の 10% 未満（約 1,100 人）に留まる。これは、DA によるマッチングが「大多数の学生にとって、誰かによって嫉妬されるか、誰かを嫉妬する状態」であることを意味する。

5. 今後の課題

他のメカニズム（例：Top Trading Cycles）でも $H_n$ の結果が成り立つか。
多対一市場や選好が相関している場合の挙動（シミュレーションでは、相関がある場合さらに改善不可能な学生は減る傾向が見られた）。
嫉妬フリーかつ誰も嫉妬しない学生以外の「改善不可能な学生」の割合の完全な特徴付け（関連論文で 0 に収束することが確認されている）。

総じて、本論文は確率論的ツールを用いて、安定マッチングアルゴリズムの公平性と効率性の限界を定量的に明らかにし、市場設計における「嫉妬」の分布に関する重要な知見を提供している。