0

0
0

文字

分享

0
0
0

2015 年阿貝爾獎桂冠得主:約翰納許--《科學月刊》

科學月刊_96
・2015/11/19 ・3734字 ・閱讀時間約 7 分鐘 ・SR值 570 ・九年級

李武炎/曾任教淡江大學數學系,現為《科學月刊》編輯委員

就在幾個月前,今年5月23日,「賽局論」(game theory)大師、也是諾貝爾經濟學獎得主的美國數學家約翰納許與妻子艾莉西亞(Alicia Esther Nash)在美國因車禍雙雙喪命,事實上,納許5月19日剛在挪威奧斯陸領取2015年「阿貝爾獎」(Abel Prize), 他們出席相關活動後,返家途中搭乘了一輛計程車,不幸在新澤西州的快速道路上發生車禍,消息傳來,令人不勝唏噓。

約翰納許(John Forbes Nash Jr., 1928~2015

「某個程度上,正常思考就是一種對現狀的順從。人們總是想傳達患有精神疾病者煎熬受苦的意象,但其實並沒有那麼單純,我認為精神疾病或瘋狂也可以是一種超脫。」

JR
約翰納許。 Source: Wiki

納許的人生故事,尤其是長期掙扎於精神分裂的情節,曾在2001年被改編拍成電影《美麗境界》(A Beautiful Mind)轟動一時,更奪下2002年奧斯卡最佳影片,在片中飾演納許的影星羅素 克洛(Russell Crowe)傳神的演技,更是令人印象深刻,真實的人生中,納許在1959年因「思覺失調症」入院接受治療,直到1970 年方才出院。

納許本身是一位數學家,他在上個世紀五零年代就已經在數學的研究上作出很多重要的成果,只是外界比較熟悉的反而是他在「賽局論」上的成就,「賽局論」是一個與作決策有關的數學,它最早被應用在經濟學上,變成研究經濟學不可或缺的工具,如今「賽局論」也被廣泛應用於生物學、政治學及控制理論等等的領域。「賽局論」是研究理性決策者之間的衝突與合作所產生的效益的一種數學模式,例子很多,例如打牌、球賽、商務談判等。「賽局論」最有名的問題便是「囚犯困境」的經典例子:

警方逮捕甲乙兩名嫌犯,但沒有足夠證據指控兩人有罪,於是警方將嫌疑犯分開隔離囚禁,而且分別向兩人遊說認罪並提供以下的選擇:

(一)若一人認罪並作證指控對方,而對方不招供,則此人將立即獲得釋放,而被指控者將被判刑10年。

(二)若兩人都不招供,則兩人將同樣被判刑半年。

(三)若兩人都認罪並互相檢舉對方,則兩人將同樣被判2年。

game

囚犯應該選擇那一種策略才對自己最有利?由於兩名囚犯是被隔離監禁,所以不知對方會選擇哪種策略,試想有理性的囚犯會作出何種選擇,若對方沉默,我指控對方,則我將獲釋,所以我會選擇指控對方;若對方指控我,我如果沉默,則我會被判刑10年,所以我也要指控對方才能獲得2 年較短的刑期。因此我總是要採取指控對方的策略,結果理性的兩人都選擇相同的策略,也就是指控對方,其結果是兩人皆獲判監2年,這在「賽局論」中就是所謂的「納許均衡」(Nash equilibrium)。這也是納許在1950年獲得美國普林斯頓大學數學博士的論文中一個重要的概念,由於他的研究應用在經濟學上的貢獻,使得他與另外兩位「賽局論」的學者約翰海薩尼(John Harsanyi)與萊因哈德謝爾騰(Reinhard Selten)共同獲頒1994年諾貝爾經濟學獎。

納許雖然榮獲諾貝爾經濟學獎,但他本來就是數學專業,他在數學上的研究當然也是非常的傑出,尤其是在廿世紀五零年代,他就已經在數學領域的分支「偏微分方程式」證出很多重要的定理,只是外界比較熟悉的是他在「賽局論」上的成就。由於他在數學上的傑出研究,終於獲得挪威科學與人文研究院的青睞,決定頒授2015年的阿貝爾獎給他,與他同時獲獎的是另外一位美國「偏微分方程式」的巨擘尼倫伯格(Louis Nirenberg),尼倫伯格也是中研院院士林長壽的指導教授。

數學界最崇高的阿貝爾獎

阿貝爾獎常被稱為數學的諾貝爾獎,因為諾貝爾獎項並沒有數學,所以阿貝爾獎可說是數學界最崇高的獎項,它不像另外一個也是數學的菲爾茲獎(Fields metal)有年齡的限制,而且是早年為了彌補諾貝爾獎沒設數學項目的缺憾所提議設立的,不過這個獎項的設立直到公元2002年方才實現,挪威政府為了紀念十九世紀挪威的一位數學家阿貝爾(Niels Henrik Abel,1802~1829)200 歲誕辰,決定設立阿貝爾獎,並且在2003 年開始頒發第一次的獎,獎勵當代研究傑出的數學學者,獎金有挪威幣六百萬克朗(約合750000 美金),歷屆的得主都是當代數學界的翹楚。

阿貝爾是挪威歷史上一位才華橫溢的數學家,他在很年輕時就已經作出很出色的研究成果,其中最有名的是證明一般五次方程式沒有根式解,開啟抽象代數學之濫觴,對代數學往後的發展奠定不可磨滅的根基,他與同時代的法國數學家伽羅瓦(Galois)雙雙被推崇為「現代群論的先驅」。抽象代數中有一種代數結構是運算可交換的「群」,為了紀念阿貝爾,數學圈中就把交換群叫做「阿貝爾群」,英文是「abelian group」,以人命名的專有名詞,在英文的習慣中,第一個字母應為大寫,可是abelian的第一個字母a 卻是小寫,這是因為數學界為了表彰阿貝爾特別卓越的貢獻而把它普通化了,所以如果你在其他地方也看到小寫的專有人名名詞,應該肅然起敬,只有特別了不起的人物才能擁有如此的待遇。

納許與尼倫伯格成為2015 年的阿貝爾桂冠的得主,是因為要表彰他們在數學領域的非線性偏微分方程式及其在幾何分析上的應用,作出顯著與影響深遠的貢獻。偏微分方程式(partial differential equations)是數學的其中一門分支,高中生在高中數學中都學過一點微積分,所涉及的微分都是求單變數函數的導數,而在大學微積分中就會學到多變數函數的導數,針對不同的變數所求的導數就稱為偏導數;因為導數是研究變化率的問題,所以數學中的很多問題以及物理現象,常用與偏導數有關的方程式來描述,因此研究偏微分方程式就成為近代數學的主流,如果方程式中與偏導數有關的項其次數都不超過一次,則這種偏微分方程式就稱為線性(linear),否則就是非線性。非線性方程式(nonlinear partial differential equations)的解法並無一般常規方法可循,幾乎每一種形式都有其特別的解法,而且要用到「分析」的背景知識,分析是指以微積分、無窮級數與解析函數為理論的數學內容,是純數學的三大分支之一,其他兩支為代數與幾何,所以偏微分方程式的題目都很難,為破解非線性偏微分方程的問題,就必須具有獨特與高超的手腕,納許與尼倫伯格就是箇中高手,納許尤其聰明,他的很多這方面的研究都是單打獨鬥自己發明的。

微分流形

除了非線性偏微分方程,納許也專研微分幾何,微分幾何(differential geometry)也是數學的一個分支,主要是研究「微分流形」。流形(manifold)是高等數學中的一個專有名詞,它是一個具有拓樸結構的幾何形體,它的局部具有歐幾里得空間的性質,用比較白話來說,就是近看起來像歐幾里得空間。例如像地球的表面(球面)就是一個流形,我們所處的這個地面範圍看起來是平坦的,這是因為我們所看到的地面其實是地球表面很微小的一部分,所以我們將地面視為平面,但就整個球面而言,它不是平面,我們可以把地球的表面看成一片一片的平面拼接起來,所以球面就是流形的一個例子。當然,流形還是很抽象的概念,簡單地說,它就是高維度的曲線或曲面,物理學中的許多構造也是流形的例子,如力學中的相空間以及廣義相對論中時空模型的「黎曼流形」。

流形中最常應用的是微分流形,它可以用微積分來處理方向、切空間、曲度等問題,而且也用偏微分方程來描述,所以微分幾何與偏微分方程式關係是非常密切的。納許研究微分幾何也會用偏微分方程式作為工具,例如「納許嵌入定理」(Nash embedding theorem):任何抽象的黎曼流形可以嵌入一個歐幾里得空間而保持距離不變;嵌入的意思是把流形放進歐幾里得空間之中而視為一個子流形。為了證明微分幾何中的定理,他必須處理一些特殊偏微分方程式的問題,而這些方程式在以前被公認是不可能解出的,可是納許運用一個迭次的技巧方才克服,這種重複的方法是以確定的部分作為起始點,循序漸進推演,最後求得答案,微積分中的「牛頓法」就是其中一個例子,納許研究的功力真的是一流的,能得到阿貝爾獎真正是實至名歸當之無愧。也是阿貝爾獎得主的葛洛莫夫(Mikhail Gromov)就曾讚許說:「納許在幾何上的貢獻,在我看來,是比他在經濟學上的研究更具無與倫比的偉大,他讓人對流形的看法有不可思議的改變,他能將流形掌握在手,而且比傳統方法更加運用自如。」納許就是玩流形的高手。

令人緬懷的傳奇伴侶

納許早年深受精神疾病所若,沉潛數十年之久,但他後來逐漸復原,重回學術領域繼續研究,他的成就自屬拔尖,他的人生故事就是一段傳奇。對於他的驟逝,數學界為之不捨,也讓世間響起一陣陣嘆惜,納許過世前是美國普林斯頓大學數學系的資深研究員,對於納許的不幸過世,普林斯頓大學群體深感震驚與悲傷,普大校長艾斯格魯伯(Christopher Eisgruber)發表下面的談話:「約翰的卓越成就,激發了數代的數學家、經濟學家與科學家,因為他們都深受納許在賽局論上的顯赫突破所影響,他與夫人艾莉西亞的故事更是感動數以百萬計的讀者與電影觀賞者,他們尤其激賞他倆在面對令人恐懼的挑戰時所展現的無比勇氣。」電影《美麗境界》中飾演納許的羅素.克洛在推特上懷念納許,他寫道:「我心歸之;一對令人神奇的伴侶,美麗的心智,美麗的心靈。」

1234〈本文選自《科學月刊》2015年8月號〉

延伸閱讀:
罹患精神疾病的天才數學家-奈許的美麗境界
數學的諾貝爾獎

什麼?!你還不知道《科學月刊》,我們46歲囉!
入不惑之年還是可以
當個科青

文章難易度
科學月刊_96
229 篇文章 ・ 2098 位粉絲
非營利性質的《科學月刊》創刊於1970年,自創刊以來始終致力於科學普及工作;我們相信,提供一份正確而完整的科學知識,就是回饋給讀者最好的品質保證。

0

5
1

文字

分享

0
5
1
婚姻中的賽局理論!從兩首古詩理解「穩定婚姻問題」
tml_96
・2021/09/23 ・3781字 ・閱讀時間約 7 分鐘

國小高年級科普文,素養閱讀就從今天就開始!!

賽局理論演算的「穩定婚姻」

賽局理論中有所謂「穩定婚姻問題」。在所有婚姻狀態均「穩定」的已婚社群,每對夫妻各自都無法找到比現在更好的另一半。換句話說,所謂「穩定」的已婚社群,就是丈夫想出軌,他想出軌的對象也不認為他會比現在的另一半來得好,因此不可能會跟這位丈夫在一起,反之妻子亦然。 因此,婚姻中的男女即使見異思遷,實際上也改變不了自己的婚姻狀態。

穩定婚姻意涵社群中,曠夫怨婦不可能藉著與原來配偶離婚,再互相結婚來改進他們的婚姻狀況。這也是賽局理論所說的「伯瑞多最佳」狀態。但這並不代表每個婚姻中人都是如魚得水,他們可能只是找不到更好而有意願的對象而已。

賽局理論中的穩定婚姻,並不表示夫妻兩人過得好。圖/Pixabay

「穩定婚姻問題」尋求一個把男女配對而形成穩定婚姻社群的演算法。這方法早在 1962 年即由 2012 年諾貝爾經濟學獎得主 Lloyd ShapleyDavid Gale 解出。其方法稱做 Gale-Shapley 演算法。Gale-Shapley 演算法的應用遠超過婚姻配對問題,例如美國醫學協會把住院醫師與實習醫院配對便用了這個演算法。

這個演算法要求社群中每個人都要列出他或她對所有異性的喜好順序。例如在三男三女的社群中,假設各人的偏好順序如下表:

三男三女各自心目中的喜好順序。

三男三女共可有六組不同的婚姻配對,其中有三組是穩定婚姻。

第一組:(A 女,乙男)、(B 女,丙男)、(C 女,甲男)。社群中每位女士均嫁了她們最心儀的男士,但每位男士均娶了他們最看不上眼的女士。很顯然地,雖然男士們都蠢蠢欲動,其奈女士們不動如山何?這組婚姻符合穩定的定義。

所有的女士都找到了自己最好的對象,就算男士對自己的對象再有怨言,也無法找到願意出軌的女士。

第二組:(A 女,甲男)、(B 女,乙男)、(C 女,丙男)。與第一組恰恰相反,這裡每位男士均娶了他們最心儀的女士,但每位女士均嫁了她們最看不上眼的男士。依同理,這組婚姻也是穩定的。

所有的男士都找到了自己最好的對象,就算女士對自己的對象再有怨言,也無法找到願意出軌的男士。

第三組:(A 女,丙男)、(B 女,甲男)、(C 女,乙男)。這裡不分男女均已獲得了次愛對象的垂青。如果有人還不知足,想更上一層樓,很抱歉:他(她)們心目中最愛的對象卻看他(她)們最不上眼呢,還是乖乖守護家庭吧。穩定婚姻!

三男三女皆找了自己還能接受的對象在一起,但所有人也無法找到比目前對象更好的伴侶。

從這個例子可以看出:穩定婚姻的演算法並不保證唯一解,而且也不保證人人都美滿幸福。

穩定婚姻的演算法是基於無法找到更好的人,並不保證所有人幸福美滿。圖/Pixabay

那麼,對婚姻充滿浪漫期待的青年男女們如何才能在穩定的前提上爭取到如意的對象呢?賽局分析顯示,採取主動的一方,比較容易得到排序較高的對象。例如若女性採取主動,則結果較可能是第一組。若男性採取主動,則結果較可能是第二組。被動的一方很可能在形勢比人強的情形下止於末選。

網路上有好幾個網頁以 Python 程式語言執行了 Gale-Shapley 演算法。有興趣的讀者可以參考文末書目。

中國古詩中的穩定婚姻問題

這裡以兩首中國古詩為例說明什麼是「穩定婚姻」、什麼不是「穩定婚姻」。

從漢朝樂府詩 《陌上桑》來看穩定婚姻問題

漢朝樂府詩《陌上桑》全詩如下:

日出東南隅,照我秦氏樓。秦氏有好女,自名為羅敷。羅敷喜蠶桑,採桑城南隅。青絲為籠繫,桂枝為籠鉤。頭上倭墮髻,耳中明月珠。緗綺為下裙,紫綺為上襦。行者見羅敷,下擔捋髭鬚。少年見羅敷,脫帽著帩頭。耕者忘其犁,鋤者忘其鋤。來歸相怨怒,但坐觀羅敷。

使君從南來,五馬立踟躕。使君遣吏往,問是誰家姝。「秦氏有好女,自名為羅敷。」「羅敷年幾何?」「二十尚不足,十五頗有餘。」使君謝羅敷:「甯可共載不?」

羅敷前致辭:「使君一何愚!使君自有婦,羅敷自有夫。東方千餘騎,夫婿居上頭。何用識夫婿?白馬從驪駒。青絲繫馬尾,黃金絡馬頭;腰中轆轤劍,可直千萬餘。十五府小吏,二十朝大夫,三十侍中郎,四十專城居。為人潔白皙,鬑鬑頗有鬚。盈盈公府步,冉冉府中趨。坐中數千人,皆言夫婿殊。」

這詩中的「使君」與「羅敷」都已婚。「使君」喜歡「羅敷」甚於喜歡自己太太,但是「羅敷」喜歡自己的先生甚於「使君」。何以見得?「使君一何愚」等於現代人罵無聊男子是「癡漢」。而「皆言夫婿殊」更掩不住嫁了如意郎君的沾沾自喜。

另外,詩中雖未點明,但「羅敷」的夫婿四十幾歲了能娶到十幾歲而又真心愛慕他的美女,即使「使君」的太太羨慕「羅敷」先生高富帥,怨嘆「使君」隨地拈花惹草,「羅敷」的先生應該不至於會喜歡她甚於喜歡自己太太。果然如此,這兩對夫妻所組成的社群,其婚姻狀態便算「穩定」。所以「穩定婚姻」不代表婚姻中人不見異思遷,而是即使想劈腿自己更喜歡的人也找不到願意的對象而無法做到。

依照上面的假設,各人的偏好順序如下:

《陌上桑》 中二男二女的喜好順序。

我們可以看到(羅敷,羅敷夫)、(使君婦,使君)的配對是穩定的。雖然使君婦跟使君都是跟他們的最末順位結婚,可是那即使不滿意也已經無法改善了,被罵「癡漢」也只能黯然。

黃色為使君夫婦的配對,藍色為羅敷夫婦的配對,可以看到羅敷夫婦正好是對方心目中的第一順位。縱使使君認為羅敷才是他的真愛,但羅敷對他的另一半非常滿意,因此兩人不可能在一起。

從《節婦吟·寄東平李司空師道》來看穩定婚姻問題

同樣描寫婚姻狀態的唐代張籍的《節婦吟·寄東平李司空師道》,道出了不太一樣的情境。

君知妾有夫,贈妾雙明珠。
感君纏綿意,繫在紅羅襦。
妾家高樓連苑起,良人執戟明光裡。
知君用心如日月,事夫誓擬同生死。
還君明珠雙淚垂,恨不相逢未嫁時。

這首詩中的「妾」受到「君」的撩撥其實已經動了心。她起初還把「君」贈她的兩顆明珠繫在她貼身的紅色蕾絲小可愛上。後來雖然還給了他,並不是因為喜歡「良人」甚於喜歡「君」。

何以見得?詩中所引用的理由是「妾家高樓連苑起,良人執戟明光裡」。這兩句我怎麼看怎麼不對勁。也許傳統的解釋是說夫家有錢還位居高官。但高樓深宅事實上並沒有防得了「妾」與「君」私通款曲,當然更栓不住她愛慕的心。

至於「良人執戟明光裡」,其實也不過是在皇宮充當侍衛,並不是什麼大不了的官,遠比不上「陌上桑」裡羅敷的夫婿。說不定「良人」不值班的夜晚便拿著他那枝戟月光下在自家門外巡防太太私奔呢!無論如何,這詩裡的「妾」只是個受傳統規範羈束的「節婦」加「怨婦」。「事夫誓擬同生死」不過是「從一而終」的概念。

最後一句「恨不相逢未嫁時」更毫不掩飾地表明了「怨婦」的心情:如果不是喜歡「君」甚於喜歡「良人」,直接罵他「痴漢」就是了,何至於「還君明珠雙淚垂」?又何需心中有恨?這樣的婚姻只能以外力來維持穩定,算不得賽局理論的「穩定婚姻」。

在這個配對中,假設各人的偏好順序如下(註:原詩未提「君」是否已婚。這裡的分析假設他已娶妻,但「君婦」的偏愛順序並不重要。):

(妾,妾夫)、(君婦,君)的配對是不穩定的,因為「妾」跟「君」如果做得到可以離開原配、互結連理而改進他們的婚姻幸福。只是不幸活在不能隨意離婚的時代,也只能「恨不相逢未嫁時」了!

黃色為君與君婦的配對,藍色為妾與妾夫的配對,可以看到妾與君兩人都選了第二順位作為伴侶,並認為彼此都是最佳伴侶(紅色標示),因此極有可能出軌。在這個情況下,最穩定的結果是(妾,君)、(君婦,妾夫)的組合。

參考書目

  1. D. Gale and L. S. Shapley. “College Admissions and the Stability of Marriage.” The American Mathematical Monthly, Vol. 69, No. 1 (Jan., 1962), pp. 9-15.
  2. Alexander Osipenko, “Gale–Shapley Algorithm Simply Explained.”
  3. 漢娜弗萊著,洪慧芳譯。《數學的戀愛應用題》第三章〈提高安打率的秘密〉。天下雜誌出版。
tml_96
34 篇文章 ・ 225 位粉絲
台大電機系畢業,美國明尼蘇達大學政治學博士, 現任教於美國德州大學奧斯汀校區政府系。 林教授每年均參與中央研究院政治學研究所及政大選研中心 「政治學計量方法研習營」(Institute for Political Methodology)的教學工作, 並每兩年5-6月在台大政治系開授「理性行為分析專論」密集課程。 林教授的中文部落格多為文學、藝術、政治、社會、及文化評論。

0

38
3

文字

分享

0
38
3
【快訊】數學與計算機科學的交織──2021 阿貝爾獎
Yi-Hsuan Lee_96
・2021/04/08 ・3202字 ・閱讀時間約 6 分鐘 ・SR值 534 ・七年級

國小高年級科普文,素養閱讀就從今天就開始!!

  • 作者/李奕萱

阿貝爾獎(Abel Prize)自2003年開始由挪威國王頒發給傑出數學家的獎項。阿貝爾獎的歷史可以追溯到1899年,當時挪威數學家索菲斯·李(Sophus Lie)得知阿佛烈·諾貝爾(Alfred Nobel)計劃設立的諾貝爾獎將不包括數學獎,又剛好正逢數學家尼爾斯·亨里克·阿貝爾(Niels Henrik Abel)誕辰100週年紀念,便提出設立阿貝爾獎。 不幸的是,索菲斯·李不久後逝世、提供資金的奧斯卡二世國王也因為瑞典和挪威聯合王國解散而下台,阿貝爾獎這件事也就不了了之。

2001年,人們覺得應該給數學家一個相當於諾貝爾獎的獎項,便再次將阿貝爾獎提案給挪威總理。隔年挪威政府便宣佈撥款2億挪威克朗在數學家阿貝爾誕辰200週年時正式設立阿貝爾獎,並由挪威自然科學與文學院成立阿貝爾委員會負責審理。

阿貝爾獎的獎金高達750萬挪威克朗,是國際數學獎中的最高金額。圖/wikipedia

雖然說阿貝爾獎被譽為數學界的諾貝爾獎,但表彰方向卻和諾貝爾獎不盡相同。舉例來說,諾貝爾物理學獎主要是頒發給對物理作出重要發現或發明的人,像是2020年的諾貝爾獎得主就是成功觀察到銀河系中心的超大質量緻密天體,並發現黑洞的形成是廣義相對論的確鑿預測,因而得獎。阿爾貝獎則是大多頒獎給在數學領域發展中的重要推手,也就是引領數學界的人。

今年挪威科學院將2021年的阿貝爾獎頒給匈牙利羅蘭大學(Eötvös Loránd University)的洛瓦茲·拉茲洛(László Lovász)和美國普林斯頓大學的以色列數學家阿維·威格森(Avi Wigderson),表彰他們對理論計算機科學與離散數學的貢獻,以及將兩者塑造成現代數學的重要領域

“for their foundational contributions to theoretical computer science and discrete mathematics, and their leading role in shaping them into central fields of modern mathematics”

剪不斷理還亂的計算機科學和數學

1970年代,理論計算機科學和純數學是沒什麼關係的兩個學術領域。經過幾十年的發展,這兩個學科之間早已變得極為密切,在現代數學,我們甚至很難分清它們之間的界限。其中,洛瓦斯和威格森就是在最前線開疆闢土的人。

阿貝爾委員會主席漢斯·蒙特·卡斯(Hans Munthe-Kaas)表示:「在過去的幾十年中,洛瓦茲(圖中左)和威格森(圖中右)一直是這一發展的領導力量。他們的工作以多種方式交織在一起,尤其是它們都為理解計算中的隨機性和探索有效計算的邊界做出了根本性貢獻。」圖/The Abel Prize

計算複雜性理論 (Computational complexity theory)是數學和計算機科學領域的一個重要分支。從小我們就知道算數學要快、狠、準,如何更快、更輕鬆地解決問題一直是人類追求的目標。計算複雜性理論通過引入數學計算模型計算各個演算法的資源使用情形,像是時間(透過幾個步驟產出結果)、空間(需要佔用多少記憶體),再進一步進行複雜性分類、聯絡。洛瓦茲設計的LLL演算法、威格森的去隨機化研究對拓寬和深化這個領域的貢獻無疑是最重要的領導者。

從數學到計算機科學──拉茲洛·洛瓦斯

圖/wikipedia

洛瓦茲於1948年出生在布達佩斯,從小就對數學有濃厚的天份,22歲便拿到博士學位,他的早期靈感大部分來自數學家艾狄胥·帕爾(Erdős Pál)。艾狄胥的成就集中在離散關係的數學,而不是典型的連續變量上,也就是組合學、圖論等領域。

組合學(Combinatorics)、圖論(Graph theory)都是離散數學的範疇。前者主要解決組合模型中的存在、計數以及構造等方面的問題;後者作為組合學的分支,將對象之間的關係通過邊和節點組成數學結構圖。拉斯洛·洛瓦茲作為新一代數學家自然不會將離散數學侷限在純數學的理論研究中,他意識到離散數學在計算機科學中非常具有發展潛力,並著手研究離散數學可以解決計算機科學問題的方法。

圖論中的經典七橋問題:在所有橋都只能走一遍的前提下,如何才能把這個地方所有的橋都走遍呢?圖/wikipedia

最著名的研究是由洛瓦茲(Lovász)以及荷蘭數學家阿爾揚·倫斯特拉(Arjen Lenstra)和亨德里克·倫斯特拉(Hendrik Lenstra)的名字命名的LLL演算法(LLL lattice)。這種稱為LLL的算法將由整數組成的大向量分解為各種類型的最短向量的總和,也就是可以計算出空間中的點集與原點的距離。

最初的LLL演算法被應用將多項式時間(Polynomial time,P)以有理係數多項式表示,來找出他的實數近似值來解決固定維數的整數線性規劃問題。LLL演算法在數論、密碼學和通訊計算等領域也都具有顯著的應用,更是現今可以抵禦量子計算機攻擊的加密系統之一。

從計算機科學到數學──阿維·威格森

威格森對他的研究領域一直都充滿熱情,常常感染身旁的同事一起參與研究。圖/Wikipedia

威格森於1956年出生於以色列海法。威格森最著名的成就之一就是闡明了隨機性在計算中的作用。在聊隨機性之前,我們先來聊聊什麼是P, NP:

P和NP是複雜性的類別,P問題是可以快速計算出來的問題,NP問題則是可以快速驗證的問題。

當問你17乘以19是多少時,你可能沒辦法馬上心算出來,但按一按計算機就一定能得出答案,那麼這個問題就是屬於P問題,包含了所有容易解決的計算問題。現在,問你323的所有質因數有哪些呢?問題複雜了許多吧!我們必須從2、3、5……開始慢慢找,正著找質因數很困難,如果我們反著找呢?先告訴你17、19是323的質因數,是不是只要把它們乘在一起就能驗證答案對不對了?這個例子就是屬於NP問題,包含了可能是很難解決的計算問題,但只要有答案就很容易被驗證正確與否。

科學家便提出了一個看法:「會不會其實P=NP?」也就是說NP問題有可能可以被簡單解決。威格森的主要研究就是將複雜性類別一一歸位,將多項式時間演算法完全去隨機化,更快速的得到結果,並把隨機演算法和複雜性理論結合,提出P = BPP(bounded-error probabilistic polynomial time),回答了多年來對P/NP問題的疑問,大大拓寬了資訊界的未來視野。

P/NP問題是一個在理論資訊學中計算複雜度理論領域裡至今未被解決的問題,也是克雷數學研究所七個千禧年大獎難題之一。圖/wikipedia

威格森對貨幣加密的零知識證明也很有貢獻,零知識證明簡單來講就是在不透露任何資訊的情況下驗證正確性的方法。最初是在保護個資方面,像是我們想要申請某個購物網站的會員,我們就必須提供姓名、電話、出生年月日等各種資料來驗證我們的真實身份,但在零知識證明之下我們可以選擇提供「零密碼證明」、隱藏真實密碼,達到完全保護個資的目的。

有些人可能會有疑問說數學有用嗎?數學不是只能拿來算錢嗎?那你就錯了!數學一直扮演著承載科學的角色,躲在背後支持著科學發展,不難發現每一門科學都或多或少跟數學交織在一起,每一年頒發的阿貝爾獎、菲爾茲獎、諾貝爾獎都顯現出這些數學家、科學家正將科學這個巨網越織越堅固。一起為今年的得獎者送上掌聲吧!

圖/Giphy

參考資料

Yi-Hsuan Lee_96
3 篇文章 ・ 1 位粉絲
Science Communicator | 數學系畢業,跑到心理系當了一年間諜,現在是應用科學研究生。喜歡文學、古典戲劇和薏仁。立志在台灣創造一個老人小孩都能樂在其中的科普空間。

0

0
2

文字

分享

0
0
2
戰機擾台有效嗎?從賽局理論看中國的「危險邊緣」策略
tml_96
・2020/10/06 ・3005字 ・閱讀時間約 6 分鐘 ・SR值 523 ・七年級

  • 作者/林澤民

最近中國在台海附近頻頻軍演,其戰機也連日騷擾台灣領空。央視主播李紅甚至引前總統馬英九「首戰即終戰」論調出言恐嚇。這明顯的是所謂「危險邊緣」 (brinkmanship) 策略的施展,常見於國際間協商談判的「懦夫賽局」中,是逼對方讓步的有效手段。

這個策略讓對方領會「兵凶戰危」,但其實它的極限是「戰爭邊緣」而不是「戰爭」。 

在「懦夫賽局」中,僵局雙方的的偏好順序都是: 

  • 最高:(我堅持,你讓步)=4
  • 次高:(我讓步,你讓步)=3
  • 第三:(我讓步,你堅持)=2
  • 最末:(我堅持,你堅持)=1

換句話說,雙方都希望自己堅持而對方讓步。一方堅持一方讓步是「納許均衡」,但雙方都堅持卻是最壞的結果。

施展「危險邊緣」策略的一方會使用各種手段讓對方相信自己寧可玉石俱焚也不會讓步。但是這種不理性的威脅有時會讓對方嗤之以鼻。要讓對方深信,必須要在行為上顯示自己願意一步步走向危險邊緣的態勢。

在懸崖上綁著鐵鍊,如何避免一起摔死?

諾貝爾經濟學獎得主湯瑪士.謝林 (Thomas Schelling) 教授是最早提出「危險邊緣」策略的人。他曾在哈佛大學課堂上舉了一個例子:「想像你在懸崖上,腳踝被鐵鍊與另一人的腳踝互相拴住。如果你們兩人有一人讓步,你們就可得到解放,而堅持到底的那人還可以獲得大獎。你要如何說服另一人讓步呢?要知道你能夠做的可就只有威脅他要把他推下懸崖,而那可會讓你們兩人一齊摔死喔!」

謝林對這個問題的答案是:「你開始跳舞,一步一步逼近懸崖。這樣你不用說服他你會做出兩敗俱傷的不理性動作,你只要讓他相信你比他願意承擔發生意外的危險就行了。」

只要讓對方相信你比他更願意承擔發生意外的風險,就可以說服對方讓步。圖/Pexels

謝林把心理學引入賽局理論,是行為經濟學的先驅。他的意思是:因為兵凶戰危,「與汝偕亡」的威脅不容易讓對方深信,但如果你用魯莽的行為表現出你不在乎「擦槍走火」,這種打了折扣的威脅反而較容易取信於人。

謝林說:「瘋狂可以是惡意地合乎理性」 (“Madness can be wickedly rational.”) 因此,「危險邊緣」的理論常被稱為「瘋子理論」 (Madman Theory) 。

因為雙方都堅持是最壞的結果,施展「危險邊緣」策略的玩家其實就是要對方相信自己是不理性的。當對方相信你瘋了、不可理喻的時候,對方就會讓步。謝林把這種算計稱為「不理性的理性」 (rationality of irrationality) 。

在懸崖邊緣裝瘋賣傻而不真摔需要走鋼索的技巧。

冷戰時期的美國國務卿杜勒斯 (John Foster Dulles) 就說「能做到走向戰爭邊緣而不致真正開戰」是必要的「藝術」。

這種藝術常在電影中被戲劇化。名導演史丹利.庫柏力克 (Stanley Kubrick) 的1964年電影《奇愛博士》 (Dr. Strangelove or: How I Learn to Stop Worrying and Love the Bomb) 便是戲劇化冷戰時期美、蘇雙方「相互保證毀滅」 (mutually assured destruction, MAD) 的黑色喜劇。

片中美方一位發瘋的指揮官下令B–52轟炸機對蘇聯目標投擲氫彈,即使總統及國防部長都無法攔阻。庫柏力克便是因為看了謝林對小說《紅色警戒》 (Red Alert) 的評論而改編小說拍攝成電影,他並邀謝林擔任此片顧問。

電影《奇愛博士》美方對蘇聯投擲氫彈。圖/flickr

1962年古巴飛彈危機的時候,赫魯雪夫在古巴部署核彈及甘迺迪對古巴進行封鎖更是「危險邊緣」策略的實例。羅杰。唐納森 (Roger Donaldson) 主導的2000年電影《驚爆13天》(Thirteen Days) 中蘇聯貨輪在美國艦隊發射魚雷之前迴轉可以說是此一策略的經典意像。

電影《驚爆13天》(Thirteen Days)

前國安會秘書長蘇起說中國會「小打」台灣。蘇起寫過一本叫《危險邊緣》的書分析「兩國論」、「一邊一國」之後的兩岸關係,他是懂得「危險邊緣」策略的。他的意思應該是說中國會以「小打」來「舞」向戰爭邊緣,冀望不必全面開戰就逼使台灣讓步。

甚麼是「最壞的結果」?

但是「危險邊緣」要奏效有一個前提,那就是雙方的對峙必須是「懦夫賽局」。

如果對峙的局面是「囚徒困局」,這策略不會有效。

在「囚徒困局」中,雙方的的偏好順序都是:

  • 最高:(我堅持,你讓步)=4
  • 次高:(我讓步,你讓步)=3
  • 第三:(我堅持,你堅持)=2
  • 最末:(我讓步,你堅持)=1

其與「懦夫賽局」最大的不同在於(我讓步,你堅持)是最壞的結果,比玉石俱焚還糟糕。

當參賽雙方感知到讓步會帶來最壞的結果的時候,堅持下去是合乎理性的優勝策略,而雙方都堅持是納許均衡。

我教賽局的時候,常引用電視遊戲節目《金球》來作為例子。詳細請參考拙作金球的囚徒

這個遊戲中參賽者雙方可以選擇「平分」(讓步)或「獨吞」(堅持)。如果兩人中一人選擇獨吞另而一人選擇平分,則獨吞者獨享巨額獎金,平分者抱蛋;如果兩人都選擇平分,則各得一半獎金;如果兩人均選擇獨吞,則兩人均抱蛋。

這個遊戲是「囚徒困局」,因為:

(我獨吞,你平分)>(我平分,你平分)>(我獨吞,你獨吞)>(我平分,你獨吞)

有一次節目中,參賽者之一在賽前向對方做了兩項承諾:第一,他一定會選擇獨吞(堅持);第二,如果對方選擇平分(讓步)而由他贏得全部獎金,他會把獎金分一半給對方。

雖然主持人一再提醒賽前承諾不具法律效力、不可輕信,這位參賽者的口頭承諾卻達到了兩個效果:

第一、他平分獎金的承諾,只要對方相信有一點點可能性,對方就會認為(我平分,你獨吞)的期望值比(我獨吞,你獨吞)還要好。也就是在他的心中,賽局已經悄悄地從「囚犯困境」轉變為「懦夫賽局」。

第二、他堅持會選擇獨吞的承諾,正是「危險邊緣」策略。當對方把賽局認知為「懦夫賽局」的時候,這策略可以奏效。

果然,在這次賽局中,對方選擇了平分。而這位聰明的玩家也出乎意料地選擇了平分,用合乎賽局規則的方式履行了他平分獎金的承諾。遊戲全程請見:

電視遊戲節目《金球》 (Golden Balls)

我用這例子來說明:中國要用「危險邊緣」策略來逼台灣讓步是不夠的。只要台灣民意認為讓中國統治是最壞的結果,「危險邊緣」策略便不會奏效。

傳統中國所謂「大國」要能做到「近者悅,遠者來」。 中國要做大國,恐怕還得學學《金球》遊戲節目的聰明玩家!

tml_96
34 篇文章 ・ 225 位粉絲
台大電機系畢業,美國明尼蘇達大學政治學博士, 現任教於美國德州大學奧斯汀校區政府系。 林教授每年均參與中央研究院政治學研究所及政大選研中心 「政治學計量方法研習營」(Institute for Political Methodology)的教學工作, 並每兩年5-6月在台大政治系開授「理性行為分析專論」密集課程。 林教授的中文部落格多為文學、藝術、政治、社會、及文化評論。