Skip to content (access key 's')
Logo of Technion
Logo of CS Department


Query Evaluation in Election Databases
event speaker icon
Muhammad Tibi, M.Sc. Thesis Seminar
event date icon
Wednesday, 23.10.2019, 15:00
event location icon
Room 601 Taub Bld.
event speaker icon
Advisor:  Prof. Benny Kimelfeld
Election databases are the main elements of a recently introduced framework that aims to create bridges between the computational social choice and the data management communities. An election database consists of incomplete information about the preferences of voters, in the form of partial orders, alongside with standard database relations that provide contextual information. Earlier work in computational social choice focused on the computation of possible winners and necessary winners that are determined by the available incomplete information and the voting rule at hand. The presence of the relational context, however, permits the formulation of sophisticated queries about voting rules, candidates, potential winners, issues, and positions on issues. Such queries can be given possible answer semantics and necessary answer semantics on an election database, where the former means that the query is true on some completion of the given partial orders and the latter means that the query is true on every such completion. We carry out a systematic investigation of query evaluation on election databases by analyzing how the interaction between the partial preferences, the voting rules and the relational context impacts on the complexity of query evaluation. To this effect, we focus on positional scoring rules and unions of conjunctive queries. We establish a number of results that delineate the complexity of the possible answers and of the necessary answers for different positional scoring rules and for various classes of unions of conjunctive queries. Furthermore, we show that query evaluation is fixed parameter tractable, where the parameter is the number of candidates in the election.
[Back to the index of events]