Exploring the No-Show Paradox for Condorcet Extensions Using Ehrhart Theory and Computer Simulations

F. Brandt, J. Hofbauer, M. Strobel
AAMAS 2019
Abstract
Results from voting theory are increasingly used when dealing with collective decision making in computational multiagent systems. An important and surprising phenomenon in voting theory is the No-Show Paradox (NSP), which occurs if a voter is better off by abstaining from an election. While it is known that certain voting rules suffer from this paradox in principle, the extent to which it is of practical concern is not well understood. We aim at filling this gap by analyzing the likelihood of the NSP for six Condorcet extensions (Black's rule, Baldwin's rule, Nanson's rule, MaxiMin, Tideman's rule, and Copeland's rule) under various preference models using Ehrhart theory as well as extensive computer simulations. We find that, for few alternatives, the probability of the NSP is rather small (less than 4% for four alternatives and all considered preference models, except for Copeland's rule). As the number of alternatives increases, the NSP becomes much more likely and which rule is most susceptible to abstention strongly depends on the underlying distribution of preferences.

Experiments:

Election type Culture Candidates Voters Instances Parameters
Ordinal Impartial Anonymous Culture [1-30] [1-50] 1000000 None
Ordinal Euclidean 2D {4} [1-1000] 1000000 Uniform 2D ($[0,1]^2$)
Ordinal Euclidean 2D {30} [1-200] 1000000 Uniform 2D ($[0,1]^2$)
Ordinal Impartial Anonymous Culture {4} [1-1000] 1000000 None
Ordinal Impartial Anonymous Culture {30} [1-200] 1000000 None
Ordinal Impartial Culture {4} [1-1000] 1000000 None
Ordinal Impartial Culture {30} [1-200] 1000000 None
Ordinal Mallows {4} [1-1000] 1000000 {0.8}
Ordinal Mallows {30} [1-200] 1000000 {0.8}
Ordinal Urn Model {4} [1-1000] 1000000 +10 copies of the chosen ranking to the urn after each draw
Ordinal Urn Model {30} [1-200] 1000000 +10 copies of the chosen ranking to the urn after each draw