On the Tree Representations of Dichotomous Preferences

Yongjie YangIJCAI 2019 · DOI

TL;DR

This paper explores how representing voter preferences using tree structures can simplify complex voting problems. The authors introduce new tree-based preference domains and analyze their relationships with existing ones, demonstrating that many of these domains allow for efficient recognition and polynomial-time computation of election winners for various voting rules.

What Problem Does This Paper Address?

In computational social choice, determining the winner of an election can be computationally hard, especially with complex preference structures. Domain restrictions, which limit the types of preferences voters can express, have been a powerful tool to overcome these hardness results and model real-world scenarios. This paper focuses on dichotomous preferences (where voters approve a set of candidates) and investigates how restricting these preferences to specific tree structures can lead to more tractable voting problems. The authors aim to:

  1. Introduce and define new tree-based preference domains: They propose domains where candidates or votes are mapped to vertices in trees, and the approved candidates by a vote (or votes approving a candidate) exhibit specific tree-like structures.
  2. Analyze relationships between these new domains and existing ones: Understanding how these domains are related (e.g., one implies another) is crucial for transferring results and gaining a comprehensive view of the landscape of restricted preferences.
  3. Determine the complexity of recognizing these domains: For a voting rule to benefit from a domain restriction, it must be efficient to check if an election belongs to that domain.
  4. Investigate the complexity of winner determination for various multiwinner voting rules: The ultimate goal is to see if these tree-based domain restrictions make computationally hard winner determination problems tractable (solvable in polynomial time).

Methods

The paper employs a combination of graph theory, computational complexity theory, and formal definitions of voting rules and preference domains.

  • Tree Representations: The core methodology involves defining preference domains based on mapping candidates or votes to vertices of trees (rooted, oriented, or undirected). Specific structures are imposed on the set of approved candidates for each vote (or votes approving a candidate) based on these trees. Examples include:
  • a-Tree Representation (a-TR): Candidates are mapped to vertices of a rooted tree, and approved candidates for a vote form a path from the root to a specific candidate.
  • B-Tree Representation (B-TR): Candidates are mapped to vertices of an oriented tree, and approved candidates for a vote induce an arborescence.
  • Path-tree representation (PTR): Candidates are mapped to vertices of a tree, and approved candidates for a vote induce a path.
  • Similar "V" variants are defined where votes are mapped to tree vertices.
  • Domain Relationship Analysis: The authors systematically prove inclusion relationships between their proposed domains and those from prior work (e.g., Elkind and Lackner, 2015). This involves constructing proofs that show if an election satisfies one domain, it must also satisfy another.
  • Complexity of Recognition: The paper leverages existing results on recognizing tree-hypergraphs. They show that many of their defined domains correspond to specific types of hypergraphs that can be recognized in polynomial time.
  • Winner Determination Complexity: For various multiwinner voting rules (Chamberlin-Courant, Proportional Approval Voting, Minimax Approval Voting), the authors analyze the complexity of finding a winning committee when preferences are restricted to their defined domains. This often involves proving polynomial-time solvability by constructing algorithms or showing NP-hardness by reducing from known hard problems (like Exact Cover or Partial Vertex Cover).

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis of preference structures and voting rules, rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Tree structures offer a rich framework for preference restrictions: The paper demonstrates that various tree structures (paths, rooted trees, oriented trees) can be used to define meaningful and tractable preference domains.
  • Bridging candidate-centric and vote-centric views: The authors show interesting connections between domains where candidates are mapped to trees (e.g., a-TR) and domains where votes are mapped to trees (e.g., B-VTR), suggesting a unified perspective.
  • Polynomial-time recognition is achievable for most domains: A key finding is that determining whether an election belongs to most of these tree-based domains can be done efficiently, which is a prerequisite for leveraging these domains in practice.
  • Tractability for winner determination: The paper successfully shows that for several important multiwinner voting rules, restricting preferences to these tree domains leads to polynomial-time solvable winner determination problems. This is a significant practical contribution.
  • NP-hardness persists in some cases: Despite the general trend towards tractability, the paper also identifies specific tree structures (like star or comb trees) combined with certain voting rules where the winner determination problem remains NP-hard, highlighting the nuanced impact of domain restrictions.

Key Results

  • Domain Relationships: The paper establishes a comprehensive set of inclusion relationships between their proposed domains and existing ones, summarized in Figure 4 and Theorem 1. For instance, they show that a-TR is a special case of VI (Voter Interval), and t-PART implies a-TR.
  • Recognition Complexity: Most of the defined tree-based domains can be recognized in polynomial time. For example, recognizing TR (Tree Representation) or VTR (Vote Tree Representation) is polynomial, as is recognizing PTR, VPTR, β-PTR, and β-VPTR.
  • Winner Determination Complexity:
    • Polynomial-time solvable: WD-PAV and WD-CCAV are polynomial-time solvable for a-TR elections (Theorem 3). WD-MAV and WD-PAV are polynomial-time solvable for star PTR elections (Theorem 4). WD-CCAV and WD-MAV are polynomial-time solvable for star VPTR elections (Theorem 7). WD-MAV is polynomial-time solvable for star β-PTR elections (Theorem 8).
  • NP-hard: WD-CCAV is NP-hard for star β-PTR elections (Theorem 5). WD-PAV, WD-CCAV, and WD-MAV are NP-hard for comb/star VTR elections (Theorem 6).

Limitations and Future Work

  • Dichotomous Preferences: The study is limited to dichotomous preferences (approval voting). Extending these tree-based domain restrictions to other preference types (e.g., ordinal preferences) could be a future direction.
  • Dichotomous Uniformly Euclidean (DUE): The paper notes that determining whether an election satisfies the DUE domain remains an open question.
  • Specific Tree Structures: While many domains are tractable, the paper highlights that certain combinations of tree structures (star, comb) and voting rules can still lead to NP-hard problems. Further exploration of these boundary cases and other specific tree structures could be valuable.
  • Parameterization: The paper touches upon parameterized complexity but could explore it more deeply for other domains and rules.
  • Real-world applicability: While the domains are motivated by real-world scenarios, empirical studies to assess how frequently these tree structures appear in actual elections would be beneficial.

Summary updated

BibTeX
@inproceedings{yang2019tree,
  author = {Yongjie Yang},
  title = {{On the Tree Representations of Dichotomous Preferences}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.24963/ijcai.2019/91},
}
Figure