Second-price定價機制

當使用密封式拍賣標售單一物件時，以出最高標金者得標，但得標者支付的價錢是次高標金，這稱為second-price定價策略。

如果以賣方的利益來思考，會覺得此規則莫名其妙，是平白讓利給投標者。不過second-price定價策略背後的動機，是要讓投標者真實出價，以極大化社會福祉，並非要極大化賣方的利益。

至於此定價策略為何可以讓投標者真實出價，我們可以看這張表的分析。假設投標者為bidder i，他對拍賣物品的真實評價是v_i，而寫下的標金是b_i。b_i與v_i的大小關係可分為b_i>v_i, b_i=v_i, 以及b_i<v_i三種，對應到表中的三個列(row)。假設除b_i外其他投標者最高的標金是max(b_{-i})。v_i與max(b_{-i})的大小關係也可以分為v_i>max(b_{-i}), v_i=max(b_{-i}) 與v_i<max(b_{-i})三種，分別對應到表中的三個欄(column)。表中格子中顯示的是上述兩種關係各種組合下bidder i所能獲得的payoff。這裡的payoff定義成bidder i在此拍賣中所能獲得的效用。如果bidder i未能贏得拍賣，則bidder i的效用值為0，否則bidder i的效用值為bidder i對拍賣物品的真實評價v_i減掉他要付的價錢p_i。注意因為是second-price定價策略，所以p_i=max(b_{-i})<b_i (這裡不考慮平手的情形)。

表中所有payoff為0的格子表示bidder i未贏得拍賣物，不為0的格子中的值就是v_i-p_i的結果。為何有些格子有0又有其他值呢？這表示bidder i可能贏也可能輸掉拍賣。例如右上角那個格子，代表bidder i的標金b_i大於他對物品的真實評價v_i，但v_i小於所有其他人的最高標金max(b_{-i})。此時b_i可能大於也可能小於max(b_{-i})。如果b_i小於max(b_{-i})，那麼當然他的payoff為0。如果b_i大於max(b_{-i})的話，他要付的價格max(b_{-i})減掉v_i是小於0的，所以payoff為負值。

因為是密封式拍賣，投標者是無法事先得知v_i與max(b_{-i})的大小關係的，他能控制的只有選擇哪種投標策略(b_i>v_i, b_i=v_i或b_i<v_i)。經過理性分析，bidder i會發現選擇中間那列(b_i=v_i)在各種可能情況(v_i>max(b_{-i}), v_i=max(b_{-i}) 與v_i<max(b_{-i}))下所獲的的payoff，都不會輸於其他兩種策略(b_i>v_i及b_i<v_i)，只可能會更好。所以，bidder i的最佳策略就是選擇b_i=v_i (真實出價)。

實際上密封式拍賣標售單一物件採用second-price定價策略時，投標者都會真實出價嗎？並不見得。原因是投標者並不見得會認知到真實出價會是他的最佳策略。必須讓所有投標者都能理解上述分析，才能達到機制設計所想要達到的目的。

有效率的贏家決定機制

greedy(貪婪)這個字眼一般而言是負面的，不過用在演算法設計時，並不伴隨有任何道德評價(這並非意味電腦科學家沒有道德標準)，而僅僅代表某種解題策略。具體而言，如果一個問題的最佳解需關照全貌才能得知，貪婪演算法會設法將其分階段求解，將每一個階段最好的解答集合起來成為整個問題的解。

貪婪演算法不見得能找到問題的最佳解，但它的價值在於能夠快速解題。以圖中的組合拍賣為例。我們有A, B, C, D, E五項物品要進行拍賣，每項物品只有一件，且有P1 ~ P5五位投標者，每位投標者的標金(bid)及想要的物品組合(bundle)已顯示在圖中。我們假設投標者均是single-minded (不妥協的)，即不接受只給他部分物品的結果。例如P2要A, B, C三項物品，願意出54元，如果結果是分配給P2 A, B兩項，就算只要P2付40元，P2也是不會接受的。換句話說，他們不會有「沒魚蝦也好」這種心態。

在上述情形下，要找出能夠使得贏家標金總和最高的贏家組合，是一個weighted set cover問題。這個問題是一個NP-Hard問題，沒有甚麼有效率的演算法。如果先把所有可能的贏家組合列出來，再找尋其中的最佳組合(如圖中所列的那樣)。這屬於暴力作法，時間法複雜度可是嚇人的O(2^n)。

這裡就有一個貪婪的演算法。我們先計算每位投標者投標金額除以所投標物品的數量，當作投標者的性價比，然後從性價比最高的投標者開始挑選，如果投標者需求的物品尚未配置出去，就配置給該投標者，否則就跳過此投標者。

