为了保证~X*和~X@的存在性，我们要求n是最大的，并证明了~X*和~X@的存在性，以及γ√nρ>1和γ√n<γ√`的存在性，从而证明了INF上指数界的证明上的多项式下界。该证明类似于定理1中指数情形的证明。下界是直截了当的，上界是通过选择任意π∈CH(π)使得π6∈H来证明的，并用与上部多项式下界证明类似的方法去定义~π。INF上多项式上界的证明。注意，这种情况的条件意味着Sup的多项式情况成立，这意味着存在~π∈πn，使得Pr(~x~π∈H)=θndim(H)-q。这就意味着INF上的O-Ndim(H)-Q上界。INF上的多项式下界的证明。该证明与定理1中关于上部多项式下界的证明类似，只是当对~yn进行修正时，设~x*=pnj=1πj/n∈CH(π)TMH。更准确地说，我们有以下引理，可用于本文其它命题的证明。注意引理中的常数cπ，Hin只依赖于π（因此q和）和H，而不依赖于~π。引理2。对于[q]上的任意q∈N,任意闭严格正π,任意多面体H,整数矩阵A,存在Cπ,H>0,使得对于任意N∈N,Hzn6=π,任意~π=(π,...,πN)∈πN,Pnj=1πj∈H,Pr~x~π∈H≥Cπ,H·n-dim(H)证明。对于任意大的n∈n，我们得到了一个非负整数向量~yn∈HZnanda邻域bn Hnof~yn，它类似于定理1中多项式下界的证明步骤1。惟一的结论是我们设~xπ=pnj=1πj/n=E(~x~π)/n∈CH(π)TMH。其余的证明与定理1中多项式下界的证明步骤3、4、5相同。为了证明常数Cπ，hd不依赖于~π，我们注意到存在一个常数απ，即E(~x~π)=n~x*不大于α，H(√n)远离~x`=`~x*+√`~x@+~x#而O(1)远离~yn。回想一下~YNIS是Bn的“中心”，它的“半径”只依赖于`andbγ，而不依赖于~x*。因此，~yn（其O(1)接近于~x′，且常数只依赖于邻接而不依赖于~x′)对于某些απ，h>0离BN中的任何一个向量不超过απ，h√n。最后，我们注意到点集中界（引理1）中的常数不依赖于~π，这就完成了定理1的证明。A.2定理2的证明定理2。（C中PMV的平滑可能性）。给定[q]上任意q，I∈N，任意闭且严格正π，且任意C=Si∈Ihicharaceter，对于任意N∈N，sup~π∈πnpr~xπ∈C=0如果αN=-∞exp(-θ(N))如果-∞<αN<0θNαn-q否则（即αN>0)，如果βN=-∞exp(-θ(N))如果βN<βN<0θNβn-q否则（即βN>0)，证明了inf~π∈πnpr~x~π∈C=0如果βN=-∞exp(-θ(N))。为了方便起见，我们回忆了正文中的不等式(6)，maxi≤ipr~x~π∈Hi≤pr~x~π∈C≤xi≤ipr~x~π∈Hi(6)该定理是结合（6）和定理1到π、Hi的应用证明的。我们将介绍一些符号。设CZN表示C中所有Lnorm为n的非负整数向量的集合。即czn=[i≤ihzi，n给定[q]上的分布π，设iπc,n{1,。..,I}表示在激活图Gπ，C,nis中(π，Hi)上的权重在n处为正的指数I的集合。等价地，iπc,n可以定义如下，iπc,n={i≤i:HZi,n6=é和π∈Hi,60}例如图3中的iπc,n={2}。接下来，我们设πc,n CH(π)表示CH(π)中π的分布，使得iπc,n6=，或者等价地，dimmaxC,n(π)>0。即πc,n={π∈CH(π):iπc,n6=μ}我们从上面部分的证明开始。上面部分的证明。我们通过讨论以下三种情况(0、指数和多项式）来证明sup部分。·sup的0情况。

这种情况很简单，因为αn=-∞表示在n处没有多面体C活跃，这意味着C不包含任何非负整数向量，而pmv~x~π的任何结果都是非负整数向量，其大小为n。·sup的指数情况。我们回想一下，在这种情况下，czn6=θ和πc，n=θ。为了证明sup的指数下界，我们证明了存在~π∈NSUCHPR~x~π∈C=exp(-O(n))。由于czn=si≤ihzi，n6=，所以存在I*≤I使得I*在n处起作用，即hzi*,n6=.将（6）的下界应用于任意~π∈n:Pr~x~π∈C≥maxi≤ipr~x~π∈Hi≥Pr~x~π∈Hi≥n=exp(-o(n)),证明了sup的指数上界，并证明了对于每一个~π∈n，我们有Pr~x~π∈C=exp(-Ω(n))。这将通过结合（6）中的上界和定理1的上部的0或指数上界来证明。更确切地说，因为πC，n=，对于每π∈πN，我们有IπC，n=é。这意味着前π∈CH(π)和每个i≤i，HZi,n=π或π6∈Hi,60（或两者均成立）。如果形式成立，则定理1的0情况可以应用于π和Hi，这意味着对于任意~π∈πn，我们有Pr~x~π∈Hi=0。如果前者不成立，而后者成立，那么定理1的指数情况适用于π和Hi，这意味着对于每一个~π∈πn，我们有Pr~x~π∈Hi=exp(-Ω(n))。注意I是常数。因此，在（6）的上界之后，对于每一个~π∈n，pr~x~π∈C≤xi≤ipr~x~π∈Hi≤I·exp(-Ω(n))=exp(-Ω(n))·sup的多项式界。我们回想一下，在这种情况下，czn6=和πc，n6=。类似于指数情形，证明是通过结合（6）和定理1toπ及每一个hi的应用来完成的。为了证明sup的多项式下界，需要证明存在~π∈n，即pr~x~π∈C=Ω(nαn-q)。因为πC，n6=，我们让(π*，i*)表示达到αn的对。更准确地说，设(π*,i*)=arg maxπ∈πc,nmaxi∈iπc,ndim(Hi，60)在(π*,i*)的认识下，我们有hzi*,n6=，π*∈Hi*,60（表示thathi*,60TMCH(π)6=),dim(Hi*)=αn。这意味着当定理1应用于π和hi*时，定理1的上一部分的多项式情形成立。因此，存在pr~x~π∈Hiπ=Ω(ndim(hiπ)-q)的~π∈N，即pr~x~π∈Hiπ=Ω(ndim(hiπ)-q)。请注意，我们不能立即let~π=(π*,...,π*)，因为π*/∈π是可能的。在（6）的下界pr~x~π∈C≥maxi≤ipr~x~π∈Hi≥pr~x~π∈Hi(R)=Ωndim(Hi(R))-q=Ωnαn-q之后，证明了sup的多项式下界。为了证明sup的多项式上界，我们证明了对于每一个~π∈n，我们有pr~x~π∈C=Onαn-q。当定理1应用于π和每一个hi时，这将通过结合（6）中的上界和定理1上部分的(0、指数或多项式）上界来证明。更确切地说，对于每一个i≤i，将定理1的假设应用到π，并得到以下三种情况。-0情况。如果HZi,n=，那么对于每一个~π∈πn，我们有pr~x~π∈Hi=0。-指数情况。若HZi,n6=π,Hi,60TMch(π)=0,则对于每一个~π∈πn，我们有pr~x~π∈Hi=exp(-Ω(n)).-多项式情形。否则（HZi,n6=é和Hi,60àCH(π)6=0),对于每一个~π∈n，我们有pr~x~π∈Hi=o ndim(Hi,60)-q。在多项式情况下，对于任意π∈Hi,60àCH(π),我们有i∈iπc,n6=,这意味着π∈c，n。这意味着dim(Hi，60)≤αn。因此，在这三种情况下，我们都有Epr~x~π∈Hi=Oαn-q.再次，回想一下，I是一个常量。因此，继文（6）的上界后，对于每一个~π∈n，pr~x~π∈C≤xi≤ipr~x~π∈Hi≤I·o nαn-q=o nαn-q，证明了中频部分证明的多项式上界。我们现在转向inf部分，讨论以下三种情况(0、指数和多项式）。

在高水平上，inf的上界（分别为下界）的证明类似于SUP的下界（分别为上界）的证明。为了完备性，我们在下面给出了形式证明。·INF的0种情况。与sup部分的0情况一样，这种情况也很简单。·INF的指数情况。我们回想一下，在这种情况下，czn6=θ和πc，n6=CH(π)。为了证明inf的指数下界，我们可以证明：对于每一个~ππn，我们有pr~x~π∈C=exp(-o(n))。因为czn=si≤ihzi，n6=，所以假定存在si*≤I，所以hzi*，n6=.在(6):pr~x~π∈C≥maxi≤ipr~x~π∈Hi≥pr~x~π∈Hi≥n=exp(-o(n))的下界之后，给出了指数下界，证明了inf的指数上界，并证明了存在pr~x~π∈C=exp(-Ω(n))。因为πc,n6=CH(π),所以存在π∈CH(π),即π6∈πc,n,这意味着iπc,n=π。设~π=(π,...,πn)∈π表示这样一个任意向量，即pnj=1πj=θ(1)远离n·π。因为iπc，n=，对于所有i≤i，eitherHZi，n=或π6∈Hi，60（或两者都成立）。如果前者成立，那么通过将定理1的上界0应用到π和Hi，我们得到pr~x~π∈Hi=0。如果前者不成立，后者成立，则遵循Hoe-ding不等式和并界（应用于~x~π的每个q坐标），我们得到Pr~x~π∈Hi=exp(-Ω(n))。因此，在（6）的上界之后，我们有:Pr~x~π∈C≤Xi≤IPR~x~π∈Hi≤I·exp(-Ω(n))=exp(-Ω(n))这证明了INF的指数上界。o证明了INF的多项式上界。我们回想一下，在这种情况下，czn6=θ和πc,n=CH(π)。和在指数情况下一样，证明是通过结合（6）和定理1到π的应用以及每一个hi来完成的。为了证明inf的多项式下界，我们证明了对于每一个~π=(π,...,πn)∈πn，我们有Pr~x~π∈C=Ω(nβn-q)。设ππ=npni=1πi∈CH(π)。因为πC，n=CH(π)，所以我们有π*∈πC，n，这意味着π*π，n6=.因此，存在I*∈Iπ*π，即dim(Hi*,60)≥βn。另外，我们还记得，对于所有的i∈iπ~π，nwe有hzi~*,n6=π和π~∈Hi~*,60。因此引理2可以应用于~π和Hzi*,n,得到pr~x~π∈Hi*=Ωnβn-q。在（6）的下界之后，pr~x~π∈C≥maxi≤ipr~x~π∈Hi≥pr~x~π∈Hi(R)≥Ωndim(Hi(R))-q=Ωnβn-q证明了inf的多项式下界。为了证明inf的多项式上界，需要证明存在~π∈N，使得pr~x~π∈C=O(nβn-q)。因为πc,n=CH(π)，我们将(π*,i*)定义为达到βn的配对。更确切地说，设(π*,i*)=arg minπ∈πc,nmaxi∈iπc,ndim(Hi,60）得到hzi*,n6=,π*∈Hi*,60（这意味着Hi*,60ch(π)6=),dim(Hi*)=βn。设~π=(π,...,πn)∈πn表示一个任意向量，如pnj=1πnisθ(1)fromnπ*。将（6）中的上界与定理1的上界（0,指数或多项式）结合起来，证明了inf的多项式上界。更准确地说，对于每一个i≤i，将定理1的第二部分应用到~π，得到了以下三种情况：0情况。若HZi,n=0,则pr~x~π∈Hi=0。-指数情形。若HZi,n6=π,π*6∈Hi,60,则E(~x~π)离Hi,60为θ(n)。根据Hoe-ding不等式和并界（应用于~x~π的每一个q坐标），我们得到了pr~x~π→hi=exp(-Ω(n))-多项式情形。否则（HZi,n6=é和ππ∈Hi,60,即i∈iπππ，n),我们有pr~x~π∈Hi=O ndim(Hi,60)-q≤O nβn-q,因为edim(Hi)≤dim(Hi*)=βn。因此，在上述三种情况下，我们有pr~x~π∈Hi=O(βn-q)。再次提醒您，Iis是一个常量。因此，在（6）的上界基础上，我们得到了:pr~x~π→c≤xi≤ipr~x~π→hi≤I·o nβn-q=o nαn-q。这证明了第4.1节整数位置打分规则附录b.1定理3的证明定理3的多项式上界。（平局的平滑可能性：位置得分规则）。

