Practical voting rules with partial information |
| |
Authors: | Meir Kalech Sarit Kraus Gal A Kaminka Claudia V Goldman |
| |
Affiliation: | 1.Information Systems Engineering,Ben-Gurion University,Beer-Sheva,Israel;2.Computer Science Department,Bar-Ilan University,Ramat-Gan,Israel;3.Samsung Telecom Research,Herzliya,Israel |
| |
Abstract: | Voting is an essential mechanism that allows multiple agents to reach a joint decision. The joint decision, representing a
function over the preferences of all agents, is the winner among all possible (candidate) decisions. To compute the winning
candidate, previous work has typically assumed that voters send their complete set of preferences for computation, and in
fact this has been shown to be required in the worst case. However, in practice, it may be infeasible for all agents to send
a complete set of preferences due to communication limitations and willingness to keep as much information private as possible.
The goal of this paper is to empirically evaluate algorithms to reduce communication on various sets of experiments. Accordingly,
we propose an iterative algorithm that allows the agents to send only part of their preferences, incrementally. Experiments
with simulated and real-world data show that this algorithm results in an average of 35% savings in communications, while
guaranteeing that the actual winning candidate is revealed. A second algorithm applies a greedy heuristic to save up to 90%
of communications. While this heuristic algorithm cannot guarantee that a true winning candidate is found, we show that in
practice, close approximations are obtained. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|