TY - JOUR
T1 - The inverse Banzhaf problem
AU - Alon, Noga
AU - Edelman, Paul H.
N1 - Funding Information:
N. Alon’s research supported in part by an ERC Advanced grant, by a USA-Israel BSF grant, by NSF grant CCF 0832797 and by the Ambrose Monell Foundation.
PY - 2010
Y1 - 2010
N2 - LetF 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), isthevector(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.
AB - LetF 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), isthevector(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.
UR - http://www.scopus.com/inward/record.url?scp=77957280986&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=77957280986&partnerID=8YFLogxK
U2 - 10.1007/s00355-009-0402-8
DO - 10.1007/s00355-009-0402-8
M3 - Article
AN - SCOPUS:77957280986
SN - 0176-1714
VL - 34
SP - 371
EP - 377
JO - Social Choice and Welfare
JF - Social Choice and Welfare
IS - 3
ER -