###################################################################### ## Condorcet3.txt: Save this file as Condorcet3.txt to use it, # # stay in the # ## same directory, get into Maple (by typing: maple ) # #then type: read `Condorcet3.txt`: # ## Then follow the instructions given there # ## # ## Written by Rebecca Embar and Doron Zeilberger, Rutgers University # ## DoronZeil@gmail.com . # ###################################################################### with(combinat): Digits:=100: print(`First Written: April 2022: tested for Maple 20 `): print(): print(`This is Condorcet3.txt, A Maple package`): print(`accompanying Rebecca Embar and Doron Zeilberger's article: `): print(` Counting Condorcet`): print(`-------------------------------`): print(`-------------------------------`): print(): print(`The most current version is available on WWW at:`): print(` http://www.math.rutgers.edu/~zeilberg/tokhniot/Condorcet3.txt .`): print(`Please report all bugs to: zeilberg at math dot rutgers dot edu .`): print(): print(`-------------------------------`): print(`For general help, and a list of the MAIN functions,`): print(` type "ezra();". For specific help type "ezra(procedure_name);" `): print(`-------------------------------`): print(`For a list of the supporting functions type: ezra1();`): print(`For help with a specific procedure, type "ezra(procedure_name);"`): print(): print(`-------------------------------`): print(`-------------------------------`): print(`For a list of the Bram-Fishburn functions type: ezraBF();`): print(`For help with a specific procedure, type "ezra(procedure_name);"`): print(): print(`-------------------------------`): print(`-------------------------------`): print(`For a list of the Story functions type: ezraSt();`): print(`For help with a specific procedure, type "ezra(procedure_name);"`): print(): print(`-------------------------------`): ezraSt:=proc() if args=NULL then print(` The story procedures are: Paper, PaperEq, PaperSp, REpaper `): print(` `): else ezra(args): fi: end: ezra1:=proc() if args=NULL then print(` The supporting procedures are: ApCo, Comps, ConCon1, Cond, ConG1, CoSpSeq, F, Gen, IsCond, IsCondS123, IsCondS321, MyAsy, NuCoDirect, NuCori, OpeEq,OpeSp, OpeSpE, PrCo123, PrCo321, PrCoSpDirect, RVCP `): print(` `): else ezra(args): fi: end: ezraBF:=proc() if args=NULL then print(` The procedures inspired by Steven J. Brams and Peter Fishburn expository article "Voting Procedures", Ch. 4 in " Handbook of Social Social Choice and Welfare", ed. by K.J. Arrow et. al. are: `): print(` p3n, pm3 `): print(` `): else ezra(args): fi: end: ezra:=proc() if args=NULL then print(` Condorcet.txt: A Maple package for studying the Condorcet paradox with three candidates`): print(`main procedures are: CompToCond, ConCon, CondToComp, NuCo, NuCoSeq, PrCo, PrCoEq, PrCoSp, PrCoSpSeq, `): elif nargs=1 and args[1]=ApCo then print(`ApCo(v,P,K): Estimating the prob. of a Condorcet scenario with loaded dice P (a list of length 6) with 3 candidates and v voters. Try: `): print(`ApCo(11,[1/6,1/6,1/6, 1/6,1/6,1/6],1000);`): elif nargs=1 and args[1]=Comps then print(`Comps(n,k): The set of all (ordered) lists of non-negative integers into exactly k parts. Try, for example:`): print(`Comps(5,3);`): elif nargs=1 and args[1]=CompToCond then print(`CompToCond(C): The bijection between lists of non-negative integers of length 6 that add-up to n and Condorcet vote-count profiles with 2n+3 voters with cycle 1->2->3-1. Try`): print(`CompToCond([1,0,0,0,0,0]);`): elif nargs=1 and args[1]=ConCon then print(`CondCon(D1): An approximation to the Condorect with accuracy of D1 decimal points. Try:`): print(`ConCon(10);`): elif nargs=1 and args[1]=ConCon1 then print(`CondCon1(N): An approximation to the Condorect constant using N terms. Try:`): print(`ConCon1(1000):`): elif nargs=1 and args[1]=CondToComp then print(`CondToComp(C): The bijection between Condorceet vote-count profiles with 2n+3 voters with cycle 1->2->3-1 and lists of non-neg. integers of length 6 that add-up to n. Try`): print(`CondToComp([c123,c132,c213,c231,c312,c321]);`): elif nargs=1 and args[1]=Cond then print(`Cond(v): The set of vote-count profiles with three candidates that lead to the cycle 1->2->3->1 the output is the set of lists of non-negative intgers that add-up to v with that property`): print(`with the ordering [123,132,213,231,312,321]. Try:`): print(`Cond(5);`): elif nargs=1 and args[1]=ConG1 then print(`ConG1(L): An approximation to the constant implied by the sequence L`): print(`ConG1(L):`): elif nargs=1 and args[1]=CoSpSeq then print(`CoSpSeq(n1): the first n1 terms of the sequence : number of Condorcet scnearios with 2*v-1 voters and only preferences 123,231,312 allowed. Try`): print(`CoSpSeq(30);`): elif nargs=1 and args[1]=F then print(`F(n,i1,i2,i3,i4,i5): (2*n-1)!/(n-1-i2-i3-i5)!/i2!/i3!/(i2+i4+i5+1)!/(n-1-i1-i2-i4)!/i1!, the summand in the expression for a(n), the number of Condorcet preference profiles`): elif nargs=1 and args[1]=Gen then print(`Gen(a,b): The generic probability distrubution where the expected excess in the Condorcet paradox with cycle 1->2->3->1 is 0 (border-line case). Try:`): print(`Gen(1/6,1/6):`): elif nargs=1 and args[1]=IsCond then print(`IsCond(C): inputs a vote-count profile [c123,c132,c213,c231,c312,c321] meaning that c123 rankded the candidates (from best to worst) 123 etc.`): print(`decides whether the Condorcet paradox with the cycle 1->2->3->1 occurs. Try:`): print(`IsCond([2,1,5,3,4,5]);`): elif nargs=1 and args[1]=IsCondS123 then print(`IsCondS123(C): Inputs a symbolic vote-count profile and outputs the results of the three inequalities for the cycle 1->2->3->1`): elif nargs=1 and args[1]=IsCondS321 then print(`IsCondS321(C): Inputs a symbolic vote-count profile and outputs the results of the three inequalities for the cycle 3->2->1->3`): elif nargs=1 and args[1]=MyAsy then print(`MyAsy(L,n,k): tries to fit the sequence L to be of the form C*(1+c1/n+...+ck/n^k). Output is [C,*(1+c1/n+...+ck/n^k)]. Try:`): print(`L:=NuCoSeq(1000):L:=[seq(L[i]/6^(2*i-1),i=1..nops(L))]: MyAsy(L,n,3);`): elif nargs=1 and args[1]=NuCori then print(`NuCori(v): the number of Condorcet vote-profiles with three caondiates and v voters, done completey directly (i.e. neither using the recurrence nor the bijection). Of course even slower.`): print(`FOR CHECKING ONLY. Try:`): print(`[seq(NuCori(2*i-1),i=1..5)];`): elif nargs=1 and args[1]=NuCoDirect then print(`NuCoDirect(v): the number of Condorcet vote-profiles with 2v-1 voters, done via the bijection. Try:`): print(`[seq(NuCoDirect(i),i=1..5)];`): elif nargs=1 and args[1]=NuCo then print(`NuCo(v): the number of Condorcet vote-profiles with 2v-1 voters, done via the recurrence, hence much faster. Try:`): print(`NuCo(10000):`): elif nargs=1 and args[1]=NuCoSeq then print(`NuCoSeq(N):The first N terms of the sequence "number of Condorcet vote-profiles" with 2v-1 voters and three candidates. Using the third-order recurrence. Try:`): print(`NuCoSeq(100);`): elif nargs=1 and args[1]=OpeEq then print(`OpeEq(x,n,N): The operator that annililates PrCo(n,Gen(x,x)). Try:`): print(`OpeEq(x,n,N);`): elif nargs=1 and args[1]=Paper then print(`Paper(N1,N2): a paper about the Condorcet paradox with 3 candidates. It gives the first N1 terms of the Condorcet numbers, the N2-th one. Try:`): print(`Paper(100,1000);`): elif nargs=1 and args[1]=PaperEq then print(`PaperEq(K):A paper about the Condorcet Phenomenon with three candidates in the border-line phenomenon where the `): print(`prob. dist. on [123, ..., 321] is Gen(x,x), i.e. [x, 1/2-2*x, x, 1/2-2*x, x, x]. K is a simulation paramater`): print(`PaperEq(1000);`): elif nargs=1 and args[1]=PaperSp then print(`PaperSp(N1,N2,K):A paper about a special case of the Condorcet paradox where the only preferences are 123,231,312.N1: the length of the sequence. N2 the special case (larger than N1). K: the simulation parameter.Try:`): print(`PaperSp(100,1000,1000);`): elif nargs=1 and args[1]=p3n then print(`p3n(n): The probability of NOT having a Condorcet Scenario with three candidates ( our 1-NuCo(n)/6^(2*n-1) should equal p3n(n)`): print(`It uses the formula in the middle of page 204 of Brams and Fishburn's article`): print(`Try:`): print(`[seq(p3n(n),n=1..10)]; [seq(1-NuCo(n)/6^(2*n-1),n=1..10)];`): elif nargs=1 and args[1]=pm3 then print(`pm3(m): The probability of having a clear-cut Condorcet winner with m candidates and three voters, according to the formula for p(m,3) in Gehrlein-Fishburn (1979) reporduced in`. Try): print(`[seq(pm3(m),m=1..10)];`): elif nargs=1 and args[1]=PrCo then print(`PrCo(n,P): the probability of Condorcet vote-profiles with 2n-1 voters, done via the bijection with prob. distibution P. Try`): print(`PrCo(5,[1/6,1/6,1/6,1/6,1/6,1/6]);`): elif nargs=1 and args[1]=PrCo123 then print(`PrCo123(n,P): the probability of Condorcet vote-profiles with 2n-1 voters and cycle 1->2->3->1, done via the bijection with prob. distibution P. Try`): print(`PrCo123(5,[1/6,1/6,1/6,1/6,1/6,1/6]);`): elif nargs=1 and args[1]=PrCoEq then print(`PrCoEq(n1,x): the probability of a Condorcet cycle if the probab. distribution is Gen(x,x) i.e. [x, 1/2-2*x, b, 1/2-2*x, x, x] (a special case of a "border-line case", recall that Gen(a,b) is the general two-parameter scenario of`): print(` a borderline case). x can be symbolic, but it is numeric it must be between 0 and 1/4. Try:`): print(`PrCoEq(10,1/5);`): elif nargs=1 and args[1]=PrCoSp then print(`PrCoSp(n,p123,p231): the probability of a 1->2->3->1 Condorcet cycle if the probab. of 123 is p123, the prob. of 231 is p231 and the prob. of p312 is 1-p123-p231 with 2n-1 voters, using the recurrence. Try`): print(`PrCoSp(5,1/4,1/5);`): elif nargs=1 and args[1]=PrCoSpDirect then print(`PrCoSpDirect(n,p123,p231): the probability of a 1->2->3->1 Condorcet cycle if the probab. of 123 is p123, the prob. of 231 is p231 and the prob. of p312 is 1-p123-p231 with 2n-1 voters, done directly. Only for checking. Try`): print(`PrCoSpDirect(5,1/4,1/5);`): elif nargs=1 and args[1]=PrCoSpSeq then print(`PrCoSpSeq(n,p123,p231): the sequence of probability of a 1->2->3->1 Condorcet cycle if the probab. of 123 is p123, the prob. of 231 is p231 and the prob. of p312 is 1-p123-p231 with 2i-1 voters, for i=1..n, using the recurrence. Try`): print(`PrCoSpSeq(100,1/4,1/5);`): elif nargs=1 and args[1]=PrCo321 then print(`PrCo321(n,P): the probability of Condorcet vote-profiles with 2n-1 voters and cycle 3->2->1->3, done via the bijection with prob. distibution P. Try`): print(`PrCo321(5,[1/6,1/6,1/6,1/6,1/6,1/6]);`): elif nargs=1 and args[1]=OpeSp then print(`OpeSp(p123,p231,n,N): The fourth-order recurrence operator annihilating PrCo(n,[p123,0,0,p231,1-p123-p231,0]). Try:`): print(`OpeSp(1/10,2/10,n,N);`): elif nargs=1 and args[1]=OpeSpE then print(`OpeSpE(n,N): The operator annihilating the number of Condorcet scenarios with 2n-1 voters but with only 123,231,312 allowed. Try: `): print(` OpeSpE(n,N); `): elif nargs=1 and args[1]=REpaper then print(`REpaper(): a little paper about Rebecca Embar's bijection between compositions (into non-neg. integers) of n and Condorcet vote-count-profiles with 2n+3 voters. try:`): print(`REpaper():`): elif nargs=1 and args[1]=RVCP then print(`RVCP(v,P):the vote-count profile of a random voting profile with v voters. Try`): print(`RVCP(11,[1/6,1/6,1/6,1/6,1/6,1/6]);`): else print(`There is no such thing as`, args): fi: end: with(combinat): ##Start from FindRec.txt Yafe:=proc(ope,N) local i,ope1,coe1,L: if ope=0 then RETURN(1,0): fi: ope1:=expand(ope): L:=degree(ope1,N): coe1:=coeff(ope1,N,L): ope1:=normal(ope1/coe1): ope1:=normal(ope1): ope1:= convert( [seq(factor(coeff(ope1,N,i))*N^i,i=ldegree(ope1,N)..degree(ope1,N))],`+`): factor(coe1),ope1: end: #SeqFromRec(ope,n,N,Ini,K): Given the first L-1 #terms of the sequence Ini=[f(1), ..., f(L-1)] #satisfied by the recurrence ope(n,N)f(n)=0 #extends it to the first K values SeqFromRec:=proc(ope,n,N,Ini,K) local ope1,gu,L,n1,j1: ope1:=Yafe(ope,N)[2]: L:=degree(ope1,N): if nops(Ini)<>L then ERROR(`Ini should be of length`, L): fi: ope1:=expand(subs(n=n-L,ope1)/N^L): gu:=Ini: for n1 from nops(Ini)+1 to K do gu:=[op(gu), expand(-add(gu[nops(gu)+1-j1]*subs(n=n1,coeff(ope1,N,-j1)),j1=1..L)) ]: od: gu: end: ##End from FindRec.txt ###PRE-Computed opertor #OpeSp(p123,p231,n,N): The fourth-order recurrence operator annihilating PrCo(n,[p123,0,0,p231,1-p123-p231,0]). Try: #OpeSp(1/10,2/10,n,N); OpeSp:=proc(p123,p231,n,N): -8*p123*p231*(p231-1)*(p123-1)*(p123+p231)*(p123+p231-1)*(2*n+5)*(2*n+3)*(2*n+1 )/(n+3)/(n+2)/(n+1)+4*(2*n+5)*(2*n+3)*(4*n*p123^4*p231^2+8*n*p123^3*p231^3+4*n* p123^2*p231^4-4*n*p123^4*p231-16*n*p123^3*p231^2-16*n*p123^2*p231^3-4*n*p123* p231^4+2*p123^4*p231^2+4*p123^3*p231^3+2*p123^2*p231^4-n*p123^4+6*n*p123^3*p231 +13*n*p123^2*p231^2+6*n*p123*p231^3-n*p231^4-2*p123^4*p231-8*p123^3*p231^2-8* p123^2*p231^3-2*p123*p231^4+2*n*p123^3+n*p123^2*p231+n*p123*p231^2+2*n*p231^3- p123^4+2*p123^3*p231+5*p123^2*p231^2+2*p123*p231^3-p231^4-n*p123^2-3*n*p123* p231-n*p231^2+2*p123^3+3*p123^2*p231+3*p123*p231^2+2*p231^3-p123^2-3*p123*p231- p231^2)/(n+3)/(n+2)/(n+1)*N+4*(2*n+5)*(2*n*p123^4+4*n*p123^3*p231+6*n*p123^2* p231^2+4*n*p123*p231^3+2*n*p231^4-4*n*p123^3-10*n*p123^2*p231-10*n*p123*p231^2-\ 4*n*p231^3+3*p123^4+6*p123^3*p231+9*p123^2*p231^2+6*p123*p231^3+3*p231^4+n*p123 ^2+5*n*p123*p231+n*p231^2-6*p123^3-15*p123^2*p231-15*p123*p231^2-6*p231^3+n* p123+n*p231+p123^2+7*p123*p231+p231^2+2*p123+2*p231)/(n+2)/(n+3)*N^2+(8*n*p123^ 2+8*n*p123*p231+8*n*p231^2-8*n*p123-8*n*p231+20*p123^2+20*p123*p231+20*p231^2-n -20*p123-20*p231-3)/(n+3)*N^3+N^4: end: ###End-Computed opertor CompToCond:=proc(c): [1,0,0,1,1,0]+[c[1]+c[4]+c[6],c[2],c[3],c[2]+c[4]+c[5],c[3]+c[5]+c[6],c[1]]:end: CondToComp:=proc(co):[co[6], co[2], co[3], -1/2*co[2]+1/2*co[3]-1/2*co[6]-1/2-1/2*co[5]+1/2*co[4]+1/2*co[1], -1/2*co[3]+1/2*co[6]-1/2*co[2]-1/2+1/2*co[5]+1/2*co[4]-1/2*co[1], -1/2*co[6]+1/2*co[2]-1/2*co[3]-1/2+1/2*co[5]-1/2*co[4]+1/2*co[1]]: end: #Comps(n,k): The set of all compositions of n into exactly k parts (with non-negative entrties) Comps:=proc(n,k) local S,a,S1,s: option remember: if k=0 then if n=0 then RETURN({[]}): else RETURN({}): fi: fi: S:={}: for a from 0 to n do S1:=Comps(n-a,k-1): S:=S union {seq([op(s),a],s in S1)}: od: S: end: #IsCond(C): inputs a vote-count profile [c123,c132,c213,c231,c312,c321] meaning that c123 rankded the candidates (from best to worst) 123 etc. #decides whether the Condorcet paradox with the cycle 1->2->3->1 occurs. Try: #IsCond([2,1,5,3,4,5]); IsCond123:=proc(C) local i,P,T: P:=permute(3): for i from 1 to nops(C) do T[P[i]]:=C[i]: od: #1->2->3->1 if (T[[1,2,3]]+T[[1,3,2]]+T[[3,1,2]])- (T[[2,1,3]]+T[[2,3,1]]+T[[3,2,1]])>0 and (T[[1,2,3]]+T[[2,1,3]]+T[[2,3,1]])-(T[[1,3,2]]+T[[3,1,2]]+T[[3,2,1]])>0 and (T[[2,3,1]]+T[[3,2,1]]+T[[3,1,2]])-(T[[2,1,3]]+T[[1,2,3]]+T[[1,3,2]])>0 then true: else false: fi: end: IsCond321:=proc(C) local i,P,T: P:=permute(3): for i from 1 to nops(C) do T[P[i]]:=C[i]: od: #3->2->1->3 if (T[[1,2,3]]+T[[1,3,2]]+T[[3,1,2]])- (T[[2,1,3]]+T[[2,3,1]]+T[[3,2,1]])<0 and (T[[1,2,3]]+T[[2,1,3]]+T[[2,3,1]])-(T[[1,3,2]]+T[[3,1,2]]+T[[3,2,1]])<0 and (T[[2,3,1]]+T[[3,2,1]]+T[[3,1,2]])-(T[[2,1,3]]+T[[1,2,3]]+T[[1,3,2]])<0 then true: else false: fi: end: IsCond:=proc(C): IsCond123(C) or IsCond321(C): end: #Cond(v): The set of vote-count profiles with three candidates that lead to the cycle 1->2->3->1 the output is the set of lists of non-negative intgers that add-up to v with that property #with the ordering [123,132,213,231,312,321]. Try: #Cond(5); Cond:=proc(v) local A,a,C: A:=Comps(v,6): C:={}: #C is the SET of vote-count profiles with v voters that lead to 1->2->3->1 for a in A do if IsCond(a) then C:=C union {a}: fi: od: C: end: #IsCondS123(C): inputs a vote-count profile outputs true iff 1->2->3->1, IsCondS123:=proc(C) local i,P,T: P:=permute(3): for i from 1 to nops(C) do T[P[i]]:=C[i]: od: [T[[1,2,3]]+T[[1,3,2]]+T[[3,1,2]]- (T[[2,1,3]]+T[[2,3,1]]+T[[3,2,1]]), T[[1,2,3]]+T[[2,1,3]]+T[[2,3,1]]-(T[[1,3,2]]+T[[3,1,2]]+T[[3,2,1]]), T[[2,3,1]]+T[[3,2,1]]+T[[3,1,2]]-(T[[2,1,3]]+T[[1,2,3]]+T[[1,3,2]])]: end: #IsCondS321(C): inputs a vote-count profile outputs true iff 3->2->1->3, IsCondS321:=proc(C) local i,P,T: -IsCondS123(C): end: #NuCori(v): the number of Condorcet vote-profiles with v voters NuCori:=proc(v) local S,i,s: S:=Cond(v): add(convert(s,`+`)!/mul(s[i]!,i=1..nops(s)),s in S): end: F:=proc(n,i1,i2,i3,i4,i5): (2*n-1)!/(n-1-i2-i3-i5)!/i2!/i3!/(i2+i4+i5+1)!/(n-1-i1-i2-i4)!/i1! end: #NuCoDirect(n): the number of Condorcet vote-profiles with 2n-1 voters done via the bijection NuCoDirect:=proc(n) local i1,i2,i3,i4,i5,co: co:=0: for i1 from 0 to n-2 do for i2 from 0 to n-2-i1 do for i3 from 0 to n-2-i1-i2 do for i4 from 0 to n-2-i1-i2-i3 do for i5 from 0 to n-2-i1-i2-i3-i4 do co:=co+(2*n-1)!/(n-1-i2-i3-i5)!/i2!/i3!/(i2+i4+i5+1)!/(n-1-i1-i2-i4)!/i1!: od:od:od:od:od: 2*co: end: #[0, 6, 270], 4*(19*n^2-57*n+45)/(n-1)^2/N-36*(2*n-3)*(22*n^2-99*n+111)/(n-2)/(n-1)^2/N^2+1296*(n-3)*(2*n-3)*(2*n-5)/(n-2)/(n-1)^2/N^3 #NuCoSeq(N):The first N terms of the sequence "number of Condorcet vote-profiles" with 2v-1 voters and three candidates. Using the third-order recurrence. Try: #NuCoSeq(100); NuCoSeq:=proc(N) local L,n,kha: L:=[0,12,540]: for n from 4 to N do kha:=4*(19*n^2-57*n+45)/(n-1)^2*L[-1]-36*(2*n-3)*(22*n^2-99*n+111)/(n-2)/(n-1)^2*L[-2]+1296*(n-3)*(2*n-3)*(2*n-5)/(n-2)/(n-1)^2*L[-3]: L:=[op(L),kha]: od: L: end: #NuCo(N):The first N terms of the sequence "number of Condorcet vote-profiles" with 2v-1 voters and three candidates. Using the third-order recurrence. Try: #NuCo(100); NuCo:=proc(N) local L,n,kha: L:=[0,12,540]: if N<=3 then RETURN(L[N]): fi: for n from 4 to N do kha:=4*(19*n^2-57*n+45)/(n-1)^2*L[-1]-36*(2*n-3)*(22*n^2-99*n+111)/(n-2)/(n-1)^2*L[-2]+1296*(n-3)*(2*n-3)*(2*n-5)/(n-2)/(n-1)^2*L[-3]: L:=[L[2],L[3],kha]: od: L[-1]: end: #PrCo123(n,P): the probability of Condorcet vote-profiles with 2n-1 voters with cycle 1->2->3->1 done via the bijection with prob. distibution P PrCo123:=proc(n,P) local i1,i2,i3,i4,i5,co: co:=0: for i1 from 0 to n-2 do for i2 from 0 to n-2-i1 do for i3 from 0 to n-2-i1-i2 do for i4 from 0 to n-2-i1-i2-i3 do for i5 from 0 to n-2-i1-i2-i3-i4 do co:=co+(2*n-1)!/(n-1-i2-i3-i5)!/i2!/i3!/(i2+i4+i5+1)!/(n-1-i1-i2-i4)!/i1!* P[1]^(n-1-i2-i3-i5)*P[2]^i2*P[3]^i3*P[4]^(i2+i4+i5+1)*P[5]^(n-1-i1-i2-i4)*P[6]^i1: od:od:od:od:od: co: end: #PrCo321(n,P): the probability of Condorcet vote-profiles with 2n-1 voters with cycle 3->2->1->3 done via the bijection with prob. distibution P PrCo321:=proc(n,P): PrCo123(n,[P[6],P[4],P[5],P[2],P[3],P[1]]): end: #PrCo(n,P): the probability of Condorcet vote-profiles with 2n-1 voters with prob. distibution P PrCo:=proc(n,P):expand(PrCo123(n,P)+PrCo321(n,P)):end: #MyAsy(L,n,k): tries to fit the sequence L to be of the form C*(1+c1/n+...+ck/n^k). Output is [C,*(1+c1/n+...+ck/n^k)]. Try: #L:=NuCoSeq(1000):L:=[seq(L[i]/6^(2*i-1),i=1..nops(L))]: MyAsy(L,n,3); MyAsy:=proc(L,n,k) local gu,logC,theta,c,i,eq,var,C,x,ku: if nops(L)<20 then print(`List must be at least of length 20`): RETURN(FAIL): fi: if 10+k>nops(L) then print(`k must be at most`, nops(L)-10 ): fi: gu:=logC+theta*log(n)+add(c[i]/n^i,i=1..k): var:={logC,theta,seq(c[i],i=1..k)}: eq:={seq(log(L[i])-subs(n=i,gu),i=nops(L)-k-1..nops(L))}: var:=evalf(solve(eq,var)): C:=exp(subs(var,logC)): theta:=subs(var,theta): ku:= exp(subs(var,add(c[i]*x^i,i=1..k))): ku:=taylor(ku,x=0,k+1): ku:=evalf(add(coeff(ku,x,i)/n^i,i=0..k)): [C,ku]: end: #ConCon1(N): An approximation to the Condorect constant using N terms. Try: #ConCon1(1000): ConCon1:=proc(N) local L,i,n: L:=NuCoSeq(N): L:=[seq(L[i]/6^(2*i-1),i=1..N)]: MyAsy(L,n,4)[1]: end: #ConCon(D1): The 3-candidate Condorcet constant to D1 digits ConCon:=proc(D1) local a,b,c,i: a:=ConCon1(1000): b:=ConCon1(2000): for i from 3 while abs(a-b)>10^(-2*D1) do c:=ConCon1(1000*i): a:=b: b:=c: od: evalf(b,D1): end: #LD1(L): Inputs a list of positive integers L (of n:=nops(L) members) #outputs an integer i from 1 to n with the prob. of i being #proportional to L[i] #For example LD([1,2,3]) should output 1 with prob. 1/6 #output 2 with prob. 1/3 #output 3 with prob. 3/6=1/2 LD1:=proc(L) local n,i,su,r: n:=nops(L): r:=rand(1..convert(L,`+`))(): su:=0: for i from 1 to n do su:=su+L[i]: if r<=su then RETURN(i): fi: od: end: #LD(P): Prob. table P LD:=proc(P) local i,M: if convert(P,`+`)<>1 then RETURN(FAIL): fi: M:=lcm(seq(denom(P[i]),i=1..nops(P))): LD1([seq(M*P[i],i=1..nops(P))]): end: #RVCP(v,P):the vote-count profile of a random voting profile with v voters. Try #RVCP(11,[1/6,1/6,1/6,1/6,1/6,1/6]); RVCP:=proc(v,P) local i,f,x: f:=add(x[LD(P)],i=1..v): [seq(coeff(f,x[i],1),i=1..nops(P))]: end: #ApCo(v,P,K): approximatin the prob. of a Condorcet scenario with probabilty table P using K random votes ApCo:=proc(v,P,K) local i,co,PROF: co:=0: for i from 1 to K do PROF:=RVCP(v,P): if IsCond(PROF) then co:=co+1: fi: od: evalf(co/K): end: #PrCoSpDirect(n1,p123,p231): the probability of a 1->2->3->1 Condorcet cycle if the probab. of 123 is p123, the prob. of 231 is p231 and the prob. of p312 is 1-p123-p231 with 2n-1 voters, done directly. Only for checking. Try #PrCoSpDirect(5,1/4,1/4); PrCoSpDirect:=proc(n1,p123,p231) local L,kha,i,j,ope: expand(PrCo(n1,[p123,0,0,p231,1-p123-p231,0])): end: #PrCoSp(n1,p123,p231): the probability of a 1->2->3->1 Condorcet cycle if the probab. of 123 is p123, the prob. of 231 is p231 and the prob. of p312 is 1-p123-p231 with 2n-1 voters, using the recurrence. Try #PrCoSp(5,1/4,1/4); PrCoSp:=proc(n1,p123,p231) local L,ope,n,N: L:= [0, -6*p123^2*p231-6*p123*p231^2+6*p123*p231, 30*p123^4*p231+60*p123^3*p231^2+60*p123^2*p231^3+30*p123*p231^4-60*p123^3*p231-90*p123^2*p231^2-60*p123*p231^3+30*p123^2*p231+30*p123*p231^2, -140*p123^6*p231-420*p123^5*p231^2-700*p123^4*p231^3-700*p123^3*p231^4-420*p123^2* p231^5-140*p123*p231^6+420*p123^5*p231+1050*p123^4*p231^2+1400*p123^3*p231^3+1050*p123^2*p231^4+420*p123*p231^5-420*p123^4*p231-840*p123^3*p231^2-840*p123^2*p231^3-420*p123*p231^4+140*p123^3*p231+210*p123^2*p231^2+140*p123*p231^3]: if n1<=4 then RETURN(L[n1]): fi: ope:=OpeSp(p123,p231,n,N): SeqFromRec(ope,n,N,L,n1)[-1]: end: #PrCoSpSeq(n1,p123,p231): the probability of a 1->2->3->1 Condorcet cycle if the probab. of 123 is p123, the prob. of 231 is p231 and the prob. of p312 is 1-p123-p231 with 2n-1 voters, using the recurrence. Try #PrCoSpSeq(5,1/4,1/4); PrCoSpSeq:=proc(n1,p123,p231) local L,ope,n,N: L:= [0, -6*p123^2*p231-6*p123*p231^2+6*p123*p231, 30*p123^4*p231+60*p123^3*p231^2+60*p123^2*p231^3+30*p123*p231^4-60*p123^3*p231-90*p123^2*p231^2-60*p123*p231^3+30*p123^2*p231+30*p123*p231^2, -140*p123^6*p231-420*p123^5*p231^2-700*p123^4*p231^3-700*p123^3*p231^4-420*p123^2* p231^5-140*p123*p231^6+420*p123^5*p231+1050*p123^4*p231^2+1400*p123^3*p231^3+1050*p123^2*p231^4+420*p123*p231^5-420*p123^4*p231-840*p123^3*p231^2-840*p123^2*p231^3-420*p123*p231^4+140*p123^3*p231+210*p123^2*p231^2+140*p123*p231^3]: if n1<=4 then RETURN([op(1..n1,L)]): fi: ope:=OpeSp(p123,p231,n,N): SeqFromRec(ope,n,N,L,n1): end: #OpeSpE(n,N): The operator annihilating the number of Condorcet scenarios with 2n-1 voters but with only 123,231,312 allowed OpeSpE:=proc(n,N) 36*(2*n+1)/(n+1)-(17*n+13)/(n+1)*N+N^2: end: #CoSpSeq(n1): the first n1 terms of the sequence : number of Condorcet scnearios with 2*v-1 voters and only preferences 123,231,312 allowed. Try #CoSpSeq(30); CoSpSeq:=proc(n1) local L,ope,n,N: L:=[0,6]: if n1<=2 then RETURN([op(1..n1,L)]): fi: ope:=OpeSpE(n,N): SeqFromRec(ope,n,N,L,n1): end: #REpaper(): a little paper about Rebecca Embar's bijection between compositions (into non-neg. integers) of n and Condorcet vote-count-profiles with 2n+3 voters`). try: #REpaper(): REpaper:=proc() local gu,c,lu,mu,i: print(`The bijective mapping between a composition into six parts `, [seq(c[i],i=1..6)], `of n, say (into non-neg. integers) and Condorcet vote-count profile with the 1->2->3->1 and 2n+3 voters, is`): gu:=CompToCond([seq(c[i],i=1..6)]): print(gu): print(`and in Maple format`): print(``): lprint(gu): print(``): print(`the sum of the components is`): print(``): print(add(gu)): print(``): print(`as you can see, it is indeed 2n+3`): print(``): mu:=IsCondS123(gu) : print(``): print(`The Condorcet inequlity conditions for 1->2->3->1 are `): print(``): print(mu): print(``): print(`As you can see they are all strictly positive if`, seq(c[i],i=1..6), ` are all non-negative (as they should be). `): print(``): lu:=[c[123],c[132],c[213],c[231],c[312],c[321]]: print(``): print(` Let `, lu, `be a composition (with non-neg. integers) that constitutes a Condorcet 1->2->3->1 vote-count profile with 2n+3 voters `): print(``): print(`The inverse mapping to compositions of n into six non-negative integers is`): gu:=CondToComp(lu): print(``): print(gu): print(``): print(`and in Maple format`): print(``): lprint(gu): print(``): print(`These mappings are inverses of each other. Indeed applying CondToComp(CompToCond) `): print(``): lprint(`To `, [seq(c[i],i=1..6)] ): print(`gives `): print(``): lprint( CondToComp(CompToCond([seq(c[i],i=1..6)]) )): print(``): print(`In the other direction, applying CompToCond(CondToComp) to `): print(``): lprint([c[123],c[132],c[213],c[231],c[312],c[321]]): print(``): print(`Gives `): print(``): lprint(CompToCond(CondToComp([c[123],c[132],c[213],c[231],c[312],c[321]]))): print(``): end: #Paper(N1,N2):A verbose form of NuCoSeq(N1) (q.v.), try: #Paper(100,1000); Paper:=proc(N1,N2) local L,n,kha,i1,i2,i3,i4,i5,a,lu,mu,t0: L:=[0,12,540]: t0:=time(): print(`The first`, N1, `terms of the sequence enumerating Vote profiles with Three candidates and 2n-1 voters that lead to the Condorcet Paradox as well as the`, N2, ` -th term `): print(``): print(`By Shalosh B. Ekhad `): print(``): print(`Suppose that there are 2n-1 voters each completely ranking three candidates, let's call them 1,2,3. So altogether there are 6 possible choices for each of these 2n-1 voters`): print(``): print(`Namely: 123,132,213,231,312,321 `): print(``): print(`Of course there are `, 6^(2*n-1) , `possible vote-profiles `): print(``): print(`Let a(n) be the number of voting-profiles that lead to Condorcet scenarios. Thanks to the beautiful bijection between compositions (into non-neg. integers) of n-2 and Condorect vote-count profiles`): print(` (doubling it to account for the reverse cycle`): print(``): print(`and since the mapping of the compositions`, [i1,i2,i3,i4,i5,n-2-i1-i2-i3-i4], `goes to the Condorcet vote-profile `): print(``): print(CompToCond([i1,i2,i3,i4,i5,n-2-i1-i2-i3-i4-i5])): print(``): print(`gives rise to the following explicit expression for a(n) as a five-fold sum`): print(``): print(a(n)=Sum(Sum(Sum(Sum(Sum(F(n,i1,i2,i3,i4,i5),i5=0..n-2-i1-i2-i3-i4),i4=0..n-2-i1-i2-i3),i3=0..n-2-i1-i2),i2=0..n-2-i1),i1=0..n-2)): print(``): print(`Using Wilf-Zeilberger proof theory it is easy to get the following third-order recurrence for a(n)`): print(``): print(a(n)=4*(19*n^2-57*n+45)/(n-1)^2*a(n-1)-36*(2*n-3)*(22*n^2-99*n+111)/(n-2)/(n-1)^2*a(n-2)+1296*(n-3)*(2*n-3)*(2*n-5)/(n-2)/(n-1)^2*a(n-3)): print(``): print(`and in Maple format `): print(``): lprint(a(n)=4*(19*n^2-57*n+45)/(n-1)^2*a(n-1)-36*(2*n-3)*(22*n^2-99*n+111)/(n-2)/(n-1)^2*a(n-2)+1296*(n-3)*(2*n-3)*(2*n-5)/(n-2)/(n-1)^2*a(n-3)): print(``): print(`subject to the initial conditions `): print(``): print(seq(a(i1)=L[i1],i1=1..3)): print(``): print(`Let;s use it to quickly compute the first`, N1, `terms of the sequence `): print(``): for n from 4 to N1 do kha:=4*(19*n^2-57*n+45)/(n-1)^2*L[-1]-36*(2*n-3)*(22*n^2-99*n+111)/(n-2)/(n-1)^2*L[-2]+1296*(n-3)*(2*n-3)*(2*n-5)/(n-2)/(n-1)^2*L[-3]: L:=[op(L),kha]: od: lprint(L): print(``): print(`Just for fun, and to prove the efficiency`): print(``): print(a(N2)=NuCo(N2)): print(``): print(`---------------------------------------------------------------`): print(``): print(`This took`, time()-t0, `seconds . `): end: #ConG1(L): An approximation to the constant implied by the sequence L #ConG1(L): ConG1:=proc(L) local n: MyAsy(L,n,4)[1]: end: #PaperSp(N1,N2,K):A paper about a special case of the Condorcet paradox where the only preferences are 123,231,312. r is the respolution for the numerics. #N1,N2, are the story parameters, and K is the simulation parameter. Try #PaperSp(100,0.1); PaperSp:=proc(N1,N2,K) local n,p123,p231,ope,N,i,lu,a,b: print(`A recurrence for the Condorcet Paradox with Three Candidates where the only allowed permutations are 123,231,312 `): print(``): print(`By Shalosh B. Ekhad `): print(``): print(`Suppose that there are 2n-1 voters each completely ranking three candidates, let's call them 1,2,3. Also assume that there are ony 3 allowed choices for each of these 2n-1 voters`): print(``): print(`Namely: 123, 231,312 `): print(``): print(`Of course there are `, 3^(2*n-1) , `possible such vote-preferences `): print(``): print(`Let a(n) be the number of vote-preferences that lead to Condorcet scenarios in this resticted case). Thanks to the beautiful bijection between compositions (into non-neg. integers) of n-2 and Condorect vote-count profiles`): print(``): print(`and Using Wilf-Zeilberger proof theory it is easy to get the following second-order recurrence for a(n)`): print(``): print(36*(2*n+1)/(n+1)*a(n)-(17*n+13)/(n+1)*a(n+1)+a(n+2)=0): print(``): print(`and in Maple formal `): print(``): lprint(36*(2*n+1)/(n+1)*a(n)-(17*n+13)/(n+1)*a(n+1)+a(n+2)=0): print(``): print(`subject to the initial conditions `): print(``): print(a(1)=0, a(2)=6): print(``): print(`Using this recurrence we can easily compute the first`, N1, `terms `): print(``): lprint(CoSpSeq(N1)): print(``): print(`Just for fun here is`, a(N2)): print(``): lprint(CoSpSeq(N2)[-1]): print(``): print(`Of course, by the law of large numbers a(n)/3^(2*n-1) tends to 1.`): print(``): print(`Now suppose that the prob. of the ranking 123 is p123, the prob. of the ranking 231 is p231 and the prob. of the ranking p312 is 1-p123-p231 . Let b(n) be the prob. of a Condorcet scenariowhen where there are 2n-1 voters.`): print(``): print(``): print(`Using Wilf-Zeilberger proof theory it is easy to get the following fourth-order recurrence for b(n)`): print(``): ope:=OpeSp(p123,p231,n,N): print(``): print(add(coeff(ope,N,i)*b(n+i),i=0..4)=0): print(``): print(`and in Maple format `): print(``): print(``): lprint(add(coeff(ope,N,i)*b(n+i),i=0..4)=0): print(``): print(`Of course by the law of large numbers, as n goes to infinity, b(n) tends to 0 if p123+p231<1/2, tends to 1 if p123+p231>1/2, and to 1/2 if p123+p231=1/2 `): print(``): print(`Let's try out an example with p123=1/5,p231=1/5, and p312=3/5 and 99 voters, i.e. n=50`): print(``): lu:=PrCoSp(50,1/5,1/5): print(`The exact probabilty of a Condorcet scenario is`, lu, `and in decimals it is`, evalf(lu,10)): print(``): print(`Let's test is with simulations, with`, K, ` tries `): print(``): lu:=ApCo(99,[1/5,0,0,1/5,3/5,0],K): print(`We get that the estimated probability is`,lu): print(``): print(`Let's try out an example with p123=1/4,p231=1/4, and p312=1/2 and 99 voters, i.e. n=50`): print(``): lu:=PrCoSp(50,1/4,1/4): print(`The exact probabilty of a Condorcet scenario is`, lu, `and in decimals it is`, evalf(lu,10)): print(``): print(`Let's test is with simulations, with`, K, ` tries `): print(``): lu:=ApCo(99,[1/4,0,0,1/4,1/2,0],K): print(`We get that the estimated probability is`,lu): print(``): print(`Let's try out an example with p123=11/40,p231=11/40, and p312=9/40 and 99 voters, i.e. n=50`): print(``): lu:=PrCoSp(50,11/40,11/40): print(`The exact probabilty of a Condorcet scenario is`, lu, `and in decimals it is`, evalf(lu,10)): print(``): print(`Let's test is with simulations, with`, K, ` tries `): print(``): lu:=ApCo(99,[11/40,0,0,11/40,9/20,0],K): print(`We get that the estimated probability is`,lu): print(``): end: #Gen(a,b): The generic probability distrubution where the expected excess in the Condorcet paradox with cycle 1->2->3->1 is 0 (border-line case). Try: #Gen(1/6,1/6): Gen:=proc(a,b):[a, 1/2-a-b, b, 1/2-a-b, b, a]:end: #OpeEq(x,n,N): The operator that annililates PrCo(n,Gen(x,x)). Try: #OpeEq(x,n,N); OpeEq:=proc(x,n,N): -1/16*n*(8*x-1)^2*(4*x-1)^2*(2*n+5)*(2*n+3)*(2*n+1)*(2*n+7)/(n+2)/(n+4)^2/(n+3) ^2+1/16*(2*n+5)*(2*n+3)*(2*n+7)*(6144*n^2*x^4-4608*n^2*x^3+15360*n*x^4+1408*n^2 *x^2-11520*n*x^3+10240*x^4-192*n^2*x+3360*n*x^2-7680*x^3+10*n^2-432*n*x+2160*x^ 2+21*n-264*x+12)/(n+2)/(n+4)^2/(n+3)^2*N-1/4*(2*n+7)*(2*n+5)*(3072*n^3*x^4-2304 *n^3*x^3+18432*n^2*x^4+864*n^3*x^2-13824*n^2*x^3+37120*n*x^4-144*n^3*x+4944*n^2 *x^2-27840*n*x^3+25600*x^4+10*n^3-792*n^2*x+9620*n*x^2-19200*x^3+52*n^2-1494*n* x+6420*x^2+93*n-966*x+57)/(n+2)/(n+4)^2/(n+3)^2*N^2+1/2*(2*n+7)*(1024*n^3*x^4-\ 768*n^3*x^3+8704*n^2*x^4+448*n^3*x^2-6528*n^2*x^3+24320*n*x^4-96*n^3*x+3568*n^2 *x^2-18240*n*x^3+22400*x^4+10*n^3-744*n^2*x+9520*n*x^2-16800*x^3+73*n^2-1944*n* x+8520*x^2+180*n-1716*x+150)/(n+4)^2/(n+3)^2*N^3-(80*n^2*x^2-24*n^2*x+560*n*x^2 +5*n^2-168*n*x+980*x^2+32*n-294*x+51)/(n+4)^2*N^4+N^5: end: #PrCoEq(n1,x): the probability of a Condorcet cycle if the probab. distribution is Gen(x,x) i.e. [x, 1/2-2*x, b, 1/2-2*x, x, x] (a special case of a "border-line case", recall that Gen(a,b) is the general two-parameter scenario of # a borderline case). x can be symbolic, but it is numeric it must be between 0 and 1/4. Try: #PrCoEq(10,1/5); PrCoEq:=proc(n1,x) local L,ope,n,N: if type(x,numeric) then if not (0<=x and x<=1/4) then print(x, `should have been between 0 and 1/4`): RETURN(FAIL): fi: fi: L:=[0, -24*x^3+6*x^2, -1080*x^5+630*x^4-150*x^3+15*x^2, 43400*x^6-50400*x^7-16380*x^5+3430*x^4-420*x^3+105/4*x^2, -3465/4*x^3-163485/2*x^5-1417500*x^7-2499000*x^9+315/8*x^2+41895/4*x^4+423150*x^6+2800350*x^8]: if n1<=5 then RETURN(L[n1]): fi: ope:=OpeEq(x,n,N): SeqFromRec(ope,n,N,L,n1)[-1]: end: #PaperEq(K):A paper about the Condorcet Phenomenon with three candidates in the border-line phenomenon where the #prob. dist. on [123, ..., 321] is Gen(x,x), i.e. [x, 1/2-2*x, x, 1/2-2*x, x, x]. Try: #PaperEq(x0,1000); PaperEq:=proc(K) local n,x,b,ope,N,i,lu,P,gu: print(`A recurrence for the Condorcet Paradox with Three Candidates where the probability distribion on the ranking is `, Gen(x,x)): print(``): print(`By Shalosh B. Ekhad `): print(``): P:=Gen(x,x): print(`Suppose that there are 2n-1 voters each completely ranking three candidates, let's call them 1,2,3. Also assume that each voter independtly picks a randking with the`): print(`following probability distribution`): print(``): print(`Prob. of 123 is`, P[1]): print(``): print(`Prob. of 132 is`, P[2]): print(``): print(`Prob. of 213 is`, P[3]): print(``): print(`Prob. of 231 is`, P[4]): print(``): print(`Prob. of 312 is`, P[5]): print(``): print(`Prob. of 321 is`, P[6]): print(``): print(`Let b(n) be the probability of a Condorcet scenario when there are 2n-1 voters`): print(``): print(`Using Wilf-Zeilberger proof theory it is easy to get the following fifth-order recurrence for b(n)`): print(``): ope:=OpeEq(x,n,N): print(``): print(add(coeff(ope,N,i)*b(n+i),i=0..degree(ope,N))=0): print(``): print(`and in Maple format `): print(``): print(``): lprint(add(coeff(ope,N,i)*b(n+i),i=0..degree(ope,N))=0): print(``): print(`Let's try out an example with x=1/10 and n=100, i.e. 199 voters`): print(``): lu:=PrCoEq(100,1/10): print(`The exact probabilty of a Condorcet scenario is`, lu, `and in decimals it is`, evalf(lu,10)): print(``): print(`Let's test is with simulations, with`, K, ` tries `): print(``): lu:=ApCo(199, Gen(1/10,1/10),K): print(`We get that the estimated probability is`,lu): print(``): print(`Let's try out an example with x=1/5 and n=100, i.e. 199 voters`): print(``): lu:=PrCoEq(100,1/5): print(`The exact probabilty of a Condorcet scenario is`, lu, `and in decimals it is`, evalf(lu,10)): print(``): print(`Let's test is with simulations, with`, K, ` tries `): print(``): lu:=ApCo(199, Gen(1/5,1/5),K): print(`We get that the estimated probability is`,lu): print(``): print(`Let's try out an example with x=23/25 and n=100, i.e. 199 voters`): print(``): lu:=PrCoEq(100,23/100): print(`The exact probabilty of a Condorcet scenario is`, lu, `and in decimals it is`, evalf(lu,10)): print(``): print(`Let's test is with simulations, with`, K, ` tries `): print(``): lu:=ApCo(199, Gen(23/100,23/100),K): print(`We get that the estimated probability is`,lu): print(``): gu:=PrCoEq(50,x): print(``): print(`Finally let's see how the probability of theCondorcet paradox changes when there are 99 voters and the prob. dist. is `, Gen(x,x), ` from x=0 to x=1/4 `): print(``): print(plot(gu,x=0..1/4)): print(``): end: #p3n(n): The probability of NOT having a Condorcet Scenario with three candidates ( our 1-NuCo(n)/6^(2*n-1) should equal p3n(n) #It is formula for p(3,n) in Brams and Fishburn's article with n relaced by 2n-1 p3n:=proc(n) local n1,n2,n3:3^(-2*n+2)*(2*n-1)!*add(add(add(2^(-n2-n3)/n1!/n2!/n3!/(2*n-1-n1-n2-n3)!,n3=0..n-1-n1),n2=0..n-1-n1),n1=0..n-1):end: #pm3(m,3): The probability of having a clear-cut Condorcet winner with m candidates and three voters, according to the formula for p(m,3) in Gehrlein-Fishburn (1979) reporduced in #Brams-Fishburn (2002), p. 204 pm3:=proc(m) local m1,m2: add(add((m-1-m1)!*(m-1-m2)!/m!/(m-1-m1-m2)!/(m1+m2+1),m2=0..m-1-m1), m1=0..m-1): end: