博弈論與機制設計學習筆記一、基本概念

已經決定進入博弈論與機制設計這個大坑裡了，就寫點學習筆記加深一下理解，彙報學習進度被老闆批評了，的確是自己學的太爛，這次認真學。第一次的筆記很簡單，相當於科普了。

一、什麼是博弈論？

博弈論，英文Game Theory。其中，博弈（Game）一詞，指的是理性且智能的決策者或參與人之間的互動。

理性，英文Rationality。在收益得到明確定義的情況下，參與人選擇策略（Strategy），以使收益最大。

智能，英文Intelligence。指的是參與人能夠計算他們的最優策略。

關於博弈論的發展。

1920s-1940s：約翰·馮·諾依曼（John von Neumann）和奧斯卡·摩根斯坦（Oskar Morgenstern），博弈論的奠基者，著作《博弈論與經濟行為》（The Theory of Games and Economic Behavior）。

1974，肯尼斯·阿羅（Kenneth Arrow），憑藉社會選擇理論獲得諾貝爾經濟學獎。

1994-2012年是井噴期，有11位博弈論學家獲得諾獎。他們是：

約翰·納什（John Nash），約翰·海薩尼（John Harsanyi），萊茵哈德·澤爾騰（Reinhard Selten），1994年，博弈均衡分析（著名的納什均衡等等）。

威廉·維克瑞（William Vickery），1996年，拍賣理論（著名的第二價格拍賣，比如eBay就是用的他的理論）。

羅伯特·奧曼（Robert Aumann），托馬斯·謝林（Thomas Schelling），2005年，博弈參與人之間的衝突與合作方面的分析。

萊昂尼德·赫維奇（Leonid Hurwicz），埃里克·馬斯金（Eric Maskin），羅傑·邁爾森（Roger Myerson），2007年，機制設計理論的原創貢獻（邁爾森拍賣是目前的研究主流之一）。

勞埃德·夏普利（Lloyd Shapley），埃爾文·羅斯（Alvin Roth），2012年，提出穩定配置理論和市場設計實踐（著名的夏普利值，Sharpley value）。

如果學習這個方向，這些人名你一定會都記住的。

二、什麼是機制設計？

我們用遊戲比賽舉個例子，比如說你是一支隊伍的隊長。你的隊伍在一個比賽的小組賽階段遇到了這個場景，你們組的前兩名出線，打另一個組的前兩名。按照常規，第一名打另一個組的第二名。

現在有這樣一個問題：另一個組有個特別特別牛逼的隊伍，你打死也不想跟他們對上的那種，突然爆冷了，排在了第二名。那麼現在你是你們組的第一名，如果不想八強賽被對面幹掉，那麼一個合理的選擇是接下來的比賽放水，讓自己滑到第二，這樣就避開了。這種事情歷史上也不是沒發生過，實例就不提了。

但是站在觀眾角度來說，如果不考慮粉絲，單純從比賽來看，觀眾需要的是大家拼盡全力，展現一場精彩的比賽。但是我們按照博弈論的概念，每個參與人（即遊戲隊伍），都是理性且智能的，他們的目的是拿到更好的名次，所以你不能指望大家道德水平全體上升來解決這個問題。

所以唯一的解決途徑就是遊戲機制。我們要設計（Design）一個好的機制（Mechanism），這個機制的目的是讓參與者的策略儘可能符合機制設計者的預期，我們需要這樣一個規則（Rule），去激勵（Incentive）參與者選擇我們期望的策略。

再舉一個著名的布雷斯悖論（Braesss Paradox），圖片來自CS346A的lecture。

這個場景是說，在一個圖（Graph）上，有一群人（比如司機），從一個共同的出發點 ，到一個共同的目的地 ，有兩條路徑，一條是 ，另一條是 。

解釋一下各個參數， 是選擇這條路的人的比例， ， 只在選擇這條路的人的比例確定的前提下，走這條路的開銷（Cost，比如說時間）。

考慮Figure 1a，人們自發地選擇道路的情況下，不難（證明從略，真要證的話最好還是用後面的納什均衡）推斷出平衡狀態下，兩條路徑的人數各一半，這樣總的時間開銷為 。

現在增加一條路 ，而且不需要時間就能到達，看起來改善了道路條件，實際呢？

由於 ，所以 的開銷永遠小於等於 ，同理 的開銷永遠小於等於 。每個人都會選擇 這條路線，總時間開銷為 ，這是符合理性且智能的。但是這樣一來的總開銷，由於 ，就變成了 ，這顯然比之前沒添加新路線時候的 要差。

這個現象被稱為無政府主義的代價（The Price of Anarchy，簡稱POA，也是博弈論研究的主題之一），它的具體計算方式是： ，這裡的具體數值是 。

三、什麼是均衡？

納什均衡（Equilibrium），直觀點就是說到了一個穩定的狀態（Steady State），每個人都沒有動機（Motivation）去單方面的改變自己的策略，因為這不會給自己額外的收益。

策略不一定是純（Pure）的，也可以是混合（Mixed）的。比如著名的石頭剪刀布，如圖所示的二元矩陣（Bimatrix）。

這是一個零和（Zero-Sum）博弈，雙方的收益在任何一種場合下都是相反數，和為零。那麼你的最佳策略永遠取決於對手出什麼，而沒有哪一種純策略是納什均衡的。

純策略納什均衡（Pure-Strategy Nash Equilibrium）與混合策略納什均衡（Mixed-Strategy Nash Equilibrium）的區別就在於此，任何一個有限的博弈都有一個混合策略納什均衡（這個證明來自於納什定理），但不是每一個博弈都有純策略納什均衡。在這裡，我們表述為：任何二元矩陣博弈都有納什均衡。

二元矩陣的零和博弈，計算納什均衡的複雜度必然是多項式時間的（can be computed in polynomial time），但非零和博弈卻沒有多項式時間的複雜度。由於我們是從理論計算機科學（Theoretical Computer Science）角度研究博弈論與機制設計，所以必須關注複雜性。這裡，後者不是 -hard的，我們叫它PPAD-hard。

最後，我個人想法是，關於各類在博弈論領域引申出的xxx-hard，xxx-completeness問題，真的是一個恐怖的範圍。CS346A這門課最後一章專門討論了這些，看得我頭皮發麻，沒有絲毫想法......

END

參考文獻：

《博弈論與機制設計》Y·內哈拉里著

Stanford CS346A：Algorithmic Game Theory

推薦閱讀：