【🎥《數毒求戀必修班》-- Gale Shapley演算法】


天下間芸芸眾多男女之間的姻緣,到底有沒有一套做法或算式,達到最多人都滿意的狀態?

在我們講述數學家的研究前,讓我們做個簡單的演算。在影片中,有3位男士及3位女士,假設男喜歡女,女亦喜歡男,我們要求他們每人,從3名異性中按喜好排序,最不喜歡的排1,最喜歡的排3。

男A選擇次序為:女Y > 女X > 女Z
男B選擇次序為:女X > 女Y > 女Z
男C選擇次序為:女Y > 女Z > 女X

女X選擇次序為:男A > 男C > 男B
女Y選擇次序為:男A > 男B > 男C
女Z選擇次序為:男B > 男A > 男C

假設男士主動追女仔,跟影片內有少少區別,如果我們把全部資料輸入電腦,那麼,電腦內的Gale-Shapley Algorithm會如此演算:


  1. 男A首選女Y,女Y這時單身,男A和女Y一起;


  2. 男B首選女X,女X這時單身,男B和女X一起;


  3. 男C首選女Y,女Y這時已和男A一起,女Y就根據她自己的喜好去秤:她喜歡男A多於男C,因此她不為男C所動。(如有被比更高分的人來接觸她,那麼,她便會跟現任分手,然後接受新戀情。)


  4. 男C次選為女Z,女Z這時單身,男C和女Z一起。

到這時3對男女已全部配對:

男A(3) 女Y(3)
男B(3) 女X(1)
男C(2) 女Z(1)
讓我們看看他們的滿意程度。追到首選為3分,次選為2分,如此類推(見上述括號內分數),換言之,整體分數愈低,滿意程序愈高。男A和男B均是3分;男C 2分,即是男士的整體滿意度為8分。再看看女士的滿意程度。女X配對男B,但男B只是她的第三選擇,得1分;女Y配對男A,男A是她的首選,因此有3分;女Z配對男C,但男C是她的第三選擇,得1分。女士的整體滿意度為5分,比起男士的8分,明顯較不滿意。

現在我們演算一下女方主動的情況。


  1. 女X首選男A,男A這時單身,女X和男A一起;


  2. 女Y首選男A,男A這時已和女X一起,男A就根據他自己的喜好去秤:他是喜歡女Y多過現任的女X,因此他轉軚,甩掉女X,和女Y一起;


  3. 女Z首選男B,男B這時單身,女Z便和男B一起;


  4. 再來新一輪。女X上一輪被甩,現在單身,她次選是男C,男C現在單身,二人便在一起。

這時3對男女亦配對完畢:

女一(2) 男三(3)
女二(3) 男一(1)
女三(3) 男二(1)

今次男方的整體滿意度為3+1+1=5;女方則為2+3+3=8。這次,女方的整體滿意度高於男方。

Gale-Shapley Algorithm的一個結果,是主動一方的整體滿意度,會相等或多於被動一方,萬試萬靈。這是否好有啟示呢?

【再談Gale Shapley演算法】


數學上著名的演算法Gale Shapley演算法,是美國數學家David Gale和Lloyd Shapley在1962年發明,是一種尋找穩定婚姻的策略。只要男女各有相同人數,不論他們的偏好,運用這個策略,總會得出穩定的配對。

什麼是穩定的配對?
如果M(男)跟W(女)是穩定情侶,即以下起碼其中一項是成立的。


  • M喜歡W多與其他所有女生,或


  • 如果M喜歡另外一個女生W’多於W,那W’就比較喜歡他現任的伴侶多於M。反之,如果從女性角度出發,亦然。

演算前設定


  • 一共有相同數目的男跟女(n男n女)


  • 假設全部都是異性戀


  • 每位男士都按照自己喜好把n位女士給分數(1,2,...,n),數字不能有重複


  • 女士一樣,按照喜好把n位男士給分數


  • 假設男士是採取主動的一方

