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

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

• 批准号: 1813888
• 负责人: Julia Stoyanovich
• 金额: $ 23.36万
• 依托单位: Drexel University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2018
• 资助国家: 美国
• 起止时间: 2018-07-15 至 2019-03-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1813888&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.

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