イベント / EVENT

Gale-Shapleyアルゴリズムにおいて、８人の間ではこのカップリングは全体最適かもしれませんが、Aは第３希望の女性Yと、Yは第４希望の男性Aとのカップルなので破局を迎える可能性が高いと思われる。A・Y間は不安定マッチングではないのでしょうか。

今回は「各参加者が、すべての異性をリストに書く」という設定のモデルを紹介しました。確かにそれだと、破局を迎えるようなカップルが生まれてしまうかもしれません。しかしより一般的な、「各参加者はマッチしたい相手だけを、希望順にリストに書く （『この人とマッチするくらいなら独身でいるほうがマシだ』という相手は書かなくても良い）」という設定のモデルに対しても、Gale-Shapleyアルゴリズムは安定マッチングを見つけることが知られています。このようなモデルを使えば、破局を迎えそうなペアは初めから除かれたマッチングを計算できるかと思います。

安定結婚問題の例で、男性Aと女性とのマッチングは理論的には安定マッチングなのだと思いますが、現実的に受入れ難いのではないかと思いました。質問というより感想ですみません。

質問１の回答に関連するかと思いますので、ご参照ください。

スライドP17 のA→Yのプロポーズに対して、Yが断るというケースはないのか。

Gale-Shapleyアルゴリズムのルールではそのようなことはありません。誰ともマッチしていない女性は。受けたプロポーズは必ず受ける、というルールになっています。　（質問１の回答も関連してそうなので、ご参照ください。）

スライドP19「GSアルゴリズムの性質」に関して、男女の役割を入れ替えると、安定マッチングが異なる結果のペアリングになる場合がある。と言う点において、
・男側からのプロポーズによるマッチングの結果
・女側からのプロポーズによるマッチングの結果
をさらにマッチングして、男女ともに一番不満が少ない形のマッチングを出力するというアルゴリズムは可能でしょうか？
例えば男側からのプロポーズに従うと、女性Yは一番好きでない人とマッチする形になる。このような不満を解消した場合。

安定マッチングどうしの比較に関しては、男性の満足度と女性の満足度のあいだにトレードオフ関係があることが知られています。すなわち、男性にとってより良い安定マッチングは女性にとってはより悪い安定マッチングである、ということが成り立ちます。ですので、男女全員にとって一番良い安定マッチング、というものは存在しません。
男女双方にとって程良い中間的な安定マッチングを求めようとする研究や、何らかの評価尺度をいれてその意味で最適な安定マッチングを見つけようとする研究などが行われています。（質問１２の回答も関連してそうなので、ご参照ください。）

スライドP19　GSアルゴリズムの性質で男性プロポーズ版アルゴリズムとありますが、女性プロポーズ版アルゴリズム以外に男女にとって最適なアルゴリズムはありますか。

質問４にて回答

スライドP21　「正直が最善の策」はどういうステップを経てそのような結果に到達するのかがわかりません。具体的に示して欲しい。　

「各男性にとっては正直が最善の策」というのは、以下の命題を意味します。「ある入力(各参加者の希望順位リストの組)に対してのGale-Shapleyアルゴリズムの出力マッチングをMとする。ある男性Xだけが希望順位を変更して他の人は変更していないような入力に対してのアルゴリズムの出力をNとする。すると、どのような変更をした場合でも、XにとってNでのパートナーの方がMでのパートナーより好ましいということはない(変更前の希望順位の意味で) 。」この命題は背理法を使って証明されます（Nでのパートナーの方が好ましいと仮定して、矛盾を導きます）。きちんとした証明は、論文でも２～３ページを要する難解なものとなっています。 その非自明性のためか、応用の場面でも、「耐戦略性を周知しているにも関わらず、一定数の参加者が嘘の希望順位リストを提出する」、という現象がみられることが報告されています。
直感的には、Gale-Shapleyアルゴリズムの耐戦略性は、「各男性がある女性とマッチできるかどうかが、その女性にいかに早くプロポーズしたかではなく、どれほど好まれているかによって決まる」ということからきています。早くプロポーズをするからといって優先されることはないので、第２希望などを前にもってきてもメリットはありません。むしろ、前にもってきた第２志望とマッチしてしまうと、本来ならアクセプトされる可能性があったかもしれない第１希望にプロポーズせずにアルゴリズムが終了してしまい、結果が悪くなる恐れがあります。

P27のAECだけで完結する割り当て方はあってはいけない結果なのでしょうか。

