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_14: 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.
  @cite_29: 
  @cite_52: 
  @cite_6: 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.
  @cite_39: 
  @cite_0: The number of threshold functions of eight variables is counted by ILLIAC II, the computer of the University of Illinois. Sets of optimum weights of majority elements realizing these functions also are investigated. Actually, canonical positive self-dual threshold functions of nine variables are investigated instead of directly investigating threshold functions of eight variables because it is easier to deal with them. The number and optimum weights of threshold functions of eight variables are easily obtained from these functions of nine variables and their realization.
  @cite_23: 
  @cite_5: 
  @cite_34: An important consideration when applying neural networks is the sensitivity to weights and threshold in strict separating systems representing a linearly separable function. Perturbations may affect weights and threshold so that it is important to estimate the maximal percentage error in weights and threshold, which may be allowed without altering the linearly separable function. In this paper, we provide the greatest allowed bound which can be associated to every strict separating system representing a linearly separable function. The proposed bound improves the tolerance that Hu obtained. Furthermore, it is the greatest bound for any strict separating system. This is the reason why we call it the greatest tolerance.
  @cite_51: 
  @cite_66: 1. Introduction. 2. Linear Threshold Element. 3. Computing Symmetric Functions. 4. Depth Efficient Arithmetic Circuits. 5. Depth-Size Tradeoffs. 6. Computing with Small Weights. 7. Rational Approximation and Optimal Size Circuits. 8. Geometric Framework and Spectral Analysis. 9. Limitations of AND-OR Circuits. 10. Lower Bounds via Communication Complexity. 11. Hopfield Network. Glossary. Bibliography. Index.
summary: Threshold functions @cite_5 @cite_29 are of fundamental research interest in voting games, circuit complexity and neural networks. The problem of realizing Boolean threshold functions by neural networks has been extensively studied @cite_51 @cite_66 @cite_34 , where upper and lower bounds are derived on the synaptic weights for such realization. The enumeration of threshold functions is closely related to the enumeration of weighted voting games (as threshold functions are essentially weighted voting games where negative weights are allowed.). The enumeration of threshold functions up to six variables has been done in @cite_52 . Subsequently, in @cite_39 @cite_0 , all threshold functions of respectively seven and eight variables were enumerated. Krohn and Sudh "olter @cite_23 enumerated the canonical weighted voting games up to eight players, as well as the class of canonical linear games. Kurz @cite_14 was the first to enumerate all nine player canonical weighted voting games, and Freixas and Molinero @cite_6 were the first to enumerate all nine player canonical linear games.