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

匹配(matching)問題

匹配(matching)是將人與人、人與物、或物與物進行一對一、多對一、或多對多的配對。電腦科學家對此議題並不陌生，圖論(graph theory)中亦有最大匹配(maximum matching)的問題，尤其是在二分圖(bipartite graph)中的最大有權重/無權重匹配，更常常用在電腦科學家的問題建模上。

不過電腦科學家或圖論學家探討的匹配問題，目標在極大化某個全域效能數值，是不會考慮被處理對象對結果的喜好的。如果是人參與的匹配，這樣的演算法會有適用性的問題，這時就該輪到賽局理論出馬了。

像圖中這樣四個人與四個物的配對，以及圈起來的配對結果，我們說已經達到帕雷多最適(Pareto optimal)。講白點是說此匹配已經是每個人都很滿意的結果，因為我們已經無法在沒有人會更不滿意的前提下，單獨使某人或某些人更滿意。換句話說，如果我們要使某人或某些人更滿意，勢必會有人會得到(比起現在結果)更不滿意的結果。

與優化單一目標值的傳統匹配問題不同，這種考慮到參與對象偏好(preference)的匹配問題，存在多個帕雷多最適解，因為本質上這是個多目標最佳化問題。不僅如此，將匹配視為一個合作賽局的話，匹配解還需滿足穩定性(stability)的條件。

給定一個匹配結果，如果某個或某些個參與者脫離此結果另行配對，結果不會比現在匹配的結果更差，而且至少有一個參與者對匹配結果更滿意，則此匹配結果是不穩定的。例如，圖中的匹配結果就是不穩定的。如果a3與a4脫離此賽局另外配對(交換彼此的物品)，a3與a4都會更滿意。

帕雷多最適結果不見得是穩定解，穩定解(如果有的話)一定是帕雷多最適。而這只是人與物的匹配，只有單方面(人這一方面)對配對結果有偏好，另一方面是沒有的。Gale and Shapley探討的男女婚配問題，是有雙向偏好(two-sided preference)的。另外，上述提到的皆是一對一(one-to-one)匹配，更進階的問題有多對一(many-to-one)與多對多(many-to-many)配對。雙向偏好多對多匹配應該是目前最困難的問題，許多研究者還在投入研究中。

如果這樣的複雜度還無法難倒研究者，我們還可以進一步擴充偏好的表示能力。在多對一或多對多的匹配問題中，參與者對可能匹配對象的偏好是設定成對個別對象的偏好排序。實務中，參與者可能比較想對各種匹配對象的「組合」進行偏好排序。例如，如果一個學校想組一個籃球隊，在招募新生時，校方對「中鋒、前鋒、大前鋒、後衛」這樣組合的偏好程度，顯然會高過「中鋒、中鋒、中鋒、後衛」這樣的組合。如果是這樣，對於n個可能的匹配對象，我們可能需要排序O(2^n)種組合。

另外，我們上述說明隱含了偏好關係皆為全序(total ordering)，如果考慮偏序(partial ordering)的偏好關係，這個問題會變得更為複雜。所以，別小看匹配這個看似簡單的問題。

Two General's Problem

想起唸博班時，讀到Nancy Lynch寫的Distributed Algorithms。這本書在還沒談任何分散式演算法之前，就列出了不少的impossibility result。其中最令我吃驚的定理是，若兩個程序純粹以訊息交換(message passing)的方式溝通，那麼在訊息可能遺失的前提下，沒有任何協定可以保證這兩個程序能達成完全一致的共識(consensus)。不能達成共識的原因並非溝通的事情太複雜。例如，可以想像這兩個程序只是很單純地想共同確定某個二元變數A的值是0還是1。

如果兩個程序連單一變數的值都無法達成共識，那麼其他fancy的演算法(leader election, termination detection, gloal snapshot, self-stabilization, ...)都是建立在隨時可能垮掉的基礎上。

在網路的課程中，我們通常稱這個困境為Two General's Problem。根據這個定理，TCP的three-way handshake可能導致client與server兩端對TCP連線是否已經建立起來有不同的看法。例如，three-way handshake的最後一個ack如果沒有被server收到，則client會認為連線已建立，而server會認為未建立。而這個問題理論上是沒有辦法解決的。

理論與現實的差異就在這裡。這個理論上不完美的TCP three-way handshake已經為網際網路貢獻幾十年了，而每年學生都還是要從頭開始認識它的不完美。

萬能資料壓縮演算法

有一個定理說，不存在一個萬能的無損資料壓縮演算法，總是能把任何長度的輸入字串，壓縮到比原來的長度還小。

這個定理的證明也不難。以長度為n的位元串(bit string)為例，總共有2ⁿ個，而長度小於等於n-1的位元串有2^n-1個。資料壓縮演算法可以視作一個將輸入字串對應到輸出字串的函數，而無損壓縮的要求是這個函數必須為一對一(injective)，否則解壓縮會有問題。但是，不存在從n個元素到n-1個函數的一對一函數，所以推論不存在這種演算法。

事實上，如果存在這樣的壓縮演算法，那把它的壓縮結果用同樣演算法再壓縮一次，豈不可以再縮得更小? 重複此動作，資料大小終究會為0。

換句話說，對於任何無損資料壓縮演算法，我們總是可以找到某個輸入字串， 使得壓縮後的結果沒有更好。

我不記得我唸書的時候有沒有學過這個定理，但說真的我們應用時好像不太care(?) zip 程式好像偵測到原始資料的entropy高到一種程度，就直接原文照登不壓縮，加上表頭後最後產生的檔案比原始檔還大。

部落格原作者的講解真不錯。

Line貼圖的左右鏡像建議

在line的對話框中，對方的文字出現在左邊，自己的文字出現在右邊。所以有向對方鞠躬道謝之類的貼圖時，圖中人物是由右邊向左邊彎腰鞠躬的。從傳送者的角度來看，這是很合理的。

不過，貼圖出現在接收者的對話框中時，會變成一個出現在左邊且向左邊鞠躬的圖樣。這樣子變得很奇怪，因為這時候接收者是在右邊啊。如果雙方都傳送類似這樣的貼圖，就會出現兩個彷彿向左膜拜致敬的貼圖。

如果line公司可以提供貼圖創作者一個選項，讓傳送者和接收者看到不一樣的貼圖，就可以免去這樣的尷尬。就我舉的例子，接收者應該要收到傳送圖形的鏡像(但圖形中文字不能鏡像，所以本質上就是另一張雙生貼圖)。