Manipulability Blessing

The two major "impossibility" results in voting theory are Arrow's impossibility theorem (AIT) and the Gibbard-Satterthwaite theorem (GST). AIT states, correctly, that a specific set of seemingly reasonable conditions for a social welfare function are inconsistent. GST states, also correctly, that under the same basic conditions as AIT, any social welfare function must be dictatorial, trivial, or manipulable.

Both of these theorems are true, but they do not prove impossibility. There is an unstated assumption in both AIT and GST that there is only one round of input to a social welfare function. The refutation of that unstated assumption is the key to building a good and reliable procedure for making truly democratic social welfare decisions. In fact, there are already collective choice systems in use with multiple rounds. Any system that starts with more than two initial choices, narrows the field down to the top two choices, and then has a runoff election to determine the final winner, is an example of a collective choice process with multiple rounds of input.

However, these filter and runoff systems don't go far enough.

To understand why, we need to look a bit more closely at what these two theorems actually say, and then look at what we can do when we allow multiple rounds.

Note on terminology: For the purpose of this discussion, and for most of the site in general, we are considering collective choice where the choice set consists of documents, not individuals. Our reason is the set of documents, even when constrained to a fairly specific type of document such as an annual budget for the US Federal government, has a ridiculously large number of possible variations. Each document in the initial choice set is typically reflective of the will of only a small subset of the voters. This means even the collectively best of our initial choices can be far from our actual collective will. As our collective preferences, expressed as vote counts, become clearer, it is trivially easy to add new documents to the choice set that can be more aligned with our collective will. We will therefore use motion as the noun for the items in our choice set.

AIT is not the first theorem in Arrow's Social Choice and Individual Values. His first theorem is his "Possibility Theorem for Two Alternatives", which states majority decision satisfies his conditions. Majority decision is a simple pairwise comparison of two alternatives, with the alternative receiving the majority of the vote is selected. Thus, we have majority decision as a valid tool with which to construct our social welfare method.

It has been known since Condorcet's time that for a given electorate, any set of potential outcomes contains either a single outcome that is at least as good as every other outcome, or a top cycle of outcomes, when majority decision is used to conduct a tournament among all pairs of outcomes. Voting methods of the filter and runoff type, use this fact to get a definitive result when there is not a clear winner on the first round. They reduce the choice set to two possible outcomes, then use majority decision to make the final choice. These systems do get a result, but it is not necessarily the case that the final choice is the collectively best choice, and it might not even be in the top cycle of the original set.

If, instead, we relax the unstated condition that limits us to only one or perhaps two rounds, we can do something different. Consider our initial choice set. We know it has either a Condorcet winner (CW) or a top cycle.

We already know the CW, if one exists, is the best possible choice from any given choice set. We also know if we can eliminate a single outcome from the top cycle, the reduced set will have a CW. Now consider what happens if we increase the number of outcomes in the choice set. With every additional outcome the set changes, and each of these sets has its own CW or top cycle. If the newly added outcome is collectively not as desirable as the earlier CW or the cycle members, the original CW or cycle will be unchanged. But if the newly added outcome is collectively more desirable than the earlier CW or at least two of the cycle members, the new set will have a new CW or a modified top cycle.

That last point is important and worth emphasizing. If we have a system that reliably identifies a CW or a top cycle, and we can add new outcomes to the choice set, we can get better collective outcomes than possible with the original choice set and only one round. Which is to say, we can find a choice that is more consistent with our collective will than even the best of the original choice set.

Although there are other ways voting systems can fail, the two main issues from AIT and GST are: "how to deal fairly with top cycles?", and "What to do about manipulability?"

GST has described all voting rules as being in one or more of three main categories: those that are dictatorships, those that are trivial meaning limited to two choices, or those subject to manipulation. Dictatorships are obviously bad for democratic societies. Restricting the choice set to two options is extremely problematic for healthy debates over complicated societal issues. And manipulability is seen as bad, even if it can also be difficult to accomplish.

The fear of manipulability is that some voter or voters may, in some situations and with advanced knowledge of the likely outcome, be able to submit a ballot that could change an election result to a subjectively better outcome. But what if each and every voter had an equal opportunity to effectively manipulate their ballot? Would an equal-opportunity manipulable voting system still be bad?

