為什麼 Google 的搜索廣告拍賣採用 GSP 機制，而不是 VCG 機制？

12-05

效果廣告競價機制

GSP 是Generalized second-price auction （廣義二價拍賣）的簡稱，VCG 是 Vickrey-Clark-Groves 機制的簡稱。

先簡單談一下Google 採用GSP 拍賣搜索關鍵詞的歷史。較早的搜索廣告拍賣設計是雅虎的Overture 設計，採用廣義一級價格拍賣：如果有K 個廣告位，那麼競價最高的K 個商家每人贏得一個，並且支付競標的價格。一級價格拍賣最大的問題是策略選擇很不穩定，商家會頻繁地修正出價。如果最高出價者出價2塊，次高為1.5塊，那麼最高者就有激勵把出價將到1.51，仍然贏得最好的廣告位同時省下0.49。可是這同時次高者或許正為了拿到最好的廣告位將出價往上修正。

Google 使用GSP 主要就是為了避免廣義一價拍賣中不斷參考相鄰出價進行的策略修正。在GSP 下，每個贏家只需要支付次高出價的金額，從而沒有激勵把出價修正到次高出價。

而多物品拍賣中的VCG 機制中，每個贏家支付的是他給其他人帶來的負外部性，即他由不參與變為參與帶給其他商家利益的損失。由於廣告位本身的異質性和商家對廣告位的估值的不同，這種損失的計算並不簡單。

由上，Google 使用GSP 而不是VCG 的原因可能包括：
1. 歷史問題。開始的設計使用了GSP，如果現在用VCG 替代，評估好壞不是太容易的事情。
2. 複雜度。VCG 的優點主要在於參與人投標真實估值是弱佔優策略，但是最直接的缺點是在多物品拍賣中理解起來遠不如GSP 簡單。
3. 利潤考慮。從基本模型的理論分析角度，GSP 在特定均衡中帶給Google 的利潤並不比VCG 的差（參考[2]）。

最後，在上面的例子里，每個參與人只需要一個物品（廣告位）。在更一般的多物品拍賣中，例如spectrum auction，參與人的需求可能是多個物品的組合，那時候由於物品之間可能存在的互補性使用VCG 機制會出現各種各樣更嚴重的問題（參考[1]）。

References:
1. Ausubel and Milgrom (2006), "The Lovely but Lonely Vickrey Auction", Combinatorial Auctions, MIT Press.
2. Edelman, Ostrovsky, Schwarz (2007), "Internet Advertising and the Generalized Second-Price Auction: Selling Billions of Dollars Worth of Keywords". American Economic Review 97(1), 242-259

幾個月前課上做presentation，正好講的是這裡獲贊同數最多的 @唐前鋒教授答案中提到的論文，Edelman, Ostrovsky, Schwarz (2007)。因為這篇文章的目的就是來解決題主的問題，所以我把我的PPT發上來希望能拋磚引玉。此外由於知識的極度欠缺，我自己也對這篇文章也有不少疑問希望可以得到這裡老師和同學的指正。

主要的觀點是，不對GSPA的NE進行精鍊的話，很難說GSPA就比VCG強。但個人覺得Edelman, Ostrovsky, Schwarz (2007)受於所處時代的局限性，對GSPA進行精鍊的假設似乎並不令人信服。

首先題主的疑問是有道理的，因為GSPA乍看上來不如VCG，缺少了幾個VCG擁有的良好性質：

所以Edelman, Ostrovsky, Schwarz (2007)選擇比較某些具有穩定性質 of GSPA的NE和VCG的NE。這裡他們的想法是把每個廣告位看成一個與廣告商配對獨立的個體，藉助two-sided matching theory里的stable assignment的概念來精鍊：

具體的整個問題可以轉化要求以下兩個最優化問題同時達成：

第一個constrained optimization的意思是要保證Pareto最優，第二個constrained optimization保證沒有一對廣告商和廣告位願意脫離原來的配對，並組成一個新的配對以讓雙方都有利可圖，具體見Roth and Sotomayor（1994）。

存在性由強對偶性定理保證：

順便說一下這個博弈應該可以看做是合作博弈的特殊形式，所以stable assignment應該算作概念「in the core」的特殊形式：