设M=(θ,L(A),π)为严格正闭的单代理偏好模型，设~S为整数计分向量。对于任意2≤k≤m且任意n∈n,gtiemaxπ(R~s,k,n)=0,如果P∈L(A)n,r~s(P)6=kexp(-θ(n)),否则，如果π∈CH(π),r~s(π)<kθ(n-k-1),否则，gtiemaxπ(R~s,k,n)=0,如果P∈L(A)n,r~s(P)6=kexp(-θ(n)),否则，如果ππ∈CH(π),r~s(π)<kθ(n-k-1),证明了gtiemaxπ(R~s,k,n)=0,r~s(π)<kθ(n-k-1)。该定理是通过将k个赢家的集合建模为常多个多面体的并集，然后应用定理2来证明的。更准确地说，我们有以下三个步骤。在步骤1中，对于每一个潜在的赢家集T A,我们定义一个多面体H~s，T，该多面体刻画了赢家是T的profections。在步骤2中，我们证明了H~s，T的性质，特别是dim(H~s，T)=m！-T+1。在步骤3中，我们将定理2正式地应用于C=st a:t=kh~s,t。对于任一T A,H~s,T，由(i)表示T中任一方案得分相等的方程和(ii)表示任一方案整数的得分严格大于A\\T中任一方案得分的不等式组成。在形式上，我们定义了一组约束条件来建模两个备选方案之间的得分关系。定义15（得分关系向量）。对于任意得分向量~s=(s,...,sm）和任意两个备选方案a,b,设score~sa,b表示用秩inL(a)索引的m-维向量：对于任意R∈L(a),score~sa的R-元bis sj-sj,其中jand分别是a和b在R中的秩。设~xa=(xr:R∈L(a))表示m的向量！变量，每一个变量都表示一个线性顺序的多级性。因此，score~sa,b·~xa表示直方图为~xa的prof中a与b之间的score dierence。对于任意T a,我们定义多面体h~s,ta如下。对于任意整数得分向量~s和任意T A,我们设E~s,T表示行向量为{score~sa,b:A∈T,b∈T,a6=b}的矩阵。设S~s，T，表示行向量为{score~sa,b:a6∈T,b∈T}的矩阵。设A~s,T=E~s,T~s,T,~b=(~0,-~1),设H~s,T表示相应的多面体。第二步：证明H~s,T的性质。我们证明了以下关于H~s，t的主张。主张4。对于任意整数记分向量~s和任意T A,我们有:(i)对于任意整数P，Hist(P)∈H~s，Tif且仅当R~s(P)=T；(ii)对于任意~x∈Rq，π∈H~s，Tif且仅当TR~s(~x)；(iii)dim(H~s，T)=M！-T+1。证明。(i)及(ii)紧随第16条。为了证明(iii)，我们注意到dim(H~s，T)=m！-秩(A=)，其中A=是A~s，T的基本等式，根据[57]第100页的等式（9）。我们注意到a==e~s，T，因为根据对e~s，T的认识a=。为了证明s~s中没有行，在a=中有Tis，需要说明存在~x∈H~s，即s~s,t·(~x)><~>。通过构造一个pro-p，使r~s(P)=T，然后设~x=Hist(P)来证明这一点。我们定义了两个循环排列:σ在T上，σ在A\\T上。更准确地说，设σ=1→2→···→T→1和σ=T+1→T+2→···→m→T+1,则我们设P={σi(σj(12···m)):i≤T,j≤m-t}。不难看出R~s(P)=T，因而E~s，T=a=，这意味着E~s，T=a=。因此，有必要证明秩(E~s，T)=t-1。我们证明了秩(E~s，T)≤t-1。W.L.O.G.设T={1,...,k}，其中k=T。不难证明，E~s，T~s的所有行都可以用t-1行score 1,2...score 1,k的线性组合来表示。这意味着Rank(E~s，T)≤t-1。其次，我们用矛盾的方法证明Rank(E~s，T)≥t-1。为了矛盾起见，假定秩(E~s，T)≤t-1。然后，存在{score~sa，bi:i≤`}表示的e~s，T≤k-2行，使得任何score~sa，bi≤`都是它们的线性组合。设G表示{1,...,k}上具有以下边的未加权无向图：{{ai,bi}:i≤`}。因为G包含k-2个边和k个节点，所以G是不连通的。W.L.O.G.

假设G中的{1,...,t}和{t+1,...,k}之间没有边，对于某个1≤t≤k-1。我们现在构造一个profectirep来证明score~s1,ki不是{score~sai,bi:i≤`}的线性组合。本文给出了一个线性序R和两个循环置换:R=[1..t k+1···m t+1···k]设σ=1→···→t→1表示{1,....,t}之间的循环置换，设σ=t+1→···→k→t+1表示{t+1,...,k}之间的循环置换。LetP={σi(σj(R)):1≤i≤t,1≤j≤k-t}不难证明，在P中，{1,...,t}的总得分相同，{t+1,...,k}的得分相同，且前者严格大于后者。因此，对于所有i≤`,score~sai,bi·Hist(P)=0,而score~s1,k·Hist(P)>0,这意味着score~s1,ki不是{score~sai,bi:i≤`}的线性组合，这是一个矛盾。这意味着秩(E~s，T)≥t-1。这完成了权利要求4的证明。步骤3：应用定理2。设C=St A:T=KH~s,T。因此，对于任意P，r~s(P)=k当且仅当Hist(P)∈C。因此，对于任意n和任意~π∈n，我们有:prp'A~π(R~s(P)=k)=Pr(~x~π∈C)回想一下对于所有Tk=k的Tk A，从权利要求4(iii)我们有dim(H~s，Tk)=m！-Tk+1=m！-k+1。这意味着αn=βn=m！(-k+1)当它们是非负的时（这对n是成立的）。因此，为了证明定理3，必须证明定理3中的0,指数和多项式情况的条件与定理2中的0,指数和多项式情况的条件（分别适用于C和π)是等价的。0的情况很简单。回想一下权利要求4(iii)中的dim(h~s,T)=m！-T+1。因此，将定理2应用到定理3中，证明了对于任意π∈CH(π),R~S(π)≥k当且仅当π∈C（它等价于αn6=-∞)。“if”方向成立，因为如果π∈C，那么存在T=k，使得π∈H~s，T，这意味着根据权利要求4(ii)的tR~s(π)。因此，R~s(π)≥k，“仅当”方向成立，因为如果R~s(π)≥k，则设T R~s(π)表示具有T=k的任意集合。从权利要求4(ii)中可以得出π∈H~s，T，这意味着π∈C.C附录4.2节：基于EO的规则1命题1的证明命题1。对于任意A和任意n≥m,{EO(P):P∈L(A)n}=OAIF2NOAIF2-n.证明。设eon={EO(P):P∈L(A)n}。我们将证明2n情形。我们通过显式地构造一个n-pro-p来证明OA,使得对于anyO∈OA,EO(P)=O。设O=t···TT t TT+1···T2T表示一个加权有向图GOsuch,wgo(e)=2(t+1-i),如果e∈Tifor某个1≤i≤t-2(t+1-i),如果e∈Tifor某个1≤i≤t0,则存在一个不超过m(m+1)t<mvolents,即WMG(PO)=go。设R为任意线性顺序，并表示其相反顺序。letp={R,R}。因此，WMG(P)是空图。设P=PO+n-po×P。下面是P=n和WMG(P)=WMG(PO)=GO，这意味着EO(P)=o。这意味着a eon。因此，引理对2n成立。接下来，我们证明了2-n情形。对于任意n-pro，EO(P)的中间层是空的，因为任意边的权重必须是奇数。这意味着Eon OA。与2n情形一样，我们通过显式地构造一个n-pro-p，使得对任意O∈OA来说，EO(P)=O。更准确地说，设O=T···TT T TT+1···T2T，表示O的层表示，其中=.根据McGarvey定理[42]，我们得到了一个加权有向图GOsuch,当wgo(e)=2(t-i)+1,如果e∈Tifor某些1≤i≤t-2(t-i)-1,如果e∈Tifor某些1≤i≤t-1,则存在一个不超过m(m+1)t<mvotes，使得WMG(PO)=go。设P=PO+n-po×P。下面是P=n和WMG(P)=WMG(PO)=GO，这意味着EO(P)=o。这意味着oa eon。

因此，该定理对于2-N.C.2基于边序的规则（第4.2节）的正式确认17成立。给定一个基于边序的规则r,任意2≤k≤m,任意n∈n,任意分布π,L(A)上任意分布π的Letoπr,k,n={O∈on:r(O)=k和O refernes EO(π)},设Oπr,k,n=sπ∈ch(π)Oπr,k,n。当Oπr,k,n6=é时，设`min=mino∈Oπr,k,nTies(O)。当Oπr,k,n6=é对于所有π∈CH(π),我们设`mm=maxπ∈CH(π)mino∈Oπr,k,nTies(O).C.3定理4的证明定理4。（平衡点的平滑似然性：基于边缘顺序的规则）。设M=(θ,L(A)，π)是严格正闭的单主体偏好模型，设r是基于边序的规则。对于任意2≤k≤M且任意n∈n,gtiemaxπ(r,k,n)=0,如果the O∈OnA,r(O)6=kexp(-θ(n)),否则，如果Oπr,k,n=θn-`min,否则，gtiemaxπ(r,k,n)=0,如果the O∈OnA,r(O)6=kexp(-θ(n)),否则，如果xππCH(π)s.t。Oπr，k，n=θn-`mm另有证明。与定理3的证明一样，该定理是通过将k个赢家的集合建模为常多个多面体的并集，然后应用定理2来证明的。更准确地说，我们有以下三个步骤。在步骤1中，对于每一个回文阶O,我们构造一个多面体HO，它表征回文阶为O的pro，在步骤2中，我们证明了关于HO的性质，特别是dim(HO)=m！-领带(O)。在第3步中，我们正式地应用定理2toC=so∈ona:r(O)=kho。我们回顾了[66]中对两对双反向量的认识，以及对18（两对双反向量[66])的认识。对于任意一对双列备选方案a、b，设Paira,b表示在L(a)中按排序索引的m维向量：对于任意R∈L(a)，如果a为Rb,Paira的the-元bis 1；否则为-1。步骤1：去除HO。对于任何回文阶O∈OA，我们定义一个多面体HothathateProfection，其边阶为O。定义19。对于任意O∈OA，我们设列向量为{Paira,b-pairc,d：（a,b)O(c,d）}的矩阵；对于行向量为{Pairc,d-paira,b:(a，b)o(c，d)}的矩阵，我们设SOdenote。设AO=EOSO,~B=(~0,-~1),并设HOO表示相应的多面体。EOO包含冗余行，为了表示方便，如第19条所示。对于任意1≤i≤t，EO中对应于tia的行与EO中对应于t2t+1-i的行相同。步骤2：证明关于ho的性质。关于HO我们有以下索赔。索赔5。对于任一pro-p和任一O∈OA，我们有:(i)Hist(P)∈HOif，且仅当EO(P)=O，(ii)Hist(P)∈HOif，且仅当O refoundnes EO(P)，(iii)dim(HO)=m！-领带(O)。证明。第（一）和（二）部分分别在HOand HO的识别之后。对于第(iii)部分，letO=T··TT+1··T2T，表示O的层表示，设A=表示AO的本质等式。同样，我们不难证明A==EO归因于McGarvey定理[42]。因此，我们需要证明Rank(EO)=Ties(O)。我们注意Rank(EO)≤Ties(O)，因为对于任何0≤i≤t使得ti={e,...,e}和任何profirep,下列`-1方程(Paire-Paire)·Hist(P)=0,(Paire-Paire)·Hist(P)=0。.，(paire-paire`)·Hist(P)=0意味着ti中的所有边在WMG(P)中具有相同的权重。为了证明秩(EO)≥Ties(O)，为了矛盾起见，假定秩(AO)<Ties(O)。然后，存在一个tierti={e,....,e`}，其中EO中0≤i≤t且不超过s<`-1行，表示为bye=pairei-pairej，..，pairis-pairjs>，其线性组合包括与ti对应的其他行。让Eidenote对应于ti的eo行。根据McGarvey定理[42]，存在一个pro-p，使得wP(ei)=wP(ej)，..，wP(eis)=wP(ejs)，但不是tall e,。.e`在WMG(P)中具有相同的权重。这意味着E·(Hist(P))>=~>ButeI·(Hist(P))>6=~>，这意味着EII中的行并非都是行inE的线性组合，这是一个矛盾。这证明了秩(EO)=Ties(O)，这意味着该定理的部分(iii)。步骤3：应用定理2。

设C=so∈Ona:R(O)=KHO。因此，对于任意P，r(P)=k当且仅当Hist(P)∈C。因此，对于任意n和任意~π∈n，我们有:prp'A~π(r(P)=k)=Pr(~x~π∈C)回想一下，对于所有具有r(O)=k的O∈ona，从权利要求5(iii)我们有dim(HO)=m！-ties(P)+1。这意味着αn=m！-`minandβn=m！因此，为了证明定理4，必须证明定理4中的0,指数和多项式情形的条件与定理2中的0,指数和多项式情形的条件（分别适用于C和π)是等价的。这遵循了与权利要求5(ii)相结合的定理3证明的步骤3中的类似推理。这就完成了定理4.C.4的证明，命题2的证明，命题2。（联系的最大平滑似然:Copelandα)。设M=(θ,L(A)，π)为严格正闭单主体偏好模型，且πuni∈CH(π)。设Lα=min{t∈N:tα∈Z}。对于任意2≤k≤m且任意n∈n,gtiemaxπ(cdα,k,n)=0,如果2-n,2k,和k=m,如果2n,2k,和(1)k=m,或(2)k=m-1和α≥,或(3)k=m-1和k≤Lα(Lα+1)θ(n-Lα+1)θ(n-Lα+1)),如果2n,2k,k=m-1,α<和k>Lα(Lα+1)θ(1),否则（即如果2-k或k≤m-2)证明。应用定理4证明了该命题。设GAdenote是a上所有有向加权图的集合。对于任何图G∈GA和任一对备选方案a、b，如果a和b之间没有边，那么我们说a和b在G中是并列的。设GAdenote是a上所有图的集合，即无带的图的Gaconsits。对于任意的P,设UMG(P)表示P的未加权多数图，它是一个存在边a→b的图当且仅当wP(a，b)>0。不难看出，Copelandα可以在GA上进行修正。与命题1一样，从N-Profireles的UMGs中得到的所有图的集合可以用GnaThe来刻画，在下面的权利要求中进行修正。权利要求6。对于任意n>m,我们有GNA={UMG(P):P∈L(A)n}=gaif2ngaif2-n.证明。通过直接应用命题1，并注意回文顺序的中间层是空的当且仅当它的UMG不包含任何层，从而证明了该主张。应用定理4中的0情况。在这一部分中，我们证明了应用定理4中的0情况可以得到该命题的0情况。通过权利要求6,证明了对于任意n>m,存在G∈GnAsuch,即cdα(G)=k当且仅当2n,或2-k,或k≤m-2.o“if”方向。我们通过构造来证明“if”方向。当2 n时，根据权利要求6我们有GNA=GA，并且我们可以选择一个图G，使得{1,....,k}中的所有备选方案都是相互联系的，并且所有备选方案都严格地优先于其他备选方案。由此得到cdα(G)={1,...,k}，这意味着cdα(G)=k。当2-k或k≤m-2时，我们可以得到如图8(a)和(b)所示的θ(1)情形下的完全图。o“仅当”方向。现在我们证明了所有n>m的“仅当”方向。当2-n,2k,且m=k时，我们有gna=ga。为了解决存在的矛盾，假定cdα(G)=k。注意G是一个完全图。因此，所有备选方案的Copelandα得分为m，这意味着每个备选方案必须getm+16∈N点。这是一个矛盾，因为当G是一个完全图时，每个备选项的Copelandα得分都是一个整数。当2-n,2k,且m=k+1时，又有gna=ga。为了矛盾的缘故，假定存在G∈Gasuchcdα(G)=K。同样，所有替代方案的Copelandα总得分为m。假设每个获胜者得到u∈N分。然后，总的Copelandα得分必须在(m-1)u-mu-1之间。请注意，所有备选方案的Copelandα总得分为m。如果u≤m+1，则我们有m>mu-1；如果u≥m+1，则为m？<(m-1)u。任何一种情况都会导致误判。定理4中的指数情况的应用。

