The Liquid Democracy Journal
on electronic participation, collective moderation, and voting systems
Issue 6
2018-07-27

Practical Consequences of Arrow's Theorem for Open Electronic Voting

by Jan Behrens, Berlin, July 27, 2018 other format: text version (UTF-8)

In the second article [Roadmap] in this Issue #6 of The Liquid Democracy Journal, we mentioned two contradictory design criteria for electronic decision making systems: on the one hand, considerations regarding tactical voting require that cast ballots are temporarily hidden and that ballots should not be changed or removed after disclosore of the cast ballots; on the other hand, we want to ensure that wrongly cast ballots (e.g. through hacker attacks) can be corrected afterwards.

This article will elaborate a deeper conflict that can be seen as a consequence of Arrow's Impossibility Theorem in combination with complexity of computer systems and which affects all forms of electronic decision making.

Arrow's impossibility theorem

Kenneth Arrow showed in 1951 that it is impossible to create a voting system where all voters may express their preferences while fulfilling several desirable properties of the system at the same time. In consequence, tactical voting cannot be ruled out when there are more than two voting options. [Gibbard] [PLF, section 4.14]

One might be tempted to restrict people from expressing their true preferences on a ballot (or to allow voters to express more than their preferences, e.g. a “satisfaction rate” that is a real number between 0 and 10). But these attempts are not suitable to eliminate the possibility of tactical voting either. [PLF, section 4.14]

Given more than two voting options, we have to face the possibility of tactical voting. Thus, preferential ballots should be hidden between submitting and tallying, such that individual voters cannot gain advantages by delaying their own vote and casting a strategically modified ballot based on other ballots that have been already submitted by other voters. [GoD]

It should be noted that the above considerations only apply when there are more than two voting options. A binary decision (that is totally independent from other decisions) is not subject to tactical considerations because it makes always sense to vote for your favorite option. The next section will explain why democratic decisions cannot generally be broken down to a sequence of binary decisions without influencing the outcome of the vote.

Majority cycles and binary decisions

The general existence of collective majority cycles has already been discovered in the 18th century by Marquis de Condorcet. [Condorcet] [PLF, p.151] An example for a collective majority cycle is that there is a majority preferring B over C, another majority preferring A over B, and yet another majority preferring C over A. Research in the last century revealed that under certain preconditions, there is a high probability that all voting options are tied in such a Condorcet paradox. [Schofield] In consequence, breaking down a complex decision into a sequence of yes/no-questions has a major influence on the overall outcome depending on the order in which the questions are being asked. [GoD] Having a committee determining the order of the questions would give power to the committee to decide about the outcome of the vote in certain scenarios and thus violate the democratic goal to treat everyone equal in the decision making process. [Note: Also when randomizing the order, not all voting options could be treated equally. Additionally such a system could be vulnerable to clones (see also [Tideman]).]

Even if this problem of losing fairness is disregarded, breaking a decision down into a sequence of yes/no-questions doesn't solve the problem of tactical voting either. Consider an example where a voter prefers A over B over C. The first ballot is about eliminating B or C. Naturally, you would expect the voter to vote for B (i.e. for eliminating C). But considering that C is an option almost nobody favors, it might be smarter to eliminate B because in the subsequent ballot between A and C, the first preference of the voter (i.e. A) might win. Any attempt to convert political decisions into a series of binary questions will, in case of majority cycles, not just introduce unfair side effects but also cannot solve the problem of tactical voting.

Complexity of technology

Another circumstance we have to consider when designing or assessing electronic decision making systems is complexity of technology and its impact on verifiability, particularly in those cases where cryptography or remote authentication and authorization methods are used. Computer systems are too complex to be verified by their users. In consequence, hacking attempts are possible that might stay undetected or at least undetected until a ballot has been closed.

Using open ballots allows for a verification of the overall process by the participants. [PLF, chapter 3] However, depending on the impact of the decisions made with an electronic system, we might not just want verifiability but also the ability to recover from a hacking attempt and to correct wrongly cast ballots (which would be possible given an open ballot where identities are disclosed). But if it was possible to correct a ballot after tallying, tactical advantages could be gained by claiming to be hacked and “correcting” one's ballot in such a way that tactical considerations regarding all other cast ballots are taken into account. In the end, those people who correct their votes last would gain an unfair advantage.

An unsolvable conflict

Obviously, a correction of ballots cannot be forbidden and made possible at the same time. There seems to be an unsolvable conflict: either we declare all ballots as immutable once they have been tallied by an electronic voting system, or we allow corrections by each person who cast a vote (which is possible in case of recorded votes). In the latter case, people who fake a manipulation (e.g. by claiming their system was hacked and/or posting their credentials) would gain a tactical advantage.

Work around

