10 June 2008

Some electoral math from fivethirtyeight.com

A "homework assignment" from FiveThirtyEight.com: Electoral Projections Done Right: in a US presidential election, "[h]ow many unique ways are there to acquire at least 270 electoral votes without any excess?" That is, how many sets of states with at least 270 electoral votes, such that when any state is removed less than 270 electoral votes remain?

For the most part the comments so far are:
  • people misunderstanding the problem (which is not surprising; it's the sort of problem mathematicians are better at understanding than the general population, and the audience there is not necessarily mathematicians);
  • programmer types whining "waah, this problem is in NP, I can't do it!". Is it in NP? I don't feel like thinking about that -- but I did it in a few minutes, and more importantly with a couple seconds of computation time. NP doesn't stand for "not possible";
  • people saying "who cares, most of those combinations are politically unrealistic!" (which I have to admit is true);
  • a few estimates of the answer based on some quick and dirty statistical assumptions, which look basically right;
  • and a couple people (me included) who have gotten a numerical answer.
I'd explain my solution here, but I think some of you might want to try out this problem. If you poke around in the comments at FiveThirtyEight.com you can find my solution.

What's interesting to see is that a lot of people seem to believe you have to actually generate the sets in order to count them. That would of course be hopeless. The explanation of combinatorics as "counting without counting" comes to mind.


General Mobius said...

Your solution is lovely and elegant. I was impressed.

Also, according to facebook (because that's the sort of person I am), you know Megan Cook, who is an old associate of mine from Michigan. Small world.

Ray said...

To defend the CS types:

The problem is NP-hard and large enough to be unwieldy if not outright infeasible -- if you give each state a random 15 digit number of electoral votes.

Some CS types just don't understand the concept of an easy instance. Be glad they aren't cryptographers.

Mark said...

Great solution Isabel. Coincidentally, I've been reading parts of Generatingfunctionology recently.

As for the computer scientists and their cries of NP-hard, I'm reminded of the quote "The person who says it cannot be done should not interrupt the person doing it."

Also, unless those people are potential Turing award winners that haven't released their proof to the public yet, the "NP" in NP-hard does not mean "non-polynomial".

Soroosh said...

I was surprised how close the quick and dirty statistical solution came to the exact answer.

As ray points out, this is related to knap sack problem. (The knap sack problem would ask for the smallest number of delegates possible above 270...)
Coincidently, given todays computation power, we can solve a knap sack problem with 50 problems exhaustively.

Drew Miller said...

I don't think this problem is NP hard. Actually finding all the combinations would be, but that wasn't what was asked. It can be solved in approximately n^2 time, using essentially the same method Isabel used, writing out an algorithm that is probably very similar to what matlab uses to solve equations.

Anonymous said...

I tried it, on your advice. My weapon of choice is Perl. It wasn't hard, but it was surprisingly tricky to get it exactly right. The program also definitely requires memoization -- not entirely coincidentally a topic that you've discussed before, and somewhat coincidentally a Perl module that Mark-Jason Dominus developed. I'll note that even with your approach you used a software system to automate the tedium.

I'll also note that the number of function calls to "calc()", with Memoization, was only 13307, which surprised and pleased me, not least because the echo of l337. :-)

Here's the code:

use Memoize;
memoize 'calc';
memoize 'nCm';

my @evs = ( [55, 1], [34, 1], [31, 1], [27, 1], [21, 2], [20, 1], [17, 1],
[15, 3], [13, 1], [12, 1], [11, 4], [10, 4], [9, 3], [8, 2],
[7, 4], [6, 3], [5, 5], [4, 5], [3, 8] );
sub calc {
my ($i, $worktot) = @_;
return 0 if ($i > $#evs);

my ($val, $mul) = @{$evs[$i]}[0..1];
my ($sum, $goal, $count, $p) = (0, 270, $mul);

do {
$sum += nCm($mul, $count) *
(($p < $goal) ? calc($i + 1, $p) : 1)
if $goal + $val > ($p = $count * $val + $worktot);
} while (--$count >= 0);

return $sum;

sub nCm {
my ($n, $m) = @_;
$m = $n - $m if ($m > ($n/2));
my $total = 1;
for (1..$m) { $total *= $n-- / $_; }

printf("%s\n", calc(0, 0));

unapologetic said...

guessing before reading anything else on this page or those linked: generatingfunctionology? Even if it's not the quickest route, the overhead involved in setting up the problem lends itself to answering related questions, and thus gives a pretty good RoI