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

Yongjie YangIJCAI 2022 · DOI

TL;DR

This paper investigates the computational complexity of finding winning committees in approval-based voting systems where candidates are positioned in a metric space. The authors introduce and analyze six variants of winner determination problems based on utilitarian and egalitarian criteria, considering various distance functions and graph structures, and establish their NP-completeness and parameterized hardness.

What Problem Does This Paper Address?

Traditional approval-based multiwinner voting (ABMV) often treats candidates as independent entities. However, in real-world scenarios, candidates can have inherent relationships, such as geographical proximity or similarity, which can influence the desirability of a committee. This paper addresses this gap by introducing a model where candidates are embedded in a metric space, and the "closeness" of a committee to voters' preferences is evaluated based on these distances. The core challenge is to understand the computational difficulty of finding optimal committees under different distance metrics (utilitarian and egalitarian) and candidate structures (general, path, star, complete graphs). This is crucial for designing fair and efficient voting systems in applications ranging from selecting travel destinations to recommending books.

Methods

The paper's primary contribution lies in its comprehensive complexity analysis of various winner determination problems. The authors define six problem variants based on two aggregation rules:

  • Utilitarian rules: Minimize the sum of distances between the committee and voters' preferences.
  • Egalitarian rules: Minimize the maximum distance between the committee and voters' preferences.

These rules are applied with three distance functions: minimum, maximum, and sum of distances between candidates and votes. The analysis covers both general metric spaces and specific graph structures like paths, stars, and complete graphs, which represent common ways candidates might be related.

For computational complexity, the authors employ standard techniques:

  • NP-completeness proofs: Reductions from known NP-complete problems (like Restricted Exact Cover by 3 Sets - RX3C) are used to establish NP-hardness.
  • Parameterized complexity: W[2]-hardness is shown with respect to the committee size ($k$) and sometimes $k+s$ (where $s$ is a threshold value), indicating that these problems are unlikely to be efficiently solvable even for small committee sizes.
  • Approximation algorithms and lower bounds: For NP-hard problems, the paper explores the limits of approximation and provides some polynomial-time approximation algorithms.
  • Fixed-parameter tractable (FPT) algorithms: The authors also develop algorithms that are efficient when parameterized by specific input features, such as the number of candidates ($m$), the number of votes ($n$), or the number of distinct distances ($a(f)$).

Datasets

Not discussed in the paper. The paper focuses on theoretical complexity analysis and does not involve empirical evaluation on specific datasets.

Key Insights and Ideas

  • Metric Space Matters: Introducing a metric space for candidates significantly impacts the complexity of winner determination. Many problems that might be tractable in a simple approval setting become NP-hard or W[2]-hard when candidate distances are considered.
  • Utilitarian vs. Egalitarian Trade-offs: The choice between utilitarian and egalitarian criteria leads to different computational challenges. For instance, utilitarian-min distance problems are often harder to approximate than their egalitarian counterparts.
  • Structure is Key: The underlying structure of the candidate relationships (e.g., path, star, complete graph) drastically affects solvability. Path-metrics, especially with consecutive approvals, allow for more efficient algorithms compared to general metrics.
  • Approximation Limits: For some problems, like OPT-UWD-MIN and OPT-EWD-MIN, the paper establishes strong inapproximability results, suggesting that finding near-optimal solutions is as hard as finding exact solutions.
  • Fixed-Parameter Tractability: The research highlights that while general problems are hard, they can become tractable when parameterized by specific features like the number of candidates or votes, offering practical solutions for certain scenarios.

Key Results

The paper presents a detailed complexity landscape for six ABMV variants:

  • NP-Completeness and W[2]-Hardness: Most of the studied problems (UWD-MIN, UWD-MAX, EWD-MIN, EWD-MAX) are shown to be NP-complete and W[2]-hard with respect to the committee size $k$, even for restricted metric spaces like paths.
  • Inapproximability: OPT-UWD-MIN and OPT-EWD-MIN are proven to be W[2]-hard to approximate to any factor.
  • Polynomial-Time Solvability:
    • UWD-SUM is polynomial-time solvable for general metrics.
  • EWD-SUM is polynomial-time solvable when the distance threshold $s=0$.
  • UWD-MIN and UWD-MAX are polynomial-time solvable for path-metrics when voters approve consecutive candidates.
  • EWD-MIN is polynomial-time solvable for path-metrics under similar consecutive approval conditions.
  • Fixed-Parameter Algorithms: Algorithms with complexity $O^*(2^m)$, $O^*(n^n)$, $O^*(2^{2^n})$, and $O^*(4^k)$ are provided for various problem variants and parameterizations.

Limitations and Future Work

  • Specific Distance Functions: The paper focuses on three specific distance functions (min, max, sum). Future work could explore other aggregation functions, such as the Hausdorff distance, which is widely used in other areas.
  • Ordered Weighted Average (OWA): Generalizing the distance calculation using OWA operations is suggested as a promising avenue.
  • Robustness to Inaccuracy: The paper acknowledges that precisely measuring distances between candidates can be challenging in real-world applications. Investigating the robustness of the proposed models to inaccuracies in distance measurements is an important future direction.
  • Voter Preferences: While candidates are in a metric space, voters' preferences are modeled as approval sets. Exploring models where voters themselves are embedded in a metric space (spatial voting) could be a valuable extension.

Summary updated

BibTeX
@inproceedings{yang2022complexity,
  author = {Yongjie Yang},
  title = {{On the Complexity of Calculating Approval-Based Winners in Candidates-Embedded Metrics}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.24963/ijcai.2022/83},
}
Figure