European Conference on Operational Research

p. 74-

Presentation's date: 2015-07-12

Abstract:

This work is a follow up of results given in [1]. Here we present some computational complexity results for specific problems and simple games. For instance, we consider the complexity of determining trade robustness for a given simple game in the four natural explicit representations: winning, losing, minimal winning, and maximal losing. Our results show that the problem is solvable in polynomial in some cases but in other it is NP-hard depending on the input and the output. We also define the j-trade application for a given simple game and we analyze how to find such j-trade application in those natural forms of representation. We conclude stating some conjectures and open problems. For instance, given a simple game, we consider how to compute the dimension and the co-dimension [2,3], and how to represent such game by a union or an intersection of some weighted games.]]>

Date: 2015-03-24

Abstract:

We analyze the computational complexity of the problem of deciding whether, for a given simple game, there exists the possibility of rearranging the participants in a set of j given losing coalitions into a set of j winning coalitions. We also look at the problem of turning winning coalitions into losing coalitions. We analyze the problem when the simple game is represented by a list of wining, losing, minimal winning or maximal loosing coalitions.]]>

RAIRO. Operations research

p. 295-314

DOI: 10.1051/ro/2011115

Date of publication: 2011-10

Abstract:

Simple games cover voting systems in which a single alter- native, such as a bill or an amendment, is pitted against the status quo. A simple game or a yes-no voting system is a set of rules that specifies exactly which collections of “yea” votes yield passage of the issue at hand. Each of these collections of “yea” voters forms a winning coalition. We are interested in performing a complexity analysis on problems defined on such families of games. This analysis as usual depends on the game representation used as input. We consider four natural explicit representations: winning, losing, minimal winning, and maximal losing. We first analyze the complexity of testing whether a game is simple and testing whether a game is weighted. We show that, for the four types of representations, both problems can be solved in polynomial time. Finally, we provide results on the complexity of testing whether a simple game or a weighted game is of a special type. We analyze strongness, properness, weightedness, homogeneousness, decisiveness and majorityness, which are desirable properties to be fulfilled for a simple game. Finally, we consider the possibility of representing a game in a more succinct and natural way and show that the corresponding recognition problem is hard.

The original publication is available at www.rairo-ro.org]]>