On the dimension of simple monotonic games

V.G. Deineko; G.J. Woeginger

doi:10.1016/j.ejor.2004.09.038

On the dimension of simple monotonic games

V.G. Deineko, G.J. Woeginger

Combinatorial Optimization

Research output: Contribution to journal › Article › Academic › peer-review

27 Citations (Scopus)

2 Downloads (Pure)

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.

Original language	English
Pages (from-to)	315-318
Journal	European Journal of Operational Research
Volume	170
Issue number	1
DOIs	https://doi.org/10.1016/j.ejor.2004.09.038
Publication status	Published - 2006

Access to Document

10.1016/j.ejor.2004.09.038

Cite this

@article{43fcec30184946839fadb10c4a3df6e0,

title = "On the dimension of simple monotonic games",

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.",

author = "V.G. Deineko and G.J. Woeginger",

year = "2006",

doi = "10.1016/j.ejor.2004.09.038",

language = "English",

volume = "170",

pages = "315--318",

journal = "European Journal of Operational Research",

issn = "0377-2217",

publisher = "Elsevier B.V.",

number = "1",

}

TY - JOUR

T1 - On the dimension of simple monotonic games

AU - Deineko, V.G.

AU - Woeginger, G.J.

PY - 2006

Y1 - 2006

N2 - 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.

AB - 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.

U2 - 10.1016/j.ejor.2004.09.038

DO - 10.1016/j.ejor.2004.09.038

M3 - Article

SN - 0377-2217

VL - 170

SP - 315

EP - 318

JO - European Journal of Operational Research

JF - European Journal of Operational Research

IS - 1

ER -

On the dimension of simple monotonic games

Abstract

Access to Document

Fingerprint

Cite this