Winner Robustness via Swap- and Shift-Bribery: Parameterized Counting Complexity and Experiments
N. Boehmer, R. Bredereck, P. Faliszewski, R. Niedermeier
IJCAI 2021
Abstract
We study the parameterized complexity of counting variants of Swap- and Shift-Bribery, focusing on the parameterizations by the number of swaps and the number of voters. Facing several computational hardness results, using sampling we show experimentally that Swap-Bribery offers a new approach to the robustness analysis of elections.
Experiments:
| Election type |
Culture |
Candidates |
Voters |
Instances |
Parameters |
| Ordinal |
Euclidean 1D |
{10} |
{100} |
10000 |
Uniform 1D {[0,1]} |
| Ordinal |
Euclidean 2D |
{10} |
{100} |
10000 |
Uniform 2D ($[0,1]^2$); Uniform 2D Sphere ($(0, 0)$ $r=1$) |
| Ordinal |
Euclidean 3D-or-more |
{10} |
{100} |
10000 |
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 |
{10} |
{100} |
10000 |
None |
| Ordinal |
Mallows |
{10} |
{100} |
10000 |
The same as in “Putting the Compass on the Map of Elections” |
| Ordinal |
Single-Crossing |
{10} |
{100} |
10000 |
None |
| Ordinal |
Single-Peaked (Conitzer/Random Peak) |
{10} |
{100} |
10000 |
None |
| Ordinal |
Single-Peaked (Walsh/Uniform) |
{10} |
{100} |
10000 |
None |
| Ordinal |
Urn Model |
{10} |
{100} |
10000 |
The same as in “Putting the Compass on the Map of Elections” |
| Ordinal |
Urn Model |
{10} |
{100} |
800000 |
$\alpha \in \{0.01, 0.02\}$ |