Power indices of simple games and vector-weighted majority games by means of binary decision diagrams

Stefan Bolus

European Journal of Operational Research, 2011, vol. 210, issue 2, 258-272

Abstract: A simple game is a pair consisting of a finite set N of players and a set of winning coalitions. (Vector-) weighted majority games ((V) WMG) are a special case of simple games, in which an integer (vector) weight can be assigned to each player and there is a quota which a coalition has to achieve in order to win. Binary decision diagrams (BDDs) are used as compact representations for Boolean functions and sets of subsets. This paper shows, how a quasi-reduced and ordered BDD (QOBDD) of the winning coalitions of a (V) WMG can be build, how one can compute the minimal winning coalitions and how one can easily compute the Banzhaf, Shapley-Shubik, Holler-Packel and Deegan-Packel indices of the players. E.g. in case of weighted majority games it is shown that the Banzhaf and Holler-Packel indices of all players can be computed in expected time and in general, the Banzhaf indices can be computed in time linear in the size of the QOBDD representation of the winning coalitions. Other running times are proven as well. The algorithms were tested on some real world games, e.g. the International Monetary Fund and the EU Treaty of Nice.

Keywords: Simple; game; Vector-weighted; majority; game; Binary; decision; diagram; Threshold; function (search for similar items in EconPapers)
Date: 2011
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (20)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377-2217(10)00618-1
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:210:y:2011:i:2:p:258-272

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().