Computational Aspects of Conditional Minisum Approval Voting in Elections with Interdependent Issues
Authors: Evangelos Markakis, Georgios Papasotiropoulos
IJCAI 2020 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We focus on the computational aspects of Conditional Minisum, where progress has been rather scarce so far. We identify restrictions to every voter s dependencies, under which we provide the first multiplicative approximation algorithms for the problem. The restrictions involve upper bounds on the number of dependencies an issue can have on the others. At the same time, by additionally requiring certain structural properties for the union of dependencies cast by the whole electorate, we obtain optimal efficient algorithms for well-motivated special cases. Overall, our work provides a better understanding on the complexity implications introduced by conditional voting. |
| Researcher Affiliation | Academia | Evangelos Markakis and Georgios Papasotiropoulos Athens University of Economics and Business, Department of Informatics {markakis, gpapasotiropoulos}@aueb.gr |
| Pseudocode | Yes | Algorithm 1 Input: P 1: Create P from P using Lemma 1 and Equation (1). 2: Run an α-approximation of MIN 2-SAT on P . 3: Set the value of Ij in P to the value of xj in P . |
| Open Source Code | No | The paper does not provide any concrete access to source code for the methodology described, nor does it state that code is made available. |
| Open Datasets | No | The paper focuses on theoretical aspects (algorithms, complexity, approximation ratios) and does not describe empirical experiments with datasets that would require a publicly available dataset. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical validation on datasets, thus no training, validation, or test splits are discussed. |
| Hardware Specification | No | The paper is theoretical and focuses on algorithms and complexity; therefore, it does not mention any hardware specifications used for experiments. |
| Software Dependencies | No | The paper mentions using algorithms for MIN 2-SAT and MIN 3-SAT (e.g., by Avidor and Zwick), but it does not specify any software names with version numbers or other ancillary software details needed for replication. |
| Experiment Setup | No | The paper is theoretical, describing algorithms and complexity analysis rather than empirical experiments, so it does not include details on experimental setup such as hyperparameters or training configurations. |