りきのblog

理学部数学科→経営工学修士（理論経済学；多対一マッチング） 　もし間違いあればおしえてください！ ハリーポッター（魔法の覚醒）が好き

多対一マッチングにおけるアルゴリズムと耐戦略性

マッチング理論
指標を満たすマッチングに到達するアルゴリズム

ここでは, 指標を満たすマッチングに到達するアルゴリズムを紹介します.

指標に関する記事は

rikida.hatenablog.com

で紹介しています. 

 マッチング理論では, 指標を満たすマッチングが存在するかどうかに加えて, 存在するならそれをどのように見つけるかが大事になっています. 

私が学部時代に学んでいた数学（例えば微分方程式やブラウワーの不動点定理など）は, 存在だけを証明することが多く, 実際に求める手順まではやらない（もしくはできない）こともよくありました（多分）. しかしマッチング理論では「求める手順」も重要になります.

ポイントなぜ手順（アルゴリズム）が重要か
理由は2点あります.
  1. 実用性を強く求められているため.
  2. 全てのマッチングを列挙してから, 指標を満たすものを探すのは数が膨大すぎるため.

例えば学生の数がn人で学校の数がm個あるとき, 「各学生がどの学校に行くか（未割当も含める）」という割当の総数は, おおざっぱに m^n のオーダーになります. nやmが少し増えるだけで爆発的に増えるので, 全列挙は現実的ではありません. そのため, 希望の指標を満たすマッチングを直接求めるアルゴリズムが必要不可欠なのです.

アルゴリズムを回すために必要な情報

アルゴリズムを実行するときは情報がいります. 典型的には, 次の情報を用意します.

  • 学生の人数, 学校の数.
  • 各学生が学校に対して持つ選好.
  • 各学校が学生に対して持つ優先順位.
  • 学校がどんな制約を持つか（単純定員なのか属性定員なのか等）.
  • （もしあれば）その他の追加情報.
注意「選好」は真実が分からないことがある
学生の人数や学校の数, 学校側の優先順位, 定員などは, 真の情報を手に入れやすい一方で, 各学生が学校に対して持つ選好については, 真の情報を得るのが難しいです.

アルゴリズムを回すとき, 設計者（マッチングを決める人）は学生に 「あなたの学校ランキングはどうなってる？」と聞いて提出してもらいます. しかし, ほんとうの情報が提出される保証はありません.
耐戦略性（strategy-proofness）
定義耐戦略性
あるアルゴリズムが耐戦略性をみたすとは, 「他の学生全員が真の情報を提出した」と仮定したとき, 自分も真の情報を提出することが自分にとって最も良い結果につながる, という性質を指します.

直感的には, 設計者に提出する情報に戦略性が薄くなる(つまり, そのシステムは学生の戦略的な操作に耐えているといえる. )ということです.

では指標に到達するアルゴリズムを紹介しましょう. どれも良いアルゴリズムですが, 適用できる範囲が決まっていたり, 到達できる指標が異なります. もしマッチングを決める必要が出た場合は, 欲しい指標に合わせてアルゴリズムを選ぶ（あるいは設計する）ことになります.

前提の整理
定義制約の種類（ざっくり）
  • 単純定員制約：全ての学校が「人数の上限」だけを持つ.
  • 属性定員制約：少なくとも一つ以上の学校が, 男女別など属性ごとの上限を持つ.
  • 一般上限制約：属性定員よりも抽象的な制約だと思っておけば十分です（詳しい定義は別途）.

制約に関する詳しい記事は

rikida.hatenablog.com

で紹介しています. 

定義共通プライオリティ
学校側の優先順位が, 全ての学校で同じ順番になる状況を「共通プライオリティ」と呼びます.
例えば, テストの点数で学生が一つのランキングに並び, 全ての学校がその順に学生を好む場合です（高校受験など）.

一方で, 各学校が面接などで独自に評価して優先順位がバラバラになると, 共通プライオリティは成り立ちません.
定義「何位下まで許せるか」の情報
設計者が学生に対して, 「あなたより順位が下の生徒が, あなたが今入っている学校より良い学校に行ったとき, 何位下までなら許せますか？」という情報を集められる場合があります.

この情報を得られると, “どの程度の公平性を許すか” を反映した設計ができるようになります.
アルゴリズム一覧
例SD（Serial Dictatorship）
利用できる制約 ; 単純定員, 属性定員, 一般上限制約.
選好の条件 ; 共通プライオリティが仮定できるときのみ.
何位下まで許せるかの情報 ; 不要.
達成する指標 ; [無駄のなさ + 実行可能 + 個人合理性 + 効率性 + 耐戦略性].
作成者 ; ?.
例KSD（K Serial Dictatorship）
利用できる制約 ; 単純定員, 属性定員, 一般上限制約.
選好の条件 ; 共通プライオリティが仮定できるときのみ.
何位下まで許せるかの情報 ; 必要.
達成する指標 ; [無駄のなさ + K公平 + 実行可能 + 個人合理性 + K効率性 + CA結果の改善 + 耐戦略性].
作成者 ; 私（2026）.
例DA（Deferred Acceptance）
利用できる制約 ; 単純定員.
選好の条件 ; なし.
何位下まで許せるかの情報 ; 不要.
達成する指標 ; [無駄のなさ + 公平性 + 実行可能 + 個人合理性 + 耐戦略性] + 学生最適.
作成者 ; Gale and Shapley (1962).
例CA（Cutoff Adjustment）
利用できる制約 ; 単純定員, 属性定員, 一般上限制約.
選好の条件 ; なし.
何位下まで許せるかの情報 ; 不要.
達成する指標 ; [公平性 + 実行可能 + 個人合理性] + 学生最適.
作成者 ; Kamada and Kojima (2024).
論文 ; Efficient matching under general constraints.
例EADA（Efficiency-adjusted Deferred Acceptance）
利用できる制約 ; 単純定員.
選好の条件 ; なし.
何位下まで許せるかの情報 ; 不要.
達成する指標 ; [無駄のなさ + 極小正当羨望 + 実行可能 + 個人合理性 + 効率性 + DA結果の改善].
作成者 ; Kesten (2010), Battal (2021).
論文 ; School choice with consent. Minimally unstable Pareto improvements over deferred acceptance.
例SEPF（Student Exchange under Partial Fairness）
利用できる制約 ; 単純定員.
選好の条件 ; なし.
何位下まで許せるかの情報 ; 必要.
達成する指標 ; [無駄のなさ + 部分公平性 + 実行可能 + 個人合理性 + 部分効率性 + DA結果の改善].
作成者 ; Dur (2019).
論文 ; School choice under partial fairness.
例TTC^{\mu}（Top Trading Cycles under feasible matching \mu）
利用できる制約 ; 単純定員, 属性定員.
選好の条件 ; なし.
何位下まで許せるかの情報 ; 不要.
達成する指標 ; [無駄のなさ + 実行可能 + 個人合理性 + 効率性 + 実行可能マッチング\muの改善].
作成者 ; Imamura and Kawase (2024).
論文 ; Efficient matching under general constraints.
補足

各アルゴリズムに関する詳細な説明は, いつか（多分）作ろうと思います. この中でCAアルゴリズムに関しては, 「マッチング理論とマーケットデザイン（著：小島武仁, 河田陽向）」にも載っています. 初学者におすすめしたい良書です.

多対一マッチングにおける制約.

マッチング理論
単純定員（容量制約）と属性定員

応用で重要となる, 単純定員（容量制約）と属性定員を紹介します.

研究室配属を考えてみましょう. 同じ学科の全ての人が希望する研究室にいけるでしょうか. また高校受験を考えてみましょう. 希望する学校に全ての学生が入ることができるでしょうか.