In many contexts (e.g. policy making), it would be irresponsible to abandon the possibility of correcting manipulations because this could put hackers in a dangerous position of power. We thus have to deal with corrections but try to keep the impact on the overall fairness of the decision making process as little as possible. One solution could be to proceed with vote corrections as follows:

If the correction of ballots does not change the overall outcome of the vote, these corrections can simply be performed and the result doesn't change. If, however, the overall outcome would be different with the corrected ballots, then we distinguish between two cases.

Case I: the decision was a binary decision. In this case, the ballots get corrected and the overall result is changed accordingly.

Case II: the decision involved more than two voting options. In this other case, the outcome of the vote is declared void and the vote must be repeated. Declaring the vote void instead of allowing another voting option to win reduces the potential impact by faking a manipulation in order to gain tactical advantages to maintaining the status quo (i.e. a decision can only be declared void but not changed). Furthermore, voters who make use of their possibility to correct votes could be treated differently in future elections: their votes could be published prematurely and they could be given a certain time to have them corrected until the remaining votes are made public and tallied.

It should be noted that this approach would treat the affected voters in Case II in an unfair fashion if they were true victims of a hacking attempt (or victim of an administrator's privilege abuse in case of a central server system where the administrator could manipulate votes easily). However, reducing the impact to disadvantages in tactical voting (by letting certain voters vote prematurely and publish their votes) is a lesser problem than giving hackers the power to completely control a voter's ballot.

Future work

It has been shown that the impossibility to verify the correct behavior of electronic decision making systems has an effect on the overall fairness of a compromised system even in cases where all votes are done by roll call (recorded identities for each ballot, which get published along with the ballot). A proposal has been made how to practically deal with later corrections of ballots while trying to preserve the equal treatment of all voters as good as possible. Not all impacts have been fully analyzed. For example, a premature publication of certain ballots would allow estimations on the final outcome of the voting procedure and might foster tactical voting of the other voters. For a decentralized decision making system based on the LiquidFeedback Blockchain [LFB], a precise algorithm for publication order and timings would need to be created.

The considerations in this article are a rough analysis of a generic problem that affects all forms of electronic decision making. In order to better assess the consequences and potential solutions or workarounds, it would be helpful to formalize the problem and provide a mathematical proof for (a formalized variant of) the previous statements. We believe this undertaking to be non-trivial because it would, for example, require a modeling of real-world processes such as “publication” of certain data or a “public objection” to one's ballot.

[Condorcet] Marquis de Condorcet: “Essai sur l'application de l'analyse à la probabilité des décisions rendues à la pluralité des voix”. Imprimerie Royale, Paris, 1785. (referenced at: a)
[Gibbard] Allan Gibbard: “Manipulation of Voting Schemes: A General Result”. In “Econometrica”, Vol. 41, No. 4, July 1973, pp. 587–601. Published by the Econometric Society (Wiley-Blackwell). (referenced at: a)
[GoD] Jan Behrens: “Game of Democracy”. In “The Liquid Democracy Journal on electronic participation, collective moderation, and voting systems”, Issue 2, October 7, 2014, pp. 11-22. ISSN 2198-9532. Published by Interaktive Demokratie e. V., available at http://www.liquid-democracy-journal.org/issue/2/The_Liquid_Democracy_Journal-Issue002-02-Game_of_Democracy.html (referenced at: a b)
[LFB] Jan Behrens, Axel Kistner, Andreas Nitsche, Björn Swierczek: “The LiquidFeedback Blockchain”. In “The Liquid Democracy Journal on electronic participation, collective moderation, and voting systems”, Issue 6, July 27, 2018, pp. 18-29. ISSN 2198-9532. Published by Interaktive Demokratie e. V. (referenced at: a)
[PLF] Behrens, Kistner, Nitsche, Swierczek: “The Principles of LiquidFeedback”. ISBN 978-3-00-044795-2. Published January 2014 by Interaktive Demokratie e. V., available at http://principles.liquidfeedback.org/ (referenced at: a b c d)
[Roadmap] Andreas Nitsche: “Roadmap to a decentralized LiquidFeedback”. In “The Liquid Democracy Journal on electronic participation, collective moderation, and voting systems”, Issue 6, July 27, 2018, pp. 13-17. ISSN 2198-9532. Published by Interaktive Demokratie e. V. (referenced at: a)
[Schofield] Norman Schofield, Bernard Grofman, Scott L. Feld: “The Core and the Stability of Group Choice in Spatial Voting Games”. In the “American Political Science Review”, Vol. 82, No. 1, March 1988, pp. 195–211. Published by Americian Political Science Association (Cambridge University Press). (referenced at: a)
[Tideman] Nicolaus Tideman: “Independence of clones as a criterion for voting rules”. In “Social Choice and Welfare”, Vol. 4, Issue 3, 1987, pp. 185-206. Published by Springer. (referenced at: a)