Computational Social Choice Meets Databases

Benny Kimelfeld, Phokion G. Kolaitis, Julia Stoyanovich

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 WINNER relation, 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 WINNER atoms 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 WINNER atoms 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 WINNER atoms 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 WINNER atom 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 WINNER atoms, its necessary answers are computable in polynomial time.
  • coNP-Completeness for Connected WINNER Atoms: For conjunctive queries with two WINNER atoms 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 WINNER atoms and a relation R(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

Abstract

We develop a novel framework that aims to create bridges between the computational social choice and the database management communities. This framework enriches the tasks currently supported in computational social choice with relational database context, thus making it possible to formulate sophisticated queries about voting rules, candidates, voters, issues, and positions. At the conceptual level, we give rigorous semantics to queries in this framework by introducing the notions of necessary answers and possible answers to queries. At the technical level, we embark on an investigation of the computational complexity of the necessary answers. We establish a number of results about the complexity of the necessary answers of conjunctive queries involving positional scoring rules that contrast sharply with earlier results about the complexity of the necessary winners.
BibTeX
@inproceedings{kimelfeld2018computational,
  author = {Benny Kimelfeld and Phokion G. Kolaitis and Julia Stoyanovich},
  title = {{Computational Social Choice Meets Databases}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.24963/ijcai.2018/44},
}
Figure