直感では無理そうですよね. それはなぜかというと, 研究室や学校には定員が設けられているからです. 定員をオーバーしてしまうと, 学生の面倒を見切ることができなくなります. そのため定員が設けられており, その結果, 全ての学生が希望する研究室や学校に入ることはできないんですね.

マッチング理論の本質は, 限りある定員にどのように学生を配属するか, といえます. これが難しいんですよね^^

定員の種類

定員には何種類かあります. 代表的なのが次の2つです.

定義単純定員（容量制約）
単純定員とは, 学校（または研究室など）が「人数の上限」だけを持っている状態を指します.
例単純定員
  • ホグワーツの定員は2人まで.
  • 研究室Aの定員は5人まで.
  • 高校Bの定員は320人まで.
定義属性定員
属性定員とは, 学校（または研究室など）が「複数の属性ごとの上限」を持っている状態を指します.
注意属性は重ならない（互いに素）とする
属性が重なってしまうと, 1人の学生が複数の属性に同時に属する可能性があり, 数え方が不明確になります.
例えば「リンゴ好き」と「バナナ好き」を属性にすると, 両方好きな学生が存在しうるので, このままだと扱いがややこしくなります.
例属性定員
  • 学校と男女（男性上限, 女性上限）.
  • 研究室と実験系/理論系（実験系上限, 理論系上限）.
  • ホグワーツで「各寮 × 純血/非純血」ごとの上限.
  • 学校と血液型（A, B, O, AB の各上限）.
制約の呼び方

全ての学校が単純定員のときは, 全体として「単純定員（容量制約）」と呼びます. 全ての学校が属性定員をもつときは, 全体として「属性定員（属性制約）」と呼びます.

もし「ある学校は単純定員, 別の学校は属性定員」という混在がある場合はどうするか, という疑問も生まれると思います. この場合は, 全体としては属性定員（属性制約）として扱うのが自然です.

定義実行可能（feasible）
マッチング\muが各学校の定員内に収まっているとき, マッチング\muを実行可能とよびます.

実行可能なマッチングの例は

https://rikida.hatenablog.com/

で紹介しています. 

単純定員と属性定員の違いは, マッチングに効く

この2つの制約の違いはマッチングに関係します. 各指標を紹介した記事で, 良いとされる指標を複数紹介しました. 実は単純定員と属性定員を比べると, 単純定員の方が「良い性質を同時に満たすマッチング」が存在しやすいです.

定義「存在する」とは
マッチングの仕方を全通り調べあげたときに, 少なくとも一つは100%その指標を満たすマッチングが見つかることをいいます.
まとめ指標の達成可能性（イメージ）
全ての学校（研究室など）が単純定員のとき
  • [公平性 + 個人合理性 + 実行可能性] + 学生最適：○
  • [無駄のなさ + 公平性 + 個人合理性 + 実行可能性] + 学生最適：○
全ての学校（研究室など）が属性定員のとき
  • [公平性 + 個人合理性 + 実行可能性] + 学生最適：○
  • [無駄のなさ + 公平性 + 個人合理性 + 実行可能性] + 学生最適：×（存在しないことがある）
※上は「一般にどうなるか」の要点だけを書いたまとめです. 例2で見たように, 属性定員下では「無駄のなさ」を同時に入れると壊れやすい, というのがポイントです.

上の指標を達成するマッチングの求め方（アルゴリズム）は別記事で紹介しています.

さらに一般の制約へ

制約には, もう少し条件を抽象化したマトロイド制約や, 一般上限制約というものがあります. この定義はここでは省略しますが, くわしい内容が知りたい方は 「マッチング理論とマーケットデザイン」（小島武仁, 河田陽向 著）を読んでみてください.

マッチング理論でよく議論される各指標

マッチング理論
マッチングでよく使う指標まとめ（例つき）

ここではマッチングを考えるときに重要な指標について話します.

マッチング理論では, どんな性質を満たすべきかがよく議論されます. 指標は自由に定義されますが, まずは「この性質をみたすとよい」とされている指標をいくつか紹介します.

初めに, マッチング理論でよく使われる

  • 実行可能（feasible）
  • 個人合理的（IR）
  • 公平性（fair）
  • 無駄のなさ（non-wasteful）
  • （A の中で）学生最適（student-optimal in A）
  • 効率的（Pareto efficient）

を紹介します.

定義実行可能
マッチング\muが各学校の定員内におさまっている場合, マッチングは実行可能であるという. (そもそもこれを満たさなければ話にならないですね.)
定義個人合理的（IR）
マッチング\muが, 全ての学生が未割当となる結果以上の良い結果であるときマッチング\muを個人合理的という.  この指標は, 全ての学生が「配属されないより行きたくない学校にいくことはない」という性質を保証する指標である.
定義公平性（fair）
マッチング\muでの配属結果において, 「自分の配属先より行きたい学校にいっている他の学生がいるが, その学生は自分より成績が下」 という状況が, 全学生にとって発生しないときにマッチング\muを公平性をみたすとをいう.  これは「自分の方が成績がいいのに, いいところに入っている学生がいる」という理不尽さがない, という指標である.
定義無駄のなさ（non-wasteful）
マッチング\muの配属結果において, 「自分の配属先よりも, 行きたい学校があるにもかかわらずその学校の定員が余っている（正確には, 自分をいれることができる）」 という状況が, 全ての学生にとって発生しないとき, マッチング\muを無駄がないという. この指標は, 定員に空きがあり, そこに行きたい学生がいる状況がない, という無駄のなさを表す指標である.

次に紹介する効率性の指標は, 無駄のなさよりも強い指標です.

定義効率的（Pareto efficient）
今のマッチング\muの配属のに対して, 以下の条件を全て満たす別のマッチング\mu'が存在しないときマッチング\muが効率的であるといいます.
・マッチング\mu'は実行可能の指標を満たす
・全ての学生にとって\mu'の配属の方が\muの配属よりも同じか良い
・少なくとも一人以上の学生は\mu'の配属の方が\muの配属より（厳密に）良い

この指標は, それより全ての学生にとって良くなるマッチングが存在しないことを保証する.

実はマッチング\muが効率性を満たすならばマッチング\muは無駄のなさを満たします. つまり効率性は無駄がない状態であり, さらにこれ以上マッチングをよくできない状態を表すといえます.

定義Aの指標の中で学生最適
マッチング\muが指標Aを満たす全てのマッチングの中で, 各学生が最も良い配属先となるマッチングを選んでもらった時, 全ての学生が同じマッチングを選んでいた場合, そのマッチング\muを指標Aの中で学生最適という.

普通, 各学生にとって好みのマッチングは別々となる. 一致することは珍しいが, 特定の指標だったり, 特定の制約だったりすれば存在が保証される. 全ての学生の好みが一致しているという点でも, もし存在すれば採用してあげたい.

これらの指標はマッチング理論でよく使われます.

ただし指標というのは自由な発想が多くあるものです. そこで私がオリジナルで新たな指標を挙げましょう.

定義未割当主義
マッチング\muが未割当主義をみたすとは, 全ての学生が未割当となっているときで定義する.
定義一人は一番いいところにいかせる主義
マッチング\muが一人は一番いいところにいかせる主義をみたすとは, 少なくとも一人の学生は第一希望に入ることができているときで定義する.
定義みんな一番いいところにいかせない主義
マッチング\muがみんな一番いいところにいかせない主義をみたすとは, 全ての学生が第一希望の学校にはいれていないときで定義する.
定義みんな第一希望主義
マッチング\muがみんな第一希望主義をみたすとは, マッチング\muにおいて, 全ての学生が第一希望の学校に配属されているときで定義する.
これらの指標を用意したところで, 具体例をもとにどのようなマッチングが指標を満たすか考えてみましょう!!
記法（このブログ内のマッチングの表示）

