Yamagishi Complexity Torus Lab山岸勇輝ラボ

【論文615】安定な組み合わせでは、申し込む側が得をする

要旨

$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. 点呼と結び

  1. 申し込む方法の結果は $300$ 組すべてで安定(計算 2.1):全部の組み合わせと突き合わせ。
  2. 申し込む側は全員が最良(計算 2.1):$300$ 組すべて。
  3. 受ける側は全員が最悪(計算 2.1):$300$ 組すべて。
  4. 一方の最良が他方の最悪(観察 2.3):本稿の芯。
  5. 安定な組み合わせは平均 $1.856667$ 個(計算 2.2):最大 $6$ 個。
  6. 一つだけの組は $0.426667$(観察 2.4):そこでは差が無い。
  7. $100$ 人ずつで申し込む側 $\mathbf{5.081700}$ 番目(計算 3.1):$\ln n$ に近い。
  8. 受ける側 $\mathbf{19.731150}$ 番目(計算 3.1):$n/\ln n$ に近い。
  9. 比 $\mathbf{3.882785}$(計算 3.1):人数が多いと開く。
  10. 分離子はどちらが申し込むか(観察 3.3):入れ替えれば得も入れ替わる。

結び:二つの側が相手に好みの順をつけるとき、一方が順に申し込み、受ける側が良い方を残す方法は、安定な組み合わせを作る。そして、申し込む側が得をする。$6$ 人ずつの好み $300$ 組で全部の組み合わせ $720$ 通りと突き合わせると、申し込む方法の結果はすべて安定で、申し込む側は全員が安定な中で最良の相手、受ける側は全員が最悪の相手になった。人数が多いと差は大きく開く。$100$ 人ずつでは、相手の順位の平均が申し込む側 $5.081700$ 番目、受ける側 $19.731150$ 番目で、$3.882785$ 倍の開きがあった。分離子は、どちらが申し込むかである。安定な組み合わせは両端を持つ集まりで、手続きを決めることは、その端を一つ選ぶことである。既刊との位置、論文161 が分けた「在ることを言う定理」とは違い、ここでは手続きが作るものまで決め、それが一方に偏る。正直に言えば、好みは乱数で、制度にも嘘の申告にも立ち入っていない。

参考文献

  1. Gale, D., & Shapley, L. S. (1962). College admissions and the stability of marriage. The American Mathematical Monthly.
  2. Knuth, D. E. (1976). Mariages stables et leurs relations avec d’autres problèmes combinatoires. Les Presses de l’Université de Montréal.
  3. Pittel, B. (1989). The average number of stable matchings. SIAM Journal on Discrete Mathematics.
  4. Roth, A. E., & Sotomayor, M. A. O. (1990). Two-Sided Matching: A Study in Game-Theoretic Modeling and Analysis. Cambridge University Press.
  5. 山岸勇輝 (2026). 『「不動点」は一つの定理ではない』[論文161]. Zenodo. 10.5281/zenodo.22092530

作成にあたって:本稿の着想と内容は、著者自身の考察に基づくものです。文章の構成整理や英訳、数式の確認には AI(大規模言語モデル)の助力を得ました。最終的な内容の解釈や誤りがあれば、それらはすべて著者の責に帰します。お気づきの点があれば、ご教示いただければ幸いです。

書誌

山岸勇輝(2026)「安定な組み合わせでは、申し込む側が得をする」[論文615]. Zenodo.
DOI: 10.5281/zenodo.23014484

YOI 615第1版・2026年9月ビットコインに記録済み

日付の証拠(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.pdf
560407653b9cadbe70ceee6bff8e5a2e90ab8ca6ba0042960fee539af5313b6f yamagishi_yoi615_v1_en.pdf

PDF と .ots を同じ場所に保存し、opentimestamps.org に .ots、続けて PDF を落とすと、記録された日時が表示されます。PDF が 1 バイトでも変わっていれば通りません。