Computing the nucleolus of weighted voting games

DSpace/Manakin Repository


Search DR-NTU

Advanced Search Subject Search


My Account

Computing the nucleolus of weighted voting games

Show simple item record

dc.contributor.author Elkind, Edith
dc.contributor.author Pasechnik, Dmitrii V.
dc.date.accessioned 2011-05-09T09:12:17Z
dc.date.available 2011-05-09T09:12:17Z
dc.date.copyright 2009
dc.date.issued 2011-05-09T09:12:17Z
dc.identifier.citation Elkind, E., & Pasechnik, D. (2009). Computing the nucleolus of weighted voting games. Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA'09) (pp.327-335).
dc.identifier.uri http://hdl.handle.net/10220/6783
dc.description.abstract Weighted voting games (WVG) are coalitional games in which an agent’s contribution to a coalition is given by his weight, and a coalition wins if its total weight meets or exceeds a given quota. These games model decision-making in political bodies as well as collaboration and surplus division in multiagent domains. The computational complexity of various solution concepts for weighted voting games received a lot of attention in recent years. In particular, Elkind et al.(2007) studied the complexity of stability related solution concepts in WVGs, namely, of the core, the least core, and the nucleolus. While they have completely characterized the algorithmic complexity of the core and the least core, for the nucleolus they have only provided an NP-hardness result. In this paper, we solve an open problem posed by Elkind et al. by showing that the nucleolus of WVGs, and, more generally, kvector weighted voting games with fixed k, can be computed in pseudopolynomial time, i.e., there exists an algorithm that correctly computes the nucleolus and runs in time polynomial in the number of players n and the maximum weight W. In doing so, we propose a general framework for computing the nucleolus, which may be applicable to a wider of class of games.
dc.format.extent 9 p.
dc.language.iso en
dc.rights © 2009 SIAM This paper was published in SODA’ 09 and is made available as an electronic reprint (preprint) with permission of Society for Industrial and Applied Mathematics. The paper can be found at the following official publisher’s URL: [http://siam.org/proceedings/soda/2009/soda09.php.] One print or electronic copy may be made for personal use only. Systematic or multiple reproduction, distribution to multiple locations via electronic or other means, duplication of any material in this paper for a fee or for commercial purposes, or modification of the content of the paper is prohibited and is subject to penalties under law.
dc.subject DRNTU::Science::Mathematics::Applied mathematics
dc.title Computing the nucleolus of weighted voting games
dc.type Conference Paper
dc.contributor.conference Symposium on Discrete Algorithms (2009 : New York, USA)
dc.contributor.school School of Physical and Mathematical Sciences
dc.identifier.openurl http://siam.org/proceedings/soda/2009/soda09.php
dc.description.version Published version

Files in this item

Files Size Format View
45. Computing t ... weighted voting games..pdf 421.5Kb PDF View/Open

This item appears in the following Collection(s)

Show simple item record


Total views

All Items Views
Computing the nucleolus of weighted voting games 636

Total downloads

All Bitstreams Views
45. Computing the nucleolus of weighted voting games..pdf 253

Top country downloads

Country Code Views
United States of America 79
Singapore 73
China 30
Russian Federation 23
France 12

Top city downloads

city Views
Singapore 73
Mountain View 47
Redwood City 5
Sunnyvale 4
Seattle 3