http://ja.wikipedia.org/wiki/%E5%AE%89%E5%AE%9A%E7%B5%90%E5%A9%9A%E5%95%8F%E9%A1%8C
安定結婚問題の例題に対し、互いに現在組んでいる相手よりも好きであるペア（以下ブロッキングペアとする）が存在しないマッチングを安定なマッチングという。
(中略)
全ての例題について、安定マッチングは必ず存在する。
http://www.msi.co.jp/nuopt/glossary/term_ad874ebcd774bf3bd9a6f06fba1ad54f28e399a9.html
Gale-Shapley(Deferred Acceptance)アルゴリズムにより求まる安定マッチングは，男性にとっての最適解（各男性が安定マッチングの中でとり得る最も良い相手を選んで求まる解）であり，女性にとっての最低解（各女性が安定マッチングの中でとり得る最も悪い相手を選んで求まる解）になっている．アルゴリズム内での男性，女性の役割を交換すれば女性にとっての最適解が求まる．
情報処理 Vol.54 No.10 Oct.2013 P.1064
ボストン方式(中略)第一ステップで、男性全員が第一位の女性にプロポーズする。複数の男性からプロポーズを受けた女性は、その中でもっとも好きな男性とカップルになり、残りの男性を振る。第二ステップでは第一ステップで振られた男性全員が第二位の女性にプロポーズする(中略)以後全員がマッチするまでこれを繰り返す。
男性プロポーズのGSアルゴリズムでは女性側はリストを操作して得する可能性がある。
(逆順)
男性がリストを操作しても得をしない。
以下超訳
ボストン方式は耐戦略性を持たない＝ex.男性の嘘の選好リストによる得の可能性(好印象を持たれていない対象の順位を下げ、好印象を持たれている対象の順位を上げる等の戦術影響)がある。
(耐)戦略性というより戦術レベルだな。
http://www.prefield.com/algorithm/misc/stable_matching.html
通常，安定マッチングは複数（指数オーダ）存在する(中略)
男女のスコア総和を最大化する安定マッチングを最適安定マッチングとよぶ．これは二部グラフの重みつきマッチングに帰着して多項式時間で計算できる．男女のスコア差を最小化する安定マッチングを平等安定マッチングとよぶ．これは NP 困難である．
参考
http://www.living-in-peace.org/_common/img/pdf/ks0904_game.pdf
- StableかつStrategy-Proofなメカニズムは存在しない。
もしも実際のマーケットでウソをつくインセンティブが無視できるほど小さいならば、現実的にはDAアルゴリズムを使うことに重大な問題はない(中略)4000近い病院の中からウソをつくインセンティブを持つのはわずか20から30程度であることが明らかにされた。(中略)マーケットが大きい、つまりマーケット参加者の数が多いと、各病院が自分の報告によりDAアルゴリズムに与えることができる（病院自身に都合のよい）影響は小さくなっていく(中略)大きなマーケットでは、たとえStrategyProofでないDAアルゴリズムを用いたとしても、実際上の問題点はクリアされているということが示唆されている
へー
