Computational Social Choice Meets Databases
Computational Social Choice Meets Databases
复制标题
计算社会选择与数据库的结合
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Julia Stoyanovich
中科院分区：
文献类型：
--
作者：
B. Kimelfeld;Phokion G. Kolaitis;Julia Stoyanovich
我们开发了一个新的框架，旨在建立计算社会选择和数据库管理社区之间的桥梁。这个框架丰富了目前支持的任务，在计算社会选择与关系数据库的背景下，从而使其能够制定复杂的查询投票规则，候选人，选民，问题和立场。在概念层面上，我们给出了严格的语义查询在这个框架中，通过引入必要的答案和可能的答案查询的概念。在技术层面上，我们开始调查的计算复杂性的必要答案。特别是，我们建立了一些结果的复杂性的必要答案的合取查询涉及的复数规则，对比鲜明的复杂性的必要赢家根据复数规则与早期的结果。
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. In particular, we establish a number of results about the complexity of the necessary answers of conjunctive queries involving the plurality rule that contrast sharply with earlier results about the complexity of the necessary winners under the plurality rule.