Edelman, Ostrovsky, Schwarz (2007)的貢獻在於他們給出了一個簡單的characterization， locally envy-free equilibria來刻畫他們研究的對應stable assignment的GSPA的NE：

但我覺得他們關於競價的廣告商數目的條件似乎多餘：

到這裡，他們得出了locally envy-free equilibria除了簡單外，優於VCG的重要原因：

此外，他們似乎還類比SPA和English auction的情況，認為GSPA和generalized English auction strategic equivalent，給出了以下定理（但是Gomes Sweeney（2014）看起來並不支持這個strategic equivalence）

此外他們為什麼決定locally envy-free equilibria，而不是一般的GSPA的NE，才是值得關注的邏輯我也並不信服：

我的猜測是他們當時並沒有一個stable assignment under incomplete information的定義所以才這麼hand-waving：

用一個簡單的例子來對比說明GFP、GSP與VCG三種競價機制的特點。

假設某網頁有2個廣告位，存在3個廣告主參與競爭。廣告位1每小時可獲得200次點擊，廣告位2每小時獲得100次點擊。廣告主1、2、3對於每次點擊的預算估價分別為10元、4元、2元。

在GFP（Generalized First-Price ）競價機制下，廣告主按出價將序排列，出價最高的廣告主獲得廣告位1，出價次高的廣告主獲得廣告位2，以此類推。廣告主向搜索引擎的付款即為自己的出價。在上述例子中，則廣告主2隻需要出價2.01元（超過廣告主3的出價）即可保證自己獲得廣告位（類似於圖1(a)中A點）；而廣告主1想要獲得廣告位1，僅需出價2.02元（超過廣告主2的出價）。每個廣告主都希望通過最小的付出而獲得每小時點擊次數最多的廣告位，則廣告主2將提高自己的出價到2.03，從而重新獲得廣告位1。這個過程將不斷重複，直到出價達到某個廣告主的最高預算（類似於圖1(a)中B點），在這裡，即廣告主2可以負擔的4元，此時廣告主2無法再通過提價獲取廣告位1，為了使自己付款最少，它將把自己的出價從4元銳減為2.01元，從而保證自己獲得廣告位，廣告主1也相應將出價銳減為2.02元（類似於圖1(a)中C點）。此後重複上述循環。可見最高價出現成鋸齒狀。競價結果非常不穩定。

在GSP（Generalized Second-Price）競價機制下，廣告主還是按照其出價降序排列，出價最高的廣告主獲得廣告位1，出價次高的廣告主獲得廣告位2，以此類推。但廣告主向搜索引擎的付款不再是自己的出價，而是自己所在廣告位的下一個廣告位上的廣告主的出價。假設廣告主誠實出價，則在上述例子中，廣告主1、2、3分別出價10元、4元、2元。競價結果為廣告主1獲得廣告位1，其向搜索引擎付款200*4=800元；廣告主2獲得廣告位2，其向搜索引擎付款100*2=200元。此情況下廣告主將不再會頻繁地調整自己的出價，因為調整自己的出價無法影響自己的付款。相比於GFP，GSP機制的可博弈性更低。從圖形上理解，則最高價曲線的的鋸齒狀程度更低。一個不嚴謹的理解，可以認為最高價曲線的積分對應於搜索引擎的收入，GSP下最高價曲線接近矩形，若只考慮波動部分收益（即不考慮積分相交部分），則GSP機制下的收益為GFP機制下的兩倍（矩形面積為三角形的兩倍）。

在VCG（Vickrey-Clark-Groves ）競價機制下，廣告主仍按照其出價降序排列，出價最高的廣告主獲得廣告位1，出價次高的廣告主獲得廣告位2，以此類推。不過廣告主的付款計算方式更複雜。獲得廣告位的某個廣告主需要支付的金額為它對其他獲得廣告位的廣告主造成的損失，即其外部效應（externality）。在相同的例子中，廣告主1、2、3分別出價10元、4元、2元。競價結果為廣告主1獲得廣告位1，廣告主2獲得廣告位2。廣告主2所需支付的金額仍然為100*2=200元；但廣告主1所需支付的金額變為600元=200元+400元，其中200=100*2代表其導致廣告主3沒能獲得廣告位的損失，400=（200-100）*4代表其導致廣告主2無法獲得廣告位1，從而損失100次點擊對應的損失。此例中，GSP下搜索引擎的收益800+200&>=VCG下搜索引擎的收益600+200。文獻[1]給出理論證明，若廣告主誠實出價，則GSP機制收益至少不低於VCG機制收益。