AECだけで完結する交換も、安定性を満たしています。講義では省略してしまった事項を以下で補足いたします。
"ブロッキングコアリション"とは、そのグループ内で抜け駆けして交換すると、全員が元の割り当てより良いものを受け取れるようなグループのことです。ブロッキングコアリションが存在しない割り当てを、"安定割り当て"といいます。 "弱ブロッキングコアリション"とは、そのグループ内で抜け駆けして交換すると、グループ内の一部もしくは全部のメンバーが元の割り当てより良いものを受け取り、残りのメンバーが元と同じものを受け取るグループのことです（ブロッキングコアリションは、弱ブロッキングコアリションの特殊ケースです）。この弱ブロッキングコアリションすらも存在しない割り当てを、"強安定割り当て"といいます。
AECだけで完結する交換は、安定割り当てではありますが、強安定割り当てではありません（AFEが弱ブロッキングコアリションとなっています）。
TTCアルゴリズムの出力は、強安定な割り当てであること、さらに、それ以外の強安定割り当ては存在しないことが知られています。

男女の役割を入れ替えても同じ安定マッチングが出てくる条件は何ですか。

男女の役割を入れ替えても同じ安定マッチングが出てくることの必要十分条件は、安定マッチングがその問題に１つしか存在しかないことです。どのような希望順位リストの組に対して安定マッチングが１つになるかということについては、いくつかの十分条件が知られています。例えば、男性全員が同じ順位リスト、女性全員が同じ順位リストをもっているような場合には安定マッチングは１つになります。

ブロッキングを問題ありとする前提より、むしろそれを作り出して解決したほうが安定するような気がする。

そのようなことも研究されています。任意のマッチングから始めて、ブロッキングペアを解消する（その二人を今のパートナーと別れさせてマッチさせる）ことを繰り返して安定マッチングになるように変形していく、というタイプのアルゴリズムが知られています。

最初の二部マッチングモデルで、第１志望４点、第２志望３点、　～２点、　～１点と　得点をつけると、説明されたアルゴリズムモデルで出された結果の得点合計が、最高得点にもなりますか？

必ずしもそうなるとは限りません。しかしそのような最高得点のマッチングは、最大重みマッチングアルゴリズムという別のアルゴリズムで計算できます。最大重みマッチングとは、各ペア（二部グラフとして描いたときの辺）に何らかの価値が付いているようなときに、その価値の和が最大となるマッチングのことです。
二部マッチングモデルで、各ペアに希望順位に従って価値をつける（例えば、XがAの第１志望でAがXの第２志望なら、４＋３＝７点をペア XA に割り当てる）と、得点合計が最高のマッチングは最大重みマッチングとして表せます。これを求める効率的なアルゴリズムがあることが知られています。

こうした理論は、いわゆるマッチングアプリや婚活サイト、就活サイトで応用されているのでしょうか。

国内のアプリやサイトでの応用は把握していませんが、例えば米国のオンラインデーティングアプリ「Hinge（ヒンジ）」は"マシーンラーニングとGale-Shapleyアルゴリズムを用いて、登録者にリコメンデーションを送っている"　と謳っています。

安定マッチングは複数あると思いますが、その中でより良いマッチングを探索するアルゴリズムはありますか。

はい、そのような研究は行われています。 マッチングに対して、各参加者の不満度を、その人がマッチしている相手の順位だとします。すなわち第１希望の相手とマッチしている人の不満度は１、第３希望とマッチしている人の不満度は３という感じです。参加者全員の不満度の総和を最小にする安定マッチングは「最小不満度安定マッチング」と呼ばれており、これを効率的に計算するアルゴリズムが知られています。また、参加者の中で最大の不満度が最も小さくなるような(どの人も大きな不満をもっていないような)安定マッチングは「最小後悔安定マッチング」と呼ばれ、これを効率的に計算するアルゴリズムも知られています。

安定マッチングになっていたとしても、総和としての不満度が大きい場合があるのでは。

不満度の定義にもよりますが、確かに安定性を追求することと不満度の総和を最小化することは必ずしも一致しません。安定性は気にせずに総和としての不満度の最小化を目指すならば、質問１１での回答に説明したような、最大重みマッチングを計算するアルゴリズムを用いるという方法が考えられます。また、安定性を保ちつつ不満度の総和の最小化を目指すならば、質問１３の回答で説明したような最小不満度安定マッチングを計算するという方法が考えられます。

複数の安定マッチングがあった場合はその選択はどのようにするのか。

