text: 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.
  @cite_35: This paper is a twofold contribution. First, it contributes to the problem of enumerating some classes of simple games and in particular provides the number of weighted games with minimum and the number of weighted games for the dual class as well. Second, we focus on the special case of bipartite complete games with minimum, and we compare and rank these games according to the behavior of some efficient power indices of players of type 1 (or of type 2). The main result of this second part establishes all allowable rankings of these games when the Shapley-Shubik power index is used on players of type 1.
  @cite_18: 
  @cite_7: We investigate voting systems with two classes of voters, for which there is a hierarchy giving each member of the stronger class more influence or important than each member of the weaker class. We deduce for voting systems one important counting fact that allows determining how many of them are for a given number of voters. In fact, the number of these systems follows a Fibonacci sequence with a smooth polynomial variation on the number of voters. On the other hand, we classify by means of some parameters which of these systems are weighted. This result allows us to state an asymptotic conjecture which is opposed to what occurs for symmetric games.
summary: There exists some litature on enumeration of special subclasses of voting games as well: see @cite_7 for linear games with two desirability classes; @cite_35 for weighted voting games with one roof; and @cite_18 for linear games with certain special types of voters and few desirability classes.