Under många omständigheter där flera agenter måste fatta ett gemensamt beslut används röstning för att aggregera agenternas preferenser. Varje agent röst bär en vikt, och om summan av vikterna av agenterna till förmån för något utfall är större än eller lika med en given kvot, då detta resultat beslutas. Viktfördelningen leder till en viss maktfördelning. Flera "kraftindex" har föreslagits för att mäta sådan makt. I det så kallade inversa problemet får vi en målfördelning av makt, och uppmanas att komma med ett spel-i form av en kvot, plus en tilldelning av vikter till spelarna-vars maktfördelning är så nära som möjligt till målfördelningen (enligt vissa specificerade avståndmått). Här studerar vi lösningar för den större klassen av röstspelsdesign (VGD) problem, varav ett är det omvända problemet. I det allmänna VGD-problemet är målet att hitta ett röstningsspel (med ett givet antal spelare) som optimerar vissa funktioner över dessa spel. I det omvända problemet, till exempel, letar vi efter ett viktat röstningsspel som minimerar avståndet mellan fördelningen av makt mellan spelarna och en given målfördelning av makt (enligt en given avståndsmått). Vårt mål är att hitta algoritmer som löser rösta spel design problem exakt, och vi närmar oss detta mål genom att räkna upp alla spel i klassen av spel av intresse. Vi presenterar först en dubbelt exponentiell algoritm för att räkna upp uppsättningen enkla spel. Vi förbättrar sedan på denna algoritm för klassen viktade röstspel och få en kvadratisk exponentiell (dvs, 2 O(n 2 ) ) algoritm för att räkna upp dem. Vi visar att denna förbättrade algoritm körs i utdata-polynom tid, vilket gör det snabbast möjliga uppräkning algoritm upp till en polynomial faktor. Slutligen föreslår vi en exakt när som helst-algoritm som körs i exponentiell tid för effektindex viktade röstspel design problem ("det omvända problemet"). Vi implementerar denna algoritm för att hitta en viktad röstspel med en normaliserad Banzhaf maktfördelning närmast ett mål effektindex, och utföra experiment för att få några insikter om uppsättningen viktade röstspel. Vi noterar att vår algoritm är tillämplig för att optimera någon exponentiellt-tids beräkningsbar funktion, avståndet mellan den normaliserade Banzhaf index till ett mål effektindex tas bara som ett exempel.
En annan exakt, men exponentiellt-tid, algoritm för invers power index problem ges av De Keijzer, Klos, och Zhang REF.
Finding optimal solutions for voting game design problems
{'venue': 'J. Artif. Intell. Res.', 'journal': 'J. Artif. Intell. Res.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}