Röstning är en allmän metod för aggregering av preferenser i multiagentinställningar, men seminala resultat har visat att alla (icke-diktatoriska) röstningsprotokoll är manipulerbara. Man kan försöka undvika manipulering genom att använda röstningsprotokoll där det är svårt att beräkna en fördelaktig manipulering. I flera av de senaste dokumenten studeras komplexiteten i att manipulera befintliga protokoll. Detta papper är det första arbetet att ta nästa steg för att utforma nya protokoll som är särskilt svåra att manipulera. I stället för att utforma dessa nya protokoll från grunden, visar vi istället hur man justerar befintliga protokoll för att göra manipulering hårt, samtidigt som mycket av den ursprungliga karaktären av protokollet är intakt. Den tweak studerade består av att lägga en eliminering preround till valet. Förvånansvärt nog gör denna extremt enkla och universella tweak typiska protokoll svåra att manipulera! Protokollen blir NP-hårda, #P-hårda, eller PSPACE-hårda att manipulera, beroende på om schemat för preround bestäms innan rösterna samlas in, efter att rösterna samlas in, eller schemaläggningen och röstinsamlingen är interleading, respektive. Vi bevisar att de allmänna villkoren för protokollen för denna tweak är tillräckliga för att införa hårdheten, och visar att de vanligaste omröstningsprotokollen uppfyller dessa villkor. Dessa är de första resultaten i röstningsinställningar där manipulering är i en högre komplexitet klass än NP (förutsatt PSPACE = NP).
Conitzer och Sandholm REF undersökte effekterna på den beräkningsmässiga komplexiteten av manipulering genom att lägga till en första omgång av Cup-regeln till en röstningsregel.
Universal Voting Protocol Tweaks to Make Manipulation Hard
{'venue': 'In Proceedings of the 18th International Joint Conference on Artificial Intelligence (IJCAI-03), Acapulco, Mexico, 2003', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}