NP-completeness of some problems concerning voting games
type: Item
instance of: scholarly article
title: NP-completeness of some problems concerning voting games
zbMATH Open document ID: 0705.90103
DOI: 10.1007/BF01753703
author: Elsie Sterbin Gottlieb
published in: International Journal of Game Theory
publication date: 1990-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 91A12
Mathematics Subject Classification ID: 91B12
Mathematics Subject Classification ID: 90C60
Mathematics Subject Classification ID: 91B14
zbMATH DE Number: 4158422
zbMATH Keywords: Coalition voting games
reviewed by: Milan Mareš
MaRDI profile type: Publication
cites work: Q4198056
cites work: Q3252269
cites work: The complexity of computing the permanent
description: scientific article; zbMATH DE number 4158422