Hi everyone! Are you feeling a little tired of the same-old political discussions? Wishing there could be more math involved? If so, I’ve got a blog series for you!
In light of the upcoming elections, I thought it’d be a good time to write on The Math of Elections. In this post I will talk about the Gibbard-Satterthwaite theorem. Tomorrow I will write about how this theorem illuminates the problems that exist in our primary system. Following that I will talk about Kings, suggest alternatives to our primary system, discuss the electoral college, analyze whether voting matters, and lastly, on election day, will analyze the complexity of vote counting. Let’s get started.
The Gibbard-Satterthwaite theorem deals with elections where there are at least 3 candidates running for a single position. Observe that most elections have these characteristics — for instance most US elections begin with primaries that feature at least three candidates. Most elections that take place within your community or among your friends would also qualify. And even in our largest nation-wide general elections, many races feature an independent or third party candidate who will receive a notable number of votes.
Let’s assume that every member of the electorate explicitly ranks their preferences. They may prefer the Democrat’s candidate most, then the Libertarian, then Herman Cain, then the Republican, then the Green Partier, etc.. From this, we are going to generate society’s preference list in some way, with the most preferred candidate being declared the winner. The goal, of course, would be to find a way to do so that is fair. One procedure could be to ignore how people voted and simply place the candidate’s names in alphabetical order, and declare that to be society’s preference ranking. But, of course, that is not fair.
What about a system like our own? Our current primary system, for example, takes each voter’s preference list, ignores everything but their top choice, and gives one vote to the candidate who was that top choice. Then the candidate with the most votes wins.
Is this system fair? How can we tell? And if it isn’t, does a fair system even exist?
Well, unfortunately for society, the Gibbard-Satterthwaite theorem roughly says that no voting system with 3 or more candidates, decided by these voter preference lists, is fair. First let’s talk about what makes a voting system “fair”? I believe that most everyone would agree that the following properties are ones that a fair voting system should have.
Dictatorial Property. For starters, a dictatorship does not seem fair. So let’s say that the first condition that we demand is that there is no dictator; i.e. the result of the election cannot simply mimic the preference of a single voter.
In Iran, for instance, it appears that many citizens voted for president, but the only vote that mattered was Ahmadinejad’s vote for himself.
Winnability Property. Second, it must be possible for any candidate to win. A system where the winner is decided by picking the person whose name comes first in alphabetical order does not seem fair. We gotta give Zygarri Zzyzzmjac a fighting chance!
Manipulability Property. Finally, it should not be to one’s advantage to engage in tactical voting. Meaning, it should never be possible for someone to submit false preferences because doing so will help their true preference win.
So, for example, suppose that at the moment the Societal Ranking Procedure (whatever it may be) reports that society likes the Republican candidate the most, then the Democrat, then the Green Partier, then Herman Cain, then the Libertarian. If I personally have the ranking of Republican then Democrat then Herman Cain then Green then Libertarian, but I decide to interchange Democrat and Libertarian or Libertarian and Herman Cain, then that should not change the fact that society prefers the Republican to the Democrat. It would make no sense if suddenly the Democrats candidate jumped into first place. More to the point: no one changed their preferences with respect to the Democrats and the Republicans, so it does not make sense that society should have changed its preference either.
So those are three conditions which all seem fairly reasonable ones to ask of a voting system. However, Gibbard and Satterthwaite showed that these three conditions can not all happen simultaneously. Given any voting system with at least 3 candidates, where the winner is deterministically chosen as a function of these voter preference lists, either your system has a dictator, or some candidate is incapable of winning, or there is a way to manipulate the system by being dishonest. How sad.
I will omit the proof of this theorem in order to keep this series accessible to a large audience. Possibly some day I will come back and write a post proving it. But that day is not today.
This series will continue tomorrow when I will talk more about this theorem in the context of one unfair electoral system: the US primaries.