学生集合を
\{R,\ He,\ Lu\}=\{\text{ロン},\ \text{ハーマイオニー},\ \text{ルーナ}\}
学校集合を
\{H,\ M,\ U\}=\{\text{ホグワーツ},\ \text{まほうどころ},\ \text{未割当}\}
と書きます.

マッチング\muは「上段＝学生, 下段＝行き先」の行列表示で書きます.

\mu=\begin{pmatrix} R & He & Lu\\ H & M & U \end{pmatrix}
（例：ロンはホグワーツ, ハーマイオニーはまほうどころ, ルーナは未割当, を表す.）

（準備）「全マッチング」

ここでは全ての割当（各学生の行き先がH,M,Uのいずれか）を列挙します. 学生3人×行き先3つなので3^3=27通りあります.

  1. \begin{pmatrix}R&He&Lu\\H&H&H\end{pmatrix}
  2. \begin{pmatrix}R&He&Lu\\H&H&M\end{pmatrix}
  3. \begin{pmatrix}R&He&Lu\\H&H&U\end{pmatrix}
  4. \begin{pmatrix}R&He&Lu\\H&M&H\end{pmatrix}
  5. \begin{pmatrix}R&He&Lu\\H&M&M\end{pmatrix}
  6. \begin{pmatrix}R&He&Lu\\H&M&U\end{pmatrix}
  7. \begin{pmatrix}R&He&Lu\\H&U&H\end{pmatrix}
  8. \begin{pmatrix}R&He&Lu\\H&U&M\end{pmatrix}
  9. \begin{pmatrix}R&He&Lu\\H&U&U\end{pmatrix}
  10. \begin{pmatrix}R&He&Lu\\M&H&H\end{pmatrix}
  11. \begin{pmatrix}R&He&Lu\\M&H&M\end{pmatrix}
  12. \begin{pmatrix}R&He&Lu\\M&H&U\end{pmatrix}
  13. \begin{pmatrix}R&He&Lu\\M&M&H\end{pmatrix}
  14. \begin{pmatrix}R&He&Lu\\M&M&M\end{pmatrix}
  15. \begin{pmatrix}R&He&Lu\\M&M&U\end{pmatrix}
  16. \begin{pmatrix}R&He&Lu\\M&U&H\end{pmatrix}
  17. \begin{pmatrix}R&He&Lu\\M&U&M\end{pmatrix}
  18. \begin{pmatrix}R&He&Lu\\M&U&U\end{pmatrix}
  19. \begin{pmatrix}R&He&Lu\\U&H&H\end{pmatrix}
  20. \begin{pmatrix}R&He&Lu\\U&H&M\end{pmatrix}
  21. \begin{pmatrix}R&He&Lu\\U&H&U\end{pmatrix}
  22. \begin{pmatrix}R&He&Lu\\U&M&H\end{pmatrix}
  23. \begin{pmatrix}R&He&Lu\\U&M&M\end{pmatrix}
  24. \begin{pmatrix}R&He&Lu\\U&M&U\end{pmatrix}
  25. \begin{pmatrix}R&He&Lu\\U&U&H\end{pmatrix}
  26. \begin{pmatrix}R&He&Lu\\U&U&M\end{pmatrix}
  27. \begin{pmatrix}R&He&Lu\\U&U&U\end{pmatrix}
例1：単純定員

学校2つ\{H,M\}（+ 未割当U）, 学生3人\{R,He,Lu\}とします. 各学校の定員や選好, 優先順位を以下で定義します.

  • 定員：Hは2人まで, Mは2人まで.
  • 学生の選好：全員H \succ M \succ U.
  • 優先順位：
    • H：He \succ Lu \succ R.
    • M：Lu \succ He \succ R.
例1の指標を満たすマッチングを考えていきましょう.
例実行可能
実行可能（定員以内に収まる）なのは, 全マッチング27通りから
  • \begin{pmatrix}R&He&Lu\\H&H&H\end{pmatrix}（H が3人で超過）
  • \begin{pmatrix}R&He&Lu\\M&M&M\end{pmatrix}（M が3人で超過）
の2つを除いた25通りです.

次に公平性をみたすマッチングが何か見ていきましょう. （以降は「実行可能性」を別に課さない限り, 定員内に収まっている必要はありません.）

例公平（fair）
公平なマッチングは8通り：
  • \begin{pmatrix}R&He&Lu\\M&H&H\end{pmatrix}
  • \begin{pmatrix}R&He&Lu\\M&H&M\end{pmatrix}
  • \begin{pmatrix}R&He&Lu\\U&H&H\end{pmatrix}
  • \begin{pmatrix}R&He&Lu\\U&H&M\end{pmatrix}
  • \begin{pmatrix}R&He&Lu\\U&H&U\end{pmatrix}
  • \begin{pmatrix}R&He&Lu\\U&M&M\end{pmatrix}
  • \begin{pmatrix}R&He&Lu\\U&U&M\end{pmatrix}
  • \begin{pmatrix}R&He&Lu\\U&U&U\end{pmatrix}
例無駄のなさ（non-wasteful）
無駄がないのは3通り：
  • \begin{pmatrix}R&He&Lu\\H&H&M\end{pmatrix}
  • \begin{pmatrix}R&He&Lu\\H&M&H\end{pmatrix}
  • \begin{pmatrix}R&He&Lu\\M&H&H\end{pmatrix}
例個人合理的（IR）
今回の設定では実行可能25通りすべてが個人合理的.
例効率的（Pareto efficient）
効率的なのは3通り（上の「無駄のなさ」と一致）：
  • \begin{pmatrix}R&He&Lu\\H&H&M\end{pmatrix}
  • \begin{pmatrix}R&He&Lu\\H&M&H\end{pmatrix}
  • \begin{pmatrix}R&He&Lu\\M&H&H\end{pmatrix}

次に私が自由な発想で考えた指標たちをみたすかどうか見ていきましょう!!

例未割当主義
  • \begin{pmatrix}R&He&Lu\\U&U&U\end{pmatrix}
例一人は一番いいところにいかせる主義
全マッチング27通りのうち, H に誰も入らないのは 2^3=8 通りなので, それ以外の19通りがこの指標をみたす.
（参考：除かれる8通り = 行き先が全員 M または U のもの.）
  • \begin{pmatrix}R&He&Lu\\U&U&U\end{pmatrix}
  • \begin{pmatrix}R&He&Lu\\M&U&U\end{pmatrix}
  • \begin{pmatrix}R&He&Lu\\U&M&U\end{pmatrix}
  • \begin{pmatrix}R&He&Lu\\U&U&M\end{pmatrix}
  • \begin{pmatrix}R&He&Lu\\M&M&U\end{pmatrix}
  • \begin{pmatrix}R&He&Lu\\M&U&M\end{pmatrix}
  • \begin{pmatrix}R&He&Lu\\U&M&M\end{pmatrix}
  • \begin{pmatrix}R&He&Lu\\M&M&M\end{pmatrix}
例みんな一番いいところにいかせない主義
「全員が第一希望 H」のマッチングを除いたものなので26通り.
  • \begin{pmatrix}R&He&Lu\\H&H&H\end{pmatrix}を除く.
例みんな第一希望主義
この指標をみたすマッチングは次の1通り：
  • \begin{pmatrix}R&He&Lu\\H&H&H\end{pmatrix}
（実行可能性を課していないので, 定員オーバーでもOK.）

次に指標の組み合わせで新しい指標をつくり, それをみたすマッチングを列挙していきましょう!!

