要旨
$n$ 人ずつの二つの側があり、各人が相手側の全員に好みの順をつける。どの二人も「今の相手より互いを好む」ことが無い組み合わせを、安定な組み合わせという。一方の側が好きな順に申し込み、受ける側がそのつど良い方を残す方法(ゲール=シャプレーの方法)で組み合わせを作り、それを全部の組み合わせと比べる。新しい定理も法則も主張しない。
第一に、申し込む方法は、いつも安定な組み合わせを作る。$6$ 人ずつの好みを乱数で $300$ 組作り、全部の組み合わせ $720$ 通りから安定なものを探すと、申し込む方法の結果は $300$ 組すべてで安定だった(第2節)。
第二に、これが本稿の芯である。申し込む側は全員が最良、受ける側は全員が最悪の相手になる。$300$ 組すべてで、申し込む側の一人一人が、安定な組み合わせの中で得られる最良の相手を得、受ける側の一人一人が、安定な組み合わせの中で最悪の相手になった(第2節)。
第三に、安定な組み合わせは一つとは限らない。$6$ 人ずつでは、安定な組み合わせの数は平均 $1.856667$ 個、最大 $6$ 個で、一つだけだったのは $0.426667$ である。一つしか無ければどちらが申し込んでも同じだが、複数あると、申し込む側がその両端の自分に良い端を取る(第2節)。
第四に、人数が多いと、差は大きく開く。$100$ 人ずつの好み $200$ 組で、相手が自分の好みの何番目かを平均すると、申し込む側は $\mathbf{5.081700}$ 番目、受ける側は $\mathbf{19.731150}$ 番目で、$\mathbf{3.882785}$ 倍の開きがあった(第3節)。
第五に、分離子は、どちらが申し込むかである。好みも人も同じで、申し込む側を入れ替えるだけで、どちらの側が最良の端を取るかが入れ替わる。どちらも「安定」であることに変わりはない(第3節)。
キーワード:安定結婚問題、ゲール=シャプレーのアルゴリズム、マッチング、申し込む側の有利、メカニズムデザイン。
射程(何を示さないか)
新しい定理も法則も主張しない。申し込む方法がいつも安定な組み合わせを作り、申し込む側に最良、受ける側に最悪になること(ゲールとシャプレー、$1962$)、安定な組み合わせの構造(クヌース、$1976$/ロスとソトマイヨール、$1990$)、相手の順位の平均が申し込む側で約 $\ln n$、受ける側で約 $n/\ln n$ になること(ピッテル、$1989$)は、いずれも既知である。制度を論じない。研修医の配属や学校選択の仕組みには立ち入らない。好みは乱数である。実際の好みの偏りや、嘘の好みを申告する場合は扱わない。既刊との関係:論文161 は、「不動点」の定理が何を要求し何を与えるかで別物であることを示した。安定な組み合わせでは、在ることを示す手続きが、どの組み合わせを作るかまで決め、しかもそれが一方の側に偏る。加えたのは、$6$ 人ずつで全部の組み合わせを調べ、申し込む方法の結果と突き合わせたこと、安定な組み合わせの数の分布と、$100$ 人ずつでの順位の平均を出したこと、分離子を「どちらが申し込むか」に置いたことである。
1. 記法と問い
設定:申し込む側 $n$ 人と受ける側 $n$ 人がいて、各人が相手側の $n$ 人に好みの順をつける。一対一の組み合わせのうち、「二人とも今の相手より互いを好む」二人が一組もいないものを安定という。
申し込む方法:相手のいない申し込む側の人は、まだ断られていない中で一番好きな相手に申し込む。受ける側は、それまでの申し込みの中で一番好きな人だけを残し、ほかは断る。断られた人はまた次に好きな相手に申し込む。誰も断られなくなったら終わる。
問い:申し込む方法の結果は安定か。安定な組み合わせの中で、それはどこにあるか。どちらの側に得か。
2. 全部の組み合わせと比べる
計算 2.1:$6$ 人ずつの好みを乱数で $300$ 組作り、組ごとに全部の組み合わせ $6!=720$ 通りを調べて安定なものをすべて求めた(申し込む方法とは独立な道筋)。
| 確かめたこと | $300$ 組のうち |
|---|---|
| 申し込む方法の結果が安定 | $300$ |
| 申し込む側の全員が、安定な中で最良の相手 | $300$ |
| 受ける側の全員が、安定な中で最悪の相手 | $300$ |
計算 2.2:安定な組み合わせの数は、平均 $1.856667$ 個、最小 $1$ 個、最大 $6$ 個で、一つだけだった組は $0.426667$ だった。
観察 2.3 これが本稿の芯である。申し込む側は全員が最良、受ける側は全員が最悪の相手になる。安定な組み合わせが複数あるとき、それらは申し込む側から見て良い端と悪い端を持つ。申し込む方法は、申し込む側の良い端を、全員について同時に取る。同じ組み合わせは、受ける側から見れば全員にとって悪い端である。一方の最良が、他方の最悪になっている。
観察 2.4 安定な組み合わせが一つなら、差は生まれない。$300$ 組のうち $0.426667$ は安定な組み合わせが一つだけで、どちらが申し込んでも同じ結果になる。残りの組では、安定な組み合わせが二つ以上あり、そのどれを取るかを申し込む側が決めている。
3. 人数を増やす
計算 3.1:$100$ 人ずつの好みを乱数で $200$ 組作り、申し込む方法で組み合わせ、相手が自分の好みの何番目かを平均した。
| 側 | 相手の順位の平均 | 漸近の目安 |
|---|---|---|
| 申し込む側 | $\mathbf{5.081700}$ 番目 | $\ln100=4.605170$ |
| 受ける側 | $\mathbf{19.731150}$ 番目 | $100/\ln100=21.714724$ |
受ける側と申し込む側の比は $\mathbf{3.882785}$ だった。調和数 $H_{100}=5.187378$ を使うと、目安は $5.187378$ と $100/H_{100}=19.277564$ で、どちらも実測に近い。
観察 3.2 人数が多いと、申し込む側の得は大きく開く。申し込む側は $100$ 人中およそ $5$ 番目に好きな相手と組み、受ける側はおよそ $20$ 番目の相手と組む、どちらの組み合わせも安定で、誰にも「駆け落ち」する理由は無い。それでも、得の分け方は申し込む側に大きく偏っている。
観察 3.3 分離子は、どちらが申し込むかである。好みも人も同じまま、申し込む側と受ける側を入れ替えると、今度は元の受ける側が最良の端を取る。「安定」は一つの組み合わせを指す言葉ではなく、両端を持つ集まりを指す。手続きを決めることは、その端を一つ選ぶことである。
観察 3.4 論文161 と並べる。161 は、「不動点」の定理が、何を要求し何を与えるかでそれぞれ別物であることを示した。在ることを言うだけの定理とは違い、申し込む方法は安定な組み合わせを作ってみせ、しかもその中の特定の一つ、申し込む側に最も良いものを返す。
観察 3.5 言わないこと。研修医の配属や学校選択の制度には立ち入らない。好みは乱数で、嘘の好みを申告する場合は扱わない。示したのは、$6$ 人ずつでの全部の組み合わせとの突き合わせ、$100$ 人ずつでの順位の平均、そして申し込む側を入れ替えると得が入れ替わることである。
4. 点呼と結び
- 申し込む方法の結果は $300$ 組すべてで安定(計算 2.1):全部の組み合わせと突き合わせ。
- 申し込む側は全員が最良(計算 2.1):$300$ 組すべて。
- 受ける側は全員が最悪(計算 2.1):$300$ 組すべて。
- 一方の最良が他方の最悪(観察 2.3):本稿の芯。
- 安定な組み合わせは平均 $1.856667$ 個(計算 2.2):最大 $6$ 個。
- 一つだけの組は $0.426667$(観察 2.4):そこでは差が無い。
- $100$ 人ずつで申し込む側 $\mathbf{5.081700}$ 番目(計算 3.1):$\ln n$ に近い。
- 受ける側 $\mathbf{19.731150}$ 番目(計算 3.1):$n/\ln n$ に近い。
- 比 $\mathbf{3.882785}$(計算 3.1):人数が多いと開く。
- 分離子はどちらが申し込むか(観察 3.3):入れ替えれば得も入れ替わる。
結び:二つの側が相手に好みの順をつけるとき、一方が順に申し込み、受ける側が良い方を残す方法は、安定な組み合わせを作る。そして、申し込む側が得をする。$6$ 人ずつの好み $300$ 組で全部の組み合わせ $720$ 通りと突き合わせると、申し込む方法の結果はすべて安定で、申し込む側は全員が安定な中で最良の相手、受ける側は全員が最悪の相手になった。人数が多いと差は大きく開く。$100$ 人ずつでは、相手の順位の平均が申し込む側 $5.081700$ 番目、受ける側 $19.731150$ 番目で、$3.882785$ 倍の開きがあった。分離子は、どちらが申し込むかである。安定な組み合わせは両端を持つ集まりで、手続きを決めることは、その端を一つ選ぶことである。既刊との位置、論文161 が分けた「在ることを言う定理」とは違い、ここでは手続きが作るものまで決め、それが一方に偏る。正直に言えば、好みは乱数で、制度にも嘘の申告にも立ち入っていない。
参考文献
- Gale, D., & Shapley, L. S. (1962). College admissions and the stability of marriage. The American Mathematical Monthly.
- Knuth, D. E. (1976). Mariages stables et leurs relations avec d’autres problèmes combinatoires. Les Presses de l’Université de Montréal.
- Pittel, B. (1989). The average number of stable matchings. SIAM Journal on Discrete Mathematics.
- Roth, A. E., & Sotomayor, M. A. O. (1990). Two-Sided Matching: A Study in Game-Theoretic Modeling and Analysis. Cambridge University Press.
- 山岸勇輝 (2026). 『「不動点」は一つの定理ではない』[論文161]. Zenodo. 10.5281/zenodo.22092530
作成にあたって:本稿の着想と内容は、著者自身の考察に基づくものです。文章の構成整理や英訳、数式の確認には AI(大規模言語モデル)の助力を得ました。最終的な内容の解釈や誤りがあれば、それらはすべて著者の責に帰します。お気づきの点があれば、ご教示いただければ幸いです。
書誌
山岸勇輝(2026)「安定な組み合わせでは、申し込む側が得をする」[論文615]. Zenodo.
DOI: 10.5281/zenodo.23014484
日付の証拠(OpenTimestamps):日本語版の .ots・英語版の .ots・SHA256SUMS
予備の置き場所(ミラー。中身は上と同じです):PDF 日本語・PDF English・SHA256SUMS
住所:https://www.yamagishiyuuki.com/yoi/615・DOI 10.5281/zenodo.23014484・CC BY 4.0・プレプリント(査読を経ていません)・ORCID 0009-0006-8587-3450
引用するとき
山岸勇輝 (2026). 安定な組み合わせでは、申し込む側が得をする [論文615]. YOI: https://www.yamagishiyuuki.com/yoi/615 ・ DOI: 10.5281/zenodo.23014484
Yamagishi, Y. (2026). In a Stable Matching, the Side That Proposes Comes Out Ahead [Paper 615]. YOI: https://www.yamagishiyuuki.com/yoi/615; DOI: 10.5281/zenodo.23014484
@misc{yamagishi2026yoi615,
author = {Yamagishi, Yuuki},
title = {In a Stable Matching, the Side That Proposes Comes Out Ahead},
year = {2026},
howpublished = {YOI: https://www.yamagishiyuuki.com/yoi/615},
doi = {10.5281/zenodo.23014484},
note = {Preprint, edition 1}
}
指紋(SHA-256)と確かめ方
0b6e0e3af3aa518da7da228af861bfbcf3815e0108d2e2fb8d7c57d3e71d5dd7 yamagishi_yoi615_v1_jp.pdf560407653b9cadbe70ceee6bff8e5a2e90ab8ca6ba0042960fee539af5313b6f yamagishi_yoi615_v1_en.pdfPDF と .ots を同じ場所に保存し、opentimestamps.org に .ots、続けて PDF を落とすと、記録された日時が表示されます。PDF が 1 バイトでも変わっていれば通りません。