Weighted voting games are frequently used in decision making. Each voter has a weight and a proposal is accepted if the weight sum of the supporting voters exceeds a quota. One line of research is the efficient computation of so-called power indices measuring the influence of a voter. We treat the inverse problem: Given an influence vector and a power index, determine a weighted voting game such that the distribution of influence among the voters is as close as possible to the given target value. We present exact algorithms and computational results for the Shapley-Shubik and the (normalized) Banzhaf power index.
Besides using the finiteness of the set of weighted voting games, the first general bounds stating that some power distributions can not be approximated by Banzhaf vectors too closely are given by Alon and Edelman @cite_8 .
@cite_8
2043836864
Let ( F ) be a family of subsets of the ground set [n] = 1, 2, . . . , n . For each ( i [n] ) we let ( p( F ,i) ) be the number of pairs of subsets that differ in the element i and exactly one of them is in ( F ). We interpret ( p( F ,i) ) as the influence of that element. The normalized Banzhaf vector of ( F ), denoted ( B( F ) ), is the vector ( (B( F ,1), ,B( F ,n)) ), where ( B( F ,i)= p( F ,i) p( F ) ) and ( p( F ) ) is the sum of all ( p( 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.