例実行可能 + みんな第一希望主義
みんなホグワーツに入ると定員オーバーなので, この指標をみたすマッチングは存在しない.
例実行可能 + 無駄のなさ + 公平性
この3つを同時にみたすのは1通り：
  • \begin{pmatrix}R&He&Lu\\M&H&H\end{pmatrix}
（理由：無駄のなさは3通りだが, そのうち公平性もみたすのはこの1通りだけ.）
例実行可能 + 公平 + 無駄のなさ + 個人合理的
→ 1通りだけ残る：
  • \begin{pmatrix}R&He&Lu\\M&H&H\end{pmatrix}

ここまで指標に対応するマッチングを列挙してきました. 指標を組み合わせれば組み合わせるほど, その指標をみたすマッチングの数が少なくなることを実感できたでしょうか. この感覚はとても大切で, 満たしてほしいマッチングが存在しないことを理解することで, どの指標であればマッチングが存在するかに目を向けられるようになります.

定理
各学校の制約が単純定員であるとする. （また選好と優先順位が強選好と強優先順位であるとする.） このとき実行可能 + 公平 + 無駄のなさ + 個人合理的をみたすマッチングが少なくとも一つ存在する. さらに指標Aを「実行可能 + 公平 + 無駄のなさ + 個人合理的」とするとき, Aの中で学生最適をみたすマッチングも存在する.
例2：属性定員（ホグワーツが男女1,1 / まほうどころが定員2）
  • 制約：
    • H は「男性1名まで・女性1名まで」（計2名まで）.
    • M は定員2名まで.
  • 学生の選好：全員 H \succ M \succ U.
  • 優先順位：
    • H：He \succ Lu \succ R.
    • M：Lu \succ He \succ R.
  • 性別：ロン＝男性, ハーマイオニー＝女性, ルーナ＝女性.
指標実行可能（feasible）
例2では, 全マッチング27通りのうち次の4通りが非実行可能である. 従って実行可能は23通りである.

  • \begin{pmatrix}R&He&Lu\\H&H&H\end{pmatrix}（H が3人で超過）.
  • \begin{pmatrix}R&He&Lu\\M&M&M\end{pmatrix}（M が3人で超過）.
  • \begin{pmatrix}R&He&Lu\\M&H&H\end{pmatrix}（H に女性2人）.
  • \begin{pmatrix}R&He&Lu\\U&H&H\end{pmatrix}（H に女性2人）.
指標実行可能 + 公平（fair）
例2で実行可能かつ公平なマッチングは6通りである.
（公平性は, あなたの説明どおり「行きたい学校に自分より下位がいる」タイプの正当な羨望が発生しないこと, で判定している.）

  • \begin{pmatrix}R&He&Lu\\M&H&M\end{pmatrix}
  • \begin{pmatrix}R&He&Lu\\U&H&M\end{pmatrix}
  • \begin{pmatrix}R&He&Lu\\U&H&U\end{pmatrix}
  • \begin{pmatrix}R&He&Lu\\U&M&M\end{pmatrix}
  • \begin{pmatrix}R&He&Lu\\U&U&M\end{pmatrix}
  • \begin{pmatrix}R&He&Lu\\U&U&U\end{pmatrix}
指標実行可能 + 無駄のなさ（non-wasteful）
例2で実行可能かつ無駄がないマッチングは2通りである.
  • \begin{pmatrix}R&He&Lu\\H&H&M\end{pmatrix}
  • \begin{pmatrix}R&He&Lu\\H&M&H\end{pmatrix}
指標実行可能 + 個人合理的（IR）
今回の設定では, 学生全員が H \succ M \succ U を持つので, 実行可能23通りすべてが個人合理的である.
指標実行可能 + 公平 + 無駄のなさ + 個人合理的
この4つを同時にみたすマッチングは存在しない.

理由として, 「実行可能 + 無駄のなさ」の2通りではいずれもロンが H にいる.
しかしルーナは H をより好み, かつ H の優先順位でルーナはロンより上（Lu \succ R）なので, ルーナがロンに正当な羨望を持ち, 公平性に反する.

この例で重要なのは, 制約が属性定員のとき, 実行可能 + 公平 + 無駄のなさ + 個人合理的を満たすマッチングが必ずしも存在するとは限らないということです. 単純定員では必ず存在する一方で, 属性定員では必ず存在するとは限らないことに注意して下さい.

指標A＝（実行可能 + 公平 + 個人合理的）の中で学生最適
ここで A を「実行可能 + 公平 + IR」を満たすマッチング全体とする.
上で列挙した A の候補（6通り）の中で, 全員の選好が H \succ M \succ U で同じなので, 「各学生の割当ができるだけ上になる」ものが学生最適になる.

結論として, 学生最適（A の中で学生最適）は次の1通りである.
  • \begin{pmatrix}R&He&Lu\\M&H&M\end{pmatrix}

実は, 属性定員下のマッチングにおいて, 次の存在定理が成り立つ.

定理（実行可能 + 公平 + 個人合理的）の存在と学生最適
各学校の制約が単純定員または属性定員であるとする. （また選好と優先順位が強選好と強優先順位であるとする.） このとき実行可能 + 公平 + 個人合理的をみたすマッチングが少なくとも一つ存在する. さらに指標Aを「実行可能 + 公平 + 個人合理的」とするとき, Aの中で学生最適をみたすマッチングも存在する.

この定理は, タルスキの不動点定理を用いて証明されます.

タルスキの不動点定理に関する記事はこちらになります

rikida.hatenablog.com

順序・上界/下界・上限/下限・束の定義

マッチング理論

 

この記事ではマッチング理論で活躍する（そもそも経済学が使われる）順序の定義を厳密に行おうと思います. 最後に選好の定義との関連も述べます.

定義半順序
集合 P 上の二項関係 R\subseteq P\times P が半順序であるとは, 任意の x,y,z\in P に対して次を満たすことをいう.
  • （反射律）(x,x)\in R.
  • （反対称律）(x,y)\in R\ \text{かつ}\ (y,x)\in R \Rightarrow x=y.
  • （推移律）(x,y)\in R\ \text{かつ}\ (y,z)\in R \Rightarrow (x,z)\in R.
このとき (P,R) を半順序集合という.
定義記法の置き換え（\geq を使う場合）
半順序関係 R を読みやすくするために, x\geq y \Longleftrightarrow (x,y)\in R と書くことが多い.
定義全順序
(P,R) が全順序であるとは, (P,R) が半順序であり, さらに任意の x,y\in P に対して (x,y)\in R\ \text{または}\ (y,x)\in R が成り立つことをいう. （\geq 記法では x\geq y または y\geq x.）
例半順序 R
\begin{aligned} R=\{& (\text{ばなな},\text{ばなな}), (\text{りんご},\text{りんご}),\\ & (\text{もも},\text{もも}), (\text{めろん},\text{めろん}),\\ & (\text{ばなな},\text{りんご}), (\text{りんご},\text{もも}),\\ & (\text{りんご},\text{めろん}), (\text{ばなな},\text{もも}),\\ & (\text{ばなな},\text{めろん}) \}. \end{aligned}

このとき R は半順序であり, 全順序ではない.

証明
半順序であること, すなわち反射律, 反対称律, 推移律を順に確認する.

(反射律) 任意の x\in P に対して (x,x)\in R を示せばよい. 定義より
(\text{ばなな},\text{ばなな}),\ (\text{りんご},\text{りんご}),\ (\text{もも},\text{もも}),\ (\text{めろん},\text{めろん})\in R
であるから成り立つ.

