The gale shapley algorithm
- 2. Agenda ? Stable Marriage Problem ? Introduce ? Gale-Shapley Algorithm ? Algorithm Proof ? Algorithm Big O ? Pseudo Code ? Animation Demo ? Reference
- 3. Stable Marriage Problem ? 亦稱為 Stable matching problem ? 給定兩個相同數量的元素集合 ? 每個元素給對面元素一個喜好排序 ? 讓彼此之間配對找出穩定配對 ? 配對：將兩邊的元素一對一組合成一組
- 4. Stable Marriage Problem ? 配對後需要達成每個人都有彼此的伴侶，並且提 供給雙方的最大利益 ? 穩定配對 – 假設(A,B)是一組配對 – 不存在A男對B’女喜好度大於現任妻子B女 – 並且B女對A’男喜好程度也大於現任丈夫A男
- 5. Stable Marriage Problem ? Stable marriage 的進行方式： – 給定兩組一樣的元素集合, men 與 women – 每個元素給另外一個集合的元素進行喜好順序的排序 – 進行每個元素的配對，依照求婚者喜好最高順序進行 配對 – 配對到兩兩元素間沒有比現在更好的選擇，配對就完 成 – 由上述條件可以知道，如果彼此間沒有更好的選擇， 就代表這兩組元素是穩定配對
- 6. Introduce ? In 1962, David Gale and Lloyd Shapley proved that – For any equal number of men and women, it is always possible to solve the SMP and make all marriages stable
- 7. Gale-Shapley Algorithm Concept ? 有n個男生與n個女生，每個男生將所有女生依據 喜歡順序排成喜好列隊(strictly ordered preference list)，而每個女生也將所有男生依據喜歡順序排成 喜好列隊 ? M (match)配對，是男生集合與女生集合的一個 1 to 1 對應 ? PM(m)=w 與 PM(w)=m，w是m的M-伴侶，m是w的 M-伴侶
- 8. Gale-Shapley Algorithm Concept ? Blocking Pair : 若(m,w)在M中沒有配成一對，m喜 歡w甚於PM(m)，而且w喜歡m甚於PM(w)，則稱 (m,w)是M的阻撓對 ? Stable Match : 若配對M不存在阻撓對，則稱M為 穩定配對 ? Stable Pair : 若(m,w)在某一穩定配對中配成一對， 則稱(m,w)為穩定對，m與w互稱為穩定配偶
- 16. Stable Matching Proof ? 首先，每個男生都該被配到一個女生，這代表配 對過程有正確進行 ? 若有男生沒被配到，表示他被所有女生拒絕 ? 可是女生拒絕他，表示當時已訂婚，又女生一旦 訂婚只會換訂婚對象不會回到自由身 ? 因為男女的總數相同，這會導致矛盾
- 17. Stable Matching Proof ? 假設m喜歡w甚於PM(m)，則在演算中w曾拒絕m ? 當時因w較喜歡m‘而拒絕m，w若有換訂婚對象也 是換得比m’更好的對象 ? 因此w喜歡PM(w)甚於m，因此(m,w)不會是M的阻 撓對，也就是說M沒有阻撓對，M是穩定配對
- 18. Stable Matching Proof ? 假設(m,w')在M中不是一對，在某穩定配對M'中為 一對，而且m喜歡w'甚於w=PM(m) ? m在演算過程中必定曾遭w'拒絕 ? 我們可假設m是整個過程中第一個被穩定對的對 象所拒絕的男人 ? m被w‘拒絕的原因是w’喜歡當時的未婚夫m‘甚於 m=PM′(w′)，又w’是m‘的穩定配偶中最喜歡的(因m’ 不曾被被穩定對的對象所拒絕)，所以m‘喜歡w’甚 於 PM′(m′)≠w′=PM′(m)，所以(m‘,w’)是M‘的阻撓對， M’不是穩定配對，產生矛盾
- 19. Algorithm Big O ? Assuming the same number of proposers and acceptors : – If exactly one proposer gets his last choice woman, he will have proposed n times. – The remaining n?1 men are able to propose a maximum of n?1 times so – (n?1)(n?1)+n = n2?2n+1+n = n2?n+1
- 20. Algorithm Big O ? The Gale-Shapley algorithm terminates after at most n2?n+1 proposals ? Time Complexity : T(n) = O(n2)
- 21. Pseudo Code
- 23. Reference ? https://en.wikipedia.org/wiki/Stable_marriage_problem ? http://www.columbia.edu/~js1353/pubs/tst-ipco99.pdf ? http://mathsite.math.berkeley.edu/smp/smp.html ? http://www.sephlietz.com/gale-shapley/
Editor's Notes
- #4: Finding a stable matching between two equally sized sets of elements given an ordering of preferences for each element. A?matching?is a mapping from the elements of one set to the elements of the other set.
- #5: A matching is stable when there does not exist any match (A,?B) by which both?A?and?B?are individually better off than they would be with the element to which they are currently matched.
- #6: The stable marriage problem has been stated as follows: Given?n?men and?n?women Each person has ranked all members of the opposite sex in order of preference Marry?the men and women together such that there are no two people of opposite sex who would both rather have each other than their current partners. When there are no such pairs of people, the set of marriages is deemed stable.
- #23: 穩定的婚姻問題是經典數學匹配的問題。 目標是找到（男性和女性）兩個集合之間的匹配的穩定。 這運用在許多真實世界的應用中，包括配套畢業的醫學生的醫院工作 每一位男士在所有 ranking 中選擇一位被他排名最優先的女士； 每一位女士將正在追求她的男士與其當前男友進行比較，選擇其中排名優先的男士作為其男友，即若男士優於當前男友，則拋棄前男友；否則保留其男友，拒絕男士。 若某男士被其女友拋棄，重新恢變自由。 在演算法執行期間，男士則依次對最喜歡和次喜歡的女人求愛，一旦被接受，失去自由身，進入訂婚狀態；而女人們則採取「守株待兔」和「喜新厭 舊」策略，對前來求愛的男士進行選擇：若該男子比未婚夫強，則悔婚，選擇新的未婚夫；否則拒絕該男子的求婚。被女友拋棄的男人重獲自由身，重新擁有了追求 女人的權利，當然，新的追求對象比不過前女友。 這樣，在演算法執行期間，每個人都有可能訂婚多次，也有可能一開始就找到了自己的最 愛，從一而終，每訂一次婚，女人們的選擇就會更有利，而男人們的品味則越來越差。只要男女生的數量相等，則經過多輪求婚，訂婚，悔婚和再訂婚之後，每位 男女最終都會找到合適的伴侶，雖然不一定是自己的最愛（男人沒能追到自己的最愛，或女人沒有等到自己的最愛來追求），但絕對不會出現「雖然彼此相愛，卻 不能在一起」的悲劇，所有人都會組成穩定的婚姻。