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.
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.
@cite_14 @cite_29 @cite_52 @cite_6 @cite_39 @cite_0 @cite_23 @cite_5 @cite_34 @cite_51 @cite_66
2032670288 1609370892 2049491920 2041273777 1597956236 2153545244 1533087874
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. 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. 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) a Weighted threshold games are coalitional games in which each player has a weight (intuitively corresponding to its voting power), and a coalition is successful if the sum of its weights exceeds a given threshold. Key questions in coalitional games include finding coalitions that are stable (in the sense that no member of the coalition has any rational incentive to leave it), and finding a division of payoffs to coalition members (an imputation) that is fair. We investigate the computational complexity of such questions for weighted threshold games. We study the core, the least core, and the nucleolus, distinguishing those problems that are polynomial-time computable from those that are NP-hard, and providing pseudopolynomial and approximation algorithms for the NP-hard problems. 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:243260, 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. The dollar game represents a kind of diffusion process on a graph. Under the rules of the game some cofigurations are both stable and recurrent, and these are known as critical cofigurations. The set of critical configurations can be given the structure of an abelian group, and it turns out that the order of the group is the tree-number of the graph. Each critical configuration can be assigned a positive weight, and the generating function that enumerates critical configurations according to weight is a partial evaluation of the Tutte polynomial of the graph. It is shown that the weight enumerator can also be interpreted as a growth function, which leads to the conclusion that the (partial) Tutte polynomial itself is a growth function. 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. 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. 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, especial Weighted voting games are a popular model of collaboration in multiagent systems. In such games, each agent has a weight (intuitively corresponding to resources he can contribute), and a coalition of agents wins if its total weight meets or exceeds a given threshold. Even though coalitional stability in such games is important, existing research has nonetheless only considered the stability of the grand coalition. In this paper, we introduce a model for weighted voting games with coalition structures. This is a natural extension in the context of multiagent systems, as several groups of agents may be simultaneously at work, each serving a different task. We then proceed to study stability in this context. First, we define the CS-core, a notion of the core for such settings, discuss its non-emptiness, and relate it to the traditional notion of the core in weighted voting games. We then investigate its computational properties. We show that, in contrast with the traditional setting, it is computationally hard to decide whether a game has a non-empty CS-core, or whether a given outcome is in the CS-core. However, we then provide an efficient algorithm that verifies whether an outcome is in the CS-core if all weights are small (polynomially bounded). Finally, we also suggest heuristic algorithms for checking the non-emptiness of the CS-core.