(反対称律) (x,y)\in R かつ (y,x)\in R ならば x=y を示す. 上で列挙した R のうち, 異なる2元 x\neq y に対して含まれているのは次の5つのみである.
(\text{ばなな},\text{りんご}),\ (\text{りんご},\text{もも}),\ (\text{りんご},\text{めろん}),\ (\text{ばなな},\text{もも}),\ (\text{ばなな},\text{めろん})
これらの逆向き
(\text{りんご},\text{ばなな}),\ (\text{もも},\text{りんご}),\ (\text{めろん},\text{りんご}),\ (\text{もも},\text{ばなな}),\ (\text{めろん},\text{ばなな})
はいずれも R に含まれていない. よって (x,y)\in R かつ (y,x)\in R が同時に起こるのは x=y の場合に限られる.

(推移律) (x,y)\in R かつ (y,z)\in R ならば (x,z)\in R を示す. 非自明な関係（x\neq y）は上の5つなので, y が第1成分として現れる場合のみを見れば十分である. このとき y=\text{りんご} の場合しか起こらない. 実際,
(\text{ばなな},\text{りんご})\in R,\ (\text{りんご},\text{もも})\in R\Rightarrow (\text{ばなな},\text{もも})\in R
であり, 右辺は定義より確かに R に含まれる. 同様に
(\text{ばなな},\text{りんご})\in R,\ (\text{りんご},\text{めろん})\in R\Rightarrow (\text{ばなな},\text{めろん})\in R
であり, 右辺も R に含まれる. それ以外は同時に成立しないか, 自明な場合（反射律）に帰着する.

以上より R は反射律, 反対称律, 推移律を満たすから半順序である.

次に R が全順序ではないことを示す. 全順序なら任意の x,y\in P について (x,y)\in R または (y,x)\in R が必要である. しかし x=\text{もも} , y=\text{めろん} とすると
(\text{もも},\text{めろん})\notin R,\quad (\text{めろん},\text{もも})\notin R
である. よって完備性が成り立たず, R は全順序ではない.
□
この R は「ばなな>りんご, りんご>もも, りんご>めろん」という関係を R として書き下したものである. 半順序として扱うためには, 反射律（例：\text{ばなな}\ge \text{ばなな}) や, 推移律から新たに従う関係（例：\text{ばなな}\ge \text{もも}) も含めて考える必要がある. それらをすべて R に落とし込むと, 上の集合表示になる.
上界・下界・上限・下限
定義上界
半順序集合 (P,R) と部分集合 A\subseteq P に対して, u\in P が A の上界であるとは (u,a)\in R\quad (\forall a\in A) が成り立つことをいう. （\geq 記法では u\geq a\ (\forall a\in A).）
定義下界
半順序集合 (P,R) と部分集合 A\subseteq P に対して, \ell\in P が A の下界であるとは (a,\ell)\in R\quad (\forall a\in A) が成り立つことをいう. （\geq 記法では a\geq \ell\ (\forall a\in A).）
定義上限
半順序集合 (P,R) と部分集合 A\subseteq P に対して, m\in P が A の上限（最小上界）であるとは, 次を満たすことをいう.
  • m は A の上界：(m,a)\in R\ (\forall a\in A).
  • 任意の上界 u に対して (u,m)\in R.
上限が存在するとき m=\sup A と書く.
定義下限
半順序集合 (P,R) と部分集合 A\subseteq P に対して, \ell\in P が A の下限（最大下界）であるとは, 次を満たすことをいう.
  • \ell は A の下界：(a,\ell)\in R\ (\forall a\in A).
  • 任意の下界 v に対して (\ell,v)\in R.
下限が存在するとき \ell=\inf A と書く.
束・有限束・完備束
定義束
半順序集合 (P,R) が束であるとは, 任意の x,y\in P に対して \sup\{x,y\}\ \text{と}\ \inf\{x,y\} が存在することをいう. このとき x\vee y:=\sup\{x,y\},\qquad x\wedge y:=\inf\{x,y\} をそれぞれ結び（join）, 交わり（meet）と呼ぶ.
定義有限束
束 (P,R) が有限束であるとは, (P,R) が束であり, かつ |P|<\infty が成り立つことをいう.
定義完備束
半順序集合 (P,R) が完備束であるとは, 任意の部分集合 A\subseteq P（空集合も含む）に対して \sup A\ \text{と}\ \inf A が存在することをいう.
強選好・弱選好との関係（注意）
強選好と弱選好の定義は, 次の記事でしています！

rikida.hatenablog.com

この定義のもと以下の注意が成り立ちます. 

注意
強選好ならば弱選好であり, 全順序ならば強選好である. ただし逆は一般に成り立たないことに注意する.
また, 半順序ならば強選好とは限らず, 強選好ならば半順序とは限らないことにも注意する.

 

多対一マッチングにおける選好と優先順位

マッチング理論

 

選好と優先順序

多対一マッチングにおける選好とは, 学生が学校をどのように好んでいるかを表すものです.
多対一マッチングにおける優先順序とは, 学校が学生をどのようにランク付けしているかを表すものです.
選好と優先順序は意味合いが異なります.
学校側が学生を一人だけ受け入れるなら誰を優先するかを表すのが優先順序といえます.
一方で, 学校側で選好を定義するには, 学生の部分集合に対して好みを持っている必要があります.
なぜなら考えている対象が多対一マッチングであり, 学校は複数の学生を受け入れるためです.
そのため, 学校が学生に対する選好を考えるのは複雑になりがちなので, 優先順位（一人だけの選好）に制限して考えることが多いです.

選好（優先順序）には弱選好と強選好の2種類があります.

数学的な定義

数学的な定義を以下で与える.

弱選好
定義弱選好
学生 i\in I が学校に持つ選好 R_i \subseteq (S\cup \{\emptyset\})\times (S\cup \{\emptyset\}) が以下の条件を全て満たすとき, R_i を弱選好という. 任意の a,b,c\in S\cup \{\emptyset\} に対して,
  • （反射律）(a,a)\in R_i.
  • （推移律）\{(a,b)\in R_i\ \text{かつ}\ (b,c)\in R_i\}\Rightarrow (a,c)\in R_i.
  • （完備性）(a,b)\in R_i\ \text{または}\ (b,a)\in R_i.
強選好
定義強選好
学生 i\in I が学校に持つ選好 R_i \subseteq (S\cup \{\emptyset\})\times (S\cup \{\emptyset\}) が以下の条件を全て満たすとき, R_i を強選好という. 任意の a,b,c\in S\cup \{\emptyset\} に対して,
  • （反射律）(a,a)\in R_i.
  • （推移律）\{(a,b)\in R_i\ \text{かつ}\ (b,c)\in R_i\}\Rightarrow (a,c)\in R_i.
  • （完備性）(a,b)\in R_i\ \text{または}\ (b,a)\in R_i.
  • （未割当に関する対称律）
    \{(a,\emptyset)\in R_i\ \text{かつ}\ (\emptyset,a)\in R_i\}\Rightarrow a=\emptyset.
  • （未割当以上に関する対称律）
    \{(a,\emptyset)\in R_i\ \text{かつ}\ (b,\emptyset)\in R_i\ \text{かつ}\ (a,b)\in R_i\ \text{かつ}\ (b,a)\in R_i\}\Rightarrow a=b.
