Complexity of Merging and Splitting for the Probabilistic Banzhaf Power Index in Weighted Voting Games

摘要

The Banzhaf power index is a prominent measure of a player's influence for coalition formation in weighted voting games, an important class of simple coalitional games that are fully expressive but compactly representable. For the normalized Banzhaf index, Aziz and Paterson [1] show that it is NP-hard to decide whether merging any coalition of players is beneficial, and that in unanimity games, merging is always disadvantageous, whereas splitting is always advantageous. We show that for the probabilistic Banzhaf index (which is considered more natural than the normalized Banzhaf index), the merging problem is in P for coalitions of size two, and is NP-hard for coalitions of size at least three. We also prove a corresponding result for the splitting problem. In unanimity games and for the probabilistic Banzhaf index (in strong contrast with the results for the normalized Banzhaf index), we show that splitting is always disadvantageous or neutral, whereas merging is neutral for size-two coalitions, yet advantageous for coalitions of size at least three.