Please use this identifier to cite or link to this item:
http://hdl.handle.net/2445/193061
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Jané Ballarín, Martí | - |
dc.date.accessioned | 2023-02-03T10:50:48Z | - |
dc.date.available | 2023-02-03T10:50:48Z | - |
dc.date.issued | 2023 | - |
dc.identifier.uri | http://hdl.handle.net/2445/193061 | - |
dc.description.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. | ca |
dc.format.extent | 42 p. | - |
dc.format.mimetype | application/pdf | - |
dc.language.iso | eng | ca |
dc.publisher | Universitat de Barcelona. Facultat d'Economia i Empresa | ca |
dc.relation.ispartof | UB Economics – Working Papers, 2023, E23/441 | cat |
dc.relation.ispartofseries | [WP E-Eco23/441] | ca |
dc.rights | cc-by-nc-nd, (c) Jané Ballarín et al., 2023 | - |
dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/3.0/es/ | * |
dc.source | UB Economics – Working Papers [ERE] | - |
dc.subject.classification | Teoria de grafs | cat |
dc.subject.classification | Programació (Matemàtica) | cat |
dc.subject.classification | Algorismes | cat |
dc.subject.other | Graph theory | eng |
dc.subject.other | Mathematical programming | eng |
dc.subject.other | Algorithms | eng |
dc.title | The complexity of power indices in voting games with incompatible players | ca |
dc.type | info:eu-repo/semantics/workingPaper | ca |
dc.rights.accessRights | info:eu-repo/semantics/openAccess | ca |
Appears in Collections: | UB Economics – Working Papers [ERE] |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
E23-441_Jane+Ballarin.pdf | 677.22 kB | Adobe PDF | View/Open |
This item is licensed under a
Creative Commons License