Abstrakt. 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 protokoll 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. Sådana hårdhetsresultat förlorar relevans när antalet kandidater är litet, eftersom manipuleringsalgoritmer som är exponentiella endast i antalet kandidater (och endast något så) kan vara tillgängliga. Vi ger en sådan algoritm för en enskild agent att manipulera Single Transferable Behörighet att göra digitala eller hårda kopior av en del eller allt detta arbete för personligt eller klassrum användning beviljas utan avgift, förutsatt att kopior inte görs eller distribueras för vinst eller direkta kommersiella fördelar och att kopior visar detta meddelande på första sidan eller första skärmen av en display tillsammans med den fullständiga citering. Upphovsrätt till delar av detta verk som ägs av andra än ACM måste hedras. Abstraktering med kredit är tillåten. För att kopiera på annat sätt, för att återpublicera, för att posta på servrar, för att omfördela till listor, eller för att använda någon komponent i detta verk i andra verk krävs förhandsgodkännande och/eller avgift. Behörighet kan begäras från publikationsavdelningen, ACM, Inc., 2 Penn Plaza, Suite 701, New York, NY 10121-0701 USA, fax +1 (212) 869-0481, eller behörigheter@acm.org. Omröstning (STV) protokoll, som har visat sig svårt att manipulera i ovanstående mening. Detta motiverar kärnan i denna artikel, som ger hårdhet resultat för realistiska val där antalet kandidater är en liten konstant (men antalet väljare kan vara stort). Den viktigaste manipuleringsfrågan som vi studerar är koalitionsmanipulering av viktade väljare. (Vi visar att för enklare manipulationsproblem kan manipulation inte vara svårt med få kandidater.) Vi studerar både konstruktiv manipulation (att göra en viss kandidat vinna) och destruktiv manipulation (att göra en viss kandidat inte vinna). Vi karakteriserar det exakta antalet kandidater för vilka manipulation blir svårt för plurality, Borda, STV, Copeland, maximin, veto, plurality med avrinning, regelbundna kopp, och randomiserade kopp protokoll. Vi visar också att hårdhet av manipulation i denna miljö innebär hårdhet av manipulation av en individ i oviktade inställningar när det finns osäkerhet om de andras röster (men inte vice versa). Så vitt vi vet är detta de första resultaten på manipuleringens hårdhet när det råder osäkerhet om de andras röster.
Conitzer m.fl. visade att vid viktade val är problemet med koalitionsmanipulation, som manipuleras av en koalition av väljare, NP-fullständigt även när vi har ett litet konstant antal alternativ för de flesta av de allmänt använda omröstningsreglerna REF.
When are elections with few candidates hard to manipulate?
{'venue': 'JACM', 'journal': None, 'mag_field_of_study': ['Computer Science']}