TY - JOUR
T1 - Easy weighted majority games
AU - Chakravarty, Nilotpal
AU - Goel, Anand Mohan
AU - Sastry, Trilochan
PY - 2000/9
Y1 - 2000/9
N2 - In a weighted majority game each player has a positive integer weight and there is a positive integer quota. A coalition of players is winning (losing) if the sum of the weights of its members exceeds (does not exceed) the quota. A player is pivotal for a coalition if her omission changes it from a winning to a losing one. Most game theoretic measures of the power of a player involve the computation of the number of coalitions for which that player is pivotal. Prasad and Kelly [Prasad, K., Kelly, J.S., 1990. NP-completeness of some problems concerning voting games. International Journal of Game Theory 19, 1-9] prove that the problem of determining whether or not there exists a coalition for which a given player is pivotal is NP-complete. They also prove that counting the number of coalitions for which a given player is pivotal is #P-complete. In the present paper we exhibit classes of weighted majority games for which these problems are easy.
AB - In a weighted majority game each player has a positive integer weight and there is a positive integer quota. A coalition of players is winning (losing) if the sum of the weights of its members exceeds (does not exceed) the quota. A player is pivotal for a coalition if her omission changes it from a winning to a losing one. Most game theoretic measures of the power of a player involve the computation of the number of coalitions for which that player is pivotal. Prasad and Kelly [Prasad, K., Kelly, J.S., 1990. NP-completeness of some problems concerning voting games. International Journal of Game Theory 19, 1-9] prove that the problem of determining whether or not there exists a coalition for which a given player is pivotal is NP-complete. They also prove that counting the number of coalitions for which a given player is pivotal is #P-complete. In the present paper we exhibit classes of weighted majority games for which these problems are easy.
UR - http://www.scopus.com/inward/record.url?scp=0043281213&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0043281213&partnerID=8YFLogxK
U2 - 10.1016/S0165-4896(99)00050-5
DO - 10.1016/S0165-4896(99)00050-5
M3 - Article
AN - SCOPUS:0043281213
SN - 0165-4896
VL - 40
SP - 227
EP - 235
JO - Mathematical social sciences
JF - Mathematical social sciences
IS - 2
ER -