TL;DR
This paper bridges computational social choice (COMSOC) and database management by introducing a framework for querying voting data within relational databases. It defines "necessary" and "possible" answers to queries, extending existing COMSOC notions, and investigates the computational complexity of these queries, revealing surprising hardness results that differ from traditional COMSOC problems.
What Problem Does This Paper Address?
Computational Social Choice (COMSOC) traditionally focuses on determining election winners based on aggregated preferences. However, real-world scenarios involve richer data: demographic information about voters and candidates, candidate stances on issues, and the context of elections or polls. Existing COMSOC methods often struggle to incorporate this contextual information. Furthermore, voter preferences are frequently incomplete, leading to the concepts of "necessary winners" (those who win in all possible preference completions) and "possible winners" (those who win in at least one completion). This paper addresses the challenge of formulating and answering complex queries that combine these contextual database elements with COMSOC concepts, particularly when dealing with incomplete preference data. It aims to provide a formal framework and analyze the computational cost of such queries.
Methods
The paper introduces a novel framework that integrates COMSOC primitives into a relational database context. Key methodological contributions include:
- Formal Semantics for Queries: The authors define rigorous semantics for queries over partial preference databases, introducing the notions of "necessary answers" and "possible answers." These extend the COMSOC concepts of necessary and possible winners to general database queries.
- Relational Framework: They propose augmenting relational schemas with a
WINNERrelation, allowing voting rule outcomes to be treated as data within standard database queries. - Complexity Analysis: A significant portion of the work is dedicated to investigating the computational complexity of evaluating these necessary answers for conjunctive queries. They analyze queries involving positional scoring rules, particularly the plurality rule, and then generalize to other positional scoring rules.
- Bipartite Graph Matching: For tractability results concerning the plurality rule, they employ bipartite graph matching to efficiently determine necessary answers.
- Reductions for Hardness: To establish coNP-completeness results, they use reductions from known hard problems (like the complement of maximum independent set and 3-DNF Tautology) to specific query structures.
Datasets
Not discussed in the paper. The paper uses a running example of a preference database (Figure 1) to illustrate its concepts, but this is a synthetic example, not a benchmark dataset.
Key Insights and Ideas
- Context Matters Significantly: The paper demonstrates that incorporating relational database context (candidate demographics, issue stances) into COMSOC problems can drastically alter computational complexity. What is tractable for simple winner determination can become intractable when combined with relational data.
- Necessary Answers Can Be Harder Than Necessary Winners: For certain conjunctive queries, especially those involving multiple
WINNERatoms that are connected, determining necessary answers can be coNP-complete, even for simple voting rules like plurality. This contrasts with the polynomial-time solvability of finding necessary winners for positional scoring rules. - Pairwise Disconnectedness is Key for Tractability: For queries with multiple
WINNERatoms under the plurality rule, if these atoms are "pairwise disconnected" (i.e., their winner variables don't interact through ordinary atoms), the problem remains tractable (polynomial time). This highlights a structural property of queries that dictates complexity. - A Dichotomy for Two WINNER Atoms: The paper establishes a PTIME vs. coNP-complete dichotomy for queries with exactly two
WINNERatoms under the plurality rule, depending on whether these atoms are connected or disconnected.
Key Results
- Tractability for Single WINNER Atom Queries: For Boolean conjunctive queries with a single
WINNERatom and ordinary atoms, determining necessary answers is decidable in polynomial time. - Polynomial-Time Algorithm for Plurality with Disconnected WINNER Atoms: If a conjunctive query with plurality rule has pairwise disconnected
WINNERatoms, its necessary answers are computable in polynomial time. - coNP-Completeness for Connected WINNER Atoms: For conjunctive queries with two
WINNERatoms under the plurality rule, if these atoms are connected, the problem of determining necessary answers is coNP-complete. - coNP-Completeness Beyond Plurality: For a natural conjunctive query structure involving three
WINNERatoms and a relationR(x1, x2, x3), the problem of determining necessary answers is coNP-complete for any strict positional scoring rule.
Limitations and Future Work
- Focus on Conjunctive Queries: The current framework and complexity analysis primarily focus on conjunctive queries. Future work could extend this to more complex query languages.
- Complexity of Possible Answers: While the paper provides some results for plurality and veto rules, the complexity of possible answers for other rules remains an open area.
- Aggregate Operators: The authors suggest exploring queries that involve aggregate operators (like count and average) in future research.
- Alternative Preference Models: Extending the framework to handle probabilistic preferences (e.g., Mallows models, RIM) and developing probabilistic query answering is a promising direction.
- Constraints on Completions: Incorporating voter preferences with explicit constraints (e.g., party affiliation) that restrict possible completions is another avenue for future work.
Summary updated