Computer Science – Computer Science and Game Theory
Scientific paper
2008-08-03
Proceedings of SODA 2009, pp. 327-335
Computer Science
Computer Science and Game Theory
LaTeX, 12 pages, COMSOC-2008 workshop
Scientific paper
10.1145/1496770.1496807
Weighted voting games (WVG) are coalitional games in which an agent's contribution to a coalition is given by his it 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, k-vector 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 and the maximum weight. In doing so, we propose a general framework for computing the nucleolus, which may be applicable to a wider of class of games.
Elkind Edith
Pasechnik Dmitrii V.
No associations
LandOfFree
Computing the nucleolus of weighted voting games does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Computing the nucleolus of weighted voting games, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computing the nucleolus of weighted voting games will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-626239