NSF-BSF: III: Small: Collaborative Research: Databases Meet Computational Social Choice

NSF-BSF：III：小型：协作研究：数据库满足计算社会选择

• 批准号: 1814152
• 负责人: Phokion Kolaitis
• 金额: $ 26.52万
• 依托单位: University of California-Santa Cruz
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2018
• 资助国家: 美国
• 起止时间: 2018-07-15 至 2024-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1814152&HistoricalAwards=false
• 关键词: NSF; BSF; III; Small; Collaborative

Social choice underlies the equitable and efficient operation of a society. How does one aggregate preferences of individuals, arriving at a society-wide consensus? This question has been the subject of intense debate throughout history, dating as far back as ancient Greece, and, in the past two decades, has led to the development of computational social choice - an interdisciplinary area of research and practice that combines insights from mathematics, logic, economics, and computer science. One of the main foci of computational social choice are the algorithmic aspects of determining actual or potential winners in a poll or in an election. Moreover, dealing with incompleteness and uncertainty (an inherent characteristic of polling) is an important challenge confronted by computational social choice. In recent years, the data management community embarked on an investigation of preference databases, which extend traditional databases by treating preferences on a par with relational data. This project will bring forth a foundational and systems research agenda that will create bridges between the computational social choice and the data management communities. The main aim of this project is to develop a unifying framework that brings together preferences, rules, outcomes, contextual information, and database query languages.This project will enrich the kinds of data analysis tasks that are currently supported by computational social choice methods to include context, going beyond determining winners, and into reasoning about positions and issues that the alternatives represent, as well as information about those choosing. To this effect, this project will develop a query language that will enhance traditional database query languages with special operators for voting rules and winners, thus making it possible to study social choice problems in the context of additional information about voters, candidates, and issues. Furthermore, this language will support sophisticated queries about incomplete or uncertain preferences, rules, and winners in the relational context. Rigorous semantics of queries in this language will be provided and fundamental algorithmic problems, such as query evaluation and reasoning about constraints, will be investigated. The techniques developed in this project will be experimentally evaluated in a query engine prototype using real data sets. By establishing a technical connection between computational social choice and data management and by developing a unifying framework, the computational social choice community will have access to a plethora of methods for managing incomplete and uncertain information that were developed by the database community.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

社会选择是社会公平有效运行的基础。如何综合个人喜好，达成全社会共识？这个问题在整个历史上一直是激烈辩论的主题，最早可以追溯到古希腊，并在过去20年里导致了计算社会选择的发展--这是一个结合了数学、逻辑、经济学和计算机科学见解的跨学科研究和实践领域。计算社会选择的主要焦点之一是在投票或选举中确定实际或潜在赢家的算法方面。此外，处理不完备性和不确定性(投票的固有特征)是计算型社会选择面临的一个重要挑战。近年来，数据管理界开始了对偏好数据库的研究，它通过将偏好与关系数据同等对待来扩展传统数据库。该项目将提出一个基础和系统研究议程，在计算社会选择和数据管理社区之间建立桥梁。这个项目的主要目的是开发一个统一的框架，将偏好、规则、结果、上下文信息和数据库查询语言结合在一起。该项目将丰富目前由计算社会选择方法支持的数据分析任务的种类，包括上下文，超越确定赢家，以及关于替代方案所代表的立场和问题的推理，以及关于那些选择的信息。为此，该项目将开发一种查询语言，它将使用投票规则和获胜者的特殊运算符来改进传统的数据库查询语言，从而能够在有关选民、候选人和问题的额外信息的背景下研究社会选择问题。此外，该语言将支持有关关系上下文中不完整或不确定的首选项、规则和赢家的复杂查询。将提供这种语言中查询的严格语义，并将研究基本的算法问题，如查询评估和关于约束的推理。本项目中开发的技术将在使用真实数据集的查询引擎原型中进行实验评估。通过在计算社会选择和数据管理之间建立技术联系，并开发一个统一的框架，计算社会选择社区将获得由数据库社区开发的用于管理不完整和不确定信息的过多方法。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

On the Computational Complexity of Non-Dictatorial Aggregation

关于非独裁聚合的计算复杂性

• DOI: 10.1613/jair.1.12476
• 发表时间: 2021
• 期刊: Journal of Artificial Intelligence Research
• 影响因子: 5
• 作者: Livieratos, John;Kolaitis, Phokion G.;Kirousis, Lefteris
• 通讯作者: Kirousis, Lefteris

Theory and Practice of Relational-to-RDF Temporal Data Exchange and Query Answering

关系型 RDF 时态数据交换和查询应答的理论与实践

• DOI: 10.1145/3591359
• 发表时间: 2023
• 期刊: Journal of Data and Information Quality
• 作者: Ao, Jing;Cheng, Zehui;Chirkova, Rada;Kolaitis, Phokion G.
• 通讯作者: Kolaitis, Phokion G.

Decision Problems in Information Theory

信息论中的决策问题

• DOI: 10.4230/lipics.icalp.2020.106
• 发表时间: 2020
• 期刊: and Programming (ICALP 2020
• 作者: Abo Khamis, Mahmoud;Kolaitis, Phokion G;Ngo, Hung Q;Suciu, Dan
• 通讯作者: Suciu, Dan

A SAT-Based System for Consistent Query Answering

基于 SAT 的一致查询应答系统

• DOI: 10.1007/978-3-030-24258-9_8
• 发表时间: 2019
• 期刊: 22nd International Conference
• 作者: Dixit, Akhil A;Kolaitis, Phokion G.
• 通讯作者: Kolaitis, Phokion G.

Algorithmic Techniques for Necessary and Possible Winners

必要和可能的获胜者的算法技术

• DOI: 10.1145/3458472
• 发表时间: 2021
• 期刊: ACM/IMS Transactions on Data Science
• 作者: Chakraborty, Vishal;Delemazure, Theo;Kimelfeld, Benny;Kolaitis, Phokion G.;Relia, Kunal;Stoyanovich, Julia
• 通讯作者: Stoyanovich, Julia