0
2017 年10月19——21日，中國計(jì)算機(jī)學(xué)會學(xué)科前沿講習(xí)班（CCF —— ADL）在上海財(cái)經(jīng)大學(xué)舉辦。本期主題是《計(jì)算經(jīng)濟(jì)學(xué)的理論與應(yīng)用》，邀請了七位來自清華、上海財(cái)經(jīng)大學(xué)、上海交通大學(xué)、香港大學(xué)的計(jì)算經(jīng)濟(jì)學(xué)領(lǐng)域?qū)＜乙约拔浵伣鸱?、萬向集團(tuán)的負(fù)責(zé)人，從計(jì)算機(jī)經(jīng)濟(jì)學(xué)（算法博弈論）的基本原理、到拍賣、采購機(jī)制設(shè)計(jì)、區(qū)塊鏈及分布式商業(yè)，并結(jié)合理論在實(shí)際中的應(yīng)用場景進(jìn)行了詳盡的分享和解讀。
陸品燕是上海財(cái)經(jīng)大學(xué)信息學(xué)院教授，理論計(jì)算機(jī)科學(xué)研究中心（ITCS）主任。在獲得清華大學(xué)計(jì)算機(jī)系博士學(xué)位后，他加入微軟亞洲研究院，2015年離開微軟研究院加盟上海財(cái)經(jīng)大學(xué)領(lǐng)銜組建了ITCS。有50余篇科研論文在STOC、FOCS、SODA、EC等頂級計(jì)算機(jī)理論及博弈論的國際會議和雜志發(fā)表，榮獲ICALP2007、FAW2010、ISAAC2010等重要國際會議最佳論文獎。2017年擔(dān)任計(jì)算經(jīng)濟(jì)學(xué)方向重要國際會議WINE 2017的程序委員會主席。他的主要研究方向是理論計(jì)算機(jī)，并注重與其它學(xué)科的交叉，例如與經(jīng)濟(jì)學(xué)、博弈論交叉后誕生的算法博弈論（algorithmic game theory)，主要關(guān)注拍賣理論及機(jī)制設(shè)計(jì)。
計(jì)算經(jīng)濟(jì)學(xué)，或稱算法博弈論。作為本次課程的首位講師，他首先作了一個(gè)關(guān)于算法博弈論的簡單介紹，并重點(diǎn)分享了算法博弈論研究中的三條主線。
算法博弈論在現(xiàn)實(shí)中的應(yīng)用有如，搜索引擎網(wǎng)址排序、淘寶賣家排序等?？偟膩碚f，在市場行為、交通道路設(shè)計(jì)、導(dǎo)航問題、在線廣告拍賣、選舉等方面，算法博弈論都能發(fā)揮作用。他告訴雷鋒網(wǎng)，他認(rèn)為業(yè)界從業(yè)者也有必要了解算法博弈論，尤其是上述搜索引擎、電商平臺等產(chǎn)品負(fù)責(zé)人，減少可能的作弊行為，為用戶帶來更良好的體驗(yàn)。除了主動學(xué)習(xí)，業(yè)界主動引進(jìn)相關(guān)理論人才也是一種選擇。此外，陸品燕教授還重點(diǎn)講解了設(shè)施選址問題的機(jī)制設(shè)計(jì)和最佳拍賣機(jī)制（optimal competitive auctions）。
沒有參與 CCF 線下課程的朋友不要著急，雷鋒網(wǎng)人工智能培訓(xùn)平臺AI慕課學(xué)院獲 CCF 獨(dú)家線上視頻版權(quán)，觀看本次講習(xí)班完整視頻+PPT可戳：http://www.mooc.ai/course/193。完整再現(xiàn)各路專家現(xiàn)場授課、交流的場景。
以下是陸品燕教授演講原文，雷鋒網(wǎng)作了不改變原意的編輯：
博弈論的一大基本假設(shè)就是，游戲中的玩家或者參與的人是理性的。當(dāng)然，游戲不一定是字面意義上的游戲，現(xiàn)實(shí)中任何涉及到多方不同利益的情況都可以認(rèn)為是博弈。但事實(shí)上人并不理性，例如行為經(jīng)濟(jì)學(xué)就已經(jīng)指出這一點(diǎn)。那么什么叫理性的人？這里討論的不是哲學(xué)的理性而是數(shù)學(xué)的理性。數(shù)學(xué)的理性是指，當(dāng)一個(gè)人他有很多行為選擇的時(shí)候，他會有非常強(qiáng)的欲望實(shí)現(xiàn)效用函數(shù)即收益最大化，或者說成本最小化，并依據(jù)此來做出選擇。當(dāng)然，不同的人可能有不同的效用函數(shù)或者成本函數(shù)，每個(gè)人對同一件事情的衡量標(biāo)準(zhǔn)不同，但是決策標(biāo)準(zhǔn)是相同的。這個(gè)假設(shè)有兩個(gè)層面，第一層是模擬出個(gè)人的效用函數(shù)，第二是他總是去最優(yōu)化函數(shù)。
第二個(gè)重要因素是競爭的環(huán)境。這是指同一時(shí)間有多個(gè)玩家參與博弈，多個(gè)玩家都想最優(yōu)化他們各自的利益，而且他們不同的行為會影響到彼此的利益。
所以，博弈論試圖分析的就是在一個(gè)競爭的環(huán)境里面，理性的玩家是怎么選擇，行為又會產(chǎn)生什么后果。最簡單的例子就是石頭剪刀布，收益的關(guān)系可以利用類似的矩陣來展示。
這里還引入了均衡的概念，博弈均衡是指使博弈各方實(shí)現(xiàn)各自認(rèn)為的最大效用，在博弈均衡中，所有參與者都不想改變自己的策略的這樣一種相對穩(wěn)定、靜止的狀態(tài)。
與以前一般的優(yōu)化問題不同，一般的優(yōu)化問題總是在尋找最優(yōu)解或者近似最優(yōu)解，但在博弈論中很難找到全局最優(yōu)，每個(gè)玩家希望最大化自己的收益，但是處在有很多玩家的競爭環(huán)境，所以它的解一般是用均衡或者穩(wěn)態(tài)來描述。穩(wěn)態(tài)的意思是，大家卡在一種狀態(tài)，誰也不想離開這個(gè)狀態(tài)，因?yàn)閱为?dú)離開對他沒有好處。但實(shí)際上，這樣的穩(wěn)態(tài)也有一些問題，比如說囚徒困境。
還有一個(gè)問題是，在一個(gè)定義了每個(gè)人的效能函數(shù)，或者成本函數(shù)的博弈中，穩(wěn)態(tài)是不是總是存在。
馮諾依曼在1928年的時(shí)候就證明，如果是在兩個(gè)玩家參與，并且是類似石頭剪刀布的零和博弈（兩個(gè)玩家完全對抗，效能函數(shù)之和是定值或0）的情況下，穩(wěn)態(tài)總是存在的，而且用比較簡單的線性規(guī)劃方法來找到。而在其他更復(fù)雜的，如多個(gè)玩家、不是零和博弈的情況下，納什證明穩(wěn)態(tài)也總是存在，就是所謂的納什均衡。
在傳統(tǒng)博弈論中，涉及的玩家很少，只有兩三個(gè)，但當(dāng)競爭環(huán)境變得非常復(fù)雜，比如資本市場，傳統(tǒng)博弈論就不太適配。而算法有一個(gè)重要特性就是復(fù)雜性，在加入復(fù)雜性這個(gè)維度后的博弈論，玩家行為會更加多元化，這也是算法博弈論研究的重點(diǎn)。
剛剛提及，博弈論認(rèn)為，模擬出來后的最終狀態(tài)應(yīng)該是穩(wěn)態(tài)，如果這是很簡單的游戲，基本有預(yù)測能力。但當(dāng)系統(tǒng)非常大時(shí)，還能不能做這樣的預(yù)測？
從純粹博弈論的角度來說，肯定可以，比如能夠證明納什均衡的存在。但在實(shí)際中，研究者能否有效地計(jì)算出均衡呢？如果計(jì)算不出，那么就不能進(jìn)行有效的預(yù)測。
還有一個(gè)更深刻的問題，理論上的預(yù)測能否出現(xiàn)在現(xiàn)實(shí)中。當(dāng)計(jì)算機(jī)都不能算出均衡的時(shí)候，市場為什么就能達(dá)到這個(gè)均衡？如果不能達(dá)到，預(yù)測有何意義？這些都是系統(tǒng)變得越來越復(fù)雜時(shí)，我們需要去研究和回答的。
算法博弈論在現(xiàn)實(shí)中應(yīng)用包括公共基礎(chǔ)設(shè)施規(guī)劃、電商平臺、車牌拍賣。實(shí)際上，我們可以通過算法和策略設(shè)計(jì)博弈。比如車牌拍賣，各地根據(jù)不同的需求設(shè)計(jì)不同的規(guī)則，需求可能是控制數(shù)量，減少污染；或者保持公平性。博弈的規(guī)則會影響玩家的效能函數(shù)。
歸納來說，算法博弈論或者計(jì)算經(jīng)濟(jì)學(xué)是從計(jì)算機(jī)科學(xué)的維度來研究博弈論，包括可計(jì)算性、復(fù)雜性、算法設(shè)計(jì)的角度。
1、研究的是博弈論、經(jīng)濟(jì)學(xué)中的計(jì)算問題，包括復(fù)雜性等，博弈論為計(jì)算機(jī)科學(xué)提供了一些新問題。
第一個(gè)問題，經(jīng)濟(jì)學(xué)告訴我們，納什均衡和市場均衡總是存在，那么如何計(jì)算平衡？這一類計(jì)算平衡問題不同于以往研究方向：判定問題或者優(yōu)化，對應(yīng)不動點(diǎn)計(jì)算，給計(jì)算機(jī)科學(xué)創(chuàng)造了新的計(jì)算問題和計(jì)算復(fù)雜類。
第二個(gè)問題更像優(yōu)化問題。但是傳統(tǒng)的優(yōu)化問題約束、目標(biāo)函數(shù)可知。但是在博弈的最優(yōu)策略的時(shí)候，不止是一個(gè)方案，除了自己的想法，還要預(yù)測對方的行為，是一個(gè)交互式的過程。
現(xiàn)實(shí)中的問題有，如何給商品定價(jià)以達(dá)到利益最大化。比如蘋果怎樣給新發(fā)布的產(chǎn)品定價(jià)。市場調(diào)查可以得到預(yù)期反饋，包括價(jià)格和購買人數(shù)。如果只有一個(gè)產(chǎn)品，我們只要研究需求曲線基本就可以了。但是在產(chǎn)品配置不同，定價(jià)也不同的時(shí)候，如何能讓高價(jià)產(chǎn)品有足夠多的消費(fèi)者，如何讓低價(jià)產(chǎn)品不至于出現(xiàn)太高性價(jià)比吸引走原高價(jià)產(chǎn)品的客群等。傳統(tǒng)的優(yōu)化問題就是，定完價(jià)格、分配方式，收益是確定的。但是博弈情況下，需要預(yù)測潛在買家對于不同的價(jià)格策略有什么反饋。
第三個(gè)問題，如何計(jì)算合作博弈中的“核”(Core)及沙普利值(Shapley value)。合作博弈是指一些參與者以同盟、合作的方式進(jìn)行的博弈，博弈活動就是不同集團(tuán)之間的對抗。
2、本質(zhì)上是算法設(shè)計(jì)、優(yōu)化問題，但是考慮到眾多理性人和競爭環(huán)境，傳統(tǒng)的算法設(shè)計(jì)就變成了機(jī)制設(shè)計(jì)問題。機(jī)制設(shè)計(jì)被稱作“經(jīng)濟(jì)學(xué)中的工程學(xué)”，因?yàn)榇蠖鄶?shù)的經(jīng)濟(jì)學(xué)研究是去解釋世界，而機(jī)制設(shè)計(jì)是設(shè)計(jì)。
在競爭環(huán)境下，設(shè)計(jì)的算法運(yùn)行實(shí)際效果可能并沒有那么好。例如搜索引擎和淘寶商家排名。比如搜索引擎的PageRank網(wǎng)頁排名，是由Google發(fā)明的一種由根據(jù)網(wǎng)頁之間相互的超鏈接計(jì)算的技術(shù)，Google用它來體現(xiàn)網(wǎng)頁的相關(guān)性和重要性。算法會根據(jù)用戶的搜索關(guān)鍵字匹配網(wǎng)頁，而一些公司就開始利用這種規(guī)則，衍生了一種專門的職業(yè)——SEO，搜索引擎優(yōu)化。工程師通過一些技術(shù)手段，彼此增加鏈接或者在頁面上使用隱形的關(guān)鍵詞，使得搜索引擎的算法認(rèn)為該網(wǎng)頁與關(guān)鍵字的匹配度很高，這樣就破壞了PageRank和頁面排名的初衷。
類似的也體現(xiàn)在淘寶賣家。他們會通過刷信譽(yù)刷銷量等方式提高自己的排名。而這些，是背后公司和用戶都希望杜絕的。
這些都有一個(gè)共同點(diǎn)：設(shè)計(jì)者并不能掌握網(wǎng)頁或者賣家的信息，即無法掌握所有的輸入信息真實(shí)性。第二，輸出的結(jié)果能否真實(shí)實(shí)現(xiàn)也是不能確定的。
在與這些理性或者說自私的玩家進(jìn)行交互的時(shí)候，簡單的算法設(shè)計(jì)就變成了機(jī)制設(shè)計(jì)問題。不僅需要滿足計(jì)算機(jī)科學(xué)方面的有效性要求等，還需要滿足從博弈論的角度，考慮用戶的反饋。這是在網(wǎng)絡(luò)時(shí)代，特別網(wǎng)絡(luò)經(jīng)濟(jì)時(shí)代非常重要的。
3、引入計(jì)算機(jī)視角，研究對象還是博弈系統(tǒng)。
舉一個(gè)例子，比如研究經(jīng)濟(jì)學(xué)中的納什均衡。從社會福利方面來看，經(jīng)濟(jì)學(xué)其實(shí)很早就知道不一定最優(yōu)，比如囚徒困境。但之前經(jīng)濟(jì)學(xué)只能確定，哪一類博弈是最優(yōu)或者不是最優(yōu)的，計(jì)算機(jī)科學(xué)有近似比的概念，當(dāng)它不是最優(yōu)的時(shí)候，可以研究是否是近似最優(yōu)，于是引入了最差均衡效率(PoA)等。
這也體現(xiàn)在宏觀看市場調(diào)節(jié)是否有效方面。在某些領(lǐng)域，市場充分競爭的最后，整體的社會利益是一個(gè)非常好狀態(tài)。但是在另外一些領(lǐng)域，彼此的惡性競爭可能就會失效，整個(gè)社會在非常不好的狀態(tài)，于是會研究是否需要政府干預(yù)走出這個(gè)博弈。
所以，我們引入了近似比的概念來衡量它多不好，因?yàn)橛行┎皇亲顑?yōu)的情況能夠接受，有些不是最優(yōu)的情況可能相差太大，需要改變。
第二從時(shí)間的角度來研究有效性。納什均衡是玩家不斷改變自己的策略，以至于最終慢慢收斂到一個(gè)動態(tài)平衡的結(jié)果。也就是說這是一個(gè)動態(tài)的過程，這個(gè)動態(tài)過程是不是趨向于穩(wěn)態(tài)或者很快的趨向于穩(wěn)態(tài)。如果純粹從數(shù)學(xué)方面來說，一般得出的結(jié)論是最終會收斂，
那么在不同動態(tài)的假設(shè)中，收斂究竟會多快呢，比如它是不是在一個(gè)多項(xiàng)式時(shí)間里收斂到納什均衡，這也是計(jì)算機(jī)科技引入的新概念。以前經(jīng)濟(jì)學(xué)只研究收斂或不收斂，但是在現(xiàn)實(shí)中這個(gè)區(qū)別非常重要。如果能夠很快收斂，他們的行為可能與現(xiàn)實(shí)比較相符。如果動態(tài)非常慢，你可能可以假設(shè)，系統(tǒng)還處在動態(tài)變化的過程，另一個(gè)方向就是，可否去干預(yù)該系統(tǒng)，使它能夠比較快的收斂。
附提問：
提問：當(dāng)用戶面臨信息過載的情況，面對傳統(tǒng)經(jīng)濟(jì)學(xué)的理性人假設(shè)可能就不是很適用，這是否超出了計(jì)算經(jīng)濟(jì)學(xué)的研究上限？
回答：這是一個(gè)很好的問題。我們假設(shè)每個(gè)用戶最優(yōu)化自己的效能函數(shù)或者成本，當(dāng)用戶在一個(gè)復(fù)雜的系統(tǒng)中，可能出現(xiàn)信息過載，以至于用戶沒有收集到足夠的信息，或者是沒有足夠的可能計(jì)算能力。這樣他無法算清什么是最優(yōu)。實(shí)際上，在傳統(tǒng)的博弈論中也有有限理性的假設(shè)，比如計(jì)算能力有限等，這也是計(jì)算經(jīng)濟(jì)學(xué)一個(gè)重要的研究方向。
相關(guān)文章：
7位大咖齊聚CCF ADL計(jì)算經(jīng)濟(jì)學(xué)課程，探索算法博弈論，區(qū)塊鏈、人工智能與經(jīng)濟(jì)學(xué)的交叉
雷峰網(wǎng)原創(chuàng)文章，未經(jīng)授權(quán)禁止轉(zhuǎn)載。詳情見轉(zhuǎn)載須知。
