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
[email protected] 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—
Comment on this article in the ACM Digital Library
Jinnan Guo, Peter Pietzuch, Andrew Paverd, Kapil Vaswani - Trustworthy AI using Confidential Federated Learning
The principles of security, privacy, accountability, transparency, and fairness are the cornerstones of modern AI regulations. Classic FL was designed with a strong emphasis on security and privacy, at the cost of transparency and accountability. CFL addresses this gap with a careful combination of FL with TEEs and commitments. In addition, CFL brings other desirable security properties, such as code-based access control, model confidentiality, and protection of models during inference. Recent advances in confidential computing such as confidential containers and confidential GPUs mean that existing FL frameworks can be extended seamlessly to support CFL with low overheads.
Raluca Ada Popa - Confidential Computing or Cryptographic Computing?
Secure computation via MPC/homomorphic encryption versus hardware enclaves presents tradeoffs involving deployment, security, and performance. Regarding performance, it matters a lot which workload you have in mind. For simple workloads such as simple summations, low-degree polynomials, or simple machine-learning tasks, both approaches can be ready to use in practice, but for rich computations such as complex SQL analytics or training large machine-learning models, only the hardware enclave approach is at this moment practical enough for many real-world deployment scenarios.
Matthew A. Johnson, Stavros Volos, Ken Gordon, Sean T. Allen, Christoph M. Wintersteiger, Sylvan Clebsch, John Starks, Manuel Costa - Confidential Container Groups
The experiments presented here demonstrate that Parma, the architecture that drives confidential containers on Azure container instances, adds less than one percent additional performance overhead beyond that added by the underlying TEE. Importantly, Parma ensures a security invariant over all reachable states of the container group rooted in the attestation report. This allows external third parties to communicate securely with containers, enabling a wide range of containerized workflows that require confidential access to secure data. Companies obtain the advantages of running their most confidential workflows in the cloud without having to compromise on their security requirements.
Charles Garcia-Tobin, Mark Knight - Elevating Security with Arm CCA
Confidential computing has great potential to improve the security of general-purpose computing platforms by taking supervisory systems out of the TCB, thereby reducing the size of the TCB, the attack surface, and the attack vectors that security architects must consider. Confidential computing requires innovations in platform hardware and software, but these have the potential to enable greater trust in computing, especially on devices that are owned or controlled by third parties. Early consumers of confidential computing will need to make their own decisions about the platforms they choose to trust.