The complexity of power indices in voting games with incompatible players

We study the complexity of computing the Banzhaf index in incompatibility games. We show: 1) weak #P-completeness for computing the index when the incompatibility graph has very few maximal independent sets, 2) strong #P-completeness if the incompatibility graph is co-planar and perfect, 3) weak NP-completeness for deciding whether the index is non-zero when the incompatibility graph has few maximal independent sets. Finally, we discuss the possible existence of pseudopolynomial time algorithms to compute the index for some classes of incompatibility graphs.