COMP 3200 - Intro to Artificial Intelligence - Lecture 11 - Voting Algorithms

Overview

Dave Churchill frames voting as preference aggregation: a defined ballot and counting rule turn individual preferences into a shared outcome, and changing the rule can change who wins. He compares first-past-the-post, runoff and instant-runoff voting, Borda scoring, Condorcet, approval voting, and single transferable vote, illustrating trade-offs such as spoiler effects, cycling preferences, and gerrymandering; Arrow’s impossibility theorem shows that no ranked-choice system satisfies all five of his criteria at once. The examples connect electoral methods to AI and computing applications such as multi-agent coordination, recommender systems, and search ranking.

Key takeaways

First-past-the-post counts only first choices, so adding a similar candidate can split support and let a candidate opposed by most voters win.
Instant-runoff voting transfers ballots from eliminated candidates to later preferences, avoiding repeat elections but allowing non-monotonic outcomes where stronger initial support can sometimes hurt a candidate.
The Borda method scores ranks, awarding 3, 2, 1, and 0 points for four candidates; positional scoring captures more preferences than plurality but can encourage strategic rankings.
Condorcet voting seeks a candidate who defeats every opponent head-to-head, but cyclic preferences such as burgers over pizza, pizza over sushi, and sushi over burgers can leave no such winner.
Arrow’s impossibility theorem establishes that no ranked-choice method can simultaneously satisfy unanimity, independence from irrelevant alternatives, individual sovereignty, consistent group ranking, and non-dictatorship.
Voting-method trade-offs apply beyond elections: multi-agent systems, recommender engines, search rankings, and AI answer rankings all aggregate preferences or competing options.

Chapters

0:00 Voting as Preference Aggregation in Society and Computing

Voting combines individual preferences over shared options into a collective decision, such as choosing a leader, food, or algorithm.
Dave Churchill connects elections to distributed systems, multi-agent decision-making, and recommender systems, where agents also need to coordinate on shared outcomes.
Ballots can ask voters to select one candidate, approve several, rank candidates, or assign numerical scores.
Election outcomes may be a single winner, multiple winners, or a complete candidate ranking, as in a professor search committee.

10:10 Voting-System Criteria and Ballot Information Types

Churchill identifies fairness, simplicity, expressiveness, resistance to manipulation, and computability as design considerations.
A voting method combines two choices: how much preference information a ballot records and how that information is aggregated.
The lecture distinguishes single-choice plurality, ranked or partial preferences, approval, score-based, positional-score, Condorcet, and proportional systems.
Churchill defines plurality as the highest vote count and majority as more than 50 percent.

17:05 First-Past-the-Post: Simple Counting, Limited Expression

First-past-the-post gives each voter one vote, and the candidate with the most votes wins without needing more than 50 percent.
Counting is linear in the number of ballots, and the single-mark ballot is easy to understand and tabulate.
Because voters can name only one choice, the method discards their preferences among all other candidates.
Churchill highlights minority rule: a candidate can win even when most voters selected someone else.

21:49 The Pizza Example Demonstrates the Spoiler Effect

In Churchill’s food-party example, pepperoni pizza initially beats hamburgers with 60 percent to 40 percent.
Adding Hawaiian pizza splits support between two similar pizza options, allowing hamburgers to win even though more than half preferred some kind of pizza.
The spoiler effect occurs when a new, similar candidate divides votes and changes the winner under single-choice plurality.
The underlying limitation is that voters cannot indicate a second preference for use if their first choice loses.

27:30 Spoiler Effects in U.S. and Canadian Elections

Churchill uses the 2000 Florida contest between George W. Bush and Al Gore, alongside Ralph Nader’s candidacy, to illustrate how a third-party candidate may affect a close plurality result.
He relates vote splitting among Canada’s Liberal and NDP parties to the possibility of an advantage for a Conservative candidate under first-past-the-post.
Duverger’s Law is introduced to explain how plurality incentives tend to favor two-party competition and discourage voters from supporting less-established parties.
Strategic voting, including the slogan “Anything But Conservative,” describes voting for a viable alternative rather than one’s genuine first choice.

