AF: Small: Collaborative Research: Boolean Function Analysis Meets Stochastic Design

优化领域的一个中心目标是在存在约束的情况下开发有效的决策程序。这些约束通常由真实世界的数据施加，但通常情况下，执行优化的代理并不完全知道相关数据;使用与数据相关联的概率分布来对这些设置进行建模是很自然的。在这样的分析中，与优化问题相关的约束本身就是“随机的”，标准目标是在产生最小成本的同时最大化满足所有约束的可能性。(As一个激励性的例子是，航空公司可能希望尽可能少地运行航班，同时确保99%的概率没有乘客被碰撞。 除了建模不确定性，随机约束的优化也提供了一种方法来简洁地建模约束，其标准描述是非常大的，在投票理论中的设计问题，有很多选民，是这类的例子。 这个项目研究这两种问题，称为随机设计问题，从一个统一的新的角度基于计算复杂性理论的技术。该项目还培养研究生，他们将在复杂性理论和优化方面达到流利，并将促进运筹学和理论计算机科学之间的跨学科活动。 激励的洞察力，这是这个项目的基础是，布尔函数分析-在调和分析，概率论和复杂性理论的交叉点的主题-提供了一套有用的技术随机设计问题。研究人员将研究两个广泛的主题。第一个是机会约束优化：在这类问题中，给定一组随机约束，目标是以至少一定的固定阈值概率满足所有约束。虽然以前的工作，这些问题通常实现了计算效率的算法，通过放松实际的约束条件，调查人员将集中在算法，完全满足原来给定的随机约束。这条线的工作将解决机会约束版本的基本优化问题，如装箱，背包，和线性规划。第二个广泛的主题是社会选择理论中的逆问题：博弈论使用所谓的“权力指数”来衡量选民在投票计划中的影响力。一个基本的算法问题是设计有效的算法的反问题，其中，给定一组规定的权力指标，目标是构建一个投票游戏与这些指标。研究人员将研究的问题，如（a）在多大程度上是一个给定的投票计划指定的权力指数？(b)在给定权力指数的情况下，精确重构一个未知目标投票博弈的复杂性是多少？(c)在部分信息的情况下，何时以及在何种程度上可以进行重建？该奖项反映了NSF的法定使命，并被认为是值得通过使用基金会的知识价值和更广泛的影响审查标准进行评估的支持。

A central goal in the field of optimization is to develop effective procedures for decision-making in the presence of constraints. These constraints are often imposed by real-world data, but it is frequently the case that the relevant data is not completely known to the agent performing the optimization; it is natural to model such settings using probability distributions associated with the data. In such analyses, the constraints associated with the optimization problem are now themselves "stochastic," and a standard goal is to maximize the likelihood of satisfying all the constraints while incurring minimum cost. (As a motivating example, an airline may wish to operate as few flights as possible while ensuring that with 99% probability, no passenger is bumped.) Apart from modeling uncertainty, optimization with stochastic constraints also provides a way to succinctly model constraints whose standard description is very large; design problems in voting theory, where there are very many voters, are examples of this kind. This project studies both of these kinds of problems, called stochastic design problems, from a unified new perspective based on techniques from computational complexity theory. The project also trains graduate students who will achieve fluency both in complexity theory and in optimization, and will promote cross-disciplinary activities between operations research and theoretical computer science. The motivating insight which underlies this project is that Boolean function analysis -- a topic at the intersection of harmonic analysis, probability theory, and complexity theory -- provides a useful suite of techniques for stochastic design problems. The investigators will study two broad topics. The first one is on chance-constrained optimization: In problems of this sort, one is given a set of stochastic constraints and the aim is to satisfy all the constraints with at least a certain fixed threshold probability. While previous work on such problems has typically achieved computationally efficient algorithms by relaxing the actual set of constraints, the investigators will focus on algorithms which exactly satisfy the original given set of stochastic constraints. This line of work will address the chance-constrained versions of fundamental optimization problems such as bin packing, knapsack, and linear programming. The second broad topic is that of inverse problems in social choice theory: Game theorists use so-called "power indices" to measure the influence of voters in voting schemes. A basic algorithmic problem is to design efficient algorithms for the inverse problem, in which, given a set of prescribed power indices, the goal is to construct a voting game with these indices. The investigators will study questions such as (a) to what extent is a given voting scheme specified by its power indices? (b) what is the complexity of exactly reconstructing an unknown target voting game given its power indices? (c) when and to what extent is reconstruction possible in a partial information setting?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.