在我們的例子中，P4的性價比70/2=35是所有投標者最高的，所以配給P4所要的DE兩項物品。性價比次高的為P3 (93/3=31)，但P3所需求的BDE無法如數配給(DE已分配給P4)，所以跳過P3。性價比再其次的為P1 (63/3=21)，其所需求的ACD一樣無法如數配給。第四個考慮的是P2，他所需求的ABC可以配置沒有問題。最後的贏家組合就是P4和P2。

不過，這種組合拍賣問題的精隨並不在找出贏家組合(雖然找出贏家組合的時間複雜度的確是個問題)，而是決定每位贏家該付多少價錢的訂價策略(pricing strategy)。此策略須使得所有投標者有動機誠實出價。以臨界值(critical value)的訂價策略為例，贏家所應付的價錢，是(在所有其他投標者標金不變的前提下)仍能使該贏家不會輸掉拍賣的最小標金。這個定價策略的基本精神其實與second-price auction類似。在我們的例子中，P2應該付42元而P4應該付62元。

拍賣的機制設計

拍賣(auction)也是一種配置資源的方式，適用於資源供應者與需求者並不隸屬同一機構的情形，屬於一種非合作賽局。

將拍賣視為一種資源配置機制，背後的想法是當資源不足以滿足所有的需求者時，應當要將資源配置給最能善用此資源的需求者(所謂物盡其用)，以極大化社會福祉(social welfare)。不過，我們要如何找出最能善用資源的需求者呢? 基本想法是投標者對資源(拍賣物)的評價，會反應在他們提出的標金上，因此提出最高標金的投標者，就是最能善用此資源的需求者，應該將資源配置給他。

這個想法有幾個問題。第一是投標者可能無法客觀地評價拍賣物。這一點我們暫且不論。第二是投標者所提出的標金並不見得純粹是投標者對資源(拍賣物)的客觀評價。在公開拍賣(如英式拍賣)的競價過程中，投標者的標金往往會受到其他投標者提出標金的影響。結果是投標者往往會提出高於評價的標金，造成贏家的詛咒。

為了避免投標者受到外部因素的影響，我們可以採行密封式拍賣(sealed-bid auction)，讓投標者將標金事先寫在一張紙上，密封在信封中交給主持拍賣者，由主持拍賣者拆封後認證最高的投標金額以決定最後的贏家。

這種拍賣方式仍然有一個問題，即投標者並不見得會將心中對拍賣物的評價真實反應在標金上。如果說謊(例如壓低標金)可以使投標者有更高的利潤，則投標者就沒有動機真實出價。

如果投標者並沒有真實出價，則拍賣作為一種資源配置機制，就無法達到極大化社會福祉的目標(因為資源可能錯誤地配置給並非最能善用此資源的需求者)。有一門學問叫做機制設計(mechanism design)，即在探討如何設計諸如拍賣的機制，以達成諸如極大化社會福祉的目標。

與一般人的認知不同，拍賣的機制設計，目的並非在極大化買方或賣方的單方面利益。假設一個對拍賣物評價為v的投標者贏得拍賣，並付出p的金額時，其效用(utility)為v-p (可以想成差額算贏家實際賺到的)，且此交易賣家可獲得的效用為p。對其他參與拍賣的競標者而言，效用值為0。則這場拍賣的社會福祉為所有參與者(包含買賣雙方)的效用總和為(v-p)+p+0=v，與贏家所需付的金額p無關，但與贏家對此拍賣物的評價v有關。因此，機制設計的首要目標就是要找到對拍賣物評價最高的競標者。要做到這點，最簡單的就是要保證投標者皆能誠實出價。如何保證呢？我們並非訴諸法律等外部機制，而是透過設計拍賣規則，使得對競標者而言，誠實出價乃是他們的最佳策略。Second-price auction即是這樣的一個機制。

當有多項物品進行拍賣，且競標者乃針對多項物品的組合提出單一標金時，即變成組合拍賣(combinatorial auction)。此時光要找出某個贏家組合，以使得該組合的標金總和為所有組合中最大者，就已經是計算複雜度很高的問題，可以對應到電腦科學中的weighted set cover problem。然後更複雜的來了，該怎麼決定每個贏家應付多少錢，才能使誠實出價是投標者的最佳策略呢？經典的Vickrey-Clarke-Groves (VCG)演算法在理論上解決了這個問題。不過，VCG演算法的計算複雜度太高，學者後續提出了各種approximation或保證誠實出價但不保證社會福祉最佳的greedy演算法。