Miniatura

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. [consulta: 23 de gener de 2026]. [Disponible a: https://hdl.handle.net/2445/193061]

Exportar metadades

JSON - METS

Compartir registre