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.
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.
@cite_35 @cite_18 @cite_7
2050727325 2062270858 2151865687 1482693011
Simple games cover voting systems in which a single alternative, such as a bill or an amendment, is pitted against the status quo. A simple game or a yes–no voting system is a set of rules that specifies exactly which collections of “yea” votes yield passage of the issue at hand, each of these collections of “yea” voters forms a winning coalition. We are interested in performing a complexity analysis on problems defined on such families of games. This analysis as usual depends on the game representation used as input. We consider four natural explicit representations: winning, losing, minimal winning, and maximal losing. We first analyze the complexity of testing whether a game is simple and testing whether a game is weighted. We show that, for the four types of representations, both problems can be solved in polynomial time. Finally, we provide results on the complexity of testing whether a simple game or a weighted game is of a special type. We analyze strongness, properness, decisiveness and homogeneity, which are desirable properties to be fulfilled for a simple game. We finalize with some considerations on the possibility of representing a game in a more succinct representation showing a natural representation in which the recognition problem is hard. Abstract Completeness is a necessary condition for a simple game to be representable as a weighted voting system. This paper deals with the class of complete simple games and centers on their structure. Using an extension of Isbell's desirability relation to coalitions, different from the extension normally used, we associate with any complete simple game a lattice of coalition models based upon the types of indifferent players. We establish the basic properties of a vector with natural components and a matrix with non-negative integer entries, both closely related to the lattice, which are also shown to be characteristic invariants of the game, in the sense that they determine it uniquely up to isomorphisms. In many multiagent settings, situations arise in which agents must collectively make decisions while not every agent is supposed to have an equal amount of influence in the outcome of such a decision. Weighted voting games are often used to deal with these situations. The amount of influence that an agent has in a weighted voting game can be measured by means of various power indices. This paper studies the problem of finding a weighted voting game in which the distribution of the influence among the agents is as close as possible to a given target value. We propose a method to exactly solve this problem. This method relies on a new efficient procedure for enumerating weighted voting games of a fixed number of agents. The enumeration algorithm we propose works by exploiting the properties of a specific partial order over the class of weighted voting games. The algorithm enumerates weighted voting games of a fixed number of agents in time exponential in the number of agents, and polynomial in the number of games output. As a consequence we obtain an exact anytime algorithm for designing weighted voting games. Abstract A simple game ( P, W ) can serve as a model of a voting system in which an alternative is pitted against the status quo. In what follows, we investigate the following three aspects of such games as they apply to four real-world examples of voting systems: a characterization of weighted voting systems in terms of the ways in which coalitions can gain or lose by trading players; the application of a graph-theoretic notion of dimension to simple games and voting systems; and the consideration of a way to measure the power of a player as an interval of real numbers. American Mathematical Society Classification Numbers: 90A28, 90D80, 05C65. Journal of Economic Literature Classification Number: C71.