کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
478569 1446106 2011 15 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Power indices of simple games and vector-weighted majority games by means of binary decision diagrams
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله
Power indices of simple games and vector-weighted majority games by means of binary decision diagrams
چکیده انگلیسی

A simple game is a pair consisting of a finite set N   of players and a set W⊆2NW⊆2N 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 O(nQ)O(nQ) 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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Operational Research - Volume 210, Issue 2, 16 April 2011, Pages 258–272
نویسندگان
,