Menu:
ECE 594BB Course Page for Fall 2024
Mathematical, Algorithmic, and Engineering Aspects of Democratic Elections
Page last updated on 2024 December 16
Enrollment code: 14043
Prerequisite: Graduate standing in computer engineering
Class meetings: MW 2:00-3:15, Phelps 1431
Instructor: Professor Behrooz Parhami
Open office hours: MW 3:15-3:45 PM, Phelps 1431
Course announcements: Listed in reverse chronological order
Course calendar: Schedule of lectures, with pertinent links
Homework assignments: Four assignments, 40% of the grade
Exams: None for fall 2024
Research paper: Different topic for each student, worth 60%
Research paper guidlines: Brief guide to format and contents
Policy on academic integrity: Please read very carefully
Grade stats: Grade range, mean, etc. for each activity
References: Information sources for the course
Miscellaneous information: Motivation, catalog entry, history
This seminar has been described in a UCSB Current article.
Course Announcements
2024/12/16: The fall 2024 offering of ECE 594BB is officially over and course grades have been reported to the Registrar. I wish you a happy and relaxing holiday season and hope to see some of you in my upcoming graduate courses during winter (ECE 254B), spring (ECE 252B), and fall (ECE 257A), 2025.
2024/12/02: All lecture slides are now in their final forms.
2024/11/28: Solutions to HW4 have been posted to the homework area below.
2024/11/17: The complete HW4 has now been posted to the homework area below.
2024/11/14: Solutions to HW3 have been posted to the homework area below. HW4, the last one for the course, will appear in a couple of days.
2024/11/01: Solutions to HW2 have been posted to the homework area below. Also, 4 of the HW3 problems have been posted to give you a head start. The remaining 3 problems will appear shortly.
2024/10/30: I just uploaded the updated slides for today's lecture. There are quite a few slides that did not appear in the version I screened in class. The incomplete slides have also been completed. My apologies. I am working on HW3 and should be able to post it by Saturday 11/02, a couple of days ahead of schedule.
2024/10/21: Please see the addendum to Problem 1's solution in HW1.
2024/10/19: HW2 has been posted to the homework area below a couple of days ahead of schedule.
2024/10/17: HW1 solutions have been posted to the homework area below.
2024/10/15: Students who will be submitting their research topic preferences over the next few days please pay attention to the 13 topics that have arleady been taken.
2024/10/04: HW1 has been posted to the homework area below. Please pay attention to the submission instructions.
2024/09/30: I look forward to teaching the first class and meeting the 21 enrolled students today. My office hours will be held immediatly after each class session in the same classroom.
2024/05/09: Welcome to the ECE 594BB Web page for fall 2024. This is a new graduate seminar being offered for the first time during fall 2024. I will be designing the course material and lectures during the summer of 2024 and will update this page periodically as I make progress. Please stay tuned.
[Please report any broken hyperlinks and other problems on this page to the instructor.]
Course Calendar
Course lectures, homework assignments, and research milestones have been scheduled as follows. Lecture titles are tentative and may change as I work on them. PowerPoint presentations used in my lectures will be converted to PDF files and posted under References near the end of this page. Given that slides will be updated throughout the quarter, please pay attention to the date of last update, indicated next to the links.
Day & Date Lecture/discussion topic [Homework posted/due] {Special notes}
M 09/30 Introduction to the course and its requirements (Lecture 1)
W 10/02 Voting, data fusion, social choice, research projects (Lecture 2) {Research topics announced}
M 10/07 Direct elections: One-person-one-vote and weighted voting (Lecture 3) [HW1 posted]
W 10/09 Indirect elections: Electoral College and parliamentary systems (Lecture 4)
M 10/14 Complications in voting when there are 3 or more candidates (Lecture 5) {Research prefernces due}
W 10/16 An impossibility result: Arrow's Theorem and its implications (Lecture 6) [HW1 due]
M 10/21 Voting schemes: Basic properties (Lecture 7) [HW2 posted] {Research topics assigned}
W 10/23 Voting schemes: Complexity, practicality, fairness (Lecture 8)
M 10/28 Vote-splitting, spoiler candidates, and how to handle them (Lecture 9)
W 10/30 Election interference and mis-/dis-information (Lecture 10) [HW2 due]
M 11/04 Districting: Advantages, fairness, and social justice (Lecture 11) [HW3 posted]
T 11/05 US Election Day
W 11/06 Districting: The serious problem of Gerrymandering (Lecture 12) {Preliminary references due}
M 11/11 Veterans' Day Holiday, no lecture/class
W 11/13 No class/lecture (research focus week) [HW3 due]
M 11/18 Election technology: Hardware & software (Lecture 13) [HW4 posted]
W 11/20 Election technology: Oversight & certification (Lecture 14)
M 11/25 Summary & conclusions: Voting schemes compared (Lecture 15) {Abstract & final references due}
W 11/27 No class/lecture on Thanksgiving Eve [HW4 due]
M 12/02 The road ahead: Areas in need of action and further study (Lecture 16)
W 12/04 No class/lecture (research focus week)
W 12/11 Research paper due by midnight
W 12/18 Course grades due by midnight
Homework Assignments
- Turn in your solutions as a PDF file attached to an e-mail sent by the due date/time.
- Because solutions will be handed out on the due date, no extension can be granted.
- Include your name, course name, and assignment number at the top of the first page.
- If homework is handwritten and scanned, make sure that the PDF is clean and legible.
- Although some cooperation is permitted, direct copying will have severe consequences.
Homework 1: Lectures 1-4 (due W 2024/10/16, at any time)
Problem 1: Nonuniform voting schemes The United Nations Security Council consists of five permanent members and 10 nonpermanent members that serve two-year terms. For a resolution to be approved by the Council, all five permanent members and at least four nonpermanent members must agree. Can this decision scheme be formulated as weighted voting? How, or why not?
Problem 1 solution Assume that the approval process is in fact a weighted voting scheme with weights x and 1 for permanent and nonpermanent members, respectively. If the threshold is T, we must have 5x + 4 ≥ T and 4x + 10 < T. The two inequalities lead to x > 6. We can easily verify that x = 7 and T = 39 satisfy the requirements.
Problem 1 solution addendum It was brought to my attention that the UN Security Council's voting process requires at least 9 positive votes. The normal outcome in most cases is "pass," with 5 positive votes from permanent members and 4 positive votes from non-permanent members, or "fail," with a negative vote (veto) from a permanent member. However, the rules provide for the case that a permanent member abstains in discussing a conflict involving that permanent member as one of the sides. In such a case, 4 permanent members and 5 non-permanent members can pass a resolution. Although extremely rare, more than one permanent member may abstain, in which case support from an equivalent additional number of non-permanent members will be needed. With these additional provisions, weighted voting will not work, except if we modify the voting process to define a positive vote by a permanent member being worth 7 points and an abstention being worth 6 points.
Problem 2: Generalized and weighted voting A generalized voting scheme can be specified by listing its agreement sets. For example, simple 2-out-of-3 majority voting with participants V1, V2, and V3 has the agreement sets {V1, V2}, {V2, V3}, {V3, V1}. Show that each of the agreement sets below corresponds to a weighted threshold voting scheme.
a. {V1, V2}, {V1, V3}, {V1, V4}, {V2, V3, V4}
b. {V1, V2}, {V1, V3, V4}, {V2, V3, V4}
c. {V1, V2, V3}, {V1, V3, V4}, {V2, V3, V4}
d. {V1, V2}, {V1, V3, V4}, {V2, V4}
Problem 2 answers The weights and the threshold T for weighted voting are given below.
a. W1 = 2, W2 = W3 = W4 = 1, T = 3
b. W1 = W2 = 2, W3 = W4 = 1, T = 4
c. W1 = W2 = 1, W3 = 2, W4 = 1, T = 4
d. W1 = 2, W2 = 3, W3 = 1, W4 = 2, T = 5
Problem 3: Generalized and weighted voting Is there any generalized voting scheme (see Problem 2) on 4 inputs that cannot be realized as a weighted threshold voting scheme? Fully justify your answer.
Problem 3 solution Yes, there are quite a few. Here is an example:
The agreement sets {V1, V2}, {V3, V4}, {V1, V3} cannot be realized by a weighted voting scheme. This is because the requirements W1 + W2 ≥ T and W2 + W3 < T imply W1 > W3, while W3 + W4 ≥ T and W1 + W4 < T lead to the contradictory requirement W1 < W3.
Problem 4: Majority rule for data fusion When raw data coming from multiple sources are viewed as exact, ordinary majority voting can be used to obtain the fused result. For example, if 5 sensors classify an incoming plane as one of {Bomber, Figther, Passenger}, then 3-out-of-5 agreement can be taken as reliable evidence of the plane's type. Now, consider that 5 sensors provide the estimated distance of the incoming plane, with the raw data, in kilometers, being {12.5, 14.0, 12.6, 11.0, 12.4}. Discuss how the majority rule can be interpreted in this context to obtain an appropriate fused result.
Problem 4 solution One way would be to use an approximate majority voting scheme, where values that differ by less than a small threshold are viewed as being in agreement. In this example, if the threshold is set to 0.2, we have a majority of compatible values and one of them (usually the median value) can be viewed as being in the majority. Another approach is to take the median of all five values, which would yield 12.5 as the output here. This is known as median voting, which does a good job of discarding extreme values on both ends but isn't a majority voting scheme.
Problem 5: Proportional representation Answer the following questions for US elections.
a. What is the range of population per House district across the US?
b. What is the range of population per Electoral College district across the US?
c. Which one of the two schemes above is closer to the one-person-one-vote ideal?
Problem 5 solution The answer would vary, depending on whether you use population data from the 2020 census or estimates for a more recent year based on extrapolation. In the following, I use the 2020 census data.
a. Smallest (Wyoming) 576,651/1 = 576,651; Largest (Texas) 29,145,505/38 = 766,987
b. Smallest (Wyoming) 576,651/3 = 192,217; Largest (Texas) 29,145,505/40 = 728,638
c. With a largest-to-smallest ratio of 1.33, House districts are closer to proportional representation than Electoral College votes, which have a ratio of 4.00.
Problem 6: Proportional representation Answer the following questions for US elections.
a. What is the range of population in the districts that elect Representatives to Congress?
b. What is the range of population represented by each Senate seat?
c. What is the smallest possible fraction of the US population corresponding to 51 votes in the Senate?
Problem 6 solution
a. Smallest (Wyoming) 576,651/1 = 576,651; Largest (Texas) 29,145,505/38 = 766,987
b. Smallest (Wyoming) 576,651/2 = 288,326; Largest (California) 39,538,223/2 = 19,769,112
c. We can find this by taking the 25 states with the smallest populations and adding half the population of the next larger state. It is easier if we add percentages representing state populations relative to the total US population, as provided on this Wikipedia page.
0.172 + 0.192 + 0.219 + 0.233 + 0.265 + 0.295 + 0.328 + 0.324 + 0.407 + 0.411 +
0.434 + 0.535 + 0.549 + 0.585 + 0.632 + 0.884 + 0.877 + 0.899 + 0.927 + 0.952 +
0.976 + 1.076 + 1.182 + 1.265 + 1.345 + 1.390/2 = 16.659% (~1/6 of the US population)
Problem 7: Mini-research assignment Look up May's Theorem and describe it in one typeset page (double-spacing okay).
Problem 7 solution summary May's Theorem is referred to as a possibility result for 2 candidates, in contrast to Arrow's impossibility result for 3 or more candidates. May's Theorem states that with 2 candidates, majority voting is the unique voting scheme satisfying the following 3 axioms.
Anonymity: All voters are treated identically.
Neutrality: All candidates are treated identically.
Monotonicity: Voters changing their preference to candidate Ci cannot turn Ci from a winner to a loser.
Homework 2: Lectures 5-8 (due W 2024/10/30, at any time)
Problem 1: Influential coalitions A coalition is a set of voters. Given a social choice function, a coalition is deemed influential if whenever every voter in the coalition places a candidate in first place, that candidate becomes the unique winner.
a. What are influential coalitions of the plurality method?
b. What are influential coalitions in a dictatorship?
c. Given 10 voters and 4 candidates, characterize influential coalitions of the Borda count method.
Problem 1 solution
a. Influential coalitions are those consisting of more than half the voters.
b. Influential coalitions are those containing the dictator.
c. Influential coalitions are those that contain 8 or more voters. If 8 voters place candidate A in first place s/he will earn at least 24 points. For any other candidate, the maximum number of points would be 22 (2 x 3 for first-place votes + 8 x 2 for second-place votes). A coalition of 7 will give 21 points to candidate A, while another candidate might earn 23 points (3 x 3 + 7 x 2).
Problem 2: Arrow's Impossibility Theorem In the proof of Arrow's Impossibility Theorem given on the lecture slides, we began with four axioms. The proof provided in the Veratissium video, in accordance with Arrow's own proof, refers to five axioms. Can you explain the discrepancy?
Problem 2 solution Our first two axioms are identical to the first two conditions in the video. Our last axiom A4 is identical to the video’s last condition. Our universality axiom A3 is the same as what in the video is called “unrestricted domain” (with an added decisiveness condition, that we did not state explicitly). So, in mathematical terms, the social choice function must be a total function that returns a value for every possible set of inputs. The video includes transitivity as a separate condition. Transitivity is in fact not a condition for the social choice function but a restriction on its inputs.
Problem 3: Condorcet ballots A Condorcet ballot with n candidates contains n(n – 1)/2 two-way races, with each voter indicating his/her preferred candidate in each race among the two options listed.
a. Does a Condorcet ballot supply the same information as a ranked-choice ballot?
b. Show that it is possible for voters to specify circular preferences on a Condorcet ballot.
c. How should we conduct a Condorcet-style election to avoid the problem in Part b?
Problem 3 solution
a. A ranked-choice ballot can provide all the information on a Condorcet ballot, but not vice versa. There is no way to deduce from vote tallies of a Condorcet ballot the number of first-place votes for a candidate. In other words, a Condorcet tally may be consistent with multiple ranked-choice profiles.
b. Here is a simple example with 3 candidates and 3 voters: A vs. B, 3-0; B vs. C, 2-1; C vs. A, 3-0. Because all three voters prefer C to A and A to B, all must prefer C to B by transitivity.
c. We should use a ranked-choice ballot, which both avoids circular preferences and gives us all the needed information for Condorcet tallies.
Problem 4: Approval voting With approval voting, we still need a social choice function such as plurality, majority, or 2/3 supermajority to select the winner(s).
a. Which of the three social choice functions named above can lead to multiple winners?
b. What would be a reasonable method of ensuring a single winner?
c. Discuss application contexts where multiple winners would be admissible.
Problem 4 solution
a. All three social choice functions may have as many as m winners when there are m candidates. Practically speaking, however, supermajority is least likely to produce multiple winners.
b. Multiple winners result from tie votes, so we need a tie-breaking rule. Here is a reasonable approach (there may be others). We might give a weight of 1 to an approval vote that includes a single candidate, 1/2 if two candidates are approved, 1/3 if three candidates are approved, and so on. The idea behind this method is that a voter who approves only one candidate likely has a stronger preference than others who approve multiple candidates. Though highly unlikely, this process may still lead to tie votes.
c. One example is in a law firm, where junior partners might vote on which candidates should become full partners.
Problem 5: Condorcet methods Given m candidates, a Condorcet matrix is m x m, with entry in row i, column j indicating the number of voters who prefer candidate i to candidate j in a two-way election. The diagonal entries are all 0s. Any social choice function that uses only information from the Condorcet matrix is a Condorcet method. Prove that the Borda count method is a Condorcet method.
Problem 5 solution It is fairly easy to show that the sum of the entries in the row corresponding to a candidate gives his/her Borda count score. According to stories about Condorcet despising Borda, he was very upset by the discovery that Borda’s method met the requirements of his own method.
Problem 6: Range voting Range voting is a generalized form of approval voting in which the voter can assign a support strength from 0 to 1 to each candidate. The winner is the candidate with the maximum average support. For example, if support strengths from 5 voters are 0.3, 0.5, 0.6, 0.7, and 0.9, the average support strength will be 0.6. Approval voting is the special case when only support strengths 0 and 1 are allowed. An approval ballot can be derived from a range ballot by rounding the support levels to 0 or 1, whichever is closer. Construct an example with 3 candidates A, B, and C such that approval voting ranks the candidates A > B > C, while range voting ranks them C > B > A.
Problem 6 solution Consider the following range-voting profile and the approval-voting profile derived from it.
Range: 3 voters: A 0.6, B 0.4, C 0.3; 2 voters: A 0.0, B 0.6, C 0.4; 1 voter: A 0.0, B 0.2, C 1.0
Approval: 3 voters approve A; 2 voters approve B; 1 voter approves C
Clearly, the range-voting profile leads to the ordering C > B > A, while the approval-voting profile produces A > B > C.
Problem 7: Mini-research assignment Look up mixed approval/preference voting, Describe the method, its advantages, and its drawbacks in one typeset page (double-spacing okay).
Problem 7 solution summary The ballot for mixed approval/preference voting allows a voter to submit both an approval list and a preference list. Even though more information is collected from each voter, there are potential complications. For example, the approval ballot may be inconsistent with the preference ballot. If candidate A is ranked higher than candidate B, then it makes sense that approving B implies also approving A. This problem can be avoided by insisting that a voter approve a number of consecutive candidates at the top of his/her preference list.
Other details can be found in the on-line document “On Two Voting systems that combine approval and preferences: Fallback Voting and Preference Approval Voting,” by Eric Kamwa. [PDF]
Homework 3: Lectures 9-12 (due W 2024/11/13, at any time)
Problem 1: Assessment of vote splitting Three candidates A, B, and C are running for Chair of a company’s Board of Trustees. Fifteen board members submit ranked-choice ballots as follows:
A > B > C (5 voters)
B > A > C (4 voters)
C > B > A (3 voters)
C > A > B (3 voters)
The fairly unpopular candidate C wins the plurality vote. Would you say vote-splitting is responsible for this outcome? Discuss.
Problem 1 solution Judging from their ranked positions, A and B appear to be similar candidates who split 9 of the 15 votes. In head-to-head contests, A would beat B (8-7), and both A and B would beat C (9-6). So, A is the Condorcet winner, but B isn’t far behind. C seems to be a polarizing candidate, who is ranked first or last. Without C, A would win a majority 8 of the 15 votes, so C can be viewed as a spoiler for A.
Problem 2: Spoiler candidate becomes the winner In the 1992 US presidential election, Ross Perot had some devoted voters (19%) and was also preferred to one of the other two candidates, Clinton or Bush, by a substantial number of voters. Can you envisage a scenario where Perot would have ended up winning, if the election were conducted by the Borda method?
Problem 2 solution Consider the following hypothetical profile in which Perot earns 19% of the first-place votes and 66% of the second-place votes.
C > P > B (33% of the voters)
C > B > P (8% of the voters)
B > P > C (33% of the voters)
B > C > P (7% of the voters)
P > C > B (10% of the voters)
P > B > C (9% of the voters)
Plurality voting leads to a Clinton victory 41% to 40% to 19%. Borda voting leads to the following scores, making Perot the winner: C, 41*2 + 17 = 99; B, 40*2 + 17 = 97; P, 19*2 + 66 = 104.
Problem 3: Was Ralph Nader a spoiler? In the 2000 US presidential election in the state of Florida (which ended up being decisive in the national election outcome), there were five candidates: George W. Bush, Al Gore, Ralph Nader, Pat Buchanan, and Harry Browne. Taking vote totals from the Wikipedia page “Ralph Nader 2000 presidential campaign”:
a. Compute the fraction x of Nader voters who would have had to vote for Gore, with the fraction 1 – x voting for Bush, in order to make Gore the winner.
b. Assess the claim that Nader was a spoiler candidate. Make sure you argue based on facts.
c. Discuss the roles played by the other two candidates.
Problem 3 solution Here are the five candidates’ votes from the suggested Wikipedia page:
George W. Bush voters: G = 2,912,790
Al Gore voters: A = 2,912,253
Ralph Nader voters: R = 97,488
Pat Buchanan voters: P = 17,484
Harry Browne voters: H = 16,415
a. A + x*R > G + (1 - x)*R leads to x > (G - A + R)/(2R) = 0.5 + (G - A)/(2R) = 0.50275
b. Nader was a spoiler candidate for sure. The result of part a indicates that had Nader not run, 50.275% of his voters (49,013) would have had to vote for Gore, vs. 49.725% (48,475) for Bush, in order for Gore to win Florida. Of course, some Nader voters may have stayed home if he were not a candidate. Nader voters who would not have stayed home (~68% est.) favored Gore over Bush by more than a 2-to-1 ratio (P. L. Southwell, “Nader Voters in the 2000 Presidential Election: What Would They Have Done Without Him?”).
c. The other two candidates, Pat Buchanan and Harry Browne, were conservatives and drew a lot more votes from Bush than Gore, so they were certainly no spoilers for Gore. Whether they could have been spoilers for Bush in the absence of Nader as a candidate is unclear. They drew a total of 33,899 votes. The Nader analysis in part b suggests that this total could have exceeded the Gore advantage in the absence of Nader.
Problem 4: Dealing with dis-information Listen to this 33-minute podcast or read the transcripts and answer the following questions briefly in your own words.
a. How might AI be used to create convincing disinformation texts by foreign operatives?
b. How do tech company reporting requirements help us fight disinformation?
c. What are the Digital Services Act and Digital Markets Act of the European Union?
Problem 4 solution In the answer to Part c, I went outside the referenced podcast to get detailed information.
a. With help from ChatGPT and similar tools, a prompt can be converted to polished text that is nearly as effective as human-generated disinformation (44% vs. 47% impact, according to one study). Also, hundreds of versions of a disinformation text can be generated and posted to different social-media accounts, making the detection of its origin more difficult.
b. Ideally, the reports contain clues about where disinformation is produced and how it is propagated across a particular platform. However, the submitted reports have not been very effective so far, because they tend to contain boilerplate text for minimal compliance and not much quantitative data.
c. The Digital Services Act and Digital Markets Act of the European Union are described on this Web page. The Digital Services Act has been recently enacted and, among other things, it aims to convert the voluntary code of practice on disinformation, discussed in the podcast, into a mandatory code of conduct.
Problem 5: Jefferson’s apportionment method Consider Jefferson’s apportionment method. The eventual divisor d that leads to a1 + a2 + a3 + . . . + an = h isn’t unique.
a. Why doesn’t this non-uniqueness cause a problem? Use a precise argument.
b. Formulate a binary-search-like process to zoom in on a correct divisor.
Problem 5 solution
a. Let the divisor be d in the next-to-last step, when h - x seats are assigned, and d - b in the final step leading to the assignment of h seats. There exist real values a and c, with a < b < c, such that any divisor in (d - c, d - a] would also lead to the assignment of h seats. To see this, assume that we decrease the divisor from d in infinitesimal steps. At some point one more seat will be assigned. Continuing with the infinitesimal reduction steps, eventually we reach a divisor d - a when x more seats are assigned. Proceeding further with the infinitesimal reductions, eventually the number of assigned seats becomes h + 1 when the divisor reaches d - c. Clearly, any value of the divisor in (d - c, d - a] will assign the same number h of seats in the same proportions.
b. Let the divisor value d lead to the assignment of h - x seats and the divisor value d - e yield h + y seats. Following a binary-search procedure, we next try a divisor that is halfway between d and d - e, that is, d - e/2. Consider three cases: (1) If exactly h seats are assigned, then we are done. (2) if fewer than h seats are assigned, the divisor should be further reduced and we focus on the interval [d - e/2, d - e]. (3) If more than h seats are assigned, the divisor should be increased and the domain of search will become [d - e/2, d]. It is possible to use interpolation search for quicker convergence to an acceptable divisor.
Problem 6: Districting and gerrymandering Consider a hypothetical square-shaped state with 64 equally sized square precincts, holding blue and red voters as shown. The state is to be divided into districts.
a. Show how 4 competitive districts can be formed.
b. Show a packing of blue voters into one district to create 3 red-majority districts.
c. Show a packing of red voters into one district to create 3 blue-majority districts.
d. If we were to switch to 2 districts, with 2 representatives elected from each district, what are some of the options of drawing the dividing line and the advantages and drawbacks of each?
Problem 6 solution
a. Dividing the square-shaped state into four quadrants will do the trick, as it leads to 8 red and 8 blue precincts in each quadrant.
b. The leftmost diagram shows one of many possible solutions. It packs 14 blue precincts with 2 red precincts into one district and leaves the other three districts with 10 red and 6 blue precincts.
c. The middle diagram shows one of many possible solutions. It packs 12 red precincts with 4 blue precincts into the center 4 x 4 square, leaving one 10-6 blue precinct on the right and two 9-7 blue precincts on the left.
d. Dividing the square down the middle, by a horizontal or vertical straight line, produces two competitive 16-16 districts. The rightmost diagram shows an example of packing two 20-12 blue and red districts. The competitive split can lead to 2 blue, 2 red, or 1 + 1 in each district. The packed split is more likely to lead to 2 representatives of the same color in each district.
Problem 7: Mini-research assignment Look up the Gibbard-Satterthwaite theorem. Describe the theorem, its proof, and its implications in one typeset page (double-spacing okay).
Problem 7 solution summary The theorem shows that the only ranked-choice voting scheme that is both unanimous and strategy-proof is a dictatorship. The following paper contains definitions of the terms and a simple proof:
J.-P. Benoit, “The Gibbard–Satterthwaite Theorem: A Simple Proof,” Economics Letters, 69(3), 2000, pp. 319-322.
Like Arrow’s impossibility theorem, this is a disturbing result. The theorem shows that a democratic (non-dictatorial) voting system with multiple options fails to be both fair and manipulation-free.
Homework 4: Lectures 13-16 (due W 2024/11/27, at any time)
Problem 1: On paperless voting We strive, and are often encouraged, to go paperless in various daily activities, such as on-line banking and healthcare records, two domains that raise safety and privacy issues. What is different about voting that makes us squirm about totally paperless systems? Discuss.
Problem 1 solution Distrust of unfamiliar technology is widespread. Take the case of self-driving cars. No amount of data on the greater safety of a self-driving car compared with one operated by a human driver may suffice to convince skeptics. Such a distrust existed in the early stages of on-line banking and computerized healthcare records, but it seems to have faded away with years of trouble-free use. Nowadays, the convenience and broader choice in on-line transactions, shopping in particular, trumps any misgivings that may have existed. As I mentioned in class, this is an issue primarily for “digital immigrants,” who were not born into or raised with digital technology the way “digital natives” have. See Marc Prensky’s insightful article, “Digital Natives, Digital Immigrants.”
Problem 2: Usability of voting machines You are in charge of a comparative usability study for two different voting machines.
a. One usability parameter is time-to-vote, which is the amount of time a voter spends with the machine in order to complete the voting task. Discuss an experiment that you would conduct to compare the usabilities of the two machines with respect to time-to-vote.
b. Once you have collected two sets of time-to-vote values for the two machines, discuss how t-test allows you to rule out the null hypothesis, which you will define.
c. Can you think of at least one more usability parameter that can be experimentally measured?
Problem 2 solution Suppose we pick 200 representative voters, with similar levels of education and digital literacy, divide them into two equal groups of 100, and have them fill out the same ballot on the two machines, measuring the amount of time spent. This will lead to two list of numbers:
x1, x2, x3, ... , x100
y1, y2, y3, ... , y100
b. If the two machines are equally usable with respect to the time-to-vote measure (the null hypothesis) the two sets of values of part a come from the same distribution. In statistics, t-test is used to determine whether two sets of values come from the same distribution. There are multiple on-line t-test calculators, and Microsoft Excel spreadsheet program also has a t-test feature.
c. Error rate is one example. I’ll leave it up to you to think about how error rate can be measured experimentally.
Problem 3: Use of voting machines in the classroom Your professor in a course with 200 students has decided to use a yes/no voting machine to administer and grade quizzes in class. A yes/no question is asked and the students have a specified time limit to enter their yes/no votes.
a. What do you think of the reliability and accuracy of this scheme?
b. Is it a good idea to make the quiz self-grading by comparing each student’s answer to the answer given by a majority of students?
c. One advantage of this voting-based testing is instant feedback. Are there other advantages? What about disadvantages?
Problem 3 solution
a. In exams/quizzes with yes/no and other types of multiple-choice questions, different students typically receive multiple versions of the exam to prevent cheating. If the same question is broadcast to everyone, say, on a video screen, the possibility of copying the answer from a neighboring student exists. Furthermore, with the use of wireless voting devices, such as clickers, erroneous recording of answers is a real possibility, with errors not detectable and thus not correctable.
b. This is tempting to do, given Condorcet’s Jury Theorem. However, there is no basis to assume that the probability of a student answering a question correctly is more than 50%. In fact, many tests contain special questions designed to distinguish the very top students from average students. For such questions, it is possible that the probability of a correct answer by a randomly chosen student is far less than 50%.
c. Studies have shown that the use of technology in classrooms increases student excitement and engagement. The instructor can also benefit from feedback that may indicate a particular topic was not well-understood and may need additional explanation. The standard disadvantages of multiple-choice questions apply. Such questions are extremely difficult to design to ensure correct interpretation. They also lack the depth that one can pursue with free-form or essay-type questions.
Problem 4: Integrity of elections Threats to election integrity can arise at many different levels, including disinformation during the campaign, interference in the casting of ballots, irregularities in vote-counting, inadequacies in result verification, and failures in the final certification process. Read this NPR story from September 2024, entitled "Here's why many election experts aren't freaking out about certification this year," and answer the following questions in connection with US elections.
a. Why is certification of the results critical?
b. Who/What is in charge of election certification?
c. Why aren't experts freaking out? (Explain in a PowerPoint-like slide with three bullet points.)
Problem 4 solution
a. Without certification, the election process cannot be closed and elected officials can’t receive their credentials to occupy the new position in which they are to serve.
b. At the state level, results may be certified by a single elected official (for example Governor or Secretary of State), state’s legislative body, an appointed election director, or by a designated board. Certifying a presidential election involves an additional set of deadlines and players, namely, electors.
c. Here are three of the main reasons cited in the NPR story.
- Since 2020, certification laws at the state and federal level have been made clearer
- Courts have successfully forced certification when local officials were inclined not to do it
- Withholding certification may stand in the way of legal challenges and recount requests
Problem 5: The US Electoral College system It is well-known that the US Electoral College system violates the majority criterion.
a. Cite two exmples from recent US presidential elections where the losing candidate earned a majority of the popular vote.
b. True or false? Because half of the 538 electoral college votes are needed to win the presidency and in most states, a tad over half of the popular vote suffices to win all of the state's Electoral College votes, it is theoretically possible to win the US presidency with about 25% of the popular vote. Discuss.
c. Bonus optional part: What is the smallest possible fraction of the popular vote that could lead to Electoral College victory?
Problem 5 solution
a. After 1824, 1876, and 1888, the first example in modern times is the 2000 election, in which George W. Bush won the Electoral College 271-269 but lost the popular vote to Al Gore by 0.54 million. A second example is the 2016 election, in which Donald Trump prevailed 306-232 in electoral votes but had 2.9 million fewer total votes than Hillary Clinton.
b. The statement is essentially true, ignoring the two states (Maine and Nebraska) which allocate their total of 9 electoral votes proportionally and the impact of uneven voter turnout & state populations per electoral vote. Perhaps 26% or 27% would be a better estimate of the minimal fraction of voters that could give an Electoral College win to a presidential candidate. On the other hand, with more than two candidates, it is possible to win a state’s Electoral College votes by earning far fewer than 50% of the state’s popular vote. So, let’s keep 25% as an approximate working estimate.
c. According to this video, a candidate can win the US presidency with just 21% of the popular vote. Computing the number is complicated, because it depends on the voter turnout in each state and the number of candidates. The 21% estimate was obtained assuming that every American votes.
If you let your imagination run wild, 11 voters can determine who wins the presidency.
Problem 6: UCSB Chancellor UCSB has just begun the search process to replace Chancellor Henry Yang, who will step down at the end of the 2024-2025 academic year. Suppose four candidates are invited to campus and representatives of the various stakeholders (students, staff, faculty) are allowed to interview them. The final selection is to be based on weighted voting among the stakeholders. How would you go about setting the appropriate weights and conducting the election process?
Problem 6 solution This is a tough question. It seems that students should be given the lowest vote weight (they are transitory, whereas staff and faculty are here for the long haul) and faculty members the highest vote weight (a research university’s reputation derives primarily from the quality and prestige of its faculty). However, it can also be argued that UCSB’s reputation follows students for many years after they graduate, so they do have a long-term interest in the success of our institution. A second factor is whether all three stakeholders are equally equipped to judge the quality of a chancellor candidate. Certain qualifications, such as academic background and awards/honors are easy to judge for anyone, but there are also intangible qualities that may not be apparent to every stakeholder. Overall, if I had to make such a choice, I’d give vote weights of 3, 2, and 5 to students, staff, and faculty. It can also be argued that undergraduate and graduate student views should be considered separately, in which case the weights 1, 2, 2, 5 may be appropriate.
Problem 7: Mini-research assignment Look up blockchain voting. Describe the idea and list a few of its claimed advantages & perceived problems (double-spacing okay).
Problem 7 solution summary A blockchain is a decentralized, distributed and public digital ledger that is used to record transactions across many computers so that the record cannot be altered retroactively without the alteration of all subsequent blocks and the consensus of the network. Given that blockchain has been used successfully for Bitcoin and other sensitive financial transactions, it is natural to think about the possibility of using it for voting. While there are many enthusiastic proposals and start-ups for the use of blockchain in voting, the consensus appears to be against this approach.
US Vote Foundation states: “Although the subject of considerable hype, blockchains do not offer any real security from cyber attacks. Like other online elections architectures, a blockchain election is vulnerable to a long list of threats that would leave it exposed to hacking and manipulation by anyone on the Internet, and the attack might never be detected or corrected.”
In a paper entitled “Going from bad to worse: from Internet voting to blockchain voting,” the authors maintain that “given the current state of computer security, any turnout increase derived from Internet- or blockchain-based voting would come at the cost of losing meaningful assurance that votes have been counted as they were cast, and not undetectably altered or discarded.”
Research Paper
Each student will review a subarea of elections & voting or do original research on a selected and approved topic. A list of pre-approved research topics is provided below. However, students should feel free to propose their own topics for approval. To propose a topic, send via e-mail a one-page narrative, including 2-3 key references, to the instructor.
A publishable report earns an "A" for the course, regardless of homework grades. See the course calendar for schedule & due dates and Research Paper Guidlines for formatting tips.
List of pre-approved research topics
01. Elections and Voting for the EU Parliament
02. Elections and Voting in the UK [Assigned to Guannan Wang]
03. Elections and Voting in France [Assigned to Keshav Taneja]
04. Elections and Voting in Germany [Assigned to Torin Schlunk]
05. Elections and Voting in Israel
06. Elections and Voting in Japan [Assigned to Ethan Epp]
07. Elections and Voting in India [Assigned to Sahiti Challa]
08. Elections and Voting in Australia
09. Elections and Voting in Canada
10. Elections and Voting in Mexico
11. Elections and Voting in Brazil
12. Elections and Voting in Uruguay
13. Elections and Voting in Egypt
14. Elections and Voting in South Africa
15. Elections and Voting in Tunisia
16. Elections and Voting in Ghana
17. Impossibility Results Beyond Arrow's Theorem
18. Will Internet Voting Ever Become Practical? [Assigned to Jack Shoemaker]
19. The Cases For and Against Approval Voting [Assigned to Ryan Wenger]
20. The Cases For and Against Borda-Count Voting
21. The Cases For and Against Ranked-Choice Voting
22. Voting Machines: History and Trends [Assigned to Yu Jia]
23. Converting Quorum Sets to Weighted Voting Schemes
24. Game-Theoretic Formulation of Voting Schemes
25. US Legislation to Prevent Gerrymandering
26. Documented Effects of Mis-/Dis-information on US Elections
27. Arguments for and Against Electoral College in the US [Assigned to Cameron Barrett]
28. Voting Shemes with Strength Indicators for Preferences
29. Condorcet vs. Plurality Winner Without or With Run-off
30. Approval Voting with Strong and Weak Endorsements
31. Elections and Voting in South Korea [Assigned to Bulou Tian]
32. Effects of Large Language Models on Candidates' Strategies and Voting Results [Assigned to Wei-Yuan Su]
33. Elections and Voting in Taiwan [Assigned to Szu-Wei Yeh]
34. Sequential and Parallel Computational Complexity of Majority Voting
35. Sequential and Parallel Computational Complexity of Plurality Voting
36. Sequential and Parallel Computational Complexity of Borda Voting
37. Voting in the BRICS Intergovernmental Organization [Assigned to Parth Kulkarni]
Grade Statistics
All grades listed are in [F, A+], unless otherwise noted.
HW1 grades: Range = [C+, A], Mean = 3.31, Median = B+
HW2 grades: Range = [B, A], Mean = 3.52, Median = B+
HW3 grades: Range = [B, A], Mean = 3.67, Median = A–
HW4 grades: Range = [B, A], Mean = 3.62, Median = A–
Overall homework grades (percent): Range = [75, 110], Mean = 90.4, Median = 90
Research grades: Range = [B, A], Mean = 3.41, Median = B+
Research grades (percent): Range = [75, 100], Mean = 85.3, Median = 83
Course grades: Range = [B, A], Mean = 3.48, Median = B+
References
This course has no required textbook. The lecture slides and documents linked below are our main information sources.
PDF slides for Lectures 1-4 (last updated 2024/10/10)
PDF slides for Lectures 5-8 (last updated 2024/10/23)
PDF slides for Lectures 9-12 (last updated 2024/11/07)
PDF slides for Lectures 13-16 (last updated 2024/12/02)
Useful books (not required):
Arrow, K., Social Choice and Individual Values, Yale U. Press, 2nd ed., 1970.
Borgers, C., Mathematics of Social Choice: Voting, Compensation, and Division, SIAM, 2010.
Brams, S. J., Mathematics and Democracy: Designing Better Voting and Fair-Division Procedures, 2009.
Brams, S. J. & P. C. Fishburn, Approval Voting, Springer, 2nd ed., 2007.
Cooper, W., How America Works ... And Why It Doesn't: A Brief Guide to the US Political System, 2024.
El-Helaly, S., The Mathematics of Voting and Apportionment: An Introduction, 2019.
Gehrlein, W. V. & D. Lepelley, Elections, Voting Rules and Paradoxical Outcomes, 2017.
Gehrlein, W. V. & F. S. Roberts (eds.), The Mathematics of Preference, Choice and Order, 2009.
Heckelman, J. C. & N. R. Miller (eds.), Handbook of Social Choice and Voting, Edward Elgar, 2015.
Hodge, J. & R. E. Klima, The Mathematics of Voting and Elections: A Hands-on Approach, 2nd ed., 2018.
Lewis, V., The Myth of Left and Right: How the Political Spectrum Misleads and Harms America, Oxford, 2023.
Poundstone, W., Gaming the Vote: Why Elections Aren't Fair (and What We Can Do About It), 2008.
Robinson, E. A. & D. H. Ullman, The Mathematics of Politics, CRC Press, 2nd ed., 2016.
Saari, D. G., Chaotic Elections: A Mathematician Looks at Voting, American Math. Society, 2001.
Saari, D. G., Decisions and Elections: Explaining the Unexpected, Cambridge, 2001
Saari, D. G., Disposing Dictators, Demystifying Voting Paradoxes, Cambridge, 2008.
Sullivan, B. W., An Introduction to the Math of Voting Methods, 2022.
Szpiro, G., Numbers Rule: The Vexing Mathematics of Democracy, from Plato to the Present, Princeton, 2020.
Taylor, A. D. & A. M. Parcelli, Mathematics and Politics: Strategy, Voting, Power, and Proof, 2nd ed., 2008.
Volic, I., Making Democracy Count: How Mathematics Improves Voting, Electoral Maps, & Representation, 2024.
Wallis, W. D., The Mathematics of Elections and Voting, Springer, 2014.
Relevant articles/chapters:
Fishburn, P. C. & J. D. C. Little, "An Experiment in Approval Voting," Management Science, 34(5), 1988.
Fujiwara, T. et al., "The effect of Social Media on Elections: Evidence from the United States," J. European Economic Association, 22(3), pp. 1495–1539, 2024.
McLean, I., "The Strange History of Social Choice," Chapter 2, pp. 15-34, in Heckelman & Miller (2015).
Saari, D. G., Power of Mathematical Thinking: From Newton's Law to Elections & the Economy, 24 lectures
On-line sources:
Batholdi, J. J. et al., "The Computational Difficulty of manipulating an Election" [PDF]
Budd, Chris (Gresham Prof. of Geometry), 58-minute lecture on "Maths and Voting."
Congressional Research Service, "Apportionment and Redistricting Process for the US House ...," 2021.
Contemporary Mathematics, Fairness in Voting Methods.
Fishburn, P. C. & J. D. C. Little, "An Experiment in Approval Voting," MIT Working Paper, 1986.
Geanakoplos, John, "Three Brief Proofs of Arrow's Impossibility Theorem," 2005. PDF
Haunsperger, D., "Saari, with no Apologies," College Mathematics J., 36(2), pp. 90-100, 2005.
Hodge, J. & R. E. Klima: Book's on-line front/end matters.
Kohler, U. & J. Zeh, "Apportionment Methods," The Stata Journal, 12(3), 2012.
Maskin, E., "Arrow's Theorem, May's Axioms, and Borda's Rule," on-line document, 2022.
Parhami, B., "A Taxonomy of Voting Schemes for Data Fusion and Dependable Computation," PDF.
Parhami, B., "Threshold Voting Is Fundamentally Simpler than Plurality Voting," PDF.
Parhami, B., "Parallel Threshold Voting," PDF.
Parhami, B., "Voting: A Paradigm for Adjudication and Data Fusion in Dependable Systems," PDF.
Stanford Encyclopedia of Philosophy: Social Choice Theory.
US Congress, Constitution Annotated: Analysis & Interpretation of the 14th Amendment.
Veritasium, "Why Democracy is Mathematically Impossible," 24-minute video.
Wikipedia, "List of elections involving vote splitting," link.
Young, H. P., "Condorcet's Theory of Voting," American Political Science Review, on-line access.
Miscellaneous Information
Motivation: Elections are one of the pillars of democracy, yet most citizens know very little about the process other than their privilege/ability to cast votes for their preferred candidates. There are in fact a lot more to elections than voting for your top candidate. Being aware of issues & problems and learning about alternative voting schemes is a prerequisite for reforming our election system in order to avoid some of the pitfalls discussed in this course.
Catalog entry: 594BB. Mathematical, Algorithmic, and Engineering Aspects of Democratic Elections. (4) Parhami. Prerequisite: Graduate standing in Computer Engineering. Lecture, 4 hours. This course reviews the history, characteristics, and variants of democratic elections. Since an ideal voting system does not exist (Arrow's Theorem), alternative voting schemes that come close to the ideal are introduced and evaluated. Algorithmic, software, and hardware aspects of modern elections, and issues related to districting, including the notorious problem of Gerrymandering, are also discussed.
History: This gtraduate-level seminar was offered in fall 2024 for the first time. Its offering was inspired by Professor Parhami's research on voting algorithms and networks in the context of fault-tolerant computing and his peripheral studies on the subject of voting in the domains of social choice and data fusion.