4支隊伍怎樣安排比賽決出冠軍最為合理？

01-11

4支隊伍怎樣安排比賽決出冠軍最為合理？合理，即用最少的場次，避免最小可能的意外，決出最公正的結果？數學專業的專家請進！

這個問題是一個典型的數學建模問題，我來試著做一下吧！

一、模型簡述

我們假設有n支隊伍需要排名次，為了簡化問題，我們讓他們兩兩對決，然後在每次比賽只分出勝負而不計比分和每次比賽計比分兩種情況，建立不同的模型來解決。其中前者引入競賽圖，通過雙向聯通競賽圖的性質解決；而後者則利用比分矩陣的性質解決。

二、模型假設：

1.不考慮「場次最少」，使之兩兩對決，進行n(n-1)/2場比賽；

2.模型1中比賽是沒有平局的，模型2中可以讓每場比賽的比分均不等。

三、模型建立及求解

3.1 模型1的建立及求解

在模型1的情況下，我們用圖來表示比賽結果。令圖的頂點表示球隊，而用連接兩個頂點的、以箭頭標明方向的邊表示比賽結果，由勝方指向負方。如圖所示：

即1隊戰勝了2,3隊，2隊戰勝了3,4隊等等。

排名辦法之一就是在圖中順著箭頭找一條通過所有4個點的路徑，如1-&>2-&>3-&>4，然而這種路徑不止一條，如還可以找2-&>4-&>1-&>3，所以這種方法不能決定排名。

另一個方法是計算得分，即勝利次數。比如上圖中四支隊伍得分分別為2,2,1,1,；然而1,2兩隊，3,4兩隊之間就無法說明了。

為此我們用圖論知識來解決這個問題。

競賽圖及其性質

所有邊均有向的圖叫做有向圖，每對頂點之間均有一條邊的有向圖稱為競賽圖，問題歸結為如何由競賽圖排名次。

2個頂點的競賽圖顯然可以排出。

3個頂點的競賽圖有兩種情況，如下圖所示：

其中第一種情況是無法排序的，第二種情況顯然是2-&>3-&>1.

而4個頂點的競賽圖共有4種形式，下面分別討論。

(1)有唯一通過全部頂點的有向路徑1-&>2-&>3-&>4，這種路徑叫做完全路徑，顯然這就是排名順序。

（2）這種情況2顯然第一，其餘3點滿足上文中3個頂點競賽圖的第1種模式，所以排名為{2，（1,3,4）}

(3)同(2),顯然名次為{(1,3,4),2}.

(4)如下圖所示，有不止一條完全路徑，無法簡單地排序。

注意到（4）具有前三者沒有的性質：對於任意一對頂點，存在兩條有向路徑，這種有向圖稱為雙向連通的。

可以證明，所有競賽圖均可歸為以下三類中的一類：

1.有唯一完全路徑；

2.雙向連通；

3.其他類型。

其中1的排名為唯一完全路徑，3中必有對稱情況，並列後可轉化為1或2，所以重點研究2的情況。

雙向連通競賽圖名次

定義競賽圖鄰接矩陣 $A=(a_{ij})_{n imes n}$ 如下：

$a_{ij} =1$ 如果從頂點i到j有一條有向邊

0，else

則上圖中雙向連通圖的鄰接矩陣為

記頂點的得分向量為 $s=(s_{1}, s_{2},L, s_{n})^T$ ,其中 $s_{i}$ 是第i個頂點的得分，則 $s=A*ones(n,1)$ ,即A矩陣乘上一個n維的全1向量，易知上圖得分向量為 $s=(2,2,1,1)^T$ ,依然無法排出名次，不過我們可以繼續計算，令 $s_2=As$ ,則 $s_2=(3,2,1,2)^T$ ,可以證明，越往後算這個向量的排名就越合理，若 $k ightarrow infty$ 時這個向量收斂，那麼我們就用其作為排名依據。

可以證明，這個極限是存在的，具體的證明後邊再說，下面我們討論每場比賽均有比分的情況。

3.2模型2的建立及求解

有n個運動員，同一項目同一標準下進行競賽，i與j的得分之比為 $a_{ij}$ ,如何排序？

