YOI 615：安定な組み合わせでは、申し込む側が得をする

論文615 の記録のページです。住所（YOI）は https://www.yamagishiyuuki.com/yoi/615 で、論文の本文は下の PDF にあります。ファイルは自分で用意した置き場所（https://yamagishi.sakuraweb.com）に置き、日付の証拠（.ots）を添えています。Zenodo でも公開しています（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}
}

日付の証拠（OpenTimestamps）

2026年10月1日に、2 本の PDF の指紋（SHA-256）をまとめて OpenTimestamps に送り、ビットコインのブロック 969434・969435・969440・969461 に記録されました（2026年10月01日 18:16（日本時間））。この .ots があれば、PDF がその時点で存在したことを、このサイトや運営者を信用しなくても、誰でも確かめられます。

書誌

要旨

$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節）。

キーワード：安定結婚問題、ゲール＝シャプレーのアルゴリズム、マッチング、申し込む側の有利、メカニズムデザイン

Abstract

Two sides of $n$ people each rank everyone on the other side. A matching is stable if no two people prefer each other to their current partners.A matching is made by one side proposing in order of preference while the other side keeps the best offer so far (the Gale--Shapley method), and it is compared with all matchings.No new theorem or law is claimed.

First, the proposing method always produces a stable matching、making $300$ random sets of preferences with $6$ on each side and finding every stable matching among all $720$, the result of the proposing method was stable in all $300$ (Section 2).

Second, and this is the core.Every proposer gets the best, and every receiver the worst, partner、in all $300$ sets, each proposer got the best partner obtainable in any stable matching, and each receiver the worst (Section 2).

Third, there need not be only one stable matching、with $6$ on each side the number of stable matchings averaged $1.856667$, at most $6$, and was exactly one in $0.426667$ of the sets. With only one it does not matter who proposes; with several, the proposers take the end better for them (Section 2).

Fourth, with more people the gap widens、averaging, over $200$ sets with $100$ on each side, where one’s partner stands in one’s own ranking, proposers were at $\mathbf{5.081700}$ and receivers at $\mathbf{19.731150}$, a gap of $\mathbf{3.882785}$ times (Section 3).

Fifth, the separator is which side proposes、with the same people and preferences, swapping the proposing side swaps which side takes its best end. Both results remain “stable” (Section 3).

Keywords: stable marriage problem, Gale-Shapley algorithm, matching, proposer advantage, mechanism design

版の記録

ここの PDF（倉庫の v1）は第1版（2026年9月）の原稿から作りました。ファイルは版ごとに分けて置いています（/yoi/615/v1/ の下）。中身を直すときは、このファイルを書き換えず、新しい版を足します（住所 https://www.yamagishiyuuki.com/yoi/615 はいつも最新の版を指します）。Zenodo の記録とは、Zenodo に上げる前の改訂のぶんだけ違うことがあります。

YOI の一覧へ