The inverse Banzhaf problem

Let ${\mathcal{F}}Let F{\mathcal{F}} be a family of subsets of the ground set n] = {1, 2, . . . , n}. For each i ? n]{i \in n]} we let p(F,i){p(\mathcal{F},i)} be the number of pairs of subsets that differ in the element i and exactly one of them is in F{\mathcal{F}}. We interpret p(F,i){p(\mathcal{F},i)} as the influence of that element. The normalized Banzhaf vector of F{\mathcal{F}}, denoted B(F){B(\mathcal{F})}, is the vector (B(F,1),...,B(F,n)){(B(\mathcal{F},1),\dots,B(\mathcal{F},n))}, where B(F,i)=\fracp(F,i)p(F){B(\mathcal{F},i)=\frac{p(\mathcal{F},i)}{p(\mathcal{F})}} and p(F){p(\mathcal{F})} is the sum of all p(F,i){p(\mathcal{F},i)}. The Banzhaf vector has been studied in the context of measuring voting power in voting games as well as in Boolean circuit theory. In this paper we investigate which non-negative vectors of sum 1 can be closely approximated by Banzhaf vectors of simple voting games. In particular, we show that if a vector has most of its weight concentrated in k < n coordinates, then it must be essentially the Banzhaf vector of some simple voting game with n − k dummy voters.