Computing the nucleolus of weighted voting games

摘要: Weighted voting games (WVG) are coalitional in which an agent's contribution to a coalition is given by his weight, and wins if its total weight meets or exceeds quota. These model decision-making political bodies as well collaboration surplus division multiagent domains. The computational complexity of various solution concepts for weighted received lot attention recent years. In particular, Elkind et al.(2007) studied the stability-related WVGs, namely, core, least nucleolus. While they have completely characterized algorithmic core nucleolus only provided NP-hardness result. this paper, we solve open problem posed al. showing that and, more generally, k-vector with fixed k, can be computed pseudopolynomial time, i.e., there exists algorithm correctly computes runs time polynomial number players n maximum W. doing so, propose general framework computing nucleolus, may applicable wider class games.