NP-completeness of some problems concerning voting games (Q918448)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | NP-completeness of some problems concerning voting games |
scientific article |
Statements
NP-completeness of some problems concerning voting games (English)
0 references
1990
0 references
Coalition voting games with different weights of players are considered. A player is pivoting for a coalition if his participation in the coalition decides about its being winning. The paper concerns the computational NP-completeness of the problem of confirming lower bounds on the number of coalitions for which a given player is pivoting. A positive answer is proved for a few variants of the lower estimates.
0 references
Coalition voting games
0 references
