Voting Theory & My First Coursera Experience

While studying mathematics as an undergraduate in college, I became aware of the subject of voting theory through a colloquium discussing Arrow’s famous impossibility theorem. Later I learned of MOOCs (Massive Open Online Courses) like edX and Coursera, which since around 2012 have started offering (sometimes) free online courses on a variety of subjects.  Compared to traditional classrooms MOOCs have many desirable qualities to recommend themselves, including lower costs and more flexible schedules.  Some of these courses have actually been recommended for accreditation by the American Council on Education, but the universities that organizations such as Coursera partner with typically do not offer college credit for these classes unless you are taking them in conjunction with being enrolled as a student there. Undoubtedly the motivation for this is the financial incentive to artificially limit competition with existing university models (this is my stark opinion anyway; for a more “balanced” discussion on the topic see this article). Undeterred however, perhaps anticipating eventual policy changes on the behalf of universities/employers, I took it upon myself to enroll in one of the Signature Track (i.e. paid) courses offered by Coursera this fall, Making Better Group Decisions: Voting, Judgement Aggregation and Fair Division taught by University of Maryland Dept. of Philosophy professor Eric Pacuit, which just so happened to revolve around this subject of voting theory that I was already somewhat familiar with by the time. The recommended audience for the course includes economists, political scientists, & computer scientists.

Mathematical Woes and Quizzing Conundrums

The professionalism and the quality of the lectures was impressive. These were presented in a format familiar from Khan Academy videos and the like. Each week’s course materials consisted of about ten 10-15 minute videos for the seven weeks of the half-semester course, with an additional week zero giving preliminaries for the mathematics used. Some of the “advanced lectures” would last up to half an hour because the instructor was proving a more involved theorem. During each week there was also a quiz with at least nine or ten questions, usually multiple choice, as well as in-video questions; these tested your understanding of the material.

One of the
One of the “Advanced Lectures”.

Indeed, the level of mathematical sophistication was one of the most reoccurring complaints in the forums for the course, with many people considering dropping out due to the difficulty of the weekly quizzes. During week three the instructor responded to these complaints by changing the quizzes so that students could have up to three attempts at them and receive the best of those three scores. Unfortunately, the instructor also turned off feedback to some extent: although we could still see our score after each attempt, there was no longer any indication about which questions we had gotten incorrect.

My thoughts on changes to quiz policy.
My thoughts on changes to quiz policy.

Thankfully, the instructor has since said he is going to take everyone’s concerns into consideration and redesign the quizzes when teaching future courses.

After seeing this though I’m not too sure how likely that is:

Problems from the last time this course was offered remain.
Problems from the last time this course was offered remain.

Coursera & Verified Online Education

Coursera takes an interesting approach to verifying its Signature Track courses: after submitting each quiz I was prompted to type out a sentence of academic integrity, very similar to what you do when taking the ACT and most other standardized achievement tests. While your unique cursive signature can be used to detect fraud in the case of the ACT it turns out that each person has a unique biometric signature as well with respect to his or her typing patterns. After giving my biometric signature, I am also required to submit a webcam photo of my face for facial recognition purposes. I am on the “Signature Track Trial” being offered for the course that lets me postpone payment until the last week of the course, which gives me a greater likelihood of passing and not wasting money. Should I decide, I then give Coursera my credit card info for billing purposes and a copy of some gov-issued photo id.

All of these things together make it pretty clear exactly who is the recipient of the certificate you receive for passing the course. None of this guarantees that I am not cheating or being assisted by an accomplice of course, but it is at least very difficult to pretend to be someone else this way. If, say, I had been required to write an essay in real-time then this concept of biometrics could potentially become extremely effective at detecting instances of cheating as well. All that it would take for a cheater to be identified would be for him to help more than one person: then, the cheater’s biometric fingerprint would show up in two different places, clearly indicating foul-play (if you’re worried about a cheater simply dictating his thoughts to another person, you can even detect individuals based on their writing styles and choice of words). Besides just detecting cheating, MOOCs are also automating the grading/feedback process (in order to cut costs): Peer Assessment is already being used and Automated Essay Scoring looks promising. After the course is completed I can post a link to my verified Coursera course record to LinkedIn for employers or whoever else might be interested. [UPDATE: I passed! Here’s my certificate.]

Neat stuff huh

Course Overview

This is a quick outline of the content of the course, going week by week:

Basic properties that relations might satisfy.
Basic properties that relations might satisfy.

Week Zero: The mathematical preliminaries to the course are introduced: these include relations (used for expressing individual preferences) and functions (used for taking groups of indiv. preferences and computing the societal preference) and the basic laws of probability theory and propositional logic.

Different types of voting systems.
Different types of voting systems.

Week One: Different types of voting procedures are examined. Also, reasons are provided for why certain voting systems should be considered inadequate: for instance, with Plurality Rule there is the potential to elect a candidate disapproved by a majority of voters. Condorcet-consistent voting methods including Copeland’s Rule, Black’s Rule, and Dodgson Rule [PDF]/Young, positional scoring rules (e.g. Borda Count), Multistage methods including Plurality with Runoff, Single-Transferable Vote/Hare Rule, and Coombs RuleApproval Voting, Range Voting and Majority Judgment are all discussed.

