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_48: Lecture Notes prepared for Summer School, “EU Decision Making : Assessment and Design of Procedures”, San Sebastian, Spain, July 8-11, 2002.
  @cite_43: 
  @cite_8: A priori voting power analysis can be useful in helping to design a weighted voting system that has certain intended properties. Power indices can help determine how many weighted votes each member should be allocated and what the decision rule should be. These choices can be made in the light of a requirement that there be a given distribution of power and or a desired division of powers between individual members and the collective institution. This paper focuses on the former problem: choosing the weights given that the power indices and the decision rule are fixed exogenously.
summary: Leech proposes in @cite_48 @cite_8 an approach that largely resembles the method of : it is the same, with the exception that a different updating rule is used. The method that Leech uses for computing the Banzhaf index is not mentioned. The focus in this paper is on the results that are obtained after applying the method to the 15-member EU council (also see @cite_43 ), and to the board of governors of the International Monetary Fund.