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