I Shift Bribery-problemet får vi ett val (baserat på preferensorder), en föredragen kandidat p, och en budget. Målet är att se till att p vinner genom att flytta p högre i vissa väljares preferens order. Varje sådan begäran om förskjutning kommer dock till ett pris (beroende på väljaren och på omfattningen av förskjutningen) och vi får inte överskrida den givna budgeten. Vi studerar den parameteriserade beräknings komplexiteten av Shift Bribery med avseende på ett antal parametrar (med hänsyn till vilken typ av lösning som eftersträvas och storleken på valet) och flera klasser av prisfunktioner. När vi jämför Shift Bribery med antalet drabbade väljare, då för var och en av våra omröstningsregler (Borda, Maximin, Copeland) problemet är W[2]-hård. Om vi istället paraferar med antalet positioner genom vilka p skiftas totalt, då problemet är fast-parameter dragbar för Borda och Maximin, och är W[1]-hård för Copeland. Om vi parameterisera av budgeten, då resultaten beror på prisfunktionen klass. Vi visar också att Shift Bribery tenderar att vara dragbar när parameteriseras av antalet väljare, men att resultaten för antalet kandidater är mer gåtfulla. 1 Till exempel den tyska webbplatsen idealo.de aggregerar olika produkttester genom att först översätta testresultaten till ett enhetligt betygssystem och sedan ta "genomsnitt" av alla betyg. Olika universitetsrankningar utarbetas på ett liknande sätt. Det skulle vara mycket intressant, dock, att använda rankingen själva, i stället för betygen, för aggregering. Dessutom använder Formel 1 racing (och många liknande tävlingar) ren rankning information (t.ex., Formel 1 använder en mycket något modifierad variant av Borda valregeln). 2 Vi antar att vi har kunskap om väljarnas preferensordningar (t.ex. från förhandsundersökningar). Dessutom, i våra exempelinställningar är ofta den fullständiga rankingen känd. Till exempel har en förare som förbereder sig för en ny Formel 1-säsong full kunskap om resultaten från den föregående. 3 Vad "att övertyga" innebär kan variera mycket beroende på ansökan scenario. På den onda sidan har vi mutor, men det kan också betyda saker som produktutveckling, anställa fler fakultetsmedlemmar, utbildning på en viss racingbana, eller förklara detaljerna i ens politiska plattform. Det är uppenbart att olika rankningsleverantörer kan uppskatta olika insatser, som modelleras av de enskilda prisfunktionerna.
Chen och Al. REF anses parametriserad komplexitet Constructive Shift Bribery, och har visat en varierad uppsättning resultat (i allmänhet, parametrisering av antalet positioner som den föredragna kandidaten flyttas tenderar att leda till FPT algoritmer, parametrisering av antalet drabbade väljare tenderar att leda till hårdhet resultat, och parametrisering genom den tillgängliga budgeten ger resultat mellan dessa två ytterligheter).
Prices Matter for the Parameterized Complexity of Shift Bribery
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}