Easy weighted majority games

Nilotpal Chakravarty, Anand Mohan Goel, Trilochan Sastry

Research output: Contribution to journalArticlepeer-review

6 Scopus citations

Abstract

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.

Original languageEnglish
Pages (from-to)227-235
Number of pages9
JournalMathematical social sciences
Volume40
Issue number2
DOIs
StatePublished - Sep 2000

Fingerprint

Dive into the research topics of 'Easy weighted majority games'. Together they form a unique fingerprint.

Cite this