The Library
Two hardness results for Gamson’s game
Tools
Tools
Tools
Deineko, Vladimir G. and Woeginger, Gerhard J. (2014) Two hardness results for Gamson’s game. Social Choice and Welfare, 43 (4). pp. 963-972. doi:10.1007/s00355-014-0819-6 ISSN 0176-1714.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1007/s00355-014-0819-6
Abstract
We derive two hardness results on stable winning coalitions in Gamson’s game. First, it is coNP-complete to decide whether there exists a stable winning coalition that is connected. Secondly, it is Δ2P-complete to decide whether there exists a stable winning coalition that includes a weakest player. Our results precisely pinpoint the computational complexity of both problems, and they indicate a negative answer to a recent question of Le Breton et al. (2008, Soc Choice Welf 30:57–67).
| Item Type: | Journal Article | ||||||
|---|---|---|---|---|---|---|---|
| Divisions: | Faculty of Social Sciences > Warwick Business School | ||||||
| Journal or Publication Title: | Social Choice and Welfare | ||||||
| Publisher: | Springer | ||||||
| ISSN: | 0176-1714 | ||||||
| Official Date: | December 2014 | ||||||
| Dates: |
|
||||||
| Volume: | 43 | ||||||
| Number: | 4 | ||||||
| Page Range: | pp. 963-972 | ||||||
| DOI: | 10.1007/s00355-014-0819-6 | ||||||
| Status: | Peer Reviewed | ||||||
| Publication Status: | Published | ||||||
| Access rights to Published version: | Restricted or Subscription Access |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
