#OK to post homework
#Yuxuan Yang, March 26th, Assignment 16
with(combinat):

#2
IsCondorcet:=proc(P) local L:
L:=SV(Tour(P)):if nops(L)=nops({op(L)}) then RETURN(false): fi: true:
end:

#3
ExactCond:=proc(n,v) local R,rp,m,m1:
R:=RP(n,v): m:=nops(R):m1:=0:
for rp in R do
 if IsCondorcet(rp) then m1:=m1+1: fi:
od:
evalf(m1/m):
end:

#4
EstCond:=proc(n,v,K) local m1,rp,i:
m1:=0:
for i from 1 to K do
 if IsCondorcet(RandP(n,v)) then
  m1:=m1+1:
 fi:
od:
evalf(m1/K):
end:

#5
Borda:=proc(P) local n,vo,B,i:
n:=nops(P[1]):
B:=[0$n]:
for vo in P do
 for i from 1 to n do:
  B[vo[i]]:=B[vo[i]]+n-i:
 od:
od:
B:
end:


#6
CondorcetRank:=proc(P) local V,W,i,rank,n:
V:=SV(Tour(P)):W:=[]:
n:=nops(V):
rank:=[seq({},i=1..n)]:
for i from 1 to n do
rank[n-V[i]]:={op(rank[n-V[i]]),i}:
od:
for i from 1 to n do
if nops(rank[i])<>0 then 
W:=[op(W),rank[i]]:
fi:
od:
W:
end:

#7
BordaRank:=proc(P) local ve,le,rank,i,j:
ve:=Borda(P):
le:=sort([op({op(Borda(P))})],`>`):
rank:=[seq({},i=1..nops(le))]:
for j from 1 to nops(le) do
 for i from 1 to nops(ve) do
  if le[j]=ve[i] then
   rank[j]:={op(rank[j]),i}:
  fi:
 od:
od:
rank:
end:



#Maple code for Lecture 16
#C16.txt, March 21, 2022; Starting Social Choice theory
Help16:=proc(): print(`RP(n,v), inv(pi) , Cij(P,i,j), RandP(n,v), Tour(P), SV(T) `): 
end:

with(combinat):

#inv(pi): the inverse of the permutation pi
inv:=proc(pi) local T,i:
for i from 1 to nops(pi) do
T[pi[i]]:=i:
od:
[seq(T[i],i=1..nops(pi))]:
end:

#RandP(n,v)
RandP:=proc(n,v) local i:
[seq(randperm(n),i=1..v)]:
end:

#RP(n,v): all the possible voting profiles with n candidates {1,...n}
#[[1,3,2],[2,1,3]],   [1,3,2]-> [[1,3,2]]
RP:=proc(n,v) local S,P1,p,s:
option remember:
S:=permute(n):
if v=1 then
 RETURN( {seq([s]  , s in S)}):
fi:
P1:=RP(n,v-1):
{seq(seq([op(p),s],s in S),p in P1)}:
end:


#Cij(P,i,j): inputs a voting profile P and candidates i and  j how many
#voters pefer i to j?
Cij:=proc(P,i,j) local k1,co,pi:
co:=0:

for k1 from 1 to nops(P) do
pi:=inv(P[k1]):
if pi[i]<pi[j] then
 co:=co+1:
fi:
od:
co:
end:

#Tour(P): inputs a voting profile and outputs the torunament
#M[i,j]=1 if i beat j otherwise -1, M[i,i]=0
Tour:=proc(P) local n,T,i,j:
n:=nops(P[1]):
for i from 1 to n  do
T[i,i]:=0:
od:

for i from 1 to n do
 for j from i+1 to n do
 if Cij(P,i,j)>Cij(P,j,i) then
  T[i,j]:=1:
   T[j,i]:=-1:
   else
  T[i,j]:=-1:
  T[j,i]:=1:
 fi:
od:
od:
[seq([seq(T[i,j],j=1..n)],i=1..n)]:
end:

#SV(T): inputs a tournament (as a list of lists) with n players
#n=nops(T), and outputs the vector V[i]: how many other candiates did
#candidate i beat
 SV:=proc(T) local n, S,i,j:
n:=nops(T):

for i from 1 to n do
 S[i]:=0:
od:

for i from 1 to n do
 for j from i+1 to n do
   if T[i][j]=1 then
    S[i]:=S[i]+1:
    elif T[i][j]=0 then
      S[i]:=S[i]+1/2:
       S[j]:=S[j]+1/2:
    else
     S[j]:=S[j]+1:
    fi:
od:
od:

[seq(S[i],i=1..n)]:
    
end: