Not Impossible

There are two main impossibility results in voting theory: Arrow's impossibility theorem (AIT), and the Gibbard-Satterthwaite theorem (GST), and a few other results that generalize them. I have not gone over other results such as the Muller-Satterthwaite Theorem or the Sen theorem, but my suspicion is all these results are mathematically precise, correct, and unfortunately misleading.

It is the misleading aspect that I want to address here. I'm focusing on AIT and GST because I am familiar with them and because they are reasonably well-known. I first encountered AIT in an undergraduate discreet mathematics course, and while I successfully proved it as an assigned exercise, so I have no doubt it is true, I really did not like the result. I felt there must be something wrong with it, but it took me decades to get back to it, and more time to figure out both what bothered me about it and what could be done.

Arrow's impossibility theorem and the Gibbard-Satterthwaite theorem both present difficulties for collective choice. However, while both theorems are true, they are not as limiting as I once thought. I deal with them in the order I encountered them. First Arrow, then Gibbard-Satterthwaite.

There is much work available on Arrow's impossibility theorem. The work I used as my source is (Arrow [1951] 2012).

For reference, Arrow's impossibility theorem (technically his general possibility theorem), sets out the problem of defining a social welfare function for collectively making social choices which takes as input a collection of individual preference orders over a set of alternatives and produces as output a social order of that set.

There is an immediate problem with the definition of Arrow's social welfare function. The need is to pick a single option for the social choice, but his social welfare function is defined to return an ordering. The reason this is a problem is the likelihood that any significant social need will have trade offs that make any solution a matter of balancing multiple issues. It may well be possible to select a good collective option for a first choice, but the possibility of finding a defensible second, third, or fourth choice gets progressively lower. The idea of a full ordering that makes sense is about the same as defining a linear ordering of the points in an \(2\)-dimensional space that preserves topology.¹ So Arrow's specifications for his social welfare function are too ambitions from the start.

Arrow then lays out five conditions that a social welfare function should satisfy. These conditions are:

Generality

This essentially prevents the restriction of voter preferences. It states the set of alternatives must include a subset of three alternatives with all possible individual orderings allowed. There are thirteen possible orderings: six strict orderings (no indifference allowed) with \(3\) choices for first place times \(2\) choices for second place, three orderings with a clear first place and a tie for second place, three orderings with a tie for first place and a clear third place, and one order with a three-way tie for first. This generality condition is one that I fully support and consider quite reasonable. But it should be noted that this condition is what allows cycles to exist.

Positive Association of Social and Individual Values

This means if two ballot sets \(B\) and \(B^{\prime}\)are given as input to the social welfare function \(W\)where the only difference between the sets is that one voter has raised the position of one alternative \(A\) in ballot set \(B^{\prime}\), then the ranking of \(A\) in \(W(B^{\prime})\) must be at least as high as \(A\)'s ranking in \(W(B)\). Or in English, more support should not hurt an alternative.

Independence of Irrelevant Alternatives

This is intended to disallow a flaw in the Borda count in which the presence or absence of a losing alternative can change the outcome. In essence, it states the pairwise social preference order between alternatives \(x\) and \(y\) should not be affected by the presence or absence of an alternative \(z\).

Citizens' Sovereignty

This means the outcome cannot be imposed by the voting system. In essence, it means for any possible preference relation \(P\),there must exist a ballot set \(B\) such that for social welfare function \(W\), \(W(B)=P\).

Nondictatorship

This simply means that the social welfare function should not be dictatorial. That is there should not be any individual voter whose preferences override those of the rest of the group.

What Arrow proved is that these five conditions are inconsistent with his definition of a social welfare function when there are two or more voters and three or more alternatives.

Arrow also proved when there are only two alternatives, majority decision does satisfy these conditions with the exception of Condition 1 which needs to be modified.

The major take-away, however, is that cycles are almost always a possibility and any collective decision system must be able to cope with them. My preference for this, and what is essentially implemented in SAVE, is to go back to the voters and have the collective deal with the cycle.

For a much more detailed version of AIT and my critiques of it, see Arrow's Theorems.

Both Allan Gibbard (Gibbard 1973) and Mark Satterthwaite (Satterthwaite 1975) start with Arrow's conditions, with the modification that Arrow's social welfare function (defined to return a collective preference profile) is replaced by a social choice function that returns a single chosen alternative. This modification hides the problem of cycles but exposes a different problem. That problem is the situation where there is a difference between an honest or sincere ballot and a tactical or strategic ballot.

The idea of an honest / sincere ballot is essentially what you would put on your ballot if your ballot was the only one that counted. In contrast, a tactical / strategic ballot requires some knowledge or expectation of how everyone else will be voting, and realizing both that if you marked your ballot honestly the election would result in one outcome, but that if you marked your ballot a different way you might be able to get a different outcome that you like better than what would happen with your honest ballot. A voting system in which there can be a difference between an honest and a tactical ballot is manipulable (Gibbard's term), and a voting system in which an honest ballot is always the best option is strategy-proof (Satterthwaite's term) or straight-forward (Gibbard's term).

The Gibbard-Satterthwaite theorem states that any voting system in which there are three or more alternatives is either manipulable or dictatorial.

Whereas the cycles underlying AIT are real and need to be dealt with (as SAVE does), manipulability is a bit more subtle. SAVE is neither manipulable nor dictatorial at the round level because it limits voter options to binary choices. Yet it also in some sense encourages and solicits manipulation in each focus round when considering ballots as normal approval votes.

To see how this works, it is helpful to have a bit more background regarding modeling electorates, and some insights from spatial models.

The main result from the Gibbard-Satterthwaite Theorem is that under the same constraints that Arrow proposed, it is impossible for voters to know how to fill out their ballot in a way that best supports their personal preferences. This is a stronger result than Arrow's because it is independent of the existence or non-existence of majority cycles.

• Home