36:50 Runoff Elections Require Majority Support

A runoff first holds a conventional election and declares a winner only if a candidate receives more than 50 percent.
If no candidate reaches that threshold, the lowest-ranked candidate is removed and voters cast another ballot.
In the food example, eliminating Hawaiian pizza lets its supporters choose again, potentially giving pepperoni pizza a majority.
Runoffs reduce the spoiler effect but require voters and administrators to conduct and count multiple elections.

39:48 Instant-Runoff Voting Uses Ranked Ballots

Ranked-choice ballots record candidates in preference order, so an eliminated first choice can transfer to the voter’s next available choice.
Instant-runoff voting, or IRV, repeatedly eliminates the candidate with the fewest first-choice votes until someone exceeds 50 percent.
The ballot simulates multiple runoff rounds without requiring voters to return for another election.
Churchill distinguishes ranked-choice voting as a broad ballot category from IRV as one specific way to count ranked ballots.

43:06 Ranked-Choice Voting Can Reward a Weak First Round

In a burgers, pizza, and sushi example, changing first-round support can alter which candidate is eliminated and redirect later preferences.
A candidate with fewer initial first-choice votes can benefit when a different candidate is eliminated first and their supporters’ rankings transfer.
This non-monotonic behavior means that improving a candidate’s position in one round can sometimes hurt their eventual result.
The example shows that eliminating the spoiler effect does not make IRV immune to counterintuitive outcomes.

45:52 Borda Count and Positional Scoring

Positional voting assigns points according to ballot rank and elects the candidate with the highest summed score.
In the Borda method with four candidates, rankings earn 3, 2, 1, and 0 points from first to fourth place.
Mario Kart 64 awards 9, 6, 3, and 1 points for its top four finishing positions, illustrating ranking-based scoring outside elections.
Arbitrary score systems can invite strategic ratings; Churchill compares this issue to extreme one-star or five-star Amazon and Uber reviews.

49:25 Condorcet Pairwise Elections and the Rock-Paper-Scissors Cycle

A Condorcet winner defeats every other candidate in a head-to-head comparison; ranked ballots can supply preferences for all those comparisons.
The Condorcet paradox occurs when preferences cycle, like rock-paper-scissors, so no candidate beats every other candidate.
Churchill’s example has burgers defeating pizza, pizza defeating sushi, and sushi defeating burgers.
He relates this cycle to a StarCraft AI competition where bots’ head-to-head results formed a cycle despite an overall win-rate ranking.

53:40 Arrow’s Five Criteria and Impossibility Theorem

Kenneth Arrow’s criteria include unanimity, freedom from irrelevant alternatives, individual sovereignty, a consistent group ranking, and non-dictatorship.
Freedom from irrelevant alternatives requires that removing an option not change the relative ranking of the remaining options.
Arrow’s impossibility theorem proves that no ranked-choice system can satisfy all five criteria simultaneously.
The result means voting-system design requires choosing which desirable properties to prioritize rather than expecting a perfect method.

57:18 Approval Voting Counts Acceptable Candidates

In approval voting, each voter marks every candidate they consider acceptable, and the candidate with the most approvals wins.
A voter can approve multiple candidates without ranking them, making the ballot simpler than a full ranked list.
Churchill describes approval voting as especially intuitive for multi-winner elections, such as selecting up to six members from 19 town-council candidates.
Approval voting preserves more information than a single-choice ballot but loses the distinction between a voter’s first and later approved choices.

1:00:41 Gerrymandering, Single Transferable Vote, and AI Applications

Gerrymandering manipulates electoral district boundaries to change outcomes; Churchill’s 10-house example shows how the same voters can yield different winners under different district maps.
First-past-the-post districts are especially vulnerable: dividing three cheetahs, four owls, and three gorillas into two districts can produce two non-owl winners despite owls having the largest overall group.
Single transferable vote is a ranked-ballot method for electing multiple winners and can improve representation while reducing vulnerability to gerrymandering.
Churchill connects preference aggregation and manipulation to AI systems, including search rankings, recommender systems, and attempts to influence which websites appear in ChatGPT results.

Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, Dave Churchill.