※ [本文转录自 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