Minimal voting paradoxes
| Author | Felix Brandt,Marie Matthäus,Christian Saile |
| DOI | http://doi.org/10.1177/09516298221122104 |
| Published date | 01 October 2022 |
| Date | 01 October 2022 |
| Subject Matter | Articles |
Minimal voting paradoxes
Felix Brandt
Technische Universität München, Germany
Marie Matthäus
Technische Universität München, Germany
Christian Saile
Technische Universität München, Germany
Abstract
Voting paradoxes date back to the origin of social choice theory in the 18th century, when the
Chevalier de Borda pointed out that plurality—then and now the most common voting rule—
may elect a candidate who loses pairwise majority comparisons against every other candidate.
Since then, a large number of similar, seemingly paradoxical, phenomena have been observed in
the literature.As it turns out, many paradoxes only materialize under somerather contrived circum-
stances and require a certain number of voters and candidates. In this paper, we leverage computa-
tional optimization techniques to identify the minimal numbers of voters and candidates that are
required for the most common voting paradoxes to materialize. The resulting compilation of voting
paradoxes may serve as a useful reference to social choice theorists as well as an argument for the
deployment of certain rules when the numbers of voters or candidates are severely restricted.
Keywords
Social choice theory, voting paradoxes, integer linear programming, computational social choice
1. Introduction
Electoral systems are a crucial pillar of liberal democracy. The formal properties of electoral
systems are studied in social choice theory, whose origins can be traced back to the Age of
Corresponding author:
Felix Brandt, Technische Universität München, Germany.
Email: brandtf@in.tum.de
Article
Journal of Theoretical Politics
2022, Vol. 34(4) 527–551
© The Author(s) 2022
Article reuse guidelines:
sagepub.com/journals-permissions
DOI: 10.1177/ 09516298221122104
journals.sagepub.com/home/jtp
Enlightenment, in particular during the French Revolution, and whose modern development
was initiated by Arrow’s impossibility theorem. In its simplest form, the central question of
social choice theory is which candidate ought to be elected based on the preferences of mul-
tiple voters, typically given as strict rankings. Countless voting rules have been proposed
over the years and there have been arguments for and against each of these. Manya rguments
are presented in the form of voting paradoxes, that is, it is pointed out that under certain cir-
cumstances the rule in question elects a candidate that is “obviou sly a bad choice.”
Voting paradoxes have remained indispensable in the analysis of electoral systems
because there is growing consensus that there is no single optimal voting rule (see, e.g.,
Fishburn, 1974, 1982; Fishburn and Brams, 1983; Nurmi, 1987, 1999; Felsenthal, 2012,
2018). This has been confirmed by impossibility theorems, showing that every voting
rule is susceptible to one paradox or the other. For example, Moulin (1988) proved that
every voting rule either suffers from the Condorcet Winner Paradox, i.e., it may fail to
elect a candidate that is preferred to every other candidate by some majority of voters, or
from the No-Show Paradox, i.e., voters can be better off by abstaining from an election.
As it turns out, many paradoxes only materialize under some rather contrived circum-
stances and require a certain number of voters and candidates. In order to address this
problem, two important questions are how frequently paradoxes occur given distribu-
tional information about the voters’preferences and what is the minimal number of
voters and candidates required for a given paradox to materialize. The former problem
was addressed extensively in the literature by Gehrlein and Fishburn (1976, 1978),
Gehrlein (2006), Gehrlein and Lepelley (2011, 2017), Plassmann and Tideman (2014),
and many others. It is the latter problem that we are concerned with in this paper. The
theorem by Moulin (1988) mentioned earlier requires at least 4 candidates and at least
25 voters. Moulin showed that, when there are only 3 candidates, the maximin procedure
is Condorcet-consistent and immune to the No-Show Paradox. Yet, the question of
whether there are voting rules immune to both paradoxes when there are less than 25
voters remained open. This was settled by Brandt et al. (2017) who showed the existence
of such rules when there are at most 11 voters and proved a tightened version of Moulin’s
theorem by showing that one of the two paradoxes occurs whenever there are at least 4
candidates and 12 voters. However, the positive result is based on an artificial computer-
generated voting rule and common Condorcet-consistent voting rules suffer from the
No-Show Paradox for significantly lower numbers of voters. The goal of this paper is
to compute minimal instances of voting paradoxes for common voting rules.
Our point of departure will be the comprehensive compilation of voting paradoxes by
Felsenthal (2012). While finding instances of some voting paradoxes is relatively straight-
forward, this canbe very tricky for other ones. Many cleverinstances required a lot of hard
work and have been passed on from one author to another.
1
For example, in order to show
that instant-runoff and Coomb’s method violate Condorcet-consistency, Felsenthal gives a
85-voter example (that he constructed with Moshè Machover) and a 45-voter example
(attributed to Nicolaus Tideman), respectively.
2
The minimal examples only require 5
and 13 voters, respectively. Felsenthal also gives a 5-candidate 49-voter example (attribu-
ted to Hannu Nurmi) which shows that Young’s method suffers from the No-Show
Paradox. The minimal example requires only 4 candidates and 11 voters. In fact, we
have found smaller examples of all paradoxes considered by Felsenthal except for his
528 Journal of Theoretical Politics 34(4)
To continue reading
Request your trial