Papers › Using Database Dependencies to Constrain Approval-Based Committee Voting in the...
Using Database Dependencies to Constrain Approval-Based Committee Voting in the Presence of Context
Roi Yona, Benny Kimelfeld
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
In Approval-Based Committee (ABC) voting, each voter lists the candidates they approve and then a voting rule aggregates the individual approvals into a committee that represents the collective choice of the voters. An extensively studied class of such rules is the class of ABC scoring rules, where each voter contributes to each possible committee a score based on the voter's approvals. We initiate a study of ABC voting in the presence of constraints about the general context surrounding the candidates. Specifically, we consider a framework in which there is a relational database with information about the candidates together with integrity constraints on the relational database extended with a virtual relation representing the committee. For an ABC scoring rule, the goal is to find a committee of maximum score such that all integrity constraints hold in the extended database. We focus on two well-known types of integrity constraints in relational databases: tuple-generating dependencies (TGDs) and denial constraints (DCs). The former can express, for example, desired representations of groups, while the latter can express conflicts among candidates. ABC voting is known to be computationally hard without integrity constraints, except for the case of approval voting where it is tractable. We show that integrity constraints make the problem NP-hard for approval voting, but we also identify certain tractable cases when key constraints are used. We then present an implementation of the framework via a reduction to Mixed Integer Programming (MIP) that supports arbitrary ABC scoring rules, TGDs and DCs. We devise heuristics for optimizing the resulting MIP, and describe an empirical study that illustrates the effectiveness of the optimized MIP over databases in three different domains.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections