This proposal aims to study two different types of algorithmic problems through the lens of Boolean function analysis. The ﬁrst is chance-constrained optimization problems, in which the constraints are stochastic (deﬁned in terms of random variables) and the aim is to ﬁnd an assignment which satisﬁes 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 speciﬁcation 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 deﬁnitions, such power index problems also ﬁt the motif of ‘stochastic design problems’ (i.e. problems where the constraints are deﬁned in terms of random variables).
|Effective start/end date||6/1/18 → 12/31/18|
- National Science Foundation (CCF-1814706)