The Library
Classification of computationally tractable weighted voting games
Tools
Tools
Tools
Aziz, Haris and Paterson, Michael S. (2008) Classification of computationally tractable weighted voting games. In: World Congress on Engineering 2008, Imperial Coll London, London, England, Jul 02-04, 2008. Published in: World Congress on Engineering : WCE 2008 : 2-4 July, 2008, Imperial College London, London, U.K., Vol.1-2 pp. 129-134. ISBN 978-988-98671-9-5. ISSN 2078-0966.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Abstract
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 #P-complete. We give a comprehensive characterization of weighted voting games which can be solved in polynomial time. Among other results, we provide a polynomial (O(k(n/k)(k))) algorithm to compute the Banzhaf indices in weighted voting games in which the number of weight values is bounded by k.
| Item Type: | Conference Item (UNSPECIFIED) | ||||
|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
| Library of Congress Subject Headings (LCSH): | Computer algorithms, Computational complexity, Game theory | ||||
| Series Name: | Lecture Notes in Engineering and Computer Science | ||||
| Journal or Publication Title: | World Congress on Engineering : WCE 2008 : 2-4 July, 2008, Imperial College London, London, U.K. | ||||
| Publisher: | Newswood Ltd. | ||||
| ISBN: | 978-988-98671-9-5 | ||||
| ISSN: | 2078-0966 | ||||
| Editor: | Ao, SI and Gelman, L and Hukins, DWL and Hunter, A and Korsunsky, AM | ||||
| Official Date: | 2008 | ||||
| Dates: |
|
||||
| Volume: | Vol.1-2 | ||||
| Number of Pages: | 6 | ||||
| Page Range: | pp. 129-134 | ||||
| Status: | Not Peer Reviewed | ||||
| Publication Status: | Published | ||||
| Access rights to Published version: | Restricted or Subscription Access | ||||
| Title of Event: | World Congress on Engineering 2008 | ||||
| Type of Event: | Conference | ||||
| Location of Event: | Imperial Coll London, London, England | ||||
| Date(s) of Event: | Jul 02-04, 2008 |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
