Weighted voting games are frequently used in decision making. Each voter has a weight and a proposal is accepted if the weight sum of the supporting voters exceeds a quota. One line of research is the efficient computation of so-called power indices measuring the influence of a voter. We treat the inverse problem: Given an influence vector and a power index, determine a weighted voting game such that the distribution of influence among the voters is as close as possible to the given target value. We present exact algorithms and computational results for the Shapley-Shubik and the (normalized) Banzhaf power index.
Coalition formation is the process of bringing together two or more agents so as to achieve goals that individuals on their own cannot, or to achieve them more efficiently. Typically, in such situations, the agents have conflicting preferences over the set of possible joint goals. Thus, before the agents realize the benefits of cooperation, they must find a way of resolving these conflicts and reaching a consensus. In this context, cooperative game theory offers the voting game as a mechanism for agents to reach a consensus. It also offers the Shapley value as a way of measuring the influence or power a player has in determining the outcome of a voting game. Given this, the designer of a voting game wants to construct a game such that a player's Shapley value is equal to some desired value. This is called the inverse Shapley value problem. Solving this problem is necessary, for instance, to ensure fairness in the players' voting powers. However, from a computational perspective, finding a player's Shapley value for a given game is #P-complete. Consequently, the problem of verifying that a voting game does indeed yield the required powers to the agents is also #P-complete. Therefore, in order to overcome this problem we present a computationally efficient approximation algorithm for solving the inverse problem. This method is based on the technique of 'successive approximations'; it starts with some initial approximate solution and iteratively updates it such that after each iteration, the approximate gets closer to the required solution. This is an anytime algorithm and has time complexity polynomial in the number of players. We also analyze the performance of this method in terms of its approximation error and the rate of convergence of an initial solution to the required one. Specifically, we show that the former decreases after each iteration, and that the latter increases with the number of players and also with the initial approximation error. This paper examines the system of Qualified Majority Voting, used by the Council of the European Union, from the perspective of enlargement of the Union. It uses an approach based on power indices due to Penrose (1946), Banzhaf (1965) and Coleman (1971) to make two analyses: (1) the question of the voting power of member countries from the point of view of fairness, and (2) the question of how the threshold number of votes required for QMV should be determined. It studies two scenarios for change from 2005 onwards envisaged by the Nice Treaty: (1) no enlargement, the EU comprising 15 member countries, and (2) full enlargement to 27 members by the accession of all the present twelve candidates. The proposal is made that fair weights be determined algorithmically as a technical or routine matter as the membership changes. The analysis of how the threshold affects power shows the trade-offs that countries face between their blocking power and the power of the Council to act. The main findings are: (1) that the weights laid down in the Nice Treaty are close to being fair, the only significant discrepancies being the under-representation of Germany and Romania, and the over-representation of Spain and Poland; (2) the threshold required for a decision is set too high for the Council to be an effective decision making body.  Lecture Notes prepared for Summer School, “EU Decision Making : Assessment and Design of Procedures”, San Sebastian, Spain, July 8-11, 2002.