演算過程


  1. 每一位男士都向自己的第一志願提出邀請。


  2. 收到邀請的女士會從中選擇自己排分最高的男士,然後接受。其他的便拒絕。(如果得一位男士邀請自己,那一定要接受啊。)


  3. 還未被配對好的男士向自己的次選提出邀請。


  4. 如果女士還是單身,或新來邀請自己的男士比現任高分,女士便會接受邀請,其他的便會拒絕或跟現任分手。


  5. 重複3,4直至每一位男士都跟一位女士配對好。

2012年Shapley和另一位經濟學家Alvin Roth獲頒諾貝爾經濟學獎(當時David Gale已離世),以表揚他們的「穩定配對理論 (Theory of stable allocation)與市場設計的實踐 (Practice of market design)」對人類作出重大貢獻。

Gale Shapley演算法,總是有利於採取主動的人。這種撮合的婚姻都很穩定,不論哪位配偶有多想分手,其另一半都不希望和現有配偶離婚。不過,現實生活又豈是如此理想?一旦被理想伴侶拒絕,有人會寧願選擇單身;而且人心是會變的,今天喜歡,明天可能又貪新厭舊了。

這項演算法後來發展出其他用途,除婚姻外,用於醫生向醫院求職,住客物色房子居住,學生升學分配學校,等。

【🎥《數毒求戀必修班》-- 最佳停止策略】


第一次拍拖的年輕人,有些會覺得同對方一起是最開心,好心急想立刻結婚;也有些人對婚姻有恐懼,覺得遇到的人總不是最適合的,拍二十萬次拖都不願意結婚。究竟在甚麼時候才停止再選擇,一心一意與目前伴侶結婚才最適合自己?原來數學上有所謂「最佳停止策略」,一齊來看看數學Miss如何計算這條數。

【詳談最佳停止策略-拍幾多次拖先好穩定下來?】


在愛情上,假設一生會遇到10個對象,見合適即結婚,伴侶見你不結即分,休想吃回頭草。到底跟第幾個人結婚,才比較保證沒有揀錯?

其實是有數計的。 最佳停止策略是由一系列的排列(Permutation)及人性的合理選擇組成。先不說10個,以最新一集《必修班》提出,「假設一生有緣份與3個心儀對象談戀愛」的簡單例子來說明。3人各有自己的性格,有些較適合你,有些較不適合。所以適合程度分為1至3分,3分是最夢寐以求的對象。但你一天未認識未來的人,一天也不知道現在的伴侶是不是最高分最適合你的那人。所以我們要考慮所有心儀對象的適合排列可能性:

3個心儀對象的話,適合排列可能性有3! = 6個。

策略有3種:

i. 不用試水溫,與第一個心儀對象結婚。這是一個比較省時的抉擇,好處就是你會比較早婚,好命的話可以早點生小孩或把時間放在事業或其他重點上。但由於你來者不拒,所以你遇到最適合的人的機會率便是:P(3是你結婚伴侶)=2/6=1/3。

ii. 第一個拍拖對象是用來試水溫的,之後遇到比第一個更適合的便結婚。

*你的標準是1,而2>1,所以在這個時間上的你會覺得2已經很適合結婚而不想錯過他。

**你的標準是2,你會放棄比你的標準差的1。然後等待3的出現。

***你的標準是3,之後遇到1或2你都不會甘心,但最後總也想有伴侶渡過餘下光陰(對,就是排除一世單身的可能性)所以也會選擇最後一個作結婚對象。

這個策略的話,會遇到最高分(3)的機會率是:3/6=1/2。

iii. 最後一個策略是用頭兩個對象試水溫,換言之,你的結婚對象便是最後的一個,遇到3的機會率便是2/6=1/3。

結論:當n是3,最佳停止策略大概是33%。

再來一個例子,假設一生會遇到心儀對象數目:4。他們在你生命中出現次序的排列可能性有4!=24個。

