Computational Complexity of Weighted Threshold Games
Authors: Edith Elkind, Leslie Ann Goldberg, Paul W. Goldberg, and Michael Wooldridge
Abstract:
Weighted threshold games are coalitional games in which
each player has a weight (intuitively corresponding to its voting
power), and a coalition is successful if the sum of its
weights exceeds a given threshold. Key questions in coalitional
games include finding coalitions that are stable (in the
sense that no member of the coalition has any rational incentive
to leave it), and finding a division of payoffs to coalition
members (an imputation) that is fair. We investigate the computational
complexity of such questions for weighted threshold
games. We study the core, the least core, and the nucleolus,
distinguishing those problems that are polynomial-time
computable from those that are NP-hard, and providing pseudopolynomial
and approximation algorithms for the NP-hard
problems.