弱優先順位
定義弱優先順位
学校 s\in S に対して, R_s \subseteq I\times I が弱優先順位であるとは, 反対称律の条件を除いた全順序の条件を満たすときである.
（強）優先順位
定義（強）優先順位
学校 s\in S に対して, R_s \subseteq I\times I が（強）優先順位であるとは, 全順序の条件を満たすときである.
（補足）R_s が I 上の全順序であるとき, と言い換えてもよい.
選好の記法（\succsim,\ \succ,\ \sim を用いた表現）
定義記法
学生 i の弱選好 R_i に対して, 以下の記法を用いる.
  • a \succsim_i b  \Longleftrightarrow  (a,b)\in R_i
  • a \succ_i b  \Longleftrightarrow  (a,b)\in R_i\ \text{かつ}\ (b,a)\notin R_i
  • a \sim_i b  \Longleftrightarrow  (a,b)\in R_i\ \text{かつ}\ (b,a)\in R_i
ここで,
  • a \succ_i b は「i は a を b より厳密に好む」を表す.
  • a \sim_i b は「i は a と b を無差別とみなす」を表す.
例：ハリーの選好

学校集合を S=\{\text{グリフィンドール},\ \text{ハッフルパフ},\ \text{レイブンクロー},\ \text{スリザリン}\} とする.

例例1. 強選好の例
ハリーはスリザリンはいやだという. これはスリザリンに行くぐらいだったら寮に入らない方がいいと思っていることを意味する.
またハリーはレイブンクローに入るぐらいだったら, 寮に入らないほうがましだと考えているとする.
またハリーはハッフルパフよりもグリフィンドールの方が入りたいと思っているとする.
このときのハリーに関する選好 \succsim_{\text{ハリー}} は次で定義できる.

\text{グリフィンドール} \succ_{\text{ハリー}} \text{ハッフルパフ} \succ_{\text{ハリー}} \emptyset \succ_{\text{ハリー}} \text{レイブンクロー} \sim_{\text{ハリー}} \text{スリザリン}

このとき,
  • 未割当 \emptyset より上（グリフィンドール, ハッフルパフ）では無差別が存在しない.
  • したがって, 未割当より上で強い選好を持つ.
よってこの選好は強選好である.
例例2. 弱選好の例
一方, ハリーが次のように考えているとする.

\text{グリフィンドール} \sim_{\text{ハリー}} \text{ハッフルパフ} \succ_{\text{ハリー}} \emptyset \succ_{\text{ハリー}} \text{レイブンクロー} \sim_{\text{ハリー}} \text{スリザリン}

このとき,
  • 未割当 \emptyset より上に位置するグリフィンドールとハッフルパフが無差別である.
したがって, 未割当より上で無差別が存在するため, この選好は弱選好である.
例例3. ロンの選好
ロンが次のように考えているとする.

\text{グリフィンドール} \succ_{\text{ロン}} \emptyset \succ_{\text{ロン}} \text{ハッフルパフ} \sim_{\text{ロン}} \text{レイブンクロー} \sim_{\text{ロン}} \text{スリザリン}

このとき,
  • 未割当 \emptyset より上はグリフィンドールのみである.
  • その部分では無差別が存在しない.
したがって, ロンの選好は未割当より上で強い選好である.
例例4. ハーマイオニーの選好
ハーマイオニーが次のように考えているとする.

\text{グリフィンドール} \succ_{\text{ハーマイオニー}} \text{レイブンクロー} \sim_{\text{ハーマイオニー}} \text{ハッフルパフ} \succ_{\text{ハーマイオニー}} \emptyset \succ_{\text{ハーマイオニー}} \text{スリザリン}

このとき,
  • 未割当 \emptyset より上にレイブンクローとハッフルパフの無差別が存在する.
したがって, この選好は弱選好である.
グリフィンドールの優先順位の例

学生集合を I=\{\text{ハリー},\ \text{ロン},\ \text{ハーマイオニー}\} とする.

例例5. 強優先順位の例
グリフィンドールが次のように順位付けしており, 無差別が存在しないとする.

\text{ハーマイオニー} \succ_{\text{グリフィンドール}} \text{ハリー} \succ_{\text{グリフィンドール}} \text{ロン}

このとき, グリフィンドールの優先順位は強優先順位（学生集合上の全順序）である.
例例6. 弱優先順位の例
一方, グリフィンドールが次のように考えているとする.

\text{ハリー} \sim_{\text{グリフィンドール}} \text{ロン} \succ_{\text{グリフィンドール}} \text{ハーマイオニー}

この場合, ハリーとロンの間に無差別が存在するため, これは弱優先順位である.
未割当より下は省略してよい

一般に未割当 \emptyset より下に位置付けられているものは省略して書くことが多いです.
例えばハリーの選好が

\text{グリフィンドール} \succ_{\text{ハリー}} \text{ハッフルパフ} \succ_{\text{ハリー}} \emptyset \succ_{\text{ハリー}} \text{レイブンクロー} \sim_{\text{ハリー}} \text{スリザリン}

であった場合は,

\text{グリフィンドール}\succ_{\text{ハリー}}\text{ハッフルパフ}

のように書きます.
未割当より下の順位はマッチングにほとんど影響しないため, この省略が許されていることに注意しましょう. （ただし制約による.）

 

有限束ならば完備束の証明とタルスキの不動点定理の証明

マッチング理論

 

タルスキの不動点定理（証明メモ）

この記事ではマッチング理論において, 最適マッチングを求めるのにしばしば応用されるタルスキの不動点定理の証明を行います. はじめに「有限束ならば完備束」であることを示し, 有限束でもタルスキの不動点定理を使えることを確認します. 次にタルスキの不動点定理を2種類証明します. 後半の有限束バージョンがマッチング理論でよく使われるイメージがあります. タルスキの不動点定理を用いる文献としては, Kamada & Kojima (2024) の学生最適公平マッチング, 安達による学生最適安定マッチング, Hatfield の多対多マッチングの安定マッチングなどがあります.

 

 

命題有限束は完備束である
(P,\geq) を有限束とする. このとき (P,\geq) は完備束である.
証明
n:=|P| とおく. k\leq n とし固定する. |A|=k を満たす任意の A\subseteq P に対して, A に上限と下限が存在することを数学的帰納法を用いて示す.
k=0,1,2 の時は明らかに成立する. 今 k=t\ (n>t\geq 1) を仮定して, k=t+1 の時を示す.

任意に A_{t+1}\subseteq P かつ |A_{t+1}|=t+1 をとる. A_{t+1}=\{a_1,a_2,\dots,a_t,a_{t+1}\} とする.

X:=\{a_1,a_2,\dots,a_t\},\qquad Y:=\{a_{t+1}\}

帰納法の仮定より, X と Y に上限が存在する. それぞれ m',m'' と表す. また束の定義より, \{m',m''\} に上限が存在するのでそれを m とおく. 推移律より m は A_{t+1} の上界である.

S を A_{t+1} の上界全体の集合とする. 任意に s\in S をとる. これから s\geq m' と s\geq m'' を示す.

s は A_{t+1} の上界より, s\geq a,\ \forall a\in (A_{t+1}\setminus\{a_{t+1}\}) (=X) かつ s\geq a,\ \forall a\in \{a_{t+1}\} (=Y) が成立している.

よって s\in S は X の上界でもあり Y の上界でもある. m' は X の上限であり m'' は Y の上限であるから, s\geq m',\qquad s\geq m'' を得る.

よって s\in S は \{m',m''\} の上界である. m は \{m',m''\} の上限なので s\geq m を得る.

s\in S は任意であり, m は A_{t+1} の上界であるから, m は A_{t+1} の上限である. A_{t+1} は任意な P の部分集合である. ゆえに k=t+1 も正しい. 下限も同様に示せる.

よって数学的帰納法を k=1 から k=n まで繰り返せば, 任意の A\subseteq P に対して A は上限と下限を持つ. 従って (P,\geq) は完備束である.
□

 

 