In order to manipulate their ballots in a single round voting system, the voters need to know in advance what the outcome would be if everyone submitted their honest ballots, and needs to be able to determine a way to more strategically fill in their own ballot to make a subjectively better outcome more likely. Thus manipulation requires advanced data on the expected outcome and the ability to correctly optimize a ballot for a better subjective result given that data. The fear of a manipulable system can stem from the need for advanced data that might be restricted to a subgroup, which then gains an advantage. It could also stem from a complicated ballot requiring significant computing power for subjective optimization, which also might be limited to a subgroup. It could even be both.

Private surveys in which the respondents are not provided with the survey results, or when the survey results themselves are manipulated, support one source of the fear, and voting systems designed to make it difficult to manipulate ballots correctly support the other source of fear.

Fear of some voters having more power through manipulation is valid for some (perhaps many) voting systems. But it is possible for a voting system to be engineered to support ballot manipulation in such a way that all voters have and equal opportunity to submit ballots that best support their personal preferences, and where the system actively requests such manipulation.

The key to fear-free manipulability in a voting system is making the manipulation simple and allowing multiple rounds over which the manipulations can play out. So, what does it mean to manipulate a voting system? The usual definition of a voting method being manipulable is when there is an "honest" way to fill out a ballot, and a "strategic" way to fill out a ballot, where the strategic and honest ballots differ and the strategic ballot leads to a better outcome than the honest ballot under some circumstances.

One problem with this definition of manipulable is the "honest" versus "strategic" distinction. We really do not want to encourage anyone to lie, and using the terms honest and strategic as opposites can be inferred to be saying a strategic ballot is dishonest. Instead, I would replace honest with naive, and strategic with informed, where the information needed is what the rest of the electorate wants.

When dealing with an ordinal ballot, the completed ballot indicates a preference order of the choice set, with the most support going to the most preferred choice and the least support going to the least preferred choice. A naive voter completes the ballot using only their personal preference ordering of the choice set. Informed voters, with some sense of what the collective result will be, complete their ballots using an ordering that gives more support to choices subjectively better than the expected outcome with a chance of winning, and less support to the expected outcome itself, so as to increase the probability of a subjectively better collective outcome. So, with an ordinal ballot, manipulation means altering the submitted order in order to get a subjectively better outcome.

When dealing with cardinal ballots, a naive voter completes the ballot based on their perceived utility of the outcomes in the choice set, essentially giving each possible outcome a score. Naive voters complete their ballot with grades showing their personal expected utility scores for each choice. Partially informed voters consider the expected outcome and adjust the scores on their ballots to increase the probability of a subjectively better collective outcome. So, with a cardinal ballot, manipulation means altering the scores in order to get a subjectively better outcome.

The specific cardinal case of approval voting (AV) is particularly easy for strategy. There are only two grades: pass or fail, so there is only a single threshold to consider. Naive voters take their lists of the choices ordered by expected utilities, set a cutoff threshold separating their approved choices from the rest. Then they simply vote for all choices at or above the threshold. Partially informed voters have some idea of the expected outcome, so their calculation is simple. Look at the expected outcome and always voter for every alternative better than it. Then decide whether the expected outcome itself is acceptable. If yes, also vote for the expected outcome. If no, do not vote for the expected outcome.

One nice feature of AV is that it already has a vocabulary for adjustments around a voter's individual threshold. Over-voting means voting for more choices than you actually approve of. While under-voting means voting for fewer choices.

Putting all these ideas together, we can derive a collective choice method I've called serial approve vote election (SAVE). It starts with a single AV round including all the initially proposed choices. As usual for AV, the choice with the most votes wins the first round. This first round is naive, because no voters had any idea of what the outcome was going to be. For all the following rounds, until a final winner is declared, the voters have much more information to use when completing their ballots. These following round constitute the SAVE loop, and use what I call focused approval vote (FAV) rounds.

The key feature of an FAV round is a single choice that is the current collective best choice. With this designation, all voters now have the exact information they need to complete informed ballots. Voters are now explicitly requested to vote for all choices subjectively better than the focus choice, and to vote for the focus choice if they want it to be the final winner.

