The complexity of power indices in voting games with incompatible players

Martí Jané Ballarín ()
Additional contact information
Martí Jané Ballarín: Universitat de Barcelona
Authors registered in the RePEc Author Service: Martí Jané Ballarín

No 2023/441, UB School of Economics Working Papers from University of Barcelona School of Economics

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.

Keywords: Banzhaf index; Graphs; Algorithms. (search for similar items in EconPapers)
JEL-codes: C71 (search for similar items in EconPapers)
Pages: 42 pages
Date: 2023
New Economics Papers: this item is included in nep-gth
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/2445/193061 (application/pdf)
Our link check indicates that this URL is bad, the error code is: 500 read timeout (http://hdl.handle.net/2445/193061 [302 Found]--> https://diposit.ub.edu/dspace/handle/2445/193061)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:ewp:wpaper:441web

Access Statistics for this paper

More papers in UB School of Economics Working Papers from University of Barcelona School of Economics Av. Diagonal 690, 08034 Barcelona. Contact information at EDIRC.
Bibliographic data for series maintained by University of Barcelona School of Economics ().