拍賣的機制設計

拍賣(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演算法。