A simple game (N, v) is given by a set N of n players and a partition of (2^N ) into a set ( L ) of losing coalitions L with value (v(L)=0 ) that is closed under taking subsets and a set ( W ) of winning coalitions W with (v(W)=1 ). Simple games with ( = _ p 0 _ W W ,L L p(L) p(W) 0 ).
Another way to measure the distance of a simple game to the class of weighted voting games is to use the dimension of a simple game @cite_29 , which is the smallest number of weighted voting games whose intersection equals a given simple game. However, computing the dimension of a simple game is -hard @cite_28 , and the largest dimension of a simple game with @math players is @math @cite_24 . Moreover, simple games with dimension 1 have @math , but @math may be arbitrarily large for simple games with dimension larger than 1. A simple game with @math players of type A and @math players of type B and minimal winning coalitions consisting of one player of each type has dimension 2 and @math . Hence there is no direct relation between the two distance measures. We also note that Gvozdeva, Hemaspaandra, and Slinko @cite_4 introduced two other distance parameters. One measures the power balance between small and large coalitions. The other one allows multiple thresholds instead of threshold 1 only. See @cite_4 for further details.
@cite_28 @cite_29 @cite_4 @cite_24
2089610977 2057183894 2951131197
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. This paper contributes to the program of numerical characterization and classification of simple games outlined in the classic monograph of von Neumann and Morgenstern. We suggest three possible ways to classify simple games beyond the classes of weighted and roughly weighted games. To this end we introduce three hierarchies of games and prove some relationships between their classes. We prove that our hierarchies are true (i.e., infinite) hierarchies. In particular, they are strict in the sense that more of the key “resource” (which may, for example, be the size or structure of the “tie-breaking” region where the weights of the different coalitions are considered so close that we are allowed to specify either winningness or nonwinningness of the coalition) yields the flexibility to capture strictly more games. Voting is a commonly applied method for the aggregation of the preferences of multiple agents into a joint decision. If preferences are binary, i.e., "yes" and "no", every voting system can be described by a (monotone) Boolean function @math . However, its naive encoding needs @math bits. The subclass of threshold functions, which is sufficient for homogeneous agents, allows a more succinct representation using @math weights and one threshold. For heterogeneous agents, one can represent @math as an intersection of @math threshold functions. Taylor and Zwicker have constructed a sequence of examples requiring @math and provided a construction guaranteeing @math . The magnitude of the worst-case situation was thought to be determined by in 2008, but the analysis unfortunately turned out to be wrong. Here we uncover a relation to coding theory that allows the determination of the minimum number @math for a subclass of voting systems. As an application, we give a construction for @math , i.e., there is no gain from a representation complexity point of view.