Rank Aggregation Flashcards
Fairness parts
Anonymity
Neutrality
Monotonicity
Anonymity
Voting system treats all voters equally
Neutrality
Voting system treats candidates the same
Monotonicity
Impossible for winning candidate to become a losing candidate by gaining votes
May’s Theorem
Among all possible two-candidate voting systems that never result in a tie, majority rule is the only one that is anonymous, neutral and monotone
Condorcet Winner
Defeats every other candidate in a 1v1 with majority rule
Doesn’t always exist
Condorcet criterion
If condorcet winner exists, they should be top in the aggregate ranking
Issues with manipulation
Election results don’t reflect the true will of society
Aggregation rules designed with social welfare criteria in mind.
Borda Count Method
0 for lowest ranked candidate
n-1 for highest candidate
Sum of all scores for each candidate
Borda Count Properties
Monotonicity
Doesn’t satisfy Independence of irrelevant alternatives
Doesn’t satisfy the condorcet criterion
Independence of irrelevant authorities
Social preferences between candidates A and B depend only on the individual preferences between A and B
Black’s Rule
Select condorcet if exists
Otherwise use borda count
Copeland’s Method
Pairwise victories minus pairwise losses
Candidates ranked according to score
Condorcet consistent
Arrow’s Impossibility Theorem
With 3 or more candidates and any number of voters, there doesn’t exist (and will never exist) voting system with
Unanimity
Independence of irrelevant alternatives
Non-dictatorship
Unanimity
If every voter prefers alternative A over alternative B, then the group prefers A over B
Other impossibility results
Gibbard-Satterthwaite
Every non-dictatorial aggregation rule with >=3 candidates is manipulable
Spearman’s footrule
Sum of displacements
Kendall-tau distance
Number of pairwise disagreements between two rankings
Computational complexity for optimal
Spearman’s footrule - Polynomial time with hungarian algorithm
Kendall-tau (Kenemy Rule) - NP-hard
