Vi studerar beräkningsaspekter av tre framträdande röstningsregler som använder godkännandesedlar för att välja flera vinnare. Dessa regler är tillfredsställande godkännanderöstning, proportionell godkännanderöstning och omvägd godkännanderöstning. Vi visar först att computing vinnaren för proportionell godkännanderöstning är NP-hård, avslutar ett långvarigt öppet problem. Eftersom ingen av reglerna är strategiskt säker, även för dikotomiska preferenser, studerar vi olika strategiska aspekter av reglerna. I synnerhet undersöker vi den beräkningsmässiga komplexiteten i att beräkna ett bäst svar för både en enda agent och en grupp av agenter. I många inställningar visar vi att det är NP-hårdt för en agent eller agent att beräkna hur man bäst röstar med en fast uppsättning av godkännanderöster från de andra agenterna.
För varianter av AV inklusive Proportionell godkännanderöstning, tillfredsställande godkännanderöstning, och upprepade godkännanderöstning, komplexiteten i att hitta nyttomaximering röster varierar i komplexitet från lätt till coNP-fullständig REF.
Computational Aspects of Multi-Winner Approval Voting
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}