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 the normal view instead:
scientific article; zbMATH DE number 4158422
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| 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
0.8378322124481201
0 references
0.8348817229270935
0 references
0.8348816633224487
0 references
0.8144850134849548
0 references
0.8045474290847778
0 references
