Página 1 dos resultados de 73 itens digitais encontrados em 0.001 segundos

## Information transmission in coalitional voting games

Serrano, Roberto; Vohra, Rajiv
Tipo: Trabalho em Andamento Formato: application/pdf
Relevância na Pesquisa
48.217705%
A core allocation of a complete information economy can be characterized as one that would not be unanimously rejected in favor of another feasible alternative by any coalition. We use this test of coalitional voting in an incomplete information environment to formalize a notion of resilience. Since information transmission is implicit in the Bayesian equilibria of such voting games, this approach makes it possible to derive core concepts in which the transmission of information among members of a coalition is endogenous. Our results lend support to the credible core of Dutta and Vohra [4] and the core proposed by Myerson [11] as two that can be justified in terms of coalitional voting

## Applying integer programming techniques to find minimum integer weights of voting games

Strauss, Aaron B., 1980-
Fonte: Massachusetts Institute of Technology Publicador: Massachusetts Institute of Technology
Tipo: Tese de Doutorado Formato: 76 p.; 3809395 bytes; 3817408 bytes; application/pdf; application/pdf
Português
Relevância na Pesquisa
48.04603%
Using concepts from computer science and mathematics I develop three algorithms to find the minimum integer weights for voting games. Games with up to at least 17 players can be solved in a reasonable amount of time. First, coalitions are mapped to constraints, reducing the problem to constraint optimization. The optimization techniques used are Gomory's all-integer simplex algorithm and a variant of the popular integer programming method branch and bound. Theoretical results include that minimum integer weights are not unique and a confirmation of a prior result that minimum integer weights are proportional to a priori seat share. Thus, these algorithms can be useful for researchers evaluating the differences between proportional bargaining models and formateur models. The running times of the different algorithms are contrasted and analyzed for potential improvements.; by Aaron B. Strauss.; Thesis (M. Eng.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2003.; Includes bibliographical references (p. 73-76).

## The Cost of Stability in Coalitional Games

Bachrach, Yoram; Elkind, Edith; Meir, Reshef; Pasechnik, Dmitrii; Zuckerman, Michael; Rothe, Joerg; Rosenschein, Jeffrey S.
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
37.871426%
A key question in cooperative game theory is that of coalitional stability, usually captured by the notion of the \emph{core}--the set of outcomes such that no subgroup of players has an incentive to deviate. However, some coalitional games have empty cores, and any outcome in such a game is unstable. In this paper, we investigate the possibility of stabilizing a coalitional game by using external payments. We consider a scenario where an external party, which is interested in having the players work together, offers a supplemental payment to the grand coalition (or, more generally, a particular coalition structure). This payment is conditional on players not deviating from their coalition(s). The sum of this payment plus the actual gains of the coalition(s) may then be divided among the agents so as to promote stability. We define the \emph{cost of stability (CoS)} as the minimal external payment that stabilizes the game. We provide general bounds on the cost of stability in several classes of games, and explore its algorithmic properties. To develop a better intuition for the concepts we introduce, we provide a detailed algorithmic study of the cost of stability in weighted voting games, a simple but expressive class of games which can model decision-making in political bodies...

## Computing voting power in easy weighted voting games

Aziz, Haris; Paterson, Mike
Tipo: Artigo de Revista Científica
Português
Relevância na Pesquisa
48.80027%
Weighted voting games are ubiquitous mathematical models which are used in economics, political science, neuroscience, threshold logic, reliability theory and distributed systems. They model situations where agents with variable voting weight vote in favour of or against a decision. A coalition of agents is winning if and only if the sum of weights of the coalition exceeds or equals a specified quota. The Banzhaf index is a measure of voting power of an agent in a weighted voting game. It depends on the number of coalitions in which the agent is the difference in the coalition winning or losing. It is well known that computing Banzhaf indices in a weighted voting game is NP-hard. We give a comprehensive classification of weighted voting games which can be solved in polynomial time. Among other results, we provide a polynomial ($O(k{(\frac{n}{k})}^k)$) algorithm to compute the Banzhaf indices in weighted voting games in which the number of weight values is bounded by $k$.; Comment: 12 pages, Presented at the International Symposium on Combinatorial Optimization 2008

## Power Distribution in Randomized Weighted Voting: the Effects of the Quota

