博弈高手 淺論約翰·納殊的 諾具爾得理論 吳端偉 香港大學理學院 香港大學數學系
有 2001年奥斯卡金像獎最佳電影 行+ n 《有你終生美麗》（又譯《美麗心靈》） (A Beautiful Mind)的主人翁約翰· 納殊(John Nash)·是1994年諾貝 爾經濟學獎得主。他在2003年初到 香港大學演講，並掀起香港的一股 納殊旋風。納殊以研究博弈論 (game theory)揚名，究竞甚麼是博 弈論呢？這個理論是由數學家約 翰·馮·諾伊曼(John von Neumann)於1928年所創立的·簡 單而言·博弈論是研究每一個決策 者應如何根據其他對手的選擇，去 作出最有利自己的策略。以下是中國古代一個巧用策略的故事·它 能幫助我們了解博弈論所要探討的間題· 話說齊威王經常要大將軍田忌與他賽馬，賽馬的規則是這樣的： 每次雙方各出三匹馬·一對一比賽三場·每一場的負方輸給勝方一 千斤銅。齊威王的三匹馬和田忌的三匹馬按實力都可以分為上 中、下三等，但齊威王的上、中、下三匹馬分别比田忌的上、中、 下三匹馬略勝一籌。起初總是同等次的馬進行比賽·因此田忌每次 都是連輸三場·連輸三千斤銅。實際上·田忌的上馬雖然不如齊威 王的上馬·卻比齊威王的中馬和下馬都要好·而田忌的中馬比齊威 王的下馬要好一些，因此田忌每次都連輸三場是有些冤枉的。 後來田忌的謀士孫臏想出了一個辦法·使田忌反敗為勝。孫臏叫 田忌不要用自己的上馬去對抗齊威王的上馬·而要用下馬去對抗齊 威王的上馬·上馬則去對抗齊威王的中馬·中馬對抗齊威王的下
1 OMMN= !"#$%&'( !"#$% !"#$ E^=_É~ìíáÑìä=jáåÇF= !"#$ =EgçÜå=k~ëÜF NVVQ !"#$%&'=OMMP= !"#$%&'()* !"#$% EÖ~ãÉ=íÜÉçêóF= !"#$%& !"#$%&'()* !"#=EgçÜå=îçå kÉìã~ååF=NVOU= !"#$ !"#$%&'()*+, !"#$%&'()*+, !"#$%&'()*+,-./0123&'%4567 !"#$%&'()*+,-./ !"#$%&'()*+,-./-.01234506 !"#$%&'()(*+$,'(,-.!/01!( !"#$%&'()*+%&'(,-./012345 !"#$%&'() !*+,-./0() !"#$%&'()*+,-.!/012345678- !"#$ !"%&'()*+$,-.+/012345 !"#$%&'!()!*+,"-./'!$%& !"#$%&'()*+,-./0123%456 !"#$%&'()*+,-./ !01234%&5 !"#$%&'()*+,-%&'./!"0'()*+ !"#!"$%&'( )"#)"&'( *
馬。這樣·雖然第一場田忌必輸無疑·但後兩場卻都能獲勝，二勝 一負·田忌反而能赢齊威王一千斤銅。 這個著名的故事生動地告訴我們，巧用策略是多麼重要。事實 上·一旦齊威王發覺田忌在使用計謀，明白了自己為什麼輸給對方 時·他必然也會改變自己三匹馬的出場次序·以免再落入田忌的圈 套。這樣齊威王和田忌之間的賽馬，便變成一個雙方應如何選擇策 略的間題·這正是博弈論所要處理的課題。 今日博弈論已被廣泛應用於招標、國際貿易、選舉、公共政策等 等的經濟及社會科學間題上。它甚至被應用到演化生物學 (evolutionary biology)上來解釋生物演化的現象·例如為何很多物 種的雌雄比例總是約一比一的· 在本書裹我們將深入淺出·輔以大量生動的例子·來介紹博弈論 以及納殊的諾貝爾獎得獎理論· 2■
2 !"#$%&'()*+,-"./0'12345"65 !"#$%&'()*+,- !"#$%&'()*+,-./0123456$7 !"#$%&'()*+,-./0123456789 !"#$%&'()*+,-./01234567,8 !"#$%&'()*+,-./0123456789: !"#$%&'()*+,-!. !"#$%&'()*+,-./0,12,34567 !"#$%&'()*+,-./012345& EÉîçäìíáçå~êó=ÄáçäçÖóF= !"#$%&'()*+,-./# !"#$%&'"'( !"#$%&'()*+,-./012)345678 !"#$%&'&()*
钠殊的生平 首先讓我先介紹一下納殊的生平。納殊在1928年6月13日出 生於美國西維吉尼亞洲的藍田鎮(Bluefield,W.Virginia)。他的父親 是一位電機工程師·母親則是一位教師。納殊於1945年考進卡內 基技術學院(Carnegie Institute of Technology)化學工程系·但很 快就轉讀數學系，並且只用了三年時間便取得了學士及碩士學位· 在此期間·納殊選修了一科他唯一修讀過的經濟科·他寫了一篇關 於協商間題(bargaining problem)的重要論文作為此科的功課· 在取得碩士學位後·納殊進入普林斯頓大學(Princeton University) 攻讀博士。原校老師為他所寫的推薦信只有一行：「此人是天才！ (This man is a genius) 在攻讀博士期間·納殊發明了一種名為Hx的遊戲·並證明了執 先者有必勝的策略（見附錄一·頁31）。他在短短十四個月左右便 寫出了那篇使他獲得1994年諾貝爾經濟學獎的博士論文一《非 合作性博g弈》Non-Cooperative Games)·全文只有二十七頁！而博 弈論裹的一個極為重要的概念一 混合納殊均衡(mixed Nash 李君热学，放戒不倦 此人是天才1 镜扰到了 年使十入，热验) 《嵘性耳子》 三区斯 ■3
3 !"#$%&'()*+&',=NVOU==S==NP= !"#$%&'()*+=E_äìÉÑáÉäÇI=tK=sáêÖáåá~F !" !"#$%&'() *%+,-.=NVQR= !" !"=E`~êåÉÖáÉ=fåëíáíìíÉ=çÑ=qÉÅÜåçäçÖóF= !"#$% !"#$%&'()*+,-./01*#2342#56 !"#$%&'()*+(&,-./0)1*2'(34 !"=EÄ~êÖ~áåáåÖ=éêçÄäÉãF= !"#$%&'() !"#$%&'()*+,-./#=EmêáåÅÉíçå=råáîÉêëáíóF !"#$%&'()*+,-./0123 !"#> EqÜáë=ã~å=áë=~=ÖÉåáìëF !"#$%&'()*+,-.=eÉñ= !"#$%& !"#$% !"#$=PN !!"#$%&'( !"#$%&=NVVQ= !"#$%&'()* !"#EkçåJ`ççéÉê~íáîÉ=d~ãÉëF !"#$%&'() !"#$%&'!() !"#=EãáñÉÇ=k~ëÜ !"
equilibrium)·就是在此論文中首次提出的。納殊還證明了對一般的 非合作性博弈，混合納殊均衡一定存在·為今日非合作性博弈論之 發展奠定了最重要的數學基礎。在納殊二十二歲生日那天·他獲得 了博士學位。令人驚訝的是·納殊在撰寫博弈論論文的同時·亦在 研究一個關於實代數簇(real algebraic varieties)的純數學間題。 他對這個間題的解答，以及他對偏微分方程(partial differential equations)和黎曼幾何(Riemann geometry)的研究工作·使他在 1999年獲得一個純數學的大獎一 斯蒂爾獎(Steele Prize)o 納殊拿到博士學位後，旋即受聘於麻省理工學院(MT)·在教授高 等微積分時·納殊認識了一位名叫阿莉西亞·拉德(Alicia Larde)的 物理系學生。他們於1957年結婚·翌年兒子馬田出生·這是納殊 生活最愉快的日子。可惜好景不常，在1959年·三十一歲的納殊 患上了精神分裂症·隨後多次進出精神病院·患病以後·他行為怪 異，無法與人溝通，並不時寫些莫名其妙的信給公眾人物。1963年 納殊辭去教職並和太太拉德離婚。為了能讓納殊安心養病·拉德便 搬家回到普林斯頓·她讓那離了婚的丈夫住在家裹·自己當電腦操 作員·賺錢養他和兒子·透撾拉德的悉心照顧、普林斯頓大學師友 的關懷，和納殊自己的努力·二十多年後·他竟然能奇蹟般康復撾 來·並又開始從事博弈論的研究· 在納殊患病的二三十年間·博弈論有了快速的發展和廣泛的應 用。並成為了經濟學裹一個重要的分枝。而正是納殊的基礎性貢 獻·使博弈論有可能蓬勃發展·因此在1994年，瑞典皇家科學院 諾貝爾獎委員會把經濟學獎頒予納殊和另外兩位博弈論學者約翰· 夏仙義(John C.Harsanyi)和雷恩哈德·塞爾頓(Reinhard Selten)o 4■
4 ÉèìáäáÄêáìãF !"#$%&'()*+,-./01234* !"#$%&'()*+,-$./0 !"#12 !"#$%&'()*+,-./0/123456789 !"#$%&'()*+,-./0112(34*5- !"#$%&'=EêÉ~ä=~äÖÉÄê~áÅ=î~êáÉíáÉëF= !"#$ !"#$%&'()*+,-.=Eé~êíá~ä=ÇáÑÑÉêÉåíá~ä Éèì~íáçåëF= !"=EoáÉã~åå=ÖÉçãÉíêóF= !"#$%& NVVV= !"#$%&'( !=EpíÉÉäÉ=mêáòÉF !"#$%&'()*+,-./0$1=EjfqF !" !"#$%&'()*+,-./0123=E^äáÅá~=i~êÇÉF= !"#$%&=NVRT= !"#$%&'(!)*+, !"#$%&'()*+,-.=NVRV= !" ! !"#$%&'()*+,!"-./-0(&1234 !"#$%&'()*+,-./0123#45NVSP= !"#$%&&'()*+,-./01234'(5 !"#$%&'()*+,-./012&345678 !"#$%&'()*+,-./0123456789: !"#$%&'(!)*+,-!./01234567 !"#$%&'()*+, !"#$%&'()*+,-./0#12345#6 !"#$%&'()*+,-./0123,4567 !"#$%&'()*+,-.=NVVQ= !"#$%& !"#$%&'(!)*+,-./01234(5678 =EgçÜå=`K=e~êë~åóáF= !"#$%&=EoÉáåÜ~êÇ=pÉäíÉåF
巧合的是·該年剛好為博弈論始創人馮·諾伊曼和奥斯卡·摩根斯 坦(Oskar Morgenstern)合作的巨著一《博弈論和經湾行為》 (The Theory of Games and Economic Behavior）出版五十周年。 年1年中ds 厅年中4对信 5■
5 !"#$%&'()*+,-./0123456/785 =Elëâ~ê=jçêÖÉåëíÉêåF= !" !"#$%&' EqÜÉ=qÜÉçêó=çÑ=d~ãÉë=~åÇ=bÅçåçãáÅ=_ÉÜ~îáçêF= !"#$
馬·諾伊曼 博弈論是由1903年出生的美籍匈牙利數學家 馮·諾伊曼於1928年所創立的。馮·諾伊曼被 譽為最後一位數學全才·他不單在多個數學和理 論物理的分枝做了很多基礎性的工作，還參加了 原子彈的創造和設計·並建造了第一部電腦。不 難想像他擁有驚人的記憶力和思考速度·以下的 這個故事很能說明這一點。 話說有人間馮·諾伊曼以下的間題。假設甲、乙兩人相距二十 哩·並以時速十哩騎著單車向著對方前進。一隻蜜蜂從甲單車的前 輪飛向乙單車的前輪·再折返甲單車的前輪·如是者來來回回直至 兩部單車相遇，如果蜜蜂的速度是每小時十五哩·牠來來回回總共 飛了多少哩呢？ 這個問題有兩種解法·方法一是找出蜜蜂每一次來回的路程·然 後把它們加起來。這個方法直接但費時。方法二是留意到兩車將於 一小時後相遇，所以蜜蜂便飛了十五哩。馮·諾伊曼毫不費勁便立 刻給出正確的答案·這使間者以為他一早便知道第二個方法·然而 他只是在腦中快速地把所有距離加起來！ ■6
6 !"=NVMP= !"#$%&'() !"#=NVOU= !"#$%&'() !"#$%&'()*+,-.$%/0 !"#$%&'()*!+,-./0% !"#$%&'()#*+,-./01 !"#$%&'()*+,-./01& !"#$%&'( !"#$%&'()*"+,-./012!3456 !"#$%&'()&*+,-./01234'(5, !"#$%&'()*"#$%&+,-..//01 !"#$%&'()*+,-./012$3445567 !"#$ !"#$%&'(&)*+,-./)012345'6 !"#$%&'()*+,-.%()/01234567 !"#$%&'()*+,-./012345678)9 !"#$%&'()*+,-./01234567&89 !"#$%&'()*+,-./ !"
博弈論與經濟學 當馮·諾伊曼在1928年創立博弈論時·它只是純數學裹的一個 分枝。博弈論為人所知並被廣泛應用到經濟學上·始於1944年《博 弈論和經濟行為》的出版·這本由馮·諾伊曼和普林斯頓大學經湾 學家摩根斯坦所寫的博弈論巨著，首次嘗試運用博弈論去分析經濟 間題。博弈論嘗試為決策者之間的衝突與合作建立數學模型·它研 究每一個决策者如何根據其他對手的策略·去作出最有利於自己的 策略。由於經濟活動往往涉及策略的運用，博弈論因而大派用場· 設想某地的兩份報紙，《水果日報》和《方向日報》正在考慮進 行一場减價戰。我們可以嘗試運用博弈論去為它們作分析·為了簡 化所考慮間題的複雜性·我們將假設《水果日報》和《方向日報》只 可選擇减價一元或不减價這兩種策略·如果兩報都不减價·則各可 在該年赚取二千萬元（此處用的數字純屬虚構）。若己方减價而對 方向 水果日報VS 報 7
7 !"#$=NVOU= !"#$%&'()*+,-./ !"#$%&'()*+,-./012345=NVQQ= !"#$% !"#$%&'()*+,-./012 !"#$%&'()*+,-./012'()34567 !"#$%&'()*+,-./0123456789: !"#$%&'()*+,-#./012345678- !"#$%&''()*+,-./01234,5 !"#$%&' !"# !"# !" !"#$%&'()*+,-./012&345$167 !"#$%&'()*+,- !"# !"# !"#$%&!"'()*+,-.(/0&!"123 !"#$%& !"#$%&'() !"#$% !"#$
手不减價·己方可赚取三千萬元而對手只能赚到五百萬元。若兩報 同時减價·則各可賺取一千萬元。明顯地·雙方的最終得失取決於 自己和對手所選的策略。表一總結了兩報面對的情况·表内的數字 單位為千萬元。每個格子中左邊的數字是《水果日報》的利潤·右 邊是《方向日報》的利潤。 方向日報 减價 不减價 减價 1,1 3,0.5 水果日報 不减價 0.5,3 2,2 表一 在進一步分析這個例子前·讓我們先看看博弈論裹另一個著名的 例子一疑犯困境(Prisoner's Dilemma)。它是納殊的論文導師艾 伯特·塔克(Albert Tucker))所構造的。 8■
8 !"#$%&'()*+,-./&012*+3456 !"#$%&'()*+,-./"0123456'78 !"#$%&'()*+,-./0!%123)4%56 !"#$%&'()*+,-./ !"# !" !"# ! !"#$%&'()*+,-../0123 %456 !=EmêáëçåÉêDë=aáäÉãã~F !"#$%&'( !"=E^äÄÉêí=qìÅâÉêF= !"
疑犯困境 話説約翰和彼得被警方以藏械罪 00 名拘捕。警方懷疑他們曾分別參與 認罪？ 多宗嚴重罪案。兩人被單獨囚禁和 不認罪？ 盤間。警方分别向兩人提出以下的 條件，如果二人都承認曾參與那些 罪案·每人將被判入獄三年。若他 們都不認罪·則各判入獄一年。如 果一人否認而另一人認罪·並且願意轉作污點證人指證對方，那不 認罪者將被判入獄五年，而認罪者則可獲釋放。這樣·兩個疑犯面 對的情况如下（見表二)，每個格子中左邊的數字是約翰的刑期· 右邊是彼得的刑期· 彼得 認罪 不認罪 認罪 3,3 0,5 約翰 不認罪 5,0 1,1 表二 細心的讀者或會留意到，上面兩個例子雖然表面上很不同·但它 們卻有著不少共同點。首先·兩例中都有兩個參與者·我們不妨叫 它們做A和B。例如A是《水果日報》·B是《方向日報》：或 A是約翰·B是彼得。另外，每個參與者都有雨個策略C和D。 例如C是减價而D是不减價：或C是認罪而D是不認罪·總共可 以有四種情况出現：(C,C),(C,D),(D,C)和(D,D)。這裹(C,D)表示 A選C而B選D·(C,D)稱為-個策略組合(strategy portfolio)。 9
9 !"#$%&'()*+ !"#$%&'()*+, !"#$%&'()*+, !"#$%&'()*+, !"#$%&'()*+, !"#$%&'()*+, !"#$%&'()*+, !"#$ "%&'()*+,-./ 0/12&34 !"#$%&'() *+,-./01(23456 !"# !" !"#$%&'()*+&,- !"#$%& ! !"#$%&'()*+,-./01*)234(56 !"#$%&'()*+,-. +/012*3"45 =^==_ =^= !"# _= !"# ^= ! _= !"#$%&'()*+,&-.=`==a =`= !=a= !"#=`= !=a= !"#$% !"#$%&E`I`FI=E`IaFI=EaI`F==EaIaF =E`IaF= ^==`==_==aE`IaF= ! !=Eëíê~íÉÖó=éçêíÑçäáçF=