Amb motiu del tancament d'estiu, la validació de documents es reprendrà a partir del 28 d'agost de 2026. Disculpeu les molèsties.
Con motivo del cierre de verano, la validación de documentos se reanudará a partir del 28 de agosto de 2026. Disculpad las molestias
Due to the summer closure, document validation will resume starting August 28, 2026. We apologize for any inconvenience.

Files

E23-441_Jane+Ballarin.pdf (677.22 KB)

Document type

Working paper

Publication date

2023

Publication license

cc-by-nc-nd, (c) Jané Ballarín et al., 2023
Please use this identifier to cite or link to this item: https://hdl.handle.net/2445/193061

The complexity of power indices in voting games with incompatible players

Journal Title

Authors

Director/Tutor

Journal ISSN

Volume Title

Related resource

Abstract

We study the complexity of computing the Banzhaf index in weighted voting games with cooperation restricted by an incompatibility graph. With an existing algorithm as a starting point, we use concepts from complexity theory to show that, for some classes of incompatibility graphs, the problem can be solved efficiently, as long as the players have "small" weights. We also show that for some other class of graphs it is unlikely that we can find efficient algorithms to compute the Banzhaf index in the corresponding restricted game. Finally, we discuss the complexity of deciding whether the index of a player is non-zero.

Subject

Teoria de grafs, Programació (Matemàtica), Algorismes

Subject (English)

Graph theory, Mathematical programming, Algorithms

Citation

Collections

UB Economics – Working Papers [ERE]

Citation

JANÉ BALLARÍN, Martí. The complexity of power indices in voting games with incompatible players. UB Economics – Working Papers. 2023. Vol.  E23/441. [consulted: 17 of August of 2026]. Available at: https://hdl.handle.net/2445/193061

Export metadata

JSON - METS

Share record