Drawing a Map of Elections in the Space of Statistical Cultures
S. Szufa, P. Faliszewski, P. Skowron, A. Slinko, N. Talmon
AAMAS 2020
Abstract
We consider the problem of forming a testbed of elections to be used for numerical experiments (such as testing algorithms or estimating the frequency of a given phenomenon). We seek elections that come from well-known statistical distributions and are as diverse as possible. To this end, we define a (pseudo)metric over elections, generate a set of election instances, and measure distances between them, to assess how diverse they are. Finally, we show how to use these elections to test election-related algorithms.
Experiments:
| Election type |
Culture |
Candidates |
Voters |
Instances |
Parameters |
| Ordinal |
Euclidean 1D |
{100} |
{100} |
None |
Uniform 1D {[0,1]} |
| Ordinal |
Euclidean 2D |
{100} |
{100} |
None |
Uniform 2D ($[0,1]^2$); Uniform 2D Sphere ($(0, 0)$ $r=1$) |
| Ordinal |
Euclidean 3D-or-more |
{100} |
{100} |
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 |
Impartial Culture |
{100} |
{100} |
None |
None |
| Ordinal |
Mallows |
{100} |
{100} |
None |
$\phi \in \{ 0.999, 0.99, 0.95, 0.75, 0.5, 0.25, 0.1, 0.05, 0.01, 0.001\}$ |
| Ordinal |
Single-Crossing |
{100} |
{100} |
None |
None |
| Ordinal |
Single-Peaked (Conitzer/Random Peak) |
{100} |
{100} |
None |
None |
| Ordinal |
Single-Peaked (Walsh/Uniform) |
{100} |
{100} |
None |
None |
| Ordinal |
Urn Model |
{100} |
{100} |
None |
$\alpha \in \{0.01, 0.02, 0.05, 0.1, 0.2, 0.5\}$ |
| Ordinal |
Euclidean 1D |
{8} |
{8} |
10 |
Uniform 1D {[0,1]} |
| Ordinal |
Euclidean 2D |
{8} |
{8} |
10 |
Uniform 2D ($[0,1]^2$); Uniform 2D Sphere ($(0, 0)$ $r=1$) |
| Ordinal |
Impartial Culture |
{8} |
{8} |
10 |
None |
| Ordinal |
Mallows |
{8} |
{8} |
10 |
$\phi \in \{ 0.01, 0.05, 0.1\}$ |
| Ordinal |
Single-Crossing |
{8} |
{8} |
10 |
None |
| Ordinal |
Single-Peaked (Conitzer/Random Peak) |
{8} |
{8} |
10 |
None |
| Ordinal |
Urn Model |
{8} |
{8} |
10 |
$\alpha \in \{0.1, 0.2\}$ |
| Ordinal |
Mallows |
{100} |
{100} |
100 |
See paragraph “Mallows” in Section 4.1 of the paper (a somewhat involved variant of probing the $\phi$ parameter, later replaced by the normalized Mallows model in the paper “Putting a Compass on the Map of Elections”) |