策略有4種:

i. 停止策略(試水溫數目):0

得到4做終身伴侶可能性:6/24=1/4

ii. 停止策略(試水溫數目):1

得到4做終身伴侶可能性:11/24

iii. 停止策略(試水溫數目):2

得到4做終身伴侶可能性:10/24=5/12

iv. 停止策略(是水溫數目):3

得到4做終身伴侶可能性:6/24=1/4

結論: 當n是4,最佳停止策略大概是在25-50%之間。

如此類推,一生會遇到10個對象的話: n是10 ,最佳停止策略大概是在30-40%之間。

這個便是數學世界中的最佳停止策略(Optimal Stopping Strategy),估計相遇數目愈多,演算也過程也愈複雜,需要用電腦來幫助計算。當n趨向無限,得到n是終生伴侶的機會率最高的為人數數目的1/e,約等於0.368 或約37%。換言之,如果你預計會跟n名異性拍拖,頭 nx37%個怎也不結婚,用來介定自己的擇偶標準。在之後遇見的人中,選擇第一個比標準好的人,最有機會會是你的真命天子/女。

【玩啤牌了解你的婚姻恐懼指數】


遊戲好簡單,首先從一副啤牌中抽出A到10, 十張牌。把他們洗勻,然後倒轉放下。這10張牌從左到右代表你會遇到的10個約會對象。A即是1,最低點數,10是最高點數。

目的:希望抽到最高點的一張牌,10,然後跟他/她一起結婚生活。

規則:從左邊開始抽。頭數張牌你可以選擇只與他們約會,而不作任何婚姻承諾。當中最大點數的便是你選擇結婚對象的標準點數。

然後再順着開餘下的啤牌,當開到第一張比起你標準點數大的,遊戲便結束,那張牌便是你的結婚伴侶。以下例子只是其中一種排列可能。

例子1:

若果你不用建立標準,那麼第一張牌便是你的結婚伴侶。

結婚伴侶:2

例子2

若果你抽四張牌只作約會及建立標準用途,那麼頭四張的最大點數便是你的標準,

標準:8

之後一抽倒比標準大的數便是你的結婚伴侶。

結婚伴侶: 10

例子3

若果你選擇抽九張牌作建立標準用途,

標準:10

那麼最後一張牌便會是你的結婚對象。

結婚伴侶: 6

例子4

若果只作約會及建立標準用的頭數張牌已經包括10,那麼你的結婚伴侶亦都會是最後一張。(因為你的標準是10,之後怎樣約會也不會覺得滿意,但你總也想有個伴,所以去到最後一張你便會定下來結婚)。

嘗試跟朋友玩玩,如果他選擇多張啤牌只作約會及建立標準用,代表他的婚姻恐懼指數頗高。 如果他選擇啤牌的數目小,代表他的婚姻恐懼指數相對低。

你選擇抽幾多張啤牌去只作約會,而不作任何婚姻承諾,便會決定你結婚伴侶啤牌的點數。數學界的「最佳停止策略」,便是上兩篇文章總結的:37%。

最佳的停止策略,還會用在面試職場上。假如你是一位僱主,要見十個應徵者,假設你只能見一次,見好即請,應徵者見你不請,休想會再來。你需要做的便是頭三個不請,用來組織自己的標準。從第四個應徵者開始找到你認為好過頭三個的,便立刻請。

參考文獻:

羅勃‧依斯威、傑瑞米‧溫德漢 (2014)。一條線有多長?(蔡承志譯)。台灣﹕臉譜出版。(2002年)

【🎥《數毒求戀必修班》-- 愛情命題邏輯】


每逢情人節、聖誕節、生日等大日子,男士送貴重禮物給女仕,(好像是)愛的表現。鑽石一向被包裝成永恆的愛,卻價值不斐⋯女仕一想到便雙眼閃光,男仕一想到立即上呼吸道感染病發。但假若不送的話,又是否代表愛意不再?

今次阿基米德及其女友Yuler遇到這邏輯難題了,看看 Miss Wong 怎樣幫他們解拆?

【用邏輯化解愛情陷阱】


「不買鑽石等於不愛他?傻的嗎?不愛他才不買鑽石! ! !」 在解釋這命題邏輯轉換之前,我們先來了解什麼是命題及命題的四種形式。

命題 (Proposition) 是推理邏輯哲學的術語,具備以下兩個條件:

1. 表達內容的語句

2. 能夠被判斷是真還是假 (True/False)

以下是命題的例子:


  • 我的媽媽是一名女性(T)


  • 從地球上看,太陽是從東方升起(T)


  • 一個三角形內有五隻內角(F)


  • 蘋果不是食物(F)

以下的例子並不是命題:


  • 愛情小短篇(這只是一個名字,本身沒真假可言)


  • 「此路不通」(不能定真假)


  • 累若品祝王二人開(只是文字的堆砌,並沒有內容)

而每一條命題都可以演繹成四個形式:

一. 最常見直接的便是「原命題」:若P,則Q。當中P是命題的條件/前提,而Q便是命題的結論。我們在此假設原命題全是真的(T)。

(i) 若「送鑽石」,則「愛你」。

(ii)若「上堂」,則「想pass」。

(iii)若「m, n都是單數」,則「m+n是雙數」。

二. 第二種形式是「逆命題」:若Q,則P。

(i)若「愛你」,則「送鑽石」。🤔🤔

(ii)若「想pass」,則「上堂」。🤔🤔

(iii)若「m+n是雙數」,則「m, n都是單數」。🤔🤔

三. 第三種是「否命題」:若非P,則非Q。

(i)若「不送鑽石」,則「不愛你」。😨😨

(ii)若「走堂」,則「不想pass」。😨😨

(iii)若「m, n非全是單數」,則「m+n是單數」。😨😨

四. 第四種是「逆否命題」:若非Q,則非P。

(i)若「不愛」,則「不送」。

(ii)若「不想pass」,則「不會來上堂」。

(iii)若「m+n是單數」,則「m, n兩者非同時單數」。

聰明的你應該感覺到,以上三個例子中的「逆命題」及「否命題」都是怪怪的。事實上,如果「原命題」是真實(T)的話,只能推論到「逆否命題」亦是真實(T),並不能推論出「逆命題」及「否命題」的真實性。

(i)若「愛你」,不一定「買鑽石」,可以「煮飯給你吃」也可以「保險受益人寫你姓名」。

(ii)若「想pass」,不一定會「來上堂」,可以「覺得自修比較有效率而走堂」,也可以「因為不舒服而走堂」。

(iii)若「m+n是雙數, 例: m+n=16」,不一定「m,n都是單數」,可以「m, n兩者都是雙數,例:m= 4,n=12」。

像Miss Wong 在【🎥《數毒求戀必修班》-- 愛情命題邏輯】 來的圖像解釋:

• 假設原命題是T: 那麼在P的範圍內,就一定會在Q的範圍內。

• 逆命題便是F:在Q的範圍內,不一定會在P的範圍內。

• 否命題亦是F:不在P的範圍內,就不一定會不在Q的範圍內。

• 逆否命題是T:而不在Q的範圍內,就一定不會在P的範圍內。

所以,將「原命題」等同「否命題」或「逆命題」是不正確的 。前者是否定前提,後者是倒果為因,兩者都是毫無意義的。偏偏,這兩個邏輯謬誤就是坊間最常見的:

• 社交媒體常流傳的「聰明人會比較晚睡」⋯⋯然後你會見到有人分享並說,「哈哈,我晚睡,所以我聰明~」(倒果為因的謬誤)

• 電視或報章上看到「若地方A跟國家B打好關係, A一定會發展迅速。」⋯⋯然後某某政治家便會說「若地方A不和國家B打好關係, A的發展一定一落千丈。」(否定前提的謬誤)

