EVT / WOTE 2011

This week I attended EVT/WOTE ’11, a workshop on voting, technology, and trustworthiness co-located with the USENIX Security conference. I phased in and out of the workshop, which had a number of different session themes:

  • “E2E”, or end-to-end voting
  • empirical studies of real elections direct-recording electronic voting machines (DREs), forensics for them, and their impact on the reliability of election outcomes
  • studies of accessibility issues, either to polling places or for different voting technologies
  • new proposals for voting systems
  • auditing and metrics for existing election systems

I pretty much work on the last one, so while some of the panels were quite interesting, some technical talks were a little beyond me. Dana Debeauvoir, the Travis County Clerk (where Austin is) gave a keynote about how she thinks technologists and elections officials can work together, and rather bravely put forward a proposal for an electronic voting system to be used at the county level. There were lots of comments about that, of course.

Theron Ji gave a nice talk about how write-in marks are (or are not) properly counted by optical scan machines. People often forget to fill in the bubble saying they are doing a write-in, which can have pretty disastrous effects, as San Diego politician Donna Frye found out. Gillian Piner reported on a survey she did of vision-impaired voters, asking them what they want for accessibility technologies. Imagine that, asking them what they want!

The two talks of most interest to me were by David Cary and Tom Magrino, both on the margin of victory for IRV elections. Cary presented a method for estimating the margin based only on the tabulation of first-choices in each round, whereas Magrino presented an exact calculation that involved solving many integer linear programs. The scaling is not so great with the number of candidates (exponential), but for the kind of IRV elections we see in the US it was definitely doable. Margin calculations are important for developing auditing algorithms (on which I will write more once my paper is done). Philip Stark gave a plenary lecture on auditing which I missed part of due to a conflict with a parallel workshop.

There were also some interesting panels. The most contentious one was on internet voting, which I missed much of but the discussion went over by an hour so I think got the gist of it. Some people are afraid of voting over the internet, but the crypto people think it can be made safe. The panel on the the Sarasota House race in 2006 tried to hone in on the reason for the problems with undervotes in that contest. A lot can be explained by the design of the ballot, proving again that user interface and graphic design is really important!

The rump session was, as always, a mixture of amusing and technical and dry. The real highlight was probably David Bismark, who seems to have antagonized someone who has a new voting system involving moon projections. Wow.

California Elections Code on auditing

From Section 15360:

(a) During the official canvass of every election in which a
voting system is used, the official conducting the election shall
conduct a public manual tally of the ballots tabulated by those
devices, including vote by mail voters’ ballots, cast in 1 percent of
the precincts chosen at random by the elections official. If 1
percent of the precincts is less than one whole precinct, the tally
shall be conducted in one precinct chosen at random by the elections

In addition to the 1 percent manual tally, the elections official
shall, for each race not included in the initial group of precincts,
count one additional precinct. The manual tally shall apply only to
the race not previously counted.

Additional precincts for the manual tally may be selected at the
discretion of the elections official.

Clearly this is not written by a statistician. Counting 1% of precincts “chosen at random” is hardly clear, and also doesn’t tell you too much about how many ballots you are going to count.


Shing-Tung Yau and Steve Nadis, The Shape of Inner Space — This book was about the Calabi conjecture, Calabi-Yau manifolds, string theory, and all that jazz. It’s supposed to be for a general/lay audience, but I found it rather daunting and often confusing. Perhaps I know just enough math to get confused, whereas other readers might gloss over things. I definitely would not recommend it to those without some serious mathematical background (like a few college classes). That being said, I found it pretty interesting, and now I know (kind of) what a Calabi-Yau space is.

Donald G. Saari, Decisions and Elections : Explaining the Unexpected — This sums up a large chunk of the analysis of social choice problems and voting systems done by Donald Saari. It’s a bit overwritten for my taste and veers between some mathematical formalism and a chatty form of argumentation. I don’t think I fit in the right “audience” for this book, which is part of the problem. It discusses Arrow’s Theorem and Sen’s Theorem via a bunch of examples and spends a fair bit of time on the “paradoxes” and perversities of different choice systems. The chattiness makes it feel less than systematic. Towards the end Saari puts on more of an advocate hat and argues that symmetry (in a particular sense) is a desirable property of election systems and puts out a case for the Borda count. That in a sense is the least convincing part of the book. This might be a good present for a precocious high school student, since the math is not so complicated but there are a lot of ideas to chew on in there.

