Beräkningsmässigt socialt val

Computational social choice är ett fält i skärningspunkten mellan sociala valteori , teoretisk datavetenskap och analys av multi-agent system . Den består av analys av problem som uppstår från aggregeringen av preferenser för en grupp agenter ur ett beräkningsperspektiv. I synnerhet handlar det beräkningsmässiga sociala valet om effektiv beräkning av utfall av röstningsregler , med beräkningskomplexiteten hos olika former av manipulation , och frågor som uppstår från problemet med att representera och framkalla preferenser i kombinatoriska miljöer.

Vinnare beslutsamhet

Användbarheten av ett visst röstsystem kan begränsas kraftigt om det tar mycket lång tid att beräkna vinnaren av ett val. Därför är det viktigt att utforma snabba algoritmer som kan utvärdera en röstregel när de ges röstsedlar som input. Som är vanligt inom beräkningskomplexitetsteorin anses en algoritm vara effektiv om den tar polynomtid . Många populära röstningsregler kan utvärderas i polynomtid på ett okomplicerat sätt (dvs. att räkna), såsom Borda- räkningen , godkännandeomröstningen eller pluralitetsregeln . För regler som Schulze-metoden eller rankade par , kan mer sofistikerade algoritmer användas för att visa polynom körtid. Vissa röstningssystem är dock beräkningsmässigt svåra att utvärdera. Framför allt är vinnarbestämningen för Kemeny-Young-metoden , Dodgsons metod och Youngs metod alla NP-hårda problem. Detta har lett till utvecklingen av approximationsalgoritmer och hanteringsbara algoritmer med fasta parametrar för att förbättra den teoretiska beräkningen av sådana problem.

Hårdhet av manipulation

Genom Gibbard-Satterthwaite-teoremet kan alla icke-triviala röstningsregler manipuleras i den meningen att väljarna ibland kan uppnå ett bättre resultat genom att missvisa sina preferenser, det vill säga att de lämnar in en icke-sanningsseddel till röstningssystemet. Socialvalsteoretiker har länge övervägt sätt att kringgå denna fråga, såsom förslaget av Bartholdi, Tovey och Trick 1989 baserat på beräkningskomplexitetsteori. De övervägde andra ordningens Copeland-regel (som kan utvärderas i polynomtid), och bevisade att det är NP-komplett för en väljare att avgöra, givet kunskap om hur alla andra har röstat, om det är möjligt att manipulera i en sådan. sätt att göra någon favoritkandidat till vinnare. Samma egendom gäller för en överlåtbar röst .

Om man antar den allmänt trodda hypotesen att P ≠ NP , finns det tillfällen där polynomtid inte räcker till för att fastställa om en fördelaktig manipulation är möjlig. På grund av detta är röstningsreglerna som kommer med ett NP-hårt manipulationsproblem "resistenta" mot manipulation. Man bör notera att dessa resultat bara gäller det värsta fallet : det kan mycket väl vara möjligt att ett manipulationsproblem vanligtvis är lätt att lösa och kräver bara superpolynomisk tid på mycket ovanliga ingångar.

Andra ämnen

Turneringslösningar

En turneringslösning är en regel som tilldelar varje turnering en uppsättning vinnare. Eftersom en preferensprofil inducerar en turnering genom sin majoritetsrelation , kan varje turneringslösning också ses som en röstregel som endast använder information om resultatet av parvisa majoritetstävlingar. Många turneringslösningar har föreslagits, och teoretiker för beräkningsmässiga sociala val har studerat komplexiteten i de associerade problemen med att fastställa vinnare.

Preferensrestriktioner

Begränsade preferensdomäner, såsom enkeltoppade eller enkelkorsande preferenser, är ett viktigt studieområde inom sociala valteorin , eftersom preferenser från dessa domäner undviker Condorcet-paradoxen och därmed kan kringgå omöjlighetsresultat som Arrows teorem och Gibbard-Satterthwaite-satsen . Ur ett beräkningsperspektiv är sådana domänbegränsningar användbara för att påskynda problem med att fastställa vinnare, både beräkningsmässigt svåra envinnare och flera vinnareregler kan beräknas i polynomtid när preferenser är strukturerade på lämpligt sätt. Å andra sidan tenderar manipulationsproblem också att vara lätta på dessa domäner, så komplexitetsskydd mot manipulation är mindre effektiva. Ett annat beräkningsproblem förknippat med preferensrestriktioner är att känna igen när en given preferensprofil tillhör någon begränsad domän. Den här uppgiften är polynomisk tidslösbar i många fall, inklusive för preferenser med en topp och en korsning, men kan vara svår för mer allmänna klasser.

Flervinnarval

Medan de flesta traditionella röstningsregler fokuserar på att välja en enda vinnare, kräver många situationer att flera vinnare väljs. Detta är fallet när ett parlament eller en kommitté med fast storlek ska väljas, även om röstningsregler för flera vinnare också kan användas för att välja en uppsättning rekommendationer eller faciliteter eller en delad samling av föremål. Arbetet med beräkningsmässigt socialt val har fokuserat på att definiera sådana röstningsregler, förstå deras egenskaper och studera komplexiteten i de associerade vinnarbestämningsproblemen. Se flervinnarröstning .

Se även

externa länkar

COMSOC-webbplatsen erbjuder en samling material relaterat till beräkningsmässiga sociala val, såsom akademiska workshops, doktorsavhandlingar och en e-postlista.