20 Elections
An election involves a group of individuals, commonly referred to as voters, who must make a collective decision regarding a set of alternatives, typically known as candidates. The form of this collective decision can vary. It might result in a single winner, a tie among several candidates, a ranking of all candidates, the selection of a committee, or some other outcome.
For the purposes of this course, unless stated otherwise, we will concentrate on single-winner elections. So, the group decision is either a single winner or a set of candidates that are tied for the win. Examples of such elections range from large-scale political events, like the election of a president, to smaller-scale decisions, such as choosing the president of a club or a group of friends deciding where to have dinner.
20.1 Ranked Ballots
In an election, each voter submits a ballot that is meant to express their preferences among the candidates.
In a ranked ballot, voters are asked to rank the candidates in order of preference. Below is an example of a ranked ballot used in the 2019 election for the Mayor of San Francisco:
The ranking provided by the voter can be described as a linear order over the set of candidates. A linear order is a relation \(P\) that is asymmetric and transitive over the set of candidates, \(\{Zhou, Breed, Ventresca, Pang, Jordan, Robertson\}\). In the case of the above ballot, the linear order is:
\[Zhou \mathrel{P} Robertson \mathrel{P} Breed \mathrel{P} Pang \mathrel{P}Ventresca\mathrel{P}Jordan.\]
In this formalization, \(Zhou \mathrel{P} Robertson\) indicates that the voter ranked \(Zhou\) over \(Robertson\). This is visible on the ballot, as \(Zhou\) is marked as the “1st Choice” and \(Robertson\) as the “2nd Choice.” Similarly, we have that \(Zhou \mathrel{P} Breed\) since \(Zhou\) was marked “1st Choice” while \(Breed\) was marked “3rd Choice”.
We will often display this ranking of the candidates by listing the candidates from top to bottom in the order of the voter’s preference. For example, the above ranking can be displayed as:
\[\begin{array}{c} Zhou\\ Robertson\\ Breed\\ Pang\\ Ventresca\\ Jordan \end{array}\]In this course, we will primarily focus on ranked ballots and the various methods used to determine the winner(s) when voters submit ranked ballots. To conclude this section, it is important to clarify the terminology used when discussing voters’ rankings. Consider the following example of two voters, Voter 1 and Voter 2, who have different rankings of the candidates (with \(Zhou\) and \(Ventresca\) highlighted):
\[\begin{array}{cc} Voter 1 & Voter 2\\\hline \cellcolor{blue}{\textcolor{white}{Zhou}} & Pang\\ Robertson & Breed\\ Breed & \cellcolor{blue}{\textcolor{white}{Zhou}}\\ Pang & \cellcolor{red}{\textcolor{white}{Ventresca}}\\ \cellcolor{red}{\textcolor{white}{Ventresca}} & Jordan\\ Jordan & Robertson \end{array}\]There are two ways to describe the rankings of \(Zhou\) and \(Ventresca\) by these voters:
- Voter 1 and Voter 2 rank \(Zhou\) and \(Ventresca\) the same way: Both voters rank \(Zhou\) above \(Ventresca\).
- Voter 1 and Voter 2 rank \(Zhou\) and \(Ventresca\) in different positions: Voter 1 ranks \(Zhou\) in 1st place, while Voter 2 ranks \(Zhou\) in 3rd place. Voter 1 ranks \(Ventresca\) in 5th place, while Voter 2 ranks \(Ventresca\) in 4th place.
In many real-world elections, voters are not required to rank all candidates, and they may even rank two candidates equally, indicating a tie between them. However, for simplicity, we will focus on elections where voters rank all candidates and do not allow ties.
20.2 (Anonymous) Profiles
Suppose that \(V\) is the set of voters and \(X\) is the set of candidates. Let \(L(X)\) denote the set of all rankings over \(X\), i.e., the set of all linear orders on \(X\). A profile is a description of an election that specifies the (ranked) ballot submitted by each voter.
Definition 20.1 (Profile) A profile for the pair \((V, X)\) is a function \(\mathbf{P}: V \to L(X)\), which assigns to each voter \(i \in V\) a ranking \(\mathbf{P}(i) \in L(X)\). We denote the ranking of voter \(i\) in profile \(\mathbf{P}\) by \(\mathbf{P}_i\), and we use \(a \mathrel{\mathbf{P}_i} b\) to indicate that voter \(i\) ranks candidate \(a\) above candidate \(b\) in profile \(\mathbf{P}\).
For example, suppose that \(V = \{v_1, v_2, v_3, v_4, v_5\}\) and \(X = \{a, b, c, d\}\). Let \(\mathbf{P}\) be a profile for the pair \((V, X)\), depicted in the following table:
\[\begin{array}{ccccc} v_1 & v_2 & v_3 & v_4 & v_5\\\hline a & c & c & a & a\\ b & d & d & b & b\\ c & a & a & c & d\\ d & b & b & d & c\\ \end{array}\]We note the following about the rankings in profile \(\mathbf{P}\):
- \(v_1\) and \(v_4\) submitted the same ranking: \(a\) is ranked first, followed by \(b\), then \(c\), and finally \(d.\)
- \(v_2\) and \(v_3\) submitted the same ranking: \(c\) is ranked first, followed by \(d\), then \(a\), and finally \(b.\)
- \(v_1\), \(v_4\), and \(v_5\) all rank \(a\) above \(c.\) That is, \(a \mathrel{\mathbf{P}_{v_1}} c\), \(a \mathrel{\mathbf{P}_{v_4}} c\), and \(a \mathrel{\mathbf{P}_{v_5}} c.\)
- \(v_2\) and \(v_3\) both rank \(c\) above \(a.\) That is, \(c \mathrel{\mathbf{P}_{v_2}} a\) and \(c \mathrel{\mathbf{P}_{v_3}} a.\)
- all voters rank \(a\) above \(b\). That is, for all \(i\in V\), \(a \mathrel{\mathbf{P}_i} b.\)
In most elections, we are primarily concerned with how many voters submitted a particular ranking, rather than the identities of the voters who submitted it. When we only list the number of voters associated with each ranking, we refer to this as an anonymous profile. For example, the profile \(\mathbf{P}\) above can be represented as an anonymous profile as follows:
\[\begin{array}{ccc} 2 & 2 & 1\\\hline a & c & a\\ b & d & b\\ c & a & d\\ d & b & c\\ \end{array}\]20.3 Exercises
- Suppose that \(V = \{v_1, v_2, v_3\}\) and \(X = \{a, b, c\}\). Let \(\mathbf{P}\) be a profile for the pair \((V, X)\), depicted in the following table:
What is the anonymous profile associated with \(\mathbf{P}\)?