定義タルスキに用いる概念
束（あるいは半順序集合）(P,\ge) に対して写像 F:P\to P を考える.
F が\geの意味で単調写像であるとは, 任意の x,y\in P に対して x\ge y \Rightarrow F(x)\ge F(y) が成り立つことをいう.
また F の不動点とは F(x)=x を満たす P の元 x のことである.

 

 

定理タルスキの不動点定理（完備束版）
完備束 (P,\ge) と単調写像 F:P\to P に対して, A:=\{x\in P\mid F(x)=x\} を F の不動点全体とすると, A\neq\varnothing であり, (A,\ge) は完備束となる.
証明
Step 1. 不動点が存在すること（A\neq\varnothing）.
u=\inf\{x\in P\mid x\ge F(x)\} と定義する. (P,\ge) は完備束なのでこの u は存在する. 任意の x が x\ge F(x) を満たすとき, 定義より x\ge u である. 単調性より F(x)\ge F(u) なので x\ge F(x)\ge F(u) が従う. よって F(u) は集合 \{x\in P\mid x\ge F(x)\} の下界であるから, u\ge F(u) である.

さらに u\ge F(u) と単調性から F(u)\ge F(F(u)) が成り立つ. 従って F(u)\in\{x\in P\mid x\ge F(x)\} が分かるので, 定義より F(u)\ge u である. 以上より u=F(u) となり u\in A. 従って A\neq\varnothing.
Step 2. \inf A と \sup A.
A\subseteq\{x\in P\mid x\ge F(x)\} であるから, 上の議論は \inf A=\inf\{x\in P\mid x\ge F(x)\}\in A も与える.

同様に v=\sup\{x\in P\mid F(x)\ge x\} と定義すると, 同様の議論から v\in A であり, \sup A=\sup\{x\in P\mid F(x)\ge x\}\in A が導かれる.
Step 3. 任意の Y\subseteq A に対し \sup_A Y,\inf_A Y を作る.
(上限の存在).
B:=\{x\in P\mid x\ge y\ \forall y\in Y\} を考える. 任意に S\subseteq B をとる. (P,\ge) は完備束なので \inf_P S と \sup_P S が存在する. 各 s\in S は s\ge y\ (\forall y\in Y) を満たすから, 任意の y\in Y は S の下界である. 従って \inf_P S\ge y\ (\forall y\in Y) であり \inf_P S\in B を得る. また \sup_P S\in B も同様に分かる. よって (B,\ge) は完備束である.

