拍賣方法的藝術

「潛水」了兩個月，事關七月、八月初都在科大寫paper，忙到不得了，而八月中下旬就要準備出國和參加一連串的farewell。對了，我現在身處New York，正在New York University的Courant Institute讀PhD in Computer Science。

雖然讀的博士銜頭表面上轉了科，但做的事還是跟數學脫不了勾；這也証明了在科學的學術界上數學幾乎是無處不在的。最近在看一本上，講algorithmic game theory。我見到一個結果很漂亮的，想在這裏和大家分享一下。

有以下這個情況：有一幅名畫要拍賣，而有n個買家。設買家B_i心中看這幅畫的價值是p_i。若買家最後買不到畫，他最終的「滿足度」為0；若他以價格p買了這幅畫，他的「滿足度」為p_i-p。而買家們的目標都是令滿足度盡量大。所以，買家B_i是絕不會以高於p_i的價錢買畫的，因為他不買的話滿足度為0，但他以高於p_i的價錢買畫，滿足度就變了負數。拍賣以「投暗標」方式進行，即每名買家只可向拍賣行提一次價，而這個價是保密的——其他買家是不知道的。

決定名畫誰屬的第一種方法就是大家所想的：價高者得。這個方法叫first price auction。假設買家們都不知道其他買家心中看名畫的價值，那麼他們應如何出價呢？他們就要估其他畫家看這幅畫的價值，對不對？若看這幅畫價值最高的幾個買家都錯誤地低估其他買家的叫價，名畫賣出的價錢恐怕就要大大降低。

有沒有其他方法令買家投標價就是他們各自的p_i呢？有！這個方法叫second price auction。方法是：各買家投暗標後，投標價最高者以投標第二高價購得名畫。即是說，若四名買家投標價分別是14M、12M、8M和6M，第一名買家將以12M價格購得名畫。

這時，大家要仔細想一想。買家的確是會以各自的p_i投標的；因為無論其他人投標價如何，若他們以低於p_i的價格投標，都不可能會有better benefit。以上一段的例子來說，第一名買家不論以14M或13M投標，他最後的滿足度都是14M-12M = 2M；但若他以11M投標，他們滿足度就是0。以低於p_i投標只會令滿足度有減少的風險。

現在回到first price auction。假設買家們還是不知道其他買家心中對名畫的價格，但現時卻有多一點的資料：買家心中價格滿足一個probability distribution。那麼，買家們應該怎樣投標呢？我們可以見到一個很漂亮與second price auction呼應的答案：假設自己心中價格是最高，然後以second highest bidding的預期值（expected value）投標。舉例說，若那個probability distribution是說買家心中價格在6M至18M之間平均分佈，那麼心中價格是14M的買家就應以(6+14)M/2 = 10M的價格投標。