アルゴリズムを適用する問題の背景に依存して選択されます。例えば、学校選択制度では、"学生側の希望順位が優先されるべき"ということで、学生側最適安定マッチングを求めるアルゴリズム(学生プロポーズ版Gale-Shapley)が使用されています。同様に、研修医配属制度では研修医側最適、学内の進学先割り当てでは学生側最適な安定マッチングが求められています。

安定ではないが、不満度の少ないマッチングをするアルゴリズムは？

質問１０の回答で説明したような、最大重みマッチングを求めるアルゴリズムなどが候補として考えられます。

二部マッチングモデルについて、複数の安定マッチングがある場合について、どのマッチングを選択するかについての合理的な選択方法はあるのか。

質問１２、１５にて回答

すべての安定割り当てのマッチングを洗い出す事はできるのか。複数の安定マッチングがあった場合（ex　男性からプロポーズする場合と女性からプロポーズする場合）どのように選択するのか。

安定マッチングの数は、指数サイズになり得る（組合せ爆発が起こってしまう）ことが知られているので、全ての安定マッチングを列挙することは、計算時間の観点から現実的ではありません。２つ目の質問に関しては、質問１３および１５の回答をご参照ください。質問１２の回答で説明したような安定マッチング集合上の最適化は、この集合がもつ構造的な性質をうまく活用して、効率性を実現しています。

日本で身近な例でこのようなマッチングが社会実装されているものがあれば教えてください。被災地のボランティア割り当てでは？

日本では医師臨床研修マッチング（JRMP）や、大学内での進学選択、研究室配属などに使われています。
ボランティア割り当てについては、それをモチベーションとした研究や論文はありますが、私の知る限りまだ社会実装はされていないようです。

安定マッチングは効用が各人にとって最大なのでしょうか。

効用とは？ 全員の選好を反映させているので、各人にとって効用最大とはならないかと思います。

P49　均衡マッチング　この図から１-１，２-３，３-２　が導かれる理由がよく分からず・・・道に途中から赤い線が出てくる理由も分からず・・・

このゲーム木は、ボトムアップに（後ろ向き帰納法で）各点での最適戦略を計算する過程を表しています。各意思決定点（葉以外の点）から出ている赤い線は、仮にゲームがその点に至った場合に、どちらに進むのがその意思決定者にとってより良いかを示しています。ある点において、どちらの戦略を選んだらより良い結末に辿り着くかを知るためには、その先（その点の下にある各点において）どのような戦略が選択されるかを見ないといけません。
このような計算の過程では、各プレイヤーが最適戦略をとったときには実際には通過しない点に関しても、最適戦略を知る必要があります、それが途中から出ている赤い線に対応しています。（この均衡概念は、"部分ゲーム完全均衡"と呼ばれているものです。）

耐戦略性希望順位を偽ると、なぜ得をしないのか。でもし第２希望で出していたらどういう事が起こり得るか。本人が得しない？全体が得しない？

なぜ得をしないのか、ということに関しては質問６の回答をご覧ください。
嘘の希望順を出した場合には、本人が得しません（マッチする相手が悪くなるもしくは変わらない）。他の人は得をする可能性も、損をする可能性もあります。

P51の良いオファー順の正解を教えてください。

正解のオファー順は一意ではないのですが、例えば最初にp_2が３つのオファーを好ましい順に行い、その次にp_3が２つのオファーを好ましい順に行い、最後にp_1がオファーを行う、という順序に設定すると、均衡マッチングがこの希望順位リストにおける安定マッチングと一致します。

「良い性質を持つ制約」の話の中で、「個」（＝「１対１」の「１」）を「集合」という「１つのまとまり」に置き換えることの意義を教えてください。

制約付きの問題を考えるときには、各個人に対する選好だけではなく、その人たちの組合せ方に対しても選好をもっているため、まとまりとして捉える必要があります。
（質問の意図が十分に理解できていないので、回答になっていないかも知れません）

「オファー順の設計」で取り上げている内容は、「TTCアルゴリズム」で取り上げられた「ペアが成立したら、（マッチングの試行から）抜けていく」というイメージに近いのですが、何が似ていて、何が違うのでしょうか。

確かにこれらの動きは似て見えますね。TTCアルゴリズムでの動きはすべて計算手順の一部であって、アルゴリズム設計者が"与えたもの"であるのに対して、動的マッチングでの「ペアが成立したらマッチング市場から抜ける」というのは、このモデルでのルール、つまり"与えられたもの"である、という点が異なります。

