Conditional and Sequential Approval Voting on Combinatorial Domains
Authors: Nathanaël Barrot, Jérôme Lang
IJCAI 2016 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study three such rules. The first two generalize simple multiwinner approval voting and minimax approval voting. The third one is an approval-based version of sequential voting on combinatorial domains. We study some properties of these rules, and compare their outcomes.Computing a winning committee for minimax approval voting is NP-hard [Moti and Ami, 1997], which of course carries over to conditional minimax approval voting. On the other hand, the polynomial time computation of winning committees for simple approval voting does not carry over to conditional minisum (even without feasibility constraints): Proposition 1. Given a CA profile P and an integer k, deciding whether there exists d 2 D such that Pi δ(d, Bi) k is NP-complete, even for binary variables and, for each voter, an acyclic dependency graph with maximal indegree 1.The largest possible ratio, over all O-legal CA profiles, between the disagreement score of the SCAV winner and the disagreement score of the conditional minisum winner, is Pp i=1(1 1 i )/(1 1 1 ). |
| Researcher Affiliation | Academia | Nathana el Barrot and J erˆome Lang CNRS LAMSADE, Universit e Paris-Dauphine, France {nathanael.barrot, jerome.lang}@lamsade.dauphine.fr |
| Pseudocode | No | The paper does not include any explicitly labeled "Pseudocode" or "Algorithm" sections, nor does it present structured steps formatted like code. |
| Open Source Code | No | The paper does not contain any statements about releasing open-source code or links to a code repository. |
| Open Datasets | No | This paper is theoretical and does not describe experiments run on a specific dataset. The examples provided, such as Example 2, use illustrative data rather than a publicly available dataset for empirical evaluation. |
| Dataset Splits | No | The paper does not describe an experimental setup with data splits, as it is a theoretical work. |
| Hardware Specification | No | The paper does not mention any specific hardware used for running experiments, as it is a theoretical work. |
| Software Dependencies | No | The paper mentions "MAXSAT solvers" as a tool for solving conditional minisum, but it does not specify any particular software names with version numbers. |
| Experiment Setup | No | The paper does not provide details about an experimental setup, such as hyperparameters or system-level training settings, as it is a theoretical paper. |