Oren, Joel; Filmus, Yuval; Zick, Yair; Bachrach, Yoram
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
37.859373%
We study the Shapley value in weighted voting games. The Shapley value has been used as an index for measuring the power of individual agents in decision-making bodies and political organizations, where decisions are made by a majority vote process. We characterize the impact of changing the quota (i.e., the minimum number of seats in the parliament that are required to form a coalition) on the Shapley values of the agents. Contrary to previous studies, which assumed that the agent weights (corresponding to the size of a caucus or a political party) are fixed, we analyze new domains in which the weights are stochastically generated, modelling, for example, elections processes. We examine a natural weight generation process: the Balls and Bins model, with uniform as well as exponentially decaying probabilities. We also analyze weights that admit a super-increasing sequence, answering several open questions pertaining to the Shapley values in such games.

## Generating functions partitioning algorithm for computing power indices in weighted voting games

Meglicki, Bartosz
Tipo: Artigo de Revista Científica
Português
Relevância na Pesquisa
37.503025%
In this paper new algorithm for calculating power indices is described. The complexity class of the problem is #P-complete and even calculating power index of the biggest player is NP-hard task. Constructed algorithm is a mix of ideas of two algorithms: Klinz & Woeginger partitioning algorithm and Mann & Shapley generating functions algorithm. Time and space complexities of the algorithm are analysed and compared with other known algorithms for the problem. Constructed algorithm has pessimistic time complexity O(n 2^(n/2))and pseudopolynomial complexity O(nq), where q is quota of the voting game. This paper also solves open problem stated by H. Aziz and M. Paterson - existence of the algorithm for calculating Banzhaf power indices of all players with time complexity lower than O(n^2 2^(n/2)). Not only is the answer positive but this can be done keeping the pseudopolynomial complexity of generating functions algorithm in case weights are integers. New open problems are stated.; Comment: 15 pages, algorithm pessimistic complexity O(n 2^(n/2)), pseudopolynomial complexity O(nq), calculates Banzhaf indices of all players, #P-complete problem. Minor errors corrected. Explicit explanation of general (non-integer) case without pseudopolynomial complexity

## On minimum sum representations for weighted voting games

Kurz, Sascha
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
48.6117%
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. Freixas and Molinero 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.; Comment: 6 pages, 3 tables

## Equilibrium Refinement through Negotiation in Binary Voting

Grandi, Umberto; Grossi, Davide; Turrini, Paolo
Tipo: Artigo de Revista Científica
Português
Relevância na Pesquisa
37.724849%
We study voting games on binary issues, where voters might hold an objective over some issues at stake, while willing to strike deals on the remaining ones, and can influence one another's voting decision before the vote takes place. We analyse voters' rational behaviour in the resulting two-phase game, showing under what conditions undesirable equilibria can be removed as an effect of the pre-vote phase.

## On $\alpha$-roughly weighted games

Freixas, Josep; Kurz, Sascha
Tipo: Artigo de Revista Científica
Português
Relevância na Pesquisa
37.81523%
Gvozdeva, Hemaspaandra, and Slinko (2011) have introduced three hierarchies for simple games in order to measure the distance of a given simple game to the class of (roughly) weighted voting games. Their third class $\mathcal{C}_\alpha$ consists of all simple games permitting a weighted representation such that each winning coalition has a weight of at least 1 and each losing coalition a weight of at most $\alpha$. For a given game the minimal possible value of $\alpha$ is called its critical threshold value. We continue the work on the critical threshold value, initiated by Gvozdeva et al., and contribute some new results on the possible values for a given number of voters as well as some general bounds for restricted subclasses of games. A strong relation beween this concept and the cost of stability, i.e. the minimum amount of external payment to ensure stability in a coalitional game, is uncovered.; Comment: 26 pages, 4 tables

## Computing the nucleolus of weighted voting games

Elkind, Edith; Pasechnik, Dmitrii V.
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
48.695728%
Weighted voting games (WVG) are coalitional games in which an agent's contribution to a coalition is given by his it weight, and a coalition wins if its total weight meets or exceeds a given quota. These games model decision-making in political bodies as well as collaboration and surplus division in multiagent domains. The computational complexity of various solution concepts for weighted voting games received a lot of attention in recent years. In particular, Elkind et al.(2007) studied the complexity of stability-related solution concepts in WVGs, namely, of the core, the least core, and the nucleolus. While they have completely characterized the algorithmic complexity of the core and the least core, for the nucleolus they have only provided an NP-hardness result. In this paper, we solve an open problem posed by Elkind et al. by showing that the nucleolus of WVGs, and, more generally, k-vector weighted voting games with fixed k, can be computed in pseudopolynomial time, i.e., there exists an algorithm that correctly computes the nucleolus and runs in time polynomial in the number of players and the maximum weight. In doing so, we propose a general framework for computing the nucleolus, which may be applicable to a wider of class of games.; Comment: LaTeX...

