Better Know a Theorem: Arrow’s Voting Theorem
The following is a book review I wrote thanks to a blog-based call for volunteers (technically I got paid with a free book). One of the main themes in the book is a theorem known colloquially as “Arrow’s Impossibility Theorem” for voting, which says that every voting system fails one of three simple axioms: non-dictatorship, agreement with unanimous pairwise comparisons, and “irrelevance of independent alternatives.” However, after reading the book, my view became that the last axiom is much too strong to expect any reasonable system to have. Also, this is the first math book I have ever read to involve Michele Kwan.
Review of Decisions and Elections: Explaining the Unexpected by Donald G. Saari, reviewed by David Pritchard
In Decisions and Elections: Explaining the Unexpected, Donald Saari gives a highly accessible introductory tour of decision theory: the study of mechanisms that amalgamate several separate preferences into a single preference (for example elections, in which voters’ preferences over candidates are combined). The book has an excellent style that combines a deep understanding of mathematics, good pedagogy, and lighthearted prose; Saari provides compelling arguments, high-level insights, and interesting applications.
The book combines the nice flavors of paradoxes and puzzles, important real-world applications, and a good sense of humor. There are a number of examples drawn from engineering and group dynamics which make interesting food for thought. One example is about a non-voting chair of a meeting: even if she has no vote and thus seems powerless, she can tremendously determine the outcome of an election (page 91). Another example (page 54) is that in an engineering company, when solving a huge problem like the design of an aircraft, divide-and-conquer/decentralization is not always a good idea, as it can introduce new problems due to having to combine the answers to the various parts.
The book is aimed at undergraduates and professionals according to its introduction, and it seems it would serve this purpose well. I think many other people (e.g. researchers from related fields) would appreciate the book as an interesting, relatively quick read. The pedagogical style mostly eschews formality except where it is needed. Saari introduces new terms only after providing enough background to warrant them; I wish all mathematics authors had this skill! An example of the level of discourse is that Saari takes the time to explain a proof by contradiction (“If the Moon were Purple,” page 47). Thus, for example, I think that the book would make nice secondary reading material for a game theory class aimed at people from other disciplines. I would urgently recommend any future teachers/researchers in decision theory to read this book.
Summary of Contents
The central formal result in the book is Arrow’s theorem (1951): any group ranking mechanism with at least 3 candidates is either a dictatorship, fails to respect unanimous pairwise rankings, or allows some pairwise rankings to interact with others, i.e. fails to have “Independence of Irrelevant Alternatives.” Saari gives a full proof, but defers it to the appendix due to its technical nature. Literature references also occur only in the appendix, giving the book high readability but also giving the interested reader pointers to more details. Proofs are usually sketched, and sometimes omitted. The flip-side of this approach is that sometimes the reader is not precisely sure what Saari means; although usually, ambiguities either can be clarified with a little effort of the reader, or are made clear later in the book.
Saari spends a considerable amount of time looking at the ramifications of Arrow’s theorem, and discussing variants. Over the course of the book, one accumulates the view that Arrow’s theorem should be thought of as saying that Independence of Irrelevant Alternatives (IIA) is too strong to expect from a reasonable voting system. Here are two nice results in this vein: first, even with a weaker version of IIA where we consider triples instead of pairs, Arrow’s theorem still holds (Section 5.4); second, if we replace IIA by a more detailed variant “Intensity of Binary Independence,” then Arrow’s theorem fails to hold (Section 6.5). The book acts in part as an introduction to some of Saari’s research from the last two decades, e.g. both of the aforementioned results come from publications of Saari and coauthors.
Sen’s theorem (1970) is discussed at length. In a decision mechanism, a given voter is “decisive” over two given alternatives if the mechanism’s ranking of those two always agrees with that voter. Then Sen’s theorem says that for any ranking mechanism with at least two decisive voters (over any two pairs of alternatives), that mechanism will sometimes disagree with a pairwise ranking agreed on unanimously by all voters. Saari phrases this differently: if unanimous pairwise rankings are to be respected, then the mechanism sometimes produces cyclic preferences (i.e., not a ranking). Saari gives a number of examples which illustrate applications — sharing an apartment, book censorship, and a stock-buying club — which at same time illustrate the most important ideas in the full proof of Sen’s theorem.
An explicit mantra in the book has to do with what goes wrong in the standard impossibility results of Arrow, Sen, and others. Saari notes that in many cases, a potential explanation is that we are disregarding valuable information: e.g. in Arrow’s theorem, we essentially throw away the voters’ full preference lists and focus only on pairwise rankings. We read on page 97 that “suspect outcomes can occur should the decision procedure ignore portions of the available information.” Saari notes more concretely that even irrational voters with cyclic preferences can submit pairwise rankings, but if we want to think rationally about a good voting procedure, we should certainly demand that the voters be rational!
Saari pinpoints a certain sub-structure, a “Condorcet tuple,” as the source of many problems. E.g. in a Condorcet triple, we have three players, one of whom prefers outcome A to outcome B to outcome C, another who prefers B to C to A, and a third who prefers C to A to B; then any global ordering upsets a majority of the voters in at least one pairwise comparison. Small modifications to this sort of example are fodder for the book, and Saari describes a certain result saying that indeed all impossibility results of a certain type come from modifications of Condorcet tuples, although I did not find his description of this result clear enough to properly parse.
If one were to read Saari’s book with the goal of choosing a voting system to put in to practice, the reader would be very persuaded to use the Borda Count: each voter ranks all n candidates and gives n points to their top-ranked one, n-1 to their second-ranked one, and so forth; then we order the candidates by total points. This avoids some problems of the usual plurality vote (where each voter contributes just one point to their favorite candidate) and has several other nice properties, for example the Borda Count is the only ranking mechanism which is never backwards in all pairwise comparisons, i.e. it ranks at least one pair of candidates in accordance with the majority of voters (Section 5.4.3). On page 193 Saari mentions a few other natural conditions that together get “close to creating an axiomatic representation of the Borda Count” although he later (in Section 8.3.2) tempers this by pointing out that axiomatic representations alone do not warrant a given protocol is best. For the election-designer, Saari’s book has no explicit advice (unfortunately) on what to do if more than one candidate should be elected, although there is certainly lots of implicit advice in the book. I should also note that, according to Wikipedia, the Borda Count is generally not used in practice, but replaced by other mechanisms with better properties; it would have been nice if Saari attempted to describe what sort of sophisticated voting methods are used in practice and what distinguishes them from the Borda Count.
Style and My Opinion
The book is sprinkled with a lot of specific small abstract examples, and also relevant real-world examples steeped in modern culture. The initial abstract examples in the first couple of chapters illustrate that even for a fixed set of preferences, different choices of reasonable-looking voting procedures can yield drastically different results; and often, the results of a vote seem clearly not to agree with the intent of the voters. Some of the real-world examples include Ross Perot’s Reform Party, the election of Jesse “The Body” Ventura, and scoring in professional figure skating (where IIA fails to hold). It is quite helpful to see these connections between theory and real life. The ubiquitous Prisoner’s Dilemma is given an atypical presentation — usually notions from strategic games are used but since this is the only strategic game in the book it would not make sense. I liked the Prisoner’s Dilemma example of two lanes merging on the highway, which I had not seen before. (Here two drivers may either be polite or a jerk, where each driver gets home faster as a jerk regardless of the other drivers, but two polite drivers get home faster than two jerks.)
I have a few general criticisms of the book. The lack of formality is a promising approach but sometimes important terms are used before they are introduced or informally defined. E.g. I was several times confused whether a “decision procedure” or “choice procedure” is supposed to give a ranking of candidates, or just a (possibly cyclic) list of pairwise rankings. Smoothing problems like this would save readers time. Likewise, there are a number of grammatical and numerical bugs which slow the reader down. At a higher level, I found the numerous small examples in the first couple chapters to lack structure, in the sense that I didn’t quite see how each one differed from the other, and so they appeared repetitive. Likewise, the discussion and corollaries surrounding the discussion of Arrow’s theorem in Chapter 2 seemed repetitive. Section 7.2 mentioned some nice theorems involving “strong” rankings; but since this term was never even precisely defined informally, that section only read like a mathematical parable, taking the details on faith.
The book sometimes has too many “scare quotes” in a small section. Let me take one funny quote from page 185 as an example:
All this “coordinate component” and “fractional voter” tech talk makes Theorem 10 seem impractical and restricted only to those weird “number-crunchers” whose sense of a “hot Saturday night” is checking new web features while designing a C++ program. Fortunately, this is not the case. What saves us from this nerdy fate is [a property of the Borda Count.]
To conclude I will mention the top reasons that I liked the book. It shed light on fundamental results that I never fully understood before (Arrow’s theorem, Sen’s theorem, Black’s single-peaked condition). I learned of new interesting fundamental theorems (e.g. the extensions of Arrow’s theorem to quasi-transitive or restricted preferences in Chapter 6, where a dictator is respectively replaced with an oligarchy or partial dictator). Its mantras gave new high-level perspectives which would be useful for guiding research or in practice. Finally, I enjoyed the folksy writing style; if you appreciate real-life (or plausible-fake) stories in mathematical discussion, then you probably would enjoy this book.
Count On The Swiss
Trivia question: pick a random person. Conditioned on the event that they live in a country with both French and English as official languages, what is the probability they live in Canada?
I took French classes in school from grade 5 to grade 12, most years of which were mandatory. But I have barely used French in real life; part of the reason I chose to come to Lausanne is that I could hopefully improve my skills a bit in this area.
A striking feature in French is how numbers are translated into words. The numbers 17, 18, 19 are pronounced “10 7″ (dix-sept), “10 8″ (dix-huit) and “10 9″ (dix-neuf)… the numbers 70, 80, 90 are pronounced as “60 10″ (soixante-dix), “4 20″ (quatre-vingt), “4 20 10″ (quatre-vignt-dix)… the ultimate weirdness is the last few numbers before 100, e.g. “99″ is “quatre-vignt-dix-neuf” or four twenties, a ten and a nine.
Swiss French behaves more decimally in this regard:
| 3 | trois | 30 | trente |
| 4 | quatre | 40 | quarante |
| 5 | cinq | 50 | cinquante |
| 6 | six | 60 | soixante |
| 7 | sept | 70 | septante |
| 8 | huit | 80 | huitante |
| 9 | neuf | 90 | nonante |
So 99 is “nonante neuf”! So far there were only two other words in Swiss French different than the (Paris) French I learned in school: a “cornet” is a plastic bag (I have no idea why) and a “natel” is a cellular phone (due to the name of the first cell phone company here).
Answer to trivia: a little more than half. According to the internet the only officially anglofrancophone countries are Cameroon, Canada, Rwanda, Seychelles and Vanuatu; Canada has a population of about 33 million and the other four combined have a total population of about 30 million.
Switzerland
I arrived yesterday in Switzerland to start a post-doc in Lausanne! I bypassed the well-documented vicious bank-residency-apartment cycle (I paid my first rent in cash and went off-campus where normal banks require an address+passport but not a residency card to set up an account) and am now well-situated in a boarding house in Ecublens, a 20 minute walk from my office. On my way down the hill (Ecublens is basically a hill) I saw the photo at right, which is I think a point multiplier for the European release of Grand Theft Auto.
I had some problems leaving—when the Swiss consulate mailed out my passport, it was lost (Canada Post had no data for the tracking number written on the Expresspost envelope). Dear Canada, I’m flattered, but you should let me leave, I promise to come back! In fact I am keeping in touch with home by listening to streaming radio episodes of CBC 2’s The Signal. In an unprecedented bureaucratic feat, I was able to apply for an urgent passport at the Kitchener passport office and get it with 1 day turnaround.
Living at a boarding house (an arrangement my research group’s administrator found) is new for me, and a little weird at first since I’m used to cooking a lot. However, it’s nice to meet a few other guys around my age living here and the owner of the house seems to cook very tasty food, so I won’t be in an extreme rush to find an apartment. Starting tomorrow I am off to the skiing town of Zinal, Switzerland for a 4-day workshop. In closing, here is a picture of a random horse I saw on the way to school.
Horsing around near Ecublens
Margarita’s
A while ago Waterloo got it’s first Mexican restaurant; the population has now doubled thanks to the restaurant Margarita’s in uptown Waterloo, at the corner of King and Erb. It seems to be aimed at the non-student crowd, as entrees are priced at about $15. I had some questions for the waiter who gave me some useful suggestions on the menu, and ended up getting two appetizers for about $20 after tax and tip. Overall it was pretty good, at least by Waterloo standards.
First I had tortilla soup: a chicken-based broth, with diced fresh mozzarella sitting at the bottom of the bowl, crispy tortilla strips on top, half an avocado nestled in-between, with sour cream and (Mexican?) oregano garnish. This gave me a run for my money by being really fun to eat — spoonfuls containing cheese and crispy tortilla and velvety avocado were much tastier than the sum of their parts. I see judges in Iron Chef America, Chopped, Top Chef etc sometimes playing with their food to get the optimal bite, and this is the first time in recent memory it happened to me. The cubes of cheese were not well-separated… they didn’t last as long as I would have liked since they usually got on top of my spoon in teams.
Second was a queso dip: Mexican cheese melted atop your choice of goodies. I was originally going to pick spicy chorizo sausage for the foundation layer, but then the waiter mentioned I could get both chorizo and mushrooms mixed together. This was good advice. The queso arrived in a little clay pot with house-made tortillas, and tortilla chips… I didn’t make full use of the chips since I had had them in the soup and as the free chips-and-salsa starter snack but the soft tortillas were perfect for tearing into chunks and filling with goodies.
The restaurant has somewhat of a bad review on urbanspoon, which I can relate to, since it’s pretty expensive for Waterloo. I also didn’t get any of the cactus-based dishes or margaritas they have to offer, so can’t speak for those. But if you and a couple of friends have a hankering for some melted cheese, this is the place to go.
Next up: I am going to Lausanne, Switzerland starting in mid-January… anybody know of a good Mexican restaurant there?
Pork Jello, Jamie Oliver’s a Jerk
Do: make ribs. I made Alton Brown’s recipe for three racks in the past few days. He goes on for a while in the episode Pork Fiction aka A Rib for all Seasons about how the “lip-smackin’ gelatin” is the key to the ribs. I kept some of the extra cooking liquids after making a batch: it’s now a porky jello!
Bill Cosby would be proud
Don’t: buy the Jamie Oliver Flavour Shaker. It is meant to crush spices, emulsify salad dressings, and make pastes, by shaking a ceramic ball with ingredients inside a hollow plastic pear-shaped thing. I bought one and use it infrequently but finally threw it out as the ball constantly chips the plastic inside.
Do: have a tasty holiday!
Epic Wins and a Fail
I defended my PhD thesis one week ago! (Successfully!) Although I am not finished until I complete my thesis revisions, being past the most stressful 2 hours is excellent and I enjoyed getting to see some talks from visitors on the same day.
Other epic wins:
- I got to visit Pittsburgh’s Carnegie Mellon University 2 weeks ago to visit my old friend Andrew and give a talk at the CS Theory Lunch (free burrito included)
- They have seriously good hamburgers and bacontinis
- The UW Grad Student Association website no longer needs to be manually updated every time we leap ahead/fall back for Daylight Savings Time thanks to WordPress being awesome and a few minutes of additional php hacking on my part
- Saw a holiday brass concert and some roof-based fiddling in Toronto last week, the first play I have seen in quite a long time. According to Wikipedia, the original Fiddler ran more than 3000 times! I get bored of doing something three times…
Epic fail: I lost one glove over the weekend! Have you seen it?
Math Circles
The University of Waterloo’s CEMC holds Math Circles in which they invite local grade 6-12 kids to come to the university one evening a week for math enrichment activities. In the past years I have participated for 2-3 weeks per year, running sessions on the topics of Game Theory and Conics (ellipses, parabolas, etc). This year my topic is Graphs! Here are six small graphs (you can ignore the numbers on the edges):
The first session, yesterday, was very enjoyable (at least to me, but it also seemed to get positive feedback from the other participants as well).
In my experience, it can be tricky to guess the appropriate level of discourse when preparing the lessons, mostly since I have no prior experience with most of the kids in the session. This caused me to “lose” about a 1/3 of my first session to covering background material: proof by induction. (It’s not really a “loss” because I would say that the time spent was still fun for me and beneficial for the students.)
In the course of developing the online notes to accompany the presentation, I wanted to see if there was a good resource online with an appropriate explanation of “proof by induction.” There are certainly hundreds of books including the subject, and given the size of the internet, one might conclude that there are thousands of articles online about induction? Well, it doesn’t quite seem to be that many. I found that Wikipedia had the best all-purpose description (with an example, and without getting too abstract) and there is another online at Carnegie Mellon University. I was hoping to find something good at the Art of Problem Solving website but their description was a little too terse. It looks like there is still some room on the internet for well-written mathematical enrichment material, I am glad the Math Circles content is available to help fill that hole.
Movember
Did you know that 1 in 6 men will get Prostate Cancer? If you are a man with a butt, or know a man with a butt, you should take notice that this is the month of MOvember, in which mustachioed gentlemen aim to “change the face of men’s health” by growing moustaches to promote awareness.
If you want to donate to the cause, visit http://ca.movember.com/mospace/423838. Incidentally, also let me know if you want to hire me to drive your truck.
Bound to Be a Good Time
I got my (draft) thesis printed and bound this week on Waterloo’s “espresso” book printer. It was fast, convenient, and cost about $10/copy (it turns out to be 60% the cost of printing it the normal spiral-bound way at the print shop). The only drawback I found is that there are still some bugs in the printing process: several fraction lines didn’t show up in the printing. Here’s a youtube of the printer in action.
Update: now with bacon
Comics Are Relevant
Evidence #1: “History’s Chumps” by Dinosaur Comics, after recent at-length discussions of chumpism. (Click for full size)
Evidence #2: “Backup Face” by Toothpaste For Dinner, which was posted the very night I almost lost my non-backed-up laptop in a bar, with my nearly-complete thesis on it.
There is a comic called “PhD Comics” which is not relevant, somehow, ever! So in their place I am going to give “Banana Dogs” by Superpoop which, while also not relevant, is awesome.
