Multi-Winner Reconfiguration
Authors: Jiehua Chen, Christian Hatschka, Sofia Simola
NeurIPS 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We summarize our findings as follows (also see Table 1); For a brief definition of the relevant parameterized complexity classes see Section 2: (i) The problem is fixed-parameter tractable (FPT) wrt. m. Under CC it is also FPT wrt. n. (ii) While the problem is in XP wrt. n (resp. k). it remains NP-hard even for constant value b + ℓ. The XP result for k is essentially tight since it remains W[2]-hard under CC (resp. W[1]-hard under PAV). (iii) Combining n with any other single parameter always yields an FPT algorithm. Our preliminary experimental investigations (see Appendix C) indicate that for most randomly generated committees, a reconfiguration path not only exists but can also be efficiently determined using a straightforward heuristic. |
| Researcher Affiliation | Academia | Jiehua Chen Institute of Logic and Computation TU Wien Austria jchen@ac.tuwien.ac.at Christian Hatschka Institute of Logic and Computation TU Wien Austria chatschka@ac.tuwien.ac.at Sofia Simola Institute of Logic and Computation TU Wien Austria ssimola@ac.tuwien.ac.at |
| Pseudocode | No | The paper describes algorithms and proof strategies in prose and mathematical notation but does not include any explicitly labeled pseudocode or algorithm blocks. |
| Open Source Code | Yes | The code and the synthetic data are included in the supplementary material. The raw Netflix data, which is not ours, is available at Netflix (2006). Code and description of the preprocessing are included in the supplementary material and Appendix C. |
| Open Datasets | Yes | We use both real-life (Netflix Prize data (Netflix, 2006)) and synthetic data (geometric and (p-ϕ)-resampling). |
| Dataset Splits | No | The paper describes data processing and how instances are created (e.g., dividing Netflix ratings by date, creating 100 random committees, removing movies/days with few approvals), but it does not specify explicit train/validation/test splits with percentages or sample counts. |
| Hardware Specification | Yes | The experiments are run on Ubuntu 22.04.2 with 3.8 GB of RAM, CPU of the virtual machine Intel Xeon (Cascadelake), 2x 1-Core , on a host with Intel Xeon Gold 5215, 2x 10-Core . |
| Software Dependencies | Yes | The experiments are run on Python 3.10.12. Additionally we use for example the following Python libraries: abcvoting version 2.8.0, Gurobipy version 10.0.2 and Networkx version 3.1. |
| Experiment Setup | Yes | For each instance-rule-k-combination, we create 100 random committees. We order them by score, then pick and pair the 20 best ones. This way we obtain random but still reasonably well-scoring committees. If the number of alternatives is too small to obtain 100 random committees, we skip the instance. For each pair, we choose the lower scoring committee as the starting committee W, the higher scoring as the goal committee W , and set δs = 0 and δc = 1. |