匹配(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高到一種程度，就直接原文照登不壓縮，加上表頭後最後產生的檔案比原始檔還大。

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