我们现在证明定理4的指数情形不存在。我们注意到UMG(πuni)是空图，这意味着EO(πuni)只包含中间层T。因此，对于Cdα(O)=k的任何回文阶O,我们认为O是EO(πuni),这意味着Oπr,k,n6=.应用定理4中的多项式情况。证明的其余部分集中于刻画定理4的多项式情况下的minin。我们证明了\'MinThat的另一个表征将被频繁使用。它指出:`Minequals等于Gna中的最小绑对图数，其中正好有k个Copelandα赢家。回想一下权利要求6，当nis su_ciently large(>m)时，对于任意一个evennumber n，Gna=GA，它是A上所有未加权有向图的集合；对于任意一个怪数n，Gna=GA，它是a上所有未加权竞赛图的集合。对于a上任意一个未加权有向图G，我们让Ties(G)表示G中的Ties对的个数。权利要求7。对于Copelandα下具有πuni∈CH(π)，n和k的任意π,使得Oπr，k，n6=，我们有:`min=min{Ties(G):G∈Gnas.t.cdα(G)=k}证明。因为EO(πuni)只包含中间层T，所以任何回文序都可以重新定义它，即Oπr,k,n={O∈ona:CDα(O)=k}。对于任何回文序O,设UMG(O)∈GAbe图，使得存在边a→bif且仅当a→b排在中间层之前。不难证明CDα(O)=CDα(UMG(O))。也不难证明O∈OnAif，且仅当UMG(O)∈GNA。因此，对于任何O∈Oπr，k，N，当Ties(O)=`min时，我们有UMG(O)∈Gna，cdα(UMG(O))=k，我们也有Ties(O)≥Ties(UMG(O))，因为后者对应于Ties(O)中的Tpart，所以我们有`min≥min{Ties(G):G∈Gnas.t.cdα(G)=k}。对于任何Gπ=arg ming∈Gna:cdα(G)=kties(G)，我们构造了一个回文序O,它的ts由G*中的所有绑边组成，而其他层中的每一层正好包含一条边。不能验证Ties(O)=Ties(G*)和UMG(O)=G*,这意味着O∈onaandcdα(O)=k。因此，Ties(g*)≥`min。这证明了这一点。θ(1)情况:2-k或k≤m-2。我们将证明θ(1)情况为热身。部分证据将在其他案件的证明中重复使用。事实上，θ(1)情况涵盖了最多数量的m和k的组合：它发生在k为奇数或k≤m-2时。根据权利要求7，证明了在这种情况下存在一个竞赛图G，使得cdα(G)=k,becauseets(G)=0,并且任何竞赛图都在GNA中。我们将在两个子情形中显式地构造这样的G。o2-k。下面的图G正好有k个Copelandα赢家{1,....,k}，见图8(a)关于m=6,k=5的例子。对于任意1≤i≤k和任意1≤s≤k-1，存在边→(1+(i+s-1mod k))，例如图8(a)中的黑边。对于任意1≤i≤k，任意k+1≤j≤m，存在一条边i→j，例如图8(a)中的蓝边。·2k和k≤M-2。下面的图G正好有k个Copelandα赢家{1,...,k}，见图8(b)关于m=6,k=4的例子。边在以下步骤中被修改。第1步：{1,...,k}内的边。这些边在图8(b)中是黑色的，与图8(a)中的图相似，只是有一些“对角线”边，它们的方向需要指定，因为k是偶数。形式上，对于任意1≤i≤K，任意1≤s≤K，存在边i→i+s。对于anyk+1≤i≤k和any1≤s≤k-1，存在边i→(1+(i+s-1mod k))。步骤2：{1,...,k}和{k+1,...,m}之间的边。这些边在图8(b)中为coloredblue。对于任意1≤i≤k，存在边(k+1)→i；对于任意其他（i,j)∈{1,...,k}×{k+1,...,m}，存在边i→j。步骤3：{k+1,...,m}内的边。有一条边(k+2)→(k+1)，红色图8(b)。

