Provably Probable Social Choice

There is a strong theoretical similarity between computer networks and people networks. Here we will discuss a surprising fact that has been proven to be true for both human and computer networks.

Without a coin to flip, there is no safe way for independent entities to reach consensus! 

The previous chapter contained a light treatment of a fairly heavy theoretical topic in computer science, Byzantine Agreement (BA), and an exploration of how randomness is an essential requirement in overcoming certain impossibility results in distributed computing. As it turns out, there are some tantalizingly strong similarities between the theory of distributed agreement and the theory of social choice (SC).

Recall that the BA problem setup involves a number of distributed processes each of which starts out with an initial value for some variable. We might call this initial value the "authentic" or "honest" value of a process, because all properly functioning processes will honestly report this value to all others. The goal of any BA algorithm is to allow the processes to vote for their authentic value and to compute, eventually, a global value in such a way that two straightforward requirements are met:

1. If all well-behaved processes have the same authentic value, then the global consensus value must be that value.
2. If the well-behaved processes do not all agree on the same authentic value, they must still agree on some global value; it doesn't matter which one.

To make it more interesting, the problem allows for the possibility of faulty processes that do not honestly report their authentic value choices but rather attempt to game the system to influence the agreed upon result, or to prevent any agreement from being reached. If we place no constraints at all on the types of failures the faulty processes can experience, then we may as well assume the nefarious nodes are consciously trying to thwart our algorithm and that they have complete access to all the information they need to do so.

Already we can start to see similarities between BA and SC (voting) problems. We have a number of independent processes (voters), each of which has its own preferred value (candidate) and they must report (vote) in order to agree on (elect) a global winner in a fair manner. Some of the entities may be faulty (dishonest) and instead report (vote) strategically, using information about partial results to unfairly game the system in favor of their authentic choice.

Terminology note: The social choice literature seems to use the terms "strategic voting" and "tactical voting" interchangeably to mean voting for some candidate who is not your authentically preferred one in order to try to influence the election in your favor. Here we will use "tactical voting" because it describes better what's actually going on.

A very interesting question to ask for both BA and SC is this: Is it possible to devise an algorithm in which the non-faulty (honest) processes (voters) can overcome the evil impact of one or a few faulty (dishonest) ones so they cannot unfairly influence the result?  Not surprisingly, many mathematicians have examined this and similar questions and, perhaps surprisingly, the answers have been rather discouraging.

In the area of Byzantine Agreement, it was proven in 1985 that, for any practical scenario (where, e.g.,  message delivery times are unpredictable) there is no deterministic algorithm that will prevent even a single faulty process from influencing the results of the agreement. All the great work and research to find solutions in this area depends on randomness in some way to solve this important problem.

So what about the Social Choice arena? Around the same time (1984) Michael Dummett published several proofs of a decade-old conjecture now called the Gibbard-Satterthwaite theorem which is about voting algorithms used to select one winner from a group of three or more candidates based on voters' preferences. To paraphrase, the theorem states that for any reasonable scenario (where, e.g., there are no blacklisted candidates and the winner is not chosen by a single dictator) there is no deterministic algorithm that will prevent even a single tactical voter from influencing the results of the election. Sound familiar?

There is a more well-known, but in some ways less interesting, result in social choice called Arrow's Impossibility Theorem that has a lot in common with the G-S theorem discussed above. Dr. Kenneth Arrow received the Nobel Prize in Economics for his work related to this theorem in 1972. Professor Nancy Lynch received the Knuth Prize in 2007, in part for her seminal work on the impossibility proof for Byzantine Agreement. Yet, as near as I can tell, neither discipline has cited the other in all these years, despite the striking similarities of the problems and results and the huge amount of research activity associated with the two independent fields.

Don't get me wrong. I'm not saying these two canonical problems are identical, or even that there is a common underlying body of theory (though I believe there very well might me). But even the differences in the problem statements are illuminating and may indicate areas for further research in one field or the other. For example, the BA problem statement requires every non-faulty process be able to independently compute and verify the agreed upon value. There is no central authority to tabulate votes in BA, whereas in SC, it is typically assumed the independent voters submit their preferences which are then tallied in one place by a trusted central authority. But would it be a useful requirement for each voter in a SC scenario to be able to independently verify the results of an election? I believe this could be the basis of a reasonable formal definition of election transparency, a very useful property of real elections.

There are also areas where the typical formulations of SC problems are actually more stringent than BA. Remember the validity requirement for BA is, if every non-faulty process begins with the exact same initial value, then the algorithm must choose that value. If even one good process has a different value, then a correct BA algorithm is free to choose any value at all, as long as everyone agrees with it in the end. For SC, however, we must agree to elect a candidate based on more flexible requirements. An alternative validity rule might be, if a plurality of non-faulty processes have the same preferred value, the algorithm must choose that value. Or more generally, the algorithm must choose the winning candidate such that voters are the least unhappy about the result. This suggests some interesting extensions to the BA problem, such as Synchronous Byzantine Plurality.  I have no idea whether that problem has been studied or results reported in the literature, but reasoning by analogy (always a tricky thing to do) with the Gibbard-Satterthwait theorem, I would guess that synchronous BA with a plurality rather than unanimity constraint would be impossible in a deterministic way.

Despite all the interesting complexities with these two fields of study, one can definitively say that no completely robust solution to either BA or SC is possible without randomness. Faulty and/or malicious participants can always overwhelm honest participants to influence agreements and elections.  Without a coin to flip, there is no safe way for independent entities to reach consensus!