搜索
足球比赛排名问题报告人：龚珣•一、问题引入•二、问题分析•三、合理假设•四、建模与求解•模型1：总积分法•模型2：平均积分法•模型3：特征向量法•模型3’：得分矩阵法•模型4：参数法•模型5：概率法一、问题引入•众所周知，足球界对同一赛事中比赛结果的排名有现成的算法，例如，循环比赛结果的排名，按二分制（或三分制）计算总积分，以总积分的高低来决定名次的先后（总积分相同者，再比净胜球的多少、总进球的多少，再相同就抽签决定）。但是，这一算法着眼于排出比赛的胜负名次，并不能合理反映出各队真实水平的高低。比赛名次当然主要决定于各队的真实水平，但各队在比赛场次安排中“运气”的好坏也有相当的影响，比如某队在比赛中避开了强队而大胜弱队，就是由于“运气”好而得分高的例子。我们不能完全排除这一类因素，但应尽可能合理的考虑并处理它。•我们的目标就是针对这种不规则的比赛数据提出一种算法，尽可能合理地反映各队真实水平。二、问题分析•本问题讨论的难度，即足球队之间比赛结果不具有传递性。如甲队胜乙队，乙队胜丙队，然而丙队可以平甚至胜甲队。再有甲队该场胜乙队，而另一场比赛可能乙队胜甲队，即便两场都是甲队胜了，也可能第一场3：2胜，第二场却是2：0胜了。然而数学上任何排序问题都应具有传递性，严格地将不具有传递性就无法排序。•总体实力与一次比赛中所体现的实力并不总是相等，每次比赛的胜负并不取决于总体实力，而取决于比赛中所体现的实力。各队在每次比赛中所体现的实力并不一样强，有发挥失常也有超常发挥。虽然比赛结果不具传递性，并不妨碍我们比较实力。•确定这一问题是一个随机模型。某队在比赛中的表现是一个随机变量，有均值也有方差，服从一定的分布。每场比赛实际上是两个球队分别独立抽样，比赛的结果实际上是比较样品的大小。正是由于抽样的随机性，各种不同的结果分别按不同的概率发生，因而造成比赛结果的不可传递性。所以足球队进行排序应理解为是对均值的排序。变量是随机，但均值却是不变的，从道理上讲，是不受某场比赛结果所左右的。因此，对均值进行排序从数学上看是合理的。•那么问题来了：随机问题要能用较为准确的结论，应该有丰富的观测数据。根据根据大数定律频率代替概率可得到较为可靠结果，然而实际很多球队之间根本没有比赛过，“无米之炊”的感觉。三、合理假设•简化问题，先作如下假设：1.比赛是确定型的，或者每个队方差均为0，抽样结果就是均值；2.比赛的结果是可以精确反映相对实力的，没有误差；3.比赛的场次是完全的，任意两个队之间都有比赛成绩。例子•A、B、C、D四个球队循环赛，比赛结果如下：积分如下：排名：CA=DB（A、D比净胜球DA）CDABABCDA3:21:21:1B1:35:1C2:4D胜（2分）平（1分）负（0分）总积分A1113B1022C2014D1113四、建模与求解•模型1总积分法•按两分制（或三分制），即胜一场得两分或三分，平一场的一分，负一场不得分。计算各队在所有比赛中的总积分，按总积分的高低排出名次。•优点:综合考虑比赛的情况，也设法多利用一些结果信息。•缺点（1）没有考虑对手的情况，胜第二名和胜最后一名是一样看待；（2）没有考虑胜负的程度，9：0与5：4没有差别；（3）没有考虑比赛场次的多少，显然多参加比赛有利。•结论：只适用于循环赛。比赛场次少的队吃亏。模型2平均积分法•将每个队的总积分除以该队参加比赛场次，得出每场平均积分。按各队平均积分的高低来排名。•一区：A、B、C、D二区：E、F、G、H、I胜（2分）平（1分）负（0分）总积分E3107F1214G1032H0222I2024ABCDEFGHI总积分324374224平均积分10.671.3311.7510.50.51按各队平均积分的高低排名（相同则比较平均净胜球）•模型1中缺点（1）（2）仍无法克服。•为克服缺点（1），自然的算法应该是：胜强队得分应该多一些，胜弱队得分应少一些。给每个队赋予一个“强弱系数”𝑥𝑖(非负实数)，来反映各队的强弱，强队的系数大，弱队的系数小。•如果对手的强弱系数为，胜了它，得分为这个系数对基本得分2分进行加权，为2𝑥𝑖分。由此提出了特征向量法。特征向量法•记第𝑖队为𝑇𝑖（1≪𝐼≪N）。算出𝑇𝑖总得分，先对每个T𝑗算出𝑇𝑖对T𝑗的各场比赛中按二分制的平均得分，记为aij，如果两队没有比赛过，就取aij=0，特别a𝑖𝑖=0（严格来说，对于没有比赛过的𝑇𝑖，T𝑗取aij=0不合理，相当于判𝑇𝑖输了比赛，相对于其他队就吃亏了）。将𝑇𝑖对T𝑗的得分aij用T𝑗的强弱系数𝑥j加权，则𝑇𝑖对T𝑗的得分变为aij𝑥j，T𝑖的总得分为𝑦𝑖=𝑎𝑖1𝑥1+⋯+𝑎𝑖𝑁𝑥𝑁𝑦𝑖=𝑎𝑖1𝑥1+⋯+𝑎𝑖𝑁𝑥𝑁（*）•算出的各队总得分𝑦1，⋯，𝑦𝑁反映了各队实力强弱的比，可以作为排名的标准。•目的是为了求出反映各队实力强弱比的向量𝒚=𝑦1,⋯𝑦𝑁𝑇，为了求𝒚又要用到反映各队实力强弱比的另一个向量𝒙=𝑥1,⋯𝑥𝑁𝑇•将𝒙、𝒚都写成列向量形式，并记矩阵A=𝑎𝑖𝑗𝑁×N，则（*）式可以写成矩阵形式𝒚=𝑨𝒙（**）由于𝒙未知，当然不能直接从这个公式算出来，因为𝒙、𝒚都是反映各队实力强弱比的向量，有理由认为他们所反映的比相同，即存在正实数λ，使𝒚=λ𝒙,且𝑨𝒙=λ𝒙，且是𝑨的特征根，𝒙是对应于λ的特征向量。•把矩阵𝑨成为得分矩阵，它的元素𝑎𝑖𝑗是𝑇𝑖对T𝑗的各场比赛的平均得分，是非负实数。…可由Perron-Frobenius定理知道𝑨存在最大正实特征根及相应的特征向量𝑥，可以取这个𝑥作为反映各队实力比的向量。•定理指出：设𝒆=1,1,⋯,1T是由1组成的N维列向量，𝑨是不可约的非负矩阵，λ是它的最大正实特征根，则极限𝒙=lim𝑚→∞𝑨𝑚𝒆λ𝑚存在，且就是𝑨对应于λ的特征向量。计算𝑥的实用算法•我们所需要的是𝒙各分量的比值，为使𝒙由比值唯一确定，我们将非负向量𝒙归一化。归一化:各分量同时除以它们之和𝑥=𝑥1+⋯+𝑥𝑁，即用𝒙𝑥=𝑥1𝑥,⋯,𝑥𝑁𝑥𝑇代替𝒙。•先取𝒆=1,1,⋯,1T的归一化向量𝒙1=1𝑛,⋯,1𝑛T作为𝒙的初始值。既然一开始不知道各队实力强弱，不妨先认为各队实力相同。将𝒙=𝒙1带入式（**），算出𝒚1=𝑨𝒙1作为𝒚的最初近似值（即先不加权，直接按𝑇𝑖的总分𝑎𝑖1𝑥1+⋯+𝑎𝑖𝑁𝑥𝑁作为𝒚1的第𝑖分量）。𝒚1当然比𝒙1能更好的反映各队实力强弱比，归一后得到的𝒙2作为𝒙的更好的近似值。再用𝒙2算出𝒚的更好的近似值𝒚2=𝑨𝒙2。继续下去，得到𝒙的第m个近似值𝒙m之后，再由𝒙m算出𝒚m,将𝒚m归一化后得到𝒙m+1，作为𝒙的第m+1个近似值。•由Perron-Frobenius定理可知，这一迭代过程是收敛的。极限•𝒙=lim𝑚→∞𝒙(𝑚)存在且就是𝑨的对应于最大正实特征根的特征向量•实际计算时，只要𝒙m+1−𝒙m的各分量的绝对值都小于预先给定的误差允许值𝜀，就结束计算，取𝒙=𝒙m+1。•求𝑨的特征向量𝒙的这一算法，在计算数学中通常叫做“幂方法”。•以上特征向量法，在建立得分矩阵𝑨=𝑎𝑖𝑗𝑁×N之后，求出𝑨的对应于最大正实特征根的特征向量，作为代表各队水平比的向量，以它作为依据来为各队排名次。胜（2分）平（1分）负（0分）总积分A1113B1022C2014D1113•得分矩阵𝑨=0200010222100020•n=1•x1=•0.2500•0.1667•0.3333•0.2500•n=2•x1=•0.2059•0.1765•0.2941•0.3235n=3x1=0.23470.22450.26530.2755n=4x1=0.24480.18620.31030.2586n=5x1=0.21940.17990.29980.3010n=6x1=0.22940.20900.27730.2843n=7x1=0.23960.19400.29910.2674n=8x1=0.22640.18470.29950.2894n=9x1=0.22830.20060.28500.2861n=10x1=0.23570.19620.29420.2738n=11x1=0.22960.18870.29770.2840n=12x1=0.22880.19650.28940.2854n=13x1=0.23330.19630.29260.2778n=14x1=0.23090.19130.29590.2819n=15x1=0.22950.19470.29160.2842模型3’得分矩阵法•矩阵𝑨=𝑎𝑖𝑗𝑁×N的元素𝑎𝑖𝑗是𝑇𝑖对T𝑗各场比赛按二分制算出的平均得分。当𝑇𝑖与T𝑗没有比赛过时取𝑎𝑖𝑗=0。•模型3比模型1、2更合理，仍有不合理性：用来加权的向量𝒙=𝑥1,⋯𝑥𝑁𝑇代表的是各队水平的比，而算出的向量𝒚=𝑦1,⋯𝑦𝑁𝑇=𝑨𝒙的各分量是各队的得分。严格来说，向量𝒚=𝑦1,⋯𝑦𝑁𝑇代表的是各队水平的差而不是比。比如：某队比赛全败，得分为0，它所对应的y𝑖=0。可以说明它比其他队都差，但不能说明它与别队的水平比是0，或者别的队的水平是它的无穷大倍。•设想积分制改为胜1平0负-1，则各队的得分之差不变，但比值变了。而代表各队水平比的向量𝒙却不应因此改变。•更合理的办法：用反映各队水平比的正实数b𝑖𝑗代替𝑎𝑖𝑗，用水平比矩阵𝑩=b𝑖𝑗𝑁×N来代替得分矩阵。这样，由𝒚=𝑩𝒙算出的向量𝒚就仍是水平比向量，与𝒙成比例。•b𝑖𝑗是𝑇𝑖对T𝑗的水平比，而b𝑗𝑖是𝑇𝑗对T𝑖的水平比,b𝑖𝑗与b𝑗𝑖就应该互为倒数。•如何求水平比矩阵？•显然根据𝑇𝑖与T𝑗比赛成绩来算b𝑖𝑗。自然想到用𝑇𝑖与T𝑗比赛的得分比𝑎𝑖𝑗𝑎𝑗𝑖作为b𝑖𝑗，这样b𝑗𝑖也自然是b𝑖𝑗的倒数了。•问题？•假如𝑎𝑗𝑖=0怎么办？•我们可以认为凡参加比赛的队𝑇𝑖的水平都不是0，而是一个起码的水平分𝑎0(𝑎是待定的参数)。将这个起码分𝑎加上比赛得分𝑎𝑖𝑗作为𝑇𝑖对T𝑗的水平分，反过来𝑎+𝑎𝑗𝑖是T𝑗对𝑇𝑖的水平分，而b𝑖𝑗=(𝑎+𝑎𝑖𝑗)/(𝑎+𝑎𝑗𝑖)就可作为𝑇𝑖对T𝑗的水平比。•𝑎可由体育界人士根据经验确定，它的大小在一定程度上反映比赛成绩的可信程度。模型4参数法•预先选定参数𝑎（正实数），设任意𝑇𝑖对T𝑗的各场比赛平均得分为𝑎𝑖𝑗，则取b𝑖𝑗=(𝑎+𝑎𝑖𝑗)/(𝑎+𝑎𝑗𝑖)。所有的b𝑖𝑗组成水平比矩阵𝑩=b𝑖𝑗𝑁×N。再求出𝑩的对应于最大正实特征根的特征向量作为反映各队水平比的向量。•当𝑇𝑖与T𝑗未比赛过，两队水平比b𝑖𝑗如何确定？•取b𝑖𝑗=𝑥𝑖𝑥𝑗。•𝑦𝑖=𝑏𝑖𝑗𝑥𝑗𝑁𝑗=1=𝑏𝑖𝑗𝑥𝑗𝑗∈𝐽+𝑥𝑖𝑥𝑗𝑥𝑗𝑗∈𝑠=𝑏𝑖𝑗𝑥𝑗𝑗∈𝐽+𝑟𝑥𝑖=𝑐𝑖𝑗𝑥𝑗𝑁𝑗=1𝑟是与𝑇𝑖为比赛过的队（包括自己）的个数•模型4中参数𝑎的选定带有主观性，且𝑎是否应因𝑇𝑖、T𝑗的不同而异也是问题。更主要的问题是：计算b𝑖𝑗时所用的得分𝑎𝑖𝑗是用平均积分法得到的，有不合理性。•若𝑇𝑖对T𝑗只赛一场，𝑇𝑖一战一胜得2分，𝑎𝑖𝑗=2；若三战三胜，得6分，平均分𝑎𝑖𝑗仍为2分。但实际上，三战三胜的难度明显比一战一胜大，而两者得分一样，显然不合理。•假如𝑇𝑖胜T𝑗的概率是70％，一战一胜概率为70％，很可能实现；但三战三胜概率