「卡」和「片」

我今天心中浮現一個疑問，為何我們常說的信用卡、悠遊卡的「卡」字音和義和英文的card幾乎是一樣的。如果查網路資料可以發現一個說法，這是因為「卡」字是由英文card音譯而來。如果真是這樣，那麼「卡片」這個詞，似乎是由音和義組合出來的新詞，採「卡」為音而以「片」為義。

此外，前人翻譯時好像並沒有一定的標準。聖誕卡、賀卡的「卡」採用音譯，但明信片、賀年片的「片」卻採用意譯。如果當初統一用意譯，也許現在我們說的是信用片、悠遊片、和健保片。

「瀑布」與「永恆族」

昨天看了鍾孟宏導演的新作「瀑布」。這部片的時空背景是當下的台北，全片戲劇的成分又比前作「陽光普照」淡了些，全片沒有特別的高潮起伏，但仍可感受到單親家庭的脆弱以及面臨危機時的衝擊。鍾導把一些看似與主題無關的日常瑣事剪進電影中，作為這個時代的剪影，但不知用意是要堆砌情感(像是枝裕和)，還是要刻意沖淡戲劇感？

今天看了「永恆族」。是標準的漫威電影。導演趙婷表現稱職，雖然看不出他在「游牧人生」片中的個人風格，但故事性比一般曼威宇宙系列電影豐富許多，故事講得很完整，人性刻畫也比較深刻，感覺每個角色都有血有淚，並非單純在看動作和特效而已。

倒扣機制對分數的影響

採用單選題且無倒扣的測驗方式，可以讓胡亂選答的考生獲得一定的分數。採用答錯倒扣的機制，目的在於讓心存僥倖的亂答考生無利可圖，甚至得不償失，不過倒扣的機制也同時改變了分數的分佈。採用傳統的調分機制也許可以還原原始分數的分佈。

舉例而言，胡亂選答的考生在四選一單選且不倒扣的考試中，可望得到25分，顯然無法反應出考生真正的程度。如果要讓這類考生的期望分數降為0，可以設計成答對時每題得x分但答錯時每題要扣y分，且滿足 0.25x<0.75y。例如x=4時，y要大於4/3 (如1.5)。這樣胡亂選答的考生的期望得分會是負的，所以沒有動機亂答。

不過倒扣的機制也同時改變了分數的分佈。例如原本有1/2與1/3答題成功機率的考生，所得到的分數會從沒有倒扣時的50分和33分，降到有倒扣時的31.25分和8.33分(以答對一題得4分答錯扣1.5分計)。雖然全對的考生分數仍然是滿分100，滿分考生和有1/2與1/3答題成功機率的考生的分數比例會從原始的6比3比2，改變成約14比4比1。顯然中等程度考生的分數被倒扣機制拉低了。

以前唸書時，老師會用的一個調分機制是原始分數開根號再乘以10。雖然這個調分規則有戲謔的成分在，但似乎可以用來校正倒扣機制所造成的分數分佈。上述例子的分數31.25分和8.33分，經過這個規則處理後，會各變成55.9分與28.68分，比較接近無倒扣機制時的分數。至於胡亂選答考生的分數則不受影響。

時間不夠時準備考試的一種策略

記得以前考試前夕，常常會發現時間不夠，不可能唸得完全部要考的範圍內容。那時常常在兩個策略間掙扎。一是利用剩餘的時間將全部要考的範圍全部掃過一遍，這樣至少不會看不懂題目。另一個策略是穩扎穩打，務必確保看過部分的出題都會答，雖然這樣可能只看到考試範圍一半的內容。

到底哪種策略比較好呢。這應該跟題目的題型(選擇題還是計算題)、出題範圍涵蓋的完整度(每個單元都有出題還是偏重少數幾個單元)以及計分方式(有無倒扣、是否有部分分數)有關。

如果是選擇題(如單選四選一)、不倒扣、且出題涵蓋完整均勻的話，我的推論是第二種策略較好。我的推論基於下面幾項假設。一、將要考的範圍內容全部掃過一遍的話，因為沒辦法看得仔細，在考試時無法讓你確定問題的答案，只能讓你縮小答案的範圍(例如刪除那些你沒看過、顯然是亂入的答案選項)。二、只精讀考試範圍一半的內容的話，會讓你答對此範圍的全部題目，但剩下一半的題目你完全都不會。

我假設第一種策略的效應是每一題都可以讓你在兩個選項中挑一個(而且其中一個選項是正確的)，如此一來的分數期望值會是50分。至於第二種策略，會讓你拿到一半題目札實的50分，還有剩下一半題目亂猜的期望分數12.5分(四選一單選不倒扣)，總共是62.5分。所以結論是，第二種策略比較好。

事實上，就算是答錯會倒扣分數，仍然是第二種策略較佳。原因是第一種策略有50%的機率會答錯倒扣，而第二種策略答錯倒扣的機率只有37.5%。

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