綜上，Google採用GSP機制而非VCG機制的原因總結如下：

相同情況下，GSP更賺錢；
GSP更易向廣告主解釋；
歷史原因先採用了GSP，而從GSP轉變為VCG之後的收益具備不確定性；
如果真的要從GSP賺到VCG，光是系統實現與測試就是很大一筆花費；
業界，能夠保證一個還不錯的穩定收益就已經令人滿意了。（個人不嚴謹的想法）

參考資料：
[1]Benjamin Edelman, Michael Ostrovsky, Michael Schwarz.INTERNET ADVERTISING AND THE
GENERALIZED SECOND PRICE AUCTION:
SELLING BILLIONS OF DOLLARS WORTH OF KEYWORDS.2005

以上各位從博弈論的角度解釋得很對，歸納起來，AdWords之所以沒有選擇VCG，主要存在的問題是 1). 預期收益可能沒有GSP高，以及 2). 其他參與者的損失成本難以估算，以及由這兩點導致的 3). 系統轉換代價過高
另外從實踐角度補充一個很重要的原因，4). 客戶教育成本驚人。試著向沒有經濟學基礎的幾十萬、數百萬人解釋什麼是VCG拍賣，看他們能不能聽懂？相比之下，GSP機制下只需要告訴廣告主「你的每次點擊付費不會高於你的出價」，真是容易得多。

原因主要有兩點:
1. vcg機制中對贏者的計費採用受損者的社會總效用，在實際中難以計算。
2. 從搜索引擎收益角度來看，vcg作為社會效率最優的拍賣機制帶給搜索引擎的收益是gsp的下限。

Google參考的是競價排名廣告的鼻祖Overture (後被Yahoo收購) 的二價拍賣機制。每個排位的贏家先出價獲得排名，然後只要付出其第二順位的出價價格即可。

這樣做的理由是
1）提供廣告商最優化的廣告費用。減少競價帶來的浪費，提高廣告商的使用體驗。

2）給予廣告商有依可循的價格。防止盲目競價，廣告商不再需要猜測競價的價格，只需要提供最高可承受的價格。這樣小公司也可以參與加入到遊戲中來。

3）廣告商不用擔心在競價中導致浪費，並在一些重要關鍵字中投入大量成本。他們就會投入更多精力在長尾關鍵字數量上。其實，Google也知道廣告商投入預算和競價機制沒有必然聯繫。該花的預算終究是要在Google花掉的。所以不如使用第二拍賣價，讓廣告商在更廣泛的關鍵字中進行競爭。

4）二價拍賣機制也使得後來Google引入的關鍵字質量指標更加順利。

理論上VCG比GSP要更好，但是如果廣告主的出價策略不調整的情況下，GSP的收入會比VCG高很多（這個可以從上面的例子推導出來），所以如果做abtest，google一定會發現VCG實驗桶的收益會比GSP低很多，沒有辦法平滑上線。但是如果直接全量上線，廣告主出價策略調整需要多久，這些未知因素對一家體量如此大的公司來說是不能接受的，因此Google搜索引擎的GSP不會遷移到VCG，VCG比較適合廣告平台第一次使用，這時候商家不會出現比較大的出價跳躍。

歡迎關注我和我的專欄，會對VCG做更加細緻的介紹。計算廣告學 - 知乎專欄

GSP比較好理解，要照顧客戶的理解能力的嘛
《計算廣告》讀書筆記 - 機器鼓勵師手冊 - 知乎專欄

類似Google廣告價位的distribution還是相對較為明確的有大量歷史數據可供參考這樣在寫競價的時候把握還是比較大的因此對於自己的surplus也比較好掌控略想看一次投標啊

各位實際真的想多了，其實就是gsp 掙錢多，而且據說g家有些地方已經用vcg 了。

另外fb用的是vcg. https://m.facebook.com/business/help/www/430291176997542