ACM's annual **Applicative** conference is June 1-2 in New York City.

Watch presentations from Applicative 2015:

• Keynote: JSON Graph: Reactive REST at Netflix

• Keynote: Systems at Facebook Scale

• Utilizing the other 80% of your system's performance

• Flux: A Unidirectional Dataflow Architecture for React Apps

• Exploring the Reactive Extensions in JavaScript

Watch presentations from Applicative 2015:

• Keynote: JSON Graph: Reactive REST at Netflix

• Keynote: Systems at Facebook Scale

• Utilizing the other 80% of your system's performance

• Flux: A Unidirectional Dataflow Architecture for React Apps

• Exploring the Reactive Extensions in JavaScript

I usually shun clichés like the plague, but could not resist this oft-quoted slogan that sums up what I like to call Psephological Cynicism.1 Psephology is the huge and growing branch of mathematics (with frequent distractions from sociologists, psychologists, political scientists, and allied layabouts) that studies the structure and effectiveness of polling and electoral strategies. Related domains include probability and games theory, although, as we’ll see, the subject has many far-from-playful implications. Indeed, there are depressing but valid proofs that no voting system fully guarantees “fair play.” Such non-existence theorems are common in most fields of mathematics: Gödel’s on the consistency proofs for certain arithmetical axioms, and Turing’s Halting Problem.2

Nevertheless, just as cranks continue to square circles and trisect angles, claims for new, perfectly democratic electoral schemes persist. As early as 1951, economist Kenneth Arrow shocked the world (but not me) by showing that non-democratic results can emerge from any democratic voting system, and this without conscious cheating or ballot-rigging. Paul Samuelson, who, like Arrow, won the Nobel Memorial Prize for Economics, commented, “The search ... for the perfect democracy, it turns out, is the search for a chimera, for a logical self-contradiction.”3 This, of course, leaves open the real-world, lesser-evil challenge: Is there a least unfair method? Promising candidates include Thomas Hare’s STV (single transferable voting) proposal from the 1850s (also known as the preferential vote) and many PR (proportional representation) variants.

The problem is not in the physical counting of votes, although we all know
of the dangling chadim (my preferred plural) in the Bush vs. Gore drama of Florida,
2000.4 Etymologists delight in the fact that the Latin *calculus* and
the Greek *psephos* each mean “small pebble,” indicating
the early, less controversial methods of counting sheep and goats, ayes and
nays. Or, depending on your agenda, vice versa?

At first sight, there seems no problem in determining a group’s preferences and then deducing a course of action to somehow maximize their general gruntlement.5 In simple “one-person-one-vote” situations, where an odd number of voters must select one of two candidates, a head count provides a sensible winner. (Proof is left to the reader. Hint: think “pros + cons = 2n + 1”). A close result will upset many (“We demand a recount!”), but assuming a “civil” society that pre-accepts the majority principle, the minority have no cause to complain.

Arrow’s impossibility theorem and subsequent work by Saari and others6 depend on various counterintuitive quirks regarding the non-transitivity of preferences. (But note that some of us start with sounder intuitions than others.)

Thus, quite simple examples can be constructed where pairwise majorities exist for “A beats B” and “B beats C,” yet C wins the election! You may notice a resemblance to the non-transitive class relationship “friend of” in C++. “X is a friend of Y” and “Y is a friend of Z” does not imply that “X is a friend of Z.” Where I live, though, X and Z have already shacked up and dropped Y.

Of more practical concern, perhaps, is the competence of those whose opinions might dictate important decisions, always assuming they take the trouble to vote. A frustrated Dr. Walter Martin once asked his class if they preferred ignorance to apathy. One pupil replied, “I don’t know and I don’t care.”

I was in Canada during its recent federal election. The perfect democratic paradise, one would imagine. Yet 40 percent failed to vote. The usual explanation was given: “What difference can my single vote make?” In the event, the results were close almost everywhere, leading to delicate shifts of power between the Liberals, Conservatives, NDP, the BLOC Québécois, and the Greens. Each party found something to rejoice in. Incumbent Liberal leader Paul Martin, having lost his overall majority, declared himself happy to have secured a “solid minority!” What emerged yet again was what Geoffrey Grimmett dubs “stochastic apportionment,”7 namely the injustices in assigning parliamentary seats on a winner-takes-all basis. For example, the Greens, with five percent of the popular vote, remain seatless. The Canadian Law Commission has prepared a huge white paper on electoral reform (http://www.lcc.gc.ca/en/themes/gr/er/er_report/er_report_toc.asp), hoping to correct this lack of fair apportionment. The plan is to hold a referendum to determine the preferred method of devising a referendum. O Canada! O Recursion!

Churchill’s view that “Democracy is the worst system, apart from all the others” is not entirely correct. There’s Plato’s benevolent “philosopher-king” with later Hobbesian refinements. This now deserves a chance given that, after modest introspection and hard-earned elitist omniscience, I offer myself as candidate. No need to vote. I can read your minds and know what’s good for you.

1. Yet another abbreviational overload for PC, alas, although on this occasion the “P” is silent as in bucket.

2. Briefly: there’s no general method of deciding whether an arbitrary program will terminate or not. Some have suggested Gates’s counter-example: termination (as in crash) is assured if the program runs under Windows.

3. Quoted in Hoffman, P. Archimedes’ Revenge—The Joys and Perils of Mathematics,” Fawcett Crest, New York: NY, 1988. See chapter 12, “Is Democracy Mathematically Unsound?”

4. The 1876 presidential election was even closer; an exact dead heat, in fact, at the Electoral College.

5. I support the effort to reestablish positive words that have lost ground to their peccable antonyms. My shevelled fans will surely be dainful.

6. Saari, Donald G. Geometry of chaotic and stable discussions. The American Mathematical Monthly III, 5 (May 2004).

7. Grimmett, G. Stochastic apportionment. The American Mathematical Monthly III, 5 (April 2004).

**LOVE IT, HATE IT? LET US KNOW**

feedback@acmqueue.com or www.acmqueue.com/forums

**STAN KELLY-BOOTLE** (http://www.feniks.com/skb/;
http://www.sarcheck.com), born in Liverpool,
England, read pure mathematics at Cambridge in the 1950s before tackling the
impurities of computer science on the pioneering EDSAC I. His many books include
The Devil’s DP Dictionary (McGraw-Hill, 1981) and Understanding Unix (Sybex,
1994). Under his nom-de-folk, Stan Kelly, he has enjoyed a parallel career as
a singer and songwriter.

© 2004 ACM 1542-7730/04/0900 $5.00

*Originally published in Queue vol. 2, no. 6*—

see this item in the ACM Digital Library

For more articles and columns like this, check out the latest issue of acmqueue magazine

Tweet

The blogroll is open to authors who have contributed to Queue.