アルゴリズムデザイン読書メモ1-2

アルゴリズムデザインを読んでるのですが、
先週に引き続き読書メモがあるので、それを貼っておきます。

アルゴリズムデザイン: Jon Kleinberg, Eva Tardos

以下、メモ。

■G-Sアルゴリズム
日本語の助詞が絶対におかしかったり、
言葉が足りないために意味が一意にならない部分を補った。

すべての男性m∈Mとすべての女性m∈Wは自由な身であると仮定する。
Whileすべての女性にはプロポーズしていない自由の身の男性mがいる
　そのような男性mを選ぶ
　wをmの好意順リストでmがまだプロポーズしていない女性の中で、最も好きな女性とする
　mがwプロポーズする
　If wが自由な身である then
　　(m, w)は婚約する
　Else
　　wは現在m'と婚約しているとする
　　If wは、mよりm'が好きである then
　　　mは自由な身で在り続ける
　　Else
　　　（wはm'よりmが好きである）
　　　(m, w)は婚約する
　　　m'は自由な身になる
　　Endif
　Endif
Endwhile
婚約のペアの集合Sを返す。


■解答付き演習1の設定
n人の男性と、n人の女性がいる。

各男性は全女性の好意順リストをもち、
各女性は全男性の好意順リストをもっている。

また、2n人の集合は「良い人」と「悪い人」に分けることができる。
良い人は、男女共にk人ずついるとする。

このとき、誰もが悪い人よりも良い人と結婚しようとする。
そのため好意順リストでは必ず良い人が悪い人より先に来る。

とする。

■解答付き演習1の問い
いずれの安定マッチでも、良い男性は良い女性と結婚することになる、ことを示せ。

■「！」：解答付き演習1の解答法のポイント
命題が真で無いと仮定し、その仮定の矛盾点を示す。

■解答付き演習1の解答
「いずれの安定マッチでも、良い男性は良い女性と結婚することになる」が真ではない時として、
「いずれの安定マッチでも、良い男性は良い女性と結婚することになるとは限らない」という状況を仮定できる。

このような仮定が真である場合には、
「良い男性と悪い女性の組」と「悪い男性と良い女性の組」が
少なくとも一組づつ、存在することになる。

このとき、少なくともこれらの組の間には不安定性があると言える。

なぜなら、「良い男性が良い女性と組になりたい」と考えており、
「良い女性が良い男性と組になりたい」と考えており、
良い男性と良い女性のニーズが合致してしまうからである。

最終的にいずれの安定マッチングも、良い人同士が組になり、悪い人同士が組になる。

ゆえに、「いずれの安定マッチでも、良い男性は良い女性と結婚することになるとは限らない」
という仮定は偽であり、仮定は成立しない。
したがって、命題は正しいと言える。

■記号「∈」と「⊆」
前者は、左辺の要素が、右辺の集合の元であることを表す。
後者は、左辺の集合が、右辺の週報の部分週報であることを表す。

■解答付き演習2の設定
禁止されている男女ペアの集合Fがあるとする。
つまりn人の男性の集合Mと、n人の女性の集合Wにおいて、
結婚が許されないペアの集合「F ⊆ M×W」が存在するということである。

各男性mは、すべての(m, w)!∈Fである女性の好意順リストをもち、
各女性wは、すべての(m, w)!∈Fであ男性の好意順リストをもっている。

■解答付き演習2の設定における安定マッチング
以下が、いずれも真ではないときに、一般に安定であると呼ばれる。
ただし、以下の定義では、安定マッチチングが必ず完全マッチングになるとは言えない。

