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) |