拍賣方法的藝術

「潛水」了兩個月，事關七月、八月初都在科大寫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的價格投標。

用數學去看情侶相處之道

某大電視台剛剛播完了一套電視劇，其中有一幕就是說甚麼男人是來自金星，女人是來自水星之類的東西（本人不確保這些星球所對應的性別是正確的）。因此當情侶一起去看電影時，往往因為大家因為想看的電影不同而吵架（其實係咪電視台D編劇腦作架？我去左戲院咁多年都未見過有情侶係戲院門口嗌交……）。

這個時候，老生常談就是「一人讓一步」、「互相遷就」、「輪流睇自己鐘意o既戲」。聽起來也覺得悶吧。但如果我說，其實這些老生常談是有數學根據的，應該會有趣得多吧！

首先我們要將情況來一個數學建模 (Mathematical Modelling)。假設男的想看電影A，女的想看電影B，那我們可以建立以下的bimatrix：

		女
		電影A	電影B
男	電影A	(2,1)	(0,0)
	電影B	(0,0)	(1,2)

先解釋一下。如果情侶們不能達成共識去看同一套戲，那麼兩方面都不會開心吧，所以我們用(0,0)表示這種情況。如果今次女的遷就男，大家一起看電影A，那麼男的會比較開心，故"payoff"=2，而女的雖然看不到自己喜歡的電影，但最少不用吵架吧，故"payoff"=1，所以左上角的bimatrix entry是(2,1)。右下角的bimatrix entry同理。

然後我們可以用博奕論(Game Theory)去分析了。如果兩個都覺得對方是故意跟自己過不去的話，那就會防著對方而只顧自己利益。利用博奕論內的safety level這個概念，長遠來說，男女的payoff是(2/3,2/3) = (0.67,0.67)。不過這樣的情侶的話，大概也做不長的了，「長遠來說」這四個字意義就變得不大。

但如果兩個是會互相包容體諒的話，那我們就可以將這當成一個Nash Game。得出的結果就是一次遷就男方，一次遷就女方。這樣的話，長遠來說，男女的payoff就是(3/2,3/2) = (1.50,1.50)，比之前的(0.67,0.67)好多了。

之前的討論都是刪去了比較博奕論裏面的computation的。如果有興趣的話可參考UCLA的Prof. Thomas Ferguson著的Game Theory的Part III。