On the Complexity of Calculating Approval-Based Winners in Candidates-Embedded Metrics

On the Complexity of Calculating Approval-Based Winners in Candidates-Embedded Metrics

Yongjie Yang

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence
Main Track. Pages 585-591. https://doi.org/10.24963/ijcai.2022/83

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.
Keywords:
Agent-based and Multi-agent Systems: Computational Social Choice
Agent-based and Multi-agent Systems: Algorithmic Game Theory