So as mentioned in an emergency edit, the version of the Gibbard-Sattherthwaite Theorem for non-deterministic voting systems that I mentioned in my last post is wrong. The set of voting systems permitted by it is in fact notably larger than I claimed (I got my version of it from this rangevoting.org post. Ah, trusting third party reporting of science by people with an agenda).

So now I’m reading the original paper. I’m struggling a bunch with the details, but I at least understand the result and think I can see my way towards constructing an alternate proof that makes more sense to me.

Here is the true version of the theorem as near as I can tell:

Consider a voting system under the following setup:

1. There are N candidates
2. Each of M voters must submit a ballot consisting of a full ordering of the N candidates
3. The votes are aggregated in some way to produce a lottery over the N candidates

Further, assume that voters are Von Neumann-Morgenstern rationalists with full preferences over lotteries arising from expected values of utility functions, and that they have strict preferences amongst the candidates (i.e. there are no two candidates to which they assign the same utility).

A voter’s ballot is honest if whenever they rank candidate x better than candidate y their utility function \(U\) has \(U(x) > U(y)\).

A voting system is strategy-proof if there are never circumstances where a single voter can change their vote from an honest one to a dishonest one and get a lottery they strictly prefer in expected utility.

The theorem is that any strategy-proof voting system is a probabilistic mixture of the following types of system (that is, we choose from any number of items of this type with fixed probabilities independently of the votes cast):

1. Fixed, meaning it always elects a specific candidate
2. Unilateral, meaning there is a single voter such that any other voter can change their ballot without affecting the outcome
3. Duple, in the sense that there are only two candidates it can elect (fixed is a special case of this where it can only actually elect one)

Three examples of this are sortition (it is an equal mixture of each of the possible fixed systems), random ballot (it is an equal mixture of each of the unilateral systems which elect the candidate’s top choice) and random pair (it’s an equal mixture of majority vote between each of two possible pairs of candidates).

But these aren’t the only examples. For example, a system which randomly chooses between a fixed voter’s top k choices is unilateral and strategy-free. So is a system which chooses between two fixed candidates, picking a candidate with probability equal to the fraction of people who prefer that candidate. There is a lot of flexibility in terms of how you construct the unilateral and duple systems which is ignored by random ballot and random pair.

How might we prove the theorem? Well… I haven’t quite understood the proof yet, truth be told. I’ve got bits of it lying disassembled in pieces hanging around on the shop floor of my brain, and I’m getting there, but so far I don’t have anything coherent enough to blog about. Once I do I’m hoping to try to slim it down and blog about it. We’ll see. For now though, I just thought it was important to have a correct statement of the theorem online.