Parliamentary Voting Procedures: Agenda Control, Manipulation, and Uncertainty
Authors: Robert Bredereck, Jiehua Chen, Rolf Niedermeier, Toby Walsh
JAIR 2017 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | On the other hand, our experimental studies with real-world data indicate that most preference profiles cannot be manipulated by only few voters and a successful agenda control is typically impossible. If the voters preferences are incomplete, then deciding whether an alternative can possibly win is NP-hard for both procedures. Whilst deciding whether an alternative necessarily wins is co NP-hard for the amendment procedure, it is polynomial-time solvable for the successive procedure. [...] Our experiments on Agenda Control and on Coalitional Manipulation using real-world profiles indicate that while both problems are polynomial-time solvable, a successful agenda control is very rare and a successful manipulation on average needs a coalition containing at least half of the original voters. |
| Researcher Affiliation | Academia | Robert Bredereck EMAIL Institut f ur Softwaretechnik und Theoretische Informatik TU Berlin, Germany; Jiehua Chen EMAIL Dept. Industrial Engineering and Management Ben-Gurion University of the Negev, Israel; Rolf Niedermeier EMAIL Institut f ur Softwaretechnik und Theoretische Informatik TU Berlin, Germany; Toby Walsh EMAIL Institut f ur Softwaretechnik und Theoretische Informatik TU Berlin, Germany |
| Pseudocode | Yes | Algorithm 1: Algorithm for solving Agenda Control under the successive procedure by computing an appropriate agenda. [...] Algorithm 2: Algorithm for solving Coalitional Manipulation under the amendment procedure by computing all manipulation winners. |
| Open Source Code | Yes | Our algorithms for Agenda Control and Coalitional Manipulation are written in C ++ and are freely available through http://www.akt.tu-berlin. de/menue/software/. |
| Open Datasets | Yes | To this end, we use data from the Pref Lib collection of preference profiles (Mattei & Walsh, 2013) to examine the ratio of profiles that admit successful agenda control or manipulation operations. The preference profiles in Pref Lib are not taken from parliamentary votes. Nevertheless, we decided to use Pref Lib simply because it is one of the few free, online accessible libraries that we know of. |
| Dataset Splits | No | The paper uses preference profiles from Pref Lib for empirical evaluation, analyzing properties of voting procedures. It does not involve machine learning model training and therefore does not specify conventional training/test/validation dataset splits. Instead, it uses subsets of the available profiles (e.g., profiles with an odd number of voters) to calculate vulnerability ratios. |
| Hardware Specification | No | The paper states that algorithms are written in C++ and are freely available, but it does not provide any specific details about the hardware (e.g., CPU, GPU models, memory) used to conduct the empirical studies. |
| Software Dependencies | No | The paper states that the algorithms are written in C++, but it does not specify any particular C++ compiler, library versions, or other software dependencies with version numbers that would be needed to replicate the experiments. |
| Experiment Setup | Yes | For each alternative c and for each agenda L Z, using the algorithms behind Theorems 3 and 4, we compute the minimum coalition size, that is, the minimum number of voters needed to make c a successive (resp. an amendment) winner. [...] If m <= 8, then let Z be the set of all possible agendas, that is, |Z| := m!. Otherwise, we generate a set Z of agendas by randomly choosing |Z| := min(n^2, 8!) agendas from the set of all possible agendas, where n denotes the number of voters in the input. All possible agendas are equally likely of being chosen for Z. |