# OK to post homework
# Vikrant, Mar 27 2022, Assignment 16

# ================================================================================
# 0. Code that has been given.
# ================================================================================

read("C16.txt"):

# ================================================================================
# 1. Read Yu's Proof of Arrow's Theorem.
# ================================================================================

# Done.

# ================================================================================
# 2. Condorcet check.
# ================================================================================

IsCondorcet:=
    proc(P)
        local s:
        evalb(nops({seq(s,s in SV(Tour(P)))}) < nops(P[1])):
    end:

# ================================================================================
# 3. Exact ratio of condorcet profiles.
# ================================================================================

ExactCond:=
    proc(n,v)
        local P:
        nops([seq(`if`(IsCondorcet(P),1,NULL),P in RP(n,v))])/(n!^v):
    end:

# ================================================================================
# 4. Estimate ratio of condorcet profiles.
# ================================================================================

EstCond:=
    proc(n,v,K)
        local i:
        evalf(nops([seq(`if`(IsCondorcet(RandP(n,v)),1,NULL),i=1..K)])/K):
    end:

(*

randomize(2056897454):

n:= 3:
for v from 3 to 5 do
    print(abs(EstCond(n,v,10^5)-ExactCond(n,v)));
od:

# 0.00036444444
# 0.00003444444
# 0.00072444444

*)

(*

randomize(717078617):

for n from 3 to 5 do
    for v in [20,30,40] do
        print(n,v,EstCond(n,v,10^5));
    od:
od:

# 3, 20, 0.08286000000
# ...
# 4, 20, 0.2511200000
# ...
# 5, 20, 0.4590000000
# ...

*)

# ================================================================================
# 5. Borda count.
# ================================================================================

Borda:=
    proc(P)
        local v:
        add([(1+nops(P[v]))$nops(P[v])]-inv(P[v]),v=1..nops(P)):
    end:

# ================================================================================
# 6. Condorcet rank.
# ================================================================================

Rank:=
    proc(range,score)
        local i,S:
        local Ss:= [{}$(range+2)]:
        for i from 1 to nops(score) do
            Ss[-score[i]-1]:= Ss[-score[i]-1] union {i}:
        od:
        [seq(`if`(S<>{},S,NULL),S in Ss)]:
    end:

CondorcetRank:=
    proc(P)
        Rank(nops(P[1]),SV(Tour(P))):
    end:

# ================================================================================
# 7. Borda rank.
# ================================================================================

BordaRank:=
    proc(P)
        Rank(nops(P)*nops(P[1]),Borda(P)):
    end: