Math Lecture

The Linear Algebra of Voting

Mike Orrison, of Harvey Mudd, visited the REU on Wednesday and talked about the generalized Condorcet criterion and the underlying linear algebra used to prove a surprising result.

The Condorcet criterion is said to hold for a voting system if it guarantees that, if a candidate would win each head-to-head election, then that candidate would win the election.

In our usual voting system, we only ask voters to vote for their first choices. But you could imagine having voters list their preferences. For instance, if I had to rank my cats, I’d rank them M > T > S (Moo’s my favorite, then Tipper, and lastly, there’s Sophie).

Now, I could ask my friends to rank my cats, and maybe I’d come up with:

  • M > T > S – ten ballots
  • T > M > S – four ballots
  • T > M > S – five ballots
  • S > T > M – two ballots

We can take away a few things from these rankings:

  1. No one likes Sophie (poor Sophie!).
  2. Moo wins the election!
  3. I have a lot of friends (okay, okay: it’s a fictional example).
  4. Tipper beats Moo (11 to 10); Tipper beats Sophie (19 to 2); Moo also beats Sophie (19 to 2).

Item 4 means that Tipper is the Condorcet winner. However, if we use our usual “most first place votes” election, we’d see that Moo is the winner.*

If you have more than three candidates, the results get weirder. You can have someone who wins every head-to-head competition (call the 2-winner Bob), but someone else could win in every three-way battle (call the 3-winner Alice).

The surprising and cool result is that once Bob’s 2-winningness (my term) is overshadowed by Alice’s 3-winningness, Bob can’t go on to be a 4-winner. He can’t be any n-winner for n > 3. And the proof, my friends, rests in linear algebra.  You can read all about the work Mike did with his REU students in their paper: Generalized Condorcet winners.

*In reality, Moo would win by any metric because she’s fantastic.

Screenshot 2015-06-29 09.05.42

Golden mutation…?

The argument I’ve always heard for why leaves or branches grow by rotating around a stem/trunk one golden angle at a time is that this is an optimal mutation. I’ve even heard this as an explanation for why clovers typically have three leaves. I’m not sure I understand how the thinking applies, since it seems to be about getting the most sunlight without completely overshadowing earlier growth, and this clearly isn’t a factor for a single clover. I haven’t sat down with a collection of clovers and a protractor, either. So I’m basically saying I’m riddled with doubts here.

Anyway, nevertheless, I wonder about the Fibonacci/golden angle/n-leaf-ness aspect of four leaf clovers often. If we planted a patch of 4 leaf clovers, would a 3 leaf mutation really be optimal “enough” to eventually win out? This is an empirical question, so I hope someone will take the charge and design a long-term controlled study!

The following NPR story starts with an anecdote about Kepler. Apparently, he was trying to find himself a wife, and he had 11 candidates, but he was too thorough in interviewing them (read: slow!), and they all got impatient and rejected him. Damn.

Turns out, if you have limited options, the best strategy for a good match (though maybe not the best match) is to interview 1/e (~36.8%) of your candidates without offering the “job” to any of them. Then, if you’re interested in anyone after that point, pop the question and forget the rest of the list.

Read more at NPR:
NPR: How to marry the right girl

Golden Power Series!

As you probably know, I wear my heart on my sleeve:

Well, I took the golden opportunity (ha!) to bring the golden ratio \Phi = \frac{1+\sqrt{5}}{2} into Calc 2 this week, using it (and its little pal \Psi = \frac{1-\sqrt{5}}{2}) to find a closed formula for the n-th term of the Fibonacci sequence.

The ubiquitous Fibonacci sequence! It’s something you may have encountered out in the wild. You know, it goes a little like this:

F_0 = 1, \, \, F_1 = 1, \, \, F_n = F_{n-1} + F_{n-2},
so F_2 = 2, \, \, F_3 = 3, \, \, F_4 = 5, \, \, F_5 = 8, \, \, F_6 = 13, \, \, F_7 = 21 \, \, \ldots.

And let’s say for some reason, you need to cook up F_{108}. I hope you have some time on your hands if you’re planning to add all the way up to that. Instead, wouldn’t it be nice if we had a simple formula that we could use — i.e., a formula that was not recursive — to figure out the n-th Fibonacci number?

Luckily, such a formula exists, and there are lots of ways to find it. In this post, we’ll find it using power series. Read on, brave blogosphere traveler.