Winner Robustness via Swap- and Shift-Bribery: Parameterized Counting Complexity and Experiments

N. Boehmer, R. Bredereck, P. Faliszewski, R. Niedermeier

Election type Ordinal
Culture Urn Model
Candidates {10}
Voters {100}
Instances 800000
Two particular elections out of 800 elections from “Putting the Compass on the Map of Elections”. For each of these two elections, each $r \in \{0.0125, 0.025, . . . , 0.5\}$, the authors used 10,000 samples. 2 * 40 * 10000 = 800000.
Parameters $\alpha \in \{0.01, 0.02\}$
To exemplify this phenomenon, we visualize PE,c(r) under Borda for two particular elections from the 800-elections dataset in Figure 2 (for these two elections, we estimated PE,c(r) for $r \in \{0.0125, 0.025, . . . , 0.5\}$ using 10000 samples in each case). We want to emphasize that these elections are not artificial extreme examples but were generated both as part of 180 elections generated by the Urn model with different parameters. In fact, there exist several other elections in the dataset exhibiting a similar behavior.
Notes Section 4. Experiments