I multiagentinställningar där agenterna har olika preferenser är preferensaggregation en central fråga. Röstning är en allmän metod för aggregering av preferenser, men resultat har visat att alla allmänna omröstningsprotokoll är manipulerbara. Man kan försöka undvika manipulering genom att använda röstningsprotokoll där det är svårt att fastställa en fördelaktig manipulering. Särskilt bland beräkningsagenter är det rimligt att mäta denna hårdhet genom beräkningskomplexitet. Lite tidigare arbete har gjorts på detta område, men man antog att antalet väljare och kandidater är obegränsat. Vi får hårdhetsresultat för praktiska multiagentinställningar där antalet kandidater är litet men antalet väljare kan vara stort. Vi visar att med fullständig information om de andras röster är individuell manipulering lätt, och koalitionsmanipulering är lätt med oviktade väljare. Men konstruktiv koalitionsmanipulering med viktade väljare är oinskränkt för alla de röstprotokoll som studeras, med undantag för den icke-randomized Cup. Destruktiv manipulation tenderar att vara lättare. Randomisering över instantieringar av protokollen (såsom scheman av Cup-protokollet) kan användas för att göra manipulering hårt. Slutligen visar vi att under svaga antaganden, om den viktade koalitionsmanipuleringen med fullständig information om de andras röster är svår i vissa omröstningsprotokoll, då är individuell och ovägd manipulering svår när det råder osäkerhet om de andras röster.
Ett viktigt resultat av REF är att om manipulation för vissa omröstningsregler är svårt när fullständig information tillhandahålls, då är det också svårt att ens utvärdera en kandidats vinnande sannolikhet med detta protokoll när det råder osäkerhet om rösterna.
Complexity of Manipulating Elections with Few Candidates
{'venue': 'Proceedings of the 18th National Conference on Artificial Intelligence (AAAI-02), Edmonton, Canada, 2002', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}