AF: Small: Collaborative Research: Boolean function analysis meets stochastic design

This proposal aims to study two different types of algorithmic problems through the lens of Boolean function analysis. The first is chance-constrained optimization problems, in which the constraints are stochastic (defined in terms of random variables) and the aim is to find an assignment which satisfies the constraints with at least some minimum threshold probability. The second is inverse power index prob-lems, which arise from social choice theory; the canonical problem of this sort is to design a voting game achieving some given specification of the “power” that each voter should have over the outcome (known as a power index). As popular power indices such as Shapley-Shubik and Banzhaf power indices admit simple probabilistic definitions, such power index problems also fit the motif of ‘stochastic design problems’ (i.e. problems where the constraints are defined in terms of random variables).