Komplexitetsteori är ett användbart verktyg för att studera beräkningsfrågor som omger framkallandet av preferenser, liksom den strategiska manipuleringen av val aggregera tillsammans preferenser av flera agenter. Vi studerar här komplexiteten i att bestämma när vi kan avsluta frammanande preferenser, och bevisa att komplexiteten beror på framkallningsstrategin. Vi visar till exempel att det kan vara bättre ur ett beräkningsperspektiv att framkalla alla preferenser från en agent i taget än att framkalla individuella preferenser från flera agenter. Vi studerar också sambandet mellan den strategiska manipulationen av ett val och preferenser. Vi visar att det vi kan manipulera påverkar manipuleringens beräkningskomplexitet. I synnerhet bevisar vi att det finns omröstningsregler som är lätta att manipulera om vi kan ändra alla en agents röst, men att vi kan beräkna om vi bara kan ändra en del av deras preferenser. Detta tyder på att, som med förtur framkallar, en finkornig syn på manipulering kan vara informativ. Slutligen studerar vi sambandet mellan att förutsäga vinnaren av ett val och preferenser. Baserat på denna koppling identifierar vi en röstningsregel där det är svårt att beräkna sannolikheten för att en kandidat vinner med tanke på en sannolikhetsfördelning över rösterna.
Walsh REF tar upp frågan om hur man ska bestämma när man ska sluta framkalla preferenser som vinnaren garanteras.
Complexity of Terminating Preference Elicitation
{'venue': 'AAMAS 2008: 967-974', 'journal': None, 'mag_field_of_study': ['Computer Science']}