博弈论课程下周要讲的论文，感觉理解的不错，并且还有所发展，哈哈~~~~
欢迎旁听
><超过两万字了？怎么可能……分两篇吧
College Admissions and the Stabilityof Marriage
D. Gale; L. S. Shapley
The American Mathematical Monthly, Vol. 69, No. 1. (Jan., 1962),pp. 9-15.
Stable URL:
http://links.jstor.org/sici?sici=0002-9890(196201)69:1<9:CAATSO>2.0.CO;2-C
一．大学入学问题
1． 大学
一般情况下，大学都有个Quota，这个Quota假设是根据学校所拥有的师资、教室、设备等各种资源所确定的一个最优的招生数量，即一个最有效率的数量。
大学根据这个Quota从Applicants中选择录取谁或者不录取谁。但是一般它不会只发出正好等于Quota数量的Offer，而是会多发一些，多发的这些是为了弥补一些不确定性而采取的措施。
Uncertainty
①Appliedelsewhere: ifno, then Admit
学生是否申请其他学校 if yes, then ②
②Rank first: ifyes, then Admit
是否把这所学校排在第一位 if no, then ③
③Admit him by the better: ifno, then Admit
是否被其他学生认为更好的学校录取 if yes, then Give up
但是上面这些问题也是很难估计的，所以即使多发一些Offer，一般最后结果也是不等于Quota的，从而造成了学校教育的效率下降。
然后，有另外一个方法可以进一步减少不确定性。就是WaitingList。它可以把那些多发的Offer改成WaitingList，在确定已录人数后再从WaitingList中选择与Quota的差额发Offer。但是这对学生是不公平的，学生因此会付出更多的时间成本和丧失其他学校录取的机会成本。同下面学生所面临的道德问题一样。学生接受而又反悔也会导致学校的时间和机会成本。
2． 学生
假设申请了2所大学A和B，Prefer A to B
Uncertainty
①A录，whatever B；选A
②A没录，B录；选B
③A等待名单，B没录；选等待
④A等待名单，B录：？
if accept B, then；if A offer, then A，but with moral problem 3
if A reject, then B 2
if reject B, then；if A offer, then A 4
if A reject, then NoCollege 0
| A Offer | A Reject |
Accept B | 3 | 2 |
Refuse B | 4 | 0 |
3, 2, 4, 0: Utility of Applicant
Accept B，Maximization Strategy
But, left and down is the most valuable result
3． 本文主题
可以根据每个学生和每个学校对彼此的偏好，确定一种分配方式，得到一个NashEquilibrium，而且这个NE是Pareto Optimal
4． 论文结构
Ⅰ.肯定回答，可以得到NE
Ⅱ.介绍一种方法可以达到NE
Ⅲ．对于Pareto Optimal简单的证明
二．婚姻问题
这是一个相比于大学入学问题简化了的模型，由此可以更容易的理解本文所述的方法。
入学问题：n applicants; m college; q quota for college; 1 quotafor applicants
婚姻问题：1．n boys; n girls; 1 quota （3*3，4*4）
2．n boys; m girls; 1 quota (5*4)
3．n boys; m girls; 2 quota for boys, 1 quota forgirls (3*(6 1))
Assumptions：
⑴A Closed System
系统中人数有限
⑵Ranking,similar to Utility, but 1>2>3
⑶Complete Information
每个人都知道自己和别人的Ranking
⑷rankingis constant,
不随时间改变（排除日久生情和婚变）
⑸one boy’s rankings to each girl aredifference
Similarly, one girl’s rankings are also difference
No tie, 对于任意两个女孩/男孩都可以选出一个更喜欢的
| A | B | C |
α | 1,3 | 2,2 | 3,1 |
β | 3,1 | 1,3 | 2,2 |
γ | 2,2 | 3,1 | 1,3 |
1．Identical Number Model
⑴3 boys: α, β, γ
3 girls:A, B, C
Left: boys’ ranking to girls
Right: girls’ ranking to boys.
Speciality
α, β, γ对同一人的Ranking不同
A, B, C对同一人的Ranking不同
1~3，2~2，3~1
能看出NE不？
NE:
⑴boy with priority: (α,A)( β,B)( γ,C)
⑵girl with priority: (β,A)( γ,B)(α,C)
⑶Second choice: (γ,A)(α,B)( β,C)
证明~~~~
在这个特殊模型中可以得到三个NE，从而回答了第一个问题，在match问题上是有NE的。
同时可以看出具有优先选择权者会占到优势。
条件：在完全信息，封闭系统，不会日久生情，每个人都能做出选择的情况下。
命题1：去主动追求可以得到更加心仪的伴侣。
等待别人追可以让自己成为对方更心仪的。
⑵ 4 boys：α, β, γ, δ
4 girls: A, B, C, D, E, F
能看出NE不？of course no
以前学的博弈论是如何判断一个状态是不是NE，而如何得到一个NE是比较困难的，也没有一般的方法，而本文给出了解决match问题的一个得到NE的方法。下面介绍。
从一方（Boys orGirls，第一个例子得出结论，谁先开始谁可以得到更接近自己Ranking的伴侣）。
比如男生首先开始追（选择）。
１．α, β, γ, δ各自选择第一喜欢的女孩，去追求，
２．然后被追逐的女生留下追她的人中，她相对更喜欢的，而甩掉自己不喜欢的那些
３．被甩掉的男生做第二个选择，也就是去追第二喜欢的女孩
４．这个时候，女孩再从第一轮中留下的和第二轮中的追求者中选择自己相对更喜欢的
５．重复３，４
| A | B | C | D |
α | 1,3 | 2,2 | 3,1 | 4,3 |
β | 1,4 | 2,3 | 3,2 | 4,4 |
γ | 3,1 | 1,4 | 2,3 | 4,2 |
δ | 2,2 | 3,1 | 1,4 | 4,1 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
α | A | / | / | / | B | / | / | / | C | / |
β | A | B | / | / | / | C | / | / | / | D |
γ | B | / | C | / | / | / | A | / | / | / |
δ | C | / | / | A | / | / | / | B | / | / |
A α δ γ
B γ β α δ
C δ γ β α
D β
可以证明这样得到的结果是一个NE。比如……
命题：
２．每个人都有老婆／老公，但大都不是自己最喜欢的，也大都不是最喜欢自己的。
３．被更多女孩喜欢的男孩是占有优势的，即可以娶到更好的老婆，也就是说容易引起女朋友吃醋的男孩是占有优势的。由表格可以看出α,β相同偏好，但结果α比β要好，这在与女生对α的评价比β要好。
４．关于花心，就是见一个喜欢一个的
如果系统中只有一个花心者（或者无法确定自己偏好者），只要按照对方偏好进行选择（选择更喜欢自己的）不会改变结果。即花心不会改变自己的婚姻状况（在不改变异性看法时，而现实中人们往往对花心者降低评价）
| A | B | C | D |
α | X,3 | X,2 | X,1 | X,3 |
β | 1,4 | 2,3 | 3,2 | 4,4 |
γ | 3,1 | 1,4 | 2,3 | 4,2 |
δ | 2,2 | 3,1 | 1,4 | 4,1 |
女生优先情况
α C
β D
γ A
δ B
可以看出在这个例子中无论男生优先或者女生优先结果一样，但这只是个特例。一般情况下是不一样的。在男生优先的情况下结果对于男生是PO的，女生优先的情况下结果对于女生是PO的。第一个３＊３的例子可以作为在这一点上比较一般的例子。
n2-2n 2 rounds
