．原載於數學傳播第三卷第二期
．作者當時任職於美國貝爾實驗室
淘汰賽
黃光明
|
．原載於數學傳播第三卷第二期 ．作者當時任職於美國貝爾實驗室 | |||
|
淘汰賽
黃光明 |
|
相信讀者都有參加過淘汰賽的經驗。這是一種很簡單的賽程，每一場比賽有兩個賽員，一個是輸家，一個是贏家，輸家立刻從賽程中淘汰，贏家繼續比賽。當祇剩下一個賽員沒有被淘汰時，賽程告終，剩下的那個賽員被稱為冠軍。因為每一比賽淘汰一個賽員，所以如果開始時有n個賽員參加，則冠軍必在 n-1 場比賽後產生。
一個淘汰賽需要有一個賽程表規定誰和誰比賽。賽程表通常以一個「二元樹」的圖形表示。如圖一是一個五個賽員的賽程表：
這一棵樹有五個起點（小方塊）。A、B、C、D、E 五個賽員每人被指定到一個起點上準備開賽（這樣一個「賽員 → 起點」的映像我們稱之為一個「定位」）。每一個
我們另外有一個表，叫做「勝算表」，是一個 {pij} 的集合，pij。代表賽員 i 和賽員 j 比賽時，前者獲勝的機率。我們也規定
pij+pji=1，圖三是 A、B、C、D、E 間的勝算表。譬如 A 勝 B 的機率是 0.6，勝 C 是 1，……。如果勝算表有下列一性質
則我們說它滿足了「強機率傳遞性」。圖三的表就有這性質，在這情形下，我們可以很自然的說 A 比 B 強，因為 A 無論對抗誰都比 B 的勝算大，同理 B 比 C 強，C 比 D 強，D 比 E 強。
有了賽程表和定位，再有了勝算表，則我們可以直接算出每一個賽員做冠軍的機率。但是這一個機率當然不能反映出各人真正的實力。因為起點有好有壞，譬如圖一中 E 被派到最有利的起點，當然大大增加了他做冠軍的機會。因此如果我們要測出各人的實力，應該要考慮所有可能的定位，然後再算出做冠軍的平均機率，我們以 Wi(T,P) 來代表當賽程表是 T，勝算表是 P 時，賽員 i 做冠軍的機率。
一個有趣的問題是探討 Wi(T,P) 和 P 的關係。譬如當 P 有強機率傳遞性，我們直覺上覺得 P 決定了賽員間孰強執弱，而強的賽員應該有較大的 W(T,P)，不然強弱的觀念就失去了意義。以上這一陳述雖然直覺上很合理，但還祇是一個沒有被證明的猜測。只有當 pij 有更強的性質如
如果我們進一步假設每一個有 n 個起點的 T 出現的機率都一樣，然後再把 Wi(P) 看作 Wi(T,P) 的平均數，則可以證明（參閱3），如果 P 有強機率傳遞性而 i 比 j 強時，Wi(P)>Wj(P)。
如果有了賽程表和勝算表，是不是每個賽員都可以比較任兩個起點孰優孰劣？會不會賽員 A 覺得起點 x 比起點 y 好而賽員 B 覺得反是？如何在起點間找出一個最強的偏序適用於所有的賽員？換句話說這一個偏序祇和 T 有關而和 P 無關。以圖四的樹而言，這些問題有很顯明的答案。對每一個賽員而言，都是越高的起點越好，所以起點間存在一個線性次序，且和 P 無關。圖一的樹也很單純，有四個起點一樣好，另一個（E 所佔者）比它們都好，這也是一個線性次序也和 P 無關。圖五的樹中 y 比 z 好很容易證明，x 比 y 好就不太容易證明了，但實際上線性次序還是存在和 P 無關，看了這幾個例子，也許我們會以為線性次序永遠存在，且和 P 無關，但其實不然。如圖六的樹，起點 x 和起點 y 孰優視 P 而異，且也隨人而異。譬如賽員 A，除了對 B 有可能輸外，對其它賽員都必勝，則 x 對 A 較有利，因為碰到 B 的機會較少。另一賽員 C 除了對其四個賽員有可能贏外，其它都必敗，則 y 對 C 較有利，因為 C 如從 x 出發，則共需贏五場才能作冠軍而這是不可能的事。這一例顯出了這些問題相當複雜，而現在所知道的非常有限（參閱4）。
另一類問題是如何選擇賽程表，譬如圖一、圖四、圖五，都是五個賽員的賽程表，那一個比較好呢？要比較誰好我們先要有一個測定的標準。這標準可以隨淘汰賽的目的而異，這裏我們討論一個最簡單的標準。即當 P 有強機率傳遞性時（即當我們可以說誰強誰弱時），我們希望最強的賽員有最大的機率做冠軍。換句話說我們希望淘汰賽的結果能真正反映出各人的實力，因此我們不希望賽程表中起點的不同會造成太大的影響。從這個觀點出發，如果一個賽程表起點的差異越小，似乎越好。當有五個賽員時，圖五的賽程表滿足這個要求。一般而論，如果一棵樹中任兩個起點的高度差異不超過一時，我們稱之為「均高樹」，因此我們猜測，對任意有強機率傳遞性的 P 而言，均高樹都是最好的賽程表。這一個猜測還沒有被證明，祇在非常特殊的情形下有一些結果（參閱[4,5]）。
在選定賽程表後，主持人還要選定一個「定位」。如果我們的目的仍是希望最強的賽員做冠軍的機會最大，則當然應該把最有利的起點分給最強的賽員。推廣這一精神，則即是說越強的賽員應該佔據越有利的起點（通常比賽中種子隊輪空即是根據這一原理）。但這就牽涉到我們前面提到過的如何決定那一個起點對誰有利的問題。如果這一問題沒有解答的話，我們自然也無從來分派起點。
暫時不管這些困難，我們此處提出一個更有意義的定位標準，即我們不只是要最強的賽員做冠軍的機率最大，我們也要求第 i 強的賽員做冠軍的機率第 i 大，換句話說賽員間強弱的次序要被完全保存下來。我們首先問，是否對何一個賽程表而言，都會有一個具有這種性質的定位呢？如果賽程表是梯樹，則當然有這樣的定位；如果是均高樹，我們就不知道答案了，當賽程表是一棵「完全均高樹」時（即起點間全無差異，淘汰賽常用圖七的定位法（設 ABCD……為強弱次序）：
這方法可以推廣到祇有 2k-m 賽員時。從 2k 賽員的完全均高樹中除去最弱的 m 個賽員，把這些賽員的對手昇高一級，即得 2k-m 賽員的定位。圖八給了賽員數為 3, 5, 6, 7 時的定位。
通常我們覺得這樣的定位法很合理。但是合理的基礎在那裏呢？很顯然的，在某些 P 下，譬如 ABCDE 間相差極微，但他們間任一個都必勝 FGH 中任一個時，則圖七的定位對最強者 A 並不利。事實上 B 和 C 做冠軍的機會都比 A 大。但是另一方面，我們也實在想不出其它更合理的定位。所以問題似乎是如何對這種我們主觀上願意接受的定位法找出一個客觀的基礎來。
也許上面這一個問題應該放在更大的一個範疇裏來看。究竟淘汰賽的目標是什麼？如果是要保持強弱的次序的話，則應該採用梯樹的賽程表，而把越強的賽員放在越高的起點。這樣做保證了越強的賽者做冠軍機率越大的合理結果。但是為什麼不更進一步乾脆取消淘汰賽而即宣佈最強者為冠軍呢？不是更不會出錯嗎？如果要給每個賽員一個做冠軍的機會的話，也有不須比賽只需抽籤而可達到保持強弱次序的辦法。 這樣的討論很清楚的顯示了淘汰賽一定還有別的目標。我想每一個參加過淘汰賽的人對這些目標是什麼，心裡一定都有點眉目，祇是如何清楚的嚴謹的用數學符號表示出來，到現在還是一個未解之謎。
|
|
|
 |
|
（若有指正、疑問……，可以在此 留言 或 寫信 給我們。） |
|
 |
EpisteMath (c) 2000 中央研究院數學所、台大數學系 各網頁文章內容之著作權為原著作人所有 |
| 編輯：李渭天 ／ 繪圖：簡立欣 | 最後修改日期：4/26/2002 |
