Omröstning är en allmän metod för att samla flera agenters preferenser. Varje agent rankar alla möjliga alternativ, och utifrån detta produceras en aggregerad rangordning av alternativen (eller åtminstone ett vinnande alternativ). Men när det finns många alternativ är det opraktiskt att helt enkelt be agenter att rapportera sina fullständiga preferenser. I stället måste agenternas preferenser, eller åtminstone de relevanta delarna av dem, framkallas. Detta görs genom att fråga agenterna ett (förhoppningsvis litet) antal enkla frågor om deras preferenser, såsom jämförelsefrågor, som ber en agent att jämföra två av alternativen. Tidigare arbete med preferenser vid omröstningar har fokuserat på fall av obegränsade preferenser. Det har visats att i denna inställning är det ibland nödvändigt att fråga varje agent (nästan) så många frågor som skulle krävas för att avgöra en godtycklig rangordning av alternativen. I det här dokumentet fokuserar vi däremot på enkelordade preferenser. Vi visar att sådana preferenser kan framkallas med endast ett linjärt antal jämförelsefrågor, om antingen den ordning med avseende på vilken preferenser är entalt är känd, eller åtminstone en annan agents fullständiga preferenser är kända. Vi visar också att det inte räcker att använda ett sublinjärt antal frågor. Slutligen presenterar vi experimentella resultat.
På motsvarande sätt, Conitzer REF studier hur många jämförelser behöver framkallas från väljare för att kunna rekonstruera sin fullständiga rankning, och visar att antalet är linjär (i motsats till kvadratiska) när preferenser är ental (på linjen).
Eliciting single-peaked preferences using comparison queries
{'venue': "AAMAS '07", 'journal': None, 'mag_field_of_study': ['Computer Science']}