Vi studerar komplexiteten i en kombinatorisk variant av Shift Bribery-problemet i valet. I standard Shift Bribery-problemet får vi ett val där varje väljare har en preferensordning framför kandidaten och där en utomstående agent, mutaren, kan betala varje väljare för att ranka mutarens favoritkandidat ett givet antal positioner högre. Målet är att se till att mutarens föredragna kandidat vinner. Den kombinatoriska varianten av problemet, som introduceras i detta dokument, modellerar inställningar där det är möjligt att påverka positionen för den föredragna kandidaten i flera röster, antingen positivt eller negativt, med en enda muta åtgärder. Denna variant av problemet är särskilt intressant i samband med storskaliga kampanjhanteringsproblem (som ur teknisk synvinkel är modellerade som mutor). Vi visar att i allmänhet är den kombinatoriska varianten av problemet mycket svåråtkomlig (NP-hård, hård i parameteriserad betydelse, och svår att approximera), men vi tillhandahåller några (ungefärlig) algoritmer för naturliga begränsade fall.
En utvidgning av deras modell REF gör det möjligt för kampanjansvariga att påverka den föredragna kandidatens ställning vid flera omröstningar, antingen positivt eller negativt, med en enda bestickningsåtgärd, som gäller storskaliga kampanjer.
Large-Scale Election Campaigns: Combinatorial Shift Bribery
{'venue': 'J. Artif. Intell. Res.', 'journal': 'J. Artif. Intell. Res.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}