參考文獻:

吳作樂、吳秉翰 。你沒看過的數學。台灣﹕五南圖書出版古股份有限公司。(2015年)

【生活上你我都有機會犯的謬誤】


謬誤(Fallacy) 是指錯誤的觀念或推理言論。有些謬誤很容易就被直覺發現不合邏輯,有些則比較難。不容置疑的是,若不動用腦袋,培養好自己及下一代的數理邏輯能力,生活上或整個社會繼續被謬誤侵蝕下去,輕則笑話連篇,重則人民獨立思考能力下降,被某些掌權階層的荒誕規條控制着,個人自由及基本生活條件長遠被剝削。

除了上帖文的「否定前項」及「倒果為因」外,還有以下數種常見的謬誤:

輕率概化/以偏概全(Hasty Generalisation)

只發生了一次或少數次數的情況,便輕率地推廣到所有情況。


  • 兩次表白都被拒絕,所以阿德他認為以後所有女生也會拒絕他。


  • 弟弟偷吃雪糕,被媽媽發覺。弟弟說姐姐上次偷吃雪糕也沒有被媽媽責罵,所以媽媽今次不應責罵自己。


  • 有很多初接觸數學證明的學生也會犯同一個錯誤,就是隨便舉出一兩個通行的例子,便結論句子是合規格的。

此題若要真正嚴謹地證明,則要用反證法證明。可按此看解答方法。

訴諸權威(Appeal to Authority)

一看到理論是來自權威人士便覺得一定是對的,不加思考就完全相信。


  • 很多時父母會比較忙碌,看到小朋友在做一些自己不喜歡的事,只說「不行」而沒有耐性說出原因。久而久之,很多人被養成一遇到别人挑戰便不思考的習慣,只說:「因為我父母(或老師,或老闆)說不行,所以不行。」。並沒有思考當中的原因。結果會打擊與生俱來的創意及行動力。


  • 17世紀時,德國的天文學家開普勒(Johannes Kepler)相信日心說,然後他用自己的天文資料嘗試建立行星圍繞太陽運行的定律 。早在古希臘時代,哲學家畢達哥拉斯(Pythagoras)便設定出行星繞太陽轉的軌跡是「圓」的。但開普勒並沒有「訴諸權威」,他發覺繞圓成周的概念在計算上總有誤差,便開始懷疑已流芳千古的「圓」假設,然後成功解釋,行星是繞着太陽「橢圓」運行。此學說一直到牛頓時代便被證實了。

複合問題/文字陷阱/一語多義(Polysemy Fallacy)

當一句說話中,包含了多過一個意思,說話者及聆聽者之間便容易作出兩種或多種的演繹方法,導致誤會的產生。


  • 「牛扒好難食」


  • 是味道不好的意思?


  • 還是比較韌不方便吃的意思?


  • 「你有固定伴侶嗎?」


  • 「沒有」


  • 你答的是沒有伴侶?


  • 還是有伴侶,但沒有固定的?

普通閑聊說笑一下便沒有所謂,一去到男女朋友間的對話了解便大件事了。

所以培養好自己的邏輯素養是重要的,而最直接的是多接觸思維概念性強及嚴謹的數學教育 (數學有1.直接證明法(Direct Proof),2.反證法(Contradiction),3.找反例(Counter Example),4.數學歸納法(Mathematical Induction))。而以上謬誤例子只是冰山一角,對此題目及其他謬誤例子有興趣的話,可以參閱以下書籍及網頁:


  • 劉彥方 陳強立 。(2004-2019) 。思方網-常見謬誤一覽 。https://philosophy.hku.hk/think/chi/fallacy-list.php


  • 吳作樂、吳秉翰 。你沒看過的數學。台灣﹕五南圖書出版古股份有限公司。(2015年)

其他資料。。。將會陸續更新


遲些回來吧~