## False name manipulations in weighted voting games: splitting, merging and annexation

Aziz, Haris; Paterson, Mike
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
48.68951%
An important aspect of mechanism design in social choice protocols and multiagent systems is to discourage insincere and manipulative behaviour. We examine the computational complexity of false-name manipulation in weighted voting games which are an important class of coalitional voting games. Weighted voting games have received increased interest in the multiagent community due to their compact representation and ability to model coalitional formation scenarios. Bachrach and Elkind in their AAMAS 2008 paper examined divide and conquer false-name manipulation in weighted voting games from the point of view of Shapley-Shubik index. We analyse the corresponding case of the Banzhaf index and check how much the Banzhaf index of a player increases or decreases if it splits up into sub-players. A pseudo-polynomial algorithm to find the optimal split is also provided. Bachrach and Elkind also mentioned manipulation via merging as an open problem. In the paper, we examine the cases where a player annexes other players or merges with them to increase their Banzhaf index or Shapley-Shubik index payoff. We characterize the computational complexity of such manipulations and provide limits to the manipulation. The annexation non-monotonicity paradox is also discovered in the case of the Banzhaf index. The results give insight into coalition formation and manipulation.; Comment: Preprint of AAMAS 2009 (Eighth International Conference on Autonomous Agents and Multiagent Systems) paper

## False-Name Manipulation in Weighted Voting Games is Hard for Probabilistic Polynomial Time

Rey, Anja; Rothe, Jörg
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
48.217705%
False-name manipulation refers to the question of whether a player in a weighted voting game can increase her power by splitting into several players and distributing her weight among these false identities. Analogously to this splitting problem, the beneficial merging problem asks whether a coalition of players can increase their power in a weighted voting game by merging their weights. Aziz et al. [ABEP11] analyze the problem of whether merging or splitting players in weighted voting games is beneficial in terms of the Shapley-Shubik and the normalized Banzhaf index, and so do Rey and Rothe [RR10] for the probabilistic Banzhaf index. All these results provide merely NP-hardness lower bounds for these problems, leaving the question about their exact complexity open. For the Shapley--Shubik and the probabilistic Banzhaf index, we raise these lower bounds to hardness for PP, "probabilistic polynomial time", and provide matching upper bounds for beneficial merging and, whenever the number of false identities is fixed, also for beneficial splitting, thus resolving previous conjectures in the affirmative. It follows from our results that beneficial merging and splitting for these two power indices cannot be solved in NP, unless the polynomial hierarchy collapses...

## Solving Weighted Voting Game Design Problems Optimally: Representations, Synthesis, and Enumeration

de Keijzer, Bart; Klos, Tomas B.; Zhang, Yingqian
Tipo: Artigo de Revista Científica
Português
Relevância na Pesquisa
38.496833%
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...

## Complexity of comparison of influence of players in simple games

Aziz, Haris
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
38.854988%
Coalitional voting games appear in different forms in multi-agent systems, social choice and threshold logic. In this paper, the complexity of comparison of influence between players in coalitional voting games is characterized. The possible representations of simple games considered are simple games represented by winning coalitions, minimal winning coalitions, weighted voting game or a multiple weighted voting game. The influence of players is gauged from the viewpoint of basic player types, desirability relations and classical power indices such as Shapley-Shubik index, Banzhaf index, Holler index, Deegan-Packel index and Chow parameters. Among other results, it is shown that for a simple game represented by minimal winning coalitions, although it is easy to verify whether a player has zero or one voting power, computing the Banzhaf value of the player is #P-complete. Moreover, it is proved that multiple weighted voting games are the only representations for which it is NP-hard to verify whether the game is linear or not. For a simple game with a set W^m of minimal winning coalitions and n players, a O(n.|W^m|+(n^2)log(n)) algorithm is presented which returns `no' if the game is non-linear and returns the strict desirability ordering otherwise. The complexity of transforming simple games into compact representations is also examined.; Comment: Latex...