我們設每個運動員的評分向量歸一化後的結果為 $omega$ ，則 $a_{ij}=omega _i / omega _j$ ,比分矩陣

就變成了

則有 $Aomega =nomega$ , $omega$ 又稱權向量。由於矩陣特徵值之和等於主對角線元素之和，又主對角線元素之和為n，這說明n是A的最大特徵值，稱為主特徵值，對應的特徵向量稱為主特徵向量。

那麼主特徵向量是否一定存在呢？答案是肯定的。尋找的方法是迭代法，證明下文馬上給出。

3.3極限得分向量存在性證明

對於n個頂點的雙向連通競賽圖，存在正數r使得鄰接矩陣A滿足 $A^r>0$ ,這樣的A稱為素陣。

由Perron-Frobenius定理，素陣A的最大特徵根為正單根 $lambda$ ，其對應的特徵向量為s，且有

$lim(k ightarrow infty )frac{A^k*ones(n,1)}{lambda ^k} =s$

所以模型1,2的最終結果都是其矩陣的最大特徵值對應的特徵向量，在實際中，往往採用迭代法來求此特徵向量。

四、模型修正

在上述模型2中直接使用A矩陣是有道理的，但是仍然有不合理性：因為加權向量是各隊水平之比，而結果卻是各隊的得分。因此更好的方法是讓某個矩陣B的元素代表二者真實水平之比，那麼問題來了，怎麼計算B？

一個很自然的想法是上述得分的比值，即 $a_{ij}/a_{ji}$ ,但是這樣仍然有一個問題，就是萬一分母為0怎麼辦。我們可以假設每個隊伍有一個基礎的分數（知乎的排名演算法對贊同數為0的答案無效，因此採取的辦法是默認回答者對自己的答案有一票贊同）a，那麼令

$b_{ij} = frac{a+a_{ij}}{a+a_{ji}}$

再用B的特徵向量計算排名會合理很多。

五、參考文獻

[1]姜啟源，謝金星，葉俊，數學模型。北京，高等教育出版社，2011年1月。

[2]王樹禾，數學模型基礎，合肥，中國科學技術大學出版社，1996年5月。

[3]陳理榮，數學建模導論，北京郵電大學出版社。

[4]Perron，Perron定理，維基百科。

很不幸題目分類錯了。

這個問題有一半屬於社會選擇理論（Social Choice Theory）。

先來討論一個最平凡的情況：

如果：

A 勝過了 B、C、D；

B 勝過了 C、D；

D 負於 C；

並且比賽結果實際上就反應了兩個人之間的實力水平；

那麼毫無疑問，A 是第一，B 是第二， C 是第三，D 是第四。

問題在於現實生活中有隨機因素和環。

所謂的隨機因素就是，A 和 B 打十次，可能 6 勝 2 平 2 負。但是如果恰好撞到了 2 平或者 2 負的那一次，並且我們以這個為結果，那麼 A 就有可能獲得於自己實際水平不匹配的成績。當然，這在體育比賽中是可以忽略的事情，畢竟賽事年年有，總不至於 A 實力強於 B 但是次次都負於 B，既然有贏有輸，那就不必計較了。

如果我們一定要鑽牛角尖，決出理想的結果，自然是讓兩兩之間對決 100 次，然後根據總體上的勝負情況來看最後兩個隊伍之間的真正的實力對比是怎麼樣的，說不定還能將簡單的勝負關係通過勝負場次的狀況數值化為一種實力差之類的東西。並且，原則上來說，雖然在偶然的情況下可能有環，但是在大量比賽之後依然有環出現的概率會小很多。

麻煩的東西是環。

假定有 A&>B&>C&>D&>A （X&>Y 表示在直接對決的時候 X 勝了 Y，畢竟單場比賽有運氣因素，這也不是不可能的事情）。

如果採取世界盃決賽的方式，即，將四隊分成兩組，然後兩組的勝者之間決出冠亞軍，敗者之間決出三四名，就會出現這樣的情況：如果 A、B 在一組，那麼 A 至少能獲得亞軍，而如果 D、A 在一組，那麼 A 至多只能獲得季軍。