任意分配其它边的方向，使G成为完备格。(a)m=6和k=5。(b)m=6和k=4。(c)m=k=6。图8:Copelandα的构造，其中获胜者是{1,...,k}。θ(n-k)情况：2 n,2 k,和(1)k=m，或(2)k=m-1和α≥，或(3)k=m-1和k≤lα(Lα+1)。通过在命题陈述中所示的三个子情形中应用权利要求7，我们证明了`min=k.(1)2n,2k,和k=m。我们证明了`min≤K。通过权利要求7，构造了cdα(G)=k和Ties(G)=k的未加权图G∈GNA=GAsuch。事实上，以下具有Kties的未加权有向图G有k个Copeland赢家{1,...,k}，例如Seefigure8(c)。对于任意1≤i≤k和任意1≤s≤K-1，存在边→(1+(i+S-1 mod k))。G中存在{1,k+1},{2,k+2},。.{k,k}。其次，我们证明了`min≥k。通过权利要求7，证明了任意精确为k=m Copelandα赢家的未加权有向图G不可能有严格的少感恩。为了矛盾起见，假设这样的图是存在的，用G表示，那么一定存在另一个选择，W.L.O.G。备选案文1，它不与G中的任何其他备选案文联系在一起，否则至少有必要“涵盖”所有备选案文。这意味着备选方案1的Copelandα得分必须是一个用u表示的整数，这意味着所有备选方案的Copelandα得分必须是u。因此，所有备选方案的总Copelandα得分为uk。注意，每个有向的每个边对总Copelandα得分的贡献为1，每个条对总Copelandα得分的贡献为2α∈[0,2]。因此，总的Copelandα得分介于m-(k-1)（对应于有k-1条联系且α=0)和m+(k-1)（对应于有k-1条联系且α=1)之间，但如果u≥kthen uk>m-+(k-1)；如果u≤k-1，则uk<m-(k-1)。无论哪种情况，uk6∈[m-super-(k-1),m-super+(k-1)]，这是一个矛盾。因此，`min=k.o(2)2n,2k,k=m-1,且α≥.通过在{1,...,m-1}上构造图G∈GNA=Gahiter子图证明了`min≤kis与上例（1）所构造的图相同，然后对每个i≤m-1增加m-1条边i→m。`Min≥Kis证明了bya与上述情况（1）类似的论点。更确切地说，为了矛盾的缘故，假定存在一个图G，即cdα(G)=k=m-1和Ties(G)<k。那么，就存在一种替代方案，即W.L.O.G.替代1，它不与任何其他替代ing绑定。这意味着备选方案1的Copelandα得分必须是一个整数，表示为BYU。因为α≥，所以Copelandα总得分介于m和m+k-1之间，也介于uk和u(k+1)-1之间。但是，如果u≤k，则u(k+1)-1<m^=k(k+1)；且ifu≥K+1,则uk>M-HERO+K-1。在任何一种情况下[m-Alibaby，m-Hero+k-1]TM[uk，u(k+1)-1]=，这是一个矛盾。这意味着`min=k.o(3)2n,2k,k=m-1,k≤Lα(Lα+1)。`min≤ki由与上述（2）相同的图证明。`min≥kis由与上述情况（1）类似的论点证明。更确切地说，为了矛盾性，假设存在一个图G，即cdα(G)=k=m-1和Ties(G)<k。那么，一定存在一个胜利者，而这个胜利者不与任何其他备选静脉G相联系。因此，k个胜利者的Copelandα得分是一个整数。然而，为了使任何备选方案a的Copelandα得分与bean整数在G（与任何其他备选方案）中并列，a必须与至少Lα备选方案并列。在这些Lα备选方案中，至少有Lα-1必须是共同获胜者，每个备选方案必须至少与Lα备选方案相联系，才能使它们的Totalcopelandα得分为整数。GISLα(Lα+1)≥K，这是一个矛盾。这意味着`min=k.θ(n-Lα(Lα+1))情况：2 n,2 k,k=m-1,α<和k>Lα(Lα+1)。与θ(n-k)情况一样，我们应用权利要求7来证明`min=Lα(Lα+1)。

我们通过显式构造一个未加权有向图G∈Gna=GAsuch证明了`min≤Lα(Lα+1),证明了Copelandα是{1,...,k},其Copelandα得分为k。设A=A→A→{m}，其中A={1,...,Lα}和A={Lα+1,...,M-1}。G的构造依赖于Lα的奇偶性，Lα是奇数。我们构造G∈GNA=得到以下三个步骤，如图9所示。注意，图9仅用于说明，但不对应于θ(n-Lα(Lα+1))的情况，因为k=8<12=Lα(Lα+1)。一个实际的例子要求k≥14，这在G中包含太多的边，很难被看到。A的边与A的边。A的边与A的边。A的所有备选方案是绑定的，即A的任一对备选方案之间不存在边。验证A是奇数是无济于事的。因此，我们设G overAto的子图为图8(a)所示的完全图。经过这一步，每个备选方案的Copelandα得分在Aé{m}中变为αLα,每个备选方案的Copelandα得分在Abecomesk-Lα-1中变为αLα。A和A之间的边我们分配了A和A方向之间的所有边，使得AA中的每一个备选项都有精确的K-αLα输出边，而AHASLα-1或α+1输出边中的每一个备选项。这可以通过在A上均匀地分配Ato的边来实现。在步骤1和步骤2中结合边的图中，每个备选方案的Copelandα得分变成精确的K，Abecomesk中的K-Lα(Lα+1)+αLα备选方案的Copelandα得分变成精确的K，Abecomesk中的K+Lα(Lα+1)-αLα备选方案的Copelandα得分变成精确的K-Lα(lα+1)-αLα备选方案的Copelandα得分变成精确的K-Lα(lα+1)-αLα备选方案的Copelandα得分变成精确的K-Lα(lα+1)-αLα备选方案的Copelandα得分。m和A之间的边。最后，利用这一步中边的方向来保证AISK中所有备选方案的Copelandα得分。设G表示步骤1-3中边的并集。我们不难证明，所有方案的Copelandα分数在Aüaisk中，以及方案misαLα+K-Lα(Lα+1)+αLα<k的Copelandα分数，因为α<。证明了当Lα为奇数时，`min≤Lα(Lα+1)。456782319a1a2(a)步骤1。(b)步骤2。(b)步骤3.图9：奇数Lα的θ(n-Lα(Lα+1))情况下的构造说明，其中m=9，k=8，α=和Lα=3。请注意，此代码仅用于说明三步构造。它不符合θ(n-Lα(Lα+1))的情况，因为k<Lα(Lα+1)。在(b)和(c)中，从右到左的边都是红色的。Lα是偶数。与2-Lα的情形一样，我们构造G∈GNA=得到以下三个步骤。A的边与A的边。A的边与A的边。A的所有备选方案是绑定的，即A的任一对备选方案之间不存在边。验证A是奇数是无济于事的。因此，我们设Ato上G的子图与{1,...,k}上的（完全）子图同构，如图8(b)所示，在这一步之后，每一个备选方案的Copelandα得分变为αLα，Abecomesk-Lα中K-Lα备选方案的Copelandα得分，以及Abecomesk-Lα-1中剩余K-Lα备选方案的Copelandα得分。A和A之间的边我们分配了A和A方向之间的所有边，使得AA中的每一个备选项都有精确的K-αLα输出边，而AHASLα-1或αα输出边中的每一个备选项。这可以通过在A上均匀地分配Ato的Edges，从步骤1中Copelandα得分为-Lα的备选方案开始。在步骤1和步骤2的结合边的图中，每个备选方案的Copelandα得分变成精确的k，Abecomesk中的Lα+αLα备选方案的Copelandα得分，剩余的K-Lα-Lα-αLα（因为k>Lα(Lα+1)和Lα≥4因为α<)备选方案的Copelandα得分变成精确的K-Lα-Lα（因为k>Lα(Lα+1)和Lα≥4是严格的正）。m和A之间的边。最后，利用这一步中边的方向来保证AISK中所有备选方案的Copelandα得分。设G表示步骤1-3中边的并集。

由于Lα≥4且k>Lα(Lα+1),因此不难证明AüAisk中所有备选方案的Copelandα得分为Lα+αLα+αLα≤Lα+2≤Lα+Lα<k,而备选方案的Copelandα得分为Lα+αLα+αLα≤Lα+Lα<k。证明了当Lα为均匀时，`min≤Lα(Lα+1)。我们现在证明了`min≥Lα(Lα+1)。该证明类似于θ(n-k)情形（3）的证明，更确切地说，为了矛盾，存在一个图G，即cdα(G)=k=m-1和Ties(G)<Lα(Lα+1)<k。因此，k个赢家的Copelandα得分是一个整数。然而，为了使与G（与其他任何可选性）相联系的任一可选性a的Copelandα得分与bean整数一致，遵循与证明θ(n-k)情形（3）相同的论证，我们必须有(G)≥Lα(Lα+1)，这是一个矛盾。这意味着`min=Lα(Lα+1)。这就完成了命题2.C.5的证明，命题3的证明，命题3的证明。（Max抚平了平局的可能性：maximin）。设M=(θ,L(A)，π)为严格正闭单主体偏好模型，其中πuni∈CH(π)。对于任意2≤k≤m，任意n∈n，Gtiemaxπ(MM,k,n)=θ(n-k-1)证明。应用定理4证明了该命题的0情形和指数情形。证明了当n>m时，不存在定理4的0和指数情况。通过命题1并注意EO(πuni)只包含T，可以证明对于任意k,存在M(O)=k的O∈OAsuch。这是通过对一个有向加权图G进行解算来完成的，然后设O=EO(G)。设G表示A上的以下有向加权图，如图10所示。图10：maximin的构造，其中m=5和k=4.·G包含以下k个边圈，每个边的权为m+1。E={1→2,2→3,。.,(k-1)→k,k→1}o{1,..k}具有与m+1相同的奇偶性，且绝对值严格小于m+1且严格大于0。o任何其它边的绝对值与m+1相同奇偶性且严格大于m+1。另外，对于任意1≤i≤k且任意k+1≤j≤m,i→j上的权是正的。不难检验MM(G)={1,...,k}。设O=EO(G)。由于G中没有结，所以中间层Tin EO(G)是空的，这意味着O∈OA ONA。多项式情况。我们用上面给出的O对0和指数情况证明了`min≤k-1。只有两层有一个以上元素，即对应于E和逆E的层，这意味着Ties(O)=k-1。我们现在证明`min≥k-1。对于任何O∈OπR,k,n,假定W.L.O.G.最大值Winners是{1,.对于每个1≤i≤k，设i→ai表示与i的minscore相对应的任意边，因为{1，...,k}具有相同的最小得分，{i→ai:1≤i≤k}必须在相同的层中。如果它们在T中，则T1至少包含2k条边{i→ai,ai→i:1≤i≤k}，这意味着关系(O)≥T/2≥k。如果它们不在T中，则TIE(O)≥k-1。在任何一种情况下，我们都有`min≥k-1。因此，`min=k-1。这就完成了命题3.C.6的证明，命题4的证明，命题4的证明。（马克斯抚平了平局的可能性：舒尔茨）。设M=(θ,L(A)，π)是一个严格正的闭单主体偏好模型，且πuni∈CH(π)。对于任意2≤k≤m，任意n∈n，Gtiemaxπ(Sch,k,n)=θ(n-k-1)证明。应用定理4证明了该命题的0情形和指数情形。当n>m时，不存在定理4的0和指数情况。这是由与图10所示命题3的证明相同的图G证明的。多项式情况。对于同样的G用倒命题3用O=EO(G)证明了`min≤k-1.现在我们证明了`min≥k-1。对于任意O∈Oπr,k,n,设W.L.O.G.Schulze winnersare A={1,...,k}。我们定义了以下t个未加权有向图。

对于任意1≤i≤t+1,设Gidene A上的图的边为té。...TT+1-i。设GT+1表示具有任意边的图。根据规定G=UMG(O)。给定任意未加权有向图G，节点a是无支配的，如果对于任意节点b，存在从b到a的有向路径，则存在从a到b的有向路径。对于每一个1≤i≤t，{1,...,k}在Gi.证明中是无支配的。为了矛盾起见，假设该主张不是真的，而W.L.O.G.备选方案1在Gifor数1≤i≤T中由j支配。设w表示tt+1-i中边的权重。这意味着S[j,1]≥w，并且在从1到j的每条路径中都有一条边的权严格小于w。因此，S[j,1]>S[1,j]，它压缩了1是一个赢者的假设。对于每个1≤i≤t，设Si等于Githat交线上的连通分量={1,...,k},设ηi=Si。根据权利要求8，在Sin中的每个集合S没有来自A\\Sin Gi的传入边，否则SüAA在Gi中占优。如果η>1，那么我们有T≥2(k-1)，这意味着Ties(O)≥k-1，因此`min≥k-1，这证明了这个命题。在其余的证明中，我们假定η=1。对于每一个1≤i≤t，由于Giby去掉一些边得到Gi+1,所以SI+1中的每一个集合一定是SI中一个集合的子集。若ηi+1>ηi，则在Si+1中至少存在ηi+1-ηi+1集，以Si+1表示，它们是GI中某些集的严格子集。对于任意si+1∈si+1，设si∈Sibe theset使得si+1(si。根据权利要求8，si+1不包含来自A\\si+1ingi+1的任何传入边，特别是，从si\\si+1到si+1的边（它们在Gi+1中，并且至少有一个边，因为Siis是Gi中的连通分量）在Gi+1中。这意味着TT+1-Icontainst在SI+1中的每个集合中至少有一个进入边，并且这些边集合是不重叠的，因为I+1由A的不重叠子集组成。因此，TT+1-I≥ηI+1-ηI+1。如果ηi+1=ηi，那么显然我们有tt+1-i≥ηi+1-ηi+1=1。回想一下η=1和ηt+1=k，我们有:ties(O)=txi=1(tt+1-i-1)+t/2≥txi=1(ηi+1-ηi)=ηt+1-η=k-1，我们有`min≥k-1。这就完成了命题4的证明。C.7命题5的证明命题5。（平局的最大平滑可能性：排列对）。设M=(θ,L(A)，π)为严格正闭单主体偏好模型，且πuni∈CH(π)。对于任意2≤k≤m，任意n∈n，Ω(n-k-1)≤gtiemaxπ(RP,k,n)≤n-Ω（log klog log k)，当m≥k+5dlog ke时，gtiemaxπ(RP,k,n)≤Ω(n-dlog ke）当k=2时，gtiemaxπ(RP,2,n)=θ(n-0.5)证明。应用定理4证明了该命题。当n很大时，不难证明定理4的0情形和指数情形不发生。让skote表示这个elargest整数，这样sk！≤K。接下来是sk=O（log klog log k）。为了证明该命题陈述中的不等式，我们需要证明SK-1≤`MIN≤K-1。我们通过构造一个加权有向图G来证明`MIN≤K-1,这样(EO(G))=K-1,RP(G)=k,且EO(G)∈OA。事实上，我们可以使用图10所示命题3的证明图。胜利者由循环1→2→···→k→1中边之间的平局打破顺序决定。我们现在证明了`min≥sk-1。设O∈OnAdenote回文序，这样(O)=`min。在排序对中，断开连接的方法总数不超过(`min+1)！，当tt之前的一层包含所有l+1个连接边时，达到最大值。因此，wemust have(`min+1)！≥k，表示`min≥sk-1.“而且”部分。这一部分是通过构造来证明的。当m≥5dlog ke+k时，构造了一个加权有向图G，使得(1)EO(G)∈OA,(2)RP(G)=k,（3）Ties(EO(G))=dlog ke。该结构如图11(b)所示。我们让A表示以下三组备选方案的联合。o{0,...,k-1}。这些是排名对的获胜者。

请注意，索引从0开始，而不是从1开始。o对于每一个i≤dlog ke，都有备选项{ai,bi,ci,di,fi}。o设A表示剩余的m-k-5Dlog ke备选项。在G中存在具有相同权重的dlog ke对：对于任何i≤dlog ke,wG(ai→ci)=wG(bi→di)。这些边被分成以下几组，以便较早组中的权重高于较晚组中的权重。我们进一步要求除了ai→ci和bi→di以外，没有一对边具有相同的权重，特别是没有一条边具有权重0.o群1。对于每个i≤dlog ke，我们有以下边:CI→bi，DI→ai，CI→fi，DI→fi。对于每一个0≤j≤K-1，从j到A中的每一个备选方案都有一条边。对于each0≤j≤K-1和每一个i≤dlog ke，如果j的二进制表示中从右数开始的第i位是0，则有一条边j→AI；否则存在边j→Bi。o群2。对于每个i≤dlog ke和每个0≤j≤K-1，存在一个边FI→j.0A1B1C1D1F1A2B2C2D2F21 23图11：排序对的构造。AI→CI和BI→DIH具有相同的权重。foungureonly显示第1组边缘。o第3组。对于每一个i≤dlog ke，如果AI→CII在BI→di之前（分别在BI→di之后）被定义，则从每一个0≤j≤K-1有一条路径，其二进制中从右数开始的第i位为0（分别在1）到FI。因此，对于所有i≤dlog ke，通过断开{ai→ci,bi→di}之间的联系来调整组1中的边后，存在一个唯一的备选方案0≤j≤k-1，该方案具有到所有fi的路径。然后，{0,...,k-1}中除j以外的每个备选项将至少有一个FI的传入边。因此，j将成为排名双人组的获胜者。我们注意到{0,....,k-1}中的每一个选择都可以通过某种方式打破联系来赢得。因此，在EO(G)中，我们有t=，并且有包含多个边的dlog ke层，每个层正好包含两个边。这意味着当k=2时，Ties(EO(G))=dlog ke,即`min≤dlog ke。对于一般K来说，已经证明了Ω(n-0.5)的下限。因此，ITSU-CES证明`min≥1。为了矛盾起见，假设这不是真的。然后，存在一个回文序O使得Ties(O)<1且RP(O)=2。但是，Ties(O)=0表示WMG(P)中没有边被绑定。因此，RP(O)=1.6=2，这是一个矛盾。这就完成了4.3节的命题5.D附录：STV和Coombs.1结果的正式定义和陈述我们正式定义了多轮基于分数的淘汰(MRSE)规则，它是STV和Coombs的推广。定义20。针对m个备选方案的多轮基于分数的消除(MRSE)规则r被定义为M-1个规则（r,...,rm）的向量，使得对于每2≤i≤m，RI是针对i个备选方案的整数位置计分投票规则，该规则根据它们的分数输出对它们的总预排序。给定P优于m个备选方案，r(P)在M-1个步骤中选择。对于每1≤i≤M-1，在第i轮中，RM+1-II2下的一个失败者（最低层的替代者）将被淘汰出选举。如果有一种方法来打破联系，使b是在第1轮淘汰后剩下的替代方案，则替代方案b是赢家。我们现在在第4.2节中对回文顺序的对应方进行筛选，称为PUT结构，它包含了确定MRSE规则赢家所需的所有信息。识别21（PUT结构）。A上的PUT结构是一个映射W，它将eachB（A）映射到A\\B上的总预序。设WAdenote是A上的所有PUT结构的集合。对于任何MRSE规则r和任何预序P，设PSr(P)表示PUT结构W，使得对于任何B(A，W(B)=RM-B(P A\\B)是A\\B上的总预序，其中P A\\B是通过去除B中的所有备选方案从P得到的A\\B上的预序。我们注意到PSr(P)依赖于r和P。

PUT结构W可以等价地表示为PUT图，其中节点是A的非空子集，每个节点B由W(B)标号，节点B与Bif B=B{A}之间存在边，且A位于W(B)的最低层。我们也将用W来表示它的PUT图，它的主要组成部分是它的子图，它的节点可以从“？”到达，表示为byMC(W)。例如，图12中显示了profielle P和PSSTV(P)的主要组成部分。我们注意到，获胜者只取决于profielle的PUT结构的主要组成部分。第22条（PUT结构的层表示和重新定义）。对于任意PUTstructure W∈Wa，且任意B(A)，设t···ts表示W(B)的层表示，其中对于每个i≤s，Tiare中的备选方案是绑定的。设带(W(B))=pi≤s(Ti-1)和带(W)=pb(ATies(W(B))。一个PUT结构取另一个PUT结构W，如果对于所有的B(A，W(B)取W(B)，在总的预购顺序中取W(B).例19。图12显示了profile P和PSSTV(P)的PUT图。MC(PSSTV(P))是节点为{0,{1},{2},{1,2},{1,3},{2,3},{1,2,4},{1,3,4},{2,3,4}}的子图。LetW=PSSTV(P)。我们有领带(W(ρ))=领带(W({1}）)=领带(W({2}））=1，而对于任何其他B(A)，领带(W(B))=0，这意味着Ties(W)=3。首选项乘法1 3 2 4 11 2 3 4 22 1 3 4 33 2 1 4 44 1 2 3 6}{2}{1}{2,3}{2,3}{2,3}{1,3,4}{1,4}{3,4}{1,2,3}4 3{1,2}4{2,3}2 4 1{1,4}31 3 23 43 2 31 41 31 2(a)a profilfile P.(b)PSSTV(P)及其主要组成部分的PUT图。图12：一个优先选项P，其STV下的PUT结构PSSTV(P)及其对应的PUT图。其次，我们给出了STV下的光滑似然关系定理的符号。对于具有层表示t··Tt的弱阶O,其中任何层中的元素都是连接的，我们让GCD(O)表示O中t层大小的最大公约数，即GCD(O)=GCD(t,...,Tt）例20。设W表示图12(b)中的PUT结构。我们有GCD(W(Ⅵ))=GCD(3 4{1,2}）=GCD(1,1,2)=1。另一个例子是，GCD({3,4}{1,2}）=GCD(2,2)=2。下一个引理指出，对于任意大的n，W可以用STV下的PUTstructure或某个n函数的Coombs表示当且仅当n对于所有B(A引理3（STV和Coombs下的PUT结构）可被GCD(W(B)整除）。设r∈{STV,Coombs}。对于anym≥3,存在N∈N,使得对于A上的任意PUT结构W,且任意N≥N,(p∈L(A)ns.t。PSr(P)=W)phile§(The B(A，GCD(W(B))n)证明见附录D.2。根据引理3，对于任意A和任意n∈n，wede wn是A上的PUT结构，使得对于每B(A，gcd(W(B))n.definition 23。设r∈{STV,Coombs}。给定任一个A,任一个n∈n,任一个2≤k≤m,和L(A)上的任一分布π,对于L(A)上的任一分布π集，设Wπr,k,n={W∈WN:r(W)=k和W Refornes PSr(π)},设Wπr,k,n=Sπ∈CH(π)Wπr,k,n。当Wπr,k,n6=é时，我们给出wmin=minW∈Wπr,k,nTies（W）。当Wπr,k,n6=é对于所有π∈CH(π),我们给出wmm=maxπ∈CH(π)minW∈Wπr,k,nTies（W）,wn由所有n-prof在r∈{STV,Coombs}下产生的所有PUT结构组成。Wπr,k,nis是满足三个条件的PUT结构集：（1）W是r下n-prof的PUT结构；（2）根据r在W中正好有k个赢家；（3）W refoundnespsr(π)。WπR,k,nis是对应于所有π∈CH(π)的所有PUT结构的并集。Wπr,k,n中PUT结构中的连接数是最小的。wmmis系的最大数目，其中对于所有π∈CH(π)取最大值，对于任意给定的π，Wπr,k,n中的所有PUT结构取最小值。我们注意到WMIN和WMM依赖于r,{STV,Coombs},π,k和n,这在上下文中是清楚的。

事实上，wminand WMM对应于M！-αNAND M！对于STV和Coombs，我们分别得到了定理2和定理5。（平局的可能性：STV和Coombs）。设r∈STV,Coombs}和M=(θ,L(A),π)是严格正闭的单主体偏好模型。对于任意2≤k≤m且任意n∈n,gtiemaxπ(r,k,n)=0,如果W∈Wn,r(W)6=kexp(-θ(n)),否则如果Wπr,k,n=θn-wmin,否则gtieminπ(r,k,n)=0,如果W∈Wn,r(W)6=kexp(-θ(n))。Wπr,k,n='Aθn-Wmm另一个证明可在附录D.3中找到。与第4.2节一样，我们接着刻划了分布π的最大光滑似然性，其中πuni∈CH(π)。（最大平滑平局的可能性：STV和Coombs）。设r∈{STV,Coombs}和M=(θ,L(A)，π)是一个严格正闭的单主体偏好模型，且πuni∈CH(π)。对于任意2≤k≤m和任意n∈n，Gtiemaxπ(r,k,n)=θ(n-k-1)如果(1)m≥4,或(2)m=3和k=2,或(3)m=k=3和(2n或3n)0否则（即m=k=3,2-n和3-n)，命题6的证明可以在附录D.4中找到。D.2引理3的证明引理3。（将结构置于STV和梳子下）。设r∈{STV,Coombs}。对于anym≥3,存在N∈N,使得对于A上的任意PUT结构W,且任意N≥N,(p∈L(A)ns.t。PSr(P)=W)证明(λB(A,GCD(W(B))n)。本文证明了r=STV的引理，并对如何修改证明公式进行了评述。注意：注意到除去B后所有备选方案的总pluralityscore（即n）可被GCD（W(B)整除）后，STV的指示如下。更准确地说，对于任何n-pro-p，使得PSSTV(P)=W和任何B(A)，设W(B)的层表示为：W(B)=t t··tt，对于每s≤t，设γst表示去掉B后ts中任何备选方案的复数得分。因此，我们得到了=xa∈(a\\B)scorreplu(pa\\B，a)=x1≤s≤tγsts，它可被GCD(W(B))整除。对于任一个B A和任一对备选方案A、B∈A\\B，在这一步中，我们定义M！-PB,A,ba为构造块。定义24(PB,A,B）。对于任一对二价备选方案a、b和任一个b((a\\{a,b}）,PB,a,bis由L(a)得到如下。对于每一个B*,使得bb*(A\\{A,B}）,o如果B*\\B是偶数，那么我们将[B*B A others]替换为[B*A B others]，其中“others”代表其他备选项，而B*中的备选项和“others”是W.R.T.词典编纂顺序。o如果b*\\b是奇数，然后我们将[b全a b其他]替换为[b全b a其他]。表3显示了一个例子，其中只显示了L(A)与P{1},2,3之间的关系。b*{1}{1,4}{1,5}{1,4、5}L(A)1 3 2 4 5 1 4 2 3 5 1 3 4 1 4 5 3 2 2p{1},2,31 2 3 4 5 1 4 3 2 5 1 5 3 2 4 1 1 4 5 2 2 3表3：对于m=4,B={1},A=2,B=3,L(A)与P{1},2,3之间的关系。我们现在证明PB,A,B具有以下权利要求中描述的两个性质。figurrstproperty指出，对于任何b6=B，去掉Bis后，PB、a、ba\\bare中其余备选项的多个分数相等。第二个性质是，在B从PB、a、B中移除后，a的复数分数增加1，B的复数分数减少1，并且在B从PB、a、B中移除后，其他备选方案的复数分数相同。权利要求9（PB、a、B的性质）。设PB,a,B表示第24条中的结果，(i)对于任意B(a with B6=B和任意c∈a\\(B"a{a,B}）,我们有coreplu(PB,a,BA\\B,c)=ScorePlu(PB,a,BA\\B,a)=ScorePlu(PB,a,BA\\B,B)(ii)对于任意c∈a\\(B"a{a,B}）,我们有coreplu(PB,a,BA\\B,c)=ScorePlu(PB,a,BA\\B,c)=ScorePlu(PB,a,BA\\B,a)-1=ScorePlu(PB,a,BA\\B,B)+1证明。

我们证明在B（A）被移除后(i)成立，对于B的下列情况。o如果B6B，那么在Bis被移除后，B中至少有一个替代方案没有被移除。根据PB,a,b的定义（定义24)，所有剩下的备选方案的复数分数是相同的，这验证了(i).o如果a∈b，则注意到PB,a,b只在a和b相邻的某些排序中切换位置。因此，在移除Bis之后，即a被移除，(i)成立。o类似地，我们可以证明，如果b∈b，则(i)成立。唯一剩下的情况是b b(a\\{a,b}）。其次，我们证明了假设B B(a\\{a,B}）,(ii)成立当且仅当B=B,否则(i)成立（即当B(B(a\\{a,B}））。首先，对于任意c∈a\\(Bü{a,B}）,注意PB,a,带L(a)之间的di仅是除去Bis后a和B的多个分数。因此，对于任意B，我们有coreplu(PB,a,ba\\B,c)=scorreplu(L(a)a\\B,c）。其次，我们计算了在PB,a,B中的a的复数与在L(a)中的a的复数之间的关系。如第24条所述，这是通过检查在某些投票中切换a和b（相邻）位置的e----ect来完成的。更确切地说，对于每一个B*带有B*的B*（A{A,B}），我们有以下的观察。o如果B**B，那么在去掉Bis之后，A不排在[B*A B其他]或[B*B A其他]的前几位。因此，与B*相对应的PB、a、带L(a)之间的di值在去掉Bis后，并不等于PB、a、带L(a)中的a的多个分数中的di值。o如果B*带B*\\B是偶数，那么根据对PB、a、B的识别（识别24)，PB、a、在L(a)中以[B*a、B其他]递减[B*a、B其他]。注意，去掉Bis后，b在前一个排名中排名第一，而a在后一个排名中排名第一。因此，a（分别，b)的复数分数增加（分别，减少）1在PB，a，b，除去Bis后，与a的多个分数相比（分别为，b）在L(A)中。o同样，如果b*带b*\\b是一个奇数，那么在去掉bb后，在PB,a,b中a（分别，b)的多个分数比在L(a)中a（分别，b)的多个分数减少（分别，b)增加1。因此，我们有以下的计算。scorreplu(PB,a,ba\\b，a)-scorreplu(L(a)a\\b，a)=xb*:bb*b(-1)b*\\b=xb-bi=0(-1)ib-bi=1如果b=B0。）=-xB*:BB*b(-1)b*\\b=-1，如果b=B0，则遵循当b=b时(ii)成立，否则(i)成立。这证明了索赔9。对于每一个B(A)，我们用PB,A,B来调谐去除B时的多个备选项的分数，使它们之间的弱序变为W(B)。对于每一个0≤n≤m！-1，使得对于每一个B(A，GCD(W(B))n，我们构造一个profile Pn，使得Pnn(mod m！）和PSSTV（mod m！）（mod m！）（mod m！）（mod m！）（mod m！）（mod m！）（mod m！）（mod m！）

当gcd(W(B)=xts=1ηs×Ts，对于每1≤s≤t，且每B∈Ts，我们在Pn上加上以下公式，其中为方便起见，我们将PB,aB,aB=-如果ηt≥0，那么我们加上PB,aB,B的ηTnGcd(W(B))副本；-如果ηt<0，那么我们加上PB,B,aB的ηTnGcd(W(B))副本。o步骤2.4。最后，对于（a,b）topnn的某些组合，我们将添加PB,a,b的多个副本，以便层之间的顺序与W中相同。在形式上，对于W(B)的层表示为t···Tt的每一个B(A)，且每1≤s≤T-1,我们添加了sa∈TS，B∈TTPB,A,bto Pn的Cscopies,其中C，..，ct-1是保证W(B)的常数。这是因为去掉B后，Sa∈TS，B∈TTPB，a，bto Pn增加了Tsby Tt中每个备选方案的复数分数，减少了TtbyTs中每个备选方案的复数分数。它遵循Pnn(mod M！）并且PSSTV(Pn)=W。设N=max1≤N≤m！-1 pn。对于任意n>n，设n=n(mod m！）,且P=pn+n-nm！×L(A)，不难证明P是n-pro，而PSSTV(P)=W证明了部分flemema 3,从而完成引理3的STV部分的证明。Coombs的证明。请注意，Coombs在每一轮中使用否决，一个排名的否决分数是反向排名的复数分数。根据这种联系，证明类似于STV部分，主要的结论是，对于Coombs，我们使用PB，a，b，即通过颠倒所有排名从PB，a，b中扣除（扣除24）。这就完成了引理3.D.3定理5定理5的证明。（平局的可能性：STV）。设M=(θ,L(A),π)是一个严格正闭的单代理偏好模型。当任意2≤k≤m且任意N>N时，gtiemaxπ(STV，k，N)=0,如果插W∈Wn,则STV(W)6=kexp(-θ(N)),否则WπSTV,k,N=θn-wmin,否则gtieminπ(STV，k，N)=0,如果插W∈Wn,则STV(W)6=kexp(-θ(N))。wπstv,k,n=θn-wmm另有证明。与定理3的证明一样，该定理是通过将k个赢家的集合建模为常多个多面体的并集，然后应用定理2来证明的。与引理3的证明一样，我们给出了r=STV的证明，并对如何修改这些证明进行了评述。证明按以下三个步骤进行。在步骤1中，对于每个PUTstructure W，我们定义一个多面体HW，该多面体HW表征PUTstructure所在的profigure。在步骤2中，我们证明了关于HW的一些性质，特别是dim(HW)=M！-领带(W)。在步骤3中，我们正式地将定理2应用于C=SW∈WN:STV(W)=KH。我们将在构造中使用向量。第25条（STV的两两向量）。对于任意一对di-everent交替a,b和任意一个b∈a\\{a,b}，我们设PairB,a,b表示向量，使得对于任意一个R∈L(a)，PairB,a,bis scorreplu(Ra\\b,a）-scorreplu(Ra\\b,b）的R-分量。换句话说，PairB,a,breply表示去掉b后a的复数分和b的复数分之间的di-everence。我们现在用这些向量来构造一个与给定的PUT结构W相对应的多面体。给定一个PUT结构W，对于具有以下约束AW·(~xa)>≤~B>:对于任一对备选方案a W(B)B，存在一个不等式对B,B,a·~xa≤-1；对于任一对备选方案awbb，存在一个不等式airb,b,a·~xa≤0。STV的第二步：证明关于hw的性质。我们证明了以下关于HW的主张。主张10（HW的性质）。对于任意PUT结构W，我们有:(i)对于任意pro，Hist(P)∈HWif，且仅当PSSTV(P)=W；(ii)对于任意~x∈RM！，~x∈HWif，且仅当W是PSSTV(~x)；(iii)dim(HW)=M！-领带(W)。证明。(i)和(ii)在确认HW之后。为了证明第(iii)部分，再次根据[57]第100页的等式(9)，我们需要证明AW的本质等式的秩（用A=表示）是Ties(W)。

我们证明了a=={PairB,a,B:λB(a和aW(B)B}，(24)其中aW(B)B表示a和B在W(B)中绑定。显然A=包含右手边的ofEquation（24）。通过引理3，存在一个（m！）-亲p*使得PSSTV(p*)=W。因此，Hist(p*)是HWin的一个内点，即方程（24）右边没有提到的所有不等式在Hist(p*)下都是严格的，这意味着方程（24）成立。我们现在证明秩(a=)=Ties(W)。对于任意B(A)，设W(B)=T···TsdenoteT W(B)的层表示。设ABbe为a=由对b、b、a组成的子矩阵，对于所有对的备选方案aW(b)b。对于任意Ti,{PairB,a,b:a,b∈Ti}中的每一个向量都可以表示为Ti-1个线性阶子集的线性组合，因此检验Rank(AB)≤Ties(W)是不难的。这意味着秩(a=)≤Pb(ATies(W(B))=Ties(W).秩(a=)≥Ties(W)紧随引理3之后。更确切地说，为了矛盾起见，假定Rank(A=)<Ties(W)，并设A表示A=的任意行基。根据鸽子洞原理，存在B（A使得A包含不超过Ties（W(B)）rowsin AB,这意味着存在一层tize使得A包含不超过Ti-2 rowsin{PairB,A,B:A,B∈Ti}。这意味着Tican被划分为两个集合{a,...,at}和{b,...,bt},使得对于1≤I≤Tan和1≤I≤T的任意组合，a不包含PairB、ai、BI。根据引理3，存在一个（M！）-亲P使得对于所有B6=B，除去Bis后所有备选方案都是绑定的，且PSr(P)(B)由两层组成：第一层是Tü···(R)Ti-1{a,...,at}，第二层是{b,...,bt}@ti+1@···@tt。不难检验ata·(Hist(P))>=~>，但PairB,a,b·Hist(P)6=0。这意味着PairB,a,b∈a=不是a中行的线性组合，这与a是a=的基的假设相矛盾。因此Rank(a=)=Ties(W)。这就完成了权利要求10的证明。STV的步骤3：应用定理2。设C=SW∈WN:STV(W)=KHW。因此，对于任意pro，STV(P)=k当且仅当Hist(P)∈C。因此，对于任意n和任意~π∈n，我们有:prp'A~π(STV(P)=k)=Pr(~x~π∈C)回想一下，对于A上的所有PUT结构W，通过权利要求10(iii)我们有dim(HW)=m！-ties(P)+1。这意味着αn=m！-`minandβn=m！因此，为了证明定理5，必须证明定理5中的0,指数和多项式情形的条件与定理2中的0,指数和多项式情形的条件（分别适用于C和π)是等价的。这遵循了与权利要求10(ii)相结合的定理3证明的步骤3中的类似推理。这就完成了定理5的STV部分的证明。Coombs的证明。在引理3的Coombs部分的证明中，注意Coombs在每一轮中都使用veto，而一个排序的veto得分是反向排序的复数得分，因此，证明与STV部分相似，主要的结论是，对于Coombs来说，在求成对得分的di-erence向量时，我们使用veto规则而不是复数规则。这就完成了引理3.D.4命题6命题6的证明。（最大平滑平局的可能性：STV和Coombs）。设r∈{STV,Coombs},且M=(θ,L(A)，π)是一个严格正闭单主体偏好模型，且πuni∈CH(π)。对于任意2≤k≤m且任意n∈n，当(1)m≥4,或(2)m=3且k=2,或(3)m=k=3且（2 n或3 n)0否则（即m=k=3,2-n和3-n)证明Gtiemaxπ(r,k,n)=θ(n-k-1)。根据定理5，我们将证明：（1）指数情形不发生，(2)wmin=k-1在多项式情形中。为了看(1)，注意如果定理5的0情形不成立，那么存在W∈wn，使得STV(W)=k。

