Analytical Tools in Probability for Social Choice Theory and Computer Science

社会选择理论和计算机科学的概率分析工具

基本信息

批准号：
1839406
负责人：
Steven Heilman
金额：
$ 4.65万
依托单位：
University of Southern California
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2018
资助国家：
美国
起止时间：
2018-07-01 至 2020-06-30
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1839406&HistoricalAwards=false
关键词：
Analytical Tools Probability Social Choice

项目摘要

This project seeks to answer the following questions. (1) "How can we design an election so that the outcome does not change due to miscounted or corrupted votes?" (2) "What is the best way to cluster data on a computer?" (3) "How can we understand the geometry of networks?" Questions (1) and (2) can be reformulated as isoperimetric problems. One example of an isoperimetric problem asks for the shape of a fence of fixed length that encloses the most area (the answer being a circular fence, which was known since ancient times). The specific isoperimetric problems the principal investigator studies can be phrased as probabilistic problems, and this project develops some new tools from calculus to deal with these problems. Different versions of Question (1) have been studied extensively by game theorists in the 1950s and 1960s, but investigations in theoretical computer science in the last two decades have given renewed interest for Questions (1), (2), and (3). Generally speaking, theoretical computer science finds ways for computers to solve problems as quickly and as efficiently as possible.This project develops two analytic tools in probability: the calculus of variations and curvature. Several recent isoperimetric problems in probability and theoretical computer science such as (1) and (2) ask for the Euclidean sets of smallest Gaussian perimeter and fixed Gaussian volume. A breakthrough result of Choksi and Sternberg from 2007 allows the calculus of variations to be applied to these optimization problems, though others have not yet used variational tools for these problems. The principal investigator will also develop theories of curvature for hypercontractive and logarithmic Sobolev inequalities. For a Riemannian manifold, Ricci curvature bounds imply logarithmic Sobolev inequalities, a result of Bakry and Emery from 1985. In this project, different notions of Ricci curvature on random graphs will be investigated. Theories of Ricci curvature for noncommutative logarithmic Sobolev inequalities will also be investigated.

该项目试图回答以下问题。（1）“我们如何设计选举，以使结果不会因投票误差或损坏而改变？” （2）“在计算机上群集数据的最佳方法是什么？” （3）“我们如何理解网络的几何形状？” 问题（1）和（2）可以作为等级问题重新校正。等等问题的一个例子要求固定区域的固定长度的形状（答案是一个圆形栅栏，这是远古时代以来已知的）。特定的等法问题主要研究者研究可以用作概率问题，该项目开发了一些从微积分来处理这些问题的新工具。在1950年代和1960年代，游戏理论家对不同的问题（1）进行了广泛的研究，但是在过去的二十年中，对理论计算机科学的调查给予了对问题（1），（2）和（3）的重新兴趣。一般而言，理论计算机科学为计算机找到了尽快和高效地解决问题的方法。该项目以概率开发了两种分析工具：变化和曲率的计算。概率和理论计算机科学方面的几个近期等等问题，例如（1）和（2）要求欧几里得集合最小的高斯周长和固定高斯体积。 Choksi和Sternberg从2007年开始的突破性结果允许将变化的计算应用于这些优化问题，尽管其他人尚未使用各种工具来解决这些问题。首席研究者还将开发出针对超合同和对数Sobolev不平等的曲率理论。对于Riemannian歧管，RICCI曲率界限意味着对数Sobolev不平等，这是1985年的Bakry和Emery的结果。在此项目中，将研究随机图上RICCI曲率的不同概念。还将研究针对非交通对数Sobolev不平等的RICCI曲率理论。