Hannu Nurmi, Voting Procedures under Uncertainty — This also fits into the “slightly math-y books for political scientists” genre, so I found it insufficiently math-y. It’s a survey of different models of uncertainty in voting procedures and a survey of the work in that area. As such, it discusses alternatives to “traditional” social choice theory including Euclidean models of preference and so on. There’s a little more “survey” and less “integrating the different perspectives” but that’s ok. I am not sure who should read it, but it did point out some new literatures of which I had previously been unaware.

Moez Draif and Laurent Massoulié, Epidemics and Rumors in Complex Networks — A nice and compact introduction to rumor-spreading processes, including branching processes, small world graphs, SIS/SIR type models, and concluding with some models for “viral marketing.” I really liked this book because it was concise and to the point, but others may find that it lacks some context and connections to literature with which they are familiar. It doesn’t feel like a tutorial in that respect, but it’s self-contained and great for someone who has seen some of the material before but not all of it.

John Mortimer, Rumpole and the Primrose Path — Reading Rumpole short stories is kind of like relaxing in a pair of old slippers. Enjoyable, but probably not his best work.

Quote of the day : squabbles

I am writing a paper at the moment on some of my work with Steve Checkoway and Hovav Shacham on voting, which has involved a pretty broad literature search in social choice theory. I came across this quote about approval voting (AV) as an alternative to plurality voting (PV) in the paper Going from theory to practice: the mixed success of approval voting by Steven J. Brams and Peter C. Fishburn (Soc Choice Welfare 25:457–474 (2005)):

The confrontation between theory and practice offers some interesting lessons on “selling” new ideas. The rhetoric of AV supporters has been opposed not only by those supporting extant systems like plurality voting (PV)—including incumbents elected under PV—but also by those with competing ideas, particularly proponents of other voting systems like the Borda count and the Hare system of single transferable vote.

We conclude that academics probably are not the best sales people for two reasons: (1) they lack the skills and resources, including time, to market their ideas, even when they are practicable; and (2) they squabble among themselves. Because few if any ideas in the social sciences are certifiably “right” under all circumstances, squabbles may well be grounded in serious intellectual differences. Sometimes, however, they are not.

I don’t think it’s particular to the social sciences…

On another note, the IEEE adopted AV at some point but then abandoned it. According to a report on the (very partisan) range voting website, there are shady reasons.


The Gangster We Are All Looking For (lê thi diem thúy) — This is a fragmented and short narrative of a young Vietnamese immigrant to the US and her time growing up in various neighborhoods in San Diego. It’s the KPBS One Book, One San Diego selection so there were 25 copies at the library. The little vignettes are fleeting but touching, but in a sense you don’t feel that the narrator is particularly introspective, at least not in a direct way. However, I think it was definitely worth reading, if for no other reason than to hear her unique perspective.

The Terrible Privacy of Maxwell Sim (Jonathan Coe) — A satirical novel which came recommended but which in the end I felt cheated by. Maxwell Sim embarks on a new job after a recent divorce and few months off for depression, and ends up learning new things about himself and his family. He’s a bit of a loser, to be honest, but in the end you kind of feel for him as he muddles through emails, old letters, facebook, and the like. What is a big cheat is the ending, in which the author (!) appears. Blech.

Symmetry and Its Discontents (Sheridan Zabell) — A lovely collection of essays on the philosophy, history, and mathematics of symmetry assumptions in problems of induction. The last two chapters are especially good as they discuss a bit of the history and background of such things as Good-Turing estimators and exchangeable partition processes. I learned about this book a while ago from Susan Holmes at the AIM Workshop on estimating probability distributions.

