Single-Peakedness and Total Unimodularity: New Polynomial-Time Algorithms for Multi-Winner Elections
Authors: Dominik Peters
AAAI 2018 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We introduce a new technique: carefully chosen integer linear programming (IP) formulations for certain voting problems admit an LP relaxation which is totally unimodular if preferences are singlepeaked, and which thus admits an integral optimal solution. This technique gives efficient algorithms for finding optimal committees under Proportional Approval Voting (PAV) and the Chamberlin Courant rule with single-peaked preferences, as well as for certain OWA-based rules. |
| Researcher Affiliation | Academia | Dominik Peters Department of Computer Science University of Oxford, UK dominik.peters@cs.ox.ac.uk |
| Pseudocode | No | The paper presents Integer Programming (IP) formulations rather than pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide any concrete access to source code for the methodology described. |
| Open Datasets | No | The paper is theoretical and does not use datasets for training or evaluation. |
| Dataset Splits | No | The paper is theoretical and does not involve dataset splits for training, validation, or testing. |
| Hardware Specification | No | The paper is theoretical and does not describe specific hardware used for experiments. |
| Software Dependencies | No | The paper mentions 'any standard IP solver' but does not provide specific software names with version numbers for reproducibility. |
| Experiment Setup | No | The paper is theoretical and does not detail experimental setup parameters like hyperparameters or training configurations. |