On the Complexity of Calculating Approval-Based Winners in Candidates-Embedded Metrics
Authors: Yongjie Yang
IJCAI 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study approval-based multiwinner voting where candidates are in a metric space and committees are valuated in terms of their distances to the given votes. In particular, we consider three different distance functions, and for each of them we study both the utilitarian rules and the egalitarian rules, resulting in six variants of winners determination problems. We focus on the (parameterized) complexity of these problems for both the general metric and several special metrics. For hardness results, we also discuss their approximability. |
| Researcher Affiliation | Academia | Yongjie Yang Chair of Economic Theory, Saarland University, Saarbr ucken, Germany yyongjiecs@gmail.com |
| Pseudocode | No | The paper describes algorithms in prose, particularly within the proofs (e.g., Theorem 4), but it does not contain clearly labeled pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not include any statements about releasing code or links to source code repositories. |
| Open Datasets | No | This is a theoretical paper focused on computational complexity. It does not involve empirical experiments with datasets that require training, validation, or testing splits. The 'input' described in the paper consists of abstract sets and metrics for theoretical problem definition. |
| Dataset Splits | No | This is a theoretical paper focused on computational complexity. It does not involve empirical experiments with datasets that require training, validation, or testing splits. |
| Hardware Specification | No | This is a theoretical paper on computational complexity. It does not describe any specific hardware used for running experiments. |
| Software Dependencies | No | This is a theoretical paper on computational complexity. It does not mention any specific software dependencies with version numbers. |
| Experiment Setup | No | This is a theoretical paper on computational complexity. It does not describe an experimental setup with hyperparameters or system-level training settings. |