Electronic Elections (R. Michael Alvarez and Thad E. Hall) — A short but dense book that makes the case for a “risk management” approach to assessing the value of electronic voting machines. Electronic voting machines have all sorts of benefits, including better accessibility for the disabled, no “hanging chads,” and so on. But they are also woefully unsecure and hackable, as has been demonstrated time and again by computer security folks. Alvarez and Hall feel like the CS folks are being unfair and think (in a very nebulous way) that the benefits outweigh the risks. I found the data about voter confusion and error rates, etc. interesting, but I think the authors completely miss the point of the security community’s critique of electronic voting systems. Designing a shoddy electronic voting system is bad, regardless of the purported benefits.

Instant Runoff Voting, STV, AV, and the like

One thing I’ve gotten interested in lately is Instant Runoff Voting (IRV), which is an alternative vote tabulation system to our “first-past-the-post” system here in the US. It’s also known as the Alternative Vote (AV), and in multi-winner elections, the Single Transferrable Vote (STV). I’ll probably blog a bit on-and-off about this topic, but for starters, there’s a lot of activism/partisanship when it comes to promoting different voting systems. Unfortunately, almost all voting systems under consideration fall victim to Arrow’s theorem, which says, basically, that you can’t have a method of aggregating people’s preferences that satisfies a bunch of desirable criteria (under some assumptions on how preferences are given).

IRV or STV is used to elect Representatives in Australia, and the Australian Electoral Commission has a nice video explaining the process. It also mentions the election monitors, which are called scrutineers. That always cracks me up. But I digress. AV has come up more recently in the UK, where people are thinking of using it for Parliamentary elections. The pro-AV side has its videos as well, which seem designed to appear to the beer-lovers out there. However, the polling on its popularity seems to indicate that the switch to AV will not happen. There’s opposition to AV from different sources, and even some small parties don’t think it will make a difference.

I’ve gotten interested in IRV because it’s used in California for some local elections. The recent mayoral election in Oakland was run via IRV, which requires a bit of voter re-education. The outcome of the election was quite interesting, wherein Don Perata, who won the largest share of first-choices, ended up losing because Rebecca Kaplan was eliminated and the second- and third-choices went to Jean Quan. This is exactly the kind of thing proponents of IRV want.

What is less clear is how the mathematics of counting IRV works, and how sensitive the counting process is to errors. A lot of people have written about the former, but there has been less work about the latter, and that’s something I’ve started working on, because auditing the outcome of elections is an important step in ensuring voter confidence in the results.

UPDATE: As Oxeador points out below, Arrow’s Theorem is actually a statement about producing a total order of all the candidates that satisfies a given set of criteria, not about single-winner elections. In particular, if you treat the IRV ordering as the order in which the candidates are eliminated, then IRV would fall under Arrow’s Theorem.


The Hakawati (Rabih Alameddine) — an expansive novel, framed by the story of a son who has gone to the US coming back to visit his dying father in Lebanon. The sharply drawn tension and anguish of the present shifts rapidly through old family stories, to the story of Baybars (and parts in between). It’s hard to pick up the strands initially, but it’s a rewarding read once you get into it.

A Short History of the American Stomach (Frederick Kaufman) — a quick read, repeats of some stories from Harpers I had read. It might appeal to people who like Sarah Vowell’s writing, but it’s too heavy on snark for me. Good for picking up some cocktail-hour conversation pieces, if you enjoy talking about the puking habits of Puritans at cocktail hours.

The Magicians (Lev Grossman) — I enjoyed this book, even though some people call it Hipsters in Narnia. It is a bit of that, but I couldn’t really put it down (= brain candy). Recommended for those who want a jaded view of Harry Potter.

Ghostwritten (David Mitchell) — I read this one after reading Cloud Atlas, which I absolutely loved. It’s written in a similar style, with interlocking stories, but more direct storytelling going on than, say, if on a winter’s night a traveler. Maybe I just like the relay-race novel. In any case, definitely engrossing, if a bit… bleak? It’s simultaneously lush (descriptively) and bleak (psychologically).

Gaming the Vote (William F. Poundstone) — a popular nonfiction book about elections, the spoiler effect, and the history of voting systems. It’s larded with examples of elections from US history and makes for an engrossing read. Most of the focus is on the weaknesses of first-past-the-post and other methods of determining winners, but it’s a nice accessible read.