店のシフト勤務（曜日、時間、人員、希望）も計算できるのでしょうか。

勤務スケジューリングをマッチング問題として解けるかどうかは、設定や課される制約にも依存するので一概には言えません。勤務スケジューリングに関しては、オペレーションズ・リサーチの分野などで多くの研究がなされているので、その理論を直接活用する方が適しているかと思います。

初学者がアルゴリズムを学ぶとしたら、何を学ぶと良いでしょうか？（言語？ソフト？）

演習問題付きの教科書を用いて、各アルゴリズムの理論を学び、それを実装して理解を深める、というのを繰り返していくのが良いのかと思います。アルゴリズムを学ぶのためのプログラミング言語はどれでも構わないと思います（各言語メリット・デメリットがあり、人によって意見の分かれるところだと思います）。ポピュラーな言語の方が、参考書やWeb上の情報は多いと思います。

さまざまなマッチング問題があり、また、アルゴリズムがいろいろ考案されていると伺いました。このとき、すべてのマッチング問題に対応できる最強のマッチングアルゴリズムというのはないと思うので、マッチング問題の性質に応じたアルゴリズム選択が問題になると思います。その現実応用のところはどのように取り組めば良いのでしょうか？

応用の場面で解きたい問題にどのモデル・アルゴリズムが当てはまるかを見極めるのは、知識を要することでもあるので、専門家や研究者の役目なのかなと思います。一方、現実問題の特徴や要望を熟知しているのは現場の方たちなので、専門家と関係者が話し合って取り組んでいく必要があると思います。

ビジネスにマッチングを応用する場合には、マッチングに参加する人数をいかに増やすかが重要になると思われますが、参加者の人数やインセンティブを増やすようなアルゴリズムやマッチングの手法はありますか。

アルゴリズム自体によって直接的に参加人数やインセンティブを高めるという方法は思い当たりませんが、長期的に見た場合には、やはり安定で満足度の高いマッチングを出力することが重要なようです。マッチングの実績が良いと参加者が多く集まり、さらに参加者が多くなると良い相手とマッチできると期待してより多くの参加者が集まる、という好循環が生まれることが、実際の市場でも観察されています。

マッチング理論を実生活で利用して得したことはありますか。

残念ながら今のところありません。。。

マッチングを行う際に、声の大きい（我の強い）人の意見を優先してしまう状況が実社会では多々あると思うのですが、そういった部分も考慮してアルゴリズムを組むこともあるのでしょうか。

Gale-Shapleyアルゴリズムでは、どの男性も対等に扱われ、またどの女性も対等に扱われているので、声の小さい人の意見も取り入れたアルゴリズムになっているかと思います。ただ、男性プロポーズ版のアルゴリズムにするか。女性プロポーズ版のアルゴリズムにするか、という点では議論が必要です （つまり、男性にとって最適な安定マッチングを選ぶか、女性にとって最適な安定マッチングを選ぶか）。
実際の応用の場面では、研修医マッチングや学校選択制のように、人と組織のマッチングを考えることが多いのですが、そこでは組織側よりも人側の希望順位がより反映されるアルゴリズムが採用されています。米国の研修医マッチングは、かつては病院プロポーズ版のGSアルゴリズムを用いていましたが、90年代の制度再設計の際に研修医プロポーズ版に変更しています。

保留アルゴリズムの証明は、なにを用いるのですか？背理法ですか？

はい、その通りで、背理法を用いて示せます。仮に、Gale-Shapleyアルゴリズムの出力したマッチングに、ブロッキングペアAXがあったと仮定します。すなわち男性Aも女性Xも、出力でのパートナーより互いを好んでいるとします。アルゴリズムでは男性は好きな順にプロポーズしているので、男性Aが出力でのパートナーよりXを好むいうことは、どこかの時点でAがXにプロポーズして振られたということになります。一方、女性Xが出力でのパートナーよりAよりも好むということは、Xはどの時点でもAやそれ以上の男性からはプロポーズを受けていないということを意味します。これらは矛盾します。

アパートやマンションの部屋を決めるときは、何軒目で決めた方がいいというのはありますか？

これは、「最適停止問題」と呼ばれる、マッチング理論とは別種の問題に関連するものだと思います。 最適停止問題の中での有名な例として、「秘書問題」と呼ばれるものがあります。この設定での最適ポリシーは、"最初の１/e (約３７％) の候補をスキップし、それ以降に、それまで見た最良のものよりも良い候補が現れたら直ちに採用する" というものです。「秘書問題」でお調べいただくとより詳しいことがわかると思います。

