※ [本文轉錄自 AfterPhD 看板 #1NmHGhTR ]
作者: ggg12345 (ggg) 看板: AfterPhD
※ 引述《ggg12345 (ggg)》之銘言：
: https://www.youtube.com/watch?v=q4d7fNjCQ4A
: 這是 BBC 影片在 youtube 的放映本.
: 關於 stable matching 的實例, 片中是橋牌的 Queen 與 King 為例.
: 紅磚Queen 對 King(磚 桃 梅 黑桃) 的喜愛次序是 (3 4 2 1)
: 紅桃King 對 Queen(磚 桃 梅 黑桃) 的喜愛次序是 (1 2 3 4)
: K
: 磚 桃 梅 黑桃
: Q 磚 3,2 4,1 2,2 1,1
: 桃 2,1 4,2 1,3 3,2
: 梅 3,4 4,3 2,1 1,3
: 黑 2,3 3,4 4,4 1,4
: 假設 Queen 先對 King 表白喜愛的志願, 結果 黑桃King 收到 3個第一志願,
: 但黑桃King有其對Queen的喜愛志願. 此時, 梅黑 2 Queen就被 磚Queen比下去
: 梅Queen只好改找第二志願(2,1)當第一志願, 就是改找梅King. 此時, 桃Queen
: 表白的第一志願, 因為梅King 的志願喜好恰為梅Queen, 就把桃(1,3)比下去,
: 桃Queen只好改以桃(2,1)為新第一志願改找磚King, 又恰好是磚King的第一志
: 願, 配對就成了.
: 黑Queen的(1,4)落選, 改以(2,3)為第一志願, 但又輸給桃(2,1),就再改(3,4)
: 為第一志願, 此時桃King只有此份表白, 就配對了.
: 最後的配對是(1,1), (2,1), (2,1), (3,4)
: 這個算法先從 Queen 開始表白, 但若先從 King 開始, 得到的 stable matching
: 也是相同的解.
===============
假設先從 King 開始對 Queen 表白. King紅桃 與 King黑桃 都對紅磚Queen
表示喜愛的第一志願, 但 Queen紅磚 反應最愛 King 黑桃, 紅桃King 落選 只好
將紅桃Queen (4,2)改為第一志願. 此時, 因紅磚King以(2,1)表白, 紅桃Queen 最
不喜愛(4,2)紅桃King, 因此紅桃King又落選, 紅磚King 被紅桃(2,1)保留. 黑桃
King只有再將 梅Queen(4,3)改為第一志願, 但又不如黑梅King（2,1)被黑梅Queen
所喜愛, 最後, 紅桃King 只能以(3,4)為第一志願, 在無其他King表白競爭下, 黑
桃Queen 只有接受紅桃King(3,4).
最後的配對依然是 (1,1), (2,1), (2,1), (3,4)
這算法是對稱的, 配對對象是單一的. 又稱 stable marriage.
假設 Queen 是學生要選志願優先入學, King 就是不同學校但也對各個學生做成績
的優先篩選. 例如某校對學生的等第區分：1(總分90以上, X >=90), 2( 90 > X
>=80), 3(80 >X >= 70), 4(70 >X >=60), 5( 60 >X >=0). 假設相同等第的學生
可被學校同樣的接受. 因此同等第的學生可以有很多個, 但學生選校的志願只有一
個. 總分的計算, 各校不同, 是由各校決定並公布的.
學校
A B C D
學生
a (1,1) 2,1 3,1 4,1
b (1,1) 2,1 3,1 4,1
c 2,2 (1,2) 4,2 3,2
d 2,2 (1,2) 3,2 4,2
e 4,3 3,3 2,3 (1,3)
f 4,3 2,3 (1,3) 3,3
g 4,3 2,3 3,3 (1,3)
h 1,4 2,4 (3,4) 4,4
假設各校限收兩名學生, 可能的志願與分發結果如上表.
台灣自從有大專聯考以來, 1950年之後也開始有學生的志願選填. 但當時卻有個
說法就是照前一年度的錄取最低分數排直線式的志願, 每個學生的志願都相同,
學校都是按聯考總分排篩選的次序, 所以高分都是在名校, 排名次序幾乎都無法
突破. 關鍵是各校都按同一套記分公式排篩選的次序, 也就變成聯考分發是總分
決高下. 最敏感的就是分數無法區分高下時, 就無法定高低, 就訂了一堆比序的
辦法.
當12年國教開始時, 幾乎又回到以前的各縣市辦理初中升高中的聯考分發. 但跨
縣市就讀確實不如就地學區入學. 某些高中如同某些大學為了標榜名校, 就比較
偏向按成績高低分發, 完全不考慮學生的意願. 例如降低志願申請某校就被降低
篩選的優先次序. 理論上, 學校如同學生可隨意定其喜好次序, 但使用公共稅務
來源的公立學校似乎不可如此隨意. 但若放任家長隨意決定學校篩選學生的入選
公式, 正如同讓國家命官的公務員放棄監督公共預算的職責.
Shapley 的 stable marriage 算法並沒有讓落選者一直持續使用其無法競爭的
志願與其他競爭者競爭. 相反的, 是讓這回合落選者放棄表白對象, 改用下一個
志願升級為第一志願, 去與其他表白者競爭.
假如各校想打破既定的校名排名競爭, 至少要讓學生選擇該校為第一志願時能給
該生優先的錄取機會, 該校才有可能有學生是第一志願的狀況發生.
學校
A B C D
學生
a (1,1) 2,1 3,1 4,1
b (1,1) 2,1 3,1 4,1
c 1,2 2,2 (3,2) 4,2
d 3,2 (1,2<) 2,2 4,2
e 4,3 (1,3<) 2,3 3,3
f 4,3 2,3 (1,3<) 3,3
g 4,3 2,3 3,3 (1,3<)
h 1,4 2,4 3,4 (4,4)
A校是完全用 總分篩選排序定優先
B, C, D 則是定總分高於3等第者就隨學生的第一志願(1,3<)改列為最優先(1,1)
入選.
================
假如各生志願都相同, 學校篩選學生的計算分數排序也都相同, 教育部規定的
錄取名額對各校都有限制. 名額限制也是會強迫算法改用下一個志願當最優先
的學校申請.
學校
A B C D
學生
a (1,1) 2,1 3,1 4,1
b (1,1) 2,1 3,1 4,1
c 1,2 (2,2) 3,2 4,2
d 1,2 (2,2) 3,2 4,2
e 1,3 2,3 (3,3) 4,3
f 1,3 2,3 (3,3) 4,3
g 1,3 2,3 3,3 (4,3)
h 1,4 2,4 3,4 (4,4)
各校入選的學生就如（4,3) 使用()表示.
================
如果讓各縣市家長會干預學校的計分比序方式, 就目前的已知結果, 一些奇怪不
合理的決策就會讓事情鬧得像一對父子牽驢過河, 把驢子摔進河裡.
當然, 這個算法未必保證最高志願一定會被篩選到.
例如： 原論文舉了一個實例:
A B C D
a 1,3 2,3 (3,2) 4,3
b 1,4 4,1 3,3 (2,2)
c (2,2) 1,4 3,4 4,1
d 4,1 (2,2) 3,1 1,4
[PDF] College admissions and the stability of marriage
http://cramton.umd.edu/market-design/gale-shapley-college-admissions.pdf
台灣的在位者不肯負責做事, 我們就是經歷沒必要的"庸人自擾" !
※ 發信站: 批踢踢實業坊(ptt.cc)
※ 轉錄者: ggg12345 (118.168.148.216), 08/27/2016 13:08:25