Restricted Domains of Dichotomous Preferences with Possibly Incomplete Information

Zoi Terzopoulou, Alexander Karpov, Svetlana ObraztsovaAAAI 2021 · DOI

Introduction

In computational social choice, the complexity of computing "fair" voting outcomes, such as those under Proportional Approval Voting (PAV), often hinges on the underlying structure of voter preferences. While domain restrictions for total rankings (e.g., single-peakedness) are well-documented, dichotomous preferences—where voters provide simple binary approvals or disapprovals—remain less explored. This paper investigates the structural patterns that define well-behaved dichotomous domains and addresses the practical challenge of incomplete voting data.

Structural Characterization via Forbidden Patterns

The authors identify specific "forbidden subprofiles"—small sub-matrices that, if present, disqualify a set of approvals from belonging to a restricted domain. A primary focus is the Single-sided Voter External Interval (SVEI) domain. SVEI is characterized by the absence of a simple $2 \times 2$ identity matrix pattern. This domain is significant because it models political loyalty where voters can be ordered such that their approvals form a continuous "prefix" of the candidate list.

Beyond SVEI, the paper provides the first characterizations for Voter External Interval (VEI) and Partition (PART) domains. For instance, the VEI domain is shown to be defined by a set of five specific forbidden patterns. These characterizations are crucial for identifying the boundaries of computational tractability.

Algorithmic Framework for Incomplete Data

Real-world voting data is frequently partial. The central algorithmic question addressed is whether a partial matrix of approvals (containing 0s, 1s, and unknown "?" values) can be completed to satisfy a specific domain restriction.

To solve this, the authors introduce a Consecutive Order Graph. In this directed graph, nodes represent voters. An edge is drawn from voter $v_j$ to $v_\ell$ if there exists an alternative that $v_j$ approves but $v_\ell$ disapproves. This graph serves as a tool to determine the necessary linear ordering of voters required by the domain restriction.

A partial approval matrix (left) and its corresponding consecutive order graph (right) used to propagate constraints and determine voter ordering.

The paper presents two key polynomial-time algorithms to handle these completions:

  1. SVEI-INCOMPLETE: This algorithm uses a constraint propagation "filling" procedure combined with the graph-based ordering approach. It runs in $O(m^3n^3)$ time.
  2. VEI-INCOMPLETE: This more complex algorithm employs a "coarsening" technique to group alternatives, iteratively applying SVEI logic to handle broader external interval structures. It runs in $O(m^4n^2)$ time.

Key Results and Complexity

The research identifies a critical "tractability gap." While completing a profile to satisfy the Voter Interval (VI) property is known to be NP-complete, the slightly more restrictive VEI and SVEI properties are solvable in polynomial time. This distinction provides a clear boundary for where structural complexity meets computational feasibility in social choice.

Furthermore, the authors establish a duality between voter-based and candidate-based domains, meaning results for voter ordering can be directly translated to candidate ordering. The paper provides methods to check both if a profile possibly satisfies a property (can it be completed?) and if it necessarily satisfies it (do all completions work?).

Conclusion and Future Directions

This work provides a robust theoretical foundation for handling incomplete dichotomous preferences. Future research may explore the complexity of the "necessary" version of the VI completion problem or extend the model to handle "noisy" data where reported approvals might be erroneous. Parameterized complexity analysis regarding the number of unknown cells also remains an open area for investigation.

Summary updated

BibTeX
@inproceedings{terzopoulou2021restricted,
  author = {Zoi Terzopoulou and Alexander Karpov and Svetlana Obraztsova},
  title = {{Restricted Domains of Dichotomous Preferences with Possibly Incomplete Information}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i6.16718},
}
Figure