We study the problem of designing a distributed voting scheme for electing a candidate that maximizes the preferences of a set of agents. We assume the preference of agent i for candidate j is a real number xi,j, and we do not make any assumptions on the mecha- nism generating these preferences. We show simple randomized voting schemes guaranteeing the election of a candidate whose expected total preference is nearly the highest among all candidates. The algorithms we consider are designed so that each agent has to disclose only a few bits of information from his preference table. Finally, in the impor- tant special case in which each agent is forced to vote for at most one candidate we show that our voting scheme is essentially optimal. Mathematics Subject Classification. 68W15, 91B12.
['Peter Auer', 'Nicolò Cesa-Bianchi']
A distributed voting scheme to maximize preferences