# Please do not post
# Daniela Elizondo
# March 27, 2022
# Assignment 16

read "C16.txt":

##### Problem 2 #####
# IsCondorcet(P): inputs a voting profile and and outputs true iff P is an instance of the Condorcet paradox

IsCondorcet := proc(P) local v,n,i:
v := nops(P): # number of voters
n := nops(P[1]): # number of candidates
not member(SV(Tour(P)), permute([seq(i, i=0..n-1)])):
end:

##### Problem 3 #####
# ExactCond(n,v): inputs positive integers n and v and outputs the ratio of voting profiles that are Condorcet
ExactCond := proc(n,v) local count, profile:
count := 0:
for profile in RP(n,v) do
    if IsCondorcet(profile) then count += 1: fi:
    od:
count/(n!^v):
end:

##### Problem 4 #####
# EstCond(n,v,K): inputs a large positive integer K, and integers n and v.
# Generates K random voting profiles with v votes and n candidates. Returns the ratio of those profiles that are Condorcet

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

# We'll check EstCond(n,v,K) against ExactCond(n,v) for n=3 and v=3,4,5.

#for v from 3 to 5 do:
#    print(EstCond(3,v,10000)-evalf(ExactCond(3,v)));
#    od:

# The output of this is below, which shows that EstCond is a good estimate for ExactCond.
# 0.00094444444

# 0.00275555556

# 0.00025555556

# Now we check the following:

#for n from 3 to 5 do:
#    for v from 20 by 10 to 40 do:
#        print(EstCond(n,v,10000));
#        od:
#    od:

# The output of this is below.

# 0.08120000000

# 0.08270000000

# 0.09170000000

#  0.2579000000

#  0.2549000000

#  0.2588000000

#  0.4512000000

#  0.4554000000

#  0.4685000000

# Changes in the number of voters does not greatly affect whether a voting profile is Condorcet.
# Small changes in the number of candidates affects the probability that a voting profile is Condorcet. 
# Profiles are most likely to be Condorcet with n=3.

##### Problem 5 #####
# Borda(P): inputs a voting profile P and returns the Borda score of the candidates
Borda := proc(P) local n, i, score, ballot, rankings:
n := nops(P[1]): # number of candidates

# initialize scores
for i from 1 to n do
    score[i] := 0:
    od:

# update scores based on ballots
for ballot in P do
    rankings := inv(ballot):
    for i from 1 to n do
        score[i] += n - rankings[i] + 1:
    od:
od:

# return Borda scores as a list
[seq(score[i], i=1..n)]:
end:

##### Helper functions for Problems 6 and 7 #####

# AllMaxIndices(L): Given a list of numbers, L, returns a set containing the indices at which L attains its maximum

AllMaxIndices := proc(L) local S, n, maxL, i:
S := {}:
n := nops(L):
maxL := max(L):

for i from 1 to n do:
    if L[i] = maxL then 
        S := S union {i}: 
    fi:
    od:
S:
end:

# SortInOrder(L): Given a list of nonnegative numbers L, returns a list of sets M where L[M[1,i]] is constant for all i and L[M[1,i]]>L[M[2,i]]

SortInOrder := proc(L) local maxIndices, copyList, n, i:
maxIndices := AllMaxIndices(L):
copyList := L: # copy of L that we are allowed to edit

# count elements of L that still need to be sorted
n := 0:
for i from 1 to nops(L) do
    if L[i] >= 0 then n += 1: fi:
    od:

# if all sorted, done. else, recurse
if nops(maxIndices) = n then
    return [maxIndices]:
else:
    for i in maxIndices do:
        copyList[i] := -1: # removes these indices from the running
    od:
    return [maxIndices, op(SortInOrder(copyList))]:
fi:
end:

##### Problem 6 #####

# CondorcetRank(P): inputs a voting profile P and outputs the ranking according to the Condorcet criterion

CondorcetRank := proc(P) local pairwise:
pairwise := SV(Tour(P)):
SortInOrder(pairwise):
end:

##### Problem 7 #####
# BordaRank(P): inputs a voting profile P and outputs the ranking according to the Borda criterion

BordaRank := proc(P) local scores:
scores := Borda(P):
SortInOrder(scores):
end: