→ hwanger : (a)部份 假設candidate/job為c1,c2,...,cn/j0,..,jn 09/10 00:22
→ hwanger : 就假設c0的喜好排序就是j1,j2,...,jn 並且jk以下就 09/10 00:24
→ hwanger : 不想應徵 而j1的喜好排序是c{j1},c{j2},...,c{jn} 09/10 00:27
→ hwanger : 為免符號混淆 j1的喜好排序改成c{i1},...,c{in} 並 09/10 00:31
→ hwanger : 且c{it}以下就不想應聘 09/10 00:32
→ hwanger : 現在引入imaginary candidate/job Nc1,Nc2,...,Ncn/ 09/10 00:34
→ hwanger : Nj1,Nj2,...,Njn 共2n個節點 對某個c而言 如果js排 09/10 00:37
→ hwanger : 在Njs後面 就代表其實c不想要js這份工作 而對於某個 09/10 00:38
→ hwanger : j而言 如果cs排在Ncs後面就代表j其實不想用cs這個人 09/10 00:40
→ hwanger : 而我們可以改寫c1的喜好排序為 09/10 00:42
→ hwanger : j1,j2,...,j{k-1},Nj1,Nj2,...,Njn,jk,j{k+1},..,jn 09/10 00:43
→ hwanger : 並改寫j1的喜好排序為c{j1},c{j2},...,c{j(t-1)}, 09/10 00:45
→ hwanger : Nc1,Nc2,...,Ncn,c{it},...,c{in} 09/10 00:46
→ hwanger : 其他entities的喜好排序也是依此邏輯修改 09/10 00:49
→ hwanger : 符號還是混亂了 很抱歉 09/10 00:51
→ hwanger : 再去證明按上面所述而排出來的stable matching的確 09/10 00:53
→ hwanger : 滿足原問題的五個條件 細節應該不難補完才對 09/10 00:54
→ hwanger : (b)部份我也是這樣想的 只是中間點點點的部份總感覺 09/10 01:15
→ hwanger : 沒有達到數學上的嚴謹 不過這樣的證明一般還是可以 09/10 01:16
→ hwanger : 被接受的 XD 09/10 01:16
→ hwanger : 補充一下(a)部份 為避免某c比較偏好沒有工作時 所有 09/10 16:31
→ hwanger : 的Nj卻都跑去和Nc媒合 所以每一個Nj的喜好排序為 09/10 16:33
→ hwanger : c1,c2,...,cn,Nc1,Nc2,...,Ncn 相同地 每個Nc都是 09/10 16:34
→ hwanger : j1,j2,...,jn,Nj1,Nj2,...,Njn 09/10 16:35