Aggregering av motstridiga preferenser är en nyckelfråga i multiagentsystem. På grund av dess universalitet har röstningen en central roll bland mekanismerna för aggregering av preferenser. Röstning bland en uppsättning alternativ kan användas för så olika uppgifter som att välja en gemensam plan i ett multiagentsystem, bestämma en ledare i en grupp av människor eller agenter, eller rösta bland olika resurser eller uppgifter tilldelning. Att bevara integriteten för enskildas röster är av avgörande betydelse för att garantera valfrihet (t.ex. brist på rösträtt och rykteseffekter) och inte underlätta strategiska omröstningar. Vi undersöker om villkorslös full integritet kan uppnås genom röstning, det vill säga integritet som varken är beroende av betrodda tredje parter (eller av en viss del av väljarna som är betrodda), eller av antaganden om intractability (såsom hårdheten i factoring). I synnerhet studerar vi förekomsten av distribuerade protokoll som gör det möjligt för väljarna att gemensamt bestämma resultatet av ett val utan att avslöja någon information förutom valresultatet. Vi visar att det är omöjligt att uppnå ovillkorlig full integritet för en mängd av de vanligaste omröstningssystemen, allt från enkel vetoröstning till ett enda system med överförbara röster. På den positiva sidan föreslår vi flera distribuerade protokoll som privat beräknar resultatet av gemensamma omröstningssystem och endast avslöjar en begränsad mängd information.
I detta avseende erinrar vi om ett grundläggande resultat av Brandt och Sandholm REF som visade att en sådan perfekt sekretess måste vara beroende av antingen betrodda tredje parter eller av beräkningsmässiga intractability-antaganden (såsom hårdheten i factoring, vilket är det intractability antagande som Pallier chiffer säkerhet bygger på).
Decentralized voting with unconditional privacy
{'venue': "AAMAS '05", 'journal': None, 'mag_field_of_study': ['Computer Science']}