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