IJCAI 2022poster3 citations
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.
Agent-based and Multi-agent Systems: Computational Social ChoiceAgent-based and Multi-agent Systems: Algorithmic Game Theory
BibTeX
@inproceedings{ijcai2022p83,
title = {On the Complexity of Calculating Approval-Based Winners in Candidates-Embedded Metrics},
author = {Yang, Yongjie},
booktitle = {Proceedings of the Thirty-First International Joint Conference on
Artificial Intelligence, {IJCAI-22}},
publisher = {International Joint Conferences on Artificial Intelligence Organization},
editor = {Lud De Raedt},
pages = {585--591},
year = {2022},
month = {7},
note = {Main Track},
doi = {10.24963/ijcai.2022/83},
url = {https://doi.org/10.24963/ijcai.2022/83},
}