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_28: In general in an organisation whose system of governance involves weighted voting, a member's weight in terms of the number of votes and the formal power it represents differ. Power indices provide a means of analysing this difference. The paper uses new algorithms for computing power indices for large games. Three analyses are carried out: (1) the distribution of Banzhaf voting power among members in 1999; the results show that the United States has considerably more power over ordinary decisions than its weight of 17 but that the use of special supermajorities limits its power; (2) the effect of varying the majority requirement on the power of the IMF to act and the powers of members to prevent and initiate action (Coleman indices); the results show the effect of supermajorities severely limits the power to act and therefore renders the voting system ineffective in democratic terms, also the sovereignty of the United States within the IMF is effectively limited to just the power of veto; (3) the paper proposes the determination of the weights instrumentally by means of an iterative algorithm to give the required power distribution; this would be a useful procedure for determining appropriate changes in weights consequent on changes to individual countries' quotas; this is applied to the 1999 data. Policy recommendations are, first, that the IMF use only simple majority voting, and discontinue using special supermajorities, and, second, allocate voting weight instrumentally using power indices.
  @cite_19: Laruelle and WidgrA©n (1998) have raised the question of whether the allocation of voting power in the EU is fair. This paper extends some of their results insofar as (1) it deals with the consequences if the square root rule - which is the basis for calculating fair shares of voting power - is not fully applicable; (2) it calculates voting weights that lead to a fair allocation of voting power in the EU Council; and (3) it considers the effects of an EU enlargement on the fair allocation of voting power.
  @cite_43: 
  @cite_45: It has often been claimed that the current allocation of votes among EU states is not fair. In this paper we verify this assertion by carrying out an evaluation of the distribution of power among the member states. The results show that the current distribution of votes for the qualified majority does not lead to a fair distribution of power whatever definition of the EU is considered. It can not be claimed however that the current voting process has a systematic bias in favor of certain states. We also present a simple method to derive voting weights which lead to a fair allocation of power.
  @cite_31: Weighted voting games are mathematical models, used to analyse situations where voters with variable voting weight vote in favour of or against a decision. They have been applied in various political and economic organizations. Similar combinatorial models are also encountered in neuroscience, threshold logic, reliability theory and distributed systems. The calculation of voting powers of players in a weighted voting game has been extensively researched in the last few years. However, the inverse problem of designing a weighted voting game with a desirable distribution of power has received less attention. We present an elegant algorithm which uses generating functions and interpolation to compute an integer weight vector for target Banzhaf power indices. This algorithm has better performance than any other known to us. It can also be used to design egalitarian two-tier weighted voting games and a representative weighted voting game for a multiple weighted voting game.
summary: Also, some applied work has been done on the design of voting games. In two papers, one by Laruelle and Widgr 'en @cite_45 and one by Sutter @cite_19 , the distribution of voting power in the European Union is analyzed and designed using iterative methods that resemble the algorithm of Aziz @cite_31 . Similar work was done by Leech for the EU @cite_43 , and for the IMF @cite_28 .