NP-completeness of some problems concerning voting games (Q918448)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: NP-completeness of some problems concerning voting games |
scientific article; zbMATH DE number 4158422
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | NP-completeness of some problems concerning voting games |
scientific article; zbMATH DE number 4158422 |
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