マッチングによっての結果と、満足度に関するデータなどがあれば教えてください。（得に医師と病院）

医師臨床研修マッチング協議会のホームページ（https://www.jrmp.jp/#）で「各種データ - マッチ結果・記者発表資料等」のところを見ていただくと、２００３年～現在までの　参加者数・マッチ者数・第１希望マッチ者数（第２、第３、第４以下）　等の数値データを見ることができます。 米国の研修医マッチングでも同様のデータがWeb上で公開されています（http://www.nrmp.org/）。

保育所の割り当ての問題が話題になっている（特に兄弟を一緒にしたいなど）これはアルゴリズムで解決できるのか。

保育所マッチングは研究者も関心を寄せているトピックです．2017年には保育所の入所割り当てを計算するマッチング技術を、富士通研究所、九州大学マス・フォア・インダストリ研究所富士通ソーシャル数理共同研究部門、富士通が共同で開発しています（プレスリリース：https://pr.fujitsu.com/jp/news/2017/08/30.html）。この計算は、「きょうだいの同一保育所入所」などの希望をできる限りかなえるものとなっているそうです。（アルゴリズムの詳細は公開されていません。）

アルゴリズムはどのくらいのデータ量をどのくらいのスピードで計算できるのか。

Gale-Shapleyアルゴリズムは入力サイズに関して線形の計算時間なので、とても高速です。標準的なスペックのパソコンを使っても、参加人者数百人といった規模の問題を１秒以下で解くことができます。TTCアルゴリズムも同様です。 カップルの存在を考慮するようにGale-Shapleyアルゴリズムを改変したRoth-Peransonアルゴリズムは、より複雑なアルゴリズムですが、それでも参加者数百人といった規模の問題を数秒～１分ほどで解きます。

すごく古いアルゴリズムしか存在しないですか？単純すぎるます。もっと新しい、先端の形を聞きたいんです。

今回は分野の礎となっている、単純なモデル・アルゴリズムを紹介しましたが、現在ではより複雑な設定やアルゴリズムがたくさん考案されています。それら多くの先端のアルゴリズムでも、紹介した単純なアルゴリズムのアイデアや構造をベースにしているものが多いです。

腎移植ネットワークの物々交換理論が日本では利用されていない理由はなんでしょうか。

倫理的な問題があり難しいようです。日本移植学会が公開している見解の一部を引用いたします
（http://www.asas.or.jp/jst/news/news007.html）：
"ドナー交換腎移植においては、ドナーが直接自分の近親患者に提供するのではなく、また２つの移植の結果が同等であるという保証がない条件下で行うことから、多くの倫理的問題が存在すると認識せざるをえない。"
"ドナー交換腎移植は医学的・倫理的に大きな問題を含むものであり、個別の事例として各施設の倫理審査のもとに行われるべきものである。したがって、ドナー交換ネットワークなどの「社会的なシステム」によりドナー交換腎移植を推進すべきものではない。"

今回紹介されたアルゴリズムが実際に制度等に取り上げられた実例をあげてください。

Gale-Shapleyアルゴリズムや、その拡張が用いられている例として以下のものが挙げられます：
米国の全国医学実習生マッチングプログラム（NRMP）、
日本の医師臨床研修マッチング（JRMP）
ニューヨークシティ公立学校システム、ボストン公立学校システム（公立学校選択制）
慶應義塾大学理工学部の学科分け
東京大学の進学選択の第二段階

マッチング問題について、計算困難になる場合が多いと思います。計算困難にならないケースの視点から、マッチング問題の対策例を示すことはできないでしょうか？（制約条件を追加する　等）

そのような試みに関して既存の結果は把握しておりませんが、面白くて可能性のある方針かと思います。ただ、制約を加えたりすると、解の候補を少なくしてしまうので、注意も必要です。
例えば、物々交換のモデルでは、交換サイクルの長さの上限を３にすると問題は計算困難になってしまいますが、２にすると多項式時間で解けることが知られています。一方、「長さ３のサイクルを取り入れると、長さ２に限定した場合よりも、交換に参加する人数が大幅に大きい解が存在する」ということも示されています（移植ドナー交換の文脈であれば、移植の件数を大幅に増やせる、ということ）。このようなこともあるので、解の質と、計算しやすさとのバランスを考えて解法を考える必要があります。