On the Complexity of Calculating Approval-Based Winners in Candidates-Embedded Metrics
Abstract
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.
Cite
Text
Yang. "On the Complexity of Calculating Approval-Based Winners in Candidates-Embedded Metrics." International Joint Conference on Artificial Intelligence, 2022. doi:10.24963/IJCAI.2022/83Markdown
[Yang. "On the Complexity of Calculating Approval-Based Winners in Candidates-Embedded Metrics." International Joint Conference on Artificial Intelligence, 2022.](https://mlanthology.org/ijcai/2022/yang2022ijcai-complexity/) doi:10.24963/IJCAI.2022/83BibTeX
@inproceedings{yang2022ijcai-complexity,
title = {{On the Complexity of Calculating Approval-Based Winners in Candidates-Embedded Metrics}},
author = {Yang, Yongjie},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2022},
pages = {585-591},
doi = {10.24963/IJCAI.2022/83},
url = {https://mlanthology.org/ijcai/2022/yang2022ijcai-complexity/}
}