有沒有比較好懂得例子解釋維克里-克拉克-格羅夫斯機制？

01-06

范里安那本書上寫的格羅夫斯機制和維克里-克拉克-格羅夫斯機制太晦澀了。例子也不好懂，請問各位大牛又沒更容易理解的例子，生活上的最好。

首先，估計生活中例子不好找，原因見最後。

其次，簡明闡釋VCG機制例子最簡單就是密封二價拍賣。如果不是贏家，第二高出價者本可贏得競拍。而VCG就是在分配有效前提下支付自己對別人的損害，現在第二高出價者「失去」了拍品，所以贏家正好該付他/她的估值。密封二價拍賣情形里這恰好就是第二高出價。

再給一個簡單例子。這裡我們想把貨物從S運到T，中間有兩個中轉地AB和四位運輸商1234。SP旁邊數字運輸成本。假設政府用VCG定價，我們算算我們該付四位商人各多少錢。路線有12和34兩種，前者更省錢。確定線路12，先算該付1多少。假設1突然沒了，我們只能改走34，這時2減少10塊成本，34共增加25成本，25-10等於15，所以該付1號15塊錢，同理可算得2號也該得15塊錢。同樣演算法可知：如果把4號成本改成15，那我們可以只付成本價，給12各付10塊；如果改成95，那就得給12各付90塊錢。

如果加一位商人，結果如何？假設AB間多了一位運輸商，成本2塊，還是政府用VCG定價。現在成本最低路線是325。先把3拿掉，這時成本最低線路是12，多了1的10塊成本，少了5的5塊成本，所以3應該拿5塊。再拿掉2，這時走12最節省，多了1的10塊成本，少了2的2塊成本，所以我們應該付28塊錢。最後看2，如果2突然沒了，我們只能走34，這時多4一個15塊成本，少5一個2塊成本，所以2要拿13塊。這個例子說明VCG在為網路中定價時也不具有單調性（有些類似布雷斯悖論）。例子來自Narahari的Game Theory and Mechanism Design，這本書個人覺得講得比其它書都要好，新的機制設計教材有些也會借鑒這本書。

最後解釋開頭問題。VCG理論性質是很好，但在現實中基本沒有應用。Ausubel和Milgrom（2006）和Rothkopf（2007）解釋了這一點。大致說來包括以下幾點：拍賣中賣家收益不高；有通訊等成本時性質糟糕；計算複雜（NP完全問題）；面對串謀非常脆弱等等。Rothkopf文章題目就叫Thirteen Reasons Why the Vickrey-Clarke-Groves
Process Is Not Practical。不過，雖然實際中不好用，VCG結果可作其它問題基準，在理論上提供幫助。Green-Laffont定理說明滿足一些數學條件前提下，一個機制既有效又佔優實施當且僅當它是Groves機制（VCG是特殊情形）。如果其它機制結果可以逼近VCG，也不錯。

彩蛋。雖然生活中VCG很少見，但有一種很類似的拍賣叫GSP（generalized price auction）。例子就是搜索引擎賣廣告：同一頁面有很多廣告位，商家按每次點擊價格投標，實際付下一位置廣告商投標價。GSP均衡沒有VCG那麼好，大家不愛說真話，但也不錯（local-envy free，廠商不會妒忌自己廣告位前後的商家），而且好算。這個確實是現實例子。

參考文獻：

Ausubel L M, Milgrom P. The lovely but lonely Vickrey auction[J]. Combinatorial Auctions, 2006, 17: 22-26.

Edelman B, Ostrovsky M, Schwarz M. Internet advertising and the generalized second-price auction: Selling billions of dollars worth of keywords[J]. The American Economic Review, 2007, 97(1): 242-259.

Green J R, Laffont J J. Incentives in public decision making[J]. 1979.

Narahari Y. Game Theory and Mechanism Design[M]. World Scientific, 2014.

Rothkopf M H. Thirteen reasons why the Vickrey-Clarke-Groves process is not practical[J]. Operations Research, 2007, 55(2): 191-197.

VCG的intuition就是你要支付「在efficient allocation下，你的存在給別人帶來的externality」。就如之前的答案提到的第二價格拍賣法就可以看成VCG的一個應用。不過解釋貌似可以更簡單一點？比如假設有N個人，A是估價最高的100塊，B是次高的90塊。注意，efficient allocation應該把東西給估價最高的人，以下稱一個人贏了=他估價最高。

如果這場A參加了，那最後就是A贏了；如果A不參加，B就贏了，但其他N-2個還是輸。所以對其他N-2個人來說，A的參加不對他們造成任何影響，但對B從贏變輸，從allocation上看，獲得快感從90塊變0，所以A需要支付B因為A參與損失的90塊。

再來看B，B參與不參與都是A贏，從allocation上看，參與不參與對A和其他N-2個人都不會造成影響，所以B不需要支付錢。

最後剩下的N-2個人，類似的，他們參與不參與不會造成任何影響，所以支付也為0。

總結，A支付90塊。這也是第二價格拍賣法應該得出的結果。而在實際implement VCG的時候，你只要告訴參與者：每個人說個估值，東西會給估值最高的人，你要支付「在efficient allocation下，你的存在給別人帶來的externality」。參與者會計算出說真話是weakly dominant strategy，所以大家都會說真話。

例子不太會舉，但是VCG機制的idea我認為可以簡單說一下。這個VCG就是解決最優化社會福利的問題而被設計出來的。可以把整個機制拆分成兩部分理解，第一部分是如何分配資源，第二部分就是計算每個人要付的錢。

第一部分很好理解，就是單純找出最優化社會福利的解。這部分是一個純演算法問題，並不涉及truthful之類的概念，雖然對於combinatorial setting下面並不好多項式時間求解但是這並不重要。大體上這一步就是把最值錢的物品給了價值最高的人。

第二部分就是計算每個人要付的錢。這個時候分配方式已經固定了，那麼剩下的就只是通過調節這個錢來使得整個機制滿足truthful的調節。VCG的貢獻就在於他找到了一個合適的通過計算對於其他玩家marginal cost的方式來作為他應該支付的金額，從而保證了truthful。

沒有理解未來機制會是什麼樣子。