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
2122807012 2158578607
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. 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. 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. We state an integer linear programming formulation for the unique characterization of complete simple games, i.e. a special subclass of monotone Boolean functions. In order to apply the parametric Barvinok algorithm to obtain enumeration formulas for these discrete objects we provide a tailored decomposition of the integer programming formulation into a finite list of suitably chosen sub-cases. As for the original enumeration problem of Dedekind on Boolean functions we have to introduce some parameters to be able to derive exact formulas for small parameters. Recently, have proven an enumeration formula for complete simple games with two types of voters. We will provide a shorter proof and a new enumeration formula for complete simple games with two minimal winning vectors. This paper is a twofold contribution. First, it contributes to the problem of enumerating some classes of simple games and in particular provides the number of weighted games with minimum and the number of weighted games for the dual class as well. Second, we focus on the special case of bipartite complete games with minimum, and we compare and rank these games according to the behavior of some efficient power indices of players of type 1 (or of type 2). The main result of this second part establishes all allowable rankings of these games when the Shapley-Shubik power index is used on players of type 1. 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. 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. Plurality voting is perhaps the most commonly used way to aggregate the preferences of multiple voters. The purpose of this paper is to provide a comprehensive study of people's voting behaviour in various online settings under the Plurality rule. Our empirical methodology consisted of a voting game in which participants vote for a single candidate out of a given set. We implemented voting games that replicate two common real-world voting scenarios: In the first, a single voter votes once after seeing a large pre-election poll. In the second game, several voters play simultaneously, and change their vote as the game progresses, as in small committees. The winning candidate in each game (and hence the subject's payment) is determined using the plurality rule. For each of these settings we generated hundreds of game instances, varying conditions such as the number of voters and their preferences. We show that people can be classified into at least three groups, two of which are not engaged in any strategic behavior. The third and largest group tends to select the natural "default" action when there is no clear strategic alternative. When an active strategic decision can be made that improves their immediate payoff, people usually choose that strategic alternative. Our study has insight for multi-agent system designers in uncovering patterns that provide reasonable predictions of voters' behaviors, which may facilitate the design of agents that support people or act autonomously in voting systems. We investigate voting systems with two classes of voters, for which there is a hierarchy giving each member of the stronger class more influence or important than each member of the weaker class. We deduce for voting systems one important counting fact that allows determining how many of them are for a given number of voters. In fact, the number of these systems follows a Fibonacci sequence with a smooth polynomial variation on the number of voters. On the other hand, we classify by means of some parameters which of these systems are weighted. This result allows us to state an asymptotic conjecture which is opposed to what occurs for symmetric games. The Shapley value is a key solution concept for coalitional games in general and voting games in particular. Its main advantage is that it provides a unique and fair solution, but its main drawback is the complexity of computing it (e.g., for voting games this complexity is #p-complete). However, given the importance of the Shapley value and voting games, a number of approximation methods have been developed to overcome this complexity. Among these, Owen's multi-linear extension method is the most time efficient, being linear in the number of players. Now, in addition to speed, the other key criterion for an approximation algorithm is its approximation error. On this dimension, the multi-linear extension method is less impressive. Against this background, this paper presents a new approximation algorithm, based on randomization, for computing the Shapley value of voting games. This method has time complexity linear in the number of players, but has an approximation error that is, on average, lower than Owen's. In addition to this comparative study, we empirically evaluate the error for our method and show how the different parameters of the voting game affect it. Specifically, we show the following effects. First, as the number of players in a voting game increases, the average percentage error decreases. Second, as the quota increases, the average percentage error decreases. Third, the error is different for players with different weights; players with weight closer to the mean weight have a lower error than those with weight further away. We then extend our approximation to the more general k-majority voting games and show that, for n players, the method has time complexity O(k^2n) and the upper bound on its approximation error is O(k^2 n). Simple coalitional games are a fundamental class of cooperative games and voting games which are used to model coalition formation, resource allocation and decision making in computer science, artificial intelligence and multiagent systems. Although simple coalitional games are well studied in the domain of game theory and social choice, their algorithmic and computational complexity aspects have received less attention till recently. The computational aspects of simple coalitional games are of increased importance as these games are used by computer scientists to model distributed settings. This thesis fits in the wider setting of the interplay between economics and computer science which has led to the development of algorithmic game theory and computational social choice. A unified view of the computational aspects of simple coalitional games is presented here for the first time. Certain complexity results also apply to other coalitional games such as skill games and matching games. The following issues are given special consideration: influence of players, limit and complexity of manipulations in the coalitional games and complexity of resource allocation on networks. The complexity of comparison of influence between players in simple games is characterized. The simple games considered are represented by winning coalitions, minimal winning coalitions, weighted voting games or multiple weighted voting games. A comprehensive classification of weighted voting games which can be solved in polynomial time is presented. An efficient algorithm which uses generating functions and interpolation to compute an integer weight vector for target power indices is proposed. Voting theory, especially the Penrose Square Root Law, is used to investigate the fairness of a real life voting model. Computational complexity of manipulation in social choice protocols can determine whether manipulation is computationally feasible or not. The computational complexity and bounds of manipulation are considered from various angles including control, false-name manipulation and bribery. Moreover, the computational complexity of computing various cooperative game solutions of simple games in dierent representations is studied. Certain structural results regarding least core payos extend to the general monotone cooperative game. The thesis also studies a coalitional game called the spanning connectivity game. It is proved that whereas computing the Banzhaf values and Shapley-Shubik indices of such games is #P-complete, there is a polynomial time combinatorial algorithm to compute the nucleolus. The results have interesting significance for optimal strategies for the wiretapping game which is a noncooperative game defined on a network. 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. Let ( F ) be a family of subsets of the ground set [n] = 1, 2, . . . , n . For each ( i [n] ) we let ( p( F ,i) ) be the number of pairs of subsets that differ in the element i and exactly one of them is in ( F ). We interpret ( p( F ,i) ) as the influence of that element. The normalized Banzhaf vector of ( F ), denoted ( B( F ) ), is the vector ( (B( F ,1), ,B( F ,n)) ), where ( B( F ,i)= p( F ,i) p( F ) ) and ( p( F ) ) is the sum of all ( p( F ,i) ). The Banzhaf vector has been studied in the context of measuring voting power in voting games as well as in Boolean circuit theory. In this paper we investigate which non-negative vectors of sum 1 can be closely approximated by Banzhaf vectors of simple voting games. In particular, we show that if a vector has most of its weight concentrated in k < n coordinates, then it must be essentially the Banzhaf vector of some simple voting game with n − k dummy voters. We study minimum integer representations of weighted games, i.e. representations where the weights are integers and every other integer representation is at least as large in each component. Those minimum integer representations, if they exist at all, are linked with some solution concepts in game theory. Closing existing gaps in the literature, we prove that each weighted game with two types of voters admits a (unique) minimum integer representation, and give new examples for more than two types of voters without a minimum integer representation. We characterize the possible weights in minimum integer representations and give examples for t≥4 types of voters without a minimum integer representation preserving types, i.e. where we additionally require that the weights are equal within equivalence classes of voters. In the following paper we offer a method for the a priori evaluation of the division of power among the various bodies and members of a legislature or committee system. The method is based on a technique of the mathematical theory of games, applied to what are known there as “simple games” and “weighted majority games.” We apply it here to a number of illustrative cases, including the United States Congress, and discuss some of its formal properties. The designing of the size and type of a legislative body is a process that may continue for many years, with frequent revisions and modifications aimed at reflecting changes in the social structure of the country; we may cite the role of the House of Lords in England as an example. The effect of a revision usually cannot be gauged in advance except in the roughest terms; it can easily happen that the mathematical structure of a voting system conceals a bias in power distribution unsuspected and unintended by the authors of the revision. How, for example, is one to predict the degree of protection which a proposed system affords to minority interests? Can a consistent criterion for “fair representation” be found? It is difficult even to describe the net effect of a double representation system such as is found in the U. S. Congress (i.e., by states and by population), without attempting to deduce it a priori . The method of measuring “power” which we present in this paper is intended as a first step in the attack on these problems. Many multiagent domains where cooperation among agents is crucial to achieving a common goal can be modeled as coalitional games. However, in many of these domains, agents are unequal in their power to affect the outcome of the game. Prior research on weighted voting games has explored power indices, which reflect how much "real power" a voter has. Although primarily used for voting games, these indices can be applied to any simple coalitional game. Computing these indices is known to be computationally hard in various domains, so one must sometimes resort to approximate methods for calculating them. We suggest and analyze randomized methods to approximate power indices such as the Banzhaf power index and the Shapley-Shubik power index. Our approximation algorithms do not depend on a specific representation of the game, so they can be used in any simple coalitional game. Our methods are based on testing the game's value for several sample coalitions. We also show that no approximation algorithm can do much better for general coalitional games, by providing lower bounds for both deterministic and randomized algorithms for calculating power indices. Understanding the nature of strategic voting is the holy grail of social choice theory, where game-theory, social science and recently computational approaches are all applied in order to model the incentives and behavior of voters. In a recent paper, (2014) made another step in this direction, by suggesting a behavioral game-theoretic model for voters under uncertainty. For a specific variation of best-response heuristics, they proved initial existence and convergence results in the Plurality voting system. This paper extends the model in multiple directions, considering voters with different uncertainty levels, simultaneous strategic decisions, and a more permissive notion of best-response. It is proved that a voting equilibrium exists even in the most general case. Further, any society voting in an iterative setting is guaranteed to converge to an equilibrium. An alternative behavior is analyzed, where voters try to minimize their worst-case regret. As it turns out, the two behaviors coincide in the simple setting of (2014), but not in the general case. The new voting system of the Council of the European Union cannot be represented as the intersection of six or fewer weighted games, i.e., its dimension is at least 7. This sets a new record for real-world voting bodies. A heuristic combination of different discrete optimization methods yields a representation as the intersection of 13368 weighted games. Determination of the exact dimension is posed as a challenge to the community. The system's Boolean dimension is proven to be 3. Preface. 1. Structures. 2. Linear optimization methods. 3. Discrete convex analysis. 4. Computational complexity. 5. Restricted games by partition systems. 6. Restricted games by union stable systems. 7. Values for games on convex geometries. 8. Values for games on matroids. 9. The core, the selectope and the Weber set. 10. Simple games on closure spaces. 11. Voting power. 12. Computing values with Mathematica. Bibliography. Index. Many multiagent domains where cooperation among agents is crucial to achieving a common goal can be modeled as coalitional games. However, in many of these domains, agents are unequal in their power to affect the outcome of the game. Prior research on weighted voting games has explored power indices, which reflect how much "real power" a voter has. Although primarily used for voting games, these indices can be applied to any simple coalitional game. Computing these indices is known to be computationally hard in various domains, so one must sometimes resort to approximate methods for calculating them. We suggest and analyze randomized methods to approximate power indices such as the Banzhaf power index and the Shapley---Shubik power index. Our approximation algorithms do not depend on a specific representation of the game, so they can be used in any simple coalitional game. Our methods are based on testing the game's value for several sample coalitions. We show that no approximation algorithm can do much better for general coalitional games, by providing lower bounds for both deterministic and randomized algorithms for calculating power indices. We also provide empirical results regarding our method, and show that it typically achieves much better accuracy and confidence than those required.