Viktade rösträttsspel är en familj av kooperativa spel, som vanligtvis används för att modellera röstningssituationer där ett antal agenter (spelare) röstar emot eller för ett förslag. I sådana spel godkänns ett förslag om ett lämpligt vägt belopp av rösterna överstiger ett på förhand angivet tröskelvärde. Eftersom en spelares inflytande över röstresultatet i allmänhet inte står i proportion till hennes tilldelade vikt, har olika maktindex föreslagits för att mäta varje spelares inflytande. Det omvända effektindex problemet är problemet med att utforma en viktad röstspel som uppnår en uppsättning mål influenser enligt ett fördefinierat effektindex. I detta arbete studerar vi det inversa problemets beräkningskomplexitet när effektindexet tillhör klassen semivärden. Vi bevisar att det omvända problemet är beräkningsbart intractable för en bred familj av semivärden, inklusive alla regelbundna semivärden. Som ett specialfall av vårt allmänna resultat etablerar vi beräkningshårdhet av det omvända problemet för Banzhaf-indexen och Shapley-värdena, utan tvekan de mest populära maktindexen.
Diakonikolas och Pavlou REF betonade det omvända kraftindex problemet i utformningen av viktade röstningsspel och visade att problemet är beräkningsbart intractable för en bred familj av semi-värden.
On the Complexity of the Inverse Semivalue Problem for Weighted Voting Games
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}