## False-Name Manipulations in Weighted Voting Games

Aziz, Haris; Bachrach, Yoram; Elkind, Edith; Paterson, Mike
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
38.04603%
Weighted voting is a classic model of cooperation among agents in decision-making domains. In such games, each player has a weight, and a coalition of players wins the game if its total weight meets or exceeds a given quota. A players power in such games is usually not directly proportional to his weight, and is measured by a power index, the most prominent among which are the Shapley-Shubik index and the Banzhaf index.In this paper, we investigate by how much a player can change his power, as measured by the Shapley-Shubik index or the Banzhaf index, by means of a false-name manipulation, i.e., splitting his weight among two or more identities. For both indices, we provide upper and lower bounds on the effect of weight-splitting. We then show that checking whether a beneficial split exists is NP-hard, and discuss efficient algorithms for restricted cases of this problem, as well as randomized algorithms for the general case. We also provide an experimental evaluation of these algorithms. Finally, we examine related forms of manipulative behavior, such as annexation, where a player subsumes other players, or merging, where several players unite into one. We characterize the computational complexity of such manipulations and provide limits on their effects. For the Banzhaf index...

## Efficiency, Equity, and Timing of Voting Mechanisms

Battaglini, Marco; Morton, Rebecca; Palfrey, Thomas R.
Fonte: Instituto de Tecnologia da Califórnia Publicador: Instituto de Tecnologia da Califórnia
Tipo: Article; PeerReviewed Formato: application/pdf
Relevância na Pesquisa
38.142397%
We compare the behavior of voters under simultaneous and sequential voting rules when voting is costly and information is incomplete. In many political institutions, ranging from small committees to mass elections, voting is sequential, which allows some voters to know the choices of earlier voters. For a stylized model, we generate a variety of predictions about the relative efficiency and participation equity of these two systems, which we test using controlled laboratory experiments. Most of the qualitative predictions are supported by the data, but there are significant departures from the predicted equilibrium strategies, in both the sequential and the simultaneous voting games. We find a tradeoff between information aggregation, efficiency, and equity in sequential voting: a sequential voting rule aggregates information better than simultaneous voting and is more efficient in some information environments, but sequential voting is inequitable because early voters bear more participation costs.

## A Social choice lemma on voting over lotteries with applications to a class of dynamic games

Banks, Jeffrey S.; Duggan, John
Fonte: Springer Verlag Publicador: Springer Verlag
Tipo: Article; PeerReviewed Formato: application/pdf
Relevância na Pesquisa
37.859373%
We prove a lemma characterizing majority preferences over lotteries on a subset of Euclidean space. Assuming voters have quadratic von Neumann-Morgenstern utility representations, and assuming existence of a majority undominated (or "core") point, the core voter is decisive: one lottery is majority-preferred to another if and only if this is the preference of the core voter. Several applications of this result to dynamic voting games are discussed.

## A Social choice lemma on voting over lotteries with applications to a class of dynamic games

Banks, Jeffrey S.; Duggan, John
Fonte: California Institute of Technology Publicador: California Institute of Technology
Tipo: Report or Paper; PeerReviewed Formato: application/pdf
Relevância na Pesquisa
37.859373%
We prove a lemma characterizing majority preferences over lotteries on a subset of Euclidean space. Assuming voters have quadratic von Neumann-Morgenstern utility representations, and assuming existence of a majority undominated (or "core") point, the core voter is decisive: one lottery is majority-preferred to another if and only if this is the preference of the core voter. Several applications of this result to dynamic voting games are discussed.

## Mathematical structures of simple voting games

Machover, Moshé; Terrington, Simon D.
Fonte: Elsevier B.V Publicador: Elsevier B.V
Tipo: Article; PeerReviewed Formato: application/pdf
Relevância na Pesquisa
48.04603%
We address simple voting games (SVGs) as mathematical objects in their own right, and study structures made up of these objects, rather than focusing on SVGs primarily as co-operative games. To this end it is convenient to employ the conceptual framework and language of category theory. This enables us to uncover the underlying unity of the basic operations involving SVGs.

## Strategic agents in voting games.

Hortala-Vallve, Rafael
Fonte: London School of Economics and Political Science Thesis Publicador: London School of Economics and Political Science Thesis
Tipo: Thesis; NonPeerReviewed Formato: application/pdf