さらに x\in B と y\in Y に対し x\ge y なので, 単調性より F(x)\ge F(y)=y である. 従って F(x)\in B であり, 制限 F':B\to B は単調写像である. Step 1 と同様に p:=\inf\{x\in B\mid x\ge F'(x)\} とおけば p\in \mathrm{Fix}(F') を得る. p\in B なので Y の上界であり, また Y の上界である任意の不動点 q に対して q\ge p が成り立つ. 従って p は (A,\ge) における Y の上限である.
(下限の存在).
C:=\{x\in P\mid y\ge x\ \forall y\in Y\} を考える. 同様に (C,\ge) も完備束である. x\in C と y\in Y について y\ge x なので単調性より y=F(y)\ge F(x) となり, F(x)\in C が従う. よって制限 F'':C\to C は単調写像である. 同様に r:=\sup\{x\in C\mid F''(x)\ge x\} とおけば r\in \mathrm{Fix}(F'') を得る. r\in C なので Y の下界であり, また Y の下界である任意の不動点 q に対して r\ge q が成り立つ. 従って r は (A,\ge) における Y の下限である.

以上より任意の Y\subseteq A に対して (A,\ge) で上限と下限が存在するから, (A,\ge) は完備束である.
□

 

 

定理タルスキの不動点定理（有限束 + 単調増加版）
(P,\ge) を有限束とし, F:P\to P を写像とする. 次を仮定する.

(1) F は \ge の意味で単調である. すなわち x\ge y \Rightarrow F(x)\ge F(y).
(2) F は単調増加的である. すなわち F(p)\ge p\ (\forall p\in P).

このとき次が成り立つ.

(i) 任意の p\in P に対してある k\in\mathbb{N} が存在し, F^{(k)}(p)=F^{(k-1)}(p) となる（反復列は有限回で停止する）.

(ii) さらに p^- を (P,\ge) の最小元とすると, (i) のような k に対して u:=F^{(k-1)}(p^-) は F の不動点であり, 不動点全体 A:=\{x\in P\mid F(x)=x\} の (A,\ge) における最小元である.
補足
有限束は上の命題より完備束である. 従って (P,\ge) には最小元が存在し, p^- を取ることができる.
証明
(1) 反復列が有限回で停止すること.
任意に p\in P を固定する. 背理法で, F^{(k)}(p)\neq F^{(k-1)}(p)\ (\forall k\in\mathbb{N}) と仮定する. 仮定 (2) より任意の k について F^{(k)}(p)=F(F^{(k-1)}(p))\ge F^{(k-1)}(p) である. 従って上の仮定から F^{(k)}(p) > F^{(k-1)}(p)\ (\forall k\in\mathbb{N}) が従う.

ここで任意の a\neq b に対して F^{(a)}(p)\neq F^{(b)}(p) を示す. もしある a'>b' で F^{(a')}(p)=F^{(b')}(p) が起こると, 厳密増加より F^{(b'+1)}(p)>F^{(b')}(p)=F^{(a')}(p) となり矛盾する. よって反復列の項は全て相異なる.

各 k について X_k:=\bigcup_{\alpha=1}^{k}\{F^{(\alpha-1)}(p)\} とおくと, 上の主張より |X_k|=k である. しかし X_k\subseteq P なので |X_k|\le |P| である. k=|P|+1 を取ると矛盾する. 従ってある k が存在して F^{(k)}(p)=F^{(k-1)}(p) が成り立つ.
(2) p^- からの反復で最小不動点が得られること.
(1) よりある k が存在して F^{(k)}(p^-)=F^{(k-1)}(p^-) である. u:=F^{(k-1)}(p^-) とおくと, F(u)=F(F^{(k-1)}(p^-))=F^{(k)}(p^-)=F^{(k-1)}(p^-)=u より u は不動点である.

任意に x\in A をとる. 最小元より x\ge p^- が成り立つ. 単調性から F^{(k-1)}(x)\ge F^{(k-1)}(p^-) を得る. 一方 x\in A なので F^{(k-1)}(x)=x である. 従って x\ge u が従う. よって u は (A,\ge) の最小元である.
□

ポイント支払いの収束

 

生協でカレーを食べ続けると、支払額はどこに収束するのか？

昨日、生協で 1000円のカレーを食べたのですが、ちょうど 生協ポイントが100ポイントあったので使ってみました。

  • 本来：1000円

  • ポイント利用：900円で支払い
    → これは嬉しい。

しかも、900円の10%還元が付いて、90ポイントも貰いました。
これはうれしいな……。

生協Payのポイント還元の仕組み（前提）

私の大学では、学食の支払いで 生協Pay を使うと、

  • 生協Payで支払った金額の 10% がポイントとして付与される

  • そのポイントは 次回の支払いに使える

  • ただし ポイントで払った分にはポイントが付かない

という仕組みらしいです。

※補足：PayPayポイントも同様の仕組み……と思っていたのですが、
2026年2月現在、PayPayポイントにもポイントがつく仕様になっていました。

「毎回ポイントを使う」を繰り返すとどうなる？

カレーを食べ終えてぼーっとしていると、ふと疑問が湧きました。

今ある 90ポイントを次回の支払いに使えば（また1000円のカレーを食べるとして）

  • 次は 910円で食べられる

  • さらにその910円の10%で 91ポイントが付く

次にその91ポイントを使えば……

1000 - 91 = 909 \text{円}

またポイントが付いて（小数点を許すと）

  • 909円払う → 90.9ポイント付く

  • 次は

909.1 \text{円}

払って → 90.91ポイント付く……

支払額の列はこうなる

1000 \to 910 \to 909 \to 909.1 \to \cdots

増えて減ってを繰り返しながら、最終的に どこかに収束しそうだな、と。

ひらめき：漸化式で書ける

いま、n回目の支払いを a_n と置くと、
n回目の支払いでは前回の支払い a_{n-1} に付いたポイント

0.1 a_{n-1}

を使うので、

1000 = a_n + 0.1 a_{n-1}

という漸化式が立ちます。

解くと

a_n = (-0.1)^{n-1} \frac{0.1\times 1000}{1+0.1} + \frac{1000}{1+0.1}

となります。

ここから一般化して考える

以降、一般化して次の仮定のもとで考えます。

  • 買いたい商品は常に同じ（ずっとカレーを買う状況）

  • ポイント還元率 \alpha' は 0 < \alpha' \le 100

問題のセットアップ

商品の値段を x>0 とする。
また還元率を割合で

\alpha := \frac{\alpha'}{100}

と定義する（例：10%なら \alpha=0.1 ）。

  • n回目に支払う金額： a_n

  • 総支払額：

A_n := a_1 + a_2 + \cdots + a_n

また、n回目の支払いで使うポイントを b_n とし、

  • b_1 = 0

  • b_n = x - a_n

と置く。

定理1（毎回ポイントを使うときの支払額）

定理1
任意に n\in\mathbb{N} を固定する。
x>0 、 0<\alpha\le 1 とする。
このとき「その都度ポイント支払い」をするときの n回目支払額 a_n は

a_n = (-\alpha)^{n-1} \frac{x\alpha}{1+\alpha} + \frac{x}{1+\alpha}

定理1の証明

a_k, b_k の定義より

x = a_k + b_k \quad (k=1,2,\ldots,n)

に注意する。
ここで b_k = \alpha a_{k-1} なので

x = a_k + \alpha a_{k-1}

特性方程式を解けば

a_{n+1} - \frac{x}{1+\alpha} = -\alpha\left(a_n - \frac{x}{1+\alpha}\right)

を得る。
c_n := a_n - \frac{x}{1+\alpha} とおくと

c_{n+1} = -\alpha c_n

となり、 a_1=x より解いて

a_n = (-\alpha)^{n-1} \frac{x\alpha}{1+\alpha} + \frac{x}{1+\alpha}

が得られる。■

系1（支払額の収束値）

定理1より、 n\to\infty を考えるとよい。

系1
その都度ポイント支払いしたときの支払額の収束値は

  • \alpha = 1 のとき：発散

  • 0<\alpha<1 のとき：

\frac{x}{1+\alpha}

例：1000円・10%還元の場合

x=1000,\ \alpha=0.1 を代入すると

\frac{1000}{1.1} = \frac{10000}{11} = 909.090909\ldots

つまり最初の疑問の答えは

支払額は 10000/11 に収束する

だったのですね。解決解決……。

でも本当に「毎回ポイント払い」が一番得なのか？

ここで新たな疑問が生まれました。

例えば3回買うとして、

  • 毎回ポイントを使う

    • 1000円 → 900円 → 910円

    • 合計 2810円

一方、ポイントを貯めておいて

  • 1回目1000円、2回目1000円払い

  • 3回目に200ポイント使って800円

だと合計 2800円。

……あれ？
「毎回ポイント払い」って、最安ではないのでは？

そこで私は、

現金の総支払額を最小にする支払い方は何か？

という問題を考えたくなりました。
（※実際には「毎回ポイント払い」にも意味がある。後で述べます。）

記号の導入

総支払金額：

A_n = a_1 + \cdots + a_n

n回目の支払い時に使ったポイント：

b_n
ただし

b_1 = 0,\quad b_n = x - a_n

n回目の支払いまでに使った総ポイント：

B_n = b_1 + \cdots + b_n

なお

B_n \le \alpha A_{n-1}

に注意。

命題1（総支払額を最小にする支払い方の特徴）

命題1
任意に n\in\mathbb{N} を固定する。
総支払金額

A_n = a_1 + a_2 + \cdots + a_n

を最小にする支払方法は、

  • B_n = \alpha A_{n-1} （ n\ge 2 ）

  • B_1=0

を満たす A_n の中で、 a_n が最小になるものに限られる。逆も正しい。

命題1の証明

n=1 のときは支払方法が1通りで、 B_1=b_1=0 を満たすので成立。
以下 n\ge 2 とする。

まず

B_n=b_1+\cdots+b_n = nx-(a_1+\cdots+a_n)=nx-A_n

ゆえに

A_n \text{が最小} \Leftrightarrow B_n \text{が最大}

また、 B_n は使用ポイント総額なので、獲得ポイント総額を超えない：

B_n \le \alpha(a_1+\cdots+a_{n-1})=\alpha A_{n-1}

よって B_n を最大化するには B_n=\alpha A_{n-1} を狙えばよい。

さらに

A_{n-1}=(n-1)x-B_{n-1}

などを代入して整理すると

B_n \le \frac{\alpha(n-1)x+\alpha b_n}{1+\alpha}

よって最大の B_n は

B_n=\frac{\alpha(n-1)x+\alpha b_n}{1+\alpha}

を満たし、かつ b_n が最大になるもの。
A_n=nx-B_n に戻すと

A_n=\frac{nx+\alpha a_n}{1+\alpha}

を満たすものの中で a_n が最小のものと同値。■

系2（最小支払い戦略の形）

系2
n\ge 2 回支払い、商品価格 x 、還元率 \alpha のとき、最小支払い方法は次の通り。

  • \alpha \ge \frac{1}{n-1} のとき
    a_n=0 かつ B_n=\alpha A_{n-1} を満たすもの

  • 0<\alpha<\frac{1}{n-1} のとき
    a_n = x-\alpha(n-1)x かつ B_n=\alpha A_{n-1} を満たすもの

定理2（毎回払いとの差は最大でもこれだけ）

定理2
n\ge 2 回支払い、商品 x 、還元率 \alpha とする。
このとき、「その都度ポイント支払い」と「総支払最小戦略」の金額差は最大でも

\frac{\alpha x}{1+\alpha}

である。

証明（概略）

最小化する支払方法を一つ固定し、それを A_n とする。
系2と定理1から、 \alpha\ge \frac{1}{n-1} のとき差は

\frac{1-(-\alpha)^n}{(1+\alpha)^2}\alpha x

であり、

(1+\alpha)\ge 1-(-\alpha)^n

より、nによらず差の最大は

\frac{(1-(-\alpha))\alpha x}{(1+\alpha)^2}=\frac{\alpha x}{1+\alpha}

となる。
\alpha<\frac{1}{n-1} の場合は省略。■

「毎回ポイント払い」は損なのか？

定理2より、総支払最小の支払い方との差は最大でも

\frac{\alpha x}{1+\alpha}

です。

これは「毎回ポイント払いが劣っている」ことを必ずしも意味しません。
むしろ、

  • 最小戦略は「n回しか買わない」と先に決める必要がある

  • 現実は「いつ買い物をやめるかわからない」ことが多い

という点が重要です。

そのため毎回ポイントを使っておけば、いつ買い物をやめても
損失は最大でも

\frac{\alpha x}{1+\alpha}

に抑えられます。

たとえば \alpha=0.1,\ x=1000 なら

\frac{100}{1.1}=90.9090\ldots \text{円}

つまり「毎回ポイント払い」は、

いつやめても損が大きくなりにくい保険のような支払い方

と考えられるのではないでしょうか。