Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
478034 | European Journal of Operational Research | 2006 | 4 Pages |
Abstract
We show that the following problem is NP-hard, and hence computationally intractable: “Given d weighted majority games, decide whether the dimension of their intersection exactly equals d”. Our result indicates that the dimension of simple monotonic games is a combinatorially complicated concept.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Vladimir G. Deı̆neko, Gerhard J. Woeginger,