还要注意，πuni∈CH(π)和PSSTV(πuni)是PUT结构，其中所有选项都绑定在任何B（A）被移除之后，这意味着任何PUT结构都是PSSTV(πuni)的重新组合。因此，Wπr，k，n6=，这意味着定理5的指数情况不成立。要看(2)，注意对于任何PUT结构W，任何标记为B(A，且B≤M-2)B的结点的出边数为带(W(B))+1。因此，Ties（W）至少是W中没有传出边的节点总数减去1。因此，对于STV(W)=k的PUT结构W，我们必须有关系(W)≥K-1,这意味着WMM≥K-1。在续篇中，我们将通过构造命题6所描述的多项式情况来证明WMM=K-1。更准确地说，我们将证明存在一个n-pro-p，即(PSSTV(P))=k-1和STV(PSSTV(P))=k。根据引理3，构造了如下结构W:(1)Ties(W)=k-1,(2)STV(W)=k,（3）对于每一个B(A,GCD(W(B))nθ(n-k-1)子情形(1):m≥4。当m≥4时，我们设W表示PUT结构，这样W()=kk+1···m{1,...,k-1}W({1}）=2··k-2k+1···m{k-1,k}，而对于任何其他B的W(B)是一个线性序，因此在W的图表示中，存在没有出边的knod，其赢家是{1,...,k}。有关m=k=4的示例，请参见图13(a).{3}{1}{3,4}{2,3,4}{1,4}{1,2,4}{1,3}{1,3}{2,4}{2,4}{3,4}{1,2,3}2{3,3}1 3 42 1 41 3 23 21 31 22}{3}{3}{2}1{2=3}1 33 22 12{2,3}1(a)m=k=4.(b)m=3和k=2。图13：STV的PUT结构。不难验证Ties(W)=K-1和STV(W)=k。请注意，对于每一个B(A)，在W(B)中存在一个由单个备选方案组成的层，这意味着GCD(W(B))=1，因此，W∈WN。这证明了对于m≥4情形，θ(n-k-1)子情形(2):m=3和k=2的命题。图13(b)所示的PUTstructure证明了m=3和k=2的情况，θ(n-k-1)子情况(3):m=k=3和（2 n或3 n）。图14(a)所示的PUT结构证明了m=k=3和2n的情况。用图14(b)所示的PUT结构w，证明了m=k=3和3 n的情况。{{3}{2}{1,3}胜利者{1}{1,2}1{2,3}{1,3}3 22 12{2,3}13}{3}{2}{1,3}胜利者{1}{1,2}{1,2}{1,2}1,2,3}1 33 22 12{2,3}1 3(a)2 n。(b)3 n.图14：STV.0情况下的PUT结构。当m=k=3,2-n和3-n时，为了矛盾起见，假设存在n-profective P，使得STV(P)=3。设W=PSSTV(P)。那么，对于某些B(a（这意味着GCD(()W(B))=3,因此3n)，或者W(B)是三个备选方案中的一个平局，或者对于某些B=1（这意味着GCD(()W(B))=2,因此2n)，或者W(B)是两个备选方案中的一个平局。这两种情况都导致了矛盾。因此，在这种情况下，Wπr，k，n='A.所有规则的实验结果图15：Ic下平局的百分比。图16：本文研究的307个pre-emib SOC数据中候选人数和选民数的直方图。