This is where majority decision comes into play. The first thing decided when the votes are tallied is whether the focus choice won the FAV round under slightly modified AV rules. To win an FAV round, the focus choice must be a strict AV winner (receiving more votes than any other choice), and must have a strict majority of the votes cast. If the focus choice does not win the FAV round, there will be another FAV round, possibly with a different focus choice.

Majority decision also applies to the votes for the other choices. Since voters were asked to vote for any non-focus choice that is subjectively better than the focus choice, all the votes for each non-focus choice can be considered to be votes in a pairwise majority decision between the focus choice and that specific non-focus choice. This means if some non-focus choice is deemed better than the focus choice by the collective, it will get more than half the vote. Similarly, if any non-focus choice receives fewer than half the number of ballots cast, that choice is collectively deemed worse than the focus choice.

Once the votes in the round are tallied, a look at the vote counts will quickly show whether the focus choice both won the round by receiving strictly more votes than half the number of ballots, and won under AV rules by receiving strictly more votes than any other choice. If so, the final winner is known and we proceed to the final mandate round (more about that in a few paragraphs). If not, we will have another FAV round.

If we are having another FAV round, the first thing to do is decide the focus choice for the next round. The procedure for determining the focus choice for the next round is detailed in SAVE Focus, which includes an interactive model that runs through the entire SAVE process with a detailed commentary on what happens each round. The key points are: the current focus choice is retained as the focus choice for the next round unless some other choice receives strictly more votes than half the number of ballots in the round, which forces the focus to move to another choice. When the focus must change, the set of possible replacements includes all choices with a vote count of at least half the number of ballots in the round. When the focus choice does not change, it is a CW.

Once the focus choice for the next FAV round is known, we check to see if this next focus choice is a repeat. This occurs when the focus choice is a CW, or when it is part of a cycle. Whenever the focus choice is a repeat, voters are allowed to propose new choices. This is where we an increase the choice set and possibly getting a new CW or a different cycle.

At this time in the process there is a pause before the next round to give voters a bit of time to consider the results and possibly propose or review new choices. After this pause, the voting for the next FAV round starts.

One thing to note about the final winning choice is that it is common for one or more of the non-focus choices to receive votes from more than half the ballots. Normally this would mean another FAV round. Yet in order for the loop to terminate, a sufficient number of voters from all the sub-groups that gave majorities to non-focus choices must also have voted for the acceptance of the final winning choice, and given that choice a super-majority of the votes.

When the final winning choice is known, the SAVE loop ends and we have an additional, pure AV round (no focus choice) over all choices. This round is called the mandate round and does not change any results. Its sole purpose is to clearly measure the support for each choice active at the end of the process. This final mandate round was added to the process as a response to a political election in which the winning candidate had a vote count less than half of the ballots cast, and yet claimed an absolute mandate to do whatever he wanted. Having an explicit mandate round will tell the electorate whether the final winner is a strongly supported centrist result, or a weakly supported compromise result that is nevertheless deemed a good enough result for a divided electorate. The mandate round can also serve as a measure of any change in the support of the initial set of choices, since they were part of the initial AV round that picked the first focus choice.

Voting theorists have worried about the possibility of manipulation in their voting systems, with few (if any) other authors considering whether the possibility of manipulation might actually be a positive quality. The fear is that actors with exclusive foreknowledge of the result could use that knowledge to alter the collective result to the benefit of a limited minority of the electorate.

This article presents a way of looking at the manipulability of a voting system as a blessing, an opportunity for direct negotiation on a massive scale. SAVE shows how all voters with knowledge of the prior collective behavior can complete their approval ballots using strategic over- and under-voting to manipulate the over all results to get a better subjective result.

We introduce serial approval vote election as a formalized form of manipulation with approval voting, providing each and every voter with the exact information needed to adjust their ballot to best support their subjective concepts of a better collective result. SAVE repeats this process until a strict majority (often a super-majority) of the voters accept the predicted winner as their collective choice. At the end of the process, all voters who supported the final result have direct evidence their strategy gave them about as good a result as they could possibly get, and all voters who had not supported the final result know they made their best effort to get a different result.