Computer Science – Computer Science and Game Theory
Scientific paper
2008-11-15
Computer Science
Computer Science and Game Theory
12 pages, Presented at the International Symposium on Combinatorial Optimization 2008
Scientific paper
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$.
Aziz Haris
Paterson Mike
No associations
LandOfFree
Computing voting power in easy weighted voting games does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Computing voting power in easy weighted voting games, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computing voting power in easy weighted voting games will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-39432