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

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

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.