We study the inverse power index problem for weighted voting games: the problem of finding a weighted voting game in which the power of the players is as close as possible to a certain target distribution. Our goal is to find algorithms that solve this problem exactly. Thereto, we study various subclasses of simple games, and their associated representation methods. We survey algorithms and impossibility results for the synthesis problem, i.e., converting a representation of a simple game into another representation. We contribute to the synthesis problem by showing that it is impossible to compute in polynomial time the list of ceiling coalitions (also known as shift-maximal losing coalitions) of a game from its list of roof coalitions (also known as shift-minimal winning coalitions), and vice versa. Then, we proceed by studying the problem of enumerating the set of weighted voting games. We present first a naive algorithm for this, running in doubly exponential time. Using our knowledge of the synthesis problem, we then improve on this naive algorithm, and we obtain an enumeration algorithm that runs in quadratic exponential time (that is, O(2^(n^2) p(n)) for a polynomial p). Moreover, we show that this algorithm runs in output-polynomial time, making it the best possible enumeration algorithm up to a polynomial factor. Finally, we propose an exact anytime algorithm for the inverse power index problem that runs in exponential time. This algorithm is straightforward and general: it computes the error for each game enumerated, and outputs the game that minimizes this error. By the genericity of our approach, our algorithm can be used to find a weighted voting game that optimizes any exponential time computable function. We implement our algorithm for the case of the normalized Banzhaf index, and we perform experiments in order to study performance and error convergence.
Finally, a research direction that is related to our problem is that of studying minimal integer representation for a weighted voting game: Bounds on the maximum weight in such a representation provide us with a finite set of weighted representations to search through, as a means of solving our design problem. We explain this in greater detail in the next section. Some classical relevant bounds can be found in @cite_29 , Section 9.3. See @cite_69 @cite_6 for some recent work in this direction.
@cite_29 @cite_69 @cite_6
2150705893 2032670288 2049491920 1680201399
We study minimum integer representations of weighted games, i.e. representations where the weights are integers and every other integer representation is at least as large in each component. Those minimum integer representations, if they exist at all, are linked with some solution concepts in game theory. Closing existing gaps in the literature, we prove that each weighted game with two types of voters admits a (unique) minimum integer representation, and give new examples for more than two types of voters without a minimum integer representation. We characterize the possible weights in minimum integer representations and give examples for t≥4 types of voters without a minimum integer representation preserving types, i.e. where we additionally require that the weights are equal within equivalence classes of voters. A proposal in a weighted voting game is accepted if the sum of the (non-negative) weights of the “yea” voters is at least as large as a given quota. Several authors have considered representations of weighted voting games with minimum sum, where the weights and the quota are restricted to be integers. In Freixas and Molinero (Ann. Oper. Res. 166:243–260, 2009) the authors have classified all weighted voting games without a unique minimum sum representation for up to 8 voters. Here we exhaustively classify all weighted voting games consisting of 9 voters which do not admit a unique minimum sum integer weight representation. Isbell in 1959 was the first to find a weighted game without a minimum integer realization in which the affected players do not play a symmetric role in the game. His example has 12 players in a weighted decisive game, i.e. a weighted game for which a coalition wins iff its complement loses. The goal of this article is to provide a procedure for weighted games that allows finding out what is the minimum number of players needed to get a weighted game without a minimum integer weighted representation in which the affected players do not play a symmetric role in the game. We prove, by means of an algorithm, that the minimum number of voters required is nine. The new voting system of the Council of the European Union cannot be represented as the intersection of six or fewer weighted games, i.e., its dimension is at least 7. This sets a new record for real-world voting bodies. A heuristic combination of different discrete optimization methods yields a representation as the intersection of 13368 weighted games. Determination of the exact dimension is posed as a challenge to the community. The system's Boolean dimension is proven to be 3.