Suppose we must design a weighted voting scheme to be used by n voters to choose between two candidates. We want the i-th voter to have a certain prescribed amount of "influence" over the final outcome of the vote -- for example, the voters may correspond to states with different populations, or shareholders who hold different numbers of shares in a company. How can we design a weighted voting scheme that gives each voter the prescribed amount of influence? Of course, in order to even hope to answer such a question we need a well-defined notion of the influence of a voter in a weighted voting scheme. Many such measures of influence have been studied in the voting theory literature; such measures are sometimes called "power indices". In this talk we'll consider two of the most popular power indices: the "Banzhaf indices" (corresponding to the standard notion of influence in analysis of Boolean functions) and the "Shapley-Shubik indices". These are two quite different natural ways of of quantifying how much power each voter has over the outcome in a given weighted voting scheme. As our main results, we'll describe algorithms that solve the inverse problem of designing a weighted voting scheme for each of these power indices. Specifically, (1) Given a vector of desired Banzhaf indices for the n voters, our first algorithm efficiently constructs a weighted voting scheme which has Banzhaf indices very close to the target indices (if any such weighted voting scheme exists). Our result gives an almost doubly exponential (in terms of the closeness parameter) running time improvement over the only previous provably correct solution. (2) Given a vector of desired Shapley-Shubik indices, our second algorithm efficiently constructs a weighted voting scheme which has Shapley-Shubik indices very close to the target indices (if any such weighted voting scheme exists). This is the first algorithm for this problem with a poly(n) as opposed to exp(n) runtime. A common algorithmic ingredient underlies these two results, but the structural results used to prove correctness are very different for the two indices. Our results for Banzhaf indices are based on structural properties of linear threshold functions and geometric and linear-algebraic arguments about how hyperplanes interact with the Boolean hypercube. Our results for Shapley-Shubik indices are based on anticoncentration bounds for sums of non-independent random variables.

No background in voting theory is required for the talk.

Based on joint works with Anindya De, Ilias Diakonikolas and Vitaly Feldman.