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.



Felix Gilman, The Half-Made World – A rather stunning and harrowing fantasy/western (don’t think Jonah Hex). I didn’t like it quite as much as Cosma did, but I couldn’t put it down, so that is something.

Jane Margolis, Stuck in the Shallow End : Education, Race, and Computing – really insightful look at the race-based gap in access and enrollment in computer science classes in 3 very different LA high schools. Margolis and her discuss how the actions of teachers, counselors, and administrators create barriers and disincentives that lower black and Latino enrollment in computer sciences when they are available, and that gut computer science classes for everyone in favor of computer skills classes.

John Crowley, Love & Sleep – second book in the Aegypt cycle. I found it more self-indulgent and flatter than the first one, but maybe it’s because the characters are not new to me. The writing is, as always, beautiful, but I was less excited than I was by The Solitudes.

Ian Hacking, The Emergence of Probability – a slim book about early ideas about probability and ending at Bernoulli and Hume’s problem of induction. Hacking traces how “probable” went from meaning “approved of by experts” (as in “probable cause”) to a more aleatoric interpretation, and at the same time how problems such as computing annuities brought forth new foundational questions for philosophers and mathematicians. A key figure in this development was Leibnitz, who worked on developing inductive theories of logic. The last few pages sum it up well — the early development was spurred by changes in how people thought of opinion and on what it should be based. “Probability-and-induction” required a different change in perspective; causation had to be thought of as a problem of opinion rather than of knowledge. I found the book fascinating and pretty easy to read; nice short chapters highlighting one point after the other. Hat tip to Marisa Brandt for the recommendation.


Yes yes yes, all my posts are link posts now. I swear, I’ll get back to something more interesting soon, but I always promise that.

People post funny things to ArXiV.

Razib discusses new studies of the genetic origin of Indians.

Tips for food photography. I seem to know several food bloggers now.

A new study about bullying.

The University of Michigan is allowing longer tenure processes. This is in part to address the pressures of getting tenure and starting a family at the same time, but also particularly the culture in the medical school, where “very few faculty in medical schools actually take advantage of such policies [to halt the tenure clock].” The academic Senate Assembly was opposed to the change.

CISE is hiring

I got this in my email:

NSF’s Directorate for Computer and Information Science and Engineering (CISE) seeks candidates for the position of Deputy Assistant Director. The incumbent participates with the Assistant Director in providing leadership and direction to the staff and activities of the directorate and in coordinating activities with the Directorate’s senior managers. The Deputy Assistant Director also serves as a key assistant to the Assistant Director in all phases of the Directorate’s activities and programs.

The full ad is here.

Linkage part deux

Most of these are stolen from MetaFilter.

Welcome back to public blogging, Dan.

All about time zones.

Musical instrument samples. My first UROP at MIT was at the Media Lab, where I helped record instrumentalists as part of a musical instrument identification system. Paris Smaragdis was there at the time, and now he is at UIUC where he has a lot of cool audio demos. There are also some great clips Inside the Music Library at the BBC.

Ridiculous computer interfaces from movies.


I’m blogging from Chicago, where it is a balmy 42 degrees but sunny. Whither spring, I ask! Actually, I’m not blogging so much as linking to a bunch of stuff.

For San Diegans, the SD Asian Film Festival Spring Showcase is going on. It looks like I’ll miss a lot of it but I might try to catch something at the end of the week.

Less Pretentious & More Accurate Titles For Literary Masterworks — funny but possibly NSFW.

This home-scanning program seems creepy, regardless of the constitutionality issues.

Unfortunate headlines strike again.

I really like scallion pancakes. I’ll have to try this out when I get back to San Diego.

I agree that this video is awesome. Yo-Yo Ma and Lil Buck. I think that dude is made of rubber. And steel.

Tom Waits was induced into the Rock and Roll Hall of Fame. I just hope I get to see him live some day.

Some things to skim or read from ArXiV when I get the chance:
Sequential Analysis in High Dimensional Multiple Testing and Sparse Recovery (Matt Malloy, Robert Nowak)
Differential Privacy: on the trade-off between Utility and Information Leakage (Mário S. Alvim, Miguel E. Andrés, Konstantinos Chatzikokolakis, Pierpaolo Degano, Catuscia Palamidessi)
Capacity of Byzantine Consensus with Capacity-Limited Point-to-Point Links (Guanfeng Liang, Nitin Vaidya)
Settling the feasibility of interference alignment for the MIMO interference channel: the symmetric square case (Guy Bresler, Dustin Cartwright, David Tse)
Decentralized Online Learning Algorithms for Opportunistic Spectrum Access (Yi Gai, Bhaskar Krishnamachari)
Online and Batch Learning Algorithms for Data with Missing Features (Afshin Rostamizadeh, Alekh Agarwal, Peter Bartlett)
Nonuniform Coverage Control on the Line (Naomi Ehrich Leonard, Alex Olshevsky)
Degree Fluctuations and the Convergence Time of Consensus Algorithms (Alex Olshevsky, John Tsitsiklis)

Most amusing rejection so far

Thank you for applying to the Department of Computer Science at Columbia University. I am sorry to tell you that we will be unable to offer you a position this year. The Computer Science department’s recent call for applications for new faculty members generated several hundred responses. Our delight at receiving so many applications was muted by the realization that we would be unable to talk with a large number of excellent candidates.

phone interviews

Suresh posted a few months ago about academic phone interviews and asked “maybe it’s because there are more people chasing each slot and so these filters are more necessary now?” I’ve had a few phone interviews this year, with some turning into on-campus interviews and some not. Although it’s considered a thing that only smaller departments will do, I actually think the phone interview has a lot of positive features that make sense for lots of departments:

  • You can screen a much larger set of candidates — it’s probably quite difficult to decide on 6 people to invite for on-site visits out of 300 applicants. Phone interviews let you screen out those who seem under-prepared, un-interested in your job (i.e. they applied just because it was there). If someone’s research is not really in your area (e.g. a department with no information theory people), it is a good chance to get the candidate to explain it to you rather than puzzling through the research statement. This also saves money.
  • You can talk to unknown candidates — of course if your advisor is great friends with someone at school X then chances are that person will know your name (or at least your advisor’s name on your CV). But hiring people you know personally may be a suboptimal strategy long-term, so phone interviews let you broaden your search.
  • It can be done in a decentralized manner — you don’t need the whole committee to be there on the phone call. Divide and conquer!
  • If your search is pretty broad, then you can talk to a few people in several different areas. This means you can find the best-sounding candidate in each area and then the committee can try to compare good apples and good oranges instead of the whole motley cornucopia.
  • From the interviewee’s perspective, you get to learn quite a bit more about the department, its priorities, and the culture from a 30 minute chat on the phone. You get this from the questions they ask as well as the questions you get to ask. That’s definitely the sort of thing which you can’t get from the website.
  • It provides good feedback for the interviewee — if you get a phone interview, you know you’ve made some sort of list (medium, short, whatever) and that knowledge is helpful, given the uncertainty mentioned in my previous post.

That’s not to say I necessarily enjoyed all of the phone interviews; the phone is an awkward medium. But I do think on balance that they are a good way to improve the search process from the employer and job-seeker side. Besides, I’m not sure I look my best in Skype video chats…