*The Golden Ticket: P, NP, and the Search for the Impossible*that talks about the theoretical impact of solving one of the Millenium Problems (seven unsolved math problems that the Clay Mathematics Institute will award, for each solution, a prize of one million dollars).

Since this is a very complicated problem, I will only give a superficial overview of the problem here.

Let’s say there are two kinds of problems, P and NP. P are relatively easy to solve and NP are very difficult. The conjecture is that P = NP, which would mean in the simplest sense that there are easy solutions to the much harder problems in terms of the time required to solve them.

Generally speaking, most mathematicians think P = NP is false, but nobody has proven it false. In Lance Fortnow’s amazing book, he imagines a world where P = NP true! Some of the things that he imagines with this “Golden Ticket” is that even the most aggressive illnesses could be cured in weeks and people planning weddings could know the* exact* weather on the big day months in advance.

Of course these are all dreams based on the idea of P = NP being true, but it is tantalizing to imagine the world that could open up with this single slice of mathematical truth! Even the wildly popular show The Simpsons paid homage to this mathematical idea 25 years ago in one of their early *Treehouse of Horror* Halloween episodes (several of The Simpsons writers have math/science degrees from Harvard!)

This may all seem a little abstract, so let’s talk about something that’s immediate, concrete and that impacts us all–voting! As we grow up, leaving our teenage years, one of the things that is impressed upon us as responsible citizens in a democratic society is the importance of voting. While that is indeed noble, almost everyone who votes doesn’t understand the mathematics of voting. Namely, that depending on the method of voting, a *different* candidate could win.

Namely that, simply stated, different voting *methods *produce different *results*.

The French mathematician, Marquis de Condorect (1743-1794) was the first to take a serious look at the mathematics of voting. In fact, he had a sneaky suspicion that it would be* impossible *to truly quantify the will of the people. He was proven correct a few hundred years later, in 1972, when Kenneth Arrow won the Nobel Memorial Prize in Economics with his “Arrow’s Impossibility Theorem”. In this, Kenneth Arrow proved that it is impossible to fairly elect a person in a group of three or more candidates while simultaneously meeting a set of criteria centred around fairness and democracy.

Let’s take an example in which there are three candidates in an election. Candidate A represents right of centre and candidates B and C represent left of centre. If the candidates receive 40, 30, and 30 percent of the votes respectively, then candidate A wins. However, the social will of the people (60%) was to elect a government that was left of centre. Unfortunately, it gets more complicated the more candidates there are, and there is not a single voting method–good intentions notwithstanding–that can fairly elect a person and meets Arrow’s criteria for fairness.

Condorcet actually identified a way of assessing the outcome of a vote with a very high threshold for fairness, with the winner in such an analysis named in his honor–the Condorcet winner.

Here’s how his method works. Imagine there are 3 choices for dessert–Fruit, Jello, and Cake. Every choice goes head to head with every other choice (i.e., Fruit vs. Jello, Jello vs. Cake, and Cake vs. Fruit). There will be a Condorcet winner if one of the candidates wins all their head-to-head battles. For example if Jello beats Fruit and Cake, then it can be declared a Condorcet winner. However, if in the three head-to-head battles, the results are Jello, Cake, and Fruit, then there is no Condorcet winner. See how complicated the voting can get!

Let’s see how things can get complicated with the traditional method of measuring voting outcomes. Imagine 15 people vote on their preferences for dessert, and rank them first to third.

** 1st 2nd 3rd**

6 Cake Fruit Jello

5 Jello Cake Fruit

4 Fruit Jello Cake

So, the most popular was Cake with 6 first-place votes. Cake wins. But, the Jello folks start to complain because the vote was so close. So, everyone votes again, but only choosing between the top two–Cake and Jello. So, all the Fruit folks have to change the choice to their next favorite, Jello. Jello now has 5 + 4 = 9 votes–and wins! End of story, right? Everything is settled. No! That’s because the Fruit fans realize that 6 + 4 = 10 people prefer Fruit to Jello! And so, the food fight starts!

There are some great sites for learning more about voting methods and how to run simulations that produce varying results, so that students can see and discuss how complicated voting really is! The best one is by Nicky Case–To Build a Better Ballot.

Mathematics is indeed everywhere in our lives, and it is important as a member of a democratic society to not only be aware of its influence, but also to value how much it can contribute to our well-being and curiosity about our ever-changing world.