No sensible (monotonically-increasing) positional scoring rule can elect the Condorcet winner for this voter preference profile.
No sensible (monotonically-increasing) positional scoring rule can elect the Condorcet winner for this voter preference profile.

Week Two: It is shown that there exists a preference profile of voters such that no positional scoring system can elect a Condorcet winner. It is also called into question whether the Condorcet winner should always be elected (see Saari’s Geometry of Voting). Criteria for evaluating voting systems, including Monotonicity/No-Show [PDF], the Multiple Districts Paradox/Simpson’s Paradox, Independence/Spoiler Effect, and Unanimity/Pareto-Efficiency are discussed. Finally, the last couple of lectures talk about whether voting systems should be about finding value-based compromises among voters or instead finding some objectively best candidate among voters provided with differing levels or types of information.

Unanimity, Anonymity, Neutrality, and Positive Responsiveness characterize Majority Rule with two candidates.
Unanimity, Anonymity, Neutrality, and Positive Responsiveness characterize Majority Rule with two candidates.

Week Three: Various voting systems are characterized (meaning necessary and sufficient conditions are given in terms of the criteria from week two). One of these characterization results include May’s Theorem, which is proved. Also Arrow’s impossibility theorem is proved; this is a highlight of the course.

An example of single-peaked preferences.
An example of single-peaked preferences.

Week Four: Domain restrictions are shown to sometimes circumvent the impossibility results and a proof is given of Sen’s Triple-wise Value Restriction theorem [PDF]. Strategic voting is discussed, and an impossibility result involving preference lifting is proved. Finally, the Gibbard-Satterthwaite theorem is discussed and Sen’s Liberal Paradox is explained.

Anscombe's Paradox
Anscombe’s Paradox

Week Five: Anscombe’s Paradox and the Multiple Elections Paradox are described, and the Condorcet Jury Theorem is proved. Paradoxes of Judgement Aggregation are examined and impossibility theorems are proved. Anscombe’s Paradox is resolved if a 3/4-ths majority rule is adopted [PDF].

There isn't always an envy-free and efficient division of goods.
There isn’t always an envy-free and efficient division of goods.

Week Six: Notions of Fair Division and Social Welfare are introduced. During this week indivisible goods are considered (divisible next week).  Envy-Free and Pareto-Efficient division are shown to be sometimes incompatible.  Also, voting systems and measures of social welfare are sometimes inadequate at selecting envy-free divisions from among the Pareto-efficient ones [PDF]. The Adjusted Winner algorithm for fairly dividing goods among two individuals is introduced.

An envy-free three person moving-knife cake-cutting procedure.
An envy-free three person moving-knife cake-cutting procedure.

Week Seven: Cake-Cutting algorithms are discussed. Cut and Choose produces two-person envy-free division but is not equitable. The Surplus Method [PDF] is shown to be a better alternative to Cut and Choose (although it requires a trusted third-party. There is a whole area of cryptography, Secure Multiparty Computing, which attempts to eliminate the need for such individuals). It is shown that for three players a contiguous, equitable, and envy-free division might not exist. Various “moving-knife” procedures are discussed including the Dubins-Spanier [PDF] and the Stromquist procudures.  So-called finite-bounded cake-cutting algorithms are shown to exist for any number of players that are proportional, but it is currently not known how to do this with four players and envy-free divisions (see this paper [PDF] for an overview of finite proportional/envy-free cake-cutting methods).

Forums

I took many opportunities within the discussion forums each week to bring up any interesting points that had occurred to me. My contribution during the first week was relatively modest: I asked if the professor could be more mindful of the fact that academic articles are generally not free and in fact are usually very expensive. Sometimes you get lucky and can find a pdf floating around somewhere, but generally most articles cited in the course are hiding behind pay walls. This has been the topic of much discussion in the past years.

I just want to read that's all.
I just want to read that’s all.

During week three I introduced topological social choice theory into the discussion. Although the mathematical background was even more demanding than before generally positive feedback was received for the submission.

Sounds like rocket science!
Sounds like rocket science!

During week four I drew connections between social choice theory and matching theory/labor economics (motivated by this book chapter):

Matching Theory is used by the National Resident Matching Program for medical students.
Matching Theory is used by the National Resident Matching Program for medical students.

During week five I was critical of the proof the instructor gave for a certain result (taken from this paper). Also, it is noticed how ultrafilters play an important role in many of the impossibility theorems of social choice theory.

An interesting exchange I had with the instructor. Also, in case you're wondering, the fancy characters are being rendered using LaTeX.
An interesting exchange I had with the instructor. Also, in case you’re wondering, the fancy characters are being rendered using LaTeX.

During week six I again made some minor criticisms but tried to even things out with some praise.

Different notions of social welfare.
Different notions of social welfare.

During week seven I once more made another correction.

Yet another mistake.
Yet another mistake.

