Understanding Distance Measures Among Elections

N. Boehmer, P. Faliszewski, R. Niedermeier, S. Szufa, T. Was
IJCAI 2022
Abstract
Motivated by putting empirical work based on (synthetic) election data on a more solid mathematical basis, we analyze six distances among elections, including, e.g., the challenging-to-compute but very precise swap distance and the distance used to form the so-called map of elections. Among the six, the latter seems to strike the best balance between its computational complexity and expressiveness.

Experiments:

Election type Culture Candidates Voters Instances Parameters
Ordinal exhaustive {3, 4} {3, 4, 5} None None
Ordinal Euclidean 1D {10} {50} None Uniform 1D {[0,1]}
Ordinal Euclidean 2D {10} {50} None Uniform 2D ($[0,1]^2$); Uniform 2D Sphere ($(0, 0)$ $r=1$)
Ordinal Euclidean 3D-or-more {10} {50} None Uniform 3D ($[0,1]^3$); Uniform 3D Sphere ($(0, 0)$ $r=1$); Uniform 5D ($[0,1]^5$); Uniform 5D Sphere ($(0, 0)$ $r=1$); Uniform 10D ($[0,1]^10$); Uniform 20D ($[0,1]^20$)
Ordinal Group-Separable {10} {50} None None
Ordinal Impartial Culture {10} {50} None None
Ordinal Mallows {10} {50} None classic Mallows model (we used the same sampling protocol as Boehmer et al. [2021b] - Putting a compass on the map of elections)
Ordinal Single-Crossing {10} {50} None None
Ordinal Single-Peaked (Conitzer/Random Peak) {10} {50} None None
Ordinal Single-Peaked (Walsh/Uniform) {10} {50} None None
Ordinal Urn Model {10} {50} None classic urn model (we used the same sampling protocol as Boehmer et al. [2021b] - Putting a compass on the map of elections)
Ordinal Euclidean 1D {3, 4} {3, 4, 5} None Uniform 1D {[0,1]}
Ordinal Euclidean 2D {3, 4} {3, 4, 5} None Uniform 2D ($[0,1]^2$); Uniform 2D Sphere ($(0, 0)$ $r=1$)
Ordinal Euclidean 3D-or-more {3, 4} {3, 4, 5} None Uniform 3D ($[0,1]^3$); Uniform 3D Sphere ($(0, 0)$ $r=1$); Uniform 5D ($[0,1]^5$); Uniform 5D Sphere ($(0, 0)$ $r=1$); Uniform 10D ($[0,1]^10$); Uniform 20D ($[0,1]^20$)
Ordinal Group-Separable {3, 4} {3, 4, 5} None None
Ordinal Impartial Culture {3, 4} {3, 4, 5} None None
Ordinal Mallows {3, 4} {3, 4, 5} None classic Mallows model (we used the same sampling protocol as Boehmer et al. [2021b] - Putting a compass on the map of elections)
Ordinal Single-Crossing {3, 4} {3, 4, 5} None None
Ordinal Single-Peaked (Conitzer/Random Peak) {3, 4} {3, 4, 5} None None
Ordinal Single-Peaked (Walsh/Uniform) {3, 4} {3, 4, 5} None None
Ordinal Urn Model {3, 4} {3, 4, 5} None classic urn model (we used the same sampling protocol as Boehmer et al. [2021b] - Putting a compass on the map of elections)