# A melhor ferramenta para a sua pesquisa, trabalho e TCC!

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

## Information transmission in coalitional voting games

Fonte: Universidade Carlos III de Madrid
Publicador: Universidade Carlos III de Madrid

Tipo: Trabalho em Andamento
Formato: application/pdf

Publicado em /10/2005
Português

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

Link permanente para citações:

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

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).

Link permanente para citações:

## The Cost of Stability in Coalitional Games

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 24/07/2009
Português

Relevância na Pesquisa

37.871426%

#Computer Science - Computer Science and Game Theory#Computer Science - Artificial Intelligence#Computer Science - Computational Complexity#F.2.2#G.1.6#I.2.8

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...

Link permanente para citações:

## Computing voting power in easy weighted voting games

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Português

Relevância na Pesquisa

48.80027%

#Computer Science - Computer Science and Game Theory#Computer Science - Computational Complexity#Computer Science - Data Structures and Algorithms

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

Link permanente para citações:

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

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 02/08/2014
Português

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.

Link permanente para citações:

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

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Português

Relevância na Pesquisa

37.503025%

#Computer Science - Computer Science and Game Theory#Computer Science - Data Structures and Algorithms

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

Link permanente para citações:

## On minimum sum representations for weighted voting games

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 08/03/2011
Português

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

Link permanente para citações:

## Equilibrium Refinement through Negotiation in Binary Voting

Fonte: Universidade Cornell
Publicador: Universidade Cornell

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.

Link permanente para citações:

## On $\alpha$-roughly weighted games

Fonte: Universidade Cornell
Publicador: Universidade Cornell

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

Link permanente para citações:

## Computing the nucleolus of weighted voting games

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 03/08/2008
Português

Relevância na Pesquisa

48.695728%

#Computer Science - Computer Science and Game Theory#Computer Science - Data Structures and Algorithms#G.1.6#I.2.8

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...

Link permanente para citações:

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

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 20/05/2009
Português

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

Link permanente para citações:

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

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 07/03/2013
Português

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...

Link permanente para citações:

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

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Português

Relevância na Pesquisa

38.496833%

#Computer Science - Computer Science and Game Theory#Computer Science - Artificial Intelligence#Computer Science - Multiagent Systems

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...

Link permanente para citações:

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

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 02/09/2008
Português

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...

Link permanente para citações:

## False-Name Manipulations in Weighted Voting Games

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 16/01/2014
Português

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...

Link permanente para citações:

## Efficiency, Equity, and Timing of Voting Mechanisms

Fonte: Instituto de Tecnologia da Califórnia
Publicador: Instituto de Tecnologia da Califórnia

Tipo: Article; PeerReviewed
Formato: application/pdf

Publicado em /08/2007
Português

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.

Link permanente para citações:

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

Fonte: Springer Verlag
Publicador: Springer Verlag

Tipo: Article; PeerReviewed
Formato: application/pdf

Publicado em /04/2006
Português

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.

Link permanente para citações:

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

Fonte: California Institute of Technology
Publicador: California Institute of Technology

Tipo: Report or Paper; PeerReviewed
Formato: application/pdf

Publicado em /05/2003
Português

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.

Link permanente para citações:

## Mathematical structures of simple voting games

Fonte: Elsevier B.V
Publicador: Elsevier B.V

Tipo: Article; PeerReviewed
Formato: application/pdf

Publicado em /09/2014
Português

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.

Link permanente para citações:

## Strategic agents in voting games.

Fonte: London School of Economics and Political Science Thesis
Publicador: London School of Economics and Political Science Thesis

Tipo: Thesis; NonPeerReviewed
Formato: application/pdf

Publicado em //2005
Português

Relevância na Pesquisa

38.071108%

The first part of this Thesis asks whether we can devise voting rules that allow strategic voters to express the intensity of their preferences. As opposed to the classical voting system (one person - one decision - one vote), we first propose a new voting system where agents are endowed with a fixed number of votes that can be distributed freely between a predetermined number of issues that have to be approved or dismissed. Its novelty, and appeal, relies on allowing voters to express the intensity of their preferences in a simple manner. This voting system is optimal in a well-defined sense: in a setting with two voters, two issues and uniform independent priors, Qualitative Voting Pareto dominates Majority Rule and, moreover, achieves the only ex-ante (incentive compatible) optimal allocation. The result also holds true with three voters as long as the valuations towards the issues differ sufficiently. Experimental evidence is provided supporting equilibrium predictions and showing that Qualitative Voting is better able to replicate the efficient outcome than Majority Rule. More generally in a setting with an arbitrary number of voters and issues, we show: (1) that a mechanism is implementable only if it does not undertake interpersonal comparisons of utility; (2) the impossibility of implementing strategy-proof mechanisms that are sensitive to the voters' intensities of preferences and satisfy the unanimity property. The second part of the Thesis studies the interaction between politicians' strategic behaveiour and voters' turnout decision: politicians diverge to motivate citizens to vote and they adapt their policies to the most sensitive voters -thus less sensitive voters abstain on the grounds of perceiving politicians being too similar. Moreover...

Link permanente para citações: