Vi studerar komplexiteten i följande problem: Med tanke på två viktade röstningsspel G ′ och G ′′ att varje innehåller en spelare p, i vilken av dessa spel är p: s power index värde högre? Vi studerar detta problem både med avseende på effektindexet Shapley-Shubik [SS54] och effektindexet Banzhaf [Ban65, DS79]. Vårt huvudsakliga resultat är att för båda dessa effektindex är problemet komplett för probabilistisk polynomtid (dvs. är PP-fullständig). Vi tillämpar våra resultat för att delvis lösa några nyligen föreslagna problem när det gäller komplexiteten i viktade röstspel. Vi studerar även komplexiteten i det råa effektindexet Shapley-Shubik. Deng och Papadimitriou [DP94] visade att det råa effektindexet Shapley-Shubik är #P-metric complete. Vi stärker detta genom att visa att det råa effektindexet Shapley-Shubik är många-ett komplett för #P. Och vår förstärkning kan omöjligen förbättras ytterligare till parsimonisk fullständighet, eftersom vi observerar att det råa effektindexet Shapley-Shubik inte är #P-parsimoniskt-komplett.
Dessutom visar REF att en jämförelse mellan spelarens makt i två olika viktade röstspel är PP-komplett för båda indexen.
The Complexity of Power-Index Comparison
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}