這也就是題主口中說的不合理的來源之一：環的存在。

即便我們進行了循環賽，我們也不一定能破解環，我先列一個最坑爹的情況：

A&>B，A&>D；
B&>C，B&>D；
C&>A，C&>D；

毫無疑問，D 沒戲了，但是 A、B、C 要怎麼辦？並列冠軍？嘛，這樣也好。但是直觀上來說，我們只能接受 A、B、C 相互打平的時候以打平結束，而對於這種成環的情況，還是會忍不住用別的標準再來一決勝負。

這樣說起來，雖然比賽和投票很像，但是還是有區別的。先說它們類似的地方吧：

有若干個候選人（參賽者）；
目的是得到一個候選人（參賽者）的排序；
公正的比賽和投票需要滿足中立性：即結果由選票決定，而不由候選人位置決定（比如說，如果一個比賽總是讓第一個登場的選手獲得第一名，第二個第二名，那麼它就不滿足中立性）。

不同的地方在於：

選票和比賽結果：一張選票是對於所有候選人的一個排序；一個比賽結果是對於兩個候選人之間的一個排序。
（選票中的「&>」具有傳遞性）
公正的投票需要滿足匿名性：任何兩張選票都是等效的，不會因為投票者是某個人而因此獲得更大的權重，獨裁是非匿名性的極致：獨裁者的權重為 1，其他人沒有權重。
公正的比賽制度需要避免這種情況：（假定每場比賽都是勝者得 3 分，平各 1 分，負者 0 分）A 和 B 之間進行 10 場比賽，B 和 C 之間進行 3 場，A 和 C 之間進行 1 場比賽。（這兩條是說：選票可以單方面疊加；但是比賽結果是不應該單方面疊加的，如果採取積分制度，只應該進行多輪比賽，不應該允許兩方單獨進行比賽，除非是為打破平局。選票可以疊加的根本原因在於：選票總是同時給出一個完整的排序，但是比賽永遠只是在兩個對手之間進行。）
化約關係：一張選票總可以化約為 $frac{n(n+1)}{2}$ 場比賽結果（n 是候選人數目，比如說 A&>B&>C 可以化約為三場比賽結果：A&>B，A&>C，B&>C）；但是兩兩之間的 $frac{n(n+1)}{2}$ 場比賽結果不一定能化約為一張選票（同樣是三人的情況，A&>B，B&>C，C&>A 以及 B&>A，C&>B，A&>C 各自都不能化約為一張選票，但是將兩者重新組合之後倒是有可能化約為如下兩張選票：A&>B&>C 和 C&>B&>A，但是與此同時，我們也可以將這六個結果組合成如下兩張選票：C&>A&>B 和 B&>A&>C ，這就充分體現了兩者之間的差別）。

下面介紹一個比較新的概念：Condorcet 贏家。

將一張選票拆分為 $frac{n(n+1)}{2}$ 個有序對，如果 A&>B 的數目比 B&>A 的數目多，那麼 A 就勝於 B，如果 A 在和其它玩家的比較中都勝出了，那麼 A 就是 Condorcet 贏家。正是由於這種計分法會把一張選票全部拆成兩兩對比的情況，因此它也適用與一般的比賽的結果判定中。

當然，如果出現了環的話，Condorcet 贏家就不一定存在了。（關注贏家的另一個理由是，或許我們可以分別依次遞歸地決出 1、2、3、4 名，但是由於阿羅不可能性定理，我們知道這在某些情況下一定會帶來違反獨立無關性條件的結果。）

但是，雖然這個標準可以搬到比賽中來，這並不意味著這個標準就是一個沒有爭議的標準。畢竟在投票的時候，有可能 Condorcet 贏家是沒有辦法被其它投票方式選出的。考慮如下情況：

3 張選票：A&>B&>C
2 張選票：B&>C&>A
1 張選票：B&>A&>C
1 張選票：C&>A&>B