1、これまでと同じ不安定性
(m, w')!∈Fであり、「mはwよりw'が好き」かつ「w'はm'よりmが好き」であるような
2つのペア(m, w)と(m', w')がS(= M×W)に存在する

2、既婚女性と独身男性の不倫の可能性による不安定性
(m', w)!∈Fであり、m'はSのどのペアにも含まれず、
かつwはmよりm'が好きであるようなペア(m, w)∈Fと、m'が存在する。

3、既婚男声と独身女性の不倫の可能性による不安定性
2の反対。省略。

4、未婚の男女の結婚可能性による不安定性
(m, w)!∈Fであるが、Sのどのペアにも含まれないような、
男性mと女性wが存在する。
# 禁止されてなければ結婚するし

■解答付き演習2の問い
どのような好意順リスト、および、禁止ペア集合に対しても、安定マッチングはいつも存在するか？

■「！」：解答付き演習2の解答法のポイント
以下のいずれかで解答を導く

1、任意の好意順リスト、および、任意の禁止ペア集合に対し安定マッチングを求めるアルゴリズムを提案
- より単純な条件を満たすアルゴリズムを動作させ、うまく動いていない部分を変更する。

2、「安定マッチングが存在しないような好意順リスト、および、禁止ペア集合」の反例を与える

■解答付き演習2の解答
1、アルゴリズムの提案

単純な条件を満たすG-Sアルゴリズムを動作させてみる。
すると、「Whileまだ全ての女性にプロポーズしていない未婚の男性mがいる」
というWhileループの条件がうまくいかない。

実際には、「全ての女性」ではなく「すべての(m, w)!∈Fである女性」である必要がある。

そこで、「Whileまだ『すべての(m, w)!∈Fである女性』にプロポーズしていない未婚の男性mがいる」
というように制約を厳しくしてみる。

この場合でも、
G-Sアルゴリズムの定義(1.1)(1.2)(1.3)はそのまま成立する。
また、このような拡張をおこなうと、得られるペアの集合は、
完全マッチングであるとは必ずしも言えない。
そのため、(1.4)以降は検証できない。

従って、本アルゴリズムは「出力が安定マッチングになる」
というところまで言えれば十分だと言える。

付け加えた制約によって、出力が安定マッチングになるかは
「解答付き演習2の設定における安定マッチング」で示した、
4種類の不安定性がいずれも成立しないことを示せば良い。

1、(m, w')!∈Fであり、「mはwよりw'が好き」かつ「w'はm'よりmが好き」であるような
2つのペア(m, w)と(m', w')がS(= M×W)に存在するとき、
アルゴリズム的にはmがwより先にw'にプロポーズしたが断られたことになる。
さらに、「wはm'よりも好きなm」のプロポーズを断ったことになる。
これはアルゴリズムに矛盾するので、この不安定性はない。


2、既婚女性と独身男性の不倫の可能性による不安定性
(m', w)!∈Fであり、m'はSのどのペアにも含まれず、
かつwはmよりm'が好きであるようなペア(m, w)!∈Fと、m'が存在するとすると、
未婚の男性m'がいて、そのm'は(m', w)!∈Fであるwにプロポーズしたが断られ、
かつ、「wはmより好きなm'」のプロポーズを断ったことになる。

3、既婚男声と独身女性の不倫の可能性による不安定性
2を裏返せば良い。省略。

4、未婚の男女の結婚可能性による不安定性
(m, w)!∈Fであるが、Sのどのペアにも含まれないような、
男性mと女性wが存在する場合、アルゴリズム的には
男性mが女性wに告白してしまい、その瞬間wは婚約することになるので、
未婚ではいられない、ゆえに、このような不安定性はない。

■演習問題1
以下の命題は正しいか。正しければ理由を述べ、間違っていれば反例を与えよ。

「安定マッチング問題のどのインスタンス」に対しても、mがwの好意順リストで最高位であり、
かつwもmの好意順リストで最高位であるペア(m, w)を含むような安定マッチングが存在する。

■演習問題1の解答
今回は、「「安定マッチング問題のどのインスタンス」にも、必ずペア(m, w)を含むような安定マッチングが存在する、わけではない」ことを示す例を出す。

m1 : [w2, w1]
m2 : [w1, w2]
w1 : [m1, m2]
w2 : [m2, m1]

このような好意順リストをもつ男女間の安定マッチング問題は、
GSアルゴリズムに従うと、男女が両思いにはならないので、
命題に矛盾する例の一つと言える。

ということで、反例を与えることができた。

■演習問題2
以下の命題は正しいか。正しければ理由を述べ、間違っていれば反例を与えよ。

mがwの好意順リストで最高位であり、かつ、wもmの好意順リストでで最高位である
「安定マッチング問題のインスタンス」に対して、全ての安定マッチングSはペア(m, w)を含む。

■演習問題2の解答

このような「安定マッチング問題のインスタンス」は、
GSアルゴリズムに従って操作してあげるとペア(m, w)ができる。

mからwにアプローチしても、wからmにアプローチしても、
アプローチされた側は、自分の好意順リストの最高位の候補から
告白たのだからそれを受け入れっぱなしになる。

よって、命題は正しいなぁと分かる。

■演習問題3
問題文が長いので省略。

1、任意のテレビ番組の集合と付随する任意の評価点の集合に対して、
安定なスケジュール対を求めるアルゴリズムを与えよ。

2、安定なスケジュール対が存在しないテレビ番組の集合と付随する
任意の評価点の集合の例を与えよ。

■演習問題3の解答

23ページの上から4行目に「以下の2つのいずれかを示せ」と書いてあるので、
(b)の「安定なスケジュール対が存在しないテレビ番組の集合と付随する評価点の集合の例を与えよ」をやってみる。

以下のような評価点の順になっているような集合を考える。

p1 > q1 > p2 > q2

そうすると、p社は「p1 > q1」と「p2 > q2」にしようとするし、
Q社は「p1 > q2」と「p2 < q1」にしようとして、収束しない。

ということで(b)を示せたんじゃないかな。

以下つづく。