Conclusion

In my opinion, probably the biggest strengths of this course were

  1. the instructor had a comprehensive understanding of the material, was also polite and constructively interacted with students
  2. numerous opportunities for further reading thanks to abundant citations and references to the social-choice literature
  3. in-video questions/quizzes that were sufficiently difficult and engaging, on the same level as an actual university course; indeed the material heavily borrows from PHIL 408 – Individual and Group Decision Making taught at Eric’s University of Maryland

Likewise, the biggest weaknesses of the course were these:

  1. lots of mistakes (I pointed these out in my forum selections above)
  2. underestimation and misrepresentation of the course’s mathematical difficulty and prerequisites; many students got frustrated with this
  3. not enough opportunities for feedback on quizzes (see Mathematics Woes and Quizzing Conundrums section above) and no homework problems were provided to help prepare students for these quizzes

Final Remarks

Based upon this largely positive experience, I plan on possibly taking more courses at Coursera or other MOOCs, although I probably won’t always pay for these courses as I did this time around. I am also intrigued about the possibility of teaching my own course, as apparently Udemy allows one to do. Either one of these activities could potentially become the subject of new blog posts.

There were many topics that the professor simply didn’t have the time to cover in the seven week course. As I mention in one of my forum screenshots above, there is in fact a theory of voting systems involving a countably infinite amount of voters, and there is also a theory of non-deterministic voting systems; both of these notions can be used to sidestep Arrow’s seminal impossibility result (I credit XOR’s Hammer with his post on probabilistic voting and noticing how Random Dictators overcome Arrow’s paradoxical result, thanks XOR). Another interesting topic in social choice theory omitted was voting power indices.

Agenda-setting by the mass media and the amount of money both individuals and organizations spend on elections is also an important aspect of elections.

Another important aspect of elections is the possibility of gerrymandering

One way to avoid gerrymandering is by changing the voting system.

Speaking of gerrymandering: Prison Gerrymandering Project

Proxy Voting/Delegative Democracy and Voting in Social Networks

Reddit on political knowledge testing in order to vote and Obama’s suggestion of enacting compulsory voting and felon voting rights.

More on felon voting rights: Breakdown of US state-by-state felon voting laws

I’ve noticed that a lot these MOOCs have been amenable to a sort of meta-analysis, where you take the concepts from some course and apply them to the course itself (for example see The Justice of JusticeX and MOOCs Push The Efficiency Frontier); this class is no exception vis-a-vis voting in the forums.

The cost of college tuition is outrageously expensive. Again, as I mentioned in the opening paragraph, online classrooms could present one way of providing cheaper access to higher education. Some countries are managing quite well even without reliance on this new technology: for example, Germany just recently cancelled all forms of college tuition. Combine this with a zero percent interest rate on student loans (though you still might need some loans for housing and transportation), a twenty-year repayment plan (you aren’t a debt slave forever), and five-year forbearance until loans become due (compared with six months in the US) and you end up with a considerably more student friendly college financing experience. Of course Forbes has to put things into perspective though by reminding the business community how awful it would be to have such a progressive tax rate for high income earners.

There is also a psychological component to statements of academic integrity.

Good book on social welfare: A Quiet Revolution In Welfare Economics.

Someone else from my course section did a review also (warning it’s French).

A cool dependency map I made out of some of this article’s topics.

End-to-end Auditable Voting Systems

Once it is decided which voting system will be used during an election (and also which issues or candidates will be voted upon, who is allowed to vote and how much weight is given to each vote, the time given to deliberate, etc.) there is still the question of how to prevent fraud while maintaining voter/ballot secrecy.

Ben Adida gave an excellent Google Tech Talk on this subject:

At around 6:50 in the video the speaker brings up an amusing limitation of voting systems. Although this might just seem a quaint observation by itself, what Ben is hinting at here is the notion of Differential Privacy.

Cryptography stuff not making sense? There’s a Coursera course on the subject.

For a more detailed account of E2E voting take a look at Ben’s thesis.

I found a Coursera course that just started Oct 6 2014, Securing Digital Democracy by the University of Michigan, that apparently mentions E2E voting systems (you can preview the lectures without enrolling).

Another area of mathematics I was studying in college was integer factorization algorithms, the study of which can be motivated by the dependence of a lot of common public-key cryptosystems on this task being a difficult one. Anyway Ben also made a contribution to the quadratic sieve integer factorization algorithm (which I found out about at the end of this blog post by msdn).

Towards the end of the video Ben hints at the possibility of using E2E voting for other types of preferential voting systems of the nature discussed in this post, but also warns of their limitations by way of “signature” or “Italian” attacks.

In case you were wondering why Ben even bothered discussing mix-nets at length, one reason might have been their potential for implementing these nonstandard voting systems. Here are some papers for the curious.

Shuffle-Sum: Coercion-Resistant Verifiable Tallying for STV Voting (2008)

Partial Disclosure of Votes in STV Elections (2013)

Another way to accomplish this is by using fully homomorphic cryptosystems which also came up in the video tangentially.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s