這時，A 是 Condorcet 贏家，因為 A 和 B 比較的時候 A 贏了 4 次輸了 3 次；A 和 C 比較的時候也是如此。但是，如果我們採用另外一種方法，比如說讓一張選票上的第一名得 x 分，第二名得 y 分，第三名得 z 分，只要滿足 x&>y&>z，B 就一定會是贏家。（如果按照贏了比賽得 1 分，輸了得 0 分的話，A=8，B=9，C=4，贏家竟然也不是 B，話說這特么和 Borda 計分法
（第一名得 n-1 分，依次遞減，最後一名 0 分）的結果是一樣的，貌似我可以證明這個，嘛算了不證明了，你自己看的懂的）

位置計分法看上去只能適用於選票要求給出所有候選人的排序的情況，不一定適用於比賽這種兩兩對比的結果，況且就算能夠轉化，同一種比賽結果也會得到多種可能的選票組合，不過話說回來，（A&>B&>C + C&>B&>A）在 Borda 計分法下面是 A B C 各自得 2 分，而這和（C&>A&>B + B&>A&>C ）的結果是一樣的。看來我需要去考慮看看選票的組合方式在什麼情況會受到影響，不過這是另一個問題了。或許我們可以證明，無論如何將比賽結果轉化為選票，Borda 計分法的結果和認為贏了得 1 分輸了不得分計算出來的積分數是一樣的。

好的回歸正題，由於 Condorcet 贏家的概念非常嚴苛，在大多數情況下都可能選不出恰當的贏家，所以最直接的辦法就是將這種制度進行擴展，比如說：當沒有 Condorcet 贏家的時候，我們將過去的比賽結果進行刪除，每個選手的得分 x 是他至少需要刪除 x 場才能成為 Condorcet 贏家。

比如說：

A&>B 4:1（表示 A&>B 3 場， A&

B&>C 4:1

C&>A 3:2

在這種情況下，A、B、C 都不是 Condorcet 贏家，但是如果我們刪除兩場 C&>A 的結果，那麼就會出現 C&B，B 就會變成 Condorcet 贏家，C 也要至少 4 場。因此最後的贏家是得分最少的 A。
說一下結論：

Borda 積分制的本質就是：如果 A 贏了 B 一場，那麼 A 得 1 分，B 不得分。但是 Borda 贏家並不一定是獨立的，在一名其它選手退出之後，原來的 Borda 贏家有可能不再是 Borda 贏家。

Condorcet 贏家不一定是 Borda 積分制的贏家，但是幸運的是，如果我們照樣定義出 Condorcet 輸家的概念，那麼它一定不會是 Borda 積分制的贏家。因此這種判斷法雖然並不和 Borda 規則重合，至少不會太差。

這兩個規則都至少需要四人之間兩兩之間對決一次，就是 6 次。

我覺得我應該可以證明，6 次的情況下 Condorcet 贏家應該會和 Borda 贏家重合，但是我證明不了，摔！

公平和效率是不可兼得的。我們可以重複20輪比賽來排除運氣的因素，以達到更公平的結果，但是這是要付出代價的。同樣，我們也可以選擇 4 進 2 然後 2 進 1 的方式，這樣就只需要進行四場比賽，但是這同樣是依賴於分組抽籤的運氣的。

雖然不知道你們更喜歡 Borda 計分法還是 Condorcet 贏家（+刪除場數的拓展），但是我更喜歡 Borda。

由於這兩個規則都是匿名並且中立的，並且滿足一致同意性原則，因此根據阿羅不可能性定理，一定會遇到違反獨立無關性條件的情況。但是這個就是細節問題了。畢竟如果我們將投票看作是信息整合的過程，我們從海量的選票中最終整理出來一個排序，這無非就是以拋棄大量信息為代價的。

好了不想寫了。

配給制

參考世界盃小組賽，採用積分制，最後出線的兩隻隊爭冠軍。

做過遊戲比賽一般就是分兩組兩組失敗者再打然後剩下三支打循環節省時間

打循環賽，100輪。
不會一考定終身了，不能說意外了吧？

推薦閱讀：

※備胎調度演算法如何建模？
※2017年數學建模美賽六種題型怎麼理解，應該怎麼選題，菜鳥怎麼樣才能獲M獎？

TAG:數學 | 概率 | 數學建模 |