Gibbard-Satterthwaite Theorem säger att (i obegränsade inställningar) alla rimliga röstningsregler är manipulerbara. Nyligen, en kvantitativ version av detta teorem bevisades av Ehud Friedgut, Gil Kalai, och Noam Nisan: när antalet alternativ är tre, för varje neutral röstningsregel som är långt från någon diktatur, det finns en väljare sådan att en slumpmässig manipulation-det vill säga, de sanna preferenser och den strategiska rösten är alla dras i.i.d., enhetligt på måfå-kommer att lyckas med en sannolikhet för 1 n ), där n är antalet väljare. Det verkar dock som om de tekniker som används för att bevisa detta teorem inte helt kan utvidgas till mer än tre alternativ. I detta dokument ger vi ett mer begränsat resultat som gäller för fyra eller fler alternativ. Vi ger ett tillräckligt villkor för att en omröstningsregel ska vara slumpvis manipulerbar med en sannolikhet på 1 n ) för minst en väljare, när antalet alternativ hålls fast. Specifikt, vårt teorem anger att om en omröstning regel r uppfyller 1. homogenitet, 2. anonymitet, 3. non-imposition, 4. ett avbrytande villkor, och 5. det finns en stabil profil som fortfarande är stabil efter en given alternativ är enhetligt flyttas till olika positioner; då finns det en väljare sådan att en slumpmässig manipulation för den väljaren kommer att lyckas med en sannolikhet för 1 n ). Vi visar att många gemensamma omröstningsregler uppfyller dessa villkor, till exempel alla positionsbestämningsregler, Copeland, STV, maximin och rangordnade par.
Med utgångspunkt från olika antaganden visade Xia och Conitzer att en slumpmässig manipulation skulle lyckas med sannolikhet 1 n ) för 3 eller fler kandidater för STV, för 4 eller fler kandidater för någon scoring regel och för 5 eller fler kandidater för Copeland REF.
A sufficient condition for voting rules to be frequently manipulable
{'venue': "EC '08", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}