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.

Fitxers

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

Tipus de document

Document de treball

Data de publicació

2023

Llicència de publicació

cc-by-nc-nd, (c) Jané Ballarín et al., 2023
Si us plau utilitzeu sempre aquest identificador per citar o enllaçar aquest document: https://hdl.handle.net/2445/193061

The complexity of power indices in voting games with incompatible players

Títol de la revista

Autors

Director/Tutor

ISSN de la revista

Títol del volum

Recurs relacionat

Resum

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.

Matèries

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

Matèries (anglès)

Graph theory, Mathematical programming, Algorithms

Citació

Col·leccions

UB Economics – Working Papers [ERE]

Citació

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

Exportar metadades

JSON - METS

Compartir registre